限制引導的定向模糊測試：CDGF

CDGF

• 一、背景介紹
• • 1.1 DGF
  • 1.2 CDGF
• 二、DGF
• • 2.1 DGF中距離
  • 2.2 DGF的應用
  • 2.3 DGF的局限性
  • 2.4 改進要求
• 三、CDGF
• • 3.1 概括
  • 3.2 constraint定義
  • 3.3 distance定義
  • • 3.3.1 target site的distance
    • 3.3.2 data condition的distance
    • 3.3.3 某基本塊單個constraint的distance
    • 3.3.4 某基本塊constraint sequence的總distance
    • 3.3.5 seed的distance
  • 3.4 Constraint生成
• 四、CAFL
• • 4.1種子部分
  • 4.2實驗
• 五、總結

一、背景介紹

1.1 DGF

DGF作用

　集中測試某些特定位置的代碼：target site

　應用：

　　①開發人員從第三方擷取崩潰報告，重制崩潰

　　②針對某個更新檔，生成對應修補位置處的PoC

局限性

　1、target sites之間沒有關聯，不考慮順序依賴性

　2、未考慮target crash所需的資料條件，單純以距離target sites遠近來進行種子排程

1.2 CDGF

CDGF

　在DGF的基礎上加了一些的constraint，并且按照滿足constraint的權重去排列seed

　權重：

　　seed通過的constraint越多，距離constraint越近，權重越大

constraint組成

　多個target site和n個data condition

　當指定多個constraint時，seed要按照排列順序去滿足

自動生成constraint

　作者設計了根據額外資訊源自動生成constraints的算法

　額外資訊源

　　①記憶體錯誤檢測器的偵測的記憶體錯誤

　　②更新檔的更改日志

　注：該算法支援7種crash和4種changelog自動生成constraint

constraint生成方法

　UAF：

　　首先生成free處的constraint，再生成crash處的constraint（先驅動seed到free，再到crash）

　緩存區溢出：

　　constraint驅動seed到緩存區的邊界，增加溢出的機會

　更新檔更改日志：

　　constraint轉換seed，來符合更新檔更改日志中訓示的有缺陷的條件

主要貢獻

　1、提出了CDGF，在DFG基礎上按順序排列target site和constraint

　2、使用額外資訊源，自動生成constraints

　3、基于CDGF理念設計了CAFL，用實驗展現了該方法的優秀

二、DGF

2.1 DGF中距離

調和平均值

　使用調和平均值來計算某點到某點的距離

　比如論文中的這個例子

　論文中兩個target分别為d和f，然後a到d與f的最短距離都是3，那麼a的權重是1/(1/3+1/3)=3/2

　加入seed執行的路徑是abef，那麼距離就是計算調和平均數(3/2+1+1+0)/4=0.875

　效果就是路徑越長，計算出來的距離越短，比如路徑abcdabef的距離是0.85，比路徑abef的距離0.875還要短

　缺點是如果路徑中包含的的target site少，反而會增加路徑長度，如路徑abcabef的距離為0.971

2.2 DGF的應用

針對于任何可以精确定義target site的用例中

1、靜态分析驗證

靜态分析誤報率很高，可以用DGF将目标crash設定為target site來主動驗證

2、崩潰再現

重制來自使用者或開發者的崩潰報告，崩潰報告中往往有PoC、address、location，但是往往一個PoC無法驗證該crash是否已經修複，可以用DGF來驗證

3、生成PoC

攻擊者往往攻擊的是還沒有修複漏洞的過時系統，可以使用更新檔中描述的address、data、rule并通過DGF來生成PoC，比如崩潰再現中就可以生成PoC

2.3 DGF的局限性

由于以下兩個原因，DGF往往會長時間的探索target site而沒有進展

1、target site之間互相獨立

2、沒有data condition

例：target site互相獨立

例：沒有data condition

2.4 改進要求

1、排列好的target site

因為大部分的target site都有前提條件，要将seed驅動到前提條件位置

2、data condition

大部分crash都有資料條件，是以也需要将seed驅動到前提資料條件

三、CDGF

3.1 概括

每個constraint都有target site以及在target site需要滿足的data condition

改進：賦予seed更短距離的條件

1、選擇的seed滿足的constraint更多

2、如果constraint未滿足，選擇更加滿足該constraint的seed

3.2 constraint定義

