计算机应用   2017, Vol. 37 Issue (4): 1135-1142,1163  DOI: 10.11772/j.issn.1001-9081.2017.04.1135
0

引用本文 

王欢, 张丽萍, 闫盛, 刘东升. 克隆代码有害性预测中的特征选择模型[J]. 计算机应用, 2017, 37(4): 1135-1142,1163.DOI: 10.11772/j.issn.1001-9081.2017.04.1135.
WANG Huan, ZHANG Liping, YAN Sheng, LIU Dongsheng. Feature selection model for harmfulness prediction of clone code[J]. Journal of Computer Applications, 2017, 37(4): 1135-1142,1163. DOI: 10.11772/j.issn.1001-9081.2017.04.1135.

基金项目

国家自然科学基金资助项目(61363017,61462071);内蒙古自治区自然科学基金资助项目(2014MS0613,2015MS0606)

通讯作者

张丽萍 (1974-), 女, 内蒙古呼和浩特人, 教授, 博士, CCF会员, 主要研究方向:软件工程、软件分析, E-mail:cieczlp@imnu.edu.cn

作者简介

王欢 (1991-), 男, 内蒙古巴彦淖尔人, 硕士研究生, 主要研究方向:代码分析;
闫盛 (1984-), 男, 内蒙古包头人, 讲师, 硕士, 主要研究方向:软件分析、并行计算;
刘东升 (1956-), 男, 内蒙古呼和浩特人, 教授, 主要研究方向:软件分析、计算机教育

文章历史

收稿日期:2016-08-24
修回日期:2016-09-30
克隆代码有害性预测中的特征选择模型
王欢, 张丽萍, 闫盛, 刘东升    
内蒙古师范大学 计算机与信息工程学院, 呼和浩特 010022
摘要: 为解决克隆代码有害性预测过程中特征无关与特征冗余的问题,提出一种基于相关程度和影响程度的克隆代码有害性特征选择组合模型。首先,利用信息增益率对特征数据进行相关性的初步排序;然后,保留相关性排名较高的特征并去除其他无关特征,减小特征的搜索空间;接着,采用基于朴素贝叶斯等六种分类器分别与封装型序列浮动前向选择算法结合来确定最优特征子集。最后对不同的特征选择方法进行对比分析,将各种方法在不同选择准则上的优势加以利用,对特征数据进行分析、筛选和优化。实验结果表明,与未进行特征选择之前对比发现有害性预测准确率提高15.2~34个百分点以上;与其他特征选择方法比较,该方法在F1测度上提高1.1~10.1个百分点,在AUC指标上提升达到0.7~22.1个百分点,能极大地提高有害性预测模型的准确度。
关键词: 克隆代码    有害性预测    特征子集    信息增益率    特征选择    
Feature selection model for harmfulness prediction of clone code
WANG Huan, ZHANG Liping, YAN Sheng, LIU Dongsheng     
College of Computer and Information Engineering, Inner Mongolia Normal University, Hohhot Nei Mongol 010022, China
Abstract: To solve the problem of irrelevant and redundant features in harmfulness prediction of clone code, a combination model for harmfulness feature selection of code clone was proposed based on relevance and influence. Firstly, a preliminary sorting for the correlation of feature data was proceeded by the information gain ratio, then the features with high correlation was preserved and other irrelevant features were removed to reduce the search space of features. Next, the optimal feature subset was determined by using the wrapper sequential floating forward selection algorithm combined with six kinds of classifiers including Naive Bayes and so on. Finally, the different feature selection methods were analyzed, and feature data was analyzed, filtered and optimized by using the advantages of various methods in different selection critera. Experimental results show that the prediction accuracy is increased by15.2-34 percentage pointsafter feature selection; and compared with other feature selection methods, F1-measure of this method is increased by 1.1-10.1 percentage points, and AUC measure is increased by 0.7-22.1 percentage points. As a result, this method can greatly improve the accuracy of harmfulness prediction model.
Key words: clone code    harmfulness prediction    feature subset    information gain ratio    feature selection    
0 引言

克隆代码 (Clone Code) 是源代码的一段拷贝或者重用, 在软件实践开发中是一种非常普遍的现象[1]。由于克隆代码对代码质量的重要影响, 克隆代码相关研究是代码分析领域近年来一个非常活跃的研究分支[2]。在发布软件正式版本之前, 提前找出隐含的有害克隆代码, 并反馈给开发维护人员,以便于他们及时修正由克隆引起的错误, 提高代码质量削减维护费用, 增强软件的可理解性和可靠性。而在有害性预测过程中, 选择克隆代码有害性特征的优劣决定了整个预测过程的效果。

目前, 研究人员已经进行了克隆代码有害性预测的探索[3-6], 已有从不同角度的多种特征度量被提出, 并用于克隆代码有害性自动预测研究中。但是对于不同的特征以及特征之间的影响关系缺乏较为全面的分析。例如, 其中可能存在不相关和相互依赖的特征, 导致训练模型所需的时间加长, 模型较复杂并且学习效果也会下降。因此, 如果能对克隆代码特征之间的相关程度和冗余程度进行更全面的分析, 对表征有害性的特征进行优化与评估, 将有利于提高克隆代码有害性预测的性能与效果。

