基于節點層網絡關鍵等級的嵌入式軟件集成測試序列生成方法

李騰飛 石磊

摘要：增量法是應用于集成測試的方法，合適的增量集成策略能夠降低測試成本、保障測試的充分性、提高測試效率。針對目前嵌入式軟件集成測試增量方法不明確、對于函數調用關系驗證不充分等問題，通過參考集成測試相關國家標準并結合嵌入式軟件的特點進行深入分析，提出一種新的集成測試序列生成方法。該方法從集成測試函數調用關系的充分性入手，按照以“層間集成”為主、“層內關鍵系數集成”為輔的設計思路，將嵌入式軟件中的函數基于節點層和關鍵系數以集成的先后順序劃分，得到經粗調和微調后的增量集成序列。該方法能簡單、高效地解決集成測試增量集成問題，具備工程實踐應用意義。

關鍵詞：嵌入式軟件;軟件集成測試;增量法;關鍵系數;節點層網絡

An Embedded Software Integration Test Order Method

Based on the Node?Layer Net Criticality

LI Teng?fei，SHI Lei

（Luoyang Photoelectric Technology Development Center， Luoyang 471000，China）

Abstract：Incremental Integration strategy is applied to integration testing and appropriate incremental Integration strategy could be used to reduce high?cost， ensure sufficiency and increase efficiency to a large extent. Aimed to solving problems of insufficiency of function calling testing and unclear of increasing methods， a novel method of node?layer net for generating integration testing sequence by deeply analyzing National Military Standard and characteristic of embedded software is presented. By combining outer?layer and inner?layer factors to generate integration testing sequence， the sufficiency of interface testing between different function could be guaranteed. In conclusion， the method can solve the problems of incremental integration in integration test?simply and efficiently， and has engineering practice and application significance.

Key Words：embedded software; software integration testing;increasing method;critical coefficient;node?layer net

0?引言

嵌入式軟件作為軟件應用領域的重要分支，在日新月異的科技發展中也發生著快速變革。軟件復雜度的提高、功能多樣性的增強，以及接口調用豐富性的完善對傳統測試提出了更高的技術要求。集成測試采用增量法對函數調用關系進行驗證，保障軟件產品質量[1?2]。

近年來，許多增量集成測試序列生成方法被提出并應用于工程化實踐，取得了較好的應用效果[3?5]。基于復雜網絡的類間集成測試序列生成方法將類抽象成節點，建立復雜網路模型，解決了面向對象的集成測試序列生成問題[6?7]。嵌入式軟件功能路徑測試用例自動生成方法結合了嵌入式軟件的功能特點，使集成測試用例生成更加便捷、高效[8]。基于軟件節點重要性的集成測試序列生成方法引進了軟件節點重要程度的評估方案，保障測試樁復雜度的約束前提，讓重要節點優先集成測試[9]。

函數內外關系交錯是提升集成復雜度的重要因素。復雜性高的函數引入錯誤的概率相對較大，在進行測試時需要重點關注[10]。對復雜程度高、出錯概率大和發生錯誤后傳播范圍廣的函數優先測試，能有效規避錯誤風險。

本文提出基于節點層網絡關鍵等級的嵌入式軟件集成測試序列生成方法。該方法充分考慮函數接口調用對軟件集成測試的影響程度，采用自上而下的集成策略，讓復雜程度高、關鍵性強的函數優先被集成、驗證。在相同的測試條件下該方法既保障了集成測試效率，又提高了集成測試的充分性、保證了嵌入式軟件產品質量。

1?方法建模

1.1?基于節點層網絡的層間集成模型

嵌入式軟件調用關系分為靜態和動態兩種類型。動態調用關系依據代碼動態執行路徑獲取，路徑隨著初始化變量條件的變化而產生較大差別。靜態調用不實際執行代碼，僅僅依賴對代碼中非系統函數的靜態掃描實現對函數靜態調用關系的全覆蓋。通常靜態調用關系圖能夠涵蓋所有的動態調用，故靜態集成測試方案也將適用于動態集成。本節將基于靜態函數調用關系網絡，建立該軟件的節點層模型[11?14]。

定義1?靜態調用圖：以main函數作為開始節點，靜態掃描該節點函數代碼中所有非系統函數，將掃描結果作為靜態調用圖第二層。依次類推進行迭代，直至將所有代碼文件掃描完畢后形成函數靜態調用關系層次圖。

定義2?節點層：函數靜態調用關系網絡模型中的所有葉子節點同屬于一個節點層。

