IR46智能電表軟件白盒測試的基路徑集生成方法研究

樊 博 梁 飛 黃吉濤 周媛奉 胡婷婷 郭林明 王文龍

1(國網寧夏電力有限公司電力科學研究院 寧夏 銀川 750002)

2(四川大學電氣工程學院 四川 成都 610065)

3(河南許繼儀表有限公司 河南 許昌 461000)

0 引 言

智能電表是泛在電力物聯網感知層中的關鍵器件。據國家電網的統計，目前60%智能電表的現場故障是由軟件缺陷所引起的。作為新一代的智能電表，IR46智能電表[1]還需進行芯片參數整定、整機驗證等測試。而智能電表作為典型的嵌入式產品，許多通用的測試軟件并不能完全契合其要求[2]，為此本文提出白盒測試中一種新的基路徑集生成方法。

白盒測試基于軟件內部結構設計測試案例，能夠充分測試程序內在邏輯，發現代碼層面的錯誤。而基路徑測試是語句覆蓋率很高的白盒測試方法，發現錯誤的能力很強。基路徑測試的不足是測試效率較低，為解決這個問題就需要改進基路徑集生成方法[3]。現階段，基路徑集生成方法主要分為兩種：基于圖的方法和自動生成方法。基于圖的方法是指在控制流圖的基礎上使用某種搜索算法來求取基路徑集，該方法在處理復雜程序時效率較低，如基于圖廣度優先搜索[4]、圖深度優先搜索[5]傳統方法和基于元啟發式算法的克隆選擇算法[6]、遺傳算法等[7]。自動生成方法使用某種方法識別程序結構，自動生成基路徑集，如基于模型代數[8]、基于代碼識別[9]等方法。該方法省去了程序到控制流圖的轉換工作，但要求程序符合規定的編程規范，限制了其在非結構代碼上的應用。

以上方法沒有從語句層面分析路徑的重要性，不能指導測試順序。IR46智能電表控制軟件在某些情況需要進行快速測試，詳盡的軟件測試是不合理的，而通過識別錯誤傾向性較高的基路徑，可以提高測試效率從而達到快速測試的目的。

因此本文從兩個方面來提升測試效率。首先量化語句的錯誤傾向以確定路徑重要性：引入語句的錯誤源(sources of errors，SOE)分析，通過賦予語句錯誤傾向權重(error propensity weight，EPW)來構建程序的加權有向圖，依據路徑的EPW決定測試優先級。然后改進基路徑搜索算法：改進具有模型簡單、效率高和魯棒性強等優點[10]的二進制蝙蝠算法(Binary Bat Algorithm，BBA)得到OBBA(Optimized Binary Bat Algorithm)并將其用于路徑搜索。仿真結果表明，該方法可以有效生成帶EPW優先級的基路徑集，所引入的SOE分析可以指示程序的錯誤傾向，OBBA也縮短了基路徑生成的迭代周期，有助于提升白盒測試的效率。

1 基路徑測試及SOE量化

1.1 基路徑測試

基路徑測試的思想是從可執行軟件路徑里找到一組能夠完成軟件測試任務且規模盡量小的基路徑，以簡化測試。目前被廣泛應用的基路徑集生成框架是McCabe度量法[11]。McCabe將程序路徑視為向量空間里的向量，根據任何向量可以由基來線性表示的原理，就可以用基路徑的測試來替代所有路徑的測試。基路徑測試的步驟如下：

1) 將待測程序轉化為控制流圖。

2) 根據控制流圖的圈復雜度得到基路徑的數目，定義為：

C(G)=m-n+2q

(1)

式中：m和n分別為控制流圖的邊和節點的數目；q為強連通分量個數，對于只有一個入口和一個出口的程序，q通常取1。而基路徑數目N等于C(G)。

3) 使用某種搜索算法得到一組基路徑，并驗證是否滿足基路徑集三個條件：

(1) 基路徑間至少有一條邊是不同的。

(2) 基路徑集能夠覆蓋所有的邊。

(3)其余路徑可以由基路徑線性表示。

4) 設計測試案例，使每條基路徑至少執行一次。

1.2 SOE量化

