截至2017年10月，GitHub^[1]托管的开源项目已达到6 800万个，OpenHub^[2]索引的代码已超过370亿行，Sonatype^[3]托管的开源组件下载次数已达到520亿次。由于具备成本、效率等方面的优势，复用开源软件已成为当前主流的开发形态。目前全球78%的IT企业主要产品构建在开源软件之上，只有不到3%的企业没有使用任何开源软件^[4]。

开源软件尽管开放源代码，但也附带了相应的许可证限制。这些许可证的要求不尽相同，甚至相互冲突^[5]。比如，GPL许可证^[6]强制衍生产品必须公开源代码，而Apache 2.0许可证^[7]则无此限制。近年来，随着开源软件复用程度的日益加深，许可证侵权风险愈发突出。2008年，思科的Linksys产品被起诉侵犯了coreutils、wget等产品的许可证，法院判决思科败诉^[8]。2009年，Westinghouse、JVC等14家厂商复用了BusyBox开源软件，但未遵守该软件的许可证规定，遭到了原作者的连环诉讼^[9]。2016年，Google的Android系统被诉侵犯了Java API的使用许可，遭Oracle索赔90亿美元^[10]。

为避免许可证侵权可能导致的严重后果，近年来出现了一些自动侦测开源许可证的研究成果^[11-13]。其核心思路是扫描源文件中的特定关键词，据此判定许可证类型。这类方法自动化程度较高，但有2方面局限性：1)很多开源项目并不包含上述关键词，导致无法侦测；2)开源项目通常也广泛复用了别的开源代码，文[14-15]报告这一比例约为14%~23%。受限于开源软件的开发习惯，这些复用的代码往往并未严格甄别，可能与复用项目自身存在许可证冲突^[16]。显然，这种情况下的许可证侦测结果是不准确的。尽管Black Duck^[17]、Palamida^[18]公司提供开源代码的侵权检测服务，但由于是商业公司的版权产品，其内部机制和核心算法并未公开。

解决上述问题需要利用代码溯源技术，从源头厘清开源代码的复用历史。目前常见的代码溯源方法主要来自编译领域，这些方法采用批处理模式。典型流程是读入所有工程文件，批量分析处理。在中小规模项目中，这些传统方法可以很好地实现代码溯源目标，但应用于大规模开源代码分析时，分析速度慢、响应不及时，难以有效满足大规模开源代码的分析需求。以Apache Web Server为例，其代码仓库(code repository)^[19]中有多达176万个快照^[20]。要检测Apache Web Server中的代码是否被其他项目复用了，理论上需要对上述所有快照执行分析，因为被复用的代码可能存在于任何一个快照中。传统的程序分析方法不支持代码仓库的增量分析，这将导致巨大的计算和存储代价。

为了应对上述问题，本文提出了一种开源代码仓库增量分析方法，能够有效减小计算和存储规模，加快大规模开源代码仓库的分析效率。

1 算法设计和实现

开源代码有多种不同的复用形式，既可以复用整个源文件，也可以复用源文件中的代码片段。本文算法以函数为基本分析单元，将项目视为源文件的组合，将源文件视为函数的组合，忽略函数以外的其他语法成分。

图 1给出了本文提出的增量分析方法的整体流程，包括如下4个步骤：

1) 从开源代码库中检索出代码快照；

2) 分析快照，获得每个快照与前一快照的代码变更；

3) 设计映射算法，将上述代码变更转换成可分析的完整函数；

4) 计算函数指纹，利用指纹进行函数比对。

步骤1中，可通过SVN、Git命令获取快照。步骤2中，可通过SVN-Diff、Git-Diff工具获得快照间的代码变更^[21]。上述两步骤实现比较简单，本文不再赘述。步骤3通过映射算法，将代码变更转换成可分析的完整函数。步骤4将函数转换成对应的指纹，据此进行比对。步骤3、4是本文增量分析方法的关键，节1.1和1.2对其进行详细介绍。

1.1 代码变更转换成完整函数的映射算法