本文以解决克隆代码中特征无关与特征冗余的问题, 提高有害性预测性能为目标,将基于机器学习的自然语言处理中特征选择方法引入克隆代码有害性特征选择当中, 从特征数据自身的相关性以及对预测结果的影响程度两个角度出发, 基于信息增益率 (Information Gain Ratio, IGR) 和序列浮动前向选择模型 (Sequential Floating Forward Selection Model, SFFSM), 提出一种混合式克隆代码有害性特征选择模型——IGR-SFFSM。实验结果表明本文方法能有效降低特征选择对有害性预测的影响:一方面, 该方法在时间效率和准确度方面表现更优, 从而能达到优化特征空间, 提高有害性预测准确度的目的;另一方面, 选择出4~5个真正相关的特征简化了模型, 使研究者更容易理解数据产生的过程。

1 相关工作 1.1 克隆代码有害性定义

目前, 对于克隆代码的有害性界定非常模糊, 相关的有害性预测研究中, 也没有一个标准的有害性界定范围,因此, 关于克隆代码有害性方面的研究相对较少。

Wang等[3]通过收集克隆代码的属性特征及要粘贴的目标区域的上下文特征进行学习, 预测克隆操作的有害性。李智超[4]基于机器学习中有监督学习方法支持向量机进行了克隆代码有害性评价方法的研究。该研究认为“一致变化”的代码是有害的, 而国外大多数研究者们则认为“不一致变化”才是引起程序出错的主要原因。例如Inoue等[7]研究发现通过检测手机软件中克隆代码的不一致变化能有效地找出软件中潜伏的bug。Juergens等[8]对四个系统的研究结果进行报告, 发现克隆代码中52%会发生不一致变化, 28%的不一致变化被无意地引入, 15%的不一致变化会引入错误, 50%的无意不一致变化会导致程序错误。该研究同时也表明, 几乎任何对克隆代码不经意的不一致修改, 都可能会隐藏着一个bug。德国的Steidl等[9]使用机器学习领域的决策树自动识别软件的bug, 他们认为无意的不一致修改是导致有害克隆的原因。国内外的大量研究都认为克隆代码不一致变化非常频繁并且大量的程序错误都是由这种不一致变化引起的。

图 1是不一致的bug修复引发错误的例子, 代码1和代码2已经被检测出是一对克隆代码。从图 1可以看出, 第一对克隆代码 (#1) 中, 代码1的代码片段中strncmp接收三个参数, 而代码2的片段中strcmp只接收两个参数。明显在#1代码2中存在一个逻辑错误。第二对克隆代码 (#2) 在变量命名上发生了不一致变化, #2左边代码中if条件对l_stride进行了空判断, 右边代码确并没有对r_stride进行一个空值的检测并且已经被GCC开发人员证实是一个需要快速修复的bug。

图 1 不一致的bug修复引发错误 Figure 1 Faults caused by inconsistent bug fixes

不一致变化是指克隆类中的某个克隆片段发生了和其他片段不一样的变化。不一致性检验是将源代码转换成Token表示形式, 再利用最长公共子序列算法计算两段克隆代码Token序列之间的相似程度。算法实质就是基于文本的字符匹配算法与一般的基于字符对比算法的区别是能够不受字符重命名、数据类型不同以及程序语言不同的影响。

结构化的不一致问题属于克隆代码领域中的Type-4类型, 而Type-4克隆代码则为功能相似或相同, 但句法结构不同的代码段, 目前国内外对Type-4克隆代码检测的研究仅处于探索阶段, 无法获取, 因此结构化不一致问题不作为本文研究内容。

最终本文将发生不一致变化的克隆代码标注为有害克隆代码, 如果克隆群经历了至少一次不一致变化, 本文就认为这种克隆操作是有害的。如果克隆群经历无变化或者一致性修改变化, 本文认为这种克隆操作就是无害的。对克隆代码进行修改时, 需要对克隆群内所有克隆代码作一致性修改, 而遗漏群内任何代码的一致性修改操作都会导致克隆群中发生不一致改变, 这会导致程序出现错误, 进而给软件系统带来隐含的bug。

1.2 特征选择

特征选择作为机器学习和模式识别领域中非常重要的数据预处理技术, 在有害性预测中扮演着重要角色。而特征选择的焦点是如何从输入数据中选择一个变量的子集, 使这个子集能在有效描述输入数据特性的同时也能减少一些不相关变量的噪声干扰, 最终达到提高预测结果准确的目的[10]

评价标准在特征选择过程中也扮演着重要的角色, 它是特征选择的依据。评价标准可以分为两种:一种是用于单独地衡量每个特征的预测能力的评价标准, 用来衡量每个特征与输出类别标签之间的相关性; 另一种是用于评价某个特征子集整体预测性能的标准。根据特征子集选择过程中是否依赖于后续的学习分类方法来评价, 可以将其具体分为过滤式 (Filter) 方法[11]和封装型 (Wrapper) 方法[12]共两大类。

Filter方法是采用一些基于信息统计的启发式准则来评价特征的预测能力。例如, Guyon等[10]提出采用相关系数对特征进行排序。该研究对特征数据进行预处理, 过滤掉排名等级较低的特征变量, 最终把相关程度高的特征提供给机器学习模型使用, 从而提高预测的效果。Menzies等[13]使用信息增益对特征进行排序, 他们的结论发现使用前3个特征和使用全部特征的预测效果相差无几。目前用得最多的评价准则有相关系数法、类间与类内距离测量法、信息熵法、信息增益率、一致性、Relief等。

Wrapper方法是根据一些搜索策略来选择特征子集, 并测试它在分类器上的性能表现来决定特征子集的优劣。当前搜索特征子集的算法分为完全搜索、启发式搜索、随机搜索三大类。常用的搜索算法有基于深度优先局部择优的爬山算法、最好优先算法、基于枚举加剪枝的分支限界搜索和遗传算法等。当前有K近邻、随机森林、神经网络、支持向量机等作为分类器。Kohavi等[14]使用启发式特征选择方法爬山算法, 通过分析大类训练结果来启发式的重新组合特征, 最终找到结果最好的特征子集。Janecek等[15]使用贪心加回溯的最好优先算法, 搜索出最好的属性空间子集, 在特征减少90%以上的情况下, 六种学习算法平均预测性能几乎保持不变。

通过对上述方法的总结与分析可以发现:Filter方法独立于后续的分类方法并且避免了Wrapper方法交叉验证的过程,所以它是一种计算效率较高的方法且不依赖具体的学习算法来评价特征子集。但其主要问题是当特征和分类器关联较大时, 不一定找到规模较小的最优特征子集。例如Relief中的相关性方法使用朴素贝叶斯作为特征子集选择器就不合适, 因为在大多数情况下朴素贝叶斯提高表现是伴随着相关特征的移除[10]。虽然Wrapper方法的效率不及Filter, 但该方法使用一个预定义的分类器来评估特征质量并有效避免了特征选择时依赖具体分类方法的缺点, 同时所选的优化特征子集的规模相对要小一些。然而, 这种方法需要多次运行分类器来评估选择的特征子集, 所以计算开销较高。

因此, 本文方法与上述方法主要不同之处有以下三点:

1) 大多数基于机器学习的克隆代码有害性特征的选择都依赖于研究者或开发者的经验。而本文提出了一种有害性特征选择的理论模型, 此模型以特征相关程度和模型预测的结果分析为依据选择特征数据, 为克隆代码有害性预测方面的研究提供了更加科学和客观的数据支持。

