引用本文
董国伟, 郭涛, 张普含, 贾依真. 基于路径分析和迭代蜕变测试的Bug检测. 清华大学学报: 自然科学版, 2014, 54(1): 60-67[Guowei DONG, Tao GUO, Puhan ZHANG, et al. Bug detection methods based on path analyses and iterative metamorphic testing[J]. 2014, 54(1): 60-67]  
Permissions
Copyright@2014, 《清华大学学报（自然科学版）》编辑部
版权所有
基于路径分析和迭代蜕变测试的Bug检测
董国伟, 郭涛, 张普含, 贾依真
中国信息安全测评中心, 北京 100085

作者简介: 董国伟, (1983—), 男(汉), 山东, 副研究员。E-mail:donggw@itsec.gov.cn

基金:国家自然科学基金资助项目 (61100047);
摘要

该文旨在基于白盒测试准则,提出能够在尽量复用测试资源、降低测试成本的前提下有效发现程序中错误的蜕变测试方法。任务关键软件的正确性是信息安全的重要组成部分,对其bug的测试至关重要,但Oracle问题经常制约到此类软件的测试。蜕变测试(MT)能够有效解决此类问题,但随机性较大。该文针对二元蜕变关系,提出了2种迭代的蜕变测试算法AESIST和AEMIST, 在依据此2种方法的测试中,上一轮生成的测试用例可以作为下一轮的原始用例而生成新的测试用例,并且所有的测试用例满足蜕变关系全路径覆盖准则(APCEM)。实验结果表明: 2种算法产生的测试用例能够在尽量少地运行程序的情况下有效发现程序中的错误。因此,本文提出的2种迭代蜕变测试算法在程序bug检测方面是高效的。

关键词: 路径分析; 迭代蜕变测试; 蜕变关系; bug检测
中图分类号:TP393 文献标志码:A 文章编号:1000-0054(2014)01-0060-08
Bug detection methods based on path analyses and iterative metamorphic testing
Guowei DONG, Tao GUO, Puhan ZHANG, Yizhen JIA
China Information Technology Security Evaluation Center, Beijing 100085, China
Fund:
Abstract

This paper presents metamorphic testing (MT) methods for program bug detection with white-box criterion to reuse more testing resources and reduce cost. The correctness of mission-critical software is an important part of information security. Security systems often use metamorphic testing to solve the oracle problem with random tests. This article introduces two iterative metamorphic testing algorithms, AESIST and AEMIST, to analyze binary metamorphic relationships based upon APCEM (all-path coverage for every metamorphic relation). The test shows the efficiencies of these methods for bug detection.

Keyword: path analysis; iterative metamorphic testing; metamorphic relationship; bug detection

任务关键软件是广泛应用于航空航天、武器装备、过程控制、核能工业、交通、医疗等领域的一类软件,其正确性对于人们生命财产的安全至关重要。此类软件经常基于一些复杂的数学计算,因此对其进行测试查找bug时通常难以事先获得预期输出,即测试时存在Oracle问题[1]。为了解决此类问题, Chen提出了蜕变测试技术[1],可以通过检测输出之间的关系来测试程序。

蜕变测试技术经历了十几年的发展,取得了巨大的进步。Chen和吴鹏等对特殊用例测试、基于特殊用例和随机用例的蜕变测试进行了对比[2,3]; 吴鹏还提出了一种基于用例链的迭代蜕变测试技术[4]; 之前作者也提出了一系列白盒蜕变测试方法[5]; Chen和Mayer介绍了如何选取有效的蜕变关系[6,7]; 蜕变测试与广义符号执行[8]、基于缺陷的测试[9]等技术结合使用也具有良好的效果; 由于其有效性,蜕变测试已被广泛地应用于数值计算软件[10]、图论软件[11]、计算机图形处理软件[11]、编译器[11]、面向对象程序[12]等的测试中。

通过分析可知,现有的蜕变测试技术中测试用例大多使用随机的方式生成,没有充分考虑程序路径覆盖的问题,因此测试效率往往较为低下。

本文提出了2种启发式的迭代蜕变测试方法,分别使用一个和一组测试用例作为原始用例,而后通过蜕变关系迭代地计算出新的测试用例进行后续测试,如此反复直至生成的所有测试用例满足蜕变关系全路径覆盖准则(APCEM), 而后使用这些测试用例测试程序,发现其中的正确性bug。

