白盒测试方法.

1、4. 白盒测试方法 l程序结构分析l逻辑覆盖l路径分析l程序插装14.1程序结构分析程序的结构形式是白盒测试的主要依据。程序的结构形式是白盒测试的主要依据。l控制流分析控制流分析l数据流分析数据流分析l信息流分析信息流分析程序结构分析的目的程序结构分析的目的就是要找到就是要找到程序中隐藏的各种错误。程序中隐藏的各种错误。 24.1程序结构分析 一、控制流分析一、控制流分析l非结构化程序会给测试、排错和程序的维护带来许多不必要的困难.l70年代以来，结构化程序的概念逐渐为人们普遍接受。体现这一要求对于若干新的语言，如Pascal、C等并不困难，因为它们都具有反映基本控制结构的相应控制语句。l要求

2、写出的程序是结构良好的。3 一、控制流分析1.1.控制流图控制流图程序流程图程序流程图(flowchart)：是人们一种程序控制结构的图形表示方式。在程序流程图上的框内常常标明了处理要求或条件，这些在做路径分析时是不重要的。4一、控制流分析1.1.控制流图控制流图为了更加突出控制流的结构，需要对程序流程图做些简化，我们称这种简化了的流程图为控制流图。5一、控制流分析1.1.控制流图控制流图控制流图中的符号：控制流图中的符号：节点：节点：以标有编号的圆圈表示。代表流程图中矩形表示的处理、菱形表示的判断以及两至多条控制流线的交汇点。控制流线：控制流线：以带箭头的直线或弧线表示。它与流程图中的流线是

3、一致的，标明了控制的顺序。控制流线通常标有名字，如图中所标的a、b、c等。6一、控制流分析1.1.控制流图控制流图控制流图矩阵控制流图矩阵: :为便于在机器上表示和处理控制流图，我们可以把控制流图表示成矩阵的形式，称为控制流图矩阵。如图表示的控制流图5x5矩阵,是由该控制流图中含有5个节点决定的。7一、控制流分析2对程序结构的基本要求对程序结构的基本要求对于程序结构提出以下4点基本要求，这些要求是，写出的程序不应包含：转向并不存在的标号； 没有用的语句标号； 从程序入口进入后无法达到的语句； 不能达到停机语句的语句。 8一、控制流分析2程序结构的基本要求程序结构的基本要求如何对程序进行检测，把

4、以上如何对程序进行检测，把以上4种问题从程种问题从程序中找出来序中找出来? 转向并不存在的标号； 没有用的语句标号；这两种情况是很容易发现的，在此我们不再讨论。9一、控制流分析2程序结构的基本要求程序结构的基本要求从程序入口进入后无法达到的语句；这种情况可以利用检验不可达代码算法加以检验，凡未作标记的节点均为不可达代码。 。10一、控制流分析2程序结构的基本要求程序结构的基本要求 不能达到停机语句的语句这种情况也可用相似的方法找出，在上述算法中，只需把“入口节点”改为“出口节点，“后继”改为“前趋”即可。 11一、控制流分析3 3程序结构分析程序结构分析 结构化流程图 ：12一、控制流分析3

5、3程序结构分析程序结构分析 结构化流程图 ：13一、控制流分析3 3程序结构分析程序结构分析 结构化流程图 ：14一、控制流分析3 3程序结构分析程序结构分析 l通过利用流程图语法的产生式规则进行流程图的自底向上分析，能够验证上述结构规则在程序编写中是否得到遵循，如果确已遵循，便可得到有关其构成成分的语法树。l此外，利用流程图语法还能揭示控制结构的缺限。15一、控制流分析3 3程序结构分析程序结构分析 l我们给出的结构程序规则是很有限的，通常还可作进一步扩充。例如，可以允许使用具有多出口的循环构造，提高程序的清晰性，也不会使程序正确性证明的工作更加困难。l尽管允许这样的结构会使检查流程图结构是