組成：target site和data condition

滿足限制：到達target site并滿足data condition

生成constraint的方法：

1、捕獲變量

到達targert site就捕獲該處使用的變量，捕獲什麼變量取決于在該處的操作，比如“取消引用數組”捕獲“引用位址”、“配置設定數組位址”捕獲“數組大小和目前位置等”

2、data condition

data condition是一個布爾表達式，由捕獲的變量組成，data condition可以用自己所屬constraint中的變量或者之前constraint的變量

3、排序

多個限制需要按照指定的順序來滿足

3.3 distance定義

3.3.1 target site的distance

基本塊距離

d(B1,B2)為B1和B2之間的距離

Bs是B1的後續基本塊(如果B1有調用指令的話，調用指令的基本塊可以是Bs)

target site距離

定義為target site與目前基本塊的基本塊距離(上面使用的基本塊距離算法)

3.3.2 data condition的distance

1、單個data condition

注：如果表達式中有整數是未定義的，那麼距離為無窮

這串公式中，Q是data condition，等号左邊整體為第n個資料塊在Q下的距離，min指的是取第n個基本塊之前計算出的最小距離

特殊條件：當data condition為assert時，成功為0，失敗為無窮

2、多個data condition

多個data condition時，distance表示了seed滿足所有data condition的程度，滿足的越多，distance越短

如果滿足的data condition同樣多，選序列中未被滿足的data condition更靠前的

ρ是第一個未被滿足的data condition下标

Nunsat=N(Q)-ρ，指的是未被滿足的data condition數量

Cdata是單個data condition的最大距離，作者設定為int的最大值(2的32次方)，這樣可以表示4位元組整數内的任何值

3.3.3 某基本塊單個constraint的distance

即到target site的distance和data condition的distance之和

3.3.4 某基本塊constraint sequence的總distance

沒滿足的constraint距離設為最大(2的35次方,可容納8個data condition)，其餘的正常計算

3.3.5 seed的distance

即取seed的基本塊路徑上distance最小值

3.4 Constraint生成

基本方法：根據給定的資訊源，找到合适的target site和data condition來填寫預先設定的constraint模闆

可生成來源：①來自記憶體錯誤檢測器的崩潰記錄(crash dump)②更新檔更改日志(patch changelog)

模闆：

1、nT

nT類型即多個target site，适合需要按照順尋到達多個target site但不需要data condition的crash類型

例：Use-after-free、double-free、use-of-uninitialized-value

2、2T+D

兩個target site加data condition

例：heap-buffer-overflow、stack-buffer-overflow

3、1T+D

一個target site加data condition

例：divide-by-zero、assertion-failure

PoC

對于漏洞這種，作者設計了算法來提取更新檔中的資訊填充到1T+D類模闆中，分為以下四類分别操作

C1：異常檢查類，target site為異常檢查點，data condition為異常條件，關鍵字throw、error

C2：分支跳轉類，target site為分支跳轉點，data condition為“目前跳轉條件!=原跳轉條件”

C3：變量更換類，target site為被替換的變量，data condition為“目前變量!=打更新檔前變量”

C4：不适用上述，不符合上述條件，則data condition為空

四、CAFL

作者根據CDGF的思想設計了CAFL，并由些許改進

4.1種子部分

為了防止局部最優，通俗講就是這個seed并不适合變異下去，但是這個seed現在的distance還很小，優先級會很高，是以對種子權重進行了改動。

通過以上公式，seed如果模糊時間過長、長時間停留在某個distance沒有改變，種子的權重就會降低

4.2實驗

實驗對象：AFLGo與CAFL

1、LAVA-1

選取了LAVA-1中18個崩潰來比較雙方

可以看到這裡CAFL在加入了data condition後時間大大縮短，證明了data condition的作用

2、Crash Reproduction

選了47個真實程式來測試，選取了其中的nT和1T+D類型的bug，并且使用了1T和nT以及nT+D來實驗CAFL的效果

可以看出CAFL在整體性能上要好于AFLGo，但是在部分情況下加入了data condition反而效率下降，說明了data condition有時候反而會起到誤導作用

3、PoC Generation

通過3.4裡提到的從更新檔中提取target site和data condition的規則來生成constraint，并由此生成PoC

效果要好于AFLGo

五、總結

總的來說就是一種改進distance計算方法，可進行對比的論文不多，效果還行