（计算机应用技术专业论文）基于改进型遗传算法的面向路径测试数据生成.pdf

学位论文数据集 中图分类号 t p 3 1 1 5 学科分类号 5 2 0 4 0 论文编号 10 0 1 0 2 0 1 l0 7 4 8 密级 公开 学位授予单位代码 1 0 0 l o 学位授予单位名称北京化工大学 作者姓名 王林 学号 2 0 0 8 0 0 0 7 4 8 获学位专业名称计算机应用技术获学位专业代码 0 8 1 2 0 3 课题来源自然科学基金项目研究方向软件测试与软件可靠性 论文题目基于改进型遗传算法的面向路径测试数据生成 关键词遗传算法；程序路径；测试数据生成；程序结构信息 论文答辩日期 2 0 1 1 s 2 6宰论文类型 基础研究 学位论文评阅及答辩委员会情况 姓名职称工作单位学科专长 指导教师赵瑞莲教授北京化工大学软件测试与软件可靠性 过程工业监测、编译技 评阅人l彭四伟副教授北京化工大学 术应用、并行计算 评阅人2赵会群教授北方工业大学软件测试 评阅人3 评阅人4 评阅人5 分布式系统、网格计算、 答辩委员会主席赵英教授北京化工大学 计算机网络 答辩委员1山岚教授北京化工大学网络信息获取技术研究 过程工业监测、编译技 答辩委员2彭四伟副教授北京化工大学 术应用并行计算 答辩委员3张杰副教授北京化工大学智能信息处理 答辩委员4聂伟副教授北京化工大学移动通信技术 答辩委员5 注：一论文类型：1 基础研究2 应用研究3 开发研究4 其它 二中图分类号在中国图书资料分类法查询。 三学科分类号在中华人民共和国国家标准( g b t1 3 7 4 5 9 ) 学科分类与代码中 查询。 四论文编号由单位代码和年份及学号的后四位组成。 0茎呈3咖477删8i 茎茎y 摘要 基于改进型遗传算法的面向路径测试数据生成 摘要 测试数据生成是软件测试过程中最重要的一环。如何在有限的时间及 资源条件下生成尽可能有效的测试数据是一个具有重要理论意义和应用 价值的课题。手工生成测试数据需要耗费大量的人力物力，并且生成的测 试数据不够充分且具有大量的冗余。软件测试数据的自动生成可以提高软 件测试的效率。 在基于软件结构的测试中，路径覆盖是一种常用的测试覆盖准则。遗 传算法是一种模拟自然界生物进化过程的随机搜索算法，通过对个体进行 选择、交叉、变异等操作，通过逐步迭代来生成满足要求的解。由于其适 应性强、具有全局搜索能力等特点，在面向路径的测试数据生成中广泛应 用。但在用传统遗传算法生成面向路径的测试数据时。没有考虑被测程序 的结构信息，因而算法迭代次数过多，测试生成效率低下。 为提高软件测试数据的生成效率，本文提出了一种改进的遗传算法， 利用被测程序的结构信息来辅助交叉、变异点的选取，通过更有针对性的 交叉、变异操作来降低测试数据生成所需的迭代次数，并开发了一套利用 改进型遗传算法进行面向路径测试数据自动生成的原型系统，可以实现c 语言被测程序的测试数据自动生成。大量实验表明，本文提出的改进型遗 传算法在应用于面向路径的测试数据自动生成时，比传统遗传算法具有更 快的收敛速度，更高的测试数据生成效率。 t 北京化工人学硕： ：学位论文 关键词：遗传算法，程序路径，测试数据生成，程序结构信息 a b s t r a c t 一一 p a t h o r i e n t e dt e s td a t ag e n e r a t i o nb a s e do nt o d i f i e dg e n e t i c a 1 9 0 r i t h m a b s t r a c t 1 s td a t ag e n e r a t i o ni sak e yp o i n ti ns o r w a r et e s t i n gp r o c e s s h o wt o g e n e r a t ee 行e c t i v et e s td a t au n d e r al i m i t e dt i m ea n dr e s o u r c ei so fg r e a tv a l u e i nb o t ht h e o r e t i c a la n da p p l i e da s p e c t s m a n u a l l yg e n e r a t i n g t e s td a t a c o n s u m e st o om u c hr e s o u r c ea n dt h et e s td a t ai sa l w a y si n s u 伍c i e n ta n d r e d u n d a n t a u t o m a t i ct e s td a t ag e n e r a t i o n w i l lm a k es o r w a r et e s tm o r e e 伍c i e n t i ns t r u c n l r a l t e s t i n g ，p a t hc o v e r a g ei sap o p u l a rc o v e r a g ec r i t e r i o n g e n e t i c a l g o r i t h m ( g a ) i sar a n d o m - b a s e d s e a r c ha l g o r i t h mw h i c hs i m u l a t e st h e n a m r a le v o l u t i o np r o c e s s b yc o n d u c t i n gt h es e l e c t i o n ，c i o s s o v e ra n d m u t a t i o n o p e r a t i o n s ，g ai st 咖n g t og e n e r a t et h es o l u t i o nd u r i n gam o u n to fi t e r a t i o n s d u et oi t sa d a p t a b i l i t ya n d9 1 0 b a ls e a r c h i n g2 l b i l i t y ；g e n e t i cg a h a sb e e n w i d e l yu s e di np a t h o n e n t e dt e s t d a t ag e n e r a t i o n h o w e v e r g ad o e sn o t c o n s i d e rt h es t r u c t l l r a li n f o m a t i o no ft h ep r o g r a mu n d e rt e s tw h e ng e n e r a t i n g p a t h o n e n t e dt e s t d a t a t h u si ts u f f e r s 行o mh i g hi t e r a t i o nt i m e sa n dl o w e f ! f i c i e n c y i no r d e rt oi m p r o v et h et e s td a t ag e n e r a t i o ne 伍c i e n c y ；t h i sp a p e rp r o p o s e s am o d i f i e dg e n e t i ca l g o r i t h m ( m g a ) w h i c hu s e ss t r u c t u r a l i n f o m a t i o no f t h e m 北京化t 人学硕上学位论文 p r o g r a mu n d e rt e s tt oh e l pc h o o s i n gt h ec r o s s o v e ra n dm u t a t i o np o i n t w i t h j 111， t n en e l po tp r e c l s ec r o s s o v e ra n dm u t a t l o no p e r a t i o n s ，t h ei t e r a t i o nt i m e s n e e d e dw h e n g e n e r a t i n gt e s td a t ac a nb er e d u c e d b e s i d e s ，ap a t h o r i e n t e dt e s t d a t ag e n e r a t i o np r o t o t y p es y s t e mw h i c hu s e st h em o d i f i e dg e n e t i ca l g o r i t h m h a sb e e nd e v e l o p e d u s i n gt h i sp r o t o t y p es y s t e m ，t e s td a t ao fc p r o g r a m sc a n b eg e n e r a t e da u t o m a t i c a l l y al o to fe x p e r i m e n t ss h o wt h a tm g ah a sf a s t e r c o n v e 唱e n c es p e e da n dh i g h e rt e s td a t ag e n e r a t i o ne f j e i c i e n c yw h e na p p l i e di n p a t h - o r i e n t e dt e s td a t ag e n e r a t i o n k e y w o r d s ：g e n e t i ca l g o r i t h m ，p r o g r a mp a t h ，t e s td a t ag e n e r a t i o n ，p r o g r a m s t l l l c t l l r a li n f o n n a t i o n i v 目录 目录 第一章绪论1 1 1 课题研究背景及意义一1 1 2 国内外研究现状2 1 3 论文主要贡献3 1 4 论文组织结构4 第二章面向程序路径的测试数据生成方法5 2 1 面向路径测试数据生成概述5 2 1 1 程序路径的定义s 2 1 2 面向路径测试数据覆盖准则8 2 2 基于随机法的面向路径测试数据生成8 2 3 基于静态法的面向路径测试数据生成8 2 4 基于启发式搜索算法的面向路径测试数据生成9 2 4 1 模拟退火算法9 2 4 2 禁忌搜索算法9 2 4 3 遗传算法1 0 第三章基于改进型遗传算法的面向路径测试数据生成。1 5 3 1 改进型遗传算法的测试数据生成思想1 s 3 2 被测程序结构信息的识别1 5 3 3 改进型遗传算法的设计1 7 3 3 1 编码策略的选取1 7 3 3 2 适应度函数的设计1 7 3 3 3 遗传策略的设计1 8 第四章原型系统的设计与实现2 1 v 北京化t 大学硕上学位论文 4 1 原型系统实现架构2 1 4 2 编译系统2 2 4 3 虚拟机系统2 5 4 3 1 程序路径信息的识别。2 7 4 3 2 程序结构信息的识别2 7 4 4 测试数据生成系统2 7 第五章实验及结果分析2 9 5 1 实验对象2 9 5 2 实验设计及结果分析3 0 第六章结论与展望3 5 6 1 结论2 9 6 2 未来工作3 0 参考文献3 7 致谢3 9 研究成果及发表的学术论文4 1 ： 作者与导师简介4 3 v i c o n t t s co n t e n t s c h a p t e r 1i n t r o d u c t i o n ”1 1 1r e s e a r c hb a c k g r o u n da n dm e a i l i n g 1 1 21 1 1 t e m a t i o n a la j l dn a t i o n a lr e s e a r c hs t a t l l s 2 1 3m a i nc o n t d b u t i o n 3 1 4p a p e rs t n l c t u r e 4 c h a p t e r 2p a t h o r i e n t e dt e s td a t ag e n e r a t i o n 5 2 1b r i e fo fp a t h o e n t e dt e s td a t ag e n e r a t i o n 5 2 1 1d e 6 n i t i o no fp r o 矿锄p a t h s 2 1 2c o v e r a g ec r i t e n a ”8 2 2p a t l l 一鲥e n t e dt e s td a t ag e n e r a t i o nb a s e d0 n 础【1 d o ms e a r c h 8 2 3p a m o r i e n t e dt e s td a t ag e n e r a t i o nb a s e do ns t a t i ca n a l y s i s 8 2 4p a t h o r i e l l t e dt e s td a t ag e n e r a t i o nb a s e do nh e u s t i cs e a r c ha l g o r i m m 9 2 4 1s i m u l a t e da n n e a l i n ga 1 9 0 d c h m 9 2 4 2t a l b us e a r c h i n ga l g o n t h m 9 2 4 3g e n e t i c9 l g o r i t h m 1 0 c h a p t e r3p a t h o r i e n t e d t e s td a t ag e n e r a t i o nb a s e do nm o d i f i e d g e n e t i ca l g o r i t h m 1 5 3 1i d e ao fm g ai np a m - o r i e n t e dt e s td a t ag e n e r a t i o n 。1 5 3 2i d e n t i f i c a t i o no ft h es t l l j c t u a l i n f o n n a t i o no fp r o 孕锄u n d e rt e s t 。1 5 3 3d e s j 印o ft h em g a a l g o r i t l 姗1 7 3 3 1e n c o d i n gs t r a t e g y 1 7 3 3 2d e s i g no f m ef i t i l e s s 如n c t i o n 1 7 3 3 3d e s i 印o fm eg e n e t i cs t r a t e g y “1 8 c h a p t e r4d e s i g na n di m p l e m e n t a t i o no ft h et e s td a t ag e n e r a t i o n v l l 北京化工人学硕：l ：学位论文 p r o t o 够p es y s t e m 2 1 4 1a r c l l i t e c t u r eo fm ep r o t o t y p es y s t 锄2 1 4 2c o m p i l es y s t 锄2 2 4 3 咖a 1m a c h i n es y s t e m 2 5 4 3 1i d e n t i f i c a t i o no f p r 0 伊锄p a t hi n f o 衄a t i o n 2 7 4 3 2i d e n t i f i c a t i o no fs t m c t u r a li n f 0 肌a t i o n 2 7 4 4t e s td a t ag e n e r a t i o ns y s t e m 2 7 c h a p t e r5e x p e r i m e n ta n dr e s u l ta n a l y s i s 2 9 5 1e x p e r i m e n t a lo b j e c t s 2 9 5 2d e s i 盟0 ft h ee x p e r i m e n ta i l dr e s u l ta 1 1 a l y s i s 3 0 c h a p t e r6c o n c l u s i o na n df h t u r ew o r k 3 5 6 1c o n c l u s i o n 2 9 6 2f u h l r ew o r k 3 0 r e f b r e n c e 3 7 a c k n o w l e d g e m e n t s 3 9 c o n t e n t so fa c a d e m i cp a p e rp u b l i s h e da sag r a d u a t es t u d e n t 4 1 i n t r o d u c t i o no ft h ea u t h o r 4 3 v l l l 第一章绪论 1 1 课题研究背景及意义 第一章绪论 随着软件规模的日益庞大，软件测试的重要性显得愈发鲜明。根据统计，在完整 的软件开发过程中，测试所占的工作量已经达到了软件开发全部工作量的4 0 以上。 特别对于一些安全关键类软件，测试过程的花费高达开发花费的3 5 倍【lj 。 在软件测试过程中，测试用例( 测试数据) 的生成是软件测试的核心问题，也是 软件测试的关键和难点所在。如何在广阔的输入空间中选择有限的测试用例( t e s t c a s e ) 作为输入以满足特定的覆盖准则要求，以及如何设计较好的测试用例都将直接 影响到测试的质量，进而影响到软件的质量。针对软件测试的大量研究也主要集中在 测试用例生成这个领域，争取能够以自动化或半自动化的方式来生成测试用例，进而 满足对软件进行充分测试的要求。目前，测试用例的生成主要依靠手工完成，这使得 多数的测试过程带有巨大的盲目性和不完备性，从而导致测试效率低下，测试的充分 性无法得到保证。为此，迫切需要改进软件测试数据的生成方法，开发有效的测试用 ” 例自动生成工具，以提高软件测试的效率，降低软件开发的成本，保证软件的质量。 软件测试通常可以分为功能性测试( 黑盒测试) 和结构性测试( 白盒测试) 。功 能性测试的基本观点是，任何程序都可以看作是将输入定义域取值映射到输出值域的 函数，将系统看作是黑盒。采用功能性方法标识测试用例，所使用的唯一信息就是软 件的规格说明书。功能性测试用例有两个显著优点： ( 1 ) 功能性测试与软件的具体实现方式无关，当软件的具体设计方式发生改变 时，已经开发出的测试用例可以完整保留( 无需再开发新的测试用例) 。 ( 2 ) 测试用例( 测试数据) 的开发可以同软件的开发同时进行，这将显著地缩 减软件的整个生命周期。 另一方面，功能性测试也有两个明显的缺点： ( 1 ) 完全依照软件规格说明书设计的测试用例彼此之间可能存在大量的重叠 冗余现象。这将导致执行测试用例时消耗许多不必要的资源。 ( 2 ) 功能性测试生成的测试用例可能存在遗漏现象。软件中潜藏的错误将无法 被发现。 结构性测试又称白盒测试。基于白盒测试生成的测试用例需要对系统内部的结构 和工作原理有一个完整清晰的了解。利用白盒方式生成测试用例可以： ( 1 ) 使程序模块中的独立路径至少被执行一次。 ( 2 ) 对于程序中的所有判断表达式，使其真( 假) 值各取一次。 ( 3 ) 处理循环和边界情形。 北京化_ t 人学顺1 二学位论文 对于一个被测软件来说，仅利用其规格说明书来进行黑盒测试往往是不完备的， 且容易产生大量的疏漏。因此，在能够获得被测软件源代码的前提下，利用白盒测试 技术来生成更加充分完备的测试用例则是对软件进行严格测试的必然要求。在结构性 测试的实践当中，路径覆盖通常作为测试数据的生成准则。现有面向程序路径测试数 据生成方法可以分为随机法、静态法和试探性算法【2 】。随机法通过随机方式生成测试 数据，其优点是简单易行，但当被测程序的输入空间较大时，随机法通常效率低下。 静态法只对被测程序进行静态分析，并不运行被测程序，典型的方式是符号执行法。 符号执行法1 3 j 以符号代替数值作为被测程序的输入，收集路径中的约束集，通过对约 束集进行求解【4 】来达到生成测试数据的目的。当被测程序较简单时，符号执行具有较 好的执行效果。但当存在非线性约束时，其效率会急剧下降，甚至出现求解失败的情 况。试探性算法【2 】是指从程序的输入空间中随机选择输入，运行被测程序，根据执行 结果并结合概率论的思想产生新的输入继续执行被测程序，直至生成满足要求的测试 数据。试探性算法主要包括遗传算法和模拟退火算法【5 6 ，1 7 1 。其中遗传算澍8 】是一种模 拟自然界生物进化规律( 优胜劣汰、适者生存) 的算法。最初由美国m i c h i g a i l 大学 h o l l a n d 一教授于1 9 7 5 年首先提出。在求解复杂非线性问题时，遗传算法采用概率化 的搜索方式，具有全局搜索优化能力强，能自学习、自适应的特点。故其在软件测试 数据自动生成中具有广泛的应用【1 0 。b l 。大量研究表明，遗传算法在面向路径的测试数 据自动生成中取得了较好的效果，但也存在如下问题： 遗传算法在进行交叉、变异操作时，交叉点、变异点可能选取在个体基因中的任 意位置，交叉、变异操作产生优良基凶的同时也存在破坏已有优良基因的可能。这导 致了算法生成覆盖指定路径的测试数据时，迭代次数较多，算法效率较低。 本文提出了一种改进型的遗传算法( m o d i f i e dg e n e t i ca l g o r i t h m ，m g a ) ，通过 利用被测程序的结构信息来确定个体交叉、变异操作发生的位置，约束交叉、变异操 作的范围。通过对个体中的输入变量进行有针对性地调整来提高算法收敛的速度，降 低了算法在测试数据生成时所需的迭代次数，提高了测试数据的生成效率。 1 2 国内外研究现状 面向路径的测试数据自动生成是具有巨大理论意义和实用价值的研究方向，但其 确是一个十分困难的问题。近年来，国内外存在大量的研究，提出了很多种方法。这 些方法从不同角度，不同程度地解决了这个问题。遗憾的是，目前尚未研究出能够切 实有效的解决面向路径测试数据生成问题的方法。已有方法中有些具有较高的生成效 率，但完备性不够；有些方法虽然执行效率很高，但其对被测程序的复杂度和规模有 较多限制。 给定一条程序路径，能否生成覆盖该路径的测试数据取决于是否能够找到特定的 2 第一章绪论 一个或一组输入，使得路径中的全部约束条件都能够被满足。对于路径中的线性约束 来说，通常可以利用成熟的方程理论进行解约束的操作，但对于路径中存在的非线性 约束的求解问题则从数学角度来讲亦十分困难。对于非线性约束的求解，d a v i sj 在 1 9 7 3 年已经从理论上证明了不存在数值方法来对任意约束集进行求解。另一方面， w b y u k e r 在1 9 7 9 年进一步证明了无法找到有效的算法，使得对于任意程序路径p a ， 都可以生成覆盖该路径的测试数据。w e y u k e r 的证明从理论上限制了寻找有效算法的 可能，但对于不同性质的被测程序来说，采用某些特定方法依然能够有效地生成合适 的测试数据。近年来，人们提出多种方法，虽然从理论上来说，哪种已知的算法都无 法保证绝对有效，但各种算法各有千秋，通常可以优势互补。 对于程序p 中的某一路径p a ，用某种方法生成覆盖p a 的数据。若路径p a 中的 全部约束都是线性的，且算法可以在有限时间内生成测试数据( 针对该路径确实是可 行路径的情形) 或在有限时间内判定该路径为不可行路径，则说明算法对线性约束组 成的路径是完备的。当路径p a 中存在非线性约束时，不存在任意算法可以保证在有 限时间内得到执行该路径的测试数据，故算法对非线性约束组成的路径都是不完备 的。下面依次介绍各种面向路径的测试数据方法。 随机法：随机法将从被测程序的输入空间中随机选取数据作为输入。其特点是数 据生成的代价很小，无需对被测程序进行任何分析即可以大量地生成测试数据。但其 也具有明显的缺点，随机生成的数据可能只覆盖了被测程序全部路径中的一小部分。 静态法：静态法不运行被测程序，典型的方法有数据流分析法，符号执行法等。 其中符号执行法以符号代替数据作为被测程序的输入。通过收集路径上的约束并求解 来生成满足目标路径的测试数据。 启发式算法：启发式算法主要包含遗传算法、模拟退火算法和紧急搜索算法等。 利用启发式搜索算法的共同特点是：首先随机生成一个初始解，然后通过一代代不断 对当前解进行调整来试图逼近最优解。 1 3 论文主要贡献 面向程序路径的测试数据自动生成是软件结构性测试的重要一环。本文主要讨论 对于一个给定的被测程序，如何高效地自动生成覆盖其路径的测试数据。具体工作包 括： ( 1 ) 分析研究了已有的若干测试数据生成方法，主要有随机法、静态法和启发 式搜索算法( 模拟退火算法、禁忌搜索算法、遗传算法) 在测试数据生成中的应用。 通过分析各种算法在面向路径测试数据生成中的优缺点，提出了一种基于改进遗传算 法的面向路径测试数据生成方法。 ( 2 ) 设计实现了一个利用改进型遗传算法进行面向路径测试数据自动生成的 3 北京化t 大学硕上学位论文 原型系统。该系统以c 语言被测程序源代码为输入，输出为覆盖该被测程序全部可行 路径的测试数据。 ( 3 ) 对比分析了改进型遗传算法和传统的遗传算法在生成面向路径测试数据 时的效率。 1 4 论文组织结构 第一章介绍了课题的研究背景及国内外的研究现状。 第二章首先介绍面向程序路径测试数据生成的基本概念及各种面向路径测试数 据生成方法，包括随机法、静态法和启发式搜索算法等。最后对各种测试数据生成 方法进行了分析比较并提出了一种改进的思路。 第三章讨论了改进型遗传算法的基本思想和原理，以及改进型遗传算法在面向路 径测试数据自动生成中的应用，详细说明了改进型遗传算法的各个组成部分以及相关 实现细节。并分析了算法改进所带来的优势。 第四章给出了一套利用改进型遗传算法实现面向路径测试数据自动生成的原型 系统，详细描述了原型系统的组成部分以及各模块的实现思想和策略，并通过具体的 操作步骤说明了原型系统的使用方式。 第五章对原型系统进行了实验验证及相关结果分析，给出了针对若干被测程序， 利用改进型遗传算法进行面向路径测试数据生成时，平均迭代次数、消耗时间等各项 指标，并与传统遗传算法进行了比较。 第六章对本文工作进行了总结并给出了未来研究的方向和思路。 第一二章面向程序路径的测试数据生成方法 第二章面向程序路径的测试数据生成方法 2 1 面向路径测试数据生成概述 路径覆盖是软件结构性测试中的重要覆盖准则。通常情况下，针对某一被测程序 的面向路径的测试数据生成可以形式化地描述为：对于被测程序p ，设其输入向量空 间为s ，给定一条路径p a ，寻找一个输入向量x ( x s ) ，使得程序p 在以x 为输入 时执行路径p a o 2 1 1 程序路径的定义 程序路径是根据程序控制流图的定义给出的，因此首先介绍本文中的程序控制流 图定义。控制流图( c o n t r o lf 1 0 wg r 印h ) 是一种有向图，图中的节点表示程序中的一 段连续执行且无跳转的代码，边表示程序中的分支跳转。控制流图可以形式化地表示 为一个二元组 ，其中n 表示节点集合，其中每个节点元素是由0 或n 条顺序执行 的程序语句组成；v 表示边的集合，其中每个边元素表示程序中的一个分支跳转( 对 应过程性程序设计语言中的i f 、i f e l s e 等结构) 。对于控制流图中的某两个结点a 、b ， 若存在由a 指向b 的一条有向边。则称a 为b 的前驱节点，b 为a 的后继节点。控 制流图中存在两个特殊的节点：起始：符点、终止节点。起始节点没有前驱节点，该节 点将表示程序的入口，即程序开始执行时的状态。终止节点没有后继节点，该节点表 示程序的终止状态。( 注：应排除全部程序处于某种无限循环中的特例情况) 。设某一 c 程序的源代码如下图所示： v o i dm a i n ( v o i d ) n ob r a n c hc o d e 诹s o m e c o n d i t i o n ) n ob r a n c hc o d e ) e l s e h ob r a n c hc o d e ) n ob r a n c hc o d e 图2 1 某c 程序源代码 f i g 2 一ls o u r c ec o d eo facp r o g r a m 5 北京化工大学颁j j 学位论文 针对该c 源程序的控制流图如下图所示： 图2 - 2 程序控制流图 f i g 2 2c o n t r o ln o w 訇r a p ho fap r o g r a m 该程序代码对应两条独立的路径，用控制流图上的节点编号表示即：p 1 ：1 专2 专4 p 2 ：1 专3 专4 。下面给出程序路径的定义：从控制流图中的初始节点开始，沿有向边经 过一系列节点最终到达终止节点的一条路径即为程序的一条路径。对于一条程序路 径，根据是否能生成执行该路径的测试数据可以将其分为拓扑可行路径和实际可行路 径。拓扑可行路径是指从控制流图角度看，其确实是一条从开始节点起始，经过一系 列节点最终到达终止节点的完整路径。实际可行路径是指程序在某一种( 类) 数据输 入下实际可以执行的路径。从以上定义可以看出实际可行路径一定是拓扑可行路径， 但拓扑可行路径不一定是实际可行路径。下图描述了某一程序，该程序中存在一条拓 扑可行但实际不可行的路径。 ： 6 第二章面向程序路径的测试数据生成方法 v o i dm a i n 【v o i d ) t n ob r a n c hc o d e g e ti n p u tf r o mk e y b o a r d i n ti = i n p u t ( ) ； i f ( i 1 0 ) ， n ob r a n c hc o d e i f i i 2 ) n ob r a n c hc o d e ) n ob 阳n c hc o d e ) e l s e n ob 旧n c hc o d e n ob r a n c hc o d e 譬 图2 - 3 具有不可行路径的源程序 f i g 2 - 3s o u r c ec o d eo fap r o g r a mw i t hi i l f e a s i b l ep a m 对应图2 3 中源代码的控制流图如图2 4 所示，其中节点l 表示初始节点，节点 6 表示终止节点。节点 2 5 】表示程序中的不同顺序语句序列。对于控制流图中出度大 于1 的节点来说，必然存在一个判断表达式( 分支表达式) 与其对应。即节点1 同判 断表达式( l o ) 对应，节点2 同判断表达式( i 2 ) 对应。 厂 图2 4 具有不可行路径的程序控制流图 f i g o n t r o lf l o w 目a p ho f ap r o g r 锄、而t hi n f l e a s i b l ep a t h 7 北京化+ t 人学硕i ：学位论文 针对图2 4 存在3 条拓扑可行路径。p 1 ：l 专2 3 专4 专6p 2 ：l 专2 专4 专6p 3 ： l 5 专6 其中p 2 和p 3 路径为实际可行路径，p l 为不可行路径( 程序进入状态2 后表 明变量i 一定大于1 0 ，而状态3 需要变量i 小于2 ，故程序不可能进入2 状态后再进 入3 状态) 。 2 1 2 面向路径测试数据覆盖准则 面向路径的覆盖准则是指：对于给定的一个被测程序p ，设其中的全部独立路径 ( 至少包含控制流图中一个新节点的路径) 集合为v ，生成测试数据，使得集合v 中 的全部路径都能被执行。 2 2 基于随机法的面向路径测试数据生成 随机法【1 4 ，l9 】通过随机方式生成测试数据，其优点是简单易行。对于被测程序的某 条路径，随机法将不断随机生成测试数据，试图覆盖指定路径。通常情况下，应指定 某一尝试的上限值。若在达到该上限值前，已经生成了测试数据则算法退出：否则在 达到指定尝试次数后，算法将停止尝试，此时说明针对该条路径的测试数据生成失败。 在利用随机法尝试生成覆盖指定路径的测试数据时，随机生成的数据虽不满足指 定路径的要求，但其可能满足其他的路径要求，若直接舍弃这部分数据则将产生巨大 的浪费。为此可以对随机法进行如下改进。 设p 为被测程序，r 为路径集合，对于集合r 中的一条路径p a 进行测试数据生 成时，由于随机法存在极大的不确定性，故其所需的尝试次数将会有极大的不同。为 了最大化地利用随机生成的测试数据，可以设置某一初始尝试次数值n 。即，随机生 成n 次测试数据，分别以这n 个测试数据作为输入运行被测程序，统计覆盖的全部路 径集合r n ( 其中r n r ) 。对于集合r 。中的路径来说，由于已经生成了测试数据所以 不用针对这部分路径再次进行尝试。对于不属于集合r n 中的路径，则分别再次利用 随机法进行尝试。 2 3 基于静态法的面向路径测试数据生成 静态分析是一种不运行被测程序的测试数据生成方法。代码静态分析主要包含数 据流分析、符号执行、定理证明、模型检验等。在众多方法中，符号执行1 5 ，1 7 1 是当前 程序代码静态分析中最常采用的技术手段。符号执行是指利用符号作为输入来模拟运 行被测程序的过程。符号执行中的约束求解是一种数学上的判定过程，即对一系列方 第一二章面向程序路径的测试数据生成方泫 程进行求解。随着符号执行的不断发展，人们又提出了一种利用具体数据来进行动态 执行的方式。这种方式的特点是用符号替代一部分输入，用具体数值替代另一部分输 入来执行被测程序。通过降低约束集中方程的变量个数来使得求解过程变得简单。该 种方式一定程度地简化了约束求解的复杂性，提高了符号执行法生成测试数据的效 率。 2 4 基于启发式搜索算法的面向路径测试数据生成 启发式搜索就是在问题的解空间中对每一个可能的解进行评估，得到相对 最好的解，再从这个当前最优解进行搜索直到生成问题的目标解。在启发式搜索 中，对解的评估是十分重要的。采用了不同的评估方式可以有不同的效果。启发 式算法主要包括：模拟退火算法、禁忌搜索算法和遗传算法。 2 4 1 模拟退火算法 二p 模拟退火算法2 3 ，2 4 ，2 6 1 ( s i m u l a t e d a i l i l e a l i n g ，s a ) 是一种使用十分广泛的通 用的全局搜索算法。该方法扩展了传统的局部搜索算法。区别于一般的局部搜索 算法，模拟退火算法将以某一概率来选择邻域中目标值较小的状态。s a 算法是 对物理中的热力学中物体退火过程的一个近似模拟。在某一给定的初始温度下， 通过缓慢降温，s a 将仡多项式时问内的到一个最优解。 利用模拟退火算法求解闷题足需要解决以下若j f 问题。 状态的表达：类似于传统遗传算法中的个体编码，模拟退火算法中的状态 即是问题的一个解。 领域的定义与领域移动：由于模拟退火算法是基于邻域搜索的。定义邻域 时的主要标准是使得邻域中的解能尽量覆盖整个解空| 、口j 。 达到热平衡：栩当予物理退火中的等温过程。是指在给定温度下，经过随 机搜索后达到的一种平衡过程。 降温函数：该函数用来控制算法“降温的方式”，虽然s a 算法除了要求温 度最终趋于零以外没有其他对降温函数的要求，但也不能随意设计降温函数。选 择合理的降温函数能够提高模拟退火算法的效率。 2 4 2 禁忌搜索算法 禁忌搜索算法1 8 ，2 5 1 的基本思想是由g l o v e r 提出来的，他扩展了局部领域搜索， 是一种全局最优所搜算法。禁忌搜索算法通过构造禁忌表来避免算法进行迂回式搜 9 北京化_ t 火学硕j ：学位论文 索，防止算法陷入局部最优的状态。 利用禁忌搜索算法求解问题的基本步骤如下： 1 随机给出一个初始解，令禁忌表为空。 2 判断初始解是否满足条件，如果满足则算法停止，否则继续。 3 判断候选解集中的最优解是否满足期望条件，若满足，则更新期望条件和当 前解后直接执行步骤5 。 4 从候选解中选取尚未被禁忌的最优解作为当前解。 5 更新禁忌表，执行步骤2 。 2 4 3 遗传算法 遗传算法是一种模拟自然界生物进化规律( 优胜劣汰、适者生存) 的随机搜索算 法。最初由j h o l l a n d 教授在1 9 7 5 年首次提出。在求解复杂的非线性问题时，遗传算 法利用概率化的搜索方法，全局优化搜索能力强，具各自学习、自适应的特点。因此 遗传算法常被应用于机器学习、组合优化、信号处理、自动控制等相关领域。 遗传算法【1 6 ，2 0 2 1 2 2 1 是一种具有随机性的全局搜索算法，在测试数据自动生成的过 程中，遗传算法不需要了解被测程序的具体结构信息。这个特点使得遗传算法具有广 泛的适应性。在利用遗传算法进行测试数据自动生成时，需要解决如下三个问题： 1 个体的编码。 2 适应度函数的选取。 3 遗传策略的选取。 下面分别介绍本文所用的计算方法。 a 个体的编码 在面向路径的测试生成领域