本文由叶紫孤贡献pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。第35卷Vol.35第4期No.4计算机工程ComputerEngineering文章编号:1000—3428(2009)04—0038—03文献标识码:A2009年2月February2009中图分类号:TP311.5软件技术与数据库一种用于反编译代码与源代码的比较算法曹孟春,陈凯明(中国科学技术大学计算机科学技术系,合肥230027)摘要:现有反编译器产生的代码与对应的源代码之间存在差异,找到并理解差异有助于改进并完善反编译器的设计.该文给出一种适用于C语言反编译代码与源代码的比较算法.该算法以语法树匹配方法为基础,定义新的C语言中间代码表示形式并对表达式进行动态匹配,提高了语法树匹配的准确性.实验结果表明,该算法能有效计算出反编译代码与源代码之间的多数差异.关键词:反编译代码;源代码;比较算法;中间代码;动态表达式匹配DifferencingAlgorithmforDecompilationCodeandSourceCodeCAOMeng-chun,CHENKai-ming(DepartmentofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230027)【Abstract】Therearemanydifferencesbetweenthecodesproducedbyexistingdecompilersandthecorrespondingsourcecodes.Tofindandunderstandthesedifferencescanhelptoimproveandrefinethedesignofdecompiler.ThispaperpresentsadifferencingalgorithmfordecompilationcodeandsourcecodeofaCprogram.Thisalgorithmisbasedonsyntaxtreematchingmethod.AnewCprogramintermediaterepresentationisdefinedandadynamicexpressionmatchingmethodisproposedtoimprovetheaccuracyofthesyntaxtreematchingmethod.Experimentalresultsshowthatthisalgorithmisabletofindoutmostdifferencesbetweendecompilationcodeandsourcecode.【Keywords】decompilationcode;sourcecode;differencingalgorithm;intermediatecode;dynamicexpressionmatching1反编译技术用于将可执行程序转换为等价的高级语言代码,是软件逆向工程的重要研究领域之一,它在可执行程序移植[1],软件安全性分析[2],软件复用[3]等方面具有极大应用价值.而现有反编译器产生的代码(简称反编译代码)与对应的源代码之间仍然存在很多差异,应找到并理解这些差异.目前已有很多比较分析高级语言代码的工具,如Unix下的diff,它使用LCS(LongestCommonSequence)算法获得2个程序文件间以行为单位的文本差异.该方法简单快速,但其基于文本的比较结果很难被理解.文献[4]将程序表示成依赖图的形式,试图比较程序间语义上的差别,但由于语义比较的不可判定性,因此该纯粹的语义比较方法只能用于有限的C语言子集程序,例如不能有全局变量,指针,数组和函数等.程序由文法描述,具有严格语法结构的文本将程序解析成语法树形式.通过匹配语法树上对应的语法节点来计算程序间语法上的差异,能提供比文本差异更精确且易于理解的比较结果,并避免对需要比较的程序作出过多限制[5].本文提出一种基于语法树匹配的算法,在CIL[6]的基础上定义了一种新的C语言中间代码表示形式ECIL(EnhancedCIL).将程序转换成ECIL能有效减少程序间与语义无关的语法差异,提高比较结果的准确性.概述return1;elsereturnfibo(n-1)+fibo(n-2);反编译代码:intproc_1(intarg1){intloc1,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);returnloc2;}}}在上述代码中,一段计算Fibonacci数的源代码可能只是一个if-else语句,而对应的反编译代码却包含了一个赋值语句,2个if语句和一个return语句.将程序转换成中间代码能有效减少上述差异.因此,本文在CIL的基础上定义了一种新的中间代码表示形式ECIL,其主要语法结构如下:func::=Func(stmtlist)stmt::=Loop(stmtlist)|Instr(instrlist)|Goto(stmt)instr::=Set(lvalue,exp)|Call(lvalueoption,exp,explist)基金项目:国家自然科学基金资助项目(60573140)作者简介:曹孟春(1983-),男,硕士研究生,主研方向:软件逆向工程;陈凯明,副教授收稿日期:2008-07-18E-mail:cmc84@mail.ustc.edu.cn|If(exp,stmtlist)|Return(expoption)2源代码中的语句...