軟件代碼測試技術

北京郵電大學網絡與交換技術國家重點實驗室 北京 1000876

概述

軟件測試技術可以從多種角度進行分類，如按開發階段可分為單元測試、集成測試、系統測試、確認測試和驗收測試，按是否需要程序執行可分為靜態測試和動態測試，按是否需要源代碼可分為白盒測試和黑盒測試，按程序運行特性可分為功能測試和性能測試，按功能測試類型可分為邏輯功能測試、安裝卸載測試、易用性測試、兼容性測試、安全性測試、圖形界面測試等，按性能測試類型可分為一般性能測試、壓力測試、負載測試、穩定性測試，另外，還有回歸測試、冒煙測試、隨機測試等等?；谝陨蠝y試分類，對于白盒測試可根據是否需要程序運行進一步劃分為靜態白盒測試和動態白盒測試。

靜態白盒測試主要包括缺陷檢測技術、規則審查技術和質量度量技術。缺陷檢測技術針對源代碼中存在的一些潛在語法或語義錯誤進行檢測，如對可能為空的指針進行解引用、對已分配的內存沒有及時釋放、使用未經過初始化的數據等問題，其難點在于需要準確地計算出復雜的執行語義，典型的工具有Klocwork的Klocwork Insight[1]、Coverity的Coverity Static Analysis[2]、Fortify的Static Code Analyzer[3]，GIMPEL SOFTWARE的PC-Lint[4]、北郵的DTS[5]、北航的QESAT[6]和北大的COBOT[7]；規則審查技術針對一些特定的開發規范進行檢查，如版式規范、命名規范、書寫規范等，該技術在語法層面上進行檢測難度不大，典型工具有Parasoft的Jtest和C++test[8]、Rational的Software Analyzer[9]、MicroFocus公司DevPartner中的Source Code Review[10]功能、Telelogic公司Logiscope中的RuleChecker[11]功能和馬里蘭大學的FindBugs[12]；質量度量技術首先定義若干個度量元，通過度量元的組合形成質量標準，最后通過組合質量標準形成質量因素，該技術也是在語法層面展開的，典型的工具是Telelogic公司Logiscope中的Audit功能。

動態白盒測試主要包括單元技術、測試評估技術和運行監控技術。單元技術基于被測單元的代碼及邏輯結構產生并執行測試用例，其難點在于如何對復雜結構及路徑進行求解，典型的數據生成工具有斯坦福大學的KLEE[13]、貝爾實驗室的DART[14]、伯克利大學的CUTE[15]和北郵最新研發的CTS[16]；測試評估技術針對程序結構的覆蓋情況對測試充分度進行評估，如語句覆蓋、分支覆蓋、MC/DC覆蓋、基本路徑覆蓋、定義/使用覆蓋等，典型工具有Parasoft系列test工具的覆蓋功能、MicroFocus公司DevPartner中的Code Coverage Analysis功能、Telelogic公司Logiscope中的TestChecker功能、IBM公司PurifyPlus[17]中的PureCoverage、北航QESAT中的覆蓋統計功能、北郵CTS中的覆蓋統計功能、深圳領測科技有限公司的VcTester[18]、廣州凱樂軟件技術有限公司的Visual Unit[19]；運行監控技術采用插樁或變異的方法對源程序進行一定的修改，在運行過程中收集并監控錯誤執行狀態，典型的工具有Agitar公司的AgitarOne[20]、Parasoft公司的Insure++、IBM公司PurifyPlus下的Purify。

在以上基于代碼的軟件測試技術中，涉及復雜程序執行語義的缺陷檢測技術和涉及復雜邏輯結構的單元測試技術具有相當的難度，目前得到國內外眾多高校及科研機構的研究，本文就這兩個方面的相關內容進行介紹。

1 缺陷檢測技術

針對缺陷檢測技術的研究，本文概括為如下四個部分：技術特點、技術架構、缺陷模式和關鍵技術。

1.1 技術特點

傳統軟件測試基于軟件的某些性質，如功能、覆蓋、性能等，這些測試雖然是必要的，但由于不是對軟件中的缺陷直接測試，因此就檢測缺陷的能力而言，基于代碼的缺陷檢測技術具有一定的優勢，主要包括如下6點。

1) 覆蓋范圍廣。傳統方法要達到較高的測試覆蓋范圍，依賴于測試用例的數量及質量，這將帶來大量的測試開銷。而缺陷檢測技術不需要執行程序，采用靜態的方法覆蓋程序結構及路徑，這樣可以覆蓋到更多的問題。

