面向C程序的环形复杂度自动化计算方法

秦振华,牟永敏

(北京信息科技大学 计算机学院,北京 100101)

0 概述

软件复杂性主要表现在程序的复杂性,即模块内程序的复杂性[1]。常见的定量度量软件复杂性的方法有代码行度量法、McCabe度量法和Halstead度量法。

McCabe度量法根据程序控制流的复杂程度定量度量程序复杂程度,这样度量出的结果称为程序的环形复杂度。在软件测试中,环形复杂度用于衡量一个模块判定结构的复杂程度,数量上表现为独立路径条数,即合理的预防错误所需测试的最少路径条数,这是为确保所有语句至少执行一次而必须进行测试的数量的上界,也可以理解为覆盖所有的可能情况最少使用的测试用例数[2-4]。在通常情况下,程序环形复杂度值越大,说明程序判断逻辑越复杂,越容易出错,且软件难以测试与维护。大量研究和经验表明,环形复杂度与软件模块中的错误紧密相关,假如一个模块比较复杂,那么它就容易出错,当超过了度量的阈值(通常是10),模块中的错误数量也会随之急剧增长[5-8]。

目前,计算程序环形复杂度的方法有2种:一种是根据控制流图人工计算出环形复杂度,当程序比较复杂时容易产生错误;另一种是采用工具自动计算,如SourceMonitor,计算速度快,但在某些复杂条件下得出的环形复杂度不够准确。

针对上述问题,本文通过对源程序进行预处理,提取程序中含有控制流信息的关键语句,实现程序环形复杂度的自动化计算。

1 相关技术

1.1 控制流图

控制流图(Control Flow Graph,CFG)是一个有向图G=(V,E),其中,V是控制流节点的集合,E是有向边的集合。一个控制流图有一个唯一的入口节点(其入度为0)和一个唯一的出口节点(其出度为0)。控制流图中的节点V代表程序的语句或表达式,有向边E表示语句间的执行关系。令(x,y)∈E,表示控制流图中的边x→y,称x是y的前驱,y是x的后继。

控制流图中的节点可分为2种类型:一种是块结构,即把程序划分为块,块中的语句是连续的,且只包含简单语句,不包含分支和循环等引起程序执行顺序改变的语句;另一种是程序的每一条语句都单独地看成一个控制流节点[9-13]。本文绘制的控制流图节点采用第一种类型,并且以程序的行号来表示程序的控制流节点。

1.2 McCabe度量法

计算程序的环形复杂度有3种方法,以图1所示控制流图为例。

图1 控制流图

3种方法的具体描述如下:

1)给定控制流图G的环形复杂度CC(G),控制流图中区域的数量F(仅考虑区域个数,不考虑边的方向)。图中区域数量为4(R1、R2、R3、R4),则CC(G)=F=4。

2)给定控制流图G的环形复杂度CC(G),定义为CC(G)=E-N+2,E是控制流图中边的数量,N是控制流图中节点的数量。图中边的数量为E=10,节点的数量为N=8,则CC(G)=10-8+2=4。

3)给定控制流图G的环形复杂度CC(G),定义为CC(G)=P+1,P是控制流图中判定节点的数量,判定节点是只包含一个条件的节点,从每一个判定节点发出2条或多条边。图中判定节点的数量为P=3,3个判定节点为4、6、8,则CC(G)=3+1=4。

1.3 问题分解

本文针对C语言程序研究环形复杂度的自动化计算,首先分析其结构特点。C语言程序中的语句分为控制语句、函数调用语句、表达式语句、空语句和复合语句共5种,其中,控制语句分为9种,分别是if-else条件语句、for循环语句、while循环语句、do-while循环语句、continue语句、break语句、switch多分支选择语句、return语句和goto语句[14-15]。在这里,将if-else语句、if-else if语句、switch-case语句和包含三目运算符的语句称为分支语句,for语句、while语句和do-while语句称为循环语句,分支语句和循环语句将对应于控制流图中的判定节点。因此,可以借助程序中的分支和循环语句来实现环形复杂度的计算。当程序中分支语句或者循环语句的判别条件为复合条件时,将复合条件分解成单个条件后,再进行环形复杂度的计算。下面将分情况讨论C语言程序中分支语句和循环语句对程序环形复杂度的影响。

