一、申请发明专利或者实用新型专利应当提交说明书，一式一份。
二、说明书应当打字或者印刷，字迹应当整齐清晰，呈黑色，符合制版要求，不得涂改，字高在3.5毫米至4.5毫米之间，行距在2.5毫米至3.5毫米之间。说明书首页用此页，续页可使用同样大小和质量相当的白纸。纸张应当纵向使用，只限使用正面，四周应当留有页边距：左侧和顶部各25毫米，右侧和底部各15毫米。
三、说明书第一页第一行应当写明发明创造名称，该名称应当与请求书中的名称一致，并左右居中。发明创造名称与说明书正文之间应当空一行。说明书格式上应当包括下列五个部分，并且在每一部分前面写明标题：
技术领域
背景技术
发明内容
附图说明
具体实施方式
说明书无附图的，说明书文字部分不包括附图说明及其相应的标题。说明书文字部分可以有化学式、数学式或者表格，但不得有插图。
四、涉及核苷酸或氨基酸的申请，应当将该序列表作为说明书的一个单独部分，并单独编写页码。申请人应当在申请的同时提交与该序列表相一致的光盘或软盘，该光盘或软盘应符合国家知识产权局的有关规定。
五、说明书应当在每页下框线居中位置顺序编写页码。

一种基于多指标静动态分析的软件演化过程中代码搜索方法

技术领域

本发明涉及软件设计与开发的自动化领域

背景技术

代码到代码匹配描述了使用代码查询在存储库中搜索类似代码的任务。 由于语言之间的句法和语义差异，当查询和结果属于不同语言时，这项任务尤其具有挑战性 [20]。

软件维护研究表明，许多程序包含大量重复（克隆）代码。 这种克隆代码被认为是有害的，原因有两个：(1) 代码的多个、可能不必要的重复增加了维护成本 [1]、[2] 和，(2) 对克隆代码的不一致更改会产生错误，从而导致 不正确的程序行为 [3]。 克隆对软件维护的负面影响不是由于复制和粘贴，而是由克隆的语义耦合引起的。 因此，功能相似的代码，无论其来源如何，都会遇到克隆所熟知的相同问题。 事实上，可以将现有功能的重新创建视为更为关键，因为这是一个错失的重用机会。
由于当今软件系统的规模，手动识别功能相似的代码在实践中是不可行的。 需要工具来自动检测类似的代码。 较早的一项研究 [4] 表明，现有的克隆检测工具仅限于查找重复代码，即。 即，他们无法找到独立开发的冗余代码。 因此，我们不知道真实世界的软件系统在多大程度上包含除了源于复制和粘贴编程的代码克隆之外的类似代码。 然而，对样本项目的手动分析 [4] 以及轶事证据表明，程序确实包含许多并非由复制和粘贴引起的相似之处。
因此，我们期望用于自动检测类似代码的工具可以证明与现在广泛使用的克隆检测工具一样有利于质量保证活动

虽然两个程序的等价性通常无法确定，但检测相似代码的直接方法依赖于使用随机输入数据执行候选代码片段并比较输出值。 江苏[5]和我们都采用了这种方法。 虽然他们成功地将他们的方法应用于 Linux 内核中的代码，但我们无法将这种看似简单的方法用于不同的 Java 系统，从而产生显着的结果。
由于这与 Jiang&Su 的结果不同，本文详细介绍了我们对 Java 程序中功能相似代码的动态检测挑战的见解。
研究问题：软件系统中的功能重复会给软件维护带来许多问题。 尽管克隆检测是查找复制代码的可行方法，但现有工具无法找到独立创建的类似代码 [4]。 Jiang&Su [5] 开发了一种动态方法来识别 C 系统中功能相似的代码，并且对 Linux 内核的检测率很高。 我们实现了一种类似的方法来检测 Java 系统中功能相似的代码片段。 在分析五个开源 Java 系统时，我们的检测率要低得多。 我们发现这是由于该方法应用于 Java 系统时的局限性造成的。 因此，尚不清楚动态方法是否可以在实践中应用于检测面向对象系统中功能相似的代码片段。
贡献：虽然不是严格意义上的复制，但本文将江苏的工作转移到用 Java 实现的面向对象软件上。 我们描述了我们的动态检测方法的实现，报告了检测结果，并提供了我们的方法和结果与江苏工作的详细比较。 此外，我们讨论了面向对象系统的动态检测方法的挑战，从而为经过证实的讨论以及进一步研究的方向提供了基础。

