SLACC Simion-based Language Agnostic Code Clones

SLACC: Simion-based Language Agnostic Code Clones

摘要

• 跨语言克隆检测技术可以使研究人员和开发人员创建健壮的语言迁移工具，在精通一门编程语言的时候快速学习更多的编程语言。
• 跨语言克隆检测面临着没有共同底层表示的挑战。为了解决这个问题，可以采用两种方法：静态分析框架（通过匹配不同语言的代码结构和特性）或动态分析框架（通过比较代码的运行时行为）。
• 本文提出一种跨语言克隆检测的动态分析方法——SLACC，使用输入/输出匹配克隆，通过增加输入的数量及涵盖更多的数据类型来克服之前的工作的局限性，检测到更多的的相似代码片段，生成更好的代码集群（clusters）。
• 与最近的Java克隆检测工具HitoshiIO相比，SLACC检索到的集群数是HitoshiIO的6倍，并且具有更高的精确度（86.7% vs 30.7%）
• 本文是第一个针对动态类型语言进行克隆检测的工作，也是第一个针对缺乏共同底层表示的语言进行克隆检测的工作。本文为实现可扩展语言迁移工具的更大目标迈出了第一步。

跨语言克隆检测技术是一种用于检测和识别不同编程语言之间相似代码片段的技术。

1 介绍

1.1 背景与意义

• 现在程序员通常使用多种编程语言来构建系统。

  调查显示，工业软件项目中平均拥有7种不同语言，开源软件项目中通常包含2-5种编程语言。研究表明，在学习新语言时，程序员倾向于尝试使用先前已学会的语言知识，这种方法被称为“跨语言学习策略”。

• 传统代码克隆检测通常只适用于单一编程语言，在现代编程环境和应用场景中效果有限。这些应用场景包括：

  • 迁移软件中的漏洞检测：将软件从一种语言移植到另一种语言时，克隆检测可以帮助发现潜在的漏洞；
  • 通过重构维护代码质量：克隆检测可以识别相似的代码片段，帮助开发者进行有针对性的重构；
  • 产品安全性保护：安全团队使用克隆检测扫描生产软件中可能存在的其他漏洞代码实例，以提升代码安全性。、

1.2 本文贡献

• 本文提出一种基于Simion的语言无关代码克隆检测技术(SLACC)，基于代码的行为来识别相似的代码片段，特点如下：
  • 跨语言语义克隆检测：SLACC能够在不同编程语言之间检测语义上相似的代码片段；
  • 检测整段或部分方法或函数：SLACC不仅可以匹配完整的方法或函数，也可以匹配部分方法或函数的相似性；
  • 支持静态和动态语言：SLACC适用于静态类型语言(如Java)和动态类型语言(如Python)；
  • 无需注释或手动干预：SLACC不需要额外的人工干预，例如手动添加测试输入；
• SLACC通过比较代码片段的输入/输出(I/O)关系来检测语义克隆，这种方式称为Simion(similar input output functions)，具体原理如下：
  • SLACC将目标代码库分割成较小的、可执行的函数片段；
  • 使用自定义的输入生成器来创建函数的参数，这个生成器借鉴了灰盒测试和多模态分布的理念；
  • SLACC利用生成的参数执行这些函数，根据它们的返回值将它们聚类。聚类的相似性度量基于代码片段的IO行为，而与其语法特种无关。
• 实验验证与结果：
  • 单一静态类型语言测试：SLACC在Google Code Jam（GCJ）的19,188个Java函数上进行了实验，结果显示SLACC比HitoshiIO（SOTA模型）检测到6倍多的克隆，并且精度更高（86.7% vs 30.7%）；
  • 单一动态类型语言实验：首次探索动态类型语言的克隆检测，在17,215个来自GCJ的Python函数上进行实验，SLACC在检测行为克隆方面的精度达到87.3%；
  • 跨语言克隆检测：SLACC在跨语言克隆检测中，发现了32个包含Python和Java函数的聚类，这表明代码克隆的检测不依赖于相同的类型系统。
• 提出了一种开源工具，用于检测不同编程语言之间的语义代码克隆。

2 SLACC

• 代码克隆可广泛性地分为四类，如表1所示。

  • 类型1，2，3为语法克隆，根据代码结构估计代码之间的相似性；
  • 类型4为语义或行为克隆，根据功能估计代码之间的相似性；

  语法代码克隆检测技术对于跨语言代码克隆检测来说是不切实际的，因此它需要语言语法之间的显式映射。这对于语法相似的语言（如 Java 和 C# ）是可行的，但对于语法差异较大的语言（如 Java 和 Python）则较为困难。而语义上的跨语言代码克隆检测方法主要依赖于大量的跨语言训练示例。但这种方法通常是在语法相似的编程语言上进行测试的，对于语法差异大的语言来说，效果可能并不理想。

