論文名：SMOKE: Scalable Path-Sensitive Memory Leak Detection for Millions of Lines of Code

來源會議：ICSE 2019

來源團(tuán)隊(duì)：香港科技大學(xué)（源傘團(tuán)隊(duì)）

簡介

盡管過去幾十年工業(yè)界和學(xué)術(shù)界都花很大努力在檢測內(nèi)存泄露漏洞上，但是在工業(yè)界級的代碼量上的效果一直不是很好?，F(xiàn)有的工作存在一個(gè)很難解決的悖論問題——犧牲擴(kuò)展性換取高精度，或者擴(kuò)展性好，但精度不高。

這篇文章用了staged approach（分步驟）來解決這個(gè)問題。第一步，使用擴(kuò)展性好但是不精確的分析去計(jì)算候選的內(nèi)存泄露路徑。第二步，使用更精確的分析去驗(yàn)證這些候選路徑的可行性。第一步是可擴(kuò)展的，因?yàn)槭褂昧诵碌南∈璩绦虮硎痉椒ā猽se flow graph（UFG）。UFG能夠進(jìn)行多項(xiàng)式時(shí)間狀態(tài)分析。第二步是精確和高效的，因?yàn)橹挥泻苄〔糠值暮蜻x路徑，并且設(shè)計(jì)了小巧的約束求解器。

實(shí)驗(yàn)結(jié)果表示SMOKE能夠檢測高達(dá)800萬行的代碼，并且誤報(bào)只有24.4%。同時(shí)，SMOKE比現(xiàn)有的工業(yè)工具都要快，大概快5.2x到22.8x之間。在29個(gè)成熟的常用的benchmark里，smoke發(fā)現(xiàn)了30個(gè)未知的漏洞，均被開發(fā)者驗(yàn)證，其中1個(gè)有CVE-ID。

要解決的問題

內(nèi)存泄露漏洞很多。

• 2018上半年僅僅火狐瀏覽器和谷歌瀏覽器就檢測出超過680個(gè)內(nèi)存泄露漏洞。
• 2017年超過240個(gè)CVE都是內(nèi)存泄露漏洞。

現(xiàn)在的檢測工具在擴(kuò)展性和準(zhǔn)確性做權(quán)衡。

其中一類工作犧牲路徑敏感性來換取擴(kuò)展性，但同時(shí)精確度也不高。比如SABER，最近的一個(gè)路徑不敏感的內(nèi)存泄露檢測技術(shù)，在我們的評估中有66.7%的誤報(bào)。

另外一種工作，遍歷控制流圖，并使用路徑敏感分析來實(shí)現(xiàn)高精度。然而經(jīng)常會遇到擴(kuò)展性問題，尤其是對整個(gè)程序進(jìn)行分析時(shí)。比如SATURN在500萬行的代碼上檢測內(nèi)存泄露需要超過23小時(shí)。其他的比如CSA和INFER，兩個(gè)小時(shí)后就撲街了。

如何解決的

作者發(fā)現(xiàn)程序中只有一小部分的路徑會導(dǎo)致內(nèi)存泄露。為了檢測成千上百萬行的代碼，作者認(rèn)為稀疏值流分析可以通過VFG來追蹤數(shù)據(jù)依賴圖的關(guān)系，并且效果要比控制流圖要好。然而，作者發(fā)現(xiàn)VFG要檢車任意的有限狀態(tài)機(jī)屬性（比如內(nèi)存泄露問題）效果不是很好。作者再簡單證明了一下直接用VFG方法來檢測內(nèi)存泄露問題是個(gè)NP難問題。

為了解決這一問題，作者擴(kuò)展了VFG，叫做UFG，將堆對象的定義和使用都編碼進(jìn)圖了。所有堆對象的使用的地方根據(jù)控制流圖來排序，并且用多項(xiàng)式時(shí)間圖搜索方法來找到潛在的內(nèi)存泄露路徑。驗(yàn)證過程是很高效的，平均路徑長度只有21…作者使用了約束求解器來過濾掉一些矛盾的路徑。最后用z3來解決剩下的候選路徑。

smoke系統(tǒng)的框架如下圖所示。作者將LLVM 字節(jié)碼文件作為輸入。首先預(yù)處理階段使用流敏感和上下文敏感的指針分析去計(jì)算數(shù)據(jù)依賴。同時(shí)在控制流圖的逆向圖里計(jì)算控制依賴。為了構(gòu)建調(diào)用圖，我們使用must-alias結(jié)果來解決函數(shù)指針的問題，同時(shí)用class hierarchy 分析來解決虛函數(shù)調(diào)用問題。在狀態(tài)分析里，只考慮內(nèi)存分配操作成功的情況。比如，x=malloc()。

下面幾張圖感覺很淺顯易懂，讓我們知道文章的UFG圖到底干了啥。

到達(dá)的效果如何

作者選擇的測試程序有SPEC2000和17個(gè)開源程序。同時(shí)和相關(guān)工作SABE，PINPOINT，CSA和INFER做了對比。主要針對擴(kuò)展性、準(zhǔn)確性和召回率做了評估。并且還對兩個(gè)步驟的貢獻(xiàn)程度做了評估。此外還貼了代碼說明自己的誤報(bào)在哪里。

擴(kuò)展性的實(shí)驗(yàn)結(jié)果如下：

準(zhǔn)確性和召回率的結(jié)果：

兩個(gè)分析步驟的數(shù)據(jù)：

一個(gè)誤報(bào)例子：

還有哪些沒解決的

在某些情況下準(zhǔn)確率也不好。

• lack of library specification，詳見figure11

• 指針分析自身的不精確的問題。

• 有些在分支條件里弄了很多復(fù)雜運(yùn)算、或者復(fù)雜數(shù)據(jù)依賴、或者很深的過程間影響的路徑都沒辦法識別出來。犧牲擴(kuò)展性可以緩解該問題。

總結(jié)

感覺文章的圖畫的不錯(cuò)，寫作上也很清晰，以后寫論文可以照這篇來寫。

總體來說是不錯(cuò)的工作。值得借鑒學(xué)習(xí)！

文章工作開源于：https://smokeml.github.io/

總結(jié)

以上是生活随笔為你收集整理的【论文分享】SMOKE: Scalable Path-Sensitive Memory Leak Detection for Millions of Lines of Code的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。