基于代码克隆检测的代码来源分析方法

李 锁 吴毅坚 赵文耘

(复旦大学软件学院 上海 201203) (上海市数据科学重点实验室 上海 201203)

0 引 言

随着互联网的迅速发展以及开源代码生态系统的日益繁荣，网络上各种开源项目越来越多样化并且获取也更加便利。许多软件企业内部也通过软件资源库、外部开源软件、软件产品线及开发框架等方式建立了多种多样的软件复用开发方法，同时开发人员自身也会通过多种方式大量复用已有的软件资源。在这些软件复用方法和资源的支持下，软件系统和软件产品大量引入了开源软件、网络资源、商业软件等外部代码成分。近年来，如何自动化查找分析软件系统中的外部来源代码，已成为当前非常重要的研究方向。

代码成分随着软件项目之间的派生以及项目自身的持续演化而不断发展变化，并与自有代码成分不断融合。由此造成的问题是，大量关键性软件系统和产品中的代码来源成分复杂，其中许多源自外部的代码成分都存在安全漏洞、潜在缺陷或知识产权问题[1]。有些外部依赖还会导致软件研制和开发方无法完全掌握软件的持续演进方向[2]。外部引入的代码也使项目代码过于冗余，增加了系统的复杂度和软件维护成本，降低了代码的可理解性[3]。

本文提出一种基于代码克隆检测的代码来源分析方法，将待分析代码以方法为单位建模为Hash词袋，之后利用并行化Hash词袋模型算法找出目标系统代码在代码库中不同项目间的来源关系，最后生成代码来源报告。其目标在于，为软件从业者和普通用户提供一种代码来源分析方法。而用户所输入的代码数据可能是多种多样的，存在着多种不同的情况。因此，代码来源分析工具需要具备处理不同情况下用户所输入的代码，并对不同情况的代码提供统一的处理流程，同时提供统一的交互式图形化操作工具，使得用户无需关心工具的数据处理方式和流程，只需要进行目标系统代码的输入，执行简单的操作步骤便能够得到直观的结果。

1 相关工作

代码来源分析是指，针对特定目标软件系统，分析该系统中各部分组件与其他项目之间的关系，其目的是找出该系统中组件的可能外部来源，这些系统组件包括源代码文件、依赖库、类、方法、代码块等。代码来源分析旨在回答以下问题[4]：目标系统中某一特定组成部分可能来源于何处？

当前的代码来源分析主要基于代码克隆的研究。例如，Steidl等[5]针对开源系统中高达38.9%的文件具有不完整的历史，提出了一种基于提交(commit)的增量方法，以基于克隆信息和名称相似性重建代码历史。代码克隆，即相同或相似的代码片段[6]，是软件开发中的常见现象。开发人员经常利用代码克隆简化程序的编写，在提升程序开发速度的同时也带来了一些维护隐患。多年来，已经有大量研究专注于如何高效检测程序中的不同种类的代码克隆，从而对克隆代码有了更加清晰的认识。目前对克隆代码最普遍的分类是Bellon等[7]提出的，他们把克隆分为了以下四类：第一类是完全相同的代码片段；第二类是只有变量名、类型或其他名称、类型、格式等不同的代码片段；第三类是在第二类的基础上，增加、删除或修改过少量语句的代码片段；第四类是逻辑功能完全相同而实现方式不同的代码片段。

软件代码克隆检测在软件维护、软件结构优化等方面具有重要价值和意义。代码克隆有多种检测的方法，基于的不同的对象、不同的语言都有不同检测的方法。克隆代码检测使用的技术主要包括：文本检测法(text-based)[8]、符号检测法(token-based)[9]、抽象语法树检测法(AST-based)[10]、程序依赖图检测法(PDG-based)[11]、度量检测法(metric-based)[12]和深度学习检测法(Deep Learning-Based)[13]。

基于代码来源分析结果， 研究人员又提出了许多应用，其中主要包括软件谱系和演化分析。例如，张久杰等[14]基于软件多版本演化，根据克隆代码主题信息构建版本间克隆代码的映射关系，为演化过程中的克隆代码添加演化模式，分析演化特征并构建克隆谱系。Nguyen等[15]针对软件复用库中构件演化带来的客户代码同步演化问题，提出了一种基于图的API使用代码适应性演化方法。另外一些研究工作进一步提出了对演化中的克隆代码进行科学、有效的管理[16]，以及缺陷检测等[17]。

