基于指針別名分析的高效鎖集分析工具.pdf

1、傳統(tǒng)的多線程程序引入了互斥鎖作為一種保護臨界區(qū)域的方式,然而,鎖的使用引入了新的錯誤,例如得到鎖卻沒有釋放。鎖的誤用導致的錯誤是非常常見且難以發(fā)現(xiàn)的。經(jīng)典的靜態(tài)代碼分析工具不用執(zhí)行源代碼程序就可以檢測軟件的錯誤或缺陷,所以被越來越多的采用。用該類技術(shù)實現(xiàn)的死鎖分析工具一般通過遍歷源代碼,根據(jù)程序語句更新程序當中所有鎖的狀態(tài),直到發(fā)現(xiàn)了導致死鎖的一個狀態(tài)。然而,由于缺少程序真正運行時的信息,靜態(tài)分析會變得不精確。例如,程序當中兩條相繼的l

2、ock指令是否會發(fā)生死鎖取決于它們是否是對同一把鎖進行操作,也就是這兩把鎖是否屬于同一個鎖集。在沒有準確信息的情況下,類似的工具只能做保守的估計,導致大量的誤報。
　　如果考慮采用傳統(tǒng)的指針別名分析方法來進行鎖集的識別,會存在兩個問題。一方面如果采用比較精確的上下文敏感流敏感的分析方法,分析效率比較差;另一個方面,如果采用比較簡單的上下文不敏感流不敏感的方法,則導致分析結(jié)果的不精確,原本屬于不同鎖集的鎖變量被判定為互為別名,使得后

3、續(xù)的靜態(tài)分析不能得到理想的結(jié)果。如何進行效率和精度的最大化是一個比較關(guān)鍵的問題。
　　本文通過基于指針別名分析技術(shù),針對鎖分析領(lǐng)域的典型問題,實現(xiàn)一種識別不同鎖集合的技術(shù)來輔助靜態(tài)分析。能夠在靜態(tài)分析工具查詢鎖的指向信息時給出精確的結(jié)果,該結(jié)果必須和流敏感上下文敏感指針分析的精確度相當。同時必須要解決分析的時間和空間效率問題。針對以上需求,本文提出一種利用粗粒度指針分析信息來指導后續(xù)分析的鎖集識別技術(shù),并且在此技術(shù)上開發(fā)了ELFI

4、工具。實驗表明,對于大型程序,ELFI區(qū)分出的鎖集數(shù)量是傳統(tǒng)的Andersen指針分析算法的3至6.6倍;并且經(jīng)過優(yōu)化的ELFI對于分析大程序平均有7.2倍的時間效率提升。
　　本文的主要貢獻有以下幾點:
　　(1)根據(jù)鎖變量在程序當中所占比例比較小這一事實,提出采用靜態(tài)切片技術(shù)對源程序根據(jù)鎖變量進行切片,以減少整個后續(xù)分析的工作量。對傳統(tǒng)的靜態(tài)切片方法進行改進,針對指針分析問題,利用粗粒度指向關(guān)系圖的拓撲結(jié)構(gòu)對相關(guān)指令進行

5、切片。
　　(2)把整個分析過程劃分為兩個獨立的分析階段,第一階段實現(xiàn)了輕量級的Andersen分析算法,并且實現(xiàn)了線下線上優(yōu)化算法、API概括、內(nèi)存存儲優(yōu)化提高分析性能。構(gòu)建粗粒度的指針指向關(guān)系圖,利用分析結(jié)果構(gòu)建數(shù)據(jù)流依賴圖作為細粒度的指針分析的基礎(chǔ)。初步得到的鎖集用來作為靜態(tài)切片的準則。
　　(3)在程序數(shù)據(jù)流依賴圖圖上,實現(xiàn)了上下文敏感、流敏感指針分析,采用二分決策圖來表示內(nèi)存指向關(guān)系,以及上下文信息。優(yōu)化數(shù)據(jù)流依賴