程序復(fù)雜性度量技術(shù)分析

孔慶玲,胡志軍,劉 英,馮 陽(yáng)

(中國(guó)電子科技集團(tuán)公司第五十四研究所,河北石家莊050081)

0 引言

軟件越復(fù)雜,一方面在開(kāi)發(fā)和維護(hù)過(guò)程中所消耗的資源也越多,所以軟件的復(fù)雜性可以作為軟件所需資源投入量的一個(gè)間接度量;另一方面在設(shè)計(jì)中引入錯(cuò)誤的可能性也越大,這是一種合乎邏輯的推理,也是一個(gè)為實(shí)驗(yàn)驗(yàn)證的事實(shí)。盡管軟件復(fù)雜性與軟件中的錯(cuò)誤數(shù)未必呈現(xiàn)出簡(jiǎn)單的正比關(guān)系,但是存在這種正相趨勢(shì)是肯定無(wú)疑的。軟件不可靠的根本原因是軟件中存在錯(cuò)誤,所以軟件復(fù)雜性可以作為軟件可靠性的一種間接度量。復(fù)雜性度量是軟件開(kāi)發(fā)過(guò)程中有應(yīng)用前景的一個(gè)度量。借助這個(gè)度量,設(shè)計(jì)人員在接受設(shè)計(jì)任務(wù)之初,可以從已有的性質(zhì)相似的程序中獲得經(jīng)驗(yàn)數(shù)據(jù),對(duì)現(xiàn)在所面臨問(wèn)題的復(fù)雜程度做出判斷,借助于復(fù)雜性度量還可以對(duì)若干設(shè)計(jì)方案的困難程度加以比較。

1 技術(shù)分析

目前比較流行的有3種程序復(fù)雜性度量方法:Halstead、McCabe和 Thayer。Halstead使用統(tǒng)計(jì)的方法研究程序的復(fù)雜性,按照程序中的運(yùn)算符和操作數(shù)的總數(shù)對(duì)程序的復(fù)雜性加以度量。McCabe以程序邏輯流程圖的分析為基礎(chǔ),建立復(fù)雜性的度量。Thayer按程序的邏輯關(guān)系、接口、運(yùn)算特征和輸入/輸出的特點(diǎn)來(lái)度量程序的復(fù)雜性。下面就這3種復(fù)雜性度量技術(shù)分別進(jìn)行分析。

1.1 Halstead復(fù)雜性度量技術(shù)

Halstead認(rèn)為程序的復(fù)雜性可以用程序的運(yùn)算符總數(shù)與操作數(shù)總數(shù)之和來(lái)反映,這個(gè)總數(shù)和稱為Halstead程序長(zhǎng)度。為了得出Halstead程序長(zhǎng)度的表達(dá)式,可以把程序視為由運(yùn)算符、操作數(shù)交替組成的符號(hào)序列,在這些符號(hào)序列中,有 η1個(gè)不同的運(yùn)算符符號(hào)和 η2個(gè)不同的操作數(shù)符號(hào)。屬于運(yùn)算符符號(hào)的有+、-、＞、＜、IF THEN ELSE和DO WHILE等,屬于操作數(shù)符號(hào)的有變量、常數(shù)、字符串變量和字符串常數(shù)等,η1與η2的總和構(gòu)成程序的詞匯表。注釋和其他非執(zhí)行語(yǔ)句不屬于詞匯表的范圍。

Halstead將程序的生成等價(jià)于如下的隨機(jī)過(guò)程,首先從詞匯表中隨機(jī)選擇一個(gè)運(yùn)算符符號(hào),然后從詞匯表中隨機(jī)選擇一個(gè)操作數(shù)符號(hào),這個(gè)交替過(guò)程一直持續(xù)下去,直到最后一個(gè)從未用過(guò)的運(yùn)算符符號(hào)或操作數(shù)符號(hào)被選中時(shí),程序的生成才結(jié)束,這時(shí)字符串長(zhǎng)度的期望值可以按統(tǒng)計(jì)規(guī)律求出。

為了簡(jiǎn)化分析過(guò)程,首先研究由 η個(gè)符號(hào)組成的詞匯表中的字符串的生成過(guò)程?？梢杂^察到在這個(gè)過(guò)程中,它產(chǎn)生出許多字符串,字符串長(zhǎng)度是小于等于η,用SLk表示第k個(gè)字符串的長(zhǎng)度,它表示出現(xiàn)一個(gè)以前的字符串中沒(méi)有出現(xiàn)過(guò)的字符時(shí),字符串的字符數(shù)。所以當(dāng)所有的 η個(gè)字符都被用到時(shí),總的字符串長(zhǎng)度是各個(gè)字符串長(zhǎng)度之和,即