从现有技术基础来看，相关的研究工作主要集中在克隆检测和克隆代码的管理上，即使开展了对软件代码来源和演化历史的研究分析工作，其应用目标也主要是对项目内不同版本之间代码的演化轨迹进行描述。然而，如何全面、充分地对海量软件代码资源和其他相关资源，如代码项目信息、版本信息等，全方位地建立目标系统的代码来源关系，是本文关注的核心问题。

2 代码来源分析方法

代码来源分析对于软件开发人员和软件维护人员具有重要意义。软件产品上线与更新的速度加快，以及互联网的网络资源的高速发展，为软件开发与维护人员提供了大量可利用资源。因此，现在软件开发人员在开发软件系统时往往会参考一些开源项目的代码，而分析这些代码的来源对理解和维护软件系统的代码具有重要意义。

在本项目中代码来源是指给定代码块，基于代码克隆检测，找出该代码块在代码资源库中的可能来源。当有多个克隆代码实例时，代码来源根据项目和时间进行串接，会形成“来源链”。来源链是指根据一定来源相似性阈值，代码库中与该代码块具有克隆关系的代码实例。因为分析出来的代码来源有不同的置信度(来自克隆代码的相似度)，因此来源报告中会给出多个可能的来源。

代码来源分析过程如图1所示，主要分为：(1) 解析源代码文件，创建代码块词袋；(2) 词袋Hash化；(3) 创建代码块索引Hash表；(4)并行化克隆检测，得到目标系统代码来源对；(5)生成目标系统代码来源链，得到来源报告。

图1 代码来源分析过程

2.1 代码块的词袋化方法

任意一个软件项目P，可表示为一系列的代码块：{B1，B2，…，Bn}。代码块是任意一段具有特定起止边界的代码，有不同的粒度。常见的粒度包括文件、类、方法以及语言相关的多种亚方法粒度。一个代码块B由有限多个词构成。根据自然语言处理的机制，这样的一个代码块相当于一个文本片段，可进一步表示成词袋(bag-of-words)。词袋模型最早出现在自然语言处理(Natural Language Processing，NLP)和信息检索(Information Retrieval，IR)领域。该模型忽略文本的语法和语序等要素，将其仅仅看作是若干个词汇的集合，文档中每个单词的出现都是独立的。词袋模型使用一组无序的单词(words)来表达一段文字或一个文档。同时，由于代码的特殊性，可将代码中的关键词、标识符、运算符等符号以词为单位进行以对代码进行Token化(Tokenization)，表示为一串Token。因此，经过Token化后的代码块即表示为一个Token袋(bag-of-tokens)：B{T1，T2，…，Tk}，其中Ti是代码块B中的Token。由于Token可能出现重复，因此将Token与它在该代码块中的出现次数Frequency记作一个二元组(Token，Frequency)，作为代码块的Token袋组成元素。这种(Token，Frequency)表示法大大缩减了代码块的表示长度，也有助于提高检测相似代码片段的效率。

为了定量推断两个代码块是否是克隆，使用相似性函数来度量代码块之间的相似度，并返回一个非负值。该值越高，表示代码块之间的相似性越大。最终，具有高于指定阈值的相似度值的代码块被识别为克隆。

给定两个项目Px和Py，相似性函数f和一个阈值θ，目标是找到所有的代码克隆对(或者克隆组)Px.B和Py.B，使:

f(Px.B,Py.B)≥「θ·max(|Px.B|,|Py.B|)⎤

(1)

尽管相似性函数有很多选择，为了简单方便，计算使用重叠(Overlap)相似性函数，因为它直观地捕获了代码块之间重叠的概念。重叠相似性函数计算两个代码块共有的Token数，包含计算每个Token的频数。例如给定两个代码块Bx和By，重叠相似性函数OS(Bx,By)计算代码块Bx和By中重复Token的数量，即：

OS(Bx,By)=|Bx∩By|

(2)

具体地，如果指定等于0.8，并且max(|Px.B|,|Py.B|)为t，当Bx和By共有至少「θ·|t|⎤个Token重复时认为Bx和By是克隆对。注意，如果Token a在Bx中出现两次并在By三次出现，则由于Token a而导致的Bx和By之间的匹配为2。

