(OSDI'04 Note)CP-Miner: A Tool for Finding Copy-paste and Related Bugs in Operating System Code

Zhenmin Li et al

本文核心内容：使用数据挖掘技术来分析大型程序中可能存在的因为Copy-Paste产生的Bug。

Copy-Paster可能引起很多Bug，往往是因为没有修改Paste过去的代码中应该修改的地方。对这个问题，目前有一定的研究，但是存在几个问题：
1、分析的效率：对于大型程序，如Linux、数据库等，分析速度非常慢。
2、分析的智能性：目前的一些分析工具，只做到检验出哪里存在Copy-Paste的代码，而无法判断是否存在bug，需要人工分析。

本文为这两个问题作出了贡献：
1、使用数据挖掘技术，使得效率大大增加
2、使用了一定的算法，自动监测可能存在Bug的Pattern
另外，还有一点：
3、统计功能：分析出哪些模块使用Copy-Paste方法较多等等统计信息

实现的技术难点有两点：
1、如何判断代码属于Copy-Paste
2、如何判断Bug

对于第一点，目前大致有三种方法：
1) string-based: divided into strings (typically lines)
2) parse-tree-based: pattern matching on parse-tree and sub-tree
3) token-based: duplicate token sequences are identified
本文采用第三种方法，认为这是最精确的。

对于第二点，文章的思路比较简单：
对于两段被认为是Copy-Paste的代码中，分别找到不同的token的个数，然后看个数是否匹配。一般来说，如果第一段中token1出现了4次，而第二段中token2出现了3次，token1出现了1次，那么很有可能第二段中那个token1应该改成token2。
当然，也不能这么绝对，作者还有一个很简单的算法，即测量修改的和没有修改的比率，如上面的例子中就是0.25。然后对这个比率采用一个阀值，低于一定的阀值，就很有可能是Bug。

个人感觉：
这篇论文的思路很清晰，一个限制条件——针对大规模程序，一个创新点——自动分析Bug。呵呵，这也许是比较典型的论文吧。