基于程序變異的Simulink模型測試方法

周藝斌，殷永峰，李驍丹，王明威

(北京航空航天大學 可靠性與系統工程學院，北京100191)

隨著模型驅動軟件設計思想(MBD)的廣泛應用，軟件開發的重心已由傳統的代碼設計轉移到建模及模型的轉換上［1］.如果能在完成軟件初步設計的同時，及早發現并修復模型中的錯誤，不僅能縮短后期的代碼測試周期，還能提高模型的可靠性，改善軟件產品的質量.因此，越來越多的研究開始關注高層次的模型驗證與測試工作.

Simulink是Matlab提供的一個用于對動態系統進行建模、仿真和分析的工具.它為用戶建模提供了一個圖形化的用戶界面，通過不同類型模塊庫中的功能模型來完成系統的建模.目前，許多航空機載安全關鍵軟件已運用Simulink/RTW技術進行開發，但仍存在缺乏完善的模型測試充分性準則及自動高效的測試用例生成等問題［2］.不同于基于控制流和數據流的測試充分性準則，程序變異是一項用于評價測試優良程度的有效技術，它為測試評價和測試增強提供了準則.將程序變異技術應用于Simulink的模型測試，不僅可以為Simulink模型提供測試充分性準則，還可以用來指導設計較強發現故障能力的測試用例生成.但是由于Simulink模型的變異測試過程中存在的測試執行開銷大和測試用例生成效率低兩個問題，是將變異測試技術從學術界研究轉化為工業界應用所面臨的主要技術難題.

本文研究設計了針對Simulink模型測試的改進變異算子集，在不影響測試用例集變異評分的情況下，該組變異算子集能夠減少變異模型的生成數量，從而有效降低測試開銷.在此基礎上設計了一種基于搜索的Simulink模型變異測試用例生成方法.

1 相關工作

程序變異(program mutation)是一種面向缺陷的測試技術，最早由DeMillo等在文獻［3］中提出，主要應用于單元測試，在接口測試、面向方面測試及面向對象測試中也有相關的理論研究.它依賴于兩個基本原則:其一是稱職程序員假設，即假設熟練的程序員寫出的是一個接近于正確的程序P;另一個是耦合效應假設，即若測試用例可以檢測出簡單缺陷，則該測試用例也易于檢測到更為復雜的缺陷.

程序變異的基礎是變異算子集.變異算子是在符合語法規則前提下，從原有程序生成差別極小程序(變異體)的轉換規則［4］.文獻［5］于1987年針對Fortran77語言首次定義了22種變異算子，這組算子集為后來的其他編程語言變異算子的設計提供了重要的依據.該組變異算子主要分為4種類型，即常量變異、操作法變異、語句變異及變量變異，實際中每種分類下面都有很多個變異算子.每種分類下面的變異算子的類型和數量依賴于針對的編程語言.

程序變異技術雖然已有較多研究成果，但其應用卻存在分析過程中計算開銷過大的技術難題.大量變異模型的生成使得測試分析工作的開銷及其高昂，為此需要有效的優化方法來減小計算開銷.文獻［6］中首先提出了選擇性變異的方法，即忽略ASR和SVR兩個可以生成30% ～40%變異體的變異算子.這種策略被稱為“2-selective mutation”，文獻［7］將這種策略延伸為“N-selective mutation”.實驗結果表明，使用“N-selective mutation”策略后的變異評分均值仍可以保持較高，并明顯降低了變異體數量.在以上的實驗研究分析下，文獻［8］將文獻［5］中提出的22種變異算子進一步分為了操作數類算子、表達式類算子和語句類算子.通過對每一類變異算子的分析，最終確定了5個最為重要的變異算子:ABS算子、AOR算子、LCR算子、ROR算子、UOI算子，實驗結果表明，使用這5個變異算子僅將其變異評分降低了0.5%.文獻［9］中針對Proteum測試工具為C語言的變異算子設計了優化的方法，提出了選擇出充分變異算子集的6條指導策略.即:①考慮能獲得高變異評分的變異算子.②考慮每個變異算子類中的一個算子.③依據實驗將包含在高效算子中的算子除去.④建立增量策略.⑤考慮能夠在變異評分上提供增量的變異算子.⑥考慮具有高可信度的算子.