• SLACC是一种基于语义的代码克隆检测方法，利用大型冗余代码库来进行相似性检测

  • 与依赖于预定义的规则来映射API翻译或者使用嵌入式的API翻译的传统的跨语言代码相似性检测方法不同，SLACC使用输入/输出（I/O）示例来根据代码的行为对其进行聚类；

    预定义规则映射API翻译：这种方法使用预先定义好的规则集，将一种编程语言中的API或函数调用映射到另一种编程语言中对应的API或函数。例如，将Java中的APISystem.out.println()函数映射为Python中的print()函数；

    使用嵌入式的API翻译：这种方法通常使用一种自动化工具或算法来从大量代码示例中学习API映射规则。该方法通过分析多语言代码库，自动识别出语言之间的API对应关系。例如，可以通过机器学习技术训练模型来自动将Java API映射到Python API。

  • SLACC放宽了跨编程语言的数据类型约束，使得动态类型代码（如Python）可以与静态类型代码（如Java）一起被聚类。即使不同编程语言的数据类型不同，也可以根据相似的行为被识别为相似的代码克隆。

• SLACC工作流程，如图1所示：

  1.代码分段； 2.函数创建； 3. 输入生成； 4.函数执行； 5.克隆检测；

2.1 代码分段

将项目中所有源文件中的代码分解成较小的代码片段(snippets)，每个片段的代码至少由最小行数(MIN_STMT)的连续代码块组成。代码块可以是：

• 申明语句，如 int x；
• 赋值语句，如 x = 5；
• 块语句，如 static {x = 10;}
• 循环语句，如for， while， do-while
• 条件语句，如if-else-if，switch
• Try语句，如try， try-catch

分段算法如算法1所示。

PreorderTraverse:先序遍历

2.2 函数创建

将代码片段转换为可执行的函数。

1. 推断函数的参数，返回变量。采用了与Su等人类似的数据流分析方法。

   • 返回变量的推断

     首先将在片段中被定义或修改的变量当作潜在返回变量，如果一个变量的最后一次定义是一个常数值，则将该变量从潜在返回变量中移除；

   • 参数的推断

     将在代码片段中使用但是没有被定义的变量当作参数，此外如果一个变量在类中被声明为public static，那么不会将该变量当作参数。

   对于每一个潜在返回变量，创建一个函数。

2. 推断类型。

   • 在静态语言中，通过静态代码分析来推断参数的类型和返回变量的类型。

   • 在动态语言中，通过解析代码，在上下文中寻找与这些参数相关的常量变量来推断动态类型语言中的参数类型。

     动态语言中参数可能接受多种类型的输入，动态语言中的变量类型在运行时才决定。如：

     def main(a): 
     	print a
     

     本文采用的推断技术目前已经应用于推断动态语言JavaScript的数据类型。

   示例：在下面这段python代码中，因此n与整数比较大小，所以n的类型被推断为int

   def fib(n): 
   	if n <= 1: return n 
   	return fib(n-1) + fib(n-2)
   

3. 将对象返回类型转换为函数

   如果一个代码片段返回一个对象，则将这个对象简化为多个函数，分别独立地返回这个对象的所有非私有成员。

   例如：

   

   func_s返回一个对象类型的变量，则将func_s拆分成两个分别返回该对象length和width属性的函数func_l和func_w。由于height是私有成员，所以不创建返回height属性的函数。

4. 参数顺序的排列组合

   由于参数的顺序可能影响函数的行为，因此对输入参数ARGS进行重排，生成$|ARGS|!$个不同的函数，同时为避免参数数量增加导致排列数量指数级增长，设置了一个上限，即每个函数中参与分析的参数数量不超过某个值（称为 ARGS_MAX）。

2.3 输入生成

为函数生成输入，并对这些输入进行聚类分析。

• 创建输入

  基于参数的类型，使用一种受到灰盒测试和多模态分布启发的自定义输入生成器来生成输入，具体步骤：

  1. 解析源代码并识别出每种类型的常量
  2. 为每种类型声明一个多模态分布(包含多个峰值的概率分布)，这些峰值对应代码中常量的值
  3. 从这些多模态分布中采样出不同类型的值，作为函数的输入

  在本文实验中，作者为每个函数生成了256个输入。

