程序复杂性度量技术分析

孔庆玲,胡志军,刘 英,冯 阳

(中国电子科技集团公司第五十四研究所,河北石家庄050081)

0 引言

软件越复杂,一方面在开发和维护过程中所消耗的资源也越多,所以软件的复杂性可以作为软件所需资源投入量的一个间接度量;另一方面在设计中引入错误的可能性也越大,这是一种合乎逻辑的推理,也是一个为实验验证的事实。尽管软件复杂性与软件中的错误数未必呈现出简单的正比关系,但是存在这种正相趋势是肯定无疑的。软件不可靠的根本原因是软件中存在错误,所以软件复杂性可以作为软件可靠性的一种间接度量。复杂性度量是软件开发过程中有应用前景的一个度量。借助这个度量,设计人员在接受设计任务之初,可以从已有的性质相似的程序中获得经验数据,对现在所面临问题的复杂程度做出判断,借助于复杂性度量还可以对若干设计方案的困难程度加以比较。

1 技术分析

目前比较流行的有3种程序复杂性度量方法:Halstead、McCabe和 Thayer。Halstead使用统计的方法研究程序的复杂性,按照程序中的运算符和操作数的总数对程序的复杂性加以度量。McCabe以程序逻辑流程图的分析为基础,建立复杂性的度量。Thayer按程序的逻辑关系、接口、运算特征和输入/输出的特点来度量程序的复杂性。下面就这3种复杂性度量技术分别进行分析。

1.1 Halstead复杂性度量技术

Halstead认为程序的复杂性可以用程序的运算符总数与操作数总数之和来反映,这个总数和称为Halstead程序长度。为了得出Halstead程序长度的表达式,可以把程序视为由运算符、操作数交替组成的符号序列,在这些符号序列中,有 η1个不同的运算符符号和 η2个不同的操作数符号。属于运算符符号的有+、-、＞、＜、IF THEN ELSE和DO WHILE等,属于操作数符号的有变量、常数、字符串变量和字符串常数等,η1与η2的总和构成程序的词汇表。注释和其他非执行语句不属于词汇表的范围。

Halstead将程序的生成等价于如下的随机过程,首先从词汇表中随机选择一个运算符符号,然后从词汇表中随机选择一个操作数符号,这个交替过程一直持续下去,直到最后一个从未用过的运算符符号或操作数符号被选中时,程序的生成才结束,这时字符串长度的期望值可以按统计规律求出。

为了简化分析过程,首先研究由 η个符号组成的词汇表中的字符串的生成过程。可以观察到在这个过程中,它产生出许多字符串,字符串长度是小于等于η,用SLk表示第k个字符串的长度,它表示出现一个以前的字符串中没有出现过的字符时,字符串的字符数。所以当所有的 η个字符都被用到时,总的字符串长度是各个字符串长度之和,即

假定各个字符串的产生是相互独立的,对SLη求期望值,则

第k+1个字符串中包含S各字符的概率可表示为:

因此第k+1个字符串长度的期望值为:

简化后可得:

所以,

简化后可得:

右边的累加和式的每一项都小于1,即

应用于运算符符号可得:

应用于操作数符号可得:

按照Halstead的假设,运算符符号和操作数符号是交替选用的,所以总的字符串长度满足:

取上限作为总的字符串长度的近似值,因此,

这就是Halstead程序长度的表达式,使用这个关系式时,不可将程序长度与程序的语句数相混淆。

在设计开始时,可以使用Halstead程序长度的表达式估计程序的长度。进入概要设计阶段后,设计人员通常已经能够估计出程序需用的运算符符号数,根据需要的输入变量数目,输出变量数目,中间变量数目及常数数目就可以预计出使用的操作数符号数目,因此按照Halstead程序长度的表达式可以预计出程序的长度。5个程序的预计结果如表1所示。

表1 Halstead复杂性度量技术试验结果

1.2 Thayer复杂性度量技术

Thayer认为程序的复杂性是由程序的内在因素决定的,这些因素主要有5个:①逻辑复杂性,与程序的分支、循环语句等有关;②接口复杂性,涉及程序与其他应用程序和系统程序的接口;③计算复杂性,与程序中的赋值语句及其所包含的算数运算符有关;④输入输出复杂性,与程序的输入及输出语句有关;⑤程序的可读性,与程序的注释语句有关。

1.2.1 逻辑复杂性

用LTOT表示每一个分程序或模块的逻辑复杂性,其定义是:

式中,LS为逻辑语句数;EX为可执行语句数;LLOOP为循环复杂性度量;LIF为IF条件语句复杂性度量;LBR为分支复杂性度量。

LLOOP可按下列各式计算:

式中,mi为分程序在第i嵌套层中的循环次数;Wi为权系数;Q为分程序中的最大嵌套层数;系数1 000是按循环在逻辑复杂性LTOT中的相对重要性赋予的。

LIF可按下式计算:

式中,ni为分程序在第i嵌套层中的IF条件语句数;Wi为权系数;Q为分程序中的最大嵌套层数;系数1 000是按IF语句在逻辑复杂性LTOT中的相对重要性赋予的。

LBR可按下式计算:

式中,NBR是分程序中的分支数;系数0.001是按逻辑复杂性分支中分支系数的相对重要性赋予的。

1.2.2 接口复杂性

接口复杂性用CINF表示,其定义是:

式中,AP为分程序与应用程序接口数;SYS为分程序与系统程序接口数,系数0.5是用来反映系统程序接口与应用程序接口的相对重要性。

1.2.3 计算复杂性