2) 将特征选择方法引入克隆代码有害性预测研究当中, 利用Filter方法计算开销较小以及Wrapper方法与分类器模型交互的优点, 提出一种折中的方法, 用前者作为分类的预选器, 后者在预选特征集上作进一步的特征精选。实验中采用信息增益率和序列浮动前向选择算法确定最优特征子集。通过训练特征数据集选择前后的预测表现进行评估, 发现准确率、F1测量和AUC都有明显提升, 证明了该方法的可行性。

3) 将基于机器学习的自然语言处理中特征选择方法引入克隆代码有害性特征选择当中, 利用一般特征选择方法处理形式化语言高效、准确的优势, 针对克隆代码有害性特征数量多且不容易提取, 质量粗糙的问题, 提出一种有效的优化特征子集的方法, 进而提高学习模型的性能。

2 IGR-SFFSM方法

本文提出的用于预测有害克隆代码的组合特征选择方法框架如图 2所示。在既有的克隆检测、克隆家系和克隆有害性预测的研究基础上, 针对克隆代码有害性预测过程中特征选择这一核心问题展开深入研究。结合克隆代码本身的静态信息和克隆演化信息, 提出两大类有害性特征指标即静态特征和演化特征。然后, 进行有害性标注, 由此形成原始特征数据集。在此基础上, 使用组合特征选择方法构建特征选择模型。首先通过信息增益率计算特征之间的相关程度, 获得特征相关性排名结果, 过滤掉相关程度较低的特征。然后利用序列浮动前向选择算法对初步筛选出来的特征进行最优特征子集的搜索。最后采用基本模型和集成模型两大类分类器作为克隆代码有害性评价的测试模型, 将筛选出来的特征子集输入模型进行影响程度的循环测试, 找到对预测结果影响程度最高的特征子集。

图 2 IGR-SFFSM模型框架 Figure 2 IGR-SFFSM model framework
2.1 特征评估指标——信息增益率

IGR-SFFSM方法使用信息论中的信息增益率来衡量每个特征给分类过程中所带来的信息量大小。若特征信息增益率越大, 则说明该特征与分类标签之间的相关性越大, 即特征区分所有类的能力越强。因此, 在进行属性选择的过程中, 通常选择信息增益率大的特征作为分类的依据。

设训练集S={S1, S2, …, Sn}, 其中Si包含一个属性向量Xi=(x1, x2, …, xp) 及分类标签Li∈={L1, L2, …, Lm}。在预测中XiLi分别代表一个样本数据的属性和该样本是否存在有害克隆的标记。设piS中属于类别Li的比例, 则信息熵的计算方法如式 (1) 所示:

$ Entropy(S) = - \sum\limits_i^m {{p_i}} *{\rm lb }{p_i} $ (1)

每个属性可以有多个不同的取值, 假设Values(A) 是属性A中取不同值的集合, Sv指集合S中的所有属性A取值为v的集合, 则式 (2) 表示基于按A划分后对S集合准确分类还需要的信息量。

