（计算机软件与理论专业论文）测试用例集约简技术研究.pdf

摘要 测试用例集约简技术是生成最小测试用例集，最大限度地对软件进行科学有效的测试，从而降低软 件测试的成本、提高测试效率的关键技术之一，多年来，受到人们的普遍重视和深入研究。本文从组合 测试的最小测试用例集生成和基于测试需求集的测试用例集约简方法两个方面入手，进行了系统深入的 研究，主要包括以下内容： ( 1 ) 系统地研究了美国贝尔实验室d m c o h e n 等和美国北卡罗菜纳州大学vl e i 等分别提出的两两 组合测试用例集的启发式生成方法，提出了基于网络图模型和基于解空间树模型的两种新的测试用例集 生成算法，是对已有方法的有效改善和补充。同时系统地研究了日本大阪大学n k o b a y a s h i 等和加拿大 渥太华大学aw w i l l i a m s 分别提出的两两组合测试用例集生成的代数方法，分析了存在的问题，并在这 个基础上给出了一种改进的代数方法，该方法集中了启发式方法的灵活性和代数方法的简洁性特点，可 以有效地提高生成的测试数据集的质量。 ( 2 ) 在系统研究多次单因素试验方法、均匀设计方法、正交试验设计方法等试验设计方法的理论和 应用的基础上，针对有些软件系统涉及的因素多，以及每个因素取值也很多的情况，提出一种适合软件 测试的单因素覆盖方法的概念和相应测试用例生成方法，该方法生成的测试用例集具有数量最少、覆盖 所有因素以及最大限度地覆盖因素间各种组合的特点。 ( 3 ) 针对在一些重要的软件测试中，为了减少不完全测试带来的风险，需要对系统参数进行高维覆 盖的需求，给出了种多因素组合覆盖测试用例生成方法：针对二水平多因素系统这一类特殊的系统， 给出了一种效果明显的两两组合覆盖测试用例生成算法：提出了一种用于检测相邻因素间相互作用的测 试数据生成算法。这些方法可以有效地生成最小测试用例集，满足相应测试要求。 ( 4 ) 研究了将组合测试方法应用于基于接口参数的黑箱测试、w e b 测试以及软件配置测试的测试方 案设计。并研究了基于组合测试结果的软件故障分析和调试技术，给出了一个有效的软件故障分析定位 算法，可以为软件调试提供有益的线索和参考，从而有效地提高软件调试的效率。 ( 5 ) 分析了已有的基于测试需求集的测试用例集约简方法的缺点和不足，提出了一种新的测试用例 集约简方法，可以生成由测试需求集自身固有的晟小测试用例集。 ( 6 ) 分析了已有的利用输入输出关系，约简组合测试用例集方法的不足，提出了一种简单有效的根 据输入输出关系生成组合测试最小测试用例集的方法，可以实现在不降低测试数据集检测能力的基础 上，大大约简测试数据集，从而有效地提高测试效率、降低成本。 ( 7 ) 给出了对软件系统进行全面测试的最小测试用例集生成框架，提出首先建立一个可以扩展和细 化的测试需求目录，然后针对具体的待测软件，建立测试需求之间的相互关系，最后根据这些关系对测 试用例集进行优化和约简。该框架可以有效地生成、管理、约简、分析和评估对软件系统进行全面测试 的最小测试用例集。 关键词软件测试，测试用例集约简，组合测试，测试用例生成，两两组合测试 a b s t r a c t t e s ts u i t er e d u c t i o ni so n eo ft h ek e yt e c h n i q u e sf o rt e s t i n gs o f t w a r ee f f i c i e n t l ya n dr e a s o n a b l yw i t ht h e m i n i m u mt e s ts e tt ot h eg r e a t e s td e g r e e ，a n dt h e nd e c r e a s i n gt h ec o s ta n di m p r o v i n gt h ee f f i c i e n c y i nt h el a s t y e a r s ，t h et e c h n i q u ef o rt e s ts u i t er e d u c t i o nh a sb e e np a i dg r e a ta t t e n t i o n ，w i d e l ys t u d i e da n da p p l i e d i nt h i s p a p e rw e m a d ea s y s t e m i c a n dd e e ps t u d yf r o mt w oa s p e c t s ：t h em i n i m u mt e s t s u i t e g e n e r a t i o n f o r c o m b i n a t o r i a lt e s t i n ga n dt e s ts u i t er e d u c t i o nb a s e do nt e s tr e q u i r e m e n t s ，c o n c r e t e l yi ti n c l u d e s ： ( 1 ) m a k eas y s t e m i cs t u d ya b o u tt h eh e u r i s t i cm e t h o d so ft e s ts u i t eg e n e r a t i o nf o rp a i r w i s et e s t i n gt h a t p r e s e n t e dr e s p e c t i v e l yb yd mc o h e n i nt & a ta n d b yy l e ia n dk c t a ii nt h et m i v e r s i t yo f n o r t hc a r o l i n a p r e s e n tt w ot e s ts u i t eg e n e r a t i o na l g o r i t h m sr e s p e c t i v e l yb a s e do nt h em o d e lo f n e t w o r kg r a p ha n db a s e do nt h e m o d e lo f s o l u t i o n s p a c et r e e ，t h e s et w oa l g o r i t h m sa r ea l lb e t t e r t h a nt h ee x i s t e d m e t h o d si ns o m es e n s em a k ea s y s t e m i cs t u d ya b o u t t h ea l g e b r am e t h o d sp r e s e n t e dr e s p e c t i v e l yb y n k o b a y a s h ii no s a k au n i v e r s i t y , a n db y a ww i l l i a m si nu n i v e r s i t yo fo t t a w a a n a l y z et h ee x i s t e dp r o b l e m sa n dg i v ea ni m p r o v e da l g e b r am e t h o d w h i c hh a st h ea g i l i t yo f t h eh e u r i s t i cm e t h o d sa n dt h es i m p l i c i t yo f t h ea l g e b r am e t h o da n dc a ni m p r o v eq u a l i t y o f t h e g e n e r a t e dt e s ts u i t ee f f i c i e n t l y ( 2 ) g i v eac o n c e p to fs i n g l ef a c t o rc o v e ra n dat e s ts u i t eg e n e r a t i o na l g o r i t h mf o rt h es o f t w a r ew i t hm a n y f a c t o r sw h e r ee a c hf a c t o rh a sm a n yv a l u e s ，b a s e do nt h es t u d yo f m u l t i p l es i n g l ef a c t o re x p e r i m e n t ，u n i f o r m d e s i g nm e t h o d ，o r t h o g o n a le x p e r i m e n td e s i g nm e t h o d a n ds oo i l t h em e t h o dc a ng e n e r a t eam i n i m a lt e s ts u i t e t oc o v e ra l lt h ef a c t o r sa n dc o v e ra l lt h ef a c t o rc o m b i n a t i o n st ot h e g r e a t e s td e g r e e ( 3 ) p r e s e n tat e s ts u i t eg e n e r a t i o na l g o r i t h mf o rm u l t i p l ef a c t o rc o m b i n a t i o nc o v e rm e t h o dt od e c r e a s et h e r i s kb r o u g h tb y i n c o m p l e t et e s t i n gf o rs o m ei m p o r t a n ts o f t w a r et e s t i n g p r e s e n tat e s ts u i t eg e n e r a t i o na l g o r i t h m f o rp a i r w i s et e s t i n gw i t hp r o m i n e n te f f e c t i v e n e s sf o rt h es o f t w a r es y s t e mt h a th a sm a n yf a c t o r sw i t ht w ol e v e l s p r e n s e n ta na l g o r i t h mf o rt e s td a t ag e n e r a t i o nt od e t e c tt h ei n t e r a c t i v eb e t w e e na n yt w of a c t o r st h a tt h e ya r e n e i g h b o r i n g a l lt h e s em e t h o d sc a ng e n e r a t et h em i n i m a lt e s ts u i t et h a tc a ns a r i s f yt h et e s tr e q u i r e m e n t s ( 4 ) m a k es o m er e s e a r c ha b o u tt h ea p p l i c a t i o ni nt h et e s t g e n e r a t i o nf o rb l a c k - b o xt e s t i n gb a s e do n i n t e r f a c ep a r a m e t e r s ，f o rw e b t e s t i n ga n df o rt h et e s tp l a no fc o n f i g u r a t i o nt e s t i n g m a k es o m es t u d ya b o u tt h e t e c h n i q u eo f f a u l ta n a l y s i sa n d d e b u g g i n g ；g i v ea l la l g o r i t h mf o rt h es o f t w a r ed e f e c tl o c a t i n gt h a tc a np r o v i d e g o o dg u i d ea n dr e f e r e n c ef o rs o f t w a r ed e b u g g i n g ( 5 ) a n a l y z et h es h o r t a g ea b o u tt h ee x i s t e dm e t h o df o rt e s ts u i t er e d u c t i o nb a s e do nt h et e s tr e q u i r e m e n t s a n dt h e ng i v ean e wm e t h o dt h a tc a n p r o d u c e t h ei n h e r el n l n i m u mt e s ts e to f t h et e s tr e q u i r e m e n t s ( 6 ) a n a l y z e 也ee x i s t e dp r o b l e m sa b o u tt h em e t h o d so ft e s ts u i t er e d u c t i o nb a s e do nt h ei oa n a l y s i s p r e s e n tas i m p l ea n de f f e c t i v ew a yf o rt h et e s ts u i t eg e n e r a t i o no fe o m b i n a t o r a lt e s t i n gb a s e do ni or e l a t i o n s t h em e t h o dc a nr e d u c et h et e s ts u i t ef o re o m b i n a t o r a lt e s t i n gg r e a t l yw i t h o u ta n yl o s so ft h ee x a m i n a t i o n a b i l i t y ( 7 ) g i v eaf r a m ef o rt h em i n i m u mt e s ts u i t eg e n e r a t i o nt ot e s tt h es o f t w a r ec o m p l e t e l y , w h i c hf i r s tc r e a t ea t e s t i n gc a t e g o r yt h a tc a nb ee x t e n d e da n dp a r t i c u l a r i z e d ，a n dt h e nc a nm a k es o m eo p t i m i z a t i o na n dr e d u c t i o n b a s e do nt h ec o r r e l a t i o n so f t h et e s tr e q u i r e m e n t s i tc a ng e n e r a t e ，m a n a g e m e n t ，a n a l y s i s ，r e d u c ea n dr e v i e wt h e m i n i m a jt e s ts u i t et ot e s tt h es o f t w a r ec o m p l e t e l ya n d s y s t e m a t i c a l l y k e y w o r d ss o f t w a r et e s t i n g ，t e s ts u i t er e d u c t i o n ，c o m b i n a t o r i a lt e s t i n g ，t e s tc a s eg e n e r a t i o n ，p a i r w i s et e s t i n g 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：蠹矗瞌日期： 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 凇机包篡爹裟黧羧眺一竽 研究生签名：缸导师签名：磁日期：巡! ：挈 东南大学博士学位论文 1 1 选题依据 第1 章引言 随着计算机技术的飞速发展，以计算机硬件为载体、软件为灵魂的计算机应用已经渗透到各行各业， 在为人们提高工作效率、工作质量和改造传统产业中起着越来越重要的作用。随之而来的软件质量问题 和软件产品生产率低下等问题越来越受到人们高度重视，并已经成为制约计算机应用产业发展的瓶颈。 当前，软件质量已经严重影响着人们的生活、学习和工作，并日益成为影响社会生产力发展的重要因素， 对信息产业和国民经济发展有着极为明显的推动作用；软件已不仅仅是技术与工具，同时也是一种文化， 发展民族软件已经成为发展信息化社会、发展民族文化的重要组成部分，是保证国家政治独立、安全、 文化不受侵害的重要因素。如何迅速地开发高质量的软件系统来满足各行各业日益增长的迫切需求，一 直是人们研究和关注的重要课题。人们提出的系统全面的软件工程化方法，对软件的生产起到了重要的 推动与保证作用，同时，i s 0 9 0 0 0 、c m m 也在很多国家得到成功的推广和应用 7 4 7 7 。 软件测试是软件工程化方法中的重要环节，也是i s 0 9 0 0 0 和c m m 中的重要内容，在整个软件的生 命周期中占有非常重要的地位，它对于保证软件产品的质量和提高软件产品的生产率起着重要作用。软 件测试的费用和时间往往随着对软件产品质量要求的提高而迅速增长，根据各方面估计，一般约占整个 软件开发项目的4 0 以上。软件测试活动中软件测试计划的设汁和相应测试数据的生成是至关重要的， 即，制定和生成科学、系统、有效的测试计划及相应测试数据是取得测试成功的关键。这些工作本身需 要投入大量的时间和人力，用于研究如何制定测试计划，并生成相应的测试数据，其结果将直接决定整 个软件测试的费用、效率和质量 7 8 8 6 。 软件测试从普通意义上讲是为了发现错误而执行程序的过程，它根据软件开发各个阶段的规格说明 和程序的内部结构而精心设计的一些测试用例，并利用这些测试用例去运行程序，发现错误。广义上讲 软件测试是对软件需求分析、设计说明和编码进行复审等软件质量保证工作。所以，严格地说，软件测 试活动并不只在程序编码结束之后才开始，而应该是贯穿整个软件的生命周期。因此，应当尽旱地和不 断地进行软件测试，发现问题越早，错误纠正得越及时，所造成的损失就越小。在软件开发的各个阶段 要科学系统地制定和细化测试计划，同时严格执行测试计划，排除测试的随意性。 在软件测试过程中，穷尽测试既不可能，也没必要。在实际测试过程中如何精选少量的测试用例， 对系统进行有效的测试，是软件测试研究中的关键课题。选择好的测试用例组不仅能减少软件测试的工 作量，降低软件测试的成本，而且在不降低软件测试的质量的前提下，提高软件开发的速度，从而使系 统能及早投入使用，参与市场竞争。这在当前计算机软硬件技术迅速发展的形势下，显得尤为重要。 软件测试计划设计制定及其相应测试数据的生成一直是人们研究的一个重要领域。i s 0 9 0 0 0 标准以 及c m m 中给出了一些软件测试要求，强调需求文档中的每一个需求必须要进行测试。在进行软件测试 时，必须根据软件需求分析、设计文档和编码等确定测试目标。即测试需求的集合，根据这些测试需求 可以精心构造出组测试用例，这组测试用例的数量和质量将决定软件测试的成本和有效性。 如果对于每个测试需求一般都产生相应的测试用例以实现对这个测试需求的充分测试。这样产生 的测试用例集一般比较大，而且可能有比较大的冗余，即这组测试用例的某些子集也能满足所有的测试 需求。由于运行、管理和维护这些测试用例以及回归测试将耗费大量的时间、人力和物力，软件测试的 成本太大，因此人们一直在研究如何基于测试需求集设计出组有效、数量少又能充分满足所有测试需 求的测试用例集，从而在保证和提高软件测试的质量的同时，降低软件测试的成本。 基于测试需求集的测试只是针对单个需求的测试，不能保证整个系统在这些功能需求结合在一起时 能否可以像预期的那样正常工作故有必要综合考虑影响整个系统的各种因素以及这些因素之间的相互 作用。这些因素包括待测系统的配置参数、内部事件、用户输入或者其他外部事件等，决定着待凋系统 的各种可能的测试场景。 组合测试是一种利用组合设计方法产生测试用例的重要的软件测试方法，这种方法可以充分考虑系 】 第1 章引言 统中各种因素以及各种因素之间的相互作用可能对系统产生的影响，在很多领域有着广泛的应用。在软 件测试领域应用最为广泛的有正交试验设计方法和两两组合覆盖测试方法。组合测试方法具有以下一些 优点：其一，可以根据实际需要用尽可能少的试验次数尽可能多地考察一些影响系统的因素；其二，少 数次测试的结果能够反映全面测试的内在规律，具有代表性；其三，能够通过少数次测试结果的分析和 处理探求可能更优的测试方案。因而它是一种基于数理统计基础上的科学的方法，近年来在软件测试领 域受到了非常广泛的重视、研究和应用。 为此，我们的研究主要围绕以下几个方面进行：( 1 ) 基于测试需求集的测试用例集约简技术研究； ( 2 ) 组合测试的测试用例集约简和生成技术研究；( 3 ) 同时考虑测试需求集和组合测试的测试用例集 约简技术研究；( 4 ) 基于组合测试的软件调试技术研究；( 5 ) 最小测试用例集生成技术在配置测试、w e b 测试、组件测试等方面的应用研究。 1 2 国内外研究现状 目前，对于测试用例集约简技术的研究主要集中在两个方面：一是基于组合覆盖的测试用例集生成 和约简技术研究；另一是基于测试需求的测试用例集约简技术的研究。 基于组合覆盖的测试用例集生成技术研究，主要研究应用组合设计方法对软件进行组合测试。开 始主要是将正交试验设计方法应用于软件测试，取得了比较好的效果 3 9 ，4 4 4 7 。正交试验设计方法是 一辛中比较成熟、有效的测试用例选择方法，它可以实现对各个参数的两两组合的等概率覆盖，而且提供 了一整套试验结果分析方法 5 7 6 0 。am s a l e m 在博士论文中较系统地研究了将试验设计方法应用于 软件测试 5 0 。 后来，人们关于组合测试的研究主要集中在两两组合覆盖测试用例的生成方面，主要有以下三个方 面原因：第一，在软件测试中，对各个参数及其相互间组合，只要求覆盖，并不需要等概率覆盖：第二， 正交试验设计依赖于正交表，但正交表构造还存在很多未解决的问题，这给该方法的使用带来一定的限 制；第三，使用正交试验设计所需要的测试用例数量在多数情况下要远远多于实现两两组台覆盖所需要 的测试用例的数量，这无疑将增加软件测试的成本。 对于两两组台覆盖测试数据生成的研究主要有启发式方法和代数方法两个研究领域，美国贝尔 实验室的d m c o h e n 与s r d a l a i 等 1 4 和北卡罗莱纳州大学的yl e i 与k c t a i 等f 5 ，6 】分别提出了 一种两两组合覆盖测试数据生成的启发式方法，启发式方法的特点是非常灵活、有效。作为启发式方法 的一种重要补充，日本大阪大学的n k o b a y a s h i 和 1 2 t s u c h i y a 等提出了一种代数方法7 ，同时加拿大渥 太华大学的a ww i l l i a m s 也提出了一套代数方法，并给出了相应的算法实现，可以有效地生成满足要 求的测试数据f 8 i 5 ，代数方法的特点是非常简洁。人们也开始研究对于组合覆盖测试数据的约简。p j s c h r o e d e r 在他的博士论文中提出了一种利用系统输入输出关系等附加信息对组合覆盖测试数据进行约 简的方法 5 3 ，5 4 ，这种方法试图在保证不降低测试数据集的检测能力的基础上，对它进行约简，从而提 高软件测试的效率。 在基于测试需求的软件测试中，人们一般都是根据各个测试需求，产生相应的测试用例，然后在这 些测试用例形成的测试用例集r 的基础上运用各种约简方法，得到简化的测试用例集。目前，对于测试 用例集r 的约简方法主要有贪心算法、启发式算法和整数规划方法等。 贪心算法为了把测试需求集尺对应的测试用例集，进行精简，每次从r 中挑选一个测试用例，使之 能昂多地满足所有未被满足的测试需求。m j h a r r o l d 2 6 ，2 7 等提出一种根据测试用例的重要性来选择测 试用例的启发式方法；在贪心算法和mj h a r r o l d 等提出的启发式算法的基础上，人们又提出一种将这 两种方法进行有机结合的新方法。这种方法首先选出必不可少的重要测试用例，然后利用贪心算法选出 能最多地满足未被满足的测试需求的测试用例。ty c h e n 和mel a u 在这些算法的基础上提出一个新 的测试用例集简化的启发式算法，在这个算法中不仅结合了贪心算法、m j h a r r o l d 等提出的启发式算 法的优点，而且充分考虑了剔除卜1 冗余策略 1 6 】，并用仿真方法研究这几种算法的性能f 1 7 ，给实际使 用这几个算法提供了一些参考和指导，不过这些方法不能保证产生的结果是最优的。j gl e e 和cg 东南大学博士学位论文 c h u n g 提出了一种将原问题转化为整数规划问题，利用整数规划方法求最优解的方法，可以保证选出的 测试用例集是原测试用例集最优的约简 3 5 ，8 7 - s 8 。 那么，测试用例集的简化是否会降低它的错误检测能力呢? 对于这个问题，一些研究者的研究表明测 试用例集的简化不会别它的错误检测能力产生影响 3 7 】，而另外有些研究者却发现冗余的测试用例可以用 来帮助提高测试用例集的错误检测能力 3 8 。总之，测试用例的简化并不一定是以牺牲其错误检测能力为 代价的。所以，在这里我们只关心如何生成数量最少的、能满足测试目标中的所有测试需求的测试用例集。 1 3 存在问题分析 尽管人们在利用组台设计方法产生测试用例集方面，做了很多研究，取得很多成果，但还存在着很 多尚待解决的问题，主要表现在有些测试用例集还没有很好的生成方法，例如，利用正交试验设计方法 进行软件测试时，测试用例集依赖于正交表，而正交表的构造还存在很多未解决的难题，特别是对于混 合型的正交表，目前还没有比较好的构造方法，这严重制约了正交试验设计方法在软件测试中的应用。 即使用两两组台覆盖方法来替代正交试验设计方法，但由于两两组合覆盖测试用例生成问题是一个n p 问题。各种用于生成两两组合覆盖测试用例的方法只能提供该问题的一种近似解，这些方法无法保证所 产生的测试用例集最优。 p j s c h r o e d e r 提出通过需求文档和设计文档以砹切片技术等来分析输入输出关系，从而获得一些附 加信息，在此基础上进行测试用例的约简，但由于这种约简问题本身也是一个n p 问题，而且获取附加 信息也需要一定的成本和开销，所以这种方法并不是普遍有效，有时还不如直接使用组合覆盖测试方法 简单有效，所以，这种方法还需要作进一步研究和完善。 对于有些比较重要的软件测试，如果做完全测试，工作量太大。但如果只按一般的组合设计方法来 进行测试，尽管这些方法都有科学的依据，具有很好的优点，但毕竟测试的次数比较少，没有进行完全 测试，势必存在很大的风险。为了把这些风险降低到最低限度，还需要研究如三三组合覆盖、四四组合 覆盖等基于多因素组合覆盖方法的测试用例生成。 在应用组合设计产生的测试用侧集对软件系统进行测试之后，如果发现故障，那么一方面说明测试 工作是成功的，另一方面还需要通过对试验结果的分析和处理，初步确定故障原因，并探求可能更优的 试验方案，来对故障原因进行进一步的分析、处理和验证。目前人们关于这方面的研究还不多见，虽然 在正交试验设计方法中有关于试验结果分析的方法，如直观分析方法、方差分析方法等，但是这些方法 并不适合于对软件测试结果的分析。软件调试是在测试之后不可缺少的关键性工作，方便、可靠、有效 的调试方法能帮助软件测试和调试人员迅速找出故障的原因并消除故障，从而提高软件测试的效率，降 低成本。所以，对于组台测试中调试方法的研究具有相当重要的现实意义。 目前，人们解决基于测试需求的最小测试用例集的生成问题的一般方法是：首先根据测试目标中的 每个测试需求确定出相应的测试用例，所有这些测试用例组成初步的满足测试目标的测试用例集：然后 针对这个测试用例集采用贪心算法、启发式算法或整数规划等方法来进行精简，去掉一些冗余的测试用 例 1 6 ，2 6 。这种方法的缺点在于它的效果取决于最初产生的测试用例集，因最初选定的测试用例集的 不同而不同，不能从根本e 实现根据测试目标对测试用例集的整体优化。 对于既考虑软件系统中各个因素的影响，又要对每个测试需求进行充分测试的最小测试用例集的生 成技术研究尚未见到。 1 4 主要研究内容 根据以上讨论以及目前国内外关于测试用例集约简技术的研究现状，本文主要在以下几个方面进行 了深入研究： ( 1 ) 基于组合设计方法的测试用例集约简技术研究 根据软件系统的复杂程度、软件质量的规格，在充分考虑备因素及其相互作用对系统影响的基础上， 3 第1 章引言 研究了六种具有不同特点和覆盖程度的最小测试用例集的生成方法( 以下将这六种方法统称组合设计方 法，利用组合设计方法生成测试用例集进行软件测试的方法称为组合测试) 。其中多次单因素试验方法、 均匀设计方法和正交试验设计方法为人们常用的组合设计方法，在此基础上我们研究了； 单因素覆盖方法。结合多次单因素试验方法，均匀设计方法的优缺点，提出了单因素覆盖方法。 这种方法生成的测试数据少，但能实现各个因素的覆盖和最大限度的两两组合覆盖。 两两组合覆盖方法。在深入研究已有的两两组合覆盖测试用例集的启发式生成方法和代数方法的 基础上，研究了一些基于新的模型上的两两组合覆盖测试用例集的启发式生成方法，同时研究探索新的 代数方法，研究开发一个用于自动生成两两组合覆盖测试用例的辅助工具，从而提高生成的两两组合覆 盖测试用例集的质量。 多因素组台覆盖方法。研究三三组合覆盖、四四组合覆盖等多因素组合覆盖方法的测试用例生成 方法及其应用，开发一个用于自动生成多因素组合覆盖测试用例的辅助工具。 ( 2 ) 基于组合设计方法的最小涌试用例生成技术的应用 我们在这个方面的研究主要集中在如下两个方面： 基于组合测试的浏览器兼容性测试方法。浏览器兼容性测试涉及到种类繁多的软硬件设备、数 目庞大的设备品牌和型号以及各种情况的组合，如何有效而又快速地对尽可能多的情况组合进行测试是 项很重要的工作。为此，本文结合w e b 应用程序的特点建立了浏监器兼容性测试的简单模型，并研究 使用组合测试方法来进行测试的技术。 配置测试的测试方案设计方法研究。配置测试是软件测试过程中一个必不可少的重要环节，指 使用各种硬件来测试软件操作，以保证该软件能够适用于尽量多样化的硬件组合。我们在一般的配置测 试方法的基础上提出将组合设计方法用于配置测试的测试方案的设计，并分析了这些方法的优点和局限 性。 ( 3 ) 基于组合测试的软件调试方法 组合测试主要用于检测由于系统参数及其相互作用( 取值模式) 而引起的软件系统故障，采用一种 根据组合测试结果进行故障原因定位的模型，从而在一定程度上解决故障原因的诊断问题。由于在实际 系统中的情况是非常复杂的，完全有可能出现与本模型假设相反的情况，作为组合测试方法的一种辅助 调试方法，这种方法具有一定的适用范围，提供的分析结果可以作为一个有益的参考，从而更有效地提 高软件测试的效率、降低软件测试的成本。 “) 基于测试需求集的测试用例集约简技术研究 由于目前基于测试需求集的最小测试用例集生成技术研究的几种算法都是对测试用例集的简化策 略，而测试用例集是根据测试目标中的测试需求来确定的，所以决定算法实际效果的除了算法本身外就 是它们所处理的最初生成的测试用例集。为此，我们提出了一种新的最简测试用例集生成方法，该方法 充分考虑了最初的测试用例集的作用，研究了如何根据测试目标中的测试需求来产生相应的最初测试用 例集，证明了在此测试用例集基础上利用上述算法进行精简，可以产生最好的测试用例集。特别是在此 基础上应用j gl e e 和c g c h u n g 提出的简化方法可以产生针对测试目标的最优的测试用例集。 ( 5 ) 基于测试需求集和组合设计方法的最小测试用例集生成技术研究 利用切片技术 9 2 - 1 0 0 ，蛆及通过对需求文档、设计文档等分析出各个测试需求与输入输出之间的 关系，在基于测试需求集和考虑各种因素对系统影响的基础上，我们研究了最小测试用例集的生成方法， 并实现了相应的生成工具。 1 5 主要创新点 论文主要的研究成果和创新点有以下几个方面： ( 1 ) 基于测试需求集的最小测试用例集生成技术研究，提出了一种科学实用的测试用例集生成和约 简方法，并开发实现了辅助软件工具，与已有方法相比，可以生成测试需求集所确定的最小测试用例集。 4 东南大学博士学位论文 ( 2 ) 基于组合设计的晟小测试用例集生成技术研究，从两种不同的模型出发提出两种各具特色的启 发式方法，同时提出一种代数方法，是对已有方法很好的发展和补充。 ( 3 ) 基于测试需求集和组合设计的最小测试用例集生成技术研究，提出利用输入输出关系以及各个 测试需求所涉及的输入输出信息进行测试用例约简的方法，这种方法的特点是它不降低测试用例集的检 测能力。 ( 4 ) 基于组合测试的软件调试技术研究，提出了一种基于组合测试结果进行软件调试的方法，并开 发了一个辅助工具，可以为软件调试提供有益的线索和参考，从而有效地提高软件调试的效率。 ( 5 ) 最小测试用例集生成技术在配置测试、w e b 测试、黑箱测试等方面的应用研究，可以有效地提高 软件测试的效率、降低成本。 ( 6 ) 提出并实现了多因素组合覆盖测试数据的生成方法、二水平多因素系统的两两组合覆盖测试数 据生成方法、单因素组合覆盖方法和一种用于检测相邻因素问相互作用的测试数据生成算法。这些方法 可以依据具体软件，有效地生成最小测试用例集，满足相应测试要求。 ( 7 ) 给出对软件系统进行全面测试的最小测试用例集生成框架，提出建立一个可以扩展和细化的测 试目录，针对具体的待测软件，建立各个测试需求之间的相互关系，然后进行测试用例集的优化和约简 的方法。该方法可以有效地生成、管理、约简、分析和评估对软件系统进行全面测试的最小测试用例集。 1 6 本文结构 论文全文共7 章，分成网大部分：第一部分为第l 章，是全文的一个概述：第二部分包括第2 4 章，主要研究了组合测试的方法、技术和应用；第三部分包括第5 章和第6 章，主要是对基于测试需求 集的测试用例集约简方法的研究：第四部分为第7 章，是对最小测试用例集生成系统的介绍和全文的结 论。各章节组织如下： 第1 章作为整个论文的绪论，介绍了最小测试用例集生成方法研究的背景、研究目的和意义；介绍 了国内外现有的研究现状和仍存在的不足：描述论文的研究方案，在给出研究内容和方法后简要地介 绍研究论文的创新点和论文结构。 第2 章在回顾两两组合覆盖测试的最小测试用例集生成方法已有研究成果的基础上，分别基于网络 图模型和解空间树模型提出了两种不同的两两组合覆盖测试用例集的启发式生成方法，同时还提出了一 种代数方法，并对这些方法以及已有的方法进行了比较。 第3 章首先回顾了组合设计方法在组台测试中的应用的研究，然后提出了单因素覆盖方法、多因素 覆盖方法的最小测试用例集生成方法、二水平多因素系统的测试数据生成方法和一种用于检测相邻因素 间相互作用的测试数据生成算法。 第4 章研究了将组合测试方法应用于黑箱测试、w e b 测试、软件的配置测试，并研究了应用组合测 试的结果进行软件故障诊断和调试的方法。 第5 章在已有的基于测试需求集的测试用例约简方法研究的基础上，提出了一种科学实用的测试用 例集约简方法。 第6 章提出一种利用切片等技术获得的附加信息对组合测试的测试用例集和基于测试需求的测试用 例集进行融合和约简的方法。 第7 章介绍组合测试的测试用例生成系统的设计，测试用例集的管理和约简系统设计，并对整个论 文研究和实践工作进行总结，综述了我们在最小测试用例集生成技术研究领域获得的成果，以及在其他 相关领域所做的研究工作，并且指出我们现有工作的局限性、有待提高和改进的方面，简单阐述我们正 在进行或将要进行的研究工作。 5 第2 章两两组合覆盖测试数据生成 第2 章两两组合覆盖测试数据生成 两两组合覆盖测试方法是一种实用丽科学有效的软件测试方法，相应的测试数据生成算法是人们研 究的一个重点问题。本章首先介绍组合测试的基本模型，并回顾人们对于两两组合覆盖测试数据生成方 法的研究；然后分别提出了一种基于网络图模型的测试数据生成方法、一种基于解空间树模型的测试数 据生成方法和一种改进的代数方法等三种方法；最后对两两组合覆盖测试数据生成方法的研究进行了总 结。 2 1 组合覆盖测试模型 设影响待测软件系统s u t ( s o f t w a r e u n d e rt e s t i n g ) 的参数( 因素) 有月个，这些参数可以是s u t 的配置参数、内部事件、用户输入参数以及外部事件参数等。不失一般性，可设s u t 的每个参数c ，在有 限离散点集冗中取值，该集合中有岛个元素：a ，= 1 乃i ( 1 j 月) ，不妨设a ，盘2 a n ，并假设 这些参数是相互独立的，即某个参数的具体取值不会影响其他参数的取值或存在性。 定义2 1 称口元组( v ，v 2 ，) ( v ，互，v 2 l ，v 。r o ) 为待测系统s u t 的一个测试数据， 也可称为测试用例。 定义2 2 设和t 。是s u t 的两个测试数据，如果这两个1 2 元组在某b 个位置( b 个参数) 上对应的值 相同，称这两个测试数据的重叠数为b 。 当两个测试数据的重叠数d 2 时，说明其b 个参数的某个值组合同时被这两个测试数据覆盖：当b l 时，这两个测试数据不会同时覆盖任何参数的组合对。 组合测试方法主要通过组合设计方法产生一组测试数据来检测由系统参数或系统参数之间相互作 用而引起的故障，要实现对s u t 所有参数的完全组合覆盖，需要自自x x 自个测试数据，将这个测 试数据集记为a 。始的规模一般很大，需要根据具体情况和要求进行约简。 定义2 3 设a 是个口月矩阵，肛( 鼠，) ，其第，列表示s u t 的参数c j ，它的元素取白有穷符号 集台乃( ，= l ，2 ，月) ，即a ，心如果a 的任两列第列和第j 列都满足：乃的符号和乃的符号的 全部两两组合都在第j 列和第列形成的二元有序对中等概率出现，那么称4 是正交表；如果只要求至 少出现一次，而不要求等概率出现，那么称是一个两两组合覆盖表，其中m 是测试用例的个数。如果 它是能保证上述条件成立的最小正整数，那么月可以称为最小两两组合覆盖表，a 的每一行就是一条测 试数据。 定义2 4 利用正交表进行试验设计的方法为正交试验设计方法。 定义2 5 利用两两组合覆盖表进行试验设计的方法为两两组合覆盖方法。 类似地可以定义三三组合覆盖表，四四组合覆盖表，并统称为多因素组合覆盖表或覆盖表；称 利用多因素组合覆盖表进行试验设汁的方法为多因素组合覆盖方法、组台覆盖方法或组合测试。 从以上定义中可以看出，正交试验设计方法是一种两两组合覆盖方法；反之。两两组合覆盖方法不 一定是正交试验设计方法。在有些情况下，两两组合覆盖方法所需要的测试数据规模一般要远远小于正 交试验设计方法所需要的测试数据 4 0 一4 4 。 定义z 6s u t 的某口个参数c i ( 1 j 州) 的各种取值组合数为白= 口，x a ，x a ，若爿为该系 统的一个组合覆盖表( 两两组合覆盖表或三三组合覆盖表等等) ，记被a 覆盖的这月个参数的组合数为 硎，称测试用例表a 覆盖的这口个参数的组台数0 州与该个参数的所有组合数彻的比值为该系统对 应的组合覆盖表a 对该口( 1 m h ) 个参数的组合覆盖率，记为p = c n z 4 c # 7 。 组合覆盖方法是一种重要的软件测试方法，它充分考虑r 系统中各种因素以及各种因素之间的相互 作用可能对系统产生的影响，可以根据实际需要，用尽可能少的测试用例尽可能多地覆盖一些影响系统 的因素，同时这较少次数的测试的结果能够反映全面测试的内在规律。具有代表性且对于那些由系统中 6 东南大学博士学位论文 某些因素相互作用而导致的软件故障具有较强的检测能力。 组合覆盖方法根据覆盖程度的不同可以区分为单因素覆盖、两两组合覆盖、三三组合覆盖等等。随 着覆盖程度的提高，相应需要的测试用例规模也呈指数速度迅速增长。综合考虑软件测试的成本、时间、 各种因素的组合覆盖程度、测试用例的规模等因素，人们最常用的组合覆盖测试方法是两两组合覆盖方 法。 两两组