本项目使用词法分析程序(例如TXL[18])对源代码文件进行扫描遍历，构建代码块词袋。通过词法分析程序给定语言的标记和块语义，识别并提取出源代码文件中的代码块，并为每个代码块分配一个整数标识，从而在后续处理中能够唯一标识每个代码块。

2.2 基于Hash词袋模型的克隆检测算法

2.2.1创建Hash词袋

本节将创建Hash词袋，也就是统计解析后的代码块(如方法)中每个词出现的频率，组成，以Token为键，Frequency为值创建该代码块的Hash词袋。

在传统的克隆检测算法中，所有Token都会被一一比较。但是，基于词袋模型的克隆检测算法将相同的Token只创建一个分别对应于 。这样词袋模型中的Token只需比较一次，如果该Token在该代码块中出现多次，也只创建该Token的一个索引，并将该Token出现的频率索引到该代码块Token的Hash表中，即将Token与该Token出现的频率索引到一个Hash表中。这不仅节省了空间，而且大大减少了索引数量，因此可以更快地进行后续匹配检索。目前已经能够对Java、C/C++、Python等语言进行源代码解析，创建Hash词袋。

2.2.2创建代码块索引Hash表

上一小节将代码块中Token和频率索引到Hash表中，接下来将以代码块为单位，将代码块索引到代码块Hash表中。源代码解析文件中包含多个代码块特征序列，不同的特征序列有不同或相同的Token数量，在此，将相同Token总量的序列索引到同一Hash表中。这样，在后面克隆检测的时候，可以利用性质1过滤掉许多无关代码块，大大减少候选集。

性质1：给定两个代码块Bx和By分别包含Nx和Ny个Token，对于给定相似度阈值为sim(0

Nx·sim≤Ny≤Nx/sim

(3)

创建代码块索引Hash表算法如算法1所示。该算法输入是解析后的源代码文件路径，也就是Hash词袋路径，输出是代码块索引Hash表。算法根据路径读取源代码解析文件并初始化数据(2-3行)，然后逐行读取文件中的代码块词袋序列，将代码块Token总量相同的词袋序列索引到同一Hash单元中(4-7行)。如果Hash表中已经存在该总量的词袋序列，则直接将词袋序列附件到该单元中，否则新建以该词袋序列为key的Hash单元，并将该词袋序列添加到该单元中(8-16行)。

算法1创建代码块索引Hash表算法

1: function GetHashTable(parseFilePath){

2: file = parseFilePath

3: while((line = file.readLine()) != null){

4: blockID = getBlockID(line)

5: blockSize = getBlockSize(line)

6: tokenMap = getTokenMap(line)

7: node = Node(blockID, tokenMap)

8: if(sizeMap.containsKey(blockSize)){

9: blockList = sizeMap.get(blockSize)

10: blockList.add(node)

11: }else{

12: blockList = newLinkedList

13: blockList.add(node)

14: sizeMap.put(blockSize,blockList)

15: }

16: }

17: return sizeMap

18: }

2.2.3并行化代码来源关系检测

并行化来源关系检测算法根据性质1，计算出目标代码块的Token总量的上限和下限，即upSize和lowSize，将上限和下限之外的其他代码库中的代码块直接排除，大大减少候选代码块的数量。算法伪代码如算法2所示。

算法2并行化代码来源检测算法

1: function ConcurrentDetection(sim, lines, sizeMap)

2: doubleCore 2*Runtime.availableProcessors()

3: exec = Executors.newFixedThreadPool(doubleCore)

4: for(int i=0; i

5: increment = lines.length / doubleCore + 1

6: start = increment ? i

7: end = increment ? (i + 1)

8: if(lines.length < end){

9: end = lines.length

10: }

11: subPairs = Calculator(lines; start; end; sim; sizeMap)

13: tasks.add(subPairs)

14: if(!exec.isShutdown()){

15: exec.submit(task)

16: }

17: }

18: return getResult()

19: }

20:

