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

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

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

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

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

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