子樹類型敏感的JavaScript引擎灰盒測試技術(shù)

王聰沖,甘水滔,王曉鋒

1江南大學(xué)人工智能與計算機學(xué)院 無錫 中國 214122 2數(shù)字工程與先進計算國家重點實驗室 無錫 中國214083

1 介紹

JavaScript引擎是瀏覽器的必要組成部分,其安全性一直備受關(guān)注[1],由于其代碼量巨大、邏輯極其復(fù)雜,導(dǎo)致漏洞挖掘技術(shù)發(fā)展一直無法滿足JavaScript引擎的安全測試需求,針對JavaScript引擎漏洞攻擊事件層出不窮。通過對 CVE漏洞庫統(tǒng)計,暴露在 Jerryscript[2]、ChakraCore[3]、SpiderMonkey[4]、JavaScriptCore[5]、V8[6]其高危漏洞條目超過 450條,其中ChakraCore和V8的數(shù)量分別超過150條和200條。并且在2020年上半年暴露的高危漏洞數(shù)量已超過2019年全年暴露的總數(shù)。具體如圖1所示。通過進一步對過去JavaScript引擎漏洞暴露來源調(diào)查,模糊測試是發(fā)現(xiàn)JavaScript引擎漏洞的主流自動化檢測方法[7]。

圖1 主流JavaScript引擎的CVE漏洞暴露統(tǒng)計情況Figure 1 CVE vulnerability exposure statistics for mainstream JavaScript engines

模糊測試[8]通過不斷自動構(gòu)造隨機非預(yù)期的輸入數(shù)據(jù)給目標(biāo)軟件,實時監(jiān)視目標(biāo)軟件運行異常信號,能有效發(fā)現(xiàn)軟件存在的脆弱性[9]。模糊測試主要分為黑盒和灰盒模型,在2014年以前基本以黑盒模型為主,黑盒模型不具備程序信息反饋能力,具有運行速度快,能適應(yīng)復(fù)雜規(guī)模代碼軟件等優(yōu)點,但測試效率一直受限于隨機性過大、代碼覆蓋能力弱等問題[10]。從 2015年開始,自經(jīng)典灰盒測試系統(tǒng)AFL[11]問世以來,通過路徑覆蓋信息實時反饋,在文檔解析、圖片解析、音頻解析等文件型輸入的軟件目標(biāo)測試過程中達到較高代碼覆蓋率,發(fā)現(xiàn)大量未公開漏洞,并實現(xiàn)了向協(xié)議型[12]和內(nèi)核型[13]對象應(yīng)用擴展?；液心Ｐ鸵阎鸩匠蔀樽钣行У闹髁髂：郎y試手段,并且和 libFuzzer[14]、honggfuzz[15]等灰盒工具集成在谷歌的可持續(xù)開源模糊測試服務(wù)OSS-fuzz[16]中,截止到2020年6月,OSS-fuzz已經(jīng)在300個開源項目中發(fā)現(xiàn)了上萬個可觸發(fā)漏洞[17]。

模糊測試在JavaScript引擎的應(yīng)用方法同樣劃分為黑盒和灰盒模型兩類,其難點在于如何高效的生成并測試高質(zhì)量的JavaScript代碼測試用例。不同于文檔解析等文件型測試?yán)?JavaScript代碼需要遵從嚴(yán)格的語法規(guī)范。JavaScript引擎在解析 JavaScript代碼過程中,一旦遇見不符合JavaScript語法規(guī)則代碼,就會終止對整個測試?yán)慕馕?從而無法觸及JavaScript引擎的關(guān)鍵功能模塊,難以達到理想的測試效果。然而,如果直接采用 AFL等灰盒工具的字節(jié)或比特級隨機變異策略,極易破壞JavaScript代碼的合法性,導(dǎo)致JavaScript引擎測試過程中效率極其低下。因此,JavaScript引擎模糊測試在過去以基于代碼生成的黑盒模型為主,代表性工具有JSfunfuzz[18]、LangFuzz[19]、CodeAlchemist[20]。JSfunfuzz 通過JavaScript代碼語法模板生成測試用例,容易產(chǎn)生合法的JavaScript代碼,但需要花費大量的人力構(gòu)建語法模板,而且容易漏掉有價值的語法模式。LangFuzz通過對已有合法JavaScript代碼進行解析,轉(zhuǎn)換為抽象語法樹形式,將樣本拆分成子樹代碼片段放入代碼池中,并不斷使用代碼池中的子樹替代當(dāng)前測試用例的非終止節(jié)點來構(gòu)建新的測試用例,這種方式極大提升了測試?yán)詣由赡芰?但仍然容易產(chǎn)生非法的代碼,CodeAlchemist進一步引入控制流和數(shù)據(jù)流分析,定位和緩解未定義變量問題,進一步提升了代碼生成的正確性。但總體來說,黑盒模型難以擺脫執(zhí)行速度慢和代碼覆蓋能力弱等缺點。

為了彌補JavaScript引擎黑盒模型的不足,軟工頂級會議工作Superion[21]構(gòu)建了基于JavaScript代碼子樹變異的灰盒模型,在 AFL模型中增加了子樹變異階段,以子樹替代的方式去對種子變異,一定程度降低了AFL的JavaScript代碼生成錯誤概率,同等測試環(huán)境下,其代碼覆蓋和漏洞發(fā)現(xiàn)能力明顯優(yōu)于黑盒模型。然而,Superion在變異階段對子樹類型并不敏感,這種盲目的子樹替換策略導(dǎo)致生成的代碼出現(xiàn)嚴(yán)重的類型錯誤和語法錯誤。

