并行程序中bug檢測技術(shù)研究.pdf

1、隨著多核處理器的普及，多線程程序已經(jīng)越來越普遍。對于程序員來說，編寫正確的多線程程序顯得越發(fā)重要。在多線程程序運(yùn)行過程中，線程的調(diào)度順序往往是不確定的，程序員很難完全考慮清楚所有可能的線程調(diào)度順序。并行bug的觸發(fā)通常和某一種特定的線程調(diào)度順序有關(guān)，而這種線程調(diào)度順序又可能隱藏在龐大的線程調(diào)度空間中，因此，并行bug在軟件的測試階段很難被檢測到。而且，并行bug廣泛存在于多線程程序中，嚴(yán)重影響了軟件的可靠性。
　　已有的一些技術(shù)通

2、過動態(tài)測試所有線程調(diào)度順序的方法來檢測并行bug，這類技術(shù)在面對一些規(guī)模稍大的多線程程序時就會效率低下，因為隨著程序規(guī)模的增大，線程調(diào)度順序的規(guī)模也相應(yīng)地呈指數(shù)級增長，因此，這類技術(shù)往往應(yīng)用在規(guī)模小的核心程序上。還有一些技術(shù)通過記錄多線程程序的運(yùn)行時信息，然后根據(jù)所定義的一些并行bug模式來推斷出可疑并行bug，最后再動態(tài)驗證每一個可疑并行bug，檢測到真正的并行bug。這類技術(shù)在檢測并行bug過程中需要對多線程程序進(jìn)行插裝來完成信息記

3、錄和動態(tài)驗證，從而會帶來運(yùn)行時開銷，因此，檢測效率也是并行bug檢測面臨的一大問題。本文面向多線程程序，研究了多種并行bug檢測技術(shù)，提出了多種策略來提高并行bug檢測的效率。
　　1）基于程序切片的并行bug檢測技術(shù)。為了有效地檢測多線程程序中的并行bug，我們采用靜動結(jié)合的方法，同時還使用了程序切片技術(shù)來提高動態(tài)分析的效率。通過靜態(tài)分析程序，能夠得到程序中幾乎所有的可疑并行bug，但同時也可能包含了大量的誤報，因此需要對靜態(tài)分

4、析的結(jié)果進(jìn)行動態(tài)驗證。在動態(tài)驗證之前，我們使用程序切片技術(shù)，將程序中與可疑并行bug無關(guān)的代碼剔除掉。在動態(tài)驗證的時候，只需要對規(guī)模更小的程序進(jìn)行動態(tài)分析就可以檢測到并行bug。其中，靜態(tài)分析的方法能夠有效地指導(dǎo)動態(tài)驗證，使得動態(tài)驗證時可以只分析靜態(tài)分析的結(jié)果；程序切片使得動態(tài)驗證能夠更高效地檢測到真正的并行bug；動態(tài)驗證的作用則有效地優(yōu)化了靜態(tài)分析的結(jié)果。我們實現(xiàn)了一個原型工具ColFinder來驗證我們的方法，ColFinder能

5、夠有效地檢測到多線程程序中的并行bug，程序切片技術(shù)使得并行bug被動態(tài)驗證的時間平均減少了33％。
　　2）基于分布并行的有害數(shù)據(jù)競爭檢測技術(shù)。數(shù)據(jù)競爭是多線程程序中最常見的一種并行bug，我們專門針對這種并行bug提出了一種基于分布并行的檢測技術(shù)。我們使用靜態(tài)數(shù)據(jù)競爭檢測技術(shù)對程序進(jìn)行分析，找到幾乎所有的可疑數(shù)據(jù)競爭。為了檢測到程序中真正有害的數(shù)據(jù)競爭，我們需要對靜態(tài)分析得到的所有可疑數(shù)據(jù)競爭進(jìn)行動態(tài)驗證。但是需要被驗證的可疑

6、數(shù)據(jù)競爭數(shù)量可能非常多，為了提高效率，我們將所有可疑數(shù)據(jù)競爭分發(fā)到多臺機(jī)器上，然后多臺機(jī)器并行地對所有可疑數(shù)據(jù)競爭進(jìn)行動態(tài)驗證。在每臺機(jī)器上，我們通過插裝指令的方式控制線程調(diào)度順序，動態(tài)創(chuàng)建數(shù)據(jù)競爭條件，檢查其是否會造成程序失效。我們實現(xiàn)了一個原型工具PRFinder來驗證我們的方法，PRFinder有效地檢測到了程序中的數(shù)據(jù)競爭，而且檢測的時間隨著機(jī)器數(shù)的增多呈線性減少。
　　3）基于分組歸類的有害數(shù)據(jù)競爭檢測技術(shù)。已有的技術(shù)在

7、動態(tài)驗證數(shù)據(jù)競爭的時候，在程序的每一次動態(tài)運(yùn)行過程中，只驗證一個數(shù)據(jù)競爭是否是有害的。然而，當(dāng)需要驗證的數(shù)據(jù)競爭的數(shù)量很多的時候，就需要運(yùn)行程序很多次才能驗證完所有的數(shù)據(jù)競爭。根據(jù)兩個數(shù)據(jù)競爭的四個訪存操作是否相互沖突，我們提出了一種分組技術(shù)將互不干擾的數(shù)據(jù)競爭歸類到同一組中，使得同一組中的數(shù)據(jù)競爭能夠在程序的一次動態(tài)運(yùn)行過程中被驗證。由于在一次程序動態(tài)運(yùn)行過程中我們需要同時驗證多個數(shù)據(jù)競爭，我們設(shè)計了新的動態(tài)驗證策略來檢測程序中的有害

8、數(shù)據(jù)競爭。我們的方法不僅能夠成功地檢測到有害數(shù)據(jù)競爭，而且需要動態(tài)運(yùn)行程序的次數(shù)比已有的方法少很多。我們實現(xiàn)了一個原型工具RaceChecker來驗證我們的方法，RaceChecker能夠有效地檢測出多線程程序中的有害數(shù)據(jù)競爭，和已有的工作RaceFuzzer和RaceMob相比，RaceChecker檢測時間分別平均減少81%和45%。
　　4）基于線程交織冗余分析的并行bug檢測技術(shù)?；诰€程交織模式的通用并行bug檢測技術(shù)能

9、夠同時檢測到多線程程序中多種類型的并行bug，但是由于其所定義的線程交織模式之間存在著相互重疊，導(dǎo)致有些線程交織會被重復(fù)分析。為了提高檢測效率，我們設(shè)計了一些策略來判斷一個線程交織是否是冗余的，然后針對所有的線程交織提出了一種冗余線程交織剔除算法，根據(jù)這個算法我們可以設(shè)計一種不存在線程交織冗余分析的通用并行bug檢測技術(shù)。為了驗證我們的方法，我們將剔除冗余線程交織的思想應(yīng)用到已有的兩種技術(shù)PECAN和Maple中，實驗結(jié)果表明我們的技術(shù)