邵巳航，蘇 亭，顧 斌，王 政，楊孟飛

（1.華東師范大學(xué) 軟件學(xué)院，上海200062；2.北京控制工程研究所，北京100080）

0 引 言

目前，工業(yè)界仍舊主要采用人工手動編寫測試用例的方法。但由于軟件規(guī)模的不斷擴(kuò)大，測試的人力和成本也隨之上升。在此背景下，一系列自動化生成測試用例的工具得到了研究和發(fā)展，以輔助測試人員。

動態(tài)符號執(zhí)行是自動化生成測試用例的方法之一，能通過程序?qū)嶋H運(yùn)行時的實(shí)際值信息提高符號執(zhí)行的可行性。根據(jù)測試的需求粒度不同，可以劃分為過程內(nèi)和過程間?，F(xiàn)有的工具包括DART［1］，KLEE［2］，PEX［3］等。

本文貢獻(xiàn)如下：基于一套過程間數(shù)據(jù)流分析方法（SMART 算法），在相關(guān)項目工具實(shí)現(xiàn)的基礎(chǔ)上，針對C語言進(jìn)行研究，建立了一套詳細(xì)可行的過程間動態(tài)符號執(zhí)行模型；解決了過程間調(diào)用時實(shí)參和形參變量的符號統(tǒng)一問題；對SMART 算法進(jìn)行改進(jìn)，使其在實(shí)際應(yīng)用中能更準(zhǔn)確地計算函數(shù)摘要。

1 動態(tài)符號執(zhí)行

在自動化生成測試用例的研究中，符號執(zhí)行是一種可行性較高的方法。主要思想是通過程序初始的隨機(jī)輸入，由負(fù)責(zé)監(jiān)控的插樁代碼收集路徑上的符號約束，然后根據(jù)不同的路徑選擇策略生成新的路徑約束，通過約束求解器進(jìn)行求解，從而在下次迭代中使程序轉(zhuǎn)入新的分支，最后根據(jù)相應(yīng)的覆蓋標(biāo)準(zhǔn)或特定條件終止測試［4］。

然而，由于實(shí)際程序的符號約束有時并不能被約束求解器求解，例如當(dāng)遇到源代碼不可得的函數(shù)調(diào)用，動態(tài)符號執(zhí)行正是為了有效解決這類問題而被提出。它在傳統(tǒng)的符號執(zhí)行中利用符號的實(shí)例化提高了可行性，即動態(tài)地運(yùn)行被測程序，當(dāng)動態(tài)符號執(zhí)行遇到某些不可求解的輸入時，就使用它的運(yùn)行時實(shí)際值來化簡約束，再進(jìn)行求解，從而使測試能盡可能覆蓋更多的分支和路徑［5］。

1.1 過程間動態(tài)符號執(zhí)行

在白盒測試中，傳統(tǒng)的過程間動態(tài)符號執(zhí)行算法在遇到函數(shù)調(diào)用時每次都會跟進(jìn)被調(diào)函數(shù)體內(nèi)，進(jìn)而收集分支上的約束。雖然這樣可以保證盡可能覆蓋被測程序分支，但由于實(shí)際被測的程序規(guī)模較大，加上頻繁的函數(shù)調(diào)用，很容易造成路徑爆炸的現(xiàn)象，使得過程間的動態(tài)符號執(zhí)行可行性不高，效率下降。為解決路徑爆炸的問題，T.Reps等人［6］曾提出在靜態(tài)的過程間數(shù)據(jù)流分析中縮減問題規(guī)模的方法，后來P.Godefroid等人［7］在此基礎(chǔ)上，引入SMART 算法，利用靜態(tài)分析中類似的思想，對被調(diào)函數(shù)隔離地進(jìn)行測試，收集函數(shù)的輸入 （前置條件）和輸出（后置條件）作為函數(shù)的摘要 （summary），以后調(diào)用時即可復(fù)用這些信息來收集約束，無需再重新搜索函數(shù)內(nèi)部的路徑，從而大大減少了問題規(guī)模和迭代次數(shù)，提高了測試效率。本文正是基于SMART 算法，針對C 語言論述了一套詳細(xì)的過程間符號執(zhí)行框架，并對其進(jìn)行建模和實(shí)現(xiàn)。

