基于控制流圖的代碼自動測試方法研究

張新義

摘 要：軟件測試是提高軟件質(zhì)量和可靠性的重要手段。從是否運行程序的角度來講，測試分為靜態(tài)測試和動態(tài)測試，代碼檢查屬于靜態(tài)測試的范圍。本文首先討論了傳統(tǒng)軟件測試方法的缺點和局限性，進(jìn)而提出了代碼自動檢測的方法，隨后給出了此類方法可檢測到的故障類型，具體給出了程序靜態(tài)分析技術(shù)和方法研究，依據(jù)該方法進(jìn)行了軟件測試系統(tǒng)的設(shè)計與開發(fā)，最后給出了實驗結(jié)果和對比分析，并進(jìn)一步明確了下一步的研究方向。

關(guān)鍵詞：軟件生存期；靜態(tài)測試；代碼測試；故障

1 引言

軟件測試貫穿于軟件的整個生命周期，是軟件生存周期必不可少的一部分，軟件開發(fā)從總體的需求設(shè)計到具體的代碼編寫，每一個階段都伴隨著軟件測試，階段不同，采用的測試方法和策略也各不相同。如何保證在總體的需求分析和詳細(xì)設(shè)計正確的情況下盡量減少代碼編寫過程中所犯的錯誤，是測試領(lǐng)域研究的內(nèi)容之一。

從是否執(zhí)行程序的角度來講，軟件測試方法分為兩大類，即靜態(tài)方法和動態(tài)方法[1]。靜態(tài)方法的主要特征是不利用計算機(jī)運行被測試的程序，而是采用其它手段達(dá)到檢測的目的。代碼檢測就屬于靜態(tài)方法的一種，至于靜態(tài)分析在軟件測試中究竟占據(jù)什么地位，許多人有不同的見解。有些人認(rèn)為靜態(tài)分析只是進(jìn)行動態(tài)分析的預(yù)處理工作，靜態(tài)分析并不是要找出程序中的錯誤，因為編譯系統(tǒng)已經(jīng)能夠做到這一點了。實際上，這種看法是片面的，盡管編譯系統(tǒng)能發(fā)現(xiàn)某些程序錯誤，但這些遠(yuǎn)非軟件中存在的大部分錯誤，而且也僅僅是語法方面的錯誤，對于程序中潛在的故障，很多是編譯程序檢測不到的，因此靜態(tài)分析的查錯功能是編譯程序不能代替的。

代碼自動檢測就是在程序經(jīng)過調(diào)試和編譯通過以后，運用某種測試技術(shù)對源程序進(jìn)行靜態(tài)分析，從而發(fā)現(xiàn)程序中存在的錯誤。所用的程序設(shè)計語言不同，檢測到的故障各不相同，本文針對現(xiàn)階段比較通用的程序設(shè)計語言JAVA為例，對程序可能出現(xiàn)的故障進(jìn)行分析。本文在以下內(nèi)容中介紹了代碼自動檢測技術(shù)能檢測到的各種故障，隨后對檢測原理進(jìn)行了深入剖析，最后設(shè)計了軟件測試工具，并在工程中進(jìn)行了實踐。

2 檢測的故障類型

代碼自動檢測技術(shù)能發(fā)現(xiàn)程序中存在的多類錯誤，然而編碼中采用的設(shè)計語言不同，檢測到的錯誤不同，本文以JAVA程序設(shè)計語言為例，闡述能發(fā)現(xiàn)的故障類型。JAVA是非常有吸引力的面向?qū)ο蟮木幊陶Z言，也是當(dāng)前最流行的網(wǎng)絡(luò)編程語言，在很多高校，JAVA程序設(shè)計已成為信息類相關(guān)專業(yè)學(xué)生的必修科目，然而它規(guī)定了嚴(yán)格的語法，但又有它的靈活性，它的對象性及接口的多樣性增加了程序編寫的靈活性，程序員可以任意發(fā)揮他們的編程技巧，這大大增加了程序的靈活性，然而這種靈活性又增加了程序的不可預(yù)見性，這直接導(dǎo)致了故障的發(fā)生。譬如數(shù)組越界是緩沖區(qū)溢出故障類型中的一種最常見的故障，它是由于對數(shù)組下標(biāo)的操作越過了下標(biāo)的范圍引起的，數(shù)組越界在使用數(shù)組類型進(jìn)行程序設(shè)計的軟件中普遍存在。另外還有JAVA提供的一些關(guān)于字符處理的函數(shù)，雖然提供了這方面的功能，但沒有對參數(shù)范圍進(jìn)行限制和檢查，這也很容易導(dǎo)致錯誤的發(fā)生。以上這些故障采用一般的方法是很難發(fā)現(xiàn)的，因此必須采用一些特殊的檢測方法對軟件進(jìn)行檢測。