在上述研究分析的基礎上，本文擬在不影響變異評分的前提下，以上述6條策略為指導，通過對Simulink變異算子進行約簡優化來大規模減少變異體數量，從而減小變異測試的計算開銷.

2 基于程序變異的模型測試過程

許多航空機載安全關鍵軟件已運用Simulink/RTW技術進行開發，但仍存在以下問題:①仍缺乏完善的測試充分性度量證明模型的測試是充分的.不同的軟件測試人員使用不同的充分性準則標準，沒有統一的標準.②如何自動高效生成滿足Simulink模型測試所需的測試用例集，仍是一個亟待解決的問題.③雖然已有眾多工具應用于模型驅動的軟件開發過程領域，但是對Simulink模型的測試工具研究尚屬于起步階段.

考慮Simulink環境特點，設置被測單位為一個系統模型，在生成變異模型的過程中不對子系統的模塊進行變異.這時子系統類似于代碼中的調用函數，在以子系統為被測單位時再對其模塊進行變異.本文提出了基于程序變異的Simulink模型測試過程，如圖1所示.

過程具體說明如下:①用已有的測試集T執行原始Simulink模型P.②根據設定好的變異算子生成活躍變異模型L集合.③選取一個未考慮過的活躍變異模型M.④選取未執行過的測試用例t.⑤使用測試用例t執行變異模型M，檢查針對測試用例t執行M產生的結果與執行P產生的結果是否相同.若相同則返回步驟④，選取下一測試用例;若不相同則稱為t殺死了變異模型M，將M添加到被殺死的變異模型D集合中.⑥當測試集T中沒有測試用例能將變異模型M殺死時，將M放回到活躍變異模型L中.⑦檢查L集合是否為空.若不為空，測試其與原始模型P的等價性.從L中剔除出等價變異模型E.⑧計算測試用例集T的變異評分(mutation score).給定集合L，D和E，用SM(T)表示T的變異評分，則

正如上式所示，一個測試集的變異評分總是介于0～1之間.如果測試集T能夠殺死除等價變異模型外的所有變異模型，則|L|=0，變異評分SM(T)為1，該測試集T的發現錯誤能力較強.反之T不能殺死任何一個變異模型，則|D|=0，變異評分SM(T)為0，測試集T的發現錯誤能力較弱.測試用例t殺死變異模型為當且僅當測試用例t使得變異模型的最終輸出與原模型的最終輸出不同.

圖1 基于程序變異的Simulink模型測試方法流程Fig.1 Process of Simulink model testing method based on program mutation

3 Simulink模型的改進變異算子集

Simulink包含很多現成的模塊庫，主要有輸入源庫、離散及連續系統庫、數學運算庫及非線性系統庫.根據以上通用的模塊庫，考慮Simulink建模過程中的典型錯誤，文獻［10］中首次研究了Simulink模型的故障模型，包括類型故障、變量故障、常量故障、連續離散時間故障、語句故障和表達式故障，并基于上述故障模型，針對Simulink模型提出了一組變異算子集.不同于傳統程序變異的算子，該組算子集針對Simulink中常用的不同模塊進行變異，如Switch模塊的門限發生變異、積分及延時模塊的變異.文中將其提出的變異算子集應用于一個二次方程模型的測試過程，通過計算4組測試用例集的變異評分，從而選擇出最優用例集.文獻［10］針對一組典型Simulink模型設計了變異測試實驗，本文對實驗結果進行了統計.該實驗共生成59個變異模型，其中，TRO算子生成的變異模型數量最多，且該實驗的等價變異模型全部由TRO算子產生，根據 N-selective mutation策略，本文首先將TRO算子忽略，不僅有效減少生成27.11%的變異模型，還可以減少等價變異模型的生成，從而大幅降低測試開銷.隨后的實驗驗證了優化方案的必要性.

基于充分變異算子的指導準則，上述算子集可以分為如下5類:數據類型變異(TRO)、變量變異(VCO，VNO)、常量變異(CCO，CRO，DCO)、Switch模塊變異(SCO，SSO)和表達式變異(ROE，AOR，ASR，LOR).考慮文獻［9］中的6 條變異算子優化策略，依次對每一類里的變異算子進行分析.本文選擇出6種重要的變異算子:VCO，CRO，SCO，DCO，ROR，AOR.圖2 是一個包含基本模塊的Simulink模型，其主要功能是判斷二次方程解的類型，通過對該模型的變異測試實驗表明，以上6種變異算子組成的針對Simulink模型的改進變異算子集比原有的變異算子集，在變異模型生產數量和變異評分方面都有進步.