$ Entropy(S,A) = \sum\limits_{v \in Values(A)} {\frac{{|{S_v}|}}{{|S|}}} Entropy({S_v}) $ (2)

定义IG(A) 表示属性A的信息增益, 式 (3) 是未进行特征选择划分之前的数据熵与按照属性A划分之后数据熵的差值:

$ IG(A) = Entropy(S) - Entropy(S,A) $ (3)

如果SA是相互独立的, IG(A) 将会是0;如果大于0说明它们是相互依赖的。这个算法就是在针对特征数据划分前后信息储量发生的变化, 这种变化称为信息增益。计算出特征数据的信息增益, 可以描述每个特征独立提供信息的能力。一般情况下, 信息增益最高的特征就是最好的特征选择。

由于克隆代码有害性特征数据的离散性质, 仅考虑信息增益的值进行特征选择, 很可能会导致过度拟合。此外, 信息增益作为分类选择标准也存在不足之处,即易偏向于取值较多的属性, 会极大地降低分类精度。基于以上考虑, 本文选择信息增益率来作为特征评估指标, 故引入了内在信息I(Intrinsic Information), 它表示了训练集S用A划分后的数据S′继续划分所期望的信息总量, 如式 (4) 所示:

$ I(A) = \sum\limits_{i = 1}^m {\frac{{|{S_i}|}}{{|S|}}} {\rm lb}\frac{{|{S_i}|}}{{|S|}} $ (4)

那么就可以最终获得特征属性A的信息增益率, 定义如下:

$ IGR(A) = {IG(A)}/{I(A)} $ (5)

信息增益率作为一种补偿措施解决了信息增益所存在的问题。通过信息增益率可以对特征进行相关性的初步排序, 进而对原始数据集进行了降维且利于选择出最优属性子集。

2.2 特征选择方法

本文针对的是Type-1和Type-2型的克隆代码, 检测之后可以生成克隆代码的基本信息, 例如克隆行数、代码位置、克隆相似度等, 从这些基本信息中可以获取克隆代码的一些静态特征; 之后, 在软件多版本之间进行克隆群映射以及克隆家系的构建, 又可以从某款软件的长期演化历史中分析这些克隆的发展情况, 例如克隆寿命等动态演化特征。得到的这两种特征就是一个初始的特征集合。

IGR-SFFSM方法分为两个步骤:首先采用信息增益率对初始特征集合中的特征进行相关程度的排序, 过滤掉排名靠后的特征, 生成候选特征样本集合; 然后采用序列浮动前向选择算法从候选特征子集中选出新特征集, 并使用六种常用的学习算法进行分类预测, 保留分类效果较好的特征子集, 迭代测试并最终得到最优特征子集。代码的数量级不同不会影响IGR-SFFSM方法, 但最终选出的特征会有所不同。因为数量增加之后, 不同特征的量化会发生变化,例如代码行数、分支语言以及圈复杂度等都会发生变化。

2.2.1 生成候选特征集合

生成候选特征子集的伪代码如算法1所示, 主要包括两个部分:第一部分 (第1)~8) 行) 计算Entropy(S) 和Entropy(S, A) 进而计算出IG(A) 和I(A), 最终得到信息增益率IGR(A); 第二部分 (第9)~13) 行) 把上一步计算出的IGR(A) 作为字典的值, 特征A作为键存入一个字典, 并对字典按值进行降序排序, 从而筛选出排名靠前的特征并放入特征集合F中。

算法1  生成候选特征子集。

输入:当前的训练集S。设原始特征集合S={S1, S2, …, Sn}为全部特征构成的集合, 特征总数为n

输出:候选特征子集FF为被选择出来的特征构成的子集, 即F=∅。

1)  对于训练集S

2)   按式 (1) 计算S的信息熵Entropy(S)

3)   对于每一个特征ASi(i=1, 2, …, n)

4)    按式 (2) 计算Entropy(S, A)

5)    计算特征A的信息熵IG(A)=Entropy(S)-Entropy(S, A)

6)     根据式 (4) 计算A的信息总量I(A)

7)    定义特征A的信息增益率IGR(A)

8)     如果I(A)! =0, 计算IGR(A) 值

9)     统计所有特征的信息增益率值, 令Key=A, value=IGR(A) 值

10)     存入字典dict[Key]=value

11)  对数组dict进行降序排序

12)  如果dict[Si]排名≥ $\left\lceil {n/2} \right\rceil $, 将特征Si放入集合F中, 过滤其余特征

13) 返回候选特征子集F

2.2.2 搜索最优特征子集

序列前向选择 (Sequential Forward Selection, SFS) 算法规定特征子集从空集开始, 每次选择一个能使评价函数取值达到最优的特征加入这个子集。其算法本质就是一种简单的贪心算法, 而这种算法只能加入特征而不能去除特征, 容易出现局部最优解而非全局最优解。序列浮动前向选择 (Sequential Floating Forward Selection, SFFS) 算法是一个是自底向上的搜索过程, 是在最基本的序列前向选择过程中引入了一个额外的回溯步骤, 有效地规避了SFS算法带来的弊端。

