CN101894236B - 基于摘要语法树和语义匹配的软件同源性检测方法及装置 - Google Patents

Abstract

本发明涉及一种基于摘要语法树和语义匹配的软件同源性检测方法及装置，通过生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；计算所述摘要语法树中子树的哈希值；通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。从而在语法层次上，结合语义进行准确而有效的软件同源性检测。

Description

基于摘要语法树和语义匹配的软件同源性检测方法及装置

技术领域

本发明涉及信息安全中的软件安全技术领域，尤其涉及一种基于摘要语法树和语义匹配的软件同源性检测方法及装置。

背景技术

软件同源性检测技术是计算机编程语言研究的一个重要方面，根据其检测的方法不同，这个领域现存在以下主流研究领域：基于文本的软件同源性检测和基于标记(Token)的软件同源性检测。

基于文本的软件同源性检测技术方案是基于文本层次进行软件同源性检测，而目前软件源代码抄袭的过程一般都是整块复制，或者在此基础上加以改动，比如替换变量名、在不影响程序功能的情况下打乱语句顺序、更改函数名或者函数位置等等，因此，基于文本的软件同源性检测技术方案仅仅在文本层次进行软件同源性检测，已经不能满足软件同源性检测的需求。而且，基于文本层次的软件同源性检测完全忽略了软件源代码的语法含义，因而有很大的局限性，对于上述软件源代码抄袭手段都无法正确检测出来。

基于标记Token的软件同源性检测技术方案主要是用来进行软件源代码克隆检测，也可以用来做软件同源性检测。这种技术方案一定程度上考虑了语言特点，但其原理是查找软件源代码中最长的相似子串，所以不能应对软件源代码顺序调换这样的抄袭情况。

目前，还没有一种成熟可靠的软件同源性检测技术方案，在语法层次上结合语义对软件源代码进行有效而准确的同源性检测。

发明内容

有鉴于此，本发明实施例的目的是提供了一种基于摘要语法树和语义匹配的软件同源性检测方法及装置，从而有效而准确的进行软件同源性检测，以应对各种软件源代码抄袭行为，促进了软件评估工作和保护软件版权的推进。

为了达到上述目的，本发明实施例提供了一种基于摘要语法树和语义匹配的软件同源性检测方法，包括：

生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；

计算所述摘要语法树中子树的哈希值；

通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。

优选的，上述方法中，所述生成软件源代码对应的摘要语法树包括：

将所述软件源代码中的文件包含指令、注释和多余的空白符删除；查找所述软件源代码中被宏定义指令所替换的字符串，并换回原来的字符串；判断所述软件源代码中的条件编译指令中的判断条件是否成立，然后选择删除或保留对应的软件源代码段。

优选的，上述方法中，所述语义特征规则至少为下列特征中的一种：条件表达式为比较表达式、变量标识、函数调用。

优选的，上述方法中，所述计算所述摘要语法树中子树的哈希值包括：

根据所述摘要语法树的节点类型信息，计算得到所述节点的哈希值，并以线性链表格式保存所述节点包括哈希值在内的信息；

将所述摘要语法树中子树所包括的节点的哈希值进行累加，得到所述子树的哈希值。

优选的，上述方法中，所述将所述摘要语法树中子树所包括的节点的哈希值进行累加，得到所述子树的哈希值包括：

将除法、减法和取余运算操作前后参与运算的元素赋予不同的权值。

优选的，上述方法中，所述通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测包括：

根据所述摘要语法树中子树所包括的节点数目，将子树进行分组。

本发明实施例还提供了一种基于摘要语法树和语义匹配的软件同源性检测装置，包括：

生成模块，用于生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；

计算模块，用于计算所述生成模块生成的摘要语法树中子树的哈希值

检测模块，用于根据所述计算模块计算获取的所述哈希值，通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。

优选的，上述装置中，所述生成模块包括：

预处理单元，用于将所述软件源代码中的文件包含指令、注释和多余的空白符删除；查找所述软件源代码中被宏定义指令所替换的字符串，并换回原来的字符串；判断所述软件源代码中的条件编译指令中的判断条件是否成立，然后选择删除或保留对应的软件源代码段；