6、否良好更为复杂，但作其它的流程分析还是可行的。16二、数据流分析什么是数据流分析？什么是数据流分析？l数据流分析最初是随着编译系统要生成有效的目标码而出现的，这类方法主要用于代码优化。l数据流分析方法在确认系统中也得到成功的运用，用以查找如引用未定义变量等程序错误，以及用来查找对未曾使用的变量再次赋值等数据流异常的情况。17二、数据流分析数据流分析重要性：数据流分析重要性：在程序测试中，找出这些错误是很重要的。因为这常常以一些常见程序错误为表现形式，如错拼名字、名字混淆或是丢失了语句。18二、数据流分析（1 1）数据流问题）数据流问题l如果程序中某一语句执行时能改变某个程序变量V的值，则称V是

7、被该语句定义的。l如果一语句的执行引用了内存中变量V的值，则说该语句引用变量V。 19二、数据流分析（1 1）数据流问题）数据流问题20例如例如:1.语句 X：Y十Z定义了X，引用了Y和Z；2.语句 if YZ then goto exit引用了Y和Z。3. 输入语句 READ X定义了X。4. 输出语句 WRITE X 引用了X。 二、数据流分析这是一个程序控制流图，同时给出了每一语句定义和这是一个程序控制流图，同时给出了每一语句定义和引用的变量的列表。引用的变量的列表。21二、数据流分析 该程序中合有两个错误：该程序中合有两个错误： 语句2使用了变量W，而在此之前并末对其定义。 语句5、6

8、使用变量V，这在第一次执行循环时也未对其定义过。 此外，该程序还包含两个异常：此外，该程序还包含两个异常： (3)语句6对Z的定义与使用有误。 (4)语句8对W的定义也从未使用过。 22二、数据流分析l程序中包含有些异常，如、也许不会引起执行的错误。l但是这一情况表明，也许程序中含有错误；l另外，我们也许可以把程序写得更容易理解，更优化，从而能够简化验证工作，以及随后的维护工作。23二、数据流分析（2）可达性定义）可达性定义l变量V的定义是修改V值的一个程序语句。l如果语句i是V的一个定义，我们可以用Vi来表示这一定义。24二、数据流分析（2）可达性定义）可达性定义l如果从节点i到节点j的入口

9、(或出口)变量V有一明确定义路径，定义Vi便说成是达到了节点j的入口(或出口)。如果控制流图中一路径并未对变量如果控制流图中一路径并未对变量V定定义，那么该路径就是变量义，那么该路径就是变量V的明确定义。的明确定义。l定义Vi被说成是“杀掉”了那些达到节点i的变量V的所有其它定义(但保留了其它变量的所有定义)。25二、数据流分析（2）可达性定义）可达性定义现在让我们来看哪些定义达到了程序的每一节点。l对于任一节点，我们用Si和ti分别表示达到i的入口和出口的定义集合。l设 pi是节点i保存的所有定义的集合，Ci是节点i中生成的定义集合。则对于每个节点i，这些集合满足关系：ti=(SiPi)Ci

10、26二、数据流分析（2）可达性定义）可达性定义很明显，达到节点i顶点的定义集合是达到其前趋出口的定义集合的并。l若用xi表示节点i前趋的集合，则可将此条件表示为：Si=(SiPi)di)j Xi 其中，其中，di=Cij Xi27二、数据流分析（2）可达性定义）可达性定义l若是一个具有n个节点的图，我们便有这样的一个联立方程组(i取值1，2，n)。l这样的方程组不只有一组解。但总有一个最小解，它给出要求达到的定义。l这一方程组可用循环迭代算法求解。28二、数据流分析（2）可达性定义）可达性定义在该算法中，一开始规定Si=d；(i=1，2，n)。然后依次对Sl，S2，Sn求解方程Si=(SiPi

11、)di)j Xi每次令等号左端的Si总取新值，当Si的值不再改变时，就得到了所求的解。29二、数据流分析30程序每一个节点的可达定义表：程序每一个节点的可达定义表：二、数据流分析（3）引用未定义变量）引用未定义变量根据可达定义表，可按下述方法找出对未定义变量的引用。l对每一节点i，依次考虑语句i引用的每一变量；l如果对任何这样的变量V，并没有V的定义达到i，那么程序含有一个错误。 31二、数据流分析（3）引用未定义变量）引用未定义变量l在上面的例子中，考虑节点2，根据引用变量表看出，这个语句引用变量W。l从可达定义表发现，W的定义不可能达到节点2。l因而程序中必定含有一个错误。这属于前述第一类