基于信息增益率上一步生成的候选特征子集F。本文使用随机森林等构建的克隆代码有害性评价模型作为一个评估函数, 采用序列浮动前向选择搜索最优子集。该算法结合正向选择和反向选择两种算法实现特征选择。正向选择算法的含义是首先将特征数据集清空, 之后每次把一维特征加入到数据集输入测试模型进行循环测试, 最后通过评价预测结果, 选择那些对结果影响最明显的特征数据; 而反向选择算法的流程与之相反, 首先构建包含所有特征的数据集, 之后每次从中去除一维特征输入测试模型进行循环测试, 最后去除那些对结果影响最微小的特征数据而保留剩余的特征。选择算法具体步骤伪代码描述如下。

算法2  SFFS搜索最优特征子集。

输入:候选特征子集F, 一组特征集合Fi(i=1, 2, …, q), 特征个数q=$\left\lceil {n/2} \right\rceil $, 当前已选择的特征个数k, 初始化k=0。

输出:最优特征子集Y

1   初始化特征数据集Y为空, 即Y=∅, Y={yj|j=1, 2, …, D, Dq}, J(Y) 表示Y特征子集在评估函数的表现。

2)  对于每一个特征AFi(i=1, 2, …, q)

3)   选择最好的特征A放入Y

4)    X+=Max[J(Yk+A)], AF

5)    Yk=Yk+X+; k=k+1

6) 对于每一个特征xYi (i=1, 2, …, k)

7)  选择Y中最坏的特征x剔除

8)    X-=Max[J(Yk-x)], xYk

9)    If J(Yk-x-) > J(Yk) then

10)    Yk=Yk-X-; k=k-1

11)    go to 6)

12)  El se

13)    go to 3)

14) 返回最优特征子集Y

3 实验与分析 3.1 实验数据集

本文选择了7款不同C语言软件共164款发布版本作为实验软件, 这7款软件功能不同, 规模大小不一并且持续有更新维护。目标软件详细信息如表 1所示。

表 1 目标软件基本信息 Table 1 Target software basic information
3.2 克隆代码有害性特征样本收集

本文结合克隆代码自身特征及其相邻版本映射关系和在演化过程中隐含的存在、发展、变化规律, 提出了两大类能够表征克隆代码有害性的特征, 将提出静态特征和演化特征两大类共17维特征作为克隆代码有害性的度量指标。静态特征能够反映代码本身的一些语法语义特征, 演化特征能够表征克隆代码的稳定性和成熟性。特征汇总如表 2所示。

表 2 克隆代码有害性特征 Table 2 Harmfulness characteristics of clone code

静态特征的提取建立在克隆代码检测的基础上, 本文使用的是自主开发的检测工具FClones[16], 这款工具是基于Token编辑距离的方法检测克隆, 并以最长公共子序列相似度计算模型对克隆对再进行一次源代码的相似度计算, 便于找到更合适的相似度阈值。该工具可以检测C语言的Type-1、Type-2和Type-3函数粒度克隆, 检测过程中不考虑编程人员的编程风格, 如果存在变量和算法在表达式上的差异, Token形式化抽象之后这个差异就不存在了。针对不同程序语言的特点, 本文方法具有自然语言通用性, 只需要在检测的过程中对不同自然语言分析词法层面的信息, 制定不同的Token化替换规则。最终都能得到克隆代码检测信息, 然后通过代码度量工具SourceMonitor提取克隆代码行数和注释比例等部分静态特征, 通过词法分析提取参数个数等剩余静态特征。

演化特征的提取必须依赖于克隆家系结果。本文采用克隆家系提取工具FCGE[17]根据克隆代码映射关系和演化信息自动构建克隆家系, 能够快速准确地提取出软件中存在的Type-1及Type-2型的克隆家系信息。获取以上两种特征之后, 得到有害性特征样本数据集D, 列出部分数据见表 3

表 3 实验数据集 Table 3 Experimental data set
3.3 分类器评估方法及指标

为了评估有害性预测模型的预测效果, 需要将数据集分成训练集和测试集两部分, 其中训练集用来构建模型, 测试集用来评估模型。由于数据集中的数据序列会影响预测模型的预测效果, 所以只作一次检验会存在很大的偶然性,因此本文选择K折交叉验证 (K-fold cross-validation) 的方法来评估模型效果。K-折交叉检验将数据分成K组, 使用其中的一组数据作测试集, 使用剩余的K-1组数据作训练集。该测试过程重复K次, 每次使用不同的数据作测试集, 然后取K次测试效果的平均值作为最终的预测结果。交叉验证重复K次以确保每个子集都有机会成为一个测试子集。实验采取K=10, 即10折交叉验证来评估预测模型的性能。这个方法的优势在于评估结果和数据划分方式关系不大, 每一组数据都有一次机会作为测试数据, 并有K-1次机会作为训练数据, 故模型测试误差中方差的成分变小且过拟合可能性小。

有害性预测是一个典型的二分类问题, 现有的预测性能指标多数都是基于表 4所示的混淆矩阵。因为有害性预测的目的是识别出有害的克隆代码模块, 本文认为有害的类属于正类, 反之属于负类。

表 4 混淆矩阵 Table 4 Confusion matrix

基于混淆矩阵, 本文使用3种指标评估预测模型, 分别是准确率 (Accuracy)、F1-测度 (F1-Measure) 和AUC(Area Under ROC Curve) 值:

$ Accuracy = \frac{{TP + FN}}{{TP + FP + FN + TN}} $ (6)
$ F1 - Measure = \frac{{2 * TP}}{{2 * TP + FN + FP}} $ (7)