词法分析单元，用于依次读入经过所述预处理单元预处理后的所述软件源代码文本中字符序列，根据所述软件源代码所采用的编程语言语法规则，采用对应的正则表达式将所述字符序列与所述编程语言的匹配规则对应后，返回标识所述字符序列的标记；

语法分析单元，用于根据所述词法分析单元返回的所述标记，将所述标记对应的软件源代码序列，与所述软件源代码所采用的编程语言语法规则匹配后，开辟内存空间，生成所述软件源代码对应的摘要语法树中的节点信息，构建所述摘要语法树；

语义匹配单元，用于分析所述语法分析单元构建的所述摘要语法树的结构信息，将匹配相同语义特征规则且语义相同的子树调整为统一结构。

优选的，上述装置中，所述计算模块包括：

节点计算单元，用于根据经过所述语义匹配单元调整之后的所述摘要语法树中的节点类型信息，计算得到所述节点的哈希值；

子树计算单元，用于根据所述节点计算单元计算获取的节点哈希值，将所述摘要语法树中子树所包括的节点的哈希值进行累加，得到所述子树的哈希值。

优选的，上述装置中，所述检测模块包括：

分组单元，用于根据所述摘要语法树中子树所包括的节点数目，将所述子树进行分组。

由上述本发明实施例提供的技术方案可以看出，本发明实施例中，通过生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；计算所述摘要语法树中子树的哈希值；通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。从而在语法层次上，结合语义进行准确而有效的进行软件同源性检测。

附图说明

图1为本发明实施例提供的所述方法具体实现示意图一；

图2为本发明实施例提供的所述方法具体实现示意图二；

图3为本发明实施例提供的所述方法具体实现示意图三；

图4为本发明实施例提供的所述装置具体实现结构示意图一；

图5为本发明实施例提供的所述装置具体实现结构示意图二；

图6为本发明实施例提供的所述装置具体实现结构示意图三；

图7为本发明实施例提供的所述装置具体实现结构示意图四。

具体实施方式

本发明实施例提供了一种基于摘要语法树和语义匹配的软件同源性检测方法，如附图1所示，包括：

步骤11，生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；

步骤12，计算所述摘要语法树中子树的哈希(Hash)值；

步骤13，通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。

通过本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测方法的实施，可以在语法层次上，结合语义进行准确而有效的软件同源性检测。

为使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明实施例作进一步的详细描述。

本发明实施例提供的在语法层次进行软件同源性检测方法，可以充分考虑软件源代码原有的语义，保证了同源性检测的正确性。而且，全新提出了一种利用软件源代码对应树形结构一摘要语法树的检测手段，将软件源代码对应摘要语法树中每一个节点的哈希值作为软件同源性检测的基准，并针对常见的源代码抄袭手段提出语义特征规则匹配检测方法，将检测方法提高到了语义层次，从而提高了同源性检测的准确性。同时，将相同节点数目的软件源代码摘要语法树件中的子树分组进行对比检测，避免了不必要的对比，大大提高了检测效率。

本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测方法的一个实施例在具体实现过程中，具体可如附图2所示，可以包括以下步骤：

步骤21，获取目标软件和样本软件进行同源性检测所需的检测参数。

本发明实施例中，可以将需要作对比检测的软件称之为目标软件，而作为对比样本的软件称之为样本软件。可以理解的是，上述称谓可根据需要进行更改。

在本发明一个具体实施例中，步骤21具体可以包括以下具体操作过程：

步骤211，选择需要检测的目标软件源代码和样本软件源代码；

此步骤中，如果事先已经获取并存储有根据目标或样本软件源代码生成的摘要语法树的数据库文件，则可以直接调取对应的数据库文件进行后续的对比检测，无需获取目标或样本软件的源代码。

步骤212，输入对比阈值。

