基于控制流图的代码自动测试方法研究

摘 要：软件测试是提高软件质量和可靠性的重要手段。从是否运行程序的角度来讲，测试分为静态测试和动态测试，代码检查属于静态测试的范围。本文首先讨论了传统软件测试方法的缺点和局限性，进而提出了代码自动检测的方法，随后给出了此类方法可检测到的故障类型，具体给出了程序静态分析技术和方法研究，依据该方法进行了软件测试系统的设计与开发，最后给出了实验结果和对比分析，并进一步明确了下一步的研究方向。

关键词：软件生存期；静态测试；代码测试；故障

1 引言

软件测试贯穿于软件的整个生命周期，是软件生存周期必不可少的一部分，软件开发从总体的需求设计到具体的代码编写，每一个阶段都伴随着软件测试，阶段不同，采用的测试方法和策略也各不相同。如何保证在总体的需求分析和详细设计正确的情况下尽量减少代码编写过程中所犯的错误，是测试领域研究的内容之一。

从是否执行程序的角度来讲，软件测试方法分为两大类，即静态方法和动态方法[1]。静态方法的主要特征是不利用计算机运行被测试的程序，而是采用其它手段达到检测的目的。代码检测就属于静态方法的一种，至于静态分析在软件测试中究竟占据什么地位，许多人有不同的见解。有些人认为静态分析只是进行动态分析的预处理工作，静态分析并不是要找出程序中的错误，因为编译系统已经能够做到这一点了。实际上，这种看法是片面的，尽管编译系统能发现某些程序错误，但这些远非软件中存在的大部分错误，而且也仅仅是语法方面的错误，对于程序中潜在的故障，很多是编译程序检测不到的，因此静态分析的查错功能是编译程序不能代替的。

代码自动检测就是在程序经过调试和编译通过以后，运用某种测试技术对源程序进行静态分析，从而发现程序中存在的错误。所用的程序设计语言不同，检测到的故障各不相同，本文针对现阶段比较通用的程序设计语言JAVA为例，对程序可能出现的故障进行分析。本文在以下内容中介绍了代码自动检测技术能检测到的各种故障，随后对检测原理进行了深入剖析，最后设计了软件测试工具，并在工程中进行了实践。

2 检测的故障类型

代码自动检测技术能发现程序中存在的多类错误，然而编码中采用的设计语言不同，检测到的错误不同，本文以JAVA程序设计语言为例，阐述能发现的故障类型。JAVA是非常有吸引力的面向对象的编程语言，也是当前最流行的网络编程语言，在很多高校，JAVA程序设计已成为信息类相关专业学生的必修科目，然而它规定了严格的语法，但又有它的灵活性，它的对象性及接口的多样性增加了程序编写的灵活性，程序员可以任意发挥他们的编程技巧，这大大增加了程序的灵活性，然而这种灵活性又增加了程序的不可预见性，这直接导致了故障的发生。譬如数组越界是缓冲区溢出故障类型中的一种最常见的故障，它是由于对数组下标的操作越过了下标的范围引起的，数组越界在使用数组类型进行程序设计的软件中普遍存在。另外还有JAVA提供的一些关于字符处理的函数，虽然提供了这方面的功能，但没有对参数范围进行限制和检查，这也很容易导致错误的发生。以上这些故障采用一般的方法是很难发现的，因此必须采用一些特殊的检测方法对软件进行检测。

下面这些故障是本文所能检测到的：

⑴内存泄漏。JAVA语言中的内存泄漏与传统语言的内存泄漏是十分不同的，它是指内存对象不再需要时，但却仍被程序无意识地、错误地保持或引用而导致GC无法回收对象所占用的内存空间。在GC看来，它们还是“有用”的，从而导致内存泄漏。

⑵数组越界。数组越界顾名思义就是数组超出了原先设定的范围，导致出现了意想不到的结果。

⑶中文乱码。JAVA语言内部采用UNICODE编码，所以在JAVA程序运行时，就存在着一个从UNICODE编码和对应的操作系统及浏览器支持的编码格式转换输入、输出的问题，这个转换过程有着一系列的步骤，如果其中任何一步出错，则显示出来的汉字就会出是乱码。

⑷变量未初始化。变量定义后必须被初始化，未初始化的变量的值不确定，使用它会使程序出现不正确的结果，甚至导致程序出现异常。

