本发明公开一种基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法，采用两层相似性检测方法对大规模的软件样本进行抄袭检测与证据生成：首先使用代码映射方法对大规模程序进行粗粒度的相似性分析，快速搜索疑似相似的程序；然后采用词法分析对于可疑的相似程序进行细粒度分析，判定程序相似性和生成相似代码证据。通过以上方法，可以快速准确地在大规模样本找到抄袭代码，并提供相应的证据以作支撑。
1.基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法，其特征在于，包括如下步骤：
步骤S101：通过分析待检测样本集A和源代码样本集B中样本程序的代码，获取每一个样本程序的第三方库调用信息和词频信息；基于代码映射思想，将样本程序的第三方库调用信息和词频信息转化为一个向量；对待检测样本集A，生成样本程序的向量集A*；对源代码样本集B，生成样本程序的向量集C；
步骤S102：将向量集C中的程序的向量表示作为输入，程序的源代码相似性作为标签，采用机器学习方法训练相似计算网络，用于根据程序的向量表示判定程序代码相似性；
步骤S103：利用步骤S102训练得到的相似计算网络，对向量集C和待检测样本集A中的每一个样本的向量表示进行相似度计算和相似性判定，得到向量集C和样本集A的向量集间的相似关系；
步骤S104：对于待检测样本集A中的每一个程序，如果在向量集C中不存在与其有相似关系的样本，将归类到无显著相似性的程序样本集A1中；如果存在，将该样本与相似样本归类为可疑样本集A′，并保留其抄袭关系；
步骤S105：将可疑样本集A′的源代码按照其已有的抄袭关系与源代码样本集B中的样本使用贪婪字符串匹配算法进行计算，得到相应的相似度和相似部分；
步骤S106：对经过相似度计算的可疑样本集A′的源代码，按照其相似度大小是否大于阈值分为有无相似样本两类；若其具有相似样本，将该代码及其相似部分和抄袭关系归类到抄袭程序样本集A2中，如果不具有相似样本，将该代码归类到无显著相似性的程序样本集A1中；
步骤S107：对于抄袭程序样本集A2中的每一个样本，提取步骤S105得到的相似部分，作为其抄袭证据，构建含证据的相似集A2；
步骤S108：输出抄袭程序样本集A2和无显著相似性的程序样本集A1。
2.根据权利要求1所述的方法，其特征在于，所述步骤S101具体为对于待检测样本集A和源代码样本集B中样本程序的代码，使用语法分析工具提取代码的语法树，从语法树中提取调用的API序列；使用K-gram算法对源代码进行处理，得到对应的K-gram词频信息；对于API序列和K-gram词频信息都使用one-hot的表示形式，表示为两个一维向量，其中向量的每个位置代表相应的API名称或者K-gram，向量的每个位置的数据代表出现的频数；对于一个源代码的one-hot的两个向量，使用代码映射的方法将其转化为特定维度的向量；通过以上步骤，获得样本集A的向量集A*和样本集B的向量集C。
3.根据权利要求1所述的方法，其特征在于，所述步骤S102使用向量集C，通过小批量梯度下降法训练相似计算网络，具体步骤如下：步骤S201：对于向量集C，使用向量集中所有的向量组成一对一的向量对，形成向量对集D，并且向量对集D的每对源代码的相似度Si已知，其中i为Si在向量对集D中的顺序；
步骤S202：从向量集C中随机选取若干源代码样本组成新的向量集C1；
步骤S203：对于向量集C1，使用向量集中所有的向量组成一对一的向量对，形成向量对集D′，每个向量对的两个向量分别为d1i和d2i，并且向量对集D′的每对源代码的相似度Si已知；
步骤S204：对于向量对集D′中的每对向量，使用神经网络计算其最终的相似度S′i；
步骤S205：对于相对集D′的每一个向量对，使用以下公式更新权值w：w＝w+2α∑i(Si′-Si)2di
步骤S206：计算均方误差E[(S′i-Si) ]＜阈值θ是否成立，若成立，训练结束；若不成立，返回步骤S202；
4.根据权利要求1所述的方法，其特征在于，所述步骤S103具体为对于样本集A中的每一个源代码，都使用以下步骤计算其与样本集B中的所有样本的相似度：步骤S301：按顺序从样本集A中选取源代码，记其在向量集A*中的表示为ai，其中i为ai在向量集A*中的顺序；
步骤S302：按顺序从样本集B中选取源代码，记其在向量集C中的表示为cj，其中j为cj在向量集C中的顺序；
步骤S303：使用相似计算网络计算ai和cj的相似度Sij；
步骤S304：判断cj是否是向量集C中的最后一个，若是，转到步骤S305；若不是，转到步骤S302；
步骤S305：判断ai是否是样本集A中的最后一个，若是，结束计算；若不是，转到步骤S301。
5.根据权利要求1所述的方法，其特征在于，所述步骤S104具体为对于样本集A中的每一个源代码，都使用以下步骤判断其是否有相似样本：步骤S401：按顺序从样本集A中选取源代码，记其向量表示为ai，其中i为ai在向量集A*中的顺序；
步骤S402：从ai与向量集C的相似度中按顺序选取ai与向量cj的相似度Sij，其中j为cj在向量集C中的顺序；
步骤S403：判断Sij和阈值θ的关系，若Sij大于等于阈值θ，则ai与向量集C中的cj存在抄袭关系，并将其关系记录到可疑的抄袭关系中；若Sij小于阈值θ，判断cj是否向量集C的最后一个，若是，转到S404，若否，转到S402；
步骤S404：若ai的可疑抄袭关系为空，记向量表示为ai的源代码不具有相似样本；
步骤S405：判断ai是否为源代码样本集A的最后一个，若是，则结束；若否，则转到步骤S402；
根据源代码样本是否有相似样本，将没有相似样本的源代码和其向量表示剔除，并将其源代码存储在无显著相似性的程序样本集A1中，将有相似样本的源代码和其相似度集合保留，并保存为可疑样本集A′。
6.根据权利要求5所述的方法，其特征在于，所述步骤S104具体为对保留下的可疑样本集A′中的源代码和其相似度集合，使用如下步骤得到其抄袭关系：a)按顺序从样本集A′中选取源代码，记其向量表示为ai′，其中i为ai′在向量集A*中的顺序；
b)从ai′与向量集C的相似度中按顺序选取ai′与向量cj的相似度Sij，其中j为cj在向量集C中的顺序；
c)判断Sij和阈值θ的关系，若Sij大于等于阈值θ，ai′与向量集C中的cj存在抄袭关系，并将其关系记录到可疑的抄袭关系中；若Sij小于阈值θ，ai′与向量集B中的cj不存在抄袭关系；
d)判断j是否等于向量集C的大小，若不等，转到b)；
e)判断ai′是否为源代码样本集A的最后一个，若是，则结束；若否，则转到a)。
7.根据权利要求1所述的方法，其特征在于，所述步骤S105对于可疑样本集A′中的每一个源代码，使用RKR-GST算法计算其与样本集B相似度并获得相似部分的步骤如下：步骤S501：按顺序从样本集A′中选取源代码，记其向量表示为ai′，其中i为ai′在向量集*A中的顺序；
步骤S502：对于ai′，在可疑的抄袭关系中提取ai′与样本集B的抄袭关系，并将源代码样本集B中与ai′有抄袭关系的样本筛选出来，组成源代码样本集Bi；
步骤S503：按顺序从样本集Bi中选取源代码，记其为bj′，其中j为bj′在样本集Bi中的顺序；
步骤S504：使用RKR-GST算法计算ai′和bj′的相似度Sij′并获得其相似部分；
步骤S505：判断bj′是否源代码样本集Bi的最后一个，若是，转到步骤S506；若不是，转到步骤S503；
步骤S506：判断ai′是否样本集A′的最后一个，若是，则结束；若不是，转到步骤S501。
8.根据权利要求7所述的方法，其特征在于，步骤S105中使用RKR-GST算法计算源代码ai′和bj′的相似度Sij′的过程如下：步骤S601：对于源代码ai′和bj′中的每一个源文件进行抽取代码和去除注释的处理，得到源代码ai所有的可处理源文件集P和源代码bj所有的可处理源文件集Q；
步骤S602：总相似度S＝0，P项目大小Psum＝0，Q项目大小Qsum＝0，项目Q的每个可处理源文件记为Qj，项目P的每个可处理源文件记为Pi；
步骤S603：Qsum＝∑jQj，Psum＝∑iPi；
步骤S604：按顺序从项目P选择可处理源文件Pi，最大相似度SIMi＝0，最大匹配NUMi＝
步骤S605：按顺序从项目Q选择可处理源文件Qj，计算Pi和Qj的相似度SIMij；
步骤S606：如果SIMij＞SIMi那么SIMi＝SIMij，NUMi＝j；
步骤S607：判断Qj是否为项目Q的最后一个，若不是，转到步骤S605；
步骤S608： 判断Pi是否为项目P的最后一个，若
9.根据权利要求8所述的方法，其特征在于，步骤S105使用RKR-GST算法计算两个代码文件相似度以及相似部分的过程具体为：步骤S701：搜索长度s＝初始搜索长度，停止条件＝false；
步骤S702：进行一次扫描的最大匹配Lmax＝scanpattern(s)；
步骤S703：判断Lmax和s的关系，如果Lmax＞2×s，则s＝Lmax，转到步骤S704；否则，从队列中选择匹配创建标记，即markstrings(s)；
步骤S704：如果s＞2×最小匹配长度，那么 否则如果s＞最小匹配长度，那么s＝最小匹配长度；否则停止条件＝true；
步骤S705：判断停止条件是否为true，若为true，结束；若为false，转到步骤S702；
进行一次扫描获取匹配的scanpattem(s)过程具体如下：步骤S801：将两个代码文件中的字符串分别记为T和P；
步骤S802：找到T中第一个没有被标记的字符T1，记Tt为第t个没有被标记的字符，对于每一个没有标记的Tt；如果到下一个标记的距离≤s，将t指向下一个标记后的第一个没有被标记的字符；否则为子串Tt..Tt+s-1创造一个KR哈希值，并加入哈希表中；
步骤S803：找到P中第一个没有被标记的字符P1，记Pp为第p个没有被标记的字符，对于每一个没有标记的Pp；如果到下一个标记的距离≤s，将p指向下一个标记后的第一个没有被标记的字符；否则为子串Pp..Pp+s-1创造一个KR哈希值，并加入哈希表中；
步骤S804：按顺序取出哈希表中的一次匹配，令k＝s；
步骤S805：如果PP+K＝TT+K且PP+K没有被标记且TT+K没有被标记，k＝k+1，转到步骤S805；
步骤S806：如果k＞2×s，返回k，结束；否则，记录最新的最大匹配；
步骤S807：如果哈希表中还有匹配未取出，转到步骤S804；
选择匹配创建标记的markstrings(s)过程具体如下：步骤S901：从最长的最大匹配组成的队列开始；
步骤S902：如果当前队列为空，跳到下一个非空次长的队列；
步骤S903：对队列中最长的长度为L的最大匹配，将匹配(p，t，L)从队列中移除；
步骤S904：如果该匹配与之前的匹配没有交叉，标记匹配到的所有字符，即Tt..Tt+s-1和Pp..Pp+s-1，已标记字符长度＝已标记字符长度+L；否则如果L-Loccluded≥s，即匹配的长度与交叉的长度的差大于最小匹配长度，将匹配替换为匹配中未标记的部分；
通过RKR-GST算法，可以得到已标记字符长度和标记的字符位置，使用已标记字符长度除以总长度可以得到两个代码文件的相似度；使用标记的字符位置集合可以作为两个代码的相似部分。
10.根据权利要求1所述的方法，其特征在于，步骤S106在判断代码在样本集B中是否有相似样本的过程中，使用和权利要求6中判断是否有相似样本的过程相同的方法进行；若代码在样本集B中有相似样本，则将该源代码、其抄袭关系以及抄袭证据保留下来，并存储在抄袭程序样本集A2；若代码在样本集B中没有相似样本，则将该代码存储到无显著相似性的程序样本集A1中。
基于代码映射和词法分析的大规模程序相似性快速检测与证
据生成方法
技术领域
[0001] 本发明涉及源代码程序分析及软件抄袭检测技术领域，特别涉及一种多层的源代码程序相似度检测方法。
背景技术
[0002] 随着计算机软件产业的迅速发展，软件的安全问题得到了越来越多的研究人员、教育人员及软件企业的重视。而计算机软件的开源，给软件的抄袭带来了更便利的条件。近几年来，各类软件侵权案件时有发生，Google、Apple、eBay等都曾卷入到相关案件中。
[0003] 为了对抗软件抄袭案件，保护软件知识产权，国内外的研究人员提出了大量的软件抄袭检测技术。以应用场景和技术手段作为基准，可将现有的软件抄袭检测技术归为三类：源码抄袭检测技术，基于软件水印的抄袭检测技术，以及基于软件胎记的抄袭检测技术。目前发展最为成熟、使用最为广泛的是源码检测技术。
[0004] 但是，目前的源代码抄袭检测技术存在一系列的局限性：
[0005] 1)目前大部分源码检测技术都面向小规模的抄袭检测，无法满足大规模抄袭检测场景下的快速检测需要；
[0006] 2)混淆技术的发展增加软件抄袭检测的难度，会使得一部分的抄袭检测技术失效；
[0007] 3)现有的很多抄袭检测技术都只是提供了一个简单的结果，并没有提供具体有力的抄袭证据；
[0008] 4)现有的抄袭检测技术很难做到检测精度和时间开销的同步优化，很多抄袭检测方法不能投入应用。
发明内容
[0009] 本发明的内容在于提出一种基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法，以解决上述技术问题。本方法采用两层相似性检测方法对大规模的软件样本进行抄袭检测与证据生成：首先使用代码映射方法对大规模程序进行粗粒度的相似性分析，快速搜索疑似相似的程序；然后采用词法分析对于可疑的相似程序进行细粒度分析，判定程序相似性和生成相似代码证据。通过以上方法，可以快速准确地在大规模样本找到抄袭代码，并提供相应的证据以作支撑。
[0010] 为了实现上述目的，本发明采用以下技术方案：
[0011] 基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法，包括如下步骤：
[0012] 1)、基于代码映射的疑似相似程序搜索：
[0013] 步骤S101：通过分析待检测样本集A和源代码样本集B中样本程序的代码，获取每一个样本程序的第三方库调用信息和词频信息；基于代码映射思想，将样本程序的第三方库调用信息和词频信息转化为一个向量；对待检测样本集A，生成样本程序的向量集A*；对源代码样本集B，生成所有样本程序的向量集C；
[0014] 步骤S102：将向量集C中的程序的向量表示作为输入，程序的源代码相似性作为标签，采用机器学习方法训练相似计算网络，用于根据程序的向量表示判定程序代码相似性；
[0015] 步骤S103：利用步骤S102训练得到的相似计算网络，对向量集C和待检测样本集A中的每一个样本的向量表示进行相似度计算和相似性判定，得到向量集C和样本集A的向量集的相似关系；
[0016] 步骤S104：对于待检测样本集A中的每一个程序，如果在源代码样本集B中不存在与其有相似关系的样本，将归类到无显著相似性的程序样本集A1中；如果存在，将该样本与相似样本归类为可疑样本集A′，并保留其抄袭关系；
[0017] 2)、基于词法分析的程序相似判定与证据生成：
[0018] 步骤S105：将可疑样本集A′的源代码按照其已有的抄袭关系与源代码样本集B中的样本使用贪婪字符串匹配算法进行计算，得到相应的相似度和相似部分；
[0019] 步骤S106：对经过相似度计算的可疑样本集A′的源代码，按照其相似度大小是否大于阈值分为有无相似样本两类；若其具有相似样本，将该代码及其相似部分和抄袭关系归类到抄袭程序样本集A2中，如果不具有相似样本，将该代码归类到无显著相似性的程序样本集A1中；
[0020] 步骤S107：对于抄袭程序样本集A2中的每一个样本，提取步骤S105得到的相似部分，作为其抄袭证据，构建含证据的相似集A2；
[0021] 步骤S108：输出抄袭程序样本集A2和无显著相似性的程序样本集A1。
[0022] 进一步的，所述步骤S101具体为对于待检测样本集A和源代码样本集B中样本程序的代码，使用语法分析工具提取代码的语法树，从语法树中提取调用的API序列；使用K-gram算法对源代码进行处理，得到对应的K-gram词频信息；对于API序列和K-gram词频信息都使用one-hot的表示形式，表示为两个一维向量，其中向量的每个位置代表相应的API名称或者K-gram，向量的每个位置的数据代表出现的频数；对于一个源代码的one-hot的两个向量，使用代码映射的方法将其转化为特定维度的向量；通过以上步骤，获得样本集A的向量集A*和样本集B的向量集C。
[0023] 进一步的，所述步骤S102使用向量集C，通过小批量梯度下降法训练相似计算网络，具体步骤如下：
[0024] 步骤S201：对于向量集C，使用向量集中所有的向量组成一对一的向量对，形成向量对集D，并且向量对集D的每对源代码的相似度Si已知；
[0025] 步骤S202：从向量集C中随机选取若干源代码样本组成新的向量集C1；
[0026] 步骤S203：对于向量集C1，使用向量集中所有的向量组成一对一的向量对，形成向量对集D′，每个向量对的两个向量分别为d1i和d2i，并且向量对集D′的每对源代码的相似度Si已知；
[0027] 步骤S204：对于向量对集D′中的每对向量，使用神经网络计算其最终的相似度S′i；
[0028] 步骤S205：对于相对集D′的每一个向量对，使用以下公式更新权值w：
[0029] w＝w+2α∑i(Si′-Si)2di
[0030] 式中：
[0031] α——训练步长；
[0032] di——向量d1i和d2i的组合；
[0033] 步骤S206：计算均方误差E[(S′i-Si)2]<阈值θ是否成立，若成立，训练结束；若不成立，返回步骤S202；
[0034] 通过以上步骤，完成相似计算网络的模型训练。
[0035] 进一步的，所述步骤S103具体为对于样本集A中的每一个源代码，都使用以下步骤计算其与样本集B中的所有样本的相似度：
[0036] 步骤S301：按顺序从样本集A中选取源代码，记其在向量集A*中的表示为ai，其中i为ai在向量集A*中的顺序；
[0037] 步骤S302：按顺序从样本集B中选取源代码，记其在向量集C中的表示为cj，其中j为cj在向量集C中的顺序；
[0038] 步骤S303：使用相似计算网络计算ai和cj的相似度Sij；
[0039] 步骤S304：判断cj是否是向量集C中的最后一个，若是，转到步骤S305；若不是，转到步骤S302；
[0040] 步骤S305：判断ai是否是样本集A中的最后一个，若是，结束计算；若不是，转到步骤S301。
[0041] 进一步的，所述步骤S104具体为对于样本集A中的每一个源代码，都使用以下步骤判断其是否有相似样本：
[0042] 步骤S401：按顺序从样本集A中选取源代码，记其向量表示为ai，其中i为ai在向量集A*中的顺序；
[0043] 步骤S402：从ai与向量集C的相似度中按顺序选取ai与向量cj的相似度Sij，其中j为cj在向量集C中的顺序；
[0044] 步骤S403：判断Sij和阈值θ的关系，若Sij大于等于阈值θ，则ai与向量集C中的cj存在抄袭关系，并将其关系记录到可疑的抄袭关系中；若Sij小于阈值θ，判断cj是否向量集C的最后一个，若是，转到S404，若否，转到S402；
[0045] 步骤S404：若ai的可疑抄袭关系为空，记向量表示为ai的源代码不具有相似样本；
[0046] 步骤S405：判断ai是否为源代码样本集A的最后一个，若是，则结束；若否，则转到步骤S402；
[0047] 根据源代码样本是否有相似样本，将没有相似样本的源代码和其向量表示剔除，并将其源代码存储在无显著相似性的程序样本集A1中，将有相似样本的源代码和其相似度集合保留，并保存为可疑样本集A′。
[0048] 进一步的，所述步骤S104具体为对保留下的可疑样本集A′中的源代码和其相似度集合，使用如下步骤得到其抄袭关系：
[0049] a)按顺序从样本集A′中选取源代码，记其向量表示为ai′，其中i为ai′在向量集A*中的顺序；
[0050] b)从ai′与向量集C的相似度中按顺序选取ai′与向量cj的相似度Sij，其中j为cj在向量集C中的顺序；
[0051] c)判断Sij和阈值θ的关系，若Sij大于等于阈值θ，ai′与向量集C中的cj存在抄袭关系，并将其关系记录到可疑的抄袭关系中；若Sij小于阈值θ，ai′与向量集B中的cj不存在抄袭关系；
[0052] d)判断j是否等于向量集C的大小，若不等，转到b)；
[0053] e)判断ai′是否为源代码样本集A的最后一个，若是，则结束；若否，则转到a)。
[0054] 进一步的，所述步骤S105对于样本集A中的每一个源代码，使用RKR-GST算法计算其与样本集B相似度并获得相似部分的步骤如下：
[0055] 步骤S501：按顺序从样本集A′中选取源代码，记其向量表示为a′i，其中i为ai′在向*量集A中的顺序；
[0056] 步骤S502：对于ai′，在可疑的抄袭关系中提取ai′与样本集B的抄袭关系，并将源代码样本集B中与ai′有抄袭关系的样本筛选出来，组成源代码样本集Bi；
[0057] 步骤S503：按顺序从样本集Bi中选取源代码，记其为bj′，其中j为bj′在样本集Bi中的顺序；
[0058] 步骤S504：使用RKR-GST算法计算ai′和bj′的相似度Sij′并获得其相似部分；
[0059] 步骤S505：判断bj′是否源代码样本集Bi的最后一个，若是，转到步骤S506；若不是，转到步骤S503；
[0060] 步骤S506：判断ai′是否样本集A′的最后一个，若是，则结束；若不是，转到步骤S501。
[0061] 进一步的，步骤S105中使用RKR-GST算法计算源代码ai′和bj′的相似度Sij′的过程如下：
[0062] 步骤S601：对于源代码ai′和bj′中的每一个源文件进行抽取代码和去除注释的处理，得到源代码ai所有的可处理源文件集P和源代码bj所有的可处理源文件集Q；
[0063] 步骤S602：总相似度S＝0，P项目大小Psum＝0，Q项目大小Qsum＝0，项目Q的每个可处理源文件记为Qj，项目P的每个可处理源文件记为Pi；
[0064] 步骤S603：Qsum＝∑jQj,Psum＝∑iPi；
[0065] 步骤S604：按顺序从项目P选择可处理源文件Pi,最大相似度SIMi＝0,最大匹配NUMi＝0；
[0066] 步骤S605：按顺序从项目Q选择可处理源文件Qj，计算Pi和Qj的相似度SIMij；
[0067] 步骤S606：如果SIMij>SIMi那么SIMi＝SIMij，NUMi＝j；
[0068] 步骤S607：判断Qj是否为项目Q的最后一个，若不是，转到步骤S605；
[0069] 步骤S608： 判断Pi是否为项目P的最后一个，若不是，转到步骤S604；
[0070] 步骤S609：S＝S/(Psum+Qsum)；
[0071] S即为源代码ai′和bj′的相似度Sij′。
[0072] 进一步的，步骤S105使用RKR-GST算法计算两个代码文件相似度以及相似部分的过程具体为：
[0073] 步骤S701：搜索长度s＝初始搜索长度，停止条件＝false；
[0074] 步骤S702：进行一次扫描的最大匹配Lmax＝scanpattern(s)；
[0075] 步骤S703：判断Lmax和s的关系，如果Lmax>2×s，则s＝Lmax，转到步骤S704；否则，从队列中选择匹配创建标记，即markstrings(s)；
[0076] 步骤S704：如果s>2×最小匹配长度，那么 否则如果s>最小匹配长度，那么s＝最小匹配长度；否则停止条件＝true；
[0077] 步骤S705：判断停止条件是否为true，若为true，结束；若为false，转到步骤S702；
[0078] 进行一次扫描获取匹配的scanpattern(s)过程具体如下：
[0079] 步骤S801：将两个代码文件中的字符串分别记为T和P；
[0080] 步骤S802：找到T中第一个没有被标记的字符T1，记Tt为第t个没有被标记的字符，对于每一个没有标记的Tt；如果到下一个标记的距离≤s，将t指向下一个标记后的第一个没有被标记的字符；否则为子串Tt..Tt+s-1创造一个KR哈希值，并加入哈希表中；
[0081] 步骤S803：找到P中第一个没有被标记的字符P1，记Pp为第p个没有被标记的字符，对于每一个没有标记的Pp；如果到下一个标记的距离≤s，将p指向下一个标记后的第一个没有被标记的字符；否则为子串Pp..Pp+s-1创造一个KR哈希值，并加入哈希表中；
[0082] 步骤S804：按顺序取出哈希表中的一次匹配，令k＝s；
[0083] 步骤S805：如果PP+K＝TT+K且PP+K没有被标记且TT+K没有被标记，k＝k+1，转到步骤S805；否则转到步骤S806；
[0084] 步骤S806：如果k>2×s，返回k，结束；否则，记录最新的最大匹配；
[0085] 步骤S807：如果哈希表中还有匹配未取出，转到步骤S804；
[0086] 步骤S808：返回最长的最大匹配的长度，结束；
[0087] 选择匹配创建标记的markstrings(s)过程具体如下：
[0088] 步骤S901：从最长的最大匹配组成的队列开始；
[0089] 步骤S902：如果当前队列为空，跳到下一个非空次长的队列；
[0090] 步骤S903：对队列中最长的长度为L的最大匹配，将匹配(p，t，L)从队列中移除；
[0091] 步骤S904：如果该匹配与之前的匹配没有交叉，标记匹配到的所有字符，即Tt..Tt+s-1和Pp..Pp+s-1，已标记字符长度＝已标记字符长度+L；否则如果L-Loccluded≥s，即匹配的长度与交叉的长度的差大于最小匹配长度，将匹配替换为匹配中未标记的部分；
[0092] 通过RKR-GST算法，可以得到已标记字符长度和标记的字符位置，使用已标记字符长度除以总长度可以得到两个代码文件的相似度；使用标记的字符位置集合可以作为两个代码的相似部分。
[0093] 进一步的，步骤S106在判断代码在样本集B中是否有相似样本的过程中，使用和权利要求6中判断是否有相似样本的过程相同的方法进行；若代码在样本集B中有相似样本，则将该源代码、其抄袭关系以及抄袭证据保留下来，并存储在抄袭程序样本集A2；若代码在样本集B中没有相似样本，则将该代码存储到无显著相似性的程序样本集A1中。
[0094] 本发明的进一步改进在于:所述步骤S101中API序列的提取方法是对代码进行语法分析，以生成代码的语法分析序列；在API所在的语句中，通过词法分析对API的特殊标识识别；对所有具有API标识的代码都进行提取，获得API序列。
[0095] 本发明的进一步改进在于:所述步骤S101中K-gram词频信息的提取方法是将代码进行去除注释、去除空格处理后，对于字符串中的每一个字母，都取其后k-1字母组成K-gram；然后对这些K-gram进行统计，获得K-gram的种类和频数。
[0096] 本发明的进一步改进在于:所述步骤S101中将两个向量映射为特定维度向量的方法是对于两个一维向量可以直接将两个向量进行拼接，获得源代码的一维向量表示；或者对于两个一维向量在空白处补零构成2×n的矩阵，使用合适的矩阵变化即可获得代码的向量表示。
[0097] 相对于现有技术，本发明具有以下有益效果：
[0098] 1)本发明方法可以针对不同语言进行不同的处理，不依赖于固定语言，具有更好的适用性；
[0099] 2)本发明方法通过代码映射方法可以对源代码集进行快速有效的筛选，能够有效应对大规模抄袭检测的场景；
[0100] 3)本发明方法通过词法分析方法可以对可疑代码集进行详细有效的检测，能够提供具体真实有效的证据；
[0101] 4)本发明方法提供一种有效的大规模抄袭检测的思路，即先检测筛选，后证据生成的方法，可以根据实际情况，在两个阶段进行合适替换，以更贴合实际要求。
附图说明
[0102] 图1为本发明基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法整体流程图；
[0103] 图2为基于梯度下降算法的相似计算网络训练过程流程图。
具体实施方式
[0104] 以下结合附图详细说明本发明基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法的具体实施方式。
[0105] 图1为本发明基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法整体流程图；
[0106] 本发明公开一种基于代码映射和词法分析的大规模程序相似性快速检测与证据生成方法，包括以下步骤：
[0107] 步骤S101：通过分析待检测样本集A和源代码样本集B中样本程序的代码，获取每一个样本程序的第三方库调用信息和词频信息；基于代码映射思想，将样本程序的第三方库调用信息和词频信息转化为一个向量；对待检测样本集A，生成样本程序的向量集A*；对源代码样本集B，生成所有样本程序的向量集C。
[0108] 具体而言，在第三方库调用信息的提取过程中，可以使用ANTLR软件根据相应的语言编写语法文件，从而生成语法分析工具，能够对代码中的库调用信息进行识别；在词频信息的提取过程中，可以对代码进行必要的预处理，例如去除注释，去除空行、空格等，然后对代码进行切片操作，获得代码中所含的词频种类和出现频次；最后，对于库调用信息和词频信息都可以使用一维向量表示，向量中变量的下标代表调用库种类或者单词种类，向量中变量的值代表库出现的次数或者单词出现的次数；对于两个一维向量可以直接拼合，然后进行简单的矩阵变化即可获得代码需要的向量表示。
[0109] 步骤S102：将向量集C中的程序的向量表示作为输入，程序的源代码相似性作为标签，采用机器学习方法训练相似计算网络，用于根据程序的向量表示判定程序代码相似性。
[0110] 结合图2，具体而言，步骤S102通过小批量梯度下降法训练相似计算网络，具体步骤如下：
[0111] 步骤S201：对于向量集C，使用向量集中所有的向量组成一对一的向量对，形成向量对集D，并且向量对集D的每对源代码的相似度Si已知；
[0112] 步骤S202：从向量集C中随机选取一定数量(如64,128,512等)的源代码样本组成新的向量集C1；
[0113] 步骤S203：对于向量集C1，使用向量集中所有的向量组成一对一的向量对，形成向量对集D′，每个向量对的两个向量分别为d1i和d2i，并且向量对集D′的每对源代码的相似度Si已知；
[0114] 步骤S204：对于向量对集D′中的每对向量，使用神经网络计算其最终的相似度S′i；
[0115] 步骤S205：对于相对集D′的每一个向量对，使用以下公式更新权值w：
[0116] ,w＝w+2α∑i(Si′-Si)2di
[0117] 式中：
[0118] α——训练步长；
[0119] di——向量d1i和d2i的组合；
[0120] 步骤S206：计算均方误差E[(S′i-Si)2]<阈值θ是否成立，若成立，训练结束；若不成立，返回步骤S202；
[0121] 步骤S207：输出相似计算网络。
[0122] 步骤S103：利用步骤S102训练得到的相似计算网络，对向量集C和待检测样本集A中的每一个样本的向量表示进行相似性判定，搜索较高相似性的样本。
[0123] 具体而言，对于样本集A中的每一个源代码，计算其与样本集B中所有样本的相似度的具体步骤为：
[0124] 步骤S301：按顺序从样本集A中选取源代码，记其在向量集A*中的表示为ai，其中i为ai在向量集A*中的顺序；
[0125] 步骤S302：按顺序从样本集B中选取源代码，记其在向量集C中的表示为cj，其中j为cj在向量集C中的顺序；
[0126] 步骤S303：使用相似计算网络计算ai和cj的相似度Sij；
[0127] 步骤S304：判断cj是否是向量集C中的最后一个，若是，转到步骤S305；若不是，转到步骤S302；
[0128] 步骤S305：判断ai是否是样本集A中的最后一个，若是，结束计算；若不是，转到步骤S301。
[0129] 步骤S104：对于代码集A中的每一个程序，如果在源代码样本集B中不存在与其有相似关系的样本，将归类到无显著相似性的程序样本集A1中；如果存在，将该样本与相似样本归类为可疑样本集A′，并保留其抄袭关系。
[0130] 具体而言，包括以下步骤：
[0131] 步骤S401：按顺序从样本集A中选取源代码，记其向量表示为ai，其中i为ai在向量*集A中的顺序；
[0132] 步骤S402：从ai与向量集C的相似度中按顺序选取ai与向量cj的相似度Sij，其中j为cj在向量集C中的顺序；
[0133] 步骤S403：判断Sij和阈值θ的关系，若Sik大于等于阈值θ，则ai与向量集C中的ij存在抄袭关系，并将其关系记录到可疑的抄袭关系中；若Sij小于阈值θ，判断j是否向量集C的最后一个，若是，转到步骤S404，若否，转到步骤S402；
[0134] 步骤S404：若ai的可疑抄袭关系为空，记向量表示为ai的源代码不具有相似样本；
[0135] 步骤S405：判断ai是否为源代码样本集A的最后一个，若是，则结束；若否，则转到步骤S402；
[0136] 步骤S105：将可疑样本集A′中的源代码按照其已有的抄袭关系与源代码样本集B中的样本使用贪婪字符串匹配算法进行计算，得到相应的相似度和相似部分；
[0137] 具体而言，对于可疑样本集A′中的每一个源代码，计算其与样本集B相似度并获得相似部分的步骤如下：
[0138] 步骤S501：按顺序从样本集A′中选取源代码，记其向量表示为a′i，其中i为ai′在向*量集A中的顺序；
[0139] 步骤S502：对于ai′，在可疑的抄袭关系中提取ai′与样本集B的抄袭关系，并将源代码样本集B中与ai′有抄袭关系的样本筛选出来，组成源代码样本集Bi；
[0140] 步骤S503：按顺序从样本集Bi中选取源代码，记其为bj′，其中j为bj′在样本集Bi中的顺序；
[0141] 步骤S504：使用RKR-GST算法计算ai和bj的相似度Sij′并获得其相似部分；
[0142] 步骤S505：判断bj′是否源代码样本集Bi的最后一个，若是，转到步骤S505；若不是，转到步骤S503
[0143] 步骤S506：判断ai′是否样本集A′的最后一个，若是，则结束；若不是，转到步骤S501。
[0144] 具体而言，计算源代码ai′和bj′的总相似度Sij′的过程如下：
[0145] 步骤S601：对于源代码ai′和bj′中的每一个源文件进行抽取代码和去除注释的处理，得到源代码ai所有的可处理源文件集P和源代码bj所有的可处理源文件集Q；
[0146] 步骤S602：总相似度S＝0，P项目大小Psum＝0，Q项目大小Qsum＝0，项目Q的每个可处理源文件记为Qj，项目P的每个可处理源文件记为Pi；
[0147] 步骤S603：Qsum＝∑jQj,Psum＝∑iPi；
[0148] 步骤S604：按顺序从项目P选择可处理源文件Pi,最大相似度SIMi＝0,最大匹配NUMi＝0；
[0149] 步骤S605：按顺序从项目Q选择可处理源文件Qj，计算Pi和Qj的相似度SIMij；
[0150] 步骤S606：如果SIMij>SIMi那么SIMi＝SIMij，NUMi＝j；
[0151] 步骤S607：判断Qj是否为项目Q的最后一个，若不是，转到步骤S605；
[0152] 步骤S608： 判断Pi是否为项目P的最后一个，若不是，转到步骤S604；
[0153] 步骤S609：S＝S/(Psum+Qsum)；
[0154] S即为源代码ai′和bj′的相似度Sij′。
[0155] 具体而言，使用RKR-GST算法计算两个代码文件相似度以及相似部分的过程具体为：
[0156] 步骤S701：搜索长度s＝初始搜索长度，停止条件＝false；
[0157] 步骤S702：进行一次扫描的最大匹配Lmax＝scanpattern(s)；
[0158] 步骤S703：判断Lmax和s的关系，如果Lmax>2×s，则s＝Lmax，转到步骤S704；否则，从队列中选择匹配创建标记，即markstrings(s)；
[0159] 步骤S704：如果s>2×最小匹配长度，那么 否则如果s>最小匹配长度，那么s＝最小匹配长度；否则停止条件＝true；
[0160] 步骤S705：判断停止条件是否为true，若为true，结束；若为false，转到步骤S702。
[0161] 进行一次扫描获取匹配的scanpattern(s)过程具体如下：
[0162] 步骤S801：将两个代码文件中的字符串分别记为T和P；
[0163] 步骤S802：找到T中第一个没有被标记的字符T1，记Tt为第t个没有被标记的字符，对于每一个没有标记的Tt；如果到下一个标记的距离≤s，将t指向下一个标记后的第一个没有被标记的字符；否则为子串Tt..Tt+s-1创造一个KR哈希值，并加入哈希表中；
[0164] 步骤S803：找到P中第一个没有被标记的字符P1，记Pp为第p个没有被标记的字符，对于每一个没有标记的Pp；如果到下一个标记的距离≤s，将p指向下一个标记后的第一个没有被标记的字符；否则为子串Pp..Pp+s-1创造一个KR哈希值，并加入哈希表中；
[0165] 步骤S804：按顺序取出哈希表中的一次匹配，令k＝s；
[0166] 步骤S805：如果PP+K＝TT+K且PP+K没有被标记且TT+K没有被标记，k＝k+1，转到步骤S805；否则转到S806；
[0167] 步骤S806：如果k>2×s，返回k，结束；否则，记录最新的最大匹配；
[0168] 步骤S807：如果哈希表中还有匹配未取出，转到S804；
[0169] 步骤S808：返回最长的最大匹配的长度，结束。
[0170] 选择匹配创建标记的markstrings(s)过程具体如下：
[0171] 步骤S901：从最长的最大匹配组成的队列开始；
[0172] 步骤S902：如果当前队列为空，跳到下一个非空次长的队列；
[0173] 步骤S903：对队列中最长的长度为L的最大匹配，将匹配(p，t，L)从队列中移除；
[0174] 步骤S904：如果该匹配与之前的匹配没有交叉，标记匹配到的所有字符，即Tt..Tt+s-1和Pp..Pp+s-1，已标记字符长度＝已标记字符长度+L；否则如果L-Loccluded≥s，即匹配的长度与交叉的长度的差大于最小匹配长度，将匹配替换为匹配中未标记的部分。
[0175] 步骤S106：对经过相似度计算的源代码，按照其相似度大小是否大于阈值分为有无相似样本两类；若其具有相似样本，将该代码及其相似部分和抄袭关系归类到抄袭程序样本集A2中，如果不具有相似代码，将该代码归类到无显著相似性的程序样本集A1中；
[0176] 具体而言，步骤S106判断代码在样本集B中是否有相似样本的过程与步骤S104的过程基本相同。
[0177] 步骤S107：对于抄袭程序样本集A2中的每一个样本，提取步骤S105得到的相似部分，作为其抄袭证据，构建含证据的相似集A2。
[0178] 具体描述为：
[0179] 根据步骤S105使用RKR-GST算法得到的A2中的每一个样本和其有抄袭关系的样本集B的每一个样本之间的相似度和相似部分，提取其相似度和相似部分，并与两个代码样本一起加入含证据的相似集A2中。
[0180] 步骤S108：输出抄袭程序样本集A2(含抄袭关系及抄袭证据)和无显著相似性的程序样本集A1。
[0181] 具体描述为：根据相似度的大小，将原有的待检测样本集A划分为了抄袭程序样本集A2(含抄袭关系及抄袭证据)和无显著相似性的程序样本集A1，但并不能直接判定抄袭程序样本集A2中的源代码都具有抄袭行为；在实际的抄袭判定中，需要考虑到抄袭程序样本集A2中的源代码的相似部分是包含在基础模块还是功能模块之中，如果相似部分全部为通用模块，则判定不存在抄袭；如果其中存在至少一个功能模块相同，则可以认定存在抄袭。其中，通用模块是在开发过程会共同使用的模块，功能模块是开发方所原创的模块。