12、错误(转向并不存在的标号)。32二、数据流分析33（4）未曾使用的定义）未曾使用的定义l可以用下面的方法找出未曾使用的定义。l对于每一变量定义Vi，依次考虑由Vi达到的每个程序节点I；l如果没有引用变量V的相应语句，则程序中含有一个异常。二、数据流分析（4）未曾使用的定义）未曾使用的定义l例如，在上例中，考虑定义Z6时，根据可达定义表发现，这一定义达到节点7，8和9。l然而，由引用变量表我们看出，并没有对应的语句引用变量Z，这属于第三类错误-从程序入口进入后无法达到的语句。344.2逻辑覆盖逻辑覆盖 结构测试是依据被测程序的逻辑结构设计测试用例，驱动被测程序运行完成的测试。结构测试中的一个重要

13、问题是，测试进行到什么程度就达到要求，可以结束测试了，这也就是说我们需要给出结构测试的覆盖准则。354.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 36w 1.语句覆盖 w 2.判定覆盖w 3.条件覆盖w 4.判定-条件覆盖w 5.路径覆盖4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 37w 1.语句覆盖 程序例子:IF(A1)AND(BO)IHEN XXAIF(A2)OR(X1)THEN xx十14.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 38w 1.语句覆盖 什么是语句覆盖？什么是语句覆盖？w 在测试时，首先设计若干个测试用例。w 然后运行被测程序，使程序中的每个可

14、执行语句至少执行一次。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 39w 1.语句覆盖 如果选用的测试用例是： A2 B0 CASEl X3则程序按路径ace执行。这样该程序段的4个语句均得到执行，从而做到了语句覆盖。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 40w 1.语句覆盖 如果选用的测试用例是： A2 B1 CASE2 X3则程序按路径bce执行。此时该程序段只执行了其中的3个语句，所以未达到语句覆盖。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 41w 1.语句覆盖 w 从程序中每个语句都得到执行这一点来看，语句覆盖的方法似乎能够比较全面地检验每一个语句

15、。w 但即使程序中每个语句都得到执行，也不能保证程序完全正确。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 42w 1.语句覆盖 假如这一程序段中两个判断的逻辑运算有问题：（1）第一个判断的运算符“AND”错成运算符“OR”（2）或是第二个判断中的运算符“OR”错成了运算符 “AND”。 这时仍使用测试用例CASEl，程序仍将按路径ace执行。这时虽然也作到了语句覆盖，却发现不了判断中逻辑运算的错误。 4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 43w 1.语句覆盖 w 与其它几种逻辑覆盖比较起来，语句覆盖是比较弱的覆盖原则。w 作到了语句覆盖可能给人门一种心理的满足，以为每

16、个语句都经历过，似乎可以放心了。其实这仍然是不十分可靠的。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 44w 1.语句覆盖 w 语句覆盖在测试被测程序中，除去对检查不可执行语句有一定作用外，并没有排除被测程序包含错误的风险。w 其原因是，被测程序并非语句的无序堆积，语句之间存在着许多有机的联系。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 45w 2.判定覆盖什么是判定覆盖？什么是判定覆盖？w 按判定覆盖准则进行测试是指，设计若干测试用例，运行被测程序，使得程序中每个判断的取真分支和取假分支的情况至少经历一次，即判断的真假值均曾被满足。w 所以，判定覆盖又称为分支覆盖。4.2

17、逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 46w 2.判定覆盖仍以上述程序段为例，若选用的两组测试用例是：CASEl： CASE3 A2 A1 B0 B0 X3 X1则可分别执行路径ace和abd。从而使两个判断的4个分支c、e和b、d分别得到覆盖。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 47w 2.判定覆盖若选用另外两组测试用例：CASE4： CASE5 A3 A2 B0 B1 X3 X1则可分别执行路径acd和abe。同样使两个判断的4个分支c、e和b、d分别得到覆盖。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 48w 2.判定覆盖w 上述两组测试用例不仅满足

18、了判定覆盖，同时还做到了语句覆盖。w 但是，在此程序段中的第2个判断条件x1如果错写成x1，使用上述测试用例CASE5，照样能按原路径执行(abe)，而不影响结果。w 所以，判定覆盖只能作到判定覆盖仍无法确定判断内部条件的错误。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 49w 3.条件覆盖w 什么是条件覆盖？条件覆盖是指，设计若干测试用例，执行被测程序以后，要使每个判断中每个条件的可能取值至少满足一次。 4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 504.2逻辑覆盖逻辑覆盖514.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 52w 4.判定-条件覆盖w 什么是判定-

