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

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

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

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

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

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

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

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