1.2 CAUT

CAUT （C analysis and unit testing toolkit）是本文依托項目所實(shí)現(xiàn)的動態(tài)符號執(zhí)行測試工具。它針對C 語言，以白盒測試覆蓋目標(biāo)為驅(qū)動，雖然主要面向以過程內(nèi)單元測試為需求的客戶，但設(shè)計時仍然考慮了過程間測試的功能。CAUT 作為面向自動化測試而開發(fā)的工具，可以分為前端和后端2部分，其中前端負(fù)責(zé)對C 語言被測代碼做變形、化簡和自動插樁等前期預(yù)處理，與動態(tài)符號執(zhí)行有關(guān)的設(shè)計和算法集中在后端［8，9］。

CAUT 后端可以分為3個模塊：①測試執(zhí)行模塊：負(fù)責(zé)收集程序運(yùn)行期間變量的符號值賦值變化，分支上的約束等運(yùn)行時信息。②約束求解模塊：針對選擇出來的路徑收集分支上的約束，并對C 語言特有的約束進(jìn)行化簡，最后將符合約束范式的約束傳遞給約束求解器進(jìn)行求解，CAUT 采用微軟的Z3［10］可滿足性求解器作為求解工具。③路徑選擇模塊：負(fù)責(zé)在每次測試執(zhí)行完畢之后，結(jié)合被測程序覆蓋標(biāo)準(zhǔn)需求和相應(yīng)的路徑選擇策略，生成一條新的路徑并傳遞給約束求解模塊進(jìn)行求解。

2 SMART算法

SMART （systematic modular automated random testing），是由Patrice Godefroid等人提出的過程間動態(tài)符號執(zhí)行算法。其核心的思想是隔離地對待程序中每一個函數(shù)，根據(jù)每次函數(shù)調(diào)用時參數(shù)的實(shí)際值來計算或者使用函數(shù)摘要，從而減少符號執(zhí)行的迭代次數(shù)，提高執(zhí)行效率和實(shí)際應(yīng)用的可行性［7］。

2.1 函數(shù)摘要

若給定函數(shù)f，w 是其任意一條執(zhí)行路徑，cwi為路徑上跟函數(shù)輸入有關(guān)的約束，cwo為路徑上跟函數(shù)輸出有關(guān)的約束，令

則函數(shù)f 在路徑w 上的摘要 （summary）為

若W ＝ ｛w1，w2，…，wn｝是函數(shù)f 所有執(zhí)行路徑的集合，則函數(shù)f 的摘要為

以表1所示程序代碼中的函數(shù)f 為例，由于f 只有2條執(zhí)行路徑，所以f 的摘要為 （x＞0∧ret＝1）∨ （x＜＝0∧ret＝0），其中ret為函數(shù)f 的返回值符號。

表1 示例代碼1

2.2 SMART算法

SMART 算法的重點(diǎn)在于計算函數(shù)摘要，設(shè)集合I 為函數(shù)f 的輸入，concrete（I）為輸入的實(shí)際值，summary（f）為函數(shù)f 的摘要，C 為程序的約束集合，backtracking為判斷是否追溯的標(biāo)志。則其算法框架見表2。

由算法描述可知，當(dāng)程序遇到函數(shù)f 調(diào)用時，會首先檢驗(yàn)實(shí)參傳入的實(shí)際值是否滿足f 的摘要，如果f 當(dāng)前有摘要可用，直接將摘要添加到當(dāng)前約束中，并將追溯標(biāo)志設(shè)為0，這樣程序就不再收集f 函數(shù)體內(nèi)的約束；如果f當(dāng)前無摘要可用，說明本次迭代需要計算新的摘要，設(shè)追溯標(biāo)志為1，對f 函數(shù)體內(nèi)的每個分支上的約束進(jìn)行收集，當(dāng)f 返回后，將收集到的約束和返回值添加到f 的摘要中，然后繼續(xù)搜索f 的下一條路徑。當(dāng)f 搜索完畢之后，函數(shù)摘要也就計算完成。

表2 SMART 算法

3 基于SMART算法的CAUT模型

3.1 Def－Use鏈