其中:TP表示将有害的实例正确预测为有害的实例数量;TN表示将无害的实例正确预测为无害的实例数量;FP表示将无害的实例错误预测为有害的实例数量;FN表示将有害的实例错误预测为无害的实例数量。AUC是指ROC (Receiver Operating Characteristic Curve) 曲线下面包括的面积[18], 即ROC曲线的积分。ROC曲线的X轴表示负正类率, Y轴表示真正类率。AUC值介于0~1, 值越大, 即代表分类效果越好。

3.4 实验结果与分析

本文基于Weka学习平台使用不同的机器学习方法来评估分类器的整体表现。实验中使用基于贝叶斯定理与特征条件独立假设的朴素贝叶斯 (Naive Bayes) 算法, 不同k(1~9) 值的k近邻分类器 (KNN), 修剪决策树作为基分类器的装袋集成学习器 (Bagging), 基于C4.5决策树算法的J48决策树, 随机森林分类器 (Random Forest), Java实现的命题规则学习算法RIPPER (JRip)。

图 3展示了两款软件基于信息增益率排名下前n个特征在六种机器学习方法预测的Accuracy平均值。从图 3中可以得出以下结论:

图 3 信息增益率排名前n的特征分类准确率 Figure 3 Classification accuracy of top n information gain ratios

1) 从图 3(a)中可以看到, 当特征数量增加时Naive Bayes的分类准确率急剧下降, 预测最好与最差表现相差4个百分点左右, 而其他分类器结果都在可以接受的波动范围内。当特征个数n=6时, Bagging分类的效果达到最佳, 仅仅包含了6个特征, 却缩减了约70%的特征。

2) 从图 3(b)中, 随着特征数目的逐渐增多, Naive Bayes的分类表现逐渐降低, 分析原因可能是该算法基于特征条件独立的假设下, 而实际情况中特征相关性较强, 如果不考虑此因素预测准确性会越来越低。对于KNN、C4.5、Bagging和Random Forest四个分类器, 当特征数量在4~6, 准确度提高10个百分点左右达到最佳表现, 之后随着特征增多, 两者之间并不会呈现正相关, 相反结果趋于稳定。

图 3(a)图 3(b)中发现, 针对某一款软件, 采用任何一种学习方法预测, 可以很直观地选择出能使该数据集达到最好分类效果的特征个数n。在选择n值的过程中, 并不是n值较小, 预测效果就不好, 也并不是n值越大, 分类效果就越好; 相反, 最好的n个候选特征子集是根据信息增益率排名计算得出。

从上述结论中可以得到:本文方法依据信息增益率对上述两款软件的特征进行排名, 通过关键参数特征n的选取实验, 给出了本文方法中关键参数的最佳取值, 从而为有害性预测结果提供了更简洁和准确的特征范围。同时, 针对不同软件, 特征n数目并非固定不变, 本文方法的实现也支持参数n的调节。

表 5中, 将本文提出的IGR-SFFSM方法选择出的特征子集应用在六款不同的机器学习预测模型中。从表 5的实验结果得出, IGR-SFFSM方法选择出来的特征数据集在六种分类算法中都比保留所有特征的原数据集D上分类效果好, 提高的范围从15.2~34个百分点, 平均表现提高了25.08个百分点。同时发现, 不同特征选择策略的准确度对数据集的类型有很高的敏感性。例如, fdisk数据集在经过IGR-SFFSM方法筛选之后, 平均准确度仅仅提高了2个百分点左右, 而smalltalk分类效果平均提高了28个百分点。最后发现J48+IGR-SFFSM、RIPPER+IGR-SFFSM组合的分类效果有明显提高, 其中RandomForest+IGR-SFFSM组合的效果较差。

表 5 特征选择前后不同分类算法预测的Accuracy值对比 Table 5 Comparison of different classification algorithms to predict Accuracy value before and after feature selection

将IGR-SFFSM方法与同类一些比较常用的特征选择方法进行比较, 这些方法有基于皮尔森系数的相关性计算准则 (Correlation)、基于信息熵的信息增益率和采用最好优先搜索策略 (BestFirst) 的Wrapper方法。表 6中呈现了不同特征选择相关算法的分类结果。从表 6可看出, Wrapper+BestFirst和IGR-SFFSM在三种衡量指标上都要远优于其他类方法, IGR-SFFSM比其他方法Accuracy提升7.7~17.5个百分点, F1-Measure提升3.6~10.1个百分点, AUC值提高7.0~22.1个百分点。最后, 本文提出的IGR-SFFSM方法与Wrapper+BestFirst方法相比在三类性能指标上稍有提升, 平均提高约为1.5个百分点。

表 6 特征选择相关算法的分类结果对比 Table 6 Classification results of related feature selection algorithm