考虑代码迁移的情况，其中将特定语言的应用程序重写为另一种语言是很常见的。 API匹配还涉及识别代码克隆 [63、66]、查找不同语言的代码翻译 [58]、程序修复 [10、68]，以及支持学生学习新的编程语言 [3]。 大型在线代码存储库的日益突出和源代码的重复性 [48, 70] 导致跨语言存在大量可能相似的代码，为代码到代码搜索提供了一个可行的平台。 我们提出了第一个具有动态和静态相似性度量的跨语言代码到代码搜索方法。 新颖之处在于将非支配排序 [19] 应用于代码到代码搜索，允许静态和动态信息（无聚合）识别搜索结果。 COSAL 利用输入输出 (IO) 行为 [51] 在克隆检测中利用现有技术。 由于动态克隆检测需要可执行代码，单独它无法实现实际搜索应用所需的召回。 这是静态分析中的现有技术大放异彩的地方； 我们使用基于令牌和基于 AST 的措施来补充动态分析。 当动态信息可用时，COSAL 在查找行为相似的代码方面获得了动态分析的好处，而在动态信息不可行时，则获得了静态信息的好处。 它提供了平衡代码外观和行为方式的结果，本着返回对用户来说看起来更自然的代码的精神。c

发明内容

本发明针对代码演化过程中相似代码的搜索问题，提供一种基于静动态分析的API匹配功能对不同项目中的相似代码进行匹配的方法。本发明可用于不同语言的项目，并可以提供一个最终相似度的排序列表供开发者进行选择与理解。技术方案如下。
第一步，构建数据集，其中数据集分为查询数据集和候选匹配存储数据集。查询数据集代表用户想要查询的代码片段集合，该部分可由用户自己指定。候选匹配存储数据集代表候选的匹配结果数据集，该部分数据集来自代码存储库的项目，例如GitHub，BitBucket等。
第二步，分别对查询数据集和候选匹配数据集进行静态分析和动态分析，得到对应的匹配数据集，对于候选匹配数据集，存储到数据库中，例如MySQL，Elasticsearch等数据库产品，并持久化到磁盘介质中，然后将查询数据集经分析后生成的结果在数据库中进行查询，得到一些匹配的代码及对应的相似度分数，具体方法如下。
（1）基于Token的匹配方法，通过源代码和注释中提取非语言特定的标记来推断上下文。得到标记相似距离d(Token)，返回最佳匹配结果。在许多情况下，基于令牌的分析无法产生理想的结果。它依赖于自我描述的片段；变量名、函数名、使用的库和注释的选择都会影响结果.
并非所有代码片段都遵循直观的命名约定。尽管如此，与全文搜索相比，本方法的标记化方法会产生更精确的结果。

（2）基于AST的匹配方法。不同语言中有符合其特定句法特征的AST解析器，通过解析器可以得到基于AST的相似度度量结果，然后用于跨语言比较的基于树的表示具有挑战性，因为没有包含不同语言句法特征的通用 AST 表示。例如，JavaParser 中的函数节点表示为 MethodDeclaration，而 python-ast 解析器将节点表示为 FunctionDef。因此，要比较不同语言的 AST，需要每对编程语言之间的映射方案。为了更好地扩展到其他编程语言，我们为通用 AST 构建了一个解析器。通过将 Java 和 Python 的 AST 映射到通用 AST，本方法可以在这些语言之间进行比较。通用 AST 是基于我们的直觉和选择的语言，可能会有更有效或更高效的表示。。因此，为了多语言的拓展，考虑构建通用AST解析器。
（3）为了确定两段代码之间的 IO 关系，本方法使用 SLACC [51]，这是一种公开可用的基于 IO 的跨语言代码克隆检测工具。 本方法代码分割成大小大于 MINSTMTS 的可执行片段，并在使用灰盒策略生成的 ARGS_MAX 参数上执行。然后使用基于函数的输入和输出的相似性度量（𝑠𝑖𝑚）对执行的函数进行聚类。考虑一个查询𝑞和一个潜在的搜索结果𝑠。令𝑄和𝑆分别是 SLACC 从𝑞和𝑠中识别的段落集。本方法将 IO 相似度定义为：
其中，值𝑑𝐼𝑂的范围是 [0.0, 1.0]。较高的相似度对应于较高的𝑑𝐼𝑂值。

第三步，基于上一步的结果，我们可以得到相应的基于Token，AST，IO的匹配代码结果及相应的相似度分数。然后我们基于这几个指标的相似度，设置不同指标的权重，Wtoken = 0.3, Wast = 0.4, Wio = 0.3。所以，我们可以得到最终的置信度指标为：

