秦振華,牟永敏

(北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院,北京 100101)

0 概述

軟件復(fù)雜性主要表現(xiàn)在程序的復(fù)雜性,即模塊內(nèi)程序的復(fù)雜性[1]。常見(jiàn)的定量度量軟件復(fù)雜性的方法有代碼行度量法、McCabe度量法和Halstead度量法。

McCabe度量法根據(jù)程序控制流的復(fù)雜程度定量度量程序復(fù)雜程度,這樣度量出的結(jié)果稱(chēng)為程序的環(huán)形復(fù)雜度。在軟件測(cè)試中,環(huán)形復(fù)雜度用于衡量一個(gè)模塊判定結(jié)構(gòu)的復(fù)雜程度,數(shù)量上表現(xiàn)為獨(dú)立路徑條數(shù),即合理的預(yù)防錯(cuò)誤所需測(cè)試的最少路徑條數(shù),這是為確保所有語(yǔ)句至少執(zhí)行一次而必須進(jìn)行測(cè)試的數(shù)量的上界,也可以理解為覆蓋所有的可能情況最少使用的測(cè)試用例數(shù)[2-4]。在通常情況下,程序環(huán)形復(fù)雜度值越大,說(shuō)明程序判斷邏輯越復(fù)雜,越容易出錯(cuò),且軟件難以測(cè)試與維護(hù)。大量研究和經(jīng)驗(yàn)表明,環(huán)形復(fù)雜度與軟件模塊中的錯(cuò)誤緊密相關(guān),假如一個(gè)模塊比較復(fù)雜,那么它就容易出錯(cuò),當(dāng)超過(guò)了度量的閾值(通常是10),模塊中的錯(cuò)誤數(shù)量也會(huì)隨之急劇增長(zhǎng)[5-8]。

目前,計(jì)算程序環(huán)形復(fù)雜度的方法有2種:一種是根據(jù)控制流圖人工計(jì)算出環(huán)形復(fù)雜度,當(dāng)程序比較復(fù)雜時(shí)容易產(chǎn)生錯(cuò)誤;另一種是采用工具自動(dòng)計(jì)算,如SourceMonitor,計(jì)算速度快,但在某些復(fù)雜條件下得出的環(huán)形復(fù)雜度不夠準(zhǔn)確。

針對(duì)上述問(wèn)題,本文通過(guò)對(duì)源程序進(jìn)行預(yù)處理,提取程序中含有控制流信息的關(guān)鍵語(yǔ)句,實(shí)現(xiàn)程序環(huán)形復(fù)雜度的自動(dòng)化計(jì)算。

1 相關(guān)技術(shù)

1.1 控制流圖

控制流圖(Control Flow Graph,CFG)是一個(gè)有向圖G=(V,E),其中,V是控制流節(jié)點(diǎn)的集合,E是有向邊的集合。一個(gè)控制流圖有一個(gè)唯一的入口節(jié)點(diǎn)(其入度為0)和一個(gè)唯一的出口節(jié)點(diǎn)(其出度為0)?？刂屏鲌D中的節(jié)點(diǎn)V代表程序的語(yǔ)句或表達(dá)式,有向邊E表示語(yǔ)句間的執(zhí)行關(guān)系。令(x,y)∈E,表示控制流圖中的邊x→y,稱(chēng)x是y的前驅(qū),y是x的后繼。

控制流圖中的節(jié)點(diǎn)可分為2種類(lèi)型:一種是塊結(jié)構(gòu),即把程序劃分為塊,塊中的語(yǔ)句是連續(xù)的,且只包含簡(jiǎn)單語(yǔ)句,不包含分支和循環(huán)等引起程序執(zhí)行順序改變的語(yǔ)句;另一種是程序的每一條語(yǔ)句都單獨(dú)地看成一個(gè)控制流節(jié)點(diǎn)[9-13]。本文繪制的控制流圖節(jié)點(diǎn)采用第一種類(lèi)型,并且以程序的行號(hào)來(lái)表示程序的控制流節(jié)點(diǎn)。