在圖2的二次方程模型解類型檢驗模型中，本文選擇了6組測試用例集(每組包含6個測試用例)，并執行于由上面6種算子生成的29個變異模型，得出了如表1所示的實驗結果.本文中變異模型均通過修改模塊參數以實現算子對模型的變異操作.

從表1中的結果可看出，改進后的變異算子集能夠顯著減少變異模型的數量，并且略微提高了測試用例集的變異評分.由于其中隨機生成的測試用例的廣泛性不夠，測試用例集T3的變異評分偏低.對于未被殺死的非等價變異模型，在第4節中將介紹基于搜索的用例生成方法，在改進變異算子集的基礎上，主要關注于如何生成能夠殺死上面提到的變異模型的測試用例.

圖2 二次方程式模型Fig.2 Quadratic model

表1 用例集的測試結果Table1 Testing results of test sets

4 基于搜索的測試用例生成

由圖1可看出，當用例集T的測試用例都不能殺死變異模型，則需要向T中添加用例，其中測試用例生成是最花費人力和時間的過程.文獻［11］中提出了一個自動化的測試用例生成框架，該框架采用搜索算法為結構化的模型生成了測試用例，實驗證明該組用例能夠達到較高的結構化覆蓋準則，但是該實驗僅選用了3個變異算子，對于變異測試的充分性不足.本文通過采用第3節中的改進算子集，更真實地模擬了Simulink仿真過程中可能出現的錯誤.文獻［12］研究了基于搜索的Simulink模型測試數據生成法，針對Simulink模型復雜性的特點，采用模擬退火算法對目標函數求優.但是，滿足結構化覆蓋標準的測試用例有時并不能夠發現Simulink模型中的一些錯誤，如邏輯模塊故障、Switch模塊故障等.由于結構化覆蓋標準下的測試用例僅能保證覆蓋特定路徑，如果上述模塊發生故障(如設計人員將Switch模塊的門限“＞0”錯寫為“＞=0”)的情況下，該用例仍然可覆蓋該特定路徑，則該故障不能被發現.因此如何高效地從Simulink模型產生符合高變異評分的測試用例是本節研究的重點.

基本思想是:反復執行被測程序，根據執行過程中搜集到的數據判斷當前輸入滿足特定測試需求的程度.借助反饋機制，逐漸調整輸入直到滿足測試需求為止.本文考慮對于指定路徑上不滿足要求的分支，將測試數據生成問題轉化為函數極小化問題，其重點在于如何選擇合適的目標函數和函數極小化方法.

4.1 構造代價函數

根據文獻［13］提出的代價函數，本文設計了代價函數定義基本規則和變異模型的代價函數構造規則，其中基本規則如表2所示.

表2 代價函數Table2 Cost functions

表2中，K表示當斷言不滿足時的代價函數值，可用于比較各斷言之間的差距.例如，對于斷言來說A＜5，A=6比A=10更接近于該斷言，A=6的代價函數值更小.為了構造Simulink不同模塊之間的代價函數，文獻［14］中提出為了使得原模型與變異模型的輸出產生差異，必須滿足兩個條件:

1)變異模塊的輸出必須發生改變;

2)該輸出的改變必須影響到整個模型的輸出.

一般模塊變異后，條件1能夠滿足.但是條件2則需要研究模型的結構，并保證從變異模塊到系統輸出之間的路徑上，每個模塊的輸出與原模型的不同.如果系統模型包含多個輸出，則至少1個輸出不同就認為被殺死.針對本文提出的優化變異算子集，不同位置的不同類型變異均有不同的代價函數，下面將逐一介紹代價函數的構造.

4.1.1 常量模塊與變量模塊

如果模塊的變異類型為常量變異與變量變異，則其代價函數應該為:C=CCV+CA.其中，CCV為常量模塊與變量模塊變異后需不同于原模塊的代價，CA為該模塊變異后其改變需影響到整個模型的輸出的代價.

4.1.2 Switch 模塊

