周藝斌，殷永峰，李驍?shù)ぃ趺魍?/p>

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

過程具體說明如下:①用已有的測試集T執(zhí)行原始Simulink模型P.②根據(jù)設(shè)定好的變異算子生成活躍變異模型L集合.③選取一個未考慮過的活躍變異模型M.④選取未執(zhí)行過的測試用例t.⑤使用測試用例t執(zhí)行變異模型M，檢查針對測試用例t執(zhí)行M產(chǎn)生的結(jié)果與執(zhí)行P產(chǎn)生的結(jié)果是否相同.若相同則返回步驟④，選取下一測試用例;若不相同則稱為t殺死了變異模型M，將M添加到被殺死的變異模型D集合中.⑥當(dāng)測試集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的發(fā)現(xiàn)錯誤能力較強.反之T不能殺死任何一個變異模型，則|D|=0，變異評分SM(T)為0，測試集T的發(fā)現(xiàn)錯誤能力較弱.測試用例t殺死變異模型為當(dāng)且僅當(dāng)測試用例t使得變異模型的最終輸出與原模型的最終輸出不同.

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

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

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

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

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

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

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

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

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

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

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

4.1 構(gòu)造代價函數(shù)

根據(jù)文獻［13］提出的代價函數(shù)，本文設(shè)計了代價函數(shù)定義基本規(guī)則和變異模型的代價函數(shù)構(gòu)造規(guī)則，其中基本規(guī)則如表2所示.

表2 代價函數(shù)Table2 Cost functions

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

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

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

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

4.1.1 常量模塊與變量模塊

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

4.1.2 Switch 模塊

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

圖3(b)代表受影響的信號輸入Switch模塊的第2輸入，此時其代價函數(shù)應(yīng)為: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時，則其代價函數(shù)應(yīng)為:C=CP≠M+CA.其中，CP≠M為輸入經(jīng)過變異表達式操作的輸出值不同于原模塊的代價.

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

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

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

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

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

5 實例驗證

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

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

這里設(shè)置代價函數(shù)的K=1，由定義可知，目標(biāo)函數(shù)的最優(yōu)值為0.即可使目標(biāo)函數(shù)為0的測試輸入能夠殺死對應(yīng)的變異模型.對于系統(tǒng)的代價函數(shù)及以上4組變異模型的目標(biāo)函數(shù)，可用Matlab腳本編寫.用Matlab編寫的測試數(shù)據(jù)生成腳本如下:

ObjectiveFunction=@obj_function;%目標(biāo)函數(shù)句柄設(shè)定

startingPoint=［010］;%初始值設(shè)定

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

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

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

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

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

圖5 搜索迭代次數(shù)與最優(yōu)變量輸入值Fig.5 Searching iteration number and optimal input value of variables

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

6 結(jié)論

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

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

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

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

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測試數(shù)據(jù)生成［J］.計算機應(yīng)用研究，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.