定義3?關鍵性等級：用以表征網絡中層和節點的關鍵程度（重要程度），通常分為層間關鍵性等級和層內關鍵性等級，層間的關鍵性等級高于層內關鍵性等級。網絡中所有關鍵性等級之和構成了整個網絡的關鍵性等級。網絡節點屬性和結構固定，關鍵性將保持不變。

定理1?同一節點層的節點在靜態調用圖中有相同的層間關鍵性等級。

證明：?對于多層網絡構建節點層模型，節點集合N={N?1，N?2，N?3，…，N?M} ，葉子節點集合Y={Y?1，Y?2，Y?3，…，Y?P}，滿足YN且P≤M。Y?i∈Y可以構建兩層網絡N-{Y?i}→{Y?i}，使N-{Y?i}和Y?i具有不同的關鍵性等級，即K?N-{Y?i}≠K?{Y?i} 且滿足K?N-{Y?i}>K?{Y?i}，K?N=K?N-{Y?i}+K?Y?i。當M1時，K?N-{Y?i}K?Y?i可知K?N=K?N-{Y?i}，進而得到K?N-{Y?i}=K?N-{Y?j}，K?i=K?j，（0≤i≠j≤P）。

靜態調用圖和節點層網絡在分層上存在較大差別。靜態調用圖的同層節點基于自上而下的調用關系得到，而節點層網絡模型是通過自下而上的方式得到的，因同一節點層的節點在靜態調用圖中有相同的層間關鍵性等級，從而使函數層間模型劃分更加合理。

基于靜態調用圖可以得到節點層網絡模型。從靜態調用圖中迭代刪除所有葉子節點，直至所有函數節點被覆蓋完畢。不同層的網絡節點具備不同的關鍵性等級，從main函數開始的第一層計算，節點層的關鍵性等級隨著網絡層的遞增而降低。為了保障層間關鍵性等級的絕對主導，要求節點層間的關鍵性大于該層內任意節點的關鍵性。用?L?i（i=1，2，…，N）表征不同層的關鍵性等級，F?ij表征第i層第j個函數的節點關鍵性系數。通常要求L?i?≥max?（F?ij）。具體節點層劃分算法流程如圖1所示。

1.2?基于節點關鍵等級的層內集成模型

《GJBZ102A-2012軍用軟件安全性設計指南》對嵌入式軟件安全性設計進行了說明，并對影響嵌入式軟件代碼品質的因素進行了列舉和解釋，其中扇入數、扇出數、代碼行數、靜態調用次數均為常見的影響代碼品質的因素，基于上述因素，創建關鍵節點的層內集成模型[15?17]。

定義4?品質因素矩陣：以節點為行，節點屬性值扇入數、扇出數、代碼行數和靜態調用次數為列構成的矩陣表示形式。

設函數節點的扇入數為RR（單位：個），函數節點的扇出數為RC（單位：個），函數節點的代碼行數為DH，函數節點被調用次數為DN，關鍵函數量化指標用GJ標識。

不考慮同層節點之間的耦合關系，并假設RR、RC、DH和DN在函數調用關系圖中相互獨立[18]。因此可得：

其中：?α，β，γ，δ為任意常數，i，j表示節點網絡層的第i層第j?個節點。假設RR、RC、DH、DN和other兩兩獨立，簡化得：

令GJ?ij∝GJ?ij，GJ?ij表示函數節點關鍵性系數，進而得：

約束條件：α+β+γ+δ=1，0<α，β，γ，δ<1，k為任意常數。

基于品質因素矩陣，利用上述公式可以計算出同節點層函數的關鍵性系數，從而得到該嵌入式軟件節點層等級的層內集成模型。該模型充分考慮函數節點關鍵性影響因素，創建可靠的層內集成模型，保障了層內集成的合理性和有效性。

1.3?評價指標

1.3.1?運算效率指標

基于節點層網絡關鍵等級的嵌入式軟件集成測試算法的計算復雜度，由節點關鍵性計算復雜度和排序復雜度組成，分別用?P?computer和P?rank表示。對于有m個節點的第M個節點層，依據二分法排序復雜度計算公式（假設單個節點層內和層間關鍵系數計算復雜度相同，即P?inner=P?outer），得到節點層的計算復雜度和排序復雜度如下：

從而得到第M層計算效率的調和平均結果：

其中β 為任意常數。

有N個節點層網絡的節點關鍵性計算復雜度為：

其中m?i 表示第i層網絡節點個數。

1.3.2?充分性指標

