[發(fā)明專(zhuān)利]一種基于聚類(lèi)不變式分析的錯(cuò)誤定位方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201110413498.0
• 申請(qǐng)日: 2011-12-13
• 公開(kāi)（公告）號(hào): CN102521130A
• 公開(kāi)（公告）日: 2012-06-27
• 發(fā)明（設(shè)計(jì)）人: 陳林;吳迪;許蕾;徐寶文
• 申請(qǐng)（專(zhuān)利權(quán)）人: 南京大學(xué)
• 主分類(lèi)號(hào): G06F11/36
• 分類(lèi)號(hào): G06F11/36
• 代理公司: 南京天翼專(zhuān)利代理有限責(zé)任公司 32112
• 代理人: 黃明哲

技術(shù)領(lǐng)域

本發(fā)明屬于程序調(diào)試技術(shù)領(lǐng)域，涉及程序測(cè)試結(jié)果的收集、程序不變式分析，為一種基于聚類(lèi)不變式分析的錯(cuò)誤定位方法。

背景技術(shù)

傳統(tǒng)的基于不變式的程序錯(cuò)誤定位方法主要包含以下幾個(gè)步驟：(1)首先運(yùn)行一批測(cè)試用例，收集與程序中變量相關(guān)的不變式；(2)然后運(yùn)行一個(gè)新的測(cè)試用例，得到這個(gè)測(cè)試用例運(yùn)行后的變量信息；(3)將這些變量信息與收集到的不變式信息進(jìn)行比較，若產(chǎn)生錯(cuò)誤，則判定此次執(zhí)行出錯(cuò)；(4)最后，找到該測(cè)試用例運(yùn)行時(shí)在程序中出錯(cuò)的位置，便達(dá)到了錯(cuò)誤定位的目的。這一方法的主要優(yōu)點(diǎn)是不需要判斷程序執(zhí)行是否正確，而且能得到與程序執(zhí)行有關(guān)的狀態(tài)信息。然而，現(xiàn)有的這一類(lèi)方法所提取的不變式均是針對(duì)整個(gè)程序執(zhí)行空間的，效率比較低，而且所得到的不變式粒度較粗，不能很好地反映程序的局部執(zhí)行狀態(tài)。

在基于不變式的錯(cuò)誤定位方面，主要有S.Hangal和M.S.Lam提出的方法以及B.Pytlik和M.Renieris等人提出的方法。而在程序不變式提取領(lǐng)域成果較為顯著的有M.D.Ernst等人做出的DALKON不變式提取工具。

S.Hangal和M.S.Lam進(jìn)行錯(cuò)誤定位的基本方法是，對(duì)某個(gè)變量a建立不變式1000111101111，其中的每一位表示變量a的一個(gè)屬性，取1的位表示正常執(zhí)行中該位所代表的屬性始終被保持，取0的位表示正常執(zhí)行中該位所代表的屬性沒(méi)有被保持。如果有一次執(zhí)行a的值為0100111101111，第一位不是1，那么顯然違背不變式，則可以推測(cè)該次執(zhí)行有錯(cuò)。這里變量的屬性可以包括變量a的值是否為常數(shù)，是否恒為正值，是否恒為奇數(shù)或偶數(shù)，變量的最小上限或最大上限是否在每次執(zhí)行都被保持。他們所提到不變式起初具有較為嚴(yán)格的條件，隨著正確測(cè)試執(zhí)行的增加而不斷放松。在運(yùn)行完訓(xùn)練測(cè)試集后，對(duì)新的測(cè)試，如果不變式不能得到滿足，就提示程序包含錯(cuò)誤。比如，對(duì)于一個(gè)變量a，它在第一次被賦初始值V，不變式為M。顯然，最初M中的每一位都為1。若又遇一條對(duì)a進(jìn)行賦值的指令，a被賦值成為W’，如果不變式被改成M：＝這樣就放松了不變式的限制條件。使用這樣的位記錄的方法去記錄不變式信息，在空間和時(shí)間上都達(dá)到了很好的效果。在這一方法里，為方便處理，將所有的基本數(shù)據(jù)類(lèi)型都轉(zhuǎn)化成為Integer類(lèi)型的數(shù)據(jù)，而放棄了對(duì)浮點(diǎn)數(shù)類(lèi)型數(shù)據(jù)不變式的收集。

使用這種錯(cuò)誤定位方法，S.Hangal和M.S.Lam做出了一個(gè)對(duì)Java程序進(jìn)行不變式提取及錯(cuò)誤定位的DIDUCE系統(tǒng)。該系統(tǒng)可以自動(dòng)并且快速地對(duì)包含錯(cuò)誤的Java程序進(jìn)行錯(cuò)誤定位，找到出錯(cuò)的根源。目前此種方法對(duì)Java程序的錯(cuò)誤定位有比較好的效果，但是尚未實(shí)踐在其他語(yǔ)言的程序上。

B.Pytlik和M.Renieris等人采用了類(lèi)似的思想提出了一個(gè)基于不變式分析的錯(cuò)誤定位方法。與之前所述方法主要的不同是該方法采用了更為復(fù)雜的不變式描述形式。在他們提出的方法中，主要考慮變量之間的關(guān)系，為變量之間的關(guān)系建立不變式。但是，這種不變式的收集更為困難。在效果方面，目前這兩種方法還沒(méi)有有效的比較。

另外，M.D.Ernst等人在程序不變式的收集上取得了比較豐碩的成果，他們已經(jīng)發(fā)布了一個(gè)較為成熟的不變式收集工具——DALKON，此工具可以用來(lái)收集C，C++，Java，Perl四種語(yǔ)言所寫(xiě)程序中的不變式。而且收集到的不變式信息比較豐富，包括某一變量x是否為常量(x＝a)，是否恒不為0(x≠0)，x的最大下限和最小上限(a≤x≤b)，x與其他變量之間的線性關(guān)系(y＝ax+b)，函數(shù)賦值(x＝fn(y))，包含關(guān)系(x∈y)，是否被排序(xis?sorted)等。這樣的不變式信息可以用在錯(cuò)誤定位、代碼優(yōu)化等領(lǐng)域。

利用DALKON，Y.Brun和M.D.Ernst兩人共同進(jìn)行了對(duì)程序執(zhí)行使用機(jī)器學(xué)習(xí)算法進(jìn)行代碼潛在錯(cuò)誤發(fā)現(xiàn)的工作。在機(jī)器學(xué)習(xí)的訓(xùn)練階段，他們提出了SVM(Support?Vector?Machine)算法和判決樹(shù)算法，并建立了錯(cuò)誤不變式分類(lèi)器(Fault?Invariant?Classifier)的模型。他們發(fā)現(xiàn)，這一模型可以準(zhǔn)確地對(duì)變量正確的屬性和錯(cuò)誤的屬性進(jìn)行分類(lèi)并排序。他們所搜集出的程序中變量的錯(cuò)誤屬性可以幫助程序員去定位錯(cuò)誤。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問(wèn)題是：現(xiàn)有的基于不變式的錯(cuò)誤定位方法都是對(duì)程序的整個(gè)執(zhí)行空間求不變式，再用該不變式判定錯(cuò)誤，得到的不變式粒度較粗，往往不夠精確。需要對(duì)一個(gè)程序的執(zhí)行空間根據(jù)不同的執(zhí)行場(chǎng)景分為多個(gè)部分，分析每個(gè)部分各自不同的不變式，用各個(gè)場(chǎng)景的不變式來(lái)判定一個(gè)執(zhí)行是否存在問(wèn)題，達(dá)到錯(cuò)誤定位的目的。