此步骤中，可以根据需要进行对比检测的目标软件和样本软件所采用的C、C++和Java等等编程语言，输入对比的阈值。该阈值即对比的精度，比如用户将阈值确定为5，则对比时精确到子节点数目大于等于5的摘要语法树中子树。

当然，本发明实施例中也可以不进行对比阈值的选择操作，直接进行对比检测，或者事先制定某一固定数值，作为默认对比阈值。

步骤213，确定中间文件的保存路径。

此步骤中，可以确定中间文件，具体可以包括经过预处理之后的软件源代码、日志文件和存储对比结果的数据库文件等等的保存路径。

并且，本发明实施例在具体实现过程中，可实时的进行记录保存软件同源性检测过程中的操作信息，比如软件同源性检测开始及结束时间、数据库文件保存路径等等。

需要说明的是，本发明实施例在具体实现过程中，步骤21并不是必须执行的，可作为选择性或者默认流程进行操作。

步骤22，生成目标软件和样本软件源代码摘要语法树，并调整摘要语法树结构。

本发明实施例中，可以根据目标或样本软件所用编程语言的语法规则，生成该软件源代码所对应的摘要语法树。由于摘要语法树中记录了该软件源代码的语法结构和每一个代码片段在软件源代码中的具体位置，因此生成摘要语法树文件是进行软件同源性检测时所需要的重要而有效的数据。在生成摘要语法树后，分析该摘要语法树，通过与语义特征规则匹配，调整摘要语法树结构，将符合相同语义特征规则且语义相同的子树调整为统一结构。

步骤22具体实现过程可如附图3所示，具体可以包括：

步骤221，对软件源代码进行预处理。

对软件源代码进行预处理，可以将所有软件源代码(包括目标和样本软件源代码)统一为同一个规范格式。

对软件源代码进行预处理，具体可以包括对软件源代码中的文件包含指令、宏定义指令、条件编译指令、注释和多余的空白符进行相应的处理。其中对文件包含指令、注释和多余的空白符采取的处理方式是直接删除；对宏定义指令的处理是查找软件源代码中被宏定义所替换的字符串，并换回原来的字符串；对条件编译指令的处理是判断条件编译指令中的判断条件是否成立，然后选择该删除的代码段和该保留的代码段。

在本发明一个具体实施例中，步骤221具体可以包括以下步骤：

步骤2211，删除软件源代码中多余的空白符和换行符；

步骤2212，对软件源代码中的续行符进行处理，将分为两行编写的代码接续到同一行；

步骤2213，将软件源代码中的注释删除，只留下有意义的代码段；

步骤2214，找到软件源代码中的文件包含命令“#include”，直接将其删除；

步骤2215，找到软件源代码中的条件编译指令，判断条件是否成立，正确保留或者删除所包括的代码段。

需要说明的是，上述步骤2211至步骤2215的执行可以没有先后顺序。

本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测方法，在对软件源代码进行预处理时，完全考虑了其语义，比如软件源代码中“typedeffloat FL”语句的处理就是将软件源代码中的所有“FL”替换为“float”，再比如软件源代码中条件编译语句“#ifdef”的处理则是判断其条件是否成立，然后对应的保留应该保留的语句。因此，本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测方法，可以完全按照语义对软件源代码进行预处理，在最大程度上保持软件同源性检测的准确性。

步骤222，对完成预处理的软件源代码进行词法分析。

具体的，可以依次读入经过预处理的软件源代码文本中字符序列，然后根据该软件源代码所采用的编程语言，比如C、C++和Java等等编程语言，采用对应的正则表达式将特定的字符序列与该编程语言的匹配规则对应后，返回标识此字符序列的标记(Token，用来标识某一类字符序列的特定字符串)。

步骤223，对词法分析后的软件源代码进行语法分析，生成摘要语法树。

具体的，当步骤222中产生的带有标记Token的软件源代码序列，与该软件源代码所采用的编程语言的语法规则匹配后(比如函数定义规则等特定的规则)，就开辟内存空间，生成一个节点，并在此节点中记录此时对应的节点类型，以及该节点对应于软件源代码中的位置信息。在生成软件源代码所有节点后，就生成了软件源代码所对应的摘要语法树。