McCabe度量法沒有衡量路徑的錯誤傾向，不能區分基路徑的重要性，為此本文對路徑進行加權，以得到錯誤針對性更強的基路徑集。IR46智能電表程序中的不同程序結構所包含的SOE各異，需要進行SOE量化。圖1以循環結構為例說明SOE分析過程。可以看到該程序至少有4個SOE，將錯誤發生概率視為一致，且不考慮錯誤發生的后果，則EPW的值為wEPW=4。在實際應用中，可以將IR46智能電表的一些信息如語句重要性、風險分析、運行環境等以權值的形式添加到理論EPW中，以適應不同的應用環境。參照文獻[12]對其他的程序結構做類似的SOE分析，再根據SOE數目及引入SOE的變量等，得到了基本程序結構的EPW，如表1所示。

圖1 循環結構SOE分析示例

表1 基本程序結構SOE量化

續表1

2 改進二進制蝙蝠算法

2.1 二進制蝙蝠算法

蝙蝠算法模擬蝙蝠發射聲波覓食的行為來進行全局最優解求取，其尋優效率高且原理簡單，被廣泛用于優化問題。基路徑集生成可視為一個離散的組合優化問題，搜索空間是一個二進制離散空間，組合的變化通過0和1之間的翻轉來實現。為此需要使用離散的二進制蝙蝠算法[13]，即BBA。BBA的思想是將蝙蝠的速度映射為蝙蝠位置改變的概率，能對每一個二進制位進行優化。

蝙蝠位置(x)是BBA的解，通過不斷調節速度(v)、頻率(f)兩個屬性來控制飛行，迭代地搜索最優解。而響度(A)和聲波發射率(r)用于平衡局部搜索和全局搜索。其具體算法流程如下：

(1) 初始化。設置最大迭代數tmax、蝙蝠數目npop和頻率上下界等參數，然后使用二進制編碼對蝙蝠進行隨機初始化，設置t=0。

(2) 按照式(2)、式(3)更新蝙蝠的頻率和速度。

fi=fmin+(fmax-fmin)β

(2)

(3)

(3) 飛行產生新位置。使用式(4)的V型轉換函數[13]將蝙蝠的速度映射為位置的二進制位改變的概率，并使用式(5)更新位置。

(4)

(5)

(4) 若隨機數rand1

(6)

(5) 若隨機數rand2

Ai(t+1)=αAi(t)

(7)

ri(t+1)=ri(0)[1-exp(-γt)]

(8)

式中：α是響度衰減系數；γ是發射率增長系數；ri(0)為初始發射率。

(6) 根據蝙蝠群體的適應度，更新全局最優位置。

(7) 令t=t+1，并迭代執行步驟(2)-步驟(6)直至求得基路徑或達到最大迭代數。

2.2 參數自適應的二進制蝙蝠算法

BBA在避免局部優化上和收斂速度上較一些優化算法如粒子群優化(Particle Swarm Optimization,PSO)和遺傳算法有一定的優勢[13]。然而其在某些應用場景下還是會出現過早收斂的情況[14]，為此本文提出OBBA，OBBA從提高種群的多樣性、平衡局部搜索和全局搜索兩個方面來優化。

BBA屬于仿生優化算法，需要考慮到周圍環境的影響，比如慣性。為此本文引入慣性權重(w)來緩解BBA在迭代后期種群多樣性不足的問題。參考PSO中速度和權重的關系[15]，得到的慣性權重迭代函數和優化后的速度更新函數如式(9)、式(10)所示。

(9)

c2(xbest-xi(t))ξ

(10)

在平衡搜索策略方面，將式(7)的參數α進行了修改。參數α與模擬退火算法中的冷卻因子相類似[16]，值較小時傾向于局部搜索而較大時傾向于全局搜索，為了平衡兩者，提出α的動態更新公式：

(11)

OBBA混合使用兩種速度更新方式，設置一個概率閾值Pc，若隨機數rand3

3 仿真分析

3.1 可行性驗證