表 7列出了本文方法在7款开源软件上筛选特征子集的过程。表中数字所代表的特征名称和具体描述在表 2中有详细的说明, 例如序号0代表代码行数、序号1代表计算程序长度、序号16代表改变频率, 其他序号含义以此类推。这些数字所表示的特征必须数值化成表 3所示的具体数字后才能应用到有害性预测中。由表 7可知, FullSets列表示初始特征子集经过信息增益率评估之后的排名序列;IGR-Sets列表示根据前一步计算之后, 选择出来的候选特征子集, 去除FullSets中一些与分类相关程度非常小的特征;SFFSM-Sets列表示在IGR-Sets方法提供的候选集上, 进行子集搜索应用到分类器上, 得出的预测效果最好的特征集合。可以得出结论, 本文方法平均筛选出的特征个数为4~5个, 缩减了将近70%的特征, 效果依然优于使用全部特征进行预测的表现。特别地, 多款软件中特征1、7、8、10号特征被选中次数最多, 说明这四个特征对分类结果影响较大;而0、11、12号特征似乎都被筛掉 (表 2详细说明了序号表示的意义), 这也只能说明针对这几款软件来说这几个特征用来表征有害性的程度微小一些, 对有害无害的分类结果影响较小。

表 7 特征子集生成过程 Table 7 Feature subset generation process

表 5~7的结果中可以得出:本文方法使用基于信息论的信息增益率对特征n这个关键参数进行合理的选取, 即针对不同软件参数n会有不同的调节,最终可用较少的特征来提高有害性分类的准确度、F1值和AUC三种衡量指标, 体现了本文方法在预测结果的高效性。本文认定有害克隆代码的出发点就是基于大多数的不一致变化会引入bug这个观点。从标注为发生不一致变化的克隆代码中提取众多特征, 希望能挖掘出真正和有害代码行为相关的特征行为。而实际这些特征中存在一些和有害克隆代码无关或冗余的特征影响发现有害代码的可能性,因此, 本文方法对这些特征之间和特征与有害性之间的关系进行了分析, 最终选择出与有害分类相关程度最高的特征, 实验结果表明这些精选出来的特征确实能提高预测的精确度。所以, 特征选择可以提高发现有害克隆代码的高效性和可能性。

3.5 实验结果说明

根据不同编程语言的特性, 比如不同语言有不同的关键字、不同的函数定义方式等,依据词法分析就能分析出来词法成分并制定不同的Token化替换规则进行替换。例如:针对C语言, 用r统一替换数组名, 使用D替换基本数据类型, for替换为F等替换规则。对于不同粒度的代码也一样, 在于词法分析这个预处理过程, 预处理时识别出来代码范围就一样可以进行Token化。其他语言的Token化规则类似, 考虑具体语言特性即可, 最终都能得到克隆代码检测信息。

本文实验部分的特征角度对比是从静态特征和演化特征两个维度进行分析的。以上分析结果说明对表征有害性的特征进行筛选, 确实可以提高有害性预测准确度, 也能剔除一些无关紧要的特征 (这些不必要特征的提取会耗费很大一部分时间精力)。结果发现衡量有害克隆代码的特征指标很多, 但其实只有一部分特征会影响代码的有害无害程度。例如:圈复杂度和分支语句比例过高的代码, 有害可能性非常大, 相反代码行数的多与少对于代码有害程度的影响较小。最终发现有害克隆代码是真实存在的, 其造成的原因是克隆代码中一小段代码由于bug修复或者新功能引入而发生了改变, 其他与其相似的克隆代码需要获得同样的处理和检查, 如果无意中遗漏了某一段代码, 也就是说这些克隆代码之间没有保持一致性而发生了不一致变化, 这就可能给程序中带来隐含的bug。

在有害性预测问题中存在误判现象。因为克隆代码有害性预测这个研究领域是基于克隆检测、克隆映射和克隆家系等多个基础研究之上, 每个阶段的方法都会存在一定的误差;即使是每个阶段使用效果最好的方法, 也会存在一定的误差。另外一个误差原因, 鉴定克隆代码有害无害的研究和观点没有统一标准, 而判断有害无害的标准是以国内外的大量研究为基准, 他们都认为克隆代码不一致变化非常频繁并且大量的程序错误都是由这种不一致变化引起的。

4 结语

针对克隆代码有害性预测中存在特征无关与冗余的问题, 本文采用一种基于序列浮动前向搜索和信息增益率组合的特征选择算法——IGR-SFFSM。实验结果表明, IGR-SFFSM方法选择出来的特征预测表现更好, 在本文采用的准确率、F1值、AUC三类指标上都有明显的提升。特征选择结果表明使用机器学习进行有害性预测并不是特征越多包含的信息越多, 预测结果更好,一定程度上科学合理地削减一些不重要的特征, 不但能减少模型构建的时间, 还能节省提取无关特征耗费的时间和精力。本文的研究结果仅提供给维护人员来预测即将发布的软件版本中是否存在这种不一致的变化, 大多数的不一致变化会存在bug, 有的不一致变化存在也不会对整个软件有任何危害。本文的预测结果作为一个测试/维护人员的推荐和参考, 但是要客观精确衡量每一段克隆代码有害或者无害, 还需要在人工观察之后, 决定是否有害以及是否需要重构或修改。此外, 该方法可以扩展到克隆代码管理方面, 在构建模型评估克隆代码的质量时,面对选择特征集工作量大, 特征分散等问题, 本文提出的对于特征优化筛选的方法对解决这些问题都有借鉴意义。