• 备忘录(Memoization)技术

  对于具有相同参数类型的函数，为了保证比较的公平性和一致性，使用一组相同的输入来比较它们的行为。实现方法：

  • 使用一个数据库和一个输入生成器。输入生成器首先根据给定的参数类型生成一组样本输入，并将这些输入存储在数据库中。当后续的函数具有相同的参数类型时，可以直接从数据库中取出已经存储的输入值，而不必再次生成。

​ 该方法同样可以提高在函数测试过程的效率和一致性。

• 支持的参数类型

  SLACC目前支持四种类型的参数，以及为这些参数生成输入。

  1. 基本类型

     对于基本类型，通过从多模态分布中采样来生成输入。这些基本类型包括了整数（以及长整型、短整型）、浮点数（以及双精度浮点数）、字符、布尔值和字符串。

  2. 对象类型

     对于对象类型，SLACC递归地展开对象的构造函数，并对其中的基本类型生成输入。例如，如果一个对象的构造函数需要整数作为参数，输入生成器将为这些整数生成相应的输入值。

  3. 数组类型

     对于数组类型，首先使用输入生成器为数组生成一个随机大小。然后，根据数组的类型（基本类型或对象类型），为数组中的每个元素生成一个值。例如，如果数组是由整数组成的，输入生成器将生成整数数组；如果是对象数组，输入生成器则会递归地为每个对象生成相应的输入。

  4. 文件类型

     文件以字符串形式存储在数据库中作为共享资源池。如果提供了种子文件(seed file)，这些文件会被随机修改后存储为字符串；如果没有提供种子文件，则从多模态分布中采样常量并存储为字符串。当某个参数需要一个文件类型（或其扩展类型）的输入时，系统会使用存储的字符串创建一个临时文件对象（程序结束时删除），并将其作为输入传递给函数。

• 类型大小限制

  • 不同编程语言中，同一种数据类型可能具有不同的内存大小。例如，在Java中，有4种整数数据类型：byte（1字节）、short（2字节）、int（4字节）和long（8字节）。而在Python中，整数类型只有两种：int（相当于Java的long）和long（具有无限长度）。
  • 为了在不同语言间进行代码片段的比较，需要确保数据类型的大小是兼容的。因此，本文在生成函数输入时，采用了较小的类型限制。也就是说，会基于两种编程语言中较小的类型界限生成输入。

2.4 函数执行

在生成了输入集之后，系统会对这些输入集执行已创建的函数，并存储函数的返回值。

• 执行时间限制：为每个执行的函数赋予一个时间限制（$T_L$秒）。如果函数在这个时间内没有完成执行，就会触发一个超时异常（Timeout Exception）。

  这种超时通常发生在函数中存在无限循环的情况下。

• 独立线程执行：每个执行的函数都是在一个独立的线程上进行。确保当一个函数遇到了无限循环或其他阻塞问题时不会影响到其他函数的执行。

• 结果存储：每个函数执行完成后，存储：1）返回值 2）运行时间 3）在执行过程中是否出现了异常

2.5 克隆检测

在SLACC的最后阶段，系统会对执行过的函数进行克隆识别。克隆识别的目标是找到那些功能上相似或相同的代码片段，即“克隆代码”。

识别方法：基于输入输出的聚类，即将具有相似输入和输出行为的函数归为一类。SLACC采用了一种称为“代表性分区策略”(representative-based partitioning strategy)的方法对执行过的函数进行聚类。

• 相似性测量

  • 如果对于任何给定的输入，两个函数都返回相同的输出，则认为这两个函数具有最高的相似语义性。

  • 这两个函数的相似性值通过它们在相同输入下返回相同输出的次数除以总输入次数来计算，值越高相似性越高(最高为1)。

  • 比较的条件：只有当两个函数具有相同的参数数量并且参数类型可以进行转换时，才对它们进行比较

    例如对于函数f1(int a, String b), f2(long a, File b), f3(File a, String b) 和 f4(String a)：

    f1和f2之间可以比较，因为int可以转换为long；

    f1，f2不能和f3进行比较，因为基本类型不能转换为文件类型

    f1，f2，f3不能和f4比较，因为参数数量不同

• 聚类

  每个函数根据与已有聚类的相似性来决定是否被添加到某个聚类中。当一个函数与某个聚类中的代表函数（最早加入该聚类的函数）相似度达到或超过预定义的阈值时，该函数就会被添加到该聚类中。算法步骤如下：

  1. 初始化一个空的聚类集合(line 4)
  2. 对每个函数（line 5）依次处理，将其与已有的每个聚类进行比较（line 6）
  3. 如果该函数与当前聚类的代表函数的相似度超过了预定义的相似度阈值SIM_T（line 8），则将该函数加入该聚类（line 9）
  4. 如果函数不属于任何已有的聚类（line 11），则为它创建一个单独的聚类（singleton cluster，单例聚类，line 12），并将该函数设置为该聚类的代表函数（line 13）
  5. 最后，将这个新的单例聚类添加到聚类集合中（line 14）

