（计算机软件与理论专业论文）组合测试用例的生成及优化技术.pdf

摘要 软件系统是一个复杂的逻辑系统，有很多因素都可能会影响软件系统的正常运行，这些因素可 能包括系统的配置、内部事件、外部输入等。除了单个因素之外，这些因素之间的相互作用也可能 会对系统的运行造成影响。组合测试作为一种科学、有效的软件测试方法，可以使用较少的测试用 例有效地检测软件系统中各个冈素以及它们之间的相互作用对系统产生的影响。 本文从测试用例生成、测试用例优化、及测试策略等方面，对组合测试技术进行了系统、深入 地研究。主要研究工作包括：( 1 ) 在测试用例生成方面，针对相邻因素组合测试和可变力度组合测 试等两种具体的组合测试模型，提出了多种测试用例集生成算法；( 2 ) 从同归测试下组合测试用例 优先级复用的角度，对组合测试用例的优化使用问题进行了研究；( 3 ) 对组合测试中的故障定位问 题进行了研究，提出了具体的故障定位方法，并对其性能进行了分析。上述研究工作的核心和重点 在于组合测试用例的生成和优化技术。 本文研究成果主要包括： 针对一类只在相邻冈素间存在交互作用的软件系统，提j 了一种相邻因素组合测试方法，并 给出了固定力度、及可变力度相邻冈素组合测试用例集的最优生成算法。实例分析表明，该 方法在其适用领域内可以用数量很少的测试用例实现较强的错误检测能力。 在充分考虑因素间实际交互关系的基础上，提出一种新的可变力度组合测试方法，并提出了 一系列用于生成可变力度组合测试用例集的启发式算法。实验表明，相对于一些已有的具备 类似功能的测试用例集生成算法和t 具，本文提出的算法在固定力度和可变力度组合测试用 例集的生成中均具备一定的特点和优势。 针对因素取值组合具有不同权重且测试用例运行开销已知的情况，提出一种基于组合权重及 测试用例开销的组合测试用例优先级复刚技术，并给出了两种组合测试用例优先级排序算 法。此外，还提出一种增量式组合测试用例优先级复用技术，通过对已有测试用例集之中的 测试用例进行排序，使得测试用例序列满足增量式组合覆盖的要求。 在极小故障模式模型的基础上，对组合测试的故障定位问题进行了研究。首先，从理论上分 析了已有故障定位方法的性能。针对已有方法存在的定准率不高的问题，提出了一种改进的 迭代式故障定位方法，可在一定程度上提高故障定位结果的定准率。 关键词：软件工程、软件测试、组合测试、测试用例生成、测试用例优先级、故障定位 a b s t r a c t a sac o m p l e xl o g i cs y s t e m , s o f t w a r em a yb ea f f e c t e db ym a n yf a c t o r sa n dt h ei n t e r a c t i o n sa m o n g t h e s ef a c t o r s t h e s ef a c t o r sm a yi n c l u d es y s t e mc o n f i g u r a t i o n s ，i n t e r n a l e v e n t s ，e x t e r n a li n p u t se t c c o m b i n a t o r i a lt e s t i n gi sap r a c t i c a ls o f t w a r et e s t i n ga p p r o a c h , w h i c hc o u l dd e t e c tt h ef a u l t st h a tt r i g g e r e d b yt h ei n t e r a c t i o n sa m o n gf a c t o r si ns o f t w a r es y s t e m sw i t hs m a l ln u m b e ro ft e s tc a s e s t h em a i nr e s e a r c hi nt h i sd i s s e r t a t i o ni n c l u d e st e s tg e n e r a t i o n , t e s tp r i o r i t i z a t i o n , a n dt e s ts t r a t e g yo f c o m b i n a t o r i a lt e s t i n g ：( 1 ) f o rn e i g h b o rf a c t o r sc o m b i n a t o r i a lt e s t i n ga n dv a r i a b l es t r e n g t hc o m b i n a t o r i a l t e s t i n g , s e v e r a lt e s ts u i t eg e n e r a t i o na l g o r i t h m sa r ep r o p o s e d ；( 2 ) c o m b i n a t o r i a lt e s tp r i o r i t i z a t i o nt e c h n i q u e i ss t u d i e d , a n dm a n yt e s tc a s ep r i o r i t i z a t i o na l g o r i t h m sa 他p r o p o s e d ；( 3 ) f a u l tl o c a t i o nt e c h n i q u ef o rt h e c o m b i n a t o r i a lt e s t i n gi ss t u d i e d ，a n dc o n c r e t ef a u l tl o c a t i o nm e t h o di sp r o p o s e d t h ek e yi s s u eo fo u rw o r k s i n c l u d e sc o m b i n a t o r i a lt e s tg e n e r a t i o na n dp r i o r i t i z a t i o n t h em a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r el i s t e da sf o i l o w s f o ras p e c i a lk i n do fs y s t e m st h a ti n t e r a c t i o n so n l ye x i s ta m o n gn e i g h b o rf a c t o r s ，n e i g h b o rf a c t o r s c o m b i n a t o r i a lt e s t i n gm e t h o di sp r o p o s e d c o r r e s p o n d i n g l y , as e r i e so fo p t i m a lt e s tg e n e r a t i o n a l g o r i t h m sa r ea l s op r e s e n t e df o rf i x e ds t r e n g t ha n dv a r i a b l es t r e n g t hn e i g h b o rf a c t o r sc o v e r a g e i t i sp r o v e nb ya na p p l i c a t i o ns c e n a r i ot h a tt h en e i g h b o rf a c t o r sc o m b i n a t o r i a lt e s t i n gi sp r a c t i c a l 。 an e wm o d e lo fv a r i a b l es t r e n g t hc o m b i n a t o r i a lt e s t i n g , w h i c hm a k e ss u f f i c i e n tc o n s i d e r a t i o no n a c t u a li n t e r a c t i o nr e l a t i o n s h i p ，i sp r o p o s e d t og e n e r a t et e s ts u i t ef o rs u c hn e wv a r i a b l es t r e n g t h c o m b i n a t o r i a lt e s t i n gm e t h o d ，s e v e r a lh e u r i s t i ct e s tg e n e r a t i o n a l g o r i t h m sa 碍p r o p o s e d a n d c o m p a r e dt os o m ee x i s t i n ga l g o r i t h m sa n dt o o l s ，t h ep r o p o s e da l g o r i t h m sh a v es o m em e r i t s 。 an e wc o m b i n a t o r i a lt e s tp r i o r i t i z a t i o nt e c h n i q u e ，w h i c hi sb a s e do nt h ew e i g h t so fc o m b i n a t i o n a n dt h ec o s t so f t e s tc a s e ，i sp r o p o s e df o rr e g r e s s i o nt e s t i n g b e s i d e s ，a ni n c r e m e n t a lc o m b i n a t o r i a l t e s t p r i o r i t i z a t i o nt e c h n i q u e ，w h i c hc o u l ds a t i s f yt h er e q u i r e m e n to fi n c r e m e n t a lc o m b i n a t o r i a l c o v e r a g eb yp r i o r i t i z i n gt h et e s tc a s e si nah i g h s t r e n g t ht e s ts u i t e ，i sa l s op r o p o s e d 。t h ef a u l tl o c a t i o np r o b l e mi nc o m b i n a t o r i a lt e s t i n gi ss t u d i e db a s e do nt h em o d e lo fm i n i m a lf a u l t s c h e m a f i r s t l y , a l le x i s t i n gf a u l tl o c a t i o nm e t h o di sa n a l y z e di nt h e o r y f o rt h ed i s a d v a n t a g eo f e x i s t i n gm e t h o d ，a l li m p r o v e di t e r a t i v ef a u l tl o c a t i o nm e t h o di sp r o p o s e dt or a i s et h ep r e c i s i o n t h ee f f e c t i v e n e s so f n e wm e t h o d sc a nb ep r o v e ni nb o t ht h e o r ya n de x p e r i m e n t k e y w o r d s ：s o f t w a r ee n g i n e e r i n g ，s o f t w a r et e s t i n g , c o m b i n a t o r i a lt e s t i n g , t e s tg e n e r a t i o n , t e s tp r i o r i t i z a t i o n ， f a u l ti o c a l i z a t i o n 1 1 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 ，o 、 研究生签名： 兰衄2 日期： 2 q q 2 生鱼且! ! 目 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部内容或中、英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南大 学研究生院办理。 研究生签名：兰墨丞导师签名： 第一章引言 1 1 选题依据 第一章引言 近年来，随着计算机技术的进步，以软件系统为核心的计算机廊用已经渗透剑各行各业，在工 业、农业、国防、管理以及人们的日常生活中发挥着越来越重要的作用。因此，当今社会对于高质 量软件的需求也越来越迫切。与此同时，随着计算机软件规模的不断增长，软件质量问题逐渐成为 制约计算机发展和应用的瓶颈之一。而作为软件生命周期过程中的一个重要环节，软件测试对于保 证和提高软件产品的质量起着不可替代的重要作用，并在近年来受到人们越来越多的重视。 一般来讲，软件测试可以认为是一个为了发现软件中存在的错误而运行程序的过程i lj 。其中， 选择合理的测试用例集合是决定软件测试质量的重要因素之一。而测试j j 例的生成又可以被理解为 一个抽样过程，即根据一个给定的测试标准，对可用测试用例的全集进行抽样，从中选择一批错误 敏感的测试用例，使得该测试用例集触发软件错误的可能性尽可能高。一个合理的测试标准可以保 证测试用例集的错误检测能力：而一种有效的测试用例生成方法则可以在保证测试用例集质量的同 时，尽可能减小测试用例集的规模，从而降低软件测试的成本。 作为一个复杂的逻辑系统，有很多因素都可能会影响软件系统的正常运行，这些因素可能包括 系统的配置、内部事件、外部输入等。除了单个因素之外，这些因素之间的相互作用也可能会对系 统的正常运行造成影响。冈此，在对这类软件进行测试时，不仅要考虑所有可能对系统产生影响的 因素，对这些冈素之间的相互作用，即各个因素取值之间的组合也要进行充分的测试。但在设计和 生成相应的测试用例时，可能存在以下问题：首先，由于相关因素数量较多，各个冈素的取值情况 复杂，所有可能的冈素取值组合形成了一个规模巨大的测试片j 例空间，因此穷尽测试是不可取的； 其次，手工设计和选择测试用例缺乏科学依据，而且难度也比较火。 因此，在软件测试的实践中，为了用尽可能少的测试用例来有效地检测这些因素以及它们之间 的相互作用对系统产生的影响，从而在保证测试用例集错误检测能力的基础上尽可能地降低测试成 本，人们提山了基于组合覆盖的软件测试( 简称组合测试，c o m b i n a t o r i a lt e s t i n g 或i n t e r a c t i o nt e s t i n g ) 方法。一方面，针对一些内部冈素交互关系比较复杂的系统，进行完全组合测试是不现实的，人们 一般使用同定力度维组合测试方法，即选取一个合适的组合覆盖力度并保证测试片】例集覆盖 系统中任意个闪素之间的相互作用，这样可在大幅降低测试成本的同时，尽可能少地影响测试用 例的错误检测能力，同时保证所选测试用例在总的测试用例空间中具有良好的分布性质。在此基础 上，对系统中部分重要冈素的测试可能需要进行强化，为此可以考虑使用可变力度组合测试方法， 即除保证覆盖任意个 夭l 素之问的相互作用之外，同时还保证覆盖任意大于个重要i 天i 素之间的相 互作j h i 。另一方面，如果某些系统中因素间相互作用的关系比较容易获取，则可以根据因素间的实 际或是近似的交互关系米设计测试用例集，从而保证对冈素间交互作用进行有效的测试。 组合测试的关键问题包括软件系统组合模型的抽取、测试用例生成、测试结果的分析评估、组 合测试故障诊断以及组合测试过程改进等方面。组合测试领域最为核心的关键问题是，如何以快捷 的速度精心设计一个科学的、规模尽可能小的组合测试用例集，以实现对待测试软件科学有效的测 试，并形成对该软件质量的科学判断。但由于组合测试用例生成问题的n p - c 性质i m j ，我们无法在 多项式时间内得到最优解，这就给组合测试的实际应用带米了极大的不便，并使得测试用例的生成 问题成为影响组合测试方法j “泛应用的瓶颈之一。 由于计算机软件是一种特殊的产品，不仅其他领域关于产品检查测试的方法可以被软件测试借 鉴和使用，在软件测试技术领域有效的研究结果同时也可以为其他领域的质量检查提供新的思路。 因此，组合测试技术的研究结果不仅可以对软件测试领域产生积极作用，也可以广泛地应用到各行 各业，从而对经济建设产生积极的影响。例如，使用止交实验设计和组合设计方法进行实验设计的 方法，最早曾被广泛应用于工农业的生产实践。 东南人学博二l 学位论文 组合测试技术的研究不仅在应用领域具有重要价值，在理论上也具有重要的科学价值。组合测 试技术领域的研究充分反映了计算机科学领域抽象、理论和设计的三个学科形态的特征。例如，组 合测试用例集生成的问题目前已被抽象为一个具有典型应用背景的数学问题，即最优组合设计问题。 而最优组合设计问题目前也己引起了数学界广泛的研究兴趣。 1 2 国内外研究现状 自1 9 8 5 年r m a n d l 首次尝试将固定力度二维组合测试技术应用于a d a 编译器的测试以来1 5 1 ， 基于组合覆盖的软件测试技术得到人们的广泛研究，并广泛应用于具有复杂配置的软件系统的测试 中【6 l 。目前组合测试领域的研究成果主要包括组合测试模型、组合测试用例生成、组合测试用例优 化、组合测试的应用、组合测试中的故障定位技术、以及错误检测能力分析等方面。其中，组合测 试用例的生成技术及其相关问题一直是组合测试领域研究的重点之一。 ( 1 ) 固定力度组合测试用倒集的生成 对于固定力度组合测试片j 例集的生成问题，目前已有大量研究成果。人们并先后尝试了组合设 计方法、启发式算法、以及元启发式搜索算法等不同类型的方法来生成组合测试用例集。 在组合测试应用的y - 期，人们主要使用正交拉丁方1 5 l 和正交表1 7j 来产生组合测试用例集。此后， 人们开始大晕使用递门构造的方法生成测试用例集，例如基于正交表的二维组合测试用例集构造方 法【、基于完美哈希族( p e r f e c th a s hf a m i l y ) 的三维组合测试用例集构造方法【1 2 】；等等。在此基础上， i b m 的a h a r t m a n 等人综合利用多种递归构造方法，开发了工具c t s 1 3 1 4 j 。此外，针对二水平多因 素系统，人们对其二维组合测试用例集的性质和生成方法进行了深入研列b o 引。 除组合设计方法外，人们也尝试了一些基于贪心策略的启发式算法。例如，贝尔实验室d m c o h e n 等人提出的a e t g 2 0 - 2 2 1 、喷气推进实验室yw t u n g 等人提出的t c g l 2 3 1 、以及c j c o l b o u m 等人提出 的d d a 2 4 ，2 5 l 等等。此外，本课题组也曾提出了g a _ n 2 6 1 、p s s t 【2 7 ，2 8 】等算法。上述这些算法均基于 o n e - t e s t - a t - a - t i m e 策略i z 9 3 0 1 , 即逐条选取测试用例，直至所有组合都被测试用例集所覆盖。它们都具 有思想简单，易于实现、便于扩展、贴近应用的优点。 除o n e - t e s t - a t - a - t i m e 策略外，yl e i 和k c t a i 还提出了一种以因素顺序扩充的方式生成组合组 合测试川例集的启发式策略i n p a r a m e t e r - o r d e r 。他们先后对该策略在二维、以及高维组合测试用例 集生成中的应用进行了研究，提出了i p o 、i p o g 等算法，并开发了p a i r t e s t 、f i r e e y e 等工具【3 ，3 1 。3 3 1 。 基于类似的策略，本课题组也曾提出一种以网络图为基础的二维组合测试用例生成算法1 3 4 】。 元启发式搜索算法作为解决组合优化问题的一种重要手段，在组合测试用例集生成问题中也得 到了应用。目前，人们已经对模拟退火、禁忌搜索、洪水算法、爬山算法等多种单点搜索算法( i n d i v i d u a l s e a r c h ) ，以及遗传算法、蚁群算法等群体搜索算法( p o p u l a t i o ns e a r c h ) 在组合测试用例集生成中的 应用进行了广泛的研究，并先后使用了覆盖率驱动的直接搜索【3 5 4 0 1 、组合驱动的直接搜索【4 1 1 、以及 o n e - t e s t - a t - a - t i m e 框架下的搜索1 4 2 ，4 副等具体搜索策略。相对于使用贪心策略的启发式方法，这类方法 往往可以生成规模比较小的测试用例集，但其普遍问题是运行时问较长。 此外，人们还考虑将组合测试用例集生成问题转化为一些其它类犁的问题。例如，可以将该问 题转化可满足性问题，b h n i c h 等人1 4 4 l 和严俊、张健等人 4 5 , 4 6 j 分别研究了使用局部搜索和完备搜索 的s a tt 具生成固定力度组合测试用例集的方法；a w w i l l i a m s 等人将同定力度组合测试用例集 生成问题转化为0 1 整数规划问题1 4 j ：k m e a g h e r 等人则将二维组合测试用例集的生成问题可转化为 无向图上的问题，并研究了相应的组合测试用例集生成方法 4 7 , 4 8 l 。 ( 2 ) 可变力度组合测试用例集的生成 m b c o h e n 等人提出了可变力度组合测试( v a r i a b l es t r e n g t hi n t e r a c t i o nt e s t i n g ) 的概念。可变 力度组合测试是对传统固定力度组合测试的加强，即在保证系统中任意个因素间的取值组合均被 覆盖的基础上，对其中一些比较重要的因素实施强度更高的组合覆盖。m b c o h e n 等人使用模拟退 火算法来解决相应的测试用例集生成问题【3 6 l 。 2 第一章引言 p j s c h r o e d e r 研究了基于输入输出关系的组合测试方法，并给出了三种相应的测试用例集生成 和约简算法m i n 、u n i o n 、以及g 1 e e 4 们。其中m i n 采用穷举搜索的方式寻找最优测试用例集，不 具有实用性；u n i o n 首先对每一个输出设计一组测试用例，然后将这些测试用例直接求并，其算法 简单但效果较差；而g r e e d y 是基于全局解空间搜索的贪心算法，效果相对较好，但效率极低。此后， p j s c h r o e d e r 等人针对贪心算法g r e e d y 效率较差的弱点，提出了一种对输入输出关系进行约简的 方法。但这种约简的方法具有较大的局限性，仅适用于输入输出关系数鬣较少的情况，并且有可能 导致测试片j 例集规模的膨胀p o l 。 可变力度组合测试和基于输入输 j j 关系的组合测试都在一定程度上考虑了组合测试中因素间交 互作用的特殊性。但前者只是对传统组合测试的简单改进，难以处理一些复杂情况下的因素间交互 关系。而后者仅研究输入输出测试，没有考虑组合测试的其它应用场景，因而不具有普遍性，而且 所提出的几种测试用例集生成算法也难以满足实际应用的需要。 ( 3 ) 组合测试用例的优化使用 在实际软件测试过程中，可能需要考虑组合权重的问题，对于具有高权重的组合，应该进行组 合测试时给予优先的考虑。为此，r c b r y c e 和c j c o l b o u r n 等人研究了优先级条件下的固定力度 组合测试j 】例集生成技术，并在d d a 算法基础上提出了一种改进的算法1 5 卜 1 。此外，r c b r y c e 和a m m e m o n 等人研究了固定力度组合测试用例的优先级复用技术，在不考虑组合权重而只要求 尽快、尽早覆盖所有组合的条件下，提出了相应的测试用例排序算法瞰】。使用这些测试用例优先级 技术可以优化组合测试用例序列的性能，从而在测试资源受限的情况下提高测试效率。 在实际的软件测试中，系统中各个阂素问可能存在一定的依赖关系，从而导致这些冈素中某些 取值的组合受到约束，这种约束分为非强制性约束( s o f tc o n s t r a i n t ) 和强制性约束( h a r dc o n s t r a i n t ) 等两类【5 1 1 。如果能在生成组合测试用例集时正确处理这些约束，同样可以优化测试用例集的性能。 为此，r c b r y c e 等人研究了非强制性约束条件下的d d a 算法【5 1 j ，而m g r i n d a l 和j o f f u t t 等人则 针对强制性约束问题提出了四种不同类型的解决方案5 5 ，5 们，a e t g t 2 们、p i c t l 5 7 1 、c t s l l 3 ，1 4 】等系统即 使用了这些解决方案来处理组合测试用例集生成时的组合约束问题。 ( 4 ) 组合测试过程和组合测试策略 故障定位是测试过程中一个必不可少的重要环节，它在软件调试过程起着极为重要的作用。本 课题组以极小故障模式( m i n i m a lf a u l ts c h e m a ) 模璎为基础，提出了一种基于附加测试用例的故障 定位方法1 5 8 1 。除此之外，人们还从其它角度出发研究了组合测试中的故障定位问题，如c j c o l b o u r n 、 d w m c c l a r y 研究了通过检测表( d e t e c t i n ga r r a y ) 和定位表( l o c a t i n ga r m y ) 等两种特殊的测试 用例集来检测软件故障并定位故障诱冈的方法【5 9 i 。 人们对组合测试的具体测试策略也进行了一定的研究，例如j b a c h 和pj s c h r o e d e r 对一些公 开的测试案例进行了研究，指出了组合测试技术在实际应用时应注意的一些问题，并提出了一些合 理的建议1 6 0 】。除已知的i 捌定力度组合测试、可变力度组合测试、输入输出关系测试等具体测试方法 和测试策略外，针对同定力度组合测试方法可能存在的问题，s f o u c h e 、m b c o h e n 等人提出的一 种增量式自适应组合测试策略( i n c r e m e n t a la d a p t i v es t r a t e g y ) 1 6 l j 。 除上述工作外，人们还对组合测试领域的其它一些问题进行了研究，如组合测试在特定类型软 件系统中的应用、组合测试错误检测能力的度量等。由于它们与本文研究工作之间没有太多的联系， 我们对此不再赘述。 1 3 主要研究内容 软件测试是一项贯穿于整个软件开发生命周期的、对软件产品进行验证和确认的活动，其目的 是尽快、尽早地发现软件产品中存在的各种缺陷和问题f 。一个完整的测试过程一般应该包含测试 模型和测试充分性标准的选取、测试用例集的生成、测试用例的执行、测试结果分析等儿个过程。 此外，如果在测试过程中触发了软件故障，还需要进行故障定位，并在错误排除后进行同归测试。 3 东南大学博j l ：学位论文 图1 1 简要描述了上述过程。当我们的测试目标为检测软件中各个因素间的交互作用时，组合测试 方法就成为一种合适的选择。此时，我们仍然面临着组合测试模型的选取、组合测试用例集的生成、 组合测试中的故障定位、以及组合测试中的同归测试等具体问题。我们拟从这四个方面，对组合测 试中的几个主要环节进行系统性的研究，研究的重点在于组合测试用例的生成和优化。 图1 1 软件测试的基本流程 ( 1 ) 组合测试模型 我们首先对组合测试模型进行了研究。 针对一类只在相邻因素间存在交互作用的软件系统，我们提出了一种相邻因素组合测试模型。 在其适用范闱内，这一方法可在简化测试过程、降低测试用例集规模、节约测试成本的同时，保证 测试用例集的错误检测能力不受影响。 针对传统的固定力度组合测试方法和可变力度组合测试方法中存在的问题，我们提出了一种新 的可变力度组合测试模型。该模型充分考虑了待测软件系统中因素问的实际交互关系，并能够更为 准确地描述这种冈素间交互关系。 ( 2 ) 组合测试用倒集生成技术 在提出两种新的组合测试模型后，我们对相应的组合测试用例集生成技术进行了研究，其目标 在于使用尽可能少的测试用例满足给定的测试充分性标准。 针对相邻囚素组合测试模型，研究了相应的相邻因素组合测试用例集生成算法。针对固定力度 下的相邻因素二维组合覆盖、固定力度下的相邻冈素维组合覆盖、及可变力度相邻因素组合覆盖， 我们均提出了多项式时间的最小测试用例集生成算法。最后，我们还针对一个具体的应用场景，分 析了相邻冈素组合测试方法在其适用范围内所具有的优势。 针对我们提出的可变力度组合测试模型，研究了多种基于启发式策略的可变力度组合测试用例 集生成算法。首先针对输入输出关系测试中u n i o n 算法的缺陷，提出了一种改进的算法r e q m e r g e ， 并研究了算法的具体配置：以同定力度组合测试用例生成时常用的i n p a r a m e t e r - o r d e r 策略为基础， 提出了一种基于贪心策略的算法p a r a o r d e r ，并研究了算法的具体配置；以o n e - t e s t - a t - a - t i m e 策略为 基础，提出了两种不同的贪心算法d a r o 和d a f o 。实验表明，我们提出的算法在各种情况下均 具备一定的特点和优势。 ( 3 ) 组合测试用例优先级优化技术 在同归测试时，存在一个已有的测试用例集及相应的测试历史，利用这些信息为测试用例设置 不同的优先级，可有效地提高测试效率。为此，我们对组合测试用例优先级技术进行了研究。 在使用组合测试方法进行回归测试的应用场景下，研究了基于组合权重和测试开销的组合测试 用例优先级技术，在提出相应的优先级度鼍标准的基础上，提出了两种组合测试用例优先级排序算 法t o t a l c t p r i 和a d d t l c t p r i 。通过实验发现，无反馈的t o t a l c t p r i 算法具有与带反馈的a d d t l c t p r i 算法相近甚至相同的效果，这与一些已有结论有所不同。此外，即使是在非回归测试的场景f ，相 对于已有的组合测试用例优先级生成方法，本文提出的方法仍然具有较大的优势。 在增量式自适应组合测试的基础上，提出了一种增量式组合测试用例优先级方法。该方法首先 生成一个同定力度高维的组合测试用例集，然后按照增营式组合测试的思想对测试用例执行次序进 行重新排序。实验表明，尽管在覆盖低维组合时效率可能有所f 降，但新的方法可以使用更少的测 试用例米实现最终的测试目标。 4 第一章引言 ( 4 ) 组合测试故障定位技术 最后，以极小故障模式模型为基础，我们对组合测试中的故障定位技术进行了研究。 在极小故障模式模型的基础上，本课题组曾提出一种组合测试故障定位方法d d r 。这一方法可 将导致测试用例失败的极小故障模式精确定位或是确定在一定范围内l 鼹l ，但其实际性能和故障定位 的精确性目前尚无定论。为此，我们从定全率( r e c a l l ) 和定准率( p r e c i s i o n ) 等方面分析了该方法 的理论性质，进而得出一系列有意义的结论。 研究发现，已有方法d d r 可以保证百分之百的定全率，即所得结果中一定包含了所有已被测试 用例命中的极小故障模式；但无法保证定准率，即所得结果中可能存在一些不会引发错误的非故障 模式。针对这一缺陷，我们对已有方法进行改进，提出了一种迭代式的故障定位方法l t e r a t i v e d d r 。 这一方法通过增加附加测试用例数量的方式来提高故障定位结果的精确性。理论分析和实验结果均 表明，l t e r a t i v e d d r 可有效地提高故障定位结果的精确性。 1 4 论文主要成果 针对实际应用中可能出现的需求，我们提出了两种新的组合测试模型，对相应的组合测试用例 集生成技术进行了研究，并提出了一系列相应的测试用例集生成算法。此外，我们还针对回归测试 这一应用场景，从测试用例优先级技术的角度研究了组合测试用例的优化使用问题。最后，我们还 对组合测试中的故障定位问题进行了研究。 本文的主要成果表现在以f j l 个方面： 提出了一种相邻因素组合测试方法，并给出了固定力度、及可变力度相邻冈素组合测试用例 集生成算法，这些算法均可在多项式时问内生成最小测试j i 例集。实例分析表明，相邻因素 组合测试方法在其适用范围内具有很好的性能。 提出了一种新的可变力度组合测试方法，并提出了一系列用于生成可变力度组合测试用例集 的启发式算法。实验表明，本文提出的算法在生成i 古| 定力度、以及可变力度组合测试用例集 时均具备一定的特点和优势。 研究了基于组合权重及测试用例运行开销的组合测试用例优先级复用技术，提出了两种组合 测试用例优先级排序算法，并通过实验分析了算法的性能。实验结果同时说明，相对于已有 方法，新技术在各方面均具备较大的优势。 提出了一种增量式组合测试刚例优先级技术，通过对已有组合测试用例集中的测试用例进行 排序的方式，使得测试用例序列满足增量式组合覆盖的要求。实验表明，相对于已有的增量 式自适应组合测试方法，新方法具备一定的特点和优势。 在极小故障模式模型的基础上，对已有组合测试故障定位方法的性能进行了理论分析，从定 全率和定准率等两个角度说明了已有故障定位方法的故障定位能力，指出已有方法在故障定 位结果的定准率上存在一定的缺陷。 针对已有故障定位方法存在的缺陷，在极小故障模式模型的基础上提出了一种迭代式的故障 定位方法，通过增加附加测试用例数鼍的方式来提高故障定位能力。理论分析和实验结果均 表明，新的方法可以有效地提高故障定位结果的定准率。 开发了一个组合测试辅助上具集c t t ，为研究和应用提供了一个可配置、可扩展的平台。 1 5 论文结构 本论文剩余部分组织结构如下： 第二章从组合测试模型、组合测试用例集生成方法、组合测试中的约束问题、组合测试用例优 化等方面，对组合测试领域与本文研究内容相关的已有工作和成果进行了总结。 第三章提出了一种相邻【天i 素组合测试模型，并研究了相邻囚素组合测试用例集的生成问题，给 出了多项式时间的最小相邻因素组合测试用例集生成算法。 5 东南大学博一f ：学位论文 第四章提出了一种新的可变力度组合测试模型，并研究了可变力度组合测试用例集的生成问题， 给出了多种用于生成可变力度组合测试用例集的启发式算法，最后通过实验分析了算法的性能。 第芤章对组合测试用例优先级问题进行了研究，首先研究了基于组合权重及测试开销的组合测 试用例优先级技术，此外还对增鼙式组合测试用例优先级技术进行了研究。 第入章对组合测试的故障定位问题进行了研究，首先从理论上分析了已有故障定位方法的性能， 针对已有方法存在的缺陷，进而提出了一种改进的故障定位方法。 第七章介绍了组合测试工具集c t t 的设计与实现。 第八章对整篇论文进行了简要的总结。 6 第二章组合测试问题研究现状 第二章组合测试问题研究现状 本章旨在简要介绍组合测试领域一些科学问题的研究现状。组合测试用例集的生成问题是组合 测试领域最重要的科学问题之一，目前所报道的国内外研究：l 作中，大部分均以组合测试用例集的 生成问题作为研究重点。因此，本章对这一问题的研究现状进行了简要介绍。此外，对于组合测试 用例集生成和使用中所面临的其它一些问题，如组合约束条件、测试用例优先级等，本章也进行了 讨论。最后，简要介绍了组合测试技术在实际应用中的一些结论。 2 1 组合测试模型 假设影响待测软件系统( s y s t e mu n d e rt e s t ，简称s u t ) 的因素共有力个，这些因素形成有限 集合，- 饼，五，石 ，其中因素石经过等价类划分等前期处理后共包含a t 个可选取值，从而形成该 因素的可选取值集合降 l ，2 ，嘶 ( 1 9 勤) 。 定义2 1 如果某个s u t 中所有因素取值数量均相等，即a i = _ 口2 = = ，则称该s u t 为单一水平 系统；否则，则称该s u t 为混合水平系统。 定义2 2 称一个刀元组t e s t = ( ，l ，耽，) ( v l n ，v 2 圪，v n e 圪) 为s u t 的一条测试用例。 相应地，称一个由多条这样的测试用例所构成的集合为s u t 的一个测试用例集。 在组合测试领域中，组合测试用例集往往又被称为组合覆盖表，简称覆盖表( c o v e r i n ga r r a y ) 。 覆盖表中的每一行均对应测试用例集中的一条测试用例，覆盖表的行数即是测试用例集的规模。因 此，在下文中我们不再严格区分覆盖表和测试用例集的概念，并认为两者等价。 组合测试的目的在于对软件中各个因素之问的交互作用进行测试。不同的组合覆盖标准决定了 测试用例集对于因素间交互作用的不同覆盖能力，也决定了其不同的错误检测能力，因此虑根据待 测软件的特征选择合适的组合覆盖标准。在分析已有工作的基础上，我们将现有组合覆盖标准分为 固定力度组合覆盖和可变力度组合覆盖等两大类，并分别对其进行介绍。 2 1 1 固定力度组合测试 在一般的软件测试中，若不考虑因素之间的交互作用，则只需要设计一组测试用例，使其覆盖 每一个因素的所有可能取值即可，即满足单因素覆盖标准。 定义2 3 设彳啾，) 肼。为一个m x n 的矩阵，其第_ ，列表示s u t 的因素石，其中所有元素均取自集 合场u = 1 ，2 ，刀) ，即口j ，巧。若对于任意j ( 1 9 勤) ，彳中的第，列均包含了巧中所有a j 个元素， 则称彳为单因素覆盖表，并称彳满足单冈素覆盖的要求。对于一个单因素覆盖表彳，如果m 是能够 保证上述条件成立的最小正整数，即m - - m a x , a ， ，则称彳为最优单因素覆盖表。 而在组合测试中，需要考虑因素之间的交互作用，并根据冈素问的交互作用设计测试用例集， 以覆盖某些给定的因素取值组合。例如，假设任意两个因素间均存在交互作用，则必须保证覆盖任 意两个因素间所有的取值组合，即需要满足二维组合覆盖标准。 定义2 4 设彳= 瓴加。为一个m x n 的矩阵，其第j 列表示s u t 的因素石，其中所有元素均取自集 合巧q = l ，2 ，疗) ，即口f l ，巧。如果对于彳中任意i , j ( 筒) 两列，均满足：所和巧中元素的所有 二元组合均在该两列所形成的二元有序组中出现至少一次，则称彳为二维组合覆盖表，并称彳满足 二维组合覆盖的标准。对于一个二维组合覆盖表彳，如果m 是能够保证上述条件成立的最小正整数， 则称a 为最优二维组合覆盖表。 在此基础上进行扩展，可以得到任意( 1 5 1 ) 维组合覆盖的定义。 定义2 5 设4 = ( 瓯加。为一个m x n 的矩阵，其第，列表示s o t 的因素石，其中所有元素均取自集 合巧u = l ，2 ，刀) ，即吼，巧。给定正整数( 1 蛐) ，如果彳中任意列，即第f l ，如，i m 列均 7 东南大学博： ：学位论文 满足：，中符号的所有的元组合均在这列所形成的元有序组中至少出现一次，则 称a 为维组合覆盖表，记作c 爿。刀；，d ，并称a 满足维组合覆盖的标准。对于一个维组合 覆盖表彳，如果m 是能够保证上述条件成立的最小正整数，则称a 为最优维组合覆盖表。 定义2 6 由于假设系统中任意个冈素问均存在交互作用，即系统中所有的因素间交互作用的 力度均为，因此我们义称维组合覆盖表为固定力度的组合覆盖表。其中，正整数称为组合覆 盖的力度( 或是因素间交互作用的力度) 。 显然，二维组合覆盖则是固定力度组合覆盖在n = 2 时的一种特殊情况。而单冈素覆盖可以看作 是固定力度组合覆盖在n = - i 时的一种特殊情况，但相对于n i 时的同定力度组合覆盖，单冈素覆盖 标准相对简单，最好情况下覆盖表a 的规模仅为肝= m a 蜀 铆 。固定力度组合覆盖的另外一种特殊情 况是n = n 时的完全组合覆盖，此时有肝= 兀名i a 。由于单因素组合覆盖和完全组合覆盖的特殊性质， 因此在考虑同定力度组合覆盖一般将其排除在外。如无特殊强调，下文所指的同定力度组合覆盖均 只考虑2 5 ；嘲时的情况。 我们将使用同定力度组合覆盖表设计组合测试用例集的方法称为同定力度组合测试方法。使用 同定力度下的维组合测试方法可以保证对软件中任意个因素之间的交互作用进行覆盖，从而保 证检测出这些交互作用可能引发的错误。例如，对于一个如图2 1 所示的面向对象系统进行类交互 测试时，每次测试均需要从4 个类体系结构( c l a s sc l u s