基于現(xiàn)有JavaScript引擎灰盒模型的不足,本文提出了一種基于子樹類型敏感的JavaScript引擎灰盒測試技術(shù),并且實現(xiàn)了灰盒測試系統(tǒng)ILS。ILS在路徑反饋的模糊測試框架基礎(chǔ)上[22],通過對 JavaScript代碼進行精準(zhǔn)語法分析,對子樹集合進行類型識別和分類,并且在變異階段構(gòu)建了子樹類型敏感的變異策略,使用同類型子樹進行覆蓋變異,不僅大幅提升了測試種子的有效率,而且?guī)砹烁叩拇a覆蓋能力和漏洞發(fā)現(xiàn)能力。本文挑選了Jerryscript、ChakraCore和JavaScriptCore三個常用JavaScript引擎作為測試對象,通過對 ILS和 CodeAlchemist、Superion等工具進行24 h性能測試對比,實驗表明:在保持灰盒模型執(zhí)行性能優(yōu)勢的情況下,錯誤率比Superion降低了36%,比CodeAlchemist降低了21%。在代碼行覆蓋率上,ILS相比Superion提升了72%,相比CodeAlchemist提升48%; 在函數(shù)覆蓋率上,ILS相比 Superion提升 80%,相比 CodeAlchemist提升50%。在漏洞發(fā)現(xiàn)數(shù)量上,ILS相比Superion提升了100%。最后,ILS在這三個JavaScript引擎上總共發(fā)現(xiàn)了 26個未知 Bug,并均得到了廠商的確認(rèn)和修復(fù)。

本文的貢獻總結(jié)如下:

1) 面向 JavaScript引擎對象,提出了一種子樹類型敏感的灰盒測試模型,并實現(xiàn)了相應(yīng)原型系統(tǒng)ILS。

2) 與經(jīng)典黑盒和灰盒測試工具相比,ILS能顯著降低JavaScript代碼測試用例的錯誤率,并且能大幅提高JavaScript引擎的代碼覆蓋能力。

2 背景與相關(guān)工作

本節(jié)先對 JavaScript引擎的基本工作原理進行描述,然后對 JavaScript引擎漏洞挖掘方法相關(guān)工作進行總結(jié),最后進一步說明本文方法和傳統(tǒng)方法的差異。

2.1 JavaScript引擎工作原理

JavaScript引擎是瀏覽器重要組成部分,是根據(jù) ECMAScript[23]定義的語言標(biāo)準(zhǔn)來動態(tài)執(zhí)行JavaScript字符串的重要程序。JavaScript引擎具有代碼量大,工作原理和邏輯結(jié)構(gòu)復(fù)雜等特點。JavaScript引擎動態(tài)解析JavaScript代碼過程可以分為語法檢查階段和運行階段,語法檢查階段包括詞法分析和語法分析,運行階段包括預(yù)解析和實際執(zhí)行。其具體工作流程如圖2所示: JavaScript引擎首先對 JavaScript代碼進行語法分析得到抽象語法樹(Abstract Syntax Tree,AST),然后進一步解析得到字節(jié)碼(bytecode),在生成字節(jié)碼的同時,優(yōu)化編譯器生成高度優(yōu)化的機器代碼,生成的機器代碼最后替換原來的字節(jié)碼。JavaScript引擎在優(yōu)化代碼的時候會使用未優(yōu)化的字節(jié)碼進行工作,有效提高了JavaScript引擎性能。

圖2 JavaScript引擎工作流程Figure 2 JavaScript engine workflow

在JavaScript解析過程中,一旦遇到錯誤后面的代碼就無法執(zhí)行。在ECMAScript標(biāo)準(zhǔn)中定義了5種運行時錯誤: 語法錯誤(SyntaxError)、范圍錯誤(RangeError)、引用錯誤(ReferenceError)、類型錯誤(TypeError)和URI錯誤(URIError)。如圖3所示: 第1行中,var后面沒有申明變量,直接進行賦值操作,不符合語法規(guī)則,就會拋出語法錯誤; 第2行中,一旦變量數(shù)值超出有效范圍,便會拋出范圍錯誤; 第 3行中,一旦引用一個不存在的變量時,便會拋出引用錯誤; 第4行中,當(dāng)值的類型或參數(shù)不是預(yù)期類型時,便會拋出類型錯誤; 第5行中,使用全局URI處理函數(shù)遇見不正確參數(shù)時,便會拋出URI錯誤。由于URI錯誤很少在JavaScript解析過程中出現(xiàn),因此本文只考慮前4種錯誤類型。

圖3 JavaScript引擎解析代碼過程中常見的運行時錯誤類型Figure 3 Common runtime errors in the process of JavaScript engine parsing code

2.2 JavaScript引擎漏洞挖掘相關(guān)工作

