李騰飛 石磊

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

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

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?引言

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

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

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

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

1?方法建模

1.1?基于節(jié)點層網絡的層間集成模型

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

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

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

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

定理1?同一節(jié)點層的節(jié)點在靜態(tài)調用圖中有相同的層間關鍵性等級。

證明：?對于多層網絡構建節(jié)點層模型，節(jié)點集合N={N?1，N?2，N?3，…，N?M} ，葉子節(jié)點集合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）。

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

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

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

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

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

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

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

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

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

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

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

1.3?評價指標

1.3.1?運算效率指標

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

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

其中β 為任意常數。

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

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

1.3.2?充分性指標

關鍵性等級高的節(jié)點出錯概率更高，應被優(yōu)先集成測試，對于該類節(jié)點的驗證也應更加充分。在增量集成測試中，通過動態(tài)執(zhí)行測試用例實現(xiàn)接口驗證，若測試用例先被執(zhí)行，則被動態(tài)執(zhí)行的次數也就更多?；诖藰嫿ㄔ撍惴ǖ某浞中灾笜四Ｐ?，將充分性量化成節(jié)點參與集成驗證的次數?N?i，其中i∈（1，2，3，…，m），m?為節(jié)點總數，即：

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

2?算法實現(xiàn)

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

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

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

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

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

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

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

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

3?測試實例

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

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

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

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

4?測試結果分析

4.1?運算效率

節(jié)點層網路采用分層算法，將總節(jié)點依據節(jié)點相似性原則進行分類、生成相應節(jié)點層，而非節(jié)點層網絡不存在節(jié)點層劃分，將所有節(jié)點等層看待?；谏鲜鲞壿?，本文分別計算相同網絡條件下的節(jié)點層和非節(jié)點層算法得到的集成測試增量模型效率，如表2所示。

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

4.2?測試充分性

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

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

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

5?結語

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

參考文獻：

[1]?GJB/Z 141-2004，軍用軟件測試指南[S].北京：總裝備部軍標出版發(fā)行部，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]?王瑩，于海，朱志良.基于軟件節(jié)點重要性的集成測試序列生成方法[J].計算機研究與發(fā)展，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].北京：總裝備部軍標出版發(fā)行部，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]?張妙，姜淑娟，張艷梅.多目標優(yōu)化類集成測試序列確定問題研究進展[J].小型微型計算機系統(tǒng)，2017，38（8）：1772?1777.