开源项目广泛采用SVN、Git等版本控制系统。为避免提交冲突，开发者倾向于采用小规模、频繁的代码提交模式。因此，在代码仓库中相邻快照间的差异通常非常小。Estublier^[19]的研究显示，其平均相似度约为98%。传统的开源代码仓库分析方法没有利用相邻快照高度相似这一特点，只执行完整的语法分析，大量代码分析是冗余的，因而时空复杂度较高。本文方法只处理快照间的差异部分，据此实现高效的增量分析。

步骤2中得到只是快照间的代码变更，考虑到实际的代码修改习惯，上述变更通常并非可分析的完整函数。本文以函数作为复用代码的最小检测单元，因此需要将上述代码变更转换成可分析的完整函数。算法1给出了该映射算法的伪代码。

算法1  代码变更转换为完整函数的映射算法。

输入：快照(snapshot)编号N (N≥1)

输出：快照N包含的所有函数集合F_n

1. FuncList GetFuncList (Snapshot N) {

2.  FuncList F_n=Φ //初始化为空

3.  IF (N=1) { //第1个快照

4.    //第1个快照中的所有函数都是完整的，

5.    //直接分析该快照所有源文件中的函数信息，

6.    //并获得每个函数的名字、返回值类型、

7.    //参数类型、起止行号信息

8.    F_n=快照1中的所有函数

9.  }

10. ELSE IF (N＞1) { //第2个及以后的快照

11.    //第N个快照中的函数可通过该快照与

12.    //前一快照的代码变更T_n、前一快照中

13.    //的函数集合F_n-1计算获得

14.    ChangedText T_n=快照N与N-1的代码变更

15.    //递归调用，获得前一快照中的所有函数

16.    FuncList F_n-1=GetFuncList (N-1)

17.    //根据T_n、F_n-1计算当前快照N中的函数

18.    F_n=CalFunc (N，T_n，F_n-1)

19.   }

20.  RETURN F_n

21. }

输入：当前快照编号N；当前快照和前一快照的代码变更T；前一快照中的所有函数集合F_n-1

输出：当前快照N中包含的所有函数集合

22. FuncList CalFunc (Snapshot N，

23.        ChangedText T，

24.        FuncList F_n-1) {

25.  // F_m存储快照N-1中已有的、且在快照N中

26.  //被修改了的函数集合

27.  // F_e存储快照N-1中不存在的、在快照N中

28.  //新增加的函数集合

29.  // T_e存储快照N中新增部分的代码变更

30.  FuncList F_m =Φ，F_e =Φ//初始化为空集

31.  ChangedText T_e = “” //初始化为空字符串

32.  //遍历代码变更T中的每处变更m

33.  FOREACH m in T {

34.    //获得变更代码m的起止行号信息

35.    int X = m的起始行号

36.    int cnt = m中增加和删除的代码行差值

37.    IF (cnt＜0) { //删除操作

38.     //根据F_n-1中各函数的起止行号和m的

39.     //起止行号，找到对应的函数。这些函

40.     //数在上一快照中存在，但在本快照中

41.     //已删除，因此计算当前快照中的函数

42.     //时，应将这些函数删除

43.     FuncList F_d=根据(F_n-1，X，cnt)计算已删

44.                        除的函数集合

45.     F_n-1 = F_n-1 - F_d//从F_n-1中剔除

46.   }

47.   ELSE { //编辑或增加操作

48.    //对比行号找出修改的函数F_k。此处的

49.    //修改函数是指，在本快照和前一快照

50.    //中都存在的函数，即在同一源文件

51.    //中，函数名、返回值类型、参数类型

52.    //相同，但函数体不同的函数

53.    FuncList F_k=根据(F_n-1，X，cnt)计算修

54.                        改的函数集合

55.    F_n-1 = F_n-1-F_k //从F_n-1中剔除

56.    FuncList F_k′ =更新F_k中的函数行号，

57.                        并重新扫描分析，得到

58.                        更新后的函数集合

59.    //将F_k′加入到修改函数集合F_m中

60.    F_m = F_m + F_k′

61.    }

62.    //当修改行号范围超出前一快照的所有

63.    //函数时，抽取上述函数范围外的代码

64.    //变更m′。m′中可能包含本快照中新增

65.    //的函数

66.    T_e = T_e+m′

67.    }

68.    //扫描集合T_e，找出快照N中新增的函数，

69.    //将其加入新增函数集合F_e

70.   FOREACH t in T_e {

71.    //扫描t中的代码，获得其中包含的完整

72.    //函数，并记录其起止行号信息

73.    FuncList F_t=分析获得t中的函数

74.    F_e=F_e+F_t

75.   }

76.   RETURN F_n-1+F_m+F_e

77. }

