5.3　路径覆盖

路径覆盖（Path Coverage）是遍历从程序流程的一端到达另一端的所有路径，使得每条路径至少被覆盖一次。如果程序存在环路，则要求每条环路同样至少被执行一次。路径覆盖是最高程度的逻辑覆盖技术，更具表征意义。与此同时，执行路径复合了代码权重，抽样方式更具多样性和资源弹性。

为了确保所有的分析和讨论建立在一致的平台之上，这里，仍以图5-7所示函数程序流程图为例，讨论路径覆盖问题。图5-7所示函数程序流程图仅包含如下4条路径：

L1（s-a-c-b-e-d）。

L2（s-a-b-d）。

L3（s-a-b-e-d）。

L4（s-a-c-b-d）。

那么，设计如表5-14所示路径覆盖测试用例集，即可覆盖此4条路径。

即便是不太复杂的程序，如果包含多个判断和循环，其路径数也可能是惊人的，实现路径全覆盖可能非常困难，何况是大型复杂软件系统呢！一个行之有效的方法是将覆盖路径数量压缩到可处理的限度。基本路径覆盖正是一种简化路径数的测试方法。

基本路径覆盖是基于程序控制流图，通过程序控制结构的环路复杂性分析，导出基本可执行路径集合，检查错误计算、不正确比较、不正常控制流等所导致的错误及路径错误，其基本步骤如下。

（1） 程序流程图设计： 任意程序结构都能通过图5-6所示顺序、分支、循环等基本图元来描述，采用流程图描述控制流，得到程序的邻接矩阵及独立路径集合。

（2） 程序复杂度计算： 计算程序的基本复杂度和圈复杂度，McCabe圈复杂度为程序逻辑复杂性提供定量测度，用于计算基本独立路径数，通过函数程序流程图分析得到的独立路径数就是该程序的复杂度。

（3） 基本路径确定： 一条独立路径是指和其他独立路径相比，至少引入一个新处理语句或一条新判断的程序路径，程序的圈复杂度 正好等于该程序独立路径数，通过函数程序流程图的基本路径分析，导出程序路径集合。

（4） 测试用例设计： 设计测试用例，确保基本路径集中每一条路径至少被执行一次。

5.3.1　图结构

图结构（Graph Structure）是由有限非空顶点集合 V 和边集合 E 构成的一种数据结构，记为 。顶点具有数据元素，边表示任意两个顶点 x 和 y 之间的关系，记作 。在图 中，如果 与 不等价，称 为有向图；若 与 等价，则称 为无向图，并以无序对 代替两个有序对 和 。 中，每条边都可以有一个称为权的数与之相连，权用以表示两个顶点之间的距离或从一个顶点到另一个顶点的代价。通常，称这种带权的图为网。简单路径是图 中路径上顶点不同的路径。

图 中，从顶点 x 到顶点 y 的路径为一顶点序列 ，其中 。路径上，顶点均不相同的路径称为简单路径。第一个顶点与最后一个顶点相同的路径称为回路或环或圈。除第一个顶点与最后一个顶点外，其余顶点均不重复的回路，称为简单回路。若从顶点 x 到顶点 y 至少存在一条路径，则称 x 和 y 是连通的。若图 中任意两个顶点都是连通的，则称为连通图。

通常，采用数组法和邻接表法等存储结构来表示图结构。数组法用一个一维数组存储各顶点的数据信息，用一个二维数组表示邻接矩阵即边的集合。其中邻接矩阵 A 是一个 n （图中顶点个数）阶方阵。邻接表法对图中的每个顶点建立一个单链表。在顶点 对应的单链表中，各节点表示以 为初始点的一条边，再用一个数组存储各顶点的数据信息和指向其对应的单链表的指针。此外，二进制向量表示法、邻接多重表、十字链表等都是图结构的重要表示方法。

中的弧（arc in R n ）称为简单弧，是曲线弧概念的推广，有两种不同的定义，一种是指连续的单射 ，弧就是特殊的路径，称 f 为简单路径；而另一种是指这样的 f 的值域 ，该定义更具几何含义，按照该定义，弧是自身不相交的曲线，或曲线上任意两点间不包含重点的部分。

5.3.2　控制流

控制流分析（Control Flow Analysis）是对源程序或源程序的中间表示形式直接操作，生成控制流图，是一类分析程序控制流结构的静态分析技术，包括过程内控制流分析和过程间控制流分析。过程内控制流分析是对一个函数内部程序执行流程分析，而过程间控制流分析则是对函数调用关系的分析。

静态分析研究的重点是过程内控制流分析。一种方法是利用程序执行过程中的必经点，查找程序中的环，根据程序优化需求，对环增加特定的注释，应用于迭代数据流优化器；另一种方法是基于子程序整体结构分析和嵌套区域分析，构造源程序控制树，将源程序按执行逻辑顺序，构造一棵与源程序对应的树型数据结构。