⑸不可达代码。不可达代码是指永远执行不到的代码。

3 静态分析技术

近年来由于测试技术的发展，很多人开始对静态测试进行研究，并提出了很多的理论和方法，如C.Cowan[2]等人开发了一个缓冲区溢出故障测试工具，David Wagner[3]也给出了一种程序溢出故障的静态检测方法，David Evans[4]也给出了一种对动态内存故障进行静态测试的新方法。这些测试方法的提出在很大程度上丰富了软件测试的理论，加快了软件测试发展的步伐，并在实践应用中取得了很好的效果。这里我们就给出对代码进行自动分析，从而对故障进行检测的一种新方法，并进行了工具的开发，在工程应用中取得了很好的效果。

代码自动检测方法的核心是对程序源代码进行静态分析，运用编译技术把程序翻译成一种树的中间表示，这种树叫语法树[5]，而后生成与语法树相对应的程序的控制流图，然后运用故障规则对程序进行检测和故障定位。

3.1 语法树

语法树是程序代码的一种树形表示，是程序经过翻译后的一种中间表示形式。依据JAVA语言的语法规则，语法分析器接受词法分析产生的记号串，并依照相应的规则将记号组织成具有确切含义的语句，并构造相应的语法树。譬如赋值语句position=initial+rate*60可以用图1的语法树表示。

其中根节点是赋值语句，叶结点表示终结符，即标识符。

语法树是编译程序在经过语法分析以后得到的源程序的另外一种表示，语法分析的结果是生成语法树，每一个语法规则对应一个相应的处理函数，并作为树的一个节点挂在语法树上，提供对外的接口。由语法树可以生成程序的控制流图和变量的定义使用链，同时定义一些相应的数据结构，为下一步的错误查找作准备。

3.2 控制流图

程序流程图是人们最为熟悉的一种程序控制结构的图形表示法，在这种图上的框内表明了处理要求或条件，这些在软件测试中进行路径分析时是不重要的，需要对其进行简化。

下面以一段程序为例，简要说明控制流图的构建。

程序段为：

position=initial+rate*60；

if（position>50）{

i=4；

}esle{

i=5；

}

position=position+i；

对应的流程图及控制流图如下：

其中（a）是一个含有两出口判断的程序流程图，把它简化成（b）的形式，称这种简化了的流程图为控制流图。

在控制流图中只有两种图形符号，它们是：

①节点：以标有编号的圆圈表示。它代表了程序流程图中矩形框所表示的处理、菱形表示的两至多出口判断以及两至多条流线相交的汇合点。

②控制流线或弧：以箭头表示。它与程序流程图中的流线是一致的，表明了控制的顺序。为方便讨论，控制流线通常标有名字。

用控制流图表示程序的结构简明易懂，是软件测试阶段一个很好的工具，其中一个很好的应用就是在白盒测试阶段依据源程序生成程序的控制流图，遍历控制流图的路径，对程序进行路径测试分析。由于控制流图仅有一个入口和一个出口，从入口进入的每一条路径都能到达出口节点，因此控制流图是一个有向图。

3.3 代码分析过程

代码自动分析过程就是构造程序的语法树和控制流图以及故障匹配的过程。

（1）构造程序的语法树。语法树是进行故障分析的基础。分析器读入

源程序，经过词法分析和语法分析，产生出与程序对应的语法树，程序的相关信息都可以反映在语法树上。

（2）产生控制流图。语法树是程序的另外一种表示，是一种中间形式，

然而这种树的结构并不能反映程序的控制结构，因此需要构造程序的控制流图，来反映程序的控制流程。程序的控制流图与语法树是相对应的，控制流图的每一个节点对应语法树上的一个语句节点，从控制流图的接口可以方便的访问与之对应的语法树节点，从而获得相关的信息，同样的从语法树的语句节点也可以很方便的访问到控制流图的相应节点。以上已通过例子对语法树和控制流图的构造进行了介绍，如图1和图2所示。

（3）故障检测。从控制流图的根节点出发，依次访问控制流图的各个

节点，并通过控制流图提供的接口访问与其对应的语法树节点，而后依次遍历它的每一个子节点，在遍历过程中如果发现与故障模式相匹配的地方，则将故障输出。

