基于代码相似度的隐含学生行为模式挖掘

摘 要：针对学生在编程中出现的代码拷贝问题，提出用一种改进的分段最长公共子序列匹配算法分析代码相似度，进一步挖掘隐藏在相似代码背后的学生之间合作关系以及行为模式，对于如何了解、干预和避免学生抄袭行为的扩散以及正确评价学生的编程能力进行积极有益的探索。

关键词：代码相似度；行为模式挖掘；合作关系挖掘；LCS（大于3个，小于8个）

0 引 言

计算机编程类课程一直以来面临一个难以解决的问题――代码拷贝问题，该问题严重影响教师对于教学中学生程序设计能力和编程实践水平的评估，进而影响教师有效针对学生编程情况的一系列教学设计。随着计算机科学在人工智能、程序理解等领域的发展，各种代码相似度检测的方法相继提出，如基于Token比较的方法[1]、基于文本检测的方法[2]、基于语法树[3]的方法、基于依赖关系图的方法[4]等，这些方法在检测类型、时间复杂度等方面都存在不同程度的局限性[5]。因此，我们提出一种针对轻量级代码检测的可忽略间隙的分段最长公共子序列（gapped and segmented longest common sequence， GS-LCS）算法，该方法考虑了学生代码拷贝的习惯，能有效检测代码的相似度。

1 代码相似度检测

计算机教学中代码算法复杂度及代码长度相对有限，对于同一题目会有大量学生进行算法设计和编程。学生常用的10种抄袭手段包括逐字拷贝、更改注释语句、更改空白区域、重新命名标识符、改变代码块的顺序、改变代码块中语句的顺序、改变表达式中操作符和操作数的顺序、更改数据类型控制逻辑、增加冗余的语句和变量、用等价的控制结构替换原有控制结构[6]。我们通过分析学生代码，发现其中较为高级的代码拷贝形式“用等价的控制结构替换原有控制结构”应该不属于抄袭。基于上述分析，我们提出的GS-LCS算法步骤如图1所示。

1.1 预处理、标准化、Hash

代码相似度检测流程中的预处理、标准化、Hash 3个步骤将源代码转换为Hash数字序列，进行CS-LCS算法的匹配，如图2所示。

（1）预处理：用于去掉注释、空白，并将代码按照预定义的分隔符如“；”“{”、“}”等分割成独立的表达式；

（2）标准化：用于将其中的标识符包括常量、变量、函数名等，替换成统一的符号“$”，关键字、操作符保持不变；

（3）Hash：用来将每一个独立的表达式进行唯一的编码。

1.2 GS-LCS算法

Hash编码后，对于源代码的匹配就转换成对于数字序列的匹配。GS-LCS算法中，针对学生在代码拷贝中可能增加、删除或改变部分表达式，采用忽略间隙策略进行匹配；对于代码块的顺序改变、代码块中表达式的顺序，则采用分段策略进行匹配。GS-LCS算法的基本思想如图3所示。

GS-LCS算法对源代码进行两两比较，若源代码A生成的Hash序列为（a1，a2，…， aN），源代码B生成的Hash序列（b1，b2，…， bM），则GS-LCS算法按照如下步骤进行。

步骤1：初始化T为（N+1）×（M+1）的矩阵，其中第一行和第一列置0；

步骤2：按照公式1对序列a和b进行逐行匹配，生成矩阵T；

步骤3：分段回溯，从矩阵T [M，N]开始从右至左、从下至上遍历，若两个相似Hash值间隔在[0，θ1]范围内（θ1为预先设置的可忽略间隙距离），视为一个相似子序列，如图3所示相似子序列1。回溯算法每调用一次找到一个子序列，回溯算法具体如下：

步骤4：更新矩阵，即将已匹配的序列所在行全部置0，反复调用回溯算法找出所有相似子序列li，注意相似子序列长度>1。

经过优化，GS-LCS算法的时间复杂度为O（M*N）。

1.3 计算相似度