1.2 McCabe度量法

計(jì)算程序的環(huán)形復(fù)雜度有3種方法,以圖1所示控制流圖為例。

圖1 控制流圖

3種方法的具體描述如下:

1)給定控制流圖G的環(huán)形復(fù)雜度CC(G),控制流圖中區(qū)域的數(shù)量F(僅考慮區(qū)域個(gè)數(shù),不考慮邊的方向)。圖中區(qū)域數(shù)量為4(R1、R2、R3、R4),則CC(G)=F=4。

2)給定控制流圖G的環(huán)形復(fù)雜度CC(G),定義為CC(G)=E-N+2,E是控制流圖中邊的數(shù)量,N是控制流圖中節(jié)點(diǎn)的數(shù)量。圖中邊的數(shù)量為E=10,節(jié)點(diǎn)的數(shù)量為N=8,則CC(G)=10-8+2=4。

3)給定控制流圖G的環(huán)形復(fù)雜度CC(G),定義為CC(G)=P+1,P是控制流圖中判定節(jié)點(diǎn)的數(shù)量,判定節(jié)點(diǎn)是只包含一個(gè)條件的節(jié)點(diǎn),從每一個(gè)判定節(jié)點(diǎn)發(fā)出2條或多條邊。圖中判定節(jié)點(diǎn)的數(shù)量為P=3,3個(gè)判定節(jié)點(diǎn)為4、6、8,則CC(G)=3+1=4。

1.3 問(wèn)題分解

本文針對(duì)C語(yǔ)言程序研究環(huán)形復(fù)雜度的自動(dòng)化計(jì)算,首先分析其結(jié)構(gòu)特點(diǎn)。C語(yǔ)言程序中的語(yǔ)句分為控制語(yǔ)句、函數(shù)調(diào)用語(yǔ)句、表達(dá)式語(yǔ)句、空語(yǔ)句和復(fù)合語(yǔ)句共5種,其中,控制語(yǔ)句分為9種,分別是if-else條件語(yǔ)句、for循環(huán)語(yǔ)句、while循環(huán)語(yǔ)句、do-while循環(huán)語(yǔ)句、continue語(yǔ)句、break語(yǔ)句、switch多分支選擇語(yǔ)句、return語(yǔ)句和goto語(yǔ)句[14-15]。在這里,將if-else語(yǔ)句、if-else if語(yǔ)句、switch-case語(yǔ)句和包含三目運(yùn)算符的語(yǔ)句稱(chēng)為分支語(yǔ)句,for語(yǔ)句、while語(yǔ)句和do-while語(yǔ)句稱(chēng)為循環(huán)語(yǔ)句,分支語(yǔ)句和循環(huán)語(yǔ)句將對(duì)應(yīng)于控制流圖中的判定節(jié)點(diǎn)。因此,可以借助程序中的分支和循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)環(huán)形復(fù)雜度的計(jì)算。當(dāng)程序中分支語(yǔ)句或者循環(huán)語(yǔ)句的判別條件為復(fù)合條件時(shí),將復(fù)合條件分解成單個(gè)條件后,再進(jìn)行環(huán)形復(fù)雜度的計(jì)算。下面將分情況討論C語(yǔ)言程序中分支語(yǔ)句和循環(huán)語(yǔ)句對(duì)程序環(huán)形復(fù)雜度的影響。

1)if-else語(yǔ)句

當(dāng)if語(yǔ)句中只有1個(gè)判別條件時(shí),當(dāng)前語(yǔ)句對(duì)應(yīng)的判定節(jié)點(diǎn)的數(shù)量等于1;當(dāng)if語(yǔ)句中有多個(gè)判別條件時(shí),當(dāng)前語(yǔ)句對(duì)應(yīng)的判定節(jié)點(diǎn)的數(shù)量等于if語(yǔ)句中判別條件的個(gè)數(shù)。

2)if-else if語(yǔ)句