2) 測試效率高。傳統方法需要設計并執行大量測試用例，這個開銷在整個測試過程中占有極大的比例。缺陷檢測技術采用靜態方法分析及計算，其效率相對于動態方法要高出許多。

3) 故障定位準。對于有些動態方法發現的問題，其根源可能來自于多種情況，對其進行準確的定位具有一定的困難。而靜態方法在發現問題的同時，可以對相關信息進行準確的定位。

4) 小概率故障檢測能力。對于某些小概率事件，依賴于執行測試用例的動態方法是很難覆蓋到的，而通過分析程序結構得到路徑的靜態方法卻相對容易實現，盡管有些復雜條件是很難計算的。

5) 非顯性故障檢測能力。對于某些沒有明確現象的故障，如內存泄漏或無沖突的內容使用等，動態方法即使覆蓋到了也難以發現。而靜態方法卻可以直接發現問題，盡管其可能沒有直接的后果。

6) 測試人員要求低。傳統測試方法要得到較好的效果，需要完成一定的測試設計及測試開發工作，甚至還需要熟悉系統業務流程，這對測試人員有著較高的要求。而面向故障的測試技術僅需要流程化的工具使用，對人員的要求較前者要低得多。

1.2 技術架構

缺陷檢測技術架構可劃分為輸入、基礎、計算、測試及分析5個部分，具體內容如圖1所示。

圖1 缺陷檢測技術架構

1) 輸入部分。測試文件指被測程序源代碼或經過頭文件展開、條件編譯及宏替換等預處理后的中間代碼；配置文件中包括為使系統正?；蛴行н\行所提供的一些參數；模式文件中包含故障模式的相關描述及配置信息。

2) 基礎部分。此部分針對輸入的程序文件，構建出一些基礎數據結構，在分析、計算及測試過程中使用。

3) 計算部分。采用靜態方法計算出動態運行時的狀態，包括計算不同類型對象在運行時的取值信息、分析過程中的可達及不可達路徑、采用函數摘要替代被調函數完全展開等內容。

4) 測試部分。針對輸入的配置文件及模式文件解析缺陷模式，構建相應狀態機；針對輸入文件中不同分析對象，創建狀態機實例；基于基礎數據結構運行狀態機實例，并在其執行過程中發現故障。

5) 分析部分?；跈z測到的缺陷及其相關信息，利用工具分析界面對測試結果的正確性進行分析，并將確認的結果導出。

1.3 缺陷模式

軟件缺陷模式有很多，目前常用的就有數百種，本文將其歸納為故障、安全、疑問及規則4類模式。

1)故障模式。該類模式可能引起運行異?；蝈e誤，如被分配的內存在使用后沒有正確釋放、訪問可能為空的指針內容、訪問超過有效邊界的數組內容、使用非法操作數進行運算、使用未經過正常初始化的數據、使用已經釋放的指針內容等，該類缺陷被觸發后將引起較為嚴重的后果，如異常退出或系統宕機，因此應盡量避免此類問題。

2) 安全模式。該類模式導致軟件中存在安全隱患及漏洞，如對從外部獲取的不安全數據未經驗證即使用、對緩沖區的使用超過其規定的安全范圍、使用了不安全的API函數、密碼相關操作不安全等，該類模式對應的代碼在正常操作下并沒有問題，但對其異常操作卻可能造成嚴重的后果，如拒絕服務或數據丟失，因此應謹慎對待此類問題。

3) 疑問模式。該類模式可能影響執行效率或導致邏輯錯誤，如循環中的低效操作、字符串的低效操作、冗余的對象方法、無意義的比較、相同的條件分支等，該類缺陷容易使人產生質疑，影響對程序真實意圖的判斷。

4) 規則模式。該類模式旨在統一編碼規范，避免程序員的不良習慣造成的錯誤，如聲明定義規則、版面書寫規則、分支控制規則、運算處理規則、過程調用規則、語句使用規則等。

1.4 關鍵技術

在各類缺陷模式中，對疑問模式及規則模式的檢測僅需要利用抽象語法樹等基礎數據結構，這類模式的檢測精度相對較高。對故障模式及部分安全模式的檢測需要程序執行語義信息，這就可能會遇到對某些特殊的情況，如對復雜的路徑條件、過程間數據傳播及對象表達式的分析及計算，由于缺少程序動態執行信息可能造成誤報及漏報的情況。為了更好地提高缺陷檢測精度，作者將相關技術總結如下。

