基于进化计算的源代码同源性分析
摘要
随着互联网和软件行业的蓬勃发展,软件和程序间的抄袭情况日益严重,抄袭与反抄袭技术的斗争愈演愈烈,因此同源性分析的重要性不言而喻。目前,源代码的同源性分析手段一般有以下三种或它们的不同组合：基于文本的、基于令牌的和基于语法树的。在实际应用中,基于语法树的方法起着主导作用,也被众多商业软件吸收和采纳。
但是,基于语法树的比对方法有其自身致命的缺陷,因为比对判断完全依据语法树节点哈希值的相等判断,也就是说,两棵语法树同源与否是一个“是-非”问题,不存在中间状态,所以不能解决内部语法结构的相似问题。
本文提出一种基于进化计算的方式来解决同源性分析问题,先对程序源代码进行预处理,得到中间代码后进行词法和语法分析,存储源码的语法结构信息。然后对语法分析之后的结果进行编码,建立程序之间的节点初始对应关系,通过AHP综合层次分析方法得到适应度函数,然后利用遗传算法的交叉和变异进行匹配求解,最终得到相似关系和相似程度。该方法在寻求完全相等节点的同时,也能找到可能的相似关系,弥补了经典语法比对方式的不足。
With the rapid development of Internet and software industry, software and program plagiarism is becoming more and more serious, and so is the struggle of plagiarism and anti-plagiarism technology. Therefore, the homology analysis is obviously important. Nowadays, homology analysis of the source code means generally three ways or their different combinations:text-based, token-based, and the syntax tree-based. In practical applications, the syntax tree-based method plays a leading role, and has also been absorbed and adopted by most commercial software.
However, the syntax tree-based method has its own fatal flaw, because comparison solely on the basis of an equality of the syntax tree node's hash value, that's to say, two syntax tree are homologous or not is a "Yes-No" problem, and there is no intermediate state, so it cannot solve the problem of internal syntactic structure similarity.
This paper proposed a way to solve the problem of homologous analysis based on the evolutionary computation method. Firstly, we pretreat the source code of program, and we take lexical and syntax analysis after getting the intermediate code, and store the grammatical structure information of source code. After encoding the result of syntax analysis, we try to establish an initial relationship between syntax nodes of programs. And finally get the similarity relation and similarity degree between programs using crossover and mutation of genetic algorithm to solve the final matching and with the help of AHPto find a probable fitness function.
但是,基于语法树的比对方法有其自身致命的缺陷,因为比对判断完全依据语法树节点哈希值的相等判断,也就是说,两棵语法树同源与否是一个“是-非”问题,不存在中间状态,所以不能解决内部语法结构的相似问题。
本文提出一种基于进化计算的方式来解决同源性分析问题,先对程序源代码进行预处理,得到中间代码后进行词法和语法分析,存储源码的语法结构信息。然后对语法分析之后的结果进行编码,建立程序之间的节点初始对应关系,通过AHP综合层次分析方法得到适应度函数,然后利用遗传算法的交叉和变异进行匹配求解,最终得到相似关系和相似程度。该方法在寻求完全相等节点的同时,也能找到可能的相似关系,弥补了经典语法比对方式的不足。
With the rapid development of Internet and software industry, software and program plagiarism is becoming more and more serious, and so is the struggle of plagiarism and anti-plagiarism technology. Therefore, the homology analysis is obviously important. Nowadays, homology analysis of the source code means generally three ways or their different combinations:text-based, token-based, and the syntax tree-based. In practical applications, the syntax tree-based method plays a leading role, and has also been absorbed and adopted by most commercial software.
However, the syntax tree-based method has its own fatal flaw, because comparison solely on the basis of an equality of the syntax tree node's hash value, that's to say, two syntax tree are homologous or not is a "Yes-No" problem, and there is no intermediate state, so it cannot solve the problem of internal syntactic structure similarity.
This paper proposed a way to solve the problem of homologous analysis based on the evolutionary computation method. Firstly, we pretreat the source code of program, and we take lexical and syntax analysis after getting the intermediate code, and store the grammatical structure information of source code. After encoding the result of syntax analysis, we try to establish an initial relationship between syntax nodes of programs. And finally get the similarity relation and similarity degree between programs using crossover and mutation of genetic algorithm to solve the final matching and with the help of AHPto find a probable fitness function.
引文
[1]陈月玲,贾小珠.基于程序语义的汁算机病毒检测方法[J].青岛大学学报,2007,(1)：74-77.
[2]杜之韩,涂晓青.化广义判断矩阵问题为普通判断矩阵问题[J].数学的实践与认识,2005,(3)：187-190.
[3]傅卓军,龙陈锋.网络安全漏洞检测软件的设计与实现[J].计算机与数字工程,2011,(7)：117-119.
[4]宫文峰,黄美发.逆向工程技术的应用与研究[J].机械设计与制造,2013,(1)：110-112.
[5]郭婧,吴军华.基于程序依赖图的克隆检测及改进[J].计算机工程与设计,2012,(2)：595-600.
[6]侯文永,徐志宏.通过表达式演算局部优化中间代码[J].上海交通大学学报,1996,(6)：71-75.
[7]黄德才,李秉焱.AHP中群决策的几何平均超传递近似法[J].控制与决策,2012,(5)：797-800.
[8]琚洁慧.改进适应度函数的遗传算法[J].电脑知识与技术,2005,(15)：80-83.
[9]阚能琪.软件纠错技术研究[J].四川工业学院学报,2003,(1)：56-58.
[10]康道坤,陈劲，黄永.AHP中判断矩阵一致性检验的几种统计方法比较[J].吉林省教育学院学报,2011,(10)：46.48.
[11]李书全,孙雪,孙德辉,等.遗传算法中的交叉算子的述评[J].计算机工程与应用,2012,(1)：36.39.
[12]李旭东.计算机程序抄袭检测系统的设计方案[J].电脑知识与技术,2012,(4)：799-800.
[13]李昭智.NP.完全问题浅谈[J].天津理工学院学报,1984,(1)：27-34.
[14]连瑞琦,吴承勇,张兆庆.代码优化与指令调度的集成[J].计算机学报,2001,(7)：694-701.
[15]梁正平,程一群，谭佳加,等.软件克隆检测技术研究[J].计算机应用研究,2012,(5)：1623-1627.
[16]梁中兴,罗贵明,旷宏斌.基于CEGAR偏序化简的并行程序死锁检测[J]，计算机工程,2009,(19)：65-68.
[17]廖宇力.基于遗传算法的排课问题适应度函数设计[J].现代计算机,2010,(4)：53-57.
[18]刘春燕,赖晓晨,周宽久,等.基于关系语法树的C／C++代码静态检测方法研究[J].计算机工程与设计,2011,(8)：2879-2884.
[19]刘东波,高春鸣.采用二叉树编码的遗传算法实现数据拟合[J].数学理论与应用,2002,(1)：32-35.
[20]佘党恩.数字指纹技术及其在软件版权保护中的应用研究[D].武汉：华中科技大学,2007：
[21]王发鸿,周会平,贾丽丽,等.基于GCC的容错编译器的研究与实现[J].计算机工程与科学,2011,(8)：89-94.
[22]王嘉锡.计算机软件安全漏洞的法律规制探讨[J].信息网络安全,2009,(5)：59-61.
[23]于鹏飞,吕鹏淦.软件缺陷的评估方法分析与研究[J].计一算机时代,2009,(7)：4-5.
[24]王甜甜.结构语义相似的程序识别方法研究[D].哈尔滨：哈尔滨工业大学,2009：
[25]王伟,杨庚,张迎周,等.基于程序切片和服务构件的语义Web服务组合[J].计算机技术与 发展,2011.(11)：141-144.
[26]王秀芳,孙承爱,路燕.C语言中编译预处理命令的解读与应用[J].电脑编程技巧与维护,2010,(22)：22-24.
[27]王志伟,平玲娣,陆敏锋.高效字符匹配算法的研究[J].计算机工程与应用,2010,(1)：28-31.
[28]许佳卿,彭鑫,赵文耘.一种基于模糊概念格和代码分析的软件演化分析方法[J].计算机学报,2009,(9)：1832-1844.
[29]颜昌学,杨颖.一种新的代码优化的方法[J].武汉科技学院学报,2001,(3)：010.
[30]于‘海英,赵俊岚.最长公共子序列算法在程序代码相似度度量中的应用[J].内蒙古大学学报,2008,(2)：225-229.
[31]于世英,袁雪梅,卢海涛,等.基于序列聚类的相似代码检测算法[J].智能系统学报,2013,8(1)：1-7.
[32]余有明,刘玉树,阎光伟.遗传算法的编码理论与应用[J].计算机工程与应用,2006,(3)：86-89.
[33]袁彩虹,薛光,张连堂.语义分析和中间代码产生教学过程研究[J].计算机教育,2008,(9)：59-60.
[34]袁桂霞.改进的交叉算子在遗传算法中的研究及应用[J].江苏广播电视大学学报,2011,(5)：54-57.
[35]张平,马骁.开源软件对知识产权制度的批判与兼容(二)一一开源软软许可证的比较研究[J].科技与法律,2004,(2)：46-58.
[36]张志春,雷相波.YACC中的冲突消解方法[J].哈尔滨师范大学自然科学学报,2002,(4)：40-43.
[37]赵克佳,沈志宇.一种分程序结构符号表的组织方法[J].计算机工程与设计,1996,(3)：42-50.
[38]钟美,张丽萍,刘东升.基于XML的C代码抄袭检测算法[J].计算机工程与应用,2011,(8)：215-218.
[39]朱朝霞.编译器词法分析程序实现探讨[J].长春工程学院学报,2011,(4)：132-134.
[40]朱立新,吕莉,于兰.软件开发有力工具YACC的剖析[J].哈尔滨科学技术大学学报,1987，,(2)：59-64.
[41]Baxter I, Yahin A, Moura L, et al. Clone Detection Using Abstract Syntax Trees[J],1998, (11): 368-377.
[42]Falke R, Frenzel P, Koschke R. Empirical evaluation of clone detection using syntax suffix trees[J]. Empirical Software Engineering,2008,13(6):601-643.
[43]Fogel L J, Owens A J, Walsh M J. Artificial Intelligence Through Simulated Evolution[M]. New York:John Wiley & Sons, Inc,1966:38-45.
[44]J H, L. Adaptation in natural and artificial systems[M]. Michigan:University of Michigan Press, 1975:12-16.
[45]Jos L, Bonifacio L. Agg regation of fuzzy preferences:some rules of the mean[J]. Soc Choice Welfare,2000,17(4):673-690.
[46]Kamiya T, Kusumoto S, Inoue K. CCFinder:a multilinguistic token-based code clone detection system for large scale source code[J]. Software Engineering, IEEE Transactions on,2002,28(7): 654-670.
[47]Koza J R. Genetic Programming:On the Programming of Computers by Means of Natural Selection[M]. Boston:MIT Press,1992:1-5.
[48]Rechenberg I. Evolutionsstrategie:Optimierung technischer Systeme nach Prinzipien der biologischen Evolution[M]. Stuttgart:Frommann-Holzboog,1973:2-8.
[49]Saaty, T, L. The analytic hierarchy process[M]. University of California:Mcgraw-Hill,1980:1-10.
[50]Schwefel H P. Evolution and Optimum Seeking[M]. New York:John Wiley,1995:1-23.
[51]Z L, S L, S M, et al. CP-Miner:a tool for finding copy-paste and related bugs in operating system code[J]. Proceeding of the 2004 symposium on operating systems design and implementation, 2004,(6):289-302
[2]杜之韩,涂晓青.化广义判断矩阵问题为普通判断矩阵问题[J].数学的实践与认识,2005,(3)：187-190.
[3]傅卓军,龙陈锋.网络安全漏洞检测软件的设计与实现[J].计算机与数字工程,2011,(7)：117-119.
[4]宫文峰,黄美发.逆向工程技术的应用与研究[J].机械设计与制造,2013,(1)：110-112.
[5]郭婧,吴军华.基于程序依赖图的克隆检测及改进[J].计算机工程与设计,2012,(2)：595-600.
[6]侯文永,徐志宏.通过表达式演算局部优化中间代码[J].上海交通大学学报,1996,(6)：71-75.
[7]黄德才,李秉焱.AHP中群决策的几何平均超传递近似法[J].控制与决策,2012,(5)：797-800.
[8]琚洁慧.改进适应度函数的遗传算法[J].电脑知识与技术,2005,(15)：80-83.
[9]阚能琪.软件纠错技术研究[J].四川工业学院学报,2003,(1)：56-58.
[10]康道坤,陈劲，黄永.AHP中判断矩阵一致性检验的几种统计方法比较[J].吉林省教育学院学报,2011,(10)：46.48.
[11]李书全,孙雪,孙德辉,等.遗传算法中的交叉算子的述评[J].计算机工程与应用,2012,(1)：36.39.
[12]李旭东.计算机程序抄袭检测系统的设计方案[J].电脑知识与技术,2012,(4)：799-800.
[13]李昭智.NP.完全问题浅谈[J].天津理工学院学报,1984,(1)：27-34.
[14]连瑞琦,吴承勇,张兆庆.代码优化与指令调度的集成[J].计算机学报,2001,(7)：694-701.
[15]梁正平,程一群，谭佳加,等.软件克隆检测技术研究[J].计算机应用研究,2012,(5)：1623-1627.
[16]梁中兴,罗贵明,旷宏斌.基于CEGAR偏序化简的并行程序死锁检测[J]，计算机工程,2009,(19)：65-68.
[17]廖宇力.基于遗传算法的排课问题适应度函数设计[J].现代计算机,2010,(4)：53-57.
[18]刘春燕,赖晓晨,周宽久,等.基于关系语法树的C／C++代码静态检测方法研究[J].计算机工程与设计,2011,(8)：2879-2884.
[19]刘东波,高春鸣.采用二叉树编码的遗传算法实现数据拟合[J].数学理论与应用,2002,(1)：32-35.
[20]佘党恩.数字指纹技术及其在软件版权保护中的应用研究[D].武汉：华中科技大学,2007：
[21]王发鸿,周会平,贾丽丽,等.基于GCC的容错编译器的研究与实现[J].计算机工程与科学,2011,(8)：89-94.
[22]王嘉锡.计算机软件安全漏洞的法律规制探讨[J].信息网络安全,2009,(5)：59-61.
[23]于鹏飞,吕鹏淦.软件缺陷的评估方法分析与研究[J].计一算机时代,2009,(7)：4-5.
[24]王甜甜.结构语义相似的程序识别方法研究[D].哈尔滨：哈尔滨工业大学,2009：
[25]王伟,杨庚,张迎周,等.基于程序切片和服务构件的语义Web服务组合[J].计算机技术与 发展,2011.(11)：141-144.
[26]王秀芳,孙承爱,路燕.C语言中编译预处理命令的解读与应用[J].电脑编程技巧与维护,2010,(22)：22-24.
[27]王志伟,平玲娣,陆敏锋.高效字符匹配算法的研究[J].计算机工程与应用,2010,(1)：28-31.
[28]许佳卿,彭鑫,赵文耘.一种基于模糊概念格和代码分析的软件演化分析方法[J].计算机学报,2009,(9)：1832-1844.
[29]颜昌学,杨颖.一种新的代码优化的方法[J].武汉科技学院学报,2001,(3)：010.
[30]于‘海英,赵俊岚.最长公共子序列算法在程序代码相似度度量中的应用[J].内蒙古大学学报,2008,(2)：225-229.
[31]于世英,袁雪梅,卢海涛,等.基于序列聚类的相似代码检测算法[J].智能系统学报,2013,8(1)：1-7.
[32]余有明,刘玉树,阎光伟.遗传算法的编码理论与应用[J].计算机工程与应用,2006,(3)：86-89.
[33]袁彩虹,薛光,张连堂.语义分析和中间代码产生教学过程研究[J].计算机教育,2008,(9)：59-60.
[34]袁桂霞.改进的交叉算子在遗传算法中的研究及应用[J].江苏广播电视大学学报,2011,(5)：54-57.
[35]张平,马骁.开源软件对知识产权制度的批判与兼容(二)一一开源软软许可证的比较研究[J].科技与法律,2004,(2)：46-58.
[36]张志春,雷相波.YACC中的冲突消解方法[J].哈尔滨师范大学自然科学学报,2002,(4)：40-43.
[37]赵克佳,沈志宇.一种分程序结构符号表的组织方法[J].计算机工程与设计,1996,(3)：42-50.
[38]钟美,张丽萍,刘东升.基于XML的C代码抄袭检测算法[J].计算机工程与应用,2011,(8)：215-218.
[39]朱朝霞.编译器词法分析程序实现探讨[J].长春工程学院学报,2011,(4)：132-134.
[40]朱立新,吕莉,于兰.软件开发有力工具YACC的剖析[J].哈尔滨科学技术大学学报,1987，,(2)：59-64.
[41]Baxter I, Yahin A, Moura L, et al. Clone Detection Using Abstract Syntax Trees[J],1998, (11): 368-377.
[42]Falke R, Frenzel P, Koschke R. Empirical evaluation of clone detection using syntax suffix trees[J]. Empirical Software Engineering,2008,13(6):601-643.
[43]Fogel L J, Owens A J, Walsh M J. Artificial Intelligence Through Simulated Evolution[M]. New York:John Wiley & Sons, Inc,1966:38-45.
[44]J H, L. Adaptation in natural and artificial systems[M]. Michigan:University of Michigan Press, 1975:12-16.
[45]Jos L, Bonifacio L. Agg regation of fuzzy preferences:some rules of the mean[J]. Soc Choice Welfare,2000,17(4):673-690.
[46]Kamiya T, Kusumoto S, Inoue K. CCFinder:a multilinguistic token-based code clone detection system for large scale source code[J]. Software Engineering, IEEE Transactions on,2002,28(7): 654-670.
[47]Koza J R. Genetic Programming:On the Programming of Computers by Means of Natural Selection[M]. Boston:MIT Press,1992:1-5.
[48]Rechenberg I. Evolutionsstrategie:Optimierung technischer Systeme nach Prinzipien der biologischen Evolution[M]. Stuttgart:Frommann-Holzboog,1973:2-8.
[49]Saaty, T, L. The analytic hierarchy process[M]. University of California:Mcgraw-Hill,1980:1-10.
[50]Schwefel H P. Evolution and Optimum Seeking[M]. New York:John Wiley,1995:1-23.
[51]Z L, S L, S M, et al. CP-Miner:a tool for finding copy-paste and related bugs in operating system code[J]. Proceeding of the 2004 symposium on operating systems design and implementation, 2004,(6):289-302