算法1将快照间的代码变更转换成可分析的完整函数，包括2个主要函数：GetFuncList(第1~21行)和CalFunc(第22~77行)。其中，以“//”开头的为程序注释，其他语句为有效代码。

GetFuncList函数中，首先判断当前快照是否是第1个快照。若是，执行完整语法分析，获得该快照的完整函数集合(第3~9行)。若非第1个快照，则利用版本控制工具获得当前快照和前一快照的代码变更T_n(第14行，对应图 1中的步骤1~2)。然后递归调用GetFuncList，获得快照N-1中的所有函数集合F_n-1(第16行)。基于T_n和F_n-1，调用辅助函数CalFunc，计算当前快照中包含的函数集合F_n(第18行)，并返回该函数集合(第20行)。

CalFunc函数中，首先声明3个变量F_m、F_e和T_e。其中：F_m存储当前快照和前一快照中均存在、但在当前快照中已修改的函数；F_e存储当前快照中存在、但在前一快照中不存在的函数，即当前快照中新增的函数；T_e存储当前快照中新增的代码变更(第25~31行)。当前快照N中的函数包括3部分：1)当前快照中修改的函数F_m；2)当前快照新增的函数F_e；3)当前快照和上一快照中都存在且未修改的函数。其中，第3部分中的函数是通过前一快照中的所有函数去掉当前快照中已删除的函数(第37~46行)和当前快照中已修改的函数(第47~55行)得到的。由于函数体已修改，因此需要重新扫描、分析当前快照中已修改的函数，将得到的函数加入到修改函数集合F_m中(第56~60行)。通过分析上一快照中的所有函数及其起止行号信息，结合代码变更中的起止行号信息，可以得到当前快照中新增的代码变更T_e(第62~66行)。T_e中可能会增加新的函数，因此需要对其扫描，获得新增的函数集合F_e(第68~74行)。最后，返回上述3部分函数，得到快照N中的所有函数(第76行)。

上述伪代码中，除了代码变更处理、函数范围比较、新增函数检测3部分外，其他地方均较为直观。下面重点介绍这3部分内容。

1) 代码变更处理。

在代码控制系统中，通常以文本块形式存储代码变更。例如，常见的Git版本控制系统以一个或多个hunk来存储快照间的代码变更，其格式如图 2所示。

每个hunk的第1行记录了起始行号X(from-file-line-numbers)和修改计数C(to-file-line-numbers)，在接下来的C行中记录具体修改操作，其格式为：[增加|删除] [具体代码]。例如，在某个文件中修改了第10行代码，那么在其hunk记录中起始行号为10、修改计数为2，接下来第一行记录是：[删除] [原有的第：10行代码]，第2行记录是：[增加] [修改后的第：10行代码]。Hunk的详细格式见文[22]。

2) 函数范围比较。

依据上述代码变更格式可知，对于每处变更m，其起始行号X(CalFunc函数第35行)能直接从hunk中获得，而修改行数cnt(第36行)可通过计算增加行数和删除行数的差值获得，即当m中增加的行数为p且删除的行数为q时，cnt等于p-q。当cnt为负数时，表示变更m是删除操作；当cnt为非负数时，表示变更m是编辑或增加操作。

