第5卷第4期 智能系统学报 Vol.5 No.4 2010年8月 CAAI Transactions on Intelligent Systems Aug.2010 doi:10.3969/i.issn.1673-4785.2010.04.007 不变量的程序潜在错误预测 杨振兴，刘久富，孙琳 (南京航空航天大学自动化学院，江苏南京210016) 摘要：随着软件系统变得越来越复杂和庞大，软件中的安全缺陷也急剧增加，系统中的隐含错误也在逐渐增多.提 出一种基于不变量的程序潜在错误预测方法，首先采用支持向量机对程序属性所产生的非函数依赖程序不变量进 行学习并产生机器学习模式，然后运用该机器学习模式对需预测的程序进行属性分类，并揭示出代码可能存在的潜 在错误，最后通过实验验证该方法是有效的 关键词：不变量；软件测试；支持向量机；错误预测 中图分类号：TP311文献标识码：A文章编号：16734785(2010)04032705 Using invariants to predict the potential for errors in programs YANG Zhen-Xing,LIU Jiu-Fu,SUN Lin (College of Automation Engineering,Nanjing University of Areonautics and Astronautics;Nanjing China;210016) Abstract:As software systems become increasingly complex and large,deficiencies in software security increase sharply and implicit errors increase gradually.A method based on invariants was developed to predict potential er- rors in programs.First,a support vector machine was used to find program invariants and produce a pattern for ma- chine learning.Then the pattern from machine learning was employed to classify the programs with behavior to be predicted and reveal the latent errors in codes.Finally an experiment was done that verified the effectiveness of the method. Keywords:invariants;software testing;support vector machine;error prediction 随着软件系统变得越来越复杂和庞大，软件中生的非函数依赖程序不变量进行学习并产生机器学 的安全缺陷也急剧增加.据统计有40%的系统故障 习模式的方法，然后运用该模式对需预测的程序进 是由软件缺陷引起的山.通常的测试方法是通过执 行属性分类，并标示出代码可能存在的潜在错误.该 行测试用例集来发现程序源代码中的错误，一旦程 方法的输人是一系列给定程序的属性，输出经辨识 序通过对它所测试的测试用例后，测试便不会再通 后能辨识潜在错误的属性. 过程序员来发现错误.然而，程序仍然可能存在潜在 的错误，此时，如果想通过新的测试来发现潜在的错 1支持向量机理论 误可能会显得很困难并需要付出很大的代价 潜在错误预测与很多因素有关，因此预测模型 由查找隐含错误的一般方法知，许多错误都是 的输入量将是一个高维、非线性、小样本的模式识别 由很少的一些类别引起，相似的错误都具有相似的 问题.在前人研究的基础上，选用支持向量机作为机 特性，然后这些特性能够被概括和识别.例如，3个 器学习理论对潜在错误进行预测。 普通的错误类别是由一个错误引起的（不正确的使 潜在错误预测分类模型3]与排序模型4的建 用第一个或最后一个数据结构元素)，使用未初始 立即分别寻求以下表达式的成立 化或部分初始化的值21 本文提出一种采用支持向量机对程序属性所产 f(x)sign(>ay:k(xx)+b), 收稿日期：2009-10-12. f(x)= (a-a:)K(xr)+b. (1) 基金项目：国家自然科学基金资助项目(60674100). 0 通信作者：杨振兴.E-mail:ywfu@163.com. 式中：α为可揭错误属性，x:为k个样本中的第i个
·328 智能系统学报 第5卷 样本；K(x,x)为核函数，核函数采用径向基函数， all nodes n);size keys)=size(contents);graphg is 如下式所示) acyclic.常见的不变量形式有程序的前置条件、后置 k(,)=exp(-Y‖x:-x‖2). (2) 条件、循环不变量和类不变量6。 利用支持向量机工具箱即可对式(1)的模式分 2.2程序潜在错误预测框架 类，对(2)的模式排序.本方法使用了LibSVM工具 在该方法中用类似C语言中的关系表达式描 包，LibSVM是台湾大学林智仁副教授等开发设计的 述不变量，这样可以使用多种方法检测不变量，利用 一个简单、易于使用和快速有效的SVM模式识别与 工具解析多种格式描述的不变量成为关系表达式的 回归的软件包，包含C-SVC,nu-SVC等多种支持向 形式.本文提出的基于不变量程序潜在错误预测方 量机工具的实现，这个软件包可以通过互联网直接 法的体系结构框图如图1所示，他主要由2部分组 从相关的网站上获取， 成：通过支持向量机训练得到能够辨识潜在错误的 模式和被测程序通过模式辨识得到可揭错误属性 2基于不变量的程序潜在错误预测框架 (fault--revealing properties).该方法包括如下步骤： 1)将含有已知错误的代码经过词法语法分析 合肥工业大学李嘉研究了基于支持向量机的软 检测编配得到含有错误的属性不变量，将去除错误 件可靠性早期预测，在提出模型的基础上，设计了一 后的代码经过词法语法分析检测编配得到去除错误 个软件可靠性早期预测软件系统，该预测系统把支 后的属性不变量； 持向量机引人软件可靠性早期预测领域，可以对软 2)将1)所述的含有错误的属性不变量和去除 件存在的缺陷数进行预测.但该系统不能对缺陷进 错误后的属性不变量分别经过槽的替换得到支持向 行具体的定位，只能给软件开发人员一个预测的缺 量机输入的特征向量，其中槽包括变量类型槽、运算 陷数量].本文提出的的方法是对单个程序属性， 符类型槽、属性类型槽和程序变量槽，下同； 通过辨识能得到存在错误的的程序属性，并通过该 3)将2)所述的特征向量经过SVM模式识别与 程序属性定位程序中的潜在错误， 回归进行机器学习得到能够辨识潜在错误的模型； 2.1程序不变量 4)将用户程序依次经过词法语法分析检测编 所谓不变量就是一些用于描述在程序运行时保 配、槽后得到用户程序的属性特征向量，将用户程序 持不变的性质的逻辑断言，它经常出现在断言声明、 属性与3)所述的能够辨识潜在错误的模型匹配去 形式化描述中，例如：y=4·x+3;x>abs(y);ar 除可揭示性错误。 ray a contains no dup licates;n=n:child:parent(for 含有已知错 含行错误属 通过槽 使刀支 误的代码 性的不变量 转换为 持向量 能够辩 支特向 机工具 识潜在 量机输 LibSVM 错误的 去除错误后 预处 去除属性后 入的特 进行机 模型 的代码 理 的不变量 征向量 器学习 词法 语法 通过槽 分析 转换为 程序属性 支持向 使用支持向 可揭 用户程序 量机工具 不变量 量机输 误 LibSV Mi进 属性 入的特 征向量 行分类 分类 图1程序潜在错误预测框图 Fig.1 The diagram of program potential error prediction 2.3属性转换为机器学习特征向量 在对机器算法的输入之前，每个属性都需要转 机器学习算法使用特征向量作为输入，因此研 换成为特征向量，另外，属性如果在当前存在于有缺 究需要将用不变量体现的属性转换为特征向量的形 陷的程序中时，称为可揭错误的属性，如果属性在有 式.特征向量是一些关于布尔型(bool),整型(int), 缺陷的和无缺陷的版本中都出现了，称为不可揭错 浮点型(oat)等的值，它被认为在多维空间中的一 误属性，如图2所示，左边的椭圆代表含有错误代码 个点.每维(dimension)被叫做一槽(slot)[]. 的属性，右边的椭圆代表去除已知错误代码的属性
第4期 杨振兴，等：不变量的程序潜在错误预测 ·329· 2个椭圆公共部分是并未从含有错误代码中去除错 q)任：代表不变量为当且仅当型 误的那些属性即不可揭错误属性， 4)程序变量槽. 举个例子，假如这有4槽指示一个等式，其中的 a)Num Vars:代表变量的个数 3槽指示涉及变量的类型，还有另外1槽指示了变 b)VarinoIndex:代表当前变量的索引 量的个数，其中相对应是和否用1和0来表示，变量 c)IsStaticConstant:代表是否为常静态变量 个数用实际的个数值来表示.在本文的研究方法中， d)PrestateDerived:代表变量是否是函数开始时 特征向量包含了44个槽8]，分别列举如下： 派生变量 e)DerivedDepth:代表派生的深度 含行错误代 去除错误后 码的属性 f)IsClosure:代表变量是否关闭 代码的属性 g)IsParameter:代表变量是否是函数的参数 h)IsReference:代表变量是否是函数传引用 可揭错误属性不可揭错误属性 i)IsIndex:代表变量是否是系列的索引 图2可揭错误属性 j)IsPinter:代表变量是否为指针 Fig.2 The fault-revealing properties 训练阶段需要一个二元组〈P,P〉其中P是包 1)变量类型槽. 含至少一个错误的程序，P'去除了这些错误之后的 char(字符型)，double(双精度)，float(单精 程序版本，程序P'并不需要是完全正确无误的，只 度)，int(整形)，long(长整形)，short(短整形)，void 需去除相对应的错误就可以[8)」 (空型)，string(字符串型)共8个变量类型， 3实例分析 2)运算符类型槽， ==,≥，>，≤，，≤， 参数：相关率(Relevance)和简短率(Brevity)I).采 <,≠) 用总体相关率和总体简短率，分类相关率和分类简 a)Stored:代表一系列数据进行排序 短率以及定量相关率和定量简短率对所述方法进行 b)Linear:代表变量之间成线性关系 评价： c)Constant:代表不变量之间有常量 简短率=所有被辨识出的可揭错误属性 d)Min(x):代表不变量为最小值 正确辨识可揭错误属性 e)Max(x):代表不变量为最大值 正确辨识可揭错误属性 相关率一所有被辨识出的可揭错误属性 f)x≠0orx≠null:代表变量不为零或空 属性集的相关率表明被揭错误属性的可能性大 g)x==c:代表不变量恒为常量 小.总体相关率是所有给定程序的程序属性的整组 h)Aay:代表不变量为数组 相关率；分类相关率是被辨识可揭错误属性组的相 i)x[0~n]cmpy[0~n]:代表变量为一对一的 关率；定量相关率是预先选择定量可能性排考前可 比较，并且长度一致 揭错误属性的相关率. j)x[]=~y[]:代表一个数组为另一个数组的 组属性的简短率是与相关率相反的量.即检 逆序 测到一个可揭错误属性需要平均属性的个数.最完 k)x[]cmpy:代表数组的每个量与一个变量比 美的简短率是1，也即所有的属性都是可揭错误属 较大小 性.同相关率，简短率度量分为总体简短率，分类简 I)x[门cmpi:代表数组与自己的序号比大小 短率和定量简短率 m)x[]≠：代表数组全都不等于自己的序号 通过机器学习后对预测程序进行模式分类和模 n)x[]cmpy[]:代表数组的所有值都比另一 式排序，能够得到预测分类的相关率大于总体相关 个大或小 率，即分类的简短率小于总体的简短率，或定量相关 o)Subsequence:代表一个集合是另一个的连续 率大于总体相关率，即定量简短率小于总体简短率， 一段子集 则表明该潜在错误预测方法是有效的。 p)x≤c:c为常量，x是标量.代表变量始终都小 3.2实例 于一个常量 为了验证理论方法的正确性，作者采用李春葆
330 智能系统学报 第5卷 刘斌编著的《C语言程序设计考点精要与解题指 for(i=0;i<=num/2,i++) 导》一书中的改错题型提取修正前和修正后的程 temp =out[i]; 序，通过检测编配代码提取52个数据样本，此类数 out[i]out[num-i]; 据样本中含有相似数量的可揭错误属性与不可揭错 a[num-i]temp; 误属性的程序属性不变量.运用LibSVM工具包对 所提取的52个数据样本进行训练，分别运用 return out[] LibSVM工具中的C-SVC分类机和ε-SVR回归机对 实例属性不变量进行分类和排序. 将实例程序经过检测编配分析得到表1中的8 由于预测模型生成信息量大，为说明该方法的 个程序属性不变量，采用了8槽来表示特征向量 预测步骤，作者对如下一个程序实例列出部分属性 (实际运用时模式的产生运用了44个槽)，特征向 不变量对方法进行说明. 量信息如表1，如：out[num]=oig[0]不变量的的 double[Against(double orig[]int num) 特征向量是(1,0,0,1,0,0,2,1〉（此处的1和0代 /orig[]为原数组，num为数组元素的个数 表真和假)，将之前学习所产生的分类机和回归机 int i; 分别对表中的8个特征向量进行辨识及预测，所得 double temp,out[num]; 结果如表1所示. memcpy out,orig,num) 表1不变量转换为特征向量表 Table 1 Invariants to characteristic vector converter 等式 变量类型 程序变量槽 属性不变量 分类 排序 =≠ double int Array NumVars Varinolndex 结果 结果 out[num]orig[0]1 00 1 0 0 1 1 91 i=num/2+1 100 0 1 0 2 0 89 size(out)=size(in) 100 0 1 0 3 0 1 89 out[num =null 100 1 0 0 1 77 orig二out 001 0 0 1 2 0 -1 47 out Corig 00 1 0 0 1 2 0 -1 47 out≠null 010 0 0 1 0 -1 32 orig≠nu 010 0 0 1 0 -1 32 分析实例程序得到out[num]=orig[O]和i= 3)根据所预测将得到的可揭错误属性定位到 num/2+1存在错误，根据表1中的结果，得到预测 程序中，由程序员审查程序中可能存在的错误并将 结果相关率与简短率指标如表2所示，并对该方法 其修改。 作如下分析说明： 4)分类相关率与定量相关率都大于总体相关 表2预测结果相关率与简短率表 率，即说明所提出的方法是有效的、 Table 2 The result of relevance and brevity 5)训练样本的获取非常重要，该方法的应用中 总体 分类 定量(3) 应取自实际项目中测试得到的历史数据，即测试前 相关率 2/8=0.252/4=0.52/3=0.67 的可揭错误属性不变量与去除错误后的的程序不变 量作为训练的二元组〈P,P). 简短率 8/2=44/2=2 3/2=1.5 6)训练样本应该是与所预测程序相同编程语 1)分类结果中有4个属性被辨识为存在错误， 言所编写，并从测试该项目组之前所完成的项目中 实际其中的2个存在错误，根据评价指标得到分类 提取数据样本为最佳，这可提高预测的精度，提高测 的相关率为0.5大于总体属性不变量的相关率为 试效率， 0.25,相应的分类的简短率小于总体简短率。 2)假设规定错误可能性排列在前3个属性为可揭 4结束语 错误属性，同上得到定量的相关率为0.67大于总体相 提出的程序潜在错误预测方法主要研究了应用 关率的0.25，相应的简介性小于总体简介性. 支持向量机对代码属性进行学习并产生模式，通过
第4期 杨振兴，等：不变量的程序潜在错误预测 331 模式对用户代码进行预测潜在错误的方法，得到可 LI Jia.The study of software reliability early prediction 能隐含更深的程序错误，提高程序的可信性.对属性 based on support vector machine[D].HeFei:Hei fei Uni- 不变量的提取、属性向特征向量的转换、属性分类进 versity of Technology,2005. 行了探讨.重点研究了属性转换为与代码无关的特 [6]刘杰，阳小华，罗扬等.一种交互式的不变量动态发现编 征向量. 配工具[J].计算机应用与软件.2008,10：8586. LIU Jie,YANG Xiaohua,LUO Yang,WU Qujing.An in- 该方法运用支持向量机对软件潜在错误进行定 teracten instrum enter for dynamically discovering invariant 位分析，能快速查找到程序中错误，并可以反复使 [J].Computer Applications and Software,2008,10:85- 用，提高软件测试效率；通用性强，在预测阶段用来 86. 训练的不是具体的属性，而是学习一些属性槽，通过 [7]ERNST M D,COCKRELL J,GRISWOLD W G.Dynami- 支持向量机学习之后可以完全应用于同语言的不同 cally discovering likely program invariants to support pro- 程序中。 gram evolution[J].IEEE TSE,2001,27(2):1-25. [8]GRAVES T L,HARROLD M J,KIM J M,PORTER A, 参考文献： ROTHERMEL G.An empirical study of regression test se- [1]MARCUS E,STERN H.Blueprints for high availability lection techniques[J].ACM Transactions on Software Engi- [M].Washington:John Wiley,2003:38-42. neering and Methodology,2001,10(2):184-208. [2]BRUN Y.Software fault identification via dynamic analysis [9]SALTON G.Automatic information organization and retriev- and machine learning[D].Cambridge Massachusetts:Mas- al[M].New York MeGraw-Hill,1968:485-498. sachusetts Institute of Technology,2003. 作者简介： [3]汪廷华，田盛丰，黄厚宽.特征加权支持向量机[J].电 杨振兴，男，1985年生，硕士研究 子与信息学报，2009,31(3)：514-518. 生，主要研究方向为软件测试与人工智 WANG Tinghua,TIAN Shengfeng,HUANG Houkuan.Fea- 能 ture weighted support vector machine[J].Journal of Elec- tronics Information Technology ,2009,31(3):514-518. [4]程勇，罗键，吴长庆.基于支持向量机的环境质量评估方 法[J].计算机工程与应用，2009,45(2)：209-211. 刘久富，男，1971年生，博士，硕士生导师，主要研究方 CHENG Yong,LUO Jian,WU Changqing.Environmental 向为软件测试技术与软件质量工程. quality evalution based on SVM[J].Computer Engineering 孙琳，男，1983年生，硕士研究生，研究方向：软件测 and Applications,2009,45(2):209-211. 试 [5]李嘉.基于支持向量机的软件可靠性早期预测研究 [D].合肥：合肥工业大学，2005