[论文阅读] (03) 清华张超老师 - GreyOne: Discover Vulnerabilities with Data Flow Sensitive Fuzzing
Discover Vulnerabilities with Flow Sensitive Fuzzing
Chao Zhang
清華大學(xué)
2nd International Workshop on Cyber Security and Data Privacy
《秀璋帶你讀論文》系列主要是督促自己閱讀優(yōu)秀論文及聽取學(xué)術(shù)講座，并分享給大家，希望您喜歡。由于作者的英文水平和學(xué)術(shù)能力不高，需要不斷提升，所以還請大家批評指正，非常歡迎大家給我留言評論，學(xué)術(shù)路上期待與您前行，加油~
張超老師是我非常佩服的一位青年教師， 清華大學(xué)副教授（博導(dǎo)），藍(lán)蓮花戰(zhàn)隊教練，我也聽了好幾次他的講座，受益匪淺。他主要研究軟件和系統(tǒng)安全，尤其是智能攻防方向，在國際四大安全會議發(fā)表論文十余篇。在自動攻防研究方面，提出的漏洞挖掘方案發(fā)現(xiàn)300多個未知漏洞，多次參加DARPA CGC、微軟BlueHat、Defcon CTF防奪旗賽等比賽并獲獎。作者主要分享他的兩次報告，第一篇是學(xué)術(shù)論文相關(guān)的“數(shù)據(jù)流敏感的漏洞挖掘方法”，第二篇是安全攻防實戰(zhàn)相關(guān)的“智能軟件漏洞攻防”。這些大佬是真的值得我們?nèi)W(xué)習(xí)，獻(xiàn)上小弟的膝蓋~fighting！
PS：順便問一句，你們喜歡這種方式的分享嗎？
擔(dān)心效果不好，如果不好我就不分享和總結(jié)類似的會議知識了，歡迎評論給我留言。
文章目錄
- 一.傳統(tǒng)的漏洞挖掘方法
- 1.漏洞挖掘
- 2.Fuzzing和AFL
- 二.Improvements to Fuzzing
- 1.Seed Generation
- 2.Testing Environments
- 3.Seed Selection
- 4.Seed Mutation
- 5.Efficient Testing
- 6.Coverage Metrics
- 7.Security Tracking
- 三.超神的方法-GREYONE
- 1.背景知識
- 2.污點屬性和分支匹配度
- 3.實驗結(jié)果
- 四.總結(jié)
前文推薦：
[秀璋帶你讀論文] 拿什么來拯救我的拖延癥？初學(xué)者如何提升編程興趣及LATEX入門詳解
[娜璋帶你讀論文] (02) SP2019-Neural Cleanse: Identifying and Mitigating Backdoor Attacks in Neural Networks
[網(wǎng)絡(luò)安全自學(xué)篇] 八十八.基于機(jī)器學(xué)習(xí)的惡意代碼檢測技術(shù)詳解
[安全論文翻譯] Analysis of Location Data Leakage in the Internet Traffic of Android-based Mobile
一.傳統(tǒng)的漏洞挖掘方法
演講題目： 數(shù)據(jù)流敏感的漏洞挖掘方法
內(nèi)容摘要： 模糊測試近年來成為安全研究人員的必備的漏洞挖掘工具，是近年來漏洞披露數(shù)量爆發(fā)的重要推手。然而，模糊測試工具在種子生成、選擇、變異、測試、評估、反饋等多個環(huán)節(jié)都存在一定的盲目性和隨機(jī)性，其漏洞挖掘效率存在較大提升空間。我們通過分析經(jīng)典模糊測試工具AFL的實現(xiàn)原理，找到了若干個制約其效率的瓶頸所在，包括數(shù)據(jù)流不敏感等，并針對性地提出了改進(jìn)方案GreyOne（USENIX Sec’20）。本次報告將與大家探討這一方案。
1.漏洞挖掘
漏洞大家都很熟悉了，是各大安全問題的根源。如下圖所示的Stuxnet震網(wǎng)、WannaCry、心臟滴血等等。
我們在漏洞挖掘和攻防方面做了大量的研究，有人打的CTF，也有機(jī)器全自動的漏洞挖掘、攻擊防御、二進(jìn)制程序分析、CGC比賽等。下圖是Blue-Lotus（清華藍(lán)蓮花）戰(zhàn)隊這些年的成績。
我的研究主題是漏洞挖掘和攻擊防御，今天的分享主要是我們在 漏洞挖掘（Vulnerability Discovery） 方面最近的工作，它是關(guān)于Fuzzing的一個工作，Fuzzing目前可能是漏洞挖掘最主流的方法。
漏洞挖掘發(fā)展幾十年，前面有很多技術(shù)被提出來，大家最熟悉的應(yīng)該是代碼審計、逆向工程（無源碼），它們?nèi)匀皇瞧髽I(yè)發(fā)現(xiàn)漏洞的常用渠道；學(xué)術(shù)界提出的包括靜態(tài)分析、動態(tài)分析、污點分析、符號執(zhí)行等方法，這些技術(shù)或多或少都局限，沒有最近流行的Fuzzing技術(shù)有效。
- Code Review（10%）
- Static Analysis
- Dynamic Analysis
- Taint Analysis
- Symbolic Execution
- Model Checking
- Fuzzing（80%）
2.Fuzzing和AFL
Fuzzing也不是新技術(shù)，它是在90年的時候被提出來，已經(jīng)有30年歷史，但它真正大的發(fā)展是2013年以后，最近幾年有個大的發(fā)展。它的基本思路如下圖所示，它是一個動態(tài)測試的過程，需要想辦法生成一大堆輸入，扔給程序測試，如果測試過程中出現(xiàn)問題就可能有BUG，如果沒有問題就接著測試，和軟件工程中的測試流程類似。
- Goal：Finding PoC samples that prove vulnerabilities
- Solution：testing
整個過程的核心是怎樣有效地生成輸入去觸發(fā)Bugs，因為對于程序來說，它輸入空間是個無限的空間，能夠觸發(fā)漏洞是非常少的。那么，怎樣在無限空間中有效找到少量能觸發(fā)漏洞的輸入，這是它的核心問題。
90年左右提出Fuzzing的問題基本是偏隨機(jī)輸入的，后面又提出方法告訴輸入的格式，然后基于格式去生成，但相對來說它挖漏洞的效率仍然很低，讓人去寫這個輸入格式工程量也比較大。
2013年以后，有一個叫AFL的重要方案被提出，這個方案有一個很重要的算法就是遺傳算法，它把遺傳算法放進(jìn)來了。
- A better strategy: Genetic Algorithm
- Iterative testing,keep GOOD seeds, report bugs
我們剛才說到Fuzzing的核心是在無窮多個輸入空間中去找有限的輸入，去觸發(fā)漏洞，那怎么在無窮空間中去有限探索呢？它用到了遺傳算法。下圖中間的核心循環(huán)，通過一輪一輪的迭代測試，測試過程中它會把上一輪測試比較好的測試用例留下來，作為種子進(jìn)入下一輪，下一輪是在上一輪比較好的種子基礎(chǔ)上進(jìn)一步變異測試。它在無窮空間中探索時，不是盲目的去探索，而是在上一輪探索基礎(chǔ)上去找比較好的方向，接著再這個方向上往下探索。該方法還是比較有效的。
具體分析，每輪測試保留好的測試?yán)Ｄ敲?#xff0c;什么是好的測試?yán)?#xff1f;這里有一個進(jìn)化指標(biāo)，這個進(jìn)化指標(biāo)也非常重要。我們目標(biāo)是挖漏洞，很自然就有一個指標(biāo)是漏洞數(shù)量，但是用漏洞數(shù)量作為指標(biāo)來進(jìn)化的效果很差，因為漏洞是個非常稀疏的，你可能挖了幾個小時都沒挖到一個漏洞。這意味著沒有進(jìn)化的信號，整個算法效果就很差。
- 漏洞數(shù)量
2013年AFL工作使用的指標(biāo)是代碼覆蓋率，測試工程中去監(jiān)控程序的代碼覆蓋率情況，如果一個新的測試?yán)嵘舜a覆蓋率，就認(rèn)為它是好的種子就保留下來。通過這種方式就能不斷提升代碼覆蓋率。
- GOOD：coverage increases
- Bug：sanitizers
代碼覆蓋率與漏洞有一定相關(guān)性，我們知道要觸發(fā)漏洞的話肯定要走存在漏洞的那條路徑，去觸發(fā)代碼，如果沒走過那段代碼，那個漏洞肯定不會觸發(fā)。它們之間是有個關(guān)聯(lián)性的，我們通過這種遺傳算法不斷提高代碼覆蓋率，它就有一定概率去發(fā)現(xiàn)代碼中隱藏的漏洞，整體效果也不錯。
為了支持做覆蓋率跟蹤以及在測試過程中發(fā)現(xiàn)代碼漏洞是否被觸發(fā)，通常會對程序進(jìn)行插樁，做代碼覆蓋率收集和Security Sanitizers（安全檢測工具），插樁完成之后在測試過程中，程序會自動收集Coverage信息以及檢測是否觸發(fā)安全問題。
A pioneer：AFL
下圖是真正AFL的框架，真正的AFL會在過程中每一步都有一些策略，比如怎么選種子（Select Seed）、怎么變異（Mutate Seed）、變異后怎么測試（Test）、測試過程中怎么跟蹤覆蓋率（Coverage Tracking）、覆蓋率怎么過濾保留新的種子（Filter Seeds）等等。該算法提出來之后非常有效，改變了大家在這塊的研究。AFL的重要特點如下：
- Evolving：filter out only GOOD samples contributing to code coverage
遺傳算法是個進(jìn)化的特征。 - Scalable：mutation-based, few knowledge required
方案是可量化的，不需要知道目標(biāo)軟件太多的知識，給它一個軟件就能測。 - Fast：fork-server, persistent, parallel
測試過程非常快，一秒鐘平均能測上千個測試用例。 - Sensitive: support different sanitizers to catch security violations
捕獲漏洞能力比較強，可以支持不同的Sanitizers，也可以擴(kuò)展，比較有名的是谷歌寫的AddressSanitizer，常用安全防護(hù)和漏洞挖掘。這個非常重要，有時候在測試過程中觸發(fā)漏洞但程序并不一定會讓崩潰，一個好的Sanitizers能夠在程序未崩潰的情況下發(fā)現(xiàn)漏洞。
推薦資料：https://github.com/google/sanitizers
AFL（American Fuzzy Lop）是由安全研究員Micha? Zalewski（@lcamtuf）開發(fā)的一款基于覆蓋引導(dǎo)（Coverage-guided）的模糊測試工具，它通過記錄輸入樣本的代碼覆蓋率，從而調(diào)整輸入樣本以提高覆蓋率，增加發(fā)現(xiàn)漏洞的概率。其工作流程大致如下：
- ①從源碼編譯程序時進(jìn)行插樁，以記錄代碼覆蓋率（Code Coverage）；
- ②選擇一些輸入文件，作為初始測試集加入輸入隊列（queue）；
- ③將隊列中的文件按一定的策略進(jìn)行“突變”；
- ④如果經(jīng)過變異文件更新了覆蓋范圍，則將其保留添加到隊列中;
- ⑤上述過程會一直循環(huán)進(jìn)行，期間觸發(fā)了crash的文件會被記錄下來。
參考alphalab文章：AFL漏洞挖掘技術(shù)漫談（一）：用AFL開始你的第一次Fuzzing
二.Improvements to Fuzzing
所以，在整個流程中這些環(huán)節(jié)都可以去改進(jìn)。這些年四大安全會議關(guān)于Fuzzing的論文大概有60~70篇，數(shù)量非常大，我們簡單介紹下。
安全四大頂會：
- CCS（ACM Conference on Computer and Communications Security）
網(wǎng)址：https://www.sigsac.org/ccs.html - NDSS（Network and Distributed System Security Symposium）
網(wǎng)址：https://www.ndss-symposium.org/ - Oakland S&P（IEEE Symposium on Security & Privacy）
網(wǎng)址：https://www.ieee-security.org/TC/SP-Index.html - USENIX Security（USENIX Security Symposium）
網(wǎng)址：https://www.usenix.org/
1.Seed Generation
第一塊是初始種子，它對Fuzzing的效率還是有很大影響的。如果你不給初始種子，它也會去測試，但是其效率比較低，很多學(xué)者去研究如何給一個好的初始種子，讓Fuzzing更快地進(jìn)入狀態(tài)，更好地找到漏洞。
實踐中怎么找到初始種子呢？可以從網(wǎng)上去爬取一些PDF文件作為初始種子，或者從網(wǎng)上找一些歷史上的POC。而學(xué)術(shù)界的方法如下：
How to get/generate seeds?
- 第一種是借用AI的方法
基本思路是從程序的合法輸入，網(wǎng)上爬取樣本中學(xué)出一個模型，再用這個模型生成新的測試?yán)?#xff0c;這樣構(gòu)造的初始種子相對來說更好。典型論文方法包括Skyfire、Learn&Fuzz、GAN、Neuzz等。
- 第二種是通過符號執(zhí)行（Symbolic Execution）來輔助
這種輔助手段一般稱為混合Fuzzing，其基本思路的核心還是Fuzzing來做，但Fuzzing有些代碼過不去，比如一個復(fù)雜的數(shù)組檢查，Fuzzing很難通過。對于這些過不去的分支，Drillers就提出用符號執(zhí)行來輔助，遇到分支過不去的情況用符號執(zhí)行來求解，并生成新的種子再丟給Fuzzing去通過分支，這是當(dāng)時他們做CGC比賽的方案。符號執(zhí)行和Fuzzing混合確實能提升過不去的分支。最近幾年有進(jìn)一步改進(jìn)符號執(zhí)行和Fuzzing的經(jīng)典方法，比如QSYM、DigFuzz、HFL等。
- 第三種是基于靜態(tài)分析和動態(tài)分析的
還有一些是基于靜態(tài)分析、動態(tài)分析，以及去學(xué)習(xí)輸入的規(guī)范，通過程序分析的技術(shù)手段去分析程序接受什么樣的輸入，再去指導(dǎo)測試?yán)纳伞＝衲陱埨蠋熕麄冇幸黄槍ndroid服務(wù)的工作，也是這個思路，即FANS（USENIX Sec20）。
2.Testing Environments
上面介紹的是采用不同角度，有AI、符號執(zhí)行，傳統(tǒng)靜態(tài)分析、動態(tài)分析來輔助識別或者生成初始種子的。還有一部分是針對不同測試目標(biāo)的工作，包括針對二進(jìn)制程序的，針對內(nèi)核程序的，針對JAVA、IoT、SDN的，還有虛擬機(jī)、手機(jī)驅(qū)動、文件系統(tǒng)、數(shù)據(jù)庫、智能音響等等。
針對不同的目標(biāo)做Fuzzing，它其實會存在很大的差異。一個重要原因是這些目標(biāo)很難有個較好的動態(tài)測試環(huán)境，測試環(huán)境有個要求是盡量在測試過程中做一些跟蹤，而很多目標(biāo)可能不適合做跟蹤，所以需要解決這個問題。針對不同測試目標(biāo)也是有很多工作的。
How to test targets?
3.Seed Selection
在遺傳算法每輪的迭代中，它首先需要從現(xiàn)有的種子池（Seed Pool）中選擇種子，該步驟也是有一些策略的。因為一個種子池中可能積累了很多種子，通過歷史上不斷測試留下來的，但每一輪可能只選擇一個種子，而先選擇哪一個的效率也是不一樣的，雖然大家都是種子，但可能有些種子效率更好。
2016年發(fā)表在CCS上的AFLfast的策略是如果這個種子在之前測試中很少被選出來，就稱為cold，這樣的種子后面優(yōu)先被選出來，或者這個種子搜索的路徑在之前的測試中很少被測到，也會優(yōu)先選擇這個種子。還有其他的一些策略，比如VUzzer、AFLgo、QTEP等等，包括張老師他們2018年Oakland提出的CollAFL，這些策略其實沒有哪一個是絕對的最好，各有千秋。
How to select seed from the pool?
4.Seed Mutation
選好種子之后，接下來是做變異，在這個種子基礎(chǔ)上變異生成一堆測試用例，AFL的做法是隨機(jī)選擇一些字節(jié)，對其進(jìn)行增刪改，做一些操作，但這個隨機(jī)沒法保證質(zhì)量。這塊就有一些工作嘗試改進(jìn)。
How to generate/mutate new testcases?
- 第一種是偏AI的方法
比如2017、2018年有嘗試用AI來指導(dǎo)（LSTM、強化學(xué)習(xí)），去年張老師他們在USENIX Sec上有一篇Mopt，通過粒子群優(yōu)化算法來選擇最優(yōu)的變異策略。同時CCS上有一篇ILF也是通過AI方法，先用符號執(zhí)行去生成數(shù)據(jù)并作為訓(xùn)練數(shù)據(jù)，再通過AI模型來指導(dǎo)它變異，該工作適合于智能合約和區(qū)塊鏈上。
- 第二種偏程序分析的方法
這些方法是通過程序分析的方法，經(jīng)典的是2017年發(fā)表在NDSS的VUzzer，它通過污點分析來判斷應(yīng)該對哪些字節(jié)進(jìn)行變異，以及怎么變異。后面還有一些通過符號執(zhí)行、梯度下降，2019年Oakland人大一位老師的做法也非常有意思，它通過測試去觀測測試的表現(xiàn)，來推斷輸入字段的劃分及類型，基于字段類型來指導(dǎo)怎么變異。我們今天要分享的是USENIX SeC20的GreyOne，也是關(guān)于變異的工作。
5.Efficient Testing
編譯好之后，就是測試工作（Optimizations）。測試過程中，第一個很重要的問題是性能，測得非常快，漏洞挖掘工具也會很強。這里有一些并行化、硬件輔助的工作。
How to efficiently test target application?
6.Coverage Metrics
下面一類工作是測試過程中需要跟蹤代碼覆蓋率、安全等屬性，代碼覆蓋率相對來說工作比較少，我們2018年關(guān)注的是代碼覆蓋率中的碰撞問題，讓它更精確。今年有很多團(tuán)隊嘗試用別的、不同的Coverage來做指標(biāo)，這個代表性工作是2020年Oakland的IJON工作，非常有意思，包括我們團(tuán)隊也在嘗試各種想法，它實際上自定義了很多不同的Coverage指標(biāo)，比方說在走迷宮程序時，迷宮所在的位置作為指標(biāo)。如果大家搞Fuzzing，建議大家去看看。還有一些做定向Fuzzing的，不是探索所有代碼，而是優(yōu)先探索我們想探索的，比如某個點可能有漏洞，這類也是有個Coverage的，通常是距離，比如離目標(biāo)有多遠(yuǎn)。
A better/alternative coverage algorithm?
7.Security Tracking
還有一塊是Sanitizer，剛才提到谷歌公司的AddressSanitizer是一個經(jīng)典的工作。這部分和防護(hù)比較接近，去年也有Razar方法，引導(dǎo)它往race去發(fā)現(xiàn)特定的漏洞。
How to catch security violations during testing?
寫到這里，我們就把這些年Fuzzing的一些方法介紹完畢了！可能不是很全，但大部分的方法都囊括了。
三.超神的方法-GREYONE
注意，這部分內(nèi)容是結(jié)合張老師的分享以及作者的理解來敘述，所以和原文的框架有所差異。這里強烈推薦大家從下面的鏈接去下載原文進(jìn)行學(xué)習(xí)，看看大佬們的前沿工作。
1.背景知識
下面開始講解我們的工作，第一個工作是USENIX Security 2020的一篇文章，叫做《GREYONE：Data Flow Sensitive Fuzzing》，是一個數(shù)據(jù)流敏感工作。
- https://www.usenix.org/conference/usenixsecurity20/presentation/gan
- https://www.usenix.org/system/files/sec20spring_gan_prepub.pdf
- GREYONE Data Flow Sensitive Fuzzing
簡單介紹下背景知識，我們先看下圖所示的一個例子，這是經(jīng)典的magic number檢查。
- 第1個if：前面八個字節(jié)等于“MAGICHDR”
- 第2個if：后面八個字節(jié)必須等于算出來的校驗和
- 第3個if：判斷長度
- 第4個if：輸入數(shù)據(jù)做個變形
- 第5個if：包含一些更復(fù)雜的是隱式依賴，比如第15行var1變量，它是跟第14行的控制相關(guān)
- 第6個if：bug5隱性依賴于Input的20到24個字節(jié)
我們?nèi)巳タ催@些知識很容易理解，但是Fuzzing過程中，如果想觸發(fā)bug1，我們在變異時，其實是有一些知識可以獲取的。輸入前8個字節(jié)與“MAGICHDR”進(jìn)行比較，變異時是要對前8個字節(jié)進(jìn)行變異，而不是隨機(jī)變異，變異取什么值呢？我們應(yīng)該取“MAGICHDR”。接著校驗和（checksum）也類似，它會把輸入中的8個字節(jié)（8-16）與算出來的值某個校驗和進(jìn)行對比，我們就要對input[8:16]進(jìn)行變異，變異所取的值是計算出來的值。
- Where to mutate? input[0:8]
- How to mutate？MAGICHDR
- Seed prioritization：1 byte match vs 7 byte match
還有一點，比如“MAGICHDR”例子，只有全匹配上才能出發(fā)bug1，全部匹配上的概率還是比較低的，64個bit（2的64次方）。現(xiàn)在假設(shè)我們有兩個用例，它們分別與“MAGICHDR”有1個byte和7個byte匹配，但從代碼覆蓋率上來說，它們都是一樣的，都不滿足這個檢查，都會走這個flase的分支，但它們的測試效果或者對Fuzzing的作用一樣嗎？顯然不是，明顯7個byte匹配的測試?yán)Ч?#xff0c;因為下一次在7個byte基礎(chǔ)上可能再變異一個byte就匹配上了“MAGICHDR”。
所以說這兩個測試?yán)么a覆蓋率是一樣的，但是它的測試效果不一樣。這個例子說明：Data flow information is useful for fuzzing。因此張老師他們提出了一種新的數(shù)據(jù)流敏感模糊解Greyone。
2.污點屬性和分支匹配度
首先，data-flow features的類型是什么呢？
- Taint attributes（污點屬性）
輸入和變量之間的依賴性 - Branch value conformance（分支匹配度）
轉(zhuǎn)移條件操作數(shù)間的距離，提出了一個分支匹配度的計算公式。一致性越高，距離越近，我們就認(rèn)為它的匹配度越好。
基于上述觀測，我們提出了如下圖所示的模型，關(guān)注的是Taint部分，我們需要做數(shù)據(jù)流跟蹤來識別剛才提出的兩個特性。
此時遇到3個問題：
- 怎么去獲取數(shù)據(jù)流特性呢？
How to efficiently get data-flow features?——Traint attributes、branch value conformance - 如何利用數(shù)據(jù)流特性來指導(dǎo)變異？
How to utilize data-flow features to guide mutation? - 怎么去進(jìn)一步調(diào)整fuzzing進(jìn)化的方向？
How to utilize data-flow features to tune fuzzing direction?
接著我們先來回答這部分的問題。
(1) RQ1-1：Taint Attributes
Taint是非常經(jīng)典的技術(shù)，很多地方都有，比如Libdft、DFSan等。基本思路是逐條解釋指令，因為指令是有語義的，比如MOV移動EAX到EDX中去，它就會把EAX的污點屬性轉(zhuǎn)義到EDX污點屬性中去，所以當(dāng)它逐條解釋語義它就可以分析這個輸入的污點是怎么傳播到程序中的各個變量上去的，一條條指令來解釋。
但是這種做法很笨重，需要人去逐條寫這個語義，非常麻煩，這些工具一般都需要人來寫這個規(guī)則，很容易寫錯、寫漏。那么去年NDSS有一篇做自動的，去推演Taint inst的工作，自動推演Taint的規(guī)則。
Traditional dynamic taint analysis
- Libdft/DFScan…
- Propagate taint inst. by inst.
- Taint rules manually/automatically
- Under-taint and over-taint issues
但所有這些工作都有一個問題，存在嚴(yán)重的Under-taint和over-taint的問題。這兩類問題都很多，就會漏掉一些taint信息，或者造成錯誤地把一些不應(yīng)該是taint而識別為taint。時間關(guān)系不展開講解，不論是人工或機(jī)器來做都會遇到的問題，而且還比較嚴(yán)重。
我們提出了一個新的方案，叫fuzzing驅(qū)動污點推斷（Fuzzing-driven Taint Inference，FTI）。基本想法很簡單，我們要關(guān)注的不是一條條指令的傳播，我們關(guān)注的是宏觀的效果，比如輸入的哪幾個字節(jié)會影響我的某一個分支，分支這邊涉及到變量，我想關(guān)心的就是變量與輸入的哪個字節(jié)相關(guān)。通過做一個變化，觀察變量var的值是否保持不變，如果它的值發(fā)生了變化，我們就知道，這個var和變量S[i]（第i個字節(jié)）是相關(guān)的，換句話說，如果變量的值在輸入字節(jié)發(fā)生變化時發(fā)生變化，我們可以推斷前者受到了污染，并依賴于后者。所以，我們只需要對fuzzing做動態(tài)測試，調(diào)整輸入的某些字節(jié)，然后看程序中哪些變量發(fā)生了變化，發(fā)生變化的值就認(rèn)為它與輸入字節(jié)有關(guān)。
- Interference rule
v(var, S) ≠ v(var, S[i]) - Taint inference
Byte-level mutation：逐個字節(jié)變異
Branch variable monitoring：監(jiān)控變量是否發(fā)生變化
Deterministic fuzzing stage
由于AFL是可以逐個字節(jié)變異的，我們只需要在Fuzzing過程中增加個變量監(jiān)控即可。它的優(yōu)點包括：速度非常快，不需要人工寫傳播規(guī)則，沒有Over-taint問題，可能有少量的Under-taint問題，出現(xiàn)沒測試到的情況。
下圖發(fā)現(xiàn)我們的漏報其實很少，左邊這張圖藍(lán)色（最左邊）是我們發(fā)現(xiàn)的污點，深藍(lán)色（中間）是兩者都發(fā)現(xiàn)的污點，淺藍(lán)色（最右邊）是IBM提供的污點。我們是沒有誤報的，它們可能會有Over-Taint的問題。所以我們的識別效果更準(zhǔn)確，速度影響也非常小，只有25%的會overhead，對整體Fuzzing速度沒有影響。
(2) RQ1-2：Constraint Conformance
第二個是識別數(shù)據(jù)流特征——分支匹配度。分支的地方兩個變量有多少個匹配，通過程序插樁，就看分支在哪、有多少個bit相等，我們除了定義分支匹配度外，還進(jìn)一步擴(kuò)展了基本塊的匹配度，擴(kuò)展到路徑的匹配度。
(3) RQ2：taint-guided mutation
① 識別完Taint信息和分支匹配度信息之后，怎么去進(jìn)一步指導(dǎo)我們的mutation，怎么做變異呢？
前面其實已經(jīng)提到了怎么做編譯，比如Magic number、Checksum這些，直接拷貝這種。該編譯很簡單，通過Taint信息就知道要對哪里進(jìn)行變異，然后獲取的值是Magic number、Checksum，填進(jìn)去就好了。
How to mutate direct copies of input
- Direct copies
Magic number、Checksum… - Execute twice
First round：FTI taint analysis input offsets, expected value
Second round：Mutate and test
還有一些是間接拷貝，輸入的字節(jié)是通過一些運算之后來做檢測，這種在變異的時候不能確定它準(zhǔn)確的值，采用偏隨機(jī)的方法，通過變量相關(guān)的字節(jié)進(jìn)行隨機(jī)的變異。
How to mutate indirect copies of input
- Random bit flipping and arithmetic operations on each dependent byte
- Multiple dependent bytes could be mutated together
然后taint有個問題，可能會有少量的under-taint問題，所以在變異過程中也不完全依賴于指導(dǎo)，可能也對那些我們認(rèn)為不相關(guān)的字節(jié)也做一定小概率的編譯。
Mitigate the under-taint issue
- Randomly mutate their adjacent bytes with a small probability
② 接著我們需要確定對哪些字節(jié)變異？
我們有一個排序，目標(biāo)是探索更多的代碼，首先對沒有探索的分支做一個排序；然后這些分支與某些輸入字節(jié)相關(guān)，再對輸入字節(jié)做一個排序，然后優(yōu)先選某個字節(jié)。
- Explore the untouched neighbor branches along this path one by one
In descending order of branch weight - For specific untouched neighbor branch
Mutating its dependent input bytes one by one
In descending order of byte weight
③ 這些排序怎么計算呢？
我們有公式來計算，其實就是看輸入字節(jié)與這個分支之間的依賴關(guān)系，輸入字節(jié)會影響某些變量，有些變量會應(yīng)用到不同分支中去，有些分支被探索過（Explored），有些分支沒有（Unexplored）。所以先定義字節(jié)的權(quán)重，看這個直接會影響多少個沒有測試的分支，圖中所示，數(shù)量越高它的權(quán)重越大。
- Input -> Variables -> Branches
那么，分支怎么做排序呢？都是沒有探索過的分支。也是從這個圖上說，反過來，一個分支（Branch）會依賴若干個字節(jié)，這若干個字節(jié)權(quán)重加起來越高，這個Branch的權(quán)重也就越高。
(4) RQ3：Conformance-guided evolution
最后一部分是去調(diào)整進(jìn)化方向，通過分支匹配度，一個字節(jié)匹配和七個字節(jié)匹配的效果是完全不一樣的。
① 那么，怎么把這個增加進(jìn)去呢？
我們在原來代碼覆蓋率基礎(chǔ)上增加了一個新的指標(biāo)，即分支匹配度。原來大家是把這個分支，有好的代碼覆蓋率，就把它放到種子池中去，種子池是一個線性列表，現(xiàn)在把種子池修改，它還是個列表，但是每個節(jié)點不再是一個種子了，它每個節(jié)點可能是多個種子。
- Updating seed queues
the higher conformance, the better
together with AFL’s policy: converage-guided
② 怎么做的呢？
- 如果有新的代碼覆蓋率（New coverage），即有新的測試?yán)?#xff08;每個小圓圈就是測試?yán)?#xff09;，就會在種子池中新建一組節(jié)點，里面就是新的測試?yán)Ｈ缦聢D右邊黃色部分，種子編號41。
- 如果沒有新的代碼覆蓋率（Same coverage，higher path conformance），它的代碼覆蓋率與之前某組測試?yán)且粯拥?#xff0c;但是它的路徑匹配度更好，那我就取代了剛才的兩個測試?yán)Ｈ缦聢D左下角部分，種子編號21。
- 如果沒有新的代碼覆蓋率或更高的路徑匹配度（Same coverage, same path conformance, different branch conformance），路徑匹配度是由基本塊匹配度構(gòu)成的，但是基本塊匹配度或分支匹配度組合不太一樣，我們就往里面添加一個。如下圖所示的右下角部分，種子編號23。
最后我們的種子池就修改成如下圖所示，變成了二維的，后面取種子變異就從這個種子池中完成。該方法有很多好處，這里不詳細(xì)講解，具體如下圖所示：
3.實驗結(jié)果
接著我們看看實驗結(jié)果，我們和AFL、CollAFL、Angora進(jìn)行了對比，我們比它們中最好的代碼覆蓋率也提升了20%左右。
下圖是進(jìn)化曲線，代碼覆蓋率增長的曲線。
在挖漏洞這邊，我們評價有兩個指標(biāo)——Crashes和漏洞。Crashes和之前三個中最好的相比，提升了5倍，增長曲線也非常快。
挖漏洞方面（Vulnerabilities），我們比之前的方案都要多，多2倍的效果，最后申請了41個CVE。
這次分享基本把GreyOne介紹了一遍，其實我們在Fuzzing方面還有以下這幾個方面的工作，前面也提到過，推薦大家去閱讀這些文章。
四.總結(jié)
簡單做個總結(jié)，Fuzzing目前是最流行的漏洞挖掘方法，有很多的工作在研究。我們講解的GreyOne方法是根據(jù)數(shù)據(jù)流敏感的思路來做的，在Fuzzing中更精確地通過很多的數(shù)據(jù)檢查，該方法的亮點在于用了一個清亮的污點跟蹤機(jī)制，用污點信息來指導(dǎo)進(jìn)化，同時用分支匹配度來調(diào)整進(jìn)化方向。當(dāng)然，fuzzing這塊還有很多工作可以去做的。
- Fuzzing is the most popular vulnerability discovery solution
Coverage-guided fuzzing is popular - Data-flow sensitive solution Greyone
Infers taint attributes during fuzzing
Performs taint-guided mutation
Performs conformance-guided evolution - Many more topics to explore in fuzzing
問題：這里主要針對有源碼的挖掘嗎？這套方案和源碼有什么關(guān)聯(lián)呢？
回答： 有源碼的時候效果會更好，因為需要做污點分析、監(jiān)控變量的取值，然后來做程序插樁。當(dāng)然這些工作在二進(jìn)制中也可以做，其實反匯編都很難做種，更何況需要做插樁或其他的，可以做，但是效果會差一些，準(zhǔn)確性、包括提取的分支會少一些，我們的方案可以移植過去，但是目前沒有數(shù)據(jù)會說移植過去的效果會怎樣，相比其他二進(jìn)制方案會有提升，但效果不會很高。
問題：漏洞挖掘方案它挖掘的漏洞類型會不會偏向哪一類呢？比如哪一類較多或哪一類沒有效果。
回答： 現(xiàn)在Fuzzing方案基本挖的內(nèi)存破壞漏洞比較多，還有一些定制的適用于算法復(fù)雜度的漏洞，有一小部分是其他漏洞。它能挖什么類型漏洞，主要能力在于Sanitizer這部分，寫什么樣的檢測工具，如果不寫檢測工具，只能看程序是否崩潰。很多時候漏洞觸發(fā)后，它也不一定崩潰，所以大家會定制Sanitizer，比如BufferFlow監(jiān)控，定義規(guī)則出來，比如谷歌的AddressSanitizer，它的漏洞類型和我們檢測器有關(guān)。
問題：您挖出來的這些未知漏洞，怎么去驗證它是不是真實的漏洞呢？是通過手動的方式呢？還是自動化方式呢？
回答： 這是個很好的問題，目前我們Paper中基本是人工來做，AFL提供了一些過濾功能，把顯然是重復(fù)的這些Crashes去重了，剩下的還有一定數(shù)量，幾十個、上百個，通常會人工寫一些腳本工具來判斷和驗證。學(xué)術(shù)界現(xiàn)在也是有Paper在研究這些，怎么做自動的Crashes分析和歸類。
問題：論文假設(shè)分支匹配度越高，輸入的種子越優(yōu)，這個假設(shè)怎么處理函數(shù)變化，如Hash變化再input呢？一個好的Hash函數(shù)它的輸出應(yīng)該是均勻的，這時的假設(shè)感覺就不太需要了，請問下這是怎么處理的。
回答： 我們現(xiàn)在沒有處理這種特殊情況，其實遇到這種情況現(xiàn)在的方案可能大家都做得不好，這是一個很經(jīng)典的例子。比如前面說的間接數(shù)據(jù)拷貝，做了一個變換再來判斷，我們的方案效果也不好。我們的方法識別出來它和18到20字節(jié)相關(guān)，重點變異這幾個字節(jié)，此時分支匹配度策略可能就不是很有效，比如foo可能是Hash變換函數(shù)后均勻分布了，確實是存在問題的。
作者感受：學(xué)術(shù)或許是需要天賦的，這些大佬真值得我們學(xué)習(xí)，同時自己會繼續(xù)努力的，爭取靠后天努力來彌補這些鴻溝，更重要的是享受這種奮斗的過程，加油！
最近又認(rèn)識了很多朋友和博友，非常榮幸。有問問題的，有考研交流的，有一起讀博鼓勵的，也有想考博去大學(xué)教書的，還有技術(shù)交流以及交朋友的。雖未謀面，共同前行。盡管自己非常忙碌，但還是很愿意去解答博友的問題，去幫助更多的陌生人。有時候你的一句鼓勵，一個回答，可能就是別人前行的動力，何樂而不為。雖然自己的技術(shù)和科研都很菜，安全也非常難，但還是得苦心智，勞筋骨，餓體膚。感恩親人的支持，也享受這個奮斗的過程。月是故鄉(xiāng)圓，佳節(jié)倍思親，加油，晚安娜
(By:Eastmount 2020-08-06 晚上9點 http://blog.csdn.net/eastmount/ )
總結(jié)
以上是生活随笔為你收集整理的[论文阅读] (03) 清华张超老师 - GreyOne: Discover Vulnerabilities with Data Flow Sensitive Fuzzing的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [安全攻防进阶篇] 六.逆向分析之Oll
- 下一篇： [安全攻防进阶篇] 七.恶意样本检测之编