3 评估

3.1 研究问题

• SLACC在静态语言中语义克隆检测的有效性
• SLACC在动态语言中语义克隆检测的有效性
• SLACC在跨语言语义克隆检测的有效性

3.2 数据集

2011年到2014年Google Code Jam (GCJ)第五轮的第一个问题的有效提交。

GCJ是一个由Google主办的年度编程竞赛。参赛者解决提供的编程问题，并提交他们的解决方案，Google会对这些提交进行测试。通过Google测试的提交被认为是有效的，并会在线发布。

数据集概述，见下表2

• 共考虑247个项目，其中170个Java项目，77个Python项目
• Java项目：170个Java提交共包含885个方法，生成了19,188个Java函数
• Python项目：77个Python提交包含301个方法，生成了17,215个Python函数。

3.3 实验设置

超参数

• 片段的最小长短MIN_STM：2
• 参数的最大数量ARG_MAX：5
• 每个片段函数的执行次数：256
• 相似度阈值：SIM_T：1.0(意味着两个函数必须产生完全相同的输出才认为它们是克隆的)

3.4 评价指标

• 簇(Clusters)的个数：簇是具有共同属性的函数的集合，该度量是由克隆检测算法产生的聚类数目，用|Clusters|、#Clusters或#C表示
• 克隆(Clones)的个数：属于一个簇的函数成为一个克隆。该度量是一个克隆检测算法生成的所有簇中函数的总数。用|Clones|、#Clone或者#M表示
• 假阳性(False Positives)的个数：指包含一个或多个函数的簇，这些函数不符合簇的相似性度量。用 |FalsePositive|、#FalsePositives 或#FP 表示

3.5 基线模型

• HitoshiIO，一个适用于Java虚拟机语言(如Java和Scala)的用于识别功能克隆的工具

• 自动AST比较。由于目前还没有在动态语言中检测语义代码克隆的工作，因此将SLACC与基于AST的方法进行基准测试，以检测动态语言中的语义代码克隆。

  • 首先将代码分割成片段，然后为每个片段生成抽象语法树（AST）。对于Java，使用JavaParser工具；对于Python，使用Python AST模块。
  • 通过比较AST来测量代码片段的相似性。如果AST完全相同或差异不超过一个节点，则认为它们是克隆的。

• 手动AST跨语言比较。在跨语言代码克隆的情况下，由于不同语言的抽象语法树（AST）格式差异，自动化AST比较方法无法直接应用。为了解决这个问题，作者对具有极其相似输出的跨语言代码片段进行人工验证。方法如下：

  • 随机抽取了100万对Java函数和Python函数。

  • 如果输入和输出类型兼容，并且对于相同的输入，输出相同或相差一个一致的值，则进一步进行AST相似度的人工评估。

    一致性标准：

    ​ 原始数据类型：

    ​ 布尔值或数值：输出之间有常量差异（如布尔值或数值），或常量比例，则认为它们是一致的

    ​ 字符串：使用Levenshtein距离（编辑距离）来衡量一致性，即输出之间的编辑距离是否一致

    ​ 对象类型：对象的一致性是指对象的每个成员是否一致

    ​ 数组类型：数组的一致性是指数组中所有对应的成员是否一致

​ 结果：在616对相似的函数对中，所有对函数的AST要么完全相同，要么最多相差一个节点，符合类型-III克隆（即结构相似或差异不大）。

3.6 精确度分析

SLACC 和 HitoshiIO 都是基于函数的输入/输出关系进行聚类的。然而，在不同的输入集合下，一些函数可能会生成不同的输出，从而导致它们不再是克隆，这样的聚类被标记为假阳性并被视为无效，检测和分析假阳性的方法：

• SLACC假阳性检测：对SLACC生成的聚类使用一组新的256个输入进行重新执行。新的输入集合是通过基于三角分布的随机模糊生成的。如果在新的输入集合中，有任何方法未被重新分配到原聚类中，则整个聚类被标记为假阳性。

• HitoshiIO假阳性检测：随机模糊测试输入文件32次生成一个大小为原始文件32倍的新测试文件。重新执行HitoshiIO，生成新的克隆对，并将其聚类，如果新聚类与原始聚类不匹配，则标记为假阳性。

