代码查重系统MOSS与SIM小测

由于和毕设有些关系，于是找了两个常见的代码查重系统测试了下。

最早是在HUSTOJ的介绍里得知该OJ用SIM作为查重工具。还是词法级别的，唬住了当时什么都不懂的我，也没有去试着去测测这个相似性的边界到底在哪里，只是想着这么高级，肯定什么改变量名，改先后顺序，插入无效代码什么的都是无效的。并且在实践中确实挺不错的样子。

另一个比较有名的应该是MOSS，你看人家助教真的是赞赏有加，还是斯坦福大学出品，网页的标题都写着Plagiarism Detection了，而且还是有正经论文作为理论支撑的，无数加成之下，想必也是一个极为厉害的一个系统。

起先，我是准备直接相信SIM给出的相似度作为前提的，结果到底有多相似这一念头在心中始终萦绕，老师建议我先看一下SIM的实现，不建议我什么都想着从头开始自己搞。

在一番操作搞好Makefile使得源代码能够正常编译之后，看着自带的test结果给着也挺合理的，就去看源代码了。非常头疼的是，这个作者倒真的是什么都是自己实现的，给我的阅读带来了一定的困扰。可是细细一读，这玩意不对劲啊，用flex解析出Token流存到数组里面之后，就开始LCA了……，其他大多数的代码都是在提供各式各样的比较选项，并不会对结果造成多大的影响。

可这样岂不是很不妙，在光鲜的表面下并没有什么神奇的实现，那结果可以想象也不会神奇到哪里去了，于是着手构造样例测试，随便写了个从控制台读取n个数字并求和的简单程序作为被抄袭的样本，并逐步修改一点点。

sample1.c

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        int b;
        scanf("%d", &b);
        ans += b;
    }
    printf("%d\n", ans);
    return 0;
}

sample2.c(将ans更名为c)

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int c = 0;
    for(int i = 1; i <= n; ++i)
    {
        int b;
        scanf("%d", &b);
        c += b;
    }
    printf("%d\n", c);
    return 0;
}

sample3.c(将c的声明与n合并)

#include <stdio.h>

int main()
{
    int n, c = 0;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i)
    {
        int b;
        scanf("%d", &b);
        c += b;
    }
    printf("%d\n", c);
    return 0;
}

sample4.c(将c的初始化赋值放回到与sample1.c相同的位置)

#include <stdio.h>

int main()
{
    int n, c;
    scanf("%d", &n);
    c = 0;
    for(int i = 1; i <= n; ++i)
    {
        int b;
        scanf("%d", &b);
        c += b;
    }
    printf("%d\n", c);
    return 0;
}

sample5.c(将+=运算符拆成=和+)

#include <stdio.h>

int main()
{
    int n, c;
    scanf("%d", &n);
    c = 0;
    for(int i = 1; i <= n; ++i)
    {
        int b;
        scanf("%d", &b);
        c = c + b;
    }
    printf("%d\n", c);
    return 0;
}

sample6.c(全部变量重新命名)

#include <stdio.h>

int main()
{
    int a, b;
    scanf("%d", &a);
    b = 0;
    for(int c = 1; c <= a; ++c)
    {
        int d;
        scanf("%d", &d);
        b = b + d;
    }
    printf("%d\n", b);
    return 0;
}

SIM(Version: 2.89 Options: “-p”)的结果

SIM比较的选项相当多，但对结果数量级上并没有影响。

MOSS(Options: “-l c -m 10”)的结果

这里MOSS的表格少了几项，是因为在MOSS看来，剩下的几组被判定为No matches were found in your submission.

稍微对比一下就可以发现，两个系统给出的值都相当接近，想必而它们两者背后的实现也差不到哪里去。SIM判定相似度在50%以下的代码组，MOSS的评判标准下差不对就是直接当作完全摆除抄袭嫌疑的了。

那么情况就很糟糕了，我想作为任何一个一个会写点代码的人而言，这六个代码文件可以说是一模一样。而在我的曾经美好的预想里，这些应该都能被打出相当高的相似度。

但是这两个久经沙场的系统都给出了相近的结果，真的是很意外，在我看来，这更不拦不住想要抄袭的人，随随便便改一改，换换声明位置，连整体结构都不用变，就能逃过该系统的监察了。

那么，这个仅仅是很短的代码例子，那稍微长一点的呢？以一个约50行的代码来说，仅仅交换了两组&&运算符左右的值，就暴降至87%的相似度，甚至直接基于文本的相似度计算都能比这个高。

可以说，以Token流作为对比基础的算法，仅仅能对加减注释，变更缩进，简单变更变量名这类操作进行识别，因为这些操作几乎不对Token流产生影响。其他任意的操作，都会极大地影响其的判断，非常遗憾的是，这种敏感刚好就是我不期望出现的东西。

或许这就是所谓的一开始预期调得越高，到出结果就越失望么？

当然，有知乎大神似乎相当完美地解决了我现在所提出的问题，然而并没有开源，是吧。

另外还有个看起来非常有前途的论文，提供了AST、CFG、IR层级上的相似度比较，看起来与知乎上的那个思路相近，但是，也没有看到哪里有可用的实现，而完全实现这个，作为硕士论文也不为过吧，像我这种连编译原理都没学过的人，现时应该是没可能做到了的。