（计算机应用技术专业论文）基于环形fscs的mt研究.pdf

| | i i i i | | i i i | | i | l m l | i | f l f l l | l i l l l f l f i | l 竺垄堑蔓奎堂堡主兰垡笙奎苎三至登! y 18 4 6 516 e c n u2 01 l sd i s s e 慨i o nf o rm s cd e 铲e es c h o o lc o d e ：10 2 6 9 s t i l d e n tn u l n b e r ：5 1 0 8 1 2 0 1 0 3 7 e a s tc h i n an o r m a l u n i v e r s i t y m e t a m o r p h i ct e s t i n gr e s e a r c h b a s e d0 nc i r c l i n gf s c s d e p a r t m e n t ：q 堕旦逊丛s 曼i 盟鳗垒丑鱼! 垒堡鱼q ! q g y m a j or ： q 堡p 巫丛s q 煦堑曼堑亟卫! 曼q 碰 r e s e a r c ha r e a ： 旦煎业签曼壁垒鲢q ! q g y 堑亟p p l i 堡堑i q 坠 s u p e r v i s o r ： c a n d i d a t e ： o c t o b e b2 0 1 0 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 郑重声明：本人呈犁学位论文剪亏彩旧3 弘c j 似人 r 印。觅 是 在华东师范大学攻读硕孟博士( 请勾选) 学位期间，在导师的指导下进行的研究工作及 作者签名： 华东师范大学学位论文著作权使用声明 器孑删弘钐p ，认了_ 翻 系本人在华东师范大学攻读学 位期间在导师指导下完成的硬怨博士( 请勾选) 学位论文，本论文的研究成果归华东师 范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门 和相关机构如国家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允许学位 论文进入华东师范大学图书馆及数据库被查阅、借阅：同意学校将学位论文加入全国博士、 硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、 缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文， 于年月日解密，解密后适用上述授权。 ( 叫2 不保密，适用上述授权。 ， 导师签名= 乏：兰：! 二二 本人签名 诎年f 月侈日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论文( 需 附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上述部门审定的学位 论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权) 。 华东师范大学硕士学位论文 一邀基鑫硕士学位论文答辩委员会成员名单 姓名职称单位备注 杨宗源教授华东师范大学主席 孙蕾副教授华东师范大学 叶建中副教授华东师范大学 随着现代软件规模的日益膨胀和复杂程度的日益增长，软件测试在科学控 制成本、保证软件可靠性等等方面都起着越来越重要的作用，因而受到人们广 泛的重视。然而，在软件测试中，一直存在着测试用例集的可靠性问题和o r a c l e 问题。 随机测试在输入域中随机产生测试用例，是选择测试用例最简单的方法， 因其简单有效而被广泛使用。但是，由于其固有的选择用例的盲目性，随机测 试的效率不高。近年来，t y c h e n 提出的自适应随机测试在很大程度提高了随 机测试的有效性。f s c s 是最重要和最经典的自适应随机测试算法。但是，f s c s 的边界效应影响了它的有效性，尤其是在高维输入域的情况下。为此，我们提 出了环形f s c s 算法，彻底解决了边界效应，从而提高了测试的有效性。 所谓o r a c l e 问题就是指，在软件测试中，测试人员往往无法判定程序输出 结果的正确性。为解决这个问题，t y c h e n 提出了蜕变测试。蜕变测试通过检 查一系列测试用例的输出是否满足蜕变关系来测试程序。原始用例和蜕变关系 是影响蜕变测试效果的两个非常重要的因素。我们使用环形f s c s 作为原始用 例生成策略，为蜕变测试筛选代表性强的测试用例，并通过测试工具( a m t ) 提 供组合蜕变关系的手段，取得了更好的效果。 尽管蜕变测试简单实用，但其成功使用仍然离不开合适的工具软件。为此， 我们设计并实现了一个蜕变测试工具舢订t ( a u t o m t ) ，为进行蜕变测试提供了 方便，提高了测试效率。蝴t 基于自适应随机测试产生原始用例，提供对复合 蜕变关系的支持，并且是一个开放的系统，为新的原始用例生成策略预留了接 口。 关键字：o 瑚l c l e 问题，蜕变测试，自适应随机测试，f s c s ，环形f s c s 华东师范大学硕士学位论文 基于环形f s c s 的m r 研究 a b s t r a c t w 洫n l ei n c r e 嬲锄e n to fs o r w a r es c a l ea 1 1 dc 0 m p l 谢饥s o f e t c s t i r 培p l a y sa m o r ei i i 】p r t a n tr o l ei i lc o s tc 0 n 仃o la n ds o f 呐a r er e l i a b i l i 饥a n dh e n c eg 础1 sm o r e a i l dm o r ea t t e n t i o n e 彘c t i v e n e s so ft e s tc a s e sa n do r a c l ep r o b l e m 撇t 、) l ，oi 喇o r i s s u e si i ls o f h 聊et e s t j h g a m o n gt h em e 廿l o d so fg e n e r a t i i l g 印p r o p r i a t et e s tc a s e s ，r 孤d o mt e s t i i l gi st h e s i n l p l e s to n e t b s tc a s e sa r eg e n e r a t e dr a n d o m l y1 j r o m 也ei i l p u td o i n a 血h e l l c ei tl m s b e e n 晰d e l yu s e di i ls 0 小) l ，a r et e s t i n g h o w e v e r ，i th 嬲p o o re 虢c t i v e n e s s r e c e n n y ， a d a p t i v er 锄d o mt e s t i n g ( 越) p 姊o s e db yt y c h e ni sas i 鲥f i c a n ti m p m v e m e n t o fr a n d o mt e s t 堍o fa l lt h ei m p l e m e n t a l i o i l so fa r t ，f s c sa l g o 珊l i i li s 舭m o s t c l a s s i co n e h o w e v e r ，“b o u l l d 哪e 虢c t ，h 嬲ab a di i l f l u e n c e0 nm ee 鼠c t i v e n e s so f f s c s ，p 硎c u l a r l yw h e nt h e 邱u td o m 咖i sl l i 曲d i m e i l s i o n a l 舡ar e s u l t ，w e p r o p o s ec 沁l i n gf s c sa l g o r i 廿n t 0s 0 1 v e “b o u l l d a 巧e 毹c t ，a n di m p r 0 v e s 吐l e e m c i e n c yo ff s c s i ns o 矗w a r et e s t i l l g ，t e s t e r sa r ca l w a y su n a b l et 0d e t e n l l i n et l l ec 0 r r e c t n e s so f p r o 蓼锄o u 勺? u t s ，w i l i c hi s c a l l e do r a c l ep r o b l e m m e 切m o r p l l i ct e s t i n g ( m t ) i s p r o p o s e db y l y c h e n t 0r e s 0 l v em ep r o b l e m m tt e s t sap 黟a mb yc h e c k i n gn l e r e l a t i o l l s 锄o n gs e r i e so ft e s tc 弱e s o u 印u t s a 【1 1 0 n g 廿l ef 砬t o r sm a ta f r e c tm t r e s u l t s ，o r i g 试a lt e s tc a s e sa n dm e 咖r p t l i cr e l a t i o l l sa r e 伽o 、，e 巧i n l p o r t a l l ：to n e s i nt h i sp 印e r 他u s ec 沁l i n gf s c sa l g o r i t l l i i l 弱i 血i a lc a l s eg e n e r a t i o ns 仃a t e 酉e st o s e l e c tm o r e 够p i c 2 l lt e s tc 弱e s ，a n dp r o v i d eat e s t i n gt o o l ( a m t ) t 0c o m b 证ed i f f e r e n t m e t a i i l o 印h i cr e l a t i o l l s i tt u 】m so u tt ob e 慨m tp e 而m l sb e 戗既 a l u 曲m th 嬲b e e nw i d e l yu s e di ns o f h a r et e s t i n gd u et ot l l es i m p l i c 毋a n d p m c t i c a l i 饥i ts t i l ln e e d sp r o p e rt o o l s b a s e d0 nn l ea b o v ei d e a s ，w eb u i l dat o o l c a l l e d 蝴t ( a u t o - m d ，w 1 1 i c h 矗l c i l i t a t e sm ta n di i n p r o v e st e s t i n ge 硒c i e n c 弘i t g e n e r a t e st e s tc a s e sb a s e do na d a p t i v er 觚d o mt e s t m ga n ds u p p o r t sc o n l p o u l l d m e t 锄。印m cr e l a t i o i l s m o r e o v e r ，i ti sa no p e ns y s t e mw m c ha 1 s 0p r o v i d e sa i l i n t e 而c et 0a d dn e wo r i g 砌t e s tc a s eg e n e 洲o ns 仃a t e g i e s k e yw o r d ：o r a c l ep r o b l e m ，m e t a m o 印1 1 i ct e s t i i 培，a d a p t i v er m d o mt e s t i l l g ， f s c s ，c 硫l i n gf s c s 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 摘要 目录 a b s t r a c t i 第一章绪论1 第二章软件测试概述 2 1 软件测试3 2 2 软件测试的关键问题4 2 2 1 测试用例集的可靠性问题4 2 2 2o r a c l e 问题4 2 4 随机测试5 2 5 蜕变测试5 2 6 挖掘已测试用例“信息 一6 2 7 软件测试工具6 第三章白适应随机测试 3 1 自适应随机测试算法概述一8 3 2f s c s 算法1o 3 3 其他自适应随机测试算法11 3 3 1i p 1 l 3 3 2i d i f s c s 1 2 3 3 3m i 】m 孵a r t 1 3 3 3 4 灿玎b yr a n d o mp 删廿0 1 1 i n g 1 4 3 4f s c s 算法的边界效应1 5 第四章蜕变测试 4 1 概j 丕1 7 4 1 1 蜕变关系研究18 4 1 2 原始用例研究2 0 4 2 蜕变测试工具开发2 0 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 第五章基于自适应随机测试的蜕变测试工具一触岍 2 2 5 1a m t 的总体结构2 2 5 2 测试对象解析2 3 5 2 1 构建测试对象2 3 5 2 2 测试用例之间的距离2 5 5 2 3 测试用例的随机生成2 6 5 3 原始用例的生成策略2 7 5 4 蜕变关系的表达和解析2 9 5 4 1 蜕变关系的表达2 9 5 4 2 蜕变关系的解析。3 0 5 4 3 复合蜕变关系的实现。3 2 5 5 蝴t 的应用实例3 3 第六章基于距离的f s c s 的边界效应及其解决方法。3 7 6 1 解决“边界效应”的一些方法3 7 6 1 1 分区法3 7 6 1 2 虚图像法3 9 6 2 环形f s c s 算法4 1 6 2 1 环形f s c s 的基本思想。4 1 6 2 2 实验和结果分析4 3 第七章总结和展望4 5 参考文献 q 1 7 攻读学位期间发表的论文5 1 致谢。 l v 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 第一章绪论 随着计算机的广泛应用，应用软件在人们的日常生活和工作中起了越来越重 要的作用，在许多关键领域，比如在医疗系统中，软件容不得有半点差错。以目 前的软件技术发展水平，提高软件品质最有效最现实的方法仍然是测试。随着软 件规模的日益庞大和复杂，用于软件测试的成本也逐渐升高，软件测试受到工业 界和学术界越来越多的重视，成为当前的研究热点之一。 通常软件测试根据是否需要了解程序内部结构分为黑盒测试和白盒测试。无 论何种测试方法，在实际测试中，因工作量太大不可能对待测程序进行“穷举测 试 ，即不可能将所有可能的输入都执行一遍，所以实际上软件测试都是不彻底 的。要保证测试的有效性必须妥善解决软件测试中的两大关键问题：其一，怎么 产生足够有效的测试用例保证测试的有效性，即测试用例集的可靠性问题；其二， 如何验证输出结果的正确性，即o r a c l e 问题。 黑盒测试由于不需了解程序内部结构，因而简单实用。随机测试就是一种黑 盒测试，是选择测试用例的最简单的方法，它通过在输入域中随机产生测试用例 来测试程序，因其简单有效而被广泛应用。但是随机测试有一定的盲目性，测试 效率不高。自适应随机测试有效地改进了随机测试，它将测试用例较快地均匀分 布在输入域中，从而更快地找到程序的错误。实验表明，自适应随机测试的效率 比随机测试提高约4 0 。但是，现有的许多自适应随机测试算法都是基于经典的 f s c s 算法，其中存在的边界效应极大影响了它们在高维输入域情况下的效率。 为此，我们提出了环型f s c s 算法，把有界输入域转化为环形的无界输入域，彻 底消除了输入域的边界和相应的边界效应。实验表明，环形f s c s 比f s c s 效率有 明显的提升。 解决o r a c l e 问题，蜕变测试是途径之一。蜕变测试不需验证程序运行结果 是否符合预期，而是检查程序运行结果是否满足一定的蜕变关系。因其简单实用， 这种方法已被广泛应用于基于数值型软件、图论计算软件、图像处理软件、面向 对象软件等等很多软件的测试中。这种方法的成功应用需要一个有效的辅助工 具。本文基于蜕变测试和自适应随机测试的研究，我们构建了一个蜕变测试工具 a m t ( a u t o m t ) ，a m t 有如下特点： 1 - 使用自适应随机测试的改进算法一环形f s c s 算法作为原始用例生成策 略。在蜕变测试过程中，生成原始用例是非常重要的一个环节。 4 ，5 ，6 ，7 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 已经在原始测试用例方面做了很多探索。但是在蜕变测试过程中，测试 用例的数目将成倍的增长，并且很多测试用例的测试效果相同，这严重 影响了蜕变测试的效率。a m t 使用自适应随机测试算法产生测试用例， 避免了产生大量测试效果相同的测试用例，降低了生成原始测试用例的 复杂度，从而提高了蜕变测试的效率。 2 支持复合蜕变关系。蜕变关系的研究是蜕变测试的重要方向之一。 4 ，4 5 都提出了选取蜕变关系的一般性原则，但是并未说明如何构造蜕变关系。 4 7 根据命题逻辑，提出了复合蜕变关系，即多条蜕变关系逻辑组合成 复合蜕变关系。a m t 支持复合蜕变关系，提高了蜕变测试的效率。 3 开放的工具。a m t 提供了一定的接口，测试人员可以添加新的原始用例 选择策略。所以，a m t 既可以使用原有测试用例选择算法，也可以使用 新添加的测试用例选择算法。 a m t 已经在提高蜕变测试效率上面做了初步的工作，未来还有许多值得改进 和完善的地方。例如测试程序时，a m t 仍需要测试人员创建一定的环境，比如构 造待测程序承载类等工作，未来可进一步改进以减少测试人员工作量。针对蜕变 关系也有很多值得思考的地方，未来也可以添加拓展到a m t 中。 本文第二章阐述了软件测试基本概念，并指出了软件测试中两个关键问题； 第三章对随机测试的改进算法一自适应随机测试算法做了全面的阐述；蜕变测试 相关知识及研究，包括蜕变测试相关知识，包括原始用例和衍生用例概念，蜕变 关系，蜕变测试过程等内容将在第四章中描述；第五章描述了a m t 的设计思路及 具体实现；第六章将详细阐述环形f s c s 算法；最后，第七章总结全文，并指出 今后需进一步探索的若干方向。 2 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 第二章软件测试概述 软件测试是保证软件质量的重要手段，它贯穿于软件项目的整个生命过程。 软件测试通过在软件项目各个阶段所进行的不同目的及内容的测试活动，来保证 每个阶段的正确性。对整个软件工程来说，软件测试在保证产品质量，合理控制 成本，提高企业竞争力等方面都起着非常重要的作用。本章简要阐述软件测试的 背景，以及一些与软件测试紧密相关的知识。 2 1 软件测试 1 9 8 3 年，i e e e 在软件测试文档标准中对软件测试作了如下定义：软件测试 是使用人工或自动的方式来运行或测试某个系统的过程，其目的在于检验系统是 否满足规定的需求或是比较预期结果与实际结果的差别。 g l e i 面r dj m a y e r s 【2 】认为“测试是发现错误而执行的一个程序或系统的过 程 。 因为软件测试在保证产品质量，合理控制成本，提高企业竞争力等方面都起 着非常重要的作用，所以我们必须考虑选用什么样的方法，怎么安排测试，即采 用何种软件测试技术对待测程序进行测试。软件测试的方法和技术是多种多样 的，软件测试根据是否需要了解系统的内部结构和具体实现算法，分为黑盒测试 和白盒测试。 白盒测试也称为结构测试或逻辑驱动测试。执行白盒测试，测试人员需要知 道产品内部具体的工作过程。白盒测试按照程序内部的结构测试程序，检验程序 中的每条通路是否都能按预定要求正确工作，而无需考虑它的功能。白盒测试的 方法主要有逻辑驱动、基路测试等。 黑盒测试也叫功能测试或数据驱动测试。它是在已知产品所应具有的功能的 情况下，通过测试来检测每个功能是否都能正常使用。在测试时，测试人员把程 序看作一个不能打开的黑盆，在完全不考虑程序内部结构和内部特性的情况下对 程序接口进行测试。它只检查程序功能是否按照需求规格说明书的规定正常使 用，例如程序是否能适当地接收输入数据而产生正确的输出信息，同时保持外部 信息( 如数据库或文件) 的完整性等等。黑盒测试的方法主要有等价类划分、边值 分析、因果图、错误推测、随机测试等。 3 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 在实际测试中，测试人员要根据实际情况选择合适的测试方法和技术，或选 择黑盒测试，或白盒测试，或交叉综合使用多种测试方法。但是不管黑盒测试和 白盒测试，都因工作量太大不可能对待测程序进行“穷举测试 ，即不能将所有 可能的输入都执行一遍，所以软件测试实际上都是不彻底的。当使用有限的测试 用例进行测试时，软件测试就涉及到测试用例集的可靠性问题和o r a c l e 问题。同 时在软件测试中，每一个测试用例的设计都是测试人员辛苦劳动的成果，软件测 试过程要充分利用每一个测试用例，那些已测试过但未引起程序失效的用例并非 是不再有用的，研究表明已测试用例依然包含值得挖掘的“信息”【2 6 】。 2 z 软件测试的关键问题 2 2 1 测试用例集的可靠性问题 测试用例集的可靠性问题是指一般情况下，程序的输入域d 是非常大的， 而测试人员在测试时只从d 中选择一个子集t 来测试程序，但是要设计一个t 集合，使得vt t ，p ( t ) = f ( t ) _ ( vt d ，p ( t ) = f ( t ) ) 是几乎不可能的，这个问 题称为“可靠的测试用例集问题 。即指对于被测程序，很难构造一个可靠的测 试用例集，使得程序的正确性可以由其中的所有测试用例的正确执行来保证。 2 2 2o r a c l e 问题 o r a c l e 问题【聊，也称为“测试神谕 问题。程序测试经常是在输入域中选择 合适的输入作为测试用例，然后执行待测程序，验证它的输出是否是预期输出。 测试人员要测试p ，首先要产生测试用例集t _ t l ，t 2 ，t 3 ，t n ，运行程序得到输出 p ( t 1 ) ，p ( t 2 ) ，p m ) ，然后与期望输出母1 ) ，f l ( t 2 ) ，f ( 蛐比较。如果 p “) = f i t i ) 舻1 ，2 ，3 ，n ) 那么t i 是已测试用例，否则为引发失效用例。测试人员能 判定p ( t i ) = f ( t i ) 的机制，我们称待测程序存在o r a c l e 瞄 2 ”。否则，我们称待测程序 存在o r a c l e 问题。 o r a c l e 问题是广泛存在的，因为o r a c l e 并不是总是可用，有时很难得到o r a c l e ， 抑或待测程序根本就没有o m c l e 。比如p 是计算s i n e 函数的程序。我们知道一些 输入的预期输出，例如s i i ln 3 ，s i l ln 6 ，但是对于大多数的输入如s i n ( 兀1 3 ) ，我 们很难判定其输出的正确性，即存在o r a c l e 问题。 、 4 华东师范大学硕士学位论文基于环形f s c s 的m r r 研究 2 4 随机测试 随机测试属于黑盒测试，是一种特殊的分割测试。它将输入域作为一个分区， 然后在这一分区中等概率地随机选择测试用例对待测程序进行测试。因为随机测 试“随机 选择测试用例，所以它被认为是“碰巧”发现待测程序中的错误。 m y e r s 【2 】曾说随机测试“可能是最糟糕的测试方法”。但是d u r a n 和套n a f o s 【3 】以及 h a m e l e t 和t a y l o r 【1 】的实验改变了这种看法。他们通过一系列实验比较分割测试 和随机测试结果后发现，尽管分割测试发现错误的能力比随机测试强，但是这种 优势微乎其微，可是分割测试还有分区管理上的开销，所以总体来说随机测试更 简单有效。但是，关于分割测试与随机测试测试效率上的讨论仍未停止。随机测 试算法也因其简单有效，已经被应用在很多软件测试工程和工具【8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 1 。 t y c h e n 发现当失效区域为非点状区域时，尽可能让测试用例均匀分布在输 入域中，能提高随机测试的效率。基于这种思想，他提出了对随机测试改进的方 法一自适应随机测试，并实现了固定候选集( f i x e ds i z ec 锄d i d a t e ss e t ，f s c s ) 算 法。基于自适应随机测试思想，有很多不同的自适应随机测试实现方法涌现。虽 然自适应随机测试的效率相比随机测试提高4 0 ，但由于存在边界效应，即自适 应随机测试倾向于在输入域边界产生测试用例，这严重影响了自适应随机测试的 有效性，尤其是在高维输入域的情况下。为解决边界效应，t y c h e n 等人【2 0 j 提出 了静态分区自适应随机测试和动态分区自适应随机测试，d eh a 0h u a n g 等人阱j 提出了虚拟图像法。静态自适应随机测试和动态分区自适应随机测试虽然一定程 度上提高了自适应算法纠错的效率，但二者并未真正地解决边界效应。虚拟图像 法尽管已经解决了边界效应，但是由于有太多次的距离计算，算法开销太大，效 率不高。本文提出的环形f s c s 算法将有边界的输入域化为无界的输入域，不仅 解决了边界效应，而且算法的效率相比自适应随机测试也有较大的提高。有关随 机测试的详细内容还会在本文第三章及第六章中阐述。 2 5 蜕变测试 传统的软件测试技术通过比较测试用例的实际输出和预期输出是否相等来 验证测试程序。这是因为传统测试技术都是基于待测程序存在o r a c l e 的前提下进 行的。基于待测程序存在o r a c l e 的前提下，研究人员研究测试用例选择策略，以 期用尽可能少的测试用例引发程序失效。但是很多情况下，待测程序存在o r a c l e 5 华东师范大学硕士学位论文 基于环形f s c s 的m r 研究 问题，比如复杂高维的数学计算程序。针对o m c l e 问题，t y c h e n 【2 4 2 5 】提出了蜕 变测试，该方法通过检查程序的多个输出结果之间的关系来测试程序，而不需要 构造预期输出，从而有效地解决了o r a c l e 问题。 蜕变测试通过检查程序的多个输出结果之间是否满足一定关系来测试程序。 这里所说的“执行结果之间满足的关系”被称为蜕变关系，是待测程序的属性。 蜕变测试可以使用已测试用例作为原始测试用例，根据蜕变关系产生衍生测试用 例，然后检查原始测试用例和衍生测试用例的输出是否满足蜕变关系。 由以上可知，影响蜕变测试效果的主要因素是原始测试用例和蜕变关系，目 前，基于这两个因素已有很多研究，详细内容将在本文第四章中阐述。 2 6 挖掘已测试用例“信息刀 设计和实现测试用例一般属于劳动密集型活动，所以软件测试尽量要充分利 用测试用例。在软件测试中，大多数测试用例并没有引发待测程序失效，这部分 测试用例被称为已测试用例。在传统测试方法中，已测试用例要么被舍弃【2 】，要 么仅用于回归测试。总之在传统测试方法中，它们往往不再被认为是有用的。 然而已测试用例依然包含有用的“信息，并不是不再有用的。缺陷测试【2 6 】重 用已测试用例，使用已测试用例发现待测程序特定的错误，充分挖掘了已测试用 例的“信息”。但是大多数的测试方法并不是基于缺陷测试，大部分测试用例不 能引发程序任何失效，导致已测试用例的“信息 依然未被挖掘。 随后将阐述的自适应随机测试以及蜕变测试均以不同方式利用已测试用例， 充分挖掘已测试用例所携带的“信息。在自适应随机测试中，一般会存在已测 试用例的集合，然后在候选测试用例中选择与已测试用例距离“最远 的测试用 例为下一个测试用例。蜕变测试则可利用已测试用例，然后根据蜕变关系产生衍 生用例，之后验证它们的输出结果是否符合蜕变关系。 挖掘已测试用例“信息 的工作一般是由软件测试工具自动完成的。在测试 实践中，软件测试工具的开发也是一项重要的工作。 2 7 软件测试工具 软件测试一般是一件繁琐且耗时的工作。有时软件测试过程要进行多轮，随 着软件版本的不断升级，测试工作量越来越大，不少测试工作重复进行。如果这 6 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 些工作全部由人工完成，那么工作的效率势必会收到影响。软件测试工具模拟测 试人员的实际测试过程，模拟测试人员对计算机的操作过程和行为，使得测试过 程自动运行。自动化测试工具不仅能够提高测试质量、提高测试效率、缩短测试 工作时间，而且有能提高测试覆盖率、更好地重现软件缺陷的能力、执行手工测 试不能完成的测试任务、更好地利用资源等优点。 在软件测试实践中，测试人员借助一定的软件测试工具能提高软件测试的效 率。随着软件测试技术的发展，涌现了很多优秀的测试工具，比如l o g l s c o p e 、 p r q a 、d e v p a r n l e r 、b o u n d s c h e c k e 、c o d e i 己e v i e w 等。这些工具极大地方便了测 试人员，提高了软件测试工作的效率。 因为蜕变测试思想简单，所以可构建蜕变测试工具来规范蜕变测试流程，提 高蜕变测试的效率。因此，蜕变测试工具的开发也是蜕变测试的研究方向之一。 本文构建了一个蜕变测试工具w t ( a u t 0 m d ，使用蝴t 可提高蜕变测试的效 率。 7 华东师范大学硕士学位论文基于环形f s c s 的m t 研究 第三章自适应随机测试 t y c h e n 提出的自适应随机测试改进了随机测试，其基本思想是让测试用例 尽可能均匀分布在输入域中。根据测试用例在输入域中“均匀 分布方法的不同， 自适应随机测试很多不同的实现算法。在自适应随机测试的实现算法中，f s c s 是最典型最重要的实现算法。自适应随机测试的效率比随机测试提高约4 0 。但 是，由于自适应随机测试存在边界效应，这影响了自适应测试的有效性。尤其是 在高维输入域的情况下，自适应随机测试的效率急剧下降，甚至不及随机测试。 为进一步提高自适应随机测试的效率，还必须得解决边界效应，很多研究对此进 行了尝试。 3 1 自适应随机测试算法概述 分割测试是软件测试的重要方法，它把程序的输入域分为若干子区域，然后 在子区域中随机选择用例。随机测试把整个输入域当成一个分区，在这个分区中 等概率的随机选择测试用例对待测程序进行测试，是一种特殊的分割测试。随机 测试只有一个分区，所以它相对分割测试减少了分区管理上的开销。因为随机测 试“随机”选择测试用例，所以它被认为是“碰巧 发现待测程序中的错误。 m y e r s 【2 】曾说随机测试“可能是最糟糕的测试方法”。但是，d 1 l r a n 和套i t a f o s 【3 】以 及h a m e l e t 和1 a y l o r e l 】的实验改变了这种看法。他们通过一系列实验比较分割测 试和随机测试结果后发现，尽管分割测试发现错误的能力强于随机测试，但是这 种优势微乎其微。相对于随机测试，分割测试还有分区管理上的开销，所以总体 来说随机测试更简单有效。随机测试算法因其简单有效的优点，已经被应用在很 多软件测试工程和工具中【8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 1 。但是，关于分割测试与随机测试测试 效率上的讨论仍未停止。 在研究随机测试时，t y c h e n 将引发失效的区域分为点状，块状和条状三种 类型【1 6 1 。在二维输入域中，三种失效区域类型表示如图3 1 所示。 8 华东师范大学硕士学位论文基于环形f s c s 的m r r 研究 点状条状块状 图3 1 三种失效区域类型 在失效区域为非点状区域时，t yc h e n 发现尽可能让测试用例均匀分布在输 入域中，能更快的引发程序失效。基于该思想，他提出一种对随机测试改进的测 试方法一自适应随机测试，并实现了固定候选集( f i x e ds i z ec a i l d i d a t e ss e t ，f s c s ) 算法旧。由此可见，自适应随机测试本质上也是随机测试。 f s c s 算法通过在候选用例集合中选择与已测测试用例集合中所有测试用例 最小距离最大的候选测试用例作为下一个测试用例实现测试用例均匀分布。通过 计算候最小距离的最大值，f s c s 将筛选的下一个测试用例与已测测试用例“分 的最开 ，从而达到了输入域中测试用例尽量均匀的目的。虽然f s c s 有效地提 高了随机测试的效率，但是在随着输入域维数的增加时，f s c s 算法的效率会变 差，甚至不及随机测试，我们称之为f s c s 的多维问题。另外每产生一个测试用 例都要比较候选用例集每个候选用例和所有已测试的距离，因而f s c s 算法开销 会比较大。 为解决f s c s 算法开销问题，很多研究利用分割测试思想改进f s c s 算法。 例如m i n 0 r 算法【3 5 1 。m i r r o r 算法结合分割测试将输入域分为相同大小不相交的 子区域，选择一个测试用例，称它所在的区域为源区域，根据一定的映射关系在 每一个剩余区域，即影子区域中随机产生测试用例，然后按一定序列测序程序。 t yc h e n 、ge d d y 等人也结合分割测试的思想，提出动态分割灿玎( a d a p t i v e m d o mt e s t i n gn 啪u 曲d y n a r n i cp a n i t i o 血g ，d p ) 【2 7 1 。该方法将输入域划分为 包含已测测试用例和不包含已测测试用例两类子域，然后从不包含已测测试用例 的子域中选择最大的子域作为下一个测试用例产生的区域。d p 算法虽然降低 f s c s 开销，但是降低了f s c s 的检错能力，t yc h e n 、d eh a 0h 啪g 等人提出 了有效改进d p 算法的i p ( a d a p t i v e 旺1 d o mt e s t i l l g1 1 哟u g h i t e r a t i v e p 枷t i o n i n g ) 【2 引。i p 算法详细描述见下文。以上三种算法不同程度的降低了f s c s 9 华东师范大学硕士学位论文 基于环形f s c s 的m t 研究 的的开销，但是上述算法由于未改变f s c s 策略，所以仍然存在a r t 的多维问 题。 其他自适应随机测试实现算法，例如i 硼【2 9 】、b a l a n c i l l g 【3 0 1 、c gc o n s t r a i n t 【3 i 】 等算法对f s c s 的开销问题都有所改进。其中m i 仃。卜触玎和江的有效性最好， 仅次于f s c s ( 相差5 1 0 ) ，c gc o n s 仃a i n t 算法的有效性最差，仅比随机测试 略有提高。与f s c s 相同，这些算法同样存在m 汀的多维问题【3 2 1 。i d i f s c s ( 各 维独立的递增f s c s ) 【4 6 】算法尝试解决触汀的多维问题，它利用一维f s c s 算法 分批产生各维上的若干个“一维测试用例 ，然后用这些一维测试用例随机地组 合成最终的测试用例( 目标测试用例) 。该算法虽然提高了自适应算法在高维输 入域中的效率，但是算法并不是很稳定。【3 3 】研究发现触玎在多维条件下效率差 的主要原因是因其存在边界效应。为进一步提高自适应随机算法的效率，就必须 解决边界效应。 自适应随机测试的基本思想是让测试用例尽可能均匀地分布在输入域中。对 测试用例采取不同的均匀分布策略，有着很多不同的自适应随机测实现方法。不 同自适应随机测试实现方法中测试用例“均匀 程度不同，因而有着不同的检错 能力。下面将描述几种自适应随机测试实现算法，着重阐述它们如何使得测试用 例“均匀 分布。由于f s c s 是自适应随机测试的经典实现，本文涉及的环形f s c s 研究也是基于f s c s ，所以下面重点阐述f s c s 算法。 3 2f s c s 算法 f s c s ( f i x e ds i z ec 龇1 d i d a t es e tv e r s i o no f t l l ea d a p t i v er 强d o m1 e s t 崦) 1 7 】是 自适应随机测试重要的实现算法。它分布测试用例的策略是通过对候选测试用例 和已测测试用例之间距离的计算，选择与所有已测测试用例距离最大的候选测试 用例作为下一个测试用例。在f s c s 算法中保存两个集合：e 集合和c 集合。前者 包含n 个已测试过但未引发程序失效用例的集合 e l ，e 2 ，e 3 ，e n ，而后者包含k 爪 随机产生的候选测试用例的集合 c l ，c 2 ，c 3 ，c k ) ( 在算法的过程中k 值保持不 变，一般k 取1 0 ) 。当e 为空时，随机产生初始测试用例e ，然后测试程序，若未引 发程序失效则将其加入e 中，下一个测试用例将从c 中选择产生，该测试用例与e 中离它最近的测试用例的距离大于任何其他候选测试用例与它们在e 中对应的最 近的测试用例间的距离。其算法如下： 华东师范大学硕士学位论文基于环形f s c s 的m r r 研究 图3 2 f s c s 算法 实验 1 7 】证明，相比随机测试，f s c s 的f m e a s u r e 较小，即f s c s 使用较少 的测试用例找到程序的第一个错误。所以f s c s 提高了随机测试检错的效率。 3 - 3 其他自适应随机测试算法 3 3 1i p i p 【l8 】算法“均匀”测试用例的方法是使新产生的测试用例落在没有已测试用 例的区域。i p 算法根据已测测试用例集合将输入域均分为一系列测试区域，并将 这些测试区域分为三类：包含测试用例区域、临包含测试用例区域和候选测试区 域。包含测试用例区域为存在已测试用例的区域；与包含测试用例区域相邻的区 域称为临包含测试用例区域；剩下的区域为候选测试区域。下面我们就i p 触盯 为例阐述i p 思想。 1 l 华东师范大学硕士学位论文 基于环形f s c s 的m t 研究 图3 3 i p - 甜玎算法 实验【2 8 】表明，在三种失效区域类型下，i p 的有效性在2 维和3 维的情况下略 优于f s c s ，而且算法效率也比f s c s 有所提高。 3 3 2i d i f s c s 各维独立的递增f s c s ( i n c r e m e n t a ld i m e n s i o ni n d e p e n d e mf s c s ，i d i f s c s ) 算法【4 6 】基于这样的想法提出：在多维的情况下，若能使m 盯算法所产生的多维 测试用例较早、较多地出现在一维失效区域的组合中，则有可能使用较少测试用 例找到第一个错误。 i d i f s c s 算法是利用一维f s c s 算法分批产生各维上的若干个“一维测试用 例”，然后用这些一维测试用例随机地组合成最终的测试用例( 目标测试用例) 。 在i d i f s c s 中，一维测试用例是逐步产生、逐渐累积的，并且一维