假定各個(gè)字符串的產(chǎn)生是相互獨(dú)立的,對(duì)SLη求期望值,則

第k+1個(gè)字符串中包含S各字符的概率可表示為:

因此第k+1個(gè)字符串長(zhǎng)度的期望值為:

簡(jiǎn)化后可得:

所以,

簡(jiǎn)化后可得:

右邊的累加和式的每一項(xiàng)都小于1,即

應(yīng)用于運(yùn)算符符號(hào)可得:

應(yīng)用于操作數(shù)符號(hào)可得:

按照Halstead的假設(shè),運(yùn)算符符號(hào)和操作數(shù)符號(hào)是交替選用的,所以總的字符串長(zhǎng)度滿足:

取上限作為總的字符串長(zhǎng)度的近似值,因此,

這就是Halstead程序長(zhǎng)度的表達(dá)式,使用這個(gè)關(guān)系式時(shí),不可將程序長(zhǎng)度與程序的語(yǔ)句數(shù)相混淆。

在設(shè)計(jì)開(kāi)始時(shí),可以使用Halstead程序長(zhǎng)度的表達(dá)式估計(jì)程序的長(zhǎng)度。進(jìn)入概要設(shè)計(jì)階段后,設(shè)計(jì)人員通常已經(jīng)能夠估計(jì)出程序需用的運(yùn)算符符號(hào)數(shù),根據(jù)需要的輸入變量數(shù)目,輸出變量數(shù)目,中間變量數(shù)目及常數(shù)數(shù)目就可以預(yù)計(jì)出使用的操作數(shù)符號(hào)數(shù)目,因此按照Halstead程序長(zhǎng)度的表達(dá)式可以預(yù)計(jì)出程序的長(zhǎng)度。5個(gè)程序的預(yù)計(jì)結(jié)果如表1所示。

表1 Halstead復(fù)雜性度量技術(shù)試驗(yàn)結(jié)果

1.2 Thayer復(fù)雜性度量技術(shù)

Thayer認(rèn)為程序的復(fù)雜性是由程序的內(nèi)在因素決定的,這些因素主要有5個(gè):①邏輯復(fù)雜性,與程序的分支、循環(huán)語(yǔ)句等有關(guān);②接口復(fù)雜性,涉及程序與其他應(yīng)用程序和系統(tǒng)程序的接口;③計(jì)算復(fù)雜性,與程序中的賦值語(yǔ)句及其所包含的算數(shù)運(yùn)算符有關(guān);④輸入輸出復(fù)雜性,與程序的輸入及輸出語(yǔ)句有關(guān);⑤程序的可讀性,與程序的注釋語(yǔ)句有關(guān)。

1.2.1 邏輯復(fù)雜性

用LTOT表示每一個(gè)分程序或模塊的邏輯復(fù)雜性,其定義是:

式中,LS為邏輯語(yǔ)句數(shù);EX為可執(zhí)行語(yǔ)句數(shù);LLOOP為循環(huán)復(fù)雜性度量;LIF為IF條件語(yǔ)句復(fù)雜性度量;LBR為分支復(fù)雜性度量。

LLOOP可按下列各式計(jì)算:

式中,mi為分程序在第i嵌套層中的循環(huán)次數(shù);Wi為權(quán)系數(shù);Q為分程序中的最大嵌套層數(shù);系數(shù)1 000是按循環(huán)在邏輯復(fù)雜性LTOT中的相對(duì)重要性賦予的。

LIF可按下式計(jì)算:

式中,ni為分程序在第i嵌套層中的IF條件語(yǔ)句數(shù);Wi為權(quán)系數(shù);Q為分程序中的最大嵌套層數(shù);系數(shù)1 000是按IF語(yǔ)句在邏輯復(fù)雜性LTOT中的相對(duì)重要性賦予的。

LBR可按下式計(jì)算:

式中,NBR是分程序中的分支數(shù);系數(shù)0.001是按邏輯復(fù)雜性分支中分支系數(shù)的相對(duì)重要性賦予的。

1.2.2 接口復(fù)雜性

接口復(fù)雜性用CINF表示,其定義是:

式中,AP為分程序與應(yīng)用程序接口數(shù);SYS為分程序與系統(tǒng)程序接口數(shù),系數(shù)0.5是用來(lái)反映系統(tǒng)程序接口與應(yīng)用程序接口的相對(duì)重要性。

1.2.3 計(jì)算復(fù)雜性

計(jì)算復(fù)雜性用CC表示,其定義是:

式中,CS為程序中計(jì)算語(yǔ)句數(shù);∑CS為系統(tǒng)中各個(gè)分程序的計(jì)算語(yǔ)句之和;∑LTOT為系統(tǒng)中各個(gè)分程序的邏輯復(fù)雜性之和。