1)if-else语句

当if语句中只有1个判别条件时,当前语句对应的判定节点的数量等于1;当if语句中有多个判别条件时,当前语句对应的判定节点的数量等于if语句中判别条件的个数。

2)if-else if语句

对于if-else if语句,除了考虑if语句的情况外,还需要考虑else if语句的情况,处理方法和if-else语句的处理方法相同,当前语句对应的判定节点的数量等于判别条件的个数。

3)包含三目运算符的语句

由于包含三目运算符的语句,也是一种特殊的条件语句,因此其处理方法和if-else语句的处理方法一样,其对应的判定节点的数量等于语句中判别条件的个数。

4)switch-case语句

对于switch-case而言,有没有default语句对于程序环形复杂度的计算没有影响,在一般情况下,判定节点的数量等于case的个数。由于switch-case不用像if-else if那样遍历条件分支直到命中条件,而只需访问对应索引号的表项从而达到定位分支的目的。具体地说,switch-case会生成一份大小(表项数)为最大case常量+1的跳表,程序首先判断switch变量是否大于最大case常量,若大于,则跳到default分支处理;否则,取得索引号为switch变量大小的跳表项的地址(即跳表的起始地址+表项大小×索引号),程序接着跳到此地址执行,到此完成了分支的跳转。所以,即使case中没有break语句,也不会影响产生的分支数,对程序环形复杂度的计算也不会产生影响。但是存在一种特殊情况,即多个case相连,此时需要把多个相连的case当成一个判定节点进行计算,以文献[2]中的例子加以说明,如图2所示。

图2 多个case相连的情况

5)while语句

在一个循环结构中,循环条件表达式和循环结束条件共同决定程序的最终走向,结合这一特点,对于while循环语句,可以分5种情况进行讨论:

(1)条件表达式永真,这里只考虑while(1)这种形式的永真,但是有循环结束条件,此时while语句不是判定节点,如图3所示。

图3 while语句的特殊形式

在图3中,第4行和第6行语句合并为一个节点,此时控制流图中只有一个判定节点,这与平时遇见的情况有所不同,需要特殊处理。

(2)条件表达式永真,但是无循环结束条件,即所谓的死循环,此时while语句是判定节点。

(3)条件表达式永假,这里只考虑while(0)这种形式的永假,此时循环体内的所有判定节点都不需要计算,包括while自己。

(4)条件表达式非永真永假,并且是单个条件,此时while语句相当于一个判定节点。

(5)条件表达式非永真永假,并且是复合条件,此时while语句对应判定节点的数量等于while语句中判别条件的个数。

6)for语句

for语句的处理方法和while语句的处理方法一样。

7)do-while语句

do-while语句的处理方法和while语句的处理方法基本一致,唯一的区别是当条件表达式永假时,while语句的循环体内的所有判定节点都不需要计算,而do-while语句的循环体内的判定节点需要计算。

1.4 代码度量工具

环形复杂度是代码复杂度的一个指示器,可以利用一些著名的开放源码工具计算环形复杂度,比如PMD、CheckStyle和JavaNCSS,但是这些工具只是针对Java程序的,OCLint、Testwell CMT++、Understand、SourceMonitor等工具可以度量C程序的环形复杂度。在实验部分,借助于后2种工具和本文提出的方法进行比较。

Understand是一个SciTools发行的、商用的静态分析工具,可以维护、测量和分析源代码。该工具能够分析14种语言,包括C/C++、Java、FORTRAN和一些Web编程语言,例如PHP,并且适用于大部分操作系统,包括Solaris。该工具可以对整个项目的结构、度量值进行分析并输出报表,能够对代码生成多种图,包括控制流图、依赖关系图、UML类图等。