對(duì)于if-else if語(yǔ)句,除了考慮if語(yǔ)句的情況外,還需要考慮else if語(yǔ)句的情況,處理方法和if-else語(yǔ)句的處理方法相同,當(dāng)前語(yǔ)句對(duì)應(yīng)的判定節(jié)點(diǎn)的數(shù)量等于判別條件的個(gè)數(shù)。

3)包含三目運(yùn)算符的語(yǔ)句

由于包含三目運(yùn)算符的語(yǔ)句,也是一種特殊的條件語(yǔ)句,因此其處理方法和if-else語(yǔ)句的處理方法一樣,其對(duì)應(yīng)的判定節(jié)點(diǎn)的數(shù)量等于語(yǔ)句中判別條件的個(gè)數(shù)。

4)switch-case語(yǔ)句

對(duì)于switch-case而言,有沒(méi)有default語(yǔ)句對(duì)于程序環(huán)形復(fù)雜度的計(jì)算沒(méi)有影響,在一般情況下,判定節(jié)點(diǎn)的數(shù)量等于case的個(gè)數(shù)。由于switch-case不用像if-else if那樣遍歷條件分支直到命中條件,而只需訪(fǎng)問(wèn)對(duì)應(yīng)索引號(hào)的表項(xiàng)從而達(dá)到定位分支的目的。具體地說(shuō),switch-case會(huì)生成一份大小(表項(xiàng)數(shù))為最大case常量+1的跳表,程序首先判斷switch變量是否大于最大case常量,若大于,則跳到default分支處理;否則,取得索引號(hào)為switch變量大小的跳表項(xiàng)的地址(即跳表的起始地址+表項(xiàng)大小×索引號(hào)),程序接著跳到此地址執(zhí)行,到此完成了分支的跳轉(zhuǎn)。所以,即使case中沒(méi)有break語(yǔ)句,也不會(huì)影響產(chǎn)生的分支數(shù),對(duì)程序環(huán)形復(fù)雜度的計(jì)算也不會(huì)產(chǎn)生影響。但是存在一種特殊情況,即多個(gè)case相連,此時(shí)需要把多個(gè)相連的case當(dāng)成一個(gè)判定節(jié)點(diǎn)進(jìn)行計(jì)算,以文獻(xiàn)[2]中的例子加以說(shuō)明,如圖2所示。

圖2 多個(gè)case相連的情況

5)while語(yǔ)句

在一個(gè)循環(huán)結(jié)構(gòu)中,循環(huán)條件表達(dá)式和循環(huán)結(jié)束條件共同決定程序的最終走向,結(jié)合這一特點(diǎn),對(duì)于while循環(huán)語(yǔ)句,可以分5種情況進(jìn)行討論:

(1)條件表達(dá)式永真,這里只考慮while(1)這種形式的永真,但是有循環(huán)結(jié)束條件,此時(shí)while語(yǔ)句不是判定節(jié)點(diǎn),如圖3所示。

圖3 while語(yǔ)句的特殊形式

在圖3中,第4行和第6行語(yǔ)句合并為一個(gè)節(jié)點(diǎn),此時(shí)控制流圖中只有一個(gè)判定節(jié)點(diǎn),這與平時(shí)遇見(jiàn)的情況有所不同,需要特殊處理。

(2)條件表達(dá)式永真,但是無(wú)循環(huán)結(jié)束條件,即所謂的死循環(huán),此時(shí)while語(yǔ)句是判定節(jié)點(diǎn)。

(3)條件表達(dá)式永假,這里只考慮while(0)這種形式的永假,此時(shí)循環(huán)體內(nèi)的所有判定節(jié)點(diǎn)都不需要計(jì)算,包括while自己。

(4)條件表達(dá)式非永真永假,并且是單個(gè)條件,此時(shí)while語(yǔ)句相當(dāng)于一個(gè)判定節(jié)點(diǎn)。