1.2.4 輸入輸出復(fù)雜性

輸入輸出復(fù)雜性用CI/O表示,其定義是:

式中,SI/O為分程序中的輸入輸出語(yǔ)句數(shù);∑SI/O為系統(tǒng)中各個(gè)分程序的輸入輸出語(yǔ)句之和。

1.2.5 可讀性

可讀性用UREAD表示,UREAD實(shí)際上是一個(gè)非復(fù)雜性度量,因?yàn)槌绦虻目勺x性越高,復(fù)雜性越小,其定義是:

式中,TS為程序中可執(zhí)行語(yǔ)句和非執(zhí)行語(yǔ)句之和,不包括注釋語(yǔ)句;COM為注釋語(yǔ)句數(shù)。

1.2.6 分程序復(fù)雜性

在定義了分程序復(fù)雜性的5個(gè)子度量之后,用CTOT表示分程序復(fù)雜性,其定義是:

式中,包括了0.1,0.2,0.4,-0.1四個(gè)權(quán)系數(shù),用來(lái)權(quán)衡各個(gè)子度量對(duì)程序復(fù)雜性影響的程度;UREAD的權(quán)系數(shù)取負(fù)值是由可讀性的特殊屬性決定的。

1.2.7 復(fù)雜性與軟件錯(cuò)誤的關(guān)系

Thayer假設(shè)軟件錯(cuò)誤數(shù)與程序復(fù)雜性是線性相關(guān)的。這個(gè)假設(shè)是否合理需要通過(guò)試驗(yàn)來(lái)驗(yàn)證。做了3個(gè)試驗(yàn),試驗(yàn)分析了A、B、C、D和E5個(gè)分系統(tǒng),第1個(gè)試驗(yàn)是用分程序復(fù)雜性度量CTOT與程序錯(cuò)誤數(shù)作回歸直線;第2個(gè)試驗(yàn)是用邏輯復(fù)雜性度量LTOT與程序錯(cuò)誤數(shù)作回歸直線;第3個(gè)試驗(yàn)試是在CTOT中刪去LTOT項(xiàng)后,與程序錯(cuò)誤數(shù)作回歸直線。試驗(yàn)結(jié)果如表2所示,作為近似分析,軟件錯(cuò)誤數(shù)與程序復(fù)雜性線性相關(guān)的假設(shè)在一定范圍內(nèi)是可以采用的。

表2 軟件錯(cuò)誤數(shù)與程序復(fù)雜性線性相關(guān)試驗(yàn)結(jié)果

1.3 McCabe復(fù)雜性度量技術(shù)

在構(gòu)造程序流程圖時(shí),需要標(biāo)識(shí)出1個(gè)起點(diǎn)和1個(gè)終點(diǎn),從起點(diǎn)出發(fā)引1條有向弧,連接程序的第1個(gè)處理步驟節(jié)點(diǎn),稱為入口點(diǎn),簡(jiǎn)單程序的入口點(diǎn)只有1個(gè),大多數(shù)程序的入口點(diǎn)不止1個(gè),這樣的程序流程圖應(yīng)從起點(diǎn)出發(fā)引若干條有向弧。對(duì)程序中最后處理的語(yǔ)句節(jié)點(diǎn)稱為出口點(diǎn),從出口點(diǎn)用1條有向弧通向終點(diǎn)。許多程序的出口點(diǎn)不止1個(gè),都要用有向弧與圖的終點(diǎn)相連接。程序中順序執(zhí)行的無(wú)分支語(yǔ)句,可以用1個(gè)節(jié)點(diǎn)來(lái)表示,這樣的簡(jiǎn)化不會(huì)影響回路數(shù)的計(jì)算,反而使計(jì)算變得更簡(jiǎn)單。程序執(zhí)行到IF THEN ELSE語(yǔ)句時(shí),將產(chǎn)生分支,在程序流程圖上要用相應(yīng)的有分支的有向弧來(lái)表示。

為了將圖論中的復(fù)雜性度量用于程序的復(fù)雜性度量,必須保證程序流圖是強(qiáng)連接的,為此可用虛線畫(huà)1條從終端出發(fā),與起點(diǎn)相連的有向弧,這時(shí)網(wǎng)絡(luò)中的任何1個(gè)節(jié)點(diǎn),至少存在1條通路通向其他任意一個(gè)節(jié)點(diǎn),因而滿足了圖論中強(qiáng)連接的條件,程序的復(fù)雜性可以用V(G)=m-n+1表示,m為圖中弧的數(shù)目,n為節(jié)點(diǎn)數(shù),該式稱為程序的循環(huán)復(fù)雜性度量,又稱為McCabe復(fù)雜性度量。

