梳理 | 代码克隆检测技术

in web安全 Views: 1,742 s with 0 comment

1-前言

代码克隆(Code clone),是指存在于代码库中两个及两个以上相同或者相似的源代码片段,是软件开发中的常见现象。代码克隆能够提高效率,但也可能意外引入外部漏洞。下文是对代码克隆检测技术的简单整理。

2-克隆的类型

代码克隆的类型主要分为两大类,句法克隆(syntactic clones)和语义克隆(semantic clones)。句法克隆指文本相似的代码片段, 语义克隆则是指功能相似的代码片段。基于这两大类,代码克隆可以被划分为四小类,其中前三种为句法克隆,第四种为语义克隆。

类型
Type-1句法克隆去除空格,空行和注释后,完全相同
Type-2句法克隆除了对一些unique identifiers(函数名,类名,变量)重命名以外,完全相同
Type-3句法克隆片段部分被修改,如添加或删除了部分代码片段,或是重新排序了部分代码片段
Type-4语义克隆语义相似,但句法不相似(非常难检测)

当前,学术界对Type1,2,3类克隆的检测已颇为成熟,尤其是对Java和C++语言的克隆检测;
而对Type4类克隆的检测准确率仍不高,无法达到工业界应用标准。

四类的代码示例可参照下图——
其中s1,s2,s3,s4 分别对照Type-1,2,3,4类的代码形式,加粗部分为修改部分。
四种类型的分类.png

3-克隆检测的通用流程

通览代码克隆检测领域的相关论文,可以发现代码克隆检测通常分三步走。
克隆流程.jpg

  1. 将源码拆分为对比单元(comparison units, 如class,function,block,statement)
  2. 将对比单元转化为中间表达(IR, Intermediate Representation,如token,AST, PDG)
  3. 再对这些对比单元的IR进行match detection(对比),通常是将对比单元组成clone pair的形式:一次对比两个(c1, c2)或是多个(c1, c2, c3)

4-克隆检测算法的分类

代码克隆检测发展至今,主要分为五大类检测思想: Textual, Token, Syntactic, Semantic, Learning.其具体分类见下图。

2.jpg

这几类对应的具体算法见下——

1. Textual

图中的oss指open source software

text.jpg

2. Token

token.jpg

3. Syntactic

3.1 Tree

ast.jpg

3.2 Metric

metric.jpg

4. Semantic

4.1 PDG

pdg.jpg

4.2 Other

semantic.jpg

5. Learning

5.1 ML

ml.jpg

5.2 Other Learning

learning.jpg

克隆检测的历史趋势

有关代码克隆检测的最早和最开创性的工作是在1990年代初期完成的,如下表所示。可以看出除了近年兴起的ML方法以外,代码克隆检测的开创性工作均在90年代和00年代就已完成,这也是笔者说该领域已颇为成熟的原因。

名称算法思想检测级别
Baker,1992line-by-line comparisonType-1,2
Dup,1995parameterizationType-1,2
CloneDR,1998ASTType-1,2
CCFinder,2002token stream, a prefix tree and a novel matching algorithm,Type-1,2 支持在分钟内实现百万行代码的检测。支持代码类型:C,C++,Java,COBOL
CP-Miner,2004类CCFinderbug-detection
Deckard, 2007tree-based在大型数据集上有很好的表现,如Linux Kernel。可以检测 Type-1,2,3类的代码克隆

Benchmarks 基准

除了工具本身之外,在代码克隆检测工具的基准测试和有效性测试领域也有许多发展。其中比较有名的是Bellon’s benchmark(2007)和 BigCloneBench(2015)

基准发布时间描述
Bellon’s benchmark2007在两个小型C程序和两个小型Java程序上运行六个不同的代码克隆工具,并收集克隆结果。 将这些结果与真实代码克隆的主体进行比较,创建出代码克隆数据集。
BigCloneBench2015BigCloneBench是IJaDataset-2.0(一个包含25,000个开源Java系统的大数据软件存储库)中800万个经过验证的克隆的集合。包含项目内和项目间的全部四种主要克隆类型。

开源工具

笔者整理了部分已开源的学术成果,地址见下。

ClassificationToolLanguagesLink
TokenSHINOBI2009Anyhttps://sdlab.naist.jp/projects/shinobi.html
ASTClone MergeC/C++https://krishnanm86.wixsite.com/clonerge
LearningCloneCognition2019Javahttps://github.com/pseudoPixels/CloneCognition
TokenCtCompare2012Unspecifiedhttps://github.com/awakecoding/ctcompare
TokenCloneWorks2017Javahttps://github.com/jeffsvajlenko/CloneWorks
TokenCodeEase2017Unspecifiedhttps://github.com/shamsa-abid/CodeEase
TokenSourcererCC2016Javahttps://github.com/Mondego/SourcererCC
TokenCCFinderSW2017Anyhttps://github.com/YuichiSemura/CCFinderSW
TokenNicad2011C / C# / Java / Python / WSDLhttps://www.txl.ca/txl-nicaddownload.html
PDGClone-Differentiator2011Java等https://sites.google.com/site/yinxingxue/home/projects/clonedifferentiator
MLAgec2013Javahttps://github.com/tos-kamiya/agec
MLLICCA2018Java / C / JavaScripthttps://github.com/tvislavski/licca
LearningMostaeen2018C/Javahttps://github.com/pseudoPixels/ML_CloneValidationFramework
TextBCFinder2018Binaryhttp://www.imm.dtu.dk/~sljo/bcfinder/gettingstarted.html
TextCCCD2013Chttp://www.se.rit.edu/~dkrutz/CCCD/index.html

References

[1] Walker A, Cerny T, Song E. Open-source tools and benchmarks for code-clone detection: past, present, and future trends[J]. ACM SIGAPP Applied Computing Review, 2020, 19(4): 28-39.
[2] Roy C K, Cordy J R, Koschke R. Comparison and evaluation of code clone detection techniques and tools: A qualitative approach[J]. Science of computer programming, 2009, 74(7): 470-495.

「一键投喂 软糖/蛋糕/布丁/牛奶/冰阔乐!」

薇拉航线

(๑>ڡ<)☆谢谢老板~

使用微信扫描二维码完成支付

Comments are closed.