1) 抽象解釋。抽象解釋技術用抽象對象域上的計算替代具體對象域上的計算，本質上是在計算效率和計算精度之間取得均衡。抽象域用于程序變量取值信息的近似表示，可分為關系型和非關系型兩類：非關系型抽象域假設變量之間相互獨立，如區間抽象域；關系型抽象域考慮變量之間的關聯關系，如八邊形抽象域、八面體抽象域和區間多面體域等。關系型抽象域相對于非關系型來說更精確，但其計算也相對復雜。

2) 路徑分析。從路徑抽象和近似的角度，靜態分析方法可以劃分為路徑敏感和路徑不敏感兩種方法。路徑不敏感方法不考慮程序控制流程中的不可達路徑，會引入較多的誤報，而完整路徑分析又會產生無限狀態空間。既能避免完整路徑分析帶來的組合爆炸，對給定缺陷來說又足夠精確的路徑分析方法，是提高準確性和實用性的重要手段。

3) 過程分析。精確的分析方法應包括過程內分析和過程間分析，過程間分析可以分為上下文敏感和上下文不敏感。最精確的上下文敏感方法是完整程序分析，但該方法無疑將要求大量的時間和內存開銷，在大型程序的分析過程中無法實現。在復雜度和精度之間達到合適平衡的上下文敏感函數間分析方法，是提高靜態缺陷檢測準確性的重要內容。

4) 缺陷檢測。若采用有限狀態機來描述缺陷模式，缺陷檢測基本過程可轉化為一個傳統的數據流問題。在分析過程中首先根據每類缺陷的不同狀態機創建條件，創建一系列的缺陷狀態機實例，然后沿著控制流計算各缺陷狀態機實例在每個程序位置上的可能狀態集合，如發現可能狀態集合中包含錯誤狀態即報告一個潛在的缺陷。

2 單元測試技術

針對單元測試技術的研究，本文概括為如下3個部分：技術架構、覆蓋準則和關鍵技術。

2.1 技術架構

測試用例生成架構可劃分為以下4個部分，具體內容如圖2所示。

圖2 單元測試技術架構

1) 程序預處理。對被測程序進行預處理，其目的是生成獨立運行的被測單元，主要工作包括靜態分析、單元劃分、插裝、打樁、重命名main函數、建立測試用例框架、建立測試結果框架等。

2) 測試用例生成。隨機測試用例生成方法包括：基于區間運算結果、基于輸入域劃分、基于路徑劃分、基于邊界值劃分等；基于分支限界的測試用例生成方法包括：路徑自動生成和基于分支限界的測試用例自動生成；人工輔助測試用例生成方法基于自動生成的部分結果，結合人工干預來實現用例的生成。

3) 測試執行、故障定位與結果分析。測試執行：可單步、連續執行被測單元的測試用例，執行結果生成結果矩陣；故障定位：一旦測試執行發現故障，可依據結果矩陣和啟發算法對故障快速定位；測試效果分析：對覆蓋率進行統計。

4) 結果呈現。軟件性質顯示：函數調用圖、控制流圖、軟件代碼性質(代碼行、文件個數、函數個數、變量數、注析率、McCabe數等)；測試結果顯示：反相顯示被覆蓋的代碼、故障定位輔助支持顯示、人工輔助測試用例生成、測試用例庫顯示。

2.2 覆蓋準則

測試覆蓋準則是指覆蓋測試的標準，包括語句覆蓋、分支覆蓋、謂詞覆蓋、MC/DC覆蓋、路徑覆蓋、定義使用覆蓋等，不同的準則對應要測試的對象或程序元素不同。典型的幾種覆蓋準則如下。

1) 語句覆蓋。語句覆蓋測試是最簡單的結構性測試方法之一。它要求在測試中，程序中的每條語句都得到執行。在控制流圖中，要求所有語句都被運行的充分必要條件是覆蓋圖中的所有節點。

2) 分支覆蓋。語句覆蓋測試是最基本的覆蓋測試技術，雖然它能保證所有語句都被執行，但并不能保證每條分支都被執行到；因此，分支測試要求程序中的每個取“真”分支和取“假”分支都至少經歷一次。在控制流圖中，分支表現為圖中的一條有向邊。

3) 謂詞覆蓋。一個分支的條件是由謂詞組成的，單個謂詞稱為原子謂詞，原子謂詞通過邏輯運算符可以構成復合謂詞。原子謂詞覆蓋要求每個原子謂詞都至少獲得一次“真”值和一次“假”值；分支—謂詞覆蓋不僅要求每個原子謂詞都至少獲得一次“真”值和一次“假”值，還要求每個復合謂詞本身也至少獲得一次“真”值和一次“假”值；復合謂詞覆蓋要求復合謂詞中每個原子謂詞的各種組合情況都至少出現一次。