關(guān)于循環(huán)復(fù)雜性度量,McCabe認(rèn)為主要用途是反映程序質(zhì)量的好壞,他指出所有采用從頂向下結(jié)構(gòu)設(shè)計(jì)的模塊的V(G)都小于或等于10;他發(fā)現(xiàn)循環(huán)復(fù)雜性大的程序通常也是慣于出錯(cuò)的程序。

2 復(fù)雜性與軟件可靠性指標(biāo)分配

為了使可靠性分配合理和可行,從工程上考慮,必須處理好3個(gè)方面的問(wèn)題:分系統(tǒng)的重要程度、分系統(tǒng)的調(diào)用狀況和分系統(tǒng)的復(fù)雜性系數(shù)。

2.1 分系統(tǒng)的重要程度

分系統(tǒng)的重要程度是指分系統(tǒng)發(fā)生失效后,對(duì)系統(tǒng)功能影響的程度。分系統(tǒng)k的重要程度可用重要度系數(shù)Uk表示,Uk的數(shù)值可通過(guò)工程分析確定。如果分系統(tǒng)k發(fā)生失效后將使系統(tǒng)失效或造成更嚴(yán)重的后果,則Uk取值為1;如果分系統(tǒng)k發(fā)生失效后,只引起較輕的損失,Uk取值可小于1。

2.2 分系統(tǒng)的調(diào)用狀況

軟件在運(yùn)行時(shí),各個(gè)分系統(tǒng)只能逐個(gè)調(diào)用,在系統(tǒng)總的運(yùn)行時(shí)間中,各個(gè)分系統(tǒng)的運(yùn)行時(shí)間互不相同,用調(diào)用系數(shù)Ik表示分系統(tǒng)k的調(diào)用狀況,可計(jì)算為:

式中,Wk為第k個(gè)分系統(tǒng)被調(diào)用的次數(shù)。在設(shè)計(jì)的早期根據(jù)經(jīng)驗(yàn)估計(jì)出各個(gè)分系統(tǒng)的調(diào)用次數(shù)就可確定調(diào)用系數(shù)。

2.3 分系統(tǒng)的復(fù)雜性系數(shù)

軟件可靠性分配中分系統(tǒng)的復(fù)雜性系數(shù)Ck的確定方法是借鑒軟件復(fù)雜性度量的概念,將各個(gè)分系統(tǒng)的復(fù)雜性度量經(jīng)過(guò)變換得出分系統(tǒng)的復(fù)雜性系數(shù)。用CXk表示第k個(gè)模塊的復(fù)雜性度量,它可以是Halstead度量、McCabe度量、Thayer度量或其他的度量。用于可靠性指標(biāo)分配的復(fù)雜性系數(shù)為:

2.4 可靠性指標(biāo)分配

在綜合考慮了分系統(tǒng)的重要度、調(diào)用狀況和復(fù)雜性后,分系統(tǒng)k應(yīng)分配的失效率ˉλk的計(jì)算式為:

式中,λs為系統(tǒng)的失效率指標(biāo)。該式適用于軟件可靠性分配的基本關(guān)系式,體現(xiàn)了對(duì)復(fù)雜性大的分系統(tǒng)分配的失效率大一些,對(duì)于重要程度大的和調(diào)用較頻繁的分系統(tǒng),分配的失效率小一些。

3 結(jié)束語(yǔ)

在系統(tǒng)開(kāi)發(fā)早期,分析人員掌握的信息非常有限,這時(shí)可以對(duì)各分系統(tǒng)的指令數(shù)做出粗略估計(jì),用指令計(jì)數(shù)法作為復(fù)雜性度量進(jìn)行可靠性指標(biāo)分配,在開(kāi)發(fā)過(guò)程進(jìn)入概要設(shè)計(jì)階段,設(shè)計(jì)人員掌握了各個(gè)分系統(tǒng)使用的運(yùn)算符和操作數(shù)的信息時(shí),可以用Halstead復(fù)雜性度量對(duì)預(yù)分配加以調(diào)整。Halstead復(fù)雜性度量顯然比指令計(jì)數(shù)法更能反應(yīng)程序的特征,經(jīng)過(guò)調(diào)整的復(fù)雜性系數(shù)及可靠性指標(biāo)分配值也更合理。隨著設(shè)計(jì)的深入,Thayer復(fù)雜性度量、McCabe復(fù)雜性度量及節(jié)點(diǎn)復(fù)雜性度量都可選用。

[1]蔡開(kāi)元.軟件可靠性工程基礎(chǔ)[M].北京:清華大學(xué)出版社,1995.

[2]黃錫滋.軟件的可靠性與安全性[M].北京:科學(xué)出版社,1993.