0 引言

近年来，开源代码已成为许多重要行业软件源代码的基础，在新思科技2022年的《开源安全和风险分析》报告^[1]中，共审查了计算机硬件和半导体、网络安全、物联网等17个行业的2 409个商业代码库。审查结果显示，97%的代码库中包含开源代码，并且在所有被审查的商业代码库中开源代码的平均占比高达78%。通过大量引入开源代码可以降低软件开发的成本、提升软件开发的效率，但同时也带来了许多问题。审查结果显示，81%的代码库至少存在1个安全漏洞，53%的代码库中存在许可证冲突的开源组件，20%的代码库中存在未使用许可证的开源代码，85%的代码库中存在至少4年未更新的开源依赖项。可见引入开源代码会给软件带来巨大的潜在风险。

代码溯源对于提高代码可追踪性、改进代码管理具有重要意义。代码溯源是指通过对包含开源软件等在内的混源(mixed-source)软件^[2]代码结构或组成等特征进行扫描分析，对软件代码源头、许可证、版权、作者等信息进行扫描和检测，以获取软件衍生相关联信息。代码溯源的相关问题一直在被广泛研究，主要包括软件成分分析(software component analysis，SCA)^[3]、安全漏洞识别^[4]、许可证合规性风险分析^[5]三个子方向。软件成分分析是指通过扫描软件源代码或者二进制文件来实现对软件的识别、管理和追踪。代码克隆检测^[6]是软件成分分析的一种重要技术手段，通过对软件代码和开源代码库中的代码进行一定的预处理，然后进行信息抽取并对代码进行表征，最后使用相似度算法进行对比，检测出克隆代码。虽然常见的商用和开源代码溯源软件可检测出开源代码库与被测软件之间的克隆代码，但是无法判定克隆代码之间的继承关系。判定克隆代码之间的继承关系是指分辨出克隆代码对中的原始代码片段(clone fragment，CF)与克隆代码片段。当前，开源代码库中的开源代码数量巨大，代码克隆检测的结果往往是代码片段或者代码文件的集合，通过分析溯源结果中克隆代码的继承关系，可以进一步筛选溯源结果，帮助用户发现软件中开源代码的来源和代码的演化过程。

到目前为止，关于克隆代码继承关系的研究工作还相对较少。已有的代表性工作有文献[7]提出的基于版本信息判断克隆代码对中原始代码片段和克隆代码片段的算法，通过对克隆代码对版本信息的分析来判定克隆代码继承关系，算法在处理长度不同的克隆代码时，通过移除代码片段末尾一部分代码行使克隆代码的长度一致后，进而判定其继承关系，但克隆对中存在原始代码被修改的情况，且代码片段任何位置的代码都可能被修改，所以仅通过移除尾部代码行的方式会误判继承关系，并且其主要分析软件项目克隆代码的继承关系，未涉及跨项目软件代码的分析。另外文献[5]通过分析克隆代码之间的继承关系研究开源社区中的许可证合规性风险，该方法通过比较代码片段中所有代码行最终提交时间的均值来判定它们之间的继承关系，对于存在时间较长的克隆对，其均值相对较小，若在近期对原始代码片段进行部分修改，可能会导致原始代码的均值大于克隆代码的均值，从而误判克隆对的继承关系。文献[8]提出了一种基于代码溯源的开源软件演进过程量化分析方法，通过对开源操作系统等软件的不同版本进行相似度对比，帮助开发人员分析软件不同版本的稳定性和成熟度，同时，该软件基于特征矩阵克隆检测方法^[9]进行相似性对比，在处理大规模代码时仍具备较高效率。但该方法工作重点在于研究同一软件不同版本源代码的继承关系，不支持跨软件的克隆代码的继承关系分析。

基于上述分析，本文提出了CloneIRD(clone code inheritance relationship determination)，一种基于演进信息的判定代码溯源结果中克隆代码继承关系的方法。该方法主要包括两方面内容：一是设计并实现了一个基于代码克隆检测技术的代码溯源分析框架，通过框架可以实现对软件源代码的溯源分析，并且在框架中选取了自研克隆检测工具FastDCF用于软件源代码成分分析，FastDCF基于词法的部分索引代码特征提取和分析方式，其分布式并行计算的特点使其在处理代码溯源分析任务时可以兼顾检测效率和效果^[10]；二是提出了一种基于演化信息的克隆代码继承关系判定算法(evolution information based code inheritance relationship determination algorithm，EIHR)，该算法首先利用版本控制系统Git提取克隆代码的演化信息，进行一定的处理后得到每个代码片段的演化信息序列，然后使用改进版的莱温斯坦距离算法^[11]对克隆代码的演化信息序列进行分析比较，最终得到克隆代码对的继承关系。文中在Linux内核V4.9和V4.12的开源代码上进行了实验，验证了CloneIRD方法的有效性。