本文算法可分為三部分：待測程序預處理，SOE量化和利用OBBA搜索基路徑集。本文算法流程如圖2所示，其中：N為基路徑數目；gmax是搜索一條基路徑的最大OBBA執行次數；tmax為OBBA的最大迭代數；npop為蝙蝠數目；Fi為蝙蝠i的適應度；pend為控制流圖的出口節點。下文將詳述這三部分，并使用圖3所示案例來進行可行性驗證。

圖2 本文算法流程

圖3 案例程序控制流圖

(1) 在程序預處理階段，首先通過分支關鍵字識別的方式分析代碼的分支信息，得到語句節點間的連接關系、語句的類型、節點數目、邊的數目等信息；然后根據McCabe度量法計算圈復雜度，得到基路徑數目N。而在程序較大的時候，可以將控制流圖中一些非關鍵的且滿足din+dout<3(din為節點入度，dout為節點出度)的節點合并以得到簡潔高效的DD-graph(DDG)[5]。本文使用由首尾節點組成的連接矩陣來表示節點間的連接關系，表2的1、2列為案例程序的連接矩陣，而根據式(1)可算得案例程序的N為5。

表2 案例程序的輸入矩陣

(2) 在SOE量化階段，根據程序的預處理結果，由表1確定每條邊的SOE并計算得到對應的wEPW，wEPW滿足疊加性，若節點進行了合并需將其累加。案例程序包含了函數調用、if語句和邏輯操作等SOE，依照表1量化后可以得到如表2的第3列所示的wEPW向量。

(3) 在OBBA搜索基路徑集階段，首先需要給蝙蝠編碼及確定適應度函數。本文提出如圖4所示的編碼格式，其中 ：pi為控制流圖的節點；bi為對應的二進制位；F為路徑所到達節點的標志位。若F等于出口節點pend，則表示該路徑是連通的，為此使用F的值作為蝙蝠的適應度。然后將如表2所示的輸入矩陣傳入，執行OBBA搜索，求得帶EPW優先級的基路徑集。其中，連接矩陣用于校驗路徑的連通性，而wEPW向量用于計算路徑的錯誤傾向。每一次運行OBBA，若滿足Fi=pend的路徑不滿足基路徑的條件，則舍棄該路徑，繼續迭代直至獲得基路徑或達到最大迭代次數。

圖4 蝙蝠編碼格式

在案例程序中，使用OBBA、BBA和二進制粒子群算法(Binary Particle Swarm Optimization,BPSO)進行了基路徑集搜索，迭代情況如圖5所示。可以看到，在本文方法框架下，三種算法都能收斂于“出口節點34”，即能夠生成完整有效的路徑，且OBBA的收斂速度優于BBA和BPSO。基路徑集生成結果如圖6所示，其滿足了基路徑集三個條件，能驗證本文方法可以比較高效地生成帶優先級的基路徑集。

圖5 案例程序在三種算法下的迭代次數對比

圖6 案例程序基路徑集生成結果

3.2 對比分析

為了進一步驗證本文方法的可行性和良好效果，選用了7個IR46智能電表軟件會涉及到的字符串處理程序來進行對比測試，測試程序分析如表3所示。將OBBA、BBA和BPSO的gmax、tmax和npop分別設為20、1 000和100，其余參數如表4所示，其中BPSO參數參考了文獻[17]。然后分別進行20次重復實驗，取均值作為最終結果。實驗結果如圖7所示，可以看到OBBA的迭代次數要少于BBA和BPSO，在測試程序7的更復雜的搜索空間中，優勢更加明顯，可以說明OBBA能更好地避免陷入局部最優，也有更好的收斂速度。

表3 待測程序分析

表4 待優化算法參數

圖7 算法對比實驗結果

4 結 語

本文對IR46智能電表軟件白盒測試的基路徑集生成方法進行了研究，提出一種有效的新方法。通過引入路徑錯誤傾向權重(EPW)，提升了基本路徑測試發現程序錯誤的能力，并能通過基路徑優先級排序，指導測試順序；優化了BBA的速度更新策略和響度更新表達式得到OBBA，減少了算法所需迭代次數，提高了路徑生成效率；通過實際案例的可行性驗證和OBBA與BBA、BPSO間的對比實驗，證明了本文方法在提升基路徑集生成效率上的有效性。下一步工作是將其應用于更復雜的程序中，并拓寬應用場景。