搜索

基于抽象语法树的相似代码识别方法

gecimao 发表于 2019-05-24 08:02 | 查看: | 回复:

  摘要:对于相似的缺陷,开发人员可以采用类似的方法予以解决。因此识别相似缺陷对于提高软件开发及维护效率具有重要意义。目前对于相似缺陷的分析大多是基于C++或Java两种语言,本文主要探究基于抽象语法树的相似代码识别方法在python语言代码中的实验效果。

  相似代码检测是指在软件系统的源代码中找出与其相似度高的代码片段的过程。相似代码检测是相似代码领域的基础性工作之一,它为后期更深入的探究提供了基础数据。一般来说该过程是非常耗时的,它需两两比较所有代码片段间的相似度。目前相似代码检测方法大体可分为四种:基于字符串的方法、基于token的方法、基于树的方法以及基于语义的方法。

  近年来,已经涌现出了多种关于相似代码检测的方法。有关于相似代码(也称克隆代码)检测与识别技术的研究可以追溯到上世纪90年代。到目前为止研究人员已经提出了多种相似代码检测和识别的方法,并深入研究了如何在其检测结果的基础上进行代码重构、软件再工程、软件维护支持等问题。相似代码检测技术也成为近年来软件维护领域的热点,已经开发了多种能用于相似代码自动检测的商业工具[1][2]。另外,在开源社区中也涌现出了多种基于相似代码检测的重构支持插件[3[]4]。

  根据相似的代码片段其句法结构也相似这一特点,本文利用基于树的方法,将源代码片段解析成一棵抽象语法树,通过比对子树之间的相似性找到某个代码片段的相似代码片段集合。另外,由于树这种数据结构本身的特点,若直接计算两棵树间的相似度,其复杂度势必很高。对于一棵有N个节点的抽象语法树,若对其子树逐一比较则需要O(N3)的计算时间。因此,若用固定维数的特征向量表示抽象语法树中的每个节点,则抽象语法树间的相似度比较则可以转化为特征向量间的相似度计算,有效降低了计算复杂度。具体方法如图3-1所示。

  得到各模块的AST语法树后,根据[50]中的解析AST语法树方式,定义一个9维特征向量表示AST语法树中的每个结点。9个维度分别为[Literal,Variable,Expressions,Subscripting,Comprehensions,Statements,Imports,ControlFlow,FunctionAndClassDefinitions]。例如,Variable记录该特征向量所代表的模块中的变量个数。随后每个结点的特征矢量值通过后序遍历计算,父结点的值是所有子结点的值与父结点本身的特征值的矢量和。这样一来,子树的相似性比较就转化成特征矢量的比较。上述python部分代码对应的特征向量如图3-10所示,其中,每个特征向量的最后三个维度分别代表该特征向量对应的模块在原代码中的起始行、终止行和文件名。另外,查找某一行代码或代码片段很小时,查找与其相似的代码模块时没有意义的,因此,可设定某一阈值,当特征向量的前9维之和小于这一阈值时不予考虑。图3-10就是阈值设为10时过滤某些特征向量后的结果。

  随后利用LSH算法并在该算法得到的桶中逐个计算特征向量间的欧氏距离,找出欧氏距离最小的模块,并认为该模块与目标模块的相似度最高。上述的python模块(图3-8)找出的相似度最高的模块如图3-11所示。

  本章首先介绍了基于相似代码检测的相似缺陷识别方法的基本流程,介绍了python程序语言构建抽象语法树的工具和方法,抽象语法树可以直观的表示出代码的结构信息,对程序分析具有重要意义。另外基于特征矢量法从抽象语法树的各结点信息中得到代码片段对应的特征向量的方法,将抽象语法树中每个结点对应的代码片段抽象为固定维数的特征向量,该方法有效简化了用特征矢量表示语法树结点的复杂度。最后介绍了局部敏感哈希算法,使用该算法可以显著降低逐对计算特征向量间相似度的计算时间。

  “2018新闻传播学院院长论坛”11月10日在厦门大学举行。人民日报社副总编辑卢新宁,福建省委常委、宣传部部长、秘书长梁建勇,厦门大学党委书记张彦,教育部高等教育司司长吴岩等与会并致辞。

  由国家互联网信息办公室和浙江省人民政府共同主办的第五届世界互联网大会于11月7日至9日在乌镇召开。本届大会以“创造互信共治的数字世界——携手共建网络空间命运共同体”为主题。

本文链接:http://ticatfans.com/duanyujiegoushu/328.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部