經(jīng)典程序分析方法符號執(zhí)行[24-27]和污點分析[28-31]需要對測試軟件的指令進行逐條解析,分析速度慢,當(dāng)處理復(fù)雜代碼對象JavaScript引擎,符號執(zhí)行極其容易受限于路徑爆炸和復(fù)雜約束不可解問題,污點分析極易遭受內(nèi)存爆炸、過度污染和欠污染問題[32],難以在JavaScript引擎分析中產(chǎn)生作用,在過去鮮有針對JavaScript引擎的符號執(zhí)行和污點分析工作。另外,經(jīng)典靜態(tài)分析工具 Coverity[33]、Klockwork[34]、Fortify[35]只對程序語言敏感,因此也能適用于JavaScript引擎分析,但虛報率高,需要大量人力去驗證靜態(tài)報告的真實性。針對JavaScript引擎適配和優(yōu)化的靜態(tài)分析工作[36-38]更多關(guān)注如何降低JavaScript引擎運行開銷。

相比之下,模糊測試具有速度快、能適應(yīng)于復(fù)雜代碼對象等優(yōu)勢,具備直接發(fā)現(xiàn)可觸發(fā)漏洞的能力。因此,本文在相關(guān)工作部分主要關(guān)注模糊測試方法,從測試?yán)煞椒ㄉ峡?模糊測試大體可分為基于變異的模糊測試方法和基于生成的模糊測試方法,以下分別針對JavaScript引擎對這兩類相關(guān)工作進行歸納。

2.2.1 基于生成的模糊測試方法

基于生成的模糊測試方法借助手工構(gòu)建的輸入語法模型生成有效的輸入數(shù)據(jù),在一個理想的輸入語法模型支持下,才能測試重要功能模塊。在JavaScript引擎模糊測試應(yīng)用上,基于生成的模糊測試技術(shù)一直是發(fā)展的重點,主要發(fā)展路線可概括為以下三點: 1)不斷提升語法模型的自動化生成能力;2)不斷豐富生成的 JavaScript代碼模式; 3)不斷消減JavaScript代碼的錯誤率。

在代碼自動生成能力提升方面,早期的代表性工具有 Peach[39],在應(yīng)用到 JavaScript引擎測試上,需要為每個對象創(chuàng)建模板文件,需要劃分好隨機字段和確定字段,這將消耗大量的人力和時間成本。JSfunfuzz基于JavaScript語法模板,根據(jù)公開漏洞樣本中學(xué)習(xí)已有特征生成測試用例,只能適應(yīng)SpiderMonkey解析引擎,擴展性能力差。CodeAlchemist、DIE[40]等方法通過對初始代碼樣本構(gòu)建語法特征抽象模型,盡量保留有價值的控制流和數(shù)據(jù)流特征,在該基礎(chǔ)上構(gòu)建變異策略生成新的代碼樣本; Skyfire[41]、Montage[42]等方法進一步提升了代碼生成的自動化能力,在已有訓(xùn)練代碼樣本基礎(chǔ)上,采用學(xué)習(xí)的方式生成新的代碼樣本; 以上幾種方法對初始代碼樣本極其敏感,人力成本主要體現(xiàn)在初始代碼樣本篩選上,在實際應(yīng)用過程中,這些模型更多借助標(biāo)準(zhǔn)測試集和公開漏洞觸發(fā)樣本,最后均達到了較為理想的代碼生成效果。

在 JavaScript代碼語法模式生成能力方面,Peach、JSfunfuzz主要依賴已有語法模板,不容易推導(dǎo)新的語法模式。Skyfire利用帶概率的上下文敏感語法(PCSG)從大量樣本中學(xué)習(xí)語法和語義規(guī)則,在代碼生成過程中優(yōu)先選擇低概率的語義產(chǎn)生規(guī)則以生成分布合理的測試用例。CodeAlchemist會按照J(rèn)avaScript語句的粒度分解種子文件,針對每個塊語句生成多種變體提升代碼塊的豐富性,通過對多個代碼塊組合產(chǎn)生嵌套循環(huán)等結(jié)構(gòu)。Montage從Test262[43]數(shù)據(jù)集中收集了超過3萬個JavaScript代碼樣本,通過對代碼樣本中變量和函數(shù)等標(biāo)識符重新命名和子樹分片,形成 LSTM 模型的初始訓(xùn)練數(shù)據(jù),能有效學(xué)習(xí)出JavaScript代碼中的控制流和數(shù)據(jù)流依賴關(guān)系,從而推導(dǎo)出傳統(tǒng)模型能力之外的語法模式,該系統(tǒng)經(jīng)過一個半月的測試,共發(fā)現(xiàn)了 34個未知Bug。DIE以公開漏洞庫可觸發(fā)漏洞樣本為基礎(chǔ),識別并保留其中隱式的循環(huán)、特定跳轉(zhuǎn)結(jié)構(gòu)信息以及抽象語法樹類型信息,這些特征的保留有助于模糊測試階段集中在容易引發(fā)脆弱性的功能模塊(JIT優(yōu)化模塊)上進行,最后發(fā)現(xiàn)了48個未知Bug。

