（计算机应用技术专业论文）二叉树结构型测试数据生成方法研究.pdf

学位论文数据集 中图分类号 t p 3 1 1 5 学科分类号 5 2 0 4 0 论文编号 10 0 10 2 0 1 10 7 4 9 密级公开 学位授予单位代码 10 0 1o 学位授予单位名称北京化工大学 作者姓名王倩学号 2 0 0 8 0 0 0 7 4 9 获学位专业名称计算机应用技术获学位专业代码 0 8 1 2 0 3 课题来源自然科学基金项目研究方向软件测试与软件可靠性 论文题目 二叉树结构型测试数据生成方法研究 关键词测试数据生成，动态数据结构，二叉树，二叉树形态生成，遗传算法 论文答辩日期 2 0 1 1 5 2 6论文类型 基础研究 学位论文评阅及答辩委员会情况 姓名职称工作单位 学科专长 指导教师赵瑞莲 教授北京化工大学 软件测试与软件可靠性 过程工业监测、编译技 评阅人1彭四伟副教授北京化工大学 术应用、并行计算 评阅人2赵会群教授北方工业大学软件测试 评阅人3 评阅人4 评阅人5 分布式系统、网格计算、 答辩委员会主席赵英教授北京化工大学 计算机网络 网络信息获取技术的研 答辩委员1山岚教授北京化工大学 究 过程工业监测、编译技 答辩委员2彭四伟副教授北京化工大学 术应用、并行计算 智能信患、处理、嵌入式 答辩委员3张杰副教授北京化工大学 系统 答辩委员4聂伟 副教授北京化工大学 移动通信技术 答辩委员5 压：一 四 论文类型：1 基础研究2 应用研究3 开发研究4 其它 中图分类号在中国图书资料分类法) ) 查询。 学科分类号在中华人民共和国国家标准( g b t1 3 7 4 5 9 ) 学科分类与代码中 查询。 论文编号由单位代码和年份及学号的后四位组成。 摘要 二叉树结构型测试数据生成方法研究 摘要 软件测试是软件工程学科的重要组成部分，在实际的软件开发过程 中，软件测试所发挥的重要作用己得到软件开发人员的广泛认同。软件测 试以发现软件中潜藏的缺陷和错误为目的，确保软件的可靠性和提高软件 的质量。 测试数据自动生成是软件测试中的一个重要环节，目前关于测试数据 生成的研究主要集中于数值和字符串类型的数据，对于指针和动态数据结 构类型的测试数据生成研究较少。而且，现有的解决动态数据结构类型输 入数据的测试生成方法大多采用静态方法，这对于复杂动态数据结构的测 试数据生成实现困难，并且测试生成效率较低。 二叉树是一种广泛使用并且具有代表性的动态数据结构，为此，本课 题针对二叉树结构，以路径覆盖为测试准则，提出了一种基于c o n c o l i c 的 二叉树结构型测试数据自动生成方法，使用遗传搜索算法生成二叉树结构 的形态，并利用约束求解确定其数据域的值。针对二叉树结构型测试数据 的特点，设计了一种新的染色体编码方式，用以表示二叉树结构的形态， 探讨了适用于二叉树结构的交叉操作和变异操作。同时，通过约束解决技 术求解其数据域的值，实现面向路径的二叉树结构型测试数据自动生成方 法。 为验证本课题提出的二叉树结构型测试数据自动生成方法的可行性， t 北京化t 大学硕士学位论文 选取二叉树操作程序进行大量实验。实验结果表明，基于遗传算法的二叉 树形态测试生成方法是行之有效的，不仅能够实现以二叉树结构类型为输 入的面向路径的测试数据自动生成，而且其测试生成效果明显优于随机生 成方法。 关键词：测试数据生成，动态数据结构，二叉树，二叉树形态生成，遗传 算法 t e s td a t ag e n e r a t i o nf o rp r o g r a m sw i t h b i n a r yt r e es t r u c t u r ea si n p u t s a b s t r a c t s o r w a r et e s t i n gi sa ni m p o r t a mp a r to fs o r w a r ee n g i n e e r i n g i nt h e s o r w a r ed e v e l o p m e n tp r o c e s s ，t h ei m p o r t a n tr o l et h a ts o r w a r et e s t i n gp a l y si s n o ww i d e l yr e c o g n i z e d i ng e n e r a l ，t h em a i nt a s ko fs o f t w a r et e s t i n gi sp r o o d e t e c t i o na n dp r e v e n t i o n a c c o r d i n gt o at e s t c r i t e r i o n ， i t1 e a d st ot h e d i s c o v e qo fe r r o r sb ym e a s u r i n ga n de v a l u a t i n gt h eq u a l i t yo fs o r w a r ei n o r d e rt oi m p r o v et h er e l i a b i l i t yo fs o r w a r e n o w a d a y sm o s tr e s e a r c hh a sb e e nf o c u s e do nt e s tg e n e r a t i o nf o rn u m e r i c d a t aa n ds t r i n gd a t a h o w e v e r ，t h e r ea r eaf i e ws t u d i e so nt e s tg e n e r a t i o nf o r p r o g r a m s w i t hp o i n t e r sa n dd y n a m i cd a t as t n j c t u r e s b e s i d e s ， t e s td a t a g e n e r a t i o nu s u a l l yc o n c e m su s i n gs t a t i ca p p r o a c h t oa u t o m a t i cp r o g r a m t e s t i n gf o rp r o g r a m si nt h ep r e s e n c eo fd y n a m i cd a t as t m c t u r e s i ti sd i m c u l t t oi m p l e m e n tt e s tg e n e r a t i o nf o rc o m p l e xd a t as t l l j c t u r ea n dh a v eah i 曲 e f n c i e n c yo f t e s tg e n e r a t i o n s o ，t h i sp 印e rp r o p o s e sac o n c o l i ct e s tg e n e r a t i o n 印p r o a c hf o rp r o g r a m s w i t hb i n a 巧t r e es t m c t u r ea u s i n p u t s ，aw i d e l yu s e dr e p r e s e n t a t i v eo fd y n a m i c d a t as 协j c t u r e t h es h a p eo fb i n a r yt r e es t n ，l c t u r ei sc r e a t e du s i n gg e n e t i c a l g o r i t h m ，a n ds i m u l t a n e o u s l yt h ev a l u e si nt h ed a t af i e l d sa r eg e n e r a t e db y i i i 北京化工大学硕士学位论文 m e a n so ft h ec o n s t r a i n t s o l v i n g t h i s p a p e rp r o p o s e s ac h r o m o s o m e r e p r e s e n t a t i o no ft h es h 印ew i t hr e s p e c t t ob i n a 秽t r e es t m c t u r e ，a n da c t u a l i z e s as e a r c ha l g o r i t h mf o r t h es h 印eg e n e r a t i o na r i s i n g 疳o mt h ec o n s t r a i n t so nt h e p o i n t e r sa l o n gag i v e np a t h i nt h ea p p l i c a t i o no fg e n e t i co p e r a t i o n s ，t h i sp a p e r a d o p t ss o m es t r a t e g i e st og e n e r a t et h en e ws h a p e so fb i n a r yt r e es t r u c t u r e st o e n s u r et h a tt h i sp r o c e s sw o u l dn o td e s t r o yt h es h 印ef e a t u r eo fb i n a 拶t r e e s t m c t u r e w h i l et h es h a p e so fb i n a 巧t r e es t m c t u r ea r e i m p r o v e da n d o p t i m i z e d ，印p r o p r i a t en u m e r i c a lv a l u e si nt h ed a t af i e l d so fag i v e nb i n a u t r e es t r u c t u r ea r eg e n e r a t e db yc o n s t r a i n ts o l v i n gt e c h n i q u et oo b t a i na ni n p u t t h a tm a k e st h et a 唱e tp a t he x e c u t e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o di sp r o m i s i n ga j l d e f l f e c t i v e ，a n di tn o to n l yc a ng e n e r a t et e s td a t af o rp r o g r a m sw i t hb i n a 拶t r e e s t r u c t u r ea si n p u t sb u ta l s oi so b v i o u s l ys u p e r i o rt ot h er a n d o mm e t h o do nt h e t e s tg e n e r a t i o np e r f o m l a n c e k e yw o r d s ：t e s td a t ag e n e r a t i o n ，d y n a m i cd a t as t m c t u r e ，b i n a 巧t r e e ，s h 印e g e n e r a t i o no fb i n a 拶t r e e ，g e n e t i ca l g o r i t h m i v 目录 目录 第一章绪论l 1 1 本文的研究背景与意义1 1 2 国内外软件测试数据生成研究现状2 1 3 本文的主要工作及创新点3 1 4 本文的组织结构3 第二章软件测试数据生成方法概述5 2 1 不同类型的测试数据生成方法概述5 2 1 1 数值型测试数据生成方法5 2 1 2 字符串型测试数据生成方法7 2 1 - 3 动态数据结构型测试数据生成方法8 2 2 基于不同启发式搜索算法的测试数据生成方法概述1 1 2 2 1 遗传算法1 1 2 2 2 蚁群算法15 2 2 3 模拟退火算法17 2 2 4 禁忌搜索算法18 2 3 基于不同测试准则的测试数据生成方法概述2 0 2 3 1 面向单目标的测试数据生成2 0 2 3 2 面向多目标的测试数据生成2 1 2 3 3 面向单路径的测试数据生成2 2 2 3 4 面向多路径的测试数据生成方法2 3 第三章一种面向路径的二叉树结构型测试数据自动生成方法研究2 5 3 1 二叉树结构型测试数据的特点2 5 3 2 面向路径的二叉树结构型测试数据生成方法框架2 7 3 3 一种基于遗传算法的二叉树形态生成方法研究2 8 3 3 1 二叉树形态的编码设计2 9 3 3 2 初始种群二叉树形态的生成3l 3 3 3 适应度函数的构造3 2 3 3 4 选择操作的设计3 3 3 3 5 交叉操作的设计3 4 3 3 6 变异操作的设计3 6 v 北京化工大学硕上学位论文 3 3 7 个体的评估过程4 2 4 5 4 5 4 5 4 5 4 5 4 6 5 0 5 5 5 5 5 5 5 7 6 7 6 9 c o n t e n t s c o n t e n t s c h a p t e r1 i n t r o d u c t i o n ”1 1 1b a c k g r o u l l da i l ds i g i l i f i c a n c eo f t h i st a s kr e s e 砌1 1 2r e s e a r c ha c t u a l i t yf o rt e s td a t ag e n e r a t i o n 2 1 3p r i m a r y 、o r ka i l dc o n t m u t i o no f t h ep 印e r 3 1 4c o n f i g u r a t i o no f m ep a p e r j 3 c h a p t e r2r e i a t e dw o r ko nt e s td a t ag e n e r a t i o n 5 2 1t e s td a t ag e n e r a t i o nf o rd i 娲r e n td a t a 够p e s 5 2 1 1t b s td a t ag e n e r a t i o nf o rn u m e r i cd a t a 5 2 1 2t e s td a t ag e n e r a t i o nf o rs t r i n g z 2 1 3t e s ti i a ：t ag e n e r a t i o nf o rd y n a m i cd a t as t m c t u r e 8 2 2t e s td a _ t ag e n e r a t i o nb a s e do nd i f r e r e n th e u r i s t i cs e a r c ha l g o r i t 1 1 2 2 1g e n e t i ca l g o r i t h l l l 2 2 2 觚c o l o n ya l g o r i t 1 5 2 2 3s i m u l a t e d e a l i n ga l g o r i t l u i l 1 7 2 2 4t a b o os e a r c ha l g o r i t l u n 1 8 2 31 e s td a t ag e n e r a t i o nb a s e do nd i 行e r e n tt b s tc r i t e r i a 2 0 2 3 1t h es i n g l e - o b j e c t i v eo r i e n t e dt e s td a 协g e n e r a t i o n 2 0 2 3 2t l l em u l t i _ o b j e c t i v eo r i e m e dt e s td a t ag e n e r a t i o n 2 l 2 3 3t h es i n g l e - pa c ho r i e n t e dt e s tda _ t ag e n e r a t i o n 2 2 2 3 4n em u l t i - p a t ho r i e n t e dt e s td a t ag e n e r a t i o n 2 3 c h a p t e r3t e s td a t ag e n e r a t i o nf o rp r o g r a m sw i t hb i n a r yt r e es t r u c t u r ea s i n p u t s 一“”2 5 3 1c h a r a c t e r i s t i c so f t e s td a t a 2 5 3 2t e s td a t ag e n e r a t i o nf r 胍e w o r kf o rb i n a r yt r e es t l l l c t u r e 2 7 3 3s h a p eg e n e r a t i o nu s i n gg e n e t i ca l g o r i t l l i l l 2 8 3 3 1t h ec i 啪m o s o m er e p r e s e n t a t i o no f s h 印_ e 2 9 v i i 3 3 2s h a p eg e n e r a t i o no f i n i t i a lp o p u l a t i o n j 1 3 3 3f i t n e s sf u n c t i o no f g e n e t i ca l g o r i 她j z 3 3 4s e l e c t i o np r o c e s so fg e n e t i ca l g o r i t l l n l j j 3 3 5c r o s s o v e rp r o c e s so f g e n e t i ca l g o r i t h m j | 3 3 6m u t a t i o np r o c e s so fg e n e t i ca l g o r i t j o 3 3 7e v a l u a t i o np r o c e s so f g e n e t i ca l g o r i n u n q z 3 4 n 啪e r i c a ld a t ag e n e r a t i o nf o r b i n 觚y t r e es t m c t u r e z c h a p t e r4e x p e r i m e n t a le v a l u a t i o n ”“”4 5 4 1e x p e r i m e n t a ld e s i g no ft e s td a t ag e n e r a t i o nf o rp r o g r 锄s 、) r i t h b i n a r y 仃e e 咖c t u r e 4 5 4 1 1t h es e l e c t i o no f t h et e s t e dp r o 鲈锄sa n do b j e c tp a t h s 4 ， 4 1 2t h ep a r 锄e t e rs e t t i n g sf o rg e n e t i ca l g o r i t l l l l l 4 ) 4 1 37 r e s td a t ag e n e r a t i o ne x p e r i m e n t s 4 5 4 2e x p e r i m e n t a lr e s u l t sa l l da 1 1 a l y s i s 4 0 4 3a n a l y s i sk e yf a c t o r st h a t 盘c tt h et e s tg e n e r a t i o np e 面m a n c e 5 u c h a p t e r5c o n c l u s i o n 5 5 5 1c o n c l u s i o no ft h i sp a p e r 5 5 5 2p r o s p e c to f 觚u r e 、o r k 5 5 r e f e r e n c e s 5 7 a p p e n d i x ”“- ”6 l a c k n o w i e d g e m e n t 6 7 s c i e n c ep a p e rp u b l i s h e dd u r i n gs t u d y i n gf b rd e g r e e “- ”“6 9 b r i e fi n t r o d u c t i o nt oa u t h o r 7 l v i i i 第一章绪论 第一章绪论 随着经济全球化以及信息技术的飞速发展，软件产业已经逐渐发展为国民经济 的战略性性支柱产业，并且，在国民经济中发挥着更加积极的不可代替的作用。可以 说，软件已经成为人们生活中不可缺少的且密切相关的一部分。软件产品的质量决定 了软件产品的可靠性与稳定性，它被看作是软件企业的生命。随之，软件测试技术应 运而生，并逐渐成为软件质量保障的重要方法。软件事故的频频发生，使得软件测试 在软件企业中的地位获得了很大程度的改善。目前，软件测试不再单纯只存在于软件 开发中的一个阶段，而是在整个软件开发过程中都有所涉及。 1 1 本文的研究背景与意义 软件开发人员发现他们的预算和时间有相当大的一部分花费在测试相关的工作 中【，其中测试数据自动生成是测试阶段的关键技术问题。测试数据生成过程就是寻 。 找满足某种测试准则的程序输入。按照是否实际运行被测试程序来划分，测试数据生 成方法一般分为静态法、动态法和c o n c o l i c 三类。静态测试数据生成方法不需要运行 被测程序，它通过对程序进行静态分析，得到相应的约束系统，求解约束系统即可 得到测试数据【2 j ；而动态测试数据生成方法需要使用输入数据的实际值来执行被测试 程序【3 j 。c o n c o l i c 是由c o n c r e t e 和s y m b o l i c 两个词所组成的合成词，该方法是符号执 行和具体执行的组合1 4 j 。 “ 针对数值型数据，人们提出了基于启发式搜索算法【5 】、动态域约减1 6 】、迭代松弛 法【_ 7 】等多种测试数据生成方法。还有一些研究针对字符串型数据的测试生成，例如， 文献【8 】提出了基于搜索的字符串测试数据自动生成方法。然而，对于动态数据结构 的测试数据自动生成，现有研究成果较少。 针对动态数据结构，k o r e l l 9 j 提出了一种基于数据流分析和回溯技术的测试数据 动态生成方法。但是，对于深层动态数据结构，形态生成需要大量回溯，这会严重 影响测试生成效率。此外，v i s v a i l a t h a i l 和g u p t a i l o j 提出了一种首先生成数据结构形 态，再生成其数据域值的两阶段法，该方法需要创建并且存储被测程序的抽象语法 树，这会占用很大一部分时间，测试生成效率较低。目前，动态数据结构，例如二 叉树和链表，已经广泛应用于程序设计中。为此，本文针对二叉树结构型数据，提 出了一种c o n c o l i c 测试数据自动生成方法。实验结果表明：该方法对于解决二叉树结 构类型测试数据生成问题是行之有效的。 北京化- t 大学硕士学位论文 1 2 国内外软件测试数据生成研究现状 软件测试意在增加对软件正确性的信心【1 1 1 ，即确信软件是按照它所要求的方式 执行的，而不会执行它不被希望的任何操作。无论在技术还是经济上，软件测试对 于确保软件产品具有较高的质量是必不可少的。目前，仍然有大量的测试工作需要 通过手工，或者使用一些非常繁琐的方法来完成i l 引。尽管在近三十年中，计算机行 业取得了很大的进展，但是在大多数的企业中，软件的开发和测试流程仍然不是非 常成熟，同时，随着软件产品的规模越来越大，其复杂性和严密性也大大增强。这 些都使得软件测试成为当今人们关注的焦点。 从测试技术的角度划分，可以把软件测试分成白盒测试和黑盒测试。白盒测试 也称为结构测试或者逻辑驱动测试，其应用依赖于对软件系统中程序内部工作原理 与处理过程的知晓。它通过对程序内部逻辑结构的分析来检查软件整体的架构设计 是否满足要求，并探测软件内部的实现细节是否合理正确，以发现软件系统中可能 存在的问题。白盒测试技术所采用的较为成熟的方法有控制流图法、数据流图法、 数据定义使用法等。 黑盒测试也称为功能测试。它把被测软件看作一个黑盒子，不需要考虑程序内 部的逻辑结构与实现细节，其应用依赖于对软件产品功能需求的知晓。黑盒测试通 过对软件产品外部功能的测试来检查软件系统是否符合功能需求，以发现软件产品 中可能出现的缺陷。黑盒测试技术所采用的大多数方法都借鉴或者参考了其他学科 理论和工程实践的思想，例如决策表测试方法、正交表测试方法等。 软件测试的本质是针对要测试的目标确定一组测试数据，为此，测试数据在软 件测试过程中起到的作用是非常重要的。测试数据质量的优劣在很大程度上决定了 测试工作效率的高低，恰当的测试数据不仅能够定位软件系统中的错误，还能够有 助于减少与测试工作相关的所需成本。 软件测试自动化，是一项使测试人员减轻甚至摆脱手工测试的技术，其利用自 动化测试工具代替手工测试。软件测试自动化一方面能够有效的减少测试实施过程 中的成本花费，另一方面能够在限定的时间内完成更多的测试任务，在很大程度上 提高了测试的效率。此外，它还可以有效的规避手工测试过程中人为造成的错误。 因此，为了使软件测试更加有效且更加经济，研发用于软件测试自动化的方法和工 具对于软件行业具有很强的诱惑力和吸引力。因此，软件测试自动化已经成为当今 软件测试研究领域中的热点技术问题。 对于测试人员来说，手工生成用于执行测试的输入数据是相当冗长乏味的，并 且是易于出错的。因此，测试数据的自动生成就成为了自动化测试中的研究热点。 目前，有众多学者投身于测试数据自动生成的研究中，而且已经研究出许多可行并 2 第一章绪论 有效的测试数据生成方法，应用于实践中。 1 3 本文的主要工作及创新点 本课题针对动态数据结构，以二叉树结构为例，探讨了一种新的面向路径的二 叉树结构型测试数据的自动生成方法。该方法将遗传算法和约束求解技术结合起 来，分别用于二叉树结构的形态生成和其数据域的数值生成。 针对以二叉树结构作为输入的被测程序，自动生成满足目标路径要求的测试数 据，主要工作及创新点如下： ( 1 ) 本文提出了一种c o n c o l i c 方法，用于生成以二叉树结构作为输入的给出程序 路径的测试数据。 ( 2 ) 本文提出了一种对于二叉树结构形态的染色体表示法，并且利用搜索算法实 现了二叉树结构的形态生成，该形态依赖于给定路径上所涉及的指针型约束。 ( 3 ) 本文通过对c 语言实现的大量二叉树操作程序的实验，证实了测试生成方法 的有效性。 ( 4 ) 本文通过实验，还证实了指针约束的数量是影响测试数据生成效率的关键因 素。 1 4 本文的组织结构 本文的组织结构如下： 第二章概述了测试数据自动生成方法的研究现状，分别介绍了不同类型的测试 数据生成方法，包括数值型测试数据、字符串型测试数据，以及动态数据结构型测 试数据，还介绍了基于不同启发式搜索算法的测试数据生成方法，包括遗传算法、 蚁群算法、模拟退火算法、以及禁忌搜索算法。 第三章研究了一种新的面向路径的针对二叉树结构型测试数据的自动生成方 法，对方法中的各个步骤进行了详细的描述。 第四章对本课题所研究的方法进行了实验，实验表明，本方法可以高效的生成 满足目标路径的测试数据。 第五章对本文工作进行了总结，提出了有待改进之处，给出了下一步工作的设 想。 北京化工大学硕士学位论文 第二章软件测试数据生成方法概述 第二章软件测试数据生成方法概述 k o r e l 【9 】对测试数据生成问题的定义是：给定一个程序元素( 比如一个修改的语 句) ，找到一个程序的输入，使它能够执行这个程序元素。形式化描述为：给定一个 程序p 和p 中的一条( 非确实) 路径u ，设p 的输入空间为s ，产生输入x s ，使p 以x 为输入运行时，所经过的路径为u 。具体而言，面向路径的测试数据自动生成是 指对于指定路径上不满足要求的分支谓词，通过逐渐调整程序输入，直到找到输入 并使程序沿指定路径执行为止。 2 1 不同类型的测试数据生成方法概述 目前，测试数据自动生成方法的研究涉及了数值、字符串和动态数据结构等类 型的测试数据。针对数值类型测试数据的生成方法，已经得到了比较深入的研究， 常用的方法有随机、基于符号执行和基于搜索的测试数据生成等。但是对于使用相 当普遍的字符串和动态数据结构类型的测试数据，其生成方法的研究相对于数值类 型的测试数据还较为有限，还需要进一步探索和研究。 2 1 1 数值型测试数据生成方法 针对数值型的输入参数，传统的测试数据生成方法是基于符号执行的方法【2 i 3 。 符号执行是基于代数运算的一种结构测试方法，是一种静态方法。静态法不需要运 行被测程序，而是对程序进行静态分析和转换得到相应的约束系统，求解约束系统 即可得到测试数据。符号执行以符号计算代替实际执行的数值计算，其允许程序的 输入不仅可以是具体的数值，也可以是符号值、符号表达式等。这样，在执行程序 过程中以符号的计算代替了数值的技术，所得到的结果自然是符号公式或是符号谓 词。对于面试路径的测试数据生成问题，符号执行会产生若干代数表达式，该表达 式中的变量均为代表程序输入变量的符号值，每一个代数表达式对应着一个路径约 束。生成的所有代数表达式组成了一个目标路径的分支谓词系统，它本质上是对于 程序输入变量的约束条件。通常，该分支谓词系统由若干等式以及不等式构成，对 其进行求解，以生成满足路径要求的测试输入数据。如果无解，则表明被选目标路 径为不可行路径。一般情况下，符号执行需要将复杂的代数操作简化为约束，以判 定路径是否可行。符号执行的优势在于一次符号测试的结果代表了一类普通测试的 运行结果，测试成本较低。但是，当遇到多级的指针处理、深层次的函数嵌套以及 复杂的循环结构等情况下，符号执行的实现就变得相当困难了，上述问题对于它的 北京化工大学硕士学位论文 应用与实践产生着较为严重的影响。 区间算术法是另一种静态的测试数据生成方法。区间算术是求解算术约束集的 一个方法【l4 1 。文献 1 5 提出了一种基于正则约束式的、能够求解复杂算术约束集的区 间计算方法，并应用于测试数据生成中。该方法先创性的将正则约束表达式加入到 测试数据生成中，其优势表现在以下两个方面。一方面表现于该方法在初始化过程 中，不需要对被测程序反复执行多次扫描，而只是执行一次正向扫描即可，在很大 程度上减少了传统方法用于扫描被测程序所花费的时间代价。另一方面表现于该方 法在测试数据生成过程中避免了很多重复性的计算，在一定程度上提高了测试数据 生成的效率。但是，该方法还存在一定的缺陷，即它仅仅适用于整数类型的测试数 据。而对于其他类型的测试数据，例如浮点类型的测试数据，如果想要应用该方法 生成这种类型的测试数据，则需要为该方法加入某种具有限制性的策略。例如，可 以对区间的最小范围加以限制，也可以加入过滤操作，其过滤的对象指的是包含若 干常量的约束表达式。这些常量可能在初始时就为常量，也可能在约束求解过程中 转化为常量。上述所列举的辅助策略有助于在测试输入数据类型比较复杂的情况 下，提高其测试数据的生成效率。 动态的测试数据自动生成方法基于被测程序的实际运行。随机法是动态法中的 一种，它在程序的输入空间中不断地随机选取输入数据来运行被测程序，试图找到 满足需求的测试数据。该方法容易实现且对简单程序具有一定的效果，但对于实际 的应用程序很难以合理的成本生成有效的测试数据。因此，随机法主要用来作为其 他方法的比较基准i l 引。 随机法之外的动态法则需要利用程序运行过程中收集的信息来判断当前的输入 数据在多大程度上能够满足特定的测试需求，并逐步调整当前的输入数据，试图找 到满足测试需求的测试数据。g a l l a 曲e r 和n a r a s i “山a n l 3 j ，以及r o g e r 和k o r e l i l 7 j 将测 试数据生成问题阐述为函数最小化问题。他们把给定路径上的每一个分支谓词视为 一个函数，对于选定路径上不满足要求的分支谓词，利用分支函数极小化，确定新 的输入值，直到找到输入数据。该方法每次只能考虑一个输入变量和一个分支谓 词，当该函数的值为最小时，则生成了所想要的测试数据。当给定路径上的某一分 支谓词没有生成所想要的结果时，输入值朝着使相应谓词函数的最小化方向改变。 这个过程被反复执行，直到目标路径上的所有分支谓词得到所需要的结果。 o f 胁和p a j l 【6 】提出了一种被称为动态域约减的测试生成技术。它结合许多的技 术，包括符号执行、基于约束的测试和基于执行的测试数据生成。一般情况下，基 于执行的方法为每一个输入变量赋予一个初始值，而动态域约减( d d r ) 则在初始时 给定一组值，即域，当选定路径上的分支被覆盖时，约减变量域，使对于变量域中 的任意变量值，谓词都为真。当d d r 完成时，输入变量域所包括的测试数据便是能 够使目标路径被执行的测试输入。如果路径不可行，或者给定的初始域不包含能够 6 第二章软件测试数据生成方法概述 遍历目标路径的测试数据，则当d d r 完成时，变量域将为空。虽然动态域约减技术 不能够应用于指针型变量，但相对于无法利用程序运行信息的静态测试数据生成技 术，该技术的动态特性能够更有效和更准确的处理数组和循环问题。 g u p t a 【7 ，1 8 】等人提出了另一个基于程序执行的方法，该方法使用数值分析技术来 搜索能够遍历目标路径的输入数据。如果当前输入数据不能执行给定的路径，则提 供数值来调整输入变量的值。这个技术不像使用函数最小化算法的方法，它一次考 虑所有的分支谓词和所有的输入变量。该方法通过实验证明所需的执行程序的数量 不依赖于路径长度，但是所要解决的线性约束系统的大小可能会随着给定路径上分 支谓词数量的增加而增加。 2 1 2 字符串型测试数据生成方法 目前大多数软件测试工具及软件测试数据生成的研究报告，更多涉及的是上述 数值型软件测试数据的产生，因而，只适应于一类纯数值计算的软件测试。但在实 际应用中，程序中字符串谓词的使用相当普遍，这在一定程度上限制了软件测试技 术的应用。目前针对字符串类型的输入数据，一些学者已经提出了一些有效的测试 生成方法。 文献 1 9 】针对字符串类型的测试数据，提出了一种基于谓词切片技术的测试数据； 生成方法。在该文献中对字符串之间的距离和程序变量的定义使用控制表达式进行 了定义，并且设计了一种动态算法，用于生成目标路径上指定字符串谓词的谓词切 片。 。 该算法首先创建被测程序的定义使用控制表达式，之后根据所创建的定义使 用控制表达式和所采用的切片准则，获取目标路径中与指定字符串谓词相关的程序 语句，以产生仅包含输入参数的字符串谓词切片。以随机的输入数据执行被测程 序，当执行到所生成的谓词切片时，记录下谓词中字符串变量的值；之后根据所得 到的当前值，对其中的每一个字符构造线性分支函数，并对该分支函数进行极小 化。通过上述方法就能够动态生成指定字符串谓词边界的o n o f f 测试点，最后生 成满足要求的字符串类型的测试输入数据。 文献 2 0 】以字符串类型的测试数据为例，利用遗传算法，提出了一种针对非数值 类型输入数据的测试生成方法。该方法将程序路径分为两种类型，划分的依据为程 序路中所涉及的分支谓词中包含的字符串变量的谓词约束形式。一种是以字符串变 量之间大于、大于等于、小于以及小于等于的比较形式存在的谓词约束，将其称为 第一类程序路径；另一种是以字符串变量之间等于和不等于的比较形式存在的谓词 约束，将其称为第二类程序路径。在程序路径分类的基础上，该方法定义了两种不 同类型程序路径相应的适应度函数，即路径适应度函数和字符适应度函数。在测试 7 北京化工大学硕士学位论文 数据生成过程中，该方法根据被测程序中被选目标路径的路径分支谓词特征，来确 定其所属的程序路径的种类，并计算其适应度函数值，来进一步指导字符串类型输 入数据的测试生成。该方法在应用遗传算法时，其染色体采用二进制编码策略。在 整个编码过程中需要进行两次转化操作。第一次转化操作是把字符串中的所有字符 转化为其相应的a s c i i 码；第二次转化操作是将各个字符对应的a s c i i 码转化为其相 应的二进制数值。最后，把各个字符经过两次转化过程后所得到的对应的二进制数 值连接起来，这样就构造了一个能够应用于遗传算法的染色体位串，即一个染色体 位串对应着一个字符串，一个基因对应着一个字符。 文献 8 】提出了一种面向路径的基于搜索算法的字符串类型输入数据的测试生成 方法。该文献中定义了一个从字符串集到非负整数集的单射函数，使得两个字符串 之间的距离唯一地确定了一个非负整数，以更加精确的描述字符串之间的距离。该 方法在定义字符串之间距离的基础上，利用程序插装技术记录下被测程序实际运行 时的运行信息，该信息包括对于当前输入参数所执行的路径以及分支谓词中字符串 变量的当前值。若某一字符串变量不满足目标路径中所涉及的分支谓词，则执行转 换操作，即把这个字符串变量转换为数值量，同时利用