1 相关工作 1.1 代码溯源分析

代码溯源分析在工业界和学术界被广泛研究，包括商业软件Synopsis Blackduck^[12]和FOSSID^[13]，开源工具CLASC^[2]等典型研究工作。

Blackduck是一套功能强大的商业软件工具，用于管理因在应用程序和容器中使用开源而产生的安全性、许可证合规性和代码质量风险。通过将源代码扫描与深度二进制检查相结合，提供软件成分分析解决方案，帮助将与开源和其他第三方软件相关的风险降至最低。Blackduck可以在软件生命周期的每个阶段查找并修复安全漏洞，并针对具体漏洞提供详细的补救指导和技术见解，而且支持快速分析供应商提供的二进制文件，无须访问源代码便可以识别软件中的安全风险，还通过使用业界最大的开源知识库来识别应用程序中开源代码的许可证，从而消除开源许可证不合规的风险并保护用户的知识产权。

FOSSID是一个商用的代码溯源分析工具，能够全面、准确、高效地发现用户代码库中的开源代码及其风险，能够单独部署使用，也可以集成到软件开发流程中。FOSSID通过扫描软件源代码，与开源代码知识库进行比对，发现软件中存在的开源代码。不论是整个开源组件的引用，还是仅仅引用了一小段代码片段，FOSSID都可以有效地发现并展示软件涉及的开源许可证及相关的合规性风险，也能够发现并展示这些开源软件存在的安全漏洞。

CLASC是一个在组件级别上自动区分操作系统代码来源的算法。CLASC根据组件中的代码成分，将组件分为开源组件、混源组件、自研组件3类，首先通过分析组件的修改日志，得到所有参与代码开发和修改工作的作者信息，然后将作者划分为内部开发者和开源开发者两类，最后依据组件作者的人员构成来判断组件类别，实现对大规模混源操作系统源代码的追溯和管理。

如今，代码库中的开源代码平均占比超过70%^[1]，上述研究工作在帮助识别大规模代码中的开源成分、发现软件中存在的安全漏洞以及许可证违规风险方面具有重要意义。但是随着开源规模的不断扩大，开源代码库中的数据量也越来越大，在开源代码库中可能有多个代码片段与被检测软件中的代码匹配为克隆代码，自动化判定克隆代码的继承关系可以帮助减轻人工确认开源成分的负担，提升溯源效率。

1.2 克隆代码的继承关系判定

代码克隆的研究有超过20年的历史^[14]，代码克隆研究可以简单总结为两个问题：一是如何找到克隆代码，二是找到克隆代码之后如何分析与利用。第一个问题即研究代码克隆检测问题，第二个问题即研究代码克隆的分析^[15-16]与代码克隆的管理^[17-18]。克隆代码继承关系的相关研究属于第二个问题的范畴，即通过判定克隆代码对之间的继承关系，达到对克隆代码进行分析和管理的目的。

目前，关于克隆代码继承关系的研究工作还相对较少。文献[7]提出了一个基于演化信息区分克隆代码对中原始代码片段和克隆代码片段的方法。该方法通过逐行比对两个时间版本信息序列判定克隆代码对的继承关系，并且考虑修改克隆代码的情况，方法中设置了容忍度参数来处理长度不同的克隆代码对。作者在ArgoUML和Apache两个开源软件上进行了实验研究，结果显示，当忽略源代码中的注释内容并且允许一定的误差存在时，提出的判定方法可以区分大多数克隆代码对的继承关系。但是没有考虑克隆对中的原始代码片段被修改的情况，即使原始代码片段中仅有微小的修改，仍然会导致继承关系的误判。

文献[5]通过分析克隆代码之间的继承关系来研究开源社区中存在的许可证合规性风险，利用GitHub构建了一个由Java项目组成的开源代码库，使用经过改进的SourcererCC^[19]方法检测代码库中的克隆代码对，然后同样利用代码的版本信息来判定克隆代码对的继承关系，不同之处在于该方法把一个代码片段中所有代码行最终修改时间的均值作为该代码片段的最终修改时间，通过比对两个代码片段的最终修改时间来判定克隆代码片段之间的继承关系，根据继承关系来分析许可证违规风险。通过计算代码片段中所有代码修改时间的均值来判定继承关系，这种方式会因为个别代码行发生变动使得代码片段修改时间的均值发生较大变化，导致误判克隆对的继承关系，进而影响对许可证合规性风险的分析。