在JavaScript代碼錯誤率消減方面,JSfunfuzz在已有種子模板基礎(chǔ)上,結(jié)合實現(xiàn)預(yù)先準(zhǔn)備好的函數(shù)、對象、操作符等JavaScript代碼特征庫,隨機填充可寫字段,生成可用測試?yán)?由于缺乏各語句和語句間的合法性檢查,這種方式會帶來較嚴(yán)重的語法錯誤、引用錯誤和類型錯誤。LangFuzz在生成代碼的過程中,用當(dāng)前已有的變量去替代生成的代碼片段中未知變量,但無法避免變量在使用后才聲明,而且會增加該變量對象的重復(fù)使用概率,從而導(dǎo)致大量的引用錯誤。Skyfile在生成測試用例的過程中,也沒有考慮變量定義、使用等情況,同樣容易造成運行時錯誤。針對這一問題,CodeAlchemist提出使用數(shù)據(jù)流分析技術(shù)確定未定義變量和已定義變量,并結(jié)合運行時插樁技術(shù)探測已執(zhí)行變量的類型。CodeAlchemist在 JavaScript代碼生成過程中,不斷向代碼尾部擴展代碼片段,每次擴展代碼片段都會確保其中的變量在之前已經(jīng)被定義并且具備正確的類型,CodeAlchemist的優(yōu)化方法能有效降低LangFuzz方法中存在的錯誤率,相比 JSfunfuzz,能生成超出 5倍以上的有效測試?yán)ontage采用LSTM 模型推導(dǎo)不同代碼片段之間的關(guān)聯(lián)關(guān)系,能有效學(xué)習(xí)出類似變量定義和使用的先后次序等信息,有效降低非學(xué)習(xí)代碼生成策略存在的引用錯誤率。DIE通過保留的結(jié)構(gòu)化語義和類型信息,能有效提升變異的準(zhǔn)確性,大幅增加了種子的有效率,相比CodeAlchemist,可以降低一半的代碼錯誤率。

2.2.2 基于變異的模糊測試方法

基于變異的模糊測試方法[44-48]通過對已有的測試?yán)M行隨機變異產(chǎn)生新的測試?yán)?可以不依賴輸入語法模型,正由于其模型簡單易用,對人工經(jīng)驗依賴小,相比基于生成的模糊測試方法而言,在非結(jié)構(gòu)化語法輸入對象中應(yīng)用尤為廣泛[49-51]。但對于JavaScript代碼等結(jié)構(gòu)化語法輸入,變異策略需要考慮結(jié)構(gòu)化語法特征,不然會引發(fā)嚴(yán)重的錯誤率。在JavaScript引擎模糊測試應(yīng)用上,基于變異的模糊測試技術(shù)發(fā)展歷程可概括為: 1)從黑盒模型逐步轉(zhuǎn)向帶路徑覆蓋信息反饋的灰盒模型; 2)從隨機變異策略逐步發(fā)展為JavaScript代碼語法語義敏感的變異策略。

IFuzzer[52]為針對JavaScript引擎的黑盒模型,首先把JavaScript代碼樣本轉(zhuǎn)換為樹的形式,再采用遺傳算法對測試樣本進行選擇、交叉和變異,選擇階段主要參考適應(yīng)度函數(shù)值大小對代碼樣本進行優(yōu)先選擇,并對代碼中子樹節(jié)點進行交叉變異生成新的測試?yán)?該方法和LangFuzz相比,發(fā)現(xiàn)了SpiderMonkey上 LangFuzz之外的 16個未知 Bug。Fuzzilli[53]會把JavaScript代碼樣本轉(zhuǎn)換為中間代碼,中間代碼的每條指令由輸入變量、操作碼以及輸出變量構(gòu)成,在中間代碼上進行變異不僅有助于繼承已有控制流和數(shù)據(jù)流特征,還能降低代碼錯誤率。不同于AFL,Fuzzilli在測試過程中忽略了邊的循環(huán)次數(shù),這樣容易丟失覆蓋JIT優(yōu)化功能模塊的高價值測試?yán)?。近幾年業(yè)界在JavaScript引擎模糊測試的變異策略上增加了子樹分析,以子樹為變異單位進行變異操作,如 Montage、CodeAlchemist、Nautilus、Superion。其中,Superion充分發(fā)揮AFL的優(yōu)勢,在其基礎(chǔ)上添加子樹變異階段,和AFL、JSfunfuzz對比,大幅提升JavaScript引擎對象上的代碼覆蓋能力和漏洞發(fā)現(xiàn)能力。但以上工作普遍沒有對子樹進行類型分析,對子樹類型的不敏感會極大削弱變異策略的種子生成效率。

2.3 本文方法與已有方法區(qū)別

根據(jù)以上相關(guān)工作分析可知,子樹變異和路徑覆蓋反饋能力是當(dāng)前多個JavaScript引擎模糊測試的重要方法特征,但這些工作普遍缺乏對子樹的類型分析,容易導(dǎo)致嚴(yán)重的 JavaScript代碼錯誤率,從而丟失一些子樹類型敏感的脆弱路徑。本文根據(jù)當(dāng)前工作的不足,構(gòu)建了一個具備子樹敏感變異能力和路徑覆蓋反饋能力的灰盒測試系統(tǒng)ILS。表1更清晰展示 ILS和現(xiàn)有工作的方法差異,主要從是否具備路徑反饋能力、是否考慮JavaScript語法結(jié)構(gòu)特征、是否采用子樹覆蓋變異、是否考慮同類型子樹覆蓋操作、是否開放工具源碼、是否自動化程度較高這幾個方面進行比較。

表1 ILS與現(xiàn)有相關(guān)工作的方法差異Table 1 The difference between ILS and existing JavaScript engine fuzzers