(5)條件表達(dá)式非永真永假,并且是復(fù)合條件,此時(shí)while語(yǔ)句對(duì)應(yīng)判定節(jié)點(diǎn)的數(shù)量等于while語(yǔ)句中判別條件的個(gè)數(shù)。

6)for語(yǔ)句

for語(yǔ)句的處理方法和while語(yǔ)句的處理方法一樣。

7)do-while語(yǔ)句

do-while語(yǔ)句的處理方法和while語(yǔ)句的處理方法基本一致,唯一的區(qū)別是當(dāng)條件表達(dá)式永假時(shí),while語(yǔ)句的循環(huán)體內(nèi)的所有判定節(jié)點(diǎn)都不需要計(jì)算,而do-while語(yǔ)句的循環(huán)體內(nèi)的判定節(jié)點(diǎn)需要計(jì)算。

1.4 代碼度量工具

環(huán)形復(fù)雜度是代碼復(fù)雜度的一個(gè)指示器,可以利用一些著名的開(kāi)放源碼工具計(jì)算環(huán)形復(fù)雜度,比如PMD、CheckStyle和JavaNCSS,但是這些工具只是針對(duì)Java程序的,OCLint、Testwell CMT++、Understand、SourceMonitor等工具可以度量C程序的環(huán)形復(fù)雜度。在實(shí)驗(yàn)部分,借助于后2種工具和本文提出的方法進(jìn)行比較。

Understand是一個(gè)SciTools發(fā)行的、商用的靜態(tài)分析工具,可以維護(hù)、測(cè)量和分析源代碼。該工具能夠分析14種語(yǔ)言,包括C/C++、Java、FORTRAN和一些Web編程語(yǔ)言,例如PHP,并且適用于大部分操作系統(tǒng),包括Solaris。該工具可以對(duì)整個(gè)項(xiàng)目的結(jié)構(gòu)、度量值進(jìn)行分析并輸出報(bào)表,能夠?qū)Υa生成多種圖,包括控制流圖、依賴(lài)關(guān)系圖、UML類(lèi)圖等。

SourceMonitor是一款免費(fèi)的軟件,運(yùn)行在Windows平臺(tái)下。它可對(duì)多種語(yǔ)言寫(xiě)的代碼進(jìn)行度量,包括C、C++、C#、Java、VB、Delphi和HTML,并且針對(duì)不同的語(yǔ)言,輸出不同的代碼度量值。對(duì)于C程序,提供了總行數(shù)、語(yǔ)句數(shù)目、分支語(yǔ)句比例、注釋比例、函數(shù)數(shù)目、平均每個(gè)函數(shù)包含的語(yǔ)句數(shù)目、函數(shù)環(huán)形復(fù)雜度和函數(shù)深度等度量值。

2 系統(tǒng)分析與設(shè)計(jì)

本文提出的研究方法可分為3個(gè)階段:源代碼的預(yù)處理,控制流信息的提取,環(huán)形復(fù)雜度的自動(dòng)化計(jì)算。其中,采用了狀態(tài)機(jī)編程思想刪掉源程序中的注釋來(lái)實(shí)現(xiàn)源代碼的預(yù)處理,利用模式匹配的規(guī)則來(lái)提取含控制流信息的關(guān)鍵語(yǔ)句,通過(guò)分情況處理關(guān)鍵語(yǔ)句來(lái)實(shí)現(xiàn)程序環(huán)形復(fù)雜度的自動(dòng)化計(jì)算。

2.1 源代碼預(yù)處理技術(shù)

源代碼的預(yù)處理主要是掃描程序中出現(xiàn)的注釋,并將其刪掉。由于注釋信息對(duì)最后環(huán)形復(fù)雜度的計(jì)算沒(méi)有影響,并且注釋中的某些信息會(huì)干擾接下來(lái)關(guān)鍵語(yǔ)句的提取,因此找出源代碼中的注釋信息,將其從源代碼中刪掉。這里只考慮單行注釋、多行注釋和折行注釋這3種情況,其中,折行注釋是以雙斜杠開(kāi)頭、反斜杠結(jié)尾,很多編輯器高亮都沒(méi)有考慮到這種情況。此處采用了狀態(tài)機(jī)編程思想將源代碼中的注釋刪掉。

