通过挖掘关联规则探索代码修改和错误修复之间的关系

郑 芹

(福建信息职业技术学院，福建 福州 350003)

通过挖掘关联规则探索代码修改和错误修复之间的关系

郑 芹

(福建信息职业技术学院，福建 福州 350003)

本文通过分析各种不同的软件项目中产生的源代码修改记录，探索代码修改和错误修复之间的关系来更好地理解代码修改之间的关联并挖掘它们之间的关联规则，从而得到代码修改和错误修复之间的因果关系，找出修复错误的方法以更好地降低代码修改所引起的错误。

关联规则；错误修复；代码修改；数据挖掘

代码修改是软件项目生命周期中一个重要的活动，特别是普遍地出现于软件项目的演化模型和敏捷软件开发过程中，现在也逐渐广泛应用于大型的软件工程项目中。代码修改在提高软件项目的质量上扮演了一个重要的角色，特别是在代码的可理解性、可重用性和效率上。然而，代码修改也经常引发错误，为了改正这些错误而进行代码修改引发了更多的错误。因此，锁定那些必须修复的特定错误既费时又费力：开发者经常花费相当大量的时间查找和运行不同的软件版本以确认错误所在的版本。本文的焦点就在于如何应用合适的技术来找出错误修复和代码修改之间的关系。例如，在错误修复中所涉及到的特征值（如文件、函数和变量），可以自动从软件项目中去除这些特征值或自动进行重命名。

一、方法

本文中的方法采用了数据挖掘的观点，基于Apriori算法应用关联规则挖掘，利用WEKA[1]作为规则产生和数据分析的方法。方法由以下步骤组成：

1.预先找了50个最活跃的用.net编写的开放源代码 （OSS）工程，有代表性地在并行版本库系统（CVS）或（SVN）库中调查他们的修改记录；在SVN库中收集数据比CVS库中简单，因为在SVN库中能够直接获取修改日志，而在CVS库中，需要先经过整个库的检查，然后才能获取修改日志。[2]

2.把整个修改记录作为购物篮，当对代码进行增加新特性、删除原有特性、程序重组、更新废弃代码等结构性的修改工作时，仅仅针对代码的内部结构，并不影响如程序实体的重命名、程序实体的移动、可视性的改变、数据类型的改变等代码所实现的功能和项目整体的性能的变化。这些代码的修改，是以关键字的形式在修改记录中显示的。再抽取了11个这类关键字来定义市场篮中的项目，它们是：rename,move,replace, revamp, update, merge, split,remove,delete,add,和new；

3.将代码修改及与之相联系的错误修复在一组事物处理中分类，以fix关键字表示；

4.发掘用于生成规则的那些事物处理，它们描述了各类代码修改间的相互关系以及错误修复与这些代码更改间的关系，如：“系统增加新功能时，需要重组软件结构”、“系统增加新功能时一般会引入新错误，要及时修改”，即为此类事物处理。

5.WEKA所处理的数据集是一个二维的表格，它能够通过对该二维表格的数据进行分析，从中提取出属性之间的关系。但由于WEKA处理的数据格式是ARFF格式，因此需要编写脚本先把原始数据转换成ARFF格式，方可用WEKA包对其进行下一步的挖掘。

二、规则

使用演绎算法来发现关系规则。在给定的、包括与修改相关的关键字的事务中，演绎算法找出支持度不小于最小支持度minsup，置信度不小于最小置信度minconf的所有规则。[3]这样，就把问题分解成两个子任务：

（一）、候选项生成（常见的项目集）

演绎算法首创了利用基于支持度的调整方法，该方法系统地控制了候选项成指数地增长。[4]

首先构造一个项目集晶格结构，其中列举所有可能的项目集，[5]如图1所示。一个项目集晶格表示一个包含revamp,move,add,rename,new项的项目集，如同在市场上所能够买到的物品的列表。表1是一个市场篮事务集，其minsup=30%。

图中的字母分别表示：

A=revamp,B=move,C=add,D=rename,E=new F=常见候选项目集,I=罕见项目集,N=非候选项目集。

演绎算法每次扫描一行晶格，通过原先的循环，在原先的常见K-1项项目集的基础上产生新的K项候选项目集，这样就消除了支持度小于minsup的所有候选项目集，从而产生了项目集F。演绎算法确保所有的罕见项目集均为不常见的，如图1中标记A、C的项目集。表1是一个市场篮事务的示例。

表1 市场篮事务示例

（二）、规则生成

演绎算法采用基于置信度的调整方法，从F集中计算关系规则。由每个常见项目集·I ∈F计算出→X,其中X是I的一个子集。注意：所计算出所有规则的支持度相同而置信度不同，而只有置信度满足最小置信度阈值要求的规则才能返回。

