基于擴(kuò)展馬爾可夫模型的程序約束挖掘方法研究.pdf

1、程序中的時(shí)序約束是一類廣泛存在的約束，其規(guī)定了組件的接口函數(shù)之間調(diào)用的先后順序關(guān)系。例如：調(diào)用java.util.Stack類的peek()函數(shù)之前，如果沒有調(diào)用push函數(shù)，程序會(huì)因?yàn)榭諚６鴴伋鯡mptyStackException異常；又比如調(diào)用java.util.Iteration類的next()函數(shù)之前，如果沒有調(diào)用hasNext()函數(shù)查看是否有元素存在，就會(huì)導(dǎo)致NoSuchElementException異常。根據(jù)時(shí)序約束，

2、可以對(duì)程序進(jìn)行有效的驗(yàn)證，檢測(cè)出多種類型的錯(cuò)誤。然而，時(shí)序約束經(jīng)常被軟件開發(fā)人員忽視，在軟件說明文檔中也鮮有相關(guān)說明。自動(dòng)化程序約束挖掘是獲得時(shí)序約束的重要方法。這類方法大都采用靜態(tài)分析或者動(dòng)態(tài)分析的技術(shù)從程序中提取函數(shù)調(diào)用信息，然后利用數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和數(shù)理統(tǒng)計(jì)等方法歸納出采用各種形式描述的時(shí)序約束。然而，這類方法通常都受訓(xùn)練數(shù)據(jù)中的噪聲和多樣性等因素的制約。為了更好的提取程序中的時(shí)序約束，圍繞著噪聲和多樣性等問題展開研究，采用一種

3、具有終止概率的擴(kuò)展馬爾可夫模型進(jìn)行時(shí)序約束挖掘。首先，基于類之間具有繼承關(guān)系這一性質(zhì)，從程序中收集大量的對(duì)象使用場(chǎng)景作為訓(xùn)練數(shù)據(jù)，然后采用一種聯(lián)機(jī)算法對(duì)擴(kuò)展馬爾可夫模型進(jìn)行訓(xùn)練，最后給出了一種基于客戶端/服務(wù)器架構(gòu)的動(dòng)態(tài)時(shí)序約束挖掘框架。
　　訓(xùn)練數(shù)據(jù)規(guī)模對(duì)于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等方法具有十分重要的意義。一方面，大規(guī)模的訓(xùn)練數(shù)據(jù)能緩解噪聲帶來的干擾；另一方面，大規(guī)模的訓(xùn)練數(shù)據(jù)具有更好的多樣性。因此，收集大量的對(duì)象使用場(chǎng)景作為時(shí)序約束

4、挖掘器的輸入，是緩解數(shù)據(jù)噪聲和多樣性問題并且獲得準(zhǔn)確而完備的時(shí)序約束的重要基礎(chǔ)。大量對(duì)象使用場(chǎng)景提取方法根據(jù)類之間具有繼承關(guān)系這一性質(zhì)，能夠從面向?qū)ο蟪绦蛑刑崛〕鰊倍于傳統(tǒng)方法的對(duì)象使用場(chǎng)景，其中n為程序中的平均繼承深度，為本文工作提供了可靠的數(shù)據(jù)來源。
　　為了進(jìn)一步抵抗訓(xùn)練數(shù)據(jù)中的噪聲，采用一種擴(kuò)展的馬爾可夫模型進(jìn)行時(shí)序約束建模。由于其是一種概率模型，與廣泛采用的有限自動(dòng)機(jī)相比，具有更好的噪聲處理能力。以該模型為基礎(chǔ)，采用一種

5、聯(lián)機(jī)方法進(jìn)行時(shí)序約束挖掘。該方法無須存儲(chǔ)大量的對(duì)象使用場(chǎng)景，其接收對(duì)象使用場(chǎng)景中的一個(gè)函數(shù)調(diào)用，然后對(duì)已經(jīng)存在的時(shí)序約束進(jìn)行更新或者創(chuàng)建一個(gè)新的時(shí)序約束。由于該方法不存儲(chǔ)對(duì)象使用場(chǎng)景，因此具有極小的空間開銷。另一方面，由于該方法能夠?qū)σ延械臅r(shí)序約束進(jìn)行持續(xù)更新，因此能夠挖掘出更具普遍性的模型。為了使用時(shí)序約束，需要將采用概率模型表示的時(shí)序約束轉(zhuǎn)換為一種確定性模型。轉(zhuǎn)換過程中的閾值選擇是獲取正確模型的基礎(chǔ)。采用的閾值計(jì)算方法不僅對(duì)噪聲具有

6、良好的處理能力，而且能夠確保獲得連通的確定性模型。
　　為了減少時(shí)序約束挖掘的成本，推進(jìn)其在工業(yè)界的應(yīng)用，給出了一種基于客戶端/服務(wù)器架構(gòu)的動(dòng)態(tài)時(shí)序約束挖掘框架NSpecMiner。NSpecMiner采用基于擴(kuò)展馬爾可夫模型的時(shí)序約束挖掘方法。其客戶端為一個(gè)動(dòng)態(tài)程序追蹤器，負(fù)責(zé)對(duì)目標(biāo)程序進(jìn)行插樁并將收集的程序執(zhí)行軌跡發(fā)送到服務(wù)器端。服務(wù)器端從廣泛分布于網(wǎng)絡(luò)上的客戶端接收大量程序執(zhí)行軌跡并進(jìn)行時(shí)序約束挖掘。挖掘的時(shí)序約束集中存儲(chǔ)于

7、服務(wù)器端，為程序驗(yàn)證、軟件測(cè)試和程序進(jìn)化等應(yīng)用提供數(shù)據(jù)支持。與本地挖掘器相比，NSpecMiner更容易獲得大量的訓(xùn)練數(shù)據(jù)。更重要的是，如果將程序追蹤器集成在廣泛應(yīng)用的軟件中，則當(dāng)軟件被使用時(shí)，收集的程序執(zhí)行軌跡便會(huì)自動(dòng)的發(fā)送到服務(wù)器端進(jìn)行時(shí)序約束挖掘。由于該方法不需要耗費(fèi)額外的人力運(yùn)行目標(biāo)程序，因此大大降低了時(shí)序約束挖掘的成本。
　　為了對(duì)以上工作進(jìn)行驗(yàn)證，基于Java1.6開發(fā)了動(dòng)態(tài)時(shí)序約束挖掘器ISpecMiner并進(jìn)行了相