4) 數據流覆蓋。與控制流的覆蓋思想不同，數據流覆蓋面向程序中的變量。定義覆蓋要求每個變量的定義至少被覆蓋一次，引用覆蓋要求每個變量的所有引用都至少被覆蓋一次?？紤]到回路中有無窮的引用情況，定義-引用覆蓋為消除回路后的引用覆蓋。

2.3 關鍵技術

在自動化單元測試中，主要涉及如下幾個方面的技術。

1) 數據生成。數據生成可分解為4個部分。預處理部分：提供支持的部分，要面向任何類型的程序；回退部分：對一個表達式中的某個變量而言，選擇合理的賦值使之能滿足求解的需要；回溯部分：當發生矛盾時改變前面某個變量的賦值；加速部分：非數值類型變量處理的加速、復雜表達式處理的加速、等式處理的加速、小區間有限回退技術等。

2) 故障定位。通過分析計算各程序語句發生故障的可疑度得到定位結果。針對測試用例對應的執行路徑集冗余問題，消除重復的執行路徑以及與失敗執行路徑最不相似的成功執行路徑，將約簡后的執行路徑集作為可疑空間，通過路徑邊元素的可疑度計算語句塊可疑度，最終得到根據可疑度大小進行排序的語句塊序列，實現對故障的自動定位。

3) 回歸測試。單元回歸測試的優化工作在于構造一個合理的測試用例集合，使得既能對軟件修改所影響的范圍進行充分測試，又能盡量避免冗余測試，排除與修改內容無關的測試用例。

3 工具應用

缺陷測試系統(DTS)由北京郵電大學、北京博天院信息技術有限公司聯合研發，是國內第一套面向代碼缺陷的測試工具。CTS是由北京郵電大學和北京博天院信息技術有限公司聯合研發的一款面向C語言的單元覆蓋測試工具。

3.1 測試Android4.0

Android4.0的代碼由三個部分構成，其底層有5 919 784行C代碼，中間層有6 158 454行C++代碼，部分上層有5 336 619行Java代碼。DTS累積測試時間為219小時，分析及確認的工作量為5人月。缺陷檢測結果見表1，平均故障類缺陷密度為2/KLOC，平均安全類缺陷密度為9.6/KLOC，平均疑問類缺陷密度為20/KLOC，平均規則類缺陷密度為74.5/KLOC。

表1 Android4.0的缺陷檢測結果

3.2 測試開源程序

對于開源程序的測試，從Sourceforge中選取排名靠前的20個工程，Java代碼總計1 344 179行，C代碼總計100 725行，C++代碼總計111 918行。對其中故障類缺陷的分析結果見表2，平均故障密度為4.5/KLOC。

表2 對開源程序的缺陷檢測結果

3.3 測試數據生成

對3個開源工程進行測試數據生成的測試，3個工程的屬性如表3。

利用CTS分別對其進行語句覆蓋、分支覆蓋、MC/DC覆蓋3種覆蓋準則下的測試數據自動生成，測試結果如表4，工程aa200c中有77個被測單元，有40個單元能夠達到100%覆蓋，平均覆蓋率在80%以上，完成三種覆蓋準則的測試數據生成總用時為108分鐘。工程qlib中有365個被測單元，平均有177個單元能夠達到100%覆蓋，平均覆蓋率為68%，完成3種覆蓋準則的測試數據生成總用時為444分鐘。工程deco中有319個被測單元，平均有41個單元能夠達到100%覆蓋，平均覆蓋率為38%，由于deco工程中存在大量的復雜數據類型(例如函數指針、字符串結構等)，所以有很多覆蓋率為0的情況，導致平均覆蓋率效果不如前兩個工程，完成3種覆蓋準則的測試數據生成總用時為484分鐘。

表3 3個開源工程屬性

表4 測試數據生成結果

3.4 國際工具對比

國際上典型的缺陷檢測工具有Klocwork、Coverity、Fortify和Logiscope等，DTS與其對比結果分別見圖3～圖6。

針對表2中的20個開源工程，圖3中為Klocwork的K9與DTS針對故障類缺陷的對比結果。圖3中交集部分為雙方共同檢測出，最外側部分為雙方的誤報，其余部分為比對方多報的缺陷。其中K9的準確率為73.9%，DTS的準確率為75.9%；K9的相對漏報率為59%，DTS的相對漏報率為11.6%。

圖3 DTS與K9的對比結果

針對表2中的4個開源程序(Playa、dgvideo、spgateway、bwchess)和3個軍工程序，圖4中為Logiscope與DTS的所有缺陷類型對比結果。Logiscope的規則側重于質量度量，分為建議類和強制類。DTS的1317個故障類缺陷Logiscope均沒有覆蓋，其它類型的缺陷與Logiscope的交集有5 407個，而Logiscope的45 055個建議類缺陷DTS也沒有覆蓋。

