裝備軟件接口測試自動化研究＊

孫 寧 劉 丹

（1.海軍裝備研究院 北京 100161）（2.中電科技（北京）有限公司 北京 100083）

1 引言

現(xiàn)代戰(zhàn)爭中，裝備戰(zhàn)斗力的70%是由軟件實現(xiàn)的。美軍F22戰(zhàn)機的軟件已經(jīng)超過2500萬行源代碼，福特級航母和朱姆沃爾特級驅(qū)逐艦及新型攻擊型核潛艇的軟件遠(yuǎn)遠(yuǎn)超過5000萬行源代碼。如此龐大的源代碼要是沒有嚴(yán)格的檢測措施，可想而知出錯率是相當(dāng)高的。同樣，隨著各類信息化裝備不斷裝備部隊，我軍裝備軟件正呈現(xiàn)出多樣化、復(fù)雜化和智能化等特點，其質(zhì)量直接影響著軍事指揮和武器裝備作戰(zhàn)效能的發(fā)揮［1］。

裝備軟件測試主要包括功能測試、接口測試、性能測試、強度測試、余量測試等。接口測試在裝備軟件測試中占重要地位。以艦艇指控系統(tǒng)為例，與外部通過以太網(wǎng)交聯(lián)的設(shè)備包括武器、傳感器、通信設(shè)備及其他系統(tǒng)，達(dá)三十幾種外部接口，接口實現(xiàn)的正確與否直接影響了裝備指揮控制流程和各系統(tǒng)之間的協(xié)調(diào)一致。本文的接口測試特指的是接口測試，接口測試是驗證接口數(shù)據(jù)的正確性和協(xié)調(diào)性，也就是驗證網(wǎng)絡(luò)中的報文數(shù)據(jù)滿足接口協(xié)議規(guī)定的內(nèi)容。

本文針對接口數(shù)據(jù)各字段間存在的控制或數(shù)據(jù)依賴關(guān)系，提出了一種利用符號執(zhí)行約簡測試用例空間的算法。給出了基于控制流圖的程序參數(shù)依賴關(guān)系定義；在此基礎(chǔ)上，根據(jù)輸入?yún)?shù)變量在程序執(zhí)行時的信息流，提出了一種參數(shù)依賴關(guān)系的動態(tài)分析算法。

本文根據(jù)上述方案設(shè)計實現(xiàn)了一個接口自動測試工具，通過利用符號執(zhí)行約簡測試用例空間的算法設(shè)計出輸入域數(shù)據(jù)，采用XML語言實現(xiàn)數(shù)據(jù)的自動化描述和比對。在實際應(yīng)用中，提高了接口測試數(shù)據(jù)設(shè)計的完備性［9］，提高了裝備軟件接口測試的工作效率和質(zhì)量。

2 接口測試數(shù)據(jù)的設(shè)計

接口測試除了對數(shù)據(jù)包頭、結(jié)束位、校驗位、標(biāo)志位的驗證，重點內(nèi)容是對各個字段的驗證。在測試數(shù)據(jù)設(shè)計時，往往采用等價類劃分的方法對每個字段選取有限集合，然后對所有字段進行窮舉組合的方式，這種方式對少量字段的組合似乎可行，但是對復(fù)雜字段的測試數(shù)據(jù)設(shè)計來說往往是災(zāi)難性的，其數(shù)據(jù)量是設(shè)計和實施都無法接受的。以某導(dǎo)航信息接口為例，如果按照等價類劃分后窮舉組合的方法，對一個接口的測試用例數(shù)據(jù)共有6×1023組，對一型裝備來說類似的接口有300個左右的規(guī)模，可見采用有效等價類劃分后窮舉組合和方式其成本和進度是裝備軟件測試無法接受的，但是測試質(zhì)量得不到保證同樣是無法接受的。如何使測試設(shè)計和執(zhí)行在時間和成本資源的約束下成為可能，而且使測試質(zhì)量得到充分保證是困擾和制約軟件測試的一個亟待解決的問題［2，5］，裝備軟件測試對接口測試的要求更加嚴(yán)格，時間和成本制約更為明顯。

接口數(shù)據(jù)各個字段之間并不是完全獨立的，有些字段之間存在著較強的邏輯關(guān)系，而有些字段之間沒有關(guān)系。通過對一些程序源代碼以及可信軟件棧（Tcg Software Stack，TSS）［3，6］進行深入分析，發(fā)現(xiàn)測試函數(shù)的部分參數(shù)變量相對獨立，不存在與其他變量的依賴關(guān)系。因此，可利用符號執(zhí)行的方法將獨立的變量分離出來，達(dá)到將參數(shù)空間動態(tài)分區(qū)的效果，即其相應(yīng)的取值空間因相互組合而成的指數(shù)關(guān)系會化簡為線性關(guān)系。這一方面降低了測試用例的取值規(guī)模，額外的測試用例無法檢測更多的程序行為，另一方面不會因此降低測試的原有檢錯能力。