為了更直觀地展示 ILS在漏洞檢測能力上的提升,圖4和圖5給出了具體案例分析。如圖4,Jerryscript引擎暴露的 CVE-2018-11418和 CVE-2018-11419兩個緩存區(qū)溢出漏洞,二者的觸發(fā)漏洞樣本僅體現(xiàn)在RegExp函數(shù)中的參數(shù)有所不同,如果對CVE-2018-11418的漏洞觸發(fā)樣本中的參數(shù)部分進行變異就能快速的觸發(fā)漏洞CVE-2018-11419。在后續(xù)的實際測試中,ILS通過同類型子樹覆蓋,提取CVE-2018-11418中的子樹信息,發(fā)現(xiàn)如圖5的兩個未知緩存區(qū)溢出漏洞bug-3870和bug-3871?？梢园l(fā)現(xiàn),這兩個新漏洞樣本只替換了CVE-2018-11418樣本中RegExp函數(shù)的參數(shù),該參數(shù)內(nèi)容通過語法樹解析得到的是同一種子樹類型。

圖4 已知的Jerryscript漏洞Figure 4 Existing Jerryscript vulnerabilities

圖5 ILS新發(fā)現(xiàn)的漏洞Figure 5 New bugs found by ILS

3 ILS系統(tǒng)設(shè)計與實現(xiàn)

3.1 整體工作流程

本文所提出的ILS方法在AFL基礎(chǔ)上進行擴展,更改了AFL的變異策略。ILS使用一種基于子樹類型敏感的JavaScript引擎灰盒測試方法,降低了AFL在生成JavaScript代碼時的錯誤概率,并具有更高的代碼覆蓋能力和漏洞發(fā)現(xiàn)能力。

AFL是谷歌開發(fā)的標(biāo)桿性灰盒測試系統(tǒng),它的工作流程如圖6中的Execution所示,可以分為兩步:對目標(biāo)程序進行插樁和對已插樁的程序進行模糊測試。在插樁階段,AFL對目標(biāo)程序編譯時,在每個基本塊插入一段代碼,用來記錄當(dāng)前基本塊和上一個基本塊的信息,主要代碼如下:

1 cur_location = ;

2 shared_mem[cur_location ^ prev_location]++;

3 prev_location = cur_location >> 1;

cur_location的值是隨機產(chǎn)生的,用來標(biāo)記當(dāng)前基本塊,shared_mem數(shù)組記錄上一個基本塊和當(dāng)前基本塊這條邊的命中次數(shù),如果命中次數(shù)的分類發(fā)生改變,則認(rèn)為產(chǎn)生了新的覆蓋率,prev_location表示上一個基本塊的標(biāo)記值,右移一位是為了區(qū)分基本塊的執(zhí)行順序。插樁完成后,AFL對已插樁的目標(biāo)程序進行模糊測試,可以分為如下5個步驟:

1) 從輸入隊列(包括初始種子和產(chǎn)生新路徑的測試用例)中挑選出一個種子;

2) 保證覆蓋率不變的情況下減小種子的長度;

3) 對種子進行變異生成新的測試用例;

4) 執(zhí)行新的測試用例,并監(jiān)控目標(biāo)程序執(zhí)行狀態(tài);

5) 根據(jù)目標(biāo)程序執(zhí)行結(jié)果更新輸入隊列,然后轉(zhuǎn)到步驟1。

通過不斷循環(huán)上述5個步驟,AFL持續(xù)對目標(biāo)程序進行測試,如果在步驟4中目標(biāo)程序發(fā)生崩潰,則記錄崩潰信息,并保存產(chǎn)生唯一崩潰的測試用例。

ILS的整體工作流程如圖6所示,可以分為初始種子預(yù)處理和運行兩部分,圖中藍色框部分是 ILS在AFL基礎(chǔ)上增加的工作。ILS首先在初始種子預(yù)處理階段通過相關(guān)語法分析工具對初始種子進行語法分析生成抽象語法樹,然后對得到的抽象語法樹進行類型識別和分類構(gòu)建相同類型子樹池,最后在變異階段對測試輸入增加語法分析,從同類型子樹池中隨機挑選出子樹進行覆蓋變異。下面,本文詳細(xì)討論ILS方法的實現(xiàn)細(xì)節(jié)。

圖6 ILS工作流程Figure 6 The workflow of ILS

3.2 初始種子預(yù)處理

ILS對初始種子進行語法分析得到抽象語法樹,在語法樹層次對子樹進行類型識別,并按類型分類構(gòu)建子樹池,詳細(xì)內(nèi)容如算法1所示。算法輸入為初始種子seeds和相關(guān)語法G。依次從seeds中選擇一個seed進行解析,首先根據(jù)語法G將測試輸入in解析成抽象語法樹AST(第4行),解析過程中如果出現(xiàn)錯誤,則說明測試輸入in是和語法無關(guān)的,將其舍棄(第 5~7行)。如果成功解析得到抽象語法樹seed_ast,則依次訪問語法樹的每個節(jié)點,獲取節(jié)點的類型和內(nèi)容,并保存到typetree數(shù)據(jù)集合中(第8 ~12行),typetree是一個map容器,它的key為子樹的類型,value是一個set容器,保存子樹的內(nèi)容。對所有的初始種子解析完成后,可以得到所有子樹類型和子樹內(nèi)容集合typetree。根據(jù)typetree集合中每個類型的名字tree.id在數(shù)據(jù)庫中創(chuàng)建對應(yīng)的表,并在表中插入該類型的所有子樹tree[id]構(gòu)建同類型子樹池(第 14~17 行)。

