---

前言

??此博客為PathAFL：Path-Coverage Assisted Fuzzing論文的閱讀筆記，本篇論文提出了一種新的跟蹤執(zhí)行路徑的方法、路徑過(guò)濾算法和追蹤執(zhí)行路徑的方法，以提高Fuzz的準(zhǔn)確性以及Fuzz性能。本文將會(huì)從解決的問(wèn)題和目標(biāo)、技術(shù)路線、達(dá)到的效果和結(jié)論四個(gè)角度來(lái)分析本篇論文。以下就是本文的全部?jī)?nèi)容。

---

PathAFL：Path-Coverage Assisted Fuzzing

1、解決的問(wèn)題和目標(biāo)

??現(xiàn)有的覆蓋引導(dǎo)fuzzer通常使用所探索的基本塊或邊的數(shù)量來(lái)測(cè)量代碼覆蓋，路徑覆蓋可以提供比基本塊和邊緣覆蓋更準(zhǔn)確的覆蓋信息。然而，路徑的數(shù)量隨著程序大小的增加而呈指數(shù)級(jí)增長(zhǎng)，幾乎不可能追蹤真實(shí)世界應(yīng)用程序的所有路徑，這也是本文亟待解決的問(wèn)題。針對(duì)此問(wèn)題，本文完成了以下幾個(gè)目標(biāo)：

1. 作者提出了一種新的跟蹤執(zhí)行路徑的方法，并在跟蹤路徑覆蓋粒度和fuzzing性能之間進(jìn)行了權(quán)衡。研究發(fā)現(xiàn)，作者可以用很少的開(kāi)銷(xiāo)來(lái)追蹤重要的路徑
2. 作者設(shè)計(jì)了一種路徑過(guò)濾算法，它對(duì)新的路徑做出了快速的判斷。只有那些滿(mǎn)足特定條件并具有高權(quán)重的路徑才會(huì)添加到種子隊(duì)列中
3. 作者提出了一種追蹤執(zhí)行路徑的新方法，并在追蹤路徑覆蓋的細(xì)粒度和模糊性能之間進(jìn)行了權(quán)衡。研究發(fā)現(xiàn)，作者可以在幾乎沒(méi)有額外開(kāi)銷(xiāo)的情況下追蹤重要路徑
4. 作者開(kāi)發(fā)了PathAFL的開(kāi)源實(shí)現(xiàn)，并將其作為AFL的分支發(fā)布在Github上

2、技術(shù)路線

??關(guān)于PathAFL的工作過(guò)程如下圖所示（紫色的組件顯示了作者對(duì)原始AFL的改進(jìn)）：

由上圖可知，PathAFL是在AFL的基礎(chǔ)上進(jìn)行改進(jìn)的，而AFL的整個(gè)工作流程如下所示：

1. 對(duì)目標(biāo)應(yīng)用插樁
2. 向種子隊(duì)列提供初始輸入
3. 選擇種子。AFL根據(jù)種子選擇算法從種子隊(duì)列中選擇一個(gè)種子，該算法更喜歡更快、更小的種子。種子選擇算法采用貪婪算法實(shí)現(xiàn)，如下圖所示：
   
4. 變異種子。該步驟使用多種變異算法對(duì)種子文件進(jìn)行變異，并在循環(huán)中生成大量測(cè)試用例
5. 測(cè)試和跟蹤。此步驟以測(cè)試用例為輸入，執(zhí)行并跟蹤插樁指令的目標(biāo)應(yīng)用程序
6. 報(bào)告崩潰。如果發(fā)現(xiàn)崩潰，則可能觸發(fā)了潛在的漏洞
7. 識(shí)別種子。如果發(fā)現(xiàn)新的邊緣覆蓋狀態(tài)，則將測(cè)試用例添加到下一個(gè)循環(huán)的種子隊(duì)列中
8. 如果該種子的fuzzing結(jié)束，則轉(zhuǎn)到步驟(3)，否則轉(zhuǎn)到步驟(4)

