（电路与系统专业论文）基于Pairwise扩展算法的测试用例生成工具iCase的设计与实现[电路与系统专业优秀论文].pdf

摘要 软件测试作为软件开发过程中非常重要的一部分，是软件成本 中比重很大的一部分，也是提高软件产品质量、可靠性和控制软件 开发成本的关键。而测试用例的设计与生成是软件测试的重点和难 点之所在，其本质是如何依据一种以适当方式描述的软件规格说明 来设计和生成有效的测试用例。 在软件测试人员使用的工程方法中，p a i 刑i s e 测试成为了一个 必不可少的方法。随着对p a i 研i s e 算法的广泛研究，及基于各种 p a i 聊i s e 算法工具的实现，使之受到了软件测试业界的普遍关注。 但是p a i 刑i s e 算法依然存在如何处理因子间组合关系有强弱、如何 服从因子之间的取值存在约束、异常的因子之间的交互如何回避及 如何在现有用例上进行扩展等问题。 正是在这样的背景下，本文提出了p a i 刑i s e 扩展算法，并设计 实现了i c a s e 测试用例生成工具。本文研究的意义在于： 第一、本文通过对存在强弱关系因子、存在因子约束、存在异 常因子的系统进行了深入的研究分析，在原有p a i 州i s e 算法的基础 上设计并实现了子集深度算法、因子约束算法、异常因子交互回避 算法和可扩展继承算法有效的解决了p a i 刑i s e 算法存在的四大问 题。 第二、本文基于p a i 删i s e 扩展算法，使用v b a 对o 珩c ee x c e l 进行二次开发，设计并实现的测试用例生成工具i c a s e ，此工具有效 的解决了测试用例编写和维护困难的问题，把人们从繁杂的手工用 例编写过程中解脱出来，有效的提高了测试用例编写和维护的效率， 并使其能真正在业界广泛应用。 关键词：p a i 刑i s e 测试；子集深度算法；因子约束算法；异常因子交互回 避算法；可扩展继承算法；测试用例生成 a b s t r a c t a sav i t a lp a r to fm es o f t w a r ed e v e l o p m e n t ，s o r w a r et e s t i n gi sm e c o r ei nm es o r w a r ec o s t ，a 1 1 da l s ot h ek e yt oi 瑚p r o v es o f t w a r ep r o d u c t s q u a l 咄r e l i a b i l i t ya 1 1 dm ec o s tc o n 仃0 1 1 1 1 ed e s i 盟a n dg e n e r a t i o no f t e s t c a s e sa r et h ef o c u sa n dm ed i m c u l t yo fs o f t w a r et e s t i n g ，a n di t sa i mi s t od e s i g na i l dt oc r e a t ee a e c t i v et e s tc a s e sw i mt h ed e s 嘶p t i o no ft h e s o r w a r es p e c i f i c a t i o n s p a i 刑i s et e s t i n gh a sb e c o n l ea ni n d i s p e n s a b l et 0 0 1i nas o f 研a r e t e s t e r st o o l b o x w i t he x t e n s i v er e s e a r c ho fp a i 刑i s ea l g 嘶t h n la 1 1 dt h e r e a l i z a t i o no fi t st 0 0 1 s ，s o f 研a r et e s t i n gh a sb e e nt h eg e n e r a lc o n c e mo f t h ei n d u s 臼yh o w e r e v e r ，p a i r w i s ea l g o r i t h ms t i l lh a sm a n yp r o b l e m s ，f o r i n s t 锄c e ，h o wt od e a lw i t ht h a tf a c t o r sw h i c _ hh a st h es t r e n g mo ft h e r e l a t i o n s h i p ，h o wt oo b e yt h ef a c t o rb i n d i n gb e 似e e i lm ev a l u e s ，h o wt o a v o i dm ea b n 0 1 1 玎a 1i n t e r a c t i o nb e t w e e nm ef a c t o r sa n dh o wt oe x p a n d m e t e s t i n gc a s eb a s eo nm ee x i s t i n gc a s ea n d e t c e x a c t l yu n d e rt h eb a c k g r o u n d ，t h i sp a p e rp u t sf o 刑a r dt h ep a i 刑i s e e x p a n d i n ga l g 嘶t h n la n dd e s i g l l sat e s t i n gc a s e sg e n e r a t i o nt o o l i c a s e t 1 1 es i g l l i f i c a n c eo ft h i sp a p e ri s ： f i r s t ，t h ep 印e rm a k e st h ei n d e p t hr e s e a r c ha n d 锄a l y s i so fm e s y s t e mo ft h es t r e n g mo ft h er e l a t i o n s h i pf a c t o r t h ef i a c t o rb i n d i n ga n d a b n o m a lf a c t o r s b a s e do nt h ef o n n e rp a i 唧i s ea l g o r i m md e s i g n ，t h e i n d 印t h s e t a l g 耐恤n f a c t o rb o u n da l g 矾t h ，a b n o m l a lf a c t o r i n t e r a c t i o na v o i da l g o r i m ma n ds u c c e s s i o ns ca _ l a b l e a l g o r i t h m a r e r e a l i z e da i l dt h ew h 0 1 ef o u rp r o b l e m sa r es 0 1 v e d s e c 叽d ，b a s e do nt h ee x p a n s i o no fp a i 删i s ea l g 嘶t h m ，a n dt h e s e c o n d a 巧d e v e l o p n l e n t o fv b a 氨wo m c ee x c e l ， t e s t i n g c a s e g e n e r a t i o nt 0 0 1 “i c a s e ”i sd e s i g n e da n di m p l e m e n t e d i tc a ns 0 1 v em e p r o b l e mo fw t i t ea n dn l a i n t a i nt e s t i n gc a s ee f f e c t i v e l y ；a n dr e l i e fp e o p l e 仔o mm em u l t i f 撕o u sh a n d w o r kp r o 伊a n 埘e ，w h i c hi m p r o v e sm e i i i e m c i e n c yo ft h ec a s e s p r e p a r a t i o na 1 1 dm a i n t e n a n c ea n di t s 丽d eu s ei 1 1 t h ei n d u s 旬哆 k e yw o r d s ：p a i 州i s et e s t i l l g ；s e tt h ed e p t ho fa l g o r i t h m ；f a c t o rb o m l d a l g 嘶t ；a b n o l 1 a 1f a c t o ri n t e r a c t i o na v o i da l g o r i t h m ；s u c c e s s i o n s c a l a b l ea l g o r i t h m ；t e s ts u i t eg e n e r a t i o n 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不合任何其他个人或集体已经发表或撰写过的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：确兹弛盘 如 年多月 少日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在乒一年解密后适用本授权书。 2 、不保密嘣 ( 请在以上相应方框内打“ ) 作者签名：侧、叠虾艘日期 导师签名：乡宗日期 胃 僻7 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 1 绪论 1 1 软件测试技术概述及国内外发展状况 软件测试是软件工程中一项重要活动。在最简单的计算中，则 相当于观测执行的软件系统，以验证它是否运用正确，并确定潜在 的故障。测试被广泛应用于工业的质量保证，首先通过直接检查该 软件的执行，最后提供了一个现实反馈的行为，因此，它是一项重 要的分析技术。但是，除了直接的检查充分的运行外，测试还包含 了各种各样的活动，技巧和行为，并面临着许多复杂的挑战。事实 上，面对复杂性，普遍性和重要性不断增长的软件，根据所需的质 量水平确保它行为的可靠性变得越来越重要，越来越困难和昂贵。 早先的研究估计，测试可以消耗百分之五十，甚至更多的软件开发 成本。 目前软件测试面临多方面的挑战，例如如何调解m b t ( 基于模 型驱动的测试) 与现代不断变化的动态软件系统之间的矛盾；如何 有效地选择和使用从实际部署应用的软件运行时收集的数据；如何 限定和评价的有效性测试标准，即如何最大限度地减少修改的软件 的再测试等等。 近年来，许多专门的活动和研讨会，以及越来越多的软件测试 工程会议证明了软件测试已吸引了越来越多的专题研究人员的兴 趣。例如：第2 8 届国际软件工程大会跟踪研究的重点“测试与分 1 硕+ 学位论文 授”。 1 1 1 什么是软件测试 对软件测试的研究可以追溯到上个世纪六十年代，至今有四十 多年的发展历史，但对于什么是软件测试，至今未达成共识1 1 。从 不同的侧重点出发，主要有以下四种观点： 1 i e e e 在1 9 8 3 年提出的“软件工程标准术语”中将软件测试 定义【刁为：使用人工或自动手段运行或测定某个系统的过程，其目 的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间 的差别。该定义明确地提出了软件测试以检验软件产品是否满足需 求为目标。定义中包含两个方面的含义：一、软件产品是否满足规 定的需求；二、产品运行的实现结果是否与预期结果有差别。如果 有差别，则说明设计或实现中存在着缺陷，自然无法满足规定的需 求。 2 g j m y e r s 在t h ea no f s o 脚a r et e s t i n g 中指出3 1 ，一、 测试是为了发现错误而执行程序的过程；二、测试是为了证明软件 有错，而不是证明软件无错；三、一个好的测试用例在于能发现至 今未发现的错误；四、一个成功的测试是发现了至今未发现的错误 的测试。这个定义明确指出测试目的是“寻找错误”，而不是为了证 明软件是正确的。 3 从软件质量保证的角度看，软件测试是一种重要的软件质量 保证活动，其动机是通过一些经济的、有效的方法，捕捉软件中的 缺陷，从而达到保证软件内在质量的目的。 2 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 4 从软件质量的角度看，在软件开发的阶段，软件测试主要是 为了预防错误的发生；在软件测试阶段中，软件测试主要是发现软 件中的缺陷，从而达到保证软件质量的目的。 事实上，这四个定义的含义是一致的。软件测试的目的就是检 验软件是否满足需求目标，同时尽量查找软件中存在的缺陷。测试 结果为软件可靠性分析提供了依据，通过分析缺陷产生的原因和缺 陷的分布特征，帮助项目管理者发现当前所采用的软件过程的缺陷， 以便改进软件过程【4 】；帮助软件开发人员避免出现同样的问题，进 而提高软件的质量。同时，分析的结果也能帮助测试人员设计出更 有针对性的检测方法，改善测试的有效性【5 1 。 1 1 2 软件测试的原则 ( 1 ) 尽早地和不断地进行软件测试，各种统计数据显示，软件开 发过程中发现缺陷的时间越晚，修复它所花费的成本越大，因此， 需要尽可能早地进行测试。尽早测试包含两方面含义阳3 ：一、测试 人员在软件开发的早期就要参与软件项目，及时开展测试准备工作， 包括编写测试计划、制定测试方案、准备测试用例；二、尽早地开 展测试执行工作，一旦模块代码完成就及时开展单元测试，一旦模 块被集成就开展集成测试，一旦b u i l d 提交，便开展系统测试。 同时，持续不断的测试使得测试成为一个反复、递增的过程， 每次增量完成后部分测试进入回归测试形式。不断地测试可以避免 测试过程中的疏漏，增加测试的完整性【刀。 ( 2 ) 对所有软件产品进行全面测试，软件是程序、数据、文档的 3 硕士学位论文 集合，对软件进行的测试，不仅是对程序的测试，还应该包括对软 件“副产品 的“全面测试。需求文档、设计文档作为软件开发的 阶段性产品，直接影响到软件的质量，不能把握这些阶段性产品的 质量将最终导致软件质量的不可控【8 1 。 全面测试包含两层含义：一、对软件的所有产品进行测试，包 括需求文档、设计文档、代码、用户文档等等；二、测试工作需要 测试人员、开发人员甚至用户( 或客户) 的全面参与，例如对需求 的验证和确认，就需要开发、测试人员和用户的全面参与，毕竟， 是否满足用户的需求是软件成功与否的关键【9 】o ( 3 ) 关注软件开发全过程，软件测试过程与软件开发过程有着非 常紧密的联系，软件开发活动和测试活动相互影响【1 0 1 。如开发进度 的调整可能会引起测试进度和测试策略的调整，需求的变更会影响 测试的执行，这些都需求测试人员对开发和测试的全过程进行关注。 ( 4 ) 独立的、迭代的测试，软件开发的瀑布模型只是一个理想状 况，为适用不同的需求，软件开发过程的螺旋模型、迭代模型等软 件开发模型也就应运而生，这些开发模型中的需求、设计、编码工 作可能重叠并反复进行，这时就需要测试工作也是迭代和反复的。 软件测试和软件开发是紧密结合的，同时又是相互独立的。测 试不是依附于开发的一个过程，而是一个独立的过程，如果不能将 测试活动从开发中抽象出来进行管理，势必使测试管理陷入困境。 1 2 - 3 国内外发展现状 在软件比较发达的国家，特别是美国，软件测试已成发展成为 4 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 一个独立的产业，主要体现在以下几个方面【2 】：( 1 ) 软件测试在软件 公司中占有重要地位；( 2 ) 软件测试理论研究蓬勃发展，每年举办 各种各样的测试技术年会，发表了大量的软件测试研究论文，引领 软件测试理论研究的国际潮流。( 3 ) 软件测试市场繁荣。 美国的i e e e 、a c m 等组织制定了一系列软件测试规范，国外 的许多大学( 如c a n l e g i em e l l o n 、华盛顿大学等) 、研究机构( 如 m a t i o n a ls o r w a r et e s t i n gl a 等) 和公司( 如s o f 研a r ef e s e a r c h 、 m e r c u qi n t e r a c t i v e 、r a t i o n a lc o 印o r a t i o 等) 进行了大量软件测试的 研究和应用工作。其中c 锄e g i em e l l o n 大学侧重于回归测试和 c 1 i e n t s e r v e r 测试技术的研究，g e o r g em o s a n 侧重于基于规范的测 试自动生成和面向对象测试技术。 国内的软件产品测试技术起步较晚，在人力、物力上投入与国 外相比差距较大。直到1 9 9 0 年，成立了国家级的评测中心，测试服 务才才逐步开展起来。但是，随着我国软件产业的蓬勃发展及对软 件质量的重视，软件测试也越来越被人们所看重，软件测试正在逐 步成为一个新兴的产业。2 0 0 8 年8 月，在上海举办了首届中国软件 测试与软件产业发展战略研讨会。软件公司都已经或者正要建立独 立的专职测试队伍，第三方测试机构得到了蓬勃的发展。一些大学 和科研机构也对软件测试进行了研究，北京大学、北京航空大学进 行了一系列软件分析和测试工具的研究和开发，研制了一系列的程 序理解工具和测试工具，比较具有代表性的工具有s a f e p r o c c 抖， s a f e p r o j a v a 。航空计算机研究所、南京大学在嵌入式系统测试方 硕+ 学位论文 面进行了较多工作，开发了一些静态分析工具和测试用例自动生成 工具。西北工业大学在航空软件仿真测试以及c s 系统的测试方面 进行了许多研究工作并取得了一系列成果。 1 2p a i 唧i s e 工具对比分析及课题的提出 为了对可用p a i n i s e 的工具有一定的认识，并确认其是否适合 当前的应用需求，笔者对a 1 1 p a i r s 、r e d u c e 蛔和无线的p a i r 而s e 工具进行了试用，并把试用结果进行了对比分析。对比分析主要从 功能、效率、易用性、可给他打电话性几方面进行。 1 2 1a 1 l p a i r s 工具分析 ( 1 ) 功能 输入：影响因素和因素的取值。 输出：符合2 维p a i r w i s e 全覆盖的一组用例； 不支持约束条件、不能支持2 维以上的p a i 而s e 覆盖； 可以给出每个用例覆盖的p a i 刑i s e 对的数量； 给出的用例集合不是最优，只是近似最优。 ( 2 ) 效率 速度很快，效率非常高，以下是速度和用例规模对比( 如 表1 1 所示) ： 6 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 ( 3 ) 易用性 a 1 1 p a i r s 工具是在命令行方式下操作，使用非常简单。 ( 4 ) 可维护性 为用户提供了命令行下的可执行文件； 提供了p e 订脚本。 1 2 2r e d u c e a 盯a y 工具分析 ( 1 ) 功能 输入：任意的一个用例集。 输出：按照p a i r w i s e 覆盖覆盖要求，剔除无效用例后的一 个用例子集； 可以支持约束条件； 能支持2 维或3 维p a i 刑i s e 覆盖； 可以给出每个用例覆盖的p a i 邢i s e 对的数量； 可以给出输入用例集和输出用例集有哪些p a i 刑i s e 对没有覆盖到； 给出的用例集合可以达到最优。 ( 2 ) 效率 速度很快，效率高，但随着用例规模的增加，效率下降明显 7 硕士学位论文 ( 3 ) 易用性 在e x c e l 表格中，a 编写的脚本来执行，操作较简单。 ( 4 ) 可维护性 开发v b a 源代码。 1 2 3s m 础d e s g i n 工具分析 ( 1 ) 功能 输入：影响因素和因素的取值。 输出：符合n 维p a i 研i s e 全覆盖的一组用例； 支持约束条件； 支持2 维的p a i 刑i s e 覆盖； 给出的用例集合不是最优。 ( 2 ) 效率 速度很快，但效率较低( 如表1 3 所示) ： 表卜3s 眦r t d e s g i n 性能分析表 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 ( 3 ) 易用性 在e x c e l 表格中进行操作，稍有一慎可能导致结果错误。 运行过程中有时会导致e x c e l 异常关闭。 ( 4 ) 可维护性 开发v b a 源代码。 1 2 4 工具对比分析总结及课题的提出 综合考虑各方面的因素，r e d u c e 岫的表现最佳( 如表1 - 4 所示) ： 表卜4 综合分析表 从上面的单个工具的分析及其综合对比分析可以看出，现有的 p a i 刑i s e 工具大多功能单一，而且存在以下四个方面的问题： 1 ) 因子间组合关系有强弱该如何处理? 2 ) 因子间取值有约事时该怎么办? 3 ) 重要因子组合能保证一定覆盖到吗? 4 ) 异常因子间交互回避该如何处理呢? 基于上述问题，本文将提出子集深度算法，因子约束算法，可 继承扩展算法及异常因子交互回避算法解决四个方面的不足，并根 据这四个算法设计实现i c a s e 测试用例生成工具。 9 硕士学位论文 1 3 论文的组织结构和主要研究内容 本文的组织结构如下： 第一部份：介绍了论文的背景，主要包括软件测试的基本概念 与国内外的发展现状，以及已有p a i 而s e 工具的不足并提出了本文 主要的研究课题。此外，本章还简单地介绍了本课题的主要研究内 容与意义。 第二部份：详细描述了p a i 刑i s e 的原理及算法介绍，并与正交 分析与单因素测试设计方法进行了对比分析，最后指出已有 p a i 州i s e 相关算法与工具研究中存在的问题。 第三部份：本章是本文的核心章节，在本章中阐述本章祥细描 述了子集深度算法、因子约束算法、异常因子值交互回避和可继承 扩展算法四种p a i 州i s e 扩展算法原理与实现。 第四部份：详细介绍了实现上述理论的最终产品i c a s e 软件的 设计目标及主要功能模块的实现。通过一实例演示了如何使用i c a s e 来实现一个软件的测试用例的生成，并收集了接入网i c a s e 试用阶 段实验数据，对其进行了全面的分析 第五部分：总结与展望。对论文所做工作进行了总结，并展望 了今后研究的方向。 1 0 基于p a i r w i s e 扩展算法的测试用例生成t 具i c a s e 的设计与实现 2 p a i m i s e 测试技术概述 上一章介绍了软件测试技术概述及国内外的发展，分析了已有 p a i 刑i s e 测试用例生成工具的不足，并提出了本文所研究的课题。本 章将详细介绍p a i 御i s e 工程方法的原理与算法，分析其优点，并指出 当前p a i 刑i s e 相关算法研究工作中存在的四点不足，提出p a i 刑i s e 扩展 算法。 2 1p a i 邢i s e 原理 p a i 刑i s e 方法是源于对传统的正交分析方法进行优化后得到的产 物，它的理论来源于如下的数学统计( 如表2 1 示) ： 表2 1n 维深度所引发缺陷的数目与百分比 丝塑型堕墨! 1 2 堡旦墅!竖箜堡垫! ! z ! 里旦墅! 百分比累计百分比百分比累计百分比 从上表可以看出，约3 5 的缺陷是单个因子影响下产生，约3 8 是2 个因子交互作用影响产生，约1 9 是3 个因子交互作用影响下产 生。累计约7 3 的缺陷是由1 个或2 个因子的作用引起的。因此， p a i 刑i s e 就是基于覆盖所有2 因子的交互作用产生的用例集合性价比 最高而产生的。 硕士学位论文 2 2p a i 刑i s e 算法介绍 对一个拥有三个选项按钮的对话框进行黑盒测试，此对话框用于 乘客选择自己的旅行需要，第一个按钮指定目的地，第二个按钮指定 坐仓类型，第三个按钮指定客户的坐位位置，取值分别如下： d e s t i n a t i o n ：u s a 、c a n a d a 、m e x i c o c 1 a s s ：c o a c h 、b u s i n e s sc 1 a s s 、f i r s tc 1 a s s s e a tp r e f e r e n c e ：a i s l e 、斫n d o w 对于两个分别拥有三个不同的选项r a d i ob u t t o n s 和一个拥有两个 值的c h e c k b o x ，存在3 3 2 ，共18 个可能的值需要测试，利用正交 分析方法可以产生用例集如表2 2 所示： 表2 2 正交用例生成表 1 2 基丁二p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 根据p a i 而s e 算法，测试用例就可以简化成( 如表2 3 所示) ： 表2 3 p ai r w i s e 用例生成表 此表确保c a n a d a 与c o a c h 、b u s i n e s sc l a s s 和f 以tc 1 a s s ，a i s l es t a t e 和、斫n d o ws t a t e 的组合至少被测试了一次。同样，每一个选项又与其 它的选项被测试。有些两因素所产生的缺陷在用例3 中就被暴露出来 了，因此用例1 2 就不需要了，因为用例1 2 所产生的两因素组合同时也 被用例1 5 、用例1 1 和用例3 所包含。因此使用p a i 刑i s e 算法生成测试用 例，在此示例中可以减少一半的测试用例。 2 3p a i 州i s e 与其它工程方法效果对比 2 3 1p a i 刑i s e 与正交分析法效果对比 正交分析法是一种常用的测试设计方法，它可以有效提高测试设 计的全面性，但是实际应用的时候，正交法得出的用例数量过于庞大 且冗余较多，无法全部进行测试。假如测试对像为t ，在在1 0 个输入 因子，其中4 个因子有4 个取值，3 个因子有3 个取值，3 个因子有2 个取 值。 硕士学位论文 利用正交分析方法得到的测试用例数量为：4 4 4 4 3 3 3 2 2 2 = 5 5 ，2 9 6 个测试用例。 利用p a i 刑i s e 工程方法，只要求2 因子交互作用，则生成的测试用 例数为2 4 个，是原用例规模的o 。0 4 。 因此，可以看出对于p a i r 谢s e 工程方法，因子越多，效率将越高。 2 3 2p a i 刑i s e 与单因素测试设计方法对比 单因素测试用例的设计采用不断地分解因子的策略，对一个功能 不同的因子只能按不同的测试项目来独立组织测试设计，整体的测试 设计覆盖实际上只能达到1 维正交水平，对于遗漏的因子间的交互测 试只能通过进行经验判断补充。 p a i 刑i s e 测试设计采用先分解因子再组合的策略，通过工具支持 自动完成因子的组合关系，一个功能的不同因子集中统一测试设计， 整体测试设计覆盖达到2 维正交水平。与单因素测试设计相比，强化 了因子间的交互作用，能减少漏测试；用例效率高，减少了总的测试 用例数量，其原因在于它改变了单用例覆盖单一测试点的传统模式， 一个测试用例覆盖了n 个测试因子，也即覆盖了 ( + c 乙+ c + + c ：) 个测试点。 2 4p a i 刑i s e 相关算法的研究工作与存在的问题 1 9 8 5 年m a n d l 最早提出参数两两组合覆盖的概念，将此概念应用 于a d a 编译器的测试，并利用正交拉丁方来产生测试用例集n 引。 19 9 2 年，b r o m l l i e 报告了使用正交表对p m ) ( s t a r m a i l 系统进行 1 4 基于p a i r w i s e 扩展算法的测试用例生成t 具i c a s e 的设计与实现 测试的实例研究，他们利用o a t s 工具产生正交表，使用较少的测试 用例检测出很多以前无法发现的错误1 3 】。 2 0 世纪9 0 年代后期，贝尔实验室将组合测试方法的研究推向了一 个新的高潮，他们提出一种基于贪心策略的组合测试用例生成算法， 并开发了a e t g 系统用于产生组合测试用例集【1 4 。16 1 。 2 0 0 1 年，s c h r o e d e r 在其博士论文中提出了利用软件附加信息对组 合测试的测试用例集进行约简和优化的方法【1 7 1 。同年，s a l e m 在其博士 论文中系统研究了如何将试验设计方法应用于软件测试1 8 】。l e 珥口t a i 则提出了一种基于参数顺序扩充的两两组合测试数据生成策略，并开 发了p a i r t e s t 系统用于产生两两组合的测试用例 1 9 2 0 1 。 2 0 0 2 年，k m i n 和r e i l l y 研究了组合测试的可用性，发现大约7 0 的故障是由两个以下参数的相互作用引起的，由此说明了两两组合测 试的应用价值【2 l 】。同年，k o b a y a s h i 和t s u c h i y a 提出了一种生成两两组 合测试数据的代数方法【2 2 】。w i l l i 锄在其博士论文幽中不仅研究了一 套用于生成两两组合覆盖表的代数方法，同时还深入研究并提出了组 合测试的8 个应用场景。 2 0 0 3 年，c o h e nm b 等人将模拟退火算法应用于多重维数组合测 试用例的生成，该方法综合考虑了运算效率和运算结果之间的关系，可 以根据时间和效率上不同的要求来生成尽可能优的结果2 4 乏6 1 。 2 0 0 4 年，k m l n 和w a l l a c e 通过实验进一步研究了大规模分布式系 统中组合测试可用性，发现此类系统中的故障一般最多由4 6 个参 数的相互作用引发【2 6 1 。同年，s h i b a 和t s u c l l i y a 等人研究了遗传算法和 硕十学位论文 蚁群算法在组合测试数据自动生成中的应用【2 8 】。c o l b o 唧和c o h e n m b 等人提出一种两两组合测试数据生成的确定性密度算法【2 9 】。 s c h r o e d e r 等人通过实验比较了n 维组合测试与相同规模随机测试的 错误检测能力【3 0 1 。 2 0 0 5 年，c 0 1 b 0 1 l n l 和s h e 聊o o d 等人研究了两种组合覆盖表的生成 方法，分别应用于具有不同参数取值的两两组合覆盖表和高维组合 覆盖表的生成【3 l - 3 2 1 。 至今，对于p a i n i s e 算法的研究仍然没有有效的解决因子间组合 关系有强弱，因子间取值有约束，异常因子之间交互回避及在不改变 现有用例的基础上进行扩充的问题，鉴于此，笔者提出了p a i 姗i s e 扩 展算法，将能有效解决这四大问题。 2 5 本章小结 本章首先介绍p a i 州i s e 工程方法的原理及算法，并将其与正交分 析法和单因素测试设计方法进行了对比，说明其优点。最后分析了已 有p a i 删i s e 算法的研究工作及其存在的不足，并提出了四种算法解决 现在有p a i 刑i s e 算法中四个方面的不足。下一章是本文的核心章节， 将重点介绍p a i 刑i s e 扩展算法的原理与实现。 1 6 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 3 p a i 刑i s e 扩展算法 上一章介绍p a i 州i s e 工程方法的原理与算法，并与其它工程方法 对比分析其优势，然后介绍了p a i 刑i s e 相关算法的研究工作与存在四 个方面问题，提出了p a i 而s e 扩展算法。本章将详细描述四个p a i 刑i s e 扩展算法的原理与实现。 3 1 子集深度算法原理与实现 3 1 1 子集深度算法的原理 子集深度算法根据因子间组合关系进行测试用例的生成，其设计 的主要目的是为了解决因子之间组合关系有强弱的问题。假设t 是参 数p l ，p 2 ，p 3 ，p i 的一个p a i 刑i s e 测试用例集。我们考虑其中p l ， p 2 ，p 3 必须满足3 维交互，这时我们须计算出满足3 维交互的p l ，p 2 ， p 3 的用例集n ，这里我们设存在一个参数m ，将n 的每一行( 代表p l ， p 2 ，p 3 所构成的一个用例) 代表参数m 的一个取值，代入余下的参数 p 4 ，p i ，构成新的参数序列p 4 ，p i ，m ，再使用p a i 刑i s e 算法生 成新的用例覆盖表t 。 现在举例说明：假设a 的取值为a l ，a 2 ；b 的取值为b 1 ，b 2 ； c 的取值为c l ，c 2 ，c 3 。则a 、b 和以构成的p a i m i s e 测试集如表 3 1 ( a ) 所示，如果使用子集深度算法，需要同时考虑每个用例中3 个因子的取值要同时被覆盖至少一次，则得到的用例如表3 1 ( b ) 所 17 硕十学位论文 示，现将期得到的每一个用例当做一个参数，与其它的参数一同， 根据p a i 刑i s e 算法生成最终的用例。 表3 1p a i r w i s e 用例覆盖表与3 维用例覆盖表对比 ( a )( b ) a a l a l a 2 a 2 a 2 a 1 b b 1 b 2 b 1 b 2 b 1 b 2 c c l c 2 c 3 c l c 2 c 3 3 1 2 子集深度算法的实现 首先找出子集深度为n 的最大组合数m 。我们使用一个m n 的二维数组来存放子集深度为n 的组合覆盖表。将参数fl ，f 2 ， ，f n 的组合填入数组中相应的位置，这样就会剩下m ( f l ，f 2 ，f n 的组合个数) 。 在此基础上从左向右依次扩展参数。对于参数f n + 1 来说，由于参 数f2 ，f 3 ，f n 的每一个n 1 维组合均出现第n 个参数的值的个 数次，如果第一个参数的取值个数小于第n + 1 个参数的个数，则需 要对这些n 1 维组合进行补充，使每一个n 1 维组合的出现次数 达到第n + 1 个参数的取值个数。具体方法是，针对每一个组合，首先 在m _ ( fl ，f 2 ，f n 的组合个数) 寻找一行，该行中参数f2 ，f 3 ，f n 一1 2 3 l 2 3 l 2 3 1 2 3 c c c c c c c c c c c c c 一1 1 l 2 2 2 1 l 1 2 2 2 b b b b b b b b b b b b b l 1 1 1 1 l 2 2 2 2 2 2 a a a a a a a a a a a a a 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 对应的位置与该n 1 维组合的匹配程度最高，且不匹配的位置上均 未赋值，填充该行中未赋值的位置，使得该行在参数f2 ，f 3 ，f n 对 应的位置上出现此n 1 维组合，依此类推，直至参数f 2 ，f 3 ，f n 对 应的列中该n 1 维组合总的出现次数达到第n + 1 个参数值的个 数。然后在每一个n 1 维组合的前第n + 1 个参数值的个数次出现 之后依次将参数f n + l 的值分别填入第n + l 列中相应的位置。依此 类推，依次扩展参数直至f n ，详见算法1 。 算法1 子集深度覆盖表生成算法。 其中：t m ，n 】：子集深度覆盖表 n u m b e r i 】：代表参数i 的取值个数 步骤： m = 0 ；l f l ； 矗竹i _ 1t on n + 1 计算测试用例数量 m 【i 】= n u m b e r 【i 】n u n l b e r 【i + 1 】口k n m n b e r 【i + n - l 】； ) m = m a 】【 m 【i 】) ； h l i t i a l i z et m ，n 】； 初始化矩阵t 对参数f l ，f 2 ，f n 进行初始化 f o ri = 1t oa 【1 】 处理参数f 1 和f 2 f 1 0 r j = 1t on u m b e r 【2 】 t k ，l 】= i ； t k ，2 】= j ； k + + ： 1 9 硕士学位论文 ) f o ri = 3t 0n i f n u i i l b e r 【i - 2 】 n u l n b e r i 】 m e n 对参数f i 1 进行补充 e = 1 ； f 1 0 rj = lt 0 n m n b e r 【i 】一n m n b e r i - 2 】 f0rk = 1t 0n 瑚出e r 【i - 1 】 i f t 【e ，i - l 】= 0t 1 1 t 【e ，i 1 】= k ； e + + ： ) ) f o r j = l t 0 n 伽曲e r i l 】 初始化f i l 值的出现次数 c o u n t j 】= 0 ； f 0 r j = l t 0 m 为参数f i 赋值 c o u n t ( t 【j ，i 一1 】) + + ； i f c o l l i l _ t ( t 【j ，i l 】) ) f o ri = n + lt on 向右依次扩展参数 i fn m n b e r 【i n n m h b e r 【i 】血e n f 0 r 参数f i n + 1 ，f i 1 的所有n l 维组合 找出与该组合不匹配但最相似的行，按此组合补足该行中的值，不断重复 直至该n l 维组合的出现次数达n u i n b e r 【i 】； ) 2 0 基于p a i r w i s e 扩展算法的测试用例生成工具i c a s e 的设计与实现 ) f o f j = 1 t om 记录第j 行出现的参数f i n + l ，f i 一1 的n - 1 维组合的当前出现次数 c o u m ； i f c 伽n t 3 2 因子约束算法原理与实现 3 2 1 因子约束算法原理 因子约束算法将根据所定义的约束生成符合条件的测试用例， 其设计的主要目的是为了避免生成因子之间存在约束关系的用例的 问题。假设t 是参数p l ，p 2 ，p 3 ，p i 的一个p a i n i s e 测试用例 集。我们考虑其中参数p l 和p 2 ，当p 1 的取值为v 1 时，p 2 的取值 不能为u 1 ；当p 1 的取值为v 2 时，p 2 的取值不能为u 2 ；当p 1 的取 值为v 3 时，p 2 的取值必须为u 3 ；当p l 的取值为v 4 时，p 2 的取值 必须为u 4 ；这时在生成用例的时候需要分别设置一个包含集合和一 个非包含集合，例如包含集合c o n s 仃a i n t 一 ( v 3 ，u 3 ) ，( 舛，u 4 ) ) 和非包含 集合n o n c o n s t r a i n 仁 ( v 1 ，u 1 ) ，( v 2 ，u 2 ) ) ，这样，在p a i n w i s e 算法的基 础上加入相应的p a i 麟i s e 是否在这两个集合中的判断，即可生成带 约束条件的用例集t 。 现在举例说明：假设a 的取值为a l ，a 2 ；b 的取值为b l ，b 2 ； c 的取值为c 1 ，c 2 ，c 3 ，存在a 的取值为a 1 时，b 的事不能为 2 1 硕士学位论文 b 1 的约束。则a 、b 和以构成的p a i 而s e 测试集如表3 2 ( a ) 所示， 如果使用因子约束算法，需要把约束条件考虑进去，则得到的用例 如表3 2 ( b ) 所示，由于( a 1 ，b l ，c 1 ) 包含了( a 1 ，b 1 ) 和( b l ，c 1 ) p a i 州i s e 对，因此通过补充( a 1 ，b 2 ，c 1 ) 和( a 2 ，b 1 ，c 1 ) 来完善。 表3 2p a i r w i s e 用例覆盖表与因子约束用例覆盖表对比 ( a )( b ) a a 1 a 1 a 2 a 2 a 2 a 1 b b 1 b 2 b 1 b 2 b 1 b 2 c c 1 c 2 c 3 c 1 c 2 c 3 3 2 2 因子约束算法的实现 a a 1 a 2 a 2 a 2 a 1 a 2 a 1 b b 2 b 1 b 2 b 1 b 2 b 1 b 2 c c 2 c 3 c 1 c 2 c 3 c 1 c 1 首先找出s u t 中最大的组合数m ，然后生成一个m n 的二维数组 t 来存放覆盖表。先根据约束关系生成参数1 和参数2 的p a i n i s e 用例 集，然后依次将参数代入，在扩展用例集的同时判断其是否满足约束 条件，如果满足则将用例替换或增加一个新的用例，依次类推，生成 最终的测试用例覆盖表。 算法2 ：因子约束用例表覆盖生成算法 其中：t m ，n ：因子约束用例覆盖表 n u m b e r 【i 】：代表参数i 的取值个数 步骤： m = o ；k = 1 ；