函数集合F_n-1中记录了前一快照中所有函数的起止范围，与修改范围(X，cnt)对比，可找出前一快照中删除的函数F_d(第43~44行)和修改的函数F_k(第53~54行)。从F_n-1中剔除F_d、F_k(第45、55行)，可得到当前快照和前一快照中相同的函数集合。由于F_k已被修改，因此新快照中应重新分析这些函数，得到函数集合F_k′(第59行)。

3) 新增函数检测。

当修改范围(X，cnt)超出前一快照的所有函数范围时(第62~66行)，代表当前快照中新增加了代码，其中可能包括新增的函数。为此，构建新增代码变更T_e，对其扫描分析获得新增函数集合F_e(第68~74行)。

该过程需要构建一个轻量级的语法分析器，对T_e中的代码进行扫描，获得其中的函数，并记录函数名、起止行号、返回值类型、参数类型等信息。针对Java语言的文法规则，本文利用Flex和Bison编写了分析器，详见本文的实验部分。图 3给出了Java语言中的函数定义。

通过上述分析可看出，CalFunc函数中只需要对当前快照中修改的函数F_m和新增的函数F_e进行分析，当前快照和上一快照中相同的函数则无需重复分析。考虑到版本控制系统中相邻快照间的高度相似性，与两快照间未修改的函数相比，F_m和F_e的数量通常很小，这样就有效减少了分析处理规模。

1.2 指纹算法

借助上述映射算法，已将代码变更转换成可分析的完整函数集合。为方便处理，实践中通常将源代码处理成某种中间格式，基于此格式进行比对。常用的中间格式有4种：纯文本(Text)^[23-24]、标识符(Token)^[25-26]、抽象语法树(abstract syntax tree，AST)^[27-29]、程序依赖图(program dependency graph，PDG)^[30-33]。纯文本格式将源代码视作普通文本，利用文本比对算法比对，优点是速度快，缺点是无法处理变量重命名等代码等价变换，也不能忽略注释等无效语法成分。标识符格式通过词、语法分析，将源代码转换成Token序列，基于Token比对，分析效率较纯文本略低，但能有效处理变量重命名等代码等价变换，也能滤除注释等无效语法成分。AST和PDG格式除了能处理变量更名、滤除注释外，还能获得更精细的语法结构信息，不仅能比对整个函数，还能对函数内的局部片段进行比对，但分析效率较标识符和纯文本格式要低得多^[26]。

考虑到开源软件复用时，最小粒度通常都是函数级别的，很少需要对函数内的片段进行比对，综合4种中间格式的处理能力和分析效率，本文选择标识符(Token)格式作为中间格式。

函数比对时，不仅需要判别2个函数是否完全相同，还需要计算2个函数是否相似。传统的克隆代码检测方法将上述相似度检测称为2型克隆检测，这方面的研究成果很多^[34-35]，但其主要场景服务于代码的重构和维护，如bug侦测及修复等。这些方法能很好地进行2型克隆检测，但比对效率较低，难以满足大规模开源代码中函数的高效比对需求。

理想的比对算法应满足以下3个直观要求：1)能检测完全相同的函数复用；2)能检测不完全相同但相似的函数复用；3)分析和比对速度快，能适应大规模开源代码的比对需求。本文结合了Token中间格式和自然语言处理中的N-gram模型，设计了针对开源代码复用函数检测的函数指纹算法。通过词、语法分析，得到Token序列，之后将Token序列转换成N-gram文本，据此获得函数指纹，并通过相似度算法来判别函数的相似性。采用N-gram模型的原因是，该模型支持高效的函数指纹生成，同时能有效保留函数间的语法差异，因而相似的函数其函数指纹也相似^[36]。

本文设计的指纹算法包括Token序列生成、N-gram指纹构造、相似度计算3个步骤。

1.2.1 Token序列生成

本文利用Flex和Bison生成了分析工具，将源代码中的语句转换为Token序列，同时忽略部分无关标记以缩减计算规模。例如，变量声明语句“int a = 0”，其词法分割为“INTEGER ID_a ASSIGN NUM_0 SC”，简化后Token序列为“INTEGER ID_a NUM_0”。