1 APCEM可满足性迭代算法
1.1 基本概念

定义1 (蜕变关系)[1] 假设程序 P用来计算函数 f。 x1, x2,…, xn( n>1) 是 f的 n个变量。若 x1, x2,…, xn之间满足关系 r时, f( x1), f( x2),…, f( xn)满足关系 rf, 即:

r(x1,x2,…,xn)⇒rff(x1),f(x2),…,f(xn)).(1)

成立,则称 ( r, rf) 是 P的蜕变关系[1]。显然,如果 P是正确的,那么它一定满足:

r(I1,I2,…,In)⇒rfP(I1),P(I2),…,P(In)).(2)

其中: I1, I2,…, In是程序 P中对应于 x1, x2,…, xn的输入。蜕变测试即是一种根据上式来检测 P的正确性的测试方法[1]。

本文只针对二元蜕变关系[5](式(1)和式(2)中的 r是一个二元等式关系的情况,即 r( I1, I2)) 进行研究。如果用 I1表示某用例,那么 I2 =FU ( I1,( r, rf))表示 I1基于蜕变关系( r, rf)的衍生用例,同理, I1 =FU ( I2,( r, rf))也成立; 由蜕变关系及满足它的2个用例组成的三元组(( r, rf), I1, I2)表示一个蜕变测试用例[5]。

定义2 (蜕变域)[5] 假设 D为程序 P的输入域, D'⊆ D, 在 D'上可以对 P进行蜕变测试,则称 D'为程序 P的蜕变域,记作 DMT( P), 称 D - D'为 P的非蜕变域,记作 DUMT( P)[5]。

下文算法中,根据待测程序 P构造的二元蜕变关系记作MR i( i∈[1, m], m为蜕变关系数); 测试用例所组成的用例集记作TC; 每条可执行路径记作Path j( j∈[1, n], n为路径数), 执行Path j的输入所组成的集合,即Path j对应的输入域记作DS(Path j); 以输入 I运行 P时的执行路径记作ExcPath( I)。

定义3 (蜕变关系的适用区域)[5] 假设蜕变关系MR, 若对于∀ I1∈ δ⊆ DR(MR), 无论对 P置入何种变异, I1、 FU( I1,MR)及它们所对应的输出均满足MR, 则称 δ为MR的测试盲区,记作 Dbl(MR), 称 DR(MR) -Dbl(MR)为MR的适用区域,记作 Dapp(MR)。

例如,程序double square (double a,double b) 实现了计算矩形面积 S( x, y) 的功能:

S(x,y)=x·y(x>0)∧(y>0)Error否则

为其构造一条二元蜕变关系

MRs:((x',y')=(y,x),S(x',y')=S(x,y)).

即交换2条边的值,矩形面积应当不变,其中 DR(MR s) ={( a, b) | ( a>0)∧( b>0)}。当在{( a, b) | a=b>0}中选取原始输入 I时,即使对程序植入将” x-y”改为” x-y”的变异, I、 FU( I,MR s)及它们的输出也同样满足MR s, 由定义3可知, Dbl(MR s) ={( a, b) | a=b>0}, Dapp(MR s) ={( a, b) |( a>0)∧( b>0)∧( a≠ b)}[5]。

定义4 (蜕变关系全路径覆盖准则APCEM)[5] 使用测试用例集TC测试程序 P时,对于∀MR i和Path j, 若 Dapp(MR i)∩DS(Path j)≠⌀, ∃(MR i, Ii1, Ii2)∈TC, 使得(ExcPath( Ii1) =Path j)∨(ExcPath( Ii2) =Path j)成立,则称TC满足APCEM[5]。

APCEM是一种较为严格的白盒蜕变测试准则,它要求使用每条蜕变关系测试时能够涉及到的所有路径都要被覆盖到。该准则是基于“使得2次执行尽可能不同的蜕变关系比较有效[6]”的原则提出的。