2.2 控制流信息的提取

在程序中,分支語(yǔ)句和循環(huán)語(yǔ)句最終對(duì)應(yīng)于控制流圖中的判定節(jié)點(diǎn),因此,如何提取程序中的分支和循環(huán)語(yǔ)句顯得尤為重要。此處通過(guò)模式匹配的方式提取程序中的關(guān)鍵語(yǔ)句,其中模式匹配規(guī)則如表1所示。

表1 模式匹配規(guī)則

表1中的模式匹配規(guī)則共有6種模式,左側(cè)為模式序號(hào),右側(cè)為模式匹配的規(guī)則。由于計(jì)算的是單個(gè)函數(shù)的環(huán)形復(fù)雜度,因此用模式P1匹配程序中的函數(shù)定義,從而開(kāi)啟一個(gè)處理單元。分支語(yǔ)句和循環(huán)語(yǔ)句用模式P2、P3、P4和P5進(jìn)行匹配。其中,模式P2匹配if、for和while語(yǔ)句,模式P3匹配switch-case語(yǔ)句,模式P4匹配包含三目運(yùn)算符的語(yǔ)句,模式P5匹配do-while語(yǔ)句和break語(yǔ)句,匹配break語(yǔ)句是為了后續(xù)判斷當(dāng)循環(huán)結(jié)構(gòu)中無(wú)循環(huán)條件表達(dá)式時(shí),有無(wú)循環(huán)結(jié)束條件。如果循環(huán)體中有循環(huán)結(jié)束條件break語(yǔ)句,那么循環(huán)可以正常結(jié)束,此時(shí)的循環(huán)語(yǔ)句不是判定節(jié)點(diǎn),否則是死循環(huán)結(jié)構(gòu),此時(shí)的循環(huán)語(yǔ)句是判定節(jié)點(diǎn)。模式P6用來(lái)進(jìn)行花括號(hào)匹配,左花括號(hào)對(duì)應(yīng)語(yǔ)句塊的開(kāi)始,右花括號(hào)對(duì)應(yīng)語(yǔ)句塊的結(jié)束,根據(jù)花括號(hào),可以對(duì)源程序進(jìn)行分塊處理。在表1規(guī)則的基礎(chǔ)上,再結(jié)合正則表達(dá)式中的search()方法,就可以將程序中的關(guān)鍵語(yǔ)句信息都提取出來(lái)。

2.3 環(huán)形復(fù)雜度的自動(dòng)化計(jì)算

經(jīng)過(guò)源程序的預(yù)處理和提取關(guān)鍵語(yǔ)句這2步,此時(shí)程序中只剩下分支語(yǔ)句、循環(huán)語(yǔ)句等關(guān)鍵信息,接下來(lái)需要根據(jù)這些關(guān)鍵信息,進(jìn)行程序環(huán)形復(fù)雜度的計(jì)算。在當(dāng)前步的處理中需要注意的是:當(dāng)語(yǔ)句中判別條件是復(fù)合條件時(shí),需要把復(fù)合條件分解成單個(gè)條件進(jìn)行計(jì)算。對(duì)于循環(huán)語(yǔ)句中條件表達(dá)式永真、永假的情況,尤其是當(dāng)條件表達(dá)式永真,但是有break語(yǔ)句可以跳出循環(huán),此時(shí)當(dāng)前循環(huán)語(yǔ)句并不能當(dāng)成判定節(jié)點(diǎn)這種情況,都需要進(jìn)行特殊處理。