下面這些故障是本文所能檢測到的：

⑴內(nèi)存泄漏。JAVA語言中的內(nèi)存泄漏與傳統(tǒng)語言的內(nèi)存泄漏是十分不同的，它是指內(nèi)存對象不再需要時，但卻仍被程序無意識地、錯誤地保持或引用而導(dǎo)致GC無法回收對象所占用的內(nèi)存空間。在GC看來，它們還是“有用”的，從而導(dǎo)致內(nèi)存泄漏。

⑵數(shù)組越界。數(shù)組越界顧名思義就是數(shù)組超出了原先設(shè)定的范圍，導(dǎo)致出現(xiàn)了意想不到的結(jié)果。

⑶中文亂碼。JAVA語言內(nèi)部采用UNICODE編碼，所以在JAVA程序運行時，就存在著一個從UNICODE編碼和對應(yīng)的操作系統(tǒng)及瀏覽器支持的編碼格式轉(zhuǎn)換輸入、輸出的問題，這個轉(zhuǎn)換過程有著一系列的步驟，如果其中任何一步出錯，則顯示出來的漢字就會出是亂碼。

⑷變量未初始化。變量定義后必須被初始化，未初始化的變量的值不確定，使用它會使程序出現(xiàn)不正確的結(jié)果，甚至導(dǎo)致程序出現(xiàn)異常。

⑸不可達(dá)代碼。不可達(dá)代碼是指永遠(yuǎn)執(zhí)行不到的代碼。

3 靜態(tài)分析技術(shù)

近年來由于測試技術(shù)的發(fā)展，很多人開始對靜態(tài)測試進(jìn)行研究，并提出了很多的理論和方法，如C.Cowan[2]等人開發(fā)了一個緩沖區(qū)溢出故障測試工具，David Wagner[3]也給出了一種程序溢出故障的靜態(tài)檢測方法，David Evans[4]也給出了一種對動態(tài)內(nèi)存故障進(jìn)行靜態(tài)測試的新方法。這些測試方法的提出在很大程度上豐富了軟件測試的理論，加快了軟件測試發(fā)展的步伐，并在實踐應(yīng)用中取得了很好的效果。這里我們就給出對代碼進(jìn)行自動分析，從而對故障進(jìn)行檢測的一種新方法，并進(jìn)行了工具的開發(fā)，在工程應(yīng)用中取得了很好的效果。

代碼自動檢測方法的核心是對程序源代碼進(jìn)行靜態(tài)分析，運用編譯技術(shù)把程序翻譯成一種樹的中間表示，這種樹叫語法樹[5]，而后生成與語法樹相對應(yīng)的程序的控制流圖，然后運用故障規(guī)則對程序進(jìn)行檢測和故障定位。

3.1 語法樹

語法樹是程序代碼的一種樹形表示，是程序經(jīng)過翻譯后的一種中間表示形式。依據(jù)JAVA語言的語法規(guī)則，語法分析器接受詞法分析產(chǎn)生的記號串，并依照相應(yīng)的規(guī)則將記號組織成具有確切含義的語句，并構(gòu)造相應(yīng)的語法樹。譬如賦值語句position=initial+rate*60可以用圖1的語法樹表示。

其中根節(jié)點是賦值語句，葉結(jié)點表示終結(jié)符，即標(biāo)識符。

語法樹是編譯程序在經(jīng)過語法分析以后得到的源程序的另外一種表示，語法分析的結(jié)果是生成語法樹，每一個語法規(guī)則對應(yīng)一個相應(yīng)的處理函數(shù)，并作為樹的一個節(jié)點掛在語法樹上，提供對外的接口。由語法樹可以生成程序的控制流圖和變量的定義使用鏈，同時定義一些相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，為下一步的錯誤查找作準(zhǔn)備。

3.2 控制流圖

