（计算机软件与理论专业论文）面向结构测试的演化测试优化技术研究.pdf

摘要 摘要 随着计算机软件深入到生活的方方面面，人们对计算机软件质量的要求不断提高。软件测试技 术作为一种有效的软件质量保证手段，已成为软件开发过程中必不可少的环节。在软件开发过程中， 软件测试经常耗费整个开发过程中3 0 0 0 , - - 5 0 的资源。为了提高测试效率，降低测试成本，研究者们 针对自动化测试技术进行了大量研究。 演化测试是一种非常有前景的自动化测试技术。它采用遗传算法智能搜索测试数据空间，自动 生成高质量的测试用例。目前，演化测试技术已被广泛应用于多种测试领域，包括结构测试、功能 测试、安全测试、性能测试、面向对象测试、回归测试等。 本文针对结构性演化测试，深入研究了演化测试的静态和动态优化方法。论文的主要工作包括： ( 1 ) 研究了演化测试过程中出现早熟与退化现象的本质原因，并针对性的对演化测试过程进行动态优 化。( 2 ) 通过大量实验，考察了该方法的有效性，并结合已有研究成果给出相关参数的最佳配置方案。 ( 3 ) 研究了演化测试中，f l a g 变量问题导致的测试性能下降，并针对结构性演化测试中三种覆盖率标 准提出了相应的解决方案。( 4 ) 扩展了演化测试框架e t f ，实现了自适应演化测试框架s a e t f 。 论文取得的主要成果包括： ( 1 ) 提出了自适应演化测试框架s a e t f ，动态检测早熟与退化现象并自适应地调整存活策略。 出现早熟与退化现象时，应用位翻转法d a b r 调整退化的种群，并应用p c c 存活策略使调 整后的种群参加到演化过程中。实验结果表明，s a e t f 有效消除了种群的早熟与退化现象， 提高了演化测试的性能，减少了演化过程中的资源消耗。 ( 2 ) 在先前研究的基础上，通过本文的进一步实验，提供了d a b r 相关配置参数的最佳取值方 案，给出了针对结构性演化测试的参数配置规则与建议，为s a e t f 的应用提供了指导原则。 这些建议分别针对不同类型的程序和测试目标，有助于提高演化测试的效率，也为进一步的 研究奠定了基础。 ( 3 ) 提出了基于p c 的适应值函数构造方法和基于符号执行的f l a g 变量问题解决方案，该方案通 过符号执行被测试程序，利用获得的信息构造适应值函数，指导测试数据向测试目标的转化。 该方案可用于覆盖指定语句、指定语句序列和指定路径。通过实验检验了该方法的有效性， 并提出了演化测试参数配置的建议。 ( 4 ) 扩展了现有的演化测试框架e t f ，在e t f 中添加了位翻转法d a b r 和p c c 存活策略的实现 模块，形成s a e t f 。扩展后的e t f 能够在传统的演化测试框架与s a - e t f 之间灵活地切换， 提供对比分析以验证s a e t f 的有效性。s a e t f 为以后的研究者对早熟与退化现象及相关 问题的研究提供了便利，为演化测试的研究提供了支持。 关键词：演化测试，遗传算法，优化方法，结构测试，早熟与退化现象，f l a g 变量，符号执行 a b s t r a c t a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o ni n d u s t r y , c o m p u t e rs o f t w a r eh a sm e r g e di n t oe v e r ya s p e c t o fo u rl i f e p e o p l eh a v ep a i dm u c ha t t e n t i o no ns o f t w a r eq u a l i t y , a n dr e q u i r eh i g hq u a l i t ys o f t w a r e a so n e o ft h em o s ti m p o r t a n tt e c h n i q u e sf o rs o f t w a r eq u a l i t ya s s u r a n c e ，s o f t w a r et e s t i n gh a sb e e na ne s s e n t i a lp a r t i nt h es o f t w a r ed e v e l o p m e n tl i f e c y c l e s o f t w a r et e s t i n go f t e nc o s t sm o r et h a n3 0 o ft h e o v e r a l l d e v e l o p m e n tr e s o u r c e a i m i n gt op r o m o t ee f f i c i e n c yo f t h et e s tp r o c e s sa n dd e c r e a s et h ec o s t ，r e s e a r c h e r s c a r r yo u tal o to fs t u d i e so na u t o m a t i ct e s t i n gt e c h n o l o g y e v o l u t i o n a r yt e s t i n g ( e t ) i sap r o m i s i n gt e c h n i q u ef o ra u t o m a t i ct e s t i n g e tu s e sg e n e t i ca l g o r i t h m ( g a ) t of i n dd e s i r e ds o l u t i o n si nt h es e a r c hd o m a i ni n t e l l i g e n t l y e ti sw i d e l yu s e di nm a n ya r e a s ，s u c ha s s t r u c t u r a lt e s t i n g ，f u n c t i o n a lt e s t i n g ，s a f e t yt e s t i n g ，t e m p o r a lt e s t i n g ，o b j e c t o r i e n t e dt e s t i n ga n dr e g r e s s i o n t e s t i n g t h i sp a p e rs t u d i e ss t a t i ca n dd y n a m i co p t i m i z a t i o no fe ti nt h ev i e wo fs t r u c t u r a le v o l u t i o n a r yt e s t i n g ： ( 1 ) s t u d i e st h ee s s e n c eo fp r e m a t u r ep h e n o m e n o n a n dp r o p o s e sad y n a m i co p t i m i z a t i o ns t r a t e g yt os o l v e p r e m a t u r i t yp r o b l e m ( 2 ) i n v e s t i g a t e st h ep e r f o r m a n c eo ft h ed y n a m i co p t i m i z a t i o ns t r a t e g yi ng r e a td e t a i l p r o v i d e ss u g g e s t i o n so nc o n f i g u r a t i o no fe ta n do u rd y n a m i co p t i m i z a t i o ns t r a t e g yb a s e do ne a r l i e r r e s e a r c h ( 3 ) s t u d i e st h ef l a gv a r i a b l ep r o b l e mi ne tw h i c hc a u s e sl o we f f i c i e n c y p r o v i d e ss o l u t i o n s a c c o r d i n gt o t h r e ec o v e r a g ec r i t e r i o n si ns t r u c t u r a le v o l u t i o n a r yt e s t i n g ( 4 ) b ye x t e n d i n ge x i s t i n g e v o l u t i o n a r yt e s t i n gf r a m e w o r k ( e t f ) ，r e a l i z et h es e l f - a d a p t i v ee v o l u t i o n a r yt e s t i n gf r a m e w o r k ( s a - e t f ) t h em a i nc o n t r i b u t i o n so f t h i sp a p e ra r el i s t e da sf o l l o w s ： ( 1 ) p r o v i d e sas e l f - a d a p t i v ee v o l u t i o n a r yt e s t i n gf r a m e w o r k ( s a e t f ) i tm o n i t o r st h ee v o l u t i o n p r o c e s sd y n a m i c a l l ya n d d e t e c t st h e s y m p t o mo fp r e m a t u r i t yb ya n a l y z i n g t h ep o p u l a t i o n w h e n e v e rt h es y m p t o mo fp r e m a t u r i t ya p p e a r s s a e t fa d j u s t st h ei n d i v i d u a l sb yd y n a m i c a d a p t a t i o nt e c h n i q u eb a s e do nb i tr e v e r s a l ( d a b r ) a n dg i v e st h e mt h ec h a n c et ot a k ep a r ti nt h e e v o l u t i o np r o c e s sb yp c cs u r v i v es t r a t e g y e x p e r i m e n tr e s u l t ss h o wt h a ts a - e t fc a ne l i m i n a t e t h ep r e m a t u r ep h e n o m e n o na n dg r e a t l yi m p r o v et h ep e r f o r m a n c eo fe ti nm a n yc a s e sw i t hl e s s r e s o u r c ec o n s u m p t i o n ( 2 ) p r o v i d e sd a b r c o n f i g u r a t i o ns u g g e s t i o nt h r o u g has e r i e so fe x p e r i m e n t sb a s e do ne a r l i e r s t u d i e s t h e s es u g g e s t i o n st a r g e td i f f e r e n tk i n d so fp r o g r a m sa n dt e s to b j e c t s ，w h i c hp r o v i d eg u i d e l i n e st o s a - e t fa n dl a ys o l i df o u n d a t i o nf o rf u r t h e rs t u d y ( 3 ) p r o p o s e sp c b a s e df i t n e s sf u n c t i o nc o n s t r u c t i o nm e t h o da n ds y m b o l i ce x e c u t i o nb a s e ds o l u t i o nt o f l a gv a r i a b l ep r o b l e mt oc o v e rap a r t i c u l a rs t a t e m e n t ，ap a r t i c u l a rs t a t e m e n ts e q u e n c ea n da p a r t i c u l a rp a t h e x p e r i m e n t sa r ec a r d e do u tt ov a l i d a t et h es o l u t i o na n dp r o v i d es u g g e s t i o n so n p a r a m e t e rc o n f i g u r a t i o n s ( 4 ) e x t e n d st h e e x i s t i n ge v o l u t i o n a r yt e s t i n gf r a m e w o r k ( e t f ) t h ee x t e n d e de t fc a l lf l e x i b l y s w i t c hb e t w e e ne t fa n ds a e t f , w h i c hp r o v i d e sc o n v e n i e n c ef o rr e s e a r c h e r s k e y w o r d s ：e v o l u t i o n a r yt e s t i n g ，g e n e t i ca l g o r i t h m ，o p t i m i z a t i o n ，p r e m a t u r e ，s t r u c t u r a lt e s t i n g ，f l a g v a r i a b l e ，s y m b o l i ce x e c u t i o n i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：登缝 日期：堡2 ：! ：圣 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或 部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名： 銎拘 导师签名： 日期： 第一章引言 1 1 选题依据 第一章引言 随着信息化时代的到来，计算机软件已深入到生活的方方面面，从国防、工业生产、管理、通 讯交通、医疗卫生等各行各业渗透到人们的日常生活中。低质量的软件产品轻则会降低客户满意度， 重则会在某些关键应用领域中导致巨大的生命财产损失。因此，人们对软件质量越来越重视，对提 高软件质量的要求越来越迫切。软件测试作为一种有效的软件质量保证手段，已成为软件开发过程 中必不可少的环节【1 】。 软件测试是一个通过执行程序以发现错误的过程，用来确认程序的功能、性能等属性是否已达 到规格说明所要求的质量标准 1 ，2 】。通常情况下，软件测试需要耗费整个开发过程中3 0 0 旷5 0 的资 源 3 】。为了提高测试效率，降低测试成本，研究者们针对自动化测试技术进行了大量研究。其中己 被广泛应用的是随机测试技术，该技术除了可以实现高度的自动化，还具有简单、操作性强等优点 【4 】。但是由于采取了盲目搜索的方法，随机测试往往会产生庞大低效的测试用例集，从而严重降低 测试的缺陷检测能力。为了弥补随机测试中的缺陷，进一步提高自动化测试的效率，需要探索新的 自动化测试技术，其中演化测试作为一种非常有前景的新兴技术，已受到了越来越多的关注。 演化测试( e v o l u t i o n a r yt e s t i n g 。e t ) 将测试用例的生成过程转化为应用遗传算法( g e n e t i c a l g o r i t h m s ，g a s ) 求解数值优化问题的过程，可以成功地为多种测试目标生成高质量的测试用例 【5 , 6 ，7 ，8 】。遗传算法的搜索空间为被测试软件的输入域，最优解是满足测试目标的测试用例。搜索过 程可实现完全的自动化，并且其具有的导向性可以避免盲目搜索，较随机测试有更加明确的目标性 和方向性 4 】：同时搜索过程还具有一定的随机扰动，可以克服复杂搜索域所带来的种种局限性。近 年来，对演化测试技术的研究已取得了一些成果，使之在结构性测试、功能性测试、性能测试、安 全性测试以及面向对象测试等多种领域均得到了成功地应用【7 1 3 】。 因此，对于演化测试技术的研究有极其重要的意义。随着研究的不断深入，演化测试技术将变 得更加高效和实用，其应用也将会更加广泛。 然而，目前的演化测试算法仍存在一定局限性。首先，在收敛性方面，难以保证稳定地获得所 需的测试用例。其中早熟与退化现象是造成不收敛的重要原因之一。早熟与退化现象发生时，种群 被少数几种基因型所充斥，丧失了多样性，从而导致历史迭代中的局部最优解在每一轮进化中总能 以相当大的概率存活下来，它们持续占据种群直到进化被强行终止【9 ，1 6 】，这种现象导致了演化的停 滞，严重降低了演化测试的性能。尽管目前已有研究针对早熟与退化问题提出了静态与动态解决方 案【1 7 1 9 ，但对于该问题的本质还缺少相关的研究及相应的优化方法。其次，f l a g 变量问题的存在 严重降低了演化测试的性能。i l a g 变量问题可被一般化地解释为在适应值的计算过程中，因信息隐 藏或信息丢失而使得搜索域压缩折叠，适应值的区分度降低，难以引导具有较差适应值的个体向具 有最佳适应值的个体演化，导致演化测试性能急剧下降 2 0 ，2 1 1 。 本文针对演化测试过程中的早熟与退化问题和f l a g 变量问题进行研究。对于早熟与退化问题， 研究其产生的本质原因，试图从根本上解决早熟与退化问题；对于f l a g 变量问题，研究新的适应值 函数构造方法，使得适应值函数能够正确引导测试用例向测试目标的演化。通过研究演化测试动态 优化与静态优化技术，达到提高测试数据生成效率、降低退化等不健康状态出现的风险的目的。 1 2 论文内容 根据国内外学者在结构性演化测试领域的研究现状、最新发展动态以及存在的问题，本文在演 化测试静态优化方法、演化测试动态优化方法以及演化测试框架的扩展方面进行了探索。本文工作 将在以下几个方面展开： l 东南大学硕士学位论文 ( 1 ) 针对早熟与退化问题，研究演化测试优化技术 研究早熟与退化现象的本质，并针对其本质提出自适应演化测试框架，当种群退化时调整种群 中退化的个体并调整存活策略。目前针对该问题的研究包括静态配置优化方法和动态过程优化方法， 但这些方法都难以从根本上解决早熟与退化问题。实验结果表明，自适应演化测试框架能有效消除 种群的早熟与退化现象，提高演化测试的性能，并减少演化过程中的资源消耗。 ( 2 ) 针对f l a g 变量问题，研究演化测试优化技术 针对结构性演化测试中存在的f l a g 变量问题，提出基于p c 的适应值函数构造方法和基于符号 执行的覆盖指定语句、指定语句序列和指定路径的f l a g 变量问题解决方案。该方案通过对被测试程 序进行符号执行，利用与测试目标相关的p c 设计适应值函数，指导测试用例向目标测试用例的转 化。通过实验验证该方法的有效性，并提出演化参数配置的建议。 ( 3 ) 演化测试框架的扩展 演化测试具有高度的智能性、自适应性和随机性，对于演化测试的研究应基于实验。本文扩展 已有的演化测试框架( e v o l u t i o n a r yt e s t i n gf r a m e w o r k ，e t f ) 为自适应演化测试框架s a e t f ，以验证、 调整新方案，并与其他的演化测试方法进行比较，发现问题并提出新的研究方向。本文的实验均在 此框架上完成。 1 3 论文结构 论文共分六章，结构如下： 第1 章为引言，介绍了自动化测试的重要性以及演化测试领域的研究背景和研究意义，阐述了 论文的研究内容，介绍了论文的结构。 第2 章介绍了遗传算法和演化测试的相关背景知识，以及国内外研究现状和存在的问题。 第3 章提出了自适应演化测试框架s a e t f 以解决早熟与退化问题。详细介绍了何翻转法 d a b r 、p c c 存活策略以及s a e t f 的流程。接着通过实验验证了s a e t f 的有效性，并提供了d a b r 相关配置参数的最佳取值方案，为s a e t f 的应用提供了指导原则。 第4 章提出了基于符号执行的 1 a g 变量问题解决方案。详细介绍了基于p c 的适应值函数构造 方法，并针对覆盖指定语句，指定语句序列以及指定路径三种覆盖率标准，给出了基于符号执行的 f l a g 变量问题解决方案。通过实验验证了该解决方案的有效性。 第5 章介绍了演化测试框架e t f 的可扩展性，给出了扩展e t f 为s a e t f 的方法，详细描述了 s a e t f 的控制流程以及位翻转法d a b r 和p c c 存活策略的控制流程。 第6 章为全文的总结，阐述了本文在演化测试领域获得的成果，并提出了进一步的研究内容。 2 第二章演化测试技术及其研究现状 第二章演化测试技术及其研究现状 演化测试应用遗传算法将测试用例的生成过程转化为求解数值优化问题的过程，可以成功地为 多种测试目标生成高质量的测试用例。目前演化测试已被广泛应用于多种测试领域，它高效与全自 动的特点，可以显著降低测试成本，提高测试质量。本章首先阐述了遗传算法的基本概念与形式化 描述，然后介绍了遗传算法在软件测试领域的典型应用谈化测试的流程及演化测试的特点。最 后，总结了演化测试在结构测试领域和演化测试优化方法的研究现状，并指出其中存在的问题。 2 1 遗传算法 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 是基于达尔文的遗传选择和自然淘汰的生物进化过程的计算模 型，通过模拟自然进化过程来搜索最优解。遗传算法由美国m i c h i g a n 大学h o l l a n d 教授在19 7 5 年首 先提出。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码进行简单的遗传操作和 优胜劣汰的自然选择来指导学习和确定搜索方向【2 2 。 遗传算法的形式化描述如下： g a = ( 尸( 0 ) ，s ，佛，仉，仍，p ，zt ) 其中： 尸( 0 ) = ( 口，( 0 ) ，口2 ( 0 ) ，毋“o ) ) ，表示初始种群。 ，是将解空间利用某种编码表示后的全体。选择何种编码表示将对算法的性能、效率等产生很大 的影响。通常，编码表示方案的选取很大程度上依赖于问题的性质及遗传算子的设计。常用的编码 方式包括：位串式编码、十进制编码、动态编码、以及实数编码等【1 6 ，2 2 。其中，位串编码把个体 表示为一个二进制位串( 向量) ，其结构类似于生物的染色体，不但有利于用生物遗传理论来解释算 法，也使得杂交、变异等遗传操作很容易实现。本文的遗传算法主要使用了位串式编码方式中的二 进制编码和g r a y 编码。 r 表示种群的规模。 ，表示将个体编码后的长度。 s ：一，表示选择操作。选择操作依据一定的策略在父代种群中选择两个个体作为父本进行遗 传操作。它决定了种群中哪些染色体的基因将被遗传下去。不同的选择策略将导致不同的选择压力。 通常，演化中优胜劣汰的本质决定了选择算子需要为适应值较高的个体提供更大的被选择概率，如 转盘式选择策略和锦标赛选择策略等【1 6 ，2 2 】。但是，在某些情况下，这些选择策略的效果不一定优 于随机选择，因此，需要根据优化问题的具体特点设置选择算子。 d c ：j ，一，表示杂交操作。杂交操作以一定的概率把两条染色体进行混合，得到两条新的染 色体。杂交操作在种群中提供了交换遗传信息的机制，令遗传算法具备大范围随机搜索的能力，有 助于发现近似解。杂交策略通常因编码方式的不同而相异。对于最常见的位串式编码，通常使用的 杂交策略包括单点杂交、模板式杂交等 1 6 ，2 2 】。而对于十进制编码则通常使用离散式杂交、算术杂 交等策略 16 ，2 2 1 。 d m ：，一，表示变异操作。变异操作以一定的概率，使种群中单个染色体的某些基因发生突变。 它是一种十分重要的机制，可令遗传算法在小范围内搜索最优解，并且有助于为种群引入新的遗传 信息，以保持种群的多样性。与杂交算子类似，变异策略的选择也是和编码方式相关的。在位串式 编码中，通常采用按位取反变异 1 6 ，2 2 】，比如从0 变成1 ，或从1 变成0 。在十进制编码中，常用的 变异方式则包括正态性变异、自适应性变异等【16 , 2 2 】。 q ：，斗，表示存活操作。当父代种群经过选择、杂交、变异遗传操作后，会产生一个子代种 群。这两个种群必须经过存活操作的筛选，以生成规模和父代种群相同的下一代种群。由于遗传算 法具有适者生存的特性，它通常倾向于保留适应值较高的个体。常用的存活策略包括转盘式存活策 3 东南大学硕士学位论文 鬟黧22s t h a m e r 薰基4 在软什鲥试领域的一个典型应用，它将测试用例的生二- _ 一- 成任务转化为求解数值优化的问题，弗制j 1 i 遗传算法厂i 1 募 目r 女# g 0 - 一 进行求解。在演化4 试中，需要根据指定测试目标设- r1 驾适应值酌数，评估不同测试用例的质量，台理地指 i ”。i_ ”6 导搜索的进行。j l4 “、i 蛋l r 图 为演化测试先驱等所给出的演化l 誓_ r j “ 7 ， 测试流张示意图【9 】。首先，算法随机生成指定个数1 叠- - 二 f n 测试川例，通过定规则将其编码为染色体，形成1 一：；，：是； 第二章演化测试技术及其研究现状 试用例为止。其中，在每一次外循环中，算法以一定概率按照选择、杂交、变异的顺序，控制父代种 群的繁衍过程，生成子代种群，然后以一定规则，分别从父代和子代种群中选取一部分具有较高适应 值的测试用例，组成了新一代种群。外层循环只作用于遗传算法的基因型空间，与传统算法流程的 区别不大。而内层循环则是评估过程的细化，用于控制外层演化迭代的重复与终止，从而持续地更 新种群，直到获得所需测试用例或者满足预设终止条件为止。它作用于软件测试的问题域，其中的 监控、评估以及终止条件的判断等操作都与具体的测试需求密切相关。特别是对个体适应值的评估， 它决定了演化搜索的方向，因此必须能够准确合理地反映出测试目标。所以，演化测试技术的关键 问题之一，在于如何设计一个恰当的适应值函数来量化地表示测试目标，从而指导遗传算法高效地 获得所需测试用例。 演化测试与其它测试数据生成方法相比，具有很多优点。首先，演化测试具有高度的自动化水 平，其运行过程无需过多人为干预，使用成本较低。通常，只需要提供被测试程序的规格说明，就 可以自动化构造出适应值函数，并应用遗传算法产生合适的测试数据。因此，演化测试可以大幅度 地提高测试效率，降低测试成本，并获得人工测试难以生成的测试用例。其次，演化测试是一种动 态测试技术，能够克服静态分析技术成本偏高、技术复杂、难以应用于生产实践等缺点，通过真实 地运行被测试软件，演化测试技术可以轻松地避免静态分析技术所具有的局限性。最后，演化测试 通过在被测试软件输入域内随机撒点，实现了在多个子输入域内同时搜索，使之在并行计算领域的 应用成为可能，大大提高了演化测试效率，并且能够以较大概率跳出局部最优。 2 3 研究现状及存在的问题 目前，演化测试技术已被广泛应用于多种测试领域，包括结构测试、功能测试、安全测试、性 能测试、面向对象测试、回归测试等【7 1 3 ，在结构测试领域的研究最为广泛。下面分别从结构性演 化测试和演化测试优化技术两个方面介绍演化测试的研究现状。 2 3 1 结构性演化测试 结构性演化测试是目前研究最为广泛的演化测试技术。其测试目标通常是实现对某一程序结构 的覆盖，如语句分支覆盖、路径覆盖、定义引用对覆盖等【6 】。根据适应值函数构造方法的不同， 相关研究分为以下三类： ( 1 ) 面向覆盖的适应值函数构造方法 在面向覆盖的方法中，演化测试根据测试用例的动态执行信息，度量其对程序数据流图或控制 依赖图中的语句结点或分支的覆盖程度，来评估测试用例的适应值【6 】。通常情况下，能覆盖更多语 句结点或分支的测试用例获得更高的适应值。 该类方法以w a t k i n s ，r o p e r 和p a r g a s 等人的研究为代表【1 3 ，3 1 ，3 2 】。w a t k i n s 和r o p e r 根据控制 流图，利用程序的动态执行信息进行适应值函数构造。w a t k i n s 的研究 3 】针对路径覆盖进行，适应 值函数记录种群中每个测试用例的执行轨迹，统计每条路径的被覆盖次数，以该次数的倒数作为适 应值赋给执行了该路径的测试用例。测试用例执行的路径被覆盖的次数越多，该测试用例的适应值 越低，它为测试目标的搜索提供了一种持续可调整的导向。但是，该方法只是在测试用例执行了已 被密集覆盖的路径时对其进行惩罚，并未对其执行目标路径提供导向。r o p e r 的研究针对语句分支 覆盖进行 3 2 1 。在r o p e r 的方法中，适应值函数依据所要求的覆盖率标准，度量测试用例已覆盖到的 程序结构个数，并以此作为该测试用例的适戍值。这种机制使得覆盖到较长路径的测试用例获得较 高适应值，但由于导向性弱，效果欠佳。p a r g a s 的研究针对语句分支覆盖进行【1 3 】，使用控制依赖 图，为每个待覆盖的语句和分支寻找出一条控制依赖结点序列。该序列上的结点是分支判定结点， 为了覆盖指定结构，必须覆盖这些结点。测试用例的适应值定义为已执行了该序列上结点的个数。 ( 2 ) 面向距离的适应值函数设计方法 在面向距离的方法中，演化测试采用“分而治之”的思想，将待覆盖的结点或分支分为不同的子 5 东南大学硕士学位论文 目标，依次为每个子目标构造适应值函数以指导测试用例的生成，并最终获得对所有子目标的全覆 盖f 6 】。对于每一个子目标，通常根据分支跳转的条件表达式构造适应值函数，以便生成一条测试数 据使条件表达式取某个特定的值( 真或假) 。 该类方法以x a n t h a k i s ，j o n e s 和m c g r a w 等人的研究为代表【1 2 , 2 4 ，3 0 ，3 3 】。他们的研究重点针对 语句分支覆盖，m c g r a w 等人的研究还包括条件覆盖。x a n t h a k i s 的方法【3 0 】人工选取包含程序中所 有分支条件的路径并对其构造适应值函数，从而生成测试用例覆盖当前路径，最终实现分支覆盖。 然而，该方法需要额外的人力开销并且选取的路径上可能存在相互矛盾的分支条件，往往导致搜索 效率较低。j o n e s 等人的方法不需要人工选取路径 1 2 ，3 3 】，以测试用例与当前子目标分支的距离作为 个体适应值。该方法虽然减少了x a n t h a k i s 方法中额外的人力开销，但是由于每条测试用例在执行目 标分支的同时，不可避免会覆盖到其他分支，因此每个分支均会被覆盖到多次，造成了不必要的浪 费。m c g r a w 2 4 针对这一问题，添加了分支覆盖记录模块，在对每一个分支进行覆盖时，首先检查 它是否已被覆盖，如果没有被覆盖，才进行演化测试。这样可以大大节约测试开销，提高测试效率。 ( 3 ) 组合式的适应值函数设计方法 一般来说，使用面向距离方法构造的适应值函数导向性较强，搜索效率较高，但是对于一些比 较复杂的测试目标，难以自动化地构造出合适的适应值函数；面向覆盖方法构造的适应值函数，虽 然构造比较简单，容易实现自动化，能够广泛地适用于多种类型的程序和测试覆盖率标准，但是导 向性弱，搜索速度较慢。因此，w e g e n e r 等人【6 】结合了以上两种方法的思想，在适应值函数的定义 中同时考察了覆盖率信息与距离信息。他们分别针对控制流与数据流中的四种覆盖率标准( 结点覆 盖、路径覆盖、结点路径覆盖、结点结点覆盖) 提出了相应的适应值函数构造方法。该方法弥补了 上述两种方法的不足，但是w e g e n e r 在文中仅给出了分支覆盖情况下的逼近度与分支距离的计算公 式，而对于复杂程序和其它覆盖率标准，没有给出具体的构造公式以及实验数据支持，难以判断其 实际应用的效果。 2 3 2 演化测试优化技术 演化测试技术可应用于多种测试领域，相对于同等自动化水平的随机方法，能够显著提高测试 用例的生成效率。然而，演化测试过程中仍存在诸多障碍，导致测试性能大幅降低。研究者们正积 极地研究优化方法f 1 3 ，2 0 ，2 5 2 8 1 ，以提高演化测试的性能。 首先，研究者们针对种群的早熟与退化问题，提出了两种演化测试优化方法：第一种利用静态 优化技术获得具有合理选择压力的演化测试配置，以降低由于收敛速度不合理所造成的早熟和退化 问题。对于该方法，s t h a m e r 曾在其博士论文中给出过针对语句分支覆盖的演化测试参数配置建议 9 】。由于该结论是针对单一测试对象的，适用范围较窄。因此，史亮等人针对一系列典型程序进行 了进一步的考察。通过比较总结实验结果，给出了一些关于演化测试静态参数优化的基本结论【2 9 】， 包括基准实验参数的确定，遗传策略的选取等。实验表明，该结论可以比较广泛地应用于多种程序 结构以及多种覆盖率标准下的结构性演化测试。第二种使用动态优化技术，对种群进行监控，并随 时调整策略以治疗己具有早熟与退化趋势的种群。目前的研究主要包括谢晓园等人提出的动态自适 应参数调节技术( d o m p ) 1 7 ，1 8 1 。d o m p 周期性地监视种群进化进程，分析种群中的染色体。当发现 种群的早熟迹象时，显著提高当前变异概率p 。，为种群引入更多新鲜基因，打破进化的停滞状态， 恢复种群多样性，以保证进化处于健康状态。当染色体的多样性被恢复时，恢复厶的值，以避免遗 传算法退化为随机算法。上述两种方法都从种群退化时的表面特征着手，调整演化测试配置以达到 消除退化症状的目的，对于退化的本质还缺少相关的研究及相应的优化方法。 其次，研究者们针对f l a g 变量问题，应用静态分析技术，改变搜索域的组成结构，提高程序的 可测试性，从而提高演化测试的效率。最为著名的是h a r m a n 等人所提出的可测试性转化方法 ( t e s t a b i l i t yt r a n s f o r m a t i o n ) 2 0 】。该方法针对结构性测试中的分支覆盖标准而设计。它使用不定型切 片技术( a m o r p h o u ss l i c i n g ) 消除目标分支条件中的f l a g 变量。此外，m c m i n n 等人也提出了一种基于 扩展链式方法( e x t e n d e dc h a i n i n g a p p r o a c h ) 的f l a g 变量问题解决方案 2 1 ，2 8 】。通过数据依赖分析，获 6 第二章演化测试技术及其研究现状 得被f l a g 变量隐藏的状态信息，使它们可以被商接应用于适应值函数的计算，以此来引导搜索过程， 从而改善了粗糙的适应值分布情况【2 1 ，2 8 。目前还没有应用符号执行的方法解决f l a g 变量问题的相 关研究。 2 4 本章小结 本章首先阐述了遗传算法的概念和基本流程，形式化地描述了遗传算法并详细介绍了其中涉及 到的6 种操作：编码、选择、杂交、变异、存活和评估个体适应值。接着介绍了如何应用遗传算法， 为演化测试自动化地生成测试用例，给出了演化测试的流程图并介绍了演化测试的优点。最后，总 结了演化测试在应用最为广泛的结构测试领域和演化测试优化技术方面的研究现状，并指出了其中 存在的问题。 7 东南大学硕士学位论文 第三章s a e t f ：一种自适应演化测试框架 演化测试是一种有效的测试用例自动生成技术，但演化过程中出现的早熟与退化现象严重降低 了演化测试的性能。本章通过研究发现，适应值距离和实际演化难度不致( d h 不一致) 是产生早熟 与退化现象的重要原因之一。为解决由于d h 不一致导致的早熟与退化问题，本章提出了一种自适 应演化测试框架s a e t f ，动态检测早熟与退化现象并自适应地调整存活策略。出现早熟与退化现象 时，应用位翻转法d a b r 调整退化的种群，并应用p c c 存活策略使调整后的种群参加到演化过程中。 早熟与退化现象消失后切换回传统存活策略。实验结果表明，s a e t f 有效消除了种群的早熟与退化 现象，提高了演化测试的性能，并减少了进化过程中的资源消耗。 3 1 演化测试中的早熟与退化现象 在演化测试的遗传操作中，杂交与变异的作用是“勘探”搜索空间以寻找那些可能最优区域， 它以保持群体内的多样性为主要目的；选择的作用则是“开采”搜索空间以充分利用群体内当前所 具有的有效信息，它使算法将搜索的侧重点放在那些具有较高适应值的个体上。在求解复杂的优化 问题时，如何在“勘探”和“开采”之间进行有效的权衡是使演化测试获得较高性能的关键问题。 如果改变选择策略使其增加较优个体的生存概率则会影响这种平衡而倾向于“开采”；反之，若增加 较差个体的生存概率则会使搜索倾向于“勘探”。这时，常用术语选择压力进行刻画，倾向于“开采” 的选择策略常称为具有较高的选择压力；反之，则称为具有较低的选择压力【2 2 】。 演化测试的性能通常与遗传算子的选取，参数的配置，以及适应值函数的设计等因素有关，这 些因素统称为演化配置。合理的演化配置可以提供适度的选择压力，从而保证算法在较短的时间内 找到所需的测试用例。当选择压力过低时，算法的导向性过弱，导致收敛速度过慢，极端情况下退 化为随机测试：而当选择压力过高时，则可能导致收敛速度过快，从而引起种群的早熟与退化。 早熟与退化现象是指由于过快收敛，导致种群被少数几种基冈型所充斥，丧失了多样性，进化 处于停滞状态的现象【9 】。这些基冈型通常是历史迭代中的局部最优解，它们在适应值上具有明显的 优势，因此在每一轮进化中总能以相当大的概率存活下来，它们持续占据着种群直到进化被强行终 止。这种现象严重降低了演化测试的性能。 以t r i a n g l e 函数为例，该程序以三角形三边a ，b ，c 为输入变量，测试目标为覆盖a - - - b = c 的结 点。在演化测试中，种群中个体表示形式为( 口，6 ，c ) 。算法采用二进制编码、按位取反变异以及倒数 函数作为基本配置【9 】。其中，倒数适应值函数公式为f i t n e s s ( a ，b ，c ) = l ( o 0 0 0 1 + d 。在本例中， 护( 1 2 口一b c l + 1 2 b 口c 1 + 1 2 c 口b 1 ) 3 。可知，当6 取最小值6 。口尸o 时，f i t n e s s ( a ，b ，c ) = 1 ( 0 0 0 0 1 + 0 ) = 1 0 0 0 ，取 得最大值。因此当( 口，6 c ) 满足关系a = b = c 时，为全局最优解，此时万= 6 。矿= o ，f i t n e s s ( a ，b ，c ) 为最大值 1 0 0 0 。图3 1 显示了t r i a n g l e 发生早熟与退化时种群的特征。从图3 1 ( a ) 中可以看到，此时个体( 6 3 ，6 4 ，6 4 ) 已完全占据种群，其适应值f i m e s s ( 6 3 ，6 4 ，6 4 ) = 1 ( 0 0 0 0 1 + 4 3 ) 3 4 。考虑在演化过程中，出现了图3 1 ( b ) 中的个体( 6 4 ，6 7 ，6 5 ) ，其适应值f i m e s s ( 6 4 ，6 7 ，6 5 ) = 1 ( 0 0 0 0 1 + 1 0 3 ) 3 1 0 。 由于 f i t n e s s ( 6 4 ，6 7 ，6 5 ) f i m e s s ( 6 3 ，6 4 ，6 4 ) ，演化测试倾向于选择个体( 6 3 ，6 4 ，6 4 ) 进行演化，导致个体( 6 3 ，6 4 ，6 4 ) 持续占据种群直到进化被强行终止，如图3 1 ( c ) 所示。这种现象严重阻碍了演化进程，导致演化测试 性能大幅下降。这就是演化测试中的早熟与退化现象。 ( a ) ( c ) 图3 1t r i a n g l e 发生早熟与退化时种群特征 8 第三章s a e t f 一种白适应演化测试框架 现有研究对早熟与退化现象的解决方案分为以下两种： 第一种是静态配置优化方案，在所有可行的配置策略中选取对当前测试目标最为恰当的配置策 略，得到适中的选择压力 9 】。该解决方案能一定程度上避免早熟与退化现象的出现。由于配置策略 在