面向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)?？刂屏鲌D中的節點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 結束語

環形復雜度是軟件難度度量的一個重要指標,本文通過提取源程序中含有控制流信息的關鍵語句,對其進行分析處理,用于實現環形復雜度的自動化計算。在這種方法下,無需知道源程序的控制流圖,而且通過去掉源程序中一些無關緊要的信息,只留下影響環形復雜度的關鍵信息,進而可以高效、準確地計算出程序的環形復雜度,可操作性更強,更簡單,節約了測試時間,降低了測試成本。下一步將完善該工具的擴展性,使其可以計算其他語言編寫的程序的環形復雜度。