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

孫 寧 劉 丹

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

1 引言

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

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

本文針對接口數據各字段間存在的控制或數據依賴關系，提出了一種利用符號執行約簡測試用例空間的算法。給出了基于控制流圖的程序參數依賴關系定義；在此基礎上，根據輸入參數變量在程序執行時的信息流，提出了一種參數依賴關系的動態分析算法。

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

2 接口測試數據的設計

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

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

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

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

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

定義2（后支配關系） 對于控制流圖上的兩個節點l，l′∈L，如果每條從l到lhalt的路徑上都包含l′，則l′是l的后支配節點。當滿足以下條件時，l′是l的直接后支配節點，記做l′＝idom（l）：1）l′≠l；2）l′是l的后支配節點；3）對于l的每個后支配節點l″，同時也是l′的后支配節點。控制流圖上每個節點都有唯一的直接后支配節點［4］，因此函數idom（l）對于每個l≠lhalt的節點是良構的。

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

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

定義5（節點間數據依賴） 如果滿足以下條件，則認為節點B數據依賴于節點A：

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

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

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

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

為此，首先就輸入參數空間的分區提出以下定義：

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

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

本文提出算法用于分析輸入參數間的依賴關系，從而對輸入空間進行劃分［8］，輸入參數依賴關系分析算法如下：

算法中的輸入為程序P、輸入參數集合X的初始分區H0（X）。算法中的數據結構包括：局部變量Hcur記錄由于控制或數據的依賴關系而更新的“現行”輸入分區，初始值為H0（X）；局部變量Hold，用于檢查在一輪執行中是否對輸入分區進行了修改，初始值為空集。映射關系（flow map）是用于存儲依賴關系的關鍵數據結構，將每一個輸入變量x∈X映射到當前輸入分區塊集上flow：X→2H。形象地說，flow（x）表示所有影響（數據或控制依賴）變量x的輸入塊的集合。

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

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

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

3 結語

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

［1］李曉莉，龍翔，劉超，等.軍用軟件測試現狀及對策［J］.裝甲兵工程學院學報，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，Fisher 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.