程序流程圖是人們最為熟悉的一種程序控制結(jié)構(gòu)的圖形表示法，在這種圖上的框內(nèi)表明了處理要求或條件，這些在軟件測試中進(jìn)行路徑分析時是不重要的，需要對其進(jìn)行簡化。

下面以一段程序為例，簡要說明控制流圖的構(gòu)建。

程序段為：

position=initial+rate*60；

if（position>50）{

i=4；

}esle{

i=5；

}

position=position+i；

對應(yīng)的流程圖及控制流圖如下：

其中（a）是一個含有兩出口判斷的程序流程圖，把它簡化成（b）的形式，稱這種簡化了的流程圖為控制流圖。

在控制流圖中只有兩種圖形符號，它們是：

①節(jié)點：以標(biāo)有編號的圓圈表示。它代表了程序流程圖中矩形框所表示的處理、菱形表示的兩至多出口判斷以及兩至多條流線相交的匯合點。

②控制流線或?。阂约^表示。它與程序流程圖中的流線是一致的，表明了控制的順序。為方便討論，控制流線通常標(biāo)有名字。

用控制流圖表示程序的結(jié)構(gòu)簡明易懂，是軟件測試階段一個很好的工具，其中一個很好的應(yīng)用就是在白盒測試階段依據(jù)源程序生成程序的控制流圖，遍歷控制流圖的路徑，對程序進(jìn)行路徑測試分析。由于控制流圖僅有一個入口和一個出口，從入口進(jìn)入的每一條路徑都能到達(dá)出口節(jié)點，因此控制流圖是一個有向圖。

3.3 代碼分析過程

代碼自動分析過程就是構(gòu)造程序的語法樹和控制流圖以及故障匹配的過程。

（1）構(gòu)造程序的語法樹。語法樹是進(jìn)行故障分析的基礎(chǔ)。分析器讀入

源程序，經(jīng)過詞法分析和語法分析，產(chǎn)生出與程序?qū)?yīng)的語法樹，程序的相關(guān)信息都可以反映在語法樹上。

（2）產(chǎn)生控制流圖。語法樹是程序的另外一種表示，是一種中間形式，

然而這種樹的結(jié)構(gòu)并不能反映程序的控制結(jié)構(gòu)，因此需要構(gòu)造程序的控制流圖，來反映程序的控制流程。程序的控制流圖與語法樹是相對應(yīng)的，控制流圖的每一個節(jié)點對應(yīng)語法樹上的一個語句節(jié)點，從控制流圖的接口可以方便的訪問與之對應(yīng)的語法樹節(jié)點，從而獲得相關(guān)的信息，同樣的從語法樹的語句節(jié)點也可以很方便的訪問到控制流圖的相應(yīng)節(jié)點。以上已通過例子對語法樹和控制流圖的構(gòu)造進(jìn)行了介紹，如圖1和圖2所示。

（3）故障檢測。從控制流圖的根節(jié)點出發(fā)，依次訪問控制流圖的各個

節(jié)點，并通過控制流圖提供的接口訪問與其對應(yīng)的語法樹節(jié)點，而后依次遍歷它的每一個子節(jié)點，在遍歷過程中如果發(fā)現(xiàn)與故障模式相匹配的地方，則將故障輸出。

4 自動檢測工具的實現(xiàn)

由以上的方法可知，代碼自動檢測的核心是對源程序進(jìn)行詞法分析和語法分析，生成相應(yīng)的語法樹和控制流圖，也就是設(shè)計一個編譯系統(tǒng)。其整體測試框架為：

（1）預(yù)編譯：由于源程序中存在宏定義、文件包含和條件編譯等預(yù)處理命令，因此在進(jìn)行詞法分析前必須進(jìn)行預(yù)處理，將宏進(jìn)行展開，這樣有利于變量的查找。

（2）詞法分析：將預(yù)編譯階段產(chǎn)生的中間代碼分解成單獨的詞的表示，形成初步的符號表，為語法分析作準(zhǔn)備，表的結(jié)構(gòu)主要有：標(biāo)識符表、類型表、關(guān)鍵字表、常數(shù)表、運算符表和分界符表。標(biāo)識符表中包含有利于錯誤查找的一些相關(guān)信息，如：位置、行號、錯誤類型，這些信息對于錯誤的查找和定位都有十分重要的作用。