19、条件覆盖？ 判定条件覆盖要求设计足够的测试用例，使得判断中每个条件的所有可能至少出现一次，并且每个判断本身的判定结果也至少出现一次。 4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 53w 4.判定-条件覆盖4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 54w 4.判定-条件覆盖4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 55w 4.路径覆盖w 什么是路径覆盖？按路径覆盖要求进行测试是指，设计足够多的测试用例，要求覆盖程序中所有可能的路径。 4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 56w 5.路径覆盖针对例中的4条可能路径 ace记为L1 abd记为L2

20、abe记为L3 acd记为L44.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 57w 5.路径覆盖4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 58w 5.路径覆盖4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 59w 5.路径覆盖这里所用的程序段非常简短。也只有4条路径。在实际问题中。一个不太复杂的程序，其路径数都是一个庞大的数字，要在测试中覆盖这样多的路径是无法实现的。为解决这一难题只得把覆盖的路径数压缩到一定限度内，例如，程序中的循环体只执行了一次。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 60w 5.路径覆盖其实，即使对于路径数很有限的程序已经作到了路径

21、覆盖，仍然不能保证被测程序的正确性。例如，在上述语句覆盖一段最后给出的程序段中出现的错误也不是路径覆盖可以发现的（“or”与“and”的错写）。 由此看出，各种结构测试方法都不能保证程序的正确性。4.2逻辑覆盖逻辑覆盖一.几种常用的逻辑覆盖测试方法 61w 5.路径覆盖测试的目的并非要证明程序的正确性，而是要尽可能找出程序中的错误。确实并不存在一种十全十美的测试方法，能够发现所有的错误。想要在有限的时间内用有限的方法来发现所有的程序错误做不到的，这又涉及到了有关软件测试局限性的问题。 4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 62为实现测试的逻辑覆盖。必须设计足够多的测试用例，并使用这些测

22、试用例执行被测程序，实施测试。我们关心的是，对某个具体程序来说，至少要设计多少测试用例。这里提供一种估算最少测试用例数的方法。 4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 63结构化程序是由3种基本控制结构组成：顺序型构成串行操作；选择型构成分支操作；重复型构成循环操作。为了把问题简化，避免出现测试用例极多的组合爆炸，把构成循环操作的重复型结构用选择结构代替。4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 64例如，图512表达了两个顺序执行的分支结构。两个分支谓词P1和P2取不同值时，将分别执行a或b及c或d操作。显然，要测试这个小程序，需要至少提供4个测试用例才能作到逻辑覆盖，使得ac、a

23、d、bc及bd操作均得到检验。4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 65这里的4是图中第1个分支谓词引出的两个操作，及第2个分支谓词引出的两个操作组合起来而得到的，即224。其中的2是由于两个并列的操作，1十12而得到的。 4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 66对于一般的、更为复杂的问题，估算最少测试用例数的原则也是同样的。该程序中共有9个分支谓词。 4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 67尽管这些分支结构交错起来似乎十分复杂，很难一眼看出应至少需要多少个测试用例，但如果仍用上面的方法，也是很容易解决的。注意到该图可分上下两层：分支谓词1的操作域是上层；分支谓词8

24、的操作域是下层。4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 68这两层正像前面简单例中的P1和P2的关系一样。只要分别得到两层的测试用例个数，再将其相乘即得总的测试用例数。4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 69(a)所需测试用例个数分别为1十1十1十1十15(b)所需测试用例个数分别为及1十1十13。因而两层组合，得到5315。整个程序的上层所需测试用例数为l十1516。而下层十分显然为3。故最后得到整个程序所需测试用例数至少为16348。4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 70这里需要首先考虑较为复杂的上层结构。当谓词l不满足时要作的操作又可进一步分解为两层（a),(

25、b)。4.2逻辑覆盖逻辑覆盖二.最少测试用例数计算 71整个程序的下层所需测试用例数为3。所以最后得到整个程序所需测试用例数至少为16348。4.2逻辑覆盖逻辑覆盖三.测试覆盖准则72前面介绍的逻辑覆盖其出发点似乎是合理的。所谓“覆盖”，就是想要作到全面，而无遗漏。但事实表明，它并不能真的作到无遗漏。甚至右图程序段这样的小问题都无能为力。出现这一情况的原因在于，错误区域仅仅在I0这个点上，即仅当I取0时，测试才能发现错误。 4.2逻辑覆盖逻辑覆盖三.测试覆盖准则73KAFoster从测试工作实践的教训出发，吸收了计算机硬件的测试原理，提出了一种经验型的测试覆盖准则，较好地解决了上述问题。Fos