需要说明的是，如果步骤222分析得到的某一个软件源代码的标记Token序列，在步骤223中没有任何语法规则可以匹配，则将其所在的语句片段删除之后，得到新的软件源代码，继续步骤222，直到正确生成软件源代码对应的摘要语法树。

步骤224，根据语义特征规则调整摘要语法树结构。

本发明实施例针对if-else语句、while语句等C、C++和Java语言中常见的源代码语句，可以摘要出一些对应的摘要语法树的语义特征规则，例如条件表达式为比较表达式、变量标识(ID)、函数调用等等。然后遍历分析软件源代码对应的摘要语法树，查找符合这些语义特征规则的子树。比如if-else语句结构的特征是以if类型的节点作为根节点，它的第一个子节点为条件类型的节点，第二个子节点为else类型的节点。

摘要语法树中所存储的软件源代码语法结构信息中包含着一定的语义信息，通过对摘要语法树中的语义信息进行摘要和匹配，可以得到符合相同语义特征规则但结构不同的子树，即这些子树对应的源代码语法结构不同但具有相同的语义。

将匹配相同的语义特征规则的子树进行结构调整，即把匹配相同语义规则的子树调整为统一的结构，使符合相同语义特征规则且语义相同的子树具有相同的结构，从而使语法结构不同但语义相同的语句统一为语法结构相同的语句。

具体调整可如下举例：

当匹配if语句的条件表达式的开始含有“！”(取反)的规则时，将“！”忽略并将if节点的第二个子树和else节点的子树对换，由于在计算哈希值时采用由下向上累加的方式，子树对换不影响最终的哈希值，因此子树对换的操作可以忽略；当匹配if语句的条件表达式是比较表达式的规则时，判断条件比较符号的两端如果是变量名或函数调用，就把比较符号统一为“＜”，如果是变量名和数字，那么将变量名调整到比较符号前面再进行调整。

通过该步骤的处理，本发明实施例提供的所述方法，可以将语法层次上的软件源代码同源性检测提升为语法结合语义层次的源代码同源性检测，能够准确将同义但结构不同的软件源代码抄袭准确的检测出来，显著提高了软件同源性检测的效率。

步骤225，将调整后的摘要语法树进行存储格式转换并储存。

为了方便摘要语法树相关信息的存储和调取，本发明实施例可以在生成及调整之后，将摘要语法树转换为线性链表结构并进行存储。

步骤23，计算摘要语法树中子树的哈希值。

步骤23具体实现过程可以包括：

步骤231，计算节点哈希值。

在生成软件源代码对应的摘要语法树后，可以根据摘要语法树中每一个节点的类型计算得到每一个节点的哈希值。

该步骤中，还可以以线性链表格式保存节点包括哈希值在内的信息。

步骤232，计算子树哈希值。

将该摘要语法树中每一个子树所包括的所有节点的哈希值进行累加，得到摘要语法树中每一个子树的哈希值。

计算摘要语法树中子树的哈希值的好处在于，在后续同源性检测时，可以有效的检测出打乱软件源代码顺序的抄袭手段。

在对从软件源代码生成的摘要语法树进行哈希计算时，由于采用累加的方式计算子树的哈希值，可能会产生一些误检的情况，这些情况都是跟一些特殊的运算操作有关，比如除法、减法和取余等等，如果在这些运算操作前后参与运算的元素调换位置的话，整个运算操作的意义就发生了改变，为了避免将这种情况错误的检测为相似代码，本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测方法，对这类特殊的运算操作设计了特殊的哈希计算方式，在计算这类特殊运算操作的哈希值时加入了权值的概念，将这类特殊运算操作前后参与运算的元素赋予不同的权值，这样如果调换前后参与运算的元素的位置，整个运算操作的哈希值就会改变，而不会错误的将其识别为相似代码，避免了一些将不同的代码误报为抄袭代码的情况，降低了误报率。

步骤24，进行软件同源性检测。