下图2显示的是一个由常见项目集 {revamp,rename,new}生成的关系规则晶格。演绎算法确保每个晶格节点都满足minconf阈值的要求，否则，其下延伸的子图将被立刻消除。所有结论中包含{new}的规制，包括{revamp}→ {rename,new}及{rename}→ {revamp,new}，都将被丢弃。

图2 关系规则晶格

通过WEKA，由ARFF文件生成的关系规则表示为如下形式：

revamp remove add==>move merge new conf:(0.97)lift:(1.01)

lev:(0.01)[66]

这些是后处理过的规则，它们经过grep,sort,u-niq,sed,and awk等UNIX的字符串处理工具处理后加入到CVS文件中，由制表软件转化为图形，显示相关数据。

三、方法实现

问题的具体实现步骤及相关代码如下：

（一）从SourceForge.net中最活跃的50个OSS项目的CVS和SVN库中收集修改记录，这些项目按照修改日志的输入次序编号。以下是具体的代码。

代码运行后得到的修改记录如表2所示。将表2用图形化表示，即生成图3。

表2 OSS库修改记录的提交次数

图3 OSS库修改记录的提交次数的图形化表示

（二）从项目的SVN库中为WEKA输入提交日志数据。这里，@RELATION用于命名输入的数据集，@ATTTRIBUTE命名数据集中栏目的名称和各自取值，@DATA指明以CSV格式输入的数据的起始位。0表示不存在，1表示存在。相关代码如下：

（三）将提交日志转变为ARFF格式。一般如果一个程序更改会导致40%的程序错误，那么这个更改就值得注意，因此最小置信度设置为40%；与此类似，将置信度设置为90%。将这两个参数提供给WEKA。

下面是是ARFF相关通用代码的目录。KEYWORD语句确定一个通用表达式，该表达式检查一个提交是否包含值得感兴趣的关键字。

（四）将CVS格式的提交日志转化为WEKA能识别的ARFF格式数据。

（五）将SVN格式的提交日志转化为WEKA能够识别的ARFF格式数据。

（六）将Darcs格式提交日志转化为WEKA能够识别的ARFF格式数据。

（七）通过WEKA运行ARFF文件。

四、结论

经过以上方法的实现，可以得到最常见的规则，如表3所示。其中revamp→ rename规则是所输入的数据集中最突出的一个。这表明，在OSS项目的revamp过程中，大部分工作都包含rename。在其中大部分的关系规则都是有指导意义的。如split→rename规则，由于在将文件或是函数分割成两个部分时，必须分别给每个部分一个新名字，因此，此规则非常有用。

表3：所有项目中最常见的关系规则

另外，这种方法还有一个突出的结果，即具备纠错能力的关系规则很少见（发生次数少于5次）。不具备这种功能的方法，由于其规则几乎将代码更改都联系在一起，因而显得非常繁杂，这样，这些方法得出的规则除了告诉纠错似乎包括了所有形式的代码更改，具有纠错能力的关系规则如表4所示。

表4：具备纠错功能的关系规则

因而发现，与纠错相关的关系规则的数量比仅包含代码更改的关系规则的数量少，这表明，在OSS项目研究中，用于增加、更新、优化源代码的工作量高于用于程序纠错，特别是重构（即revamping）的工作量。

[1]毛国君.数据挖掘原理与算法（第二版）.清华大学出版社.2007：50-120.

[2]西蒙（K.P.Soman）,范明（译者），牛常勇（译者）.数据挖掘基础教程.机械工业出版社.2009.

[3]S.Kim,T.Zimmermann,K.Pan,and E.J.Whitehead Jr.,Automatic Identification of Bug-Introducing Changes,in Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering,September 2006:81-90.

[4]Z.Xing and E.Stroulia,Refactoring Practice:How it is and How it Should be Supported-An Eclipse Case Study,22nd IEEE International Conference on Software Maintenance(ICSM06),2006.

[5]S.Kim,K.Pan,and E.J.WhiteheadJr.,When Functions Change Their Names:Automatic Detection of Origin Relationships,in Proceedings of the 12th Working Conference on Reverse Engineering,2005:143-152.

Exploring Relationships Between Bug Fixes and Code Changes Through Assiciation Rule M ining

ZHENGQin

（Fujian Information and Technology College，Fuzhou，Fujian 350003）

We explore the relationships between bug fixes and several kinds of source code changes to better understand how source code changes are interrelated,and how they correlate with bug fixes,and what kinds of source code changes imply higher causality of bugs and thereby necessitate bug fixing.We explore these topics by mining association rules from the source code change histories of various software projects,as such rules can suggest and predict likely future changes and guide programmers to locate bugsmore easily among committed changes.

association rules；bug fixes；code changes；datamining

TP311.5

A

1674－2109(2011)05－0019－06

2011-08-11

郑芹（1969-），女，汉族，讲师，主要研究方向：计算机软件技术和多媒体信息处理。