（计算机应用技术专业论文）参数配对组合的软件测试方法研究与实现.pdf

上海师范大学硕士研究生学位论文参数配对组合的软件测试方法叫f 宄to 实现 摘要 参数的配对组合测试是适用于各种软件系统的一种实用且有效的测试方法因为许多软 件错误是由一些测试参数的相互作用而引起的。本文首先介绍基于参数组合的测试设计方法 和配对覆盖测试方法的有效性，并提出配对组合图( p a i r - c o m b i n a t o r i a lg r a p h ，p c g ) 和 案例子图( c a s es u bg r a p h ，c s g ) 的概念来描述配对覆盖问题。同时也指出，要获得一个 最优的配对覆盖测试集是一个n p c 问题，但测试集的大小是在一个可预计的范同之内。 本文还研究和分析了目前已有的三种有效的配对覆盖测试集生成策略，并利j jp c g 幽 c s g 图分析了它们各自的扩展算法还通过一组测试样本系统综合分析和比较了它们各自的 效果。在此基础上，我们提出了一个改进的算法，该方法基于i p o 策略但对于参数扩展的 顺序作了规定，以获得到一个更优的测试集大小。同时，新的算法针对参数约束的情况作了 改进，并指出一个含有参数约束组合的软件系统其配对覆盖测试集会增人的情况。 最后我们利用j a v as w i n g 组件实现了基于该方法的一个测试案例生成工具，并演示了 如何使用该测试工具来解决参数约束和参数变动等实际测试经常遇到的问题。 关键词：配对组合测试，配对覆盖，参数约束，软件测试 一h 海师范大学硕士研究生学位论文参数配对组台的软件驯试力洼圳宄i 实现 a b s t t a c t p a i r w is et e s t i n gis ap r a c t i c a la n de f f e c t iv ea p p r o a c hf o rv a r i o ust y p e so f s o f t w a r es y s t e m s 。s l n e em a n yt r o u b l e s o m ef a u l t sa r ec a u s e db yt h ei n t e f a c t i o no f af e wt e s tp a r a m e t e r s i nt h ist h e s is w ef i r s ti n t r o d u c et h em e t h o d o l o g yo l c o m b i n a t o r i a ld e s i g no ft e s t i n gp a r a m e t e r sa n dt h ee f f e c t iv e n e s so fp a ir w is et e s t i n g t h e nw ed e f i n ep a t r c o m b i n a t o r i a lg r a p h ( p e g ) a n dc a s es u bg r a p h ( c s g ) t oa n a ly z e t h ep a i r c o v e rp r o b l e ma n di n d i c a t et h a tt oa c h i e v eam i n i m u mt e s ts e t f o rp a i r w is e t e s t i n gisa nn p cp r o b l e m ，b u tt h es i z eo fs u c ht e x ts e ti s i nap r e d i c t a b l er a n g e a f t e rac o m p a r a t iv es t u d y i n ga n da n a l y z i n gt h r e ee f f e c t i v es t r a t e g i e sf o r g e n e r a t i n gp a i r c o v e rt e s ts e tb ym e a n so fp c g ，c s ga n das e r i e so fs a m p l es y s t e m s e x p e r i m e n t s ，w ep r e s e n ta n m p r o v e da l g o r i t h m ，w h i c hh a sar u lef o ro r d e r i n g p a r a m e t e r se x t e n s i o na n da l s os o l v e sc o n s t r a i n tp a r a m e t e r sp r o b l e m f i n a l l y ，b a s e do nt h ei m p r o v e da l g o t i t h m ，w ei m p l e m e n tat e s t i n gt o o lf o r p a i r w i s et e s t i n sb yj a v as w i n gc o m p o n e n t s t h ist e s t i n gt o o ls o l v e dc o n s t r a i n t p a r a m e t e ra n dp a r a m e t e ra l t e r n a t i o np r o b l e m s ，w h ic ha r ev e r yo f t e ns e e ni np r a c t i c a l t e s t l n gs i t u a t i o n k e y w o r d s ：p a i r w is et e s t i n g ，p a i r c o v e r ，c o n s t r a i n tp a r a m e t e r ，s o f t w a r et e s t i n g 上海师范大学硕士研究生学位论文 参数配对组台的软件测试方法研究与实现 1 。1 论文研究的背景 第一章绪论 在设计软件测试案例时测试案例能否完全反应一个软件系统实际运行过程中遇到的 各种情况很难确定。由于执行一个测试案例要花费一定的时间、人力和物力，所以关丁如 何减少测试案例，用尽可能少的代价达到最大的测试效果成为众多研究机构和人员关注的 问题。一个好的测试计划及管理对软件工程的意义和作_ l _ j 是不言而喻的。 不同的测试数据发现裎序错误的能力差别很火，为了提高测试效率降低删试成本，应该 选用高效的测试数据。经验以及实践表明“”1 ，参数的配对测试是对各种软件系统测试的一 个实际而有效的方法，因为许多软件系统的故障是测试参数的相互作_ l | 引起的。配对测试要 求系统的任何一对输入参数，它们每一个有效值的组合都必须被至少一个测试案例所覆蔫。 为了简要说明它的概念，我们考察这样一个系统，该系统中有三个参数a ( a t ，a z ) 、b ( b 。，b 。) 和c ( c - ，c z ，c 。) ，括号内是它们的有效取值。对于参数a 和b ，集合 ( a - ，b ) ，( a z ，b - ) ， ( a ，b ：) ，( a z ，b z ) ) 就是它们所有的配对测试案例。若再加入参数c ，则集台将进一步扩火。 假定t i = ( ( a l ，b 。，c 1 ) ，( a ，b 。，c - ) ，( a z ，b 。，c z ) ，( a z ，b z ，c ，) ，( a z ，b t ，c ，) ( a 。，b z ，c z ) ，( a i ，b i ，c 。) ) ， t ：= ( a - ，b - ，c t ) ，( a ，bz ，c ) ，( a z ，b - ，c 2 ) ( a z ，bz ，c z ) ，( az ，b ，c t ) ，( a t ，b t ，c z ) ，( a ，b i ，c ，) ， ( a 。，b ：，c 。) ，t 。和n 都覆盖到了a 、b 、c 的每一参数组台，但t 的测试案例数为7 t z 为8 。 为了减少测试开销，我们希望能得到一个尽可能小的满足配对覆盖要求的洲试集。然 而可以证明，要获得这样一个最优的测试集合是一个n p c 问题”i 但其火小是在一个可预计 的范围之内，本文给出了这样一个估计区间。另一方面，我们可以采朋一定的策略和算法米 获得一个最优或接近于最优的测试集，目前国内在这方面的研究尚不多见，而国外有关组合 参数的测试技术研究以及测试 ：具的开发已有一些成果和经验，比较著名的有a e t gs y s t e m 、 i p o 组合策略和正交拉丁方方法等。 1 2 论文的主要内容和章节安排 本文提出了配对组合图p a i r c o m b i n a t o r i a lg r a p h ( p c g ) 和案例子图c a s es u bg r a p h ( c s g ) 的概念，并以此为工具分析了上述组合策略，且进一步通过一系列样本系统的实验， 比较了其各自的效果。从总体上说。a e t g 和i p o 的配对覆盖测试集结果是比较令人满意的 一j 二海师范大学硕士研究生学位论文 参数配对组合的软件测试方法划f 究t ，实删 而采用正交拉丁方的方法由于其本身算法构造的局限性，会产生相对较多的测试案例。此外， i p o 的算法思想能轻松适应测试系统的参数变动，其实_ 日性更强。但算法本身尚有不完备之 处，也投有解决参数约束的问题。因此，本文在此基础上提出了一个改进算法，井用j a v a s w i n g 组件实现了基于改进算法的测试工具。 本论文共分七个章节，各个章节的安排如f ： 第一章是全文的概述，介绍了本论文的背景和意义。 第二章首先介绍基于参数组合的测试方法，并通过一个简单的例子米说明配对覆盖测试 方法的有效性： 第三章从理论上对配对覆盖问题加以分析和研究。提出了配对组合图弄案例子图的概 念，同时还给出用于估计实际系统配对覆盖测试集范围的一个定理和推论： 第四章主要介绍目前国外已有的几种有效的测试集生成策略，运用配对组合目j 【l 案例子 图为1 具对它们的加以深入的分析，并通过实验对其各自的特点并1j 有效性进行比较； 第五章提出本文一个改进算法，在满足配对覆盖的同时，也解决了实际删跌活动中可能 遇到的参数约束问题； 第六章首先说明如何用j a v a 具体实现本文算法，并用j a v as w i n g 组件开发了的一个测 试工具，还演示了参数约束以及参数值变动的各种情况： 第七章对论文进行了总结和展望。在强调了本文的几个重要结论的同时，还总结了本文 的创新点以及将来的研究方向。 ：海师范大学碗士研究生学位论文参数配对圣u 台的软件测试方法讲究与实现 第二章测试参数的选择和组合测试方法 本章首先通过一个例子对基于参数组合的测试方法作了说明，指出测试参数不仅包括系 统的软件部分，也可以是用户输入或运行环境锦硬件资源。同时也指山了配对覆盖测试的有 效性； 2 1 测试参数的选择及组合 在测试工作开始阶段，我们首先要确定系统的测试参数。测试参数不仅可以是某一软 件模块设置的参数，也可以是涵盖整个测试计划中所涉及到的系统配置、_ 【= h 户输入平| l 交互操 作以及操作系统运行环境等设置。既可以包括软件部分也可以是硬件资源。这些测试参 数的每一组取值决定了一个测试案例或测试计划。 例如，我们测试一个电话服务系统的功能时，可以确定如下参数：拨号类型( c a ll t y p e ) 、记费( b i l l i n g ) 、接入方式( a c c e s s ) 和状态( s t a t u s ) ，各参数的取值见表2 1 。 表2 - 1 电话拨号测试参数 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 a l l e r l o o p b u c c e s s l o n gd is t a n c ec o l l e c ti s d nb u s y i n t e r n a t i o n a l8 0 0p b xb 1 0 c k e d 在这个例子中我们看到，测试参数不仅有电话系统本身，如拨号类型( 本地、长途、国 际长途) 和记费方式( 呼叫方付款、对方付款、8 0 0 服务记费) ，还包括有硬件接入方式( l o o p 、 i s d n 、p b x ) 以及呼叫状态( 成功、忙音、阻塞) 。这种确定测试参数的方法同样适用于软件 系统的测试计划。由此也可见，基于参数组合的测试方法是具有相当灵活性的，它可以适应 小到单元测试或模块功能测试，大至整个系统的集成测试。参考文献“1 对于测试配置等方面 有很多详细的讨论，这里不再赘述。 确定参数之后就可以应用参数组合的方法生成测试案例。继续以袭2 一lj , j 例，每一组参 数值的组合都确定了一个测试案例，由于总共有4 个参数，每个参数各有3 个参数值，因此 总共有34 = 8 1 个测试案例。假定每个测试案例的执行都要花费一定的代价汞i 时间，总共8 1 个测试案例的测试开销是相当大的。 一种简单组合策略是，先设定其他参数的默认值，只选择一个参数改变其参数值，表 2 - 2 显示了用这种方法得到的测试案例集。考察表2 - 2 可以看出，测试案例的个数从8 1 个 上海师范大学硕士研究生学位论文参数配对组合的软件测试方法研究l j 实姚 缩小到仅为9 个，但遗憾的是虽然这种方法覆盖了所有参数的取值，但没有覆盖到每一个参 数值的配对组合，只覆盖了全部5 4 种配对组合中的3 0 种。 表2 - 2 一种简单的组合策略 c a l lt y p eb i l l i n ga c o e s ss t a t u s l o c a lc a l l e rl o o pb u c c e s s l o n go is t a n c e c a l l e f l o o p 3 u c c e s s i n t e r n a t i o n a lc a l l e r l o o p l o c a lc o l l e c t l o o p 3 u c c e s s l o c a l8 0 0 l o o pj u c o e s s l o c a lc a l l e ri s d n3 u c c e s s l o c a lc a i le r p b xb o c c e s s l o c a lc a l l e r l o o pb u s y l o c a lc a l l e r l o o p b l o c k e d 表2 3 给出了一个理想的组合结果，虽然也含有9 个测试案例，却覆盖了所有测试参数 的配对组合。但迸一步研究发现，有2 3 的电话呼叫是不成功的，因此这同样不是一个好的 测试计划。多数软件系统的错误是在实际情况下参数的相互作用引起的，而测试计划又必须 能反映系统的真实运行情况因此我们在确定参数以及运 1 _ 算法进行组合时，必须要考虑到 这一点，使我们的测试设计更能满足实际需要。 表2 3 一个参数配对全覆盖的测试案例集 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 b o a lc a l l e r l o o p s o c c e s s l o c a lc o l le c ti s d n b u s y l o c a l 8 0 0p b xb l o c k e d l o n gd is t a n c e c a l l e rp b x b u s y l o n gd is t a h o e c o l l e c t l o o p b l o c k e d l o n gd i s t a n c e8 0 0i s d n3 u c c e s s i n t e r n a t i o n a c a l l e ri s d nb l o c k e d i n t e r n a t i o n a lc o l l e c tp b x3 u c c e s s i n t e r n a ti o n a l8 0 0 l o o p b u s y j 二海师范大学硕士研究生学位论义参数配对组合的软件测试方法f 【j f 究2 0 实现 2 2 配对覆盖测试的有效性 由于测试是软件工程中一个重要且代价昂贵的部分，因此软件测试的关键问题在丁如何 使有限的时闻和资源达到最大的测试效果。如前面所述，一个应_ l ；| 软件系统包括许多参数利 配置，测试案例就是基于这些参数设置构造的。然而一个实际的问题是若系统有k 个测试 参数，且每个参数有7 种取值，则总计有个案例需要测试，这在实际应_ j 中是不太可能 做到的。 经验以及实践表明，参数的配对测试是对各种软件系统测试的一个实际而有效的方法， 因为多数系统的故障是捌试参数的相互作用引起的。配对测试要求，对于系统的任何对输 入参数，它们每一个有效值组合都必须被至少一个测试案例所覆盖，其有效性就在于，能以 较少的测试案例来找出软什系统中隐藏的错误。 假设一个正确的软件功能模块如图2 1 所示，如、x l 矛x 2 是其二个输入参数，墩值均 为0 或1 ，y 是输出，其对应的真值表如下： 图2 - 1 ：一个正确的软件模块 表2 4 个正确的软件模块对应真值表 x 2x lx o y 0 0 0 0 0olo 01oo 0l1 0 l0o0 1 o l1 1l0o 1lll 若该软件模块发生了如图2 - 2 的错误，即a 点位置的值为x o 的输入。则对于这3 个2 值参数，不采用特别的方法，我们需要23 = 8 个测试案例来找出这个错谋测试案例集如 表2 - 5 所示： e 海师范大学硕士研究生学位论文参数配对组合的软件测试方法研究与实现 幽2 - 2 发生错误的软件模块 表2 - 53 个2 值参数的穷举测试集 x 2x lx 0 y o000 00l0 oloo 0ll0 lo0o 1ol 1 一 ll 0 o ll11 图2 - 3 用测试工具产生3 个2 值参数的配对覆盖测试集 另一方面，我们利用测试工具产生这3 个2 值参数的配对覆盖测试集，如图2 - 3 ，则只 需一半数目的测试案例就能找出这个错误，见表2 6 。 上海师范大学硕士研究生学位论文参数配对组合的软件测试方法_ 【j 究t j 实则 表2 - 63 个2 值参数的配对覆盖测试集 x 2x 1x o y o0 0o 0l10 lo11 110o 从而比原先减小了般的测试开销。于是问题就转化为寻找一个尽可能小的测试案例 集合，使所有有效的参数配对组合都能被这个集合所覆盖。然而，事实证明要求这样一个最 优的测试集合是一个n p c 问题。在下一章我们将从理论上分析配对覆盖问题，并给出配对覆 盖问题( p a l r c o v e r ) 属予n p c 问题的证明，接着我们也会证明这样一个测试集的大小是住 一个可预计的范围之内，并得出适用于实际系统的，估计测试集大小的一个推论。 上海师范大学硕士研究生学位论文参数配对组台的软件测试方法研究与实现 第三章配对覆盖问题的研究与分析 本章首先从理论上对配对覆盖问题进行了分析，指出配对覆蔫实质上烛一个肾c 问题。 接着，我们提出了p c g 圈$ 1j c s o 豳的概念，并以此分析配对覆盖问胚。最后给山川丁估计给定 系统的配对覆盖测试集大小的定理和推论。 3 1 基本概念 考察个含有个参数的系统s ( 兰2 ) ，对于参数，令口( a ) 为a 的值域，即所有 a 的有效输入。参数d 的某一个取值“标记为a “而系统s 的两个参数a 和口的一对取值 a ua n d 卢y 则标记为( d “卢订( ( a ，“，卢订和_ a 认为是相等的) 。系统s 的一 个测试案例r 含有 个取值，每一个取值属于系统s 的个参数。若r 在参数“位置的敬值 为“，在卢处的取值为“则称f 覆盖了配对组合( ，口订。显然，对于系统s 中任意一 个测试案例f ，它能覆盖到月( 卜1 ) 2 对组合。 从配对组合测试的目的出发，将系统s 表示为( t ，p ) ，其中t 是所有可能的测试案例集 台，p 是所有有效的配对集合。一个满足配对覆盖的测试集t ，是t 的一个子集且对于任意 一对组合( “珥卢一p ，t ，中至少存在一个测试案例f 将其覆盖。我们j j _ | 旧i 表示为t 冲含 有的测试案例总数。配对覆盖问题是：对于一个给定系统，找到一个满足配对覆盖且旧i 为 最小的测试集t 。 3 2 基本概念配对覆盖是一个n p c 问题 一般地，要证明一个问题属于n p c 问题，可采用以下方法：( 1 ) 问题p 1 属于n p 问题类： ( 2 ) 一个已知的n p c 问题p 2 能转换为p 1 ( 3 ) 这种转换是在多项式时间内的。 我们将配对覆盖问题重新描述为一个判决问题。 定义3 1 配对覆盖p a i r c o v e r = ( ：系统s 有一满足配对覆盖的测试集t ，且 rl = m ) 。 对于一个给定系统s = ( r ，p ) ，我们首先找出所有大小为m 的t 的子集，对于每一个 子集，再判断它是否覆盖了p 中所有的配对，而这一过程显然是属于n p 类的。 我们用一个已知的n p c 问题顶点覆盖( v e r t e x - c o v e r ) ，来转换为个配对覆荒 ( p a i r c o v e r ) 问题，即给定一个v e r t e x c o v e r 实例 ，可以构造一个p a lr c o v e r 实例 。 上海师范大学硕士研究生学位论义 参数配对钳台的软件测试方法研究与实现 定理3 1 ：假定图g = ( v ，e ) ，且! v = n ，则相应的系统s = ( t ，p ) 构造如下： t = i t ，j1s1 曼n ) 其中r ，= ( v 。，v ，) 1v ，v 。v ：( v ，vj ) e p = ( v ，v j ) iv v v ：( v i ，vj ) e 则g 存在一个大小为k 的顶点子集v7 ，当且仅当s 有一个人小为k 的酉己对覆盖子集h 证明：假设g 有一个v e r t e x c o v e r 顶点子集v v ，且【v l = k ，则t 是s 的一个 p a i r c o v e r 子集且1t i = k ，其中t 。( “【v v ) 。令( v ，v ) 是p 中的任意一对组台， 且( v 、，v ，) e 。由于v 是g 有一个顶点覆盖子集，则v 。v ，中至少有一个v 。不失一般i 生， 我们令v v7 ，根据t 的构造，( v ，vj ) 必定被口覆盖，因此t 是s 的一个p a i r c o v e r 子集。 反之，若s 有一个p a i r c o v e r 子集t ，且it i = k ，则相应的v 是g 的一个顶点覆盖 子集，且i v | = k ，其中v k v t1 f ，t 。令( v 。v 。) 是e 中的任意一条边由构造知 ( v 。，v ) p ，由于t 是s 的个p a i r c o v e r 子集，j f l | t 中至少有一个r ，或。覆盖( v ，v ；) ， 则边( v ，v 。) 被v ，或n 中一个顶点覆盖，冈此v 是g 的一个顶点覆盖子集。 例如前面提到的3 个2 值参数的样本系统，可以由图3 - 1 所示，含有6 个坩点的圈g 表示： 图3 - i3 个2 值参数对应的图g 表示 v 4 ) ，( v 1 ，v 5 ) i ( v 1 v 6 ) ) v 4 ) ，( v 2 ，v 5 ) ( v 2 ，v 6 ) ) v 2 ) ( v 3 ，v 5 )( v 3 ，v 6 ) v 2 ) ，( v 4 ，v 5 ) j ( v 4 ，v 6 ) )舯 ) j j 6 ) ) ) ) v i 把 门 “ “ 一l o g ( n ) l o g ( 1 一l i d2 ) ，则7 1 ，目i r = l - l o g ( n ) l 0 9 0 1 d2 ) + l j 时， 所有配对组合都能被覆盖到。 因此，必定存在满足配对覆盖的测试集t ，且it isl l o g ( n ) l o g ( 1 一l i d2 ) + 1 j ，其 中n = ( 卜1 ) 2 xd2 。 由定理3 3 ，可得到用于实际系统的，估计其配对覆盖测试集大j , f f , 推论： 推论3 1 在一个实际含有女个测试参数的软件系统中备参数的取值个数可以不同， 令测试参数按其取值个数从大到小排列为p z ，觑，皿，则在范围 口( 口) x 口( 皿) ， l - l o g ( n ) l 0 9 0 1 d ( p ) 2 ) + 1 j 内一定存在满足配对覆盖的测试集t ，其中n 。 k ( k - 1 ) 2 x 口( p 。) 2 。 理论估计的意义在于：当测试计划制订时具体实旌之前，就可预计出测试可能花费 的代价，从而给测试管理者能预先进行控制和调整；同时也易于我们评价算法的有效性。 下一章将介绍三种有效的配对测试集生成策略，它们都能在一定程度上，或一定条件一f 获 得最优或接近于最优的测试集。 上海师范大学硕士1 i j f 究生学位论文参数配对纽台的软件删试方法 i j 究与实珧 第四章三种配对覆盖测试集生成策略的的研究和比较 本章详细分析了三种有效的配对覆盖测试集生成策略，并通过一组样本系统比较了各自 的效果。 4 1a e t g 策略 a e t g 1 1 ( a u t o m a t i ce f f i c i e n tt e s t c a s eg e n e r a t o r ) 是以一个空的测试集开始 每次往测试集加入一个测试案例。为了得到一个新的测试案例，系统首先根据贪心算法产生 一组候选案例，然后选择其中能覆盖最多未覆盖配对的案例。 假设系统s 有 个参数，第，个参数有，种不同的取值，且a e t g 已选取了，个测试 案例，则第一1 个测试案例的产生方法如下：首先产生m 个不同的候选案例，然后选择其中 能覆盖最多未覆盖配对数的案例。每个候选案例的选择按下述步骤进行： 1 )选择一个参数，和，的一个参数值，该参数值在未覆盖的配对中出现次数最大： 2 )令鼻= ， 然后对剩余参数选择一个随机序列，从而得到这k 个参数的一个序列 ，i 。 ： 3 )假设 ，参数的参数值已选定令参数 选定参数值为h 那么参数，- 的取值如下：对每一个有效的的取值，找出配对集台 ，t = r ，f = y ，1 j 中的新配对数选择v j ，为出现次数最多的那个值。注意到在这一步中，每一个 参数值只在一个候选案例中考察一次。同时，当选择乃，中的一个参数值时，只 和已选取的参数 ，力的个参数值比较。 算法设置m = 5 0 ，即选择一个新的测试案例时先产生5 0 个候选案例增火m 并不会显 著减少最终产生的测试案例数。由于候选测试案例根据第2 步里产生的随机顺序，使州一个 不同的随机顺序会得到一个不同的测试集。一个有效的优化方法是产生5 0 个不同的随机顺 序得到5 0 个不同的测试集，然后选择其中最好的那个。 我们用p c g 图来考察a e t g 算法，事实上它就是每次寻找一个能覆盖最多未覆盖边的c s g 图，直至所有的边都被覆盖。 a e t g 能产生相当少的测试案例。并且已经在b e l i c o r e 使用多年1 ”1 ，j = f ! jy - n 试各种复杂 的软件系统。它也能产生高层的测试计划如用于通信协议的一致性测试计划和剧于一个网 络监视系统的测试。 上海师范大学硕士研究生学位论文参数配对绁台的软件测试方法研究b 实现 4 2i p o 策略 不同于a e t g ，i p o 策略“”1 的基本思想是以参数为对蒙，初始时先生成两个参数所有配 对组合的测试案例集合t 随后每次加入一个参数，通过扩展算法覆盖该参数并测试集内已 有参数组成的新的配对集合，并尽可能使测试集保持较优的大小如此进行直至所有的参数 都加入到测试集中。测试集合t 的扩展分为两个部分：水平扩展和垂直扩展。水平扩展是在 现有测试案例的基础_ h ；0 n j k 新参数的某一个取值，不产生新的测试案例；垂直扩展在水平扩 展之后进行，对仍未被覆盖的配对组合生成新的测试案例将其覆盖。 4 2 1i p o 水平扩展 己知t 是测试案例集合，并且当前时刻己覆盖了测试参数p t ，肪p l 所有的配对 组合，对于新加入的参数p j ，t 的水平扩展是在现有测试案例中依次加入p l 的一个值。设口 ( p ，) = o ，t 的水平扩展算法具体描述见图4 1 。 i p o _ h o r i z o n t a l ( t ，p i ) 其中t 是测试案例集合，p ；是新加入的参数 假定p ，具有参数值v ，v ，v 。： w = p 和p ，p 2 ，p 组成的未覆盖的参数配对 i f ( 1 t i l - q ) f o r ( j = l ：j = i t l ：j ) 扩展t 中第j 个测试案例，加入p 的参数值v 、 从w 中删除相应被覆盖的参数配对： ) f o r ( j = z ：j 月+ i ，则州分绑的策略可 构封熹卜删恻渤雌f 熹 舭徽但 可继续通过分组的策略来解决即在现有组的基础上构造石斋1 个高一级的组，这一过 程还可以持续下去直到覆盖所有参数的配对组合。 最终，有石害可 n + 其中。为整数且。的取值代表分组进行的次数， 并且每次分组操作。都增加个测试案例，所以最后共有( b + 1 ) n 2 个测试案例。 而自f 击卜对南1 = 1 ，广“惦， 从而b + l = l o g ( 女) ，因此最终的测试集大小为l o g 。( 女) _ 2 。 显然1 0 9 。( ) 2 要好于l o g ，( ) _ 2 即应用正交拉丁方要要好于直接应用拉丁方 分组的方法。特别