根据步骤23中生成的目标软件源代码对应的摘要语法树相关信息，以及样本软件源代码对应的摘要语法树相关信息，通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。从而获取目标软件和样本软件的同源性，即相似度的相关信息，近而可以判定目标软件是否进行了抄袭。

在进行同源性检测之前，为了提高检测效率和准确性，可以按照软件源代码对应的摘要语法树中，各个子树的子节点数目，将各个子树进行分组，将线性链表结构中存储的摘要语法树转存到数组链表中，保证有着相同子节点数目的子树存放到同一个数组下标对应的链表中，比如摘要语法树中都有着6个子节点的子树都会存入到数组的第6个元素所存储的链表中。

在同源性检测时，由于已经将摘要语法树相关信息转换了存储格式，即数组链表格式，因此，在进行同源性检测时可以根据两个数组链表记录的摘要语法树所有节点信息，进行逐节点遍历对比检测。比如，可先从目标软件源代码数组元素为1(即子树包含一个节点)的数组中选取某一个子树，与样本软件源代码数组元素为1的数组中的所有子树逐一进行哈希值比较，通过判断子树的哈希值是否一致，以确定是否存在相似源代码；然后再从目标软件源代码数组元素为1的数组中，选取另一个子树，再与样本软件源代码数组元素为1的数组中的所有子树逐一进行哈希值比较。以此类推，直至将目标软件和样本软件源代码的所有数组全部完成检测，从而确定目标软件与样本软件源代码的是否为同源性软件。

如果目标软件和样本软件为非同源性软件，还可以根据对比结果中哈希值相同所占得比例，确定目标软件和样本软件的相似度。

由于本发明实施例在进行同源性检测之前，按子节点数目对摘要语法树中的子树进行分组，因此避免了不必要的对比检测，大大提高了同源性检测的效率。而且，本发明实施例在进行同源性检测时，采用的是逐节点遍历对比检测方法，即不仅仅是对数据结构进行对比检测，还深入到数据结构内部进行对比检测。因此，即使数据结构不一样，本发明实施例也能找出其内部的抄袭代码。

另外，本发明实施例还可以根据步骤212设定对比阈值，精确到需要检测的精度。

步骤25，存储以及输出同源性检测结果。

对于同源性检测结果，本发明实施例可以进行存储，进一步还可以根据需要进行输出，比如将同源性检测结果输出至Word和Excel文件中。

通过上述描述可以看出，本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测方法，通过生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；计算所述摘要语法树中子树的哈希值；通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。从而在语法层次上，结合语义进行准确而有效的进行软件同源性检测。

而且，在本发明实施例在对软件源代码进行预处理时，完全考虑了软件源代码原有的语义，因此可以在最大程度上保持同源性对比的准确性。

而且，本发明实施例计算摘要语法树节点哈希值后，对一些特殊的运算进行了特殊的处理，比如在对减法、除法等等操作进行哈希值计算时，给其前后参与运算的元素赋予不同的权值，避免了一些将不同的代码误报为抄袭代码的情况，降低了误报率。

而且，本发明实施例在生成软件源代码摘要语法树后，将摘要语法树转换为线性链表结构，方便摘要语法树的存储和取出。

而且，本发明实施例在进行软件同源性检测之前，按节点数目对摘要语法树中的子树进行分组，避免了不必要的对比检测，大大提高了对比检测的效率。

而且，本发明实施例在进行软件同源性检测时，采用逐节点遍历对比的方法，即不仅仅是对数据结构进行对比，还深入到数据结构内部进行对比，因此即使数据结构不一样，也能找出其内部的抄袭代码，并且还可以改变输入的对比阈值来调整对比的精度。

而且，本发明实施例还可以实时的保存软件同源性检测过程中的信息，以及检测结果，为后续再次进行该软件同源性检测提高了方便，大大的提高了实际工作的效率。

基于上述显著的技术特征可以看出，本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测方法可以应对多种源代码抄袭手段，可以方便、高效、准确的进行软件同源性检测。

