基于節(jié)點層網(wǎng)絡(luò)關(guān)鍵等級的嵌入式軟件集成測試序列生成方法

李騰飛 石磊

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

關(guān)鍵詞：嵌入式軟件;軟件集成測試;增量法;關(guān)鍵系數(shù);節(jié)點層網(wǎng)絡(luò)

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

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

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

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

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

1?方法建模

1.1?基于節(jié)點層網(wǎng)絡(luò)的層間集成模型

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

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

定義2?節(jié)點層：函數(shù)靜態(tài)調(diào)用關(guān)系網(wǎng)絡(luò)模型中的所有葉子節(jié)點同屬于一個節(jié)點層。

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

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

證明：?對于多層網(wǎng)絡(luò)構(gòu)建節(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可以構(gòu)建兩層網(wǎng)絡(luò)N-{Y?i}→{Y?i}，使N-{Y?i}和Y?i具有不同的關(guān)鍵性等級，即K?N-{Y?i}≠K?{Y?i} 且滿足K?N-{Y?i}>K?{Y?i}，K?N=K?N-{Y?i}+K?Y?i。當(dāng)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)調(diào)用圖和節(jié)點層網(wǎng)絡(luò)在分層上存在較大差別。靜態(tài)調(diào)用圖的同層節(jié)點基于自上而下的調(diào)用關(guān)系得到，而節(jié)點層網(wǎng)絡(luò)模型是通過自下而上的方式得到的，因同一節(jié)點層的節(jié)點在靜態(tài)調(diào)用圖中有相同的層間關(guān)鍵性等級，從而使函數(shù)層間模型劃分更加合理。

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

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

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

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

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

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

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

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

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

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

1.3?評價指標(biāo)

1.3.1?運算效率指標(biāo)

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

從而得到第M層計算效率的調(diào)和平均結(jié)果：

其中β 為任意常數(shù)。

有N個節(jié)點層網(wǎng)絡(luò)的節(jié)點關(guān)鍵性計算復(fù)雜度為：

其中m?i 表示第i層網(wǎng)絡(luò)節(jié)點個數(shù)。

1.3.2?充分性指標(biāo)

關(guān)鍵性等級高的節(jié)點出錯概率更高，應(yīng)被優(yōu)先集成測試，對于該類節(jié)點的驗證也應(yīng)更加充分。在增量集成測試中，通過動態(tài)執(zhí)行測試用例實現(xiàn)接口驗證，若測試用例先被執(zhí)行，則被動態(tài)執(zhí)行的次數(shù)也就更多?；诖藰?gòu)建該算法的充分性指標(biāo)模型，將充分性量化成節(jié)點參與集成驗證的次數(shù)?N?i，其中i∈（1，2，3，…，m），m?為節(jié)點總數(shù)，即：

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

2?算法實現(xiàn)

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

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

步驟2：依據(jù)靜態(tài)調(diào)用圖構(gòu)建節(jié)點層網(wǎng)絡(luò)的層間集成模型，共生成M個節(jié)點層，節(jié)點的層間關(guān)鍵性系數(shù)用L?i（i=1，2，3，…，m）表示。

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

步驟4：計算節(jié)點層網(wǎng)絡(luò)的關(guān)鍵系數(shù)。在M層N個節(jié)點的節(jié)點層網(wǎng)絡(luò)中，C?ij（i<M，j<N）表示第i層，第j個節(jié)點的關(guān)鍵系數(shù)。故：

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

將層內(nèi)節(jié)點的關(guān)鍵性系數(shù)計算公式代入式（11）：

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

3?測試實例

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

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

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

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

4?測試結(jié)果分析

4.1?運算效率

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

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

4.2?測試充分性

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

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

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

5?結(jié)語

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

參考文獻：

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

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

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

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

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

[6]?趙玉麗，王瑩，于海，等.基于復(fù)雜網(wǎng)絡(luò)的類間集成測試序列生成方法[J].東北大學(xué)學(xué)報：自然科學(xué)版，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].微電子學(xué)與計算機，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]?趙磊，倫立軍，徐士華.基于軟件體系結(jié)構(gòu)的測試路徑生成方法[J].微電子學(xué)與計算機，2008，25（1）：177?180.

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

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

[14]?郭旺.嵌入式軟件覆蓋測試綜述[J].軟件導(dǎo)刊，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，軍用軟件安全性設(shè)計指南[S].北京：總裝備部軍標(biāo)出版發(fā)行部，2012.

[18]?姜淑娟，張艷梅，李海洋，等.一種基于耦合度量的類間集成測試序的確定方法[J].計算機學(xué)報，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]?張妙，姜淑娟，張艷梅.多目標(biāo)優(yōu)化類集成測試序列確定問題研究進展[J].小型微型計算機系統(tǒng)，2017，38（8）：1772?1777.