??需要注意的是，整個(gè)fuzzing處理過(guò)程是一個(gè)無(wú)限循環(huán)，只有在手動(dòng)終止時(shí)才會(huì)結(jié)束循環(huán)。此外，因?yàn)锳FL使用哈希計(jì)算來(lái)存儲(chǔ)邊緣覆蓋信息（需要通過(guò)在每個(gè)BBL中插入一個(gè)BID隨機(jī)數(shù)來(lái)進(jìn)行哈希計(jì)算），不過(guò)這樣會(huì)存在哈希沖突的問(wèn)題（哈希沖突率通常在30%~70%范圍內(nèi)浮動(dòng)）。為了解決這個(gè)問(wèn)題，AFL又發(fā)展為了CollAFL，CollAFL使用新的哈希計(jì)算來(lái)存儲(chǔ)邊緣覆蓋信息，這樣可以讓哈希沖突降低到接近0%（不過(guò)CollAFL只使用了邊緣覆蓋）。此外，CollAFL還遵循以下三個(gè)新的種子選擇策略：

9. 具有更多未受影響的相鄰分支的種子將優(yōu)先進(jìn)行fuzzing處理
10. 更喜歡有更多未受影響的鄰居后代的種子
11. 更喜歡具有更多內(nèi)存訪問(wèn)操作的種子

??現(xiàn)在我們對(duì)AFL和CollAFL已經(jīng)有了較深的理解，不過(guò)上面提到的這兩種技術(shù)的覆蓋率信息又是什么東西呢？覆蓋率信息可以看作是評(píng)判fuzzer的能力的一項(xiàng)指標(biāo)，覆蓋率越高，說(shuō)明fuzzer探索到的路徑越多，故越有可能發(fā)現(xiàn)漏洞；反之則說(shuō)明覆蓋率越低，說(shuō)明fuzzer探索到的路徑越少，故越?jīng)]有可能發(fā)現(xiàn)漏洞。目前測(cè)量代碼覆蓋率的方法主要有三種：

12. $BBL$覆蓋率（基本塊覆蓋率）：$BBL$是一個(gè)有一個(gè)入口和一個(gè)出口點(diǎn)的代碼片段，BBL中的指令將按順序執(zhí)行，并且只執(zhí)行一次。$BBL$是程序執(zhí)行的最小相干單元，可以通過(guò)第一條指令的地址來(lái)識(shí)別。通過(guò)代碼插入和靜態(tài)分析可以很容易地提取BBL信息。由于這些優(yōu)點(diǎn)，$BBL$覆蓋信息被fuzzer廣泛使用。而典型的基于$BBL$的覆蓋引導(dǎo)fuzzer只跟蹤每個(gè)塊是否被擊中，而不跟蹤fuzzing過(guò)程中哪些塊被擊中的順序，因此詳細(xì)信息會(huì)丟失。如下圖所示，在fuzzing過(guò)程中，如果首先執(zhí)行程序路徑$1（A，B，C，D）$，則與程序路徑$2（A，B，D）$相關(guān)聯(lián)的測(cè)試用例將永遠(yuǎn)不會(huì)添加到種子隊(duì)列中，因?yàn)槁窂?span id="vxwlu0yf4" class="katex--inline">$2$沒(méi)有命中新的$BBL$，因此邊緣$BD$的信息將丟失。
    
13. 邊緣覆蓋率：為了解決$BBL$覆蓋的缺點(diǎn)，邊緣覆蓋跟蹤每條邊緣是否被擊中。在上圖的例子中，如果首先執(zhí)行程序路徑$1（A，B，C，D）$，fuzzer將記錄邊緣$AB$、$BC$和$CD$，當(dāng)執(zhí)行路徑時(shí)將記錄新的邊緣$BD$，因此與路徑$2$相關(guān)的測(cè)試用例現(xiàn)在將添加到種子隊(duì)列中。然而，邊緣覆蓋并不能追蹤邊緣被命中的順序，因此一些詳細(xì)信息可能會(huì)丟失。我們使用下圖中的簡(jiǎn)單程序和其控制流圖來(lái)說(shuō)明這個(gè)問(wèn)題，該程序以$8$個(gè)字符作為輸入。當(dāng)輸入為abcd**?$或**cdef!!時(shí)，程序?qū)⒈罎ⅰ?br />
14. 路徑覆蓋率：基于路徑覆蓋的方法跟蹤整個(gè)執(zhí)行路徑，包括命中的順序邊緣，從而記錄最豐富的信息。幾乎不可能為真實(shí)世界的應(yīng)用程序?qū)崿F(xiàn)路徑覆蓋，因?yàn)槌绦蛑杏刑嗟难h(huán)和條件，路徑的數(shù)量會(huì)激增。海量路徑將帶來(lái)較大的運(yùn)行時(shí)開(kāi)銷(xiāo)，并可能降低模糊處理的效率。為了克服這個(gè)問(wèn)題，作者將新探索的路徑分為兩類(lèi)：
    • 對(duì)于之前未觸及的邊，作者將其表示為$e?path$。$“e?”$表示路徑有新的邊
    • 所有邊都已接觸的路徑，作者將其表示為$h?path$。$“h?”$表示路徑有一個(gè)新的哈希
      關(guān)鍵問(wèn)題是如何處理大量的$h?path$，作者的解決方案是，不將所有的$h?path$添加到種子隊(duì)列，而只將那些高權(quán)重的$h?path$增加到種子隊(duì)列。這是一種效率和追蹤粒度之間的權(quán)衡。