1.2.2 N-gram指纹构造

将上述获得的Token序列进行划分，生成对应的N-gram集合，并统计其频度，最后计算N-gram指纹。用于自然语言文本时，每个gram代表一个字符或一个词。在本文中，gram代表一个Token。N的取值将影响相似度计算结果。文[37]对N的取值策略进行了论述，并给出了详细的计算过程。本文参考了该文献的结果，取N=4。表 1给出了N-gram指纹生成过程的示例，根据每个Token出现的频度分配独立的索引号，然后计算每个gram的索引值之和，例如“ID_a”出现的频度最高，分配其索引值为1，其他Token按照使用顺序依次分配，N-gram序列则由上述索引标记和其频度组合构成。

1.2.3 相似度计算

常见的N-gram相似度计算方法包括：余弦相似度(cosine similarity)、Euclidean距离(Euclidean distance)和Manhattan距离(Manhattan distance)3种。相较于前2种方法，Manhattan距离算法只需要进行整型计算，运算速度较快，精度最高^[38]。本文采用Manhattan距离算法来计算2个N-gram指纹的相似度：

$ \begin{array}{l} {\rm{distManhattan = }}\sum\limits_{i = 1}^n {\left| {{p_i} - {q_i}} \right|} , \\ \;\;\;\;\;\;\;\;{T_d} = \frac{{{\rm{distManhattan}}}}{{\sum\limits_{i = 1}^n {{\rm{Max}}\left( {{p_i}, {q_i}} \right)} }}. \end{array} $

其中: p、q代表着2个待计算相似度的N-gram指纹；p_i、q_i表示在各自的N-gram指纹中第i个索引标记的频度；n是2个N-gram指纹中索引标记的计数总和；T_d表示两者间的相似度，其值越小代表二者的相似度越高。当T_d=0时，认定2个函数相同。

利用本文算法，可将开源项目中的函数转换成对应的函数指纹。借助该指纹值，进行函数分析结果的存储、查询和比对。

2 实验

为了验证本文方法的有效性，设计了4组实验。实验1验证单一文件的分析能力，实验2验证完整项目的分析能力，实验3验证指纹算法的有效性，实验4验证代码复用关系的分析能力。

基于以下2点原因，本文选择Java语言作为分析对象：1)流行度高，2017年11月的TIOBE编程语言排行榜显示^[39]，Java语言排名第1；2)代表性好，Java语法具有中等规模复杂性，具有典型命令式编程语言的各种语法特征，容易扩展到其他程序设计语言。

本文选择Redisson开源项目(2017-11-03版本)作为实验分析对象。Redisson是架设在Redis基础上的一个Java驻内存数据网格(in-memory data grid)，更多信息详见文[40]。

2.1 实验1：单一文件分析

实验1选取/redisson/src/main/java/org/redisson路径下的3个修改频率较高的文件作为分析对象：RedissonMap.java、RedissonExecutorService.java、Redisson.java。在开源代码仓库中，这些文件存在于257个快照中，共有1 033个版本。利用本文方法分析，总计得到37 349个函数，其中相邻快照间修改的函数数目为1 924，占函数总数的5.2%。

表 2给出了每个文件最旧的和最新的6个快照的函数修改情况。表 2中，“初始函数数”表示源文件在代码仓库中第1个版本中的函数数。“修改函数数”的前3列表示最旧的3个快照中的函数修改数量，后3列表示最新的3个快照中的函数修改数量。

从表 2可以看出，与传统的完整分析方法相比，本文方法有效减少了需要分析的函数数量。传统方法总计需要分析37 349个函数，而本文方法只需要分析修改过的1 924个函数，后者只占前者的5.2%。假定每个函数的平均分析速度相同，那么增量算法的分析速度可视为提高了近19倍。

2.2 实验2：完整项目分析

