代码相似度度量

注意事项

截止日期：2020 年 12 月 10 日 23:59:59 (以服务器时间为准); The deadline is firm.

提交方法：在命令行中 (请确保拥有 curl 命令) 执行 (将学号、姓名、路径替换为你的个人信息)

curl http://jyywiki.cn/upload -F course=ISER2020 -F module=PA1 -F stuid=学号 -F stuname=中文姓名 -F file=@待提交的文件路径

1. 背景

上大学的时候，大家可能多多少少都会抄一些代码。根据我们的研究，在某 985 大学的某个编程作业中，有多达 82% 的学生涉嫌抄袭，其中 53% 是相似度极大的直接拷贝。如果你是老师，你会怎么办呢？作为一个软件工程研究者，我们当然要用软件工程的办法解决啦！《软件工程研究入门》课程中介绍的静态程序分析技术就可以用来解决这个问题。

在这个实验里，让我们愉快地做一次恶人，通过对比代码的相似度来识别出可能的作业抄袭吧！

2. 实验描述

假设我们要对一些 Online Judge 上的编程作业进行相似度检测，尽可能地找出抄袭代码的嫌疑人。在本次实验中，我们假设 Online Judge 上的程序都是单个文件的 C++ 代码，能够通过 gcc 或 clang 在 -std=c++11 (C++ 11 标准) 和 -pedantic (拒绝不符合标准的程序) 选项下的编译。

你可以用任何你熟悉的主流编程语言 (C/C++/Java/Python/JavaScript/Scala/Rust/Go/...) 实现一个 Linux 下运行的命令行工具 codesim，用于比较两个 C++ 语言程序的相似性。在命令行中运行 codesim，传入两个程序的文件名作为参数，输出一行一个浮点数百分比，代表代码的相似性。百分比不需要有确切的含义，只需尽可能使实际为抄袭的代码获得更高的相似度即可。

$ codesim --help
usage: codesim [-v|--verbose] [-h|--help] code1 code2
$ codesim foo.cc bar.cpp
99.3

我们希望你编写一个用户友好的命令行工具：

1. 遵循命令行工具的基本规范。例如，你的命令行工具可能被其他脚本调用，因此请不要在标准输出中打印额外的信息 (如日志)。出错时，请将错误信息输出到标准错误输出 (stderr) 并返回错误 exit code。一个更好的 practice 是提供 -v 或 --verbose 选项，在 verbose 模式下打印更多的信息，这也可以帮助你调试。
2. 不要在当前目录产生多余的临时文件。Linux 系统提供了 mktemp 系列函数，每个主流编程语言都有相应的 API。
3. 不要产生多余的输出。你的工具可能被其他工具联合使用，因此请确保 stdout 仅输出一行相似度百分比。如遇出错的情形，可以不输出，但也请遵循命令行工具的规范，将错误信息输出到 stderr，并返回非 0 的 return code。

我们希望大家设计/选择合适的算法，基于适当的工具实现 codesim。分析 C++ 的主流工具是 clang；或者可以使用编译器编译后，对二进制代码进行分析。现代编程语言异常复杂，简单的手工实现几乎是不现实的——因此要尽量避免重复制造轮子，在已有项目的基础上实现你的算法。

如何看待已有的工作？

代码相似度/抄袭检测并不是一个新问题。我们鼓励大家查阅一些已有的文献：软件 (甚至是开源社区) 中的 copy-paste 行为是导致低质量代码传播和降低软件可维护性的重要原因。甚至，针对代码抄袭也有专门的检测方法，例如非常著名的 MOSS。我们鼓励大家能消化吸收论文里的方法，提出自己的想法，而不是照着论文的方式进行原本的实现。

3. 实验提交

将以下内容打成压缩包 (zip 或 tar) 上传：

• 工具的源代码 (仅包含源代码。请确保你源代码依赖的库函数是容易获得的；请不要将依赖、二进制文件等能够被源码生成的文件打在压缩包中——它们可能会导致你的提交超过大小限制)。
• 简短的编译说明，包括依赖的库如何获取。
• pdf 格式的实验报告，简述你实现代码相似度检的算法和关键的实现技巧。请你简要地描述你的算法。实验报告不宜超过 2 页 A4 篇幅。

本实验是开放的实验，没有绝对客观的评判标准。我们会用你的工具在一组程序上进行相似度两两比较，并按照相似度进行排序，与一些我们已知的代码抄袭事实进行比对。

4. Artifact

为了更好地促进后续的研究工作，将研究工作的代码以开源项目的形式发布是非常必要的。因此，在这门课程中，我们要求你选一个 programming assignment (codesim 或 jmtrace)，并按照开源软件的通常标准维护。对于 artifact 来说，你要尽最大的可能为这份代码负责，因为未来其他研究者可能会基于你的代码开展其他研究工作。

特别注意：Artifact 准备是二选一的。你只需要提交一份 artifact 供 peer-review。你可以任选是 PA1 (codesim) 或是 PA2 (jmtrace) 作为 artifact。关于如何准备 Artifact 请参考 Artifact 准备指南。