鑒于此,在當(dāng)前步驟的算法設(shè)計(jì)中采用自頂向下的分析策略,對(duì)各種情況分別編寫(xiě)相應(yīng)的處理函數(shù),定義一個(gè)棧stack用來(lái)進(jìn)行花括號(hào)匹配,定義一個(gè)變量num用來(lái)記錄最終環(huán)形復(fù)雜度的值,初始值為0,并用flag標(biāo)志來(lái)標(biāo)記循環(huán)語(yǔ)句塊中是否有break語(yǔ)句,flag=0表示沒(méi)有,flag=1表示有,用ok標(biāo)志標(biāo)記if語(yǔ)句塊中是否包含break語(yǔ)句,當(dāng)循環(huán)語(yǔ)句塊中嵌套if語(yǔ)句塊,if語(yǔ)句塊中包含break語(yǔ)句,此時(shí)break語(yǔ)句也可以跳出循環(huán),flag=1。然后,從上往下掃描源程序,如果當(dāng)前語(yǔ)句中包含“{”,則進(jìn)行入棧操作,stack.push(“{”);若包含“}”,則進(jìn)行出棧操作,stack.pop();若包含“if”關(guān)鍵字、“switch”關(guān)鍵字、“do”關(guān)鍵字、“for”關(guān)鍵字、“while”關(guān)鍵字、三目運(yùn)算符,則相應(yīng)地調(diào)用count_if()、count_case()、count_do()、count_for()、count_while()、count_three()方法,通過(guò)對(duì)應(yīng)的方法計(jì)算代碼塊中相應(yīng)代碼的環(huán)形復(fù)雜度,并把計(jì)算得到的結(jié)果加到變量num中去,接著進(jìn)行下面語(yǔ)句的處理,直到程序結(jié)束。這樣,最終程序環(huán)形復(fù)雜度的值便等于變量num的值。其中,計(jì)算while語(yǔ)句塊中相應(yīng)代碼的環(huán)形復(fù)雜度的算法如下。

算法1cout_while

輸入程序的行號(hào)值

輸出環(huán)形復(fù)雜度值

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中,對(duì)于while語(yǔ)句塊的處理,需要考慮條件表達(dá)式永真、永假和非永真永假這3種情況,語(yǔ)句塊的開(kāi)始和結(jié)束對(duì)應(yīng)棧的入棧和出棧操作,當(dāng)棧中元素個(gè)數(shù)為0時(shí),標(biāo)志著當(dāng)前語(yǔ)句塊中內(nèi)容處理完畢。對(duì)于條件表達(dá)式永假的情況,直接順序讀取語(yǔ)句塊中的內(nèi)容即可;對(duì)于永真的情況,需要根據(jù)flag的值來(lái)判斷sum的值需不需要加1;對(duì)于非永真永假的情況,sum需要加的值等于while語(yǔ)句中條件的個(gè)數(shù)。

3 實(shí)驗(yàn)評(píng)測(cè)

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)所用操作系統(tǒng)為64位Windows 7旗艦版Service Pack 1,內(nèi)存為4 GB,處理器為Intel(R) CoreTMi7-2820QM CPU @ 2.30 GHz。

3.2 測(cè)試用例

實(shí)驗(yàn)中用的測(cè)試用例采用了文獻(xiàn)[15]中的程序,該程序涉及到了注釋、if-else語(yǔ)句、switch-case語(yǔ)句、while語(yǔ)句、三目運(yùn)算符、單個(gè)判別條件和復(fù)合條件,具有一定的代表性。具體測(cè)試用例如下所示。

int main()

{

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

2. char operate,flag;

3. while(1)

{

4. flag=getch();

5. printf("第%d次運(yùn)算 ",++count);

//輸入的字符不是小寫(xiě)字母,退出程序

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

{

//輸入運(yùn)算數(shù)和運(yùn)算符

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("結(jié)果為:%d,%d ",max,c);

}

else

{

21. break;

}

}

22. return 0;

}