2 CloneIRD: 克隆代码继承关系的判定 2.1 方法概述

本文的方法主要包括两部分内容：一部分是设计一个可判定代码溯源结果中克隆代码继承关系的总体框架，该框架可以实现代码溯源中软件成分分析的基础功能，即通过扫描软件源代码，识别软件与开源代码库之间的克隆代码；然后判定克隆代码中两个代码片段的继承关系，生成代码溯源结果。另一部分是设计一个可判定克隆代码继承关系的算法，利用从版本控制系统中提取出克隆代码片段的演化信息，实现自动化判定克隆代码继承关系的方法。

2.2 CloneIRD的总体框架

基于2.1节的设计目标，实现了CloneIRD的总体框架，框架由克隆代码检测、演化信息提取、继承关系判定3个子模块组成。图 1为方法的整体框架图。

首先从代码仓库获取包含代码演化信息的软件源代码，对其进行预处理后，进行克隆代码检测，对检测结果进行处理，筛除软件内部的克隆代码对，仅保留被检测软件与开源代码库之间的克隆代码对；然后将得到的克隆代码检测结果映射到文件中，并提取对应的代码演化信息；最后将演化信息输入继承关系判定算法，得到包含继承关系的代码溯源结果。下面对框架中的克隆代码检测、演化信息提取、继承关系判定三部分详细阐述。

2.3 代码克隆检测工具的选取

不同的代码克隆检测方法有各自的特征与优、缺点，为判定代码溯源结果中克隆代码的继承关系，首先需要选择合适的代码克隆检测工具来处理大规模代码的溯源分析任务，检测出克隆代码。针对大规模代码的克隆检测方法有很多，可以分为非分布式克隆检测方法和分布式克隆检测方法两种类别。

NiCad是一种基于文本的单节点处理方法^[20]，它使用最长公共子序列算法来比较源代码，可以检测类型1、类型2和类型3的克隆。SourcererCC^[19]和CloneWorks^[21]也是非分布式方法，使用基于符号(Token)的单节点方式来检测克隆代码。虽然这些方法提高了大规模代码克隆检测的效率，但由于单个节点的资源有限，这些方法存在瓶颈。

随着硬件能力的提升和虚拟化技术的发展，针对克隆检测的分布式和并行处理优化技术逐渐兴起。IBFET是一种基于索引的方法^[22]，但并不是一个完全分布式的克隆检测工具，其预处理和特征提取等核心步骤没有并行化，这会显著影响整体效率，如果代码规模非常大，这些非分布式运行的核心步骤将成为算法性能的瓶颈。

为提高大规模代码成分溯源的效率，选取自研克隆检测工具FastDCF作为克隆检测引擎。FastDCF是由作者所在研究团队研发的采用分布式并行计算框架支持的基于部分索引的克隆检测工具^[23]。通过对计算密集的代码预处理、索引生成、克隆检测等任务的分布式并行化，有效解决了因单个节点资源不足而无法进行大规模检测的问题；通过采用子块过滤算法和多线程优化的手段，进一步提升了执行速度。FastDCF采用了基于TXL的灵活的代码预处理方式，能够有效支持多种语言、多种粒度的检测，非常适用于代码溯源分析中大规模代码的克隆检测任务。

2.4 代码演化信息的提取

本文中判定克隆代码之间的继承关系是指分辨克隆代码对之间的原始代码片段和克隆代码片段，即两个代码片段在时间上出现的先后顺序, 所以需要通过综合考虑代码片段中所有代码的演化信息，来判定两个代码片段之间的继承关系。Git是一个开源的分布式版本控制系统，因为可以有效、高速地处理从很小到非常大的项目版本管理任务，被用于全球最大的开源及私有软件托管平台GitHub的代码管理工具。

Git允许开发人员使用git blame命令获取源代码最近一次的修改信息，包括提交ID、修改者、修改时间、行号、源代码5项内容，本文中在判定克隆代码继承关系时，通过分析代码片段演化信息中的修改时间来判定代码片段之间的继承关系。

2.5 基于演化信息的克隆代码继承关系判定算法

