（计算机应用技术专业论文）基于演化的测试数据生成.pdf

中山大学硕士论文 基于演化的测试数据生成 基于演化的测试数据生成 专业： 计算机应用技术 硕士生： 刘桢立 指导老师： 乔海燕副教授 摘要 软件测试作为软件开发过程中的重要一环，对于保障软件质量起着至关重要 的作用。随机测试技术是软件测试的重要技术之一，也是目前函数式程序测试的 主要方法。而测试数据自动生成方法的正确性和有效性，是随机测试的根本。因 此，测试数据生成方法的研究，对于测试技术乃至整个软件测试过程来说，都有 着非常重要的意义。 q u i c k c h e e k 、s m a l l c h e e k 和l a z y s m a l l c h e e k 等都是函数式程序语言h a s k e l l 的测试工具。s m a l l c h e c k 和l a z y s r n a l l c h e c k 都是使用穷举测试方法，在某些情 况下，测试时需要大量时间。而在测试一些需要前置条件的函数时，q u i c k c h e c k 就不能够产生足够的数据来对相关的函数性质进行测试，从而出现“a r g u m e n t s e x h a u s t e d ”的问题。本文从这点出发，提出了利用演化思想的测试数据生成方 法，提供了一个h a s k e l l 程序的自动化测试工具- e c h e c k 。实验结果表明：e c h e c k 在测试需要前置条件的函数性质上取得了比q u i c k c h e c k 和s m a l l c h e c k 更好的效 果，不仅可以生成足够的数据，而且在有效性和时间效率上都得到了改进。最后， 文章探讨了演化测试技术和一些优化智能算法在函数式程序测试中的应用。 关键词：测试数据生成，随机测试，前置条件，测试工具，演化测试 e v o l u t i o n b a s e dt e s td a t ag e n e r a t i o n m a j o r ：c o m p u t e rs c i e n c ea p p l i c a t i o na n dt e c h n i q u e s n a m e ：l i uz h e n l i s u p e r v i s o r ：q i a oh a i y a n a b s t r a c t s o f t w a r et e s t i n gi sa l li m p o r t a n ts t e pi nd e v e l o p i n gs o f t w a r e ，a n di tp l a y sa c r u c i a lr o l ei n a s s u r i n gs o f t w a r eq u a n l i t y r a n d o mt e s t i n gt e c h n i q u ei so n eo f t h em o s ti m o p o r t a n tt e c h n i q u e si n s o f t w a r et e s t i n g ，i ti sa l s ot h em a i na p p r o a c ht ot e s t i n gf u n c t i o n a lp r o g r a m s t h ev a l i d i t ya n d e f f e c t i v e n e s so ft h em e t h o dt og e n e r a t i n gt e s td a t aa u t o m a t i c a l l yi st h ek e yt or a n d o mt e s t i n g t h e r e f o r e ，t h es t u d yo f t e s td a mg e n e r a t i o ni sv e r yi m p o r t a n tf o rf u n c t i o n a lp r o g r a m s o u i c k c h e c k , s m a l l c h e c ka n dl a z y s m a l l c h e c ke ta la r et e s t i n gt o o l sf o rh a s k e l lp r o g r a m s s m a l l c h c c ka n dl a z y s m a l l c h e c ku s ee x h a u s t i v et e s t i n gt e c h n i q u ew h i c hc o n s u m e m u c ht i m ef o r u s e r s w h e nt e s t i n gs o m ep r o g r a m sw h i c hn e e dp r e c o n d i t i o n s ，q u i c k c h e e ka l w a y sl e a dt o ”a r g u m e n t se x h a u s t e d ”h ao r d e rt os o l v et h i sp r o b l e m ，t h i sp a p e rp r o p o s e san o v e lm e t h o d t o g e n e r a t i n gt e s td a t aa u t o m a t i c a l l y , a n dh a sd e v e l o p e dat e s t i n gt o o lf o r i - i a s k e l l a f t e rc o m p a r e d w i t ht h eb e n c h m a r ke x p e r i m e n t si ns m a l l c h e c ka n dl a z y s m a l l c h e c k , e c h e c ks h o w s i t s a d v a n t a g e si nt e s t i n gp r o g r a m sw h i c hh a v ep r c c o n d i t i o n s ，n o to n l yi ng e n e r a t i n ge n o u g ht e s td a t a , b u ta l s oi nt e s t i n gt i m e ，e f f e c t i v e n e s sa n ds o0 1 a f i n a l l y , w ed i s c u s s e dt h ea p p l i c a t i o n s o f e v o l u t i o n a r yt 船t i n gt e c h n i q u e s a n do t h e ri n t e l l i g e n to p t i m i z a t i o na l g o r i t h m si n f u n c t i o n a l p r o g r a m m i n gl a n g u a g e s k e yw o r d s ：t e s td a t ag e n e r a t i o n ，r a n d o mt e s t i n g ，p r e c o n d i t i o n , t e s t i n g t o o l ，e v o l u t i o n a r y t e s t i n g m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关函数库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：扣1 融 日期：泸i o 年6 月力日 导师签名：罨、6 备弛 日期：沙f 口年彳月弓日 中山大学硕士论文基于演化的测试数据生成 1 1引言 第1 章绪论 在电影星际旅行i i ：可汗的愤怒中，博格斯说过：“在宇宙的历史中，毁 灭总是比创建容易”【1 1 。 1 9 9 3 年，英特尔公司推出了奔腾芯片，后来t h o m a sr n i c e l y 教授用它来寻 找素数三元偶( 连续三个奇数都是素数) ，由于他还采用了另一套验证程序，发现 运算结果出现了问题，经过半年的努力，最终将错误定位在英特尔处理器的浮点 运算单元，并报告给了英特尔公司。起初英特尔公司极力维护，并声称该缺陷出 现的概率为9 0 亿分之一。但是一位s t a n f o r d 大学的教授却指出他可以将这个缺 陷每3 0 毫秒触发一次，而且看起来比较平常的一个运算4 9 9 9 9 9 9 1 4 9 9 9 9 9 9 结 果将是0 0 0 0 0 0 4 0 7 。后来i b m 也发表报告，质疑英特尔公司的宣称。最后，英 特尔公司为自己处理软件缺陷的行为道歉并花费4 亿多美元来支付更换芯片的 费用。现在英特尔公司在其官方网站上主动公布已发现的问题，并认真查看客户 在因特网新闻组上的反馈意见。 由此可见：在软件开发过程中，软件测试是保障软件质量的重要环节【i 】。 自从g r a c eh o p p e r 女士发现第一个软件缺陷以来，各种软件测试技术得到发 展应用，人们也越来越重视软件测试。现在软件测试的投入己占了软件开发投入 的5 0 以上【6 】。而且，长期的软件开发经验积累发现，一个软件缺陷发现的越晚， 付出的代价越大。所以，在软件开发过程中，应该充分重视软件测试工作，尽早 制定软件测试计划，而且做到边开发、边测试。 当然没有人曾承诺说：软件测试会是容易的事。曾有一位智者说过：“如果 你觉得设计和编写程序很困难，你就并非无所知。”【l 】 对于软件测试，测试数据生成方法的科学性和有效性是进行成功测试的前 中山大学硕士论文 基于演化的测试数据生成 提。这些测试数据不仅应该包括那些看来“合理”的数据，还应该包括那些“不合 理”的数据，这里所谓的不合理数据，指的是用户在正常的情况下不会碰到，但 在某种特定的环境或情况下( 比如误操作) 可能输入的数据【4 2 】。因此，在保证软件 在“合理的输入下正确工作的同时，我们更应该确保软件在“不合理”的输入 下也能稳定、正常地工作。因为这些错误的操作往往是隐蔽的，不容易被发现的， 而往往其带来的后果却是极其严重的、破坏力极强的，甚至可以说是灾难性的! 然而，对于一个软件来说，由于其输入数据是无穷的，在软件测试过程中无法对 所有“合理”和“不合理”的数据都测试一遍，因此需要选择一些数据来进行测 试，这就涉及到如何选择测试数据的问题。因此，如何科学、有效地生成测试数 据，对于软件测试乃至整个软件开发过程来说，具有极其重要的意义。 而函数式程序设计语言是一种与命令式语言相对的语言。它具有很多优点： 第一，函数式程序因为没有副作用，更便于测试和推理；第二，函数式程序没有 路径、变量、流程等，也没有全局状态；第三，函数式程序更加简洁和模块化； 此外，它还具有简洁、优美、支持模式匹配、支持惰性计算和高阶函数等特点。 由于函数式程序没有流程、状态、路径等概念，主要采取的是黑盒测试。如今有 越来越多的人研究函数式程序设计语言及其测试方法。 1 2 函数式程序测试的国内外研究现状和相关工具 在测试研究领域中，函数式程序的测试方法主要是随机测试。函数式程序 设计语言的测试方法及其相关工具渐渐成为研究的热点。而作为函数程序设计语 言中经典和流行的语言，h a s k e l l 已经有多个测试程序的测试工具，并被广泛使 用和研究。本文同样也是在深入研究h a s k e l l 的各种测试工具之后进行研究的。 2 0 0 0 年，在函数式程序国际会议( i c f p ) 上，来自瑞典查尔姆斯理工大学 的两位教授k o e nc l a e s s e n 和j o h nh u g h e s 发表了他们关于q u i c k c h e c k 【6 】的论文， 他们的测试工具q u i c k c h e c k 不仅对系统的数据类型( 如整型) 可以自动产生测试 数据，对用户定义的数据和定义的函数都可自动产生测试数据。用户在使用 q u i c k c h e c k 时需要提供程序的规格说明，就是该函数应该满足的性质， q u i c k c h e c k - - 次自动产生一百个数据( 或者测试用例) 来检查这个性质是否成立， 2 中山大学硕士论文基于演化的测试数据生成 这样就可以检测和判断函数定义的正确性。如今，q u i c k c h e e k 的思想被广泛应用， 像e r l a n g 、p y t h o n 、j a v a 、f 拌等语言都开发了类似于q u i c k c h e c k 的工具。 在2 0 0 7 年，同样是在函数式程序国际会议( i c f p ) 上，英国约克大学的c o l i n r u n e i m a n 、m a t t h e wn a y l o r 和f r e d i r kl i n d b l a d 针对q u i e k c h e e k 的缺陷提出了 s m a l l c h e c k 8 】和l a z ys m a l l c h e c k t 8 】工具。s m a l l c h e c k 实质上是基于性质测试的 小数据的穷举测试的一个库，s m a l l c h e c k 用户可以( 1 ) 用简单标准的形式写出 数据的生成器( d a t ag e n e r a t o r ) ：( 2 ) 如果一个函数错了，可以看到这个函数性 质的反例；( 3 ) 可以使用更丰富的规格说明语言来表示存在量词。l a z y s m a l l c h e c k 可以检测部分函数的性质，它使用平行合取的方法来自动精简测试空 间并一直重复下去，可以自动产生满足条件性质的测试数据。在测试效果上，他 们也提出，虽然有时候s m a l l c h e c k 和l a z ys m a l l c h e c k 比q u i c k c h e c k 更有效，但 是相反，在某些情况下，q u i c k c h e c k 会比s m a l l c h e e k 和l a z ys m a l l c h e e k 更有效。 同样是在2 0 0 7 年，约克大学的m a t h e wn a y l o r 和c o l i nr u n c i m a n 在s m a l l c h e e k 之后提供了一个新的测试工具r e a c h l 9 。该工具基于惰性收缩。r e a c h 可以将使 得被测函数性质不成立作为目标函数( t a r g e t ) ，在测试时，r e a c h 利用广度优 先搜索找到达至l j t a r g e t 的测试用例。利用r e a c h ，可以避免或者尽量少写生成器。 不同于q u i c k c h e c k 和s m a l l c h c h e c k 的是，r e a c h 是在h a s k e l l 语言的另外一个编译 器y h c 中运行的。 而演化测试技术旨在利用遗传算法，在待测软件的输入空间进行启发式搜 索，以较高的效率获得满足测试目标的测试用例。它的高效性与高度的自动化水 平，可以成功地针对多种测试需求生成高质量的测试用例，可以显著降低测试成 本，提高测试质量【_ n 。近年来，越来越多的学者开始关注演化测试技术的研究， 而演化测试在结构性测试、功能性测试、性能测试以及面向对象测试等领域都得 到了很好的应用和发展。 1 3 相关研究和测试工具的不足和本文研究的动机 在h a s k e l l 程序的测试工具中，s m a l l c h e c k 、l a z y s m a l i c h e c k 和r e a c h 都是 使用穷举测试方法，而且同样都是从数据的深度信息出发。这样就导致了在某些 中山大学硕士论文基于演化的测试数据生成 情况下测试所需要较长时间，这样就不能迅速找到错误，从而分析错误原因。而 在对q u i c k c h e c k 做了大量实验之后发现，q u i e k c h e c k 存在以下几个几点不足： ( 1 ) 产生的自动测试数据数值太小，数据的深度或者长度不够；( 2 ) 若函数性质要满足一定的前置条件，则往往不能自动产生一百个数据，或者说生 成的无效数据太多，导致出现“a r g u m e n t se x h a u s t e d ”的问题。例如，当验证二 叉查找树的插入或者删除运算时，需要生成深度大于1 的二叉查找树来测试这些 运算所满足的性质。这时，q u i c k c h e c k 就不能一次生成一百个这样的二叉查找 树，因此最后返回给用户的结果是“a r g u m e n t se x h a u s t e d ”；( 3 ) q u i c k c h e c k 在 发现函数错误上的表现还不尽如人意。例如，r u n c i m a n 提供的函数库中，在其 红黑树和象棋问题程序中都植入了错误，但是q u i c k c h e c k 并没有发现。 而本文正是从现有的h a s k e l l 测试工具的缺陷出发，尝试将简单的演化策略 引入到h a s k e l l 程序测试中，也即提出基于演化的测试数据生成方法，并在这个 方法之上开发新的h a s k e l l 程序的测试工具。基于演化的测试数据生成方法先生 成一些小的、深度浅的或者长度短的小数据，然后通过组合或者简单的演化 策略生成满足前置条件的大数据，这样不仅能够解决q u i c k c h e c k 中出现的 “a r g u m e n t se x h a u s t e d 的问题，在时间效率和发现错误性能等方面都应该会得 到提高和改进。在评估方面，本文将利用r u n e i m a n 提供的函数库和其他一些函 数实例，包括一些故意植入错误的函数实例来对本文所提出的方法和工具进行验 证。 1 。4 研究的主要内容和贡献 本文针对q u i e k c h e c k 和s m a l l c h e c k 在测试有前置条件的函数时所遇到的瓶 颈问题进行研究。本文的主要内容如下： ( 1 ) 利用演化的思想来生成h a s k e l l 程序各种类型数据元素的方法， 包括基本数据类型及用户自定义类型等。 ( 2 ) 在生成各种类型数据元素的基础上，通过一些辅助函数，自动生 成函数的演化生成方法。 ( 3 ) 为方便用户定义其自定义类型数据的生成方法，提供一些简单的 4 中山大学硕士论文基于演化的测试数据生成 ( 4 ) ( 5 ) 辅助生成的函数。 提供测试工具e c h e c k ，并利用已有的函数库和其它函数实例， 对e c h e c k 与q u i e k c h e e k 和s m a u c h e c k 分别进行对比，验证新 工具在测试方法的有效性和具体应用的优越性。 对随机测试的思想和演化测试的其他技术进行探讨，提出对以后 这些思想和技术在函数式程序设计中的应用的心得体会和有关 建议。 本文的主要贡献有： ( 1 ) 针对q u i c k c h e c k 和s m a l l c h e c k 等测试工具的缺陷，将演化测试 的思想应用到函数式程序测试中，提出了基于演化的测试数据生 成自动生成方法，另外为h a s k e l l 提供了新的测试工具e c h e c k ， 有效的解决了以上几个测试工具的缺陷。 ( 2 ) 不管要求的前置条件、即生成的数据需要满足的条件多复杂，都 能够生成足够的测试数据，并可以使得生成数据满足一定的性质， 大大减少了“a r g u m e n t se x h a u s t e d 的出现。对此论文从理论上 进行了分析，并用实验进行了验证。利用现有的函数库和自己定 义的程序，实验结果发现：e c h e c k 能够生成足够的满足前置条件 的测试数据，在发现程序中的错误上表现地更优异，同时减少了 测试时间，提高了时间效率。 1 5 论文的组织结构 本论文共分为六章。 第一章：主要介绍论文研究的目的和意义，当前国内外的研究现状，本文研 究的动机及本文的主要工作等。 第二章：介绍软件测试的相关知识，包括软件测试的相关概念、随机测试、 演化测试的相关研究工作等。 第三章：介绍函数式程序设计的概念，当前h a s k e l l 程序的主流测试工具的 中山大学硕士论文 基于演化的测试数据生成 详细介绍，以及这些测试工具的缺陷。 第四章：利用演化思想生成测试数据，是本论文的中心。详细介绍了如何利 用演化的思想来生成h a s k e u 程序下各种类型数据元素的方法，包括基本数据类 型及用户自定义类型等，并提供了一些用于方便用户定义其自定义类型数据元素 生成器的辅助函数。 第五章：测试工具e c h e c k 、其性能分析以及其它实例研究、比较等。主要 介绍了在利用前面提到的演化生成h a s k e l l 程序各种类型数据元素的基础上，开 发的一个h a s k e l l 程序自动化测试工具e c h e c k ，用户利用该工具可以对h a s k e l l 程序进行随机测试；然后我们利用该工具对现有函数库进行一些测试，通过这些 测试从一定程度上验证这种系统化生成测试数据的方法的有效性和科学性；利用 包含故意植入错误的函数实例，来检验和对比e c h e c k 和其他工具在发现错误上 的性能表现。 第六章：总结与展望。主要是对论文工作的总结，此外，我们讨论了演化测 试技术在函数式程序测试的应用和个人的一些体会和心得。 6 中山大学硕士论文基于演化的测试数据生成 第2 章软件测试相关知识 2 1 软件测试相关概念 2 1 1 软件测试的相关定义 软件测试是以发现软件当中尚未发现的错误或缺陷为目的的执行软件的过 程【i 】。简而言之，软件测试是为发现错误而执行程序的过程【。 一般的，只有符合以下5 个规则才能叫做软件缺陷【2 】： 1 软件未达到产品说明书标明的功能； 2 软件出现了产品说明书指明不能出现的错误； 3 软件功能超出产品说明书指明范围； 4 软件未达到产品说明书虽未指出但应达到的目标； 5 软件测试员认为软件难以理解、不易使用、运行速度慢，或者最终用户 认为不好。 软件测试的信息流程可以用下图的数据流图来说吲4 】： 图2 1 ：软件测试信息流程 7 中山大学硕士论文基于演化的测试数据生成 与分析、设计、编码等工作相比，软件测试具有若干特殊的性质，包括：挑 剔型、复杂性、不彻底性和经济性【4 】。虽然，对于大多数软件而言，就算是满意 地执行了测试阶段之后，我们也不大可能确保软件就没有任何错误了。但我们可 以放心地结论说测试提供了一种可操作的方法来减少一个系统中的缺陷，并增加 对一个已开发系统的用户信心【4 1 。 2 1 2 软件测试的目标 软件测试的目标是什么? q m y e r s 给出了以下关于测试的一些目标【1 】： ( 1 ) 测试是为了发现程序中的错误而执行程序的过程； ( 2 ) 好的测试方案是极可能发现迄今为止尚未发现的错误的测试方 案； ( 3 ) 成功的测试是发现了至今为止尚未发现的错误的测试。 正确认识测试目标是十分重要的，测试目标决定了测试方案的设计。此外， 应该认识到测试决不能证明程序时正确的。即使经过了最严格的测试之后，仍然 可能还有没被发现的错误潜藏在程序中。正如，e d s g e rw d i j k s t r a 所说：“测试永 远不能证明软件中不存在错误，只能证明软件中存在错误。”【4 】 2 1 3 软件测试的重要准则 怎样才能达到软件测试的目的呢? 为了能设计出有效的测试方案，软件测试 工程师们必须深入理解并正确运用指导软件测试的基本准则。软件测试的重要准 则为【1 】： 1 测试用例中一个必需部分是对预期输出或结果的定义； 2 程序员应当避免测试自己编写的程序； 3 编写软件的组织不应当测试自己编写的软件； 4 应当彻底检查每个测试的执行结果； 5 测试用例的编写不仅应当根据有效和预料到情况，而且也应当根据无效 和未预料到的输入情况； 中山大学硕士论文基于演化的测试数据生成 6 检查程序是否“未做其应该做的”仅是测试的半，测试的另一半是检 查程序是否“做了其不应该做的 ； 7 应避免测试用例后即弃，除非软件本身是一个一次性的软件； 8 计划测试工作时不应默许假定不会发现错误： 9 程序某部分存在更多的可能性，与该部分已发现的数量成正比； 1 0 软件测试是一项极富创造性、极具智力挑战性的工作。 2 1 4 软件测试的方法 由于时间和成本的约束，软件测试的最关键问题剁1 】： 在所有可能的测试用例中，哪个子集具有可能发现最多的错误? 对软件测试用例的研究为这个问题提供了答案。 而测试任何产品都有两种方法：如果已经知道了产品应该具有的功能，可以 通过测试来检验每个功能都能正常使用；如果知道产品的内部工作过程，可以通 过测试来检测产品内部动作是否按照规格说明书的规定正常进行【钔。前一种方法 称为黑盒测试，后一种方法称为白盒测试【4 】。 对于软件测试而言，黑盒测试法把程序看作一个黑盒子，完全不考虑程序的 内部结构和处理过程，也就是说，黑盒测试是在程序接口进行的测试，它只检查 程序功能是否能按规格说明书的规定正常使用，程序是否能适当地接受输入数据 并产生正确的输出信息，程序运行过程中能否保持外部信息( 例如，函数库或文 件) 的完整性 4 1 。黑盒测试又称为功能测试 4 1 。 白盒测试与黑盒测试相反，它的前提是可以把程序看成装在一个透明的白盒 子里，测试者完全知道程序的结果和处理算法【4 1 。这种方法按照程序内部的逻辑 测试程序，检测程序中的主要执行路径是否按预定要求正确工作【4 】。白盒测试又 称为结构测试1 4 。 而一般的，黑盒测试的方法包括：等价类划分、边界值分析、因果图分析、 错误猜测等；白盒测试的方法包括：语句覆盖、判定覆盖、条件覆盖、判定条 件覆盖、多重条件覆盖、点覆盖、边覆盖、路径覆盖等【1 1 。 9 中山大学硕士论文 基于演化的测试数据生成 2 2 自动化测试与随机测试 2 2 1 自动化测试 自动化测试是把以人为驱动的测试行为转化为机器执行的一种过型n 】。自动 化测试与软件开发过程从本质上来讲是一样的，无非是利用自动化测试工具，经 过对测试需求的分析( 软件过程中的需求分析) ，设计出自动化测试用例，从而 搭建自动化测试的框架( 软件过程中的概要设计) ，设计与编写自动化脚本( 详 细设计与编码) ，测试脚本的正确性，从而完成该套测试脚本【】。 1 9 9 6 年美国伊利诺伊理工学院建立了测试成熟度模型( t m m ) 1 l 】。在t m m 模 型的指导下，内部的评估队伍可以确定当前的测试能力等级；高层管理者可以改 进测试计划；开发队伍可以提高测试的能力；用户和客户可以定义自己在测试过 程中的角色i l l 】。应用t m m 模型的基础是确定测试组织当前的测试能力等级，该 组织也可以通过这些等级达到更高的测试成熟度【l 。 测试成熟度模型在每个成熟度等级上都列出了一系列建议做法。它促进了软 件测试向更强的专业化方向发展，类似于软件的能力成熟度模型c m m 1 2 】的概念。 而e l f r i e d ed u s t i n ，j e f fr a s h k a 和j o h np a u l 提出了与测试成熟度相对应的自动 软件测试模型。自动软件测试模型也分为5 级：第一级为偶发的自动化，是最低 的级别；第二级为附带的自动化；第三级为有意识的自动化；第四级为高级自动 化；第五级为高度自动化，是最高级别的自动化【l l 】。 当正确地实施自动化测试并遵循严格的过程时，自动化测试表现出很多优 势。已经确定自动化测试( 与手动测试结合) 的三大好处【】：( 1 ) 生产出可靠的 系统；( 2 ) 改进测试工作质量；( 3 ) 减轻测试工作量并缩短了测试进度。 2 2 2 随机测试 在软件测试中除了根据测试用例和规格说明书进行测试外，一般情况下，还 l o 中山大学硕士论文基于演化的测试数据生成 需要进行随机测试，主要是根据测试者的经验对软件进行功能和性能等方面的抽 查。随机测试是根据规格说明书执行测试用例的重要补充手段，是保证测试覆盖 完整性的有效方式和过程【2 引。 随机测试主要是对被测软件的一些重要功能进行复测，也包括测试那些当前 的测试用例没有覆盖到的部分f 2 8 1 。另外，对于软件更新和新增加的功能要重点 测试。重点对一些特殊情况点、特殊的使用环境、并发性、进行检查。尤其对以 前测试发现的重大缺陷，进行再次测试，可以结合回归测试一起进行【2 8 1 。 随机测试起源于斯坦福大学和麻省理工学院的人工智能实验室。但是在上个 世纪八十年代以前，随机测试一直被嘲笑为“杂乱无章的”和“没有意义的” 1 3 1 。 它甚至被m a y e r s 说成是一种“可能是最糟糕的测试方法”d 4 。直到八十年代， d u r a n 和n t a f o s 的工作才使这种看法才有所改变，他们通过一系列的模拟实验发 现，分割测试( 划分测试) 发现错误的能力确实比随机测试更强，但是这种优势 是微乎其微的。分割测试在子域和测试用例设计上的开销大，随机测试却大大减 低了测试的成本。因此，d u r a n 和n t a f o s 认为随机测试的有效性要优于分割测试 f 1 4 】。到了九十年代，h 锄l e t 和t a y l o r 对模拟进行了拓展【1 5 】，其结果也与d u r a n 和 n t a f o s 的发现相同。 迄今为止，对于分割测试和随机测试的比较仍然十分活跃 1 6 , 1 7 , 1 8 , 1 9 。但是没 有研究表明一种方法明显优于另一种方法。而很多简单又有效的随机测试工具被 开发出来并应用到软件测试过程和各项工程中，例如，k o e nc l a e s s e n 和j o h n h u 曲e s 开发的针对h a s k e l l 五。- - 。 - 。i 一、l 酬。 为了进一步增强随机测试的有效性，c h e nt o n gy u e 教授提出了自适应随机 测试方法【2 0 ，2 1 捌，对随机测试进行了改进。这种方法使用一定的算法策略( 如固 定大小候选集自适应随机测试算法、划分自适应随机算法等) ，对随机产生的测 试用例进行筛选，使得所选择的测试用例能均匀分布于整个输出域中，从而提高 了测试的有效性和测试的效率。而今，自适应随机测试已经成为软件测试领域的 研究热点，产生了准自适应随机测试f 2 3 】和基于点阵的自适应随机测试方法【2 4 】等， 而自适应随机测试的方法和相关技术正越来越广泛应用于黑盒测试中。 随机测试确实可以大大降低测试开销，但是不可否认的是，随机测试还具有 以下这些缺点【1 0 l ： 中山大学硕士论文基于演化的测试数据生成 ( 2 ) ( 3 ) ( 4 ) 当测试需要满足一些前提条件时，常常因为生成数据简单或者前 提条件的信息没有“溶入 到测试数据生成的过程中，最终生成 的数据不能满足测试的前提条件； 不能达到一定的覆盖率； 许多生成的测试用例都是冗余的； 需要使用同样的随机数种子才能重建测试。 2 3 测试数据生成与演化测试 测试数据的自动生成技术是成功实施随机测试的关键。测试数据的自动生成 技术也早成为软件测试研究领域的重点和热点。根据测试数据的生成方法，一般 可以将结构测试数据自动生成技术分为三大类：静态法、动态法和基于搜索的方 法【2 5 】。这里重点介绍的是基于搜索的方法。 2 3 1 基于搜索的方法 基于搜索的方法主要是利用一些优化算法，并将测试问题转化为优化问题来 进行测试。基于搜索的方法包括模拟退火算法1 2 6 1 、禁忌搜索算法【2 7 1 、遗传算法 【1 0 】竺 寸o 早在19 9 7 年，n i g e lt r a c e y 等人就将模拟退火算法引入到软件测试中。模拟 退火法模拟高温材料的冷却过程，它有着完善的全局收敛理论【2 6 】。在n i g e lt r a c e y 的论文中，他们首先把前置条件和后置条件转换为析取范式，例如条件 a ( bv ( c d ) ) 将被转换为1av ( bv ( cad ) ) ；接着利用转换规则将布尔运算转 换为数值，这样就可以将软件测试问题转化为优化问题，进而将模拟退火算法引 入。n i g e lt r a c e y 等人的基于优化技术的框架可以考虑结构化和非结构化性质的 一系列测试条件和准则。 2 0 0 3 年，e u g e n i ad i a z 等人将禁忌搜索算法引入到软件测试中。禁忌搜索算 法是对局部领域搜索的一种扩展，是种全局逐步寻优算法该算法通过引入一个 灵活的存储结构和相应的禁忌准则来避免球架搜索，并通过藐视规则来赦免些 中山大学硕士论文基于演化的测试数据生成 被禁忌的优良状态，进而保证多样化的效率探索以最终实现全局优化【2 7 1 。而在 e u g e n i ad i a z 的论文中，提出了禁忌搜索适应度函数的计算方法和领域选择过程 的指导原则，在禁忌表的创建上考虑了多种因素，对于不可达的分枝使用了回溯 法来解决。从实验结果来看，禁忌搜索算法大大的提高了自动生成数据的分枝覆 盖率。 而r o yp p a r g a s 等人在使用遗传算法生成测试数据方面做出了里程碑式的贡 献。遗传算法是一种迭代搜索算法，采用编码技术将输入空间映射到基因空间， 并通过遗传操作如选择、交叉、变异等和优胜劣汰的自然选择确定搜索方向【1 0 1 。 在r o ye p a r g a s 的论文中，他们将程序的控制流程图转换为控制独立图，然后再 将遗传算法引入到测试数据生成中，其步骤可以概括为： s t e p1 ：初始化，包括控制独立图路径的计算 s t e p2 ：在w h i l e 循环外生成数据 s t e p3 ：在w h i l e 循环内生成数据，这里包括杂交、变异等操作 s t e p4 ：合并第二步和第三步产生的数据，把符合测试要求( 前置条件) 的 数据执行，将最后结果返回。 在这个算法基础之上，r o ye p a r g a s 等人还开发了自动生成数据的简单工具 t g e n 。实验表明：t g e n 在时间效率和测试数据的重复率上比当时现有的工 具都得到很大的改进。 2 3 2 演化测试 在上述介绍的基于搜索的测试数据生成方法中，由于遗传算法具有通用性、 易操作性，因为它被广泛地应用于各种测试领域，包括结构性测试、功能性测试、 性能测试、安全测试、错误驱动测试、面向对象测试等【2 8 】，并产生了- - i - j 新兴 的研究领域：演化测试。 演化测试技术旨在利用遗传算法，在待测软件的输入空间进行启发式搜索， 以较高的效率获得满足测试目标的测试用例【7 1 。它是一种非常有应用前景的测试 数据自动生成技术。演化测试利用优化算法在测试数据空间进行智能搜索，它的 高效性与高度的自动化水平，可以成功地针对多种测试需求生成高质量的测试用 中山大学硕士论文 基于演化的测试数据生成 例，可以显著降低测试成本，提高测试质量【7 1 。 演化测试的特点有【7 】： 演化测试高度的自动化水平可以大幅降低人力成本，提高测试效 率，并且，通过代替人工完成复杂的运算，还可以获得人工测试 所难以生成的测试用例； 演化测试是一种动态测试技术，可以很好地克服静态分析中的多 种局限性； 演化测试技术具有明确的导向性； 演化测试技术在具有明确导向性的同时，还具有一定的随机性； 演化测试技术具有大范围的空间搜索能力，可以有效提高测试用 例的生成效率。 此外，演化测试还很好地顺应了目前硬件发展的趋势。演化测试的并行计算 特性，可以更加充分地应用硬件强大的计算能力，提供高度的自动化水平，因此 具有广阔的应用前景 2 9 , 3 0 1 。 1 4 ) ) ) ) ) 1 2 3 4 5l，ll，l，l 中山大学硕士论文 基于演化的测试数据生成 第3 章函数式程序设计语言及其测试 工具 3 1函数式程序设计的介绍 函数式程序设计的主要思想是把一个功能独立的程序作为一个从输入到输 出函数，整个程序本身也是一个函数，不同的函数之间只要类型匹配，便可以相 互调用f 4 2 1 。这种函数更接近我们数学当中的函数概念，即只要给定它所需要的 参数作为输入，它便可以返回一个结果。另外，函数式程序更简洁、更优美。举 在上面的程序中，q u i c k s o r t 是函数的函数名，( i n t - i n t ) 是函数的类型， 其中【i n t 的含义是“整数的列表”，是函数的输入类型；第二个 i n t 表示函数的输 出类型为整型列表。l e s s 是列表( x ：x s ) 的x s 中所有小于x 的数组成的列表，m o r e 则是】【s 中所有大于等于x 的数组成的列表。 上个世纪二十年代到四十年代，a l o n z oc h u r c h 和h a s k e l lc u r r y 提出和发展 了见演算。五演算是关于函数的理论，是串行计算的一个模型，同样也是函数式 程序设计语言的理论基础。1 9 6 0 年左右，j o h nm c c a r t h y 开发了第一个函数式程 序设计语言叫i s p ，它同样是基于z 演算的( j o h nm c c a r t h y 于1 9 7 1 年获得图 中山大学硕士论文基于演化的测试数据生成 灵奖) 。六十年代后期，p e t e rl a n d i n 开发了第一个纯函数式设计语言 i s w i m 。1 9 7 8 年，j o h nb a c k u s 发布了f 只这个函数式语言强调高阶函数和用程 序来进行计算。七十年代中期，r o b i nm i l n e r 开发了标准元语言m l ，这是第一 个现代函数式程序设计语言，它引入了类型推导和多态类型( r o b i nm i l n e r 于 1 9 9 1 年获得图灵奖) 。在1 9 8 7 年的函数式编程和计算机体系结构会议( f p c a ) 上，p e y t o nj o n e s ，p a u lh u d a k 和p h i l i pw a d l e r 等人决定启动h a s k e l l 的开发设计 工作。1 9 9 0 年4 月1 日，由h u d a k 和w a d l e r 编辑发布了h a s k e l l1 0 版本的报告， 同时h a s k e l l 邮件组启动，对所有人开放。19 9 9 年h a s k e l l 委员会发布了h a s k e l l 9 8 的定义。2 0 0 2 年，h a s k e l l 9 8 修订报告发布，而剑桥大学出版社当年还把这份报 告作为书籍出版。 由于本文所有的程序都是用h a s k e l l 语言来编写的。下面，就以h a s k e l l 例 子来说明函数式程序的特点： 3 1 1 函数式程序设计的特点 1 高阶函数 如果一个函数的输入变量中有一个是函数，或者返回结果是一个函数，则该 函数是高阶函数【5 】。 例如，h a s k e l l 中常用的m a p 函数： l m a pf x s = 【f xx = 等。为此， 定义t 在h a s k e l l 中，各个类的关系如下： 图3 2 ：h a s k e l l 中各类的关系 有时，在定义实例或者函数是可能需要多重约束，这时需要用到( - ) 来进行 定义。例如： 1 9 中山大学硕士论文基于演化的测试数据生成 若一个类型包含了一个或者多个类约束，则称为重载【4 3 1 。例如，下面定义 的加法运算： ( + ) ：n u ma = a a - a 加法运算包含了一个数值类e n u m 的类约束。 一个类型包含了一个或者多个类型变量就被称为是多态【4 3 1 。例如，函数 l e n g t h 可以计算任意类型上列表的长度。 显然，多态函数在所有类型上的定义是一致的。而重载则不然，其定义依赖 于不同的类型。 4 无副作用 函数式程序设计语言中，没有赋值语句，没有变量、流程、路径等概念。一 个参数或者变量一旦给定一个值，那么这个值便是不可改变的。而且在h a s k e l l 中，通过m o n a d 和其它一些纯代码将产生的副作用隔离，这样使得函数式程序 设计不存在重大的安全隐患。正是函数式程序设计语言没有副作用的这一特性， 使得它比其它语言更容易测试和推理。 3 1 2 函数式程序语言的总结 下表为在特征上，命令式语言与函数式语言的比较： 表3 1 ：命令式语言与函数式语言的比较 特征命令式语言函数式语言 如何计算 关注焦点和追踪状态的变化 计算什么 状态变化重要不存在 执行顺序重要不重要 循环表达式、条件表达式 主要的流程控制 以及函数( 方法) 调用 函数调用、包括递归 主要的执行单元 类或结构体的实例 函数 中山大学硕士论文 基