SourceMonitor是一款免费的软件,运行在Windows平台下。它可对多种语言写的代码进行度量,包括C、C++、C#、Java、VB、Delphi和HTML,并且针对不同的语言,输出不同的代码度量值。对于C程序,提供了总行数、语句数目、分支语句比例、注释比例、函数数目、平均每个函数包含的语句数目、函数环形复杂度和函数深度等度量值。

2 系统分析与设计

本文提出的研究方法可分为3个阶段:源代码的预处理,控制流信息的提取,环形复杂度的自动化计算。其中,采用了状态机编程思想删掉源程序中的注释来实现源代码的预处理,利用模式匹配的规则来提取含控制流信息的关键语句,通过分情况处理关键语句来实现程序环形复杂度的自动化计算。

2.1 源代码预处理技术

源代码的预处理主要是扫描程序中出现的注释,并将其删掉。由于注释信息对最后环形复杂度的计算没有影响,并且注释中的某些信息会干扰接下来关键语句的提取,因此找出源代码中的注释信息,将其从源代码中删掉。这里只考虑单行注释、多行注释和折行注释这3种情况,其中,折行注释是以双斜杠开头、反斜杠结尾,很多编辑器高亮都没有考虑到这种情况。此处采用了状态机编程思想将源代码中的注释删掉。

2.2 控制流信息的提取

在程序中,分支语句和循环语句最终对应于控制流图中的判定节点,因此,如何提取程序中的分支和循环语句显得尤为重要。此处通过模式匹配的方式提取程序中的关键语句,其中模式匹配规则如表1所示。

表1 模式匹配规则

表1中的模式匹配规则共有6种模式,左侧为模式序号,右侧为模式匹配的规则。由于计算的是单个函数的环形复杂度,因此用模式P1匹配程序中的函数定义,从而开启一个处理单元。分支语句和循环语句用模式P2、P3、P4和P5进行匹配。其中,模式P2匹配if、for和while语句,模式P3匹配switch-case语句,模式P4匹配包含三目运算符的语句,模式P5匹配do-while语句和break语句,匹配break语句是为了后续判断当循环结构中无循环条件表达式时,有无循环结束条件。如果循环体中有循环结束条件break语句,那么循环可以正常结束,此时的循环语句不是判定节点,否则是死循环结构,此时的循环语句是判定节点。模式P6用来进行花括号匹配,左花括号对应语句块的开始,右花括号对应语句块的结束,根据花括号,可以对源程序进行分块处理。在表1规则的基础上,再结合正则表达式中的search()方法,就可以将程序中的关键语句信息都提取出来。

2.3 环形复杂度的自动化计算

经过源程序的预处理和提取关键语句这2步,此时程序中只剩下分支语句、循环语句等关键信息,接下来需要根据这些关键信息,进行程序环形复杂度的计算。在当前步的处理中需要注意的是:当语句中判别条件是复合条件时,需要把复合条件分解成单个条件进行计算。对于循环语句中条件表达式永真、永假的情况,尤其是当条件表达式永真,但是有break语句可以跳出循环,此时当前循环语句并不能当成判定节点这种情况,都需要进行特殊处理。