本文的研究工作目前表现仍有不足:一方面是文中所用到的克隆有害性特征包括静态与动态特征共17维, 仅对克隆代码部分特征进行分析并得到不同结论, 并没有从其他角度分析和收集一些特征, 例如耦合特征、上下文特征、克隆特征等。如果能够从不同的特征度量元来考虑对克隆代码有害性预测能力的影响会更全面。另一方面是在研究中发现有害性预测数据集上存在数据分类不平衡的问题, 这种数据不平衡会影响特征和类标签之间的相关程度计算。所以, 在未来的研究工作中拟从多维特征角度对比分析以及将特征选择和数据不平衡问题结合起来进行研究, 进一步提高有害性预测效果。

参考文献
[1] WAGNER S, ABDULKHALEQ A, KAYA K, et al. On the relationship of inconsistent software clones and faults: an empirical study[C]//Proceedings of the 23rd International Conference on Software Analysis, Evolution, and Reengineering. Washington, DC: IEEE Computer Society, 2016:79-89.
[2] 梅宏, 王千祥, 张路, 等. 软件分析技术进展[J]. 计算机学报, 2009, 32 (9) : 1697-1710. ( MEI H, WANG Q X, ZHANG L, et al. Software analysis technology progress[J]. Chinese Journal of Computers, 2009, 32 (9) : 1697-1710. )
[3] WANG X, DANG Y, ZHANG L, et al. Can I clone this piece of code here?[C]//Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering. Piscataway, NJ: IEEE, 2012: 170-179.
[4] 李智超. 基于支持向量机的克隆代码有害性评价方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2013: 32-34. ( LI Z C. Research on SVM-based evaluation method of clone code harmfulness[D]. Harbin: Harbin Institute of Technology, 2013: 32-34. )
[5] 张丽萍, 张瑞霞, 王欢, 等. 基于贝叶斯网络的克隆代码有害性预测[J]. 计算机应用, 2016, 36 (1) : 260-265. ( ZHANG L P, ZHANG R X, WANG H, et al. Harmfulness prediction of clone code based on Bayesian network[J]. Journal of Computer Applications, 2016, 36 (1) : 260-265. )
[6] 尹丽丽. 基于主题模型的克隆代码有害性预测研究[D]. 呼和浩特: 内蒙古师范大学, 2014: 6-7. ( YIN L L. Research on predicting harmfulness of code clones based on the topic model[D]. Hohhot: Inner Mongolia Normal University, 2014:6-7. )
[7] INOUE K, HIGO Y, YOSHIDA N, et al. Experience of finding inconsistently-changed bugs in code clones of mobile software[C]//IWSC 2012: Proceedings of the 6th International Workshop on Software Clones. Piscataway, NJ: IEEE, 2012:94-95.
[8] JUERGEBS E, DEISSENBOECK F, HUMMEL B, et al. Do code clones matter?[C]//ICSE 2009: Proceedings of the 31st International Conference on Software Engineering. Piscataway, NJ: IEEE, 2009:485-495.
[9] STEIDL D, GODE N. Feature-based detection of bugs in clones[C]//IWSC 2013: Proceedings of the 20137th International Workshop on Software Clones. Piscataway, NJ: IEEE, 2013: 76-82.
[10] GUYON I, ELISSEEFF A. An introduction to variable and feature selection[J]. Journal of Machine Learning Research, 2002, 3 (6) : 1157-1182.
[11] BONEV B, ESCOLANO F, CAZORLA M. Feature selection, mutual information, and the classification of high-dimensional patterns[J]. Formal Pattern Analysis & Applications, 2008, 11 (3/4) : 309-319.
[12] MOUSTAKIDIS S P, THEOCHARIS J B. A fast SVM-based wrapper feature selection method driven by a fuzzy complementary criterion[J]. Formal Pattern Analysis & Applications, 2012, 15 (4) : 379-397.
[13] MENZIES T, GREENWALD J, FRANK A. Data mining static code attributes to learn defect predictors[J]. IEEE Transactions on Software Engineering, 2007, 33 (1) : 2-13. doi: 10.1109/TSE.2007.256941
[14] KOHAVI R, JOHN G H. Wrappers for feature subset selection[J]. Artificial Intelligence, 1997, 97 (1/2) : 273-324.
[15] JANECEK A, GANSTERER W N, DEMEL M, et al. On the relationship between feature selection and classification accuracy[EB/OL].[2016-05-10]. http://www.jmlr.org/proceedings/papers/v4/janecek08a/janecek08a.pdf.
[16] 张久杰, 王春晖, 张丽萍, 等. 基于Token编辑距离检测克隆代码[J]. 计算机应用, 2015, 35 (12) : 3536-3543. ( ZHANG J J, WANG C H, ZHANG L P, et al. Clone code detection based on Levenshtein distance of Token[J]. Journal of Computer Applications, 2015, 35 (12) : 3536-3543. )
[17] 涂颖, 张丽萍, 王春晖, 等. 基于软件多版本演化提取克隆谱系[J]. 计算机应用, 2015, 35 (4) : 1169-1173. ( TU Y, ZHANG L P, WANG C H, et al. Clone genealogies extraction based on software evolution over multiple versions[J]. Journal of Computer Applications, 2015, 35 (4) : 1169-1173. )
[18] FAWCETT T. An introduction to ROC analysis[J]. Pattern Recognition Letters, 2006, 27 (8) : 861-874. doi: 10.1016/j.patrec.2005.10.010