（计算机应用技术专业论文）两两组合覆盖测试用例生成研究及优化.pdf

上海师范大学硕士学位论文两两组合覆盖测试用例生成研究及优化 摘要 软件测试作为软件开发过程中的重要环节，是保证软件质量，提高软件可靠 性的重要手段。由于计算机技术的不断发展，软件的规模和复杂度的不断提高， 软件测试也渐渐成为一项耗费大量资源的活动。由此，用最少的代价达到最大的 测试效果是软件测试中最重要的问题之一。经验以及实践表明，两两组合覆盖测 试是对各种软件系统测试的一个实际而有效的方法。 目前国内外对两两组合覆盖测试用例生成方法已有了广泛的研究，主要有以 下六种算法：正交拉丁方算法、a e t g 算法、口0 算法、w i l l i a m s 算法、p s s t 算法和k 曲a y a s h i 算法。p 0 算法以参数为对象，在每次扩展时都能保持测试用 例的最优化，具有很好的扩展性。虽然i p o 算法有不少优势，但是其还存在以下 几个影响性能的问题，例如：测试用例水平扩展次序的问题、测试用例覆盖两两 组合个数安排的问题和待扩展参数扩展次序的问题等。 就上述问题，本文在分析总结国内外现有两两组合覆盖测试生成方法优缺点 的基础上，提出了一种以p o 算法思想为基础的混合i p 0 算法( h 口o 算法) 。 h i p o 算法继承i p o 算法高可扩展性的优点，引入测试用例贡献度的概念，采用 优先排序、最小化算法等方法。论文深入研究和优化上述提出的三个问题，使得 算法获得更优的结果。 本文利用n e t 技术实现了一个基于该方法的测试用例生成工具，并在随后的 初步实验中证明了h i p o 算法是有效的。 。 最后本文将h i p o 算法应用到银行反洗钱系统的测试用例生成中去，获得了 比以往优秀的结果。 关键词：软件测试；测试数据；两两组合覆盖测试；i p o 算法 i i a b s t r a c t s o f 细a r et e s t i n gi sa ni m p o r t a n tp a no fs o f t w a r ed e v e l o p m e n t i ti sa l s 0a n e s s e n t i a lm e 锄st oe n s u r et h eq u a l i t y0 fs o f 细a f ea n dt 0i m p r o v et h er e l i a b i l i t y0 f s o f t w a r e d u et ot h ed e v e l o p m e n t0 fi n f o 姗a t i o nt e c h n o l o g y m es c a l ea n dc o m p l e x i t y o fs o f 时a r ek e e po ni n c r e a s i n g a sar e s u l t ，s o f 研a r et e s t i n g 伊a d u a l l yc o n s u m e sm o f e a n dm o r er e s o u r c e s t oo b t a i nt h eb e s tt e s t i n gr e s u l tw j t ht h el e a s tc o s ti s 伽eo ft h e m o s ti m p o n a n ti s s u ei i lt e s t i n g i ti sp r o v e dm a tp a i f - w i s et e s t i n gi sap r a c t i c a la l l d e f f e c t i v ew a yt ot e s ta l lk i n d so fs o f t 、 ，a r es y s t e m s e x t e n s i v er e s e a r c h e sh a v eb c e nm a d eo nt h eg e n e r a t i o no fp a i r w i s et e s t i n g t h e r ea r es i xm a i na l g o r i t h m so nt h a t ，o n h o g o n a la r m y s ，a e t ga l g o r i t h m ，口o a l g o r i t l u l l ， w i l l i 锄s a l g o r i t l u n ， p s s ta l g o r i t l u i l锄dk o b a y a s h i sa l g o r i t l l m c o m p a r e dw i t ho t h 盯s i xa l g 耐t l l i n s ，i p oa l g o r i t 虹i sb a s e do np a r a m e t e r s 觚dc a j l e n s u r et h eo p t i m i z a t i o no ft e s tc 蕊e si ne a c he x p 觚s i o n t h o u g l li p 0a l g o r i t l l i nh a sa l o to fa d v 柚t a g e s ，i ts t i l lh a ss e v e r a jd e f e c t sw h i c ha 疵c t si t sp e b 彻a i l c e f o r i i l s t 柚c e ，t h eh o r i z o n t a l 母d w t ho fp a * w i s et e s t i n 岛t h ec o m b i n a t i o n0 fp a m w i s e t e s t i n gc a s e sa n dt h ee x t e n s i o ns e q u e n c e0 ft h ep a r a m e t e r st 0b ee x t e n d e da l l 柚陀c ti t s p e r f b 珊a n c c a 血e ra n a l y z i n g 孤ds u m m a r i z i n gt h em e r i t sa n dd e f e c t s0 fp a i r - w i s et e s t i n g ， w ep r o p o s eah i p 0a 1 9 0 r i t h mb a s e do n 口0a 1 9 0 r i t h mt os o l v et h o s ep r o b l e m s t h e h i p oa 1 9 0 f i t h mi i 山e r i t st h ea d v a i l t a g eo 仆i 曲e x t e n s i o no ft h ei p oa l g o r i t l l i l l a n di t i i l t r o d u c e st h ec o n t r i b u t i o ne x t e n to ft e s t i n gc a s e sw h i c hp r o v i d e st h eb a s i sf o r j u d g i n gt e s t i n gc a s e s m e a n w h i l e ，t h eh i p oa l g o r i t l u i la d o p t s t l l em e t h o d so f p r e f e r e n t i a ls e q u e n c e 嬲w e ua sm i n i m i z a t j o na l g o r i t l u n t 0o p t i m i z et h ep r o b l e m s a b o v e a sar e s u l t ，i tp e 怕衄sm u c hb e t t e r w ed e v e l o pt h et e s tc a s e 星r e n e r a t i o nt o o lb a s e do nt h 9h i p 0a l g o r i t h mb ym e a n s 0 f n e tt e c h n 0 1 0 9 y w ep r o v ei t se f f e c t i v e n e s si nt h ef o l l o w i n ge x p e r i m e n t t h eh i p 0a l g o r i t h mw 嬲u s e di 1 1t h ea n t i m o n e yl a u n d e f i n gs y s t e m a i l d g e n e r a t e sa b e t t e rr e s u l t k e y w o r d s ：s o f t w a r et e s t i n g ；t e s t i n gd a t a ；p a i rw i s et e s t i n g ；i p oa 1 9 0 r i t h m 上海师范大学硕士研究生学位论文 两两组合覆盖测试用例生成研究及优化 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者日期：沙多b 、岬 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 储吲新虢砰飙 沙孑6 、( 1 j 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 1 1 研究背景 第一章绪论 随着现代信息技术的发展，计算机的应用已经渗透到社会生活的各个方面， 甚至人类生活的各个领域。软件在航空、航天、通讯、交通、金融等关键领域的 应用也日益广泛，这些领域对软件可靠性和安全性都有很高的要求，为保证软件 能够安全、可靠的运行，必须选择合适的测试方法对软件进行充分的测试。- 由于软件的规模和复杂程度的不断加剧，软件测试也逐渐演变成耗费巨大资 源的活动。对软件系统进行全覆盖测试是相当困难的。统计表明，在典型的软件 开发项目中，软件测试的工作量往往占软件开发工作总量的5 0 以上，并因此而 开销3 0 5 0 的总成本l 。 与此同时，测试中的许多操作是重复性的、非智力性的和非创造性的，并要 求做准确细致的工作。这些操作都不是人类所擅长的，而计算机却能够自动高速 而又精确地处理各类信息和数据，从而避免测试人员因为厌烦和疲倦而产生的错 误。对于那些步骤与方法相对固定的测试完全可以采用自动测试方法，由计算机 代替人工去完成。 由此可见，如何能高效的自动的生成尽量少测试用例并实施，用尽可能少的 代价达到最大的测试效果成为众多研究机构和人员关注的问题。 实践表明：软件系统的故障往往是由一些难以预料的系统因素及其相互作用 而引起的。软件测试就是对系统因素的各种组合情况进行充分覆盖的测试。研究 发现，有2 0 一4 0 左右的软件故障是由某个系统参数引发，2 0 4 0 左右的故 障由某两个参数的相互作用引发，由此存在大约7 0 的软件故障是由一个或两个 参数的作用引起的【2 1 。 因此，两两组合覆盖测试是对各种软件系统测试的一个实际而有效的方法 【3 圳。两两组合覆盖测试要求系统的任何一对输入参数，它们每一个有效值的组 合都必须被至少一个测试用例所覆盖。 为了简要说明它的概念，我们考察这样一个系统，该待测系统中有三个参数 a ( a 。，a 2 ) 、b ( b - ，b 2 ) 和c ( c 1 ，c 2 ，c 3 ) ，括号内是它们的有效取值。对于参数a 和b ， 它们之间的两两组合共有a 1 8 1 、a 1 8 2 、a 2 8 1 和a 2 ，b 2 四对，那么测试集合( a 1 ，b 1 ) 、 ( a ，b 2 ) 、( & ，b 1 ) 和( ，b 2 ) 就是满足两两组合覆盖要求的测试用例集合。若再加入 参数c ，则集合将进一步扩大。假定t = 【( a 1 ，b l ，c 1 ) ，( a 1 ，b 2 ，c 2 ) ，( a 2 ，b 1 ，c 3 ) ， ( a 2 ，b 2 ，c 1 ) ，( a 1 ，b 2 ，c 3 ) ，( 赴，b - ，c 2 ) 。由于三个参数间所有的两两组合都被包含于 集合t 中，所以集合t 就是满足两两组合覆盖要求的测试用例集合。很显然， 上海师范大学硕士研究生学位论文 两两组合覆盖测试用例生成研究及优化 满足两两组合覆盖要求的测试用例集合不是唯一的，例如t = ( a 1 ，b 1 ，c 2 ) ， ( a l ，b 2 ，c 2 ) ，( a 2 ，b 1 ，c 3 ) ，o 电，b 2 ，c 1 ) ，( a 1 ，b 2 ，c 3 ) ，( a 2 ，b 1 ，c 2 ) ，( a 1 ，b 2 ，c 1 ) ，o 电，b 1 ，c 1 ) 】、 t ”= ( a 1 ，b 1 ，c 2 ) ，( a 1 ，b 2 ，c 2 ) ，( a 2 ，b 1 ，c 3 ) ，( a 2 ，b 2 ，c 1 ) ，( a 1 ，b 2 ，c 3 ) ，( a 2 ，b 1 c 2 ) ， ( a 1 ，b 2 ，c 1 ) ，( & ，b 1 ，c 2 ) ) 等。 为了减少测试开销，我们希望能得到一个尽可能小的，满足两两组合覆盖要 求的测试集。然而可以证明，要获得这样一个最优的测试集合是一个n p c 问题 【7 1 。由此，我们的目标是采用一定的策略和算法来获得一个最优或接近于最优的 测试集。 1 2 国内外研究现状 基于两两组合覆盖的测试用例集合生成技术研究，主要是研究应用组合设计 方法对软件进行组合测试。一开始，主要是将数学中正交拉丁方的特性应用于软 件测试，取得了比较好的效果，形成了正交拉丁方算法【9 。1 7 j 。 随后在两两组合覆盖测试数据生成技术的发展中，生成方法主要有启发式方 法和代数方法。美国贝尔实验室的d m c o h e n 与s r d a l a l 等提出的a e t g 算法 【7 】【搏2 1 】和北卡罗莱纳卅i 大学的yk i 与k c t a i 等提出的i p o 算法【2 2 】【冽都属于启 发式方法，它的特点是非常灵活、有效。同时加拿大渥太华大学的a w ：w _ i l l i 锄s 提出了w i l l i a m s 方法【弘”】和日本大阪大学的n k o b a y a s h i 和t t s u c h i y a 等提出了 k 曲a v a s h i 方法【2 8 】。上述两种方法都属于代数方法，都可以有效地生成满足要求 的测试数据，并且在某些情况下其效果要比启发式方法好。代数方法是启发式方 法的一种重要补充，它的特点是非常简洁。我国的史亮等提出的p s s t 算法【2 9 】 将解空间映射成一个树，它的基本思想是找出相互间重叠数不超过1 的所有解， 这种算法给我们提供了一个解决问题的新思路。 上述六种主要算法都有各自的优缺点，总结如下： ( 1 ) 正交拉丁方算法利用组合数学中拉丁方的特殊性质来构造满足两两组合 覆盖要求的测试集。它的优点在于构造简单，存在现实中的数学模型【3 0 】，并且在 已知参数个数及可取值情况下就可准确计算出满足两两组合覆盖要求的测试集 大小。不足之处是在实际系统中，往往为了满足拉丁方数学上的特性，因此在构 造算法中常常需要添加“无关值”，从而导致增加额外的测试用例。 ( 2 ) a e t g 算法先产生一组待测的测试用例，然后利用贪心算法( g r e e d y g o r i t h m ) 选择其中一个能覆盖最多未被覆盖到的两两组合1 3 。循环迭代直至所 有的两两组合都被覆盖。相对于其它算法，它获得的结果是较优的瞄】。但是a e t g 算法的在时间复杂性上不如口o 算法。 d ) i p o 算法采用贪心算法，是基于参数顺序的渐进扩展的两两组合覆盖测 2 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 试用例生成方法。与其它算法一次生成所有测试用例的方式不同，i p o 算法是以 参数为中心的，这样就有利于系统的扩展，且该方法在时间复杂度上略优于 a e t g 算法，但是结果不是较优的。 ( 4 ) w i l l i 锄s 算法以正交拉丁方算法为基础，在正交矩阵的基础上加入了分 区等因素。它改进的算法在时间复杂度上比较稳定，受参数规模等因素影响较小， 且生成测试用例集合的规模同i p o 算法基本相当【2 5 】；不足之处是该算法只适合 参数规模较小的系统。 ( 5 ) p s s t 算法将解空间映射成一个树，它的基本思想是找出相互间重叠数不 超过1 的所有解，然后对其进行扩展。p s s t 算法将启发式方法和代数方法的优 点结合起来，并尽量克服两者的不足。该算法也可以允许测试人员预先指定一组 测试用例，然后在此基础上进行扩展以生成两两组合覆盖表。该算法具有较强的 针对性和灵活性。但由于该算法终究还是属于启发式算法，所以不能保证每次测 试用例生成的结果是最优的。 ( 6 ) 同、矾1 1 j 锄s 算法相似，k 0 b a y a s l l i 算法也是通过一些基本正交表和特征 块作为基本成分，来构造满足要求的复杂两两组合覆盖表。k o b a v a s h i 算法的基 本成分是正交表o 表，并通过。表的交叉重叠来构造新的两两组合覆盖表。虽 然k | 0 b a y a s h j 算法在某些情况下能获得最优解，但是其还是不能避免由于拉丁方 特性所带来的缺陷。 1 3 论文研究内容 论文首先详细介绍和分析了六种主要的两两组合覆盖测试数据生成算法，并 通过分析比较，总结出每种算法的优缺点。在研究各种算法的同时，我们发现相 对于其它算法，i p o 算法兼顾了性能和效率，且具有更好的可扩展性，但是口o 算法缺少了对影响其性能相关问题的研究，包括测试用例水平扩展次序的问题、 测试用例集合整体覆盖安排的问题和待扩展参数的扩展次序问题。 本文通过实验分析和总结，提出了一个新的混合算法- h i p o 算法。h i p o 算法在继承m 0 算法优势的基础上，弥补了上述三个不足，取得了较优的实验结 果。h i p o 算法引用了遗传算法中个体适应度的思想，对测试用例集合中的每一 个测试用例都设置了一个贡献度的指标( 详见第3 2 1 节) ，以此来评价该测试用 例对整个集合的贡献程度，为以后的策略提供了评价的基础。 最后本文利用n e t 技术实现了一个基于该方法的测试用例生成工具，并在之 后的初步实验以及a m l 应用中，验证h i p o 算法的有效性。 3 上海师范大学硕士研究生学位论文 两两组合覆盖测试用例生成研究及优化 1 4 主要创新点 本文从理论联系到实际，深入分析了两两组合覆盖问题和各种生成策略，在 此基础上提出了改进算法一一h i p o 算法，并用n e t 实现了一个测试工具，通过 实例验证了算法的有效性。 本文主要的创新点如下： ( 1 ) 通过实验证明了影响口o 算法的几个因素：测试用例水平扩展次序的问 题、测试用例集合整体覆盖安排的问题和待扩展参数的扩展次序问题。 ( 2 ) 提出测试用例贡献度的概念，为评价测试用例提供了方法。 ( 3 ) 提出了一个口o 算法的改进算法( h i p o ) ，使它解决了现有i p o 算法的三 个缺陷。 ( 4 ) 用n e t 实现了两两组合覆盖测试集的自动生成工具。 ( 5 ) 将h 口o 算法应用到银行反洗钱系统中，获得了良好的效果。 1 5 章节安排 本文共分六章，具体章节安排如下： 第一章是全文的概述，介绍了研究的背景、意义和现状。 第二章介绍了两两组合覆盖问题，以及它的描述与分析。介绍了当前国内外 主要的六种两两组合覆盖测试用例生成算法，并通过分析总结了优缺点。 第三章提出了一个针对口o 算法的改进算法：h i p 0 算法，很好的解决了上 文提出的问题。 第四章介绍了如何在设计和实现h i p o 算法的测试工具，并通过实验证明了 该算法的有效性。 第五章将h i p 0 算法应用到银行反洗钱系统的测试用例生成中去，获得了良 好的效果。 第六章对论文进行了总结和展望。在强调了本文的几个重要结论的同时，还 总结了本文的创新点以及将来的研究方向。 4 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 第二章两两组合覆盖测试数据生成 两两组合覆盖测试是一种面向应用的测试方案，所要达到的目标是在最终生 成的测试用例集中，对所有软件系统外部输入参数可能取值的两两组合( 两两配 对) 至少覆盖一次。本章首先通过一个例子对两两组合覆盖作了说明，然后研究 分析了当前国内外相关的研究成果。 2 1 问题的提出 目前，对于组合覆盖的测试用例集生成技术研究主要是研究应用组合设计方 法对软件进行组合测试。一开始主要是将正交拉丁方应用于软件测试，取得了比 较好的效果。正交拉丁方算法是一种比较成熟、有效的测试用例选择方法，它可 以实现对各个参数可取值的两两组合的等概率覆盖，而且提供了一整套试验结果 分析方法。 后来，人们关于组合测试的研究主要集中在两两组合覆盖测试用例的生成方 面，主要有以下四个方面原因：第一，在软件测试中，对各个参数及其相互间组 合，只要求覆盖，并不需要等概率覆盖；第二，正交拉丁方算法的设计依赖于正 交表，但正交表构造还存在很多未解决的问题，这给该算法的使用带来一定的限 制；第三，使用正交拉丁方算法所需要的测试用例数量在多数情况下要远远多于 实现两两组合覆盖所需要的测试用例的数量，这无疑将增加软件测试的成本；第 四，在测试实践中发现，大约7 0 的软件错误是由系统的一个或两个输入参数的 相互作用引起【2 】【3 2 1 。 由于以上四个原因，人们对于组合测试的研究主要关注于两两组合覆盖测试 用例的生成测试方法。 2 2 两两组合覆盖测试示例 两两组合覆盖的目标是在最终生成的测试用例集中，对所有软件系统外部输 入参数可能取值的两两组合至少覆盖一次。为了便于描述，我们考察以下这个例 子： 例如，为了测试一个电话交换机系统，表1 给出了所定义的测试模型的4 个 参数及每个参数的可能取值。这4 个参数为：c a l l t y p e ( 呼叫类型) 、b i l l i n g ( 付费 种类) 、a c c e s s ( 接入方式) 和s t a t u s ( 状态) 。参数c m lt y p e 的可能取值为l o c a l 、 l o n g d i s t 锄c c 和i i l t e m a t i o n a l ，其它参数的可能取值见表1 中所列。 因为表1 中每个参数有3 个值，所以总共有3 4 = 8 1 个不同的测试情况。要测 5 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 试所有这些可能的情况，其测试成本是昂贵的。特别是当测试参数的个数或每个 参数的可能取值的个数增加时，不同的测试组合个数会迅速增加。但是如果知道 错误是由被测试系统参数的两两相互作用引起，我们就可以设计两两组合覆盖测 试用例集，此测试用例集所含测试用例的个数就会大大减少。例如对于表1 中给 出的测试系统参数，其满足两两组合覆盖测试条件的一个测试用例集在表2 中给 出，它仅含有9 个测试用例。其覆盖了任何两个可能参数取值的组合，满足了两 两组合覆盖的要求。 1 a b l e1t h ep a 髓m e t e 巧柚dv 蚰u 姻o f t e s “n gm o d e i i nt d e p h o n e 跚i t c m n gs y s t e m 表1 电话交换机系统测试模型的参数及取值 c a l lt y p e b i l l i n ga c c e s s s t a t u s l o c a lc a l l e r l o o p s u c c e s s l o n gd is t a n c e c 0 1 1 e c ti s d n b u s y i n t e r n a t i o n a l8 0 0 p b x b l o c k e d 1 a m e2t h ep a i r - w i s et 姻u n g 傀s 器o ft e s t i n gm o d e l 缸t e l e p h o n es w i t c 帖n gs y s t e m 表2 电话交换机系统测试模型的两两组合覆盖测试用例集 c a l lt y p e b i l l i n g a c c e s ss t a t u s l o c a lc 0 1 l e c t l o o pb u s y l o n gd is t a n c e 8 0 0 l o o pb u s y i n t e r n a t i o n a lc a l l e ri s d n b u s y l o c a l8 0 0i s d nb l o c k e d l o n gd is t a n c e c a l l e rp b xb 1 0 c k e d i n t e r n a tio n a lc o l l e c t l o o p b l o c k e d l o c a lc a l l e r l o o p s u c c e s s l o n gd is t a n c e c o l l e c ti s d ns u c c e s s i n t e r n a t i o n a l8 0 0p b xs u c c e s s 2 3 两两组合覆盖问题的描述与分析 考察一个含有k 个参数的系统s ( k 2 ) ，参数a 与参数b 是系统s 中任意两个 参数。参数a 的有效取值为( a 1 ，a 2 ，a 3 ，a m ) ，参数b 的有效取值为( b 1 ，b 2 ，b 3 ，b n ) ， 那么集合t = ( a i ，b i ) 1 1 s i s m ，1 司s n ，i n ，j n ，i 乒j ) 就是一个符合两两组合覆盖要求 的测试用例集合。从两两组合覆盖测试的目的出发，将系统s 表示为np ) ，其 中t 是所有可能的测试用例集合，p 是所有有效的两两组合集合。一个满足两两 组合覆盖的测试集t - 是t 的一个子集，且任意一个参数值对( a i ，b i ) t 。我们用i t f i 表示为t 中含有的测试用例总数，那么两两组合覆盖问题就是：对于一个给定系 统，找到一个满足两两组合覆盖且| t 1 i 为最小的测试集t 。为了方便理解，我们 用图形方式来表示两两组合覆盖问题，图1 即是两两组合覆盖问题的一个实例。 6 上海师范大学硕士研究生学位论文 两两组合覆盖测试用例生成研究及优化 关于图1 中的相关图案，我们给出以下定义： 定义1 ： 若图g 的在水平线上的每一层表示一个参数，这层中的各项点表 示为该参数的各个有效取值，每一条边代表参数值的一个需要被覆盖的两两组 合，那么我们称图g 为某个软件系统的两两组合图，简称p c g 图 ( p a i r - c o m b i n a t o r i a lg r a p h ) 。很显然，由于同一个参数的不同取值是不可能形成两 两组合的，因此同一层的顶点之间没有连线。 定义2 ：令g 是一个软件系统的p c g 图，若g 的子图g 在每一层中只有一 个顶点，则称该子图g 是两两组合覆盖测试用例图，简称p t c 图俾a i r - w i s et e s t c a s e ) 。p t c 图即是对应的测试用例在图g 上的映射。图2 是某系统的p t c 图集 合。 图1 某软件系统a 的p c g 图示例 f i gl1 1 l ep c gg 均p ho f s o 胁a ns y s t e m a ( 1 )( 2 )( 3 )( 4 )( 5 )( 6 ) 图2 某软件系统a 的6 个可能的p r r c 图 f i g2s hp 0 s s i b l ep t cg 瑚p h so f s o n w a ns y s t e m a 由上述定义可见，任意一个p t c 图表示一个测试用例，由此两两组合覆盖问 题又可以转化为，寻找一个符合以下要求的p t c 图集合：集合中所有的p t c 图 能够复合构成该系统的p c g 图，即能够覆盖p c g 中所有的边。显然，这样的 p t c 图集合不是唯一的，为了能减少资源的消耗，我们就需要一个盯c 图数量 最小的p t c 图集合。 如图1 所示，这个系统有三个参数a 、b 、c ，且a 和b 有2 个有效取值，c 7 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 有三个有效取值。图1 就是该软件系统的p c g 图，它所有的连线就是需要覆盖 的两两组合，两两组合覆盖测试的目标即是找出一个测试用例集合，使之能覆盖 图中所有的连线。图2 即是该软件系统的可能的六个p t c 图，根据定义，每个 p t c 图可以对应一个测试用例。可以看出图2 中p t c 图集合就是图1 所示系统 的一种最优两两组合覆盖测试集合。 2 4 国内外相关研究 2 4 1 正交拉丁方算法 正交拉丁方算法【9 1 7 】是一种利用组合数学中拉丁方的特殊性质来构造两两组 合覆盖测试集的算法。 在组合数学中拉丁方是一个具有特殊性质的方阵，即每个元素在各行各列中 均出现且只出现一次。正是由于其特殊性质，拉丁方可以有效构造覆盖所有参数 两两组合的测试用例集，形成一个独立的测试用例。虽然这种方法简单易行，但 却是效率低，且不能应用于有三个以上参数的系统。 正交拉丁方是指，若由s 个拉丁方所组成的复合方阵里，没有重复的s 元组， 则称这s 个方阵是相互正交的。例如，方阵【a 胡和【b 胡组成的复合方阵【吲，其中 q = ( 绚，b i j ) ，若对于任何确，q j 时，都有q 铀，则称方阵【a 胡和【b i j 】是相互正交 的。 根据组合数学原理中正交拉丁方的性质，正交拉丁方算法利用一种规格化的 表格：正交表，仅作较少次数的试验，便能得出较为明确可靠的结论。软件测试 工作正是利用其方便、科学、简洁、快捷的特性，来降低开发费用、缩短开发周 期和提高系统的可靠性。在两两组合覆盖测试用例生成过程中，只需要按照一定 方法计算出正交表，即就产生了相对应的测试用例。 虽然正交拉丁方算法有效的测试用例选择方法，但这种方法依赖于正交表。 正交表的构造还存在很多未解决的难题，特别是对于混合型的正交表，目前还没 有比较好的构造方法，这给正交拉丁方算法在黑箱测试用例选择中的应用带来较 大的局限【3 3 确】。在软件测试中，测试用例只要满足两两组合覆盖的要求就可以了， 并不要求等概率，而且使用正交试验设计产生的测试用例数量在多数情况下要远 远多于两两组合覆盖方法中测试用例的数量。例如，假定一个系统有1 0 个参数， 其中，3 个参数每个参数有5 个取值，3 个参数每个有4 个取值，3 个参数每个 有2 个取值，1 个参数有3 个取值，如果用正交拉丁方算法至少需要3 0 0 个测试 用例，且生成方法比较复杂，而生成一个a e t g 算法的测试用例组只需3 0 个测 试用例，所以在上述例子中a e t g 算法更适合软件测试。 8 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 2 4 2w i l i i a m s 算法 加拿大渥太华大学的a w w i l l i 锄s 在2 0 0 2 年他的博士论文中提出一种新的 两两组合覆盖测试用例的生成方法【2 4 之7 】。在这个方法中他首先定义了构造两两组 合覆盖表的基本成分( 见图3 ) ：o ( n 2 ，n + 1 ，n ) 表示一个正交表，b ( n 2 n ，n + 1 ，n ，d ) 表 示将正交表o ( n 2 ，n + 1 ，n ) 第1 行去掉每一列连续重复d 次而得到的表，有n 2 1 行，( n + 1 ) 卑d 列；r ( n 2 - n ，n + 1 ，n ，d ) 表示将正交表o ( n 2 ，n + 1 ，n ) 的前n 行去掉，每 列重复d 次而形成的表，有n 2 - n 行，n 宰d 列；i ( c ，d ) 表示全由1 组成的c 行d 列 矩阵；n ( n 2 - n ，n ，d ) 表示由n 拳d 的2 ，n 毒d 的3 ，n 宰d 的n 从上而下垂直组成的 矩阵。 考虑待测试系统有k 个参数，其中第i 个参数有n i 个取值( i _ 1 ，k ) ，具体 构造算法见算法2 1 。 图3 基本构成成份的定义示倒 f i g37 r h ed e 6 n i t i o ns a m p l eo fb a s i cc o m p o n e n t 2 4 3k o b a y a s h i 算法 同w i l l i a m s 算法相似，k 0 b a y a s l l i 算法也是通过一些基本正交表和特征块作 为基本成分，来构造满足要求的复杂两两组合覆盖表。k o b a v a s h i 算法的基本成 分是正交表0 表，并通过o 表的交叉重叠来构造新的两两组合覆盖表。 k 曲a y a s h i 算法主要依据的取值个数为某个素数方幂v 的多因素系统【v k l ， 当参数( 因素) 个数k s v + 1 时，存在一个正交表，而且生成这样的正交表o ( v 2 ，k ，2 ) 是容易的，然后以此为基础，进行推广；当k v + 1 时，利用o ( v 2 ，k ，2 ) 和具有块结 构的表进行构造。如果v 不是素数方幂，那么找一个大于v 的最小素数方幂，进 行近似处理。对于【v 。，v 2 ，v n 】的设计也是找一个不超过v 2 的最大素数方幂r ( 当 n s r + 1 ) ，或者找一个不小于v1 的最小素数方幂r ( 当n r + 1 ) 生成正交表o ( r 2 ，n ，2 ) ， 以此为基础生成【v 1 ，v 2 ，v 。】的覆盖表。对于一般情况，是将这两种情况进行组合 使用。因此方法k 曲a v a s h i 算法的效果在一定程度上取决于用素数方幂对一般情 况取近似时的误差上。在有些情况下，这个误差还是比较大的。例如考虑生成6 4 1 ， 由于6 不是素数，找出大于6 的最小素数方幂是7 ，生成【7 4 】的需要4 9 行，虽然 9 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 算法2 1 参数两两配对覆盖c ( c ，k ，n ，2 ) w i l l i 锄s 算法 输入：参数个数k ，每个参数的取值个数n 输出：参数两两配对覆盖表c ( c ，k ，n ，2 ) 步骤： 设g ，表示在第r 个构造阶段所用的基本块的列数，初始化时g ，= n + 1 ( 使用0 ( n 2 ，n + 1 ， n ) 作为基本构造块) ，r ：2 ，s 时，g ，= n 表示用的是r 阵，g ，= n + 1 时表示用的是b 阵。参数容量为h g ，= n + 1 ：f o rr = 2t osd og ，= ne n df o r ：宅| 丁始化 f o rr = 1t 0sd o h = n + 1 f o ri = 2 t osd o 确定参数容量 h = h 木g i i fg i nt h e nh = h + 1e n di f ：增加附加列 e n df o r ： i fh kt h e ng r - n + le l s eb r e a ke n di f ：决定每个构造阶段使用r 或b 阵 e n df o r ： 确定列的重复次数，决定每一个阶段使用r 阵或b 阵时每一列重复的次数d r d j = 1 ：f o rr = 2t osd od ，= d r _ l 木g 卜ie n df o r ： 确定附加列，设e 为第r 阶段所增加的附加列，在这一阶段使用i ( c ，e ，) 和n ( n ：一n ，n ，e ，) ，其中c 为第r 阶段当前覆盖表的行数 f o rr = 2t osd o i fg ，一n + 1t h e ne ，= oe n di f ： i fg ，= = nt h e ne ，= ( d 。昏) ( d ，g r ) e n di f ： e n df o r ： 设九。表示在q 阶段为r 阶段的附加列追加的r 阵数目 i fq = = r + 1a n dr + l st h e n 九f 1 ：狩k l 木n ( q ：r + 2 ，s ) ： 将o ( n 2 ，n + 1 ，n ) 水平重复( d 。g 。) ( n + 1 ) 次形成表c ： 构造覆盖表c ( c ，k ，n ，2 ) f o r r = 2t osd o 在c 的右边加上i ( c ，e 。) ，c 是c 当前的行数： 设a 为r ( n 2 一n ，n ，n ，d ) i fg ，= n ，或者b ( n 2 1 ，n + 1 ，n ，d ) i fg r - n + 1 ： s 为a 水平重复( d 。g 。) ( d 。g ，) 次： f o rq = 2t osd o 在s 的右边增加e r ( 氓。) 个r ( n 2 - n ，n ，n ，九玛) 并水平地将 n ( n 2 一n ，n ，e r ) 放在s 的左边，将s 垂直地放在c 的下边： e n df o r ： e n df o r ： e n df o r ： 【6 4 】的至少需要3 6 行，但使用p s s t 算法只要4 2 行。 1 0 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 2 4 4a e t g 算法 a e t g ( a u t o m a t i ce 币c i e n tt e s t c a s eg e n e r a t o r ) 算法1 8 2 1 1 是由美国贝尔实验 室的d m c o h e n 与s r d a l a l 等提出了一种基于两两组合覆盖的测试数据启发 式生成方法，所产生的测试数据可以根据测试要求实现对系统参数的两两组合覆 盖，或者多个参数的组合覆盖的测试方法。a e t g 算法是以一个空的测试集开始， 每次往测试集加入一个测试用例。为了得到一个新的测试用例，系统首先根据贪 心算法产生一组候选用例，然后选择其中能覆盖最多未覆盖两两组合的用例，具 体算法见算法2 2 。 这种方法也可以让测试人员事先指定一些测试用例，然后在这些测试用例的 基础上生成一组能实现对所有两两组合覆盖的测试用例集合。a e t g 算法能产生 相当少的测试用例，并且已经在b e l l c 0 r e 使用多年【”l ，用于测试各种复杂的软件 系统。它也能产生高层的测试计划，如用于通信协议的一致性测试计划和一个网 络监视系统的测试。 算法2 2a e t g 算法 输入：参数f 1 ，f 2 ，f k 及其相应的值集，t l ，t 2 ，t k ，已经选择了r 个测试用例，未被覆盖的 组合对集蚰c o v e r 输出：对k 个参数的两两配对覆盖表 步骤： w h i l e ( 岫c o v 钉不为空) 选择参数f 和参数f 的值i 使得该参数的值在所有未被覆盖的组合对集合 岫v e r 中出现的次数最多； 置f l = f ，剩下的参数随机排序，则这k 个参数分别为f l ，f 2 ，f 3 ，f k ； 假定参数f 1 ，f 2 ，f k 的值己经确定，对于1sisj ，设f i 的值是v i ，那么按照如下 方法选择f i + 1 的值v “1 ，对于勾+ 1 的每个值v 找出所有组合 f i 弓1 即v i v 1s i s j 】n u n c o v e r ，把在这些组合中出现次数最多的值v 赋给v i + 1 ，并在岫c o v e r 中将这 些己被覆盖的组合对去掉： e n dw h i l e ： 2 4 5i p o 算法 美国北卡罗莱纳大学计算机系的yk i 和k c 附提出一种基于参数顺序的 渐进扩展的两两组合覆盖测试数据生成方法。与a e t g 算法不同，i p 0 算法的基 本思想是以参数为对象，初始时先生成满足组合覆盖的测试要求的用例集合t ， 然后一个个扩展剩余的参数，直至所有的参数都被包涵到测试用例中，并在算法 中时刻都尽可能使测试集个数大小保持最优。参数的扩展步骤共有两步：水平扩 展，即扩展原有最优的测试用例，将待扩展参数的取值添加到现有的测试用例中； 上海师范大学硕士研究生学位论文两两组合覆盖测试用例生成研究及优化 垂直扩展，即在水平扩展后将剩余的未被覆盖两两组合重新组织，形成新的测试 用例的过程。具体算法见算法2 3 。 算法2 3i p o 算法 输入：参数f l ，f 2 ，f n 及其相应的值集t 。，t 2 ，t n 输出：配对组合覆盖表t 步骤： 对于前两个参数f l ，f 2 建立配对组合二元组，形成集合t t = ( v 1 ，v 2 ) i v l t l 和v 2 玎i 分别是参数f 1 ，f 2 的值】； 删剩下的参数构造测试用例 f o r i - 3 t 0n d 0 朋寸于参数f i 首先对t 中每个测试用例作水平扩充 胆 参数f i 和参数f 2 ，f 3 ，f i 1 中任何一个参数形成的组合对) ； s = m i n ( 口；i ，r i 1 ) ； f o r j = 1 t o sd 0 将参数f i 的第j 个值添加到t 中第j 个测试用例的第i 个位置上， 即用( v 1 ，v 2 ，v j ) 取代“，v 2 ，v j 1 ) ； 兀= 兀 扩展的测试用例覆盖组合对) ； e n d f o r ： i fs =