鉴于此,在当前步骤的算法设计中采用自顶向下的分析策略,对各种情况分别编写相应的处理函数,定义一个栈stack用来进行花括号匹配,定义一个变量num用来记录最终环形复杂度的值,初始值为0,并用flag标志来标记循环语句块中是否有break语句,flag=0表示没有,flag=1表示有,用ok标志标记if语句块中是否包含break语句,当循环语句块中嵌套if语句块,if语句块中包含break语句,此时break语句也可以跳出循环,flag=1。然后,从上往下扫描源程序,如果当前语句中包含“{”,则进行入栈操作,stack.push(“{”);若包含“}”,则进行出栈操作,stack.pop();若包含“if”关键字、“switch”关键字、“do”关键字、“for”关键字、“while”关键字、三目运算符,则相应地调用count_if()、count_case()、count_do()、count_for()、count_while()、count_three()方法,通过对应的方法计算代码块中相应代码的环形复杂度,并把计算得到的结果加到变量num中去,接着进行下面语句的处理,直到程序结束。这样,最终程序环形复杂度的值便等于变量num的值。其中,计算while语句块中相应代码的环形复杂度的算法如下。

算法1cout_while

输入程序的行号值

输出环形复杂度值

1.str=the current statement,sum=0,flag=0

2.index=the current statement’s line number value

3.ok=whether the if statement block contains break

4.if conditional expression is equal to 0 then

5. while stack count is not equal to 0 do

6. read the next statement

7. end while

8.else

9. while stack count is not equal to 0 do

10. str=the next statement

11. if str contains if then

12. sum+=count_if(index)

13. if ok is true then

14. ok=false,flag=1

15. end if

16. else if str contains switch then

17. sum+=count_case(index)

18. else if str contains do then

19. sum+=count_do(index)

20. else if str contains while then

21. sum+=count_while(index)

22. else if str contains for then

23. sum+=count_for(index)

24. else if str contains ternary operator then

25. sum+=count_three(index)

26. else if str contains break then

27. flag=1

28. end if

29. end while

30. if conditional expression is equal to 1 then

31. if flag is equal to 0 then

32. sum++

33. end if

34. else

35. sum+=the number of conditions

36. end if

37. end if

38. return sum

在算法1中,对于while语句块的处理,需要考虑条件表达式永真、永假和非永真永假这3种情况,语句块的开始和结束对应栈的入栈和出栈操作,当栈中元素个数为0时,标志着当前语句块中内容处理完毕。对于条件表达式永假的情况,直接顺序读取语句块中的内容即可;对于永真的情况,需要根据flag的值来判断sum的值需不需要加1;对于非永真永假的情况,sum需要加的值等于while语句中条件的个数。

3 实验评测

3.1 实验环境

实验所用操作系统为64位Windows 7旗舰版Service Pack 1,内存为4 GB,处理器为Intel(R) CoreTMi7-2820QM CPU @ 2.30 GHz。

3.2 测试用例

实验中用的测试用例采用了文献[15]中的程序,该程序涉及到了注释、if-else语句、switch-case语句、while语句、三目运算符、单个判别条件和复合条件,具有一定的代表性。具体测试用例如下所示。

int main()

{

1. int a,b,max,c,count=0;

2. char operate,flag;

3. while(1)

{

4. flag=getch();

5. printf("第%d次运算 ",++count);

//输入的字符不是小写字母,退出程序

6. if(flag>='a' && flag<='z')

{

//输入运算数和运算符

7. scanf("%d%c%d",&a,&operate,&b);

8. max=a>b ? a:b;//max记录最大值

9. switch(operate)

{

10. case'*':

11. c=a*b;

12. break;

13. case'/':

14. if(b==0)

15. c=-1;

else

16. c=a/b;

17. break;

18. default:

19. c=-1;

}

20. printf("结果为:%d,%d ",max,c);

}

else

{

21. break;

}

}

22. return 0;

}

为了能更好地验证本文提出的环形复杂度自动化计算方法,同时实现控制流图的自动生成,采用如下方法:利用GCC编译源代码生成中间文件,提取并分析中间文件的语句块信息,找出语句块之间的关系,用替换的方法把语句块之间的关系转换成行号之间的关系,并把结果输出到一个.dot文件中去,最后使用WinGraphviz这个COM组件把最终结果以控制流图的形式展示出来[16-18]。

本文系统在自动生成控制流图时,对于程序中判别条件是复合条件的情况,将复合条件拆成单个条件,并用“行号_条件标号”这种形式进行表示,例如“6_1”,表示第6行第1个判别条件。对于三目运算符来说,执行的语句用“行号_语句块标号”这种形式来表示,例如“8_01”,表示执行第8行第1个语句块中的语句。上述测试用例所对应的控制流图如图4所示。

图4 测试用例对应的控制流图

测试用例中if(flag>=‘a’&& flag<=‘z’)语句的判别条件是复合条件,拆成2个判定节点,max=a>b ? a:b;语句包含三目运算符,判别条件是单个条件,相当于一个判定节点,switch-case中有2个case,产生2个判定节点,再加上嵌套的if(b==0)语句,共产生3个判定节点,而对于while(1)这种条件表达式永真的循环语句,由于循环体中存在循环结束条件,因此while(1)语句不是判定节点。综上所述,测试用例中共有6个判定节点,程序的环形复杂度为7。

3.3 实验结果

根据图4可知测试用例的环形复杂度为7,这与图5得出的实验结果一致。所以,本文提出的方法可以准确地计算出程序的环形复杂度。将系统命名为RcTest工具,与Understand和SourceMonitor工具针对上述测试用例计算得到的结果进行比较,最终结果如表2所示。

图5 程序运行结果

工具环形复杂度分析RcTest7while(1)语句不是判定节点Understand7把复合条件、while(1)语句都当成一个判定节点SourceMonitor11while(1)、else、default语句都当成一个判定节点

经过大量实验得出,Understand和SourceMonitor工具在计算环形复杂度时与RcTest有如下不同:

1)Understand工具