圖4 DTS與Logiscope的對比結果

針對表2中的UUCP工程，圖5中為Coverity與DTS針對故障類缺陷的對比結果。圖5中各部分的含義與圖3中一致。其中Coverity的準確率為80.72%，DTS的準確率為71.68%；Coverity的相對漏報率為90.7%，DTS的相對漏報率為6.24%。

圖5 DTS與Coverity的對比結果

針對表2中的spell和barcode工程，圖6中為Fortify與DTS的對比結果。雙方共同測出內存泄漏和緩沖區溢出問題15個，而Fortify的269個安全缺陷DTS沒有測出，而DTS的1491個其它缺陷Fortify沒有測出。

圖6 DTS與Fortify的對比結果

3.5 國內應用情況

自2006年以來，DTS在4個國家863項目及2個自然科學基金項目資助下完成，主要技術指標達到國際先進、國內領先的水平?；谙嚓P研究成果，發表論文70余篇，申請專利30余項(授權10余項)，獲得軟件著作權登記17項。

DTS目前已經在全國發行近500多個試用版，在美國、日本、歐洲、香港、澳門有零星使用，在國內航天、航空、造船、銀行、證券、電信、電力、交通、冶金等領域廣泛應用，擁有50多個商用單位，成功應用于神舟、嫦娥及天宮等航空航天工程。

4 結束語

在基于代碼的軟件測試技術中，缺陷模式檢測和測試數據生成是效率很高的測試方法，具有其它測試無法替代的地位。隨著此技術的逐步成熟，相應測試工具必然會在市場上廣泛流行。

在美國，面向缺陷模式的測試服務是軟件測試市場的主流方向之一。在我國，該技術的研究及應用雖然剛剛起步，但已收到了很好的效果。在單元測試方面已經得到廣泛應用，但對復雜結構對象、循環結構和函數調用的處理仍存在較大的困難，這將是未來幾年的研究趨勢。

參考文獻

[1]Domain Market.com[EB/OL].[2015-04-20].http://www.klocwork.com

[2]Code Advisor on Demand[EB/OL].[2015-04-20].http://www.coverity.com

[3]Application Security[EB/OL].[2015-04-20].http://www.fortify.com

[4]Gimpel Software[EB/OL].[2015-04-20].http://www.gimpel.com

[5]北京博天院信息技術有限公司[EB/OL].[2015-04-20].http://www.dtstesting.com

[6]中國測試平臺[EB/OL].[2015-04-20].http://www.chinatesting.cn/331/12585331.shtml

[7]庫博[EB/OL].[2015-04-20].http://cobot.net.cn

[8]PARASOFT[EB/OL].[2015-04-20].http://www.parasoft.com

[9]Rational Software Analyzer Developer Edition[EB/OL].[2015-04-20].http://www-03.ibm.com/software/products/zh/rsade

[10]Software Testing[EB/OL].[2015-04-20].http://www.borland.com/Products/Software-Testing

[11]Elelogic Logiscope[EB/OL].[2015-04-20].ftp://public.dhe.ibm.com/software/rationalsdp/documentation/archive/Logiscope/version_6-5/ReviewerJava.pdf

[12]FindBugs[EB/OL].[2015-04-20].http://sourceforge.net/projects/f i ndbugs/

[13]Cadar C,Dunbar D,Engler D.KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs[C]//USENIX Symposium on Operating Systems Design and Implementation(OSDI 2008),San Diego,CA,USA,2008

[14]Koushik S,Darko M,Gul A.CUTE:a concolic unit testing engine for C[C]//The 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering,2005:263-272

[15]Godefroid P,Klarlund P,Sen P.DART:directed automated random testing[C]//The 2005 ACM SIGPLAN conference on Programming language design and implementation(PLDI),2005:213-223

[16]唐容.支持非數值型測試用例自動生成的抽象內存建模技術研究[D].北京郵電大學,2013

[17]使用IBM Rational PurifyPlus[EB/OL].[2015-04-20].http://www.ibm.com/developerworks/cn/rational/07/0306_chitale/

[18]經典的單元測試工具VcTester介紹[EB/OL].[2015-04-20].http://www.ltesting.net/html/30/n-161730.html

[19]凱樂軟件[EB/OL].[2015-04-20].http://www.kailesoft.com

[20]Agitar Technologies[EB/OL].[2015-04-20].http://www.agitar.com/solutions/products/agitarone.html