（计算机系统结构专业论文）程序中不可达路径的识别及其在结构测试中的应用.pdf

中国科学院硕士学位论文一程序中币町达路径的识别及其在结构测试中的应用 摘要 结构测试有利于评价软件测试的充分性然而，测试的不充分是很常见的，必须选 择更多的测试用例去改善测试。每个新选择的测试用例需要执行特定的路径。首先面临 的问题就是如何确定一条可达的路径，即：在某一输入下路径是可执行的。在结构测试 领域中，不可达路径分析越束越突出地显示出重要的意义。尽早的发现路径测试中的不 可达路径，可以有效的减少测试过程中所耗费的人力物力。而目前现有的不可达路径识 别方法存在着许多弊端。本文首先分别综述了结构测试的方法及已有不可达路径的识别 方法，并分析了已有不可达路径识别方法中存在的不足本文给出了一个基于程序控制 流程图的识别不可达路径的方法，并将识别到的不可达路径信息有效的应用于结构测试 中，它能够帮助结构测试中的路径测试和数据流坝9 试提高准确性本文的主要贡献如下： 1 给出了一种程序中识别不可达路径的方法。本文给出了一种利用数据流分析信息 识别不可达路径的方法。该方法基于程序控制流程图，通过选取适当的条件谓词提高了 识别分支的覆盖率；并利用数据流分析技术对控制流程图中每个基本块的定值引用到达 信息进行分析，降低了相关性分析的复杂度。最后利用分支相关性的结果，制定了从路 径集合中识别不可达路径的规则。 2 、给出了基于分支相关影响的相对基本路径集的生成方法。该方法在路径集合生成 过程中考虑到分支相关的影响，生成的相对基本路径集合中路径全部可达，并且该集合 最大程度的提高了路径的覆盖率，为路径测试提供了便利。相对基本路径集是程序的部 分路径集合。它有以下特点：( 1 ) 每一条路径都是一条独立路径，即每一条路径中都包 含至少一条不包含在其它路径中的边。( 2 ) 程序中所有可达的边都放访问。该相对基本 路径集合比直接从基本路径集合中去除不可达路径方法所生成的路径集合，对于程序控 制流图中的可达边有了较高的覆盖率 3 、给出了在不可达路径影响下的数据流测试方法。本文扩展 5 】中的数据流分析 方法，将不可达路径的影响加入到数据流分析中精确数据流分析，从而能够提高软件故 障检测的准确率同时给出了伪元素的定义和伪交集，伪并集、伪差集的运算方法，该 方法能够有效的区分软件故障是否由不可达路径的影响而产生，并能有效的对故障进行 定位。这些信息为程序人员及测试人员改善程序性能提供了更多的依据 在开放源码编译i 器o r c ( o p e nr e s o u r c ec o m p i l e r ) 中实现了上述的方法，并以 s p e c 2 0 0 0 基准程序作为待测对象，取得了有效的实验结果 关键词：结构测试，不可达路径，分支相关、数据流分析、基本路径集 中国科学院硕士学位论文一程序中不可达路径的识剧及其在结构测试中的应用 i n f e a s i b l ep a t hi d e n t i f i c a t i o na n di t sa p p l i c a t i o ni ns t r u c t u r a lt e s t c h e nr u t ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yux i a o w e i s t m d u r a ll e , s ti sb e n e f i c i a lt oe v a l u a t ew h e t h e rt h et e s ti ss u f f i c i e n t h o w e v e r i ti s c o m m o nt h a tt e s t i n gi sn o ts u f f i c i e n t ，m o r et e s tc a s e ss h o u l db es e l e c t e dt oi m p r o v et h e s u f f i c i e n c yo f t h et e s t u s u a l l y , e a c hn e wt e s tc a s es e l e c t e dn e e dt ob ee x e c u t e do ns o m es p e c i a l p a t h s t h ef i r s tq u e s t i o ne n c o u n t e r e di sh o w t od e c i d ei ft h ep a t hi sf e a s i b l e ，w h i c hm e a n st h a t t h ep a t hi sf e a s i b l eb ys o m ei n p u t i nt h ea r e ao fs t r u c t u r a lt e s t , i d e n t i f i c a t i o no fi n f e a s i b l ep a t h b e c o m e sm o r ea n dm o r ei m p o r t a n t t h ee a r l i e rt h ei n f e a s i b l ep a t hi nt h ep r o g r a mw a s i d e n t i f i e d , t h ef e w e rt h et i m es p e n t t h e r ee x i s ts o m em e t h o d so fi n f e a s i b l ep a t hi d e n t i f i c a t i o n ， w h i c hh a v et h e i ro w n d i s a d v a n t a g e s t h i sd i s s e r t a t i o ns u r v e y st h ep r i n c i p l ea n dt h em a n n e ro f s t r u c t u r a lt e s ta n ds h o w st h es i g n i f i c a n c eo fi n f e a s i b l ep a t ht ot h es t r u c t u r a lt e s t t h e na n a l y s i s t h er e a s o no fi n f e a s i b l ep a t hg e n e r a t i o n ，a n ds u r v e y st h er e c e n td e v e l o p m e n to fi d e n t i f i c a t i o n o fi n f e a s i b l ep a t h am e t h o do fi n f e a s i b l ep a t hi d e n t i f i c a t i o ni sp r o p o s e db a s e do nc o n t r o lf l o w g r a p h ( c f g ) ，a n dt h ei n f o r m a t i o no fi n f e a s i b l ep a t hw a sa p p l i e dt oo p t i m i z e ds t r u c t u r a lt e s t ， w h i c hc a ni m p r o v et h ea c c u r a c yo fp a t ht e s ta n dd a t a - f l o wt e s t t h em a j o rc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s 1 am e t h o do fi n f e a s i b l ep a t hi d e n t i f i c a t i o ni sp r o p o s e d t h i sm e t h o di sb a s e do n c o n t r o lf l o wg r a p h ( c f g ) w ec o m p u t et h ed e f i n e u s e dr e a c hi n f o r m a t i o no f e a c hb a s i cb l o c k b yd a t a - f l o wa n a l y s i s , t h o s ei n f o r m a t i o nc a l lb eu s e dt od e t e c tt h eb r a n c hc o r r e l a t i o n f i n a l l y , a r u l eo fi d e n t i f y i n gi n f e a s i b l ep a t hf r o mp a t hs e ti se s t a b l i s h e da c c o r d i n gt ot h er e s u l to fb r a n c h c o r r e l a t i o na n a l y s i s w ei m p r o v et h er a t eo fb r a n c h e sc o v e r e db ys e l e c t i n gp r o p e rc o n d i t i o n p r e d i c a t i o na n d d e c r e a s ec o m p l e x i t yo f b r a n c hc o r r e l a t i o nb yd a t a f l o wa n a l y s i s 2 a g e n e r a t i o nm e t h o do f r e l a t i v eb a s i ss e to f p a t hi sp r o p o s e db a s e do ne f f e c to f b r a n c h c o r r e l a t i o n i nt h em e t h o d , w eh a v ec o n s i d e r e dt h eb r a n c hc o r r e l a t i o ni nt h ep r o c e s so fp a t h g e n e r a t i o n , w h i c hi m p r o v et h er a t eo fp a t h sc o v e r e di nt h er e l a t i v eb a s i ss e to fp a t h ，w h i c h f a c i l i t a t ep a t h sl e s t r e l a t i v eb a s i ss e to fp a t hi sap a r to fp a t hs e ta n dh a ss u c ha t t r i b u t e sa s f o l i o , v ：( 1 ) e a c hp a t hi so n ei n d e p e n d e n tp a t ha n di n c l u d e so n ee d g ea tl e a s tw h i c hd o e sn o t e x i s ti na n yo t h e rp a t h s ( 2 ) a l lo fe d g e si nt h ep r o g r a mw i l lb ei n c l u d e d t h er e l a t i v eb a s i ss e t o fp a t hh a st h eh i g h e rr a t eo fe d g e sc o v e r e di nt h ec f gt h a nt h ep a t hs e tw h i c hh a sb e e n e x c l u d e di n f e a s 而l ep a t h sd i r e c t l y 中国科学院硕士学位论文一程序中不可达路径的识别及其在结构测试中的应用 3 am e t h o do fd a t a - f l o wt e s tb a s e do ni n f e a s i b l ep a t hi sp r o p o s e d w ee x t e n dt h e m e t h o dp r o p o s e di n 【5 】a n da d dt h ee f f e c to fi n f e a s i b l ep a t hi n t ot h em e t h o d ，s ow ec a ng e tt h e h i g h e rv e r a c i t yo ff a u l td e t e c t i o ni nt h es o f t w a r e a n dw ep r o p o s ean e ws e to fm a n n e ro fs e t c o m p u t i n gt oa d a p tt ot h ei n f e a s i b l ep a t he x i s t i n g , s ow ec a nj u d g ei ft h ef a u l ti nt h es o f t w a r ei s d u et oi n f e a s i b l ep a t ho rn o t , a n dl o c a t et h ef a u l te f f e o i v e l gw h i c hc a n p r o v i d em o r eu s e f u l i n f o r m a t i o nt op r o g r a m m e ra n dt e s t e rt oi m p r o v et h ep e r f o r m a n c eo fp r o g r a m n ep r o p o s e dm e t h o d sh a v eb e e ni m p l e m e n t e do no p e nr e s o u r c ec o m p i l e r ( 0 r e ) , e x p e f i m e n t a lr e s u l t sr e v e a lt h e i re f f i c i e n c y k e y w o r d s ：s t r u c t u r a lt e s t , i n f e a s m l ep a t h ，b r a n c hc o r r e l a t i o n ，d a t a f l o wa n a l y s i s , b a s i cp a t hs e t m 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，本论 文中不包含其它人已经发表或撰写过的研究成果。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 作者签名：你虫、 日期：2 咧蹈目f g 日 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部 门或机构送交本论文的复印件和电子文档，允许本论文被查阅和借 阅，可以将本论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 储签名：际氐导师繇锄吼2 卵印目舢 第一章引言 第一章引言 1 1 研究背景及意义 软件测试在软件开发中具有非常重要的作用软件测试的目的在于按照规定的步 骤，采用适当的方法，对软件进行严格的检查，以发现和改正软件的错误，使软件的质 量在测试过程中不断提高，逐渐达到规定的要求，能够交付使用。从如何标识测试用例 的角度，软件测试可分为功能测试、结构测试。其中结构测试又称为白盒测试，是基于 程序结构特征，以实现某种测试覆盖为目的一种测试方法。结构测试有利于评价测试的 充分性，决定测试是否可以结束。然而，测试的不充分是很常见的，必须选择更多的测 试用例去改善测试。这种情况下，测试准则决定新测试用例的选择。通常来说，每个新 选择的测试用例需要执行特定的路径。首先面i 临的问题就是如何确定一条可达的路径， 即：在某一输入下路径是可执行的。在结构测试领域，不可达路径分析越来越突出地显 示出重要的意义。 结构测试中的静态分析方法是很重要的，是大多数软件工程工具的一个重要部分。 因为静态分析是在程序运行前进行的，它会有一些假定的条件。而一个最普通的假定就 是程序的路径是可行的。然而，确实存在着一些路径是不可行的，没有输入可以通过它。 因此，静态分1 斤可能会产生一些不确定的信息。不确定信息导致了软件工程实现中的一 些不理想结果。在路径测试中，选定的路径有可能是不可达的；数据流测试中，选定d u 对可能由于位于不可达路径上而成为不可测的。这将导致测试数据生成阶段大量人力， 财力的浪费。 不可达路径信息不仅可以优化一些基于数据流分析的工具，更有利于软件工程各领 域的实现，包括以下3 个方面： i 、路径测试直接使用。在路径测试中，选择待测路径的算法可以避免由分支相 关性造成的不可达路径，从而减少了测试用例生成的耗费。 2 、定值引用对测试中，可以从需求集中去掉那些存在于不可达路径上的定值 引用对。 3 、静态程序片的测试中，由于避免了对不可达路径的考虑，程序片只包含少量 语句，提高了识别语句潜在错误的准确性。 不可达路径的信息可以改善静态分析的准确性尽管还不可能确认所有的不可达路 径【1 】，却可以通过探测静态分支相关性( 分支冲突) 来确定一部分不可达路径。对于 某一条路径上的一个条件分支，如果它的结果可以由之前的语句或分支确定，则它具有 静态相关性 2 】实验表明，对于大型程序，在编译阶段可探测到约有9 到4 0 的条件 语句相关性因此有一定数量的不可达路径在程序运行前就可以探测到。 中国科学院硕士学位论文一程宁中不町达路径的识别及其在结构捌试中的应用 在早期的不可达路径的研究中，d h e d l y 在【3 】中，提出了一种对程序l c s a j ( 1 i n e a r c o d es e q u e n c ea n di u m p ) 线性程序序列的划分方法，从n a g 库中取出7 8 8 个程序来测试 ( n a g 库中的程序是用f o r t r a n 语言来写的，普遍认为有较高的质量) ，这些程序包含了 4 7 9 0 个l c s a j 平均每个程序有5 6 个l c s a j 其中有6 1 9 个不可达的路径。但是d h e d l y 认 为【4 1 中提到的f u n c t i o n a lp r o g r a m m i n g 编程方法是唯一的解决方法。但是不管用再好的编 程方式，不可达路径的存在是不可避免的。 由此可以看出不可达路径的识别不论是在理论上还是实践中部有着研究的重要性， 同时将不可达路径的信息运用在精确数据流分析及路径自动生成方面有着很重要的意 义。 1 2 本文的主要工作 本文给出了一种基于控制流程图的不可达路径识别方法，通过适当选取条件谓词提 高分支检测覆盖率，并利用各基本块的数据流信息来探测分支相关性，降低相关性分析 的复杂度。并将分支相关性转化为基本块之间的相关性问题进行讨论，将产生相关的基 本块信息运用到已生成的路径集合中，从而确定了集合中的不可达路径。另外，本文将 分支相关分析所得到的结果运用到基本路径生成过程中，得到了相对基本路径集合。该 相对基本路径集中的每一条路径都是一条独立路径，程序中所有可达的边都能被访问， 这样的路径集合对路径测试是有意义的。最后利用在路径生成过程中所判定的一些不可 达的边，将其运用于数据流测试中，精确了数据流分析，并根据数据流分析结果判定哪 些程序中的故障是由不可达路径的存在所引起。 一、不可达路径的识别方法 目前现有的不可达路径识别方法存在着许多弊端，基于此，本文给出了一种利用数 据流分析信息识别不可达路径的方法。该方法基于程序控制流程图，通过选取适当的条 件谓词提高了识别分支的覆盖率；并利用数据分析技术对控制流程图中每个基本块的定 值引用到达信息进行分析，降低了相关性分析的复杂度。利用分支相关性的结果，制定 了从路径集合中识别不可达路径的规则。在待测路径集合中识别出不可达路径，可以有 效的减少路径测试过程中所耗费的人力物力。 二、基于分支相关影响相对基本路径集合的生成方法 将分支相关信息应用于基本路径集合生成过程中，最大程度的覆盖了程序中可行的 路径。当得到了不可达路径信息时，在路径测试过程中仅仅将这些不可达路径去掉并不 是最终的目的因为这样会直接影响到路径集合的覆盖率在考虑到目前所存在的路径 集合生成方法中绝大部分是基于路径可达的假设之下，本文在路径生成过程中就考虑到 路径不可达的问题，尽可能多的覆盖到所有可达的边，提高了路径集合的覆盖率 在路径生成阶段，首先根据一次分支相关中各基本块在其中起到的作用不同，给基 本块进行分类对程序控制流图进行遍历以构造路径时，用一个临时路径( 是一条程序 的路径) 来记录已经遍历过哪些边，并且通过选边规则判断哪些边的加入不会引起路径 2 第一章引言 不可达。在不断的选边过程中对c f g 矩阵中各元素的值( 各个边的状态) 根据不同的条 件进行转换，以达到生成相对基本路径集的目的。相对基本路径集是程序的部分路径集 合。它有以下特点：( 1 ) 每一条路径都是一条独立路径，即每一条路径中都包含至少一 条不包含在其它路径中的边( 2 ) 程序中所有可达的边都被访问。该相对基本路径集合 比直接从基本路径集合中去除不可达路径方法所生成的路径集合，对于程序控制流图中 的边有了较高的覆盖率。 三、基于不可达路径影响的数据流测试方法 给出了不可达路径影响下的数据流测试方法。由于应用程序中部分软件故障与变量 在引用之前是否被定值或被定值的变量是否被引用有关，为检测程序中存在的这些故 障，需要对程序进行到达定值数据流分析和活跃变量数据流分析。本文扩展 5 中的 数据流分析方法，将不可达路径的影响加入到数据流分析中精确数据流分析，从而能够 提高软件故障检测的准确率。同时本文给出了伪元素的定义和伪交集，伪并集、伪差集 的运算方法，能够有效的区分软件故障是否由不可达路径产生，并能对故障有效的定位， 为程序人员及测试人员提供更多的信息改善程序性能。 1 3 论文的组织 论文按如下的方式来组织：第二章介绍了结构测试的概念及意义，并综述了结构测 试的基本方法。第三章综述了目前现有的不可达路径的识别方法，并加以比较分析其各 自的优劣势，从而指出本文立题的出发点。第四章详细介绍了基于程序控制流程图的不 可达路径的识别方法。第五章和第六章介绍了不可达路径于结构测试中的应用方法。第 五章详细介绍了不可达路径于路径生成过程中的应用。第六章介绍了不可达路径如何应 用于数据流分析以精确数据流测试，精确的检测软件中产生的故障。第七章对本文的工 作进行总结，提出了有待改进之处和今后的工作方向 3 第二章结构测试综述 第二章结构测试综述 软件测试在软件开发中具有非常重要的作用。软件测试的目的在于按照规定的步 骤，采用适当的方法，对软件进行严格的检查，以发现和改正软件的错误，使软件的质 量在测试过程中不断提高，逐渐达到规定的要求，能够交付使用。软件测试从如何选择 测试用例的角度上来看可以分为功能测试和结构测试，功能测试和结构测试在软件测试 中起到的作用不同。本章首先介绍结构测试的概念，并将结构测试与功能测试作比较， 说明结构测试在软件测试过程中的重要性，然后详细介绍了几种常见的结构测试方法。 2 1 结构测试的概念与意义 结构测试也称为自盒测试或逻辑驱动测试，按照程序内部的结构对程序进行测试， 通过测试来检查产品内部动作是否按照设计规格说明书的规定正常进行，检查程序中的 每条通路是否能按照预定要求正确工作结构测试将测试对象看成是一个打开的盒子， 测试人员依据程序内部逻辑结构相关信息，设计或选择测试用例，对程序的所有逻辑路 径进行测试，通过不同点检查程序的状态，确定实际的状态与预期的状态一致。 在软件测试中，与结构测试相对的是功能测试结构测试和功能测试是从如何选择 测试用例的角度上来划分的。功能测试是指按照程序的功能说明，设计测试用例进行测 试，借以发现程序的错误、验证程序是否符合预定的功能。 对于结构测试和功能测试这两种根本不同的测试用例标识方法，很自然会产生哪种 方法更好的问题对于这两种测试方法都有着很坚定的拥护者对于结构测试，r o b e r t p o s t o n 【6 】曾经这样写道：这种工具自2 0 世纪7 0 年代以来一直在浪费测试人员的时间 它不支持好的软件测试实践，应该从测试人员的工具包中剔除。e d w a r dm i l l e r 7 在为结 构性测辩护时写道：如果达到8 5 或更好的水平，分支覆盖率标识出的缺陷，一般是靠 直觉( 功能性) 测试找出的缺陷两倍这两种方法的目标都是标识测试用例功能 性测试只利用规格说明标识测试用例，而结构性测试使用程序源代码( 实现) 作为测试 用例标识的基础。对于两种方法的单独使用都是不充分的考虑程序行为( 如图2 1 ) ： 如果所有已描述行为都没有被实现，则结构性测试永远也不会认识到这一点反过来， 如果程序实现了没有被描述的行为，功能性测试用例永远也不会揭示这一点( 病毒是 这种未描述行为的很好的例子) 很容易得出的答案是，两种方法都需要测试工艺师 的答案是，明智的组合会带来功能性测试的置信，以及结构性测试的度量功能性测试 常常会有冗余和漏洞两方面的问题如果功能性测试结合结构性测试覆盖率指标执行， 则这两个问题都会被解决 5 中国科学院硕士学位论文一程序中f 可达路径的识别及其在结构删试中的应用 图2 1 测试用例来源 2 2 结构测试方法概述 结构测试可以在静态分析过程中进行，也可以在动态阶段进行，所以分为静态方法 和动态方法。静态的分析方法主要有：程序控制流分析、数据流分析；动态阶段的实施 方法主要有：逻辑覆盖、域测试、符号测试、路径测试、程序插装及程序变异等。其中 多数方法比较成熟，也有较高的实用价值 2 2 1 程序结构分析 程序的结构形式是结构测试的主要依据。本节将从控制流分析和数据流分析的不同 方面讨论几种机械性的方法分析程序结构。自然，我们的目的总是要找到程序中隐藏的 各种错误 2 2 1 1 控制流分析 由于非结构化程序会给测试、排错和程序的维护带来许多不必要的困难，人们有理 由要求写出的程序是结构良好的。7 0 年代以来，结构化程序的概念逐渐为人们普遍接受 体现这一要求对于若干语言，如p a s c a l 、c 等并不困难，因为它们都具有反映基本控制 结构的相应控制语句。但对于早期开发的语言来说，要作到这一点，程序编写人员需要 特别注意，不应忽视程序结构化的要求。使用汇编语言编写程序，要注意这个问题的道 理就更为明显了。正是由于这个原因，系统地检查程序的控制结构成为十分有意义的工 作 一、控制流图 程序流程图( f l o w - c h a r t ) 又称框图 8 】，是人们最熟悉，也是最容易接受的一种程 序控制结构的图形表示在这种图上的框内常常标明了处理要求或条件，这些在做路径 分析时是不重要的为了更加突出控制流的结构，需要对程序流程图做些简化在图2 2 中给出了简化的例子其中( a ) 是一个含有两出口判断和循环的程序流程图，我们把它 6 第二章结构测试综述 简化成( b ) 的形式，称这种简化了的流程图为控制流图( c o n t r o l f l o wg r a p h ) 在控制 流图中只有两种图形符号，它们是： 节点：以标有编号的圆圈表示。它代表了程序流程图中矩形框所表示的处理、菱 形表示的两至多出口判断以及两至多条流线相交的汇合点。 控制流线或弧：以箭头表示它与程序流程图中的流线是一致的，表明了控制的 顺序为讨论方便，控制流线通常标有名字，如图中所标的a 、b 、o 等。 为便于在机器上表示和处理控制流图，我们可以将它表示成矩阵的形式，称为控制 流图矩阵( c o n t r o l - - f l o wg r a p hm a t r i x ) 图2 3 表示了图2 2 的控制流图矩阵这个 矩阵有5 行5 列，是由该控制流图中含有5 个节点决定的矩阵中6 个元素入a 、b 、c 、 d 、e 和f 的位置决定于它们所联接节点的号码。例如，弧d 在矩阵中处于第3 行第4 列，那是因为它在控制流图中联接了节点3 至节点4 。这里必须注意方向。图中节点4 至节点3 是没有弧的，矩阵中第4 行第3 列也就没有元素。 。 t b ) 控制淹图 图2 2 程序流程图与控制流图 a cb d e f 图2 3 控制流图矩阵 二、程序结构的基本要求 我们对于程序结构提出以下4 点基本要求，这些要求是，写出的程序不应包含： a ) 转向并不存在的标号； 7 中国科学院硕士学位论文一程序中不可达路径的识别及其在结构测试中的应用 b ) 没有用的语句标号； c ) 从程序入口进入后无法达到的语句； d ) 不能达到停机语句的语句。 显然，提出这些要求足合理的。在编写程序时稍加注意，做到这几点也是很容易的。 这里我们更为关心的是如何进行检测，把以上4 种问题从程序中找出来。 三、结构分析 结构化程序在编写、理解和测试中的优越性是人所共知的。为了得到结构良好的程 序，就不能不对程序编写人员提出一些要求。d i j k s t r a 提出的几种结构化程序中若干逐 步细化( s t e p f i n e m e n t ) 的流程图构造形式正如使用语占的产生式规则，编译程序可 以对程序作语法分析，我们可以利用流程图语法的产生式规则进行流程图的自底向上分 忻。用这种方法能够验证上述结构规则在程序编写中是否得到遵循，如果确已遵循，便 可得到有关其构成成分的语法树。此外，还能揭示控制结构的欠缺。这在需作进一步分 析时是很有用的。 2 2 1 2 数据流分析 数据流分析【9 】最初是随着编译系统要生成有效的目标码而出现的，这类方法主要 用于代码优化。近年来数据流分析方法在软件测试中也得到成功的运用，用以查找如引 用未定值变量等程序错误也可用来交接对以前未被使用的变量再次赋值等数据流异常 的情况。找出这些错误足很重要的，因为这常常是常见程序错误的表现形式，如错拼名 字、名字混淆或是丢失了语句。数据流分析的主要目的是识别与变量的赋值和引用有关 的通路，在此基础上设立测试准则基本的测试准则有：所有定值覆盖、所有引用覆盖、 所有定值引用通路覆盖。这些准则关注的是最简单的数据流通路，即，从某个变量的 定值处开始，到同一变量的引用处终止的通路 一、数据流问题 如果程序中某一语句执行时能改变程序变量v 的值，则称v 是被该语句定值的。如 果一语句的执行引用了内存中变量v 的值，则说该语句引用变量v 例如，语句 x ：y + z 定值了x ，引用了y 和z ，而语句 i fy zt h e ng o t oe x i t 只引用了y 和z 输入语句 r e a dx 定值了x 输出语句 w r i t ex 引用了x 。执行某个语句也可能使变量失去定值，成为无意义的。例如，在f o r t r a n 中，循环语句d o 的控制变量在经循环的正常出口离开循环时，就变成无意义的 图2 4 给出了一个程序的控制流图，同时指明了每一语句定值和引用的变量同时 8 第二章结构测试综述 可以看出，第一个语句定值了3 个变量x ，y 和z 。这表明它们的值是程序外赋给的例 如，该程序是以此三变量为输入参数的过程或子程序。同样，出口语句引用：表明，z 的值被送给外部环境 图2 4 控制流图及其定值及引用的变量 该程序中含有两个错误： 语句2 使用了变量霄，而在此之前并未对其定值。 语句5 、6 使用变量v ，这在第一次执行循环时也未对其定值过。 此外，该程序还包含两个异常： 语句6 对z 的定值从未使用过。 语句8 对w 的定值也从未使用过。 当然，程序中包含有些异常，如、也还不会引起执行的错误。不过这一情况表 明，也许程序中含有错误；也许可以把程序写得更容易理解，从而能够简化验证工作， 以及随后的维护工作( 去掉那些多余的语句一般会缩短执行时间，不过在此我们并不关 心这些) 二、已有的数据流分析方法 数据流分析技术的系统研究开始于7 0 年代，是由a l l e n 和c o c k e 开创的数据流分析 是确定变量定值与引用关系的工具【1 0 l 。数据流分析技术在程序切片1 1 、程序的可测性分 析【1 2 1 等方面得到了广泛的应用 【9 】( c h a p t e r l o ) 对数据流分析方法进行了详细说明数据流分析必须考虑所有的 控制路径： 9 中国科学院硕士学位论文一程序中不可达路径的识别及其在结构删试中的应用 1 如果控制路径从语法上就是一日了然的话，可以使用语法制导的分析技术来建 立和求解数据流方程。 2 如果程序中包含g o t o 语句，或者b r e a k 和c o n t i n u e 语句，就需要考虑控制通路 迭代分析技术适用于随意流图( a r b i t r a t yf l o wg r a p h ) 。 3 如果b r e a k - c o n t i n u e 语句是可规约的，则可以使用基于问隔的分析技术 ( i n t e r v a l b a s e dm e t h o d s ) 对这样的结构进行系统处理。问隔分忻技术在对通用 流图分析时保留了语法制导方法的优点，其代价则是非常高的概念上的复杂性。 常见的数据流分析方法有很多，如流敏感流不敏感的分析方法，上下文敏感上下 文不敏感的分析方法1 1 3 l 等静态分析方法，【1 4 】等提出了动态数据流分折方法。这些分析 方法从不同的角度反映了程序的数据流状态。对别名( a l i a s ) 和过程间分析的技术在 7 0 年代末已经有很有效的方法提出了。过程间数据流分析的基本思想，足确定每个过程 如何影响其它过程的g e n 、k i l l 、u s e 、或者d e f 等信息，再对每个过程独立计算数掘流信 息。由于典型的过程间数掘流分忻时间与被分析流图的大小成正比，g o o d w i n 1 5 描述 了一种压缩表示，应用于程序的过程内和过程间控制流，来有效的分析程序中寄存器的 定值和使用。这种压缩表示使得一个优化器能够分忻包含了百万条指令和数百个基本块 的程序。以上这些分析方法从不同的角度反映了程序的数据流状态，但是将这些方法由 于没有考虑程序中仍有不可达路径的影响，应用在软件测试中分忻结果并不精确。 2 2 2 逻辑覆盖法 逻辑覆盖1 1 6 是通过对程序逻辑结构的遍历实现程序的覆盖。依据覆盖源程序语句 的详尽程度分为以下几类：语句覆盖s c ( s t a t e m e n tc o v e r a ；e ) 、判定覆盖d c ( d e c i s i o nc o v e r a g e ) 、条件覆盖c c ( c o n d i t i o nc o v e r a g e ) 、条件判定组合覆盖c d c ( c o n d i t i o n d e c i s i o nc o v e r a g e ) 、多条件覆盖m c c ( m u l t i p l ec o n d i t i o nc o v e r a g e ) 、修改条件判定覆盖m c d c ( m u l t i p l ec o n d i t i o nd e c i s i o nc o v e r a g e ) 1 ) 语句覆盖：选择足够多的测试数据，使被测程序中每条语句至少执行一次。 缺点：对程序执行逻辑的覆盖很低。 2 ) 判定覆盖：设计足够多的测试用例，使得程序中的每一个判定至少获得一次真 值和、假，值，或者使得程序中的每一个取真分支或取假分支至少经历一次，因 此又称分支覆盖，可以满足语句覆盖。 缺点：主要对整个表达式最终取值进行度量，忽略了表达式内部取值 3 ) 条件覆盖：设计足够多的测试用例，使得每一判定语句中每个逻辑条件的可能值 至少满足一次，不能够满足判定覆盖 4 ) 条件判定组合覆盖：设计足够多的测试用例，使得判定中的每个条件的所有可能 ( 真假) 至少出现一次，并且每个判定本身的判定结果也至少出现一次。 缺点；没有考虑单个判定对整体结果的影响，无法发现逻辑错误 1 0 第二章结构测试综述 5 ) 多条件覆盖：也称条件组合覆盖，设计足够多的测试用例，使得每个判定中条件 的各种可能组合都至少出现一次( 以数轴形式划分区域，提取交集，建立最少的 测试用例) 满足条件覆盖一定满足判定覆盖、条件覆盖、条件判定组合覆盖。 缺点：判定语句较多时，条件组合值比较多。 6 ) 修正条件判定覆盖：每一个程序模块的入口和出口点都要考虑至少要被调用一次， 每个程序的判定到所有可能的结果值要至少转换一次。程序的判定被分解为通过 逻辑操作符( a n d ，o r ) 连接的b o o l 条件，每个条件对于判定的结果值是独立的。 2 2 3 基本路径覆盖法 在程序控制流图的基础上，通过分析程序控制流图的环路复杂性，导出基本可执行 路径的集合，然后据此设计测试用例，设计出的测试用例要保证在测试中程序的每一条 可执行语句至少执行一次。 按照1 1 7 l 中的定义，程序的路径是程序中顺序执行的一个语句序列。从c f g 的角度 来看，程序路径是由控制流图中的一系列节点组成，相邻的两个节点表示控制流图中的 一条边。丽数学上的“基”的概念对于结构性测试足具有现实意义的。特定的集合都可 以有一个基，如果有，则基对于整个集合来说有着非常重要的意义。根据b b c i t e r l l 8 l 的讨论，在程序中存在分支语句、循环语句的情况下，程序中的路径的数目会变得很大， 因此，对于复杂的程序，对程序中的所有路径进行测试需要巨大的资源。为在有限的测 试资源下进行路径测试，【1 8 】中提到了基本路径测试的概念。按照【1 8 1 中关于基本路径 集的定义，当对程序中的某一个基本路径集进行测试之后，程序中的所有的语句、所有 的程序分支都被覆盖。因此，基于基本路径集的覆盖测试可以有效的提高测试的效果。 基本路径集、基本路径【1 8 1 1 1 9 珈j 的概念：基本路径集是程序的部分路径的集合。在 给定的一个基本路径集中的路径具有下列特点： ( 1 ) 每一条路径都是一条独立路径，即每一条路径中都包含至少一条不包含在其它 路径中的边 ( 2 ) 程序中所有的边都被该基本路径集中的路径访问 ( 3 ) 程序中的所有的、不属于某一个基本路径集的路径都可以由这个基本路径集中 的路径经过线性运算得到。 独立路径1 2 1 1 指的是程序中的一条路径，在这条路径中，至少包含一条在其它独立路 径中从未有过的边的路径。 一、基本路径集的生成方法 目前已有的基本路径生成方法有代表性的有以下几种； d c r b i n t 等【2 2 l 提出了采用遗传算法进行路径生成的方法。该方法需要对程序进 行如下的处理：首先消去程序中的循环，然后对程序中多出度的节点进行二叉化处理， 即用一组含有两个分支的节点表示一个多出度节点，在对程序进行上述处理的基础上， 可以确定一个表示程序路径的种群，用遗传算子( 变异，交叉) 对这一种群进行处理得 1 1 中国科学院硕士学位论文一程序中不可达路径的识别及其在结构测试中的应用 到新的路径集。这种方法进行路径生成的过程中，由于消去了程序中的循环，使得生成 的程序路径不能覆盖程序中的所有的边。 a n t o n i ab e r t o l i n o 掣2 3 1 提出了利用简化了的控制流图进行程序路径的确定。该方法 从程序的控制流图出发，首先建立程序的d t ( d o m i n a t et r e e ) 和i t ( i m p l i c a t i o nt r e e ) ( d t 或i t 中的一条程序路径表示了程序一组程序路径) ，继而通过构造两个相邻控制节点 之问的子图的方法来确定两个控制节点之日j 的所有的路径从而进行测试路径的生成。采 用这种方法进行测试路径的生成需要在控制流图的的基础上构建d t 、i t 及控制流图的 子图，虽然该方法生成的路径集实现了对程序中所有的语句、所有分支都进行了覆盖， 但不能保证生成的路径集是基本路径集； j o s e p hp o o l e1 2 4 1 提出了采用图的深度优先搜索的方法建立基本路径集的方法。该方 法通过递归的调用搜索过程实现路径生成。 【2 5 1 提出了基于图的深度优先搜索的基本路径集的生成方法。算法中采用的生成子 路径的方法可以有效的减少路径生成过程中的搜索过程，提高路径生成的效率。 二、程序环路复杂性 程序的环路复杂性即m c c a b e 2 6 复杂性度量，简单的定义为控制流图的区域数。从 程序的环路复杂性可导出程序基本路径集合中的独立路径条数，这是确保程序中每个可 执行语句至少执行一次所必须的测试用例数目的上界。独立路径：包括一组以前没有处 理的语句或条件的一条路径。通常环路复杂性可用以下三种方法求得： 1 、将环路复杂性定义为控制流图中的区域数 2 、设e 为控制流图的边数，n 为图的结点数，则定义环路复杂性为v ( g ) = e n + 2 3 、若设p 为控制流图中的判定结点数，则有v ( g ) = p + 1 三、基本路径测试步骤 1 、以详细设计或源代码为基础，导出程序的控制流图。 2 、计算得到控制流图g 的环路复杂性v ( g ) 。 3 、确定线性无关的路径的基本集。 4 、生成测试用例，确保基本路径集中每条路径的执行。 2 2 4 其它的结构测试方法 一、域测试 域测试 2