基于布爾運算符替換算法的機載系統(tǒng)測試用例生成

基于布爾運算符替換算法的機載系統(tǒng)測試用例生成

嵌入式軟件通常對可靠性的要求高于普通軟件，因此需要對嵌入式軟件進(jìn)行嚴(yán)格測試，以提高產(chǎn)品的可靠性。DO-178B是國際公認(rèn)的機載軟件開發(fā)指南。通過人工構(gòu)造測試用例時,需要分析每個條件對結(jié)果的影響,往往出現(xiàn)考慮不周,或設(shè)計冗余的問題,無法保證設(shè)計出來的測試用例既精簡又能對需求進(jìn)行充分的覆蓋。本文針對目前軟件測試過程中測試用例設(shè)計的特點,依據(jù)DO-178B的A級覆蓋的標(biāo)準(zhǔn)———MC/DC準(zhǔn)則,研究了一個布爾運算符替換算法,并實現(xiàn)了工具。在將需求用布爾表達(dá)式描述基礎(chǔ)上,利用該工具能自動生成滿足MC/DC準(zhǔn)則要求的測試用例。1測試用例有效性分析MC/DC是ModifiedCondition/DeeisionCoverage的縮寫,含義是修正條件/判定覆蓋。條件表示不含有布爾操作符號的布爾表達(dá)式;判定表由條件和零或者多個布爾操作符號組成的布爾表達(dá)式。MC/DC準(zhǔn)則主要用來測試飛行性軟件的安全性審查。它具有多重條件覆蓋的優(yōu)點,同時只是線性增加測試用例的數(shù)量,可以得到理想的目標(biāo)碼覆蓋率。該準(zhǔn)則要求:(1)判定中的每個點的入口和出口至少被測試一次;(2)判定中每一個條件的每種可能的結(jié)果至少發(fā)生一次;(3)每一個條件都能單獨地影響判定的結(jié)果,即在其他條件不變的情況下改變這個條件的值,使得判定結(jié)果改變。因此,在測試用例集中,必須針對每個條件出現(xiàn)一對測試用例來滿足MC/DC覆蓋要求。布爾表達(dá)式是由布爾算符(and、or、not)施于布爾變量或關(guān)系表達(dá)式而成。對于布爾表達(dá)式AandB和AorB,其完備測試用例對相同為邀(0,0),(0,1),(1,0),(1,1)妖。滿足MC/DC準(zhǔn)則要求的測試用例對集合卻不同,如表1、表2所示。2測試系統(tǒng)的程序Chilenski指出:對于一個具有N個條件的布爾表達(dá)式,測試集合中至少包括N+1組元素。布爾運算符替換算法實現(xiàn)對一個布爾表達(dá)式求出至少N+1組的這些元素,設(shè)計條件獨立的影響結(jié)果的最小測試用例集。該算法流程如圖1所示。首先根據(jù)編譯原理的布爾表達(dá)式文法構(gòu)造操作符優(yōu)先關(guān)系表。當(dāng)輸入布爾表達(dá)式后提取出布爾常量和操作符,根據(jù)優(yōu)先關(guān)系表計算各操作符的優(yōu)先級權(quán)值,按權(quán)值對各個操作符排序。按序生成每個操作符的真值表并將結(jié)果帶入表達(dá)式,最終優(yōu)先級最低的操作符生成初始真值表。初始真值表可能存在冗余的測試用例,故接下來利用樹的廣度優(yōu)先遍歷的思想對其做優(yōu)化找到滿足MC/DC準(zhǔn)則的對應(yīng)于每個布爾常量的測試用例對,最終求得MC/DC的最小測試用例集?，F(xiàn)分四個步驟說明這個算法。2.1編碼g的算法定義布爾表達(dá)式文法G如下:終結(jié)符是:or、and、not、(、)、const。其中const是布爾變量。該文法是算符優(yōu)先文法為了構(gòu)造終結(jié)符優(yōu)先關(guān)系表,首先需要對G的每個非終結(jié)符P構(gòu)造兩個集合FIRSTVT(P)和LASTVT(P)。構(gòu)造結(jié)果如下:FIRSTVT(NOT_EXP)=邀not,(,const妖LASTVT(NOT_EXP)=邀not,),const妖使用每個非終結(jié)符P的FIRSTVT(P)和LASTVT(P),根據(jù)構(gòu)造優(yōu)先表的算法,能夠構(gòu)造文法G的優(yōu)先表如表3。表中的空白格表示相應(yīng)終結(jié)符偶沒有優(yōu)先關(guān)系。2.2操作符優(yōu)先關(guān)系的處理輸入布爾表達(dá)式后,將操作符與布爾常量分離。每個操作符優(yōu)先級權(quán)值初始化為1。設(shè)b1與b2為左右相鄰兩個操作符,初始化后P(b1)=P(b2)=1,當(dāng)前計算b2的優(yōu)先級權(quán)值。根據(jù)優(yōu)先關(guān)系表,按以上函數(shù)規(guī)則計算各操作符優(yōu)先級權(quán)值。然后按權(quán)值從大到小的順序,利用快速排序算法對所有操作符排序。因括號匹配原則,左右括號的優(yōu)先級權(quán)值一致。排序后只將“and”、“or”和“not”的優(yōu)先級權(quán)值取出存入優(yōu)先級隊列。例如輸入的布爾表達(dá)式是(AandB)and(CorD)。操作符與布爾常量分離后,操作符按從左到右的順序放入數(shù)組b中,即b=″(″,b=″and″,b=″)″,b=″and″,b=″(″,b=″or″,b=″)″。根據(jù)優(yōu)先關(guān)系表及上述函數(shù)規(guī)則。計算出各操作符權(quán)值如下:P(b)=P(b)=2;P(b)=P(b)=P(b)=P(b)=1;P(b)=0;排序后按先進(jìn)先出入優(yōu)先級隊列的是:b、b、b。2.3基于c/dc的布爾運算符替換規(guī)則由表1、表2可看出,當(dāng)遇到操作符“and”,只需考慮測試用例對邀(1,1)、(1,0)、(0,1)妖;當(dāng)遇到操作符“or”,只需考慮測試用例對邀(0,0)、(1,0)、(0,1)妖就可滿足MC/DC覆蓋要求?；谏鲜鲈?定義布爾運算符替換規(guī)則表(表4)。將布爾操作符從優(yōu)先級隊列依次出隊,根據(jù)替換規(guī)則表,得到每個操作符的對應(yīng)真值表放入鏈表中臨時保存。真值表中一、二列為該操作符在布爾表達(dá)式中的左右兩個布爾常量,第三列為邏輯表達(dá)式計算結(jié)果Ri。當(dāng)同一優(yōu)先級的布爾操作符替換完畢后,將Ri代回表達(dá)式以便進(jìn)行下一優(yōu)先級的布爾操作符替換。最終由優(yōu)先級最低的操作符生成初始真值表。以布爾表達(dá)式(AandB)and(CorD)為例,當(dāng)優(yōu)先級隊列中第一個元素b出隊,根據(jù)布爾運算符替換規(guī)則表得到真值表如表5所示。b出隊得到真值表(表6)后,將R1和R2回代,表達(dá)式變?yōu)镽1andR2。繼續(xù)作出隊操作直到隊空,由優(yōu)先級最小的操作符生成初始真值表(表7)。2.4用樹優(yōu)化檢測初始真值表可能存在冗余的測試用例,利用樹的廣度優(yōu)先遍歷的思想對其做優(yōu)化,以找到滿足MC/DC準(zhǔn)則的對應(yīng)于每個布爾常量的測試用例對。把初始真值表的每一行作為樹的一個節(jié)點,第一行為根節(jié)點,建立一顆樹。為了方便查找每個布爾常量獨立影響表達(dá)式結(jié)果的測試用例對,建樹過程保證父子節(jié)點的真假值不同。利用樹的廣度優(yōu)先遍歷,按順序?qū)⒏缸庸?jié)點做按位異或操作,當(dāng)且僅當(dāng)按位異或結(jié)果含有一個“1”時,根據(jù)“1”的位置標(biāo)記該父子對的獨立影響布爾常量。當(dāng)所有布爾變量都被標(biāo)記,即每個布爾變量都找到了獨立影響對,樹的遍歷完成。取出標(biāo)記過的節(jié)點,生成優(yōu)化真值表。繼續(xù)上面的例子,把初始真值表的每一行作為樹的一個節(jié)點Ni,建立了如圖2所示的樹。對樹進(jìn)行廣度優(yōu)先遍歷,比較每一對父子節(jié)點后,找到了布爾變量A~D的獨立影響對如圖3所示。最后取出作過標(biāo)記的節(jié)點,生成優(yōu)化真值表。3設(shè)置測試用例MC/DC測試用例生成工具以布爾運算符替換算法為核心,輔助設(shè)計覆蓋全面而又簡化的測試用例。該工具輸入為一個布爾表達(dá)式,輸出為符合MC/DC準(zhǔn)則要求的最小測試用例集。以某衛(wèi)星導(dǎo)航系統(tǒng)的白盒測試為實驗案例,為了達(dá)到DO-178B軟件驗證的目標(biāo),對機載軟件的測試通常分為以下幾步:基于需求設(shè)計測試用例;結(jié)合源代碼運行測試用例,分析測試結(jié)果;在宿主機上進(jìn)行MC/DC結(jié)構(gòu)覆蓋測試,判斷軟件是否實現(xiàn)了需求描述的功能。首先利用MC/DC測試用例生成工具輔助生成測試用例。根據(jù)DO-178B中需求覆蓋要求,每一條需求要有對應(yīng)的測試用例。例如下面這條需求“WheninFLSmodeandlabel271indicatesSelectedModeStatus(bit26)isModeFailed(0)orlabel270hasnotbeenreceivedafter10secondshaveelapsedfrompowerup.label177shallsetbetransmittedwithSSM=FW.”從該需求中抽象出布爾表達(dá)式[FLSmode]and([bit26oflabel271=0]or([label270notbeenreceived]and[10shaveelapsedfrompowerup]))和預(yù)期結(jié)果:setlabel177betransmittedwithSSM=FW作為MC/DC測試用例生成工具輸入,運行后根據(jù)優(yōu)化真值表,可設(shè)計5個符合MC/DC準(zhǔn)則的測試用例如圖4所示。第二步結(jié)合源代碼編寫測試驅(qū)動,運行測試用例。比較期望結(jié)果和預(yù)期結(jié)果是否一致,若出現(xiàn)“Fail“,則說明需求與代碼不一致,在分析代碼后寫出問題報