定義－使用鏈［11］（definition－use chain，Def－Use鏈），是一種經(jīng)典的數(shù)據(jù)流分析結(jié)構(gòu)，實(shí)際上由2個鏈表組成，分別按順序存放所有的變量使用和定義情況。CAUT 正是基于此類方法分析運(yùn)行時變量的符號值變化，其算法見表3。

表3 CAUT 的Def－Use算法

以表1所示C 語言代碼為例，CAUT 模型將分別對每個函數(shù)維護(hù)一個Def－Use鏈，如果一次動態(tài)實(shí)際執(zhí)行中top函數(shù)的形參取w＝1，y＝1，那么其Def－Use鏈將會見表4。

表4 top 函數(shù)形參取w＝1，y＝1時的Def－Use鏈情況

即取得函數(shù)f 當(dāng)前摘要的符號表達(dá)式： （x＞0）∧（return＿symbol＿f＝1）。以后使用該摘要時，只需要根據(jù)實(shí)參和形參的對應(yīng)關(guān)系，如y 對應(yīng)x，即可替換成調(diào)用點(diǎn)所在函數(shù)的符號，即 （y＞0）∧ （return＿symbol＿f＝1）。算法以函數(shù)為單位正確收集了分支上的約束條件，由于調(diào)用函數(shù)時保存了實(shí)參和形參的對應(yīng)關(guān)系，從而解決了在過程間符號執(zhí)行期間，約束求解變量的符號統(tǒng)一問題。

3.2 擴(kuò)展的執(zhí)行樹

由于SMART 算法需要隔離對待每個被測函數(shù)，所以本文對傳統(tǒng)的執(zhí)行樹定義進(jìn)行擴(kuò)展。

擴(kuò)展的執(zhí)行樹定義：

（1）執(zhí)行樹是二叉樹，根節(jié)點(diǎn)代表每個函數(shù)的入口。

（2）葉子節(jié)點(diǎn)表示函數(shù)的一條路徑。

（3）非葉子節(jié)點(diǎn)包括2種節(jié)點(diǎn)類型：分支條件和函數(shù)調(diào)用。

（4）分支條件節(jié)點(diǎn)的假分支節(jié)點(diǎn)表示該路徑下條件取假，真分支節(jié)點(diǎn)表示該路徑下條件取真。

（5）函數(shù)調(diào)用節(jié)點(diǎn)的假分支節(jié)點(diǎn)為調(diào)用點(diǎn)之后的分支條件節(jié)點(diǎn)，真分支節(jié)點(diǎn)為被調(diào)函數(shù)的根節(jié)點(diǎn)。

以表1所示程序代碼為例，如果一次動態(tài)實(shí)際執(zhí)行中top 函數(shù)的形參取w＝1，y＝1，那么其經(jīng)過擴(kuò)展后的執(zhí)行樹如圖1所示。函數(shù)top 的執(zhí)行樹由實(shí)線節(jié)點(diǎn)組成，函數(shù)f的執(zhí)行樹由虛線節(jié)點(diǎn)組成。由此可見，本文提出的執(zhí)行樹不但能隔離地表示各個函數(shù)的執(zhí)行情況，而且同時保存了函數(shù)調(diào)用的信息，從而為SMART 算法提供了模型基礎(chǔ)。

3.3 改進(jìn)后的SMART算法

圖1 top 函數(shù)的形參取w＝1，y＝1時程序的執(zhí)行樹

觀察表5所示代碼，按照SMART 算法，由于第3 行有y＞0的約束條件，第4行的函數(shù)調(diào)用只會產(chǎn)生 （x＞0）∧ （return＿symbol＿f＝1）一條摘要，如果下一次迭代中函數(shù)的輸入w 隨機(jī)取到1，由于SMART算法只檢驗(yàn)w 的實(shí)際值是否滿足當(dāng)前函數(shù)摘要，結(jié)果導(dǎo)致第5行的函數(shù)調(diào)用并沒有如預(yù)期產(chǎn)生相應(yīng)的函數(shù)摘要 （x＜＝0）∧ （return＿symbol＿f＝0）（實(shí)際上w 此時是可以取小于等于0的值）。

表5 示例代碼2

