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

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

0 引 言

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

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

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

1 動(dòng)態(tài)符號(hào)執(zhí)行

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

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

1.1 過(guò)程間動(dòng)態(tài)符號(hào)執(zhí)行

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

1.2 CAUT

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

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

2 SMART算法

SMART （systematic modular automated random testing），是由Patrice Godefroid等人提出的過(guò)程間動(dòng)態(tài)符號(hào)執(zhí)行算法。其核心的思想是隔離地對(duì)待程序中每一個(gè)函數(shù)，根據(jù)每次函數(shù)調(diào)用時(shí)參數(shù)的實(shí)際值來(lái)計(jì)算或者使用函數(shù)摘要，從而減少符號(hào)執(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 的返回值符號(hào)。

表1 示例代碼1

2.2 SMART算法

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

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

表2 SMART 算法

3 基于SMART算法的CAUT模型

3.1 Def－Use鏈

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

表3 CAUT 的Def－Use算法

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

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

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

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

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

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

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

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

（3）非葉子節(jié)點(diǎn)包括2種節(jié)點(diǎn)類(lèi)型：分支條件和函數(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所示程序代碼為例，如果一次動(dòng)態(tài)實(shí)際執(zhí)行中top 函數(shù)的形參取w＝1，y＝1，那么其經(jīng)過(guò)擴(kuò)展后的執(zhí)行樹(shù)如圖1所示。函數(shù)top 的執(zhí)行樹(shù)由實(shí)線節(jié)點(diǎn)組成，函數(shù)f的執(zhí)行樹(shù)由虛線節(jié)點(diǎn)組成。由此可見(jiàn)，本文提出的執(zhí)行樹(shù)不但能隔離地表示各個(gè)函數(shù)的執(zhí)行情況，而且同時(shí)保存了函數(shù)調(diào)用的信息，從而為SMART 算法提供了模型基礎(chǔ)。

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

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

觀察表5所示代碼，按照SMART 算法，由于第3 行有y＞0的約束條件，第4行的函數(shù)調(diào)用只會(huì)產(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)用并沒(méi)有如預(yù)期產(chǎn)生相應(yīng)的函數(shù)摘要 （x＜＝0）∧ （return＿symbol＿f＝0）（實(shí)際上w 此時(shí)是可以取小于等于0的值）。

表5 示例代碼2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

動(dòng)態(tài)符號(hào)執(zhí)行將在未來(lái)一段時(shí)間內(nèi)成為自動(dòng)測(cè)試?yán)碚撗芯康闹髁骺蚣?，而如何在C 語(yǔ)言的過(guò)程間動(dòng)態(tài)符號(hào)執(zhí)行中處理指針和復(fù)雜內(nèi)存操作的函數(shù)摘要模型將會(huì)是本文未來(lái)的工作方向。

［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.