21: function Calculator(lines, start, end, sim, sizeMap){

22: for(int iline=0; iline

23: for(int i=lowSize; i

24: cList = sizeMap.get(i)

25: if(cList != null){

26: for(cNode in cList){

27: cID = cNode.blockID

28: cMap = cNode.map

29: for(wBag in mBag){

30: mWord = getWord(wBag)

31: mFreq = getFrequency(wBag)

32: if(cMap.containsKey(mWord)){

33: canFreq = getFrequency(mWord)

34: wordC = min(mFreq, canFreq)

35: }

36: }

37: if(wordC / mSize >= sim){

38: subPairs = subPairs + mID + cID

39: }

40: }

41: }

42: }

43: }

44: }

该算法输入是来源相似性阈值、目标项目词袋路径、代码库索引Hash表，输出是目标项目代码来源关系对。算法首先根据主机CPU核心数创建相应数量的线程，接着根据不同线程拆分任务，使来源关系检测并行化运行(1-19行)。Calculator函数根据线程参数，执行具体的克隆检测(21-44行)。首先获取待检测代码块词袋(参数lines)，并逐行读取词袋并进行克隆检测(22-44行)；然后计算出目标代码块的Token数量的上限和下限(22-23行)，从下限Token数量开始循环遍历代码块索引Hash表(23-44行)。如果已经匹配的Token总数大于等于相似性阈值，则将目标代码ID与候选代码ID加入到克隆对中，表示这两个代码块是克隆代码，结束匹配(37-38)。

2.3 构建代码来源链

由于我们的系统的输入对象是多项目多版本的，不管是演化图谱的提取还是跨项目的检测对比时都会面临时间线不一致的情况，故采取对项目演化历史时间进行对齐的方案：对于大量的项目，按照不同项目release的时间先后版本对齐，接着执行基于Hash词袋模型的克隆检测算法找到待检测项目中的代码块在代码库中不同项目的来源关系，利用不同项目内release版本的时间先后顺序，找到待检测项目中代码块在代码库中不同项目的来源关系，时间最早的release代码块作为目标系统代码的来源，其他的代码块根据不同置信度作为可能来源信息。

3 实验与案例分析

3.1 性 能

为了检测工具效率，我们从开源代码库中随机选择文件来构建不同大小代码行数的输入。使用Unix工具cloc[19]测量代码行数，并且仅包含代码，不包含注释或空行。我们选择的目标项目代码行数为1.27 MLOC，代码库中选择的代码行数从6.75 MLOC到120 MLOC不等。环境和设置：所有实验均在配备Intel i7-7820X CPU(8核，16线程)、SAMSUNG 970 EVO 1T SSD和SAMSUNG DDR4 2400 RECC 32GB RAM的单个服务器上运行。工具配置为检测长于10行的代码行数。相似性设定为0.6，相对较低的阈值可能产生更多的产出，因此执行时间应该接近上限。如果将相似度设置得更高以获得更好的精度，则执行时间会更短。

执行时间结果如表1所示。实验结果表明，当目标系统代码为1.27 MLOC(百万行)，代码库中选取代码行数为10 MLOC的来源关系检测用时1小时14分钟，相同的目标系统代码，在代码库中选取代码行数为100 MLOC的来源关系检测用时16小时27分钟。

表1 执行时间

3.2 召回率与准确率

由于到目前为止并没有代码来源的基准库，我们参考了代码克隆中用于评估召回率的The Mutation and Injection Framework[20]框架，这是一种综合基准框架，用于评估工具在突变分析程序中对数千个细粒度人工代码克隆的召回率。

以Java语言编写的kubernetes-clint项目为例，这是一个开源的kubernetes客户端软件项目。我们在目标软件项目中随机选择了10个不同的方法级代码片段；然后将这10个代码片段分别手动修改50%和70%，再将这些修改后的变异代码片段随机注入小规模代码库中；最后利用我们的工具检测目标项目kubernetes-clint在注入变异代码片段的代码库中进行来源检测。检测来源相似度阈值设置为70%，进行多次检测取其平均值。其他编程语言也做类似的处理，最终检测结果如表2所示。

表2 召回率

传统的克隆代码召回率主要评估某段或者某些代码在整个数据集中的查全率问题。与传统克隆代码召回率相比，代码来源的召回率主要评估目标系统中代码片段在代码库中其他项目的来源关系。其中不仅包含了相似性代码片段的检测，还包含了该段代码所在的代码库信息、项目信息、结构信息等。

