代码相似度计算框架调研

研究现状

代码相似度计算是一个已有40年研究历史的问题了。它的应用范围广泛，主要包括代码抄袭检测[3]、软件维护中的相似代码查找等。
Whale[1]于1988年首次提出一个代码相似性检测的通用框架和步骤，将检测过程分为以下两个阶段：

代码格式转换 + 相似度确定

后来很多检测方法都参考这一框架，并将检测过程细分为四个部分：

预处理 -> 中间代码转换 -> 比较单元生成 -> 匹配算法

参考以上算法，我把代码相似度计算的技术按照如下三个指标分类

中间表示 + 比较单元 + 匹配算法

综述中[2][3]对中间表示的总结常常把这个中间表示的内容（承载了代码的什么信息）和形式（用了什么样的数据结构）混在一起。对此，我想做一个把内容与形式分离的总结。

先总结代码中有哪些信息可以被提取出来用于相似度计算，包括：

词法信息
语法信息
统计属性信息
控制流信息
数据流信息

这些信息在被具体定义并准确提取后，可以构成中间表示的内容。其中有些信息是具有一些天然的数据结构的。如下表所示：

信息	数据结构	具体表示实例
词法信息	线性结构	Token流
语法信息	树形结构	抽象语法树（AST）
统计属性信息	数值向量结构	保留字计数向量
控制流信息	有向图结构	控制流图（CFG）
数据流信息	有向图结构	数据流图（DFG）

学过数据结构的同学应该记得，课本[4]将数据结构的逻辑结构分为三类：线性结构（如向量、列表）、半线性结构（树）与非线性结构（图）。

以上三类结构并不是相互独立的关系，而是有层次的关系。我认为，它们按照复杂程度和转换层次，可以表示为如下的递进关系：

线性结构 -> 树结构 -> 图结构

其中，高层次的结构可以通过分解为若干低层次的结构，而低层次的结构也可以通过组合得到高层次的结构。具体来说，树结构可以通过遍历序列化为线性结构，而线性结构也可以通过合并节点转化为树结构或图结构。

基于这个不同结构之间可转化的特性，无论我们的中间表示多么复杂，都可以转化为低层次的结构来做匹配。我认为这也是论文[2]中提出的把“中间表示”与“比较单元”区分开来的原因。而对于不同结构的匹配算法，这其实是数据结构与算法领域研究的内容了。

除了计算复杂度上的差异，我认为，不同的中间表示对源代码结构的反映程度也是不同的。

更高层次的结构承载的代码结构信息更多，也更接近源程序的结构，但这些结构比较复杂，不利于计算机处理；相反，较低层次的结构更便于计算机处理，但包含的信息过于抽象笼统，不能反映代码结构的全貌。

针对我的特定业务场景找到最适配的中间表示与比较单位，是我近期的目标。

未来研究展望

代码相似度计算的一个主要应用是软件抄袭检测[3]。
综述[3]给出了软件抄袭检测领域的几个挑战和未来研究方向，包括：

部分抄袭问题

抄袭定位及证据生成

对于这两个方向，我认为可以尝试引入其他领域的方法论，比如信息检索和知识工程。具体怎样融合我会在后续的博客文章中介绍。

参考文献

[1] Whale, Geoff and University of New South Wales. Department of Computer Science Plague : plagiarism detection using program structure. School of Electrical Engineering and Computer Science, University of New South Wales, [Sydney], 1988.
[2] 熊浩,晏海华,郭涛,等. 代码相似性检测技术:研究综述[J]. 计算机科学, 2010, 37(8): 9-14, 76.
[3] 田振洲,刘烃,郑庆华,等. 软件抄袭检测研究综述[J]. 信息安全学报, 2016, 1(3): 52-76.
[4] 邓俊辉. 数据结构（C++语言语言版第3版）. 2013

第一次在博客园发布markdown格式的随笔，效果还不错。以后的博客会同步在gitpages和博客园上发布，欢迎关注。