为了提高蜕变测试中测试用例的利用率,吴鹏提出了链式地使用蜕变关系的IMT算法[4],具体描述如下: 假设 T={ t1, t2,…, tk-1}和mr1,mr2,…,mr n是为待测程序构造的初始的测试用例集和 n条蜕变关系, IMT算法首先使用每条蜕变关系mr i( i=1,2,…, n) 和 T中的每条用例 tj( j=1,2,…, k-1) 来测试程序,并将生成的衍生用例添加到 T中以形成新的测试用例集 T', 然后使用每条mr i及所有满足 ( tk∈ T'∧ tk∉ T) 的测试用例 tk来测试程序,将得到的衍生用例添加到 T'中,重复上述过程 n次即停止测试。IMT算法的本质是针对 T中每条测试用例 tj, 都基于每种可能出现的蜕变关系序列进行一组测试。虽然实验结果表明IMT算法检测bug的能力令人满意,但是高昂的时间代价极大地制约了其使用范围,在待测程序完全正确的情况下,该算法需要对程序进行( T· n·( nn-1) /( n-1))次测试[4]。

在此使用APCEM准则规范IMT的测试过程,使得每次产生的衍生用例中只有部分被选出并应用于后面的测试,这样既可以生成满足APCEM准则的测试用例集,还能够避免IMT算法中测试用例数量呈指数级增长的问题。本节提出了2种算法,即APCEM可满足性单点迭代算法AESIST和APCEM可满足性多点迭代算法AEMIST。前者每次从未测试域中选取某个输入作为起点迭代地测试程序; 后者每次随机地生成一组输入作为初始用例,而后循环地测试程序。使用2种算法均能得到满足APCEM准则的蜕变测试用例集。

1.2 AESIST算法

使用APCEM可满足性单点迭代算法AESIST测试程序时,为待测程序随机生成的第一个测试用例被称作起始测试用例; 如果在测试过程中,根据AESIST算法规定的条件,所有衍生测试用例都不能被选取用以进行后继测试,而此时又不满足测试结束的条件,则需要随机生成一个新的用例作为后继测试的起点,则该随机产生的测试用例被称作初始测试用例。

AESIST算法首先为待测程序的每条蜕变关系初始化一个用以记录未测试部分的区域,而后循环地选择测试用例、计算衍生用例、测试程序,如此反复直到所有的未测试区域为空。每轮测试都从当前所有关系的未测试区域的并集中随机地选取一个输入作为初始测试用例,而后在生成的衍生用例中挑选能使得未测试区域缩小的进行后继测试,详细过程如算法1所示。

AESIST算法的时间复杂性为 O ( m· n+n· p), 其中 m是蜕变关系的数量, n 是待测程序 P可执行路径的数量, p是程序路径中结点个数的最大值 (符号执行时需要检查执行到的每条语句)。假设AESIST算法生成的蜕变测试用例集为TC, 则 |TC |≤ m· n。

1.3 AEMIST算法

使用APCEM可满足性多点迭代算法AEMIST测试程序时,为待测程序随机生成的第一组测试用例被称作起始测试用例组; 如果在测试过程中,根据AEMIST算法规定的条件,当前所有测试用例都不能被选取用以进行后继测试,而此时又不满足测试结束的条件,则需要随机生成一组新的用例作为后继测试的起点,则这一组随机产生的测试用例被称作初始测试用例组。

AESIST算法虽然可以生成满足APCEM的测试用例集,但是所有用例都是由少数几个起始或初始测试用例(单点)衍生出来的,这可能会使得所有测试用例在结构、数值等方面具有很大的相似性,从而影响测试效果。AEMIST算法使用随机的方法生成一组测试用例作为每轮迭代测试的初始用例组,这样可以使用随机的方法弱化用例间的相似性,详见算法2。

AEMIST和AESIST这2种算法只是在起始/初始测试用例(组)的选取上有所差别,中间过程的操作步骤几乎完全相同。AEMIST算法的时间复杂性为 O( k + m· n + n· p), 其中 k是每次随机生成的初始测试用例个数的最大值,其他符号的含义与上文相同。假设AESIST算法生成的蜕变测试用例集为TC, 则|TC|≤ m· n。

2 实例分析
2.1 实例说明

本节通过实例分析的方法来表明2种迭代算法的效率。TriSquareU是一个计算三角形面积的程序,它首先判断三角形是锐角三角形、钝角三角形,还是直角三角形,而后计算其面积,具体代码如图1所示。