计算复杂性用CC表示,其定义是:

式中,CS为程序中计算语句数;∑CS为系统中各个分程序的计算语句之和;∑LTOT为系统中各个分程序的逻辑复杂性之和。

1.2.4 输入输出复杂性

输入输出复杂性用CI/O表示,其定义是:

式中,SI/O为分程序中的输入输出语句数;∑SI/O为系统中各个分程序的输入输出语句之和。

1.2.5 可读性

可读性用UREAD表示,UREAD实际上是一个非复杂性度量,因为程序的可读性越高,复杂性越小,其定义是:

式中,TS为程序中可执行语句和非执行语句之和,不包括注释语句;COM为注释语句数。

1.2.6 分程序复杂性

在定义了分程序复杂性的5个子度量之后,用CTOT表示分程序复杂性,其定义是:

式中,包括了0.1,0.2,0.4,-0.1四个权系数,用来权衡各个子度量对程序复杂性影响的程度;UREAD的权系数取负值是由可读性的特殊属性决定的。

1.2.7 复杂性与软件错误的关系

Thayer假设软件错误数与程序复杂性是线性相关的。这个假设是否合理需要通过试验来验证。做了3个试验,试验分析了A、B、C、D和E5个分系统,第1个试验是用分程序复杂性度量CTOT与程序错误数作回归直线;第2个试验是用逻辑复杂性度量LTOT与程序错误数作回归直线;第3个试验试是在CTOT中删去LTOT项后,与程序错误数作回归直线。试验结果如表2所示,作为近似分析,软件错误数与程序复杂性线性相关的假设在一定范围内是可以采用的。

表2 软件错误数与程序复杂性线性相关试验结果

1.3 McCabe复杂性度量技术

在构造程序流程图时,需要标识出1个起点和1个终点,从起点出发引1条有向弧,连接程序的第1个处理步骤节点,称为入口点,简单程序的入口点只有1个,大多数程序的入口点不止1个,这样的程序流程图应从起点出发引若干条有向弧。对程序中最后处理的语句节点称为出口点,从出口点用1条有向弧通向终点。许多程序的出口点不止1个,都要用有向弧与图的终点相连接。程序中顺序执行的无分支语句,可以用1个节点来表示,这样的简化不会影响回路数的计算,反而使计算变得更简单。程序执行到IF THEN ELSE语句时,将产生分支,在程序流程图上要用相应的有分支的有向弧来表示。

为了将图论中的复杂性度量用于程序的复杂性度量,必须保证程序流图是强连接的,为此可用虚线画1条从终端出发,与起点相连的有向弧,这时网络中的任何1个节点,至少存在1条通路通向其他任意一个节点,因而满足了图论中强连接的条件,程序的复杂性可以用V(G)=m-n+1表示,m为图中弧的数目,n为节点数,该式称为程序的循环复杂性度量,又称为McCabe复杂性度量。

关于循环复杂性度量,McCabe认为主要用途是反映程序质量的好坏,他指出所有采用从顶向下结构设计的模块的V(G)都小于或等于10;他发现循环复杂性大的程序通常也是惯于出错的程序。

2 复杂性与软件可靠性指标分配

为了使可靠性分配合理和可行,从工程上考虑,必须处理好3个方面的问题:分系统的重要程度、分系统的调用状况和分系统的复杂性系数。

2.1 分系统的重要程度

分系统的重要程度是指分系统发生失效后,对系统功能影响的程度。分系统k的重要程度可用重要度系数Uk表示,Uk的数值可通过工程分析确定。如果分系统k发生失效后将使系统失效或造成更严重的后果,则Uk取值为1;如果分系统k发生失效后,只引起较轻的损失,Uk取值可小于1。

2.2 分系统的调用状况

软件在运行时,各个分系统只能逐个调用,在系统总的运行时间中,各个分系统的运行时间互不相同,用调用系数Ik表示分系统k的调用状况,可计算为:

式中,Wk为第k个分系统被调用的次数。在设计的早期根据经验估计出各个分系统的调用次数就可确定调用系数。

2.3 分系统的复杂性系数

软件可靠性分配中分系统的复杂性系数Ck的确定方法是借鉴软件复杂性度量的概念,将各个分系统的复杂性度量经过变换得出分系统的复杂性系数。用CXk表示第k个模块的复杂性度量,它可以是Halstead度量、McCabe度量、Thayer度量或其他的度量。用于可靠性指标分配的复杂性系数为:

2.4 可靠性指标分配

在综合考虑了分系统的重要度、调用状况和复杂性后,分系统k应分配的失效率¯λk的计算式为:

式中,λs为系统的失效率指标。该式适用于软件可靠性分配的基本关系式,体现了对复杂性大的分系统分配的失效率大一些,对于重要程度大的和调用较频繁的分系统,分配的失效率小一些。

3 结束语

在系统开发早期,分析人员掌握的信息非常有限,这时可以对各分系统的指令数做出粗略估计,用指令计数法作为复杂性度量进行可靠性指标分配,在开发过程进入概要设计阶段,设计人员掌握了各个分系统使用的运算符和操作数的信息时,可以用Halstead复杂性度量对预分配加以调整。Halstead复杂性度量显然比指令计数法更能反应程序的特征,经过调整的复杂性系数及可靠性指标分配值也更合理。随着设计的深入,Thayer复杂性度量、McCabe复杂性度量及节点复杂性度量都可选用。

[1]蔡开元.软件可靠性工程基础[M].北京:清华大学出版社,1995.

[2]黄锡滋.软件的可靠性与安全性[M].北京:科学出版社,1993.