根据GS-LCS算法可以得到任意两个源文件的所有相似Hash子序列L={l1，l2…lk}，因此我根据公式（2）计算相似度，其中M， N分别为待比较文件a和b的有效独立表达式总数。

（2）

2 实验分析

我们随机抽取3个班6个作业题目进行测试和验证，3个班每班人数分别为20、22和21；实验中我们设置的忽略间隙θ1=2，根据题目的难易、算法的多样性、代码量等，用半监督的方式为每一个题目设置3种不同的相似度阈值θ2={0.75，0.8，0.85}，见表1，若sim（a，b）≥θ2，则认为文件a和b为拷贝。

2.1 作业相似度分析

根据表1的设置，我们对3个班的6份作业进行相似度两两比较，算法准确率和召回率见表2。

可以看出，题目1（约瑟夫环）的准确率和召回率最高，主要是由于其解题方法较为多样化，相似代码较为集中；题目4（排序）的准确率和召回率都较差，主要是由于该作业实现7个不同的排序算法，每个算法代码量较小，解题方法较单一；题目6（图）准确率较高，但召回率较差，因为该题目中涉及的部分算法如最短路径、最小生成树等比较难，解题思路较为一致，其他算法具有一定的多样性分布。

2.2 学生拷贝行为分析

根据相似度分析，我们对每一个学生在6次作业中出现的拷贝行为次数进行统计，统计结果如图4所示，可以看出一班的拷贝行为最轻，二班其次，三班最为严重。

其次，我们对每个题目的代码相似分布进行分析，如图5所示。相似代码对代表学生之间的拷贝关系，从中我们可以看出班内代码拷贝现象远远多于班级之间，代码拷贝趋向于小组协作模式，即每个班内容易形成3～5个同学的子集团进行合作拷贝，并且相似代码的编号较连续，说明相邻的学生趋向于形成拷贝小组的可能性更大。

最后，我们对相似代码对进行统计，在6次作业中超过3次相似度大于阈值的代码对，则认为是稳定拷贝合作关系，我们可以得到图6所示的合作关系图，可以发现，班级内部存在{15-20，12-18，10-11，29-30}4个稳定合作对，存在{24，28，32，34}， {31，35，36，37，38，39，40}，{56，58，62，63}3个稳定拷贝协作组以及{44，46，48，54，55，59}1个拷贝合作链；班级之间仅有4和57两个节点具有稳定拷贝关系，因此教学中只需要重点关注班内稳定合作关系，即可有效避免代码过度拷贝及扩散。

3 结 语

GS-LCS算法能够有效地检测存在于学生作业和实验中的代码拷贝，因此计算机程序设计类课程中的学生代码拷贝行为，尤其是学生之间的拷贝写作依赖行为，可以通过代码相似度的计算来发现、评估和监管，从而有助于教师更好地了解学生的真实编程水平，有效设计教学内容，促进课程良性发展。

参考文献：

[1] Kamiya T， Kusumoto S， Inoue K. CCFinder： A multilinguistic token-based code clone detection system for large scale source code[J].IEEE Transactions on Software Engineering， 2002， 28（7）： 654-670.

[2] Schleimer S， Wilkerson D S， Aiken A. Winnowing： Local algorithms for document fingerprinting[C]//Proceedings of the 2003 ACM SIGMOD international conference on Management of data. New York： ACM， 2003： 76-85.

[3] Koschke R， Falke R， Frenzel P. Clone detection using abstract syntax suffix trees[C]//13th Working Conference on Reverse Engineering. Washington D C： IEEE， 2006： 253-262.

[4] Higo Y， Yasushi U， Nishino M， et al. Incremental code clone detection：A pdg-based approach[C]//18th Working Conference on Reverse Engineering. Washington D C： IEEE， 2011： 3-12.

[5] Roy C K， Cordy J R. A survey on software clone detection research[R]. Kingston： School of Computing， Queen’s University， 2007.

[6] Jones E L. Metrics based plagarism monitoring[J]. Journal of Computing Sciences in Colleges， 2001， 16（4）： 253-261.

（辑：宋文婷）