路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成理論及方法.pdf

1、軟件測(cè)試是保障軟件質(zhì)量的重要手段,其目的是在測(cè)試過(guò)程中盡可能多地發(fā)現(xiàn)軟件存在的缺陷,因而其在整個(gè)軟件開(kāi)發(fā)過(guò)程中占有特別重要的位置。測(cè)試數(shù)據(jù)的好壞直接決定著測(cè)試的效果,因此軟件測(cè)試中關(guān)鍵的問(wèn)題是設(shè)計(jì)有效的測(cè)試數(shù)據(jù)。已有研究表明,路徑覆蓋是一種非常重要的軟件測(cè)試充分性準(zhǔn)則;遺傳算法是自動(dòng)生成路徑覆蓋測(cè)試數(shù)據(jù)的有效方法,但是已有研究成果在測(cè)試數(shù)據(jù)的生成效率和檢錯(cuò)率上都有待提高。本文研究使用遺傳算法自動(dòng)生成路徑覆蓋測(cè)試數(shù)據(jù)的理論及方法。

2、　　首先,針對(duì)現(xiàn)有方法對(duì)穿越難以覆蓋節(jié)點(diǎn)的稀有數(shù)據(jù)缺乏保護(hù)措施問(wèn)題,提出了在測(cè)試數(shù)據(jù)進(jìn)化生成中動(dòng)態(tài)捕捉稀有數(shù)據(jù)的方法。通過(guò)統(tǒng)計(jì)每代種群中目標(biāo)路徑各節(jié)點(diǎn)被穿越的個(gè)體數(shù)量,得到個(gè)體對(duì)生成穿越目標(biāo)路徑測(cè)試數(shù)據(jù)的貢獻(xiàn),以此作為權(quán)重調(diào)整個(gè)體的適應(yīng)度,使稀有數(shù)據(jù)的適應(yīng)度增加,在后續(xù)進(jìn)化中得到保留,從而提高測(cè)試數(shù)據(jù)的生成效率。
　　其次,提出了一種新的多路徑覆蓋測(cè)試數(shù)據(jù)生成方法。將被測(cè)程序表示成一棵二叉樹(shù),對(duì)目標(biāo)路徑采用赫夫曼編碼方法表示成二進(jìn)

3、制串,依此設(shè)計(jì)了一種新的適應(yīng)度函數(shù),綜合考慮個(gè)體穿越路徑與每個(gè)目標(biāo)路徑的匹配程度,將提出的方法用于多個(gè)基準(zhǔn)程序的測(cè)試,并與已有方法比較,結(jié)果表明所提方法計(jì)算量小,生成測(cè)試數(shù)據(jù)效率高。
　　第三,針對(duì)已有方法生成的測(cè)試數(shù)據(jù)不能有效發(fā)現(xiàn)被測(cè)程序的缺陷,尤其是小概率缺陷的問(wèn)題,提出了一種面向缺陷的路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成方法。分別針對(duì)單路徑和多路徑情況,將路徑覆蓋和缺陷檢測(cè)問(wèn)題轉(zhuǎn)化為約束多目標(biāo)優(yōu)化問(wèn)題,以測(cè)試數(shù)據(jù)運(yùn)行被測(cè)程序時(shí)發(fā)現(xiàn)的缺陷

4、個(gè)數(shù)和缺陷的危險(xiǎn)程度為目標(biāo),以穿越目標(biāo)路徑為約束,建立了該問(wèn)題的數(shù)學(xué)模型,并提出了有針對(duì)性的求解方法。在實(shí)際軟件測(cè)試中的應(yīng)用表明,所提方法生成的測(cè)試數(shù)據(jù)不但穿越了目標(biāo)路徑,而且能有效檢測(cè)到目標(biāo)路徑中的缺陷。
　　最后,提出基于搜索空間縮減的路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成理論。針對(duì)單路徑覆蓋測(cè)試數(shù)據(jù)生成問(wèn)題,先確定目標(biāo)路徑與輸入變量之間的關(guān)系,將可分目標(biāo)路徑分離出與部分分量相關(guān)的獨(dú)立子路徑;進(jìn)化生成測(cè)試數(shù)據(jù)的過(guò)程中,固定被穿越子路徑對(duì)應(yīng)的

5、輸入分量,并縮小交叉和變異操作的范圍,使種群在不斷縮小的空間里尋找測(cè)試數(shù)據(jù);然后針對(duì)多路徑覆蓋測(cè)試數(shù)據(jù)生成問(wèn)題,提出了基于搜索空間縮減的多種群遺傳算法,該方法將目標(biāo)路徑按照具有相同子路徑進(jìn)行分組,并確定每組公共子路徑對(duì)應(yīng)的分量,使用多個(gè)子種群分別進(jìn)化生成各組目標(biāo)路徑的測(cè)試數(shù)據(jù),進(jìn)化過(guò)程中固定子種群內(nèi)被穿越子路徑對(duì)應(yīng)的輸入分量,并縮小交叉和變異操作的范圍,使每個(gè)子種群在不斷縮減的空間里尋找測(cè)試數(shù)據(jù),有效提高了每個(gè)子種群內(nèi)目標(biāo)路徑測(cè)試數(shù)據(jù)的