MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); function MyAutoRun() {    var topp=$(window).height()/2; if($(window).height()>450){ jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); }  }    window.onload=MyAutoRun; $(window).resize(function(){ var bodyw=$win.width(); var _leftPaneInner_width = jQuery(".rich_html_content #leftPaneInner").width(); var _main_article_body = jQuery(".rich_html_content #main_article_body").width(); var rightw=bodyw-_leftPaneInner_width-_main_article_body-25;   var topp=$(window).height()/2; if(rightw<0||$(window).height()<455){ $("#nav-article-page").hide(); $(".outline_switch_td").hide(); }else{ $("#nav-article-page").show(); $(".outline_switch_td").show(); var topp=$(window).height()/2; jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); } }); 面向条件判定覆盖的线性拟合制导测试生成
  软件学报  2016, Vol. 27 Issue (3): 593-610   PDF    
面向条件判定覆盖的线性拟合制导测试生成
汤恩义1, 2, 周岩1, 3, 欧建生1, 3, 陈鑫1, 3     
1. 计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210023;
2. 南京大学软件学院, 江苏 南京 210093;
3. 南京大学计算机科学与技术系, 江苏 南京 210023
摘要: 条件判定覆盖(condition/decision coverage,简称C/DC)准则是各种安全攸关软件测试中常用的测试覆盖准则,它要求软件测试覆盖程序中每个判定以及条件的真/假取值.现有的自动测试生成方法在针对该准则的测试用例生成过程中存在很多不足.例如:符号执行方法很难处理较为复杂的非线性条件约束,并在处理程序的规模上受到很大限制;希尔攀登法由于在搜索过程中易陷入局部最优,而难以达到满足C/DC准则的高覆盖率;模拟退火法和遗传算法依赖于用户使用过程中的复杂配置,测试用例生成效果具有一定的随机性.针对这一现状,提出了一种线性拟合制导测试用例生成方法.依据C/DC准则,该方法将程序中的每一个条件判定规范化为一个与零值比较的数值函数,并以插桩与执行获得该函数当前输入下的采样.通过拟合这些采样,能够逐步判断出程序中各个条件判定与输入的关系,并利用这些关系生成高覆盖率的测试用例.相对于传统方法,该方法具有参数配置简易、生成过程高效等优点,并且能够处理带非线性条件约束、逻辑复杂的程序.在3个开源软件库中的25个真实程序上运行的实验结果表明,所提出的方法比目前以覆盖率见长的遗传算法(genetic algorithm,简称GA)制导方法具备更好的覆盖能力与更高的执行效率.
关键词: 测试用例自动生成    条件判定覆盖    线性拟合    关联路径    
Test Generation Approach Guided by Linear Fitting for Condition/Decision Coverage Crit
TANG En-Yi1, 2, ZHOU Yan1, 3, OU Jian-Sheng1, 3, CHEN Xin1, 3     
1. State Key Laboratory for Novel Software Technology(Nanjing University), Nanjing 210023, China;
2. Software Institute, Nanjing University, Nanjing 210093, China;
3. Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China
Abstract: Condition/decision coverage(C/DC) is a frequently used coverage criteria for safety-critical software testing.It requires every decision and condition in the program have taken all possible outcomes(true or false).Existing approaches of automatic test generation for C/DC criteria are defective.For example, symbolic execution based approaches are limited by the constraint solver, which is difficult in processing non-linear constraints;hill climbing often sticks at local optima, which limits yielding of high-coverage cases;and simulated annealing and genetic algorithm need complicated configuration, which make the results unstable.In this paper, a novel test generation approach that is guided by linear fitting is proposed.The basis of the approach is to sample every decision and condition of numerical values with program instrumentation.The relationship of inputs and samples is then build with linear fitting functions.By searching the target inputs on the gradually refined functions, test case is generated with high coverage.Experiments on 25 real programs in open source projects show that the proposed approach is more effective and efficient than the genetic algorithm of test generation.
Key words: automatic test generation    condition/decision coverage    linear fitting    associated path    

软件测试是软件开发过程中不可或缺的步骤之一,也是工业界保障软件质量最主要的手段.在软件生命周期中,软件测试往往占据了很大的比重[1].随着软件系统规模的增长,软件的逻辑结构日益复杂,软件测试所耗费的时间和生产成本也越来越多,而其中由于人工设计测试用例的成本就占据了测试总成本的40%[2].因此,研究自动化的测试用例生成技术,节省软件测试成本,成为了时下热门的研究方向之一[3].

条件判定覆盖(condition/decision coverage,简称C/DC)准则是白箱测试中的一种重要测试覆盖准则,由于该覆盖准则的要求比路径覆盖更为精细,且比条件覆盖效率更高,故而许多安全攸关的软件测试协议都以该覆盖准则作为判断标准.例如,飞行安全软件标准DO-178B就将MC/DC(modified C/DC)列为必须满足的测试覆盖准则之一[4].因此,本文基于该准则来研究高效的测试用例生成方法.

现有的测试用例自动生成技术主要有两类:基于符号执行和基于搜索的方法.符号执行方法将程序输入定义为抽象符号,在程序执行过程中以符号运算操作代替具体的运算指令,从而收集各执行路径的符号条件约束,将测试用例生成问题转化为约束求解问题.这里的约束是以程序输入为符号变量的等式或不等式组.符号执行使用约束求解器来求解约束,但由于精度限制和非线性约束求解的复杂性,现有的约束求解器很难处理较为复杂(例如存在SMT不可判定的量化公式)的非线性浮点约束,这导致符号执行在遇到非线性浮点约束时覆盖效果并不理想[5].基于搜索的方法包括随机法和启发式方法.随机法通过随机地生成大量程序输入来试图满足测试覆盖准则,这种方法处理小规模的简单程序时效果较好,但随着程序规模的扩大,随机法的命中率显著下降[6].启发式搜索用一个适应度函数(fitness function)来评估搜索到的数据,并选取最佳数据作为搜索结果.这种带有导向性的搜索机制使得启发式方法的平均性能优于随机法[7].更进一步,启发式搜索又分为局部搜索和全局搜索.局部搜索(例如希尔攀登法)受制于初始输入数据的影响,容易陷入局部最优[2].全局搜索(例如模拟退火法(simulated annealing,简称SA)、遗传算法(genetic algorithm,简称GA))采用了特殊的控制机制,使得计算结果能更容易达到全局最优,是目前面向C/DC覆盖标准的最好的测试用例自动生成方法[2].已有的研究表明:在适当的配置条件下,遗传算法的搜索覆盖效果最好[2].但是,该方法仍然存在以下不足:

· 遗传算法要求在执行之前明确各个测试用例的搜索空间.当用户给出的搜索空间过大时,会极大地影响搜索效率;而当给出的搜索空间过小时,搜索空间之外的测试用例将无法覆盖.在大部分情况下,要求用户在执行测试之前给出较为精确的测试用例搜索空间是十分困难的;

· 遗传算法要求较为复杂的参数设定.在不同的测试场景下,遗传算法严格要求设定各项参数.由于遗传算法来源于生物学,所设定的参数包括编码策略、种群大小、选择策略、模拟染色体的交叉策略、交叉概率、变异概率等等.不同设定条件下的搜索性能差别很大.

针对这些问题,本文面向条件判定覆盖准则提出了一种新的线性拟合制导的测试生成方法.该方法首先将程序中的每一个判定条件规范化为一个与零值比较的数值函数,并通过插桩获得该函数在程序执行时的采样.我们利用这些采样值线性拟合数值函数,并由拟合函数估算出程序的各个判定条件与程序输入的关系,并生成测试用例.随着采样的增多,各条件判断对应的拟合函数会得到不断地细化与更新,拟合函数的定义范围也会逐步得到拓展.最终,我们沿着C/DC准则逐个在拟合函数上查找满足条件的目标输入区间,从而生成满足C/DC准则的测试用例.相对于已有的方法,该线性拟合制导的测试生成方法具有如下优点:

· 可处理复杂非线性条件约束.由于本文方法直接执行程序获得约束对应的函数采样,故而并不依赖于条件约束的形式,对于较为复杂的非线性约束,我们仍然可以通过拟合逐步逼近原始函数而使其得到正确的处理,从而找到正确覆盖的测试用例;

· 能够高效获得高覆盖率的用例.本文方法避免了复杂的符号计算,因而能够处理工业级规模的程序.相对于局部搜索和全局搜索算法,本方法直接针对程序的判定进行拟合,因而制导过程更加直接,且具有针对性.实验表明,本方法能在比现有方法更短的时间内获得更高的测试生成覆盖率;

· 不需要明确测试用例的搜索空间,搜索过程不会陷入局部最优.本文方法在生成测试用例的过程中并不需要用户明确给定搜索空间,而会自动对程序的各个拟合函数进行定义域拓展,尝试定义域外的测试用例.本文方法对各拟合函数的求解具有全局性,因此在搜索测试用例时,不会陷入局部最优;

· 参数配置简易.本文方法几乎没有需要用户精细配置的参数,用户使用简单有效.

虽然相对于传统方法,本文提出的线性拟合制导测试生成方法具有很多优势,但该方法也有其适用范围.线性拟合制导的测试生成方法仅能用于数值类型(如整型int、长整形long、浮点型float、double等)及其复合类型(如结构体、数组、容器等)的测试生成.对于存在非数值型输入(如字符串)的程序,需要先结合其他方法来对非数值型输入进行预处理,再由本文的方法来完成数值类型测试用例的生成.

我们基于Eclipse平台,以插件的形式设计并实现了线性拟合制导测试生成的工具原型,并在3个开源软件库中的25个真实程序上进行实验.实验结果表明:由于线性拟合制导的测试生成方法直接针对程序逻辑进行制导,在大多情况下,比经过参数优化的遗传算法制导的测试生成方法在C/DC准则下获得更高的覆盖率与更好的测试效率.在处理覆盖输入特别少的极值条件目标时,这一优势特别明显.

本文第1节将通过一个具体的例子来直观地介绍本文线性拟合制导测试生成方法的执行过程.第2节详细描述该方法的整体流程和具体的技术细节.第3节将本文提出的线性拟合制导方法与遗传算法制导的测试生成方法进行比较,在3个开源软件库中的25个真实程序上进行实验并给出实验结果.第4节介绍本文的相关工作.第5节总结全文并得出结论.

1 示例介绍

图1所示为一段以x为输入的示例代码.其中,方框部分为插桩代码,在原始待测程序中并不存在,故而没有标定行号.

Fig.1 An example program 图1 样例程序

在原始程序共有两个判定(第2行和第3行的两个if)和3个判定条件表达式(分别为第2行的条件c1:sin(w)≤0,第3行的条件c2:w>10以及第3行的条件c3:cos(x)<0.2),条件判定覆盖准则要求生成的测试用例覆盖程序中的每个判定,且每个条件表达式都要取到真/假值,例如生成4个测试用例,使条件关系表达式(c1,c2,c3)的取值为(true,true,true),(true,false,false),(false,true,true),(false,false,false),就能满足C/DC准则的覆盖要求,这也是基于C/DC准则的测试用例生成目标.当判定条件c1,c2,c3存在复杂非线性计算时(例如这里的三角函数操作sin,cos等),传统方法很难直接求解判定条件成立时的测试输入.本文的方法将各个判定条件看作黑箱函数$f(\vec x)$与0的不等式(或等式),即$f(\vec x)$$ \odot $0,这里的函数自变量$\vec x$为程序输入(向量维度为程序输入变量的个数).函数$f(\vec x)$也称为拟合目标函数;$ \odot $为不等号或等号,即$ \odot $$\in ${>,≥,<,≤,=,≠}.因此对于图1的示例代码来说,各个判定条件及其对应的目标函数写成如下形式:

· c1: sin(x2+1)≤0,即f1(x)=sin(x2+1);

· c2: x2+1-10>0,即f2(x)=x2-9;

· c3: cos(x)-0.2<0,即f3(x)=cos(x)-0.2.

为了生成高覆盖率的测试用例,我们希望生成不同的程序输入,使得程序中的每个判定条件表达式能取到尽可能多的真假值组合.本质上,我们只需要找到程序输入$\vec x$,使各个目标函数$f(\vec x)$取到0值点以及0值点的各包围区间(例如f1(x)>0的区间和f1(x)≤0的区间).对于一般程序来说,$f(\vec x)$本身可能非常复杂,本文的测试生成方法并不需要精确的求解黑箱函数$f(\vec x)$,而是通过插桩和制导程序的执行,获得各个判定条件所对应目标函数的采样值.这些采样值是很容易获取的,例如对于图1所示程序来说,我们仅需要对原始程序插桩图中方框部分的代码,即可获得对应目标函数在当前执行输入下的采样.更进一步,我们基于这些采样值进行线性拟合,从而粗略地估计出目标函数$f(\vec x)$的性质,以便更为方便地找到其对应零值点的包围区间,从而能够高效地生成高覆盖率的测试用例.