所以，在實(shí)際執(zhí)行中，為了獲得更精確的函數(shù)摘要，在遇到函數(shù)調(diào)用時，還需要結(jié)合實(shí)參當(dāng)前的取值范圍來判斷是否可以生成新的函數(shù)摘要?；贑AUT 的擴(kuò)展執(zhí)行樹模型，對SMART 改進(jìn)后的算法描述見表6，其中calling＿context（f）為調(diào)用函數(shù)f 前的約束集合，current＿node為當(dāng)前執(zhí)行樹路徑上的節(jié)點(diǎn)，choice為分支的選擇。

算法的本質(zhì)實(shí)際上是一個構(gòu)造程序執(zhí)行樹的過程，當(dāng)程序遇到函數(shù)f 調(diào)用時，首先在當(dāng)前執(zhí)行樹路徑上添加一個函數(shù)f 的調(diào)用節(jié)點(diǎn)calling＿node，然后檢驗(yàn)參數(shù)的實(shí)際值是否滿足函數(shù)f 摘要，如果不滿足，設(shè)置追溯標(biāo)記backtracking＝1；如果參數(shù)實(shí)際值能滿足，此時仍不能保證當(dāng)前摘要可用，需要對f 執(zhí)行樹上每條不可達(dá)的路徑結(jié)合此次調(diào)用實(shí)參的取值范圍calling＿context（f）進(jìn)行求解，如果有解，說明此次調(diào)用仍可以產(chǎn)生新的摘要，將此解I’作為程序輸入，進(jìn)入下一次迭代。如果無解，表示此次調(diào)用確實(shí)不能生成新的摘要，將f 的函數(shù)摘要作為約束保存到calling＿node，設(shè)置追溯標(biāo)記backtracking＝0。如此便可確保每次函數(shù)摘要都能被充分計算。

表6 補(bǔ)充后的SMART 算法

當(dāng)程序遇到函數(shù)f 體內(nèi)的分支語句時，會根據(jù)追溯標(biāo)志backtracking 來判斷是否需要繼續(xù)構(gòu)造執(zhí)行樹。如果backtracking＝1，說明正在計算函數(shù)新的摘要，函數(shù)f 返回時，將此次f 執(zhí)行樹路徑上的約束集合和返回值作為新的摘要保存，然后對f 的執(zhí)行樹深度優(yōu)先搜索新的路徑，把無解的節(jié)點(diǎn)標(biāo)記為當(dāng)前不可達(dá)路徑，對有解的路徑，則將其解作為程序的輸入進(jìn)入下一次迭代，直到f 的執(zhí)行樹搜索完畢。

4 應(yīng)用和實(shí)驗(yàn)

4.1 應(yīng)用實(shí)例

表7的被測函數(shù)test（）為例，本文將使用SMART 算法和基于CAUT 模型改進(jìn)后的SMART 算法分別進(jìn)行動態(tài)符號執(zhí)行自動化測試。

表7 被測函數(shù)test（）

SMART 算法的測試結(jié)果見表8，根據(jù)生成的函數(shù)摘要來看，測試并沒有覆蓋程序第11行和第17行的分支路徑。

表8 SMART 算法的測試結(jié)果

基于CAUT 模型改進(jìn)后的SMART 測試結(jié)果見表9，由于在判斷函數(shù)摘要的過程中結(jié)合了參數(shù)的當(dāng)前約束，所以能更準(zhǔn)確地計算摘要，最終覆蓋了被測函數(shù)的全部路徑。

4.2 實(shí)驗(yàn)分析

首先對本文出現(xiàn)的3段示例代碼做實(shí)驗(yàn)分析。測試結(jié)果見表10。

表9 改進(jìn)后的SMART 算法的測試結(jié)果

表10 示例代碼實(shí)驗(yàn)結(jié)果

其中表1代碼是簡單的過程間調(diào)用例子，2種算法都能做到完全分支覆蓋；表5代碼是為了測試算法是否能精確計算函數(shù)摘要而設(shè)計的，SMART 由于只采用形參實(shí)際值來檢驗(yàn)函數(shù)摘要是否可用，導(dǎo)致函數(shù)摘要計算受形參隨機(jī)值影響，未能覆蓋被調(diào)函數(shù)的所有分支。而改進(jìn)的SMART 算法由于考慮了形參的當(dāng)前約束，所以排除了隨機(jī)情況的影響，覆蓋了被調(diào)函數(shù)的所有分支；表7代碼是為了測試上述隨機(jī)情況對程序后續(xù)分支的影響，SMART由于沒有精確計算函數(shù)摘要，影響了后續(xù)代碼的分支覆蓋情況。改進(jìn)的SMART 算法則能正常覆蓋調(diào)用點(diǎn)之后的分支。