第四步，根据置信度，我们可以得到最终的候选代码片段排名，因此，通过静动态分析，我们最终得到了一个候选相似代码列表，从而完成匹配，得到的相似代码的搜索结果。

附图说明

图1，方法流程概要图

具体实施方式

为了使本发明的技术方案更加清楚，下面结合附图对本发明做进一步阐述。本发明按照以下步骤具体实现：
第一步，准备数据集。
（1）准备候选匹配代码数据集。
我们可以从版本控制系统中获取本方法所需的数据集，包括Github，Labraries.io等在线项目存储库或数据集库。
（2）准备查询代码数据集。
该部分数据集可由用户指定，用户可以根据自己的项目或需求给出该部分数据集。
第二步，分别计算查询API与候选API之前各个指标的相似度情况。
（1）基于Token的指标计算。
开发人员倾向于根据功能在注释中描述代码。我们通过从源代码和注释中提取非语言特定的标记来推断上下文，如下所示。
1. 根据文档删除特定于语言的关键字。 例如，Java 标记 public 和 static 以及 Python 标记 def 和 assert 都被删除。
2. 根据通用的编码约定，去除一种语言中的常用词。 例如，在 Python 中，标记 self 经常用于表示类对象。
3. 从英语词汇表中去除常见的停用词，例如does和from。
4. 拆分标记以解决特定于语言的命名法。 变量在Java中通常使用camelCase，在Python中使用snakecase。 它们分别分为{“camel”和“case”}和{“snake”和“case”}。
5. 我们定义MIN_TOK_LEN为用于计算的token的最小长度，因此，在这一步中，删除长度小于MIN_TOK_LEN 的token。
6. 将所有标记转换为小写
使用上述方法对代码存储库进行标记并存储在 ElasticSearch索引中。 对于用户的代码查询，在搜索索引中查找索引方法生成的标记，并使用标记相似距离dtoken返回最佳匹配结果。 该距离与 Jaccard Coefficient [59] 相同，定义如下
dtoken的范围是 [0.0, 1.0]。 𝑑𝑡𝑜𝑘𝑒𝑛的值越大，表示查询和结果之间的相似度越高

(2)基于AST的指标计算
用于跨语言比较的基于树的表示具有挑战性，因为没有包含不同语言句法特征的通用 AST 表示。 传统的 AST 解析器，如 ANTLR [61]、JavaParser [83]、python-ast [65] 模块使用不同的语法来表示相似的特征。
例如，JavaParser 中的函数节点表示为 MethodDeclaration，而 python-ast 解析器将节点表示为 FunctionDef。 因此，要比较不同语言的 AST，需要每对编程语言之间的映射方案。 为了更好地扩展到其他编程语言，我们为通用 AST 构建了一个解析器。 通过将 Java 和 Python 的 AST 映射到通用 AST，我们可以在这些语言之间进行比较。 通用 AST 是基于我们的直觉和选择的语言，可能会有更有效或更高效的表示。
使用 Zhang-Sasha 算法 [90] (𝑑𝐴𝑆𝑇) 计算 AST 之间的相似性。 该算法计算在二次时间内将一个有序标记树转换为另一个有序标记树所需的最小编辑次数。 𝑑𝐴𝑆𝑇的范围是 [0, ∞)。 𝑑𝐴𝑆𝑇的越低，相关性越高。

（3）基于输入输出(IO)的指标计算
本方法中的动态搜索，是由基于它们的 IO 关系的聚类代码执行的
为了确定两段代码之间的 IO 关系，我们使用 SLACC [51]，这是一种公开可用的基于 IO 的跨语言代码克隆检测工具。 SLACC 将代码分割成大小大于 MINSTMTS 的可执行片段，并在使用灰盒策略生成的 ARGS_MAX 参数上执行。 然后使用基于函数的输入和输出的相似性度量（𝑠𝑖𝑚）对执行的函数进行聚类。 考虑一个查询 𝑞和一个潜在的搜索结果 𝑠。 令 𝑄和 𝑆分别是 SLACC 从𝑞和 𝑠中识别的段落集。 我们将 IO 相似度定义为：
值 𝑑𝐼𝑂的范围是 [0.0, 1.0]。 较高的相似度对应于较高的 𝑑𝐼𝑂值。
第三步，聚合指标得到置信度排名
将上述过程得到的相似度度量指标，根据事先定义好的各个指标值权重进行聚合，得到最终的置信度排序。