基于代碼的分析和測試都需要對代碼進行抽象，進而建立一種中間模型，控制流圖（Control Flow Graph，CFG）是一種常用的中間模型［10］。

定義1（控制流圖） 控制流圖是以基本塊（basic block）為節(jié)點的有向圖。所謂基本塊，是程序中具有唯一入口和唯一出口的語句序列，其中不包含條件轉(zhuǎn)移語句?；緣K中語句在程序執(zhí)行過程中要么全都執(zhí)行，要么全都不執(zhí)行。形式化地說，控制流圖是一個有向圖G＝〈X，L，op，E〉。其中，X為變量集合，子集x0?x為輸入向量；L代表程序基本塊節(jié)點的集合，l0∈L為特定的開始結(jié)點；函數(shù)op表示l0∈L中塊節(jié)點的基本操作｛halt｜abort｜x：＝e｜if（x）thenl′elsel″｝，其中，halt為程序正常中止，abort為程序錯誤退出，賦值語句x∶＝e，x∈X且e是X上的運算表達(dá)式，條件語句if（x）thenl′elsel″，x∈X且l′，l″∈L；E?L＊L表示兩個節(jié)點之間的轉(zhuǎn)移，N（l）為唯一的鄰居節(jié)點。

控制流圖是所有依據(jù)程序推演依賴關(guān)系的基礎(chǔ)，形象地展示了信息是如何沿著語句流進行傳播的。為影響計算結(jié)果，程序的每個語句都必須（至少潛在地）以某種方式影響信息流，因此變量間可能存在某種控制或數(shù)據(jù)上的依賴關(guān)系。

定義2（后支配關(guān)系） 對于控制流圖上的兩個節(jié)點l，l′∈L，如果每條從l到lhalt的路徑上都包含l′，則l′是l的后支配節(jié)點。當(dāng)滿足以下條件時，l′是l的直接后支配節(jié)點，記做l′＝idom（l）：1）l′≠l；2）l′是l的后支配節(jié)點；3）對于l的每個后支配節(jié)點l″，同時也是l′的后支配節(jié)點?？刂屏鲌D上每個節(jié)點都有唯一的直接后支配節(jié)點［4］，因此函數(shù)idom（l）對于每個l≠lhalt的節(jié)點是良構(gòu)的。

定義3（前支配關(guān)系） 對于控制流圖上的兩個節(jié)點l，l′∈L，如果每條從lroot到l的路徑上都包含l′，則l′是l的前支配節(jié)點。當(dāng)滿足以下條件時，l′是l的直接前支配節(jié)點：1）l′≠l；2）l′是l的前支配節(jié)點；3）對于l的每個前支配節(jié)點l″，同時也是的前支配節(jié)點。

定義4（控制依賴） 如果控制流圖上存在某條執(zhí)行路徑l0…l…l′，并且idom（l′）并不存在于l′與l之間的路徑上，則認(rèn)為l控制依賴于l′。

定義5（節(jié)點間數(shù)據(jù)依賴） 如果滿足以下條件，則認(rèn)為節(jié)點B數(shù)據(jù)依賴于節(jié)點A：

1）節(jié)點A寫入某個變量V（或者更一般地說，寫入部分程序狀態(tài)），隨后該變量V被節(jié)點B讀取；

2）在控制流圖上至少有一條從A至B的路徑，在該路徑上V沒有被其他任何節(jié)點所更新。

定義6（輸入變量間的數(shù)據(jù)依賴） 給定表達(dá)式e和程序的輸入變量集合X，Use（e）用于表示e中包含輸入變量的集合，對于兩個變量x，y∈X，如果存在一條到節(jié)點l的路徑，op（l）：x＝e且y∈Use（e），則認(rèn)為變量x數(shù)據(jù)依賴于變量y。

利用符號執(zhí)行的方法分析輸入?yún)?shù)變量間的依賴關(guān)系，并對參數(shù)空間進行劃分的基本思想是［7］：1）將程序的輸入?yún)?shù)空間按所有變量相互獨立的假設(shè)進行初始分區(qū)；2）在使用符號變量依次代替各參數(shù)變量執(zhí)行的過程中，如果發(fā)現(xiàn)來自于不同分區(qū)的輸入變量之間存在依賴關(guān)系，則將相應(yīng)的分區(qū)合并；3）經(jīng)過反復(fù)合并后，最終形成的分區(qū)之間是相互獨立的，不同分區(qū)的參數(shù)變量之間不存在信息流的流動。

為此，首先就輸入?yún)?shù)空間的分區(qū)提出以下定義：

定義7（分區(qū)集） 輸入變量集合X的分區(qū)集H（X）是集合X的若干不相交子集的集合X＝∪Y∈H（x）Y；分區(qū)集中的每個子集稱為該分區(qū)集的塊（block）；對于變量x∈X，H（X）［x］用于表示包含變量x的塊。