為了能更好地驗(yàn)證本文提出的環(huán)形復(fù)雜度自動(dòng)化計(jì)算方法,同時(shí)實(shí)現(xiàn)控制流圖的自動(dòng)生成,采用如下方法:利用GCC編譯源代碼生成中間文件,提取并分析中間文件的語(yǔ)句塊信息,找出語(yǔ)句塊之間的關(guān)系,用替換的方法把語(yǔ)句塊之間的關(guān)系轉(zhuǎn)換成行號(hào)之間的關(guān)系,并把結(jié)果輸出到一個(gè).dot文件中去,最后使用WinGraphviz這個(gè)COM組件把最終結(jié)果以控制流圖的形式展示出來(lái)[16-18]。

本文系統(tǒng)在自動(dòng)生成控制流圖時(shí),對(duì)于程序中判別條件是復(fù)合條件的情況,將復(fù)合條件拆成單個(gè)條件,并用“行號(hào)_條件標(biāo)號(hào)”這種形式進(jìn)行表示,例如“6_1”,表示第6行第1個(gè)判別條件。對(duì)于三目運(yùn)算符來(lái)說(shuō),執(zhí)行的語(yǔ)句用“行號(hào)_語(yǔ)句塊標(biāo)號(hào)”這種形式來(lái)表示,例如“8_01”,表示執(zhí)行第8行第1個(gè)語(yǔ)句塊中的語(yǔ)句。上述測(cè)試用例所對(duì)應(yīng)的控制流圖如圖4所示。

圖4 測(cè)試用例對(duì)應(yīng)的控制流圖

測(cè)試用例中if(flag>=‘a(chǎn)’&& flag<=‘z’)語(yǔ)句的判別條件是復(fù)合條件,拆成2個(gè)判定節(jié)點(diǎn),max=a>b ? a:b;語(yǔ)句包含三目運(yùn)算符,判別條件是單個(gè)條件,相當(dāng)于一個(gè)判定節(jié)點(diǎn),switch-case中有2個(gè)case,產(chǎn)生2個(gè)判定節(jié)點(diǎn),再加上嵌套的if(b==0)語(yǔ)句,共產(chǎn)生3個(gè)判定節(jié)點(diǎn),而對(duì)于while(1)這種條件表達(dá)式永真的循環(huán)語(yǔ)句,由于循環(huán)體中存在循環(huán)結(jié)束條件,因此while(1)語(yǔ)句不是判定節(jié)點(diǎn)。綜上所述,測(cè)試用例中共有6個(gè)判定節(jié)點(diǎn),程序的環(huán)形復(fù)雜度為7。

3.3 實(shí)驗(yàn)結(jié)果

根據(jù)圖4可知測(cè)試用例的環(huán)形復(fù)雜度為7,這與圖5得出的實(shí)驗(yàn)結(jié)果一致。所以,本文提出的方法可以準(zhǔn)確地計(jì)算出程序的環(huán)形復(fù)雜度。將系統(tǒng)命名為RcTest工具,與Understand和SourceMonitor工具針對(duì)上述測(cè)試用例計(jì)算得到的結(jié)果進(jìn)行比較,最終結(jié)果如表2所示。

圖5 程序運(yùn)行結(jié)果

工具環(huán)形復(fù)雜度分析RcTest7while(1)語(yǔ)句不是判定節(jié)點(diǎn)Understand7把復(fù)合條件、while(1)語(yǔ)句都當(dāng)成一個(gè)判定節(jié)點(diǎn)SourceMonitor11while(1)、else、default語(yǔ)句都當(dāng)成一個(gè)判定節(jié)點(diǎn)

經(jīng)過(guò)大量實(shí)驗(yàn)得出,Understand和SourceMonitor工具在計(jì)算環(huán)形復(fù)雜度時(shí)與RcTest有如下不同:

1)Understand工具

(1)在生成控制流圖和計(jì)算時(shí),把復(fù)合條件當(dāng)成一個(gè)條件進(jìn)行分析;

(2)像循環(huán)語(yǔ)句中while(1)和while(0)這2種特殊的永真和永假形式,并沒(méi)有被考慮,在控制流圖中會(huì)畫(huà)出while節(jié)點(diǎn),并把while節(jié)點(diǎn)當(dāng)成判定節(jié)點(diǎn)加入到環(huán)形復(fù)雜度中去;

