（计算机应用技术专业论文）基于禁忌搜索算法的efsm测试数据生成.pdf

中图分类号t p 3 1 1 5学科分类号 5 2 0 4 0 论文编号 10 0 10 2 0 1 1 0 7 0 7 密级公开 学位授予单位代码 10 0 10 学位授予单位名称北京化工大学 作者姓名 任君 学号 2 0 0 8 0 0 0 7 0 7 获学位专业名称计算机应用技术获学位专业代码 0 8 12 0 3 课题来源国家自然科学基金研究方向软件测试与软件可靠性 论文题目基于禁忌搜索算法的e f s m 测试数据生成 关键词 禁忌搜索；遗传算法；可扩展有限状态机；测试数据生成；禁忌表 论文答辩日期 2 0 11 5 2 6论文类型 基础研究 学位论文评阅及答辩委员会情况 姓名职称工作单位学科专长 北京化工大 指导教师赵瑞莲教授软件测试与软件可靠性 学 北京化工大 过程工业监测、编译技 评阅人1彭四伟副教授 学 术应用、并行计算 北方工业大 评阅人2 赵会群教授软件测试 学 评阅人3 评阅人4 评阅人5 北京化工大分布式系统、网格计算、 答辩委员会主席赵英教授 学计算机网络 答辩委员1山岚教授北京化工大学网络信息获取技术的研究 过程工业监测、编译技术 答辩委员2彭四伟副教授北京化工大学 应用、并行计算 智能信息处理、嵌入式系 答辩委员3张杰副教授北京化工大学 统 答辩委员4聂伟副教授北京化工大学通信与信号处理 答辩委员5 江：一 四 论文类型：1 基础研究2 应用研究3 开发研究4 其它 中图分类号在中国图书资料分类法查询。 学科分类号在中华人民共和国国家标准( g b t13 7 4 5 9 ) 学科分类与代码中 查询。 论文编号由单位代码和年份及学号的后四位组成。 摘要 基于禁忌搜索算法的e f s m 测试数据生成 摘要 随着计算机软件行业迅速发展，需求日益复杂，软件产品质量的提高 变得越来越重要，已成为人们关注的焦点。软件测试是保证软件质量最重 要的手段，也逐渐成为软件开发过程的重要阶段。随着软件规模越来越大， 结构越来越复杂，测试成本相对提高。软件测试自动化已成为提高测试效 率，降低测试成本的重要手段，其最关键的难点之一是测试用例的自动生 成。 面向对象软件代码重用率高，需要严格的测试以保证软件质量。但传 统的面向过程软件测试技术不适用于面向对象软件的测试，因此随之出现 了基于模型的测试研究。这类模型主要包括u m l ( 统一建模语言) 模型、 l t s ( 标号迁移系统) 模型和e f s m ( 可扩展有限状态机) 模型等，能够 表达软件系统的一系列活动集合。 e f s m 模型可以精确刻画软件系统的动态行为，已被广泛的应用于描 述面向对象软件的对象行为及对象间的交互。因此，针对e f s m 模型， 探讨测试用例的自动生成具有重要的理论意义和实用价值。e f s m 模型的 测试用例生成包括测试路径生成和测试数据生成两部分。目前，针对 e f s m 模型的测试研究大多集中于测试路径自动生成。为探索路径上测试 数据的自动生成，本文提出了一种面向e f s m 路径，利用禁忌搜索策略 北京化工大学硕上学位论文 实现其测试数据自动生成的方法，成功生成了测试数据。在此基础上，通 过测试数据生成时间与路径不同特征因素之间关系的相关性分析，获得了 影响e f s m 测试数据生成效率的关键因素，并选取复杂路径通过适应度 值的变化与遗传算法的测试生成效率进行了比较。实验结果表明：基于禁 忌搜索的e f s m 模型测试数据自动生成确实可行，并且其测试生成效率 相对于遗传算法有很大提高。 关键词：禁忌搜索；遗传算法；可扩展有限状态机；测试数据生成；禁忌 表 a st h ei n c r e a s i n gs c a l eo fs o 胁a r ea n dm o r ec o m p l e xo ft h es t l l l c t u r e ，t h e t e s t i n gc o s ti sr e l a t i v e l yi n c r e a s e d a u t o m a t i cs o r w a r et e s t i n gi st h em a j o r r e s e a r c hf o ri m p r o v i n ge 侬c i e n c ya n dr e d u c i n gc o s t s h o w e v e r ，t h ea u t o m a t i c g e n e r a t i o no f t e s tc a s e si so n eo ft h em o s tc r i t i c a lc h a l l e n g e s t h es o r w a r ec o d eo fo b je c t o r i e m e ds o r w a r ed e v e l o p m e n tt e c h n o l o g y h a sh i g 且e rr e u s er a t e ，s oi tn e e ds t r i c t t e s t i n gt o e n s u r es o 姗a r eq u a l i t y h o w e v e r ， t h et e s t e rc a nn o td i r e c t l y 印p l y t h e p r o c e s s - o r i e n t e dt e s t i n g t e c h n i q u e s ， a n df o l l o w e db yt e s tm o d e l sw h i c hc a ne x p r e s sas e r i e so f c o l l e c t i o n ，s u c ha si7 m i ，( u n i f i e dm o d e l i n gl a n g u a g e ) m o d e l ，i s ( 1 a b e l e d t r a n s i t i o ns y s t e m ) m o d e l ，e f s m ( e x t e n d e df i n i t ec a ns t a t em a c h i n e ) m o d e l e f s mc a nc h a r a c t e r i z et h ed y n a m i cb e h a v i o ro fs o r w a r es y s t e mm o r e p r e c i s e l y ： t e s tc a s eg e n e r a t i o nb a s e do ne f s m( e x t e n d e df i n i t es t a t e i l i 北京化工大学硕上学位论文 m a c h i n em o d e l s ) i n c l u d e st e s tp a t h g e n e r a t i o na n dt e s t d a t ag e n e r a t i o n h o w e v e r ，m o s to ft o d a y sr e s e a r c ha _ t t e n t i o nt oe f s mt e s t i n gf o c u so nt e s t p a mg e n e r a t i o n i no r d e rt oe x p l o r et h ea u t o m a t i ct e s tg e n e r a t i o n ，t h i sp a p e r p r e s e n t sat e s td a t ag e n e r a t i o nm e t h o dw i t hr e s p e c tt ot h ep a t ho fe f s m m o d e l s at a b us e a r c hs t r a t e g yi sa d a p t e dt oa u t o m a t i c a l l yg e n e r a t et e s td a t a ， a n dm ek e yf a c t o r st h a ta f - f e c tt h ep e r f o m a n c eo ft e s td a t ag e n e r a t i o ni n e f s mm o d e l sa r ea n a l y z e d m o r e o v e r t h et e s tg e n e r a t i o ne m c i e n c yi s 2 2 遗传算法1 0 2 2 1 遗传算法简介1 0 2 2 2 遗传算法基本原理1 0 2 2 3 遗传算法特点及流程1 2 2 2 4 遗传算法在软件测试中的应用1 3 2 3 禁忌搜索算法1 4 2 3 1 禁忌搜索算法概述1 4 2 3 2 禁忌搜索算法原理及特点1 5 2 3 3 禁忌搜索算法具体流程1 6 2 3 4 禁忌搜索算法在软件测试中的应用1 7 2 4 本章小结1 8 第三章e f s m 模型1 9 3 1e f s m 基本术语1 9 3 2e f s m 模型范例1 9 v 北京化工人学硕十学位论文 3 3 基于e f s m 模型的测试2 l 3 3 1 基于e f s m 模型的测试的相关定义2 l 3 3 2 基于e f s m 模型的测试覆盖准则2 2 3 3 3 基于启发式搜索算法的e f s m 测试数据生成2 2 3 4 本章小结2 4 第四章基于禁忌搜索算法的e f s m 测试数据生成研究及实现2 5 4 1 基于禁忌搜索算法的e f s m 测试数据生成概述2 5 4 2 基于禁忌搜索的e f s m 测试数据生成算法描述2 5 4 3 基于禁忌搜索的e f s m 测试数据生成操作及参数设计2 7 4 3 1 基于禁忌搜索的e f s m 测试流程2 7 4 3 2 初始解构造2 8 4 3 3 适应度函数构造2 8 4 3 4 邻域函数设计2 8 4 3 5 禁忌表结构2 9 4 3 6 终止准则3 0 4 4 基于禁忌搜索的e f s m 模型测试数据生成3 0 4 5 本章小结3 2 第五章禁忌搜索算法的e f s m 测试数据生成效率比较及关键因素分析3 3 5 1 禁忌搜索与遗传算法在e f s m 模型测试数据生成上的效率比较3 3 5 2 影响测试生成效率的关键因素分析3 8 5 3 禁忌搜索与遗传算法测试数据生成效率分析4 1 5 4 本章小结一4 3 第六章结论4 5 6 1 本文的主要贡献4 5 6 2 本文进一步研究方向4 5 参考文献。4 7 致谢5 1 v i 目录 研究成果及发表的学术论文5 3 作者与导师简介5 5 v i l 北京化工人学硕上学位论文 c o n t e n t s c o n t e n t s c h a r p t e rli n t r o d u c t i o n 。”1 1 1r e s e a r c hp u 印o s ea n dm e a n i n go f t h et h e s i s 1 1 2c u r r e n tr e s e a r c hs t a t e 2 1 2 1r e s e a r c hs 吮o f t e s t i n gb a s e dm o d e l ：2 1 2 2r e s e a r c hs t a t eo f t e s t i n gs e q u e n c eg e n e r a t i o nb a s e de f s m 3 1 2 3r e s e 棚hs t a t eo f t e s t i n gd a t ag e n e r a t i o nb a s e de f s m 4 1 3p r i m a l yw o r k 踟1 dc o n 6 9 u r a t i o no f t h ep a p e r 6 1 3 1 p r i m a r y 、o r k 6 1 3 2c o n f i g u r a t i o no f t h ep a p e r 7 1 4s l 】m m a i yo f t h i sc h a p t e r 7 c h a r p t e r2h e u r i s t i cs e a r c ha i g o r i t h m 9 2 1t h eb r i e fo fh e u r i s t i cs e a r c ha l g o r i t h m 9 2 2g e n e t i ca l g o r i t h n l 1 0 2 2 1t h eb r i e f o f g e n e t i ca l g o r i t h l l l 1 0 2 2 2n l ec h a r a c t e r i z a t i o no f g e n e t i ca l g o r i t h m 1 0 2 2 3f r 锄eo fg e n e t i ca l g o r i t l l l n 。1 2 2 2 4t h e 印p l i c a t i o n so fg e n e t i ca 1 9 0 r i t h mi ns o m ，a r et e s t i n g l3 2 3t a b ua l g o r i t l u i l 1 4 2 3 1 t h eb r i e f o f t a b ua l g o r i t h m 。1 4 2 3 2t h ec h a r a c t e r i z a t i o no f t a b ua l g o r i m 1 5 2 3 3f 姗eo f t a b ua l g o r i t h m l6 2 3 4t h e 印p l i c a t i o n so f t a b ua l g o r i t mi ns o 胁a r et e s t i n g 1 7 2 4s u m m 缸yo f t h i sc h a p t e r 18 c h a r p t e r3t h eb a s i cp r i n c i p l ea n da p p i i c a t i o no f e f s m 。”19 3 1t l l eb a s i ct e m i n o l o g yo fe f s m l 9 3 2t l l ee x 狮p l eo fe f s m 1 9 3 3t e s t i n ga p p l i c a t i o nb a s e de f s m 2 1 北京化工大学硕上学位论文 3 3 1t h ed e f i n i t i o no f t e s t i n gb a s e de f s m 2 1 3 3 2c o v e r a g ec r i t e r i o no f t e s t i n gb a s e de f s m 2 2 3 3 31 e s td a t ag e n e r a t i o nf o re f s mb a s e do nh e u r i s t i cs e a r c ha l g o r i t l m l 2 2 3 4s u m m 娜ro f m i sc h a p t e r 2 4 c h a r p t e r47 r e s td a t ag e n e r a t i o nf o re f s m b a s e do n7 i 、a b us e a r c h 。2 5 4 1 s u m n l a r i z eo f t e s t i n gd 2 l t ag e n e r a t i o nf o re f s mb a s e do n 7 i 砧us e a r c h 。2 5 4 2 f r a mo f t e s t i n gd a t ag e n e r a t i o nf o re f s mb a u s e do n t a b us e a r c h 2 5 4 3 s t r a t e g yo f t e s t i n gd a t ag e n e r a t i o nf o re f s m b a s e do nt a b us e a r c h 。2 7 4 3 1p r o c e s so f t a b us e a r c hf o rt e s t i n g ( 1 a t ag e n e r a t i o no f e f s m 2 7 4 3 2i i l i t i a ls o l u t i o no f t a b us e 2 u r c h 2 8 4 3 3f i t i l e s so f t a b us e a r c h 2 8 4 3 4f o c a l 胁c t i o n so f t a b us e a r c h 2 8 4 3 5t a b ul i s to f t a b us e a r c h 2 9 4 3 6s t o pc r i t e r i o no f t a b us e a r c h 2 9 4 4r e a l 时印p l i c a t i o no nt e s td a t ag e n e r a t i o nf o re f s mo f t a b 3 0 4 5s u m m a r yo f t h i sc h a p t e r 3 2 c h a p t e r 5c o m p a r i s o no fe f n c i e n c ya n da n a l y s i so fk e yf a c t o rf o rt e s t d a t ag e n e r a t i o nf 1 0 re f s mb a s e do n7 i a b ua i g o r i t h m ”。”3 3 5 1c o m p 撕s o no fe f j e i c i e n c yb e t w e e nt a b ua n dg e n e t i cf o rt e s td a t ag e n e r a t i o nb a s e do n e f s m 3 3 5 2k e yf a c t o ro f t e s td a t ag e n e r a t i o n 3 8 5 3a n y l i s i so f e f j f i c i e n c yt l l r o u 曲f i t n e s s 4 1 5 4s u i 】3 m a r yo f t h i sc h a p t e r 4 3 c h a p t e r6t h g 4 5 6 1i n n o v a t i o no ft h et h e s i s 4 5 6 2t h ec o n t r i b u t i o n sa 1 1 df u r t l l e rs t u d yd i r e c t i o n 4 5 r e f e r e n c e 。4 7 x c o n t e n t s a c k n o w i e d g e m e n t s 。5 1 c o n t e n t so fa c a d e m i cp a p e rp ub l i s h e da s ag r a du a t es t u d e n t 。5 3 i n t r o d u c “o no ft h ea u t h o ra n dt u t o r 。5 5 x i 北京化t 大学硕上学位论文 第一章绪论 第一章绪论 近些年来，国民经济蓬勃发展，科学技术不断进步，软件系统逐渐深入到生活的 各个方面，从普通的计算机软件到新一代的手机a n d r o i d 系统软件，再到如今火热的 物联网传感设备，软件系统已经已经影响到了整个国家的发展进程，也影响人类社会 发展的各个阶段。 现代软件系统越来越多元化，越来越复杂，业界对软件质量要求程度也不断提高。 但现实中软件系统的质量和稳定性却不尽人意，采用有效的软件测试方法是保证软件 质量、提高软件可靠性的重要手段。 1 1 课题研究的目的和意义 软件测试是很多软件开发项目中较为重要的部分，其工作内容繁琐，耗费时间多。 为了降低测试所花的费用，提高测试的效率，更有效的增强软件的可靠性，现在测试 的研究方向比过去更为广阔，测试方式由简单的手工测试发展为手工、自动两者皆有 的方式，并开始有专门的公司承担这项工作。计算机软件开发的研究表明，只有明确 阐述软件客户的最终期望，并对期望进行确认，核实软件功能的有效性，才能最终使 客户对完成的软件产品感到满意，测试用例这概念的提出就是为了核实并反映产品 的需求。对于一个软件产品或者程序来说，其输入是无穷的，为了保证测试的可行及 时间的允许，测试时必须选择一定数量的测试用例( t e s t c a s e ) 进行输入，并且所选择 的测试用例要满足所要测试的一定需求，这就需要对所用的测试用例进行特定设计。 现在很多关于测试的研究都集中于测试用例的构造和生成中，希望能够以自动化的方 式生成测试用例，提高测试的效率。 随着软件系统的逐渐庞大，使用不同的状态模型来对软件系统进行描述的应用越 来越多，关于状态模型测试的研究也越来越广泛。可扩展的有限状态机模型( e f s m ) 在有限状态机( f s m ) 模型上增加了变量、操作、以及状态迁移的前置条件，可以精 确的刻画软件的动态行为【i 】1 2 】。因此，基于e f s m 的测试具有重要的研究意义和实用 价值。目前，基于e f s m 模型的测试研究大多集中于如何生成可执行路径上，对于给 定e f s m 模型的可执行路径探讨如何自动生成测试数据的研究还较少。与此同时， e f s m 模型软件测试数据生成在整个测试过程中占很大比重。如果通过使用合适的方 法能使该过程自动高效的实现，则会极大地减少软件开发的周期和费用。因此，如何能 够使用高效的算法设计生成更高效更准确且便于使用的测试用例也是当前研究的热 点。 近些年来，遗传算法、模拟退火算法、粒子群算法等启发式搜索算法被广泛的应 北京化工大学硕士学位论文 用于测试领域，取得了一定的成果。禁忌算法作为一种能够模拟人类智力过程的全局 搜索算法在组合优化等领域取得了很大的成功，但其在测试领域的应用还相对较少。 综上所述，软件测试领域中，基于e f s m 模型的测试数据自动生成是一个很重要 的研究问题，本文正是针对这一问题，对e f s m 模型特点及算法进行了分析，选取禁 忌搜索算法进行测试数据生成，目的一是探索能够适应e f s m 数据生成的禁忌搜索算 法策略，二是使其测试数据生成的时间有所减少，获得更好的测试数据生成效率。因 此本课题具有一定的理论意义和应用前景。 1 2 国内外研究现状 1 2 1 基于模型的测试研究现状 基于模型的软件测试可以使测试效率及测试用例生成的自动化程度有效地提高， 有利于进行测试失效辨识并较准确地评价测试结果。在基于模型的研究中，较为普遍 的包括基于u m l 模型的测试研究、基于f s m 模型的研究以及基于e f s m 模型的研 究。 u m l 模型是一种统一建模语言，可以对软件系统进行可视化建模，这种语言提出 了一系列的建模机制和可视化图形，对于系统的开发及管理很有大作用【3 1 。p s 锄u e l 等提出了在u m l 状态图上使用数据流控制流及函数削减的技术自动产生测试用例【4 】。 y g 等提出了使用数据流和和控制流方式解决u m l 测试数据生成的覆盖准则问 题吼 f s m 模型为有限状态机模型，是软件领域重要的模型工具，在时序电路分析、数 字系统设计等领域起到了很大的作用。 e f s m 为可扩展的有限状态机模型，在有限状态机模型上添加了一系列的变量， 操作及条件可以精确的刻画软件的动态行为。x i w a i l g 等在2 0 0 8 年分析了u m l 和 f s m 的优缺点，实现了将u m l 转化为f s m 【6 1 。为了解决f s m 模型应用中常常出现 状态或迁移爆炸的问题，出现了e f s m 模型，并且e f s m 模型对于描述软件系统的动 态行为更加精确。 随着这些模型的应用越来越广泛，基于这些模型的测试研究也日益得到了人们的 重视。本文主要针对的是基于e f s m 模型的测试数据生成研究，下面主要介绍近几年 来国内外关于e f s m 模型测试的研究现状。 目前，国内外基于e f s m 模型的测试研究主要包括测试序列生成和测试数据生成 两方面的内容。e f s m 模型由于在f s m 基础上添加了迁移条件等，使测试序列存在 不可执行问题，测试序列生成主要针对这一问题进行研究，采用不同的方法解决测试 序列不可行问题。测试数据生成则是在测试序列生成的基础上，生成满足指定测试序 2 第一章绪论 1 2 2e f s m 模型的测试序列生成研究现状 e f s m 模型是在f s m 模型的基础上扩展而来的。首先，f s m 模型测试序列生成 包括4 种经典方法，分别为t 方法、d 方法、w 方法、u 方法。 1 第一种方法是t 方法，其前提是f s m 是强连通的，其中测试序列通过将随机 数据输入到f s m ，使f s m 中所有迁移至少都被执行一次。测试中使用t 方 法只能测试迁移的存在，并没有达到测试迁移目标状态的目的【”。 2 第二种方法是d 方法，这种方法使用时有一个前提，就是f s m 的每一个状态 机要存在区分序列。首先为f s m 模型建立一个区分序列，然后根据建立的这 区分序列建立测试输入序列，这种方法能产生序列的数量不会很多【8 j 。 3 第三种方法是w 方法，其前提是f s m 是精简的，这样就能找到状态识别集， 然后通过f s m 的状态识别集来建立测试输入序列。所以，w 方法的可使用性 程度较大。然而这种方法有一个弊端，就是得到的测试输入序列数量较大， 在现实的使用中测试效率会相对较低【9 】。 4 第四种方法是u 方法，首先为了对每一个状态进行区分，先对f s m 的所有状 态都分别建立一个叫作单一输入输出的识别序列，然后通过已有的这一识别 序列建立测试输入序列。这种方法在很多进行f s m 测试序列生成的实际情况 中得到应用【1 0 j 。 为了解决e f s m 测试序列生成的问题，有一些研究尝试将e f s m 转化为等价的 f s m 模型，利用现有的f s m 模型测试序列生成方法来解决e f s m 模型的序列生成问 题。先将原始的e f s m 模型进行转换，使其状态迁移不受前置条件的影响，再利用u 方法进行测试序列生成【1 1 】。但是，由于e f s m 中迁移的行为与条件相互关联，转换比 较复杂，很容易出现状态爆炸现象。 针对e f s m 测试序列生成涉及到路径的可行性分析问题，r 锄a l g i o m 等人提出使 用上下文独立单一输入序列( c i u s ) 的概念来间接地解决可执行性问题，并根据c i u s 来构造测试输入数据，该方法只在测试序列生成时考虑测试序列的可执行性，c i u s 用 作状态鉴别序列。事实上c i u s 也是一种u 1 0 序列，不过，并非每个e f s m 都有 c i u s ，该方法的适用范围因此受到限制i l 引。 n a i k 等人提出扩展单一输入输出( e u i o ) 的概念来解决可执行性问题。e u i o 方 法首先将e f s m 转换为规范化e f s m ，然后配置初始状态，并选择一个以当前状态 为头的可执行待测转换，对其进行t e a ( 转换可执行性分析) 扩展，得到对应的 e u i o 序列【1 3 】。 周晓煜等人引入了逆向判定性的概念，并利用这一概念对转换可执行性分析 ( t e a ) 方法进行了改进，减短了生成的测试序列的长度，并且减小了所需的t e a 树扩 展空间【1 4 】。 北京化工人学硕上学位论文 d u a l e 等人利用图分裂技术消除e f s m 图中的两条边的行为冲突和条件冲突。通 过图分裂，将有冲突的两条边分别置于两个彼此独立的子图中，这样就避免了两条冲 突的边包含在同一路径里，也就避免了基于路径生成的测试序列的不可执行问题【1 5 】。 目前，通过各种途径解决e f s m 测试序列生成问题已经取得了一定的成果，随着 启发式搜索算法在很多领域得到广泛应用，测试研究中的应用也越来越多。有一些研 究尝试使用启发式搜索算法解决e f s m 测试序列生成问题。f s m 模型是由一系列状 态迁移条件构成的结构，测试过程中需要按照路径序列进行。应用宽度优先等方法对 e f s m 模型图进行遍历能够产生相应的序列，但由于e f s m 添加了一些前置条件，导 致产生的序列存在不可行问题，所以应用启发式搜索算法处理e f s m 测试序列生成最 主要的内容就是解决其不可执行问题。 b o 甜1 f i r 等人提出了一种将数据流和控制流相结合的e f s m 模型测试序列自动生 成方法。这种方法使用一种早期的可执行核查机制减少后期被丢弃的路径，使用启发 式搜索算法处理多转换或者循环转换的可执行性分析，再通过添加前序编码和后序编 码的方式生成测试序列，使生成路径的可执行性得到了很大的提高，并在进一步的工 作中指出将其与s d t 工具结合的研究i l 刚。 k a l 旬i 等人提出一种方法，通过使用一种适应度衡量方法分析路径中转换的条件 依赖及行为，在执行结构过程中使用遗传算法生成可执行路径( f t p s ) 。实验表明使 用这种方法得到的路径可行性能达到1 0 0 ，而随机方法中大部分可行性失败【1 7 】。 在使用启发式搜索算法的基础上使用某些策略更大程度的解决了测试序列生成不 可执行的问题，使这一问题取得了很大的发展。 1 2 3e f s m 模型测试数据自动生成研究现状 测试数据生成即如何产生满足程序中某条路径上的约束条件的输入值的问题，这 一研究在国内外也已经有了j 些成果。 对于面向路径的测试数据生成，k o r e l 等人提出使用函数最小化方法来自动产生 测试数据，此方法先使用实际值来执行程序，并在执行过程中对程序执行流进行监测， 使用最小化方法自动定位测试输入值l l 引。 g u p t a 提出使用松弛技术来进行测试数据生成，首先输入任意值，在此基础上反 复改进输入值并同时评价各分支谓词的执行，直到得到能满足每个分支谓词条件的输 入值。e f s m 模型的测试数据生成方法也是面向路径基础上实现的，路径的表示有基 于状态的，也有基于迁移的【眇j 。 张涌等人提出一种自动选取e f s m 模型测试数据的方法，其文献中提出使用两种 策略，一是对数据区间进行削减，再是采用分段梯度最优下降算法。通过一系列实验 结果说明其采用的方法收敛速度较快，并且能够成功实现大多部分测试数据的自动选 第一章绪论 取，即使有一部分数据无法得到准确解，采用的区间削减也能缩小测试输入数据变量 的取值区间，为进一步的测试数据获得工作提供了方便，有利于人工进行进一步测试 数据的选择【2 们。 易国洪等人给出了叫做等价类测试的划分方法，在文献中提出了一种算法用来确 定等价类测试用例，对测试用例等价类进行划分，很大程度上减少了测试用例的数量， 在实践应用中具有很深的指导作用，其测试最小集的确定速度较快，从而使测试成本 得到有效控制，并且提高了软件的可靠性，为这一领域的研究及发展起到了不可估量 的作用【z l j 。 b o u t h f i r 在研究测试序列可执行问题的过程中，对生成的测试序列后期使用符号 执行的方式，收集约束来解决测试数据生成问题，对测试序列的是否可执行性进行判 定【2 2 1 。 遗传算法、模拟退火算法、禁忌搜索算法蚁群算法等启发式搜索算法在许多领域 得到了广泛应用。近些年来，研究者将测试数据的生成问题转化为优化类的搜索问题， 将启发式搜索算法应用于这方面的研究。启发式搜索就是在状态空间中的搜索对每一 个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到找到目标。相 对于随机搜索，使用这样的方法可以减少大量无谓的搜索路径，提高了效率。 目前，应用启发式搜索算法进行不同层次上的测试数据的自动生成已经取得了较 大的发展，其中包括基于源代码的，面向对象的，基于各种不同结构的等领域。 如在源程序基础上，j a i t l e s 等人在测试中针对布尔类型和枚举类型的数据使用遗 传算法结合程序依赖分析技术进行测试数据生成1 2 引。 应用启发式搜索算法针对e f s m 模型解决其测试数据生成也有一些研究。 ( 1 ) 遗传算法 k a l 碰等人使用遗传算法实现e f s m 模型中给定可行路径的测试数据自动生成。 这种方法把测试数据生成看作通过搜索找到能满足函数变量值的问题，为了应用遗传 算法，他们提出了一种新的适应度计算方法，在实验中与随机方法进行了比较，效率 得到了有效地提高【2 4 】。 i h l u c a 等人将基于搜索的启发式技术应用于测试数据生成，将模拟退火技术和基 因算法，以及粒子群算法都应用于测试数据自动生成中，并对生成的结果分别进行了 比较【2 5 1 。 ( 2 ) 模拟退火算法 随着模拟退火算法的发展，研究者也开始将其在测试数据生成中进行应用。 郭巍等人提出基于模拟退火多亲遗传算法的测试数据自动生成算法，给出算法中 适应度函数选择方法和变异函数退火控制策略，并分析了算法的实际应用结果【2 6 1 。 朱玉萍等人结合遗传算法( g a ) 的并行搜索结构特点和模拟退火算法( s a ) 的 概率突跳性特点，并结合自适应交叉操作和遗传操作，形成了一种新的自适应s a g a 北京化工大学硕j j 学位论文 混合优化算法。在测试数据自动生成系统中，经过实际程序的实验，表明该算法有更 强的搜索能力，可以更快的找到全局最优解【2 7 1 。 ( 3 ) 禁忌搜索算法 ， 1 9 8 6 年g l o v e r 提出禁忌搜索的思想以来，这一算法主要被广泛的应用于组合优 化、生产调度等现实领域，基于禁忌搜索算法的测试数据生成研究还比较少。这种算 法能够模拟人类智力过程，有效的避免迂回搜索，在解决调度问题中取得了很大的成 功。 考虑利用其全局搜索、防止迂回的的特点，将其应用于e f s m 测试数据生成问题， 将是一个比较新的应用。 d i a z 等人将禁忌搜索算法应用于结构性软件测试数据生成，提出了同时使用两种 价值函数函数来引导禁忌搜索算法的搜索方向，也就是基于双价值函数的禁忌搜索测 试数据生成。价值函数能够评估一个软件测试用例的质量，好的价值函数对于一个价 值生成器是很有用处的。d i a z 提出的禁忌搜索策略中一个适应度函数评估当前解是否 达到目标节点，另一个评估函数评估是否达到目标节点的父节点，并在测试执行前判 断当前解是否为被禁忌的测试数据。这一研究在针对于数据流结构和控制流结构的测 试中使用了禁忌搜索策略，取得了一定的结剁2 引。 遗传算法、禁忌搜索算法、模拟退火算法等不同的启发式搜索算法被越来越广泛 的应用于测试数据生成问题，使复杂的测试数据生成问题逐渐被解决，但是，测试数 据生成仍存在应用范围局限、效率低等问题，所以还需要进一步的研究。 1 3 本文的主要工作及组织结构 1 3 1 本文的主要工作 e f s m 模型可以精确刻画软件系统的动态行为，已被广泛的应用以描述面向对象 软件的对象行为及对象间的交互，因此，基于e f s m 的测试生成具有重要的研究意义 和实用价值。为此，本文探索了一种适应于e f s m 测试数据生成的禁忌搜索策略，实 现了e f s m 测试数据的自动生成，具体工作如下： ( 1 ) 通过研究基于e f s m 模型的测试序列生成及测试数据生成的方法，深入分 析了基于启发式搜索的e f s m 模型测试数据生成的应用。 ( 2 ) 研究了禁忌搜索算法的原理及应用，提出将禁忌搜索算法应用于e f s m 模 型的测试数据生成，对禁忌搜索策略中各操作的设置及参数的选定进行了详细设计， 并将禁忌搜索算法策略应用于e f s m 测试数据生成中，成功实现了e f s m 模型的测试 数据生成。 ( 3 ) 为了分析路径中不同特征因素对e f s m 测试数据生成效率的影响，将禁忌 6 第一章绪论 搜索算法策略应用于4 组( 共8 个) e f s m 模型进行实验，并记录其生成测试数据的 迭代次数与所花费的时间，通过相关性分析，得到了影响e f s m 测试数据生成效率的 关键因素。 ( 4 ) 为进一步探讨禁忌搜索算法与遗传算法的效率差异，本文根据关键因素，选 取适当的路径，分别将禁忌搜索算法与传统的遗传算法应用于e f s m 特定路径的测试 数据生成，并对生成时间进行了比较，结果表明禁忌搜索算法收敛速度快，生成效率 相对于遗传算法有很大提高。 1 3 2 本文的组织结构 本文第二章主要研究了禁忌搜索算法、遗传算法等启发式搜索算法的原理及其在 测试中的应用。 第三章详细分析了可扩展有限状态机e f s m 的特点及其表示。 第四章探讨了禁忌搜索算法应用于e f s m 测试数据自动生成的方法及策略，详细 设计了禁忌搜索算法应用于e f s m 测试数据生成各个关键操作的设置及其参数的选 定，将其应用于a t m 模型，成功生成了测试数据。 第五章通过一系列的实验说明将