（计算机软件与理论专业论文）基于sa规则的全路径用例自动生成方法研究.pdf

硕士学位论文 m a s t e r st h e s i s r e s e a r c ho fa u t o m a t i ct e s tc a s e sg e n e r a t i o n o ff u l lp a t hb a s e do ns ar u l e at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em s d e g r e ei nc o m p u t e rs o f t w a r ea n dt h e o r y b y c u ih u a n h u a n p o s t g r a d u a t ep r o g r a m c o m p u t e r s c i e n c ed e p a r t m e n t c e n t r a lc h i n an o r m a l u n i v e r s i t y s u p e r v i s o r ：c h e nl i a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e a p p r o v e d m a y , 2 0 1 1 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名崔叹娠 日期：2 d j ) 年占月妨日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：膛则之砜 日期：州1 年5 月谚日 导师签名： 日期：加， 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的规 定享受相 作者 日期 硕士学位论文 m a s t e r st h e s i s 摘要 测试用例是软件测试技术中的核心角色，测试用例的人工生成不能满足现代软 件开发的需要，使得测试用例自动生成成为研究热点。在测试用例自动生成方法中， 有基于规格说明和基于结构两种生成的方法。人工智能技术：粒子群优化算法、遗 传算法、b p 神经网络算法、混沌理论等也被用于对测试用例自动生成的研究。路 径测试是白盒测试中覆盖强度最强的测试，因此基于结构的路径测试用例自动生成 一直受人关注。目前，对单路径测试用例自动生成方法的研究较多，在文献中采用 了最常见的单路径测试用例自动生成方法，如：随机法、动态法和符号执行法等。 全路径是程序的所有可能路径，如果能对程序的所有可能的路径都进行测试则称为 全路径测试，单个函数中全路径测试的优点是：测试不需指定路径，因为指定路径 本身就比较麻烦；全路径的测试用例覆盖了该程序的所有可执行路径，比较全面的 测试了程序的可行路径；对于庞大的程序结构进行人工的穷举路径不可取，因此如 何设计出一种基于全路径的搜索方法对实际应用具有重大意义。在论文中以单个函 数的全路径为背景，研究测试用例自动生成的方法。 本文设计了一个基于s a ( s o u r c e a n a l y s i s ) 规则的全路径测试用例自动生成系 统的框架。这个框架主要由：初始化组件、程序解析组件、优化组件和结果分析组 件四部分组成。论文对程序解析组件和优化组件的功能和算法实现进行了较详细地 讨论。程序解析组件的工作主要有两个：一是对测试目标进行静态解析，主要着重 于源程序的语义分析和语法分析；二是运用s a 规则对源程序进行逐行解析，按照 关键字分析程序的结构并插装相应的节点，插装的目的是记录执行的语句，得到有 向无负权图和插装后的目标函数。s a 规则中制定了构造源程序的有向无负权图的 方案，有向无负权图可以排除源程序的回路，简化源程序中的路径。优化组件的工 作主要有三个：一是不重复路径集的获取，在有向无负权图上搜索所有不重复的路 径，并且存放到不重复的路径集合中；二是将初始化的测试数据放到插装后的源程 序中执行，得到测试数据的实际执行路径；三是计算已执行路径的相似度，在本工 作中，制定了使用粒子群优化算法选择测试用例集的方案。若满足预先设定的阈值， 则此组测试数据即为较为合适本程序的测试用例，若不满足，则继续使用粒子群算 法进行调整。 本文通过一个具体的测试用例自动生成的例子，证明基于s a 规则的全路径测 试用例自动生成方法是可行的。 硕士学位论文 m a s t e r st h e s i s 关键词：全路径测试用例；粒子群优化算法；静态解析；s a 规则；不重复路 径搜索算法；路径相似度 a b s t r a c t t e s tc a s e sp l a yac a 3 r er o l ei ns o t t w a r et e s t i n g , t h em a n u a lg e n e r a t i o no ft e s tc a s e s 啪n o tm e e tt h en e e d so fm o d e ms o f t w a r ed e v e l o p m e n t , m a k i n gt h e a u t o m a t i c g e n e r a t i o n o ft e s tc a s e sb e c o m ear e s e a r c hh o t s p o t t h e r e a r ct w om e t h o d s ， s p e c i f i c a t i o n - b a s e da n ds t r u c t u r e b a s e di na u t o m a t i cg e n e r a t i o no ft e s t c a s e s a r t i f i c i a l i n t e l l i g e n c e ：p a r t i c l e s w a l l l lo p t i m i z a t i o n , g e n e t i ca l g o r i t h m s ，b pn e u r a l n e t w o r k a l g o r i t h m ，c h a o st h e o r y , a l s ob e u s e df o ra u t o m a t i cg e n e r a t i o no ft e s tc a s e s p a t ht e s t i n g i st h es t r o n g e s tc r i t e r i a i nt h ew h i t eb o xt e s t i n g ，5 0t h es t r u c t u r e - b a s e da u t o m a t i c g e n e r a t i o no ft e s tc a s e s i sa l w a y sb e e no fc o n c e r n c u r r e n t l y , a u t o m a t i ct e s t c a s e s g e n e r a t i o nm e t h o d s o fs i n g l e - p a t ha r em o r eu s e d i nt h el i t e r a t u r el i s t e dt h em o s t c o n o na u t o m a t i ct e s te a s e sg e n e r a t i o nm e t h o d so fs i n g l e - p a t h , s u c ha s ：r a n d o m ， d y n a m i cm e t h o da n ds y m b o l i ce x e c u t i o nm e t h o d f u l lp a t hi s t h ep r o g r a mo fa l lt h e p o s s i b l ep a t h s i nt h ep r o g r a m ，i fa l lt h ep o s s i b l ep a t h sh a v eb e e nt e s t e di sc a l l e dt h ef u l l p a t ht e s t i n g i ns i n g l ef i l e ，b a s e do n t h ef u l lp a t ho ft e s t i n g sa d v a n t a g e sa r e - t e s tw i t h o u t s p e c i f y i n gt h ep a t h ，b e c a u s et h es p e c i f i e dp a t hi t s e l fi sm o r e t r o u b l e ；t e s tc a s e so ff u l lp a t h c o v e ra l lt h ee x e c u t a b l ep a t ho ft h ep r o g r a m , t e s t i n gt h ef e a s i b l ep a t hi nt h ep r o g r a m m o l ec o m p r e h e n s i v e l y ；t oc o m p u t ea l lp r o c e s sp a t h sf o rc o m p l e x s t r u c t u r ei sn o t d e s i r a b l e s 0h o wt od e s i g nas e a r c hm e t h o db a s e d o i lf u l lp a t hh a sg r e a ts i g n i f i c a n c ef o r p r a c t i c a la p p l i c a t i o n t h i sp a p e rd e s i g n sas y s t e mf r a m e w o r kb a s e do ns a ( s o u r c ea n a l y s i s ) r u l e a u t o m a t i ct e s tc a s e sg e n e r a t i o nm e t h o d s o ff u l lp a t h t h e f r a m e w o r ki n c l u d i n g ： i n i t i a l i z a t i o nc o m p o n e n t s ，p r o g r a ma n a l y s i sc o m p o n e n t , o p t i m i z i n gc o m p o n e n ta n d r e s u i ta n a l y s i sc o m p o n e n t , f o u rp a r t s p a p e rm a d eam o r ed e t a i l e d d i s c u s s i o na b o u t p r o g r a ma n a l y s i sc o m p o n e n ta n do p t i m i z i n gc o m p o n e n t s f u n c t i o na n da l g o r i t h m p r o g r a ma n a l y s i sc o m p o n e n th a st w om a i nt a s k s ：f i r s t , m a k eas t a t i ca n a l y s i sf o rt e s t o b j e c t i v e s t h em a i nf o c u so n t h es o u r c eo ft h es e m a n t i ca n a l y s i sa n ds y n t a xa n a l y s i s ；t h e s 。c o n di su s i n gs ar u l et oa n a l y s i st h es o u r c ep r o g r a ml i n eb yl i n e ，u s ek c y w o r dt o a n a l y s i ss t r u c t u r eo ft h ep r o g r a ma n dp l u gt h ea p p r o p r i a t en o d e ，t h ep u r p o s e o fp l u gt h e a p p r o p r i a t en o d ei st or e c o r ds t a t e m e n te x e c u t i o n ，g e ta d i r e c t e dg r a p hw i t hn o n n e g a t i v e w e i g h t sa n dt h eo b j e c tf u n c t i o nw h i c hh a sb e e np l u g g e d s ar u l e s h a v ed e v e l o p e d 硕士学位论文 m a s t e r j st h e s i s s 0 i u t i o nf o rc o n s t r u c t i n gs o l u t i o na b o u t $ o u r t ? 冶c o d e sd i r e c t e d g r a p hw i t hn o n n e g a t i v e w e i g h t s ，d i r e c t e dg r a p hw i t hn o n n e g a t i v ew e i g h t ss o l u t i o nc a ne x c l u d el o o p si ns o u r c e p r o g r a m ，a n ds i m p l i f yt h ep a t ho ft h es o u r c ep r o g r a m o p t i m i z a t i o nc o m p o n e n th 嬲t t a s k s ：f i r s t , g e tt h en o n 。r e p e t i t i o np a t h , t os e a r c hf o ra l lt h en o n - r e p e t i t i o np a t hi nt h e d l r e c t e dg r a p hw i t hn o n n e g m i v e w e i g h t s ，a n ds t o r et h ep a t ht ot h es e to fn o n - r e p e t i t i o n ； s e c o n d ，p u tt h ei n i t i a l i z e dt e s td a t ai n t os u r c ep r o g r a mw h i c hh a sb e e n p l u g e dt oe x e c u t e g e tt h ea c t u a le x e c u t i o np a t ho ft e s td a t a ；t h i r d , c a l c u l a t et h ec o v e r a g eo f 比e x e c u t e d p a t h , mt h i sw o r k , h a sd e v e l o p e ds o l u t i o nu s i n gp a r t i c l es w a r mo p t i m i z a t i o na l g o r i 岫t 0 s e l e c tt h es e to ft e s tc a s e s f li tm e e t st h ep r e s e tt h r e s h o l d ，t h e nt h i sg r o u po ft e s t i s t h em o r e a p p r o p r i a t et e s tc a s e so ft h i sp r o g r a m ，i fn o tm e t ，c o n t i n u et ob ea d j u s t e du s i n g t h ep a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m i nt h i sp a p e r , b yt h ep r o c e s so fa a u t o m a t i ct e s tc a s e sg e n e r a t i o n , t ov e r i f yb a s e do n s ar u l e sa u t o m a t i cg e n e r a t i o nt e s tc a s e so ff u l lp a t hi sf e a s i b l e k e yw o r d s ：f u l lp a t ht e s tc a s e ；p a r t i c l es w a r m o p t i m i z a t i o n ；s t a t i ca n a l y s i s ；s a r u l e ；n o n - r e p e t i t i o np a t hs e a r c ha l g o r i t h m ；p a t hs i m i l a r i t yc a l c u l a t i o n 硕士学位论文 m a s t e r st h e s i s 目录 摘 要i a b s t r a c t 第1 章绪论。 l 1 1 研究背景及意义l 1 2 国内外研究现状2 1 3 论文的研究内容和主要工作2 1 4 论文的组织结构3 第2 章相关技术和方法 5 2 1 软件测试基本理论5 2 1 1 白盒测试技术6 2 1 2 路径测试技术8 2 1 - 3 自动化测试技术8 2 2 粒子群优化算法9 2 3 本章小结。1 1 第3 章基于规则的全路径测试用例生成方法设计1 2 3 1 系统的框架1 2 3 2 解析规则的建立1 4 3 2 1 静态解析15 3 2 2s a 规则19 3 3 不重复路径搜索算法2 2 3 4 路径相似度的计算2 4 3 5 本章小结2 4 第4 章实验结果及分析2 6 4 1 验证对象2 6 4 2 实验过程2 7 4 3 实验结果及分析3 0 硕士学位论文 m a s t e r st h e s i s 4 3 1 设计思路3 0 4 3 2 算法分析3 0 4 3 3 算法比较3 2 4 4 小结3 3 第5 章总结和展望3 4 5 1 总结。：3 4 5 2 进一步的研究工作3 5 参考文献 硕士期间发表的论文和参与科研项目3 8 致谢3 9 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景及意义 第1 章绪论 软件测试是为了发现程序中潜在的错误而去执行的过程【1 1 。出现软件之后，由 于软件开发及维护的成本居高不下，使得软件危机时时都存在着，例如，美国的“水 手一号”飞船的飞行失败，及“阿里亚娜5 ”火箭的首发失败，原因都是由软件故障引 起的1 2 1 。多年来，很多的国f l j b 的专家学者为设计高效的测试用例上煞费苦心。完 美的软件是不存在的，但可以通过测试的手段降低软件中的b u g 。随着人们对软件 测试重要性认识日趋深刻，软件测试在整个软件开发周期中的比例越来越大。有些 重要的软件的测试费用是工程阶段费用的3 5 倍 3 1 。因此，对于公司而言，软件测 试直接关系到核心竞争力的提高、软件生产过程的改进以及公司利润的增加。 软件测试包括白盒( 删t eb o x ) 测试和黑盒( b l a c kb o x ) 测试两种。白盒测 试，也称逻辑测试，它需要测试人员对程序的内部结构非常了解，然后设计一定的 测试用例去对目标进行测试。黑盒测试，也称功能测试，它不需测试人员对软件的 逻辑结构有所了解，只需将测试对象看作一个黑盒子，然后根据规格说明书的要求 来比对是否所有的功能已实现。本文属于白盒测试的范畴。白盒测试的测试方法有 代码检查法、逻辑覆盖法和基本路径测试法。其覆盖标准包括：逻辑覆盖、基本路 径测试、循环覆盖。白盒测试方法中应用最广的方法是基本路径测试法，它是在分 析程序的逻辑结构的基础上得到基本路径的集合，然后去设计相应的测试用例的方 法。但基本路径测试法有一个缺点，它有一部分工作需要依靠人工去做，即导出控 制流图和计算环路复杂度。这样就降低了测试用例生成的效率。本文提出的s a 规 则可以避免这一缺陷。 程序设计的方法主要有面向过程和面向对象两种。无论是面向过程还是面向对 象都是基于结构的方式进行程序设计，面向对象只是将结构化的程序进行了封装， 为的是方便程序员理解。归根到底，程序的基本结构仍然没有发生任何改变。由于 基于结构的程序是其它编程语言的基础，所以仍具有研究价值。结构化的软件测试 最基本的方法是路径测试，它是通过指定特定的路径，然后去在搜索空间内去找到 能满足此特定路径的测试用例。现阶段，一般采用的方法有线性谓词约束法、迭代 松弛法等等。 程序中路径的条数有时是天文数字，用人工的方式穷举去测试是不可取的，因 此，如何设计高效的算法去获取程序中数目庞大的路径是一直研究的热点。基于路 硕士学位论文 m a s t e r st h e s i $ 径的测试用例自动生成方法的研究，对于提高路径测试的效率、保证路径测试的质 量，提高软件测试的准确性和高效性有重要的实际应用意义，在上述背景下，本文 研究和探讨了c c + + 程序中基于路径的测试用例自动生成方法。 1 2 国内外研究现状 自从1 9 7 0 年以来，国外许多专家提出了很多研究测试用例自动生成的方法， 综合地来说，主要有两种：基于规格说明的测试数据自动生成方法与基于结构的测 试数据自动生成方法1 4 1 ，即非路径测试和路径测试两种。基于规格说明的测试用例 的自动生成主要从软件的规格说明出发，选择满足要求的测试数据；基于结构的测 试用例的自动生成常以路径覆盖作为准则，进行测试数据自动生成的研究。人工智 能技术也常被用于对测试数据自动生成的研究工作中。基于结构的测试用例的自动 生成常采用路径测试法去自动生成用例。 在我国，路径测试数据自动生成一直是研究的热点。中国科技大学的陈天石博 士对演化算法的复杂性、分布评估算法的计算复杂性、动态优化问题下随时间可变 的变异率策略对经典演化算法的影响等进行了详细的研究。将人工智能技术应用到 软件测试领域【5 j ；中国科学技术大学的钱思佑博士扩展了g u i 事件交互架构得到了 事件与状态的关联模型，生成了g u i 测试用例，并对测试用例进行评判 6 1 ；华中科 技大学的江胜博士对多目标进化算法进行了改进【7 l ；武汉大学的夏启明博士提出了 软件测试过程管理中的复用策略，奠定了软件测试与评价复用策略基础吲；中国科 学技术大学的刑学智博士提出了将测试所共有的特征向t t c n 一3 测试模型进行转化 的方法【9 j ，取得了不错的效果。、 单路径测试和全路径测试是路径测试的两种分类。单路径是指程序中某条路 径。全路径是指程序中所有的路径，包括：不可行路径、可行路径。目前对于单路 径测试用例自动生成方法的研究较多，文献【1 0 】总结了最常见的单路径测试用例自 动生成方法。基于全路径的测试用例自动生成方法的研究一直在探索中。 1 - 3 论文的研究内容和主要工作 论文研究的主要内容如下： ( 1 ) 提出s a 规则：从研究大量的源代码为着眼点，以结构化的程序为主要研 究目标，针对各个结构如：i f 结构、f o r 结构、w h i l e 结构、s w i t c h 结构进行分析总 结，建立详细的解析规则。通过这一套解析规则，可以把静态的程序按照规则进行 分析。 2 硕士学位论文 m a s t e r st h e s i s ( 2 ) 有向无负权图的建立。运用s a 规则对源文件进行解析，将函数的入口作 为起始节点，函数出口作为终止节点，然后对每一行运用s a 规则，创建相应的节 点，从而得到一个有向无负权图。 ( 3 ) 不重复路径搜索算法。得到的有向无负权图，是源程序中可执行路径的 描述，本文设计了不重复路径搜素算法，通过对图的遍历，得到图的不重复路径集。 也就是源程序的可执行路径的简化路径。 ( 4 ) 粒子执行路径集的获取。将粒子放到程序中执行，必然会有一条或者有 几条执行的路径，那么路径所组成的集合，称为粒子执行的路径集。本文借用了谓 词函数插装的方法对分支节点进行记录。因本文是对图的节点进行插装，故执行路 径可从图中搜索得到。 ( 5 ) 运用粒子群实现测试用例的自动化优化选择，粒子群属于人工智能的领 域，粒子可以通过阈值的调整和有指导的学习实现自动适应。根据这一特征，我们 把粒子作为测试用例，根据自身调整实现测试用例自动生成。 ( 6 ) 将现有的全路径测试用例生成的方法与本文方法的比较。从数据上证明 本文方法的可行性，同时可以看到采用本文方法可使效率有所提高。 论文的主要工作： ( 1 ) 提出s a 规则来对单个文件中的源程序进行静态解析，同时在源文件中 插入图节点的对象，该对象是一个结构体，其中有一个属性用来记录在运行时是否 执行该分支，起到插装谓词的作用。静态解析与插入图节点对象的过程同时进行， 解析完后生成了源文件的有向无负权图和新的源程序。 ( 2 ) 提出一种n r p s ( n o n r e p e t i t i o np a t hs e a r c ha l g o r i t h m ) 算法对有向无负权 图进行不重复路径搜索，得到一个不重复路径集，记录此图中从开始节点到终止节 点的所有不重复的简单路径。 1 4 论文的组织结构 论文共分为五章。 第一章绪论。介绍了论文的研究背景及意义、基于结构的路径测试的研究现 状，并介绍了本论文的研究内容。 第二章相关技术和理论。本章对论文中涉及的一些相关技术以及理论基础做 一个综述。详细叙述了软件测试基本理论和本文所用到人工智能中的算法，包括： 白盒测试技术、路径测试技术、自动化测试技术、粒子群优化算法。 第三章基于s a 规则的全路径测试用例生成系统框架设计。首先叙述基于s a 3 硕士学位论文 m a s t e r st h e s i s 规则的全路径测试用例生成方法的系统架构和设计思想。然后详细讨论了各个组件 的实现过程中涉及到的算法设计和实现。包括s a 规则的建立、不重复路径的搜索 算法、已执行路径集的路径相似度。 第四章实验结果及分析。通过实验来验证本文思想的正确性；通过对本文的 算法进行分析和比较，验证本文方法的优劣。 第五章总结和展望。本章是论文的总结和展望，一方面对论文所作的工作进 行了归纳和总结，另一方面，也对本文框架设计的不足之处进行了说明，并对进一 步的研究工作进行了展望。 4 硕士学位论文 m a s t e r st h e s i s 第2 章相关技术和方法 2 1 软件测试基本理论 文献【4 】中提到软件测试是以软件形成过程的文档和数据，以及程序作为测试的 对象，去发现其中存在的错误的一个过程。测试按软件的开发阶段一般分为单元测 试、集成测试、确认测试、系统测试、验收测试五类。图2 1 显示了软件测试经历 的五个步骤。 图2 1 软件测试的过程 单元测试，也称模块测试，是对程序中的模块进行的测试，测试的目的是发现 各个模块中是否存在潜在的错误。单元测试的主要工作可以用图2 2 来说明。 图2 2 单元测试的主要工作 5 硕士学位论文 m a s t e r st h e s i s 集成测试常称作组装测试，是在单元测试的基础上将各个模块按详细设计说明 书与概要设计说明书的要求来进行组装的，并且考虑各个子功能之间的兼容性以及 全局数据结构是否正确，它的测试活动用图2 3 来表示。 图2 3 集成测试的活动 确认测试的任务是去验证软件的功能和性能是否与用户的要求一致。它是在模 拟的环境下，主要运用黑盒测试去验证软件是不是满足需求规格说明书中的需求。 系统测试是将一些相关的系统元素结合在一起，然后再在模拟或者实际环境中 进行的一系列的测试。 验收测试是按照和客户签订的合同或验收文档等进行的测试。 2 1 1 白盒测试技术 白盒测试通常采用两种方法，一种是静态的测试方法，一种是动态的测试方法 【l l 】。静态的测试方法，不需要去真正执行程序，只需人工的对软件进行分析、通过 使用工具来生成各类图形图表，从而清晰的分析系统的结构，检查软件的潜在b u g ； 动态的测试方法，需要设计测试用例去放到待测程序中执行，根据执行的结果去发 现程序中存在的错误。 动态测试方法的应用非常普遍，最常见的测试方法主要包括有以下几种：黑盒 测试、白盒测试1 2 l 。动态测试是白盒测试中会用到的测试方法，它的主要测试手 fx + 4 x 0 段是进行程序的插装。在这里，以分段函数j ，= 4 工：0 ，来说明插装方法的要 【- x + 4 x o t h e n y = x + 4 e l s e i fx = o t h e n ) 卸 e l s e ) ，= 一) 【+ 4 e n d i f e n di f p i n t y e n d 图2 4 插装后求分段函数值程序的流程图 7 硕士学位论文 m a s t e r st h e s i s 上述程序的流程图如图2 4 所示，图中的虚线框不是源代码所包含的，进行插 入操作是为了记录源代码中的包含的语句的执行次数。图中的虚线框所做操作的功 能是进行计数，它的形式为：c ( 0 - - c ( 0 + l i = l 一2 ，7 。程序从函数入口开始执行， 到函数出口结束。主要任务是记录该语句执行次数。若在程序的入口处插入了计数 器c ( d 初始化的语句，在出口处插入计数器的语句，这样就构成了一个完整的程序， 它可以很方便的记录并输出各个程序点中语句的实际执行次数。 2 1 2 路径测试技术 如何设计生成基于路径的测试用例是路径测试的核心所在，常用的方法有随机 法、试探法、线性谓词约束法、z 路径覆盖法。 随机法的基本思想是在变量的定义域内进行随机地取样，不受程序结构的控 制，迅速地生成大量的测试数据，但是这种方法比较容易受数据分布的影响，同时， 当输入空间是无穷的空间时，此方法通常不可行。 线性谓词约束法：它是通过线性的谓词函数来构造线性的约束系统，此算法主 要适用于路径中的分支谓词是线性约束的这种情况，对于非线性约束的路径，则需 要通过迭代多次的方式，才能找到较优的测试用例，这种情况下会使算法的效率大 大降低。 z 路径覆盖法：将路径中的一些次要因素略去不记，对循环机制进行简化它的 循环次数。但是这种方法在验证路径时所采用的探索移动法在探索路径时容易陷入 死循环。 上述几种方法常与人工智能的一些算法相结合，如遗传算法，粒子群优化算法， 实现动态地查找测试用例，其中最关键的是如何构造谓词函数和适应值函数，如果 适应值函数构造的合理，将会大大提高算法的效率，如果适应值函数构造的不恰当， 则会适得其反。 通常来讲，路径分为两种，单路径和全路径。由于全路径在实现上仍存在技术 难题，所以很多对于它的研究都处于启蒙和理论研究阶段。 2 1 3 自动化测试技术 自动化测试也是软件测试的一个重要组成部分，它能够完成手工测试无法完成 的工作，同时也可以提高软件的质量，并且能够节约经费。但是自动化测试的适用 范围也有一定的限制，这就需要测试工作者按照实际情况运用不同的测试方法。 8 硕士学位论文 m a s t e r st h e s i s 伴随着软件测试技术的发展，专家学者一直没有放弃过对自动化测试技术的研 究，由于软件测试本身的复杂性，使得对于自动化测试技术方法和理论的研究受到 较大的限制，曾经一度使人们怀疑自动化测试技术的发展前景，但是现阶段，自动 化测试技术的发展较之过去已经有了较大的进步，研究的热点主要有以下三个方 面：测试自动化的框架，在软件开发项目中软件自动测试与开发的融合仍是研究的 热点；测试自动化脚本技术，人们希望通过以脚本的形式去指导测试的自动执行来 提高测试的效率；测试用例的自动生成，是一个典型的数据驱动的测试技术，它是 自动化测试技术研究中的最为广泛的技术，通过与相关的智能技术相结合来加速测 试用例的生成，本文就是属于对测试用例自动生成的研究。 2 2 粒子群优化算法 k 和e 提出了粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ) 1 1 3 1 1 1 4 1 ，本文概述 性地对p s o 算法进行描述，该算法中将每一个个体看作在搜索空间中按一定的速度 来“飞行”的粒子，同时根据群体与个体的历史飞行经验，经综合分析后，来动态地 调整个体的飞行速度。在每一次迭代中，每一个粒子按照极值进行调整自己的位置 和速度，其中主要有两个极值，一个极值是p b e s t ，代表粒子自身最优值，另一个 极值是g b e s t ( 1 4 1 ，代表全局最优值。 假设粒子群在一个d 维空间中搜索，粒子的总数为疗，那么每个粒子的速度 和位置按如下公式，进行变化： 吻( f + 1 ) = ( f ) + q * r t p 凡) 一而( f ) ) + c 2 * r 2 ( g j ( t ) - x o c t ) ) ( 2 1 ) 而( h i ) = 而( f ) + ( t + 1 ) ( 2 2 ) p s o 优化算法的流程图如图2 5 所示。 9 硕士学位论文 m a s t e r st h e s i s 初始化种群 l i 7 计算每个粒子的适应度 士 记录每个粒子的当前最优值和全局最优值 7 赢冬y 更新粒子的速度和位置 上 最优解i ， 图2 5p s o 算法的流程 p s o 优化算法的流程： s t e p l建立粒子群以及相关的一些参数，定义一个粒子的结构体p a r t i c l e ，包 括它的速度，位置，粒子当前的适应度以及粒子历史上的最佳适应度； s t e p 2 初始化一个粒子群，然后用随机的方法来初始化粒子群中的各个粒子， 包括粒子的位置，速度，通常来说，将当前位置设为最佳位置，并且求 出每个粒子的适应度，并且将当前适应度设为最佳应适度； s t e p 3 计算粒子的适应度； s t e p 4 更新粒子，包括粒子的位置和速度，在p s o 优化的过程中粒子的速度和 位置用公式( 2 1 ) 和( 2 2 ) 来进行变化，由于粒子的速度和位置发生了变 化，这时就需要重新计算粒子的适应度；然后再更新粒子的p b e s t 与 g b e s t ； s t e p 5 检查适应度，或者是它的迭代次数，如果本次迭代中最优粒子的最佳适 1 0 硕士学位论文 m a s t e r 。st h e s i s 应度已经小于，或者等于预先设定的阈值，那么则停止迭代，如果迭 代次数达到最大的迭代次数，也同样停止迭代。 2 3 本章小结 本章对软件测试的基本理论和相关人工智能的算法进行了阐述。在本章中，对 路径和自动化测试技术进行了较为详细地说明。按顺序依次对白盒测试技术理论、 路径测试技术、自动化测试技术进行了介绍；在此之后，介绍了在测试用例自动生 成中最为简单和应用最广的优化算法一粒子群优化算法进行了细致地描述。 硕士学位论文 m a s t e r st h e s i s 第3 章基于规则的全路径测试用例生成方法设计 随着应用软件规模的急剧增大，使得传统的人工作业的方式不能满足较大规模 的软件开发需要，基于此背景来研究半自动化或者是自动化的软件测试工具的意义 重大。就目前来讲，业界还没有通用的商业软件，所以只有设计完善并且强大的测 试手段和方法，以及软件测试工具，才更能保证软件的质量。单元测试是最基本的 测试方法，它的测试对象是某单个过程或者函数，任务是去确认这个函数和过程的 正确性。结构化的程序是最为常见的程序设计方法，由于它大量的广泛使用，使得 路径测试仍是研究的热点。本文属于基于结构的测试数据自动生成方法的研究。基 于结构的测试数据自动生成方法最用的方法是采用路径测试数据自动生成的方法。 路径又包括单路径和全路径，本章主要讨论基于规则的全路径测试用例自动生成系 统的框架，其中包括解析规则的建立、相关的搜索算法、已执行路径覆盖度的计算 等等内容。 3 1 系统的框架 软件测试自动化和软件开发过程这两者是需要有个相互融合的过程，但是在现 今阶段，由于技术发展的局限性，自动化测试技术仍然很难与整个项目完全匹配， 这些实际问题的存在，为具有可塑性的自动测试模型的发展提供了契机，目前出现 了一些模型，例如a l t m 模型i l5 】将自动化测试生命周期和软件开发周期的各个融 合的角度进行了探讨，还有一些自动化测试框架模型 1 6 1 也分别从不同的角度来对自 动化测试框架进行了相关的设计。在文献 1 7 j q 丁对测试用例的定义是：为特定目标 而设计的测试输入、执行条件与期望输出结果的集合；为某一个测试项记录的特定 输入和预测结果、一组执行条件的集合。测试用例是由输入数据及与之对应的输出 结果来构成的，测试用例的好和坏对它测试的结果有着直接的影响，所以如何设计 高效的测试用例在测试过程中有着很重要的作用，白盒测试的测试类型主要包括： 语句覆盖、判断覆盖、条件覆盖、判断一条件覆盖、条件组合覆盖、路径测试，其中 路径测试是最强的覆盖准则，它是使程序中的每条路径都执行一次。通过上述比对， 可知测试数据自动生成采用路径测试的方法具有明显的优势。 先前对于测试用例自动生成的研究主要集中在对随机测试用例生成【l 8 j 【l9 j 的研 究，这种方法最大的缺点是容易产生大量的冗余数据，与之相比，较好的方法是启 发式测试用例自动生成方法，这个方法在效率上有了较大的提高 2 0 1 1 2 ，但它的实现 1 2 硕士学位论文 m a s t e r st h e s i s 技术有一定的难度，目前应用的范围不是很广。文献 2 2 1 提出的全路径测试数据自 动生成方法的求解步骤如下：s t e p l 手动导出源代码的控制流图g 。s t e p 2 计算图g 的环路复杂度v ( g ) 。s t e p 3 生成基本路径集p a t hs e t 。s t e p 4 自动生成测试用例。 由上述求解过程可知，文献 3 5 没有实现该程序的控制流图的自动导出，同时，该 文中没有给出相关的伪代码和相应的流程图来对全路径测试进行详尽的描述。本文 在此基础上提出一种基