圖3(a)代表受影響的信號輸入Switch模塊的第1或第3輸入，此時其代價函數應為:C=CD+CS+CA.其中，CD表示受影響的信號需不同于原模型中信號的代價，CS表示若受影響的信號輸入Switch模塊的第1輸入時，第2輸入信號達到門限的代價;若受影響的信號輸入Switch模塊的第3輸入時，第2輸入信號未達到門限的代價.

圖3(b)代表受影響的信號輸入Switch模塊的第2輸入，此時其代價函數應為:C=CD+(CS1S3+)∨(C′S1S3+)+CA.其中，CS1S3為原Switch模塊的第3輸入與變異Switch模塊的第1輸入不同的代價，C′S1S3為原Switch模塊的第1輸入與變異Switch模塊的第3輸入不同的代價.

圖3 受變異的信號輸入Switch模塊Fig.3 Mutated signal input Switch blocks

4.1.3 表達式模塊

如果模塊的變異算子為ROR，AOR或LOR時，則其代價函數應為:C=CP≠M+CA.其中，CP≠M為輸入經過變異表達式操作的輸出值不同于原模塊的代價.

圖4(a)代表受影響的信號輸入表達式模塊的任意輸入端口，其代價函數為:C=CD+CP≠M+CA.圖4(b)代表受影響的信號輸入兩個表達式模塊的任意輸入端口，其代價函數為:C=CD+(CO1∨CO2)，其中，CO1=CP1≠M1+CA1，CO2=CP2≠M2+CA2.

圖4 受變異的信號輸入表達式模塊Fig.4 Mutated signal input expression blocks

結合表2中的代價函數構造規則，可以遞歸地從變異模塊到最終輸出來計算，從一組隨機測試用例中搜索出能夠殺死該變異模型的測試用例的代價函數.假設圖3中模型受變異算子ROR影響生成變異模型，其中Compare To Zero模塊的“＞=”被替換為“＜=”.如果該變異模型在圖1中步驟⑤中沒有被殺死，則其代價函數應為

4.2 搜索殺死特定變異模型的測試用例

在4.1節中將測試用例生成問題轉化為了代價函數值極小化問題的基礎上，采用模擬退火算法來解決代價函數極小化問題［15］.首先，模擬退火算法能夠跳出初始輸入的局部最優解，搜索到目標輸入的穩定性較高，對Simulink模型中各種復雜情況具有更高適應性［12］.另外，由于從R2009a版本開始，Matlab自帶的優化工具箱集成了模擬退火算法，因此用Matlab環境來驗證本文的測試數據生成算法方便易行.在第5節中將通過典型實例來簡要介紹該算法的應用和變現.

5 實例驗證

本節通過設計4組圖2中模型的變異模型來驗證第4節的測試數據生成方法.表3為圖2中模型的4個變異模型，具體描述如表3所示.

表3 實驗變異模型描述Table3 Description of mutated models in experiment

這里設置代價函數的K=1，由定義可知，目標函數的最優值為0.即可使目標函數為0的測試輸入能夠殺死對應的變異模型.對于系統的代價函數及以上4組變異模型的目標函數，可用Matlab腳本編寫.用Matlab編寫的測試數據生成腳本如下:

ObjectiveFunction=@obj_function;%目標函數句柄設定

startingPoint=［010］;%初始值設定

lb=［－10－10－10］;%輸入值下限

ub=［101010］;%輸入值上限

options=saoptimset(‘InitialTemperature’，1000，‘TemperatureFcn’，@temperatureexp，‘ReannealInterval’，500，‘PlotFcns’，{@saplotbestx，@saplotbestf，@saplotx，@saplotf});% 模擬退火算法參數設定

［x，fval，exitFlag，output］ =simulannealbnd(ObjectiveFunction，startingPoint，lb，ub，options);%執行模擬退火算法

這里設置模擬退火算法的終止條件為目標函數達到0，起始溫度為1000，冷卻率為0.95.通過分別編寫目標函數，執行算法生成測試數據，運行上述腳本，4組模型的執行結果如圖5所示.最優目標函數表示在橫軸的迭代次數下得到縱軸的目標函數值(最優目標函數為0)，最優變量值表示當目標函數達最優時的測試數據.

圖5 搜索迭代次數與最優變量輸入值Fig.5 Searching iteration number and optimal input value of variables