通过手动验证其输出的随机样本来估计工具的准确率，这是典型的方法。我们从工具的结果中随机选择了实验中检测到的200个代码来源关系对。每个克隆对由两位评委独立验证，如果存在冲突，则在与第三位评委讨论后做出最终决定。最终在函数粒度的检测上，我们的工具准确率达到95%，误报主要存在于非常短的函数片段中，因为函数片段越小，单个词的相对权重就越大，对结果又比较大的影响。而在代码块粒度的检测上，我们的工具准确率为85%，误报的原因与函数片段类似。

3.3 案例分析

针对单个项目不同的release版本中的代码来源关系，我们以Linux内核中包含的arch模块代码为例，研究arch模块中部分代码在Linux和FreeBSD不同发布版本之间的来源关系。我们在arch模块中选取了长度大小适中的void acct_process(void)函数，目的是研究该段代码在不同Linux和FreeBSD发布版本中的来源关系，也就是要找出该段代码在哪些Linux内核版本中出现过。void acct_process(void)函数只是static void do_acct_process(struct file *file)函数的包装器，而static void do_acct_process(struct file *file)函数的主要功能是调用者保存对文件的引用。void acct_process(void)函数代码片段如下：

void acct_process(void){

struct file *file = NULL;

//accelerate the common fastpath:

if (!acct_globals.file)

return;

spin_lock(&acct_globals.lock);

file = acct_globals.file;

if (unlikely(!file)) {

spin_unlock(&acct_globals.lock);

return;

}

get_file(file);

spin_unlock(&acct_globals.lock);

do_acct_process(file);

fput(file);

}

由于Linux和FreeBSD中release版本众多，我们选取了具有代表性的Linux-2.5.75、Linux-2.6.0、Linux-3.2.3、Linux-3.10.1版本和FreeBSD-7.3、FreeBSD-9.1、FreeBSD-11.0版本。结果显示arch模块中void acct_process(void)函数在Linux-2.6.0、Linux-3.2.3和FreeBSD-9.1中出现过，在Linux-3.10.1和FreeBSD-11.0其他版本中并未出现，结果如图2所示。

图2 arch模块在Linux和FreeBSD中代码来源

针对多个项目的代码来源关系，我们分析了android-xbmcremote项目在不同来源项目中的来源关系。android-xbmcremote 是GitHub上Android开源项目，我们的代码库选取了50个开源项目。其中android-xbmcremote中public boolean equals(Object o)函数代码在当前代码资源库中，来自5个项目，完全相同的代码最早出现在Spring-Framework项目的3.2.18版本中，有70%相似的代码最早出现在ElasticSearch项目，因此我们认为它可能来自Spring-Framework项目、ElasticSearc项目、Spring-boot项目。由于代码资源库中的项目和版本有限，因此所得到的结论仅能参考。但本文所提的方法是通用的，并且可以通过并行化方式在更大规模的代码资源库中使用。

3.4 有效性威胁

内部有效性威胁：所提的方法目前仅是以代码克隆为手段的，由于代码可能会发生持续演化，因此对演化的分析可能是本方法的弱点，难以找到由于持续演化而不再是克隆的可能来源片段。但是由于本方法对克隆检测是逐版本进行的，因此一定程度上缓解了版本演化的矛盾，可以在一定的置信度内找到演化的代码来源关系。

外部有效性威胁：目前只对两个待测系统进行了来源分析，并且代码资源库中的代码量也只有千万行级，因此本方法对于其他类型或语言的项目的来源检测效果仍有待考量。但我们在选择项目时考虑了不同时间、不同规模的项目，从而所选项目具有一定的代表性，这表明在符合特定条件的情况下，本方法具有通用性。

4 结 语

本文提出了一种基于Hash词袋模型的跨项目的大规模代码来源分析方法，设计并实现了一个大规模代码库的代码来源追踪系统。该系统首先提取代码词袋模型，然后利用词袋模型设计并实现了一个并行化的代码来源算法，找出目标项目在代码库中的来源关系。该系统能够在多个项目之间找到不同克隆代码的来源关系，辅助软件维护人员作出相应的软件维护决策。实验结果表明，该系统能够有效地找出目标项目在大规模代码库中的代码来源信息。

本文下一步工作将考虑代码演化，进一步细分置信度，使来源分析更精确；同时也将扩展数据规模，优化算法，提升效率。