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

《基于擴(kuò)展馬爾可夫模型的程序約束挖掘方法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinComputerScienceandTechnologyResearchonMiningProgramSpecificationsBasedonExtendedMarkovModelPh.D.Candidate：DengChenMajor：ComputerSoftwareandTheorySupervisor：Prof.YanshengLuHua

2、zhongUniversityofScienceandTechnologyWuhan，Hubei430074，P.R.ChinaSeptember，2014獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除文中已經(jīng)標(biāo)明引用的內(nèi)容外，本論文不包含任何其它個(gè)人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對(duì)本文的研究做出貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到本聲明的法律結(jié)果由本人承擔(dān)。學(xué)位論文作者簽名：日期：年月日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)

3、位論文的規(guī)定，即：學(xué)校有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)華中科技大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。本論文屬于保密□，在_____年解密后適用本授權(quán)書。不保密□。學(xué)位論文作者簽名：指導(dǎo)教師簽名：日期：年月日日期：年月日華中科技大學(xué)博士學(xué)位論文摘要程序中的時(shí)序約束是一類廣泛存在的約束，其規(guī)定了組件的接口函數(shù)之間調(diào)用的先后順序關(guān)系。例如：調(diào)用java.util.Stack類的peek()函數(shù)之前，如果沒

4、有調(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í)序約束，可以對(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ù)挖掘

5、、機(jī)器學(xué)習(xí)和數(shù)理統(tǒng)計(jì)等方法歸納出采用各種形式描述的時(shí)序約束。然而，這類方法通常都受訓(xùn)練數(shù)據(jù)中的噪聲和多樣性等因素的制約。為了更好的提取程序中的時(shí)序約束，圍繞著噪聲和多樣性等問題展開研究，采用一種具有終止概率的擴(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ù)能緩解噪聲帶來的干

6、擾；另一方面，大規(guī)模的訓(xùn)練數(shù)據(jù)具有更好的多樣性。因此，收集大量的對(duì)象使用場(chǎng)景作為時(shí)序約束挖掘器的輸入，是緩解數(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ǔ)，采用一種聯(lián)機(jī)方法進(jìn)行時(shí)序約

7、束挖掘。該方法無須存儲(chǔ)大量的對(duì)象使用場(chǎng)景，其接收對(duì)象使用場(chǎng)景中的一個(gè)函數(shù)調(diào)用，然后對(duì)已經(jīng)存在I華中科技大學(xué)博士學(xué)位論文的時(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ì)噪聲具有良好的處理能力，而且能夠確保獲得連通的確定性模型。為了減少時(shí)序約束挖掘的成本，推進(jìn)其在

8、工業(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ù)器端從廣泛分布