第8卷第1期 智能系统学报 Vol.8 No.1 2013年2月 CAAI Transactions on Intelligent Systems Feh.2013 D0I:10.3969/j.issn.16734785.201209054 网络出版地址：htp:/nw.cmki.net/kcms/detail/23.1538.TP.20130125.1445.005.html 基于序列聚类的相似代码检测算法 于世英12，袁雪梅，卢海涛'，任家东，李硕 (1.燕山大学信息科学与工程学院，河北秦皇岛066004；2.河北省科技管理信息中心，河北石家庄050021) 摘要：为了提高源程序代码之间相似性的检测效率，提出一种基于序列聚类的相似代码检测算法.算法首先把源 代码按照其自身的结构进行分段提取，然后对各个分段进行部分代码变换，再以带权重的编辑距离为相似度量标准 对这些符号进行序列聚类，得到相似的程序代码片段，以达到对源程序进行相似功能检测的目的.使用多个真实和 仿真程序对上述算法进行了实验，实验结果验证了算法的有效性和可伸缩性， 关键词：序列聚类：权重编辑距离：相似代码检测 中图分类号：TP311.131文献标志码：A文章编号：16734785(2013)010052-06 Similar code detection algorithm based on sequence clustering YU Shiying'2,YUAN Xuemei',LU Haitao',REN Jiadong',LI Shuo (1.College of Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China;2.Hebei Provincial S&T Man- aegement Information Center,Shijiazhuang 050021,China) Abstract:In order to improve efficiency of similar detecting between the codes of source programs,similar code de- tection algorithm based on sequence clustering was proposed in this paper.First,the algorithm extracts the source code by partitioning it into multi-segments according to its structure.Secondly,parts of the codes in each segment were transformed and the sequences were then clustered taking the weighted edit distance as the similar measure standard.Next,similar code fragments were obtained,achieving the objective of detecting similar functions among multi-codes of the source program.The experimental results based on a series of real and synthetic programs reveal the validity and scalability of the algorithm. Keywords:sequence clustering;weighted edit distance;similar code detection 随着计算机软件的发展，程序代码在日常生活相似性的方法山，模式被指定为概念语言中的源程 中越来越常见，代码能够实现各种各样的计算、匹配 序或者摘要描述的序列.该方法采用一系列代码对 和查询.正是由于软件行业的快速发展，以编程为职 代码和摘要描述对代码的匹配技术，前者使用动态 业的工作人员层出不穷，因而代码的质量也因人而 编程技术来局部化相似代码片段，能处理大型软件 异.相似代码的检测应运而生，能在许多应用中发挥 系统.后者使用马尔可夫模型，根据一个给定摘要描 作用，比如可以通过检测源程序中的相似代码对源 述生成一个给定代码段的概率，来计算一个摘要描 程序进行简化，也可以查找出多个程序之间的相似 述与代码段之间的不同距离.A.Ohno提出一种使用 功能，还能用于抄袭检测. 相关向量来度量源代码相似性的算法).该算法直 国内外许多学者对检测相似代码进行了大量研 接使用相关向量而不是使用源程序代码，相关向量 究，K.Kontongiannis等提出一种使用模式检测代码 中的元素是从源代码中产生的token-cooccurrence 矩阵的结构特征值，由于相似性仅仅定义为2个相 收稿日期：2012-09-25.网络出版日期：201301-25 基金项目：国家自然科学基金资助项目(61170190) 关向量之间的距离，因此该方法节省了计算时间，同 通信作者：于世英.E-mai:wangqianysu@163.com. 时也不用为存储源程序开辟大的存储空间.T