Redisson在开源代码仓库中共有3 066个快照，源文件234万个。实验2分析了最新的3个快照(编号为3064、3065和3066)，实验数据见表 3。3个快照中的总函数数目分别为94 402、94 387、94 465，而修改函数数分别为212、243、74，修改函数数占总函数数的比例分别为0.22%、0.26%、0.08%。

从实验2数据可以看出，从完整项目层面得到的结论与实验1类似，即对一个完整项目而言，每次版本变动中被修改的函数也只占很小比例，绝大部分未修改的函数无需进行分析。

2.3 实验3：函数指纹算法有效性验证

为了验证函数指纹算法的有效性和函数比对的准确性，实验3将源文件RedissonMap.java进行变换，包括2类：第1类变换不改变函数原有语义，例如替换变量命名、修改注释等；第2类变换改变函数的语义，例如修改循环结构、添加表达式等，之后计算变换后得到函数的相似度。

变换后得到的源文件中，有438个跟变换前相同的函数, 90个不同的函数。其中，第1类变换的函数为30个，第2类变换的函数为60个。图 4-6展示了同一函数在2种不同的变换后的区别，图 4表示原始的函数，图 5修改了变量名称，图 6对语句进行了较大程度的修改。

本文采用的相似度阈值为0.2。当2个函数的Manhattan距离为0时，认定为相同的函数。当二者的距离大于0小于0.2认定为相似的函数。当二者距离大于0.2时，认定为不同的函数。最终的比对结果如图 7所示。

从图 7可以看出，所有相同的438个函数都被正确检测出了；第1类变换的函数应该认定是相似的，应被检测出30个，实际检测出了33个，其中有3个函数进行了第2类变换，但修改内容控制在区分不同函数的阈值要求之内，因此属于相似函数；第2类变换的函数应认定是不同的，应被检测出60个，实际检测出了57个，原因是其中的3个函数修改幅度较小，未达到0.2的阈值要求。从上述实验结果可看出，指纹算法能很好地识别相同的函数，对近似函数也有很好的识别能力。该实验虽然针对的是单一文件，但容易扩展到整个项目，只需对项目中的文件递归处理即可。

2.4 实验4：代码复用关系分析

实验4选取了Hibernate-Redis开源项目(2017-11-29版本)作为分析对象，该项目在Hibernate的基础上增加了Redis用于二级缓存服务，支持Redisson 2.3以上的版本。

实验部署了Hibernate-Redis项目环境，其中引用的Hibernate版本为5.2.12，引用的Redisson版本为2.9.0。在实验环境下，提取了项目所使用的Redisson组件，共391个Java文件，从中获得了29 615个函数指纹。

在实验环境下，Redisson并非被完整复用，因此以实验环境中已复用的29 615个函数作为基数计算相似度结果。同时，挑选并分析了Redisson版本号2.6.0至3.1.0间的6个发布版本，并为每个版本的所有函数生成了函数指纹，并将实验中提取到的29 615个函数指纹与这6个版本的函数指纹进行了相似度计算，实验结果如表 4所示。

表 4中相同函数数和相似函数数由“实验3”得到的阈值判定，相同函数数与相似函数数之和与总体的29 615个函数的比值即为最终的相似度比例。相似度比例越高，两者具有复用关系的可能性越大。图 8更为清晰地展示了相似度比例的具体情况。

从图 8可以看出，版本号为2.9.0的Redisson与实验所部署的Hibernate-Redis存在最高的相似比例，在上述5个版本中最有可能被Hibernate-Redis复用。该分析结果与实际的实验配置环境一致，证明了本文方法能有效分析代码复用关系，具备代码溯源能力。

3 结论

本文从挖掘分析开源代码仓库的角度出发，通过分析快照，设计了代码变更映射算法，构造了增量函数数组，并提出了一种改进的函数指纹算法，结合N-gram模型来实现对近似函数的判断识别。基于增量函数数组和函数指纹，设计了一种增量的开源代码仓库分析方法，据此进行函数复用比对。该方法有效利用了快照间高度相似这一特性，具有良好的时空复杂度，能满足大规模开源代码仓库的分析需求。