(1)在生成控制流图和计算时,把复合条件当成一个条件进行分析;

(2)像循环语句中while(1)和while(0)这2种特殊的永真和永假形式,并没有被考虑,在控制流图中会画出while节点,并把while节点当成判定节点加入到环形复杂度中去;

(3)对于包含三目运算符的语句,在控制流图中当成顺序语句节点来处理,在计算时,会当成一个判定节点进行计算,但是没有考虑复合条件的情况;

(4)对于switch-case语句,在一般情况下,当case语句块中没有break语句时,对环形复杂度的计算无影响,但是一旦出现多个case相连这种特殊情况,在生成控制流图时,会把多个相连的case当成一个节点,在计算时,统计的是case的个数。

2)SourceMonitor工具

(1)将复合条件拆成多个单条件进行计算,但是在处理包含三目运算符的语句时,没有考虑复合条件,只当成一个判定节点;

(2)对于if-else结构的语句,会把else当成一个判定节点;

(3)没有考虑循环语句中永真和永假的特殊形式;

(4)对于switch-case语句,在一般情况下,不管有没有default语句,判定节点数等于case的个数+1。但是当case语句块中没有break语句时,当前case语句不当成判定节点,对于多个case相连的情况,会把多个相连的case当成一个判定节点进行计算。

通过比较可知,系统在计算环形复杂度时,相对于Understand和SourceMonitor工具更加准确。

下面分析3种工具在计算时间开销上(单位是秒)的差别,分别以104、105、106行代码为例进行比较,最终结果如表3所示。

表3 3种工具的计算时间开销 s

由表3可知,RcTest工具在计算效率上比SourceMonitor略高。由于Understand工具会生成控制流图等额外信息,因此时间开销较大,但是产生的信息比较齐全。

4 结束语

环形复杂度是软件难度度量的一个重要指标,本文通过提取源程序中含有控制流信息的关键语句,对其进行分析处理,用于实现环形复杂度的自动化计算。在这种方法下,无需知道源程序的控制流图,而且通过去掉源程序中一些无关紧要的信息,只留下影响环形复杂度的关键信息,进而可以高效、准确地计算出程序的环形复杂度,可操作性更强,更简单,节约了测试时间,降低了测试成本。下一步将完善该工具的扩展性,使其可以计算其他语言编写的程序的环形复杂度。