26、rer的经验型覆盖准则是从硬件的早期测试方法中得到启发的。我们知道，硬件测试中，对每一个门电路的输入、输出测试都是有额定标准的。通常，电路中一个门的错误常常是“输出总是0”，或是“输出总是1”。4.2逻辑覆盖逻辑覆盖三.测试覆盖准则74与硬件测试中的这一情况类似，我们常常要重视程序中谓词的取值，但实际上它可能比硬件测试更加复杂。Foster通过大量的实验确定了程序中谓词最容易出错的部分，得出了一套错误敏感测试用例分析ESTCA(ErrorSensitiveTestCasesAnalysis)规则。4.2逻辑覆盖逻辑覆盖三.测试覆盖准则75规则1对于A rel B(rel可以是，和)型的分支谓词

27、，应适当地选择A与B的值，使得测试执行到该分支语句时，AB，AB和AB的情况分别出现一次。4.2逻辑覆盖逻辑覆盖三.测试覆盖准则76规则2对于A rel1 C(rel1可以是或是，A是变量，C是常量)型的分支谓词，当rel1为时，应适当地选择A的值，使： ACM(M是距C最小的机器容许正数，若A和C均为整型时，M=1)。同样，当rel1为时，应适当地选择A，使： AC十M 4.2逻辑覆盖逻辑覆盖三.测试覆盖准则77规则3对外部输入变量赋值，使其在每一测试用例中均有不同的值与符号，并与同一组测试用例中其它变量的值与符号不一致。 4.2逻辑覆盖逻辑覆盖三.测试覆盖准则78显然，上述规则1是为了检测

28、rel的错误;规则2是为了检测“差一”之类的错误(如本应是“IF A1”而错成“IF A0”);规则3则是为了检测程序语句中的错误(如应引用一变量而错成引用一常量)。 4.2逻辑覆盖逻辑覆盖三.测试覆盖准则79上述三规则并不是完备的，但在普通程序的测试中确是有效的。原因在于规则本身针对着程序编写人员容易发生的错误，或是围绕着发生错误的频繁区域，从而提高了发现错误的命中率。 4.3路径分析路径分析 l什么是路径分析什么是路径分析?分析程序中的路径是指：检验程序从入口开始，执行过程中经历的各个语句，直到出口。804.3路径分析路径分析 l路径分析是白盒测试最为典型的问题。l着眼于路径分析的测试可称

29、为路径测试。l完成路径测试的理想情况是做到路径覆盖。814.3路径分析路径分析 l从上节的讨论中我们已经看出，对于比较简单的小程序实现路径覆盖是可能做到的。l但如果程序中出现多个判断和多个循环，可能的路径数目将会急剧增长，以至实现路径覆盖不可能做到。824.3路径分析路径分析 一、程序路径表达式1路径的弧序列表示及节点序列表示l如果图51(b)中的1号节点为程序入口，5号节点为程序出口，这一程序中可能的路径就有许多个。834.3路径分析路径分析 1路径的弧序列表示及节点序列表示l在此列举4条路径，分别以弧序列表示及节点序列表示。844.3路径分析路径分析 2路径表达式（pathexpressi

30、on）l路径表达式作为一种表达式，其运算对象指的是控制流图中的弧。路径表达式中引入两个运算：l乘运算l加运算854.3路径分析路径分析 2路径表达式（pathexpression）乘运算乘运算l弧a和弧b相乘，所得的乘积为ab，它表示先沿弧a，再沿弧b所经历的路段。l例如，acde是四个弧的乘积，它表示沿着a、c、d和e的顺序所经历的路段。864.3路径分析路径分析 2路径表达式（pathexpression） 加运算加运算l弧a与弧b相加，其和a+b表示两弧是或的关系。l如图中节点2至节点3有两个弧相联，是并行的路段。874.3路径分析路径分析 2路径表达式（pathexpression）l