图1 被测程序代码

通过分析可知,程序中需要使用蜕变方法测试的路径有6条,表1给出了具体的路径信息,其中Tir={(min,mid,max) | (min>0)∧(mid>0)∧(max>0) ∧(min+mid>max)}。

表1 程序TriSquarePlus的路径信息

此处为待测程序构造了7条蜕变关系,如表2所示。其中mr2-4基于平行四边形的性质[5],而mr5-7是根据三角形的面积等于底乘以高除以2的性质构造出来的,如图2, 三角形 ABC的三边分别为 a、 b、 c, AB对应的高是 h, 假设将 HC延长到 D点,使得 DH的长度为2 h, 则三角形 ABD的面积是三角形 ABC的2倍,由直角三角形各边之间的等式关系可以容易地求出 AD和 BD的长度。

图2 mr<sub>5-7</sub>的构造原理

表2 基于TriSquareU功能构造的蜕变关系

为了能够对AESIST和AEMIST这2种算法生成的测试用例集的性能有一个清晰的对比,本节使用变异分析的方法来检验实验结果,将4个变异分别置入TriSquareU的4条不同的路径中,具体为:

变异1 将第11行代码中的“pow(min/2,2)”替换为“pow(mid/2,2)”;

变异2 将第18行代码替换为“return Sqrt(( p-max)*( p-mid)*( p-min))”;

变异3 将第25行代码替换为“return max* h”;

变异4 将第27行代码替换为“double x=(pow(max,2) +pow(min,2)-pow(mid,2))/(2*max); ”。

图3是某次使用AESIST算法测试TriSquareU时,生成用例过程的示意图,图中每个三元组表示一个测试用例(三角形三边), 测试用例右侧的数字是该用例执行的路径(见表1); 连线旁的数字表示所使用的蜕变关系的标号,例如4表示mr4; 底线是虚线的衍生用例与它的原始用例执行相同的路径,所以此类用例在后继测试中不被使用; 底线为实线的衍生用例不在 ⋃i=17UTArea i中,因此也不在后继测试中使用; 黑色实心三角表示它所对应的原始测试用例不在相应蜕变关系的未测试域(UTArea i)中,因此无需计算该用例的衍生用例。经过4轮测试后,算法生成的蜕变测试用例集满足APCEM准则。使用AEMIST算法测试TriSquareU时与图3所示的过程类似,只不过每次迭代从 k个随机生成的测试用例开始,在此不再赘述。

图3 使用AESIST算法测试TriSquareU的过程

2.2 实验结果分析

本文设计了3组实验来对比2种算法的测试效果。第一组实验中,使用这2种算法对每个含有变异 i( i=1,2,3,4) 的TriSquareU基于mr1-7分别测试20次,起始测试用例(组)随机产生。第二组实验中,也使用这2种算法对每个含有变异 i ( i=1,2,3,4)的TriSquareU基于mr1-7分别测试20次,但规定起始测试用例(组)必须要执行Path1、 Path2、 Path4或Path5。第三组实验中,使用这2种算法对作者另一篇论文中[5]含有变异 i( i=1,2,3,4)的TirSquare基于其中的mr1-4分别进行20次测试。

错误发现率[5]用来计算在使用测试用例集TC测试变异方法 m时,能够发现错误的测试用例数 (即测试失败的次数) Nf在涉及错误路径的测试用例 Nfp中所占的比重,反映了TC发现每个变异的能力,记为:

FPD(m,TC)=NfNfp.

下文中以 FPDialg( i=1,2,3,4)来表示使用算法alg生成的测试用例集针对含有变异 i的待测程序的FPD值, alg是AESIST或AEMIST。通过实验,可以得出如下几点结论:

1) 使用2种算法测试程序时,选取能够执行复杂路径的用例作为起始用例(组)时,测试效果更好。