本发明实施例提供了一种基于摘要语法树和语义匹配的软件同源性检测装置，如附图4所示，该装置具体可以包括生成模块41，计算模块42，检测模块43。其中：

生成模块41，用于生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；

计算模块42，用于计算所述生成模块41生成的摘要语法树中子树的哈希值；

检测模块43，用于根据所述计算模块42计算获取的所述哈希值，通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。

在本发明实的一个具体实施例中，可选的，生成模块41如附图5所示，具体可以包括：

预处理单元411，用于将软件源代码中的文件包含指令、注释和多余的空白符删除；查找软件源代码中被宏定义指令所替换的字符串，并换回原来的字符串；判断软件源代码中的条件编译指令中的判断条件是否成立，然后选择删除或保留对应的软件源代码段。

预处理单元411的具体操作过程，可以包括：

删除软件源代码中多余的空白符和换行符；

对软件源代码中的续行符进行处理，将分为两行编写的代码接续到同一行；

将软件源代码中的注释删除，只留下有意义的代码段；

找到软件源代码中的文件包含命令“#include”，直接将其删除；

找到软件源代码中的条件编译指令，判断条件是否成立，正确保留或者删除所包括的代码段。

词法分析单元412，用于依次读入经过预处理单元411预处理后的软件源代码文本中字符序列，根据软件源代码所采用的编程语言语法规则，采用对应的正则表达式将该字符序列与编程语言的匹配规则对应后，返回标识该字符序列的标记。

语法分析单元413，用于根据词法分析单元412返回的标记，将该标记对应的软件源代码序列，与软件源代码所采用的编程语言语法规则匹配后，开辟内存空间，生成软件源代码对应的摘要语法树的节点信息，构建摘要语法树。

语法分析单元413具体可以将带有词法分析单元412产生的标记Token的软件源代码序列，与该软件源代码所采用的编程语言的语法规则匹配后(比如函数定义规则等特定的规则)，开辟内存空间，生成一个摘要语法树节点，并在此节点中记录此时对应的节点类型，以及该节点对应于软件源代码中的位置信息。在生成软件源代码所有节点后，就生成了软件源代码所对应的摘要语法树。

语义匹配单元414，用于分析所述语法分析单元413构建的摘要语法树的结构信息，将匹配相同语义特征规则且语义相同的子树调整为统一结构。

语义匹配单元414具体可以使用深度遍历的方式遍历整棵摘要语法树，分析摘要语法树的结构信息。if-else和while语句对应的摘要语法树结构符合一定的语义规则，通过匹配这些语义规则，可以查找具有一定特征的if-else语句和while语句，例如条件表达式为比较表达式、变量ID、函数调用等等。对于匹配一定语义规则的语义相同if-else和while语句的条件表达式，将其对应的摘要语法树整理为统一的结构，即具有相同语义的语句具有相同的摘要语法树结构，从而可以检测出语法结构修改却有相同语义的if-else和while等语句。

通过生成模块41，尤其是语义匹配单元414的具体操作，本发明实施例提供的装置，可以将语法层次上的软件源代码同源性检测提升为语法结合语义层次的源代码同源性检测，能够准确将同义但结构不同的软件源代码抄袭准确的检测出来，显著提高了软件同源性检测的效率。

在本发明实的一个具体实施例中，可选的，计算模块42如附图6所示，具体可以包括：

节点计算单元421，用于根据经过语义匹配单元414调整之后的摘要语法树中的节点类型信息，计算得到摘要语法树中节点的哈希值。

子树计算单元422，用于根据节点计算421单元计算获取的节点哈希值，将摘要语法树中子树所包括的节点的哈希值进行累加，得到子树的哈希值。

