一种基于数字指纹的代码相似度检测方法

摘要

本发明涉及一种基于数字指纹的代码相似度检测方法，属于计算机应用技术领域。本发明的检测方法包括代码预处理、分词、格式化、采用数字指纹技术进行数值化、计算数字指纹序列和相似度计算六个步骤。本发明计算过程简单，代码相似度检测结果可信度高，能够选取出较有效的代码特征，降低了误判的概率，能够识别多种代码抄袭掩饰手段，采用数字指纹的方法，有效地提高了整体计算速度。

主权项

一种基于数字指纹的代码相似度检测方法，其特征在于检测过程为：1)将对比双方源代码分别进行预处理，即对双方源代码进行以下操作：删除注释、删除宏命令、删除与代码语义无关的内容；2)将经步骤1)预处理后的双方代码分别进行分词，即将代码中相邻的不同类型的词之间加上空格；3)将经步骤2)分词过后的双方代码分别进行格式化，即将代码中所含关键词中表征数据类型的词和标识符分别用一个自定义的词进行替换，并删除相邻词与词之间的空格，形成格式化代码串；4)将经步骤3)处理后的双方的格式化代码串分别利用数字指纹技术转化成一系列的数值，形成数值序列，包括以下两个步骤：4.1将格式化代码串重叠切分为固定长度的特征片段；4.2使用Karp‑Rabin方法将所有特征片段转化为其对应的数值序列；5)利用步骤4)中获得的双方数值序列分别计算双方的数字指纹序列，包括以下四个步骤：5.1从已训练好的无效代码库中提取无效数值；5.2将步骤4)获得的双方的数值序列中去除掉由步骤5.1中所提取的无效数值，余下的即为双方的有效数值序列；5.3将步骤5.2所获得的双方有效数值序列分别进行重叠切分，形成多个数值片段；5.4采用最小Hash法从由步骤5.3中获得的双方的多个数值片段中选取计算双方的数字指纹序列，即从多个数值片段中选择最小的Hash值组成数字指纹序列；6)根据步骤5)中得出的双方的数字指纹序列来计算双方源代码的相似度值，并用其表征双方代码间的相似程度；上述步骤2中所述不同类型包括与双方源代码编写方式对应的关键词、标识符、操作符和库函数；上述步骤4和步骤5中所述的重叠切分方法为将代码串或者数值序列按照字符顺序依次切分成固定长度的数值片段，其中相邻的两个片段只有前一个片段的第一个字符与后一个片段的最后一个字符不同，其余内容完全相同；上述步骤6中所述的计算双方指纹间的相似度值的方法为采用公式 Similarity ( A , B ) = 2 * | LCS ( F ( A ) , F ( B ) ) | | F ( A ) | + | F ( B ) | 进行计算；其中A、B代表双方用于对比的源代码，F(A)和F(B)分别表示代码A和B的数字指纹序列的长度，LCS(F(A)，F(B))表示指纹序列F(A)和F(B)之间的最长公共子序列的长度，Similarity(A，B)即表示双方代码的相似度。