通常，我们采用控制流图（Control Flow Graph，CFG）表示软件中的各种结构。控制流图是一个过程或程序的抽象表示，用以表示一个程序中所有基本块执行的可能流向，即各基本块之间的相互关系、动态执行状态、各基本块对应的语句表示，反映程序的实时执行过程，代表一个程序执行过程中会遍历到的所有路径。使用图形符号描述程序控制流，每一种结构化构成元素都有一个相对应的流图符号。控制流图分类及符号表示如图5-8所示。

在控制流图中，圆圈代表软件模块，称为流图节点，每个节点表示一个基本块；箭头表示控制流，称为边或连接。但是，没有任何跳跃或跳跃目标的直线代码块，跳跃目标以一个块开始，以一个块结束。有向边代表控制流中的跳跃。一张流图可展现一个过程内各基本块之间的相互关系、动态执行状态、各基本块对应的语句表以及各基本块执行的次数、执行时间等。

通常，我们所获得的往往是源程序、程序流程图或设计说明。在实际工作中，需要将源程序、流程图转化成控制流图。在选择或多分支结构中，分支汇聚处有一个汇聚节点；边及其节点圈定的区域称为“区域”。对区域计数时，图形外的区域亦计为一个区域。图5-9展示了如何将一个程序流程图转化为控制流图的过程。

通过上述转换，即可使用控制流图来表示程序。如果判断中的条件表达式是由or、and、nand及nor等一个或多个逻辑运算符连接的复合条件表达式，则需要按照布尔计算法则将其转化为只有单条件的嵌套判断。

5.3.3　独立路径

5.3.3.1　控制流图

工程上，可将控制流图映射到一个流程图。假设流程图的判断框中不包含复合条件，一个处理框序列和一个判断框可被映射为一个节点。一条边必须终止于一个节点，即使该节点不代表任何语言，如if-else-then结构。通常，采用Z路径优化等方法对路径进行优化，无论循环形式和循环体实际执行情况如何，简化后的循环测试只考虑执行循环体一次和零次两种情况，限制循环次数。这里，我们考察如下函数，讨论如何将程序转化为控制流图。

这是一段用C语言实现的简单程序，能够很容易地得到其程序流程图。根据前述讨论，即可生成其控制流图。函数Sort程序流程图和控制流图分别如图5-10和图5-11所示。

5.3.3.2　圈复杂度

模糊性和依赖性是影响软件复杂度的重要因素。模糊性使得代码难以理解，是导致软件复杂性的直接因素；依赖性则导致复杂性不断传递，不断外溢的复杂性导致系统不断腐化。一旦代码变成“一锅意大利面条”，测试和维护将变得越发困难。

简单即可靠。复杂度越高，软件可靠性越低。这同系统可靠性工程“复杂即不可靠”论断一致。复杂性是导致软件难以理解和维护的根本原因。基于不同视角，各种定义乏善可陈。其中最具代表性的是Thomas J.McCabe的理性派复杂性度量及John Ousterhout的感性派复杂性认知。1976年，McCabe提出圈复杂度（Cyclomatic Complexity Metric）概念。圈复杂度是指软件线性无关的路径数量，是目前使用最为广泛的软件复杂度度量之一。软件复杂度度量体系如图5-12所示。

圈复杂度是一个模块判定结构复杂程度的重要测度，数量上表现为线性无关的路径数，即预防错误所需要测试的最少路径数。表5-15给出了一个推荐的圈复杂度度量指标。圈复杂度高的代码一定不是高质量代码，但圈复杂度低的代码未必就是卓越的代码。

圈复杂度计算方法比较简单，根据控制流图的边、节点数量、判定节点数及平面被控制流图划分成的区域数等，均可得到圈复杂度。依据图论方法，归结为如下三种方法。

1.基于控制流图边数及节点数的计算方法

其中， E 是 边的数量； N 是 的节点数； P 是 的连接组件数，即相连节点的最大集合。控制流图是连通图， 。

这里，首先考察如图5-13所示程序控制流图。

由式（5-1）及图5-13可得

也就是说，图5-13所示程序的圈复杂度为5。对照表5-15给出的圈复杂度评价指标，该程序具有较低的复杂度，即具有较好的可靠性及可维护性。

2.基于判定节点数的计算方法

圈复杂度所反映的是判定条件的数量，即控制流图的区域数。因此，基于判定节点数，圈复杂度就是判定节点数量加1，即

V ( G ) = 区域数 = 判定节点数 + 1

（5-2）

判定节点是指包含条件的节点。对于多分支case及if-elseif-else结构，统计判定节点时，须统计全部实际判定节点数，即每个elseif语句以及每个case语句，都计为一个判定节点。图5-13中，节点1、2、3、4均为判定节点，因此有： 。

3.基于控制流图区域划分的计算方法

