張新義

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

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

1 引言

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

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

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

2 檢測(cè)的故障類(lèi)型

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

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

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

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

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

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

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

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

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

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

3.1 語(yǔ)法樹(shù)

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

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

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

3.2 控制流圖

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

下面以一段程序?yàn)槔?，?jiǎn)要說(shuō)明控制流圖的構(gòu)建。

程序段為：

position=initial+rate*60；

if（position>50）{

i=4；

}esle{

i=5；

}

position=position+i；

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

其中（a）是一個(gè)含有兩出口判斷的程序流程圖，把它簡(jiǎn)化成（b）的形式，稱(chēng)這種簡(jiǎn)化了的流程圖為控制流圖。

在控制流圖中只有兩種圖形符號(hào)，它們是：

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

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

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

3.3 代碼分析過(guò)程

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

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

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

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

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

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

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

4 自動(dòng)檢測(cè)工具的實(shí)現(xiàn)

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果分析

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

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

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

6 結(jié)論

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

[參考文獻(xiàn)]

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

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

[2]朱穎芳.關(guān)于JAVA內(nèi)存泄漏問(wèn)題的探討.電腦知識(shí)與技術(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.