定義8（分區(qū)合并） 給定1個分區(qū)集H（X）和該分區(qū)集中若干塊的子集合Y?H（X），在子集合Y合并為1個塊后，分區(qū)集H（X）為Merge（H（X），Y）＝（H（X）－Y）∪｛∪a∈Ya｝

本文提出算法用于分析輸入?yún)?shù)間的依賴關(guān)系，從而對輸入空間進行劃分［8］，輸入?yún)?shù)依賴關(guān)系分析算法如下：

算法中的輸入為程序P、輸入?yún)?shù)集合X的初始分區(qū)H0（X）。算法中的數(shù)據(jù)結(jié)構(gòu)包括：局部變量Hcur記錄由于控制或數(shù)據(jù)的依賴關(guān)系而更新的“現(xiàn)行”輸入分區(qū)，初始值為H0（X）；局部變量Hold，用于檢查在一輪執(zhí)行中是否對輸入分區(qū)進行了修改，初始值為空集。映射關(guān)系（flow map）是用于存儲依賴關(guān)系的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，將每一個輸入變量x∈X映射到當(dāng)前輸入分區(qū)塊集上flow：X→2H。形象地說，flow（x）表示所有影響（數(shù)據(jù)或控制依賴）變量x的輸入塊的集合。

在每一輪循環(huán)中，調(diào)用Generate函數(shù)針對現(xiàn)行分區(qū)中的每塊I（I∈Hcur）進行測試。將塊I中的變量作為符號變量，而I之外分區(qū)的變量取隨機的初始值，將兩個部分的合并作為程序的輸入。

算法中的主循環(huán)Generate函數(shù)的主要功能是：使用符號執(zhí)行的方法在遍歷程序內(nèi)部的可執(zhí)行路徑的過程中，收集動態(tài)依賴信息，并由此更新輸入映射關(guān)系flow（x）。最終，該映射關(guān)系用于合并Hcur中的塊，從而得到一個新的分區(qū)。新合并后的分區(qū)是初始分區(qū)｛Hcur［x］｝的粗糙分區(qū)。當(dāng)某一輪輸入分區(qū)不再發(fā)生變化時，循環(huán)停止Generate函數(shù)的輸入為程序P、輸入分區(qū)H、映射關(guān)系flow、分區(qū)中的塊I、I之外分區(qū)的初始輸入input和一個路徑索引last，Generate函數(shù)用于跟蹤最近一次訪問的程序分支。Generate函數(shù)采用深度優(yōu)先的遍歷算法，將通路條件中的約束條件從后向前依次求反，選擇新的可執(zhí)行路徑。

通過應(yīng)用該算法，接口測試數(shù)據(jù)量大大降低，共計算出6萬條測試數(shù)據(jù)組合，達(dá)到了將指數(shù)關(guān)系化簡為線性關(guān)系的顯著效果，且用例的規(guī)模是可以接受的，可以工程化實現(xiàn)的，但是付出的代價是依賴于對源代碼的進行數(shù)據(jù)流分析。

3 結(jié)語

實驗結(jié)果表明：該方法在約簡測試用例空間上具有較強的實用性，同時不會降低測試原有的檢錯能力，通過自動化的篩選和比較大大提高了接口測試的效率和質(zhì)量。

［1］李曉莉，龍翔，劉超，等.軍用軟件測試現(xiàn)狀及對策［J］.裝甲兵工程學(xué)院學(xué)報，2008，22（5）：66－69.

［2］MYERS G J.The art of software testing［M］.New Jersey：John Wiley ＆Sons，1979：12－15.

［3］Trusted Computing Group.TCG software stack（TSS）specification，version 1.2［EB／OL］. （2005－06－10）［2009－09－30］.https：www.trustedcomputinggroup.org.

［4］MUCHN ICK S.Advanced compiler design and implementation［M］.San Francisco：Morgan Kaufmann，1997：256－263.

［5］Berndt D J，F(xiàn)isher J，Johnson L，et al.Breeding software test case with genetic algorithms［C］／／Proceedings of the 36th Hawaii international conference on system science（HICSS－36），Hawaii，January 2003.

［6］Berndt D J，Watkins A.Investigating the performance of genetic algorithm－based software test case generation［C］／／Proceedings of the 8th IEEE international symposium on high assurance systems engineering（HASE'04），University of South Florida；march 25－26，2004：261－2.

［7］Wegener J，Baresel A，Sthamer H.Suitability of evolutionary algorithms for evolutionary testing［C］／／Proceedings of the 26th annual international computer software and application conference，Oxford，England，August 26－29，2002.

［8］Hermadi I.Genetic algorithm based test data generator［D］.Saudi Arabia：Department of Information and Computer science，King Fahd University of Petroleum and Minerals，2004.

［9］Hamlet D.Foundation of software testing：dependability theory［D］.Protland：Portland University，1994.

［10］Edvardsson J.A Survey on automatic test data generation［C］／／proceedings of 2nd conference on computer science and engineering，Linkoping：ESCEL；October 1999.P.21-8.