關鍵性等級高的節點出錯概率更高，應被優先集成測試，對于該類節點的驗證也應更加充分。在增量集成測試中，通過動態執行測試用例實現接口驗證，若測試用例先被執行，則被動態執行的次數也就更多。基于此構建該算法的充分性指標模型，將充分性量化成節點參與集成驗證的次數?N?i，其中i∈（1，2，3，…，m），m?為節點總數，即：

其中K為節點的關鍵性等級集合，K?i為第i個節點的關鍵性等級系數，即：N?i∝K?i。

2?算法實現

基于層間、層內增量集成模型，形成基于節點層網絡關鍵等級的嵌入式軟件集成測試序列生成算法。具體實施步驟如下：

步驟1：?利用嵌入式軟件C代碼，生成函數（系統函數除外）的靜態調用圖和嵌入式軟件的品質影響因素矩陣Q。

步驟2：依據靜態調用圖構建節點層網絡的層間集成模型，共生成M個節點層，節點的層間關鍵性系數用L?i（i=1，2，3，…，m）表示。

步驟3：將品質影響因素矩陣Q按照層內的關鍵性等級計算公式分別計算各層節點的層內關鍵性系數F?ij（第i層的第j個節點）。

步驟4：計算節點層網絡的關鍵系數。在M層N個節點的節點層網絡中，C?ij（i<M，j<N）表示第i層，第j個節點的關鍵系數。故：

為計算方便，通常取?L?i?=max（?F?ij?），代入式（9）可得：

將層內節點的關鍵性系數計算公式代入式（11）：

步驟5：對同層?C?ij?進行二分法排序，輸出嵌入式軟件集成測試的增量集成序列[19?21]。

3?測試實例

本節應用基于節點層網絡關鍵等級的嵌入式軟件集成測試序列生成方法，對復雜的嵌入式軟件進行增量測試序列生成和結果分析。選取嵌入式工程軟件進行實驗，統計發現該軟件共包含172個非系統函數單元（為了簡化后續描述，對軟件基于函數單元進行編號，共生成編號1-172）。單個函數的最長代碼行數達到291行、最大調用頻率高達48次，最大扇入數14，最大扇出數30。基于上述統計信息，繪制該軟件經排序后的屬性圖，如圖3所示。

經分析可知，該軟件函數調用交聯復雜，層內調用和層間調用交錯，單次調用與多次調用并存，直接進行系統級增量集成序列生成研究相對困難。為此，本文引進系統論思維，對自上而下的靜態調用關系參考節點層模型進行自下而上的層間關系劃分，將屬性相似的節點進行歸類，得到層間集成模型，接著引入層內關鍵系數因素影響，實現增量集成序列生成。

該算法通過自下而上的方式進行節點層劃分，每刪除一層葉子節點就會產生新的葉子節點，減少節點總數。通過多次迭代，共生成12層網絡節點層，不同層之間的節點組如表1所示，因為刪除了連續的葉子節點，故同層節點層間關鍵性等級相同，實現了對函數集成順序的粗略排序。

建立節點關鍵等級的層內集成模型，并結合表1對同節點層函數按照關鍵性等級大小進行排序，排序結果采用自上而下的集成方式進行連接，函數序列集成如圖4所示。

4?測試結果分析

4.1?運算效率

節點層網路采用分層算法，將總節點依據節點相似性原則進行分類、生成相應節點層，而非節點層網絡不存在節點層劃分，將所有節點等層看待。基于上述邏輯，本文分別計算相同網絡條件下的節點層和非節點層算法得到的集成測試增量模型效率，如表2所示。

比較可知，與非節點層網絡相比，節點層網絡進行增量集成可提升16%的運算效率。

4.2?測試充分性

進一步量化層間關鍵性系數，取下層節點關鍵系數集合的最大值作為該層間關鍵性系數，即?L?i?=max?（F?ij）?，層內節點關鍵系數與該值相加，得到該節點的網絡關鍵性等級系數。

通常增量集成測試的充分性和節點被動態執行的次數正相關，動態執行次數越多，測試充分性越高。每增加一個函數集成點，就需要集成網絡動態驗證一次。受網絡調用關系約束，新加入節點在一次動態執行中將至少被執行一次。為了計算方便，設該網絡動態執行一層能夠實現對所有調用接口的全覆蓋。從而可以得到整個網絡函數的關鍵系數隨著網絡增量集成次數變化的曲線。