由圖5可看出，通過采用模擬退火算法經過一定迭代次數均可使目標函數達到最優值，即可以找到需要的測試數據.除第1組的迭代次數為761次外，另3組的平均迭代次數不超過30次，就可以找到滿足代價函數為0的測試輸入.因此，當變異模型不能被現有測試用例殺死而需要額外添加測試用例時，使用本文方法能夠有效實現.

6 結論

本文基于程序變異技術提出了Simulink模型的變異測試過程和一組改進變異算子集，并相應設計了一種基于搜索的Simulink模型變異測試用例生成方法，經實驗驗證表明:

1)該組改進變異算子集能夠減少變異模型的數量，并且保證測試用例集的變異評分基本不變;

2)對于Simulink基本模塊庫中的不同變異模塊，基于搜索的Simulink模型變異測試用例生成方法能夠快速準確地生成滿足測試要求的測試用例.

今后研究將從以下幾個方面展開:本文采用手工方式構造實驗變異模型的代價函數，未實現代價函數構造自動化.僅考慮了Simulink中的基本模塊庫，對于其他特定領域的模塊庫，其變異算子的設計有待繼續研究.等價變異模型判定、子系統模塊處理等問題的優化，也是未來值得研究的方向.

References)

［1］ Molina J M，Pan X，Grimm C，et al.A framework for modelbased design of embedded systems for energy management［C］//Modeling and Simulation of Cyber-Physical Energy Systems(MSCPES).Piscataway，NJ:IEEE，2013:1-6.

［2］ He N，Rümmer P，Kroening D.Test-case generation for embedded Simulink via formal concept analysis［C］//Proceedings of the 48th Design Automation Conference.New York:ACM，2011:224-229.

［3］ DeMillo R A，Lipton R J，Sayward F G.Hints on test data selection:help for the practicing programmer［J］.Computer，1978，11(4):34-41.

［4］ Jia Y，Harman M.An analysis and survey of the development of mutation testing［J］.IEEE Transactions on Software Engineering，2011，37(5):649-678.

［5］ King K N，Offutt A J.A fortran language system for mutationbased software testing［J］.Software:Practice and Experience，1991，21(7):685-718.

［6］ Mathur A P.Performance，effectiveness，and reliability issues in software testing［C］//15th Annual International Computer Software and Applications Conference.New York:IEEE，1991:604-605.

［7］ Offutt A J，Rothermel G，Zapf C.An experimental evaluation of selective mutation［C］//Proceedings of the 15th International Conference on Software Engineering.Piscataway，NJ:IEEE Computer Society Press，1993:100-107.

［8］ Offutt A J，Lee A，Rothermel G，et al.An experimental determination of sufficient mutant operators［J］.ACM Transactions on Software Engineering and Methodology(TOSEM)，1996，5(2):99-118.

［9］ Barbosa E F，Maldonado J C，Vincenzi A M R.Toward the determination of sufficient mutant operators for C［J］.Software Testing，Verification and Reliability，2001，11(2):113-136.

［10］ Binh N T.Mutation operators for Simulink models［C］//Knowledge and Systems Engineering(KSE)，2012 Fourth International Conference on.Piscataway，NJ:IEEE，2012:54-59.

［11］ Zhan Y，Clark J.Search based automatic test-data generation at an architectural level［C］//Genetic and Evolutionary Computation-GECCO 2004.Berlin:Springer，2004:1413-1424.

［12］ 鄧紹鵬，楊志義，王宇英.基于搜索的Simulink測試數據生成［J］.計算機應用研究，2012，29(7):2527-2530.Deng S P，Yang Z Y，Wang Y Y.Search-based test-data generation for Simulink［J］.Application Research of Computers，2012，29(7):2527-2530(in Chinese).

［13］ Bottaci L.Predicate expression cost functions to guide evolutionary search for test data［C］//Genetic and Evolutionary Computation—GECCO 2003.Berlin:Springer，2003:2455-2464.

［14］ Zhan Y，Clark J A.Search-based mutation testing for Simulink models［C］//Proceedings of the 2005 Conference on Genetic and Evolutionary Computation.New York:ACM，2005:1061-1068.

［15］ McMinn P.Search-based software test data generation:a survey［J］.Software Testing，Verification and Reliability，2004，14(2):105-156.