对于图1所示的程序样例,本文的方法将目标函数f1(x),f2(x),f3(x)看做未知的黑箱函数.首先,任意随机生成两个初始测试用例x=7,x=1,并利用该测试用例执行程序.当程序执行到第2行和第3行时,我们通过执行插桩后的程序很容易获得当前执行时各拟合目标函数的采样值f1(7)=sin(w)=-0.26,f2(7)=w-10=40,f3(7)=cos(x)-0.2=0.55.使得条件$\vec c(7)$的取值为(true,true,false),判定$\overrightarrow {dc} (7)$的取值为(true,false);对于测试用例x=1来说,执行程序将获得f1(1)=0.91,而f2(1)和f3(1)由于未能被执行覆盖到对应路径而不能获得采样.从而覆盖条件$\vec c(1)$=(false,x,x),判定$\overrightarrow {dc} (1)$=(false,x).由这些采样数据,我们构建f1(x)的拟合函数${f'_1}(x)$=-0.195x+1.11.本文的方法基于C/DC准则检查判定和条件的覆盖情况,对于判定$\overrightarrow {dc} $来说,其第一分量dc1的真假值已经都被覆盖,第二分量dc2=true还未被覆盖.从条件$\vec c$来看,dc1所属的条件χ1的真假值已都被覆盖,dc2所属条件χ23仍未被覆盖.根据这一状况,我们的算法会以dc2=true作为当前生成测试用例的覆盖目标.算法执行会首先使dc1=true以保证目标判定dc2被执行到,这可以通过在拟合函数${f'_1}(x)$中搜索使得${f'_1}(x)$≤0的x区间来获得(如x=10).但实际上,当我们以x=10执行程序时,会得到f1(10)=0.91,从而dc1(10)仍然为false.这时,以采样f1(10)进一步细化${f'_1}(x)$,使得拟合函数${f'_1}(x)$成为分段线性函数(即,由f1(1),f1(7),f1(10)这3个点计算分段线性函数的系数,使两个分段均通过3个采样点):

${f'_1}(x) = \left\{ {\matrix{ { - 0.195x + 1.11,{\rm{ }}x \in [1,7)} \hfill \cr {0.39x - 2.99,{\rm{ }}x \in [7,10]} \hfill \cr } } \right.$.

随着分段细化的不断进行,${f'_1}(x)$会越来越接近于实际的目标黑箱函数f1(x),从而使得我们通过搜索能够找到满足dc1=true的输入x=3.9,使得f1(3,9)=-0.48,f2(3,9)=6.21,f3(3,9)=-0.92,$\vec c$(3.9)=(true,true,true),$\overrightarrow {dc} $(3.9)=(true,true).利用这些采样值,我们可以进一步构建和不断细化拟合函数${f'_2}(x)$和${f'_3}(x)$,并搜索到覆盖dc2=true的测试用例(这里,x=3.9直接覆盖到了dc2=true).然后,算法依据C/DC准则设定下一个未覆盖的测试目标χ2=false.同样用上述方法,通过反复迭代,最终能够生成满足C/DC准则的测试用例集.

2 线性拟合制导的测试生成方法

本节正式描述基于一般情况下,线性拟合制导的测试生成方法以及该方法的各项技术细节.本方法能够全局搜索数值类型的输入变量(如整型、浮点型),从而获得基于条件判定覆盖准则的测试用例集.对于非数值类型的输入,本方法并不直接适用.

2.1 整体流程

不失一般性,对于给定程序的程序输入在本文中表示为向量$\vec x$=(x1,x2,…,xn)的形式,这里,xi为程序第i个输入变量的值.程序的执行路径表示为执行语句的序列p=〈s1,s2,…,sm〉,当语句sj为一个条件跳转时(如分支条件、循环条件),我们称sj为判定语句.判定语句的判定条件无论多复杂,都可以规范化成多个条件关系表达式χ联立而成的析取范式(disjunctive normal form,简称DNF),且析取范式中各个条件表达式为无副作用的关系表达式e1ee2.这里,e为关系运算符e$\in ${>,≥,<,≤,=,≠}.我们进一步将每个条件关系表达式e1ee2规范化成等价的零值比较形式e$ \odot $,这里,e=e1-e2.为了简便起见,我们简称条件关系表达式为条件.

定义1(关联路径). 从程序起点到当前条件关系表达式χ所在判定语句的某一条执行路径p,称为条件χ的一条关联路径.

在实际程序中,每个条件关系表达式χ可能存在多条不同的关联路径,所有χ的关联路径将组成关联路径集P(χ).对于其中一条关联路径,规范化条件表达式e$ \odot $的左部e可看作由程序输入$f(\vec x)$经过固定的操作指令序列执行而得到的结果,因此,本文将其看做一个程序输入的函数$f(\vec x)$,称为拟合目标函数.对于实际的复杂软件,我们很难精确得到$f(\vec x)$,因而采用分段线性拟合函数$f(\vec x)$来逼近它,并由此计算满足C/DC准则的测试用例.

图2给出了线性拟合制导测试用例生成的整体流程.整个流程以待测程序与少量随机生成的初始用例为输入,生成满足条件判定覆盖准则的测试用例.

Fig.2 Main frame of linear fitting based test generation 图2 线性拟合制导测试用例生成方法的总流程框架

图2可以看出,整个框架分为5个步骤.前两个步骤对待测程序进行预处理,以获得各判定语句及其判定条件的集合;并通过插桩,在程序的每个判定语句前插入各拟合目标函数的采样代码,从而在执行程序时获得相应的采样值.后3个步骤是一个反复迭代的过程:首先,由随机生成的少量测试用例驱动程序执行,获得目标函数的采样值;然后,依据已有的采样值拟合各个判定条件的目标函数;最终,依据C/DC准则选择一个当前测试用例尚未覆盖到的条件表达式作为覆盖目标,从当前分段线性拟合函数中生成多个可能覆盖目标的测试用例.所生成的测试用例将会进一步驱动采样程序的执行而进入下一轮的迭代,这样既可以验证生成的测试用例是否覆盖到对应的目标,又可以进一步精化各分段线性拟合函数,使下一轮迭代生成的测试用例更为准确.这3个步骤的反复迭代,直到生成的测试用例集完全满足C/DC准则的覆盖目标.

2.2 待测程序的预处理

静态分析与程序插桩共同完成了对待测程序的预处理,以产生可用的采样程序.静态分析对源代码进行扫描,在遍历抽象语法树(abstract syntax tree,简称AST)的基础上,获得当前程序的判定语句集SD以及各判定语句s$\in $SD的规范化判定条件dc.对于存在副作用的判定条件,静态程序分析会将存在副作用的运算式从条件表达式中提出来,从而将判定条件改为无副作用的逻辑表达式.最终,判定条件dc被静态分析模块规范化为一个条件关系表达式的析取范式:

1∧χ2∧…∧cn1)∨(cn1+1cn1+2∧…∧cn2)∨…∨(cni+1cni+2∧…∧ch),

其中,各条件关系表达式ck(1≤kh)被规范化为零值比较形式e$ \odot $.这里,e为任意的算术表达式,e为关系运算符e$\in ${>,≥,<,≤,=,≠}.我们可以定义判定语句的执行先后关系.

定义2(先执行关系). 对于判定语句集SD中的两条判定语句s,so$\in $SD,如果从程序起点到当前判定语句so的每一条执行路径都经过判定语句s,则称s,so存在先执行关系x,或称s先于so被执行,记为sxso.

由自反性、反对称性和传递性,我们能够证明先执行关系x为判定语句集SD上的偏序关系.依据此偏序关系,在静态分析期间会构建判定语句集SD上的拓扑排序$\vec S$,并输出到后续模块用于覆盖目标的选择.

在静态程序分析结果的基础上,插桩模块在待测程序各判定前插入采样代码.采样代码记录两部分信息:一是各拟合目标函数在当前执行时的采样值,这将用于函数拟合;二是各判定条件的判定结果,这将用于计算当前的执行路径,并进一步推算各个条件的关联路径,从而验证C/DC准则的覆盖情况.因此,采样代码也由两部分组成:第1部分记录当前判定中每一个规范化条件关系表达式e$ \odot $的左部值e;第2部分记录当前整个判定条件的真假判断.根据程序执行时每个判定条件的真假判断,我们的算法即可构建当前的实际执行路径p.

2.3 目标函数的线性拟合

在完成静态分析和插桩预处理之后,我们就开始使用随机生成的初始用例来执行插桩后的采样程序,从而获得目标函数$f(\vec x)$的采样值和各执行对于条件χ的关联路径.由第2.1节所述:当且仅当条件χ的多个采样值对应于χ的相同关联路径时,它们才对应于同一个目标函数$f(\vec x)$.此时,才能对这多个采样值进行拟合.

2.3.1 多维输入向量的拟合处理

对于多维输入向量$\vec x$=(x1,x2,…,xn),从其第1分量x1开始,每次仅关注其一个维度,而将其他维度上的分量设为常数进行拟合.

图3显示了当输入向量$\vec x$为二维向量(x,y)时,线性拟合的处理过程,这里的曲面是指某目标函数$f(\vec x)$的函数图像.

Fig.3 Fitting process for two-dimensional input vector 图3 二维输入向量的拟合处理过程

我们首先关注其第1维度x而固定其第2维度y为随机常数y0,正如图3中绿色箭头所示:随着拟合过程的进行,x方向上会逐步采样到x1,x2,x3,x4,x5而构建出x方向上的分段线性拟合函数f'(x,y0).对于C/DC准则中指定的覆盖目标$f(\vec x)$$ \odot $为真,可能我们在这一拟合过程中就已经找到了覆盖这一目标的程序输入向量(xi,y0),使f(xi,y0)$ \odot $为真,或者我们未能找到覆盖该目标的输入向量.对于第1种情况,直接按照C/DC准则的下一个覆盖目标进入下一轮的测试生成;而对于第2种情况,在当前条件关系表达式$f(\vec x)$$ \odot $的x方向上一定存在xop使得分段线性拟合函数f'(x,y0)的绝对值达到最小值.该向量(xop,y0)即为固定y0后在x方向上能找到的最接近于覆盖目标的用例,因此,进一步固定xxop而在y方向上进行拟合,并搜索能满足覆盖目标的测试用例,如图3中紫色方向箭头所示.

一般地,对于多维输入向量$\vec x$=(x1,x2,…,xn),本方法从i=1开始,每次仅对其中一个分量xi做拟合,并尝试寻找满足覆盖目标$f(\vec x)$$ \odot $的输入值,如果成功覆盖目标,则拟合尝试过程结束.在此过程中,除i之外的其他各分量被固定为常数,对于后面的各分量xj(j>i),由于该分量还未经过拟合而未能得到任何信息,故而本方法将其固定为一个随机常数.而对于每一个已经经过拟合的分量xk(k<i),我们会在拟合xk时找到最接近覆盖目标的取值xop,使得当xk=xop时|$f(\vec x)$|达到最小值.故在尝试拟合xi时,将分量xk固定为常量xop.

2.3.2 拟合函数的构建与更新

对于多维输入向量,我们在拟合过程中每次仅关注其一个维度,因此,该方法仅需要讨论在各分量维度上一维目标函数f(x)的线性拟合过程.当我们以输入x0,x1执行两次采样程序后,获得f(x)的采样值f(x0),f(x1),我们即可构建拟合函数f'(x)=ax+b.其中,$a = {{f({x_1}) - f({x_0})} \over {{x_1} - {x_0}}},\;b = f({x_0}) - a{x_0}.$

随着程序执行次数的增多,我们可能会获得目标函数f(x)的更多采样值.例如:当我们进一步以x2来执行程序来获得采样值f(x2)后,可以将拟合函数f'(x)进一步细化为两段:

$f'(x) = \left\{ {\matrix{ {ax + b,{\rm{ }}x \in [{x_0},{x_2})} \hfill \cr {cx + d,{\rm{ }}x \in [{x_2},{x_1}]} \hfill \cr } } \right.,$

其中,$a = {{f({x_2}) - f({x_0})} \over {{x_2} - {x_0}}},b = f({x_0}) - a{x_0};c = {{f({x_1}) - f({x_2})} \over {{x_1} - {x_2}}},d = f({x_2}) - c{x_2}$.这一更新过程如图4所示.

Fig.4 Updating of component linear fitting function 图4 线性拟合函数的更新

随着我们执行采样程序次数的增多,程序中各目标函数的采样值也会越来越多,拟合函数f'(x)会由于不断细化而逐步接近目标函数的取值,从而使得我们寻找的测试用例越来越准确.

2.3.3 拟合函数的自变量目标区间

拟合的最终目的在于帮助后续的测试生成,因此当获得各条件关系表达式对应的拟合函数f'(x)之后,我们需要利用拟合函数根据覆盖目标f(x)$ \odot $为真或者为假获得当前的自变量目标区间.

图5为拟合函数f'(x)的一个自变量目标区间,由于虚线所示的拟合目标函数f(x)为未知的黑箱函数,我们仅能在执行过程中得到实线所示的拟合函数f'(x).由拟合函数的0值点(与x轴的交点)d,e,我们能够获得该拟合函数针对目标f(x)<0为真在x分量上的自变量目标区间(d,e).

Fig.5 A target interval of the linear fitting function 图5 拟合函数的一个自变量目标区间

定义3(自变量目标区间). 对于分段线性函数f'(x)及其对应的条件关系表达式f(x)$ \odot $,当对于区间(u1,u2)中的每一个值u$\in $(u1,u2)都满足(或都不满足)f'(u)$ \odot $,则称区间(u1,u2)为一个针对目标f(x)$ \odot $为真(或为假)在x分量上的自变量目标区间.

所有针对同一条件表达式目标为真(或为假)在x分量上的自变量目标区间构成了自变量目标区间集,输入向量$\vec x$的各分量在该条件表达式目标为真(或为假)的自变量目标区间集的并集,即为针对该覆盖目标输入向量$\vec x$的目标区间集X.

2.3.4 拟合函数的细化与拓展

当拟合函数不够精确时,采用拟合函数f'(x)获得的自变量目标区间存在很大误差,甚至会因此而根本找不到正确的自变量目标区间.我们通过对拟合函数的细化和拓展来解决这一问题.细化和拓展的本质是在输入的x分量上依据一定规则进一步找一些采样点,并由这些采样点来执行程序获得新的拟合目标函数采样值,从而将拟合函数更新的更加细致(或覆盖更多的自变量范围).但如果采样点过多,一方面需要大量的程序执行消耗资源来获得采样值;另一方面也会使得分段拟合函数过于复杂,使得目标求解变得更困难.因此,细化与拓展规则对于本文的方法来说十分重要.以下介绍本文的细化和拓展规则.

细化规则1. 对于分段线性拟合函数f'(x)的分段(a,f'(a)),(b,f'(b)),当该分段直线直接存在0值点d时,以d作为细化目标,以便逼近拟合目标函数f(x)的真实0值点(如图6所示).

Fig.6 Generating the refinement point d in the interval (a,b) according to the refinement rule 1 图6 拟合函数的分段区间(a,b)按细化规则1获得细化目标d

细化规则2. 对于分段线性拟合函数f'(x)的分段(a,f'(a)),(b,f'(b)),当该分段直线延长线上的0值点d落在拟合函数的相邻分段(b,χ)时,我们以d作为细化目标.

图7所示,分段(a,b)的延长线落在区间(b,χ),说明(a,b)的相邻分段(b,χ)相对于当前区间(a,b)来说给得过于宽泛,我们可以以d进一步细化分段区间(b,χ).如果延长线0值点d落在相邻分段(χ,a),也将以d作为细化目标.

拓展规则1. 令l,a,b为满足la<b的实数.对于定义在区间(l,b)上分段线性拟合函数f'(x)的边缘分段(a,f'(a)),(b,f'(b)),当该分段直线延长线上的0值点d落在拟合函数的定义区间外时,我们以d作为拓展目标.

当边缘分段延长线上的0值点落在拟合函数的定义区间外时,说明当前拟合函数在边缘外可能有遗漏的0值点,这对获得完整的自变量目标区间是不利的,因此,我们将试图以d作为拓展目标拓展拟合函数f'(x)的定义区间.

拓展规则2. 令l,a,b为满足la<b的实数.对于定义在区间(l,b)上分段线性拟合函数f'(x)的边缘分段(a,f'(a)),(b,f'(b)),满足拓展规则1的条件,即:该分段直线延长线上的0值点d落在拟合函数的定义区间外,且d与拟合函数边缘b的距离d-b大于边缘区间宽度b-a时,将在d点周围宽度为b-a的区间$\left( {d - {{b - a} \over 2},d + {{b - a} \over 2}} \right)$上随机取一个位置点e,并以e为拓展目标.

Fig.7 Generating the refinement point d near the interval (a,b) according to the refinement rule 2 图7 拟合函数的分段区间(a,b)按细化规则2获得相邻分段的细化目标d

图8显示了两个拓展规则获得拓展目标de的方式,当边缘分段直线延长线上的0值点d离拟合函数边缘b的距离过远时,分段(b,d)并不能清晰地反映目标函数在该区间上的细节.因此我们需要额外增加一个拓展目标e,使得拓展区间更为精细.

Fig.8 Extending the refinement point d,e according to the extension rule 1 and 2 图8 由拓展规则1、拓展规则2获得的拓展目标de
2.4 测试生成算法

执行经过了插桩的采样程序除了能够获得采样值进行各目标函数的拟合外,还有一个重要作用在于能够验证到当前已有的测试用例集覆盖了C/DC准则中的哪些取值,即,哪些真假值组合已经被覆盖.对于本文方法的整体框架来说,测试生成的每一次迭代(即图2中的后3个步骤)都要求以一个C/DC准则中未被覆盖到的真假取值组合作为当前的测试生成目标.一般地,我们形式化定义测试生成目标为cc=boolval的形式,其中,cc为一个规范化条件.基于C/DC准则,它既可以是一个规范化的判定条件dc,也可以是判定条件中的一个规范化条件关系表达式χ.这里,boolval$\in ${true,false}是一个布尔真假值,用于标识测试生成目标条件的取值.

由第2.2节可知,静态分析预处理输出判定语句的拓扑序列$\vec S$=(s1,s2,s3,…,sm).对应地判定条件构成判定向量$\overrightarrow {dc} $=(dc1,dc2,dc3dcm),每个判定条件dci规范化成如下形式的析取范式:

1∧χ2∧…∧cn1)∨(cn1+1cn1+2∧…∧cn2)∨…∨(cni+1cni+2∧…∧ch).

每一个条件关系表达式目标cj=true在对应的分段拟合函数上都存在输入向量$\vec x$的目标区间集Xj,因此,整个判定条件为真dci=true的目标区间集DXi

(X1$\cap $X2$\cap $…$\cap $Xn1)$\cup $(Xn1+1$\cap $Xn1+2$\cap $…$\cap $Xn2)$\cup $…$\cup $(Xni+1$\cap $Xni+2$\cap $…$\cap $Xh).

判定条件取值为假dci=false的目标区间集为其补集,即:

$\overline {({X_1} \cap {X_2} \cap ... \cap {X_{n1}}) \cup ({X_{n1 + 1}} \cap {X_{n1 + 2}} \cap ... \cap {X_{n2}}) \cup ... \cup ({X_{ni + 1}} \cap {X_{ni + 2}} \cap ... \cap {X_h})} $.

当覆盖目标直接是判定条件的取值dc=boolval时,对应的目标区间集即是上面给出的集合;而当测试生成目标为判定条件dc中的某一个规范化条件关系表达式ct时,由于程序设计语言条件表达式中的逻辑短路**,我们首先要保障ct能够被执行到.即:必须使得(χ1∧χ2∧…∧cn1)∨…∨(cns+1cns+2∧…∧ct∧…)∨…∨(cni+1cni+2∧…∧ch)中ct前面的每一个合取子句的取假值,且ct所在的合取字句中ct前面的每一个规范化条件关系表达式取真值.而ct后面的条件关系表达式和合取子句可以取任意值而忽略.因此,条件关系表达式目标ct=true的在当前判定中目标区间集为

$D{I_t} = \overline {{X_1} \cap {X_2} \cap ... \cap {X_{n1}}} \cap \overline {{X_{n1 + 1}} \cap {X_{n1 + 2}} \cap ... \cap {X_{n2}}} \cap \;... \cap ({X_{ns + 1}} \cap {X_{ns + 2}} \cap ... \cap {X_t}).$

而条件关系表达式目标ct=false的在当前判定中的目标区间集为

$D{I_{\bar t}} = \overline {{X_1} \cap {X_2} \cap ... \cap {X_{n1}}} \cap \overline {{X_{n1 + 1}} \cap {X_{n1 + 2}} \cap ... \cap {X_{n2}}} \cap \;... \cap ({X_{ns + 1}} \cap {X_{ns + 2}} \cap ... \cap \overline {{X_t}} ).$

当我们进一步考虑关联路径的覆盖因素,设ct所在判定为dct,ct的关联路径要求判定条件向量$\overrightarrow {dc} $中dct前面各分量的真/假取值(具体该取真值还是假值由关联路径确定)对应的目标区间集分别为DX1,DX2,...,DXt-1.故而,ct=true的总目标区间集为

DX1$\cap $DX2$\cap $…$\cap $DXt-1$\cap $DIt.

ct=false的总目标区间集为

$D{X_1} \cap D{X_2} \cap ... \cap D{X_{t - 1}} \cap D{I_{\bar t}}.$

算法1给出了经过待测程序预处理后,线性拟合制导测试用例生成的整体算法.在该算法中,我们用映射Y来维护实际覆盖了每一个覆盖目标cc=boolval的输入向量集Y(cc,boolval).初始的时候,由于还没有任何测试用例,Y被置空.按照C/DC准则,算法1沿着判定条件的拓扑序列依次检查各判定条件及其条件关系表达式的真假取值是否已经被覆盖到,如未被覆盖Y(cc,boolval)==∅,则调用算法2定义的CaseGeneratecc=boolval为目标搜索测试用例.算法2以目标cc=boolval生成测试用例.它对当前目标的每一条关联路径进行尝试,并对输入向量进行各维度的分量处理.通过反复尝试搜索策略,逐步细化拓展各拟合函数.在找到当前的目标区间集以后,对每一个目标区间进行随机采样,以试图覆盖算法2的搜索目标.最终,如经过反复迭代仍然未能覆盖目标,则返回空值.

算法1. 线性拟合制导的测试用例生成算法.

输入:由静态分析预处理生成的判定条件的拓扑序列$\overrightarrow {dc} $=(dc1,dc2,dc3,…,dcm);

输出:最终生成的测试用例集.

1. ∀cc$\in $CC($\overrightarrow {dc} $),Y(cc,true)←∅; Y(cc,false)←∅; //初始化所有目标条件都还未被覆盖

2. i←1;

3. while im

4.  for j←0; jcond_num(dci); ++j //循环次数为dci中的条件数多1

5.   if j==0 then

6.    ccdci; //目标条件首先尝试当前整个判定条件

7.   else

8.     cccj$\in $dci //然后以当前判定中各个条件关系表达式为目标

9.    end if

10.    if Y(cc,true)==∅ then //假如当前覆盖目标真值未被覆盖,则尝试生成

11.     Y(cc,true)={CaseGenerate(cc,true)};

12.    end if

13.    if Y(cc,false)==∅ then //假如当前覆盖目标假值未被覆盖,则尝试生成

14.     Y(cc,false)={CaseGenerate(cc,false)};

15.    end if

16.    end for

17.  ++i;

18.  end while

19.  return $\cup $Range(Y) // 返回覆盖各目标的测试用例集的并集

算法2. 覆盖目标为cc=boolval的单次测试用例生成:CaseGenerate(cc,boolval).

1. X←∅

2. 随机生成输入向量$\vec x$=(x1,x2,…,xn),用做初始随机输入

3. for each p in P(cc) //对于目标的每一条关联路径

4.  i←1;

5.  while in

6.   $\vec x \leftarrow \vec x$[xi/Random]; //将输入向量$\vec x$的第i个分量换成随机值

7.   X←{$\vec x$}$\cup $X //将输入向量$\vec x$加入待尝试集合X

8.   for all $\vec x$in X

9.    {sample,path}=ProgramExec($\vec x$); //以$\vec x$执行采样程序,获得采样值和执行路径

10.    UpdateLinearFitting(sample); //以采样值更新各拟合函数

11.    if (cc2,boolv)=CheckCover($\vec x$) then

12.     Y(cc2,boolv)←{$\vec x$}$\cup $Y(cc2,boolv); //记录$\vec x$执行过程覆盖到的新条件

13.    end if

14.    if p in path AND eval(cc,$\vec x$)==boolval then //找到满足目标的测试用例$\vec x$

15.     return $\vec x$;

16.    end if

17.    XObjInterval(i,cc,boolval)$\cup $X //将当前xi分量上的目标区间集随机采样后加入X

18.    XRefExpInterval(i,p)$\cup $X //将关联路径上各拟合函数的细化拓展目标加入X

19.   end for

20.   ++i;

21.  end while

22. end for

23. return null; //未能找到覆盖目标

3 实例研究

我们基于Eclipse平台以插件的形式设计并实现了线性拟合(linear fitting,简称LF)制导测试生成方法的工具原型,用户在使用过程中仅需要直接将待测的C/C++程序以Eclipse项目的形式导入,即可使用本文的工具自动生成满足C/DC规则的测试用例.由于Eclipse插件要求以Java语言实现,因此本方法的实现本身是基于OpenJDK7的,并通过CDT8.1库来操作用户待测的C/C++程序.本文的全部实验在一台处理器为Intel CoreTM i5-2400 3.1GHz内存为4GB的工作站上运行,操作系统为Ubuntu 13.04.

针对C/DC准则,本文的实验以基于遗传算法的测试用例生成技术[7, 8]作为比较对象.遗传算法的测试用例生成技术是目前面向C/DC覆盖标准覆盖效果最好的测试用例生成方法[2].通过同遗传算法生成测试用例的比较,我们将试图回答以下几个研究问题:

· 问题1:针对条件判定覆盖准则,线性拟合制导与遗传算法制导产生测试用例相比,覆盖效果如何?

· 问题2:对于同样的覆盖目标,线性拟合制导与遗传算法制导相比,哪一种方法用时较短?

· 问题3:对于传统方法较难处理的覆盖目标,例如覆盖输入特别少的目标,线性拟合与遗传算法制导的测试用例生成方法将分别有怎样的表现?

3.1 实验用例与参数设置

本文的实验用例来自于3个实际使用的开源软件库:

· Numerical Recipes(http://www.nr.com);

· Benchmark of John Burkardt(http://people.sc.fsu.edu/~jburkardt/cpp_src/cpp_src.html);

· GNU Scientific Library(http://www.gnu.org/software/gsl/).

我们保留了这些开源软件库中拥有非线性浮点运算的独立程序,并去除了带有非数值类型输入(如指针类型,字符串类型)的部分,最终得到了25个实用程序作为实验基准.它们的具体信息见表1.具体给出了各个程序的名称、功能描述、代码行数(LOC)、可覆盖的判定(DE)和条件关系表达式(RE)的个数.其中,判定与条件关系的可覆盖性是由人工专门标注的.

Table 1 Overview of the Benchmark 表1 基准用例程序介绍

遗传算法的测试用例生成效果受参数设定的影响很大,我们在多次反复实验的基础上,选取了一组效果较好的遗传算法参数,具体见表2.除此之外,对于每一个程序,遗传算法需要一个优化的测试用例搜索空间才能得到好的测试覆盖.我们同样经过反复调优,最终遗传算法的测试搜索输入区间以及在这些参数下遗传算法制导的对应测试覆盖率见表3.

Table 2 Parameter settings in genetic algorithm 表2 遗传算法参数设定

Table 3 Search interval of genetic algorithm and the corresponding coverage 表3 遗传算法的测试用例搜索区间以及对应完成搜索的覆盖率

为了防止测试用例搜索停滞在某一个难以覆盖判定条件而影响整个测试生成的效率,我们设定判定条件目标搜索的时间阈值为10s,如果线性拟合算法在10s内仍然不能搜索到覆盖当前条件目标的用例,则放弃当前目标而尝试下一个覆盖目标.

3.2 实验结果分析

为了评价测试用例生成算法的有效性,我们以覆盖率和测试效率作为评价指标.C/DC准则以生成的测试用例实际覆盖到的判定和条件的数目占可覆盖的判定和条件总数的百分比作为覆盖率.当对应的算法分别生成了两个测试输入使程序执行时条件或判定取值为真和为假时,我们称对应的条件或判定被覆盖.以程序triangle为例,其可覆盖判定总数为4,可覆盖条件总数为11,如果算法覆盖了3个判定和9个条件,则其C/DC覆盖率为(3+9)/(4+11)x100%=80%.除了覆盖率之外,算法完成测试用例生成的效率也是一个重要的评价因素,即,算法达到目标覆盖率所需要的时间.在我们的实验中,以两种算法达到相同覆盖率所需的时间作为评价测试效率的标准.对于每一个基准程序,两种算法会分别运行10次测试用例生成,并以它们的平均指标来衡量算法的有效性,以防由于一些偶然因素而引起运行结果的异常.

表4显示了两种算法在25个基准程序上生成测试用例的覆盖率和测试效率.对于每一个基准程序,我们分别用两种不同的方法进行测试用例生成,获得各自的覆盖率;然后,我们以其中较小覆盖率作为覆盖目标,再分别测定两种算法达到该覆盖率所用的时间.每一轮实验会反复运行10次,并以它们的平均值作为测定结果.从表4的数据来看:在大部分情况下,线性拟合制导测试生成方法覆盖率高于经过优化的遗传算法制导方法,仅有极少数情况下(sort_heap_external,triangle和interp_cubic),线性拟合制导的效果略低.这是由于该程序的条件判定正好与遗传算法的变异规则相匹配造成的.当我们对各程序按照程序规模(即,按照代码行数)加权平均来计算平均覆盖率时(表4最后一行),线性拟合制导方法的平均覆盖率为94.28%,比遗传算法的81.77%提高了约12.5个百分点.

Table 4 线性拟合制导与遗传算法制导测试生成方法的实验结果对比 表4 Experiment results of test generation guided by linear fitting and genetic algorithm

当我们分析两种方法对相同覆盖率目标的测试生成时间时,我们可以看到:在很多程序(如julday,minabs)中,线性拟合制导测试生成算法远远快于经过优化的遗传算法制导方法.而另外一些程序,两者消耗的时间较为接近,经过加权平均,线性拟合制导方法的平均测试生成时间为50.547s,比遗传算法的平均测试生成时间64.514s加快27.6%.同时,我们比较了两种方法生成的测试用例个数,对于大部分程序,线性拟合方法以相对较少的测试用例个数获得了更好的测试覆盖.

在程序中,常常有一些特别难以覆盖到的判定和条件.例如在我们的实验基准程序r8_gamma中存在一个判定条件,要求该程序输入y的取值在2.23E-308~2.22E-16之间时才可以覆盖到,这对于可以在-200~200之间任意取值的输入y来说是很难覆盖到的.我们把这一类在程序中很难覆盖到的条件称为极值条件.在实验中,我们手工标注了含有极值条件的6个基准程序,并分别检测两种测试生成方法对于极值条件的覆盖情况,实验结果如图9所示.

Fig.9 The covered number of extreme conditions with the approach guided by LF and GA 图9 线性拟合制导与遗传算法制导方法的极值条件覆盖数

图9的数据可知,线性拟合制导的测试用例生成算法在覆盖极值条件目标时的优势特别明显.不同于遗传算法采用类似于染色体交叉、变异的制导方式,线性拟合方法会不断逼近程序中实际条件上的拟合函数.当经过有限次迭代后,只要拟合函数足够接近极值条件的目标函数,我们就可以搜索到对应的极值条件点,从而覆盖该条件.这是传统方法很难做到的.

3.3 实验结论

综上所述,我们的实验结果表明:由于线性拟合制导的测试生成方法直接针对程序逻辑进行制导,因而能够获得更好的程序测试用例生成效果.对于问题1,在大多数情况下,即使遗传算法经过了优化,线性拟合制导的测试生成方法仍然能在C/DC准则的标准下获得更高的覆盖率;对于问题2,当我们以某可达的覆盖率作为覆盖目标时,线性拟合制导的测试生成方法将会以更短的测试生成时间达到覆盖目标;对于问题3,线性拟合制导的测试生成方法在处理覆盖输入特别少的极值条件目标时,相对于遗传算法制导有特别明显的优势.

4 讨 论

本文提出了面向C/DC准则的线性拟合制导测试用例生成方法,该方法的主要优势在于,它能够处理程序中复杂的非线性条件约束.因为它将各个约束条件看作黑箱的目标函数,而采用线性拟合方法来得到一个逼近目标函数的线性拟合,因此相当于把复杂的非线性条件约束转换成了线性条件来进一步处理.因此,一个直观的测试用例生成方案是:对于程序中的普通线性条件约束,仍然采用现有的生成方法;而当遇到现有的求解器不可解的复杂非线性条件约束时,才切换到线性拟合制导测试用例生成方法来完成测试生成.本文目前并未采用这一方案,原因在于:使用求解器求解约束的测试生成方法需要一个收集约束的过程,例如符号执行过程.这一过程本身需要很大的时间开销,从而使得求解器能够得到实际的显式约束条件(即白盒约束条件),而这个收集过程在本文的方法中是可以省略的,线性拟合方法并不需要显式的白盒约束条件,从而能够极大地提高生成效率.当目标函数为线性函数时,本文方法相当于用线性参数来逼近线性的目标函数,这个过程的收敛速度很快,故而本文将测试生成过程设计成直接使用线性拟合来处理程序中所有数值约束条件的方式.

本文的测试生成方法面向C/DC准则尽可能生成高覆盖的测试用例,然而它并不能保证一定能够使生成的测试用例达到完全覆盖:一方面,程序中可能存在不可达的C/DC目标,例如当某个条件对于所有的输入恒为真时,该条件为假的C/DC目标就会覆盖不到;另一方面,线性拟合的采样策略会使得某些测试输入采样概率很低,当目标函数形状极为特殊时,对应的C/DC目标也会覆盖不到,因此在本文实验中,我们并不能使得所有程序的测试覆盖率达到100%.软件测试本身并不是完备的方法,我们的方案能够以较少的采样次数而获得高覆盖率的效果,因此本文的方法在软件测试中是有用的.

5 相关工作

针对面向C/DC的测试数据生成问题,学者提出了多种处理方法.其中,基于启发式搜索的方法受到了很大的关注.该类方法首先对程序输入进行字符串编码将程序输入域映射到搜索域;然后,通过构建一个目标函数将测试数据生成问题转化为最优化问题[8].目前,基于启发式的搜索方法主要包括希尔攀登法(Hill climbing)、模拟退火法(simulated annealing)、基因遗传法(genetic algorithm)等.希尔攀登[9, 10]是一种局部搜索方法,它从搜索空间中随机选取一个点作为初始值,然后计算该点周围其他点的适应度函数(fitness function)值,并与原始点值进行比较,从中选取最小( 或最大)的对应点作为下一次搜索的起始值.希尔攀登法能够找出初始值周围中最合适的取值,但这个取值可能只是局部最优解,并非全局最优解.全局搜索方法包括模拟退火法[2, 11, 12]和基因遗传法[13, 14, 15],它们的搜索过程类似于希尔攀登法,但它们采用各自的机理减少陷入局部最优的可能性.其中,遗传算法通过模拟自然界生物进化的思想,通过对一组由字符串编码组成的个体进行交叉、变异等操作,不断淘汰适应度值低的个体,并生成适应度值高的个体,从而找到可以覆盖目标条件取值的程序输入.然而,遗传算法要求设定的搜索空间中必须包含满足测试覆盖准则的数据;并且它包含很多参数,参数的设定对算法的效果会产生重要影响;而且,当某些条件的有效解区间只占设定搜索空间极小部分的比例时,基因遗传算法通常不能搜索出可行的解.随机法[16, 17, 18]是一种 比较简单的测试数据自动生成方法,它通过随机的生成大量的测试数据集试图去满足特定的测试覆盖标准.这种无导向的方法简单易行,比较适用于小规模的程序,但测试生成效果常常很不稳定[19, 20].

符号执行技术(symbolic execution)起源于20世纪70年代[21, 22, 23],并广泛应用于程序缺陷检测、测试数据自动生成等领域.传统的符号执行技术[21, 22, 23]通过符号推理将条件表达式转换成符号输入的不等式约束,从而将测试数据生成问题转化成约束求解问题;然后,利用约束求解器求解符号约束系统.当程序规模不断扩大时,该类方法往往存在路径爆炸问题[5].动态符号混合执行结合了符号执行和程序具体执行,扩展了符号执行的能力.典型的动态符号执行以DART[24]和EGT[5, 25, 26]为代表.DART采用了随机的方法选择起始路径,在一定程度上避免路径爆炸问题.EGT是另一种动态符号执行方式,它将约束系统中的一些变量替换为具体的值,然后再求解约束.这种处理方式可以在一定程度上弱化符号约束系统的求解难度,但是这种随意的赋值行为可能会屏蔽掉潜在的解区间[27].近年来,有学者在符号执行技术上提出了改进方案.例如,针对符号执行搜索策略难以覆盖程序路径的问题,并提出了各种符号执行的搜索制导方案[28, 29, 30].这些方案仍然依赖于符号执行的约束求解器来产生测试用例,因此,基于符号执行技术的测试生成方法受限于约束求解器的求解能力,理论上不存在可以求解包含任意非线性约束的约束系统的求解器[31].另外,由于约束求解器的求解精度限制,符号执行在处理含浮点变量 的约束时效果不佳[32].

很多测试生成技术考虑将多种方法相结合改进生成的效果,例如在符号执行技术中引入模型检验方法[33],或者将符号执行和启发式搜索方法结合的测试数据自动生成方法[27, 32, 34, 35].然而,这些方法面向的测试覆盖标准为语句覆盖(SC)或分支覆盖(BC),而并没有应用到条件判定覆盖上.这是由于C/DC准则需要考虑到判定中条件的取值,而以探索路径为指引的符号执行技术在非线性条件的处理上存在不足所致.

6 结束语

软件测试是工业界保障软件质量的主要手段之一,研究自动化的测试用例生成技术,对于节省测试成本具有重要意义.条件判定覆盖准则是各种安全攸关软件测试中常用的测试覆盖准则.针对这一准则,现有的自动测试生成方法存在很多不足.例如:符号执行方法很难处理较为复杂的非线性条件约束,并在处理程序的规模上受到很大限制;希尔攀登法由于在搜索过程中容易陷入局部最优而难以达到满足C/DC准则的高覆盖率;模拟退火法和遗传算法依赖于用户使用过程中的复杂配置,测试用例生成效果具有一定的随机性等.针对这一现状,本文提出了一种线性拟合制导的测试用例生成方法.该方法将程序中的每一个条件判定规范化为一个与零值比较的数值函数,并以插桩与执行获得该函数当前输入下的采样.通过拟合这些采样,我们能够逐步判断出程序中各个条件判定与输入的关系,并利用这些关系生成高覆盖率的测试用例.相对于传统方法,本文方法具有参数配置简易、生成过程高效等优点,并且能够处理逻辑复杂的大规模程序.我们基于Eclipse插件实现了线性拟合制导的测试生成工具原型,在3个开源软件库中的25个真实程序上运行的实验结果表明,本文提出的方法比目前业界测试生成效果较好的遗传算法制导方法能够获得更高的覆盖率与更好的执行效率.

参考文献
[1] Tassey G. The economic impacts of inadequate infrastructure for software testing. National Institute of Standards and Technology, RTI Project, 2002,7007(011).
[2] Xiao M, El-Attar M, Reformat M, Miller J. Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Software Engineering, 2007,12(2):183-239.[doi:10.1007/s10664-006-9026-0]
[3] Bertolino A. Software testing research:Achievements, challenges, dreams. In:Proc. of the 2007 Future of Software Engineering. IEEE Computer Society, 2007. 85-103.[doi:10.1109/FOSE.2007.25]
[4] RTCA. DO-178B software considerations in airborne systems and equipment certification, radio technical commission for aeronautics(RTCA). European Organization for Civil Aviation Electronics(EUROCAE). 1992.
[5] Cadar C, Sen K. Symbolic execution for software testing:Three decades later. Communications of the ACM, 2013,56(2):82-90.[doi:10.1145/2408776.2408795]
[6] Majumdar R, Sen K. Hybrid concolic testing. In:Proc. of the 29th Int'l Conf. on Software Engineering. Washington:IEEE Computer Society, 2007. 416-426.[doi:10.1109/ICSE.2007.41]
[7] Bueno PMS, Jino M. Automatic test data generation for program paths using genetic algorithms. Int'l Journal of Software Engineering and Knowledge Engineering, 2002,12(6):691-709.[doi:10.1142/S0218194002001074]
[8] Michael CC, McGraw G, Schatz M. Generating software test data by evolution. IEEE Trans. on Software Engineering, 2001,27(12):1085-1110.[doi:10.1109/32.988709]
[9] Korel B. Automated software test data generation. IEEE Trans. on Software Engineering, 1990,16(8):870-879.[doi:10.1109/32.57624]
[10] Korel B. Dynamic method for software test data generation. Software Testing, Verification and Reliability, 1992,2(4):203-213.[doi:10.1002/stvr.4370020405]
[11] Mansour N, Salame M. Data generation for path testing. Software Quality Journal, 2004,12(2):121-136.[doi:10.1023/B:SQJO. 0000024059.72478.4e]
[12] Ghani K, Clark JA. Automatic test data generation for multiple condition and MCDC coverage. In:Proc. of the 4th Int'l Conf. on Software Engineering Advances(ICSEA 2009). IEEE, 2009. 152-157.[doi:10.1109/ICSEA.2009.31]
[13] Xanthakis S, Ellis C, Skourlas C, Le Gall A, Katsikas S, Karapoulios K. Application of genetic algorithms to software testing. In:Proc. of the 5th Int'l Conf. on Software Engineering and its Applications. 1992. 625-636.
[14] McMinn P. IGUANA:Input generation using automated novel algorithms. A plug and play research tool. Technical Report, CS-07-14, Department of Computer Science, University of Sheffield, 2007.
[15] Janikow CZ, Michalewicz Z. An experimental comparison of binary and floating point representations in genetic algorithms. In:Proc. of the ICGA. 1991. 31-36.
[16] Linger RC. Cleanroom software engineering for zero-defect software. In:Proc. of the 15th Int'l Conf. on Software Engineering. IEEE Computer Society Press, 1993. 2-13.[doi:10.1109/ICSE.1993.346060]
[17] Ramamoorthy CV, Ho S-BF, Chen W. On the automated generation of program test data. IEEE Trans. on Software Engineering, 1976,3(4):293-300.[doi:10.1109/TSE.1976.233835]
[18] Thevenod-Fosse P, Waeselynck H. STATEMATE applied to statistical software testing. In:Proc. of the ACM SIGSOFT Software Engineering Notes. ACM Press, 1993. 99-109.[doi:10.1145/154183.154262]
[19] Korel B. Automated test data generation for programs with procedures. In:Zeil SJ, Tracz W, eds. Proc. of the ACM SIGSOFT Software Engineering Notes. ACM Press, 1996. 209-215.[doi:10.1145/229000.226319]
[20] McMinn P. Search-Based software testing:Past, present and future. In:Proc. of the 4th IEEE Int'l Conf. on Software Testing, Verification and Validation Workshops(ICSTW). IEEE, 2011. 153-163.[doi:10.1109/ICSTW.2011.100]
[21] Boyer RS, Elspas B, Levitt KN. SELECT-A formal system for testing and debugging programs by symbolic execution. ACM SigPlan Notices, 1975,10(6):234-245.[doi:10.1145/390016.808445]
[22] Howden WE. Symbolic testing and the DISSECT symbolic evaluation system. IEEE Trans. on Software Engineering, 1977,3(4):266-278.[doi:10.1109/TSE.1977.231144]
[23] King JC. Symbolic execution and program testing. Communications of the ACM, 1976,19(7):385-394.[doi:10.1145/360248. 360252]
[24] Godefroid P, Klarlund N, Sen K. DART:Directed automated random testing. In:Proc. of the ACM Sigplan Notices. ACM Press, 2005. 213-223.[doi:10.1145/1065010.1065036]
[25] Cadar C, Ganesh V, Pawlowski PM, Dill DL, Engler DR. EXE:Automatically generating inputs of death. ACM Trans. on Information and System Security(TISSEC), 2008,12(2):10.[doi:10.1145/1455518.1455522]
[26] Cadar C, Dunbar D, Engler DR. KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs. In:Proc. of the OSDI. 2008. 209-224.
[27] Dinges P, Agha G. Solving complex path conditions through heuristic search on induced polytopes. In:Proc. of the 22nd ACM SIGSOFT Int'l Symp. on Foundations of Software Engineering. ACM Press, 2014. 425-436.[doi:10.1145/2635868.2635889]
[28] Li Y, Su Z, Wang L, Li X. Steering symbolic execution to less traveled paths. ACM SigPlan Notices, 2013,48(10):19-32.[doi:10.1145/2544173.2509553]
[29] Marinescu PD, Cadar C. KATCH:High-Coverage testing of software patches. In:Proc. of the 9th Joint Meeting on Foundations of Software Engineering. ACM Press, 2013. 235-245.[doi:10.1145/2491411.2491438]
[30] Su T, Pu G, Fang B, He J, Yan J, Jiang S, Zhao J. Automated coverage-driven test data generation using dynamic symbolic execution. In:Proc. of the 8th Int'l Conf. on Software Security and Reliability(SERE). 2014. 98-107.[doi:10.1109/SERE. 2014.23]
[31] Davis M. Hilbert's Tenth Problem is Unsolvable. American Mathematical Monthly, 1973. 233-269.[doi:10.2307/2318447]
[32] Lakhotia K, Tillmann N, Harman M, De Halleux J. Flopsy-Search-Based floating point constraint solving for symbolic execution. In:Petrenko A, Simão A, Maldonado JC, eds. Proc. of the Testing Software and Systems. Springer-Verlag, 2010. 142-157.[doi:10.1007/978-3-642-16573-3_11]
[33] Su T, Fu Z, Pu G, He J, Su Z. Combining symbolic execution and model checking for data flow testing. In:Proc. of the 37th Int'l Conf. on Software Engineering. ICSE, 2015.[doi:10.1109/ICSE.2015.81]
[34] Inkumsah K, Xie T. Evacon:A framework for integrating evolutionary and concolic testing for object-oriented programs. In:Proc. of the 22nd IEEE/ACM Int'l Conf. on Automated Software Engineering. ACM Press, 2007. 425-428.[doi:10.1145/1321631. 1321700]
[35] Tillmann N, De Halleux J. Pex-White box test generation for net. In:Proc. of the Tests and Proofs. Springer-Verlag, 2008. 134-153.[doi:10.1007/978-3-540-79124-9_10]