第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
第1期 于世英，等：基于序列聚类的相似代码检测算法 ·53· Yamamoto等提出一种基于源代码通信的大型软件 系统相似性度量算法3，根据这个相似度量开发出 含（可-n)门为序列s和S"之间的签名距离，当 了一个软件相似性度量工具SMAT,并且应用到了 n>n,=1,否则=0；当>n时，=1，否则 多个版本的操作系统中.J.H.Ji等提出一种自适应 =0. 1.1带权重的编辑距离 的局部队列，把关键字的频率映射到相似度矩阵中， 使用这个局部队列来自动检测程序中的相似代码片 本文对序列中各种不同类型的字符赋予不同的 段4.文献[5]提出了一种基于编译优化和反汇编 权重，根据字符的可替代性大小规定各个字符的权 的程序相似性检测方法.该方法采用编译优化和反 重.如果是代表关键字的字符，所得到的权重就大一 汇编技术将源程序代码转化为汇编指令集合，再删 些，代表变量的字符得到的权重就比较小，因为相比 除和替换汇编指令中对程序本质影响不大的易变因 之下，变量的可替代性要比关键字的可替代性大.本 素，然后使用一个与指令序列无关的决策函数计算 文中，把代表关键字的字符权重设为2，代表函数或 程序相似度，最后给出一个简单有效的聚类算法，从 者变量的符号权重设为1，代表操作符的符号权重 程序集合中聚类出相似的程序子集.文献[6]针对 设为1，如表1所示. 表1不同符号的权重 源程序代码相似度的度量问题，提出一种基于属性 Table 1 The weight of different symbol 计数和结构度量的方法.通过统计源程序代码的操 作符和操作数个数，得到Halstead长度、Halstead词 符号类型 权重 汇和Halstead容量这3个源程序的特征向量，使用 关键字 2 向量夹角的余弦公式计算属性相似度，利用最长公 函数或变量 1 共子序列算法得到结构相似度，从而权衡程序之间 操作符 的相似程度.文献[79]中也分别提出了不同的相似 要对程序代码段进行聚类分析，首先要解决的 代码检测算法，它们基于不同的结构，从不同的角度 问题就是怎样定义程序代码段之间的距离度量，以 来对相似代码进行检测， 及怎样确定这2段代码是相似的.本文定义一种带 大部分判断代码相似的文献是通过不同的相似 权重的编辑距离(weight edit distance,WED)来衡量 度度量来判断2个或多个源代码整体是否相似，这 2个序列之间的距离，度量它们的相似性， 样增加了一些不必要的计算.这是因为函数功能段 定义1带权重的编辑距离(WED)编辑距 在程序代码中占有主体地位，如果2个源程序中的 离是指将一个符号序列经插人、删除、替换等编辑操 功能段相似，那么就能确定这2个源程序基本相似. 作变为另一个序列所需的操作次数，根据序列中各 因此，本文首先提取出源代码中的功能段，再以带权 种不同类型的符号的不同权重，把进行编辑操作乘 重的编辑距离为相似度量标准，通过聚类源程序代 以相应符号操作的权重，就得到一个符号序列到另 码序列的方法，查找出源程序中相似的代码功能段， 外一个符号序列的带权重的编辑距离 以达到检测相似功能程序的目的， 1)插入、删除操作.对于插入或删除操作，由于 1 问题定义 只涉及一个符号，所以其权重编辑距离设置为该符 号规定的权重，如表2. 假设Cs={a1,a2,…}作为字符集，大小为 表2符号插入、测除的权重编辑距离 N=ICl.S∈Cs表示一个字符序列，S由Cs中的 Table 2 Weight edit distance of insert and delete symbol 字符组成，其中的字符数为S1.2条序列S和S2之 符号类型 权重编辑距离(WED) 间的编辑距离Dε(S1,S2)是将S1经过插入、删除、 关键字 2 替代等操作变换成S2所需要的最少操作次数， 函数或变量 1 如果有序列S=s1s2…sn,n:是字母表中字母 操作符 1 a:在序列S中出现的次数，则向量Sx(S)=(n1,n2, …,nw)为序列S的签名.若序列S和S'的签名分别 2)转换操作.同一类型符号内部转换的权重在表3 为Sw(S)=(n1,n,…,nw)和Sw(S)=(h,,…, 中给出了，不同类型符号之间的转换权重编辑距离则 规定为这2种符号类型的权重之和.表3列举出了本 n),那么Ds(S,s)=mx[之(n-), 文使用到的符号转换时的不同权重编辑距离
·54 智能系统学报 第8卷 表3符号转换的权重编辑距离 Ds(S1,S2) Table 3 The weight edit distance of transform symbol S,+,如果D,(S,S)≥Dm(S,S,),那么根 权重编辑距离(WED) 据式(2)，可以得到Sn(S,S2)≥Sm,说明这2个序 符号类型 关键字 函数或变量 操作符 列不相似. 关键字 2 由于计算签名距离的时间复杂度O(m+)远 3 3 小于计算权重编辑距离的时间复杂度O(mn).因 函数或变量 3 1 2 此，根据性质1，在判断序列是否相似时，可以首先 操作符 3 2 1 通过计算序列间的签名距离来进行初始过滤，再通 例1假如一个符号序列S,=asdfght,另一个 过计算权重编辑距离来进行最后的判断， 符号序列S2=bcfght.可以看出这2个序列中只有 2基于带权重编辑距离的相似序列聚 2个符号不同，设定其中的b、c、d都为关键字类型 的符号，而s为操作符类型的权重，根据上面定义的 类算法 转换权重编辑距离可知，序列S,和S2之间的权重 本节将详细介绍提出的基于权重编辑距离的相 编辑距离是3+2=5. 似序列聚类算法SSCW(similar sequence clustering 1.2序列间的相似度 based on weight edit distance). 定义2序列间的相似度2个序列S,和S2 2.1源程序代码的分段提取 间的权重编辑距离为Dm（S1,S2),则序列S,和S2 检测源程序的相似代码，首先需要对源程序代 之间的相似度Sm(S,S2)表示为 码进行分段，提取出函数功能段.在对源程序代码进 .88）=1- 行分段时，采用一种多级分段方法，把源代码分为不 (1) 同标准下的多种分段，分段的标准有类、函数、语句， 若有2个序列S,和S2,它们之间的相似度为 然后再对同一个级别下的各个分段代码进行处理， Sn(S1,S2),如果Sm(S1,S2)≥S血成立，就说这2个 在查找相似代码时，由于函数功能段是整个源程序 序列S,和S2相似，说明在聚类时这2个序列可以 代码的主体，因此只需要使用第二级函数分段即可， 被归为同一个簇，S被称为序列间的最小相似度 对函数、语句和类的处理意义不大 阈值. 2.2程序代码的部分转换 为了方便计算，在进行聚类时，可以直接以权重 由于使用带权重编辑距离作为相似性度量的标 编辑距离为衡量相似度的标准.根据相似度的定义 准，并且关键字类型、变量类型与操作符类型的权重 式(1)，可以得到满足Sm(S1,S2)≥S的最大权重 各不相同，因此需要对它们进行区分.一般来说，操 编辑距离边界值Dmm(S1,S2)为 作符类型的代码能很好地与其他代码区分，但是关 Dm(S1,S2)=(IS1I+lS2I)(1-Sn).(2) 键字类型和变量类型的代码在读取和计算距离的时 即如果满足Dm(S1,S2)≤Dm(S1,S2)时，则这2个 候很难区分.本文首先把关键字类型的代码转换成 序列相似. 一个个数字，再计算权重编辑距离，虽然变量代码里 性质1若有2个序列S,和S2,其签名距离为 面也不可避免地会出现数字代码，但是这样的源代 Ds(S1,S2),如果满足Ds(S1,S2)≥Dm=(S1,S2)时， 码很少，与关键字混淆的概率也不大.这样处理既能 那么这2个序列不相似. 与变量代码进行区分，保证可以得到带权重的编辑 证明序列S,和S2之间的签名距离 距离，又能减少计算距离时的操作次数 Ds(S,S2)反映了序列字母组成上的差异，而权重 2.3符号序列的聚类 编辑距离Dm(S,S2)反应了S,和S2之间插入、删 对同一个分段级别内的序列，根据定义1中的 除、替换操作不同权重的差异，由于给序列中不同类 权重编辑距离作为相似性度量进行聚类，得到相似 型符号的插入、删除、替换操作赋予了不同的权重 的代码段.下面具体说明聚类过程中用到的几个主 (表1~3)，那么Dm(S1,S2)≥Ds(S1,S2)成立，而签 要算法 名距离是编辑距离的下界o1,即Ds(S1,S2)≥ 2.3.1判断序列与序列是否相似 Ds(S1,S2),因此可得到Dm(S1,S2)≥Ds(S1,S2)成 首先根据式(2)计算出2个序列相似的最大距 立图此及()1-1- 离阈值Dm=(S,S2)(SandSMaxDis);然后根据性质 1,先计算2个序列的签名距离Ds(S1,S2)(signDisS
第1期 于世英，等：基于序列聚类的相似代码检测算法 ·55· toS)来进行初始过滤，如果它们的签名距离大于最 中的簇的相似关系，直到所有的序列S:都被处理， 大距离阈值，就直接判定这2个序列不相似；如果签 此时的相似关系可能为3种情况：1)如果簇列表中 名距离小于最大距离阈值，再计算其权重编辑距离 没有簇与序列S,相似，那么就新建一个簇存放该序 Dg(S1,S2)(wEditDisStoS)进行进一步判断.如算法 列，并且把新创建的簇添加到簇列表中；2)如果簇 1所述. 列表中有一个簇与该序列相似，就把它加人到这个 算法1判断序列与序列是否相似算法(8- 簇中，更新簇的特征值；3)如果簇列表中有多个簇 SandSSimilar). 与该序列相似，就把这几个簇合成一个新簇，再把序 输入：要判断相似性的2个序列S,和S2: 列S:加入到新簇中，并且在簇列表中移除合并了的 输出：布尔值(isSimilar). 那几个簇，添加新创建的簇.聚类过程如算法3 Begin 所述 1）boolean isSimilar; 算法3聚类算法(clustering) 2)int SandSMaxDis=getMaxDistance(S1,S2); 输入：存放序列的哈希表seriesMap. 3)int signDisStoS=calSignDisStoS(S1,S2); 输出：簇列表clusters. 4)If signDisStoS <=SandSMaxDis Begin 5) int wEditDisStoS =calWEditDisStoS(S,S2); 1)List clusters; 6) If wEditDisStoS <SandSMaxDis 2)For each series s in seriesMap 7) isSimilar =true; 3) List simCluNotoSList:/clusters in List clus- 8) Else ters which are similar to series s 9) isSimilar false; 4) List removeCluList; 10) End if 11)End if 5) For each cluster c in clusters If isSandCSimilar(s,c) End 6) 2.3.2判断序列与簇是否相似 7) simCluNotoSList.add(c); 有了判断序列与序列是否相似的算法作为支 8) End if 撑，判断序列与簇是否相似就很容易了.只需要把簇 9) End for 中的所有序列依次与该序列进行相似性判断，如果 10) If simCluNotoSList.size()==0 簇中有任意一个序列与该序列相似，就判定为该序 11) Create a new cluster c'to put series s and 列与该簇相似.如算法2所述. put c'into clusters; 算法2判断序列与序列是否相似算法(8 12) Else if simCluNotoSList.size()==1 SandCSimilar). 13) Put s in cluster c and update the feature of c; 输人：要判断相似性的序列ser和簇cluster. 14) Else 输出：布尔值(isSimilar). 15) Merging clusters in simCluNotoSList into a Begin new cluster c'and put c'into clusters; 1)boolean isSimilar; 16) Remove clusters in simCluNotoSList from 2)For each series s in cluster clusters; 3) isSimilar =isSandCSimilar (ser,s); 17)End if 4) If isSimilar 18)End for 5) break; End 6) End if 算法3给出了改进的基于密度的序列聚类过 7)End for 程.其中，步骤5)~9)是判断簇列表中有几个簇与 End 序列是相似的，可能出现上面给出的3种情况.步骤 2.3.3符号序列的聚类 10)~11)对应情况1)，即簇列表中没有簇与序列相 本文采用改进的基于密度的聚类算法对序列聚 似；步骤12)~13)对应情况2)，簇列表中有一个簇 类，首先创建一个簇列表来存放聚类结果簇，对于存 与该序列相似；步骤14)~16)对应情况3)，簇列表 放在m即中任意一个序列S:,判断序列S:与簇列表 中有多个簇与该序列相似
·56 智能系统学报 第8卷 3实验与分析 件对1和文件对4中R,设为0.9时的情况；如果函 数代码序列本身的相似度高于设定的最小序列相似 通过对4个文件对的相似性检测，来分析SSCW 度，那么R。的设定就不会影响到最终结果。 算法结果的正确性以及运行时间.测试中使用的代码 表4SSCW聚类结果 采用人工合成的代码序列和从网上下载的真实代码. Table 4 The clustering results of SSCW 实验中文件对1(int00和int05)和文件对3(coss-ef00 测试代码 Ra.is R 和CrOSS-refO2)是从网站htp://www.sei.buaa.edu.cn/ 0.7 1.000 buaasim下载的，实现统计整数和交叉引用生成器功能 文件对1 0.8 1.000 的相似代码.文件int05是在文件int00的基础上改变 0.9 0.500 了函数顺序和修改了部分变量名得到的；文件cOss- 0.7 0.965 0.8 0.965 refO2是在文件cross-refO0的基础上改变了函数内部部 文件对2 0.9 0.965 分代码顺序，并在定义时添加了无用参数构成。文件对 0.7 1.000 2(cluste00和cluster0(1)和文件对4(adjustCluster0(0和 文件对3 0.8 1.000 adjustCluster01)是把笔者编写的源程序中一些代码段 0.9 1.000 稍作修改得到，文件对2中文件cluster01是在文件 0.7 1.000 clustero0的基础上添加了一个功能函数段构成：文件对 文件对4 0.8 1.000 0.9 0.000 4中文件adjustClusterO1是在文件adjustCluster0的基 础上修改了函数内部部分代码得到的， 3.2 SSCW算法运行时间分析 根据源文件中功能函数的个数以及聚类结果来 表5中给出了SSCW算法的运行时间随着文件 评判它们是否相似.最终2个源文件的相似度由参 大小、函数个数以及最小序列相似度阈值R,m不同 数R,来决定，其计算方法为 的变化情况，可以看出SSCW算法的运行时间受这 R-2 3个因素的共同影响.在SSCW算法中，运行时间主 (3) 要由计算权重编辑距离和聚类这2个过程的时间消 式中：W,为聚类结果中包含了来自2个源文件的函数 耗组成，权重编辑距离的计算时间与序列的长度有 的簇个数，N为这2个源程序中总的功能函数个数 关，因此当一个功能函数序列的长度增大时，算法的 实验所用的计算机配置如下：CPU为Pentium 运行时间会大幅度增加；而聚类的运行时间与功能 (R)Dual-Core2.93GHz,内存为2GB,操作系统为 函数序列的个数以及其相似性有关，如果函数序列 Microssoft Windows XP Professional Edition 2002 Serv- 的个数增多，聚类所花费的时间也随着增加.由于在 ice Pack3.所有算法用JAVA语言编写实现 计算权重编辑距离时，通过先计算序列的签名距离 3.1SSCW算法聚类结果 来进行初始过滤，因此当最小序列相似度阈值R。,mm 表4给出了使用提出的SSCW算法对相似代码序 确定的序列距离小于序列之间的签名距离时，就不需 列的聚类结果，R,为序列间的最小相似度阈值，R,为 要计算序列的权重编辑距离，此时需要的时间消耗较 2个源程序文件根据相似函数得到的相似度。 少，如表5中文件对2中R.被设定为0.9的情况， 由于在源程序中功能函数所占的比例很大，而且 表5中的3个因素中，文件大小和函数个数决 对于程序的功能取决定性作用，因此如果功能函数相 定了函数序列的长度，它们与最小相似度阈值一起 似，那么基本上可以确定其所在的源程序也是相似的， 决定了权重编辑距离的运行时间.而函数个数及其 从表4中可以看出，算法能够正确判断代码的相似性. 相似性决定了聚类过程的运行时间，因此聚类过程 另外，还可以看出序列之间的最小相似度阈值R,和 的时间消耗就与文件个数和最小相似度阈值有关 结果文件相似度R。的关系.由于判断序列相似是判断 在文件大小一定的情况下，功能函数的个数越少，说 文件相似的基础工作，而在判断序列是否相似时，R, 明函数序列的长度越大，此时序列间权重编辑距离 是一个决定性参数，序列之间的最小相似度阈值R, 的计算时间消耗就越大；但是，功能函数的个数越 的确定会影响到结果文件相似度R。·由表4中可以看 少，聚类过程所需要的时间消耗就越小，因此，功能 出，R,的增加会导致R,不变或者减小，这是因为序 函数的个数对运行时间的影响不是很明确。一般来 列最小相似度阈值的增加，会使得满足相似条件的序 说，当功能函数个数一定时，文件的规模越大、最小 列减少，从而使得最终代码相似性的减小，如表4中文 相似性阈值越小，运行时间也越多
第1期 于世英，等：基于序列聚类的相似代码检测算法 ·57 表5运行时间随着不同因素改变的变化 ington,DC,USA:IEEE Computer Society,2007:179-180. Table 5 Running time changes with different factors [5]赵长海，晏海华，金茂忠.基于编译优化和反汇编的程序 测试代码 文件 运行 相似性检测方法[J].北京航空航天大学学报，2008,34 函数个数 大小VkB 时间/s (6):711-715. 0.70 ZHAO Changhai,YAN Haihua,JIN Maozhong.Approach 0.562 1.625 2 0.75 based on compiling optimization and disassembling to detect 文件对1 1.515 program similarity J].Journal of Beijing University of 0.80 1.547 0.695 2 Aeronautics and Astronautics,2008,34(6):711-715. 0.90 1.516 [6]于海英.程序代码相似度度量的研究与实现[J].计算机 0.70 6.360 1.370 14 工程，2010,36(4)：4549. 0.75 6.844 文件对2 YU Haiying.Research and implementation of program code 0.80 6.360 1.460 15 similarity measurement[J].Computer Engineering,2010, 0.90 2.515 36(4):4549. 0.70 24.687 2.630 [7]JIANG Linxiao.Scalable detection of similar code:tech- 0.75 24.953 文件对3 niques and applications[D].Davis,CA,USA:University 0.80 24.578 2.640 of California Davis,2009:12-45. 0.90 24.875 [8]张丽萍，刘东升，李彦臣，等.一种基于AST的代码抄袭检测 0.70 1581.573 15.200 方法[J】.计算机应用研究，2011,28(12)：46164620. 0.751564.016 文件对4 ZHANG Liping,LIU Dongsheng,LI Yanchen,et al.AST- 0.80 1568.953 17.000 based code plagiarism detection method [J].Application 0.90 1521.610 Research of Computers,2011,28(12):4616-4620. [9]钟美，张丽萍，刘东升.基于XML的C代码抄袭检测算 4 结束语 法[J].计算机工程与应用，2011,47(8)：215-218. 本文提出一种基于序列聚类的相似代码检测算 ZHONG Mei,ZHANG Liping,LIU Dongsheng.Plagiarism detection algorithm based on XML for C code[J].Computer 法SSCW,以得到相似功能的代码段.该方法采用一 Engineering and Applications,2011,47(8):215-218. 种多级分段方法，把源代码分为不同标准下的多种 [10]戴东波，汤春蕾，熊赟.基于整体和局部相似性的序列 分段，分段的标准有类、函数、语句.将需要检测的代 聚类算法[J].软件学报，2010,21(4)：702-717. 码段提取出来后，把不好区分权重的关键字代码转 DAI Dongbo,TANG Chunlei,XIONG Yun.Sequence 换为数字序列，以提出的权重编辑距离为距离度量 clustering algorithms based on global and local similarity [J].Jourmal of Software,2010,21(4):702-717. 标准，对同一个等级内的符号序列进行聚类分析，得到 作者简介： 相似的代码段.在实验时，使用了多个数据集对提出的 于世英，1973年生，女，工程师，主 算法进行了验证，实验结果证明了该算法的有效性 要研究方向为数据挖掘， 参考文献： [1]KONTOGIANNIS K,GALLER M,DEMORI R.Detecting code similarity using patterns[C]//Working Notes of Third Workshop on AI and Software Engineering:Breaking the Toy Mold(AISE).[S.1.],1995:68-73. 袁雪梅，女，1989年生，硕士研究 2]0HNO A.Measure source code similarity using reference vec- 生，主要研究方向为数据挖掘。 tors[Cl//Proceedings of the First International Conference on Innovative Computing,Information and Control.Washington, DC,USA:IEEE Computer Society,2006,2:92-95. [3]YAMAMOTO T,MATSUSHITA M,KAMIYA T,et al. Measuring similarity of large software systems based on source code correspondence[C]//Proceedings of the 6th 卢海涛，女，1975年生，讲师，主要 International Conference on Product Focused Software 研究方向为数据挖掘、虚拟现实. Process Improvement.Berlin/Heidelberg:Springer-Verlag, 2005:530-544. [4]JI J H,PARKS H,WOO G,et al.Source code similarity de- tection using adaptive local alignment of keywords[C]//Pro- ceedings of the Eighth International Conference on Parallel and Distributed Computing,Applications and Technologies.Wash-