软件测试用例自动生成算法综述


  收稿日期: 2011唱09唱15; 修回日期: 2011唱10唱26  基金项目: 国家自然科学基金资助项目(60973118) 作者简介: 聂鹏(1977唱),男,陕西汉中人,博士研究生,主要研究方向为软件确保、软件测试、软件可靠性( zeanet @163. com );耿技(1963唱), 男,安徽合肥人,教授,博士研究生,主要研究方向为系统软件、软件确保、软件可靠性;秦志光(1956唱),男,四川隆昌人,教授,博导,主要研究方向 为计算机开放系统与网络安全性、信息系统安全. 软件 测试 用 例自 动生 成算 法综 述 倡 聂 鹏1,2 , 耿 技1 , 秦志光1 (1.电子科技大学 计算机科学与工程学院, 成都 611731; 2.江西财经大学, 南昌 330013) 摘 要: 按照测试用例自动生成技术的不同,将测试用例自动生成算法分为随机、遗传、蚁群、粒子群四类,对上述 各类算法的现状和进展进行介绍、分析和探讨。 最后,对软件测试用例自动生成的研究进行了总结。 关键词: 软件测试; 测试用例生成; 随机测试; 启发性测试 中图分类号: TP 311   文献标志码: A    文章编号: 1001唱3695(2012)02唱0401唱05 doi :10.3969 / j . issn .1001唱3695.2012.02.001 Survey on automatic test case generation algorithms for software testing NIEPeng 1,2 , GENGJi 1 , QINZhi 唱 guang 1 (1.School of Computer Science &Engineering,University of Electronic Science &Technology of China,Chengdu 611731,China; 2.Jiangxi University of Finance &Economics,Nanchang 330013,China) Abstract: Based on the different techniques for the automatic test case generations , there were four categories , including ran 唱 dom test algorithms , genetic algorithms , ant colony optimization algorithms , and particle swarm optimization algorithms . This paper introduced , analyzed , and discussed the status and overview of the four categories . Finally , it drew the conclusions for the automatic test case generation algorithms . Key words: software testing ; test case generation ; random test ; heuristic test 0  引言 IEEE 计算机协会在 IEEEStd 829—1983[1] 中对软件测试 给出了定义:通过人工测试或自动测试的手段对软件的质量进 行度量,用于检验被测软件实际运行结果是否与设计软件时的 初衷相一致。 IEEEStd 829—1998[2] 进一步明确软件测试是用 于检测当前软件与实际设计需求间的差异的过程,具体包括了 测试用例( test case , TC ) 集、测试过程集以及两者的组合。 IEEEStd 829—2008[3] 将软件测试延伸到整个软件开发生命周 期中,指出软件测试是给定条件下对系统或组件的执行,以及 对结果进行观察或记录的行为。 软件测试中的 TC 是用于特 定目的的数据集合,如输入数据、执行条件、程序路径、测试需 求等。 总体而言,软件测试技术是依据软件规约或者程序结构 设计一组 TC ,将 TC 作为输入来执行待测程序,判断被测程序 的动态行为和运行结果,以发现程序错误或功能缺陷。 从测试过程是否需要执行待测程序的角度,软件测试方法 可分为静态和动态两类[4]。 静态测试方法是指无须动态执行 待测程序代码,仅对软件进行静态检查和审阅来评测测试对象 是否符合编程标准,可用于发现待测软件的不足之处。 静态测 试方法包括规范测试、软件模型测试、符号执行、空间约简、文 档测试等。 静态测试的主要不足在于: a ) 难以发现由软件运 行环境导致的错误和故障; b ) 可能因测试目标的复杂性而导 致符号执行状态空间爆炸,致使静态分析无法继续。 动态测试 方法是通过运行待测程序来检查软件的动态行为,验证运行结 果的正确性,可以发现测试对象在运行环境中形成的错误和故 障。 动态测试包括两个基本要素: a )待测程序; b )运行待测程 序的数据,即 TC 。 TC 自动生成算法是一种依照 TC 规格需求和测试目标要 求自动生成 TC 的方法。 长期以来, TC 生成主要依靠手工完 成,这意味着软件测试人员需要具备丰富的经验和较高的专业 水平。 这导致实际工程中 TC 生成往往带有很大的盲目性, TC 数量多、测试效果差、测试成本高。 据统计,在软件测试的全部 开销中,约 40%花费消耗在设计 TC 阶段。 因此,如何科学有 效地通过 TC 自动生成算法,依据软件规格或程序结构自动构 造 TC 成为软件测试的研究重点之一。 多年来,许多研究者对 TC 自动生成进行了广泛而深入的研究,并取得了大量的研究 成果,本文主要针对软件 TC 自动生成算法进行了研究。 TC 自 动生成算法,尤其是启发性 TC 生成算法具备算法实现简单、 鲁棒性好的特点。 启发性 TC 生成算法是指通过对 TC 进行评 价进而自动更新 TC ,寻找可以覆盖测试目标的最优 TC 集的算 法。 该类算法通过待测程序的信息反馈,智能、动态地产生 TC ,具有良好的方向性和目的性,是 TC 自动生成算法研究的 主要内容。 1   TC 自动生成算法框架 动态测试的核心是 TC 自动生成算法,用于快速生成 TC并覆盖测试目标。 TC 自动生成算法框架如图 1 所示。 a ) TC 自动生成算法对需要测试的程序进行结构性分析, 目的在于生成测试目标 O 和 TC 规格需求。 测试目标 O 是 TC 生成算法需要覆盖的对象,根据具体测试需求的差异而变化, 第 29 卷第 2 期 2012 年 2 月  计 算 机 应 用 研 究 Application Research of Computers Vol 畅29 No 畅2 Feb 畅2012 主要包括语句、分支(判定)、条件、路径等。 TC 规格需求是对 TC 合法性的约束条件,主要包括 TC 结构说明、 TC 属性说明。 b ) TC 自动生成算法对需要测试的程序进行插桩。 插桩是 向待测程序中插入特殊的程序片段(探针),用于跟踪动态测 试中 TC 的行为,采集程序语句的执行、变量变化等信息。 这 些信息称之为测试反馈信息,是 TC 自动生成算法产生、选择 和修正 TC 数据的基础,也是构造用于对 TC 质量进行评估的 适应度函数的依据。 c ) TC 自动生成算法根据适应度函数判断测试目标是否已 经覆盖,如果覆盖则获得可用测试用例,算法结束;否则对 TC 进行选择与修正 TC ,产生新的 TC 数据。 如何对 TC 进行选 择、修正或补充新的 TC ,是 TC 自动生成算法框架的核心部分。 现有的主要研究包括基于随机算法的 TC 自动生成算法、基于 遗传的 TC 自动生成算法、基于蚁群的 TC 自动生成算法和基 于粒子群的 TC 自动生成算法。 2   TC 自动生成算法 2 畅 1   TC 自动生成算法评价指标 TC 自动生成算法的主要评价指标有首次失效发现平均 TC 数( F 唱 measure )、测试覆盖率、迭代次数、复杂度、执行时间、 累计 TC 产生数量。 其中,算法迭代次数与算法复杂度为主要 评价指标;而算法执行时间容易受到待测程序的复杂度以及测 试环境的干扰,因此为参考指标。 F 唱 measure 是对发现待测程 序中首个失效数据所需要的平均 TC 数。 常见的测试覆盖率 包括语句覆盖率、判定(分支)覆盖率、条件覆盖率、路径覆盖 率、 def 唱 use 覆盖率、函数覆盖率、状态覆盖率等。 复杂度是指 TC 自动生成算法的时间复杂度,反映了算法执行时间随 TC 数 量增加而增长的量级,在很大程度上可以反映出算法的优劣程 度。 执行时间是指 TC 自动生成算法从开始运行到完成测试 目标覆盖或退出算法时经历的运行时间。 累计 TC 产生数量 是指 TC 在算法整个执行期内产生的 TC 数量的总和。 2 畅 2  基于随机算法的 TC 自动生成算法 基于随机算法的 TC 自动生成算法,简称随机测试( ran 唱 dom test , RT )由 Hamlet 于 1994 年提出[5],是一种基本的软件 自动化测试技术[6],它通过在程序输入域上随机产生测试输 入来测试程序。 RT 的基本思想是使用 TC 规格需求随机生成 TC ,然后使 用生成的 TC 运行待测程序,最后检测测试目标是否被覆盖, 该方法不要求 TC 生成算法返回测试反馈信息。 2004 年, Chen 等人对基本的 RT 算法进行了改进,提出适 应性随机测试( adaptive random test , ART )[7],并使用 F 唱 mea 唱 sure对算法性能进行比较;他们还进一步提出 MRRT [8] 对基本 的 RT 算法计算性能进行改进。 同年, Chen 等人在 ART 中引 入输入域分区的概念,提出新的 DP [9] 算法以减少 ART 算法开 销。 ART 通过最大化 TC 在输入空间上的距离避免其对测试 目标中同一错误过度覆盖。 2005 年, Mayer [10] 进一步对此方法 进行改进,提出基于格的适应性 RT ,优化了距离比较次数,同 时在输入域采用递归格构建的方式给出 TC 的最大距离。 2006—2007 年, Chen 等人提出基于区域分割的 ART 算法[11] 和 Balancing [12] 算法,在执行时间和 F 唱 measure 两个指标上降低 了 ART 的算法开销,但仍然存在 ART 多维问题。 2007 年, Chen 等人对 ART 算法中出现的分区边界 TC 优先问题进行了 改进[13],通过对 F 唱 measure 指标的测量证明了改进的有效性。 总体来说, RT 算法可以划分为四类: a )基本随机算法; b ) 基于距离的 RT 算法( DART ),如 FSCS [7]、 ECP 唱 FSCS [13]; c )基 于排斥区域的 RT 算法( RRT ),如 MRRT [8]; d )基于区域划分 的 RT ( PART )算法,如 DP [9]、 IP [11]、 balancing [12]。 RT 的优点突出表现在: a )算法简单、易于执行; b )生成 TC 效率高; c ) RT 能够避免测试人员的主观偏见。 同时, RT 的缺 点也非常明显: a ) RT 的代码覆盖率低,测试覆盖率是衡量测试 充分度的重要指标,由于测试输入随机产生,很多情况下 RT 难以保证对程序代码的高覆盖率; b ) RT 会生成大量的非法或 无用测试数据,一般而言待测程序对输入数据有一定约束或限 制,而 RT 会忽略这些约束,从而生成大量的非法或无用测试 数据; c ) RT 表现出明显的盲目性,尽管 ART 算法较纯 RT 有所 改进,但由于 RT 算法本身缺乏待测目标的内部信息[5],同时 TC 间缺乏知识共享与协同(特别在输入域存在非均匀分布、非 连续分布的情况下),这导致 RT 表现出明显的盲目性。 尽管 RT 有其固有的缺陷,但依然是其他优化算法,特别 是近些年来迅速发展的启发性 TC 生成算法的数据来源与对 比基准。 2 畅 3  基于遗传的 TC 自动生成算法 基于遗传的 TC 自动生成算法简称遗传算法( genetic algo 唱 rithm , GA ),是一种启发性算法,它将自然界遗传基因的遗传过 程与达尔文适者生存原则相结合,不断进化(选择、交叉、变 异)与淘汰 TC ,最终得到可用 TC 的过程。 1995 年, Jones 在软 件结构性测试中将生物学的 GA [14] 引入到 TC 自动生成中 来[15,16],其基本算法如图 2 所示。 ·204· 计 算 机 应 用 研 究   第 29 卷 GA 形式化描述如下: GA ={π, TC ,P,R,M,F,τ}。 TC 种 群即 TC 的集合,π是 TC 种群的规模; TC 是初始种群, TC = { TC1 , TC2 ,⋯, TCn },其中 TCi (1≤i≤π}是种群中的个体;P、 R、M 分别为 GA 的三个基本操作,即基因选择、基因交叉和基 因变异, GA 中的基因一般为 TC 的二进制位串;F 是评价个体 适应度的适应度函数,即 TCi 的适应度可以表示为 fi =F ( TCi );τ为遗传算法的终止条件,通常为算法最大允许迭代次 数或适应度收敛值。 GA 的基本步骤如下: a )随机产生 TC ,作为 TC 初代种群,规模为 n。 b )判断算法是否满足覆盖测试目标,若覆盖,则执行步骤 h );否则执行步骤 c )。 c )判断算法是否满足达到最大迭代次数,若达到最大迭 代次数,则执行步骤 h );否则执行步骤 d )。 d )对 TC 群体的个体计算 fi =F( TCi )。 e )依据 fi 对 TC 种群进行选择产生亲代种群。 f )对亲代种群执行交叉/变异产生新 TC 。 g )形成下一代 TC 种群,并执行步骤 b )。 h )算法结束,输出可用 TC 。 GA 本质上是将 TC 生成过程转换为寻找最适合测试环境 的最优 TC 的过程。 其核心过程包括: a ) 生存环境的定义; b ) 根据测试任务设计适应度函数,量化 TC 对环境的适应性; c ) 亲代选择策略; d )交叉/变异策略。 Jones 等人[15,16] 在 GA 的研究中使用 TC 和实际可覆盖目 标间的汉明距离构造评价 TC 的适应度函数,并使用单一数据 位变异和单点交叉作为 TC 种群更新方式对待测程序进行判 断覆盖。 实验证明 GA 在迭代次数上较 RT 算法有显著降低。 1997 年, McGraw 等人[17] 使用条件表达式操作数和测试目标的 距离作为适应度函数构造 GA ,实验证明新 GA 在测试目标覆 盖效率上有所改善。 1999 年, Pargas 等人[18] 使用控制依赖图 ( control dependence graphs , CDG )对适应度函数进行构造,指出 一般情况下 CDG 产生的谓词路径较少,验证了新算法 TGen 在 迭代次数上优于 RT 算法。 2000 年, Lin 等人[19] 在控制流图 ( control 唱 flow diagram , CFD )上根据 TC 执行的路径与目标实际 路径相似度定义适应度函数,对待测程序进行了路径覆盖测 试。 2001 年, Bottaci [20] 将适应度定义为 TC 的非负变异成本。 2005 年, Girgis [21] 对数据流进行分析,根据变量定义与使用之 间的关系构造 def 唱 use 路径,并进行 def 唱 use 路径覆盖测试,该 算法在迭代次数、 def 唱 use 路径覆盖率、累计 TC 产生数量三个 指标上均优于 RT 算法。 2007 年, Ghiduk 等人[22] 在 DT ( domi 唱 nator tree )上构建适应度方程,提出 TGGA 算法,指出 Girgis 给 出的适应度方程会丢失 TC 的差异信息,从而忽略了 TC 之间 潜在的优劣性,这将导致 TC 丧失择优进化的机会; TGGA 算法 在测试覆盖率、迭代次数、执行时间、累计 TC 产生数量四个指 标上优于 RT 算法。 2009 年, Shen 等人[23] 在 GA 中使用禁忌 搜索作为 TC 种群的变异方式,使得 TC 种群中的个体 TC 在进 入繁殖前能够得到预先的独立优化,较 Jones 提出的 GA ,新的 算法在函数覆盖率指标上有一定提高。 2010 年, Pinto 等人[24] 提出多目标适应度函数,可实现针对覆盖率、测试时间、失效数 据发现能力的综合优化,实验证明该算法较 RT 在目标覆盖率 和执行时间两个指标上均有所改善。 GA 在 TC 自动生成算法中的引入,减少了 TC 自动生成 的盲目性,提高了软件测试的效率;但 GA 的早期迭代阶段, TC 种群中存在大量次优解。 这些次优解在交叉算子的作用 下进化为最优解的概率较大,即算法初期 TC 种群的质量改 善速度比较快;随着 TC 群体多样性的逐渐降低, TC 种群进 化出最优解的速度下降,即 GA 的宏观探索能力大于局部求 精能力。 2 畅 4  基于蚁群的 TC 自动生成算法 基于蚁群的 TC 自动生成算法简称蚁群优化( ant colony optimization , ACO )算法,是 McMinn 等人[25] 将 Dorigo 等人[26] 提出的仿生寻优启发性算法引入到 TC 自动生成中而形成的 新算法。 ACO 算法基本思想是将待测程序结构信息表达为某种知 识,然后应用蚁群算法完成知识推理,在推理过程中生成所需 要的 TC 。 其基本原理是将蚁群智能体放在路径有向图 G 上 (蚂蚁指形成 TC 编码的数据元), 通过蚂蚁移动、释放信息素 (覆盖图 G 中边形成的标记)等行动搜索最优路径 P,从而寻 找可覆盖测试目标 O 的输入变量。 蚂蚁在图 G 上的移动路径 经过解码形成 TC 。 ACO 算法的核心过程包括: a )将测试问题转换成有向图 G; b ) 构造基于图 G 的评估函数 F,用于量化被信息素覆盖的 路径优劣; c ) 可能解生成算法与停止准则; d ) 信息素更新策 略; e )蚁群个体从图 G 的节点 A 移动到节点 B 的策略。 ACO 基本原理和 ACO 算法路径网络构造基本原理如图 3、4 所示。 ACO 算法首先要解决的问题是知识表达, 即如何将待测 程序的输入空间映射为蚁群算法的路径[27]。 为了适应输入空 间中不同数据结构的变量, 通常使用输入变量的二进制形式 来构建映射模型。 首先,将待测程序输入空间 D 的某一 TC 通 过编码规则转换为位串 b;b 与路径有向图 G 的一条路径 P 相 ·304·第 2 期 聂 鹏,等:软件测试用例自动生成算法综述     对应;经过蚁群算法将产生新的路径 P′;P′经解码得到对应的 位串 b′,b′经转换形成新的 TC 。 ACO 算法路径有向图记为 G =(V,E), 节点集记为 V ={v1 ,v2 ,⋯,v2N}。 ACO 算法基本步骤如下: a )初始化,初始化蚁群和控制参数。 b )将规模为 m 的蚁群随机分配到图 G 的路径节点上,并 为路径上的每个有向边分配一个极小常数作为初始信息素。 c )蚁群中的个体按照算法给定的状态移动规则在节点间 移动。 d )对蚁群中的个体进行信息素的局部更新。 e )蚁群中的个体顺次选择多个节点完成信息素局部更 新,并进行路径构造。 f )对构造好的路径进行解码,生成 TC ;使用 TC 运行待测 程序,并通过适应度函数 F 对 TC 进行适应度评估,最终保留 最优路径。 g )若算法满足终止条件,则输出 TC ,结束算法;否则转入 步骤 c )。 2003 年, McMinn 等人[25] 将 ACO 算法引入到 TC 自动生成 中,用于寻找待测程序的状态迁移序列,对演化算法进行补充 优化。 同年, Doerner 等人[28] 使用 ACO 算法提取可用测试路 径,用于优化测试覆盖率和测试成本。 2005 年, Li 等人[29] 使 用 ACO 算法基于 UML 对待测程序进行状态覆盖测试。 2007 年,傅博[27] 在 ACO 算法中引入路径变异算子和自适应挥发系 数, 提高了蚂蚁路径的多样性,在迭代次数上优于 GA 。 2009 年, Li 等人[30] 将待测程序的输入域划分为不同的子域,基于子 域构建搜索路径图,并基于该路径图使用 ACO 算法生成 TC , 该算法在迭代次数上优于 GA 。 2009 年,陈明师等人[31] 对标 准 ACO 算进行改进,提出多态蚁群 TC 自动生成算法( polymor 唱 phic ant colonies algorithm , PACA )。 PACA 将蚁群划分为侦察 蚁、搜索蚁和工蚁,从而缩小了算法搜索空间,增强了蚁群间的 协作,提高了搜索效率。 陈明师等人的实验证明了 PACA 在 TC 生成的执行时间上优于 ACO 算法。 2010 年, Xu 等人[32] 在 ACO 算法寻径中引入遗传算法,提出 GAACO 算法,克服了遗 传算法局部搜索能力差、易早熟现象,同时弥补了蚁群算法费 时、易停滞现象,增强了 TC 生成的随机性、快速性和全局收敛 性。 Xu 等人实验证明了 GAACO 在迭代次数上优于 GA 、 ACO 和 RT 算法。 ACO 算法是一个增强型学习系统, 具有分布式计算、易于 与其他算法相融合、鲁棒性强等优点,但由于搜索初期信息素 相对匮乏, 导致算法的搜索效率降低, 正反馈机制容易产生 停滞早熟现象。 2 畅 5  基于粒子群的 TC 自动生成算法 基于粒子群的 TC 自动生成算法简称粒子群优化( particle swarm optimization , PSO )算法,是 Windisch 等人[33] 基于 Kenne 唱 dy 和 Eherhart 通过对动物社会行为的研究成果[34] 而提出的一 种新的 TC 自动生成算法。 PSO 具备算法简单、鲁棒性好的特 点,通过 TC 的个体认知与群体智能的相互影响和作用动态地 产生用例数据,具有很好的导向性和收敛性。 PSO 算法将 TC 规格需求作为算法的解空间;可能覆盖测 试目标的潜在 TC 集合称之为粒子群,每个潜在可达测试目标 的 TC 称之为粒子;每个粒子都以一定速度在 D 维解空间中运 动,并由一个量化评估函数产生适应值( fitness value );粒子群 追随当前最优粒子并在解空间中持续搜索,直至满足算法结束 条件。 在每一次算法迭代中,粒子通过跟踪两个极值进行自我 更新,第一个极值为粒子本身所找到的最优解,称之为个体最 优(pbest );另一个极值是整个粒子群当前找到的最优解,称之 为全局最优(gbest )。 PSO 算法基本原理如图 5 所示。 PSO 算法基本步骤如下: a )随机初始化粒子的位置和速度。 b )计算每个粒子的适应值。 c )对于每个粒子,将其适应值与所经历过的最好位置的 适应值进行比较,若较好,则将其作为当前的最好位置。 d )对每个粒子,将其适应值与全局所经历的最好位置的 适应值进行比较,若较好,则将其作为当前的全局最好位置。 e )如未达到结束条件(通常为足够好的适应值或达到一 个预设的最大代数)则执行步骤 f ),否则算法结束。 f )对粒子的速度和位置进行更新,产生新粒子群并返回步 骤 b )。 2007 年, Windisch 等人[33] 将 PSO 算法引入到 TC 自动生 成算法中,并通过分支覆盖测试与 GA 进行了分析和比较,指 出 PSO 在对复杂对象的测试中优于 GA 。 2008 年,李爱国等 人[35] 采用分支函数叠加法构造 PSO 适应值函数,对测单元 的执行路径进行覆盖测试,并与 GA 进行了分析和比较工作, 证明 PSO 算法在迭代次数和执行时间两个指标上优于 GA 。 同年, Hla 等人[36] 在 PSO 算法中,提出一种基于综合覆盖率 的适应度测量方法,并与随机算法进行了性能对比,分析了 PSO 算法在复杂度上优于 GA 。 2010 年, Cui 等人[37] 在 PSO 算法中构建 EFAU 路径度量函数, PSO 适应值为目标路径与 EFAU 度量值间的相似度, Cui 等人实验性地比较了 GA 、 PSO 和 EFAU 唱 PSO 的迭代性能,证明 EFAU 唱 PSO 在迭代次数上优 于其他两种算法。 周红等人[38] 在 PSO 算法中引入 GA ,增强 PSO 中 TC 种群的多样性,降低 PSO 算法的早熟特性,在迭代 次数和执行时间两个指标上优于 GA 。 Nayak 等人[39] 基于数 据流图建立 PSO 测试用例生成算法,对 PSO 和 GA 两种算法 的复杂度进行了分析。 在 def 唱 use 覆盖测试实验中,验证了 PSO 算法较 GA 需要的迭代次数更少。 PSO 以其计算迅速和易用性优于传统算法,但是 PSO 如 同其他智能算法一样存在早熟。 通常认为, PSO 的早熟是由粒 子群丧失多样性,从而导致群体中大部分个体聚集在一个很小 的搜索范围,当该搜索范围不含最优解时,算法将受困于局部 最优。 ·404· 计 算 机 应 用 研 究   第 29 卷 3  结束语 TC 自动生成算法的研究大大提高了软件测试的自动化水 平,为软件失效数据采集提供了一种自动化方法。 TC 自动生成 算法的研究成果得到越来越广泛的应用,并在学术界和工业界 均得到了重视。 TC 自动生成是建立在对软件结构抽象描述的 基础上,通过对部分人工软件测试行为进行替代,有效提高了测 试效率和测试失效辨识,有利于软件可靠性的评估和预测。 在现有的自动化方法中仍存在一些缺陷或不足,需在以下 几个方面进行深入研究: a )测试失效发现和测试自动化密不可分。 一方面,失效 发现是测试自动化不可缺少的内容;另一方面,自动化又使得 测试失效发现更加困难。 目前对测试失效发现的研究比较少, 实践中经常通过对比不同软件版本的输出结果进行测试失效 发现,因此测试失效发现是未来研究的内容之一。 b )在现有的 TC 自动生成算法中, RT / ART 算法由于无须 跟踪 TC 在待测程序中的运行状态而表现出较大的盲目性; GA 通过对 TC 运行状态的跟踪,加强了 TC 对测试目标的针对 性,但算法较为复杂、收敛性较差是 GA 的主要问题; ACO 具有 分布式计算、与其他算法易于融合、鲁棒性强等优点;但由于搜 索初期信息相对匮乏, 导致算法的收敛性降低, 算法中的正 反馈机制也容易产生早熟现象; PSO 算法简单、鲁棒性好,通过 粒子群的个体认知与群体智能间的知识传递,动态地产生用例 数据,对测试目标的导向性和收敛性均较好,但是 PSO 如同其 他智能算法一样存在早熟,如何抑制早熟是该算法的重要研究 内容。 c ) TC 自动生成算法中仍需不断引入新的理论和方法,通 过对新理论和方法的研究,尽可能地扩展测试覆盖,提升测试 效果,使软件测试在智能性和高效性两个方面有更进一步的 提高。 参考文献: [1] Software &Systems Engineering Committee . IEEE 829—1983, IEEE standard for software and system test documentation [ S ].[ S . l .]: IEEEComputer Society , 1983. [2] Software &Systems Engineering Committee . IEEE 829—1998, IEEE standard for software and system test documentation [ S ].[ S . l .]: IEEEComputer Society , 1998. [3] Software &Systems Engineering Committee . IEEE 829—2008, IEEE standard for software and system test documentation [ S ].[ S . l .]: IEEEComputer Society , 2008. [4] 单锦辉, 姜瑛, 孙萍.软件测试研究进展[ J ].北京大学学报, 2005,41(1): 134唱145. [5] HAMLETR . Random testing [ M ]// Encyclopedia of Software Engi 唱 neering . New York : Wiley ,1994. [6] GERLICHR , GERLICHR , BOLLT . Random testing : from the classical approach to a global view and full test automation [ C ]// Proc of the 2 nd International Workshop on Random Testing . New York : ACMPress ,2007:30唱37. [7] CHENTY , LEUNGH , MAKIK . Adaptive random testing [ C ]// Proc of the 9 th Asian Computing Science Conference . Berlin : Sprin 唱 ger , 2004:320唱329. [8] CHENTY , KUOFei 唱 ching , MERKELRG , et al. Mirror adaptive random testing [ C ]// Proc of the 3 rd International Conference on Quali 唱 ty Software . Washington DC : IEEEComputer Society , 2003:4唱11. [9] CHENTY , MERKELRG , EDDYG , et al. Adaptive random tes 唱 ting through dynamic partitioning [ C ]// Proc of the 4 th International Conference on Quality Software . Washington DC : IEEEComputer So 唱 ciety , 2004:79唱86. [10] MAYERJ . Lattice 唱 based adaptive random testing [ C ]// Proc of the 20 th IEEE / ACMInternational Conference on Automated Software En 唱 gineering . New York : ACMPress , 2005:333唱336. [11] CHENTY , HUANGDe 唱 hao , ZHOUZhi 唱 quan . Adaptive random testing through iterative partitioning [ C ]// Proc of the 11 th Conference on Software Technologics . Berlin : Springer ,2006:155唱166. [12] CHENTY , HAODe 唱 huang , KUOFei 唱 ching . Adaptive random tes 唱 ting by balancing [ C ]// Proc of the 2 nd International Workshop on Random Testing , Colocated with the 22 nd IEEE / ACMInternational Conference on Automated Software Engineering . New York : ACM Press ,2007:2唱9. [13] CHENTY , KUOFei 唱 ching , LIUHuai . Enhancing adaptive random testing through partitioning by edge and centre [ C ]// Proc of Austra 唱 lian Software Engineering Conference . Washington DC : IEEE Computer Society ,2007:265唱273. [14] HOLLANDJH . Adaptation in natural and artificial systems : an in 唱 troductory analysis with applications to biology , control , and artificial intelligence [ M ]. Cambridge : MITPress ,1975: 228. [15] JONESBF , STHAMERH , EYRESDE . Automatic structural tes 唱 ting using genetic algorithms [ J ].Software Engineering Journal, 1996,11(5): 299唱306. [16] JONESBF , STHAMERH , EYRESDE . Generating test data for ADA procedures using genetic algorithms [ C ]// Proc of the 1 st Inter 唱 national Conference on Genetic Algorithms in Engineering Systems : Innovations and Applications .1995:65唱70. [17] McGRAWG , MICHAELC , SCHATZM . Generating software test data by evolution [ J ].IEEETrans on Software Engineering, 1997,27(12): 1085唱1110. [18] PARGASRP , HARROLDMJ , PECKRR . Test 唱 data generation using genetic algorithms [ J ].Software Testing,Verification and Reliability,1999,9(4): 263唱282. [19] LINJ , YEHP . Using genetic algorithms for test case generation in path testing [ C ]// Proc of the 9 th Asian Test Symposium . Washington DC : IEEEComputer Society , 2000:241唱246. [20] BOTTACIL . A genetic algorithm fitness function for mutation testing [ C ]// Proc of Software Engineering Using Metaheuristic In novative Algorithms Workshop at the 23 rd International Conference on Software Engineering .2001:3唱7. [21] GIRGISMR . Automatic test data generation for data flow testing using a genetic algorithm [ J ].Journal of Universal Computer Science,2005,11(6): 898唱915. [22] GHIDUKAS , HARROLDMJ , GIRGISMR . Using genetic algo 唱 rithms to aid test 唱 data generation for data 唱 flow coverage [ C ]// Proc of the 14 th Asia 唱 Pacific Software Engineering Conference .[ S . l .]: IEEEComputer Society , 2007:41唱48. [23] SHENXia 唱 jiong , WANGQian , WANGPei 唱 pei , et al. Automatic generation of test case based on gats algorithm [ C ]// Proc of IEEEIn 唱 ternational Conference on Granular Computing .2009:496唱500. (下转第 413 页) ·504·第 2 期 聂 鹏,等:软件测试用例自动生成算法综述     仪器仪表学报,2009,30(9):1886唱1890. [42] VIDAKOVICB , LOZOYACB . On time 唱 dependent wavelet denoi 唱 sing [ J ].IEEETrans on Signal Processing,1998,46(9):2549唱 2551. [43] CANDESEJ . Ridgelets : theory and applications [ D ]. Stanford : Stanford University ,1998. [44] DONOHODL , DUNCANMR . Digital curvelet transform : strategy , implementation and experments [ D ]. Stanford : Stanford University , 1999. [45] CANDESEJ , DONOHODL . Curvelets : a surprisingly effective nonadaptive representation for objects with edges [ R ]. Stanford : Stanford University ,1999. [46] DOMN , VETTERLIM . The Contourlet transform : an efficient di 唱 rectional multiresolution image representation [ J ].IEEETrans on Image Processing,2005,14(12):2091唱2106. [47] PENNECEL , MALLATS . Sparse geometric image representations with bandelets [ J ].IEEETrans on Image Processing,2005,14 (4): 423唱438. [48] CANDESEJ . Ridgelet : theory and applications [ D ]. Stanford : Stanford University , 1998. [49] STARCKJL , CANDESEJ , DONOHODL . The Curvelet transform for image denoising [ J ].IEEETrans on Image Processing,2002, 11(6):670唱684. [50] 肖小奎,黎绍发.加强边缘保护的 Curvelet 图像去噪方法[ J ].通 信学报,2004,25(2):9唱15. [51] 刘盛鹏,方勇.基于数学形态学的 Contourlet 变换域图像降噪方法 [ J ].光子学报,2008,37(1):197唱201. [52] 王军华,方勇.基于 Curvelet 稀疏表示的图像盲分离初始化[ J ]. 应用科学学报,2009,27(2):162唱166. [53] 练秋生,陈书贞.基于解析轮廓波变换的图像稀疏表示及其在压 缩传感中的应用[ J ].电子学报,2010,38(6):1293唱1298. [54] 张文革,刘芳,焦李成,等.基于 Bandelets 域逐子块阈值的图像去 噪[ J ].电子学报,2010,38(2):290唱294. [55] DONOHODL . Wedgelets : nearly minimax estimation of edges [ J ]. Annals Statistics,1999,27(3):859唱897. [56] 郭武,王润生,张鹏,等.基于独立分量分析的图像去噪研究[ J ]. 信号处理,2008,24(3):381唱385. [57] HYVARINENA , HOYERP , OJAE . Sparse code shrinkage for de 唱 noising [ C ]// Proc of IEEEInternational Joint Conference on Neural Networks Computational Intelligence .1998:859唱864. [58] OLSHAUSENAB , FIELDDJ . Sparse coding with an overcomplete basis set : a strategy employed by V 1[ J ].Vision Research,1997, 37(23):3311唱3325. [59] HARITOPOULOSM , YINHu 唱 jun , ALLINSONNM . Image denois 唱 ing using self 唱 orgnizing map 唱 based nonlinear independent component analysis [ J ].Neural Network,2002,15(8唱9):1085唱1098. [60] HANXian 唱 hua , CHENYW , NAKAOZ , et al. ICA 唱 domain filtering of Poisson noise images [ C ]// Proc of the 3 rd International Symposium on Multispectral Image Processing and Pattern Recognition .2003:811唱 814. [61] ANJALIP , AJAYS , SAPRESD . A review on natural image denoi 唱 sing using independent component analysis ( ICA ) technique [ J ]. Advances in Computational Research,2010, 2(1):6唱14. [62] 蔡泽民,赖剑煌.一种基于超完备字典学习的图像去噪方法[ J ]. 电子学报,2009,37(2): 347唱350. [63] 李恒建 尹忠科,王建英.基于量子遗传优化算法的图像稀疏分解 [ J ].西南交通大学学报,2007,42(1):19唱23. (上接第 405 页) [24] PINTOGHL , VERGILIOSR . A multi 唱 objective genetic algorithm to test data generation [ C ]// Proc of the 22 nd International Confe 唱 rence on Tools with Artificial Intelligence .2010:129唱134. [25] McMINNP , HOLCOMBEM . The state problem for evolutionary tes 唱 ting [ C ]// Proc of International Conference on Genetic and Evolutio 唱 nary Computation . Berlin : Springer 唱 Verlag , 2003:2488唱2498. [26] DORIGOM , GAMBARDELLALM . Ant colony system : a coopera 唱 tive learning approach to the traveling salesman problem [ J ].IEEE Trans on Evolutionary Computation,1977,1(1): 53唱66. [27] 傅博.基于蚁群算法的软件测试数据自动生成[ J ].计算机工程 与应用, 2007,43(12): 97唱99. [28] DOERNERK , GUTJAHRWJ . Extracting test sequences from a Markov software usage model by ACO [ C ]// Proc of International Con 唱 ference on Genetic and Evolutionary Computation . Berlin : Springer 唱 Verlag , 2003:2465唱2476. [29] LIHuai 唱 zhong , LAMCP . Software test data generation using ant colony optimization [ C ]// Proc of World Academy of Science , Engineering and Technology .2005:1唱4. [30] LIKe 唱 wen , ZHANGZi 唱 lu , LIUWen 唱 ying . Automatic test data generation based on ant colony optimization [ C ]// Proc of the 5 th In 唱 ternational Conference on Natural Computation .2009:216唱220. [31] 陈明师, 刘晓洁, 李涛.基于多态蚁群算法的测试用例自动生成 [ J ].计算机应用研究, 2009, 26(6):2347唱2348. [32] XUDuo 唱 yong , LIZhi 唱 shu . Study on test case automated generation technology based on genetic algorithm and ant colony optimization al 唱 gorithm [ C ]// Proc of International Conference on Electrical and Con 唱 trol Engineering . Washington DC : IEEEComputer Society , 2010: 5655唱5658. [33] WINDISCHA , WAPPLERS , WEGENERJ . Applying particle swarm optimization to software testing [ C ]// Proc of the 9 th Genetic and Evolutionary Computation Conference . New York : ACMPress , 2007:1121唱1128. [34] KENNEDYJ , EBERHARTR . Particle swarm optimization [ C ]// Proc of the IEEEInternational Conference on Neutral Networks . Pis 唱 cataway : IEEEPress , 1995:1942唱1948. [35] 李爱国, 张艳丽.基于 PSO 的软件结构测试数据自动生成方法 [ J ].计算机工程, 2008,34(6): 93唱97. [36] HLAKHS , CHOIYS , PARKJS . Applying particle swarm optimi 唱 zation to prioritizing test cases for embedded real time software retest 唱 ing [ C ]// Proc of the 8 th IEEEInternational Conference on Computer and Information Technology Workshops . Washington DC : IEEECom 唱 puter Society ,2008:527唱532. [37] CUIHuan 唱 huan , CHENLi , ZHUBian , et al. An efficient automated test data generation method [ C ]// Proc of International Conference on Measuring Technology and Mechatronics Automation . Washington DC : IEEEComputer Society , 2010:453唱456. [38] 周红, 张胜, 刘琳岚, 等.基于 GA 唱 PSO 算法的路径测试数据自 动生成[ J ].计算机应用研究, 2010,27(4):1366唱1369. [39] NAYAKN , MOHAPATRADP . Automatic test data generation for data flow testing using particle swarm optimization [ J ].Contempora唱 ry Computing,2010,95(2): 1唱12. ·314·第 2 期 郭德全,等:基于稀疏性的图像去噪综述    
还剩5页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

super_chai

贡献于2012-07-01

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf