基于代数的软件路径的自动生成

李肇明

(安徽国际商务职业学院 信息工程学院，安徽 合肥 230000)

软件测试是软件开发周期中的一个关键阶段[1]，在此阶段可以发现潜在的软件缺陷和故障，并确保这些问题能及时得到解决，从而提高软件质量。白盒测试，又称结构测试和逻辑驱动测试，是软件测试中一种强大的技术，其目的是对要测试的软件的内部结构进行测试[2]。该方法在对软件可靠性有较高要求的领域获得广泛运用，如军事、金融和航空领域等。其中路径测试是白盒测试中应用最为广泛的方法之一。路径测试的过程通常被分为代码分析、控制流图生成、路径生成和测试用例四个部分[3]。因此，路径测试的准确性与路径生成密切相关。然而，随着软件规模的不断增加，软件系统中的循环结构出现次数也随之增多，路径成爆炸式增长，目前已有的软件路径生成方法代价大且困难。文献[4-7]中对于软件路径的自动生成问题均提出了相关算法，但这些算法只生成了软件的基本路径集，并没有生成软件的完整路径。文献[8]提出了一种基于状态图自动生成软件路径的方法，并实现了对路径的优化，但该方法未对程序中循环结构的出现次数进行约束，致使该方法的工作量增加。

本研究提出了一种基于代数的软件路径生成方法，该方法对源代码进行分析，生成控制流图；然后通过代数表示将控制流图转换为路径表达式，并对路径表达式中的循环进行展开，从而获得软件路径。

1 相关概念

定义1 控制流图(CFG)[9]:G=(N,E,b,f)，N表示CFG中的节点集，每个节点n(n∈N)代表源程序的一个语句块；E代表CFG中的有向边集。每一条有向边e(e∈E)对应源程序两个节点之间的数据流向；b代表CFG中的入口节点；f代表CFG中的出口节点。CFG的入口和出口节点都只有一个。

定义2 软件路径：软件路径(Path)是指在一个软件的CFG中程序执行控制流从b到f的一条路径。其表示为边的序列：P=ebe2…enef。其中eb表示入口节点b的出边，ef表示出口节点f的入边。

CFG是一个程序的抽象表示，表示一个程序在执行过程中可能会遍历到的所有路径。CFG一般通过图的形式表示，但它也可以通过非图示的形式表示，其中一种有效的方法是代数表示。在图的代数表示中，首先给每一条边唯一的标签，使用小写字母作为边的标签。'×'操作符表示串联。当边a连接边c时，可被表示为ac，操作符'×'省略。'+'操作符表示选择，当选择边a和边c时，将其表示为a+c。当一系列的边组成一条路径时，把这条边序列称为路径积。由路径积和零或者更多的'+'操作符构成的表达式为路径表达式。

其中路径积是没有加法操作的路径表达式的特殊情况。图1是两个控制流图，图1(a)有三条路径：abdfi;abegi;achi;

图1(b)包含循环路径，所以无法把它的全部执行序列出来，下面是其中4条序列：abef;abcbef;abcbcbef;adf;

在图的代数表示中，如果一条边、路径积或路径表达式被循环遍历，可以通过指数表示循环次数。即a2=aa,a3=aaa,a*=aaa…a。

与标准代数不同，路径积不满足交换律，即ab≠ba，这是由于它们具有先后连接的顺序。但是它满足结合律，即a(bc)=(ab)c=abc。图1(a)中的所有路径可以用abdfi+abegi+achi表示从，有'+'操作符连接的路径都可以看作是独立的软件路径。

2 路径生成

提出一种基于代数的软件路径自动生成方法。其框架构图如图2所示。该方法可分为3个阶段：第1阶段，通过对软件的源程序进行分析，构造控制流图；第2阶段，对控制流图中的每一条边进行标记，通过代数方法把控制流图转换

为路径表达式；第3阶段，对路径表达式中的循环展开，得到软件路径。

3 构造控制流图

