基于不變量的并發(fā)錯(cuò)誤檢測(cè)技術(shù).pdf

1、隨著并發(fā)軟件系統(tǒng)的廣泛應(yīng)用，由多線程的復(fù)雜交互所引發(fā)的并發(fā)錯(cuò)誤無(wú)處不在，因此如何有效檢測(cè)并發(fā)錯(cuò)誤至關(guān)重要。對(duì)于多線程程序而言，并發(fā)錯(cuò)誤的出現(xiàn)依賴于以小概率出現(xiàn)的線程之間特定的交互順序，而并發(fā)錯(cuò)誤通常會(huì)在錯(cuò)綜復(fù)雜的多線程交互中蔓延與擴(kuò)散，因此有效檢測(cè)出并發(fā)錯(cuò)誤的根源難度很大，需要消耗大量的人力與時(shí)間。目前，現(xiàn)有的并發(fā)錯(cuò)誤檢測(cè)技術(shù)大多針對(duì)數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題進(jìn)行交錯(cuò)模式分析，它們的核心思想是抽取線程之間可疑的數(shù)據(jù)訪問(wèn)模式，即從不同線程對(duì)共享數(shù)據(jù)的讀

2、寫順序中抽取模式。然而這類技術(shù)有以下局限性:1）交錯(cuò)模式的數(shù)量可能非常龐大，2）交錯(cuò)模式一般只針對(duì)單變量的讀寫模式，3）所需要的能判斷程序單個(gè)輸出結(jié)果是否正確的機(jī)制oracle在程序的操作層面上不可得。
　　本文提出基于程序不變量的并發(fā)錯(cuò)誤檢測(cè)技術(shù)。首先對(duì)并發(fā)程序中的組件進(jìn)行單元測(cè)試得到參照不變量，然后與組件在集成測(cè)試中得到的線上不變量進(jìn)行對(duì)比后，得到失效不變量。接著在測(cè)試程序的函數(shù)調(diào)用圖上應(yīng)用本文提出的不變量降噪過(guò)程與基于深度搜

3、索的錯(cuò)誤定位策略，得到可疑代碼塊（函數(shù)本身或者函數(shù)與函數(shù)之間的代碼塊）。最后計(jì)算可疑代碼塊的懷疑度并排序，分析組件交互時(shí)產(chǎn)生的并發(fā)錯(cuò)誤。為了驗(yàn)證該技術(shù)的有效性，本文在6個(gè)開源程序上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明本文提出的方法能有效檢測(cè)多種類型的并發(fā)錯(cuò)誤，如違反原子性與死鎖等。
　　本文提出的方法主要的貢獻(xiàn)點(diǎn):1）不需要oracle信息;2）可以在程序的操作層面上利用程序不變量檢測(cè)多種類型的并發(fā)錯(cuò)誤，如違反原子性錯(cuò)誤和死鎖等;3）將并發(fā)錯(cuò)誤