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

1、程序中的時序約束是一類廣泛存在的約束，其規(guī)定了組件的接口函數(shù)之間調(diào)用的先后順序關系。例如：調(diào)用java.util.Stack類的peek()函數(shù)之前，如果沒有調(diào)用push函數(shù)，程序會因為空棧而拋出EmptyStackException異常；又比如調(diào)用java.util.Iteration類的next()函數(shù)之前，如果沒有調(diào)用hasNext()函數(shù)查看是否有元素存在，就會導致NoSuchElementException異常。根據(jù)時序約束，

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

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

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

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

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

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