??根據(jù)上文分析可以發(fā)現(xiàn)，目前主要的挑戰(zhàn)是路徑的數(shù)量隨著程序大小的增加而呈指數(shù)級(jí)增長(zhǎng)。因此，建議只向種子隊(duì)列添加重要路徑。根據(jù)這一思想，作者總結(jié)了路徑覆蓋輔助fuzzer的三個(gè)關(guān)鍵問(wèn)題：

1. 如何識(shí)別$h?path$？
2. 如何減少$h?path$的數(shù)量?
3. 哪些$h?path$將被添加到種子隊(duì)列？

2.1、如何識(shí)別$h?path$？

??靜態(tài)插樁。AFL在編譯時(shí)對(duì)目標(biāo)程序進(jìn)行插樁。插樁代碼計(jì)算邊緣哈希并更新邊緣覆蓋記錄到共享內(nèi)存中。PathAFL維護(hù)一個(gè)類(lèi)似AFL的全局哈希表。表索引表示路徑哈希，值表示路徑是否被覆蓋。PathAFL以類(lèi)似的方式對(duì)目標(biāo)程序進(jìn)行插樁。它只在AFL原始插樁代碼中插入了一小段代碼來(lái)計(jì)算路徑哈希。此外，PathAFL擴(kuò)展了原始共享內(nèi)存，以存儲(chǔ)路徑哈希值的4個(gè)字節(jié)。在程序執(zhí)行期間，執(zhí)行路徑的哈希值會(huì)實(shí)時(shí)計(jì)算并追加到共享內(nèi)存中。當(dāng)程序運(yùn)行完成時(shí)，執(zhí)行路徑哈?？捎糜诖_定是否已探索新路徑。與AFL相比，PathAFL只在插入代碼中添加了哈希計(jì)算函數(shù)，導(dǎo)致開(kāi)銷(xiāo)增加很少。

2.2、如何減少$h?path$的數(shù)量？

??PathAFL采用兩種方法來(lái)降低執(zhí)行路徑的跟蹤粒度，以便模糊器可以限制新$h?path$的數(shù)量：

1. 選擇性插樁：AFL默認(rèn)情況下對(duì)目標(biāo)程序中的所有邊緣進(jìn)行檢測(cè)，使我們能夠跟蹤幾乎所有的執(zhí)行路徑。為了減少路徑，PathAFL必須降低跟蹤粒度，只檢測(cè)部分$BBL$并跟蹤到達(dá)新BBL或觸發(fā)新錯(cuò)誤的概率更高的路徑。為了實(shí)現(xiàn)這個(gè)目的，PathAFL僅對(duì)一些函數(shù)進(jìn)行執(zhí)行路徑的插樁。提出以下四個(gè)策略來(lái)選擇關(guān)鍵函數(shù)（根據(jù)以下策略，可以有效地減少新發(fā)現(xiàn)的$h?path$的數(shù)量）：

   • 插樁較大的函數(shù)，默認(rèn)為最大的$20$。因此，可以找到許多通過(guò)這些函數(shù)的$h?path$
   • 插樁具有內(nèi)存操作的函數(shù)，例如函數(shù)名包含alloc/free的函數(shù)
   • 忽略太小的函數(shù)。類(lèi)似于第一個(gè)策略，函數(shù)越小，代碼越少
   • 對(duì)其他函數(shù)的$10$進(jìn)行插樁

