（计算机应用技术专业论文）类状态测试用例自动生成方法与实现.pdf

独创性申明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学 位论文是我个人在导师指导下进行的研究工作及取得的成果。尽我所知， 除特别加以标注和致谢的地方外论文中不包含其他人的研究成果。与我 一同工作的同志对本文所论述的工作的任何贡献均已在论文中作了明确的 说明并已致谢。 本沦文及其相关资料若有不实之处由本人承担一切相关责任 论文作者签名：垂蜩塑l 牛年6 月瑁日 保护知识产权申明 本人完全了解西安理工大学有关保护知识产权的规定，即：研究生在 校攻读学位期问所取得的所有研究成果的知识产权属西安理工大学所有。 本人保汪：发表或使用与本论文相关的成果时署名单位仍然为西安理工大 学，无论何时何地。未经学校许可，决不转移或扩散与之相关的任何技术 或成果。学校有权保留本人所提交论文的原件或复印件，允许论文被查阅 或借阅；学校可以公布本论文的全部或部分内容，可以采用影印，缩印或 其他手段复制保存本论文。 ( 加密学位论文解密之前后，以上申明同样适用) 论丈作者签名：叁1 8导师签名：a 晦6 月强日 哗 摘要 类状态测试用例自动生成方法与实现 学科：计算机应用技术 作者：赵明 导师：张毅坤 职称：教授 答辩日期：2 0 0 4 7 作者签名 导师签名 摘要 目前计算机软件的规模越来越大，复杂度也不断提高，软件错 误造成的后果也就越来越严重，软件的质量和可靠性已引起人们的 高度重视。在现代软件工程中，软件开发的各个阶段，都应进行相 应的严格的质量评审和测试。软件测试成为软件质量保障的关键环 节。 类的状态测试反映了类中方法的交互特性以及动态特性，因此 类的状态测试是面向对象软件测试的关键部分。本文设计了状态测 试数据自动生成工具原型工具a t d g 4 s m ( a u t o m a t e dt e s t d a t a g e n e r a t o rf o rs t a t em a c h i n e ) 。a t d g 4 s m 通过设计u m l 规约的相应 语法，借助b i s o n + + 语法分析程序生成u m l 状态图分析器，汲取状态 图信息；采用中国邮递员算法生成全局最优测试序列：提出可执行 规约概念，综合利用规约测试和程序测试的优点来进行测试用例生 成；采用遗传算法生成最终测试数据。同时就关键性测试技术如程 序静态分析，插桩以及关键算法改进进行了详细的阐述，并给出 a t d g 4 s m 的设计框架，最后结合算例对设计思想进行分析及原型系统 验证。 关键字：类状态测试，测试用例自动生成，g a ，插桩，a t d g 4 s m 框架 该课题受陕西省教育厅科研基金资助编号：0 0 j k 2 6 5 渤 西安堙工大学硕士学位论文 t h em e t h o da n di m p l e m e n t a t i o no fa u t o m a t e dt e s tc a s e 鲫8 r a t 咖i o n h o f ，8 s s s谥tatesupervisor sn a m e z h a r n g a 筹k u n s z h a o m i n g s i g n a t u r t u r e e 黝0 ：y i i g n a t u r e 二么幺加卵多矽” s t u d e n t sn a m e ： 7 m 口 a b s t r a c t t h e s c a leo fe o m p u t e rs o f t w a r eh a sb e e nb a l l o o n e dg r e a t l ya n di t s c o m p l e x i t yh a sa l s oi n e r e a s e ds h a r p l yw h i c hb r i n ga b o u tt h em o r ea n d m o r es e r i o u se f f e c t s o f t w a r eq u a l i t yh a sa r i s e np e o p l e g h i g h a tc e n t i o o i nm o d e r ns o f t w a r ee n g i n e e r i n g ， e v e r ys t a g eo fs o f t w a r e d e v e l o p m e n ts h o u l dp r a c t i c ev e r ys t r i c tq u a l i t ye v a u a t i o na n dt e s t s o f t w a r et e s tb e c o m e st h ek e yj u n c t u r eo fs o f t w a r eq u a l i t ya s s u r a n c e t h es t 8 t eo fc 1 a s sr e f l e c t st h ep r o p e r t yo fi n t e r a c t i v ea n dd y n a m i e b e t w e e nm e t h o d s os t a t et e s ti st h ek e yp a r to f0 0s o f t w a r et e s t t h is p a p e rd e s i g n st h ep r o t o t y p eo fs t a t ea t l t o m a t e dt e s td a t ag e n e r a t i o n t o o l a t d g 4 s m ( i m p r o v e dt e s td a t ag e n e r a t o rf o rs r a t em a t h i f i e ) a t d g 4 s m a b s t r a c t st h eu m ls t a r ec h a r ti n f ob yv i r t u eo fb is o n + + g r a m m a rp a r s e r a n dt h ed e s i g no fc o r r e s p o n d i n gg r a m m a ro fu m ls p e c i f i c a t i o n ：c h i n e s e p o s t m a na l g o r i t h mi sa d o p t e dt og e n e r a t et h eg l o b a lo p t i m i z e dt e s t s e q u e n c e ：t h ec o n c e p to fe x e c u t a b i es p e c i f i c a t i o ni sa d v a n c e dw h i c h i n t e g r a t e st h ea d v a n t a g eo fs p e c i f i c a t i o nb a s e da n dp r o g r a mb a s e dt e s t c a s eg e n e r a t i o ns t r a t e g y ：a n df i h a l l yg ai su s e dt og e n e r a t et e s td a t a a 1s ot h ek e yt e s tt e c h n o l o g ys u c ha sp r o g r a ms t a t i ea n a l y s is ， i n s t r u m e n t a t i o na n dk e ya l g o r i t h mi sd i s c u s s e da n dt h ef r a m e w o r ko f a f d g 4 s misg i y e n f i h a l l yi n s t a n c esa r eg i v e nt oe x p r e s st h ed e s i g n t h e o r ya n dv e t i f yt h ep r o t o t y p e k e yw o r d s ：c l a s ss t a t et e s t ，a u t o m a t e dt e s tc a s eg e n e r a t i o n ，g a ， i n s t r u m e n t a t i o n ，f r a m e w o r ko fa t d g 4 s m 绪论 第一章绪论 1 1 选题背景 软件测试就是在软件投入运行前，对软件需求分析、设计规格 说明和编码的最终复审，是软件质量保障的关键步骤。其定义可简 略概括为：为了发现错误而运行程序的过程。随着软件规模的不断 扩大，软件质量问题已成为制约计算机发展的主要因素之一，作为 保证软件质量和可靠性的手段，软件测试起着不可替代的作用。 软件测试的关键之处在于测试用例的选取。但这项工作并非易 事。因为即使对于一般的程序，其执行路径和有效输入范围都可能 是个极大的数字。何况在选取测试用例时，测试者还必须考虑各种 无效的输入和各种输入序列，更何况软件的复杂程度还在不断提高。 软件测试费用昂贵通常占到整个软件测试开发成本的5 0 左右。 随着面向对象技术的广泛应用，面向对象软件测试技术已成为 一个重要的研究方向。与传统的软件测试不同，面向对象软件测试 的基本测试单元是类，类中封装的方法可以互相交互，这种交互特 性反映了类的动态模型，同传统的测试流和数据流相比，状态测试 侧重于对象的动态行为，这种动态行为依赖于对象的状态，测试对 象的动态行为能检测出对象成员函数通过对象状态进行交互时候产 生的错误。 有鉴于此，本课题将类状态测试用例自动生成作为主要的研究 对象。本文要实现类状态测试用例自动生成测试工具的原型，对这 方面的测试策略进行研究并编程实现关键模块，探讨技术难点提出 西安理工大学硕士学位论文 解决方案。最后形成一套成熟的、系统的类状态测试用例生成解决 方案。 1 2 软件测试用例自动生成方法及策略概述 软件测试通常可以分为基于规约的测试和基于源程序的测试， 通常也称作功能测试和结构测试。而测试用例的生成同样可以分为 基于规约的用例生成和基于源程序的用例生成。 i 2 1 基于规约的用例生成 基于规约的测试数据生成是指根据软件的规约文档即形式化文 档进行分析产生测试数据，最常见的有支持面向对象技术的 o b j e c t z 规约，代数舰约等等，通过对舰格说明翻译为某种形式化 语言描述，然后对规约分析推理产生测试用例，基于规约的测试往 往可根据规约自动或半自动地生成测试数据，但未必能提供充分的 代码覆盖。文献【l 】提出从布尔规格说明自动生成测试数据的方法， 文献【2 】提出从关系代数查询表示的规格说明中自动生成测试用例 的方法，它以软件规范为依据选取测试数据，其正确性依赖于规范 说明的正确性。事实上，我们不能保证规格说明完全正确，因此， 根据被测程序的内部结构设计测试数据必不可少。 基于面向对象的形式化规范语言( 如：c o o p n 2 ，o b j e c t z ) “1 等 的测试方法，需要较深的数学基础，很难推广和应用。而9 0 年代末 出现的统一建模语言( u m l ) 是为表示面向对象建模而采用的一种符 号句法。它合并了由b o o c h ，j a c o b s o n ，r u m b a u g h 开发的o o a d 符 号，已成为面向对象建模事实上的标准以及被o m g 所接纳的标准建 模语言，已经被许多著名厂商和学术机构所接纳ju m l 代表了面向 绪论 对象方法的软件开发技术的发展方向，具有巨大的市场前景，也具 有重大的经济价值和国防价值。同时，r a t i o n a l 公司开发的r o s e 2 0 0 0 是u m l 很好的建模工具。考虑到u m l 在对象建模方面的优越性，可 以预见，基于u m l 模型的对象状态测试技术的研究，无论是从实用 性方面还是理论性方面来说都有很高的研究价值。在理论上，可以 结合u m l 的特性，研究探讨最适合f r e e ( f i a t t e n e dr e g u l a r e x p r e s s i o n ，展平正规式) 状态模型的测试策略。同时，由于测试 是基于最有市场发展前景的u m l 建模语言，因而在软件工程方面具 有极高的实用价值，科研成果可以直接应用的软件开发的过程中。 这一点我们可以从美国著名的软件测试专家r o b e r tv b i n d e r 的专 著( ( t h et e s t i n go f0 0s y s t e m 中清晰地领悟到。 1 2 2 基于程序的用例生成 基于程序的测试数据生成即根据程序的源代码来生成测试数 据。目前，根据源程序生成测试数据的方法主要有随机法，基于符 号执行、基于程序执行的动态测试数据生成方法以及约束集求解算 法。 随机法是由计算机随机的生成测试用例直到找到满意解为止。 对于复杂的程序或者较高的测试标准需要生成大量的测试数据来覆 盖特定的路径。k o r e l 发现随机测试即使是在语句覆盖的覆盖标准 下对于复杂性比较小的程序其测试用例的生成效率也远不如其它算 法1 5 1o 随机算法没有引入任何启发性搜索策略，搜索的效率必然低 下但确不失为种廉价的且作为软件发布前测试的一种行之有效的 方法，同时它也可以作为其它算法的一种对比标准，用于衡量其它 启发性算法的效率“1 。 西安埋工大学硕士学位论文 符号执行”1 是指在一指定的逻辑路径上( 自顶向下或由底向上) 执行路径上的语句，当遇到赋值语句时赋值号左边的变量就用右边 的表达式代替，由于表达式总是由输入符号的值表示的，所以表达 式赋给变量后，左边变量的符号值也变成由这些输入符号值来表示 了，当遇到控制语句时，分支谓词中各变量就要用各自的表达式替 换。这样随着符号的不断执行，逻辑路径上的谓词表达式用逻辑运 算符连接起来，生成一综合的谓词表达式，它是关于输入数据的约 束条件，满足该谓词表达式的解，就是该逻辑路径得以执行的测试 数据，显然，如果求解出谓词表达式，那么就自动生成了测试该路 径的测试数据，但是该方法也存在着尚未解决的问题。首先，如果 被测程序有数组，则由于符号执行是一种静态的方法，数组下标变 量的值并不确定。这使得符号执行不知如何进行下去，同样的问题 也会出现在具有指针和循环的程序中，它们都将给符号执行引入不 确定性。其次，对于谓词方程组( 一组或几组等式不等式组) 的求解 也是一个问题，若该方程组是线性的，则可求解：若是非线性的，则 虽可采用非线性规划，但仍存在目标函数是否收敛的问题，而且即 使求得解也难以简化成易读的形式。 基于程序执行即动态测试数据生成法。k o r e l “1 借助于根据分支 函数最小化的思想进行程序的插桩，在程序执行过程中动态的搜集 插桩函数的返回值，来了解当前测试用例是否满足达到当前的覆盖 目的，如果不满足则分支函数的返回值可以作为一个生成下- - ! 贝k j 试 用例的依据。只要分支函数的数值尽量接近0 ，就可以逼近条件转换 点，得到满足分支条件的测试数据。 基于约束集求解的算法最近一两年逐渐成为近来国际上研究的 热点。c s p ( c o n s t r a i n ts o l v i n gp r o b l e m ) 是典型的n p c o m p l e t e 绪论 问题，所以在进行约束集求解时特别是非线性问题时尚存在较大的 困难，该算法力图通过求解程序的约束集来直接生成测试用例。文 献【3 8 】【3 9 】提出了基于c l p ( c o n s t r a i n tl o g i cp r o g r a m ) 的测试 用例生成技术，在将给定语句转换为约束集后通过c l ps c h e m a 来求 解并生成测试用例。【4 0 】【4 1 】使用区间算术求解约束集，【4 1 l 使 用e - b o xc o n s i s t e n c y 过滤区间，对于线性约束问题得到了比较满 意的结果。o f f u t t “1 提出了一种动态域削减算法，该算法首先给定 待确定测试数据的较大的输入域，然后根据选定路径上的约束条件， 动态的调整取值范围，最后生成可以覆盖选定路径上的测试数据的 范围，在这个范围内任意选取一值，从而生成测试数据。 1 3 类状态序列生成方法 在基于有限状态机的测试中，状态被认为是一个抽象的占位符 号 i o l 并没有做出明确的定义，对状态的预测采用的是把对状态的 识别转化为可观测的输出，其基本原理是预期被测实现到达特定的 状态后，通过附加的输入来观测该状态点特有的输出。文献【1 1 】 总结了基于扩展有限状态机的状态识别方法，这些方法有w 方法、 w p 方法、唯一输入输出u 1 0 ( u n i q u ei n p u to u t p u t ) 方法等。本 文对较常用的u i o 算法进行简单的介绍。 唯一输入输出方法通过u i o 来识别状态，唯一输入输出序列 u i o s ( u n i q u ei n p u to u t p u ts e q u e n c e ) 能唯一的识别一种状态，也 就是说对象处在该状态时接受了对应的u i o s 中的输入时，所产生的 输出不同于状态空间中的任何其它状态在接受此输入所产生的输 出。u i o 方法则仅为每一状态规定一唯一的输入输出序列，从而大大 减少了测试用例的生成。u i o 方法只能判断某一转换是否达到了规定 西安理工大学硕士学位论文 的状态，但当别的状态中也错误地包含了这个状态的u i o 特性时， 它却无能为力了。虽然u i o 方法存在一定的问题，但不失为一种比 较实用的方法。 唯一输入输出方法是基于有限自动机的测试中应用最广泛的方 法，特别是在通信软件的测试。但该方法是通过可观测的动作来识 别状态，应用到类的测试中时，除了一些特殊的类，如通信类、控 制类符合这个条件，大多数类没有或很少具有可观测的动作输出， 不可能为大多数状态唯一输入输出。因此我们需要为类构造一个可 观测的方法或者叫做观测者，这个方法要求是可执行的，无二义性 的和可观测的，而且调用此方法时不应该影响对象的当前状态。t h t s e 。5 1 在他的基于状态的测试方法中用状态不变量进行预测，他使 用的是基于模型的测试方法，这个模型叫作p r e d i c a t e t r a n s i t i o n n e t s ，有它自己的语法和语义。通过为每一个状态指定该状态的状 态不变量的取值空间来唯一确定状态。 1 4 状态测试自动化工具研究现状 基于扩展有限状态机也产生了很多测试用例生成工具：基于s d l 规约语言的t e s d l ，它的输入是s d l 规约，输出t t c n 表示的测试用 例；t t c nl i n k 是一个开发测试用例的环境，它可以自动检测以t t c n 表示的测试用例是否符合s d l 规约；s a m s t a g 是一种基于s d l 规约和 消息序列图( m e s s a g es e q u e n c ec h a r t s ) 的测试用例自动生成工具； t o p i cv 2 也是一种基于s d l 规约的测试用例生成工具，对状态的预 测使用一种自定义的语言g o a l ；u m l t e s t 是一种试用工具，它基于 u m l 的状态图产生测试用例1 1 2 1c l a s s b e n c h “”是个测试用例自动生 成的模板构架，它通过把o b j e c tz 表示的类的规约转换成有限状态 绪论 机来生成测试用例。因为目前基于u m l 状态图测试的理论方法正处 在研究阶段，所以开发的都是一些验证工具，离实用有不小的差距。 同时需要指出的是还未曾有通用的测试用例生成系统得以实现，这 主要是由计算测试数据类型的多样性，以及程序特性的复杂性所决 定的，基于约束集求解的静态算法目前尚在理论的研究和论证阶段， 但已经取得了一定意义上的突破，动态算法设计以及实现起来相对 比较容易，但效率问题是一个急待解决的问题。 1 5 本文的目标和主要工作 本文所做研究旨研究出一套切实可行的u m l 的状态测试用例自 动生成方法和理论，并在此基础之上开发原型验证系统a t d g 4 s m 。本 论主要的研究目标及工作有： 】研究出一套状态图的最短状态序列的生成算法； 2 提出一套将u m l 规约转换可描述该规约行为特性的可执行程 序的算法； 3 学习并掌握c + + 语法词法分析技术，并在此基础之上完成程 序信息的静态扫描以及插桩； 4 研究遗传算法生成测试用例的策略； 5 设计用例生成系统的框架并完成原型系统开发 1 6 小结 关于类状态的测试用例生成已经成为软件测试的一个较活跃的 研究领域。前人基于各种规约语言的用例生成进行了探讨，但由于 规约语言所固有的数学复杂性的特性，很难在实践中推广应用。状 态的预测在协议一致性测试中较为可行，对于面向对象语言类的状 西安理工大学硕士学位论文 态并不完全可行，且目前研究的成果中没有考虑到测试序列对测试 数据的依赖性，对满足状态覆盖的所必须的测试数据仍无法自动生 成问题。u m l 已经成为软件工程界建立系统模型的事实上的标准，因 此基于u m l 的状态测试具有相当的理论和应用价值。以下各章本文 将对基于u m l 的状态测试用例自动生成进行系统的讨论。 基于u m l 状态图的状态测试 第二章基于u m l 状态图的状态测试 面向对象程序中的类包括一组数据属性和在数据上的一组合法 操作。类的行为表现在它的状态空间和操作空间上，前者是指类的 成员函数的所有有效取值的组合，后者则是指类的所有合法操作序 列的组合。假如以s c 来表示类的状态空间，而以c 表示类的操作 空间，那么类的合法测试用例应是定义在s c v c 上的一个二元组 ( s ，1 l r ) ，其中s 表示类的一组有效状态，v 表示一个合法的操作 序列。事实上，也可以认为，类的测试用例可以分为两个部分：消 息序列和成员变量的取值，这两者是有联系而且互相制约的。为了 区别这两个部分，本文将测试用例中的消息序列部分称为类的测试 序列( t e s ts e q u e n c e ) ，而把成员变量的取值称为测试数据( t e s t d a t a ) 。 测试可以看作是一个搜索问题，我们要在数百万计的输入及状 态组合中，寻找那些极少数的能够发现错误的状态及其组合。例如， 在为类的测试生成消息序列时，由于类中往往包含了很多方法，这 些方法通过重复使用和各种结合方式可以产生数以万计的序列的组 合，其中有些是有效的、有些是无效的，在这种情况下，随机地产 生消息序列是费时费力并且不易于发现错误的，我们必须针对可能 出现的错误，找到那些少量的、能够覆盖状态空间的、并最易发现 错误的那些序列。我们的查找必须是系统的、集中的和自动的，而 模型为我们提供了这种可能性。模型不但抓住了所研究系统最本质 的关系，并且易于开发和分析。因此，测试必须是基于模型的。状 态机为类的行为提供了一种简洁的有预测的模型，采用它可以指导 测试序列的生成。 西安理工大学硕士学位论文 2 1e f s m ( e x t e n d e df i n i t es t a t em a c h in e ) 模型 h n a r c a v a l l i 在文献【1 4 】中总结了各种基于规约的测试方法， 包括经典的有限状态自动机f s m ( f i n i t es t a t em a c h i n e ) 模型方法” 以及应用最为广泛的以扩展的有限状态机e f s m ( e x t e n d e df i n i t e s t a t em a c h i n e ) 为基础的面向对象系统的基于状态的测试。在文献 【1 6 】中c h o u r o u kb o u r h f i r 系统的讲述了基于e f s m 测试的理论基 础和各种测试方法。 e f s m 可以形式化的定义如下：e f s m 是一个六元组 s 是一个非空状态集合 s 0 为初始状态 i 是非空的输入作用集合 0 是非空的输出作用集合 t 是非空的转移 v 是变量集合 t 中的每一个元素是一个五元组：t = ( s o u r c e s t a t e ， d e s t s t a t e ，i n p u t ，p r e d i c a t e ，c o m p u t e b l o c k ) 。其中，s o u c e s t a t e 和d e s t s t a t e 分别代表初始状态和终止状态，i n p u t 是来自于i 的 一个输入作用。p r e d i c a t e 是一个以变量v 表示的p a s c a l 形式的条 件，它是输入作用的参数或者一些常量。c o m p u t e b l o c k 是计算模块， 它包括p a s c a l 形式的赋值语句以及输出语句。 2 2u m l 状态图的语法语义 o f f u t t 已经为s c r ( s o f t w a r ec o s tr e d u c t i o n ) 规格说明“”和 基于u m l 状态图的状态测试 s o f l 规格既明“”研究出生成测试数据的标准，这些技术对u m l 状态 图也同样适用。u m l 状态图是使用扩展的h a r e l 状态图“”表示法的 有限状态机，并且一般用来表示对象的特征，对象的状态包括对象 的所有属性和行为，对象的动态特征通过状态转换来建模。其转换 语义表示为： e v e n t n a m e ( p a r a m e t e r s ) g u a r d a c t i o nl is t e v e n tl is t e v e n t n a l i l e 表示状态转换的触发事件的名称： p a r a m e t e r s 是与触发事件( 引起状态变化的事件) 相联系的变 量； g u a r d 是控制转换是否发生的前置条件，只有当事件发生而且满 足监视条件的前提下，转换动作才发生； a c t i o nl i s t 是目标事件表； e v e nl1 is t 状态发生转变被调用的事件列； u m l 的状态图以m d l 文件格式存储，m d l 存储以两种不同的视角 存取软件规约信息：逻辑视图和物理视图。其中状态转换图以逻辑 视图的形式存储，因此针对状态图的测试只要分析m d l 文件的逻辑 视图部分即可。从以上的状态转换图的信息可以知道，它已经充分 表达了状态转换的所有信启、，因此可以此为依据生成状态序列以及 测试数据。 2 3u m l 状态图信息的提取 u m l 分析器通过对以r a t i o n a lr o s e 建模的文本文件 m d l 扫描， 提取类的状态机模型并验证类的状态机的确定性。在分析该文档的 基础上，对于类的状态图的逻辑存贮结构构造其l a l r ( 1 ) 文法。借助 f l e x + + ，b i s o n + + ，u m l 文本扫描器由一个语法分析类p a r s e r 和一个 西安理工大学硕士学位论文 词法分析类l e x e r 组成。p a r s e r 使用词法类l e x e r 读入r o s e 的十m d l 文件，l e x e r 返回t o k e n ，p a r s e r 进行规约，执行语义动作，提取 u m l 状态图的信息。提取出来的状态规约以下列x m l 文档格式进行存 ，o 1 1 舂： ；hm 0 e阳t d i t e dw l t hx m ls 口y “4u m t t p w w wx m l s p y 。o m ) b y 1 n g t e l 0 7 2 s 6 c 1 u t ) 一s t t z c 肛npp ， e t m t i t l e eo m s t t ze 1 m t z s t c s e口p s tj u ed f o ns t r e i a j i e ，s t t e t t r z 口m t s i t l 0 i口川 je i m i 】 l l i 耵 d 盯j 叫t 昱越1 1 1 0 hs e g - 口f 日n e v e i t i j u z l m p “z t e 口旷j el m c d 耶i t l 0 口n ， m c t l 0 1 1口口r ， j el ms l r r r u z r i t i t l ei p 嘲j e 【ms t t e 耳 e r 删工口 el s t t e t t r ei p e 触j e t me v e t 日 e r 侧， t l mp r e t e i 彤：础j e l mc 0 耶i t l 0 i r 瑚， t m c t l 0 h 女r 枞彻 e l ms v p p l i e ri r 伪州 e l mi m r ij t r 棚7 h e tn lt e s t i c s e 南吖圳l 目 图2ll m l ：状态规约d t d 状态机信息的提取为：状态测试中利用深度优先、广度优先搜索、 最小生成树、旅行商等算法产生测试用例奠定了基础，实现了测试 分析过程的自动化，提高了软件测试分析效率。 2 4 小结 本章分析了扩展的有限状态机模型以及u m l 状态图的语法及语 义。下一章将就使用中国邮路算法生成最短状态测试序列问题进行 进一步的探讨。 中国邮路算法求解最短状态序冒 第三章中国邮路算法求解最短状态 3 1 状态覆盖准则 序列 同方法测试一样，对状态模型进行测试，首先需要确定状态测 试的覆盖准则。测试充分性准则有很多，例如转换覆盖、完全判定 覆盖、转变对覆盖、完全顺序测试。“ ：l i 。本文选用转变覆盖测试准 则作为类状态覆盖准则。 转换覆盖测试标准：测试集t 必须规格说明图表中的每一个转 换。这意味着测试者采用最少的测试用例遍历所有状态的每一个转 换至少一次。 这种覆盖标准常称为0 一长度( 0s w i t c h ) 覆盖，就是要求覆盖 监 个转换，其覆盖率表示如下： p， v m n km ，n f ，n 一，mj ，i e j lr q - i f “4 “”。”而丽式而而厕再忑雨而_ 一 3 2 强连通状态图的构造 功能 使用邮路算法求解最短状态序列，要求状态模型满足以下条件： 假设设计规范s p e c ( s p e c i f i c a t i o n ) 是强联系的并且具有重置 s p e c 是最小的； s p e c 是完整描述的、确定性的，它们具有相同的输入集x 西安理工大学硕士学位论文 以下面的状态模型为例，该模型有一个初始状态和一个终止状 态，以及4 个中问状态。按照u m l 规范，u m l 状态模型的初始状态只 能有一个，而终止状态可以为一个或多个。从状态图的特性可以知 道，它并不能满足使用邮路算法求解。为保证设计规范s p e c 是强联 系的并且具有重置功能，引入如下辅助边：从状态模型的终止状态 向初始状态引一条辅助边，因为任何状态都可存在到达终止状态的 路径，而任一中间状态均与某一初始状态存在路径。因此，经过处 理过后的的状态图是强联系的。 图3 一l 状态图模型实例 3 3 中国邮路算法的求解 中国邮路问题( c h i n e s ep o s t m a np r o b l e m ) 是图论中一个有重要 理论意义和广泛应用背景的问题，它来源于下述实际问题：一个邮 递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样 的路径，这就是著名的”中国邮递员问题”，由中国组合数学家管梅 谷教授提出，著名组合数学家j e d m o n d s 和他的合作者给出了一个 解答。 中国邮路问题的算法思想如下：该算法首先要进行图形的变换。 中国邮路算法求解最短状态序尹 将原图中的边抽象为新图中的节点，将新图中的每个节点与其他所 有的节点相连接。新图中的节点标记为s s ，s s 具有的外部属性为结 点在原图中对应边的首结点s s 。，。和末结点s s 。，s s 的权值为s s 结 点的序列长度。对于新图中的每个结点s s ，向其他所有的结点 s s ，( j ! - i ) 引一条边，该边的权值为s s i 。与s s j 。之间的最短路径 或s s 。，。和s s i 。之间的最短路径，具体的选取由路径方向决定。其 变换思想如图3 2 、3 3 所示。可以看出，只需要在新图中找到一个 包含所有s s 的排列，而该排列的权值和最小，然后将该节点排列中 的最短路径信息展开也就找到了邮路算法的解。 图3 2 ：原图图33 ：转换图 遗传算法求解经上述变换后的中国邮路问题的关键在于编码、 适应度函数以及选择、交叉、变异策略，本文采用文献【3 4 】介绍 的方法，具体方案如下： 编码规则采用以遍历边的次序进行编码的方法，码串0 1 2 3 4 表示自第0 条边开始，依次经过边l ，2 ，3 ，4 ，最后返回第0 条 边的遍历路径。 适应度函数取为码串的路径长度，码串的路径长度按如下方式 定义( 以码串0 1 2 3 4 为例) ：假设边0 ，1 ，2 ，3 ，4 的始端和终端分 别为( a 。，b 。) ，( a 。，b 。) ，( a 。，b 。) ，( a 。，b 。) 和( a ；，b 。) ， 西安理工大学硕士学位论文 长度分别为d 0 ，d 1 ，d 2 ，d 3 和d 4 ，w i j 为 端点i 和端点j 的最短路径长度，则码串0 1 2 3 4 的路径长度= ：。1d i + w b 。 ai + w b 1 a 。 + w b 。 a 。 + w b 。 a + w b a 。 选择操作采用的选择机制为比例选择机制。 交叉机制如下：( 1 ) 随机在串中选择一个交配区域，如两个串 及交配区域选定为a = 0 1 2 3 4 、b - 4 3 2 i 0 ( 2 ) 将b 的交配区域 加到a 的前面或后面，a 的交配区域加到b 的前面或后面，得到a = 2 l 0 1 2 3 4 、b 1 = 2 3 4 3 2 i 0 ( 3 ) 在a ，b 。中自交配区域后依次删除 与交配区相同的边码，得到最终的两字串为a ”= 2 1 0 3 4b “= 2 3 4 1 0 。 变异操作采取连续多次变换技术，使可行解有较大的顺序排列 上的变化，一旦变异操作发生，则用随机方法产生变换次数k ，对 所变异操作的串进行k 次对换。 3 4 算例分析 根据前述算法，对图3 一l 进行状态测试序列的生成。 步骤l ：首先添加辅助边，添加一条由s e n d 到s s 的辅助边，如 图3 一l 虚线所示。使用前述算法，生成的转换图中，应该有8 个节 点分别对应于状念模型中的7 个状态转换边以及一个添加的辅助边。 步骤2 ：对状态模型图进行转换，生成转换图的权值矩阵如下： 中国邮路算法求解最短状态序列 v 洲tvs ls 。v 眦nv 郴iv 心3v s2 v 删ov 咖s v 2x1l 0oo 2 l v o0x2lll32 v m o02 xill 32 v s t e103x243 v s t s 3 1302x243 vs ! h 洲 2 443 3 x lo v s s s o022l1lx2 vs e n u s s1332220x 步骤3 ：搜索最小路径权值和排列 按照前述算法，生成的转换图中的权值和最小的节点排列为： v s 2 s 1v ) v h ! v ；v s s ( ) v 、nv s e 、u _ xv ( 1 步骤d ：将该序列中蕴涵的最短路径展开，得到的序列为： s 2s ls os 2 s 3s o s 2s e n ds s s 0 步骤5 ：添加前导路径 目前得到的状态序列的起始节点不一定是状态模型中的初始状 态节点，需要在该序列上添加一条由初始状态到该序列首状态的最 短路径。 s ss o s 2s ls o s 2 s 3s os 2s e n ds ss o 步骤6 ：拆分序列 对该序列进行拆分，因为添加了辅助边，而实际上在状态模型 中并不存在由终止状态到初始状态的状态转换，可以将该序列进行 拆分，在终止状态和初始状态相邻的位置将状态序列拆开，如下： s ss o s 2s ls o s 2s 3s 0 s 2s e n d s ss o 步骤7 ：合并序列： 拆分过后的序列可能存在序列重叠的现象，采用子串查询算法， 西安挫工大学硕士学位论文 去掉重叠的子串，本例为s ss 0 ，最后得到一条满足转换覆盖且最 短的状态测试序列：s ss os 2s ls o s 2s 3 s os 2s e n d 3 4 中国邮路算法与u 10 序列综合优化 本文虽采用状态不变量作为确定状态预测的标准，但考虑到u 1 0 算法的重要性，尤其是其在协议一致性测试的重要意义，同时课题 的研究过程中提出了中困邮路算法与u i o 序列全局优化的新算法， 因此本节将对该问题进行探讨。文献【3 7 】采用中国邮递员算法和 测试序列进行了优化，但对于u i o 序列仅仅作为一种识别状态的附 加序列，并没有充分的考虑到由于u i o 序列的引入对状态迁移造成 的影响，生成的测试序列并不是全局最优的。下面将以已经讨论过 的中国邮路算法求解最短状态序列的思想为基础，探讨中国邮路算 法与u i o 序列的综合优化问题。 本文提出的的全局优化算法的基本思想是将抽象节点的定义针 对u i o 序列特点进行重新的定义。新的抽象节点( s s 。) 是扩展的有 限状态机的边e 。e 和第k 个u i o 序列的连接。将u i o 序列与状态 转换边相连接构成新的抽象结点，解决了将u i o 序列作为测试序列 的一部分进行全局优化的问题。 下面结合具体实例阐述本文所提出方法的具体实施步骤，下图 为一强连接但非对称的状态机模型图。 中国邮路算法求解最短状态序， 状态u i o 序列 s 1 a y s 2 a x ，a y s 3 * a x ，a xb y ，a y 图3 4 状态机实例图表3 一l 各状态u i o 序列 首先，根据u i o 的定义，确定各状态的唯一输入输出序列表3 一l 。 其中，标注有$ 的为本例中为该状态点实际选定的u i o 序列。 按照前述算法，根据状态图生成各个状态转换的抽象节点如挺! 所示。将每一个子序列结点与其它子序列结点相连接，权值矩阵如 下： 悸 表3 2 各状态转换对应的抽象节点 使用遗传算怯，永觯中国邮路，得到解：s s l - 3 3 3 一s s 4 一s s 2 西安理工大学硕士学位论文 s s 5 一s s 6 ，展开抽象节点序列，得到最终的测试序列如下： a y a x a y a x a y 。- b y a x a x b y a x a x b y a x a x a y - b y b y a y 以下是本文提出的算法方法和文献【3 7 】中提出的邮递员算法 的比较结果： 表3 3 对比结果 3 5 小结 本章阐述了使用中国邮路算法生成最短测试序列的方法，并讲 述了满足使用邮路算法的状态图的构造方法，给出了使用遗传算法 求解中国邮路算法的方法以及最短序列的生成算法。同时提出了中 国邮路算法与u i o 序列综合优化算法，大大降低的测试序列的长度。 下一章将在此基础之上讲述可执行规约的构造。 可执行规约的构造 第四章可执行规约的构造 目前，基于状态机的测试多集中在测试序列的生成方法学上， 然而状态机的特点决定了测试序列对测试数据具有相当的依赖性， 即一个测试序列的执行受到其上测试数据的约束。从测试理论上讲， 基于程序的测试用例生成将更加容易，因此就有需要构造一个能够 体现状态机行为特性的可编译执行的代码段。本文提出了通过构造 可执行规约的方法模拟状态机行为，将其转换为可执行的代码段并 在此基础上使用遗传算法来生成状态机的测试数据，为解决状态机 测试数据的生成提供了一种可行的方法。 4 1 可执行规约构造的算法描述 根据状态机构造可执行规约的基本思路如下：首先根据状态图 生成测试序列，针对每一个测试序列，根据该测试序列上的各种状 态及其转换信息合成一段用来描述该状态序列上的状态转换的程 序，其方法如下： 针对状态转换图中的每一个动作，生成一段描述行为描述代码。 代码段为该事件对应的动作； 针对状态图中的每一个监视生成一个条件语句，条件语句的内 容等于该监视的条件； 最后生成函数体，该函数体的参数是所有该测试序列使用到的 事件的参数集合； 参数的编码规则为t x p a r a x x x ，t x 段代表该参数来源的事件 名称，p a r a x x 为该参数在来源事件中的编号，x 段表示该参数在可 西安理工大学硕士学位论文 执行规约中的编号，因为同一事件的同一参数在可执行规约中可以 重复出现。 下面是平面状态图可执行规约的形式化定义 2 0 l ，典型的平面 状态图模型如图4 一l 所示： 巨如) g 】刊 e r 咱 图4 一l 平面状态图模型 其中e 代表该转换上的事件，p 代表该事件执行所需要的参数， g 代表该转换上的监视，a 代表该转换的动作。 其可执行规约构造的形式化定义如下： e ( p ) = i fs = s 1 gt h e ns ：= s 2 八g ae n d 在u m l 状态图具有三种基本类型：平面状态图、嵌套状态图以 及并发状态图。它们都可以通过转换生成对应的程序代