在对从软件源代码生成的摘要语法树进行哈希计算时，由于采用累加的方式计算子树的哈希值，可能会产生一些误检的情况，这些情况都是跟一些特殊的运算操作有关，比如除法、减法和取余等等，如果在这些运算操作前后参与运算的元素调换位置的话，整个运算操作的意义就发生了改变，为了避免将这种情况错误的检测为相似代码，本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测装置，对这类特殊的运算操作设计了特殊的哈希计算方式，在计算这类特殊运算操作的哈希值时加入了权值的概念，将这类特殊运算操作前后参与运算的元素赋予不同的权值，这样如果调换前后参与运算的元素的位置，整个运算操作的哈希值就会改变，而不会错误的将其识别为相似代码，避免了一些将不同的代码误报为抄袭代码的情况，降低了误报率。

通过计算模块42的具体操作，本发明实施例提供的装置，可以有效的检测出打乱软件源代码顺序的抄袭手段。

在本发明实的一个具体实施例中，可选的，检测模块43具体可以包括：

分组单元431，用于根据摘要语法树中子树所包括的节点数目，将子树进行分组。

具体的，为了提高检测效率和准确性，分组单元具体可以按照软件源代码对应的摘要语法树中，各个子树的子节点数目，将各个子树进行分组，将线性链表结构中存储的摘要语法树转存到数组链表中，保证有着相同子节点数目的子树存放到同一个数组下标对应的链表中，比如摘要语法树中都有着6个子节点的子树都会存入到数组的第6个元素所存储的链表中。

在同源性检测时，由于已经将摘要语法树相关信息转换了存储格式，即数组链表格式，因此，在进行同源性检测时可以根据数组链表记录的摘要语法树所有节点信息，进行逐节点遍历对比检测。比如，可先从A软件源代码数组元素为1(即子树包含一个节点)的数组中选取某一个子树，与B软件源代码数组元素为1的数组中的所有子树逐一进行哈希值比较，通过判断子树的哈希值是否一致，以确定是否存在相似源代码；然后再从A软件源代码数组元素为1的数组中，选取另一个子树，再与B软件源代码数组元素为1的数组中的所有子树逐一进行哈希值比较。以此类推，直至将A软件和B软件源代码的所有数组全部完成检测，从而确定A软件与B软件源代码的是否为同源性软件。如果软件为非同源性软件，还可以根据对比结果中哈希值相同所占得比例，确定各个软件的相似度。

由于本发明实施例在进行同源性检测之前，按子节点数目对摘要语法树中的子树进行分组，因此避免了不必要的对比检测，大大提高了同源性检测的效率。而且，本发明实施例在进行同源性检测时，采用的是逐节点遍历对比检测方法，即不仅仅是对数据结构进行对比检测，还深入到数据结构内部进行对比检测。因此，即使数据结构不一样，本发明实施例也能找出其内部的抄袭代码。

在本发明实的一个具体实施例中，可选的，基于摘要语法树和语义匹配的软件同源性检测装置如附图7所示，具体还可以包括：

数据库模块44，用于实时保存软件同源性检测过程中的信息。

具体的，数据库模块43可以保存生成模块41输出地摘要语法树信息，并将摘要语法树信息转换为线性链表进行保存。另外，数据库模块44还可以实时保存计算模块42以及检测模块43所输出的信息。等等。

输出模块45，用于输出检测模块43的检测结果。

对于同源性检测结果，本发明实施例可以进行存储，进一步还可以根据需要进行输出，比如将同源性检测结果输出至Word和Excel文件中。

本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测装置在进行软件同源性检测之前，还可以设定同源性检测时的对比阈值，以及检测信息的保存路径。

通过上述描述可以看出，本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测装置，通过生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；计算所述摘要语法树中子树的哈希值；通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测。从而在语法层次上，结合语义进行准确而有效的进行软件同源性检测。

而且，在本发明实施例在对软件源代码进行预处理时，完全考虑了软件源代码原有的语义，因此可以在最大程度上保持同源性对比的准确性。

而且，本发明实施例计算摘要语法树节点哈希值后，对一些特殊的运算进行了特殊的处理，比如在对减法、除法等等操作进行哈希值计算时，给其前后参与运算的元素赋予不同的权值，避免了一些将不同的代码误报为抄袭代码的情况，降低了误报率。

而且，本发明实施例在生成软件源代码摘要语法树后，将摘要语法树转换为线性链表结构，方便摘要语法树的存储和取出。