2. 哈希算法：作者采用了一個(gè)非常簡(jiǎn)單的方案，直接使用全加運(yùn)算作為路徑哈希算法，并以粗粒度的方式區(qū)分執(zhí)行路徑。哈希算法如下：
   
   $p$表示執(zhí)行路徑。$BS$表示所有插樁的基本塊的執(zhí)行序列。只需在現(xiàn)有的插樁代碼中插入一個(gè)add匯編指令，對(duì)測(cè)試程序的運(yùn)行效率幾乎沒(méi)有影響。哈希表的大小與AFL中的位圖相同。請(qǐng)注意，此方法僅用于計(jì)算路徑哈希，不影響 AFL 的原始邊緣哈希計(jì)算。

2.3、哪些h-path將被添加到種子隊(duì)列？

??為了進(jìn)一步減少添加到種子隊(duì)列的$h?path$的數(shù)量，設(shè)計(jì)了一種策略來(lái)確定是否向種子隊(duì)列添加$h?path$：

1. 效率是一個(gè)關(guān)鍵因素
2. $e?path$比$h?path$更重要
3. 應(yīng)該選擇變異后更有可能接觸到新邊緣的$h?path$

??正如以下算法所示，作者設(shè)計(jì)了一種快速過(guò)濾算法來(lái)滿(mǎn)足這些要求。

2.4、種子選擇算法

??在AFL的原始種子選擇算法中存在一個(gè)小問(wèn)題。它雖然確保$F$（受青睞的種子集）覆蓋所有探測(cè)到的邊，但它并不能確保在一個(gè)fuzzing測(cè)試循環(huán)中測(cè)試的受青睞的種子涵蓋所有已發(fā)現(xiàn)的邊，此問(wèn)題正如下面的算法所示。

??針對(duì)此問(wèn)題，作者提出了一個(gè)新的種子選擇算法，如下圖所示。它修復(fù)了上述提到的缺陷，確保在一個(gè)模糊測(cè)試周期中測(cè)試的受青睞的種子將覆蓋所有已發(fā)現(xiàn)的邊。

2.5、資源調(diào)度

??PathAFL根據(jù)路徑的權(quán)重實(shí)現(xiàn)新的資源調(diào)度，并將更多的資源分配給更高權(quán)重的路徑。具體來(lái)說(shuō)，它將所有路徑按權(quán)重劃分為六部分，每一部分都分配了不同的資源。

3、達(dá)到的效果

??作者使用IDA進(jìn)行靜態(tài)分析。編寫(xiě)IDAPython腳本來(lái)自動(dòng)分析程序結(jié)構(gòu)，獲得邊緣信息，并為目標(biāo)程序生成數(shù)據(jù)文件。該文件記錄所有邊緣信息，作為PathAFL的輸入，以計(jì)算路徑權(quán)重。下表展現(xiàn)了關(guān)于靜態(tài)分析的時(shí)間開(kāi)銷(xiāo)。

3.1、一個(gè)簡(jiǎn)單例子的結(jié)果（RQ1）

??此部分的實(shí)驗(yàn)用于回答RQ1，即“跟蹤執(zhí)行路徑對(duì)于fuzzing是否可行？”。作者以第1.3節(jié)中討論的例子作為測(cè)試用例，對(duì)其所有邊進(jìn)行了插裝，以在使用PathAFL進(jìn)行測(cè)試時(shí)計(jì)算路徑哈希。結(jié)果顯示在下表中。AFL和CollAFL-x在7天內(nèi)未能觸發(fā)崩潰，而PathAFL和PathAFL-np僅用了一個(gè)小時(shí)就觸發(fā)了。此外，PathAFL和PathAFL-np分別在一天內(nèi)觸發(fā)了6次和8次崩潰。

??這個(gè)實(shí)驗(yàn)表明，PathAFL能夠有效地識(shí)別$h?path$，并且使用$h?path$引導(dǎo)模糊測(cè)試是可行的。

3.2、代碼覆蓋率和崩潰測(cè)量（RQ2）

??此部分的實(shí)驗(yàn)用于回答RQ1，即“PathAFL的代碼覆蓋率有多好？”。在本次實(shí)驗(yàn)中，作者選擇了如下幾個(gè)流行的應(yīng)用程序進(jìn)行測(cè)試。

??下表顯示了四個(gè)模糊測(cè)試工具探索的路徑和邊的數(shù)量。