本节设计了一个基于演化信息的克隆代码继承关系判定方法EIHR，自动区分克隆对中的原始代码片段和克隆代码片段。在阐述方法之前，首先对方法中使用的符号进行说明。CF(s, l, f)表示一个代码片段，其中：f表示代码片段所在的文件；s表示代码片段的首行是文件中第s行代码；l表示代码片段共有l行代码。(CF₁, CF₂)表示一个克隆对，V(f, n)表示代码文件f中第n行代码的演化信息。

2.5.1 强限定条件下克隆对的继承关系判定

在l₁=l₂的前提下，判定继承关系时会有以下3种情况。

Identical: 即克隆代码对CF₁和CF₂的每行代码有着完全相同的演化信息，则认为CF₁和CF₂完全相同，

$\forall{ }_{i=0, \cdots, l_1-1} V\left(f_1, s_1+i\right)=V\left(f_2, s_2+i\right) 。$

(1)

Copied: CF₁中每一行代码演化信息中的提交时间都晚于CF₂中相对应的代码，即CF₁克隆自CF₂；相反，则CF₂克隆自CF₁，

$\left\{\begin{array}{l}\forall_{i=0, \cdots, l_1-1} V\left(f_1, s_1+i\right)>V\left(f_2, s_2+i\right), \\ \forall_{i=0, \cdots, l_1-1} V\left(f_1, s_1+i\right)<V\left(f_2, s_2+i\right) 。\end{array}\right.$

(2)

Unclassifiable：即除Identical和Copied之外的所有情况都属于该类，划属于该类别的克隆代码对，尽管在内容上其相似度很高，但在时间维度上，无法区分其继承关系。

上述分类方式不仅要求克隆对中的代码片段长度相同，而且克隆对中原始代码片段的改动可能会导致该克隆对的继承关系被误判，所以需要对克隆对进行一定的预处理后再判定其继承关系。

2.5.2 预处理后克隆对的继承关系判定

对于一个代码片段CF(s, l, f)，其代码演化信息可以表示为R(v₁, v₂, …, v_l)，其中

$v_i=V(f, s+i-1) 。$

(3)

判断克隆对(CF₁, CF₂)之间的继承关系，等同于比较CF₁、CF₂的演化信息序列R₁和R₂。

考虑克隆对中代码片段长度不相同和克隆对中原始代码片段被修改的情况，在进行克隆对的继承关系判定时，可以对代码片段的演化信息序列进行一定的处理，以应对上述情形。对演化信息序列的处理有增加元素、删除元素、修改元素三种，处理操作的上限定义为容忍度参数(t)。假设处理操作d次后，使得克隆对的继承关系为Identical或Copied，可以使用经改进的莱温斯坦距离(Levenshtein distance)来处理R₁和R₂，计算出d的值，具体改进方式如下。

1) d₌: 对R₁和R₂进行d₌次处理操作后，使R₁和R₂长度相同，且对应元素相同；

2) d_≥: 对R₁和R₂进行d_≥次处理操作后，使R₁和R₂长度相同，且R₁中对应元素均大于等于R₂中对应元素；

3) d_≤: 对R₁和R₂进行d_≤次处理操作后，使R₁和R₂长度相同，且R₁中对应元素均小于等于R₂中对应元素。

比较计算的d与人为设定的t，判定预处理后的克隆对的继承关系。

Identical: 当d₌≤t时，克隆对的继承关系为Identical；

Copied: 当d_≥≤t或d_≤≤t时，克隆对的继承关系为Copied；

Unclassifiable: 当不属于上述两种情况时，克隆对的继承关系为Unclassifiable。

3 实验与分析 3.1 克隆检测的性能分析

首先将该框架中所采用的FastDCF与国际上三个具有代表性的快速非分布式克隆检测工具CloneWorks、NiCad和SourcererCC进行比较。实验结果如表 1所示。随着输入的代码行数逐渐增大，FastDCF相比其他工具的性能优势愈加明显，且NiCad和SourcererCC在代码行数达到一定规模时，其检测时间超过了24 h，在表中标记为“—”。当输入的代码行规模达到250 M时，FastDCF的效率是CloneWorks的8倍。

然后将FastDCF与Hummel、IBFET两个具有代表性的分布式克隆检测方法进行比较。表 2展示了FastDCF克隆检测技术与其他基于索引的分布式克隆检测技术的比较结果。Hummel的方法只能检测类型1(T-1)和类型2(T-2)的克隆，且花费的时间远多于IBFET和FastDCF。IBFET和FastDCF均支持T-1、T-2和类型3(T-3)克隆，而FastDCF在执行时间方面相较IBFET有明显的优势。