算法1.初始種子預(yù)處理輸入: seeds: 初始種子,G: 相關(guān)語法1: type = ?2: typetree[id][text]= //id is the type name,?text is the set of subtree’s contexts 3: foreach seed in seeds do 4: parse seed into AST seed_ast according to G

5: if there are any parsing errors then 6: return 7: endif 8: ctx = VISIT(seed_ast) // ctx is the visiting node according to G 9: while ctx do 10: typetree[TYPEID(ctx)]= typetree[TYPEID(ctx)]∪ {GETTEXT(ctx)}11: VISITCHILDREN(ctx)12: endwhile 13: endfor 14: foreach tree in typetree do 15: CREATETABLE(tree.id)16: INSERTTABLE(tree[id])17: endfor

3.3 同類型子樹變異

根據(jù)3.2節(jié)中得到的同類型子樹池,更改AFL的變異策略,使用同類型子樹覆蓋變異生成新的測試用例進行模糊測試。算法2介紹了ILS同類型子樹變異過程,算法輸入為測試輸入in,相關(guān)語法G和同類型子樹池 typetree,輸出為新生成的測試用例集合T。首先使用語法G對測試輸入in進行解析,解析過程和算法1解析相同(第3~6行)。解析完成后,依次訪問抽象語法樹的每個節(jié)點,獲取節(jié)點的類型和內(nèi)容,并保存到 subtree數(shù)據(jù)集合中,此步驟和算法 1中訪問語法樹相同(第7 ~ 11行)。獲取語法樹所有節(jié)點類型和內(nèi)容信息后,對語法樹in_ast進行替換變異,依次選擇子樹類型集合tree[id],并把in_ast中tree[id]類型的每個子樹s隨機替換為子樹池typetree[id]中同一類型的子樹typetree[id][random],生成新的測試用例ret,并保存到集合T中(第12~20行)。最后返回測試用例集合T(第21行)。

參考其他相關(guān)工作中對單個測試用例變異的次數(shù),本文選擇單個測試用例最大變異次數(shù)為10000。通過 10000除以這個測試用例中的子樹類型數(shù)目,再除以該類型子樹個數(shù)得到每個子樹的平均變異次數(shù)(第 14行),這樣保證測試用例中每個子樹都能被替換,并且保證每個子樹類型的總替換次數(shù)相同。

算法2.同類型子樹變異輸入: in: 測試輸入,G: 相關(guān)語法,typetree[id][text]: 同類型子樹池輸出: T: 新生成的的測試用例集合1: T= ?2: subtree[id][interval]= ? //id is the type

name,interval is the set of subtree’s location 3: parse in into AST in_ast according to G 4: if there are any parsing errors then 5: return 6: endif 7: ctx = VISIT(in_ast) // ctx is the visiting node according to G 8: while ctx do 9: subtree[TYPEID(ctx)]= subtree[TYPEID(ctx)]∪ { GETTEXT (ctx)}10: VISITCHILDREN(ctx)11: endwhile 12: foreach tree in subtree do 13: foreach s in tree[id]do 14: count = 10000/subtree.size()/tree[id].size()15: foreach i in count do 16: ret = replace s in in_ast’s copy with typetree[id][random()]17: T = T ∪ {ret}18: endfor 19: endfor 20: endfor 21: return T

以下本文用一個例子詳細(xì)介紹ILS的工作流程。使用圖7a作為算法1中的初始種子,圖7b作為算法2中的測試輸入。圖7a經(jīng)過語法解析得到圖8所示語法樹,其中每一個非葉子節(jié)點和它的所有孩子節(jié)點表示一顆子樹,該非葉子節(jié)點的類型表示了這顆子樹的類型。從 program根節(jié)點開始訪問該語法樹,到葉子節(jié)點結(jié)束,訪問結(jié)束可以得到所有子樹類型和子樹內(nèi)容集合構(gòu)建子樹池,如表2所示,Id表示子樹的類型,Text表示子樹的內(nèi)容。

圖7 輸入種子和測試用例Figure 7 The original seed and test input

圖8 抽象語法樹ASTFigure 8 Abstract Syntax Tree

從表2中可以看到,在不同的類型中,可能它們的子樹是相同的,如圖4紅色框部分的子樹 a(),它的類型有 FunctionBody、ExpressionSequence、ArgumentsExpression 3種。這增加了子樹類型的豐富性,在 ILS子樹變異過程中可以更有效的生成新的測試用例。

表2 圖7a通過語法分析得到的類型和內(nèi)容Table 2 The type and context obtained through syntax analysis from figure 7a

在同類型子樹替換變異階段,對圖7b通過語法分析得到表3。依次選擇表3中的Id的每個子樹替換為表2中相同Id的子樹,可以得到3個新的測試用例,如下所示:在語法解析過程中還能得到 Program、SourceElements、Statement等類型的子樹,第一個類型表示整顆語法樹,進行整個語法樹替換變異是沒有意義的,第二、三個類型表示的是這個子樹的源元素和狀態(tài),在整個語法樹中會多次出現(xiàn),但是并沒有實際意義,所以刪除這些無用的類型,只保留具有一定意義的子樹類型,如表2中一共得到10種不同有意義的類型。

表3 圖7b通過語法分析得到的類型和內(nèi)容Table 3 The type and context obtained through syntax analysis from figure 7b