??以上實(shí)驗(yàn)表明，PathAFL和PathAFL-np探索的路徑數(shù)量幾乎相同，但PathAFL探索的邊的數(shù)量比PathAFL-np多。故認(rèn)為PathAFL更好，可能觸及更多的新代碼分支。
??下圖顯示了10個(gè)實(shí)驗(yàn)中不同fuzzer隨時(shí)間的增長(zhǎng)的代碼覆蓋率的增長(zhǎng)。

??這再次表明作者的解決方案是有效的。
??下表統(tǒng)計(jì)了觸發(fā)的唯一崩潰的平均數(shù)量。

??此結(jié)果表明PathAFL在找到程序中存在的不同崩潰方面表現(xiàn)出色。
??總之，PathAFL在路徑和邊緣發(fā)現(xiàn)方面優(yōu)于AFL和CollAFL-x。而且最好使用資源調(diào)度。這些實(shí)驗(yàn)證明，所提出的解決方案可以幫助提高路徑和邊緣覆蓋率，并引發(fā)更多的崩潰。

3.3、LAVA-M數(shù)據(jù)集（RQ3）的結(jié)果

??此部分的實(shí)驗(yàn)用于回答RQ1，即“PathAFL的錯(cuò)誤檢測(cè)能力有多好？”。作者在LAVA-M數(shù)據(jù)集上對(duì)AFL和PathAFL進(jìn)行了為期7天的評(píng)估。且對(duì)每個(gè)實(shí)驗(yàn)都進(jìn)行了五次，并對(duì)所有發(fā)現(xiàn)的bug進(jìn)行了計(jì)數(shù)。評(píng)估結(jié)果如下表所示。

??結(jié)果表明，與AFL相比，PathAFL發(fā)現(xiàn)了更多的錯(cuò)誤。具體來(lái)說(shuō)，PathAFL發(fā)現(xiàn)了AFL發(fā)現(xiàn)的所有錯(cuò)誤。此外，PathAFL發(fā)現(xiàn)了base64中注入的所有漏洞，甚至發(fā)現(xiàn)了LAVA-M的作者沒(méi)有列出的四個(gè)新漏洞。

3.4、發(fā)現(xiàn)現(xiàn)實(shí)世界中的漏洞（RQ3）

??作者選擇了binutils、libav和libtiff進(jìn)行實(shí)驗(yàn)，并使用PathAFL發(fā)現(xiàn)了許多嚴(yán)重的漏洞和幾個(gè)bug（如下表所示）。

??所有的錯(cuò)誤和漏洞以前都沒(méi)有報(bào)告，可能會(huì)帶來(lái)一些安全風(fēng)險(xiǎn)。作者聯(lián)系了這些工具的開(kāi)發(fā)人員，并提交了錯(cuò)誤詳細(xì)信息。

4、結(jié)論

??在本文中，作者輔助fuzzer進(jìn)行路徑覆蓋，討論了其中的一些挑戰(zhàn)，并最終實(shí)現(xiàn)了一個(gè)名為PathAFL的新fuzzing系統(tǒng)。它采用了粗粒度的路徑跟蹤和快速過(guò)濾算法，可以有效地選擇更高權(quán)重的$h?path$，大大增加了路徑覆蓋的數(shù)量。此外，作者還設(shè)計(jì)了一種基于路徑權(quán)重的種子選擇算法和資源調(diào)度。作者在幾個(gè)不同的實(shí)驗(yàn)中對(duì)其進(jìn)行了評(píng)估，結(jié)果證明 PathAFL 在改善邊緣覆蓋和發(fā)現(xiàn)更多唯一崩潰方面比AFL和CollAFL更為有效。在經(jīng)過(guò)充分測(cè)試的程序中，PathAFL 發(fā)現(xiàn)了8個(gè)新的安全漏洞，分配了6個(gè)CVE編號(hào)。

---

總結(jié)

??以上就是本篇論文閱讀筆記的全部?jī)?nèi)容了，讀完這篇論文后，相信各位讀者朋友也會(huì)認(rèn)為本篇論文寫(xiě)的相當(dāng)不錯(cuò)，當(dāng)然，有些地方筆者可能也理解不深，歡迎各位讀者朋友與我積極討論。后面如果有時(shí)間，我會(huì)分享閱讀本篇論文的心得體會(huì)！