图4给出了第一组和第二组实验中2种算法生成的测试用例的数量 (程序执行次数), 第二组实验中生成的测试用例的数量 (大部分集中于36~39) 普遍少于第一组 (大部分集中于40~46), 而检错能力两者却没有明显差距(85%< FPD1AESIST,AEMIST<90%, FP D2AESIST,AEMIST=100%, FPD3AESIST,AEMIST=75%, 90%< FPD4AESIST,AEMIST<95%)。通过分析可知,在程序TriSquareU中, Path1、 Path2、 Path4、 Path5的路径条件都含有等式关系,约束力比较强,而Path3和Path6的路径条件都是不等式关系,约束力比较弱。由于第一组实验随机生成的起始测试用例(组)绝大多数都执行Path3或Path6, 并且使用这些用例也很难得到满足Path1,2,4,5等式关系的衍生用例,因此该组实验中存在着大量原始用例和衍生用例执行相同路径的情况; 而在第二组实验中,起始用例(组)执行Path1,2,4,5, 并且由它们可以很容易地根据蜕变关系生成满足Path3,6路径条件的衍生用例,因此原始用例和衍生用例执行相同路径的情况较少。所以第一组实验生成的测试用例的数量明显多于第二组。由此看来,在使用AESIST或AEMIST算法测试程序时,要尽量使用能够执行复杂路径的用例作为起始测试用例(组)。

图4 使用AESIST和AEMIST算法测试TriSquareU时生成测试用例

2) 随机生成起始用例(组)时, AESIST算法产生的测试用例数量较少; 而使用能够执行复杂路径的用例作为起始用例(组)时, 2种算法生成的测试用例数量相差不大。

图4a表明第一组实验中AESIST算法生成的用例的数量普遍较少(三角形结点折线大部分在方块结点折线下方), 而图4b中2条折线交错在一起,没有明显差别。分析可知,在以随机值作为起始用例(组)时,通常在后继测试中还要多次生成初始测试用例(组), 如图3所示, AESIST算法每次产生一个初始用例,只有当其所衍生出的所有测试用例都不能使得未测试区域减小时才生成下一个初始用例; 而AEMIST算法每次生成多个初始用例 I0, I1,…, Ik, 那么以 Ii为起点迭代所生成的衍生用例 Ii'可能与 Ij( i, j=0,1,…, k, 且 i<j) 具有相似的属性 (比如 Ii', Ij执行相同的路径), 而在队列 Qimp(算法2) 中 Ij排列在 Ii'的前面,即测试时首先选取 Ij, 而 Ii'不再被使用,这种情况下生成的测试用例的数量比使用 Ii'时多1。因此,随机生成起始用例时, AESIST算法产生的测试用例数量较少。

3) AEMIST算法生成的测试用例集具有更强的错误检测能力。

图5是第三组实验中使用2种算法测试含有作者之前文中[5]的变异1和变异3的TriSquare程序时所得的FPD值。不难看出,对于这2个变异, AEMIST算法的检错能力更强。由分析可知,就程序TriSquareU而言,由于为其构造的蜕变关系mr2-7含有更多待测程序的语义信息[9],所以使用这2种算法测试程序时所得到的FPD值差别不大,并且4个变异都能被检测出来,即变异检测率MS[5]都是100%; 而另一方面,第三组实验中测试作者前期工作[5]的TriSquare所使用的蜕变关系m r1-45的构造原理非常简单,含有待测程序的语义信息也较少,这种情况下, 2算法执行时FPD值的差别比较明显, 20次测试中还有2次 FP1AESIST的值为0。出现上述差别的原因是: 基于简单的蜕变关系测试程序时, AEMIST算法使得测试用例之间的相似度由于随机程度的提高而减小,因此更有利于错误的检测。

图5 使用AESIST和AEMIST算法测试TriSquareU时的FPD值对比

4) 使用APCEM可满足性迭代算法生成的测试用例的数量少于传统方法。

对于程序TirSquareU, 如果使用传统方法进行测试,需要48条测试用例,即执行程序48次(6条可执行路径、 7条蜕变关系, 即生成6条原始测试用例、 42条衍生用例), 但是从图3可以看出使用迭代算法生成的用例的数量绝大多数情况下都小于48。

3 结 论

