基于遗传算法的数据流测试用例自适应生成算法

计算机系统应用　ｈｔｔｐ：／１ｗｗｗ．ｃ－Ｓ—ａ．ｏｒｇ．ｃａ　２０１３年第２２卷第７期　基于遗传算法的数据流测试用例自适应生成算法①　许力，陈江勇　（福建师范大学网络安全与密码技术重点实验室，福州３５０００７）　摘　要：测试用例的设计是软件测试实施的首要环节，对后期测试工作具有重要的指导作用，也是提高质量软件的　根本保证．针对Ｍｏｈｅｂ　Ｒ．Ｇｉｒｇｉｓ算法的不足，通过引入分支函数和改进遗传算法中的自适应性，提出一种改进的数　据流测试用例的自动生成算法，实验表明，改进算法在收敛速度和覆盖率等关键性能上都有较明显提高．　关键词：遗传算法；数据流；测试用例；自动化测试　Ｄａｔａ　Ｆｌｏｗ　Ｔｅｓｔ－Ｃａｓｅｓ　Ａｄａｐｔｉｖｅ　Ｇｅｎｅｒａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ＸＵ　Ｌｉ，ＣＨＥＮ　Ｊｉａｎｇ－Ｙｏｎｇ　（Ｆ￣ｉａｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｋｅｙ　Ｌａｂ　ｏｆＮｅｔｗｏｒｋ　Ｓｅｃｕｒｉｔｙ　ａｎｄ　Ｃｒｙｐｔｏｌｏｇｙ，Ｆｕｚｈｏｕ　３５０００７，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｄｅｓｉｇｎ　ｏｆｔｅｓｔ－ｃａｓｅｓ　ｉｓ　ｏｎｅ　ｏｆｔｈｅ　ｍｏｓｔ　ｉｍｐｏｒｔａｎｔ　ｐａｒｔｓ　ｏｆ　ｓｏｆｔｗａｒｅ　ｔｅｓｔｉｎｇ，ｗｈｉｃｈ　ｐｌａｙ　ａｌｌ　ｉｍｐｏｒｔａｎｔ　ｒｏｌｅ　ｉｎ　ｇｕｉｄｉｎｇ　ｔｈｅ　ｐｏｓｔ－ｔｅｓｔｉｎｇ　ａｎｄ　ａｌｓｏ　ｉｓ　ｔｈｅ　ｆｕｎｄａｍｅｎｔａｌ　ｇｕａｒａｎｔｅｅ　ｏｆ　ｑｕａｌｉｔｙ　ｓｏｆｔｗａｒｅ．Ｆｏｒ　ｔｈｅ　ｓｈｏｒｔｃｏｍｉｎｇ　ｏｆ　ｍｅｔｈｏｄ　ｒａｉｓｅｄ　ｂｙ　Ｍｏｈｅｂ　Ｒ．Ｇｉｒｇｉｓ，ａｎ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ａｕｔｏｍａｔｉｃ　ｇｅｎｅｒａｔｉｏｎ　ｏｆ　ｄａｔａ　ｌｏｗ　ｔｅｓｔ－ｃａｓｅｓ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｆｂｙ　ｉｎｔｒｏｄｕｃｉｎｇ　ｔｈｅ　ｂｒａｎｃｈ　ｆｕｎｃｔｉｏｎｓ　ａｎｄ　ａｄａｐｔｉｖｅ　ｇｅｎｅｔｉｃ　ｓｔｒａｔｅｇｉｅｓ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ａ　ｍｏｒｅ　ｉｎｃｒｅａｓｅ　ｉｎ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｃｏｎｖｅｒｇｅｎｃｅ　ｒａｔｅ　ａｎｄ　ｃｏｖｅｒａｇｅ　ｒａｔｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ；ｄａｔａ・・ｌｏｗ；ｔｅｓｔ・ｆ・ｃａｓｅｓ；ａｕｔｏｍａｔｅｄ　ｔｅｓｔｉｎｇ　１　引言　软件测试的难题之一就是在满足一定覆盖准则的　前提下进行测试用例的自动生成．其中测试覆盖准则　作为判断测试停止的重要依据主要有：基于控制流的　测试覆盖准则和基于数据流的测试覆盖准则．目前，国　内外学者针对控制流覆盖准则相继提出了各种测试用　ａｌｇｏｒｉｔｈｍｆｏｒｄａｔａｆｌｏｗ，简记为ＩＡＴＧＡＦＤＦ）　２数据流测试基本概念　数据流测试与传统单纯基于控制流图的结构化测　试的区别在于：传统的结构化测试方法基本上是从纯　数学的角度来分析的，这种测试方法无法对程序进行　例自动生成算法【　：然而基于数据流测试覆盖准则的　测试用例自动生成算法研究的相对较少，针对数据流　测试覆盖准则中的全使用路径准则，Ｍｏｈｅｂ　Ｒ．Ｇｉｒｇｉｓ提　静态分析而且相应的测试覆盖准则也难以保证测试的　有效性和充分性．而数据流测试则是利用了变量之间　的关系，通过定义．使用路径得到一系列的测试指标用　于衡量测试的覆盖率．程序中使用变量的方式有：给　变量赋常量值、通过其他多个变量产生另一个变量的　值、使用变量来存取外部数据．定义－使用测试主要通　过将控制流图的节点和特定的变量相关联并根据相应　出了采用遗传算法来进行数据流测试用例的自动生　成【６ｌ（Ａｕｔｏｍａｔｉｃｔｅｓｔｃａｓｅｇｅｎｅｒａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｄａｔａｆｌｏｗ，　简记为ＡＴＧＡＦＤＦ），然而其遗传算法的适应度设计过　于简单并不能十分有效区别出种群中优秀的个体，使　得算法的收敛速度缓慢，同时，其采用了固定的交叉率　和变异率使得算法容易陷入局部最优解．基于此本文　在其遗传算法的基础上提出一种改进的数据流测试用　覆盖准则来产生测试用例．其中根据变量定义与使用　位置的不同，可以将定义．使用对分成三类：函数内定　义．使用对，函数间的定义．使用对，类级别定义－使用　例自动生成算法（Ｉｍｐｒｏｖｅｄ　ａｕｔｏｍａｔｉｃ　ｔｅｓｔｃａｓｅ　ｇｅｎｅｒａｔｉｏｎ　对【刀．而测试准则是一套测试标准，主要作为测试人员　①基金项且：福建省高校产学合作科技重大项Ｉ￣１（２０１１Ｈ６００８）；福建省自然科学基￣（２０１１Ｊ５｜４８）　收稿时间：２０１２．１２－１ｌ；收到修改稿时间：２０１３－０１－２９　９０软件技术・算法ＳｏｆｔｗａｒｅＴｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ　２０１３年第２２卷第７期　ｈｔｔｐ：Ｈｗｗｗ．ｃ・Ｓ—ａ．ｏｒｇ．ｃｎ　计算机系统应用　选择测试路径集合的依据．根据测试用例覆盖定义一使　布尔型变量：无需进行编码，因为其只有真和假　两种可能的取值．　字符型变量：字符型变量可以用其ＡＳＣＩＩ码换成　二进制串进行编码．　用对情况的不同可以定义出６种数据流测试准则，包　括全定义、全使用等路径测试准则［８１．　图１是三个数中求最大值的程序．通过数据流测　试建模分析方法可知这段程序有三个变量，且有１　５个　定义．使用对．显然，通过人工直接设计测试用例的方　式难以完全覆盖这１　５个定义．使用对．一种可行的方　字符串变量：字符串可以看成是多个字符的连接，　故字符串编码用其所包含字符编码的连接．也可以根　据等价类划分或边界值分析等方法先将字符串进行分　法是采用随机算法产生随机的ａ，ｂ，ｃ的值，然后判断定　义．使用对的覆盖情况．然而随机算法往往盲目性较大，　难以在短时间产生满足条件的测试用例．本文就是主　要设计一种改进的数据流测试用例生成自动生成算法　ＩＡＴＧＡＦＤＦ来快速生成所需测试用例．　ｉｎｔ　ｇｅｔＭａｘ（ｍｔ　ａ，ｉｎｔ　ｂ，ｍｔ　ｃ）｛　ｉｆａ＞ｂ＆＆ａ＞ｃ）ｒｅｔｕｒｌｆ　ａ；　ｅｌｓｅ　ｊｆ　＞ａ＆＆ｂ＞ｃ）ｒｅａｍ　ｂ；　ｅｌｓｅ　ｉｆｃ＞ａ＆＆ｃ＞ｂ）ｒｅｔｕｒｎ　ｃ；　图１　ｇｅｔＭａｘ代码　３　ＩＡＴＧＡＦＤＦ算法的设计与实现　３．１相关Ｗｅｂ页面获取３．１　ＩＡＴＧＡＦＤＦ算法的编码　策略　使用ＩＡＴＧＡＦＤＦ算法求解问题时，首先须将目标　解的实际表示与遗传算法中染色体二进制位串之间建　立一种一对一的映射关系，这个过程称为编码．　设一程序Ｐ有七个输入变量，第ｆ个输入变量表示　为　ｉ，其中１≤ｆ≤七，　ｌ≤ｆ≤　表示个变量而的取值集　合，　叫做　而　的定义域　，∈Ｄ　）而　，ｘ２，…，　）ｃ（　，　，…，　）表示一个向量，该向量表　示程序Ｐ的一个测试输入或者叫做测试用例．　１）数值型变量编码　若变量Ｘｌ的取值集合　＝【口ｆ，　】，精度要求为　则　可以离散化成包含（　一ａ，）ｘｌ０￣个元素的集合．　若ｍ　是满足条件　一　）×ｌ０　２－，一１的最小整数，则　变量而可以用长度为ｍ　的二进制编码串　＝，朋　－１…ｆ２ｆｌ（，，∈｛０，ｌ｝，ｌ≤ｊｆ　）表示．二进制编码　串Ｓ　到变量Ｘｔ的映射（即解码）可以用如公式（１）计算：　÷１　一ｌ　，：ａｉ＋　＝　＋　（　一口ｆ一口ｆ）Ｊ　（　），　２）非数值变量编码　类，然后用索引来代表字符串，只对索引进行编码．　３．２　ＩＡＴＧＡＦＤＦ算法的适应度函数　在测试路径覆盖准则下，评价一个测试用例（染色　体）的好坏必须将测试数据输入到程序中执行并记录　测试路径的覆盖率．若根据数据流测试覆盖准则计算　出的路径共有ｎ条，Ｈ＝｛ｈｌ，ｈ２，……，ｈｎ），而某个测试用　例ｔ覆盖了其中的ｍ条测试路径，则测试用例ｔ的适应　度函数可以用公式（２）计算：　娜（ｆ）　詈　（２）　ＡＴＧＡＦＤＦ算法即采用的这种适应度计算公式，　并且其采用了全使用路径覆盖准则，所以相应的适应　度函数可以具体表示为公式（３）．　铆　（ｆ）＝　ＨＯ．ｏｆ　ｄｅｔｏｔａｌｆ—ｕ　ｎｏｓｙ　ｄｅｓｅ　ｐａｔｆ—ｕｓｅ　ｐａｔｈｓ　ｃｏｖｅｒｄ　ｂｈｓ　ｙ　ｔ　（３）　公式的含义是一个测试用例（染色体）覆盖的测试　路径条数越多其适应度值也就越大．但是这种适应度　函数的计算完全忽略了分支谓词对测试路径的影响．　随着分支取真值和取假值的不同，测试用例覆盖的测　试路径是决然不同的，因此本文提出一种改进的适应　度计算方法．　适应度函数计算的改进思想在于：对于一个测试　用例ｔ来说，其覆盖了一些测试路径，而对于那些未能　覆盖的测试路径来说，主要是因为这些路径上的某个　分支条件取值为假导致在测试路径上的后续语句得不　到执行的机会，否则对于一个顺序结构的程序来说，　每条语句肯定会按顺序依次被执行．所以，如果只是　简单的将已经覆盖的测试路径数来计算适应度函数忽　略了分支条件的取值对测试路径的贡献，不仅降低了　算法的收敛速度而且容易使算法陷入局部最优解中。　图２是某个程序片段的控制流图．　从图中可以看出在条件语句ｉｆ（ａ＞ｂ）取假的情况　下，包含节点３、４、５、６的所有路径都无法被覆盖．假　如对于两个测试用例ｔｌ，ｔ２，他们覆盖相同的测试路径，　ＳｏｆｔｗａｒｅＴｅｃｈｎｉｑｕｅ・Ａｌｇｏｎｔｈｍ软件技术・算法９１　计算机系统应用　ｈｔｔｐ：／／ｗｗｗ．ｃ～Ｓ　ａ．ｏｒｇ．ｃａ　２０１３年第２２卷第７期　并且在节点２到节点３上的条件语句都为假，即ａ≤ｂ．　但是对于测试用例ｔｌ来说其ａ的值更接近ｂ的值，则　支谓词取假时，分支函数即为计算出的分支函数值．　假如测试用例（染色体）ｔ已经覆盖的路径条数为　我们认为测试用例ｔ。的适应度值更好，因为其离ａ＞ｂ　的条件期望值更近，所以其更可能在染色体的交叉变　异过程中产生满足条件语句为真的染色体，从而覆盖　包含节点３、４、５、６的测试路径．因此，在ＩＡＴＧＡＦＤＦ　ｍ，总的需要覆盖的路径条数为　，在未覆盖的　一ｍ　条路径中包含的被执行谓词数量为Ｐ，则适应度函数　如公式（４）所示．　算法中引入分支函数来改善相应的适应度计算．　ｉｆｔｎＰ　（ｆ）：０一口）旦＋口．笪　邋　（４）　图２某程序片的控制流图　在控制流图中，每个分支都可以用一个条件表达　式来表示，该条件表达式称为分支谓词，其作用是描　述了程序遍历该分支下语句的条件，　如判断语句　“ｉ　ａ＞ｂ）…”中分支谓词为“ａ＞ｂ”．分支谓词的一般形式　可表示为：Ａ　ｏｐ　Ｂ，其中０／７∈ｆ＜，Ｓ＞，　一，！＝１是关系　运算符。Ａ和Ｂ是表达式．为了便于计算适应度需要将　分支谓词统一转化与０的关系表达式，即Ｆ　ｒｅｌ　０，其中　Ｆ为分支函数，分支函数的构造方法如表１所示．　表１分支函数的构造　分支谓词　分支函数　ＩｅＩ　Ａ＞Ｂ　Ｂ　Ａ　＜　Ｂ　Ａ　一　＞　Ａ＜Ｂ　Ａ－Ｂ　＜　Ａ　Ａ－Ｂ　一　＜　Ａ＿Ｂ　ａｂｓ（Ａ－Ｂ）　Ａ！＝Ｂ　－ａｂｓ（Ａ－Ｂ）　．（　由上表可知，当分支谓词为真时，则分支函数为　负；当分支谓词为假时，则分支函数为正．而覆盖某　条路径，则需满足该路径上的所有分支谓词应为真，　此时分支函数应为负．由于分支函数直接构成了染色　体适应度值的一部分，不应该为负，故可将分支函数　修正为：当分支谓词为真时，则分支函数取零；当分　９２软件技术・算法ＳｏｆｔｗａｒｅＴｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ　其中口是分支谓词对适应度函数的影响权重因子，取　０．５，，＝（　）是第ｆ个分支的分支函数值．　３－３　ＩＡＴＧＡＦＤＦ算法的遗传策略　１１选择策略　遗传算法中常用的染色体选择方法有轮盘赌转　法、随机抽样法等，其中以轮盘赌转法最为常见．　ＩＡＴＧＡＦＤＦ算法即采用了轮盘赌转法．　２）交叉策略　交叉运算主要作用是产生更好的新个体，目前常　用的交叉运算有单点交叉、两点交叉、均匀交叉等．在　ＩＡＴＧＡＦＤＦ算法中采用的是单点交叉的方法．　３）变异策略　变异操作增强了种群的多样性，防止个体的早熟　现象．通常，变异率Ｐ朋取值较小，为０．Ｏ１至０．２之间，　在ＡＴＧＡＦＤＦ算法中取值为０．１５．二进制编码中的变　异方法有基本位变异、均匀变异、高斯变异和二元变　异等．ＩＡＴＧＡＦＤＦ算法采用的是基本位变异方法．　３．４　ＩＡＴＧＡＦＤＦ算法的自适应策略　在遗传算法中交叉率　和变异率　．设置的好坏直　接影响着算法的收敛速度【９】．交叉率　保证了物种的多　样性，若设置得太大，容易破坏适应度高的染色体，破　坏了遗传算法的模式；若设置的太小，又不容易产生新　的染色体，导致搜索速度缓慢．同样，若变异率只．设置　得太小则难以产生新的染色体，若设置得太大，导致对　染色体破坏太大，以至于遗传算法退化成盲目的随机　搜索算法．一种可行的办法是通过多次试验找到合适　的　和　值，但是这样太繁琐，针对不同问题难以找　到最优解．因此，ＩＡＴＧＡＦＤＦ算法采用了一种自适应的　遗传策略，根据染色体的适应度值动态设置　和只．的　值．当种群中的染色体趋于局部最优时，增加　。和　的值，当种群中的染色体较为离散时，减少　．和　．的　值．对于高于平均适应度的染色体设置较小的　。和　值，使得优良物种得以保留；而对于低于平均适应度的　２０１３年第２２卷第７期　ｈｔｔｐ：ｌｌ￣ｖ．ｃ－Ｓ・ａ．ｏｒｇ．ｃｎ　计算机系统应用　染色体设置较高的　和Ｐｃ值，使得对应的个体被淘汰　从图中可以看出，在两种算法都未终止时，相同的　遗传代数ＩＡＴＧＡＦＤＦ算法的测试覆盖率明显比　出去．这样既保证了物种的多样性又保证了算法的收敛　速度．经过上述改进　和　的计算公式如（５）如下：　。　：｛　一—　哪　ｌＰｃ１　厂＇　厂　：　ｌ　Ｐ　ｌ　ｆ　其中，＝ｎ．　为每一代群体的平均适应度值，厂　为要交叉　的两个个体中较大的适应度值，　为群体中最大的　适应度值，厂为要变异个体的适应度值．　３．５　ＩＡＴＧＡＦＯＦ算法的结束条件　通常物种将根据遗传算法策略不断的繁衍，直到　最优解出现．在ＩＡＴＧＡＦＤＦ算法中需要记录已经覆盖　的测试路径数，当所有的测试路径都被覆盖时则说明　已经找到了最优解，算法结束．但是某些测试路径上　的语句节点可能难以覆盖或者无法覆盖，因此一般需　要为遗传算法为预先设定的最大进化代数作为终止条　件，通常可以取１００代到４００代．　４实验对比　选取１０个小于５０行的函数为测试对象，然后按　照要求对程序进行插桩【埘，接着分别按照ＡＴＧＡＦＤＦ　和ＩＡＴＧＡＦＤＦ算法策略产生测试用例，最后以数据流　测试准则中的全使用路径测试准则作为覆盖标准，将　ＩＡＴＧＡＦＤＦ算法与ＡＴＧＡＦＤＦ算法进行对比，其中（５）　式中的几个参数分别设计如下：Ｐｃ，＝０．９，　，＝０．６，　。＝０．１，Ｐ删：＝Ｏ．００１，将１０组测试结果取平均值其结　果汇总如图３所示．　两种算法都找到摄优解时的对比情况　一￣ＩＡＴＧＡＦＤＦ　—●■　ＡＴＧＡＦＤＦ　５　ｌＯ　ｌ５　２０　２５　３Ｏ　３５　４０　４５　５０　５５　６０　遗传代数　图３收敛速度对比　ＡＴＧＡＦＤＦ算法测试覆盖率高．虽然遗传算法运行６Ｏ代　以后生成的测试用例集的覆盖率都达到了１００％但是　明显ＩＡＴＧＡＦＤＦ算法收敛速度比ＡＴＧＡＦＤＦ算法快，在　遗传算法运行到３５代左右，ＩＡＴＧＡＦＤＦ算法己覆盖所有　的定义．使用对．而ＡＴＧＡＦＤＦ需要遗传到６０代左右才完　全覆盖目标路径．　为了进一步对比未能找到最优解时算法运行情况，　另外选取ｌ０个大于１００行的函数作为测试对象并设置　算法终止进化代数为２００代．整个测试结果汇总如图４　所示．　两种算法都未找到最优解时的对比情况　９０　８０　７０　６０　一＊ＩＡＴ（　ＦＤＦ　—ｌ－一ＡＴＧＡＦＤＦ　３０　２０　ｌＯ　Ｏ　２０　４０　６０　８０　ｌｏ０　１２０　１４０　ｌ６０　ｌ８Ｏ　２ｏｏ　遗传代数　图４覆盖率对比　因为随着程序的复杂度的增加，变量的定义．使用　对将增加，设计满足要求测试准则的测试用例将更加　困难．从图中可以看出，两种算法运行终止时（遗传到　２００代）都未能找到最优解，但是算法运行终止时　ＩＡＴＧＡＦＤＦ算法具有较高的测试覆盖率，达到了近８０ｏ／ｏ＇　而ＡＴＧＡＦＤＦ算法只有近６０％的覆盖率．从实验结果可　知无论是收敛速度或覆盖率ＩＡＴＧＡＦＤＦ算法都具有较　明显的优势．　５结论　本文在遗传算法的基础之上提出了改进的用数据　流测试用例自动生成算法ＩＡＴＧＡＦＤＦ，设计　ＩＡＴＧＡＦＤＦ算法时考虑到判定语句对测试路径覆盖的　影响，引入了分支函数的概念，同时考虑到固定的交叉　率和变异率会影响算法的收敛性，于是引入了自适应　的遗传策略，这样交叉率和变异率可以随着染色体的　适应度值的不同进行动态调整．实验表明，ＩＡＴＧＡＦＤＦ　算法具有更快的收敛性和更高的覆盖率．　ＳｏｆｔｗａｒｅＴｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ软件技术・算法９３　计算机系统应用　ｈｔｔｐ：Ｈｗｗｗ．ｃ・Ｓ－ａ．ｏｒｇ．ｃｎ　２０１３年第２２卷第７期　参考文献　ｌ　Ｈａｒｍａｎ　Ｍ，Ｍｃｍｉｎｎ　Ｗｅｇｅｎｅｒ　Ｊ．Ｔｈｅ　ｉｍｐａｃｔ　ｏｆ　ｉｎｐｕｔ　ｄｏｍａｉｎ　ｒｅｄｕｃｔｉｏｎ　ｏｎ　ｓｅａｒｃｈ　ｂａｓｅｄ　ｔｅｓｔ　ｄａｔａ　ｇｅｎｅｒａｔｉｏｎ．　Ａｎｔｏｎｉａ　Ｂｅｒｔｏｌｉｎｏｅｄ．Ｐｒｏｃ．ｏｆｔｈｅ　ｔｈｅ　６ｔｈ　Ｊｏｉｎｔ　Ｍｅｅｔｉｎｇ　ｏｆｔｈｅ　Ｅｕｒｏｐｅａｎ　ＳｏＲｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｃｏｎｆｅｒｅｎｃｅ　ａｎｄ　ｔｈｅ　ＡＣＭ　ＳＩＧＳＯＦＴ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００７：１　５５—１　５６．　２　Ｚｈｅｎｇ　Ｌ，Ｈａｒｍａｎ　Ｍ，Ｈｉｅｒｏｎｓ　ＲＭ．Ｓｅａｒｃｈ　ａｌｇｏｄｔｈｍ　ｆｏｒ　的应用．北京航空航天大学学报，１９９８，２４（４）：４３４－－４３７．　６　Ｇｉｒｇｉｓ　ＭＲ．Ａｕｔｏｍａｔｉｃ　ｔｅｓｔ　ｄａｔａ　ｇｅｎｅｒａｔｉｏｎ　ｆｏｒ　ｄａｔａ　ｆｌｏｗ　ｔｅｓｔｉｎｇ　ｕｓｉｎｇ　ａ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ．Ｊｏｕｒｎａｌ　ｏｆ　Ｕｎｉｖｅｒｓａｌ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，２００５，１１（６）：８９８－９１５．　７　Ｒａｐｐｓ　Ｓ，Ｗｅｙｕｋｅｒ　ＥＪ．Ｓｅｌｅｃｔｉｎｇ　ｓｏｆｔｗａｒｅ　ｔｅｓｔ　ｄａｔａ　ｕｓｉｎｇ　ｄａｔａ　ｌｏｗ　ｉｆｎｆｏｒｍａｔｉｏｎ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，　１９８５，ｌ　１（４）：３６７－３７５．　８　Ｆｒａｎｋｌ　ＰＧ　Ｗｅｙｕｋｅｒ　ＥＪ．Ａｎ　ａｐｐｌｉｃａｂｌｅ　ｆａｍｉｌｙ　ｏｆ　ｄａｔａ　ｆｌｏｗ　ｔｅｓｔｉｎｇ　ｃｒｉｔｅｒｉａ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，１　９８８：　ｒｅｇｒｅｓｓｉｏｎ　ｔｅｓｔ　ｅａｓｅ　ｐｒｉｏｒｉｔｉｚａｔｉｏｎ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｓｏｔｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００７，３３（４）：２２５－２２８．　３ＢｅｒｎｄｔＤ，Ｆｉｓｈｅｒ　Ｊ，Ｊｏｈｎｓｏｎ，ｅｔａ１．Ｂｒｅｅｄｉｎｇｓｏｔｔｗａｒｅｔｅｓｔｃａｓｅｓ　ｗｉｔｈ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ．Ｐｒｏｃ．ｏｆｔｈｅ　３６ｔｈ　Ｈａｗａｉｉ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅｓ．ＩＥＥＥ　Ｐｒｅｓｓ，２００２：１－－４．　４　Ｂｒｙｃｅ　ＲＣ，Ｃｏｌｂｏｕｍ　ＣＪ．Ｃｏｎｓｔｒｕｃｔｉｎｇ　ｉｎｔｅｒａ￣ｉｏｎ　ｔｅｓｔ　ｓｕｉｔｅｓ　１４８３－１４９８．　９王小平，曹立明．遗传算法－理论、应用与软件实现．西安：西　安交通大学出版社，２００２：１９－６７．　１０　ＡＨｍｅｄ　ＳＧ　Ｈａｒｒｏｌｄ　ＭＪ．Ｕｓｉｎｇ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｔｏ　ａｉｄ　ｔｅｓｔ—ｄａｔａ　ｇｅｎｅｒａｔｉｏｎ　ｆｏｒ　ｄａｔａ－ｆｌｏｗ　ｃｏｖｅｒａｇｅ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　１４ｔｈ　Ａｓｉａ－Ｐａｃｉｉｃ　Ｓｏｆｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｃｏｎｆｅｒｅｎｃｅ．　Ｎａｇｏｙａ：ＩＥＥＥ　Ｐｒｅｓｓ，２００７：４　ｌ＿４８．　ｗｉｈ　ｇｒｅｅｄｙ　ａｔｌｇｏｒｉｔｈｍ．Ｔｈｅ　Ｐｒｏｃ．ｏｆ　ＡＳＥ’０５．Ｃａｌｉｆｏｒｍｉｎａ，　ＡＣＭ　Ｐｒｅｓｓ．２ｏｏ５．１２４—１３６．　５荚伟，谢军凯，奚红宇，等．遗传算法在软件测试数据生成中　（上接第８４页）　信息检测的误码率更低．　Ｔｅｃｈｎｏｌｏｇｙ，２００３，１３：８８５—８８９．　６赵朝阳，刘振华，王挺．数字音频信号的回声隐藏技术．计算　参考文献　ｌ姚钟涵，王慧琴，毛力．一种基于回声隐藏的数字音频水印算　法．微计算机信息，２００８，２４：１一１．　２　Ｘｕ　Ｃ，Ｗｕ　Ｊ，Ｓｕｎ　Ｑ，Ｘｉｎ　Ｋ．Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　ｗａｔｅｒｍａｒｋｉｎｇ　ｔｅｃｈｎｏｌｏｇｙ　ｉｎ　ａｕｄｉｏ　ｓｉｇｎａｌｓ．Ｊｏｕｒｎａｌ　Ａｕｄｉｏ　Ｅｎｇｉｎｅｅｒｉｎｇ　机应用研究，２０００，１７：４２－－４４．　７殷凯，周辉．音频数字水印中回声隐藏技术的时域提取方法．　计算机与数字工程，２００６，３４（５）．　８段柳云，宗节保，等．一种基于回声隐藏的倒谱提取优化算法．　电子设计工程，２０１０，１８（７）．　９　Ｙａｎ　Ｂ，Ｓｕｎ　ＳＨ，Ｌｕ　ＺＭ．Ｉｍｐｒｏｖｅｄ　ｅｃｈｏ　ｈｉｄｉｎｇ　ｕｓｉｎｇ　ｐｏｗｅｒ　ｅｐｓｔｒｃｕｍ　ａｎｄ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ｂａｓｅｄ　ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅ．Ｔｈｅ　２ｎｄ　Ｉｎｔ．Ｃｏｎ￣ｏｎ　Ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ　ａｎｄ　Ｓｏｃｉｅｔｙ，Ｏｃｔｏｂｅｒ，１９９９，４７（１０）：１９９５－２００７．　３　Ｏｈ　ＨＯ，Ｋ　Ｈ　Ｓｅｏｋ　ＪＷ．Ｔｒａｎｓｐａｒｅｎｔ　ａｎｄ　ｒｏｂｕｓｔ　ａｕｄｉｏ　ｗａｔｅｒｍａｒｋｉｎｇ　ｗｉｈ　ａ　ｎｅｗ　ｅｃｈｏ　ｅｍｂｅｄｄｉｔｎｇ　ｔｅｃｈｎｉｑｕｅ．　Ｍｕｌｔｉｍｅｄｉａ　ａｎｄ　Ｅｘｐｏ，２００１：３１７－３２０．　Ｃｙｂｅｒｎｅｔｉｃｓ．Ｘｉ’ａｎ，Ｃｈｉｎａ’２００３，２（５）：２１４２－２１４７．　１０　Ｂｅｎｄｅｒ　Ｗ　Ｇｒｕｈｌ　Ｄ，Ｍｏｒｉｎｏｔｏ　Ｎ，ｅｔ　ａ１．Ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　ｄａｔａ　４　Ｈｕａｎｇ　ＤＹ　Ｙｅｏ　ＴＹ．Ｒｏｂｕｓｔ　ａｎｄ　ｉｎａｕｄｉｂｌｅ　ｍｕｌｔｉ－ｅｃｈｏ　ａｕｄｉｏ　ｗａｔｅｒｍａｒｋｉＬｎｇ．ＩＥＥＥ　Ｐａｃｉｉｃ　ｆＲｉｍ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｕｌｔｉｍｅｄｉａ，　２Ｏ０２．６ｌ５—６２２．　ｈｉｄｉｎｇ．ｍＭ　Ｓｙｓｔｅｍｓ　Ｊｏｕｒｎａｌ，１９９６，３５（３／４）：３１３－３１６．　１ｌ唐升，侯榆青，克兢．一种基于短时能量自适应的回声隐藏　算法．计算机应用，２００８，２８（１１）．　５　Ｋｉｍ　ＨＪ，Ｃｈｏｉ　ＹＨ．Ａ　ｎｏｖｅｌ　ｅｃｈｏ－ｈｉｄｉｎｇ　ｓｃｈｅｍｅ　ｗｉｔｈ　ｂａｃｋ－　ｗａｒｄ　ｎｄ　ｆａｏｒｗａｒｄ　ｋｅｒｎｅｌｓ．Ｃｉｒｃｕｉｔｓ　ａｎｄ　Ｓｙｓｔｅｍｓ　ｆｏｒ　Ｖｉｄｅｏ　９４软件技术・算法ＳｏｆｔｗａｒｅＴｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