（计算机软件与理论专业论文）测试数据自动生成技术研究.pdf

摘要 软件测试可以被视为为了发现错误而执行程序的过程，其中设计和生成有效的测试用例是决定其质量 的重要因素之一。作为人工测试的重要补充，测试数据自动生成技术可以节省测试时问降低开发成本 拓展测试人员的能力，在许多测试领域发挥着不可替代的作用。多年来，人们对它进行了广泛而深入的研 究，取得了许多研究成果，使之在功能性测试、结构性测试、性能测试等领域得到广泛应用 本文从组合测试和演化测试的角度，对功能性测试和结构性测试的测试数据自动生成技术进行了深入 研究，主要工作包括：( 1 ) 在功能性测试领域，基于组合测试模型，提出了若干种测试数据自动生成方法， 有助于获得高质量的测试数据集：( 2 ) 通过对程序分析与切片技术的研究，探索了结构性测试的基础理论； ( 3 ) 提出了若干种结构性演化测试方法及优化技术，能够自动生成满足测试目标的铡试数据。 论文工作的主要成果表现在以下几个方面： 在组合覆盖测试模型的基础上，提出了一种基于解空间树的组合测试数据生成方法，所生成的测试 数据集与同类方法相比具有一定的特点和优势。提出两种多因素组合测试数据的生成算法，可作为 已有方法的有益补充，适用于关键系统的测试。 针对面向方面程序( a s p e c t - o r i e n t e dp r o g r a m ) 的特点，提出了一种新的程序依赖性分析与切片方法， 可以准确地计算面向方面程序的控制依赖和数据依赖。结合程序分析方面的研究，提出了两种测试 数据生成方法，可以分别生成满足多重条件覆盖和改进的条件判定覆盖的测试数据集。 提出了一种针对路径覆盖的演化测试方法以及若干种适应值函数的构造方法，可以自动生成测试数 据以覆盖指定的路径。实验表明，该方法的效率显著优于随机测试和人工测试。 提出了一种自适应的演化测试动态优化方法，可以有效地解决进化停滞徭题。在演化测试的静态配 置优化方面，通过大量的实验分析，总结出一批针对结构性演化测试的规则与建议，对演化测试的 应用有较高的参考价值。 关键词软件测试，组合测试，演化测试，测试数据生成，遗传算法 a b s t r a c t s o r w a r et e s t i n gi st h ep r o c e s so fe x e c u t i n gap r o g r a mw i t ht h ei n t e n to ff i n d i n ge 肿培a st h ei m p o r t a n t c o m p l e m e n t a r i t yf o rm a n u a lt e s t i n g ，t e s td a t aa u t o m a t i cg e n e r a t i o nc a l lr e d u c et e s t i n gt i m e ，d e c r e a s ed e v e l o p m e n t c o s t , a n de ) c c e n dt h ea b i l i t i e so ft e s t e r s ，w h i c hi sa l l i m p o r t a n ti nm a n yt e s t i n ga r e a s i np e s tt w e n t yy e a r s ，m a n y a u t o m a t i ct e c h n i q u e sh a v eb e e np r o p o s e di nf u n c t i o n a lt e s t i n g , s t r u c t u r a lt e s t i n g , p e r f o r m a n c et e s t i n ga n de t c t h em a i nr e s e a r c hi nt h i sp a p e ri n c l u d e sc o m b i n a t o r i a lt e s t i n ga n de v o l u t i o n a r yt e s t i n g ：( 1 ) b yt h er e s e a r c h o f c o m b i n a t o r i a lt e s t i n g , t h ep a p e rp r o p o s e ss e v e r a lt e s td a t ag e n e r a t i o nm e t h o d sf u rf u n c t i o n a lt e s t i n g ，w h i c ha r e h e l p f u l t oo b t a i ne f f e c t i v et e s ts u i t e s ( 2 ) b yt h er e s e a r c ho f p r o g r a ma n a l y s i sa n ds l i c i n g , t h ep a p e rf i n d sw a y st o s o l v es o m ep r o b l e m si na s p e c t - o r i e n t e dp r o g r a ma n a l y s i sa n ds t r u c t u r a lt e s t i n g ( 3 ) b yt h er e s e a r c ho f e v o l u t i o n a r yt e s t i n g , t h ep a p e rs u g g e s t sm e t h o d st og e n e r a t et e s td a t ae f f i c i e n t l yf u rs t r u c t u r a lt e s t i n g t h em a i nc o n t r i b u t i o n so f t h ep a p e ra r el i s t e da sf u l l o w s t h e p a p e rr e p r e s e n t s a m e t h o d b a s e d o n t h e s o l u t i o n s p a c e t r e e t o p r o d u c e t e a t d a t a f o r c o m b i n a t o r i a l t e s t i n g , w h i c hh a ss o m em e r i t sc o m p a r e dw i t ht h er e l a t e dw o r k s t h ep a p e ra l s op r o p o s e st w od i f f e r e n tt e s t s g e n e r a t i o na l g o r i t h m sf u rt h ek - w a yc o v e r a g ec r i t e r i o n , w h i c ha f eh e l p f u li nt h et e s t i n go f c t i l i c a ls y s t e m s w ep r o p o s ea na p p r o a c hf u rt h ed e p e n d e n c ea n a l y s i sa n ds l i c i n go fa s p e c t - o r i e n t e ap r o g r a m s ，w h i c hc a n c o m p u t ec o n t r o ld e p e n d e n c e sa n dd a t ad e p e n d e n c e se f f i c i e n t l ya n dc o r r e c t l y w ep r e s e n tt w oa l g o r i t h m s b a s e do nb i n a r yd e c i s i o nd i a g r a m st op r o d u c et e s td a t af u rt h em u l t i p l e - c o n d i t i o nc r i t e r i o na n dt h e m o d i f i e dc o n d i t i o n d e c i s i o nc r i t e r i o n a n dd e s c r i b eh o wt om e a s n r gt h et e s t i n gc o v e r a g eo f t h e m t h ep a p e rs u g g e s t sa ne v o l u t i o n a r yt e s t h a gm e t h o df o rt h ep a t h - o r i e n t e ds t r u c t u r a lt e s t i n g , a n dg i v e s s e v e x a lm e t h o d sf u rt h ec o n s t r u c t i o no fr e l a t e df i t n e s sf u n c t i o n s t h ee m p i r i c a lr e s u l t si n d i c a t et h a tt h e m e t h o d sp e r f o r m a n c ee x c e e d sr a n d o mt e s t i n ga n dm a n u a lt e s t i n go b v i o u s l y t h ep a p e rp r e s e n t sas e l f - a d a p t a t i o ns t r a t e g yf u rs 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 gt of e c o v c l t h ed i v e r s i t yo f t h ep o p u l a t i o n , w h i c hm a yi m p r o v et h ep e r f o r m a n c eo f e v o l u t i o n a r yt e s t i n gg r e a t l y b e s i d e s ，b a s e do nt h e e m p i r i c a la n a l y s i s , w ep r o v i d es o m ev a l u a b l em l e sa n da d v i c e sf u rt h ec o n f i g u r a t i o ns t r a f e so f s 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 k e y w o r d s ：s o f t w a r et e s t i n g , c o m b i n a t o r i a lt e s t i n g , e v o l u t i o n a r yt e s t i n g , t e s td a t ag e n e r a t i o n , g e n e t i ca l g o r i t h m s 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名：逝日期：型：! 竺! 罗 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人 所送交学位论文的复印件和电子文档，可以采用影印、缩印或其它复 制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除 在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大 学研究生院办理。 签名：虹导师签名 期： 东南大学博士学位论文 1 1 选题依据 第一章引言 计算机应用的普及、网络技术的发展以及纳米微电子技术的突破有力推动着2 】世纪工业生产、商 业活动、科学实验和家庭生活等领域的自动化和信息化进程。以软件系统为核心的计算机应用已经渗透到 各行各业，在 ：业、农业，国防、管理以及人们的日常生活中起着越来越重要的作用。随着软件规模的不 断增长，人们对软件的质量的重视程度越来越高。作为软件质量保证的重要手段，软件测试在这方面发挥 着其他方法不可替代的作用。 一般意义上，软件测试是为了发现错误而执行程序的过程。其中，设计和生成有效的测试数据是决定 软件测试质量的重要因素之- 1 1 1 。测试数据生成可以被理解为一个抽样过程，即根据相应的测试覆盖标准， 采用一定的方法，在测试数据全集中进行抽样，选取出一批错误敏感的( e r r o r - s e n s i t i v e ) 的测试数据，它 们具有较高的发现软件错误的可能性。一个有效的测试数据设计方法可以生成高质量的测试数据并尽可 能降低测试数据的总数，从而降低软件开发成本 2 ，3 】。 作为人工测试的重要补充，测试数据自动生成技术可以节省测试时间，降低开发成本，拓展测试人员 的能力，在许多测试领域发挥着不可替代的作用。多年来，人们对它进行了广泛而深入的研究，取得了许 多研究成果，使之在功能性测试、结构性测试、性能测试等领域得到广泛的应用。然而在测试实践中，如 何自动生成高质量的测试数据仍然面临许多困难。 在功能性测试( f u n c t i o n a lt e s t i n g ) 中，因为实际的软件开发缺乏形式化规格说明，测试数据生成一般 依赖于人，1 ：选择。在结构性测试( s t r u c t u r a lt e s t i n g ) 中，由于符号执行( s y m b o le x e c m i o n ) 等自动化技术 的局限性较多，测试人员需要手i 二生成测试数据以覆盖一些特定目标。虽然，随机测试( r a n d o m t e s t i n g ) 可以实现高度自动化，但是它会生成过多的测试数据，而且这些测试数据不能确保满足测试目标，查错的 效率不高【4 】。为了进一步提高测试效率、降低开发成本，研究者们正在积极研究新的测试数据生成方法， 以自动生成高质量的测试数据。 在功能性测试领域，组合测试方法是一种科学有效的测试数据生成方法。它根据系统中各种因素的相 互关系，生成尽可能少的测试数据，以尽可能多地覆盖一些影响系统的因素。同时，这些不完全测试的结 果能够反映完全测试的内在规律，具有代表性。这种方法对于系统因素相互作用而导致的软件故障具有较 强的检测能力。 目前，两因素组合测试方法已经在软件测试领域得到了成功的应用。人们使用这种方法对软件系统进 行测试时，发现了很多传统测试方法难以发现的错误。其中，两因素组合测试的测试数据生成一直是人们 研究的重要课题，至今还没有得剑很好的解决。住一些特殊的应_ 咐领域软件测试人员为了保证软件具有 更好的可靠性，需要生成多因素甜t 合测试数据，以确保对系统的多个因素进行测试覆盖。实用的多冈素组 合测试数据生成技术已成为一个重要的研究课题。此外，如何根据测试结果。快速定能错误根源也具有重 要的研究意义。 演化测试是一种有前途的白动化测试技术。它将测试数据的生成问题转化为一个利_ j 演化计算( 遗传 算法) 进行数值优化的问题。其中，破搜索的解空间就是测试数据空间，最优解就是满足特定测试目标的 测试数据。该搜索过程可以实现完全的自动化从而有助了：提高测试效率。目前，演化测试技术已经在功 能性测试、结构性测试、性能测试、安全测试等领域得到研究与应h j 。 在结构性测试领域，演化测试技术的研究尚存在许多闷题有待解决。首先人多数研究仅针对控制流 测试中的语句覆盖和分支覆盖，对丁| 路径覆蔫的研究较少。其次，目前的研究局限在单元测试领域，对1 ： 集成测试尚未展开深入探索。此外，虽然学者们已经提出些结构性测试的演化测试方法，但是对丁- 如何 第一章i 苦 优化演化测试的配置和过程的研究较少。 本文在广泛调研的基础上，试图通过对组合测试和演化测试的研究，一定程度上解决测试数据自动生 成技术所面临的困难。在功能性测试领域，提出新的组合测试方法，以生成两因素组合测试数据和多因素 组合测试数据，并研究相应的错误定位技术。在结构性测试领域，研究新的程序分析与测试方法，探索新 的演化测试方法，以快速生成满足指定测试目标的测试数据。 1 2 国内外研究现状 在软件测试过程中，如何精选少量的测试数据，对软件系统进行有效的测试，是软件测试研究的关键 课题。组合测试方法是一种科学有效的测试数据生成方法，相应的测试数据生成算法是人们研究的重点问 题。在这一领域，研究者们进行了深入研究，并取得了一些研究成果。但是，由于组合测试数据生成问题 是一个n f 问题，大多数测试数据生成方法只能提供近似解，每种方法在特定情况下都存在不足。 演化测试技术利用遗传算法能够为不同的测试目标自动生成测试数据。作为现有测试方法的重要 补充，它已经在功能性测试、结构性测试、性能测试等领域得到应用与研究【4 - 1 0 】。本文主要讨论结构性 测试中的演化测试技术( 结构性演化测试技术) 。 1 2 1 组合测试技术 设影响待测软件的因素有n 个，这些因素可以是软件的配置参数、内部事件、外部输入等。设a 是一 个m n 矩阵，即a 叫a i ，) 。x n ，其第j 列表示被测软件的因素p j ，它的元素取自有穷符号集合t j ( j = l ，2 ，n ) ， 即a t ，。如果a 的任两列第i 列和第j 列都满足：t 。和t ；的符号的全部两两组合都在第i 列和第i 列形成 的二元有序对中等概率出现，那么称a 是正交表。如果a 的任两列第i 列和第j 列都满足：t ，和t 的符号 的全部两两组合都在第i 列和第i 列形成的二元有序对中出现( 不要求等概率出现) ，那么称a 是一个两因 素组合覆盖表，a 的每一行就是一条测试数据，m 是测试数据的个数。如果a 的任k ( 2 k n ) 列的符号 的全部组合都在这k 列形成的k 元有序对中出现，那么称a 是一个k 因素组合覆盖表( 多因素组合覆盖表) 。 1 9 8 5 年，r m a n d l 最早提出参数两两组合覆盖( 两因素组合覆盖) 的概念，并利用正交拉 一方来产生 测试数据集以测试a d a 编译器【l1 】。r b r o w n l i e 等使用止交表对p m x s t a r m a i l 系统进行了测试，利用少 量的测试数据发现了许多以前没有发现的错误【1 2 】。这两种测试方法均依赖于正交表，而正交表的构造还 存在很多未解决的难题，这使它们在软件测试中的应用具有较大的局限性。 在两因素组合测试数据生成方面，d c o h e n 等提出了种测试数据启发式生成方法，开发了相应的测 试数据自动生成系统a e t g ，并申请了专利 5 3 一1 5 1 。y l e i 等利用贪心算法，提出了一种基于参数顺序的 渐进扩充的两因素组合测试数据生成方法，也开发了相应的测试数据自动生成系统p a i r t e s t 【1 6 - l7 】。这 些方法各具特点。但是都不能保证生成最小两因素组合覆盖表，在特定情况下性能不佳。 作为启发式方法的一种重要补充，n k o b a y a s h i 等提出了一种代数方法1 1 8 】，在某些情况下其效果要 优丁启发式方法。a w i l l i a m s 也给出了一种代数方法和相应的算法实现，可以有效地生成测试数据1 9 2 1 。 然而，这两种方法对r 各个参数取值个数不同的待测系统，只能采崩统一参数取值等近似方法求解，算法 不够灵活。计算结果也不够理想。 在多闪素组合测试数据生成方面，m c o h e n 等将模拟退火算法膨心丁测试数据的生成 2 2 2 3 1 。c c o l b o u m 等研究了两种组合测试数据集生成方法，分别麻h i 丁具有不同参数取值的两因素组合测试和多冈 素组合测试1 2 4 - 2 5 1 。 p s c h r o e d e r 等提出了一种测试数据约简方法，利_ 【 j 系统输入一输出芙系等附加信息，在不降低错误检 测能力的前提f ，对组合测试数据集进行约简1 2 6 - 2 7 。但是，此类约简问题本身是一个n p 问题，而且获 取附加信息也需要一定的成本和开销，所以这种方法并不普遍有效。在某些情况f ，还不如直接使用纲合 测试方法简单、高效。 d ，k u h n 等研究了组合测试的可刚性。通过实验，他们发现人约2 0 4 0 左右的软件故障是由单个 2 东南大学博士学位论文 参数引起的，大约7 0 的故障是由一个或两个参数的相互作用引起的，而大约2 0 左右的故障由三个或 三个以上的参数相互作用而引起的【2 8 】。此外，d k u h n 等还通过实验进一步研究了在大规模分布式系统中 组合测试的可用性，发现此类系统中的软件故障摄多由四到六个参数的相互作用所引发【2 9 】。由此可知， 组合测试具有很重要的应州价值。 1 2 2 演化测试技术 结构性演化测试的核心问题是，根据给定的测试目标，构造合适的适应值函数( f i t n e s sf u n c t i o n ) 来评 价测试数据。根据适麻值函数的构造方法，现有的结构性演化测试技术可以分为三类：面向覆盖 ( c o v e r a g e - o r i e n t e d ) 方法、面向距离( d i s t a n c e - o f i e m e d ) 方法和混合方法。 在面向覆盖方法中。适应值函数根据测试数据对结构性元素的覆盖程度来计算测试数据的适应值。 m p o p e r 等提出了一种基于程序流图( c o n t r 0 1 f l o wg r a p h ) 的适应值函数构造方法，适用于语句与分支覆 盖【3 0 】。在此基础上，r w e i c h s e l b a u m 等提出了一种新的演化测试方法，可用于语句、分支与条件覆盖 3 h 。 r p a r g a s 等提出了一种基于控制依赖图( c o n t r o l - d e p e n d e n t g r a p h ) 的适应值计算方法，可用于语句与分支 覆盖【3 2 】。在一些情况下，p a r g a s 方法的性能优于基于程序流图的方法。 在面向距离方法中。适应值函数根据测试数据与测试目标的解空问距离来计算测试数据的适应值。针 对不同的测试目标，研究者们提出了一系列适应值鳕数构造方法，可用于语句与分支覆盖 3 3 3 6 。此外， g m c c m w 所提出的方法，还可用于条件覆盖【3 4 】。 一般说来，面向覆盖方法的适应值函数比较简单，较容易自动化地构造，能够适用于多种类型的程序 和测试目标。但是，这类适应值函数的导向性较弱搜索的速度较慢。面向距离方法的适应值函数的导向 性较强，搜索效率较高，但是对于一些测试对象，很难自动化地构造出合适的适应值函数。于是，j w e g e n e r 等提出了混合方法的思路，通过综合利用测试数据的覆盖信息和距离信息来计算测试数据的适应值【3 7 】。 他们提出了四种适应值函数构造策略，可分别适用于控制流和数据流覆盖的多种标准。不过，他们只给出 了策略的基本思想，并没有给出具体的适应值函数构造方法，也没有针对路径覆盖、定义引用对覆盖等测 试任务进行详细讨论。 以上研究人多针对结构性测试中的语句覆盖和分支覆盖，对于路径覆盖的研究较少。此外，目前的研 究局限在单元测试领域，对于集成测试尚未展开深入研究。 目前，对于如何优化演化测试配置、如何优化演化测试过程的研究较少。对于遗传算法的参数配置已 有一些研究结论，但是它们对于演化测试的适用性还有待考察。针对结构性演化测试，h s t h a m e r 研究了 遗传算法的参数配置【3 5 】，但是其研究范围较窄，研究结论不具备普遍性。演化测试的动态优化研究基本 上还是空白。 1 3 主要研究内容 根据国内外在组合测试、演化测试方面的研究现状，我们在组合测试数据生成、演化测试方法、演化 测试优化、演化测试平台的设计与实现等方面进行了探索。具体而青论文将在以f j l 个方面展开研究。 1 3 1 组合测试技术研究 ( 1 ) 两因素组合测试数据生成 两因素组合测试数据生成问题是一个n p 问题。由丁所有的n p 问题都还没有多项式时间算法，所以 在实际的测试中，人们一般利用一些启发式算法来近似求解。这些方法具有不同的优缺点，有些方法针对 某些具体问题可以产生虽优解( 最小测试数据表) 。目前研究的重点是在保证两因素组合覆盖的前提下， 生成尽可能小的测试数据表。 我们提出了一种基于解空间树模型的两因素组合覆盖表生成算法。在这种方法中，所有的可川测试数 据被表示为一棵解空间树，一条测试数据对应于树中一条从根节点剑叶竹点的路径。算法使川一定的搜索 策略来遍历解审问树，选择j i 一个规模较小的路枰集，以实现对测试参数的两肉素组合覆盖。研究表明， 第一牵引击 这种方法在许多情况下能够生成最小测试数据表，较同类方法有一定的优势。 ( 2 ) 多因素组合测试数据生成 我们对a e t g 方法1 1 3 】和p a i r t e s t 1 6 方法进行扩展，得到两种新的多因素组合测试数据生成方法。 基于a e t g 的扩展方法将利用贪心算法，逐个生成测试数据，以尽可能快地覆盖所有多因素组合。基了= p a i r t e s t 的扩展方法将基于参数顺序，逐列扩充多因素组合覆盖表。在理论研究的基础上，我们实现了 基于这两种方法的测试数据生成t + 具并利用实验数据比较了两种方法的优劣。 ( 3 ) 基于测试数据补充生戍的错误定位技术 我们提出了一种通_ 【 的错误定位方法。该方法基于初始测试的结果，补充一些附加测试数据进行再测 试，并对其结果作进一步的分析，从而迅速地将故障原因锁定在很小的范围内。实验表明，该方法可以为 软件调试提供有价值的线索。 1 3 2 演化测试技术研究 ( 1 1 程序分析技术 程序分析和理解是结构性测试的基础。程序切片是一种重要的程序分析方法，在程序理解、测试、调 试和维护等领域得到厂泛的应用。随着现代高级程序设计语言的发展，编译器会根据源代码生成丈量的“附 加”代码，这为程序分析与测试提出了新的挑战。我们针对面向方面程序( a s p e c t - o r i e n t e dp r o g r a m ) 的特 点，提出了一种新的程序依赖性分析与切片方法，可以准确地计算面向方面程序的控制依赖和数据依赖。 结合程序分析的研究，提出了两种测试数据生成方法，可以分别生成满足多重条件覆盖和改进的条件判定 覆盖的测试数据集。 f 2 ) 结构性演化测试技术 我们针对路径覆盖，提出了若干种适应值函数的构造方法，可以快速生成测试数据以覆盖指定路径。 在此基础上，我们通过实验检验了方法的有效性，并提出了一批有价值的建议。 ( 3 ) 演化测试的优化技术 不同的测试对象和测试目标拥有不同的测试数据空间。搜索空间的差异性要求测试人员正确地配置遗 传算法的参数。合理地调整演化测试的过程，以求尽快搜索到最优解。为此，我们从静态配置优化和动态 过程优化两个方面，展开演化测试的优化技术研究。 在静态配置优化方面，我们采用多种演化测试配置方案，对不同类型的程序进行了测试。在此基础上， 总结出一批演化测试配置规则，以指导演化测试的实践。在动态过程优化方面，我们提出了一种自适应优 化策略，用来解决进化停滞问题。实验表明，这种策略有助f 恢复种群的多样性，有利于搜索到最优解。 ( 4 1 演化测试平台 演化测试具有高度的智能性、自适应性和随机性，因此对于演化测试的研究也应该基于实验。为此我 们研发了一个演化测试框架( 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 ) ，为演化测试研究提供了一个可复用、可扩 展的实验平台。该演化测试平台可以为理论研究提供丰富可靠的实验数据，使我们能够方便地比较各种演 化测试方法，迅速地试验新技术，发现问题并提山新的研究方向。 1 4 论文主要成果 本文从组合测试和演化测试的角度，对功能性测试和结构性测试的测试数据臼动生成技术进行了深入 研究。论文的主要成果表现在以f ) l 个方面： 提出了一种启发式的组合测试数据生成方法，将所有的可川测试数据表示为一棵解空间树，利用同 溯法对解空间树进行路径搜索来生成测试数据，所，成的测试数据集与同类方法相比具有一定的特 点和优势。 改进了现有的组合测试方法提出了两种多闪素组合测试数据生成算法，可作为已有方法的有益补 充，并用于关键系统的测试。 4 东南大学博士学位论文 提出一种通用的错误定位策略。它根据初始测试的测试结果，补充生成一些测试数据来进行再测试， 然后对测试结果作进一步的分析，从而迅速地定位错误原因。该方法可以为软件调试提供有价值的 线索。 针对面向方面程序的特点，提出了一种新的程序依赖性分析与切片方法，可以准确计算面向方面程 序的控制依赖和数据依赖。 结合程序分析的研究，提出了两种测试数据生成方法，可以分别生成满足多重条件覆盖和改进的条 件，判定覆盖的测试数据集。在此基础上，提出了两种测试覆盖率计算方法，可以分别圳丁- 多重条 件覆盖率和改进的条件判定覆盖率的计算。 提出了一种针对路径覆盖的演化测试方法以及若干种适应值函数的构造方法，可以生成测试数据以 覆盖指定的路径。实验表明，该方法的效率要明显优丁随机测试和人j ：测试。 提出了一种演化测试动态优化方法，周期性地检查种群进化过程，当发现进化处于停滞状态时，动 态地调整变异概率，可以有效地解决进化停滞问题。 在大量实验的基础上，总结出一批针对结构性演化测试的规则与建议，对演化测试实践有一定的参 考价值。 研发了一个演化测试框架，为演化测试提供了一个可配置、可扩展的实验平台。 1 5 论文结构 论文共七章，可分成四大部分：第一部分为第l 章，是全文的概述和引言。第二部分包括第2 章。主 要研究了组合测试方法。第三部分包括第3 章。是对程序分析方法和测试覆盖方法的研究。第四部分包括 第4 、5 ，6 章主要研究了结构性演化测试技术。 第1 章作为论文的引言，介绍了测试数据自动生成方法的研究背景和研究意义，介绍了国内外的研究 现状和仍存在的不足，描述了论文的研究内容，最后简要地介绍了论文的创新点和论文结构。 第2 章介绍了组合覆盖测试数据生成的相关工作；提出一种两因素组合测试数据生成方法；提出了两 种多因素组合测试数据生成方法；给出了一种软件错误定位方法。 第3 章提出了一种新的程序依赖性分析与切片方法，可以准确计算面向方面程序的控制依赖和数据依 赖。结合程序分析的研究，提出了两种测试数据生成方法，可以分别生成满足多重条件覆盖和改进的条件 廖0 定覆盖的测试数据集。 第4 章提出了一种针对路径覆盖的演化测试方法，可以生成测试数据以覆盖指定的路径，并通过实验 验证了方法的有效性该方法不仅适用于单元测试，也适用于结构性集成测试。 第5 章提出了一种演化测试动态优化方法，可以有效地解决进化停滞问题。在实验分析的基础上，给 出了一批结构性演化测试的配置规则与建议，对演化测试应用有一定的参考价值。 第6 章介绍了演化测试框架e t f 的设计与实现。 第7 章是对整个论文的总结，综述了我们在测试数据白动生成领域获得的成果， = 简单阐述了我们止 在进行或将要进行的研究l ：作。 第一帝组台测试数据自动生成 第二章组合测试数据自动生成 组合测试方法是一种有效的软件测试方法，相应的测试数据生成算法是人们研究的重点问题之一。本 章第l 谛给出组合测试的基本模型：第2 讧介绍组合测试数据生成的相关工作：第3 节提出一种基丁= 解空 间树模型的测试数据生成方法，可以生成两冈素组合测试数据：第4 节提出两种多因素组合测试数据生成 方法：第5 节给出一种基于测试数据补充生成的软件错误定位方法。 2 1 组合测试模型 设影响待测软件系统s u t ( s o f t w a r e u n d e r t e s t i n g ) 的参数( 因素) 有n 个：p l ，p 2 ，r 。这些参数 可以是s u t 的配置参数、内部变量、外部输入等。不妨设参数p i ( 1 i n ) 可在有限离散点集t l 中取值， t 。中有个元素( 即= i t 1 ) ，且t l 2 t n 。并假设这些参数是相互独立的，即某个参数的具体取值不 会影响其他参数的取值或存在性。 称n 元组( v l ，v 2 ，v n ) 为待测系统s u t 的一个测试数据，其中v i t bv 2 e t 2 ，v n ( et n 。要实现对 s u t 所有参数的全部取值组合的覆盖，需要1 i t 2 t n 个测试数据，将这个测试数据集记为1 。b i 的规模一股很大，在实际测试中，需要根据测试需求对其进行约简。 定义2 1 1 设a 是一个m x n 矩阵，即a = ( a ) 。其第j 列表示s u t 的参数p j ，该列元素取自有穷符 号集合t j o = 1 ，2 ，n ) 。如果a 的任两列第i 列和第j 列都满足：t i 和t i 的符号的全部两两组合都在第i 列和第j 列形成的二元有序对中等概率出现，那么称a 是正交表。如果a 的任两列第j 列和第i 列都满足： t l 和t j 的符号的全部两两组合都在第i 列和第j 列形成的二元有序对中出现( 不要求等概率出现) ，那么称 a 是一个两两组合覆盖表( 两因素组合覆盖表) ，简称两因素覆盖表。a 的每一行就是一条测试数据，i n 是测试数据的个数。如果m 是能保证上述条什成立的最小正整数，那么a 被称为最小两两组合覆盖袁。 定义2 1 2 设a 是一个m n 矩阵，即a = ( a i ，) l t l w 其第j 列表示参数p 1 ，该列元素取自有穷符号集 合t j 【j = l ，2 ，n ) 。如果a 的任k ( 2 k n ) 列第j l 列、第i 2 列、，、第i k 列都满足：t i 的符号、t i ，的 符号、t i 的符号的全部组合都在第i - 列、第i 2 列、第ik 列形成的k 元有序对中出现，那么称a 是一个k 因素组合覆盖表( 多因素组合覆盖表) ，简称k 因素覆盖表。a 的每一行就是一条测试数据，其 中m 是测试数据的个数。如果i l l 是能保证上述条件成立的最小正整数，那么a 被称为最小k 因素组合覆 盖表。 定义2 1 3 利用正交表进行实验设计的方法为止交实验设计方法。利用两因素组合覆盖表或多因素组 合覆盖表进行实验设计的方法为组合覆盖设计方法。 由以上定义可得，正交实验设计方法是一种组合覆盖方法，反之，组合覆盖方法不一定是正交实验设 计方法。此外，两冈素覆盖表是k 冈素覆盖表在k = 2f 的特例。这样，k 因素覆盖表的生成算法不但可以 生成k 冈素覆盖表，同样也可以生成两冈素覆盖表。 组合测试方法土耍通过组合覆盖设计方法产生两闪素( 或k 冈素) 覆盖表，以覆盖系统任意两个( 或 k 个) 参数的取值组合，来检测由系统参数或参数间相且作h j 而引起的软件故障。在测试实践中，受到 测试数据集规模、测试代价等冈素的影响，测试人员一般采两冈素覆盖表进行软件测试 3 6 。4 8 。此外， 为了确保一些关键戍用的可靠性，软什删试人员也需要生成多冈素覆盖表。f 面，我们给出两个定理，j j 来分析组合测试对丁- 参数取值组合的覆盖率。 定理2 1 1 设s u t 有n 个参数，每个参数的取值个数为t l ( - 1 2 。n ) ，则s u t 对应的k 冈素覆盖 表的行数r o w 满足： r o w m a x ( t i ，t i ，x t i 。)( 1 i l i 2 i k n ) 6 东南大学博士学位论文 证明：由于k 个参数的取值组合共有t “x t b x t k 个，所以k 因素维覆盖表要满足对任意k 个参数 的所有取值组合的覆盖至少要m a x ( t i l i 2 k ) 行，即r o w 一 m a x t i l ；2x k ) 。 l 定理2 1 2 设s u t 有n 个参数，每个参数的取值个数为l ( i = 1 ，2 ，。n ) ，且t l t 2 t n ，则s u t 对应的k 因素组合覆盖表a 对任意m ( 1 【m n ) 个参数的覆盖率p 满足： p ( t lx t 2x i k ) ，( t lx t 2x x t m ) 证明：对任意m 个参数p i l ，p i ：，p i 。，不妨设它们所对应的取值个数有t i ，t i ： t i 。根据定理 2 1 1 ，a 中至少有t i ，x t i ：x t i 。个关于这m 个参数的不同组合而这m 个参数的所有组合数是 t i lx t i 2 x t i 。所以a 对这m 个参数的覆盖率p 满足： d ! j ：! j ：! k ： ! ! ：! l ! 1 21 ：! ! l i t i lx t i 2 。t i mt i n + ”t i o 脚x t i _ t k + lx t k + 2 t m t lx t 2x x t m 由以上讨论可知，组合测试旨在用最少的测试数据对各种参数的取值组合进行最大限度的覆盖。与随 机测试相比，组合测试所选择的测试用例不仅更科学，而且更精练。 2 2 相关工作 起初，研究者将正交实验设计方法应用予软件测试，取得了比较好的效果。1 9 8 5 年，r m a h d i 最早 提出两因素组合覆盖的概念，并利用正交表来产生测试数据集【1 1 】。r b r o w n l i e 等使用正交表对 p m x s t a r m a i l 系统进行了测试，利用少量的测试数据发现了许多新错误【1 2 】。但是。这两种方法均依赖 于正交表，而正交表的构造还存在很多未解决的难题，特别是对于混合型j e 交表，目前还没有比较好的构 造方法。这使正交实验设计在软件测试中的应用具有较大的局限性。在软件测试中，测试数据通常只需要 实现两冈素组合覆盖，并不要求等概率覆盖；而且正交实验设计产生的测试数据数量往往多于两因素组合 覆盖。因此，对于软件测试，两因素组合覆盖方法是一种更实用的方法。 在两因素组合测试数据生成方面，d c o h e n 等提出了一种测试数据启发式生成方法，可以生成两冈素 覆盖表，并开发了相应的测试数据自动生成系统a e t gf 1 3 1 5 1 。y l e i 等利用贪心算法，提出一种基于参 数顺序的渐进扩充的两因素组合测试数据生成方法，也开发了相应的测试数据生成工具p a i r t e s t 1 6 - 1 7 1 。 这两种方法都不能保证生成最小两因素覆盖表，在特定情况下性能不佳。 作为启发式方法的重要补充，n k o b a y a s h i 等提出了一种代数方法1 1 8 ，在某些情况下其效果优于启 发式方法。a w i l l i a m s 也给出了一种代数方法和相应的算法实现，可以有效地生成两因素覆盖表1 1 9 - 2 1 。 然而，这两种方法对于各个参数取值个数不同的待测系统，只能采用统一参数取值等方法近似求解，算法 不够灵活，计算结果也不够理想。 在多因素组合测试数据生成方面，m c o h e n 等将模拟退火算法应用于测试数据的生成 2 2 - 2 3 。c c o l b o u m 等研究了两种组合测试数据集生成方法，分别麻i j j 于具有不同参数取值的两因素组合测试和多因 素组合测试 2 4 2 5 1 。 p s c h r o e d e r 等提出了。一种测试数据约简方法，利刖系统输入一输出关系等附加信息，在不降低错误检 测能力的前提卜，对组合测试数据集进行约简1 2 6 - 2 7 。但是，此类约简问题本身是一个n p 问题，而且获 取附加信息也需要一定的成本和开销，所以这种方法并不普遍有效。在某些情况f 还不如直接使川组合 测试方法简单、高效。 d k u h n 等研究了组合测试的可用性。通过实验，他们发现大约2 0 - 4 0 左右的软什故障是由单个参 数引起的，人约7 0 的故障是由一个或两个参数的相互作刚引起的，而人约2 0 左右的故障由二个或二 个以上的参数相且作刖而引起的【2 8 】。此外，d k u h n 锋还通过实验进一步研究了在人规模分布式系统中组 合测试的可j l 性，发现此类系统中的软件故障最多由四到八个参数的相互作h j 所引发 2 9 1 。由此可知，组 合测试具有根重要的膨h j 价值。 7 第一章组台测试数据自动生成 此外，c k a n e r 等将d c o h e n 的方法应用于配置测试，在保证测试质量的同时，可以大幅度地降低测 试开销【38 】。j m c g r e g o r 等将正交表应用于面向对象程序的测试，显著降低了测试数据集的规模【3 9 】。此 外，徐宝文等将组合测试应用丁配置测试和兼容性测试，也获得较好的效果 4 0 - 4 2 。 2 3 基于解空间树的组合测试数据生成 两冈素组合测试数据生成问题是一个n p 问题。