（计算机应用技术专业论文）基于模拟退火算法的efsm模型测试数据自动生成.pdf

、 p r ”：，一瞄，1：e_；，k、 i，fpf、_l。藿1r，卜bi-，f 北京化工大学 硕士研究生学位论文答辩委员会决议书 研究生姓名：符盛宝专业：计算机应用技术 论文题目：轻型脚本引擎的研究与实现 指导教师姓名：张贝克 职称：见习教授 论文答辩日期： 2 0 1 1 0 5 2 6地点：科技楼4 0 9 室 论文答辩委员会成员 姓名职称工作单位本人签名 赵瑞莲教授北京化工大学 幽岛童 许南山副教授北京化工大学 浒殉哆 李辉副教授北京化工大学 着乏姿 王雪晶副教授北京化工大学 z 劝赢 肖亮副教授北京化工大学 唷南 注：此表用于存档，除本人签名务必用钢笔填写外，其余处必须用计算机打印。 答辩委员会对论文的评语( 选题意义、文献综述、论文所取得的成果及水平、学 风和论文写作水平、论文的不足之处) ： 论文丌发了一套轻量型脚本引擎，选题具有一定的理论意义和实用价值。 论文主要工作：。 1 设计并实现了一个v b l e t 的脚本引擎： 2 实现了脚本引擎与应用程序的集成。 论文结构较合理、写作较规范。论文工作表明作者掌握了本专业基础理论知 识，具备了基本的科研工作能力，论文达到了硕士学位论文要求的学术水平。 在论文答辩中，该学生表述较为清楚，回答问题基本正确。答辩委员会经无 记名投票，一致同意通过该学生的硕士学位论文答辩，建议授予该学生工学硕士 学位。 对学位论文水 优秀良好一般较差 平的总体评价 答辩委员会表决结果： 同意授予硕士学位5 票，不同意授予硕士学位o票， 弃权o 票。根据投票结果，答辩委员会做出建议授予该同学 硕士学位的决议。 答辩委员会主席签字声法厂乏 2 0 1 1 年5 月2 6 日 北京化工大学位论文原创性声高潮 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者签名： 丞兰差蛩 日期：2 11 f ：! l 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文的 规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京 化工大学。学校有权保留并向国家有关部门或机构送交论文的复印件 和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学 位论文。 保密论文注释：本学位论文属于保密范围，在土年解密后适用本授 权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：一丞兰鸳 日期： 丛 ：王：3 1 一一 导师签名幺轻 日期： 堂! ! ：王2 ， 学位论文数据集 中图分类号 t p 3 1 1 5 学科分类号 5 2 0 4 0 论文编号 1 0 叭0 2 0 1 1 0 6 9 5密级公开 学位授予单位代码 10 0 1 0 学位授予单位名称 北京化工大学 作者姓名程喜朝学号 2 0 0 8 0 0 0 6 9 5 获学位专业名称计算机应用技术获学位专业代码 0 8 12 0 3 课题来源 自然科学基金项目研究方向 软件测试与软件可靠性 论文题目基于模拟退火算法的e f s m 模型测试数据自动生成 关键词模拟退火算法，e f s m ，测试数据生成，启发式搜索算法，软件测试 论文答辩日期 2 0 1 1 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 模型的测试技术是一种新的测试技术，主要包括 测试序列生成和测试数据生成。其中，测试数据生成是软件测试领域研究 的热点和难点。目前，关于e f s m 模型测试数据自动生成技术介绍的文 献较少。已有文献中只采用了遗传算法在e f s m 模型上进行测试数据自 动生成，因此，尝试采用其它的启发式搜索算法在e f s m 模型上进行测 试数据自动生成的研究是一个值得探索的方向。 本文归纳总结了目前应用比较广泛的软件测试数据自动生成方法，研 究了启发式搜索算法，在此基础上，尝试使用模拟退火算法在e f s m 模 型上进行测试数据自动生成的研究。主要工作如下： 1 、应用模拟退火算法在e l ? s m 模型上进行测试数据自动生成。 2 、通过实验验证模拟退火算法在e f s m 模型上进行测试数据生成 的可行性。采用不同的模拟退火算法参数分析测试数据生成的 效果，对传统模拟退火算法加以改进，使生成效率进一步提高。 3 、将模拟退火算法，随机算法和遗传算法在测试数据生成稳定性 l 和效率方面进行了比较。 关键词：模拟退火算法，e f s m ，测试数据生成，启发式搜索算法，软件 测试 i i u i a t e da n n c a i i n g v a r i o u s 行e l d sf o ri t s i n t e l l i g e n t f e a t u r e s t h ec o m m o nh e u r i s t i cs e a r c ha l g o r i t h m sa r eg e n e t i c a l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h m ，t a b us e a r c ha l g o r i t h ma n ds oo n t h e ya r eo r e nu s e dt ot e s tc a s ea u t o m a t i cg e n e r a t i o ni ns o r w a r et e s t i n gf i e l d m o d e li n t r o d u c e st h ef u n c t i o na n db e h a v i o ro fs o f t w a r es y s t e m i tc o u l d m a k et e s t i n gp r o c e s sm o r ec l e a ra n dm o r eo r d e r e f s mm o d e l - b a s e dt e s t i n g t e c h n i q u ei s an e wt e s t i n gt e c h n i q u e ，m a i n l yi n c l u d et e s ts e q u e n c eg e n e r a t i o n a n dt e s td a t ag e n e r a t i o n a m o n gt h e m ，t e s td a t ag e n e r a t i o ni sh o ta n dd i m c u l t o fs o f t w a r et e s t i n gr e s e a r c hn e l d c u r r e n t l y ，t h el i t e r a t u r e sa r el e s sa b o u t e f s mm o d e lt e s td a t aa u t o m a t i cg e n e r a t i o nt e c h n i q u e l i t e r a t u r e so n l yu s e d g e n e t i ca l g o r i t h m f o rt e s td a t aa u t o m a t i c g e n e r a t i o n o ne f s mm o d e l t h e r e f o r e ，t 秽t ou s eo t h e rh e u r i s t i cs e a r c ha l g o r i t h mo ne f s mm o d e lf o rt e s t d a t aa u t o m a t i cg e n e r a t i o ni saw o i r t h w h i l ed i r e c t i o nt oe x p l o r e t h i sp a p e rs u m m a r i z e st h em o r ee x t e n s i v em e t h o dw h i c ha p p l i e dt o s o 胁a r et e s td a t aa u t o m a t i cg e n e r a t i o n s t u d yt h eh e u r i s t i cs e a r c ha l g o “t h m ， o nt h i sb a s i s ，t r yt ou s et h es i m u l a t e da n n e a l i n ga l g o r i t h mo ne f s mm o d e l t o i i i 北京化i ：人学硕l ：学化论文 r e s e a r c ht h et e s td a t aa u t o m a t i cg c n e r a t i o n m a i nt a s ka r ea sf o l l o w s ： 1 s i m u l a t e da n n e a l i n gi su s e do ne f s mm o d e lf o rt e s td a t aa u t o m a t i c g e n e r a t i o n 2 t h r o u g he x p e r i m e n t st ov e r i f yt h ef e a s i b i l i t yo fs i m u l a t e da n n e a l i n g a p p l i e do ne f s mm o d e lf o rt e s td a t aa u t o m a t i cg e n e r a t i o n a n a l y z i n g t h ee f i f e c to ft e s td a t ag e n e r a t i o nw i t hd i f f r e n ts i m u l a t e da n n e a l i n g p a r a m e t e r s ，a n dt h et r a d i t i o n a l s i m u l a t e da n n e a l i n gi s i m p r o v e d ，s o t h a tt h eg e n e r a t i o ne m c i e n c y 如r t h e ri m p r o v e d 3 c o m p a r e t h e e 饿c i e n c y a n ds t a b i l i t yi nt e s td a t ag e n e r a t i o nw i t h s i m u l a t e d a n n e a l i n ga i g o r i t h m ， r a n d o m a l g o r i t h m a n d g e n e t i c a l g o r i t h m 1 5 论文组织结构8 1 6 本章小结8 第二章基于启发式搜索的软件测试技术9 2 1 启发式搜索算法概述9 2 1 1 遗传算法9 2 1 2 模拟退火算法1 1 2 1 3 禁忌搜索算法1 4 2 1 4 其它搜索算法1 6 2 2 基于启发式搜索的软件测试用例自动生成1 7 2 2 1 基于启发式搜索的测试序列生成1 7 2 2 2 基于启发式搜索的测试数据生成1 7 2 3 本章小结1 8 第三章基于e f s m 模型的软件测试19 3 1 有限状态机( f s m ) 模型及其测试方法1 9 3 1 1 有限状态机( f s m ) 模型1 9 3 1 2 基于f s m 的五种经典测试方法。2 l 3 2 扩展有限状态机( e f s m ) 模型2 2 3 3 基于e f s m 模型的测试覆盖准则2 4 3 4 基于e f s m 模型的测试数据牛成方法2 5 3 5 本章小结2 6 第四章基于模拟退火算法的e f s m 模型测试数据自动生成2 7 4 1 基十模拟退火算法的e f s m 模型测试数据自动生成框架2 7 v 1 1 l 2 2 3 5 7 北京化1 ：大学硕i ：学化论文 4 2 基于模拟退火算法的测试数据表示 4 3 模拟退火算法能量函数设计 4 4 模拟退火算法构成要素设置 4 4 1 模拟退火算法邻域解生成策略 4 4 2 模拟退火算法温度参数控制 4 4 3 模拟退火算法等温过程 4 5 基丁模拟退火算法的测试生成终止条件 4 6 模拟退火算法的改进 4 7 木章小结 第五章算法实现和实验结果分析 5 1 基于广度优先遍历策略的测试序列牛成 5 2 基于模拟退火算法的e f s m 模型测试数据自动生成实现 5 3 基于模拟退火算法的e f s m 模型测试数据生成实验及结果分析3 7 5 3 1 被测e f s m 模型3 7 5 3 2 模拟退火算法的e f s m 模型测试数据自动生成的可行性3 7 5 3 3e f s m 模型测试数据白动生成的实验步骤3 8 5 3 4 随机算法，遗传算法和模拟退火算法的实验结果与比较3 8 5 3 5 模拟退火算法构成要素对实验结果的影响4 2 5 4 本章小结4 5 第六章结论与展望4 7 6 1 结束语4 7 6 2 进一步的工作4 7 参考文献4 9 致谢5 3 研究成果及发表的学术论文5 5 作者和导师简介，5 7 v l 1 4p r i m a 呵w o r ko f t h i sp a p e r 7 1 5c o n f i g u r a t i o no f t h i sp a p e r 8 1 6s u m m a 巧o f t h i sc h a p t e r 8 c h a p t e r2s o f t w a r et e s t i n gt e c h n o l o g yb a s e do nh e u r i s t i cs e a r c h 9 2 10 v e r v i e wo f h e u r i s t i cs e a r c ha l g o r i t h m 9 2 1 1g e n e t i ca l g o r i t h m 9 2 1 2s i m u l a t e da i m e a l i n g 1 l 2 1 _ 3t a b us e a r c h 1 4 2 1 4o t h e rs e a r c ha l g o r i t h m 1 6 2 2s o f h v a r et e s tc a s ea u t o m a t i cg e n e r a t i o nb a s e do nh e u r i s t i cs e a r c h l7 2 2 1t e s ts e q u e n c eg e n e r a t i o nb a s e do nh e u r i s t i cs e a r c h 1 7 2 2 2t e s td a t ag e n e r a t i o nb a s e do nh c u r i s t i cs e a r c h 1 7 2 3s u m m a 叫o f t h i sc h a p t e r 1 8 c h a p t e r3s o f t w a r et e s t i n gb a s e do ne f s m m o d e l 1 9 3 1f i n i t es t a t em a c h i n em o d e la n dt e s tm e t h o d 1 9 3 1 1f i n i t es t a t em a c h i n em o d e l 1 9 3 1 2f i v ec l a s s i c a lt e s tm e t h o d sb a s e do nf s m 2 l 3 2e x t e n d e d 丘n i t es t a t em a c h i n em o d e i 2 2 3 31 e s tc o v e r a g ec r i t e r i ab a s e do ne f s mm o d e l ，2 4 3 4t b s td a t ag e n e r a t i o nm e t h o db a s e do ne f s mm o d e l 一2 5 3 5s u m m a r yo f t h i sc h a p t e r 2 6 c h a p t e r4t b s td a t aa u t o m a t i cg e n e r a t i o nb a s e do ns i m u l a t e da n n e a l i n g f o re f s mm o d e l 2 7 v i l 5 1t e s ts e q u e n c eg e n e r a t i o nb a s e do nb r e a d t h6 r s ts e a r c hs t r a t e g y 3 3 5 2a c h i e v e m e n to ft e s td a t aa u t o m a t i cg e n e r a t i o nb a s e do ns i m u l a t e da n n e a l i n gf o re f s m m o d e l 3 4 5 3t e s td a t ag e n e r a t i o ne x p e r i m e n t sa n dr e s u l t sa n a l y s i sb a s e do ns i m u l a t e da n n e a l i n g a l g o r i t h mf o re f s mm o d e l 3 7 5 3 1t h et e s t e dm o d e l 3 7 5 3 2f e a s i b i l i t yt e s td a t aa u t o m a t i cg e n e r a t i o ni ns i m u l a t e da n n e a l i n ga l g o r i t h mf o re f s m m o d e l 3 7 5 3 3e x p e r i m e n t a la p p r o a c ho ft e s td a t aa u t o m a t i cg e n e r a t i o nf o re f s mm o d e l 38 5 3 4e x p e r i m e n t a lr e s u l t sa n dc o m p a r i s o no fr a n d o ma l g o “t h m ，g e n e t i ca l g o r i t h ma n d s i m u l a t e da n n e a l i n ga l g o t h m 3 8 5 3 5t h ee f 佗c to f e x p e r i m e n t a lr e s u l tw i t hf a c t o r si ns i m u l a t e da n n e a l i n ga l g o r i t h m 一4 2 5 4s u m m a r yo f t h i sc h a p t e r 4 5 c h a p t e r6c o n c l u s i o na n df h t u r e ：4 7 6 1c o n c l u s i o n 4 7 6 2f u t l l r ew o r k 4 7 r e f e r e n c e s 4 9 a c k n o w l e d g c m e n t 5 3 r e s e a r c hf i n d i n g sa n ds c i e n c ep a p e rp u b l i s h e d 5 5 b r i e fi n t r o d u c t i o nt oa u t h o ra n dt u t or 5 7 i x 北京化i ：人学侦i ：学化论文 x 凳一章绪论 1 1 课题研究背景和意义 第一章绪论 当今世界处十信息时代，越来越多的软件产品应月j 在生产和生活之t ，。随着生产 和生活需要处理的问题日益复杂，导致处理这些问题的软件规模逐渐扩大，凶此，软 件的复杂度也急剧增加，软件出错率也越来越高，从向由软件的错误和缺陷所引起的 后果也越来越严重。因此，软件的质量和口j 靠性已引起了人们的高度重视。软件测试 是保障软件质量和可靠性的重要手段，足软件工程的重要组成部分。软件测试r 作直 接决定着软件产品的质量。大量统计资料表明，软件测试阶段投入工作量要占软件开 发总工作量的4 0 以卜，而在测试中所投入的开销要占软件开发总成本的3 0 剑 5 0 ，甚至更纠。冈此，软件测试己成为软件整个开发过程i f l 尤为重要的环节。 软件测试的重点和难点所在是测试数据的生成问题，测试数据生成也足软件测试 过程中的核心。最原始的测试数据生成方法是采用手工设计，后来传统软什测试技术 的诞生，取代了手工设计测试数据。随着软件规模和复杂度的急剧提高，传统技术已 无法满足大型的，复杂的软件测试的需要。因此，改进软件测试方法，研究有效的测 试数据生成工具，提高软件测试的效率，以致降低软件测试的成本，保证软件产品的 质量，已迫在眉睫。目前，软件测试技术已越来越受剑软件界人士的重视，软件测试 已成为软件技术研究的重点和难点。 近年来，软件界人士对基于模型的软件测试技术产生了极大兴趣。一般来讲，一 个模犁是一个软件系统的抽象或概括。基丁模犁测试的有效性主要归结于它提供的自 动化程度。基于扩展有限状态机的测试技术是各种基于模型测试技术的理论基础，这 些技术最终都要把被测的基于状态的j j ：为表示成扩展有限状态机，然后在此皋础上自 动或半自动的生成测试数据。基于扩展有限状态机的测试数据自动生成这一技术的实 现，将大大改变以律靠直觉、经验牛成测试数据的手 ：技术，无疑将使软件测试的效 率显著提高，减轻人们在编写大餐测试数据过程【| 1 所付出的人力，物力以及财力等。 因此，研究基于扩展有限状态机的测试数据自动生成这项技术，对实现软件测试的自 动化具有l 分重要的意义。 1 2 国内外研究现状 1 9 7 2 年，美国的北卡罗来纳大学。片次召开了软件测试会议，这是软件测试领域的 一个里程碑。1 9 7 5 年，g o o d e n o u 曲和g e r h a n 首次提m 测试数据选择理论f 2 】， 软件 测试这门学科被提高到了理论高度。1 9 8 3 年，i e e e 给出了软件测试的定义：“使用人 l 北京化【：人学硕l ：学化论文 工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求 或是弄清楚预期结果与实际结果之问的差别”。上世纪9 0 年代，软件测试和软件质量 管理逐渐成为软件工程领域研究的热点。i e e e 出台了些晕要的标准，例如，软件 测试确认与验证计划标准i e e e a n s is t d 1 0 1 2 、软件测试复查和审计标准 i e e e a n s is t d 1 0 2 8 、软件质量保证计划标准i e e e a n s is t d 7 3 0 等。 目前，软件测试领域研究的重点主要集中在测试数据自动生成，测试序列自动生 成以及自动化测试工具的研制等。在软件测试领域中，基于扩展有限状态机的软件测 试技术己逐步成为研究的热点。在基于扩展仃限状态机的测试数据生成技术中，主要 包括两个方面，一是测试序列自动生成，二是测试数据f j 动生成。测试序列自动生成 技术的关键【：；k 1 素在于可行性分析，a s k a l a j i 等人提出了一种基于迁移中数据流的依 赖关系进行可行性分析的方法，该方法与遗传算法结合在一起，搜索可行的测试序列。 r a m a l i g o m 等人提出了一种使用上下文独立的单一输入序列( c i u s ) 的概念，使用此概 念间接地解决可执行问题，并根据c i u s 来构造测试输入序列。对于测试数据自动生 成技术，同内外已有了一些研究成果，例如，n m a n s o u r 和m s a l a m e 提出了使用遗 传算法和模拟退火算法在控制流程图上自动生成测试数据。r z h a o ，m h a m a n 和z l i 在扩展自限状态机卜针对基于搜索的测试数据门动生成技术做了大量的实验，这些 实验成果对提高基于扩展有限状态机的测试数据自动生成技术的效率有重要的指导 意义。另外，前人还曾使用松弛法，函数最小化法，分段梯度最优下降算法等在扩展 有限状态机t 针对测试数据自动生成进行了研究。 1 3 基于模型的软件测试概述 近年来，很多软件设计和开发人员将模型用于软件工程之中，因此，在模型的基 础上做测试也逐渐受到人们的欢迎。软件产品的功能和行为用模型表示之后，测试便 可以进行得很合理，很严谨。下面将简单概述基于模型的软件测试技术。 1 3 1 基于模型的软件测试 模型概括或抽象了一个系统，从一个特定的视角和一个特定的抽象层次描述建模 的系统。就软件而言，我们可以给出如下定义： 模型是对软件行为和功能的描述。软件系统接收测试数据，经过一些条件，发生 动作，输m 一些状态，模块问的数据流等均可以描述软件行为。软件系统接收事件， 输出结果等町以描述软件功能。模型需要与现实中的系统相符合，并且要求其尽可能 形式化，从而模型便具有可重用性，可移植性，可共享性等特点。迄今为止，人们已 研究出了很多模犁，他们从各个角度描述了软件的行为。例如，数据流、控制流、程 序依赖关系罔等通过分析源代码结构描述软件系统的行为。决策表、状态机等描述软 2 第一章绪论 件系统的黑盒行为，也就足系统的外部行为。 在软件测试领域中，常用的模型丰要包括：有限状态机，扩展有限状态机，状态 图，m a r k o v 链，u m l 模型等。下面对这些模型逐进行介绍。 有限状态机或有限状态自动机或简称状态机，是表示有限个状态以及在这螳状态 之间的迁移和动作等行为的数学模型。状态迁移图和状态迁移矩阵是有限状态机常见 的两种表示形式。在软件工程产生之前，有限状态机相关理论和技术就已经非常成熟。 有限状态机对数字系统的设计具有十分霞要的作用。有限状态机在数字电路系统中， 是一种十分重要的时序逻辑电路模块。在计算机硬件部件的设计和测试中，有限状态 机的使用已经成为一种标准。文献【3 较早提出将有限状态机技术用于软件设计和测试 中。可是复杂的，大型的软件会产生很大的有限状态机，其创建和维护费用会很高， 这是有限状态机的一个局限性所在。 扩展有限状态机模型是对有限状态机模型的一个扩展。它是在有限状态机模型的 基础上增加了变量、操作以及状态迁移的前置条件。扩展有限状态机模型是很多形式 化规约描述语言( 例如，s d l ) 的基础模型，被广泛用于嵌入式软件，通信软件和面 向对象的软件中。它可以精确地描述软件的动态行为，因此，基于扩展有限状态的测 试技术可以应用到很多领域，具有重要的研究意义。 状态图最初提出时是为了给一个复杂反应系统的控制需求建模。后来，h a r e l 又 增加了通信、并发和播机制等，提i l j 了适合描述复杂系统的状态图。状态图可以说 是有限状态机的扩展，主要用于解决复杂的，大型的交互式系统的建模问题。 m a r k o v 链是一个随机模型，它用于描述如何使用软件。m a r k o v 链很像有限状态 机，可以认为是一种概率性有限状态机。m a r k o v 链不仅用于生成测试用例，还用于 收集和分析失效数据，从而可以对软件的各种质罱参数进行评什和度量( 如可靠性、 平均失效时间等) 【4 1 。 u m l 是用来对软件密集系统进行町视化建模的一利- 语言，最适于数据建模、对 象建模以及组件建模等。u m l 模型具有很强的描述和管理能力，它综合了多种模型 的优点，可以从不同的视角描述系统。现实【f i ，众多软件企业和开发者都采用u m l 建模。u m l 将多种方法的成果融合在一起，具有定义良好、功能强大、普遍适用的 优点。这些优点，为基于模型的软件测试提供了非常好的契机。目前，基于u m l 模 型的测试方法逐渐成为研究的热点，主要集中在动态模型方面，包括用例图、类图、 状念图以及活动图等。 1 3 2 启发式搜索算法概述 启发式搜索是利用与问题相关的启发信息在搜索空间中寻找最优解的过程。它对 当前搜索剑的位置进行估价，然后从这些位置中选出认为比较好的位置，再从该位置 北京化l ：大学硕f ：学化论文 继续展开搜索，直至搜索到最优解或满足特定目标。启发式搜索与传统搜索的不同之 处在于，它在搜索过程中加入了| 卜问题切实相关的启发信息，这些信息对于沿着最有 希单的方向搜索到目标十分有用，可以将大量无效的搜索路径忽略掉，提高了搜索的 效率。在启发式搜索中，启发信息足用于对位簧的估价，凶此，采用不同的启发信息 对位置会有不同的估价结果，选择合适的启发信息是启发式搜索的关键。目前，应用 比较广泛的启发式搜索算法有以下儿种： 遗传算法( g e n e t i ca l g o r i t h m ) ，简称g a ，是人类学习自身进化这一宏观过程的结 果，是一种更为宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与进 化过程，它把待解决问题的参数编成二进制码( 或其它编码) ，即基因，若干基因组成 一个染色体( 个体) ，许多个体在一起进行类似于自然选择、交叉和变异的运算，经过 多次重复迭代直至最后的优化结果l5 | 。遗传算法最早是由j o h nh h o l l a n d 教授及其学 生于2 0 世纪6 0 年代末提出。后来，d ej o n g 和g o l d b e r g 等人做了大量的工作，遗传 算法变得更加完善。剑目前为止，遗传算法是智能优化算法中应用最为广泛也最为成 功的算法。由于遗传算法不依赖于问题的具体应用领域，对问题的种类有很强的鲁棒 性，所以许多学科均可采用。现实中，它广泛应用于函数优化，组合优化，人工智能， 自动控制等各个领域。 模拟退火( s i m u l a t e da n n e a l i n g ) 算法，简称s a ，是来源于金属固体的退火原理。 首先将固体加热至充分i 每，再让其徐徐冷却。加热时，温度逐渐升高，分子逐渐变得 无序，内能逐渐变大。当固体逐渐冷却时，分子逐渐变得有序，内能逐渐变小。处于 每个温度时，分子均会达到、f 衡状态，处于常温时，分子达到基态，此时，内能最小。 它其实是扩展了局部搜索算法，弓局部搜索算法不同之处在于它是以一定的概率选择 邻域中费用值大的状态。从理论上来讲，它足一个伞局优化算法。模拟退火算法最早 的思想由m e t r o p o l i s 【6 】在1 9 5 3 年提出，k i r k p a t r i c k i7 j 在1 9 8 3 年成功地将其应用在组合 最优化问题l 二。目前，模拟退火算法广泛应用住图像处理，生产调度，机器学习等工 程领域。 蚁群算法( a n tc o l o n ya l g o r i t h m ) ，也称为蚁群优化算法，简称a c a ，来源于人 们对蚁群行为的研究成果。基本思想是模仿蚂蚁使用信息素为通信媒介，进而显示出 的社会行为。由于该算法具有随机性，试探性的特点，所以可用于求解各种不同的组 合优化问题。1 9 9 2 年，d o r i g o f 8 】在他的博士论文中首先提出了一种全新的蚁群系统启 发式算法，从此，一种新的优化算法逐渐发展起来。最初该算法仅用于解决t s p 问题， 后来，经过人们多年的研究与完善，其它各个领域也开始出现使用蚁群算法。目前， 蚁群算法比较常见的应用领域有，图着色问题、车间调度作业问题、集成电路设计、 通讯网络中的路由问题以及负载，r 衡问题等。其中最为成功的应用是解决组合优化问 题。 禁忌搜索( t a b us e a r c h ) 算法，简称t s ，是人们模仿人类的记忆功能的研究成果， 4 第一章绪论 是局部邻域搜索算法的推广，是人工智能在组合最优化算法中的一个成功应用。该算 法使用禁忌表禁止搜索已搜索的区域，从而避免迂回搜索带来的无效性。最早是由 g 1 0 v e r 一10 j 在1 9 8 6 年提出，后来，逐渐发展成为套完整的算法。它的最大特点是使 用禁忌技术，对已做的工作禁止重复进行。在禁忌搜索算法中，禁忌表仔储了已搜索 到的局部最优点和到达局部最优点所经过的操作，在接下来的搜索中，通过读取该禁 忌表有选择性的进行某些操作，从而可以避免陷入局部最优，填补了局部邻域搜索的 不足。到目前为止，禁忌搜索算法在组合优化、电力系统、生产调度、神经网络等领 域已得到成功的应用。近年来，许多人在函数全局优化方面也采用该算法做了较多的 研究，而且具有良好的发展趋势。 粒子群算法，也称为粒子群优化( p a r t i c l es w a n i l0 p t i m i z a t i o n ) 算法，简称p s o ， 来源于人们对鸟群捕食行为的研究。它是近年米逐渐发展起来的一种新的进化算法。 最甲是由e b e r h a n 博士和k e n n e d y 博j 仁j 在1 9 9 5 年一个关于神绎网络的阁际会议上 提出。与遗传算法类似，从随机解开始搜索，通过适应度评价解的好坏，不停地迭代， 直至找到最优解。但是它与遗传算法相比又有不同之处，它没有交叉和变异操作，比 遗传算法要简单。它通过当前已搜索到的最优解来寻找伞局最优解。与遗传算法相比， 它的优势在于没有许多参数需要调整且简单容易实现。该算法具有精度高、收敛快、 容易实现等优点，而且已引起了学术界中研究人员的重视。到目前为止，该算法已在 模式识别、信号处理、神经网络、函数优化等领域得到广泛的应用。 1 3 3 面向模型路径的测试数据生成方法 软件测试数据自动生成可以分为面向功能测试数据生成和面向结构测试数据生 成两人类。在面向结构测试数据生成中，面向路径的软件测试数据自动生成方法是软 件界人十研究的热点。丰要分为【l2 j ：随机法、静态法、动态法。文献 1 3 】中介绍了一 种试探法，主要是指遗传算法，模拟退火算法等启发式搜索算法在测试数据自动生成 中的应用。下面将对这p 【 种方法逐一进行介绍。 随机法的原理比较简单，就足往输入域的范同内随机采样生成测试数据。使用该 方法进行自动化测试实现起来比较容易，生成一个测试数据所花费的成本较小，对于 输入域的大小可以不受限制，可以在短时问内生成大量的测试数据。但足如果针对某 种覆盖准则生成测试数据，需要大量的测试数据运行被测程序，而且具彳j 相同效果的 测试数据占很大比例，凶此，测试效率会变得很低。目前，关于随机法测试的研究进 展比较缓慢。文献 1 4 】归纳了随机法在各种软件系统开发过程中的单元测试阶段自动 生成测试数据的实际经验，以及在集成测试和系统测试阶段的经验成果。文献【1 5 】提 出了一种使用随机法生成自检测试数据的方法，这螳测试数据在执行被测程序时便可 以发现程序中的错误。但是由于随机法对于线性路径约束具有不完备性，所以对于而 析，识别出该路径的输入变量。然后使用输入变镶的表达式全部代替路径中赋值语句 的左侧部分，对于谓词中的变量表达式也全部使用输入变量的表达式代替。最后，便 得到了只含有输入变量的等式或不等式方程组，再对该方程组进行求解。采用符号执 行法时，输入变量可以是具体的数值，也可以是符号值。由于符号执行法对于被测程 序中的循环条件，数组类型以及函数调用难以处理，而且一般需要进行大量的代数运 算，所以该方法的应用范围受到了一定的限制。区间算术法是对被测路径中每条语句 进行静态分析，每个变量均存储丁变量表中，每个约束关系均存储于正则约束表中。 它是用布尔变最穷举，l 又：间划分，区间削减等方法使得变量取值范围减小，直到生成 被测路径的测试数据或者发现该路径不可行。但是，当变鼍的取值范围无限制时，就 不能对区间进行穷举划分，所以使用该方法也具有定的限制。另外，该方法会产生 大量的中间结果，并且这些结果需要大晕的空间进行存储，这是该方法的一个缺点。 动态法是基于程序的实际运行，其生成测试数据的过程足确定的。动态法的基本 思想是随机从输入域中生成一个初始解作为被测程序的输入值，然后不断的运行程 序，根据运行结果修改输入值，以致目标路径与实际执行路径越来越近，直至两条路 径相同。动态法有迭代松弛 1 9 】，k o r e l 【2 0 】等方法。迭代松弛法是为了解决非线性约束 问题而提出的。它集合了动态法和静态法的优点，使用被测路径中的各输入变量构造 了一个线性约束系统，一般情况下，该系统可以避免回溯技术造成的浪费。该线性约 束系统是通过采用程序切片的思想【2 ，从输入域中随机牛成一组解，然后利用该解分 析出被测路径一 ，的各个谓词与输入变量之间的依赖关