• AST比较的假阳性检测：将聚类中的AST转换为函数，对这些函数进行256个输入的重新执行，并检查假阳性。任何包含不同方法的聚类被标记为假阳性

4 结果

4.1 静态语言

885个Java方法生成了19,188个Java函数，其中：

• SLACC能够支持其中的691个Java方法，在这691个方法中生成了18,497个函数。

• 从这些生成的函数中，有4,180个被标记为克隆，占总生成函数的22%

• 这些克隆被划分为632个聚类

• 4,180个克隆中有4,038个来自方法中的部分片段，称为语句级(statement level)克隆，其余142个克隆来自完整的方法，称为方法级(method level)克隆

在885个Java方法中

• 方法级克隆对比：

  • HitoshiIO检测到43个方法，这些方法被分为13个克隆聚类。在13个聚类中，有9个被标记为假阳性，精确度为30.7%。HitoshiIO的有效聚类包含20个方法；

  • SLACC检测到142个方法，这些方法被分为15个克隆聚类。在15个聚类中，只有2个被标记为假阳性，精确度为86.7%。SLACC的有效聚类包含135个方法。

​ 表3展示了每种方法的有效聚类数。

• 语句级克隆对比
  • SLACC识别了624个包含4,038个语句级代码克隆的聚类。在这些聚类中，有48个被标记为假阳性（精度为92.3%）。

4.2 动态语言

• SLACC 在分析中识别出 17,215 个提取的 Python 函数中有 3,135 个函数（ 18.2%）具有克隆，这些克隆结果被分为 482 个克隆聚类。在这 482 个聚类中，有 421 个是有效的，精度为87.3%
• 作为对比，使用相同的 Python 函数系统地寻找了类型 III 克隆。结果显示存在 3,971 个聚类，其中 181 个是有效的（精度为 4.6%），结果如表4所示。

4.3 跨语言

• 在提取的 36,403 个代码片段中，SLACC 识别出了 131 个 Java 函数和 48 个 Python 函数，这些函数被聚类成 34 个跨语言的聚类，其中有 2 个（5.8%）是假阳性
• 通过比较 Java 和 Python 代码片段的抽象语法树 (AST) 发现了 616 个类型 III 克隆聚类（如表 4 所示），其中 25 个聚类是有效的，精确度为 4.1%

5 其他影响

5.1 输入大小的影响

将输入数量从8到256，使用生成的Java函数重复SLACC，测试克隆的个数，簇的个数，假阳性的个数，得到的实验结果如表5所示。

分析：

输入数量越小，克隆数越多，簇越少，随着输入数量增加，克隆数减少，簇数量增多；

说明额外的输入对于区分功能之间的行为至关重要；

输入数量达到64后趋于稳定；

5.2 克隆中参数的影响

图7展示了参数从1变化到5时克隆的累计数量，从而证明本文将参数数量ARGS_MAX 设置为5的合理性。

从图7可以看出：

• 大多数克隆都只有两个或两个以下的参数；
• 在 Java 函数中，检测到的 4180 个克隆中有 3252 个的参数少于三个；
• 跨语言函数的数量较少，并且通常包含具有 2 个或更少参数的函数；

说明较大的 ARGS_MAX 值不会产生大量的代码克隆，但会产生更多的计算资源。

5.3 代码行数的影响

已有研究表明，代码在较小的粒度上会表现出更高的冗余性。

图 8 展示了克隆函数的代码行数分布，从 1 行到 29 行不等，超过 30 行的函数则归为“30+”类目。

数据显示，超过 50% 的有效 Java 克隆函数的代码行数为 6 行或更少，而有效的 Python 克隆函数中位数则为 5 行或更少。

这表明，行数较多的代码片段在功能上更独特，也更难被克隆。相反，代码行数较少的片段更容易在代码库中出现克隆现象。

6 结论

6.1 局限性

• 目前该方法仅将Java和python作为静态和动态语言的实例，所以可能无法推广到其他语言；
• 本文采用的数据集无法推广到更复杂的代码库，如项目文件等；
• SLACC在python中不支持两种基本类型：long和complex

6.2 创新点

• 是第一个可以在动态类型语言中识别语义代码克隆的研究，也是第一个能够跨不同类型的编程语言识别语义代码克隆的技术
• 通过比较目标代码库中分段代码的输入输出关系（IO 关系）来识别克隆代码片段。

BibTex

@inproceedings{mathew2020slacc,
  title={SLACC: Simion-based language agnostic code clones},
  author={Mathew, George and Parnin, Chris and Stolee, Kathryn T},
  booktitle={Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering},
  pages={210--221},
  year={2020}
}
``