A Slower Speed of Light

Code Clone Detection - NiCad

  • (1) 类型一(完全相同的代码): 除了空格,注释之外,两个代码片段完全相同的代码对。

  • (2) 类型二(重命名/参数化的代码): 除了变量名,类型名,函数名之外都相同的代码对。

  • (3) 类型三(几乎相同的代码): 有若干语句的增删,或使用了不同的标识符、文字、类型、空格、布 局和注释,但是依然相似的代码对。

  • (4) 类型四(语义相似的代码): 相同功能的异构代码,在文本或者语法上不相似,但是在语义上有 相似性。 检测类型一到类型三的代码克隆,这两种技术分别是基于文本的和基于树的,两者可以独立使用来互相补充不足。

NICAD 分为三个步骤:

  • 首先使用了一个解析器(Turing eXtender Language, TXL)来将代码段分割成行,

  • 然后利用一些转换规则来进行转换,接着将剩下的潜在的克隆对进行重命名,

  • 最后利用动态的模式匹配来找到最长的相同的子序列。

NICAD 之所以能够检测到类型三的克隆是因为使用 了唯一字符串比例(percentage of unique strings, PUS)来控制检测松弛度,如果其值为 0%,则两段代码为类型一完全相同,如果其在 0%到某个阈值之间,则检测出的结果为类型二或者类型三。NICAD 能在代码段和函数粒度进行检测代码克隆,它有着较高的精确度和召回率。NICAD 的解析器让它充分利用了抽象语法树的技术的好处,但是它利用文本行的比较而非子树的比较,所以还是一个基于文本的检测方法,拥有较低的空间复杂度和计算复杂度,能够胜任大型系统的扫描。

利用文本进行源代码表征的检测技术几乎不会检测到文本差异大的代码克隆,因此精确度很高,很少会出现假阳率(错误将非代码克隆识别成克隆)。因为只从文本方面考虑,这种表征方式独立于编程语言,部署成本较低,计算开销较小,有很强的可拓展性和易用性,因此空间复杂度和时间复杂度比较低。

但是也有它的缺点和局限性,主要表现在:源代码虽然以文本方式编码,但是还保留有语法等信息,在检测中如 果只使用文本方式进行源代码表征,会损失大量信息。

论文:代码克隆检测研究进展 https://xin-xia.github.io/publication/rjxb181.pdf