（3）語法分析：這一步主要是將輸入字符串識別為單詞符號流，這里主要是找出變量聲明語句，并相應(yīng)的分離出指針變量和數(shù)組變量。按照標(biāo)準(zhǔn)的JAVA語法規(guī)則，對源程序作進(jìn)一步分析，比如什么是變量定義，什么是賦值語句，什么是函數(shù)等等。語法分析的結(jié)果是生成語法樹，每一個語法規(guī)則對應(yīng)一個相應(yīng)的處理函數(shù)，并作為樹的一個節(jié)點掛在語法樹上，提供對外的接口。由語法樹進(jìn)一步生成程序的控制流圖，同時定義一些相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，為下一步的故障檢測作準(zhǔn)備，同時在這一過程也逐漸添加和細(xì)化符號表的一些相關(guān)信息。

（4）故障檢測：查找程序中可能出現(xiàn)的錯誤。依據(jù)程序的控制流圖，依次遍歷語法樹的各個節(jié)點，匹配欲查找的錯誤，如錯誤找到，則將錯誤信息記錄到數(shù)據(jù)庫中，最后得到數(shù)據(jù)庫文件。數(shù)據(jù)庫文件記錄測試過程中得到的一些相關(guān)信息，如出現(xiàn)錯誤的變量名、出現(xiàn)錯誤的行號、該行字符串、錯誤類型等。由數(shù)據(jù)庫文件生成故障信息報告，將故障信息反饋給用戶，用戶根據(jù)故障報告進(jìn)行程序更新和維護(hù)。

5 實驗結(jié)果分析

以上給出了代碼檢測的一種自動分析方法，運用該方法我們進(jìn)行了測試系統(tǒng)的開發(fā)，并針對一些不同領(lǐng)域的具體的軟件項目進(jìn)行了測試，部分測試結(jié)果如表1：

表格中的文件大小以M為單位，ML：內(nèi)存泄漏故障；OOB：數(shù)組越界故障；UV：未初始化變量故障；DC：死碼故障；

以上表格中的內(nèi)容是我們測試數(shù)據(jù)的一部分，從表格中的數(shù)據(jù)可知，這幾類故障在軟件項目中普遍存在，只是項目不同，故障分配的概率不同，因此開發(fā)面向故障的軟件測試工具十分必要。

6 結(jié)論

以往的代碼審查通常是在代碼完成以后，通過人工的勞動對代碼進(jìn)行走讀，這種檢查不僅費時費力，而且很難發(fā)現(xiàn)其中的錯誤，因此不僅效率低，而且效果比較差。本文提出的這種代碼檢測方法通過對源程序進(jìn)行分析，匹配故障查找模式，結(jié)合程序的控制流圖和相應(yīng)的語法樹，自動查找程序中存在的錯誤，不僅節(jié)省時間，效率高，在檢測過程中不需要人為的干預(yù)，只需要對檢測的結(jié)果進(jìn)行確認(rèn)，因此自動化程度高，是代碼檢測的一種好方法。本文通過應(yīng)用這種靜態(tài)測試方法，進(jìn)行了軟件測試工具的開發(fā)，并能檢查出軟件中存在的六種故障，然而這幾種故障并不能代表所有的故障類型，在以后的工作中，我們將繼續(xù)拓展故障類型和規(guī)則，爭取使這種測試方法能檢測出更多的故障，使其更加完善。

[參考文獻(xiàn)]

[1]鄭人杰.計算機(jī)軟件測試技術(shù)[M].北京：清華大學(xué)出版社，1992.

[2]趙鵬宇，李建茹，宮云戰(zhàn).Java語言中數(shù)組越界故障的靜態(tài)測試研究.

[2]朱穎芳.關(guān)于JAVA內(nèi)存泄漏問題的探討.電腦知識與技術(shù)，2006年第32期.

[3]N. Dor， M.Rodeh，and M.Sagiv.Cssv：Towards a realistic tool for statically detecting all buffer overflows in c[C].In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation， 2003： 155–167.

[4]D. Wagner，J.Foster，E.Brewer，and A.Aiken.A first step towards automated detection of buffer overrun vulnerabilities[C].In Proceedings of the Network and Distributed Systems Security Symposium，2000：3–17.

[5]David Evans.Static Detection of Dynamic Memory Errors[C]. USA：ACM Conference on Programming Language Design and Implementation，1996：44–52.

[6]A.V.Aho，R.Sethi，R.，and J.D.Ullman.Compilers Principles， Techniques，and Tools[M].America：Addison Wesley，1986.