和ILS相比,Superion的子樹替換策略是無類型的,這樣在替換的時候會造成很多錯誤,如圖7b中的數(shù)字1被圖7a中的a()替換,生成var a = a(),會造成TypeError。但是ILS同類型子樹替換策略就會減少這類問題,Literal類型的數(shù)字1只能被表2中同類型的true子樹替換,生成新的測試用例var a = true,可以順利被解析引擎運行。

3.4 實現(xiàn)細(xì)節(jié)

本文在AFL基礎(chǔ)上,使用C/C++語言實現(xiàn)子樹類型敏感的灰盒模糊測試系統(tǒng) ILS。該系統(tǒng)使用ANTLR 4[54]作為語法分析工具對初始種子進行詞法分析和語法分析,獲取初始種子的類型和子樹構(gòu)建同類型子樹池,在子樹變異階段,使用ANTLR 4對測試輸入進行詞法分析和語法分析,隨機從子樹池中挑選同類型的子樹替換測試輸入中的每個子樹生成新的測試用例。

該系統(tǒng)充分利用了 AFL的優(yōu)勢,能夠?qū)δ繕?biāo)進行快速測試,并通過覆蓋率反饋,提高對目標(biāo)的代碼覆蓋率,增加發(fā)現(xiàn)漏洞的概率。而且該系統(tǒng)容易擴展,擴展相關(guān)的語法可以對其他結(jié)構(gòu)化語法輸入對象(如XML解析器)進行測試。

4 實驗與測試分析

4.1 實驗設(shè)置

為了驗證 ILS的有效性,本文將此模型與Superion和CodeAlchemist進行實驗對比,在表1所列出的開源工具中,Superion是基于子樹變異的模糊測試方法中的典型工具,在相關(guān)JavaScript引擎中發(fā)現(xiàn)了23個未知的Bug,CodeAlchemist是基于生成的模糊測試方法中的典型工具,在相關(guān)JavaScript引擎中發(fā)現(xiàn)了11個未知的Bug。本文與這兩個工具進行實驗對比,可以體現(xiàn)出ILS方法的先進性。

本文分別從漏洞發(fā)現(xiàn)能力、代碼覆蓋能力、測試?yán)行?、?zhí)行速度4個方面進行性能對比: 漏洞發(fā)現(xiàn)能力最能體現(xiàn)出工具的有效性; 代碼覆蓋能力是衡量測試結(jié)果好壞的基本標(biāo)準(zhǔn),能夠整體上體現(xiàn)出模糊測試工具的效果; 生成測試用例有效性對于JavaScript引擎的模糊測試來說尤其重要,一般隨機變異產(chǎn)生的測試用例都不能被JavaScript引擎解析運行; 執(zhí)行速度是模糊測試工具中重要的一環(huán),表示時間效率。

本文選擇三個開源的JavaScript引擎JerryScript、ChakraCore和 JavaScriptCore作為測試對象,JerryScript版本為2.2.0,ChakraCore版本為1.12.0.0-beta,JavaScriptCore版本為2.27.4。JerryScript是三星集團開發(fā)的輕量級物聯(lián)網(wǎng)JavaScript引擎,適用于嵌入式設(shè)備,只需要很低的CPU的性能和內(nèi)存空間。ChakraCore是 Microsoft Edge瀏覽器中 Chakra JavaScript引擎的核心部分。JavaScriptCore是WebKit瀏覽器的JavaScript解析引擎部分,WebKit是一個跨平臺的瀏覽器引擎,它支持 Safari、iBook和 App Store,以及各種Mac系統(tǒng),iOS和Linux平臺。

為了平衡實驗的系統(tǒng)資源開銷,本文對這 3個模糊測試工具都只使用 4個并行進程進行實驗,保證同時運行4個JavaScript引擎,在一定程度上體現(xiàn)系統(tǒng)資源的公平性。

在測試用例方面,對 JerryScript引擎收集了1698個測試用例,對ChakraCore引擎收集了1766個測試用例,對JavaScriptCore引擎收集了2713個測試用例。

實驗中所用機器為帶有 64G內(nèi)存的 Dell PowerEdge R740,操作系統(tǒng)為64位的Ubuntu 18.04。本文參考其他相關(guān)工作的測試時間,一般測試時間為24 h,所以本文也對JavaScript引擎測試24 h。由于模糊測試具有隨機性,所以重復(fù)進行 10次實驗,對代碼覆蓋率、測試?yán)行?、?zhí)行速度取平均值進行對比,并對比10次實驗的漏洞發(fā)現(xiàn)總數(shù)。

4.2 漏洞發(fā)現(xiàn)能力

重復(fù)進行10次24 h實驗后,Bug發(fā)現(xiàn)情況如表4所示。在Bug發(fā)現(xiàn)率方面,ILS相比于Superion提升了100%。CodeAlchemist并不支持對JerryScript引擎進行測試,而且在ChakraCore和JavaScriptCore引擎中都沒有發(fā)現(xiàn)Bug。表5詳細(xì)列出了截止本文寫作時間,ILS發(fā)現(xiàn)的所有Bug具體信息,共發(fā)現(xiàn)26個不同的Bug。在JerryScript引擎中,共發(fā)現(xiàn)22個Bug,包括1個Use-After-Free、3個Buffer Overflow、2個Stack Overflow、1個 Memory Corruption和 15個Assertion Failure。在ChakraCore引擎中,一共發(fā)現(xiàn)3個Assertion Failure。在JavaScriptCore引擎中,一共發(fā)現(xiàn)1個 Memory Corruption。由于CodeAlchemist并沒有發(fā)現(xiàn)Bug,所以沒有放入表5中進行對比。

