（计算机软件与理论专业论文）可配置ipo的测试用例生成.pdf

at h e s i ss u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y s u nw ，e n w e n s u p e r v i s e db y p r o f e s s o rn i e c h a n g h a i s c h o o lo f c o m p u t e rs c i e n c e & e n g i n e e r i n g s o u t h e a s tu n i v e r s i t y m a r c h2 0 1 0 i f 万可雨r ：睁 目蓦弼3 髟翁苇延抱 。巢 5 l 上些辇 萁的骢朝魄朗上勘七b 茸砚翠目瞬涮兽鲥丑朝】j 5 1 垢肇地章鞑翠刨朝勘工刨一錾与。林桦朝 取茸觋业肆皿臻玛杀朝瞵碑旦骣罩并疆赤￥掣霉台i 雏椠号曰业毋酱搿鹭抱朝辩皇游狂 擎髯葛1 己y 融嚣号母业串茸觇蟛华孵鲷鞭砸唑瑕斟询睥暗辨七b 茸上割蟛蚓棰哲。凿 翠琶抱鲷台i 碓暂勤工延抱鲷身檠土合群蛳畚翠y 少獯瞽茸碘母嘉朝莓百增的革y 牢 i 乙z 91 , 9 ll 人 l | j j f f i i j l l f | f 洲f f i l 胁 舶革科晦穰茸歌科毒毒￥阜半 ， 一 j n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名：日期： 东南大学学位论文使用授 东南大学、中国科学技术信息研究所、国家图书馆有权保 复印件和电子文档，可以采用影印、缩印或其他复制手段保存 容和纸质论文的内容相一致。除在保密期内的保密论文外，允 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 究生院办理。 研究生签名：导师签名： 摘要 题目：可配置i p o 的测试用例生成 硕士研究生姓名：孙文雯 导师姓名：聂长海副教授 学校名称：东南大学 摘要 随着软件系统复杂度的提高，使得影响软件运行的因素越来越多，这些因素以及因 素间的交互作用很可能引发软件故障，从而影响系统的j 下常运行。如何科学、有效的检 测出由因素及因素间的交互作用所引发的软件故障，成为了软件测试尤其是黑盒测试中 的一个重要问题。组合测试就是解决该问题的一个行之有效的方法，可以以较短的时间 生成规模较小的测试用例集，来检测因素间的交互对软件系统运行的影响。基于参数顺 序渐进扩充策略i p o ( i n p a r a m e t e r - o r d e r ) 是组合测试领域中的一种具有代表性的通用 算法，其优势在于水平扩充算法的可选择性和测试用例集的可扩展性。 本文以高效的生成组合测试用例集为目标，在对i p o 策略进行了充分、细致研究的 基础上，结合i p o 策略可扩展性，提取出影响i p o 策略具体实现的算法参数，提出了新 的可配置的i p o 框架，使得对i p o 策略的理解更为深入，并使其实现更为灵活；结合 i p o 策略的水平扩充和垂直扩充均可进行算法局部优化的特性，将遗传算法( g a ) 集 成至可配置i p o 框架的水平扩充部分，结合两种算法的优点，得到一个新的组合测试用 例集的混合算法i p og a ，为用i p o 策略生成组合测试用例集提供了一种新思路。 论文的具体研究工作主要包括以下几方面： ( 1 ) 研究和分析i p o 策略的优点和弊端，结合其可扩展特性，提取了影响i p o 实 现的算法参数，实现了可配置的i p o 框架； ( 2 ) 深入研究和分析了如何用遗传算法生成组合测试用例集，结合i p o 策略中水 平扩充和垂直扩充均可进行局部优化的特性，在可配置的i p o 框架中应用遗传算法进行 水平扩充，得到了新的组合测试用例集的混合生成算法i p og a ； ( 3 ) 为更方便的对相关算法进行研究，实现了基于原i p o 策略、原遗传算法、可 配置的i p o 框架和i p og a 的自动化测试用例集生成工具； ( 4 ) 对可配置i p o 框架中各参数对算法实现的影响进行了实验和分析，并将 i p og a 与部分已有算法进行比较。 关键词：组合测试，测试用例集生成，i p o ，遗传算法 东南大学硕： ：学位论文 a b s t r a c t t i t l e ：c o m b i n a t o r i a lt e s t i n gs u i t eg e n e r a t i o nu s i n gc o n f i g u r a b l ei p o n a m e ：s u nw e n w e n s u p e r v i s o r ：p r o f n i ec h a n g - h a i s c h o o l ：s o u t h e a s tu n i v e r s i t y a st h er a i s eo fc o m p l e x i t yo fs o f t w a r es y s t e m s ，b r i n gt h ef a c t o r st h a ta f f e c tr u n n i n g e f f e c to fas o f t w a r em o r ea n dm o r e t h ef a c t o r sa n dt h ei n t e r a c t i o n sa m o n gt h e s ef a c t o r s w o u l dp r o b a b l yt r i g g e rs o r w a r ed e f e c t st h e r e b ya f f e c tt h er e g u l a rr u n n i n go ft h es o f t w a r e s y s t e m t od e t e c tt h es o f t w a r ed e f e c t sc a u s e db 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 gt h e f a c t o r ss c i e n t i f i c a l l ya n de f f e c t i v e l yi saq u i t ei m p o r t a n tp r o b l e mo fs o f t w a r et e s t i n g , e s p e c i a l l yo ft h eb l a c k b o xt e s t i n g c o m b i n a t o r i a lt e s t i n gi so n eo ft h ee f f e c t i v ew a y so f s o l v i n gt h i sp r o b l e m ，w h i c hc a ng e n e r a t es m a l l e rt e s t i n gs u i t ei ns h o r t e rt i m et od e t e c tt h e e f f e c to fi n t e r a c t i o n sa m o n gt h ef a c t o r so ns o f t w a r er u n n i n g i np a r a m e t e ro r d e rs t r a t e g yi s o n er e p r e s e n t a t i v ep o p u l a rm e t h o di nt h er e s e a r c hf i e l d a n dt h ea d v a n t a g eo fw h i c hr e l i e so n t h es e l e c t i v i t yo fh o r i z o n t a le x p a n d i n ga n dt h ee x t e n d i b i l i t yo fg e n e r a t e dt e s ts u i t e t h i sd i s s e r t a t i o na i m st og e n e r a t ec o m b i n a t o r i a lt e s t i n gs u i t ee f f e c t i v e l y , c o m b i n e st h e e x t e n d i b i l i t yo ft h ei p 0s t r a t e g ya n da b s t r a c tt h ea l g o r i t h mp a r a m e t e r sw h i c hw o u l da f f e c tt h e i m p l e m e n t a t i o no fi p ob a s e da na d e q u a t ea n dd e l i c a t er e s e a r c h p r e s e n t san e wc o n f i g u r a b l e i p ol a m ew h i c hm a k e st h eu n d e r s t a n d i n go fr e s e a r c h e r sm o r ed e e p l ya n dm a k et h e i m p l e m e n t a t i o no fi p om o r ef l e x i b l e ；c o m b i n e st h ec h a r a c t e r i s t i ct h a tb o t ht h eh o r i z o n t a l e x p a n d i n ga l g o r i t h ma n dt h ev e r t i c a le x p a n d i n ga l g o r i t h mc a nb el o c a l l yo p t i m i z e d ，i n t e g r a t e s t h eg e n e t i ca l g o r i t h mt ot h eh o r i z o n t a le x p a n d i n g p a r to ft h ec o n f i g u r a b l ei p 0f r a m es ot h e a d v a n t a g e so ft h e s et w oc a l lb ec o m b i n e d ，p r e s e n t sam i x e da l g o r i t h mi p og aw h i c h p r o v i d e san e wt h o u g h to fu s i n gi p 0 t og e n e r a t ec o m b i n a t o r i a lt e s t i n gs u i t e t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r el i s t e da sf o l l o w s ( 1 ) r e s e a r c h e sa n da n a l y z e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so fi p 0s t r a t e g yd e e p l y , a b s t r a c t st h ea l g o r i t h mp a r a m e t e r sw h i c hw o u l da f f e c tt h ei m p l e m e n t a t i o no ft h es t r a t e g y c o m b i n i n gt h ee x t e n d i b i l i t yo ft h es t r a t e g ya n di m p l e m e n t e dt h ec o n f i g u r a b l ei p of r a m e ； ( 2 ) r e s e a r c h e sa n da n a l y z e sh o wt og e n e r a t ec o m b i n a t o r i a lt e s t i n gs u i t eu s i n gg e n e t i c a l g o r i t h m ，c o m b i n e st h ec h a r a c t e r i s t i ct h a tb o t ht h eh o r i z o n t a le x p a n d i n ga n dt h ev e r t i c a l e x p a n d i n go fi p o c a nb el o c a l l yo p t i m i z e da n du s eg aa st h e h o r i z o n t a le x p a n d i n ga l g o r i t h m p r e s e n t sa n e wm i x e dc o m b i n a t o r i a lt e s t i n gs u i t eg e n e r a t i o na l g o r i t h mi p 0g a ： ( 3 ) t or e s e a r c hr e l a t e da l g o r i t h m sm o r ec o n v e n i e n t l y , i m p l e m e n t e da u t o m a t e d c o m b i n a t o r i a lt e s t i n gs u i t eg e n e r a t i o nt o o lb a s e do nt h eo r i g i n a li p os t r a t e g y , o r i g i n a lg a ， c o n f i g u r a b l ei p 0f r a m ea n di p 0g a ： ( 4 ) p e r f o r ma ne x p e r i m e n to nt h ee f f e c tt h a tt h ea l g o r i t h mp a r a m e t e r sd ot ot h e i m p l e m e n t a t i o no fc o n f i g u r a b l ei p of r a m ea n dd or e l a t e da n a l y z e ，a l s oc o m p a r et h ea l g o r i t h m e f f e c tb e t w e e ni p og aa n ds o m eo t h e ra l g o r i t h m s k e yw o r d s ：c o m b i n a t o r i a lt e s t i n g ，t e s ts u i t eg e n e r a t i o n ， i n p a r a m e t e r - o r d e r ，g e n e t i c a l g o r i t h m i l 目录 目录 摘要i a b s t r a c t i i 目录i i i 第一章绪论1 1 1 选题依据1 1 2 研究现状及存在的问题2 1 3 主要研究内容3 1 4 本文的组织结构3 第二章组合测试模型及组合测试用例集生成算法概述5 2 1 组合测试模型5 2 2 组合测试用例集的生成6 2 2 1 代数方法7 2 2 2 随机方法8 2 2 3 计算机方法8 2 2 4 混合方法1 4 2 3 组合测试的应用研究1 4 2 4 本章小结1 5 第三章可配置i p o 框架下的组合测试用例集生成1 6 3 1 用i p o 算法生成组合测试用例集1 6 3 1 1 基于i p o 的组合测试用例生成的算法流程1 6 3 1 2i p o 的水平扩充算法1 7 3 1 3i p o 的垂直扩充算法1 8 3 1 4 结合实例说明i p o 的具体实现1 8 3 2 影响i p o 策略的算法参数2 0 3 3 可配置的i p o 框架2 2 3 4 本章小结2 2 第四章用i p o _ g a 混合算法生成组合测试用例集2 4 4 1 基于g a 的组合测试用例集生成2 4 4 2 用i p o _ g a 混合算法生成组合测试用例集2 5 4 3 本章小结2 7 第五章基于可配置i p o 框架的工具实现与实验评估2 8 5 1 工具的设计与实现2 8 5 2 算法参数对可配置i p o 运行结果的影响2 9 h i 东南大学硕上学位论义 5 3i p o _ g a 的算法效果3 2 第六章总结与展望3 3 6 1 论文总结3 3 6 2 未来一l 作展望3 3 致谢3 5 参考文献3 6 i v 第一章绪论 1 1 选题依据 第一章绪论 计算机科学技术的发展，使得软件系统在各行各业中的应用越来越广泛深入，给人 们的生产和生活带来了巨大的便利，但随之而来的软件质量保障问题也成为了制约软件 行业发展的瓶颈。软件测试作为软件质量保障中不可或缺的重要坏节，如何充分、有效 的测试系统为其重要命题之一。 测试用例作为软件测试工作中的标准，指导了测试的实施，不仅是评估测试结果的 度量标准，也是分析软件缺陷的重要依据，因此，为软件系统选择一个合理、有效的测 试用例集将直接决定软件测试的质量，即在保证测试用例集具有较高的软件故障检测率 的同时，使用例集的规模尽可能的小，这样也可以大大减少软件测试所需的时问，降低 软件测试的成本。 软件系统复杂度的提高，增加了影响软件j 下常运行的因素，如系统配罨、内部事件、 外部输入等。甚至因素之间的交互作用也会影响软件的运行，因此在为待测软件s u t ( s o f t w a r eu n d e r t e s t ) 设计测试用例集时，若只考虑为单个因素引起的软件故障设计测 试用例集，会导致软件测试的充分性不够；由于影响软件的因素及因素的可选值很多， 若要检测因素间所有可能的交互，即进行穷尽测试，通常不可能也不必要，会造成资源 的浪费和测试效率的低下【1 4 】。因此在实际进行软件测试时，为了兼顾测试的充分性和 有效性，人们根据影响软件系统的因素间的组合设计测试用例集，即进行组合测试。若 要满足对系统中任意t 个因素间组合所产生的交互作用进行测试的需求，称之为t 维组 合测试；若影响系统运行的因素间组合规模不等，则需进行变力度的组合测试。组合测 试的核心问题是在如何以较快的速度生成较小的测试用例集，同时使测试需求中的因素 间组合均出现在用例集中。d k u h n 等通过实验发现，大约2 0 , - 4 0 左右的软件故障 是由单因素引起的，大约7 0 的故障是由一个或两个因素间交互作用引起的，而只有大 约的故障是由三个或三个以上的因素问交互作用引起的，在对大规模分布式系统中进 行组合测试可用性研究时，他们发现最多四到六个因素间交互作用可能引发软件故障， 由多于六个因素间交互作用所引发的软件故障很少见【5 ，6 】。由此可见，进行组合测试不 仅能检测出大部分软件缺陷，还能大大降低测试用例集的规模，具有很高的应用价值。 在组合测试用例集的生成过程中，要使得用例集规模最小，已被证明是一个n p c 问 题 7 - 9 1 ，也正因为如此，在组合测试的研究领域，如何运用各种算法求得近似最优解， 具有重要意义。基于因素顺序渐进扩充策略i p o ( i n p a r a m e t e r - o r d e r ) 是组合测试领域 中的一种具有代表性的通用算法，其优势在于水平扩充算法的可选择性和测试用例集的 可扩展性，该方法严格按照参数出现顺序生成测试用例，对各种不同的待测软件，并不 普遍具有很好的效果。因此作为组合测试用例集生成算法中一个主要分支，总结1 p o 的 算法特点，并通过结合现有算法的优点，将其提升为一个通用框架，并衍生出新的混合 算法，具有重要意义。 东南人学硕 ：学位论文 1 2 研究现状及存在的问题 组合测试的概念由r m a n d l 等人于1 9 8 5 年首次提出，并被用于对a d a 编译器的测 试【i o l ，自此基于组合测试技术得到广泛研究。如何在满足测试需求的前提下，为待测软 件系统生成规模尽可能小的组合测试用例集，是组合测试的研究领域的核心课题之一。 聂长海等人提出将现有的组合测试用例集生成算法分成四判】：代数方法、随机方法、 计算机方法和混合方法，如图1 1 所示。 组合测试用例集生成算法 数学方法lf 随机方法ll 计算机方法lf 混合方法 j 下交表y 递归构造、f 启发式1 f 元启发式 b r o w n l i e ) j ( w i l l i a m s ) ) 【贪心算法儿搜索算法 f 元启发式( 群体) 1f 元启发式( 个体) 1 l 搜索算法 j【 搜索算法 j _ 一j j 1 捌鬣1 7 爬l h 法、禁忌搜索、1 模拟退火、洪水法 叫蕊意，。j r v c e ) 图1 1 组合测试用例集生成算法的分类 由图1 1 可见，组合测试用例集生成算法的研究重点在于计算机方法，即通过编制 计算机程序来实现组合测试用例集的生成算法以获得t 维组合测试用例集，按算法思想 的不同，计算机方法可以分为启发式贪心算法和元启发式搜索算法两大类。在用启发式 贪心算法生成测试用例集时，按照生成策略的不同，又可分为一次生成一条测试用例的 策略( o n e t e s t a t a - t i m e ) 1 2 , 1 3 和基于参数顺序渐进扩充的策略i p o ( i n p a r a m e t e r - o r d e r ) 【7 l4 。，前者是r c b r y c e 在a e t g 、t c g 、d d a 这三种贪心算法的基础上建立的算法框 架。d c o h e n 等提出了一种测试数据生成的启发式贪心算法，开发了相应的测试用例集 生成工具a e t g ”d7 】；t c g 是t w t u n g 等提出的一种先按参数的可选值规模排序再自 动生成组合测试用例集的贪心算法i i m ；d d a 是c j c o l b o u m 等提出的一种在测试用例 的生成过程中参考因素密度进行排序的贪心算法，在大多数情况下可以生成规模更小的 测试用例集 1 9 , 2 0 】。与一次生成一条测试用例的算法思想不同，yl e i 提出了基于参数 顺序渐进扩充的贪心生成方法i p o ，该方法每次生成一个部分覆盖表，然后用先进行水 平扩充再垂直扩充的策略生成组合测试用例集，开发了相应的测试用例集生成工具 p a i r t e s t 7 , 1 4 , 2 1 j ，该方法严格按照参数出现顺序生成测试用例，对各种不同的待测软 件，并不普遍具有很好的效果。 元启发式搜索方法按照目标解的不同可分为元启发式群体搜索算法和元启发式个 体搜索算法，由s a g h a z i 提出的用遗传算法求解符合测试需求的组合测试用例集就是 一种元群体搜索算法【2 2 】；而t s h i b a 等则以单条近似最优测试用例为目标解，用遗传算 法和蚁群算法逐条生成组合测试用例集【2 3 1 ，r c b r y c e 等以单条近似最优测试用例为目 标解，用爬山法、禁忌搜索法、模拟退火法和洪水法等一系列元启发式搜索方法逐条生 成组合测试用例集【2 4 】，m c o h e n 等也将模拟退火算法应用于测试数据的生成【2 5 27 1 。从 2 第一章绪论 生成用例集的思路来看，这些方法属于o n e t e s t a t a - t i m e 的用例生成策略。元启发式搜 索方法在一般情况下可生成近似最优解，但对大规模问题空间求解时，效率较低。 r m a n d l 等使用正交拉丁方生成测试用例集对a d a 系统进行了测试【lo j ；r b r o w n l i e 等使用j 下交表为p m x s t a r m a i l 系统生成了较小规模的测试用例集，并检测出了不少未 曾被发现的错误 2 8 】。这两种方法均通过构造正交表生成测试数据，j 下交表的构造对待测 软件的因素数及因素的取值数都有要求，适应性较差，不宜扩展，使其具体应用受到了 较大的局限。 随机方法思想较为简单，能快速生成相对较好的组合测试用例集，而且针对同样的 问题能产生多种不同的结果，常被用作新算法的实验对比对象；混合算法的思想较为新 颖，通过结合不同类型算法得到一个新算法，期望综合各种算法优点以得到更优的目标 解，m b c o h e n 等就通过结合递归构造方法和元启发式搜索算法得到了多个组合测试 用例集生成的混合算法【2 7 , 2 9 。 1 3 主要研究内容 本文根据国内外对组合测试用例集生成技术的研究现状，主要围绕基于因素顺序渐 进扩充策略i p o 展开工作，研究由yl e i 等人提出的原i p o 策略，分析其优缺点并加以 提炼和改进得到一个可配置的i p o 框架，使其具有更广的适用性，并在研究和分析了遗 传算法的基础上设计新的混合算法i p og a ，并通过实现一系列工具分析可配置i p o 框 架的效果，并将新算法i p og a 与已有算法进行比较。 具体来讲，本文的主要工作可以概括为： 研究和分析基于i p o 策略的思想和特点，说明i p o 策略严格按照参数出现顺序 生成测试用例的弊端，以及其算法参数不可调的缺陷，在此基础上提取i p o 的 算法参数，提出可配置的i p o 框架； 深入研究用遗传算法g a 生成组合测试用例集，在对原g a 有所改进的基础上， 将其结合至可配置的i p o 框架中，提出新的组合测试用例集的混合生成算法 i p o _ g a ； 将可配置i p o 框架的算法思想实现为具有可视化图形用户界面的自动化的组合测试 用例集生成工具i p og e n ，并将对各影响算法效果的参数进行了大量实验和分析；分别 重新实现了基于原i p o 、改进的g a 、混合算法i p og a 的组合测试用例集生成工具， 针对一系列的s u t 进行了实验，并与一些现有算法进行了算法效果的比较。 1 4 本文的组织结构 本文各章的内容安排如下： 第一章：绪论部分。对本文的选题依据进行了详细地阐述，并概括和总结和现有的 相关领域的研究现状和存在的各种问题。本章同时概述了本文的研究内容和文章组织结 构。 第二章：概述了组合测试模型，回顾了组合测试用例集生成算法研究领域中的已有 东南人学硕。 ：学位论文 成果，同时概括了现有算法的效果和特点。 第三章：研究了现有的i p o 策略，对其算法内容和优缺点进行了详尽分析，首先提 出将影响i p o 策略实现效果的算法参数提取出来，并对其影响效果进行了讨论，并在此 基础上提出了可配置的i p o 框架。接着在对用遗传算法g a 生成组合测试用例集进行了 深入研究的基础上，针对影响i p o 策略程度最大的水平扩充算法，提出用g a 替代原有 的启发式贪心算法，从而得到一个新的组合测试用例集的混合生成算法i p og a ，并预 测了算法的效果和适用范围。 第四章：设计并实现了基于可配置i p o 框架和混合算法i p og a 等组合测试用例集 的自动化生成工具，通过大量实验对可配置i p o 框架进行算法参数分析和算法效果评 估，并通过实验将本文实现的算法i p og a 等与一些已有算法进行比较，对i p og a 的 算法效果进行验证，在本章的最后基于实验结果给出关于本文工作的结论和建议。 第五章：总结和展望。对全文的工作做了总结，并结合现有工作指出需要进一步研 究的问题。 4 第一二章组含测试模型及组合测试用例集生成算法概述 第二章组合测试模型及组合测试用例集生成算法概述 组合测试用例集的生成是组合测试研究领域最为重要的课题之一，在该领域已报道 的国内外研究工作中，大部分的研究重点均为如何生成组合测试用例集。因此，本章在 介绍完组合测试模型以后，还将对目前组合测试用例集生成算法的研究现状进行介绍， 从而为后续章节的展开打下基础。 2 1 组合测试模型 为更好的阐述组合测试模型及相关概念，本文将首先给出一个示例，并在下文结合 该示例展开讨论。例如一个基于w e b 应用的待测软件s u t ，影响该s u t 正常工作的主 要因素有浏览器、操作系统、网络连接、打印配置，每个因素均有一个可选值的集合， 如图2 1 所示。 浏览器( f 1 )操作系统( f ：)网络连接( f ：，)打印配置( f 。) i e ( v 1 1 )w i n d o w s ( v 2 1 )l a n ( v 3 1 )l o c a l ( v 4 1 ) b t o z i l l a ( v 1 2 )l i n u x ( v 2 2 )p p p ( v 3 2 )n e t w o r k ( v 4 2 ) i s d n ( v 3 3 )s c r e e n ( v 4 3 ) 图2 1 基于w e b 应用的s u t 的洲素及其可选值集合 设影响软件运行的因素集合f - - f ，, f k ) ，旧= k ，同时假设f 中各因素相互独立， 即互不影响其他因素的取值。每个因素e ( 1 f k ) 都有其对应的可选值集合 降 魄，v i x i ，可选值集合的规模为i z i l = x i 。例如图2 1 中s u t 的影响因素集合为 f = f ，, f 2 , f 3 , f 4 ) ，乃对应的可选值集合为v i - - - - v i i ，v j 2 。在实际中对组合测试进行应用 时，影响s u t 的因素及其可选值集合主要可以从该软件的需求说明书、开发文档等技 术资料中获得。 定义2 1 称七元组 v l ，蚴，v 七) 为一条测试用例，其中v i e 巧，吻圪，v k e 圪。 称一个多条这样的测试用例构成的集合为测试用例集。 定义2 2 若因素集合中的某几个因素r ，以的交互作用会影响s u t 的输出，则称 这几个因素的集合为一个交互关系胪 r ， ) ，将s u t 中所有交互关系的集合记为 胆但，凡) ，僻l - - - y 。 定义2 3 对于一个交互关系r ： f m ，可得到其对应的因素可选值组合 c o m b ：= 圪( 即对交互关系中各因素的可选值集合求笛卡尔积) ，若该组合完整 得出现在所生成的测试用例集中，则称该用例集满足了对尺，的组合覆盖需求。将s u t 中所有因素可选值组合的集合记为c o m b = c o m b t ，c d ，l b ，l c o m b l = 限l 可。 定义2 4 若s u t 的交互关系集合的规模限i 妒c ：，且其中任一交互关系的规模i 母障 ( 1 勺勺) ，即对s u t 中任意t 个因素问的交互进行测试，称这样的测试为t 维组合测 5 东南人学硕l ：学位论文 试，且可选值组合集合c o m b 中所有的可选值组合均出现在所生成的测试用例集中，则 称该测试用例集满足了针对该s u t 的组合覆盖需求，所得用例集为t 维组合测试用例集， 或t 维组合覆盖表。 定义2 5 若交互关系集合中各交互关系的规模不等，若要求对这样的交互关系进行 组合测试，则称这样的测试为可变力度的组合测试( 交互关系的规模也可称为力度) 。 若图2 1中的s u t 的交互关系集合尺= 俾，角角皿彳皿，皿6 ) = 一凡) ， f i , f 3 ， f w 4 ， 局 ) ， f 2 , f 4 ， b ) ，规模为c 4 = 6 。不难看出，针对该s u t 进行的 是2 维组合测试。对于交互关系尺严 局 ) ，由f 2 对应的可选值集合v z = v 2 ，屹2 ) 和乃 对应的可选值集合v 3 = v 3 ，功2 ，坳3 ) ，可得到r 4 对应的因素可选值组合c o m b , r ：v 2 r 3 - - v 2 ，均，) ， 吻， ? ) ， 垤，v 3 j ) ， v z 2 ，的，) ， 睨2 ，”，2 ) ， v 2 2 ，功3 ) ) ，如图2 2 加深部分所示。 图2 - 2 即为例s u t 的2 维组合测试用例集。 t e s t l v 1 1r 铲 嚣日镕# 搿 l ， v 4 1 t e s t 2 v i i v 。， 。j v k 2v 4 2 t e s t 3 v i 1 睨t ， v 3 3 v 4 2 t e s t 4 v 1 2 荔 v 复麓， 一， 1 v 4 3 t e s t 5 v i 2lv 2 2 v 麓善 v 4 1 争 t e s t 6 v i 2 。瓿，。渤! 搬m ：黝 v 4 1 t e s t 7 v 1 1v 2 1v 3 2v 4 3 t e s t 8 v 1 1 v 2 1 v 3 i v 4 2 t e s t 9 v i iv 2 2v 3 3v 4 3 图2 2 例s u t 的2 维组合测试用例集 定义2 6 若能找到一个组合测试用例集使其规模最小，则称之为最小组合测试用例 集。但要找到规模最小的组合测试用例集已被证明是n p c 问题盯剖。 若对s u t 进行穷尽测试，将耗费大量资源，而且事实上并非所有因素在各种程度上 都会发生交互作用，从而影响软件的运行结果。有研究表明，通常2 维组合测试便能检 测出绝大多数的软件缺陷，且能大大的减小测试用例集的规模啪川。例如对图2 1 中的 s u t 进行穷尽测试，所需测试用例集规模为2 2 3 3 - 3 6 ，但若对该s u t 进行任意 2 个因素间交互作用的测试，即进行2 维组合测试，则只需9 条测试用例即可满足测试 需求，如图2 2 给出的2 维组合用例集便覆盖了该s u t 中任意两因素间的可选值组合。 2 2 组合测试用例集的生成 组合测试研究工作的重点之一就是组合测试用例集的生成，即如何在满足组合覆盖 标准的前提下，以较短的时间为待测软件s u t 生成规模较小的组合测试用例集。由于 组合测试用例集的生成问题具有n p c 性质，即难以在多项式时间内为待测软件生成一 个规模最小的组合测试用例集，该问题已被多次证明：qs e r o u s s i 和n b s h o u t i 通过四 色问题证明了二水平组合测试用例集生成问题的n p c 性质【9 l ：yl e i 等人通过 v e r t e x c o v e r 问题证明了二维组合测试用例集生成问题的n p c 性质【7 1 ，由此可推论一 6 第二苹组合测试模型及纰合测试用例集生成算法慨述 般的固定力度组合测试用例集生成问题也具备n p c 性质；a w w i l l i a m s 等人通过0 1 整数规划问题也证明了这一结论1 8 j 。因此，在组合测试用例集生成算法的研究领域，研 究者通过尝试用各种各样的近似算法求解。 在绪论中提到，聂长海等人到对组合测试用例集生成算法研究领域的已有相关工作 进行了深入、细致的研究的基础上，提出按算法思路的不同，将现有的相关算法分为四 大类，代数方法、随机方法、计算机方法和混合方法【i ，如图1 1 所示。在这四类方法 中，代数方法具有较差的通用性，不宜推广；随机方法由于实现简单，结果多样，常被 用做各种算法效果的比较标准之一；计算机方法通过应用算法思想编制计算机程序来求 解，主要包括启发式贪心算法和元启发式搜索方法两类，具有较强的通用性，应用得较 多；混合方法则属于新兴的算法思想，可组合各种算法的优点生成各种新的混合方法， 以期获得更好的算法效果，具有较大的研究空间。本节将就这四种不同的组合测试用例 集生成算法进行介绍和讨论。 2 2 1 代数方法 在生成t 维组合测试用例集时，如果因素集合f 满足某些特定的条件，则可直接或 递归地使用某些代数结构，来构造规模较小甚至是最小的测试用例集。一般情况下，这 类方法均要求f 中所有k 个因素具有相同规模的可选值集合，因此其通用性受到一定的 影响。本小节将对代数方法中具有代表性的思想和方法进行介绍。 ( 1 ) j 下交实验设计 正交实验设计是指使用j 下交表( o r t h o g o n a la r r a y ) 设计实验方案的方法，对于一个 包含a 个不同元素( 口为自然数) 的二维矩阵彳= ( 口，) m 蝴，若在该矩阵的任意列中，a 个元素的所有个元组合均等频率地出现a ( 1 ) 次，则称该二维矩阵为j 下交表。 该方法同样可以应用于软件测试的方案设计中。r m a n d l 和r b r o w n l i e 等人在早期 使用组合测试方法时，就主要使用正交表来构造固定力度组合测试用例集【! o , 2 8 】。 由组合测试的相关概念可知，在组合测试中只需要考虑a = l 的正交表，即保证每个 n 元组合均至少出现一次即可。由于a = 1 的正交表对于所有n 元组合均只覆盖一次， 其所对应的t 维组合测试用例集中不存在冗余的组合，因此也是规模最小的组合测试用 例集。 尽管正交试验设计是一种比较有效的测试用例选择方法，但由于该方法依赖于正交 表的构造，而正交表的构造还存在很多未解决的难题，特别是对于混合型的正交表，目 前还没有比较好的构造方法，这给正交试验设计在组合测试用例集生成中的应用带来较 大的局限 3 2 - 3 5 j 。 ( 2 ) a w w i l l i a m s 的递归构造方法 加拿大渥太华大学的a w w i l l i a m s 于2 0 0 2 年在他的博士论文中提出一种新的代数 方法【8 。】，以 = l 的二维正交表为基础，通过递归构造方式生成二维组合测试用例集。 在这个方法中他首先定义了构造二维组合覆盖表的五个基本结构：o ( n 2 , n + l ，1 ) 表示一个 正交表，b ( n 2 1 , n + l ，吃力表示将正交表o ( n 2 , n + l ，刀) 截去第一行以后，每列连续重复d 次 而得到的表，该表有n 2 - - 1 行，伽+ 1 ) d 列；g ( n 2 - - n ，n + l ，l , 力表示将o ( n 2 , n + l ，疗) 的截取 前n 行后，每列重复d 次所形成的表，该表有1 l 行，n xd 列；足c ，刃表示全由1 组 7 东南人学顾l ：学位论文 成的c 行d 列矩阵；( 1 ，n ，力表示将j 下交表的首列重复d 次以后，删除全l 行所得到 的矩阵。图2 3 给出了一个具体示例。 图2 3 在止交表基础上得剑的基本结构 这几个基本结构通过递归组合，可以得到规模更大的二维组合覆盖表，该递归构造 方法要求所有因素的可选值规模相同，且为素数或素数幂。不过在实际应用中，当因素 可选值规模均相同时，但该数不满足是素数或素数幂的情况时，可以取一个近似的素数 或素数幂来代替。根据该方法，a w w i l l i a m 等人开发了一个二维组合测试用例集的生 成工具t c o n f i g 。 ( 3 ) n k o b a y a s h