基于布爾運(yùn)算符替換算法的機(jī)載系統(tǒng)測(cè)試用例生成

基于布爾運(yùn)算符替換算法的機(jī)載系統(tǒng)測(cè)試用例生成

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