（计算机应用技术专业论文）fscs自适应随机测试算法的边界效应及运行效率研究.pdf

d i s s e r t a t i o no fu n i v e r s i t yt e a c h e ro n j o b f o rm a s t e rd e g r e e ，2 010 l i i ii ii iii ii iiii ii ii il y 18 4 710 9 s c h o o lc o d e ：10 2 6 9 s t u d e n tn o ：9 1 0 6 1 2 0 1 1 0 4 e a stc hinan orm al u nive r slty t h er e s e a r c ho f b o u n d a r ye f f e c t a n d o p e r a t i o n a lc o s t si nf s c s d e p a r t m e n t ：c o m p u t e rs c i e n c ea n dt e c h n o l o g y m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y _ r e s e a r c hd i r e c t i o n ： s q 佥型垒盟垦垒g i 卫曼金亟堕g a d v i s o r ： m a s t e rc a n d i d a t e ： 笪! 墨呈q 曼i 堑曼! q 圣h 垒坠g i q 坠g 堡i 坠 o c t o b e r ，2 0 1 0 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文耳s c 罗自适应随机测试算法的边界效应及 运行效率研究，是在华东师范大学攻读硕，士博士( 请勾选) 学位期间，在导师 的指导下进行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本 论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献 的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名： ( f s 范大学攻 日期p 卢姊 华东师范大学学位论文著作权使用声明 效率研究系本人在华东师 ( 请勾选) 学位论文，本论 文的研究成果归华东师范大学所有。本人同意华东师范大学根据相关规定保留和 使用此学位论文，并向主管部门和相关机构如国家图书馆、中信所和“知网送 交学位论文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数据库 被查阅、借阅；同意学校将学位论文加入全国博士、硕士学位论文共建单位数据 库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式 合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文串， 于年月日解密，解密后适用上述授权。 ) 2 不保密，适用上述授权。 导师签名 “涉密”学位论文应是已经华东师范大学学位评定委员 a 步埘芝 v 。篷| ，h 、宋h 位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未 经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文， 均适用上述授权) 。 王里丝硕士学位论文答辩委员会成员名单 姓名职称单位备注 陈强璋教授上海商学院主席 顾君忠教授华东师大计算机系 王新伟副教授华东师大计算机系 孙强副教授华东师大计算机系 吴文娟高工华东师大计算机系 华东师范大学硕士学位论文摘要 摘要 自适应随机测试( a d a p t i v er a n d o mt e s t i n g ，a r t ) 是近几年发展起来的 一种黑盒测试方法，固定候选集的a r t 算法( f i x e ds i z ec a n d i d a t e ss e tv e r s i o n o fa r t ，f s c s ) 是实现a r t 算法诸多方法中最为经典，最为普遍认可的算法。f s c s 在发现程序错误的能力上比随机测试( r a n d o mt e s t i n g ，r t ) 有显著的提高，但 是由于f s c s 输入域的有界性导致了f s c s 的边界效应现象。同时由于f s c s 算法 在选择生成新的测试用例时，需要大量的距离计算，尤其是当失效率较小和维数 较大的情况下，执行算法的庞大开销达到令人难以忍受的程度，严重影响了测试 工作的效率。 本文对f s c s 及其相关的算法作了深入分析，并查阅了大量文献资料，在此 基础上，借助于环的思想提出了环形f s c s ( c i r c l e df s c s ，c - f s c s ) ，把有边界 的输入域变换为无边界的环，从而彻底消除了输入域的边界，从根本上解决了 f s c s 算法的边界效应。针对f s c s 算法开销较大的问题，本文进一步提出了改进 的c - f s c s ( i m p r o v e dc - f s c s ，i c - f s c s ) ，直接消减掉绝大部分不必要的距离计 算，从而极大的提高了算法的运行效率。 此外，本文还将上述方法应用于基于限制区域的随机测试算法( r e s t r i c t e d r a n d o mt e s t i n g ，r r t ) ，提出了环形r r t 算法( c i r c l e dr r t ，c - r r t ) 和其改进 算法i c - r r t ( i m p r o v e dc - r r t ) ，解决了r r t 算法中同样存在的边界效应和运算 开销过大的问题。 为了验证所提出的算法的有效性，我们做了大量的实验，实验结果表明我们 所提出的算法在测试效果和运行开销上的改进是非常显著的。 关键词：软件测试，随机测试，自适应随机测试，边界效应，运行效率 华东师范大学硕士学位论文a b s t r a c t a b s t r a c t a d a p t i v er a n d o mt e s t i n g ( a r t ) i sa k i n do fb l a c kb o xt e s t i n gm e t h o dw h i c h d e v e l o p e di nr e c e n ty e a r s f i x e ds i z ec a n d i d a t e ss e tv e r s i o no fa r t ( f s c s ) i s o n eo f t h em o s tc l a s s i ca n dm o s tw i d e l ya c c e p t e da l g o r i t h mt oi m p l e m e n tt h ea r t a l g o r i t h m t h ea b i l i t yo ft h ef s c st of i n db u g si n c r e a s e ds i g n i f i c a n t l yc o m p a r e dw i t i lt h e r a n d o mt e s t i n g ( r t ) h o w e v e r , f o rf s c s ，d u et ot h el i m i t a t i o no ft h ei n p u tf i e l dh a s l e dt ot h ep h e n o m e n o no fb o u n d a r ye f f e c t i nt h ec h o i c eo ft h ea r t a l g o r i t h ma l s o g e n e r a t e sn e wt e s tc a s ei tn e e dal o to fd i s t a n c ec a l c u l a t i o n , e s p e c i a l l yw h e nt h e f a i l u r er a t eo fs m a l la n dl a r g ed i m e n s i o no ft h ec a s e ，t h eh u g ec o s to fr u n n i n gt h e a l g o r i t h mh a sr e a c h e dav e r yd i f f i c u l ti n t o l e r a b l el e v e l ，w h i c hs e r i o u s l ya f f e c tt h e e f f i c i e n c yo ft h et e s t i n g b a s e do nt h ef s c si n - d e p t ha n a l y s i s ，a n da c c e s st oal a r g en u m b e ro f d o c u m e n t s ，t h i sp a p e rp u tf o r w a r dt h ec i r c l e df s c s ( r e f e r r e dt oa sc f s c s ) ，w h i c h t r a n s f e rt h e i n p u tf i e l d 晰t l lb o u n d a r yt oab o u n d a r y - f l e ec i r c l e t h u s ，s o l v e sa f u n d a m e n t a lp r o b l e mo fb o u n d a r ye f f e c ta l g o r i t h m s t os o l v et h ef s c s sp r o b l e mo f h u g ec o s t ，t h i sp a p e rp r o p o s e da ni m p r o v e dc - f s c s ( r e f e r r e dt oa st h ei c - f s c s ) ，t h e a l g o r i t h md i r e c t l yc u to u tm o s to ft h eu n n e c e s s a r yc o m p u t a t i o n a lo v e r h e a d ，w h i c h g r e a t l yf s c si n c r e a s e dl e v e lo fo p e r a t i n ge f f i c i e n c y i na d d i t i o n ，t h i sp a p e ra p p l i e st h i sm e t h o dt or e s t r i c t e dr a n d o mt e s t i n g ( r r t ) ， p r o p o s e dt h ec i r c l e dr r t ( c - - r r t ) a l g o r i t h ma n di m p r o v e dc r r ta l g o r i t h mw h i c h s o l v et h ep r o b l e mo fh u g ec o s ta n dt h eb o u n d a r ye f f e c tw h i c ha l s oe x i t si nr r t a l g o r i t h m i no r d e rt ov e r i f yt h ev a l i d i t yo ft h ep r o p o s e da l g o r i t h m ，w em a d eal a r g e n u m b e ro fe x p e r i m e n t s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h i si m p r o v e m e n ti sv e r y e 航c t i v e k e y w o r d s ：s o f t 硝。i 之et e s t i n g ，r a n d o mt e s t i n g ，a d a p t i v er a n d o m t e s t i n g ，b o u n d a r ye f f e c t ，0 p e ra t i o n a lc o s t s ，f s c s ， r r t 华东师范大学硕士学位论文目录 目录 第一章绪论1 第二章自适应随机测试概述3 2 1 软件测试概述3 2 1 1 测试过程4 2 1 2 测试用例选择5 2 1 3 测试技术7 2 1 4 测试方法的度量9 2 2 自适应随机测试10 2 2 1随机测试和分割测试1o 2 2 2 失效域的类型11 2 2 3自适应随机测试13 2 2 4 算法有效性的度量13 2 2 5 自适应随机测试的研究现状15 第三章经典f s c s 算法的分析19 3 1f s c s 算法19 3 2 实验结果及其分析2 1 第四章环形f s c s 算法及其改进2 6 4 1c - f s c s 算法2 6 4 2ic - f s c s 算法2 8 4 3 实验结果及分析3 0 第五章环形r r t 算法及其改进3 4 5 1 r r t 算法3 4 5 2c - r r t 算法3 7 5 3i c - r r t 算法3 7 第六章总结与展望4 1 附录4 2 参考文献4 3 致谢4 7 i h 华东师范大学硕士学位论文 第_ 章绪论 第一章绪论 在信息时代，各种各样的软件已经深入到我们生活和工作中的各个部分， 例如计算机、复印机、电话、电视、冰箱等电子产品，都需要有相关的控制软件 来支持相应的操作，这些产品甚至已经成为人们生活和工作中的必需品。而在自 动控制领域，控制软件的作用更是举足轻重，没有这些软件一切都无从谈起。在 软件得到广泛应用的同时，软件的有效性更是显得至关重要，甚至容不得半点差 错。比如银行、航空管制、火车调度、飞机操纵、汽车控制等相关的软件系统必 须是时刻、永久、可靠地运行的。这就需要加大软件测试的力度，保证开发出来 的软件能够正确，健壮地运行。软件测试在软件行业中已占据到举足轻重的地位， 统计显示在很多软件开发公司中软件测试和错误修复在整个软件项目投入中已 占到4 0 以上的比例。 目前在软件测试领域中使用的技术有很多，总的来说最常见的分类有白盒 测试、黑盒测试和灰盒测试。不管使用哪种测试方法，对软件整个输入域进行穷 尽测试是不现实的，所以一般只能在输入域的一些有代表性的子集中选择测试用 例进行测试。从而如何组织，设计测试用例，如何让生成的测试用例能够尽可能 代表整个输入域，如何利用最少的测试用例发现最多的程序错误等问题变得尤为 重要。在黑盒测试技术中，随机测试和分割测试是两种经典的生成测试用例的算 法，随机测试是在输入域中随机生成测试用例，而分割测试则是按照指定的策略 在输入域中选取测试用例样本。后来很多新的研究都是依据这两种思想，或者就 是这两种算法的改进。而随机产生测试用例通常被认为是简单有效并且在直觉上 很具有吸引力的一种技术n 1 。 鉴于随机测试发现错误的能力不高，分割测试比随机测试略好，但却引入 了子域划分等复杂的操作而导致开销过大，都不能很好的提高算法发现错误的能 力，t y c h e n 等人对随机测试算法进行改进提出了a r t 算法，并通过f s c s 算法 具体实现。f s c s 大大提高了算法发现错误的能力，但是由于其引入了大量的距 离计算而导致了算法的巨大开销，同时f s c s 算法在选择测试用例时会因为输入 域的边界特性而产生边界效应现象。本论文主要就f s c s 算法产生的边界效应问 题和算法引入的庞大运算开销提出合理的解决方法并通过实验证明解决方法的 有效性。 华东师范大学硕士学位论文第一章绪论 本文第2 章对软件测试做了比较全面的阐述，着重描述了与a r t 有紧密联 系的黑盒测试，分析了a r t 算法的研究状况以及存在的一些问题；第3 章对原始 算法f s c s 进行了深入研究，做了大量的实验，并对实验结果作了详尽的分析， 在此基础上指出了f s c s 算法的边界效应和运行效率低下的问题；第4 章描述了 c f s c s 算法和i c - f s c s 算法，彻底解决了f s c s 的边界效应，实验结果表明 i c f s c s 的效率较之f s c s 有显著的提高：第5 章描述了c - r r t 算法和i c - r r t 算法，把c - f s c s 算法和i c - f s c s 算法的思想应用于r r t 算法，类似地解决了基 本r r t 算法中同样存在的边界效应和运行效率问题；第6 章对全文作了总结，并 提出了进一步研究的方向。 2 华东师范大学硕士学位论文第二章自适应随机测试概述 第二章自适应随机测试概述 软件测试是软件开发过程中的重要环节，是保证软件产品质量和可靠性的 关键步骤。软件测试不仅是为了发现软件产品中的错误，同时也是对软件开发成 果的一种确认。软件测试方法按照不同的标准有很多不同的分类方式，本文所涉 及的是动态的黑盒测试方法。 随机测试( r t ) 是黑盒测试中的经典算法，具有简单，有效，成本低廉的 特点，在软件行业中得到非常广泛的应用，但随机测试由于其生成测试用例的盲 目性决定了该算法发现程序错误的能力不是很理想。后来t y c h e n 等又根据引 发程序失效的测试用例的分布特点提出了基于随机测试的改进算法，被称为自适 应随机测试( a r t ) ，它根据已经用来测试程序但并没有引发程序失效的测试用例 信息按照一定的策略选择新的测试用例。a r t 较r t 有比较显著的发现程序错误 的能力，它也由此成为了黑盒测试的又一个经典算法，但是由于a r t 引入了大量 的运算开销，从而减低了程序运行的效率，同时由于输入域边界外面不存在测试 用例的原因a r t 算法在选择测试用例时会产生所谓的边界效应。为此后来有很多 类似的对a r t 改进的算法涌现出来，虽然比a r t 算法有所提高，但总体上来说效 果并不理想。 2 1 软件测试概述 随着社会信息化程度的日益提高，社会各行业对计算机的需求与日俱增， 相应的所需要的相关软件产品的种类和数量更是成倍增加。同时由于对软件产品 的功能要求越来越多，从而使所需软件系统变得越发庞大和复杂。这将为软件产 业带来莫大的机遇和挑战，不仅要加快开发进度满足广大客户的需求，更要为产 品的质量把关。质量不好的软件产品不仅会增加软件公司后期维护的巨额费用， 甚至会给用户带来灾难( 比如金融，航天等领域) ，这就把软件测试工作推到了 至关重要的位置。 保证软件产品正确的一个必要条件是软件开发的任何阶段( 需求，设计， 编码，测试等) 都能及时发现并修复本阶段的缺陷，而且修复缺陷的难度和所需 花费随着检测出缺陷时间的拖延而呈指数级增加，所以尽可能早的检测到并修复 软件的缺陷是有利于保证软件产品质量并符合软件公司利益的乜1 。事实上对软件 3 华东师范大学硕士学位论文第二章自适应随机测试概述 的测试工作贯穿于软件产品的整个生命周期( 包括用户对软件的使用过程) ，但 也不能保证软件产品是1 0 0 没有缺陷的口3 。所以软件测试工作是一项必要而且繁 琐的长期工作。 1 9 8 3 年，i e e e 对软件测试做出了如下准确定义：软件测试是使用人工或者 自动的方式来运行或者测定某个系统的过程，其目的是检验系统是否满足需求分 析中的规定或者是弄清期望的结果和实际结果之间的差异。 2 1 1 测试过程 软件测试贯穿于软件的整个生命周期，包括软件开发过程和软件交付用户 后的使用过程，前一阶段由程序员和专业的软件测试人员对软件进行有针对性的 全面的系统的测试，后一阶段则通过用户在使用软件产品过程中去发现程序的错 误和不足。本文所说的软件测试针对前一阶段。习惯上人们一般把软件测试过程 分为模块测试、集成测试、确认测试和系统测试等阶段h 3i s o 如图2 i 所示： 图2 1 软件测试过程 模块测试也叫单元测试，是在软件开发过程中对程序进行的最小单位的测 试，是对程序模块正确性进行验证的测试工作，一般由程序员自己完成测试。测 试的方法一般在单个模块编码完成时就可以开始进行，用于检验每个模块能否单 独工作，从而发现模块编码或设计的问题。在模块测试阶段由于程序代码和功能 相对比较简单，发现并修复错误比较容易，成本也很低，而到软件开发的后期， 即使花费再多的时间和精力都未必能够发现前期遗留下来的错误，即便发现，也 需要为修复错误付出更大的代价。所以合理完善的模块测试将为接下来的集成测 试的顺利进行提供可靠的保证。 4 华东师范大学硕士学位论文第二章自适应随机测试概述 集成测试是在模块测试完成之后，将多个模块按照概要设计规格说明的要 求整合起来进行的联合测试，主要用于检验模块之间接口工作是否正常，各模块 之间的数据传输有无异常，各模块的功能是否达到需求规约中的要求。一些在模 块测试中没有检测出来的问题，很可能在集成测试中就出现了。集成测试常用的 方法有：自底向上集成测试、核心系统先行集成测试和高频集成测试。其中自底 向上集成测试是最基本、最常用的方法，它从程序模块结构中最底层的模块开始 组装和测试；核心系统先行集成测试则是先对核心部件进行集成测试，然后再按 照外围部件的重要程度依次逐个集成到核心系统中；高频集成测试与软件开发过 程同步，每隔一段时间就需要对开发团队现有的代码进行一次集成测试。 确认测试也称验收测试，是按照需求规约说明书中的要求，采用一系列的 黑盒测试技术进行功能验证的测试，目的是检验软件产品的功能和使用特征是否 满足客户的预期要求。一般先由公司组织一定的人员进行尽可能逼真的模拟用户 操作的测试，也叫q 测试，开发人员和测试员会在现场但不参与测试。经过q 测 试后修正过的软件产品称为b 版本，然后进行的测试称为b 测试，开发人员和测 试员一般不在现场，一般由公司组织一定的用户在现实工作环境中使用该版本的 软件产品，把使用过程中发现的问题反馈给软件公司，并提出批评或建议，再由 公司进行完善处理。 系统测试则是将经过确认测试的软件产品与硬件等其他各种元素综合起 来，再次进行各种集成测试和确认测试。包括恢复测试、安全测试、强度测试、 性能测试和安装测试等呻3 。恢复测试主要是判断软件产品在意外因素导致的软件 系统出现异常或崩溃后，对软件系统中有效数据的恢复能力或者保障能力，比如 数据库系统，操作系统等的恢复机制。安全测试主要针对软件的安全检查系统是 否有效，是否存在一定的可被利用的安全漏洞，比如国家情报系统、金融系统、 电子商务网站等机构所使用的金融交易系统如果存在安全隐患并被人利用，后果 是可想而知的。性能测试主要针对软件在一定负载和环境下的响应时间和运行效 率。安装测试主要针对软件在安装过程中对操作系统环境的配置和处理情况，要 保证软件的安装不影响操作系统和其他软件的正常使用，软件卸载后能够把系统 配置恢复到安装前的状态，并删除和本软件相关的文件。 2 1 2 测试用例选择 在软件测试中的每个测试阶段都包括制定测试计划，编写测试大纲，产生 华东师范大学硕士学位论文第二章自适应随机测试概述 测试用例，执行测试用例，形成测试报告几项活动。测试结束后，要对测试过程 和测试结果进行分析整理，形成详尽的测试报告，为纠正软件存在的问题提供参 考依据。 在这些活动中，如何生成测试用例是关键，因为所产生的测试用例的质量 将会对最终的测试效果产生重大影响。好的测试用例应该具备尽可能大的测试覆 盖率、具有比较强的代表性、具有较低的冗余度等特点。产生测试用例的方法按 照是否针对程序内部结构通常分为白盒测试方法和黑盒测试方法。白盒测试方法 是根据程序的结构、实现代码来设计产生测试用例。而黑盒测试不涉及到程序的 内部结构和编码，它根据程序的需求规约来设计测试用例，它不管程序具体实现 细节，它只关心程序的功能，关心程序的输入和输出。 在测试活动中，通常是多种测试方法同时使用，比如在程序员每天完成一 定的程序代码时进行的阶段性测试或者进行模块测试时，主要由编程人员或者专 业的程序测试人员利用白盒测试的方法产生测试用例并进行测试，同时用黑盒测 试方法作为必要的补充。而对于其他一般的测试人员，或者是第三方测试公司的 测试原来说，主要采用的测试技术就是黑盒测试，他们主要根据软件需求规约说 明书产生测试用例，对软件的各项功能进行详尽的功能测试。而在集成测试和其 后阶段的测试过程中，主要以黑盒测试为主。毕竟白盒测试仅限于特定的专业测 试人员和程序员使用，大多数人主要还是使用黑盒测试的方法，所以黑盒测试当 之无愧成为最常用的测试方法，而且黑盒测试方法也符合用户的使用模式。所以 本文也主要是讨论黑盒测试方法，其中最常用的有等价类划分、边界值分析、因 果图、随机测试、分割测试、自适应随机测试等。 等价类划分法是黑盒测试中最常见也是应用最广泛的一种方法，它把程序 的输入域划分成若干子集，然后从每个子集中选取一定的具有代表性的样本数据 作为测试用例，当然这种方法适合一些简单的，没有很多复杂关联关系的输入。 等价类又分为有效等价类和无效等价类，利用有效等价类生成的测试用力用于检 测程序是否实现了需求规约说明中规定的功能和性能，而无效等价类中生成的测 试用力则用来测试程序是否会产生异常或是程序是否采用了一定的方法处理了 这种可能的异常。 边界值分析法是黑盒测试中的另一种常用的方法，是对等价类划分的有益 补充。根据测试经验可知，输入域的边界区域时最容易出现问题的地方，而等价 类的边界及其附近正是边界值分析法产生测试用例的地方。 6 华东师范大学硕士学位论文第二章自适应随机测试概述 而如果输入条件比较复杂，需要考虑各种条件的组合情况，这就需要用到 黑盒测试中的另一种方法因果图法，该方法用于描述各种条件的组合情况，最终 生成判定表。 相对前面这几种生成测试用例的方法，随机测试方法则更简单、有效，它 直接针对整个输入域随机的产生测试用例，随机测试可以避免在选择测试用例时 因为人为的干预而出现偏见，但很明显的一个问题是，需要生成多少测试用例才 算是达到满意的覆盖率。不过采用随机测试方法让计算机自动完成测试却是不错 的做法。另外随机测试之所以成为经典与其在学术界的影响力有很大的关系。 分割测试是黑盒测试的另一个经典算法，它按照一定的标准把输入域划分 成若干子域，然后从各子域中选取一定的样本数据作为测试用例。该算法比随机 测试略好，但是对子域的划分一笔不小的开销。其实，等价类划分就是其中的一 种分割测试算法。 自适应随机测试是在随机测试的基础上改进后的算法，它在随机生成测试 用例的过程中增加了对测试用例的筛选机制，从而使最终产生的测试用例更快速 均匀地分布在整个输入域，从而提高算法发现错误的能力。自适应随机测试算法 一出现便引起了了学术界和工业界的高度重视，其中f s c s 是具体实现该算法的 一个经典算法，很多基于f s c s 的改进算法也很快涌现出来，这一些算法都可归 类为基于距离的自适应随机测试算法，这些算法有两个共同的不足之处，一个是 由于输入域的边界产生的边界效应现象，另一个就是由于选择测试用例过程中引 入了大量的距离计算造成的算法开销问题。 2 1 3 测试技术 软件测试技术是随着软件产业的不断发展壮大而逐步发展起来的一系列针 对软件产品的测试方法。在介绍测试技术之前，我们先了解一下软件开发和软件 测试的发展历史。 第一阶段是6 0 年代及其以前，软件规模小，功能简单，复杂度低，软件开 发过程也没有特定的划分和规范，唯一的软件测试工作也就是程序员对程序的调 试过程，当然也不需要专业的软件测试员和第三方的测试公司。 第二阶段是7 0 年代，尽管此时开发的软件仍然简单，但软件行业已经开始 考虑软件开发的流程，并提出软件工程的概念，对软件的测试工作仅限于功能验 证和查找错误。这一阶段出现了由新进入软件行业的一部份员工组成的专门进行 7 华东师范大学硕士学位论文第二章自适应随机测试概述 软件测试的人员。 第三阶段是8 0 年代及其以后，软件和信息技术行业取得了较大的发展，软 件开发过程也相对规范化，形成了各种复杂而精密的流程和管理方法，软件的质 量也得到了足够的重视，软件测试也有了行业标准( i e e e a n s i ) 。此时软件测试 已经成为一个专业，具有专门的测试方法和技术，需要由有经验的、专业的软件 测试专家来担当。 其实在整个软件开发行业发展的过程中，测试和开发工作是密不可分的， 只有让测试人员参加软件的需求分析、功能设计，同时要和软件开发人员进行更 多更深入的合作，软件测试工作才能有更强的针对性，才能取得更好的成效。而 软件测试已经不只是功能验证和查找错误那么简单，它已经发展成为一种科学， 已经形成一整套全面的测试技术并开发有配套的测试工具。 根据是否需要运行被测试程序可把软件测试分为静态测试和动态测试。在 静态测试过程中，不需要运行被测程序，只用通过阅读的方式分析检查程序代码 的语法、变量、逻辑结构、程序接口等去查找程序中可能存在的错误或者是对程 序代码进行评估，可以完全凭借人工进行，也可以借助一定的软件工具。静态测 试还包括对需求规约说明书、软件设计说明书、程序流程图等材料的分析检查。 在实际使用中通过代码检查能快速找到程序绝大部分的逻辑错误和编码错误，这 种方法比动态测试效率更高，只是代码检查需要花费很多的时间，而且需要测试 人员具有一定的知识和经验。静态测试包括代码检查、静态结构分析、代码质量 度量等技术。代码检查主要检查代码和设计是否一致，代码的编写是否遵循行业 的标准并具有很好的可读性，代码的逻辑表达是否正确，结构是否合理等方面的 问题；静态结构分析主要是以图形的方式描述程序的逻辑结构，比如，类图、程 序控制流程图、函数调用关系图等。 动态测试则需要提供用来测试的样本数据，通过运行被测试的程序，把运 行结果和预期的结果进行比较来判断程序的正确性。动态测试包括生成用来测试 程序的样本数据，即测试用例。如何生成测试用例是动态测试的关键所在，它直 接决定着动态测试的效果。其中测试用例包括用来输入的数据和预期的程序输出 的结果刀。 动态测试又可以根据设计测试用例时是否需要了解程序的内部结构和具体 实现细节分为白盒测试、黑盒测试和灰盒测试。白盒测试又叫结构性测试或者基 于程序的测试，是通过考察程序内部结构和程序路径特征设计测试用例，包括控 8 华东师范大学硕士学位论文第二章自适应随机测试概述 制流测试、数据流测试、域测试、符号执行、变异测试等技术。其中控制流测试 包括语句覆盖、分支覆盖、条件覆盖、判定和条件覆盖、路径覆盖等，数据流测 试包括全定值覆盖、全引用覆盖、全定值引用覆盖等。参与测试者一般为软件开 发人员或对程序结构和各部分功能非常了解的程序员。黑盒测试也称功能测试或 者基于规约说明的测试，它不需要测试人员了解程序的内部结构，也不需要了解 程序的实现语言，而是根据程序的需求规约或者程序的输入和输出关系来设计测 试用例。黑盒测试技术包括等价类划分、边界值分析、因果图、决策表、事务流 测试、状态测试、随机测试、分割测试、自适应随机测试等技术。灰盒测试技术 是把白盒测试技术和黑盒测试技术结合起来设计测试用例。 根据测试过程是由人工或是计算机完成的来看，软件测试又可分为人工测 试( 手工测试) 和自动化测试。如静态测试中的代码检查，静态结构分析等都属 于人工测试，而利用测试工具，把测试任务交给计算机由测试软件独自测试并完 成测试分析的测试，我们成为自动化测试。自动化测试实质上就是计算机模拟手 工测试，根据测试过程中是否需要人的干预又分为半自动测试和完全自动测试。 自动化测试是软件测试的一个方向，是大势所趋。首先是速度快，自动化测试执 行测试用例的速度可能是人工的i 0 0 倍，1 0 0 0 倍甚至更快；其次是提高测试的 整体效率，当测试员把测试任务交给计算机后，测试员就解放了，就可以干其他 计算机干不了的事情了；再次自动化测试的准确度有保障，计算机不会因为疲倦 和注意力不集中而导致失误，它总能一如既往的做重复的事情；另外计算机可以 不用休息，坚持不懈地做测试口1 。当然计算机不是万能的，有些工作还必须要人 工去做，但使用计算机自动化辅助测试还是非常有必要的。 所有这些测试技术几乎都在围绕一个共同的话题，即如何生成测试用例的 问题，正如2 1 2 中所说的，如何产生测试用例是软件测试工作中的关键，而所 有这些测试技术也是围绕如何生成好的测试用例展开。我们在本文中主要针对动 态的黑盒测试技术中自适应随机测试的f s c s 进行研究。 2 1 4 测试方法的度量 衡量一个测试算法的优劣通常需要有一定的度量方法，人们对测试算法有 效性的度量方法常用的有p - m e a s u r e ，e - m e a s u r e 和f - m e a s u r e 。p - m e a s u r e 是 指对于测试用例集合，找到至少一个导致程序失效的测试用例的概率，e - m e a s u r e 是指对于一个测试用例集合，所期望找到的导致程序失效的测试用例的数量。后 9 华东师范大学硕士学位论文第二章自适应随机测试概述 来c h e n 等人提出了一个新的有效性度量方法f - m e a s u r e ，它表示找到第一个导 致程序失效的测试用例时所使用的测试用例的数量。作为评价算法有效性的标 准，p - m e a s u r e 值越大或者e - m e a s u r e 值越大则说明算法的有效性越好，而 f - m e a s u r e 值越小说明算法的有效性越好。和前两个度量方法相比，f - m e a s u r e 所提供的测试结果更能直观自然的显示出算法效率的高低，而且，在具体实践中 当一个测试用例导致程序失效时，测试也就停止了。所以不论从直观感受还是从 实用的观点来看，f - m e a s u r e 都比前两种度量方法更具有吸引力。本文和a r t 算 法一样采用f - m e a s u r e 对算法进行评估。 2 2 自适应随机测试 自适应随机测试是黑盒测试中的一种经典算法，自诞生之日起就引起了学术 界和工业界的强烈关注，f s c s 则是最早实现自适应随机测试的算法之一，也是 最经典的一个，至今依然是学术界研究的热点。基于f s c s 算法的不足之处，学 术界提出了很多改进的算法，试图解决的f s c s 存在的边界效应和算法开销问题 的不足，但也没有最终把这两个问题彻底解决。本节主要介绍f s c s 相关的一些 著名算法，以及对算法研究过程中用于统计数据的一些方法。 2 2 1 随机测试和分割测试 随机测试( r a n d o mt e s t i n g ，简称r t ) 是黑盒测试中的一种经典的软件测 试方法，它从程序的输入域中机会均等地随机选择测试用例用来测试程序1 。由 于随机测试简单有效，成本低，容易实现，所以它很快就在软件行业得到广泛应 用。但是由于其随机产生测试用例的盲目性，随机测试发现程序错误的效率并不 高。事实上随机测试在科研上的研究价值远远高于它在行业中的应用价值，因而 它吸引着广大学者对其孜孜不倦的研究，也因此又有很多改进的，或全新优秀算 法涌现出来。 分割测试( p a r t i t i o nt e s t i n g ，简称p t ) 也是一种重要的软件测试技术， 它把程序的输入域分成若干子域，然后从每个子域中选取样本用例对程序进行测 试，其中对子域的分割在很大程度上决定着分割测试的效果呻1 。d u r a n 和n t a f o s 在 1 0 中的实验以及h a m l e t 和t a y l o r 在 1 1 中的实验均发现，分割测试比随 机测试在发现程序错误能力上略有提高，但是其在划分输入域时的开销却远远超 l o 华东师范大学硕士学位论文第二章自适应随机测试概述 过随机测试。后来，c h a n 等人的研究发现分割测试的性能不仅依赖失效率，还 和失效区域的类型有关n 2 1 。这就促使我们研究能否通过考虑失效区域的类型因素 从而提高随机测试的性能。 2 2 2 失效域的类型 c h a n 等人在研究分割测试时发现，引发失效的输入容易聚集在某一连续的 区域内，也就是说引发失效的输入如果在输入域的某一区域出现，则很可能在这 一片连续的区域中的所有输入都会引发程序失效，由此产生了让测试用例均匀分 布在整个输入区域来提高算法快速发现程序错误的能力的想法，从而提出了a r t 算法。本文根据引发程序失效的输入点的分布情况把失效域划分为2 种类型，一 种是离散型失效域或点状失效域，另一种是连续型失效域或块状失效域。所谓离 散型失效域是指引发程序失效的输入并不集中在某一连续的输入区域，而是广泛 的分散在整个输入域的大部分区域，而连续型失效域是指引发程序失效的输入集 中在输入域内某一封闭的连续的区域内。下面以二维输入域为例，对这2 种失效 域类型进行简单的说明，并提供形成这些类型的失效区域的可能原因，如图2 2 所示。 ( a ) 离散型( 点状)( b ) 连续型( 块状) 图2 2 失效域的类型 形成这些失效区域一般是由于程序中某些特定的语句发成错误而产生的，下 面三幅图用以简单说明这两种失效域类型形成的可能原因。 形成离散型失效域的示例代码： 华东师范大学硕士学位论文 第二章自适应随机测试概述 图2 3 形成离散型失效域的代码片段 形成连续型失效域的示例代码( a ) ： 图2 4 形成连续型失效域的代码片段( a ) 形成连续型失效域的示例代码( b ) ： 图2 5 形成连续型失效域的代码片段( b ) 1 2 华东师范大学硕士学位论文第二章自适应随机测试概述 2 2 3 自适应随机测试 自适应随机测试( a d a p t i v er a n d o mt e s t i n g ，简称a r t ) ，是t y c h e n 等人 对随机测试算法的改进，它要求新生成的测试用例与所有已经用来测试过程序但 并没有引发程序失效的测试用例的距离尽可能的远，从而使生成的测试用例尽可 能快速均匀的分布在整个输入域，以达到快速探测到失效区域，提高算法发现程 序错误的能力n 朝。 这个改进主要和c h a n 等人研究分割测试时发现的失效域的类型有关，研究 发现引发程序失效的测试用例更容易集中出现在输入域的某一区域，也就是说引 发失效的测试用例容易组成一个连续的区域( 块状区域) ，正是基于这种连续形 失效区域( 块状失效域) 才提出来的a r t 算法。因此，a r t 算法对错误的发现能 力也仅对连续型失效区域有显著的提高。在 1 4 和 1 5 实验显示当失效域为连续 型时，a r t 的有效性比r t 有非常显著的提高，而当失效区域为离散型时几乎没 什么改进效果。 f s c s 算法是实现a r t 算法中的一个经典算法，由于在算法具体实现时所使 用的候选用例集合大小是固定的，所以我们又称该算法为固定候选测试用例集合 的a r t 算法( f i x e ds i z ec a n d i d a t e ss e tv e r s i o no ft h ea d a p t i v er a n d o m t e s t i n g ，简称f s c s ) 。 从t y c h e n ，h 1 e u n g 等人的实验结果来看，f s c s 所获得的f - m e a s u r e 值 要比r t 小得多，从而说明a r t 比r t 在发现程序错误的能力上有显著的提高。当 然实验也发现了一些不足，比如算法中由于增加了大量的距离计算而增加了程序 的开销，产生n 个测试用例的算法时间复杂度为o ( n 2 ) ，另一个是处于输入域边 界的点有更大的机会被选作下一个测试用例，也就是边界效应问题，还有就是随 着维数的增加，f s c s 的有效性逐渐降低甚至会低于r t n 6 圩3 。 本论文所做的研究工作主要是对f s c s 算法进行改进，所做的实验也和a r t 一样是在连续型失效区域下进行的。 2 2 4 算法有效性的度量 查阅文献中发现有很多概念的描述都不尽统一，在此把本文中用到的一些 概念作简单的介绍并统一称谓，同时把本文中实验数据统计和比较的计算公式作 简单介绍。 华东师范大学硕士学位论文第二章自适应随机测试概述 错误( e r r o r ) 是指人们在编写程序代码时出现的过错，可以是过失错误也 可能是遗漏错误，我们也称之为b u g 。缺陷( f a u l t ) 指的是错误的代码在程序 功能上的表现。失效( f a i l u r e ) 指的是有缺陷的程序被执行时产生的与预期不 一致程序错误。测试( t e s t ) 是为了处理错误、缺陷、失效而对程序进行的检查 检验 1 8 。测试用例( t e s tc a s e ) 是指对一项软件产品进行测试工作的描述， 需要有测试方案、方法、技术和策略。内容包括测试目标、测试环境、输入数据、 测试步骤、预期结果、测试脚本等，并形成文档，我们在本文算法中所提到的测 试用例指的是程序的一组输入值。在程序测试过程中，能够使程序失效的输入我 们称为引发失效输入( f