此文將介紹一篇 Xu 等人發表於 CCS 2020 的論文 FreeDom: Engineering a State-of-the-Art DOM Fuzzer。
DOM engine 是當代 Browser 中很根本的一環，並常常成為 attack surface，因此目前已經有不少針對 DOM engine 的 fuzzer（以下稱為 DOM fuzzer）。簡而言之，目前許多 DOM fuzzer 會基於 context-free grammars 透過不斷 mutate 新的 input，然後丟進 DOM engine 看會不會 crash，不過 Xu 等人觀察到這樣的設計並沒有把 data dependency 考慮進去，也就是說，HTML 彼此的相依性。另外，通常 fuzzing 會以盡可能增加覆蓋律為依歸（也就是 coverage-guided mutation），不過這個目標在 DOM 的情境下是否合理也是一個值得被討論的問題。Xu 等人設計了一套 context-aware 的 DOM fuzzer，同時採用 generative 和 coverage-guided mode，並找到許多現存 DOM fuzzer 無法找到的 bug。
背景
DOM
Browser 的 input 通常是一個 HTML 檔案，這個檔案會遵循 DOM (Document Object Model) 的規範。一般來說，可以分為 CSS rules, JavaScript (Event handlers), DOM Tree。DOM Tree 定義整個文件的基本結構，DOM Tree 上的每一個 element 都可以有 attribute（key-value pair）。CSS rules 則是由一些 CSS selector（控制哪些 element 要被這個 rule 影響）以及 CSS properties（控制如何裝飾）。JavaScript，額，就 JavaScript（？），其中在這篇 paper 會處理到的是 Event handlers，DOM 規範中定義了當使用者（或 JavaScript）以某些特定方式與 DOM element 互動時，就會觸發 event handler，例如當使用者在 <input> 輸入文字時會觸發 onchange。
如果 DOM engine 有 bug，則有機會透過惡意建構的 HTML document 來觸發這個 bug 讓瀏覽器有預期之外的行為，甚至觸發 RCE。
過去方法的問題
為了解決這些問題，就出現了 DOM fuzzer，其中最知名的 DOM fuzzer 可能是 Google 的 Domato。早期的 DOM fuzzer 通常是用 JavaScript 隨機在網頁上亂試，這個作法的問題也很顯然，效率很不好，而且有時會產出無法 reproduce 的 bug。因此後來開始改用靜態生成 input (HTML document) 然後嘗試用 browser 打開看會不會 crash，生成方法則通常是人工打造的 static rules 或 grammar。
不過使用 static context-free grammars 並沒有辦法把 HTML documents 之間的 data dependency 考慮進去，如此則在某些多個 element 之間有相依性的狀況下（例如 class name）會產出有 semantic error 的 output，以致 fuzzer 在巨大的 state space 中迷航。
稍微嚴謹一點地來討論何謂 data dependency 以及沒有考慮 data dependency 會如何影響 fuzzing 結果。Xu 等人整理出了四種 context-free 會導致的問題。
第一種是 CSS selectors。CSS selectors 必須要對應到 id、class 或 tag 才會生效，否則這些 rules 就不會被套用。Domato 的作法是有常數個針對 HTML 與 SVG elements 的 CSS rules，然後會預先定義一些 class name，等 HTML / SVG elements 被 generate 出來之後再 assign 這些 class name，藉此產出能有所對應的 CSS rules。不過這個做法的問題在於，tag 或 class 的數量在文件實際上被生產出來之前都是未知的， 所以可能有些 class name 被 generate 出來之後根本沒被用到，於是即便這些 CSS rules 有問題也會被忽略。
第二種是 CSS property。有些 CSS property 需要對應到既有的 element，不過 Domato 並沒有把這些情境考慮進去。舉例來說，CSS 的 clip-path property 只能用在 SVG 的 <clipPath> 上，可是 Domato 卻會把這個 property 也 assign 給其他 element。
第三種是 Attribute name values。有些元素屬性的名字可能被其他元素所引用，例如 SVG 的 <animate> 使用 attributeName 來決定動畫要作用在其 parent element 的哪個 attribute name。可是 Domato 卻會隨機 assign attributeName，以致多數產出來的 SVG <animate> 都是壞掉的。
最後則是 Attribute values。有些元素的屬性必須能夠連結到另一個元素，例如 <img> 的 usemap 要連結到 <map>、<input> 的 form 要連結到 <form>。如果不把這些關聯考慮進去，則會產生沒有作用的 attribute。
總結來說，使用 context-free grammar 的問題在它沒辦法掌握這些 data 之間的相依性，以致產生許多 semantic error。
另外一個問題是，既有 DOM fuzzer 都是 generation-based 的，也就是不斷生產新的測資而不做 mutation。如此設計的原因是 DOM fuzzer 都是產生 textual document，以致在做 mutation 時可以活動的範圍很小，因為在文字檔上亂做 mutation 會壞掉。因此現有 DOM fuzzer 難以達成 coverage-guided mutation。例如 Domato 的 mutation 就只能 append 更多資料到既有 document，而不像是 general-purpose 的 fuzzer 可以有 flipping 或 splicing 的可能性。如果要建構出一個能夠做 mutation 的 DOM fuzzer，則應該被儲存的狀態是 mutable structure 而非一大堆文字檔。
最後則是，既有 DOM fuzzer 實在太慢了。一般來說 broswer 除非是 crash 否則不會自己停止，所以很難知道現在 browser 到底是 render 完然後沒問題，還是還正在 render，於是既有 DOM fuzzer 的作法就是等個 10 秒之類的，如果都沒 crash 就當作測試通過，即便可能 0.5 秒就 render 完了，因為我們無從得知，所以就浪費掉 9.5 秒在乾等。
FreeDom 的基本結構與運作方法
上圖描述了 FreeDom 的整體架構。簡單來說，會有數個 FreeDom 的 fuzzing engine instance 構成一個 cluster，然後有個 central server 負責管理所有 fuzzing data（稱為 FD-IR，大概就是 HTML document structure 跟 context information）。
Generation-based fuzzing 就是不斷產生新的文件放進 FD-IR，然後轉成 HTML 並用 browser 打開，如果 browser crash 了會回報給 central server。Coverage-guided fuzzing 模式下，central server 不只會蒐集 crash report，還會維護一個 queue 紀錄著所有發現新的 code path（也就是增加 coverage）的測資，以及整體的 coverage map，然後每個 fuzzing engine instance 會向 central server 查詢被置於 queue 的一個 FD-IR 文件，從這個文件 mutate 出新的測資，或是和別的文件合併成新的測資，能增加整體 coverage 的新測資會被回傳給 central server 並放進 queue 作為之後 mutate / merge 的資料來源。
Context-aware Document Representation
所以我們現在可以來處理如何有效表達一個 document 以讓這樣的表達可以被 mutate。
首先是，該如何儲存 context。FD-IR 維護了一個樹狀結構來儲存 global 的 context，例如（最初的）DOM tree 中的 tag、class、id、attribute 等，以及所有可用的 token（例如 class names, CSS counter names, CSS keyframes names）。這些 global context 將用於解決前述的四種 context-free 的問題。除了 global context，另一個需要考慮的 local context。FD-IR 會儲存每一個 JavaScript function 的 local context，藉此產生正確的 DOM API calls，如此則可以達成 API mutation 與 function merging。既然有 FD-IR 儲存 context，則可以用 context-aware 的方式做 generation / mutation。
接著我們需要一個方式來表述整個 document。FD-IR 使用 Value class 來表達 HTML document 的不同物件，例如 DOM tree 中的 elements、CSS rules 等。一個 FD-IR 中的文件會有許多 Value 的實體（instance）。Value class 有 3 個重要的 method：
generate()：定義如何在給定 global 和 local context 的情況下隨機生產新的資料。mutate()：定義如何在給定 global 和 local context 的情況下做 mutation。lower()：定義如何把 Value 物件轉成 plaintext。
如此設計的好處是，如果有人想要為 FreeDom 增加新功能，只要實做對應的 Value 物件即可。
FD-IR 可以使用 Value 紀錄下述資訊。
- DOM tree：FD-IR 使用一個樹狀結構，root 對應到
<body>，並記錄每個 element 的 type, id, child nodes, attributes。 - CSS rules：FD-IR 使用一個陣列記錄所有 CSS rules，其中每個 rule 記錄 CSS selector 和 CSS properties。
- Event handlers：FD-IR 使用一個陣列記錄所有 event handler，其中每個 event handler 包含多個 DOM API calls 和 local context。如果這些 API calls 會回傳物件，也同樣會被記錄下來，放進 local context。
Context-aware DOM Fuzzing - Generation
在完成 document 的表示方法後，下一個需要處理的問題是，所以 fuzzing 到底要怎麼做。我們先討論 generation-based fuzzing 如何運作。
第一個被生成的會是 DOM tree，因為 DOM tree 決定了 CSS rules 和 event handler 有哪些 node 可以控制。DOM tree 的生成可以由下述三個方法隨機操作而成：
- 插入 element：隨機在 DOM tree 中選個 element，並插入一個 child。所生成的 child 會根據其 parent element 的 context 決定。
- 新增 attribute：隨機在一個 element 新增一個尚不存在的 attribute。此處需要借助 global context 來選擇恰當的 attribute。如果有新增 token（例如 class name 等），也會被放到 global context。
- 新增 text node：選擇一個可以插入文字的 element，並在這個 element 插入文字作為其 child。
接下來則是生成 CSS rules，同樣是在把 global context 納入考量下，不斷建立新的 CSS rule，並呼叫下述兩個 sub-routine：新增 CSS selector、新增 CSS property。
在完成上述階段後，接著會嘗試把所有 DOM element 的 event handler 都填滿。選擇 handler 的程序是，fuzzer 會先查詢 global 與 local context，確認哪些 DOM API call 是合理的，並任選一個插入點，生成 API call（會考慮插入點之前的變數作為 argument）並置入，如果這個 API call 會回傳東西，則會把它放進新的 local context。
Context-aware DOM Fuzzing - Mutation
接著是介紹在 mutation-based fuzzing 中，該怎麼做 mutation。一樣的，我們可以粗略地把它分成三個部份。
首先在 DOM tree mutation 的部份，除了前面的三種 generation 方法以外（畢竟新增資料也算是 mutation），額外定義三種 mutation 方法：
- 變異一個 attribute value：任選一個現存的 attribute，並根據其 Value 實體做變異。
- 取代一個 attribute：任選一個 element，隨機移除一個 attribute，然後新增一個 attribute（同 generation）。不過 FreeDom 不會移除有被其他 element 引用到的 attribute（例如
<animate>的attributeName）。 - 變更 text node：任選一個 element 然後變更它的 text node。
在 CSS rules，也一樣除了前述的 generation 方法外，額外定義三種變異方法：取代一個 CSS rule、變異 CSS selector、變異 CSS property。
Event handler 的變異則有三種方法：
- 插入新的 API call：隨機選擇一行 JS code，然後插入 DOM API call，且只有插入點之上的變數有可能成為 API call 的 argument。
- 取代一個 API call：隨機選擇一個既有 API call，換成另一個 API call。不過此處不會取代有回傳值的 API call。
- 變異一個 API call：隨機選擇一個既有 API call，重新生成它的 argument。
除了 document 的三個部份可以做變異以外，也可以合併兩個 document。CSS rules 和 event handlers 基本上就是都 union 起來，然後移除那些有衝突的或是 reference 壞掉的。比較麻煩的是 DOM tree，其合併方法大致可以這樣表達：假設現在有 tree A 與 B 要 merge，有個 tree B 的節點 $N_b$，在 tree A 找一個節點 $N_t$ 符合 1. 與 $N_b$ 有相同 tag 且 2. 深度小於等於 $N_b$ 原本的深度，然後把 $N_b$ （連同所有 child）都複製到 $N_t$，attribute 也全都複製過去；如果在 tree A 找不到符合的元素，則任選一個 tree A 中的元素，把 $N_b$ 全部複製過去。這麼做的好處在於可以維持 DOM tree hierarchies 以及 API calls，又不會造成 semantic error。
Mutation-based DOM Fuzzing
在了解 mutation 如何運作後，需要再稍微補述一下實際上 Mutation-based DOM Fuzzing 的運作方法。一開始 fuzzer 有兩種選擇，可以用 generation-based 的方法建立一個新的 document，或是從現存的 FD-IR 資料集（corpus）中拿一個 document 出來做 mutation。接著對於每一份 document，fuzzer 會嘗試 50 次 mutation，每一次都從上述的 mutation 方法中任選一個出來使用。如果都沒有成功增加 coverage，則會和另一個 document merge 起來再嘗試 5 次。上述過程中有增加 coverage 的 document 會被放回 corpus 供之後 mutation / merge 使用。
至於以往 fuzzing 太慢的問題，他們的解法也還蠻簡單的，就在 Webkit 中插入一小段 code 檢查，如果 main frame 發出 onload，會再等 500ms 後終止。
FreeDom 的效果
他們宣稱用 FreeDom 去掃 Safari、Firefox、Chrome 並找到 24 個 bug，拿到 10 個 CVE。
雖然原文給出蠻多分析的，不過感覺全部翻譯過來也沒什麼意義，所以我就簡單講一個比較有趣與出乎意料的發現。他們發現 coverage-guided mutation 的方法雖然 coverage 比 generation-based 方法還要好，但卻觸發更少 crash。究其原因，他們推測是因為 coverage-guided mutation 只顧著增加 code coverage 而非去嘗試既有 code block 有沒有 bug，而 generation-based 因為其超大的文件與豐富的 semantics，雖然是盲目亂試，但會不斷以各種方式造訪各個深入的 code block，所以能找到更多 bug。
後記
以上大概就是 FreeDom 的簡介，不得不說這種解決 DOM fuzzing 困境的方法蠻令人驚豔的。總之大概就先這樣，如果有興趣的話，他們有把 source code 放出來，也許哪天有空再去看看吧。