3.2 基于CloneIRD的继承关系判定结果分析

在本节中，使用基于代码演化信息的继承关系判定方法，对代码溯源结果中克隆代码的继承关系进行判定，以验证算法的有效性。

首先选取了两个不同版本的Linux内核V4.9和V4.12作为实验数据集，然后使用FastDCF算法对其进行检测，过滤掉每个版本内部的克隆代码对之后，从最终的检测结果中随机抽取了604个克隆代码对作为输入，使用本文设计的判定算法对其继承关系进行判定。表 3展示了t=0时604个克隆代码对继承关系的判定结果。其中77.5%的克隆代码对的继承关系被判定为Identical，8.3%的克隆代码对的继承关系被判定为Copied，这符合我们所选数据集的真实情况，Linux内核从V4.9演进到V4.12，其中大部分的源代码没有被改动，少部分的代码有局部改动，极少部分代码回撤至V4.9更早的版本。

表 4展示了t=1, 2, 3时，克隆代码对继承关系的统计结果，当t=1时相较于t=0，Unclassifiable的克隆代码对减少了38%。当t=3时相较于t=0，Unclassifiable的克隆代码对减少了86%，而继承关系为Identical的克隆代码对仅增加了10个，减少的Unclassifiable继承关系的克隆代码对中至少有86.5%变为Copied类型的继承关系。

在实验中，绝大多数克隆代码对的继承关系为Identical或Copied类型，当允许较小的误差存在时，Copied类型的继承关系的数量会增加。同时，通过实际案例证明即使被判定为克隆代码的两个代码片段，可以通过克隆代码继承关系判定方法，把不存在继承关系的克隆代码对过滤掉，以提升代码溯源的质量和效率，帮助软件开发和维护人员更准确高效地了解软件中的开源代码成分。

3.3 继承关系判定算法EIHR的有效性验证

在本节中我们通过手动检查3.2节中的继承关系判定结果，验证EIHR算法的有效性。首先在t=1时，随机抽取20%的克隆对继承判定结果作为验证集，通过综合分析代码片段所属文件的目录结构、代码内容以及代码演化信息，验证克隆代码继承关系是否正确。表 5为人工判定结果和EIHR判定结果的对比分析。

对比结果显示，EIHR判定结果中94个克隆对的继承关系为Identical，16个克隆对的继承关系为Copied，经与人工判定结果比较，上述110个判定结果的准确率为100%，而EIHR判定结果中11个被判定为Unclassifiable的继承关系在人工判定时，3个被判定为Identical，8个被判定为Copied。经验证，这是由于容忍度参数的值较小导致的，当t=8时，EIHR的判定结果与人工判定结果一致。

在对EIHR算法的准确性进行验证之后，还需要对其运行效率进行分析。首先将3.2节中所用数据集的代码文件随机分为4组，每组中代码文件数量相同，而后分别对上述4组代码文件进行代码克隆检测和克隆代码的继承关系判定，并记录克隆检测和继承关系判定所耗时长。

表 6为各组数据克隆检测和继承关系判定的耗时。不同组别的耗时情况基本相同，克隆检测耗时1 s左右，继承关系判定相较克隆检测耗时则非常小，约为0.1 s，仅为克隆检测耗时的1/10，所以对代码溯源结果中的克隆代码进行继承关系判定，不会对代码溯源的效率产生较大影响。

4 总结

本文提出了一个可判定代码溯源结果中克隆代码继承关系的方法CloneIRD，该方法主要包括一个基于代码克隆检测技术的代码溯源分析框架和一种基于演化信息的克隆代码继承关系判定算法EIHR。框架中FastDCF基于词法的部分索引代码特征提取和分析方式及其分布式并行计算的特点使得它在处理代码溯源分析任务时可以兼顾检测效率和效果。EIHR算法使用改进版的莱温斯坦距离算法对构建的克隆代码的演化信息序列进行分析比较，得到克隆对的继承关系。在Linux内核V4.9和V4.12的开源代码上进行了实验，验证了CloneIRD方法的有效性。

未来，需要对所提方法进行改进，考虑根据克隆代码长度自动调整容忍度参数，进一步提升判定方法的准确率。另外，也可考虑分析大规模软件克隆谱系中的继承关系^[24-26]。