源程序生成控制流图通常分为3个过程：词法分析、语法分析和构造控制流图。本研究使用Antlr工具实现词法分析和语法分析。用户所提交的语法文件通过Antlr自动生成相应的词法分析器和语法分析器。在词法分析过程中，源程序被分解为离散的字符组，也就是Tokens(标识符、关键字、操作符和符号等)。在语法分析过程中，语法分析其将通过词法分析获得的Tokens组织起来，并转换为ATS(Abstract Syntax Tree, 抽象语法树)。ATS上的每个节点都代表源代码中的一种结构，通过对ATS遍历以构造控制流图。

3.1 路径表达式生成

首先对边标记，然后将源程序转换为软件路径表达式。在控制流图中，通过小写字母依次对边标记，如图3所示。

然后，使用代数方法将其转换成路径表达式，方法步骤如下：

(1)合并所有连续边，相乘边的标签。(2)合并所有平行的边，用'+'操作符相加平行边的标签从而作为合并之后边的标签。(3)通过创建一个新“哑节点”引入一条含有指数操作符'*'边的方法消除具有自循环的节点，随后通过乘法来合并这三条边。(4)选择移除节点。(5)第一步到第四步被循环执行直到图中只有一条边。

图3的转换过程如图4所示。

3.2 循环展开

路径表达式中的每一条路径积都应该在一个合适的循环下展开。如果循环次数过多，产生的路径数量将急剧增加，将产生路径爆炸问题。

采用Z路径覆盖思想，只考虑循环0次和1次两种情况。即针对代数表达式中的循环指数，考虑操作符'*'为0和1两种情况。图4中路径表达式abde*f(gde*f)*hi+ acde*f(gde*f)*hi展开为abdefgdefhi,abdefgdfhi,abdefhi,abdfgdefhi,abdfgdfhi,abdfhi,acdefgdefhi,acdefgdfhi,acdefhi,acdfgdefhi,acdfgdfhi,acdfhi。

3.3 算法实现

具体算法伪码如表1所示。

表1 算法伪码

● 算法的输入为CFG，输出为软件路径；

● 算法第2～21行CFG约简为路径表达式；

● 算法第22～27行对路径表达式中的循环做处理。

表1续表

4 案例研究

为了验证该方法的准确性，首先对两个小规模基准程序进行路径生成。程序规模较小，便于手工生成路径，并与文中方法比较。为了验证本方法的有效性，通过案例来说明。

4.1 案例1

三角形分类旨在确定3个输入边是否能形成一个三角形，及它们能形成什么类型的三角形；冒泡排序是一种排序算法，它将待排序的数据元素从大到小或从小到大排序。三角形分类控制流图如图5(a)所示，冒泡排序控制流图如图5(b)所示。

通过本方法对三角形判别和冒泡排序进行路径

生成，结果如表2所示。

表2 实验结果

图5(a)中共有4条路径，从表2可以看出该方法生成三角形分类的全部路径。图5(b)中存在两个循环，从表2中可以看出该方法生成的4条路径对这两个循环分别执行0次和1次，实现对路径的覆盖。

4.2 案例2

选择5个经典案例进行实验。在实验环境不变的条件下对这5个经典案例分别运行10次并计算出平均运行时间。由于从源程序转换为控制流图是通过工具辅助生成，其时间无法度量，所以该运行时间只包含将控制流图转换成软件路径所需时间，而且传统方法求路径集也需要人工生成控制流图，时间也无法度量，因此不存在可比性。表3给出了案例的相关描述，该算法能有效生成5个案例的路径。

表3 5个经典案例实验结果

图6中，对算法进行比较，能够看出，当代码量迅速增大时，该算法生成软件路径所消耗的时间并未随着快速增加，而是较为平缓增长。

5 结语

本研究提出一种基于代数的软件路径生成方法，该方法通过代数表示将控制流图转换为路径表达式，并对循环展开0到1次以获得软件路径。该方法最终有效地生成了软件路径。但是，该方法未考虑软件中不可达路径的问题，而且针对循环问题只考虑了0次和两次循环这两种情况。下一步工作将开展对不可达路径检测工作。