31、 可以看出在图所表示的控制流中，共有可以看出在图所表示的控制流中，共有4条路径：条路径：eacf，eadf，ebcf和和ebdf。l这这4条路径是并行的或的关系，可以用加运条路径是并行的或的关系，可以用加运算联接它们，从而得到完整的路径表达式：算联接它们，从而得到完整的路径表达式： eacf+ +eadf+ +ebcf+ +ebdf 884.3路径分析路径分析 2路径表达式（pathexpression）l还可直接从图中看出，既然弧还可直接从图中看出，既然弧a和弧和弧b是并是并行的，弧行的，弧c和弧和弧d也是并行的。它们的头尾也是并行的。它们的头尾又分别与弧又分别与弧e和弧和弧f相联。相联。l

32、按上述两种运算的定义可写出路径表达式：按上述两种运算的定义可写出路径表达式： e(a+ +b)(c十十d)f 894.3路径分析路径分析 2路径表达式（pathexpression）l不难发现，这一表达式正是前面不难发现，这一表达式正是前面4项之和表达式的因子提出形式。项之和表达式的因子提出形式。Eacf+ +eadf+ +ebcf+ +ebdfe(a+ +b)(c十十d)f 904.3路径分析路径分析 2路径表达式（pathexpression）914.3路径分析路径分析 2路径表达式（pathexpression）924.3路径分析路径分析 二、程序中路径数的计算程序中到底有多少路径程序中

33、到底有多少路径?l这个问题表面上看似乎容易回答，其实不然。程序中所表示的程序路径数与循环的次数有关。934.3路径分析路径分析 二、程序中路径数的计算l右图如果循环体最多执行三次，那么路径数为3。然而，当程序中既有循环又有分支出现时，其路径数并不容易直觉地从控制流图中看出。944.3路径分析路径分析 二、程序中路径数的计算l1.路径表达式计算假定所讨论的程序已经得到了它的路径表达式，则可把其中的所有弧均代以数值“1”，然后依表达式的乘法和加法运算，所得数值即为该程序的路径数。954.3路径分析路径分析 二、程序中路径数的计算l1.路径表达式计算l例如，图所给的程序，其路径表达式为e(a十b)(

34、c十d)f。l把弧a，b，e，d，e，f均代人数值1，计算表达式的值即为路径数：N1(1十1)(1十1)1=4964.3路径分析路径分析 二、程序中路径数的计算l1.路径表达式计算l再以右图为例,如果暂不考虑循环，那么从节点1到节点4只有两条路径，L=a(b十cd)el代入数值“1”，得到：Ll(1十l1)1=2974.3路径分析路径分析 二、程序中路径数的计算l1.路径表达式计算l再看循环，假定只考虑循环次数小于3的情况。l路径表达式为：L+LfL十LfLfLL(1十fL十(fL)2)其中L表示循环体。984.3路径分析路径分析 二、程序中路径数的计算l1.路径表达式计算l此式中f代人“1”

35、，L代入“2”，则计算出路径数为：2(1十12十(12)2)14994.3路径分析路径分析 二、程序中路径数的计算l2.程序复杂度计算l我们知道，程序中含有的路径数和程序的复杂性有着直接的关系。l程序越复杂，它的路径数越多。1004.3路径分析路径分析 二、程序中路径数的计算l2.程序复杂度计算如何度量程序复杂性?l假定不考虑程序控制流图中，联结各节点之间弧的方向，控制流图便成为由节点和边构成的无向图。我们把无向图中任何两个节点之间至少存在一条通路的图称为连通图(connectedgraph)。1014.3路径分析路径分析 二、程序中路径数的计算l2.程序复杂度计算如何度量程序复杂性?lMcCabe给出了程序结构复杂性计算公式。lMcCabe提出，对程序控制流图的连通图G，其复杂度V（G）可按以下公式计算：V（G）=En+2其中，E为图G中的边数，n为图G中的节点数。1024.3路径分析路径分析 二、程序中路径数的计算l2.程序复杂度计算l程序结构复杂性计算公式。V（G）=En+21034.4 程序插装程序插装 程序插装(ProgramInstrumentation)是一种基本的测试手