從圖5中可知，節點關鍵系數隨著集成次數依次衰減。關鍵系數越大則節點接口相對越復雜，在集成測試中被動態執行的次數就越多，節點接口驗證更充分;關鍵系數越小則節點相對簡單，在集成測試中被動態執行的次數越少，節點接口驗證更合理，從而有效提升了集成測試對接口驗證的充分性。

5?結語

函數調用關系復雜，以函數整體為對象進行集成測試增量技術研究，會帶來測試成本較高、測試不充分等問題。基于層間節點層劃分和層內節點關鍵等級排序結合的方法有效解決了以上問題。首先，通過自下而上的節點層劃分算法實現對函數節點集成順序的粗略劃分;再采用自上而下的策略，完成對不同層內節點關鍵性等級的計算;最后，將節點關鍵性等級在網絡結構內進行量化和動態排序，實現了對節點的增量集成以及增量集成序列的生成。關鍵性等級高的函數集成順序靠前，進行集成測試時被驗證次數較多，驗證也更加充分;關鍵性等級低的函數，接口調用相對簡單、集成順序靠后，驗證次數較少。通過該集成算法，可讓整個增量集成方式更加合理、有效。

參考文獻：

[1]?GJB/Z 141-2004，軍用軟件測試指南[S].北京：總裝備部軍標出版發行部，2004.

[2]?蔡建平.嵌入式軟件測試實用技術[M].北京：清華大學出版社， 2010.

[3]?單錦輝，姜瑛，孫萍.軟件測試研究進展[J].北京大學學報：自然科學版，2005，41（1）：134?145.

[4]?王艷青，于海洋.計算機軟件測試技術綜述[J].電子技術與軟件工程，2017（22）：47?48.

[5]?陸春.軟件集成測試解析[J].信息化研究，2014（1）：10?12.

[6]?趙玉麗，王瑩，于海，等.基于復雜網絡的類間集成測試序列生成方法[J].東北大學學報：自然科學版，2015，36（12）：1696?1700.

[7]?ZHANG Y， JIANG S， WANG X， et al. An optimization algorithm applied to the class integration and test order problem[J]. Soft Computing， 2018：1?15.

[8]?胡燕京，張毅坤，朱偉，等.嵌入式軟件功能路徑測試用例自動生成研究[J].微電子學與計算機，2010，27（1）：81?85.

[9]?王瑩，于海，朱志良.基于軟件節點重要性的集成測試序列生成方法[J].計算機研究與發展，2016，53（3）：517?530.

[10]?MUNSON J C， KHOSHGOFTAAR T M. The detection of fault?prone programs[J]. IEEE Transactions on Software Engineering， 1992，18（5）：423?433.

[11]?趙磊，倫立軍，徐士華.基于軟件體系結構的測試路徑生成方法[J].微電子學與計算機，2008，25（1）：177?180.

[12]?徐煒珊，于磊，馮俊池，等.基于軟件層次化模型的軟件測試數據生成[J].計算機應用，2016，36（12）：3454?3460.

[13]?樊鑫，鄭巍，楊豐玉.基于UML模型集成測試工具的建模與設計[J].計算機測量與控制，2015，23（12）：4210?4213.

[14]?郭旺.嵌入式軟件覆蓋測試綜述[J].軟件導刊，2017，16（3）：179?181.

[15]?ABDURAZIK A， OFFUTT J. Using coupling?based weights for the class integration and test order problem[J]. Computer Journal， 2009，52（5）：557?570.

[16]?ZHOU Y， LEUNG H. Empirical analysis of object?oriented design metrics for predicting high and low severity faults[J]. IEEE Transactions on Software Engineering， 2006，32（10）：771?789.

[17]?GJB/Z 102A?2012，軍用軟件安全性設計指南[S].北京：總裝備部軍標出版發行部，2012.

[18]?姜淑娟，張艷梅，李海洋，等.一種基于耦合度量的類間集成測試序的確定方法[J].計算機學報，2011，34（6）：1062?1074.

[19]?ZHOU Y， XU B， LEUNG H， et al. An in?depth study of the potentially confounding effect of class size in fault prediction[J]. Acm Transactions on Software Engineering & Methodology， 2014，23（1）：1?51.

[20]?CONCAS G， MARCHESI M， PINNA S， et al. Power?laws in a large object?oriented software system[J]. IEEE Transactions on Software Engineering， 2007，33（10）：687?708.

[21]?張妙，姜淑娟，張艷梅.多目標優化類集成測試序列確定問題研究進展[J].小型微型計算機系統，2017，38（8）：1772?1777.