表4 24 h Bug發(fā)現(xiàn)情況對比Table 4 The comparison of Bug discovery in 24 hours

表5 ILS發(fā)現(xiàn)的BugTable 5 The Bugs found by ILS

① https://github.com/jerryscript-project/jerryscript/issues/created_by/owl337

② https://github.com/microsoft/ChakraCore/issues/created_by/owl337

③ https://bugs.webkit.org/show_bug.cgi?id=212460

4.3 代碼覆蓋提升

在模糊測試中,代碼覆蓋率是衡量測試結(jié)果好壞的基本標(biāo)準(zhǔn),能夠整體上體現(xiàn)出模糊測試工具的效果,代碼覆蓋率越高,越有可能發(fā)現(xiàn)新的Bug。

本文分別對JerryScript和JavaScriptCore進行了覆蓋率對比實驗,并使用 afl-cov[55]收集覆蓋率信息,結(jié)果表明ILS、Superion和CodeAlchemist對代碼行覆蓋率和函數(shù)覆蓋率都有提升,ILS提升效果更好。因為CodeAlchemist不支持測試JerryScript解析引擎,所以沒有進行JerryScript解析引擎的覆蓋率對比。

對于JerryScript,實驗結(jié)果如圖9所示。在代碼行覆蓋率方面,ILS相比于Superion提升48%,在函數(shù)覆蓋率方面,ILS相比于Superion提升41%。

圖9 JerryScript引擎覆蓋率對比Figure 9 The comparison coverage rate of JerryScript

對于JavaScriptCore,實驗結(jié)果如圖10所示。在代碼行覆蓋率上,ILS相比Superion提升了72%,相比CodeAlchemist提升48%; 在函數(shù)覆蓋率上,ILS相比Superion提升80%,相比CodeAlchemist提升58%。

圖10 JavaScriptCore引擎覆蓋率對比Figure 10 The comparison coverage rate of JavaScriptCore

4.4 測試用例有效率提升

生成測試用例有效性對于JavaScript引擎的模糊測試來說非常重要,一般的模糊測試工具如 AFL,隨機變異產(chǎn)生的測試用例基本上都是無效的,因為如果不符合對應(yīng)的語法規(guī)則,解析引擎將拒絕繼續(xù)執(zhí)行,所以很難發(fā)現(xiàn)系統(tǒng)運行時的Bug。

圖11顯示了生成測試用例錯誤率的實驗結(jié)果,ILS、Superion和 CodeAlchemist的平均錯誤率分別是46.16%,58.74%和72.49%。因為ILS在替換子樹時沒有對子樹的引用進行檢查,所以 ILS的ReferenceError錯誤是最多的,但是ILS能有效的減少其他的錯誤率,種子測試有效率比 Superion提升了36%,比CodeAlchemist提升了21%。

圖11 生成種子錯誤率對比Figure 11 The error Comparison of new seeds

4.5 執(zhí)行性能分析

執(zhí)行速率表示單位時間內(nèi)調(diào)用目標(biāo)軟件運行的次數(shù),執(zhí)行速度越快,越有可能在短時間內(nèi)發(fā)現(xiàn)新的Bug。

本文統(tǒng)計10次實驗每個工具生成的測試用例個數(shù),并平均計算得到每個JavaScript引擎每秒運行次數(shù),結(jié)果如表6所示。由于ILS和Superion都是基于AFL開發(fā)的,具有AFL的forkserver模式加速,所以執(zhí)行速度快,CodeAlchemist是自己控制JavaScript引擎執(zhí)行,并沒有對執(zhí)行速度進行優(yōu)化,所以性能較低。在 JerryScript引擎中,平均執(zhí)行速率 ILS比Superion每秒降低了3.03次; 在Chakracore引擎中,平均執(zhí)行速率ILS比Superion每秒降低了1.01次; 在JavaScriptCore引擎中,整體平均執(zhí)行速率 ILS比Superion每秒降低了2.6次。

表6 每秒執(zhí)行速率對比Table 6 The execution rate pre second comparison

ILS執(zhí)行速率比Superion有所降低。但總體來說相差不大,在覆蓋率提升顯著的情況下,這個執(zhí)行速率的差異是可以接受的。

5 總結(jié)與討論

本文詳細(xì)分析了針對JavaScript引擎的模糊測試技術(shù),并在路徑反饋的模糊測試框架基礎(chǔ)上提出一種基于子樹類型敏感的JavaScript引擎灰盒測試方法ILS。該方法通過對JavaScript代碼進行語法分析,把子樹進行識別分類,并在變異過程中使用同類型子樹進行替換變異。實驗結(jié)果表明,該方法能顯著提升生成測試用例的有效率,并具有更高的代碼覆蓋能力,而且發(fā)現(xiàn)了26個新的Bug。

ILS在下一步工作中,將結(jié)合基于生成的模糊測試技術(shù),對JavaScript代碼進行更細(xì)粒度的控制流分析和數(shù)據(jù)流分析,在子樹替換變異過程中消除引用未知變量,進一步消除引用錯誤以提升代碼生成的有效率。