任务关键软件的正确性是信息安全的重要组成部分,对其bug的测试至关重要,但Oracle问题经常制约到此类软件的测试。蜕变测试(MT)能够有效解决此类问题,但随机性较大。本文提出了2种启发式的迭代蜕变测试方法,它们分别使用一个和一组测试用例作为原始用例,而后通过蜕变关系迭代地计算出新的测试用例进行后续测试,如此反复直至生成的所有测试用例满足蜕变关系全路径覆盖准则(APCEM), 而后使用这些测试用例测试程序,发现其中的正确性bug。通过针对计算三角形面积的程序进行实验表明, 2种算法对于程序中预置的多个bug均可以有效地检测出来,而且所使用的测试用例的数量比传统方法少。因此可以得出结论,使用本文中提出的方法可以使用较少的测试资源有效地发现程序中的错误。

The authors have declared that no competing interests exist.

参考文献
[1] Chen T Y, Cheung S C, Yiu S M. Metamorphic Testing: A New Approach for Generating Next Test Cases, Technical Report HKUST-CS98-01 [R]. Hong Kong, China: Hong Kong University of Science and Technology, 1998. [本文引用:5]
[2] Chen T Y, Kuo F C, Liu Y, et al. Metamorphic testing and testing with special values [C]// Proceedings of the 5th International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD'04). Beijing, China: IEEE Computer Society, 2004: 128-134. [本文引用:1]
[3] 吴鹏, 施小纯, 唐江峻, 等. 关于蜕变测试和特殊用例测试的实例研究 [J]. 软件学报, 2005, 16(7): 1210-1220.
WU Peng, SHI Xiaochun, TANG Jiangjun, et al. Metamorphic testing and special case testing: A case study[J]. Journal of Software, 2005, 16(7): 1210-1220. (in Chinese) [本文引用:1] [CJCR: 2.18]
[4] Wu P. Iterative metamorphic testing [C]// Proceedings of the 29th Annual International Computer Software and Applications Conference (COMPSAC'05). Edinburgh, UK: IEEE Computer Society, 2005: 19-24. [本文引用:3]
[5] 董国伟, 聂长海, 徐宝文. 基于程序路径分析的有效蜕变测试[J]. 计算机学报, 2009, 32(5): 1002-1013.
DONG Guowei, NIE Changhai, XU Baowen. Effective metamorphic testing based on program path analysis[J]. Chinese Journal of Computers, 2009, 32(5): 1002-1013. (in Chinese) [本文引用:15] [CJCR: 2.219]
[6] Chen T Y, Huang D H, Tse T H, et al. Case studies on the selection of useful relations in metamorphic testing [C]// Proceedings of the 4th Ibero-American Symposium on Software Engineering and Knowledge Engineering (JIISIC'04). Madrid, Spain: IEEE Computer Society, 2004: 569-583. [本文引用:2]
[7] Mayer J, Guderlei R. An empirical study on the selection of good metamorphic relations [C]// Proceedings of the 30th Annual International Computer Software and Applications Conference (COMPSAC'06). Chicago, USA: IEEE Computer Society, 2006: 475-484. [本文引用:1]
[8] Chen T Y, Tse T H, Zhou Z Q. Semi-proving: An integrated method based on global symbolic evaluation and metamorphic testing[J]. ACM SIGSOFT Software Engineering Notes, 2002, 27(4): 191-195. [本文引用:1]
[9] Chen T Y, Tse T H, Zhou Z Q. Fault-based testing without the need of oracles[J]. Information and Software Technology, 2003, 45(1): 1-9. [本文引用:2] [JCR: 1.328]
[10] Chen T Y, Feng J, Tse T H. Metamorphic testing of programs on partial differential equations: A case study [C]//Proceedings of the 26th Annual International Computer Software and Applications Conference (COMPSAC'02). Oxford, England: IEEE Computer Society, 2002: 327-333. [本文引用:1]
[11] Zhou Z Q, Huang D H, Tse T H, et al. Metamorphic testing and its applications [C]// Proceedings of the 8th International Symposium on Future Software Technology (ISFST'04). Xi'an, China: IEEE Computer Society, 2004: 23-28. [本文引用:3]
[12] Chen H Y, Tse T H, Chan F T, at el. In black and white: An integrated approach to class-level testing of object-oriented programs[J]. ACM Transactions on Software Engineering and Methodology, 1998, 7(3): 250-295. [本文引用:1] [JCR: 1.472]