本文實(shí)驗(yàn)的被測項目對象主要來自SIR［12］，從中選取了bash，flex和make這3個開源項目，實(shí)驗(yàn)結(jié)果見表11。實(shí)驗(yàn)?zāi)康氖菣z測CAUT 在基于改進(jìn)前后的SMART 算法上針對分支覆蓋標(biāo)準(zhǔn)的支持度。從結(jié)果中可以看到，雖然SMART 算法已經(jīng)能對程序提供較好的覆蓋率，但改進(jìn)后的算法仍然提高了原先的覆蓋率，原因主要是在判斷函數(shù)摘要是否可用的過程中結(jié)合了參數(shù)的當(dāng)前約束，所以能更準(zhǔn)確地計算摘要。

表11 被測項目指標(biāo)及實(shí)驗(yàn)結(jié)果

5 結(jié)束語

本文介紹了自動化測試用例生成技術(shù)中動態(tài)符號執(zhí)行的基本概念和原理，并基于SMART 的過程間數(shù)據(jù)流分析算法，在相關(guān)項目工具CAUT 的實(shí)現(xiàn)基礎(chǔ)上，針對C 語言進(jìn)行研究，建立了一套詳細(xì)可行的過程間動態(tài)符號執(zhí)行模型，解決了過程間調(diào)用時實(shí)參和形參變量的符號統(tǒng)一問題，同時對SMART 算法進(jìn)行改進(jìn)，使其在實(shí)際應(yīng)用中能更準(zhǔn)確地計算函數(shù)摘要。

動態(tài)符號執(zhí)行將在未來一段時間內(nèi)成為自動測試?yán)碚撗芯康闹髁骺蚣埽绾卧贑 語言的過程間動態(tài)符號執(zhí)行中處理指針和復(fù)雜內(nèi)存操作的函數(shù)摘要模型將會是本文未來的工作方向。

［1］Godefroid P，Klarlund N，Sen K.Dart：Directed automated random testing ［C］／／Proceedings of the 5th International Haifa Verification Conference on Hardware and Software：Verification and Testing，2009.

［2］Cadar C，Dunbar D，Engler D.Klee：Unassisted and automatic generation of high－coverage tests for complex systems programs［C］／／Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation， 2008：209－224.

［3］Tillmann N，Halleux J De.Pex：White box test generation for net［C］／／Proceedings of the 2nd International Conference on Tests and Proofs，2008：134－153.

［4］Person S，Yang G，Rungta N，et al.Directed incremental symbolic execution ［C］／／Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation，2011：504－515.

［5］Cadar C，Godefroid P，Khurshid S，et al.Symbolic execution for software testing in practice：Preliminary assessment［C］／／New York：Proceedings of the 33rd International Conference on Software Engineering，2011：1066－1071.

［6］Xu Guoqing，Rountev A.AJANA：A general framework for source－code－level inter procedural dataflow analysis of aspect software［C］／／Proceedings of the 7th International Conference on Aspect－Oriented Software Development，2008：36－47.

［7］Godefroid P.Compositional dynamic test generation ［J］.ACM SIGPLAN Notices，2007，42 （1）：47－54.

［8］Yu Xiao，Sun Shuai，Pu Geguang，et al.A parallel approach to concolic testing with low－cost synchronization ［C］／／Proc the 4th International Wokshop on Harnessing Theories for Tool Support in Software，2010：83－96.

［9］Wang Zheng，Yu Xiao，Sun Tao，et al.Test data generation for derived types in C program ［C］／／Proc the 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering，2009：155－162.

［10］ Moura L de，Bjrner N.Z3：An efficient SMT solver［C］／／Proceedings of Tools and Algorithms for the Construction and Analysis of Systems，2008：337－340.

［11］Stanier J，Watson D.Intermediate representations in imperative compilers：A survey ［J］.ACM Computing Surveys，2013，45 （3）：1－26.

［12］Bertolino A.Software testing research：achievements，challenges，dreams ［C］／／Future of Software Engineering，2007：85－103.