基于控制流图计算软件圈复杂度 时，最好采用第一种计算方法；而基于模块控制流图计算软件圈复杂度 时，可以直接统计其判定节点数，即采用第二种计算方法，这样更简单直观。而对于复杂的控制流图，通过标注区域，可以方便地得到其圈复杂度为

式中， R 表示平面被控制流图所划分成的区域数。

该程序控制流图将平面划分为包括图形外区域在内的5个区域。基于控制流图区域划分的圈复杂度表示如图5-14所示。

得到程序的圈复杂度之后，即可得到程序的基本路径集。程序的基本路径集就是程序可达路径的最小集合，等于圈复杂度 。

5.3.3.3　测试用例导出

由基本路径集BP设计测试用例集 T ，使得 T 在理论上按BP执行，然后分析动态跟踪数据，构造实测路径集 。测试覆盖率为

式中， 。

对于嵌入式软件，其路径覆盖必须在交叉编译环境下，通过物理通道传输完整的动态测试跟踪数据，分析数据后得到路径覆盖率。动态执行前需要检查目标机与宿主机的连接与通信状况，确保测试正常进行。

对于图5-10、图5-11所示流程图和控制流图，根据上述计算方法，得到如下独立路径。

路径L1：4-14。

路径L2：4-6-7-14。

路径L3：4-6-8-10-13-4-14。

路径L4：4-6-8-11-13-4-14。

该函数的圈复杂度 正好等于该函数的独立路径数。那么，根据上述独立路径，设计输入数据，使程序分别执行上述4条路径即可。

5.3.3.4　测试用例准备

为了确保基本路径集中的每一条路径均能够被覆盖，根据判断节点给出的条件，选择适当数据，保证每条路径均被覆盖。对于图5-10所示程序流程图，满足基本路径集的测试用例如表5-16所示。

需要注意的是，有时，一些独立路径是程序正常控制流的一部分，并非完全孤立。这个时候，对这些路径的测试可以是另一条路径测试的一部分。

5.3.4　图形矩阵

图形矩阵是一个方阵，其行、列数对应控制流图的节点数，每行、每列依次对应到一个被标识的节点，矩阵元素对应到节点间的连接，由此确定一个基本路径集。对于图 ，将控制流图的每一个节点都用数字标识，每一条边都用字母标识。

若控制流图中第 i 个节点到第 j 个节点有一个名为 x 的边相连接，则在对应的图形矩阵中第 i 行/第 j 列有一个非空元素 x 。

给每个矩阵项加入连接权值，为控制流图提供额外的信息。一种最简单的情况，连接权值1表示存在连接，0表示不存在连接。连接权值可以赋予更有趣的属性，如执行连接的概率、穿越连接的处理时间、所需内存及资源等。图5-15展示了图5-9所示程序及其控制流图和图形矩阵之间的关系。

在图形矩阵中，如果某一行有两个及以上元素为“1”，则该行所代表的节点一定是一个判定节点，累加连接矩阵中两个及以上元素为“1”的个数，即得到圈复杂度的另一种算法。

5.3.5　基本路径覆盖用例设计

基本路径覆盖就是覆盖程序中所有可能、独立的执行路径。例如，某低温试验系统由10台低温试验箱组成，在综合显控台上，从左至右依次显示各低温试验箱的开启情况、ID号、工作状态及实时温度等信息。根据这些信息，设计如图5-16所示二进制字段。

开关：低温试验系统低温功能是否正常开启，“0”表示正常开启，“1”表示未正常开启。

ID号：10台低温试验箱的序号，分别从0000至1001。

状态号：低温试验系统中某一个低温试验箱的工作状态，范围从000到100，000表示温度正常；001表示温度过低；010表示温度过高；011表示电压过低；100表示电压过高。设定各低温试验箱的有效温度范围为−30～10℃，当某试验箱实时温度高于10℃或低于−30℃时，显示其状态及实际温度值。标准电压为180～220V，当低于180V或高于220V时，显示其状态及实际电压值。

温度数值：各低温试验箱的实时温度值，范围为[−50℃，+50℃]，在此范围内试验箱正常运行。“09”表示试验箱的运行情况，其中0表示该试验箱运行正常，1表示停止运行；“10”表示一个试验箱中实际温度的正负号，0表示正温，1表示负温；“11～16”表示实际温度，特殊情况下，当试验箱停止运行时，不再显示温度，即“09”显示为1，温度数值显示为0。

以8号试验箱为例进行讨论，在8号试验箱正常开启的情况下，首先考察其电压值是否在正常范围内，如果正常，再考察其温度值是否在正常范围内。如果电压值不正常，考察其电压值是过高还是过低，如果温度值不正常，考察其温度值是过高还是过低。8 号试验箱温度与电压程序流程图及程序实现代码如图 5-17所示。

由图5-17所示流程图及路径序号，得到该软件路径复杂度 V ( G )= E − N +2 P =5 。

由此，可设计如表5-17所示的基本路径覆盖测试用例。