而且，本发明实施例在进行软件同源性检测之前，按节点数目对摘要语法树中的子树进行分组，避免了不必要的对比，大大提高了对比的效率。

而且，本发明实施例在进行软件同源性检测时，采用逐节点遍历对比的方法，即不仅仅是对数据结构进行对比，还深入到数据结构内部进行对比，因此即使数据结构不一样，也能找出其内部的抄袭代码，并且还可以改变输入的对比阈值来调整对比的精度。

而且，本发明实施例还可以实时的保存软件同源性检测过程中的信息，以及检测结果，为后续再次进行该软件同源性检测提高了方便，大大的提高了实际工作的效率。

基于上述显著的技术特征可以看出，本发明实施例提供的基于摘要语法树和语义匹配的软件同源性检测装置可以应对多种源代码抄袭手段，可以方便、高效、准确的进行软件同源性检测。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到本发明可借助软件加必需的硬件平台的方式来实现，当然也可以全部通过硬件来实施，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案对背景技术做出贡献的全部或者部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。

Claims (8)

1.一种基于摘要语法树和语义匹配的软件同源性检测方法，其特征在于，包括：

生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构；

计算所述摘要语法树中子树的哈希值；

通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测；

所述计算所述摘要语法树中子树的哈希值包括：

根据所述摘要语法树的节点类型信息，计算得到所述节点的哈希值，并以线性链表格式保存所述节点包括哈希值在内的信息；

将所述摘要语法树中子树所包括的节点的哈希值进行累加，得到所述子树的哈希值。

2.根据权利要求1所述的方法，其特征在于，所述生成软件源代码对应的摘要语法树包括：

将所述软件源代码中的文件包含指令、注释和多余的空白符删除；查找所述软件源代码中被宏定义指令所替换的字符串，并换回原来的字符串；判断所述软件源代码中的条件编译指令中的判断条件是否成立，然后选择删除或保留对应的软件源代码段。

3.根据权利要求1所述的方法，其特征在于，所述语义特征规则至少为下列特征中的一种：条件表达式为比较表达式、变量标识、函数调用。

4.根据权利要求1所述的方法，其特征在于，所述将所述摘要语法树中子树所包括的节点的哈希值进行累加，得到所述子树的哈希值包括：

将除法、减法和取余运算操作前后参与运算的元素赋予不同的权值。

5.根据权利要求1所述的方法，其特征在于，所述通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测包括：

根据所述摘要语法树中子树所包括的节点数目，将子树进行分组。

6.一种基于摘要语法树和语义匹配的软件同源性检测装置，其特征在于，包括：

用于生成软件源代码对应的摘要语法树，并将所述摘要语法树中匹配相同语义特征规则且语义相同的子树调整为统一结构的生成模块；

用于计算所述生成模块生成的摘要语法树中子树的哈希值的计算模块；

用于根据所述计算模块计算获取的所述哈希值，通过判断节点数目相同的子树的哈希值是否一致，进行软件同源性检测的检测模块；

所述计算模块还包括：

用于根据所述生成模块生成的所述摘要语法树中的节点类型信息，计算得到所述节点的哈希值，并以线性链表格式保存所述节点包括哈希值在内的信息的节点计算单元；

用于根据所述节点计算单元计算获取的节点哈希值，将所述摘要语法树中子树所包括的节点的哈希值进行累加，得到所述子树的哈希值的子树计算单元。

7.根据权利要求6所述的装置，其特征在于，所述生成模块包括：

用于将所述软件源代码中的文件包含指令、注释和多余的空白符删除；查找所述软件源代码中被宏定义指令所替换的字符串，并换回原来的字符串；判断所述软件源代码中的条件编译指令中的判断条件是否成立，然后选择删除或保留对应的软件源代码段的预处理单元。

8.根据权利要求6或7所述的装置，其特征在于，所述检测模块包括：

用于根据所述摘要语法树中子树所包括的节点数目，将所述子树进行分组的分组单元。

Images