基于變異的錯(cuò)誤定位優(yōu)化技術(shù)研究.pdf

1、識(shí)別軟件系統(tǒng)中存在錯(cuò)誤的代碼位置是軟件調(diào)試過(guò)程中最為困難和耗時(shí)的環(huán)節(jié)之一。最近提出的基于變異的錯(cuò)誤定位(Mutation Based Fault Localization，MBFL)技術(shù)是目前定位精度最好的一種自動(dòng)化錯(cuò)誤定位技術(shù)，能有效減少開(kāi)發(fā)人員查找錯(cuò)誤所需要的時(shí)間消耗。MBFL技術(shù)源于變異測(cè)試，需要對(duì)被測(cè)程序生成變異體，執(zhí)行測(cè)試用例，并利用執(zhí)行信息來(lái)進(jìn)行錯(cuò)誤定位。通常變異體和測(cè)試用例數(shù)量都隨程序規(guī)模增加而增大，而MBFL技術(shù)需要在每

2、個(gè)變異體上執(zhí)行所有測(cè)試用例，因此執(zhí)行開(kāi)銷(xiāo)很大。以軟件回歸測(cè)試領(lǐng)域經(jīng)典的基準(zhǔn)被測(cè)程序space為例，該程序可執(zhí)行的代碼行數(shù)為5K～6K，程序自帶1萬(wàn)多個(gè)測(cè)試用例，可生成的變異體接近4萬(wàn)個(gè)。如果使用MBFL技術(shù)定位該程序中的錯(cuò)誤，需要執(zhí)行約5億次變異測(cè)試(Mutant-Test Pair,MTP)，時(shí)間花費(fèi)巨大。MBFL技術(shù)具有很高的錯(cuò)誤定位精度，約減變異執(zhí)行是改進(jìn)MBFL技術(shù)的有效手段。所以在保證錯(cuò)誤定位精度前提下，如何優(yōu)化變異體執(zhí)行，減

3、少執(zhí)行開(kāi)銷(xiāo)，是在實(shí)際中應(yīng)用MBFL技術(shù)的關(guān)鍵研究問(wèn)題。
　　本文從多個(gè)角度研究MBFL優(yōu)化問(wèn)題，在保持原始MBFL技術(shù)錯(cuò)誤定位高精度的前提下，提出變異測(cè)試執(zhí)行的優(yōu)化方法，進(jìn)而降低MBFL執(zhí)行開(kāi)銷(xiāo)，為MBFL技術(shù)從理論研究走向?qū)嶋H應(yīng)用奠定基礎(chǔ)。
　　本文具體研究?jī)?nèi)容如下:
　　(1)面向MBFL的變異體靜態(tài)采樣方法:
　　變異體采樣是一種約減變異執(zhí)行的有效方法，但不可避免的帶來(lái)定位精度損失的問(wèn)題。為減少M(fèi)BFL錯(cuò)誤

4、定位精度由于變異體約減帶來(lái)的損耗，本文首先針對(duì)變異體采樣研究相關(guān)因素與錯(cuò)誤定位精度之間的關(guān)系，具體包括采樣粒度、采樣前后的變異體集合的語(yǔ)句分布、變異算子分布、錯(cuò)誤分布等。在此基礎(chǔ)上，提出了基于語(yǔ)句層面的細(xì)粒度變異體采樣和面向錯(cuò)誤分布的變異體采樣兩種策略。相比原始MBFL，這兩種技術(shù)可以有效提高變異體的變異算子完整性和語(yǔ)句分布多樣性。實(shí)驗(yàn)表明，應(yīng)用這兩種策略可以在錯(cuò)誤定位精度損失很小的前提下，平均減少約80％的變異體，有效提高了MBFL執(zhí)

5、行效率。
　　(2)MBFL變異體執(zhí)行動(dòng)態(tài)優(yōu)化方法:
　　在MBFL變異體執(zhí)行過(guò)程中，通過(guò)研究語(yǔ)句懷疑度、變異體懷疑度計(jì)算和變異體執(zhí)行測(cè)試用例結(jié)果之間的相互關(guān)系，提出了面向變異體和面向測(cè)試用例的兩種動(dòng)態(tài)優(yōu)化策略，在變異執(zhí)行過(guò)程中，動(dòng)態(tài)約減變異體和測(cè)試用例的執(zhí)行。實(shí)驗(yàn)結(jié)果顯示應(yīng)用這兩種動(dòng)態(tài)優(yōu)化策略的MBFL技術(shù)能在保留原始MBFL錯(cuò)誤定位精度不變的前提下，平均減少約53.9％的變異體執(zhí)行開(kāi)銷(xiāo);
　　(3)靜態(tài)與動(dòng)態(tài)相結(jié)合

6、的MBFL優(yōu)化技術(shù):
　　通過(guò)整合前面兩個(gè)方面的研究成果，提出了一種結(jié)合變異體靜態(tài)采樣和變異體執(zhí)行動(dòng)態(tài)優(yōu)化方法的MBFL整體優(yōu)化技術(shù)框架。實(shí)驗(yàn)結(jié)果表明，應(yīng)用該優(yōu)化技術(shù)能在保留原始MBFL錯(cuò)誤定位高精度的前提下，平均減少約87.9％的變異體執(zhí)行開(kāi)銷(xiāo)，顯著提升了MBFL技術(shù)的執(zhí)行效率。
　　綜上所述，本文針對(duì)MBFL變異體執(zhí)行時(shí)間開(kāi)銷(xiāo)太大的問(wèn)題，在變異體運(yùn)行測(cè)試用例之前，研究?jī)煞N變異體采樣策略形成了一種能有效降低變異體規(guī)模同時(shí)保

7、持原始MBFL錯(cuò)誤定位高精度的變異體采樣方法;在變異體執(zhí)行測(cè)試用例過(guò)程中，提出了面向變異體約減和測(cè)試用例約減兩種動(dòng)態(tài)優(yōu)化策略，形成了一種MBFL變異體執(zhí)行動(dòng)態(tài)優(yōu)化技術(shù)，并通過(guò)理論分析了該方法可以保證不損失原MBFL技術(shù)的錯(cuò)誤定位精度;最后，實(shí)現(xiàn)了靜態(tài)與動(dòng)態(tài)優(yōu)化相結(jié)合的完整MBFL優(yōu)化技術(shù)，在保留原始MBFL技術(shù)錯(cuò)誤定位高精度的前提下，減少了約87.9％的變異體執(zhí)行開(kāi)銷(xiāo)，大幅度提升了MBFL的執(zhí)行效率，為MBFL技術(shù)從理論研究走向?qū)嶋H應(yīng)用