4 自动检测工具的实现

由以上的方法可知，代码自动检测的核心是对源程序进行词法分析和语法分析，生成相应的语法树和控制流图，也就是设计一个编译系统。其整体测试框架为：

（1）预编译：由于源程序中存在宏定义、文件包含和条件编译等预处理命令，因此在进行词法分析前必须进行预处理，将宏进行展开，这样有利于变量的查找。

（2）词法分析：将预编译阶段产生的中间代码分解成单独的词的表示，形成初步的符号表，为语法分析作准备，表的结构主要有：标识符表、类型表、关键字表、常数表、运算符表和分界符表。标识符表中包含有利于错误查找的一些相关信息，如：位置、行号、错误类型，这些信息对于错误的查找和定位都有十分重要的作用。

（3）语法分析：这一步主要是将输入字符串识别为单词符号流，这里主要是找出变量声明语句，并相应的分离出指针变量和数组变量。按照标准的JAVA语法规则，对源程序作进一步分析，比如什么是变量定义，什么是赋值语句，什么是函数等等。语法分析的结果是生成语法树，每一个语法规则对应一个相应的处理函数，并作为树的一个节点挂在语法树上，提供对外的接口。由语法树进一步生成程序的控制流图，同时定义一些相应的数据结构，为下一步的故障检测作准备，同时在这一过程也逐渐添加和细化符号表的一些相关信息。

（4）故障检测：查找程序中可能出现的错误。依据程序的控制流图，依次遍历语法树的各个节点，匹配欲查找的错误，如错误找到，则将错误信息记录到数据库中，最后得到数据库文件。数据库文件记录测试过程中得到的一些相关信息，如出现错误的变量名、出现错误的行号、该行字符串、错误类型等。由数据库文件生成故障信息报告，将故障信息反馈给用户，用户根据故障报告进行程序更新和维护。

5 实验结果分析

以上给出了代码检测的一种自动分析方法，运用该方法我们进行了测试系统的开发，并针对一些不同领域的具体的软件项目进行了测试，部分测试结果如表1：

表格中的文件大小以M为单位，ML：内存泄漏故障；OOB：数组越界故障；UV：未初始化变量故障；DC：死码故障；

以上表格中的内容是我们测试数据的一部分，从表格中的数据可知，这几类故障在软件项目中普遍存在，只是项目不同，故障分配的概率不同，因此开发面向故障的软件测试工具十分必要。

6 结论

以往的代码审查通常是在代码完成以后，通过人工的劳动对代码进行走读，这种检查不仅费时费力，而且很难发现其中的错误，因此不仅效率低，而且效果比较差。本文提出的这种代码检测方法通过对源程序进行分析，匹配故障查找模式，结合程序的控制流图和相应的语法树，自动查找程序中存在的错误，不仅节省时间，效率高，在检测过程中不需要人为的干预，只需要对检测的结果进行确认，因此自动化程度高，是代码检测的一种好方法。本文通过应用这种静态测试方法，进行了软件测试工具的开发，并能检查出软件中存在的六种故障，然而这几种故障并不能代表所有的故障类型，在以后的工作中，我们将继续拓展故障类型和规则，争取使这种测试方法能检测出更多的故障，使其更加完善。

[参考文献]

[1]郑人杰.计算机软件测试技术[M].北京：清华大学出版社，1992.

[2]赵鹏宇，李建茹，宫云战.Java语言中数组越界故障的静态测试研究.

[2]朱颖芳.关于JAVA内存泄漏问题的探讨.电脑知识与技术，2006年第32期.

[3]N. Dor， M.Rodeh，and M.Sagiv.Cssv：Towards a realistic tool for statically detecting all buffer overflows in c[C].In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation， 2003： 155167.

[4]D. Wagner，J.Foster，E.Brewer，and A.Aiken.A first step towards automated detection of buffer overrun vulnerabilities[C].In Proceedings of the Network and Distributed Systems Security Symposium，2000：317.

[5]David Evans.Static Detection of Dynamic Memory Errors[C]. USA：ACM Conference on Programming Language Design and Implementation，1996：4452.

[6]A.V.Aho，R.Sethi，R.，and pilers Principles， Techniques，and Tools[M].America：Addison Wesley，1986.