一种用于反编译代码与源代码的比较算法.doc

一种用于反编译代码与源代码的比较算法.txt-你脚踏俩只船,你划得真漂亮。-每个说不想恋爱的人心里都装着一个不可能的人。我心疼每一个不快乐却依然在笑的孩子。(有没有那么一个人，看透我在隐身，知道我在等人。 本文由叶紫孤贡献 pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 第 35 卷 Vol.35 第4期 No.4 计 算 机 工 程 Computer Engineering 文章编号:10003428(2009)04003803 文献标识码:A 2009 年 2 月 February 2009 中图分类号:TP311.5 软件技术与数据库 一种用于反编译代码与源代码的比较算法 曹孟春,陈凯明 (中国科学技术大学计算机科学技术系,合肥 230027) 摘 要:现有反编译器产生的代码与对应的源代码之间存在差异,找到并理解差异有助于改进并完善反编译器的设计.该文给出一种适用 于 C 语言反编译代码与源代码的比较算法. 该算法以语法树匹配方法为基础, 定义新的 C 语言中间代码表示形式并对表达式进行动态匹配, 提高了语法树匹配的准确性.实验结果表明,该算法能有效计算出反编译代码与源代码之间的多数差异. 关键词:反编译代码;源代码;比较算法;中间代码;动态表达式匹配 Differencing Algorithm for Decompilation Code and Source Code CAO Meng-chun, CHEN Kai-ming (Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027) 【Abstract】There are many differences between the codes produced by existing decompilers and the corresponding source codes. To find and understand these differences can help to improve and refine the design of decompiler. This paper presents a differencing algorithm for decompilation code and source code of a C program. This algorithm is based on syntax tree matching method. A new C program intermediate representation is defined and a dynamic expression matching method is proposed to improve the accuracy of the syntax tree matching method. Experimental results show that this algorithm is able to find out most differences between decompilation code and source code. 【Key words】decompilation code; source code; differencing algorithm; intermediate code; dynamic expression matching 1 反编译技术用于将可执行程序转换为等价的高级语言代 码,是软件逆向工程的重要研究领域之一,它在可执行程序 移植 1,软件安全性分析 2,软件复用 3等方面具有极大应用 价值.而现有反编译器产生的代码(简称反编译代码)与对应 的源代码之间仍然存在很多差异,应找到并理解这些差异. 目前已有很多比较分析高级语言代码的工具,如 Unix 下的 diff,它使用 LCS(Longest Common Sequence)算法获得 2 个程序文件间以行为单位的文本差异.该方法简单快速, 但其基于文本的比较结果很难被理解.文献4将程序表示成 依赖图的形式,试图比较程序间语义上的差别,但由于语义 比较的不可判定性,因此该纯粹的语义比较方法只能用于有 限的 C 语言子集程序,例如不能有全局变量,指针,数组和 函数等. 程序由文法描述,具有严格语法结构的文本将程序解析 成语法树形式.通过匹配语法树上对应的语法节点来计算程 序间语法上的差异,能提供比文本差异更精确且易于理解的 比较结果,并避免对需要比较的程序作出过多限制 5. 本文提出一种基于语法树匹配的算法,在 CIL6 的基础 上定义了一种新的 C 语言中间代码表示形式 ECIL(Enhanced CIL).将程序转换成 ECIL 能有效减少程序间与语义无关的 语法差异,提高比较结果的准确性. 概述 return 1; else return fibo(n-1)+fibo(n-2) ; 反编译代码: int proc_1(int arg1) int loc1,loc2; loc1=arg1; if(loc1=1|loc1=0) loc2=1; if(loc1!=1) if(loc1!=0) loc1-; loc2=proc_1(loc1); loc2+=proc_1(loc1); return loc2; 在上述代码中, 一段计算 Fibonacci 数的源代码可能只是 一个 if-else 语句,而对应的反编译代码却包含了一个赋值语 句,2 个 if 语句和一个 return 语句.将程序转换成中间代码 能有效减少上述差异.因此,本文在 CIL 的基础上定义了一 种新的中间代码表示形式 ECIL,其主要语法结构如下: func := Func(stmt list) stmt := Loop(stmt list) | Instr(instr list) | Goto (stmt) instr:= Set(lvalue, exp) | Call(lvalue option, exp, exp list) 基金项目:国家自然科学基金资助项目(60573140) 作者简介:曹孟春(1983-),男,硕士研究生,主研方向:软件逆向 工程;陈凯明,副教授 收稿日期:2008-07-18 E-mail: | If(exp, stmt list) | Return(exp option) 2 源代码中的语句和表达式一般比反编译代码中的复杂且 紧凑.源代码与对应的反编译代码示例如下: 源代码: int fibo(int n) if(n=1|n=0) 程序的 ECIL 表示 38 ECIL 将 每 个 函 数 (func) 视 为 一 个 有 序 语 句 序 列 (stmt list),并进一步简化 CIL 中语句(stmt)的语法结构,将原先的 if(exp, stmt list, stmt list)简化成 if(exp, stmt list). ECIL 中不存 在传统 if-else 结构,而是利用表达式复制将它转化成 2 个并 列的 if 结构.利用类似的方法将 switch 转化为 if 结构,用 Goto 消除 Break 和 Continue 语句. 上述示例中源代码与反编译代码的 ECIL 表示如下: 源代码: int fibo(int n) int tmp1, tmp2, newVar ; if(n=1|n=0) newVar=1 ; if(!(n=1|n=0) tmp1=fibo(n-1) ; tmp2=fibo(n-2) ; newVar=tmp1+tmp2 ; L1: return newVar ; 反编译代码: int proc_1(int arg1) int loc1, loc2,tmp1 ; loc1=arg1; if(loc1=1| loc1=0) loc2=1 ; if(loc1!=1&loc1!=0) loc1- ; loc2=proc_1(loc1) ; tmp1=proc_1(loc1) ; loc2=tmp1+loc2 ; L1: return loc2 ; 基于相似度的语法树匹配 对给定的 2 棵语法树,如图 1 所示,匹配算法最终会得 到一个反映节点间匹配关系的节点对集合,称为这 2 棵语法 树间的一个匹配.每对匹配的节点来自不同语法树,并满足 如下条件:(1)语法树中任意一个节点最多只能出现在一个节 点对中;(2)2 个匹配节点具有相同的语法类型,且叶子节点 间的相似度不为 0;(3)只有父节点匹配,其子节点才能匹配. 3.2 1 if 2 Call 3 Call 4 Set 5 6 7 8 9 10 11 12 (a)源代码 (b)反编译代码 图1 语法树 兄弟节点间的匹配是有序的,例如,若 A1 匹配 B1,A2 匹配 B2 且 A1 和 A2 是兄弟节点,则 B1 和 B2 也是兄弟节点, A1 在 A2 前当且仅当 B1 在 B2 前. 在所有满足条件的匹配中,含有节点对最多的匹配称为 最佳匹配.计算 2 棵语法树 A 和 B 之间最佳匹配的 Best_Matching 算法代码如下: Best_Matching (A, B,sim) if A and B have different syntactic types then return (0,). if A and B are both leaf nodes then if sim(A,B)=0 then return (0,) else return (sim(A,B),(A,B) As first level nodes are (A1,A2,Am) Bs first level nodes are (B1,B2,Bn) Initialization. Mi,0=0,for i=0,m N0,j=0,for j=0,n for i:=0 to m do for j:=0 to n do (Wi,j,Matches):=bestMatching(Ai,Bj) Mi,j:= max(Mi-1,j, Mi,j-1, Mi-1,j-1+Wi,j) if Mi-1,j+Wi,j is the maximum one then add (Ai,Bj) into Matches od od return(Mm,n, Matches) 可以看出,ECIL 减小了两者在语句和表达式上的差异, 并使其语法结构更相似,从而有效降低了对它们进行比较分 析的难度. 3 3.1 比较算法 动态的表达式匹配 传统语法树匹配算法都是静态的,程序的语法树一旦建 立就不再变化.静态方法忽略了一些语义上仍然等价的表达 式,尤其在比较反编译代码和源代码时.例如,上述源代码 ECIL 表示中的条件表达式!(n=1|n=0)与对应的反编译代码 条件表达 loc1!=1&loc1!=0 的语法结构不同, 但有相同语义, 静态匹配方法对此不能作出正确判断. 动态表达式匹配是通过建立表达式间的等价转换表来实 现的.在比较对应的表达式时,如果它们在语法上不完全匹 配,则逐个比较它们是否符合表中的某个等价形式,如果符 合则进行等价转换,并继续比较子表达式,否则标记为不等 价.例如,条件表达式 e1 和 e2 的等价转换形式如表 1 所示. 按表中的等价形式,!(n=1|n=0)只要经过 2 次转换就能得 到与 loc1!=1&loc1!=0 相同的语法结构. 表1 e1 !(a|b) !(ab) !(a=b) !(a=b) 条件表达式 e1 和 e2 的等价转换形式 e2 !a&!b a=b ab e1 !(a&b) !(a=b) !(a!=b) a a e2 !a|!b a!=b a=b a!=0 !a 将语法树的叶子节点限定为 ECIL 的表达式(exp)类型, 就能使用动态表达式匹配函数 sim 作为计算叶子节点间的相 似度函数.例如,对于 2 个表达式 e1 和 e2,如果 e1 和 e2 是动态匹配的,则 sim(e1,e2)=1,否则 sim(e1,e2)=0.对需要 匹配的每层节点,算法采用类似 LCS 的动态规划方法进行比 较,并返回含有所有匹配表达式的节点集合 Matches. 考虑图 1 中的 2 课语法树,它们表示 ECIL 表示示例中 反编译代码和源代码第 2 个 if 语句.其中标出了第 2 层节点 的语法类型,包括赋值语句(Set)和函数调用语句(Call),第 3 层 节点则全是表达式类型(exp).例如,节点 2 对应语句 tmp1= fibo(n-1),节点 5节点 7 分别对应表达式 tmp1,fibo 和 n-1. 39 算法 Best_Matching 递归地计算出各个节点间的对应关 系,它首先匹配根节点 1 和 13,然后处理第 2 层节点,图 2 给出了它们间的相似度,例如,节点 2 和节点 14 间的语法类 型不同,因此它们间的相似度为 0,但它同节点 15 有相同的 语法类型, 且以节点 2 和节点 15 为根的语法树间共有 3 对匹 配的节点,分别为(2,15),(5,20),(6,21),因此它们间的相似 度为 3,节点 7 和节点 22 不能匹配,因为对应的表达式 n-1 和 loc1 不能动态地匹配(实际上也不能静态地匹配).同理, 节点 2 同节点 16 间的相似度为 3, 同节点 17 间的相似度为 0. 最终,在所有的匹配组合中,(2,15), (3,16), (4,17), (5,20), (6,21), (8,23), (9,24), (11,26), (12,27) 是满足上述匹配条件的 最佳匹配. 节点 14 节点 2 节点 3 节点 4 0 0 2 节点 15 3 3 0 节点 16 3 3 0 节点 17 0 0 3 对应的反编译代码后,手工检查 SDdiff 的比较结果. 表 2 给 出 了 本 文 比 较 算 法 在 dcc7, DECLER8 和 Boomerang9这 3 个反编译器上的实验结果, 可以看出, SDdiff 正确分析出约 83%的重命名,且在所有语法差异中,语义差 异占 70%. 表2 反编译器 dcc DECLER Boomerang - 本文比较算法在不同反编译器上的实验结果 Item Type 变量名 差异 变量名 差异 变量名 差异 平均值 平均值 对应关系 288 376 308 294 255 317 283 329 All Items 343 453 343 367 343 582 343 467 准确率 /(%) 84 83 90 80 74 54 83 70 5 图2 Best_Matching 算法中第 2 层节点间的相似度 由 Best_Matching 算法可以看出,在最坏情况下,该算 法的时间复杂度为 O(mn),其中,m 和 n 为语法树 A 和 B 的 节点总数. 4 在 CIL 系统的基础上用 OCaml 语言实现一个比较工具 SDdiff,SDdiff 拥有类似编译器的接口,接收 C 语言反编译 代码和对应的源代码作为输入,输出它们之间的名字对应关 系和差异统计结果.例如,对于 ECIL 表示示例中的反编译 代码与源代码,SDdiff 输出的比较结果如下: fibo n tmp2 fibo vs proc_1 arg1, loc1 loc2 proc_1 tmp1 Names mapping : tmp1, newVar 实验结果分析 大部分现有程序比较方法都针对多个版本的程序,不适 用于比较反编译代码和源代码.而本文算法能同时进行重命 名分析和差异比较. 现有动态表达式匹配必须建立一个等价转换表,当需要 进行等价转换的表达式数量逐渐增多时,转换表会变得很复 杂,将难以管理并影响算法速度.因此,研究一个有效的等 价转换机制是笔者下一步工作的重点之一. 参考文献 1 Sites R L, Chernoff A, Kirk M B, et al. Binary TranslationJ. Digital Technical Journal, 1992, 4(4): 69-81. 2 Cifuentes C, Waddington T, Emmerik M V. Computer Security Analysis Through Decompilation and High-level DebuggingC/ Proceedings of WCRE01. Stuttgart, Germany: IEEE Computer Society Press, 2001: 375-380. 3 Emmerik M V, Waddinton T. Using a Decompiler for Real-world Source RecoveryC/Proceedings of WCRE04. Delft, Netherlands: IEEE Computer Society Press, 2004: 27-36. 4 Horwitz S. Identifying the Semantic and Textual Differences Between Two Version of a ProgramC/Proceedings of PLDI90. New York, USA: ACM Press, 1990: 234-245. 5 Kim M, Notkin D. Program Element Matching for Multi-version Program AnalysisC/Proceedings of the 3rd International Workshop on Mining Software Repositories. Shanghai, China: ACM Press, 2006: 58-64. 6 Necula G C, McPeak S, Rahul S P, et al. CIL: Intermediate Language and Tools for Analysis and Transformation of C ProgramsJ. Lecture Notes in Computer Science, 2002, 2304: 213-228. 7 Cifuente