（计算机系统结构专业论文）随机测试用例的自动化生成和约简.pdf

摘要 摘要 软件作为计算机的灵魂，在国民经济和社会生活等各方面都起着举足轻重 的作用。软件质量问题直接影响各行业的正常运作，软件错误轻则给用户带来 不便，重则造成巨大经济损失甚至人员伤亡。软件测试是保证软件质量和可靠 性的重要手段，是软件开发中不可或缺的环节。随着用户对软件产品质量的要 求不断提高以及软件工程技术的日益成熟，软件测试在整个软件开发周期中所 占的比重越来越大。而设计测试用例是软件测试的核心问题，软件测试的好坏 很大程度上取决于测试用例的质量和数量。设计测试用例往往需要手工完成， 耗时长且效率低。因此，设计实现一种高质量的测试用例自动化生成工具，对 于提高软件测试的效率和质量具有重要的研究意义和应用价值。 本文针对测试用例生成这一核心问题，整合随机测试和不变量提取技术， 设计实现了一个完全自动化的测试用例生成框架工具。在分析了随机测试优缺 点的基础上，着重利用随机测试自动化程度高的优点，1 ) 使用预设值技术来提 高随机测试的覆盖率，且支持用户自定义预设值，可扩展性强；2 ) 实现了复杂 类型数据的递归生成，适用范围更广；3 ) 引入错误测试用例过滤机制，保证测 试用例的正常执行；4 ) 不变量是程序执行过程中保持不变的逻辑断言，是对程 序属性的一种描述。利用这一特性，实现了基于不变量变化的约简算法，对随 机生成的测试用例进行有效的约简，使得最终生成的测试用例规模适度；5 ) 为 测试用例生成提供了新的终止标准，解决了以往以时间为限制条件的缺点。最 终的程序输出包括三部分：可用于人工排错或回归测试的正常测试用例，能够 揭示程序缺陷的错误测试用例，以及揭示程序属性的不变量。 通过实验证明，本文实现的随机测试用例生成技术，可以在无任何人工干 预的情况下，完全自动化的生成规模适度的测试用例；基于不变量技术的测试 用例约简算法效果突出：输出的错误测试用例可以有效的揭示程序中的错误： 与纯随机技术相比，带预设值的测试用例代码覆盖率显著提高；变异测试充分 度达到不低于同类测试用例生成工具的水平。 关键词：随机测试测试用例程序不变量测试自动化 a b s t r a c t a sc o m p u t e r ss o u l ，t h es o f t w a r ep l a y sa ni m p o r t a n tr o l e i nt h en a t i o n a l e c o n o m ya n d s o c i a ll i f e t h eq u a l i t yo fs o f t w a r ed i r e c t l ya f f e c t st h en o r m a l o p e r a t i o no ft h ev a r i o u si n d u s t r i e s t h eu s e ro f t e ns u f f e r ss o f t w a r ee r r o r s ，w h a t s w o r s e t h es o f t w a r ee r r o r sc o u l dc a u s eh u g ee c o n o m i cl o s s e so rc a s u a l t i e s s o f t w a r e t e s t i n gi sa ni m p o r t a n tm e a n st o e n s u r es o f t w a r eq u a l i t ya n dr e l i a b i l i t y i ti sa n i n d i s p e n s a b l ep a r ti nt h es o f t w a r ed e v e l o p m e n t t h eu s e r sh a v eb e e nr e q u i r i n g m o r e h i g hq u a l i t ys o f t w a r ep r o d u c ta n ds o f t w a r ee n g i n e e r i n gh a sb e e nb e c o m i n gm o r e s o p h i s t i c a t e d s ot h ep r o p o r t i o no ft h es o f t w a r et e s t i n gi nt h es o f t w a r ed e v e l o p m e n t c y c l ei si n c r e a s i n g d e s i g n i n gt e s tc a s ei st h ec o r eo f s o f t w a r et e s t i n g t h eq u a n t i t y a n dq u a l i t yo ft e s tc a s e sd e t e r m i n ew h e t h e rs o f t w a r et e s t i n g i s g o o d o rb a d d e s i g n i n gt e s tc a s eo f t e nn e e d sm u c hm a n u a lw o r k ，w h i c h i st i m e c o n s u m i n ga n d i n e f - f e c t i v e t h e r e f o r e ，i m p l e m e n t i n ga na u t o m a t i ct e s t c a s eg e n e r a t i o nt o o l ，w h i c h c o u i di m p r o v et h ee f f i c i e n c ya n dq u a l i t yo fs o f t w a r et e s t i n g ，i s v a l u a b l ef o r a c a d e m i cr e s e a r c ha n di n d u s t r ya p p l i c a t i o n i no r d e rt os o l v et h ek e yp r o b l e mo ft e s tc a s eg e n e r a t i o n ，t h i st h e s i sd e s i g n sa f u l l ya u t o m a t i ct e s tc a s eg e n e r a t i o nf r a m e w o r kt o o lb yi n t e g r a t i n gr a n d o mt e s t i n g a n di n v a r i a n te x t r a c t i o nt e c h n i q u e a f t e ra n a l y z i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e s o fr a n d o mt e s t i n g ，w eq u i t ev a l u ei t sm e r i to ft h eh i g hd e g r e eo fa u t o m a t i o na n d u t i l i z ep r e s e t 。v a l u et oi m p r o v et h ec o v e r a g eo fr a n d o mt e s t i n g a n dt h eu s e r sa r e a l l o w e dt oc u s t o m i z et h ep r e s e t - v a l u e o u rt e c h n i q u ec o u l dg e n e r a t e d a t af o r c o m p l e x e dt y p e ，s ot h a ti th a sw i d es c o p eo fa p p l i c a t i o n t h ei n t r o d u c t i o no f f a i l e d t e s tc a s ef i l t e r i n gm e c h a n i s mc o u l de n s u r et h ep r o p e ro p e r a t i o no ft e s t c a s e s i n v a r i a n t sd e s c r i b et h ep r o g r a mp r o p e r t i e st h a th o l da tap r o g r a mp o i n to rp o i n t sa t r u n t i m e b ym e a n so ft h i sf e a t u r e ，w ed e s i g na r e d u c t i o na l g o r i t h mb a s e do nt h e i n v a r i a n t ，sc h a n g e a n dt h er e d u c t i o na l g o r i t h mc a ne f f e c t i v e l ys h r i n kt h es i z eo f t h e r a n d o m l yg e n e r a t e dt e s t c a s e s a tt h es a m et i m e ，t h ea l g o r i t h mp r o v i d e san e w t e r m i n a t i o ns t a n d a r df o rt h et e s t c a s e g e n e r a t i o n , a n ds o l v e st h ef o r m e r t i m e c o n s t r a i n ts h o r t c o m i n g t h eo u t p u t si n c l u d et h r e es e c t i o n s ，t h en o r m a lt e s t c a s e su s e df o rd e b u g g i n gm a n u a l l yo rr e g r e s s i o nt e s t i n g ，t h e f a i l e dt e s tc a s e st o r e v e a le r r o r sa n dt h ei n v a r i a n t st or e v e a lp r o g r a mp r o p e r t i e s t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a t ，t h et e s t c a s er a n d o mg e n e r a t i o n i i a b s t r a c t t e c h n i q u ed e s c r i b e di nt h et h e s i sc o u l dg e n e r a t et e s tc a s e sa u t o m a t i c a l l yw i t h o u ta n y m a n u a li n t e r v e n t i o n t h et e s tc a s er e d u c t i o na l g o r i t h mp e r f o r m sw e l l t h ef a i l e dt e s t c a s e sc o u l df i n de r r o r si np r o g r a m t h et e s tc a s e sw i t hp r e s e t v a l u ea c h i e v eb e t t e r c o d ec o v e r a g et h a nt r a d i t i o n a lr a n d o mt e s t i n g ，a n dc l o s em u t a t i o ns c o r ec o m p a r e d w i t ho t h e rr a n d o mt e s t i n gt o o l s k e yw o r d s ：r a n d o mt e s t i n g ，t e s tc a s e ，p r o g r a mi n v a r i a n t ，a u t o m a t i ct e s t i n g i i i 图目录 图2 1 图2 2 图2 3 图2 4 图3 1 图3 2 图3 3 图3 4 图4 1 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 l 图5 1 2 图目录 d a i k o n 设计框架1 5 工厂方法设计模式的类图示例1 7 r a n d o o p 设计框架1 8 e c l a t 设计框架2 0 j r t 命令行使用示例2 l j r t 设计框架2 2 j r t 的u m l 类图2 3 j r t 的测试用例生成器框架2 5 完整的测试用例生成和约简框架3 8 各阂值下约简前后的平均函数调用数4 4 各种阂值下的约简率4 5 j r t 在各种阈值下的耗时4 6 各种阈值下的标准不变量数4 6 m i d d l e 类的测试用例在各种阈值下的标准不变量数4 7 m y m a t h 类的测试用例在各种阈值下的标准不变量数4 8 四个被测类的测试用例的平均约简率4 9 b o u n d e d s t a c k 类代码清单5 1 c o m p a r e 类在两种测试用例下的代码覆盖率5 3 m i d d l e 类在两种测试用例下的代码覆盖率5 3 m y m a t h 类在两种测试用例下的代码覆盖率5 4 j r t 与r a n d o o p 的变异测试充分度5 5 v i i 表目录 表目录 表2 1j a v a 反射机制相关类简介1 3 表2 2j a v a 反射机制相关函数简介1 4 表3 1j r t 的p r e m a p g e t 类代码清单2 3 表3 2 基本数据类型的预设值2 6 表3 3 预设值的组合算法2 7 表3 4r a n d o m 类相关函数简介2 8 表3 5j r t 生成随机数据的递归算法2 9 表3 6r e c t a n g l e 和p o s i t i o n 类描述2 9 表3 7r e c t a n g l e 类的测试用例示例3 0 表3 8 错误测试用例示例3 1 表4 1d a i k o n 自动化调用所需的相关类描述3 5 表4 2 基于不变量的测试用例约简算法3 7 表4 3 绝对值函数a b s 的代码清单3 9 表4 4a b s 函数的测试用例约简过程示例3 9 表4 5a b s 函数的不变量4 0 表4 6 求倒数函数i n v e r s e 的不变量4 1 表5 1 被测程序描述4 3 表5 2四个被测类的测试用例约简前后对比4 9 表5 3b o u n d e d s t a c k 类的错误测试用例5 0 表5 4j r t 与r a n d o o p 生成测试用例的杀死变异体数5 5 v i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名： 蜜聋签字日期：2 堆华上且生旦 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 耐么开口保密( 年) 作者签名：蜇责 导师签名： 签字日期：三吐璃匕单列臼签字日期：立幽蚪 签字日期：q 垒塑型：、 ：型i 第1 章绪论 1 1 课题背景及研究意义 1 1 1 课题背景 第1 章绪论 随着社会的不断进步和计算机科学技术的飞速发展，计算机软件在国民经 济和社会生活等各方面的应用越来越广泛和深入。作为计算机的灵魂，软件在 其中起着举足轻重的作用。软件质量问题直接影响各行业的正常运作，轻者表 现为给桌面用户带来不便，如浏览器崩溃；而在国防、金融、航天等攸关领域， 软件错误会造成巨大经济损失甚至危及人的生命安全。比如，1 9 9 1 年美军的爱 国者导弹未能拦截伊拉克的飞毛腿导弹导致2 8 名士兵死亡，1 9 9 6 年欧洲a r i a n e 5 运载火箭的发射失败等都是由软件错误引起的。2 0 世纪4 0 年代，女数学家 g r a c eh o p p e r 在工作日志中把因飞蛾引起“m a r ki i 计算机死机的程序故障 称为臭虫( b u g ) 。自此“b u g ”便发展成为计算机领域的专业术语( 周伟明， 2 0 0 8 ) 。 软件缺陷，或者软件故障、软件错误、b u g 等等，即软件产品开发或维护 过程中所存在的错误，或者系统需要实现的某种功能的失效或违背。软件错误 的表现形式是多种多样的( 朱少民，2 0 0 7 ) ：产品实际结果和所期望的结果不一 致；没有达到产品规格说明书所规定的特性、性能指标等；运行出错，包括运 行中断、系统崩溃、界面混乱等；数据结果不正确、精度不够、不完整或格式 不统一；功能、特性没有实现或部分实现；设计不合理，功能不明确，逻辑不 清楚或存在矛盾；用户不能接受的其他问题，如存取时间过长、界面不美观等 也都可以归为软件缺陷。 软件开发的各个阶段都需要人的参与，而人的工作不可能完美无缺，出现 错误是难免的。再者，随着计算机应用的广泛普及和软件功能的不断增强，软 件的规模也在不断增大。例如，w i n d o w sn t 操作系统的代码大约有3 2 0 0 万行。 这使得错误更可能发生。人们在软件的设计阶段所犯的错误是导致软件故障的 主要原因，软件复杂性则是产生软件缺陷的重要根源( 单锦辉等，2 0 0 5 ) 。 尽管人们在软件开发过程中也采用形式化方法描述和证明软件规约，并采 用程序正确性证明、模型检验等方法保证软件质量，但是这些方法都存在一定 的局限性，其实用性尚待发展。例如，在英国约克大学为英国海军开发的s h o l i s 第1 章绪论 项目中，尽管采用形式化方法描述和证明软件规约，并且采用程序正确性证明 方法排除了软件开发前期的许多缺陷，单元测试仍然发现了整个软件开发过程 1 5 7 5 的缺陷( 单锦辉等，2 0 0 5 ) 。因此，无论是从软件开发方法学，还是软 件测试自身的效益看，软件测试在今后较长时间内仍将是保证软件质量的重要 手段。 随着用户对软件产品质量的要求不断提高以及软件工程技术的日益成熟， 软件测试在整个软件开发周期中所占的比重越来越大，大约占到整个开发成本 的3 0 到9 0 。比如在微软公司，测试工程师与开发工程师的比例接近1 ：l ( p a c h e c oe ta l ，2 0 0 8 ) 。对于某些性命攸关的软件，其测试费用甚至高达所有其 他软件工程阶段费用总和的3 到5 倍。尽管如此，软件产品依然错误不断，2 0 0 2 年美国n i s t ( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g y ) 一份年度报告指出， 由于软件测试不充分，每年要花费近6 0 0 亿美元( g o d e f r o i de ta l ，2 0 0 5 ) 。其中， 软件公司大概占l 3 ，他们要发现、修复错误，并发布软件新版本；另外2 3 则 由软件用户承担，比如一个金融软件故障可能导致一项交易失败。 如此惊人的经济损失与软件测试的不充分是分不开的，而软件测试的不充 分相当一部分原因是软件测试需要手工完成。因此，如何提高软件测试自动化 水平是研究人员面前的一个紧迫任务。 1 1 2 测试用例的重要性 软件测试是保证软件质量和可靠性的重要手段，软件开发中不可或缺的环 节，其效果直接关系到软件产品的质量。1 9 8 3 年i e e e 将软件测试定义为：使 用人工或自动的手段来运行或测定某个系统的过程，其目的是检验它是否满足 规定的需求或是弄清预期结果与实际结果之间的差别( p a t t o n ，2 0 0 6 ) 。 对软件执行测试就必然要为其提供测试输入，即软件测试工程师所做的测 试用例设计，这是软件测试的核心问题。设计测试用例即编写用于输入的实际 数值和预期输出结果数值。软件测试的好坏很大程度上取决于测试用例的数量 和质量。测试用例的数量直接影响测试的工作量和成本，而测试用例的质量直 接影响软件测试的效果，并最终影响软件产品的质量。软件测试中的原则之一 即是“完全测试程序是不可能的”，因为测试输入空间往往是无限大的。加之受 软件开发周期的限制，在有限的时间里，设计尽量多且有效的测试用例，充分 发掘软件中的错误和缺陷，完成最有效的测试是从业人员的测试目标。 在最小的测试用例数下达到最优的测试效果无疑是最令人满意的。但当前 软件测试存在这样一对矛盾：高质量的测试用例通常需要手工构造，耗时过长； 自动化生成测试用例数量充足、耗时少，但冗余测试过多，有效测试用例过少。 2 第l 章绪论 综上所述，设计实现种高质量的测试用例自动化生成工具，对于增强软 件测试的自动化程度，提高软件测试的效率和质量具有重要的研究意义和应用 价值。 1 2 随机测试与程序不变量 1 2 1 随机测试 随机测试是通过在程序输入域上随机选择输入数据来测试程序。它是一种 应用广泛且极具潜力的软件自动化测试技术。在第2 9 届软件工程国际会议 ( i c s e 2 0 0 7 ) 上，随机测试被认为是测试用例生成领域最具潜力的三大技术之 一( b e r t o l i n o ，2 0 0 7 ) 。在软件工程方面，随机测试已被广泛应用到各领域，如 u n i x 工具集、w i n d o w sg u i 应用软件、j a v a 程序等等。 随机测试的优点突出表现在： 1 ) 随机测试的自动化程度极高，易于执行。利用有效的伪随机数生成算法， 可以很容易的生成大量的测试数据，只需要很少或者完全不需要手工操 作( h a m l e t ，1 9 9 4 ) ； 2 ) 随机测试能够有效揭示软件错误。众多研究表明，随机测试能够发现许 多其它测试技术不能发现的错误，有其它测试方法所无法比拟的优秀表 现。如美国宇航局n a s a 对火星登陆器上的一个文件系统进行了许多测 试后，使用随机测试工具仍然发现了几个未知错误； 3 ) 随机测试有生成最多的有效测试用例的潜力。随机测试用例可选空间是 最大的，甚至涵盖了所有有效的测试用例子空间。相比于其它测试用例 生成方法，随机测试理论上有更大的潜力产生更好的测试用例集合： 4 ) 随机测试能够避免测试人员的主观偏见。很多情况下，软件错误的引入 是由于开发人员的主观偏见。而随机测试中的测试数据随机产生，没有 人为的干预，使得测试数据完全不受测试人员主观偏见的影响，在一定 程度上保证了测试的充分性。 尽管如此，随机测试的缺点也非常明显： 1 ) 随机测试的代码覆盖率低。测试覆盖率是衡量测试充分度的重要指标。 由于测试输入随机产生，很多情况下，随机测试难以保证对程序代码的 高覆盖率。比如，条件语句“i f ( x 一5 ) t h e n ”，当x 采用随机值时， 该条件语句通过的可能性只有l 2 3 2 ； 2 ) 随机测试会生成大量的非法或无用测试数据。很多程序对输入数据都是 3 第1 章绪论 有约束或限制的，而随机测试会忽略这些约束，从而生成大量的非法测 试数据。比如，对于一个折半查找程序，其输入要求是己排序数组，而 随机测试用例生成器则几乎不可能生成合法的测试输入； 3 ) 随机测试会生成大量的等价输入，冗余用例过多。划分测试是将程序的 输入空间按一定规则划分为几个子集，并从子集中各取一个或几个代表 数据进行测试。而随机测试可以看作是一种特殊的，完全退化的划分测 试，即输入空间被划分为一个子集，即不做划分。划分测试的一大优点 便是尽可能地规避冗余测试，使得测试更有针对性，而随机测试则最大 程度的将这一优点弱化； 4 ) 随机测试用例往往过长。较长的测试用例发现错误的能力固然更强，但 是测试用例过长则大大增加了测试人员调试和定位错误的工作量，相对 来说，简洁明了的测试用例更利于测试人员的工作。 综上所述，随机测试是一种自动化程度高且潜力巨大的测试用例生成技术， 但覆盖率低、冗余测试过多等缺点阻碍了随机测试的应用。因此，在充分发挥 随机测试优点的基础上，研究一种高质量的随机测试用例生成技术具有良好的 学术意义和应用前景。 1 2 2 程序不变量 程序不变量是指在程序的某个特定的点或某些特定的点上保持为真的属 性，是描述在程序运行时保持不变的性质的逻辑断言；它经常出现在断言声明 ( a s s e r ts t a t e m e n t ) 、形式化描述( f o r m a ls p e c i f i c a t i o n s ) 、说明文档 ( d o c u m e n t a t i o n ) 中( e r n s te ta l ，2 0 0 7 ) ，形如表1 1 所示： 表1 1 程序不变量示例 1 f i e l d a b s ( y ) 2 y = 2 串x + 3 3 a r r a ya i ss o i r t e d 4f o ra l ll i s to b j e c t s1 s t ，1 s t n e x t p r e v = 1 s t f o ra l lt r e e n o d e o b j e c t sn ， n 1 e f t v a l u e p c o n t e n ti nm y a r r a y 程序不变量有助子软件开发人员理解程序中的数据结构、算法及各种操作， 对软件的设计、编码、验证、测试、优化和维护等各阶段都有着积极的作( e r n s t ， 2 0 0 0 ) 。近年来程序不变量的自动提取技术成为研究热点之一。 4 第1 章绪论 1 ) 程序不变量描述程序执行的特点，可提供程序操作、算法和数据结构相 关的说明文档。自动提取的程序不变量还可以保证文档的不断更新。 2 ) 程序不变量可避免引入错误。不变量能够标识在软件版本更新中需要保 持不变的程序属性，可以断言或说明文档的形式出现，这样就可以提醒 后期加入的开发人员避免引入改变这些不变量的错误。 3 ) 程序不变量为程序验证提供新的思路。以往的程序验证往往需要人工设 定验证目标，而不变量自动提取技术则解决了这一问题。自动提取的不 变量提供验证目标，程序验证技术则对不变量的准确性进行验证，两者 互相补充。 4 ) 程序不变量可用于调试和定位错误。使用自动提取技术获得程序正确执 行和失败两种情况下的不变量，并对这两种不变量进行比较，分析其中 的不同点，可帮助开发人员调试并定位错误。 5 ) 程序不变量可有效指导软件测试。比如，事先知道“x = y 这一不变量 约束条件，在设计测试用例时，便会更有针对性的生成诸如“x = 5 ，y = 5 的输入数据。通过运行程序本身而获取的动态程序不变量，能够很好的 揭示测试用例真实的执行情况，反应出测试用例对程序的影响。例如， 不变量“x 5 ”则表明小于等于5 的测试数据可能尚未测试。可以通过 对前置条件的违反来丢弃无用测试用例，对后置条件的违反来判断测试 失败，对不变量的置反来补充更优的测试用例。动态程序不变量的这种 揭示作用大大有益于测试用例的生成和优化，有助于从大量的随机测试 数据中筛选最有价值的子集，提高随机测试的质量。 研究发掘程序不变量对软件测试技术的作用，可以为软件测试，特别是测 试用例生成方面提供新的研究思路，具有积极的学术意义和广阔的应用价值。 1 3 现状分析及发展趋势 1 3 1 软件测试发展现状及未来 软件测试可以说是伴随着软件的产生而产生的。早期的软件规模较小、复 杂程度低，软件开发过程混乱无序、较为随意。测试的含义相对狭窄，而且开 发与测试也尚未明显的分化。开发人员将测试等同于“调试 ，目的是纠正软件 中的已知错误，常常由开发人员自己来完成这部分工作。对测试的投入极少， 测试介入也较晚，常常是等到形成代码，产品已经基本完成时才进行测试。 2 0 世纪7 0 年代，这个阶段开发的软件仍然不复杂，但人们已开始思考软 5 第1 章绪论 件开发流程的问题，并涌现出一批软件测试的宗师。1 9 7 2 年，软件测试领域的 先驱b i l lh e t z e l 博士，在美国的北卡罗来纳大学组织了历史上第一次正式的关 于软件测试的会议。1 9 7 3 年，他首先给软件测试定义：“就是建立一种信心， 认为程序能够按预期的设想运行。”1 9 8 3 年他又将定义修订为：“评价一个程序 和系统的特性或能力，并确定它是否达到预期的结果。软件测试就是以此为目 的的任何行为。 而另一位持不同观点的软件测试代表人物g l e n f o r dj m y e r s ， 于1 9 7 9 年提出了他对软件测试的定义：“测试是为发现错误而执行的一个程序 或者系统的过程。”除此之外，m y e r s 还给出了与测试相关的三个重要观点，那 就是： 测试是为了证明程序有错，而不是证明程序无错； 一个好的测试用例是在于它能发现至今未发现的错误； 一个成功的测试是发现了至今未发现的错误的测试。 2 0 世纪9 0 年代，软件产业迅猛发展，软件规模变的非常大，在一些大型 软件开发过程中，测试工作需要花费大量的时间和成本，而当时的测试手段几 乎完全都是手- r n 试，测试效率非常低，甚至存在很多通过手工方式无法完成 测试的情况。于是，各种商业化和开源测试工具开始出现，并逐步细化为性能 测试、功能测试、单元测试、缺陷管理、静态分析工具等等。测试工具已经成 为当今软件测试必不可少的部分，许多公司甚至都会自己开发测试工具。测试 工具的产生和发展，大大提高了软件测试的自动化程度，让测试人员从繁琐和 重复的测试活动中解脱出来，专心从事有意义的测试用例设计等活动。在大多 数情况下，软件测试自动化可以减少开支，增加有限时间内可执行的测试，在 执行相同数量测试时节约测试时间。 现如今，软件测试在理论研究和工业应用方面都得到了前所未有的发展。 国内外的科研人员利用模型检验( m o d e lc h e c k i n g ) 、约束求解( c o n s t r a i n t s o l v i n g ) 、符号执行( s y m b o l i ce x e c u t e ) 等技术，围绕测试用例优化，错误发 现等问题进行了广泛的研究探索，取得一定的成果。近些年多核系统与云计算 的兴起，使得并行分布式系统测试成为研究热点。以l o a d r u n n e r ，r a t i o n a l r o b o t ，p c l i n t 为代表的许多知名商业化测试工具受得了众多大公司的青睐， 开源社区也在各自擅长的领域提供了很多优秀的软件测试解决方案。 尽管软件测试经历了几十年的发展历程，但至今依然没有形成一个足以支 撑该领域的统一的测试理论，在工业应用中也始终没能达到1 0 0 的自动化测 试。特别是，研究人员在测试用例生成领域投入了巨大的精力，但在工业应用 方面成果有限，大部分测试用例生成还需要手工完成( b e r t o l i n o ，2 0 0 7 ) 。因此， 软件测试在理论研究和工业应用方面都依然还有广阔的提升空间。 6 第l 章绪论 1 3 2 随机测试发展现状及未来 随机测试用例生成研究最早可以追述到1 9 7 0 年h a n f o r d 关于p l i 编译器随 机测试用例生成器的实现的论文。1 9 8 3 年b i r d 等人的论文中描述了一个带“自 我检验 的随机测试用例生成技术，该技术除了生成测试输入之外，还检验输 出是否符合预期。在b i r d 之后，许多随机测试用例生成技术被开发应用于编译 器、文件系统、g u i 和面向对象程序测试等等众多领域( p a c h e c o ，2 0 0 9 ) 。 其中，m i l l e r 等人提出的“模糊测试”( f u z z i n gt e s t i n g ) 最为知名。他们利 用随机生成的a s c i i 字符流测试u n i x 工具集的异常行为。之后他们又将模糊 测试扩展，以生成键盘和鼠标事件的随机序列，并在x w i n d o w s ，w i n d o w sn t ， m a co sx 系统中发现了错误。现在模糊测试已有了很多的工业应用，被广泛的 用于发掘规范和协议中的安全漏洞。 另外，g r o c e 等人对n a s a 的一项太空任务中的文件系统进行随机测试， 并发现了十几个足以危及任务成功的错误。c l a e s s e n 等人开发的随机测试工具 q u i c k c h e c k 可以检查h a s k e l l 程序中用户自定义的正确属性，并证明了随机测 试技术的有效性。 最近，又陆续出现了面向对象的随机测试工具。美国德州大学阿灵顿分校 的c h r i s t o p hc s a l l n e r ( 2 0 0 4 ) 开发了j a v a 软件自动化随机测试工具j c r a s h e r 。 麻省理工学院m i t 的c a r l o sp a c h e c o 博士开发了针对j a v a 和n e t 的开源的随 机测试用例自动生成工具r a n d o o p ，且2 0 0 8 年已经被微软n e t 开发组采用。 本文第二章将对j c r a s h e r 和r a n d o o p 做较为详细的分析。 法国学者c a t h e r i n eo r i a t ( 2 0 0 5 ) 开发的j a r t e g e 和苏黎世理工学院的 a u t o t e s t 工具可以生成随机函数调用，但需要用户提供形式化描述( j m l e i f f e l ) 来判断测试输入是否能够揭示程序错误。 自适应随机测试( a d a p t i v er a n d o mt e s t i n g ) 是一种更加平滑的测试用例生 成技术。在给定的测试用例集中，随机选取第一个测试用例，并从集合中删除。 之后从测试用例集选取的测试用例都是与上一个选取的测试用例最远的那个。 c i u p a 等人( 2 0 0 8 ) 证明了自适应随机测试技术能够更快的发现错误。 随机测试与其它技术的结合也被认为是一种有前途的方向。d a r t ( d i r e c t e d a u t o m a t e dr a n d o mt e s t i n g ) 将符号执行与随机测试相结合，实现了单元测试的 自动化，但只能处理整型数据( g o d e f r o i de ta l ，2 0 0 5 ) ：而c o n c l i ct e s t i n g 则将约 束求解与随机测试结合( m a j u m d a ra n ds e n ，2 0 0 7 ) 。 相对来说，国内在随机测试领域涉足较少，但也取得了一定的研究成果。 7 第1 章绪论 陈宗岳等( 2 0 0 6 ) 研究了失效区域的紧致程度与适应性随机测试的性能之 间的关系。适应性随机测试是一种测试用例分布更加平滑的增强型随机测试方 法。文中证明了适应性随机测试的性能随着失效区域的紧致程度的增强而提高， 进一步地揭示了适应性随机测试优于随机测试的基本条件。 沈海华等( 2 0 0 9 ) 全面总结了覆盖率驱动的随机测试生成技术的研究历程、 现状和分类。覆盖率驱动测试的目标是通过覆盖率指导测试向量生成，减少重 复测试，加速验证的收敛过程，提高验证的自动化程度和效率。 徐伟等( 2 0 0 9 ) 在研究基于u m l ( u n i f i e dm o d e l i n gl a n g u a g e ，统一建模语 言) 活动图产生测试用例的基础上，提出了一种基于分类树的随机测试用例产 生方法( c t 2 i 玎) 。运用分类树分析已运行测试用例的输入域，指导产生新的测 试用例。 综上所述，随机测试是一种研究基础较好、且极具应用潜力的优秀测试技 术。 1 3 3 不变量现状及未来 由于不变量在程序验证和测试方面的重要作用，和人工提取程序不变量的 繁琐，其自动提取技术和应用研究吸引了越来越多的科研人员。国外近十年的 研究已经积累了一定的经验，而国内研究也正在起步。 当前有很多著名大学的研究小组在进行软件验证时的主要思想就是验证程 序是否满足不变量。如果在程序各点都严格满足了不变量的要求即可保证软件 的正确性。长久以来国内外都是依靠人工提取不变量，这是一项极其费时费力 且对操作人员有极高要求的工作，既要对源程序有深入了解又要有严谨的逻辑 思维。所以实现程序不变量的自动提取将大大减少研究人员的工作量，提高工 作效率。 文献( e r n s t ，2 0 0 0 ) 指出，有关动态不变量提取技术的最早研究起源于斯洛 文尼亚的i v a nb r a t k o 和m a r k og r o b e l n i k p 上世纪9 0 年代初，他们利用i l p ( i n d u c t i v el o g i cp r o g r a m m i n g ) 在一些特殊的循环体执行中由变量值来构造循 环不变量，不久之后也有其他几个i l p 系统来推断不变量，现在已经没有研究 继续跟进。 文献( e r n s t ，2 0 0 0 ) 还进一步提到：1 9 9 4 年b o g o n gs u 等人提出的r u n t i m e d i s a m b i g u a t i o n 技术能够检测指针别名；1 9 9 7 年加州大学圣迭哥分校的b r a d c a l d e r 等人提出的v a l u ep r o f i l i n g 能够检测常量、近似常量或指令操作数；1 9 9 8 年m a n d a n av a z i r i 等人则讨论了变量间大小关系的检测。 当前最成熟的不变量提取工具是麻省理工学院的d a i k o n 工具( e r n s te ta l ， 第1 章绪论 19 9 9 ，2 0 0 0 ，2 0 01 ，2 0 0 7 ) 。m i t 的程序分析组p a g ( p r o g r a ma n a l y s i sg r o u p ) 早 在1 9 9 8 年至今一直从事不变量领域的研究和开发，所公布的不变量提取工具 d a i k o n 是目前研究最成熟、评价最高、应用最广且开源的工具，并始终保持更 新。d a i k o n 可以应用于c ，c + + ，e i 疏l ，i o a ，j a v a ，p e r l 程序，而且能够容易地扩 展到其它应用中。d a i k o n 首先对源程序进行预处理，然后运行该程序，通过监 测运行中程序的各数值的关系，在模板库中进行匹配，以此来推断似然不变量 ( 1 i k e l yi n v a r i a n t ) 。 2 0 0 8 年乔治亚理工学院的c h r i s t o p hc s a l l n e r 等人( 2 0 0 8 a ) 实现了不变量 提取工具d y s y 。他们利用动态符号执行技术从n e t 程序中提取不变量信息， 使获取的不变量更符合程序本身。 程序不变量在软件的设计、编码、测试等各阶段都有重要作用，因此其应 用研究也吸引了很多研究人员和机构。 2 0 0 2 年斯坦福大学开发出了基于不变量提取的软件错误检测工具d i d u c e ( h a n g a la n dl a m ，2 0 0 2 ) 。d i d u c e 能够有效的帮助程序员检测复杂程序中的 错误并判断错误根源。d i d u c e 监测运行中的程序，并假定程序中应该满足的 不变量，并以与不变量的冲突为根据来判定软件错误。d i d u c e 可以检测j a v a 程序并且已经成功在四个大型的复杂项目上进行了测试，在需要耗费经验丰富 的程序员数天才能发现错误的j s s e 库中，d i d u c e 表现突出。2 0 0 6 年，普度 大学针对c 语言重新实现了c d i d u c e ( f e ia n dm i d k i f f