資源描述：
《基于擴展馬爾可夫模型的程序約束挖掘方法研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinComputerScienceandTechnologyResearchonMiningProgramSpecificationsBasedonExtendedMarkovModelPh.D.Candidate：DengChenMajor：ComputerSoftwareandTheorySupervisor：Prof.YanshengLuHua
2、zhongUniversityofScienceandTechnologyWuhan，Hubei430074，P.R.ChinaSeptember，2014獨創(chuàng)性聲明本人聲明所呈交的學位論文是我個人在導師指導下進行的研究工作及取得的研究成果。盡我所知，除文中已經(jīng)標明引用的內(nèi)容外，本論文不包含任何其它個人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對本文的研究做出貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明的法律結(jié)果由本人承擔。學位論文作者簽名：日期：年月日學位論文版權(quán)使用授權(quán)書本學位論文作者完全了解學校有關(guān)保留、使用學
3、位論文的規(guī)定，即：學校有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復印件和電子版，允許論文被查閱和借閱。本人授權(quán)華中科技大學可以將本學位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。本論文屬于保密□，在_____年解密后適用本授權(quán)書。不保密□。學位論文作者簽名：指導教師簽名：日期：年月日日期：年月日華中科技大學博士學位論文摘要程序中的時序約束是一類廣泛存在的約束，其規(guī)定了組件的接口函數(shù)之間調(diào)用的先后順序關(guān)系。例如：調(diào)用java.util.Stack類的peek()函數(shù)之前，如果沒
4、有調(diào)用push()函數(shù)，程序會因為空棧而拋出EmptyStackException異常；又比如調(diào)用java.util.Iteration類的next()函數(shù)之前，如果沒有調(diào)用hasNext()函數(shù)查看是否有元素存在，就會導致NoSuchElementException異常。根據(jù)時序約束，可以對程序進行有效的驗證，檢測出多種類型的錯誤。然而，時序約束經(jīng)常被軟件開發(fā)人員忽視，在軟件說明文檔中也鮮有相關(guān)說明。自動化程序約束挖掘是獲得時序約束的重要方法。這類方法大都采用靜態(tài)分析或者動態(tài)分析的技術(shù)從程序中提取函數(shù)調(diào)用信息，然后利用數(shù)據(jù)挖掘
5、、機器學習和數(shù)理統(tǒng)計等方法歸納出采用各種形式描述的時序約束。然而，這類方法通常都受訓練數(shù)據(jù)中的噪聲和多樣性等因素的制約。為了更好的提取程序中的時序約束，圍繞著噪聲和多樣性等問題展開研究，采用一種具有終止概率的擴展馬爾可夫模型進行時序約束挖掘。首先，基于類之間具有繼承關(guān)系這一性質(zhì)，從程序中收集大量的對象使用場景作為訓練數(shù)據(jù)，然后采用一種聯(lián)機算法對擴展馬爾可夫模型進行訓練，最后給出了一種基于客戶端/服務器架構(gòu)的動態(tài)時序約束挖掘框架。訓練數(shù)據(jù)規(guī)模對于數(shù)據(jù)挖掘、機器學習等方法具有十分重要的意義。一方面，大規(guī)模的訓練數(shù)據(jù)能緩解噪聲帶來的干
6、擾；另一方面，大規(guī)模的訓練數(shù)據(jù)具有更好的多樣性。因此，收集大量的對象使用場景作為時序約束挖掘器的輸入，是緩解數(shù)據(jù)噪聲和多樣性問題并且獲得準確而完備的時序約束的重要基礎(chǔ)。大量對象使用場景提取方法根據(jù)類之間具有繼承關(guān)系這一性質(zhì)，能夠從面向?qū)ο蟪绦蛑刑崛〕鰊倍于傳統(tǒng)方法的對象使用場景，其中n為程序中的平均繼承深度，為本文工作提供了可靠的數(shù)據(jù)來源。為了進一步抵抗訓練數(shù)據(jù)中的噪聲，采用一種擴展的馬爾可夫模型進行時序約束建模。由于其是一種概率模型，與廣泛采用的有限自動機相比，具有更好的噪聲處理能力。以該模型為基礎(chǔ)，采用一種聯(lián)機方法進行時序約
7、束挖掘。該方法無須存儲大量的對象使用場景，其接收對象使用場景中的一個函數(shù)調(diào)用，然后對已經(jīng)存在I華中科技大學博士學位論文的時序約束進行更新或者創(chuàng)建一個新的時序約束。由于該方法不存儲對象使用場景，因此具有極小的空間開銷。另一方面，由于該方法能夠?qū)σ延械臅r序約束進行持續(xù)更新，因此能夠挖掘出更具普遍性的模型。為了使用時序約束，需要將采用概率模型表示的時序約束轉(zhuǎn)換為一種確定性模型。轉(zhuǎn)換過程中的閾值選擇是獲取正確模型的基礎(chǔ)。采用的閾值計算方法不僅對噪聲具有良好的處理能力，而且能夠確保獲得連通的確定性模型。為了減少時序約束挖掘的成本，推進其在
8、工業(yè)界的應用，給出了一種基于客戶端/服務器架構(gòu)的動態(tài)時序約束挖掘框架NSpecMiner。NSpecMiner采用基于擴展馬爾可夫模型的時序約束挖掘方法。其客戶端為一個動態(tài)程序追蹤器，負責對目標程序進行插樁并將收集的程序執(zhí)行軌跡發(fā)送到服務器端。服務器端從廣泛分布
