论文研究-基于结构特征聚类的相似代码检索方法 .pdf

所需积分/C币:5 2019-08-17 15:17:24 326KB .PDF
收藏 收藏
举报

基于结构特征聚类的相似代码检索方法,王克朝,王甜甜,针对基于图的相似代码检测方法复杂度高、对代码多样化识别能力有限等问题,提出基于结构特征聚类的方法。首先将代码表示为控制依
国武技论文在线 http:/www.paper.edu.cn 75制结构,更有利于识别代码多样化,即识别语义相似的代码。 代码标准化 表达式多样化以及控制结构多样化等会影响相似度计算的准确度,因此 Gabel方法对语 法不同但语义相似的代码产生漏检。为了克服这一缺陷,本文提出了代码标准化,定义如下 定义(代码标准化)根据一系列标准化规则对CDT进行语义等价的转换,直到仼何规 80则都不能应用为止。代码标准化规则包括:拆分复合语句、表达式标准化、基木的控制结构 标准化等8 基本代码标准化的实例如下: (1 while((=/)<1){…}→-/; while(<1){…-/;} (2)int,; int int ) (4)if() if(! )if() else 特征向量分组聚类及相邻分支合并 Gabel方法每次只能识别指定规模的相似代码片段,木文对其进行改进,将源程序和目 标程序的向量分组,在此基础上应用LSH算法山对向量进行聚类,然后合并相邻相似分支 90可以识别任意规模的相似代码片段。 生成特征向量 定义(的特征向量)一棵CDT子树的特征向量是欧式空间中的一个点 (1,2,3,4,s,6,3,8,9),其中:1表小节点个数;2表小运算符个数;3表小选择结构个数; 4表小循环结构个数;5表示赋值节点个数;6表小特殊数据类型(如指针、数组以及结杓 95体)的个数;7表小CDT中最长路经长度;8表小系统函数调用个数;9表小控制依赖边的 数目 特征向量的生成方法为:给定CD子树,后根序遍历为它的子树生成特征向量 的向量由构成它的子树的向量累加而成。 特征向量分组聚类 将特征向量分组聚类的算法如图2所小 3 国武技论文在线 http:/www.paper.edu.cn 算法: vecloGIJUILU 输入:源程序向量集合={v1,Y2.1x} 目标程序向量集合U={、l,m 输出:模式向量分组中各个向量的rAN 识别模式CDT1与用户程序CDT72中相似的分支列表L B Ordcrby Des(n) OrderbyDes(0) 将卩分组F={G71,G72,G}满足: (1)G:∽Gv2u…GT=p ()每组中的第一个向量,如v,和最后一个向量,如v, 满足相似条仁s(v)-s(vx<2(1-s)mnax(sv).s(v)。 查找与每个分组G巧规模相似的用户程序可量分组GU for j=1 to f foreach v CGp foreach i∈U )Imax(s(v2), s(ur)) endfor difo foreach GU. CGr foreach vK∈GF INvH=LSH(vh, GUi r L中记录与及其相似节点对 d for End 图2特征向量分组聚类算法 Fig 2 Algorithm of feature vector group clustering 算法分为两部分,第一部分执行向量分组,首先 Orderby Des函数将向量按照规模由大 105到小排序,然后分组,将可能与(=1,…,)相似的向量都聚集在对应的中。 第二部分执行聚类,LSH算法每次处理一个源程序向量分组,查找(=1,)中的 各个向量在中的rAN集合,即与相似的向量,从而识别源程序和目标程序中相似 的控制依赖分支。步骤如下: (1)将所有向量存入LSH的哈希表,保存的是编辑距离阈值σ l10 (2)中各个向量作为查询点,对哈希表进行查询,获得其rcAN集合; (3)如果crAN(),则意味着是在σ距离之内的近邻,因此它们在CDT中对应 的分支相似,记录相似的分支。 合并相邻的相似分支 特征向量分组聚类只能检测相似的分支,而不能识别由相邻分支构成的森林,即相邻相 115似代码构成的代码块,并且rcAN集合中叮能包含误检,因此需要后处理,在向量分组聚类 中识别的相似分支基础上,进步合并相似的分支,并去除向量分组聚类中的重复检测结果。 4 国武技论文在线 http:/www.paper.edu.cn 算法: Merging 输入:CDIn1与用户程序CDT2中相似的分支列表L 输出:合并后CDTZ1与用户程序CDTZ2中相似的分支列表L Begin foreach o-相似的(SN,SMOi1andr2 if彐a相似的( Parent(SM, Parent(SM) L=L-I(SN, SM1 else if彐σ-相似的( Rightsibling(SM., Rightsibling(SM) L-L-i(SN, SM1 i(SN, Rightsibling(SN), S1), RightSibling (SM13 end for end for 上nd 图3合并相邻相似CDT分支算法 Fig 3 Algorithm of merging proximity-similarity CDT 120 对于源程序的和目标程序,分析其各个满足∝-相似的分支(,)的祖先(即包含 与的子树)和其兄弟,如果包含它们的祖先σ-相似,则意味着和被更大的相似 代码块包含,因此从检测结果中删除( ),并且不再分析与的兄弟和其祖先包 含的所有子结构。如果(,)的祖先均不相似,则需分析与的兄弟。这时,如果 的某些石兄弟,与对应的兄弟σ-相似,则它们构成相似森林。这样可以识别任意规 125模的相似代码片段。 实验结果分析 我们用VC和 Matlab实现了本文方法和 Gabel方法,并将其应用于分析大规模的开 源编译器GC源代码,将GCC2.0(261,580行)作为源程序,将GCC1.4(98,791行)作 为目标程疗。实验运行环境是3GIκ处理器、2GB内存。 130 提取候选相似代码的效果 用公式(1)所小剪枝率 衡量本文方法提取侯选相似代码的效果,其中,为 源程序中代码行数,为目标程序中代码行数 为检测出的相似代码行数, 为经人工验证真正相似的代码行数 mint ×100%A(1) min( 135 由公式(1)可知,剪枝率应该小于或等于100%,否则,如果剪枝率大于100%,则意味 着检测出的相似代码比实际的相似代码少,因此产生漏检。在实验中,本文方法没有产生漏 检,并且剪枝率可达到90%以上,可以过滤掉大韶分不相似代码。 代码多样化识别效果 本文方法和 Gabel方法识别代码多样化的结果,如表1所示。本文方法检测到GCC20 140与GCC1.4中候选相似代码对数为1081对,这些代码对中有83对候选相似代码包含一处或 多欠代码多样化,有10对包含代码多样化的候选相似代码是语义等价的,其它73对不完全 等价但语义相似。每对候选相似代码中不冋程度地包含∫复合语句多样化、表达式多样化 冗余代码、控伂结构多样化、标识符命名多样化、以及语句顺序多样化。 国武技论文在线 http:/www.paper.edu.cn Gabel的方法可以正确处理代码格式多样化、标识符命名多样化和珸句顺序多样化,但 145是对于复合语句多样化、表达式的多样化、控制结构多样化漏检较多。 综上所述,本文方法不但可以识别语法相似的代码,而且可以识别语义相似的代码,并 且代码多样化常常岀现在现实软件系统中,合并相邻分支使得本文方法可以识别仼意规模的 相似代码,,本文提出的代码标准化是必要和实用的。此外本文方法还克服了Gabc方法只 能识别指定规模的相似代码的局限性。 150 表1止确识别GCC2.0与1.4中代码多样化个数 Tablel Number of code variations identified by gCC2.0 and 1.4 代码多样化类别 正确识别的代码多样化个数 Gabel方法 本 文方法 复合语句多样化 10(500%) 表达式多样化 9(300% 余代码 控制绾构多样化 0(250%) 标识符命名多样化 2(100% 语句顺序多样化 3(100% 结论 本文提出基于结构特征聚类的相似代码检索方法:(1)将程序表示为CDT有序树的形式, 降低了稈序中间表示的复杂度,避免了图的同构测试复杂度较高、不适于大型软件相似代码 155检测的问题;(2)将特征向量聚类应用于语义级别的候选相似代码检索中,快速地过滤掉大 部分不相似代码对,降低计算复杂度,使其适用于大型软件在语义级别上的相似代码检测; (3)与 Gabel方法相比,木文方法可以识别更多的代码多样化,且可以识别仨意规模的相似代 我们下步研究目标是,对候选相似代码进行数握流分析,进¨步检测语义相似的代码, l60提高检测结果的准桷率。并将语义相似的代码检测方法及其关键技术应用于程序理解中,用 已知代码识別未知代码的语义,辅助程序理解。 参考文献 [1] Bettenburg N, Shang W, Ibrahim W. M, Adams B, Zou Y, and Hassan A. E. An empirical study on inconsistent changes to codc clones at the rclcasc lcvcl[J]. Scicncc of Computcr Programming, 1652012,7(6,;760-76 2] Nguycn H, Nguyen T, Pham N, Al-Kofahi J, and Nguyen T. Clonc managcmcnt for evolving softwarc[J] IEEE Trans. Softw. Eng, 2012, 38(5): 1008-1026 [3] Md. Saidur Rahman, Amir Aryani, Chanchal K. Roy, Fabrizio Perin. On the Relationships between Domain-Based Coupling and Code Clones: An Exploratory Study[C]/IEEE International Conference on Software 170 Engineering. New Jersey, USA, 2013: 1265-1268 4 Bruntink M. van Dcurscn A, Engclcn R. van, and Tourwc T. On thc usc of clonc dctection for identifying crosscutting concern code [j]. IEEE Trans. Softw. Eng 2005, 31(10): 804-818 [5Li J. and Ernst M. D. CRCD: Cloned buggy code detector[C/iEEE International Conference on Software Engineering. New Jersey, 2012: 310-320. 175 [6]Shuai Xie, Foutse Khomh, Ying Zou. An Empirical Study of the Fault-Proneness of Clone Mutation and Clone Migration[C]/TEEE 1 Oth Working Conference on Mining Software Repositories. New Jersey, USA: IEEE, 2013 149-158 Li Z, Lu S, Myagmar S, and Zhou Y. CP-Mincr: finding copy-pastc and rclated bugs in largc-scalc soft code[j. IEEE Trans. Softw. Eng, 2006, 32(3): 176-192 180 [8]Rahman F, Bird C, and Devanbu P. Clones: what is that smell? [-J Empirical Software Engineering, 2012,17(4-5):503-530 [9] Kamiya T, Kusumoto S, Inoue K. CCFinder: A Multi-Linguistic Token-based Code Clone Detection System for Large Scale Source Code[J]. IEEE Trans on Software Engineering, 2002, 28(7): 654-670 101 Baxter ID, Yahin A, Moura L, Sant'Anna M, Bier L. Clone Detection Using Abstract Syntax Trees(CV/IEEE 185 International Conference on Software Maintenance, New Jersey USA, 1998: 368-377 [11 Mayrand J, Leblanc C, Merlo E. Ex It on the automatic detection of function Clones in a Softwa System Using Metrics[C]EEE International Conference on Software Maintenance 国武技论文在线 http:/www.paper.edu.cn Jersey,USA,1997:314-321 [12] Komondoor R, Horwitz S. Using Slicing to Identify Duplication in Source Code[C]/8th International Static 190 Analysis Symposium(SAS), Heidelberg, Germany, 2001: 40-56 [13] Krinke J. Identifying Similar Code with PrograIn Dependence Graphs[C]/IEEE 8th Working Conference on Reverse enginccring Ncw Jcrscy, USA, 2001: 301-309 [14] Gabel M, Jiang LX, Su ZD. Scalable Detection of Semantic Clones[C]/ieee 30th international conference on Software engineering. New Jersey, USA, 2008, 321-33 195 [15] Jiang LX, Misherghi G, Su ZD, Glondu S DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones[c]EEE 29th International Conference on Software Engineering. New Jersey, USA, 2007: 96-105 [16 Ferrante J, Ottenstein KJ, Warren JD. The program dependence graph and its use in optimization[J]. ACM Transactions on Programming Languages and Systems 1987, 9: 319-349 [17 Datar M, Immorlica N, Indyk P, Mirrokni vs. Locality-scnsitivc hashing schcmc bascd on p-stablc 200 distributions[C]/ACM 20th annual symposium on Computational geometry, New York, ACM Press, 2004:253-262 [18 Wang Tiantian, Su Xiaohong and Ma Peijun. Program normalization for removing code variations[C]/International Conference on Computer Science and Software Engineering, WuHan, China, 2008:306309 205

...展开详情
试读 7P 论文研究-基于结构特征聚类的相似代码检索方法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于结构特征聚类的相似代码检索方法 .pdf 5积分/C币 立即下载
    1/7
    论文研究-基于结构特征聚类的相似代码检索方法 .pdf第1页
    论文研究-基于结构特征聚类的相似代码检索方法 .pdf第2页
    论文研究-基于结构特征聚类的相似代码检索方法 .pdf第3页

    试读已结束,剩余4页未读...

    5积分/C币 立即下载 >