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

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

Abstract：For similar bugs, developers can use a similar approach to solve it. Therefore, identifying similar bugs is of great significance for improving software development and maintenance efficiency. At present, the analysis of similar bugs is mostly based on C++ or Java. This paper mainly explores the experimental results of similar code recognition methods based on abstract syntax trees in python language.

关键字：相似缺陷 软件开发效率 抽象语法树 python

Keywords: Similar defect Software development efficiency Abstract syntax tree Verb phrase

0引言

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

1 背景

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

2基于动宾短语和主题模型的相似缺陷报告识别方法

根据相似的代码片段其句法结构也相似这一特点，本文利用基于树的方法，将源代码片段解析成一棵抽象语法树，通过比对子树之间的相似性找到某个代码片段的相似代码片段集合。另外，由于树这种数据结构本身的特点，若直接计算两棵树间的相似度，其复杂度势必很高。对于一棵有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所示。

4 结束语