(3)對(duì)于包含三目運(yùn)算符的語(yǔ)句,在控制流圖中當(dāng)成順序語(yǔ)句節(jié)點(diǎn)來(lái)處理,在計(jì)算時(shí),會(huì)當(dāng)成一個(gè)判定節(jié)點(diǎn)進(jìn)行計(jì)算,但是沒(méi)有考慮復(fù)合條件的情況;

(4)對(duì)于switch-case語(yǔ)句,在一般情況下,當(dāng)case語(yǔ)句塊中沒(méi)有break語(yǔ)句時(shí),對(duì)環(huán)形復(fù)雜度的計(jì)算無(wú)影響,但是一旦出現(xiàn)多個(gè)case相連這種特殊情況,在生成控制流圖時(shí),會(huì)把多個(gè)相連的case當(dāng)成一個(gè)節(jié)點(diǎn),在計(jì)算時(shí),統(tǒng)計(jì)的是case的個(gè)數(shù)。

2)SourceMonitor工具

(1)將復(fù)合條件拆成多個(gè)單條件進(jìn)行計(jì)算,但是在處理包含三目運(yùn)算符的語(yǔ)句時(shí),沒(méi)有考慮復(fù)合條件,只當(dāng)成一個(gè)判定節(jié)點(diǎn);

(2)對(duì)于if-else結(jié)構(gòu)的語(yǔ)句,會(huì)把else當(dāng)成一個(gè)判定節(jié)點(diǎn);

(3)沒(méi)有考慮循環(huán)語(yǔ)句中永真和永假的特殊形式;

(4)對(duì)于switch-case語(yǔ)句,在一般情況下,不管有沒(méi)有default語(yǔ)句,判定節(jié)點(diǎn)數(shù)等于case的個(gè)數(shù)+1。但是當(dāng)case語(yǔ)句塊中沒(méi)有break語(yǔ)句時(shí),當(dāng)前case語(yǔ)句不當(dāng)成判定節(jié)點(diǎn),對(duì)于多個(gè)case相連的情況,會(huì)把多個(gè)相連的case當(dāng)成一個(gè)判定節(jié)點(diǎn)進(jìn)行計(jì)算。

通過(guò)比較可知,系統(tǒng)在計(jì)算環(huán)形復(fù)雜度時(shí),相對(duì)于Understand和SourceMonitor工具更加準(zhǔn)確。

下面分析3種工具在計(jì)算時(shí)間開(kāi)銷(xiāo)上(單位是秒)的差別,分別以104、105、106行代碼為例進(jìn)行比較,最終結(jié)果如表3所示。

表3 3種工具的計(jì)算時(shí)間開(kāi)銷(xiāo) s

由表3可知,RcTest工具在計(jì)算效率上比SourceMonitor略高。由于Understand工具會(huì)生成控制流圖等額外信息,因此時(shí)間開(kāi)銷(xiāo)較大,但是產(chǎn)生的信息比較齊全。

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

環(huán)形復(fù)雜度是軟件難度度量的一個(gè)重要指標(biāo),本文通過(guò)提取源程序中含有控制流信息的關(guān)鍵語(yǔ)句,對(duì)其進(jìn)行分析處理,用于實(shí)現(xiàn)環(huán)形復(fù)雜度的自動(dòng)化計(jì)算。在這種方法下,無(wú)需知道源程序的控制流圖,而且通過(guò)去掉源程序中一些無(wú)關(guān)緊要的信息,只留下影響環(huán)形復(fù)雜度的關(guān)鍵信息,進(jìn)而可以高效、準(zhǔn)確地計(jì)算出程序的環(huán)形復(fù)雜度,可操作性更強(qiáng),更簡(jiǎn)單,節(jié)約了測(cè)試時(shí)間,降低了測(cè)試成本。下一步將完善該工具的擴(kuò)展性,使其可以計(jì)算其他語(yǔ)言編寫(xiě)的程序的環(huán)形復(fù)雜度。