對象驅動的Linux內核crash分類技術研究

何林浩,魏 強,王允超,郭志民

1(信息工程大學 數學工程與先進計算國家重點實驗室,鄭州 450001) 2(國網河南省電力公司 電力科學研究院,鄭州 450052)

0 引 言

內核是操作系統中最重要的軟件組件,其安全性決定了整個操作系統和用戶應用程序的安全性.由于內核程序的特權級別高,內核程序中的漏洞危害通常要比用戶程序中的漏洞危害更為嚴重,所以內核一直是被攻擊的目標,比較經典的例子有DirtyCow(臟牛漏洞)[1]、藍牙出血漏洞[2]以及臟管道漏洞[3]等.為了主動檢測和修復這些漏洞,安全社區不僅開發模糊測試工具來挖掘深層次的漏洞,同時組織安全分析人員和內核開發人員對報告的漏洞進行及時的修復.

前20年,內核漏洞挖掘的速度一直很慢.直到2016年前后谷歌發布了Syzkaller和Syzbot開源項目[4],內核漏洞挖掘的速度開始急劇增長.Syzbot是一個以Syzkaller為模糊測試引擎的持續化模糊測試平臺.該平臺持續地、自動化地模糊測試主要的 Linux 內核分支來發現 bug.Syzbot可以生成標準的崩潰報告和結構化信息字段,便于安全分析人員重現 bug 并分析根本原因.截至2022年9月,該系統發現了4980個內核 bug,超過了syzkaller出現之前20年所發現的內核bug總和.雖然 Syzbot的持續化模糊測試極大地提高了內核 bug發現的效率,但它也產生了大量的崩潰報告.自項目發布之日起,Syzbot已經產生了超過1000萬個崩潰報告,其中絕大多數是由相同的錯誤觸發的.安全分析人員需要手動分析這些報告來評估錯誤的嚴重性并查明根本原因,所以把由同一錯誤引起的崩潰報告分組會極大的減少修復人員的手工分析以及提高漏洞修復的效率.當 Syzbot 報告崩潰時,它會自動生成一個由崩潰函數和崩潰類型組成的錯誤標題.例如,標題“KASAN:slab-out-of-bounds Read in sctp_inq_pop”表示崩潰發生在“sctp_inq_pop”函數上,崩潰類型為“KASAN:slab-out-of-bounds Read”.持續化模糊測試會不斷觸發同一個錯誤,產生很多重復的crash.目前,Syzbot 使用一種簡單的啟發式方法進行crash分類:如果crash共享相同的崩潰函數和崩潰類型,那就將它們分組到相同的錯誤標題下.如圖1所示,crash1-N共享相同的錯誤標題B.

圖1 crash組、錯誤標題和crash之間的關系Fig.1 Relationship between crash groups,bug title and bug reports

圖2 整體流程圖Fig.2 Overall process

但是,這種基于啟發式的crash分類方法并不準確.通過調研發現,在 Syzbot dashboard(錯誤報告平臺)上由同一個根本原因引起的一些crash并沒有被分組在一起(因為它們具有不同的崩潰功能或崩潰類型).如圖1所示,錯誤標題A、B和C歸屬于同一個根本原因,但現有的方法并不能將其分到同一個crash組.這將導致同一個根本原因的不同crash被當作新的bug被分配給不同的安全分析人員.一方面,多組分析人員并行處理同一個bug缺乏互相交流會導致漏洞修復效率低下.另一方面,對同一個bug的錯誤行為的有限了解可能會導致補丁的不完整.據統計[5],2017年9月～2020年11月Syzbot上報告了2526個內核crash組和超過324萬個崩潰報告,但根據它們的根本原因,實際可以分成1686個不同的內核crash組.在2526個內核crash組中,有840個(33.2%)crash組為冗余分組.慕冬亮等人[5]針對crash大量重復的問題選取了一部分bug進行實證研究,獲得了Linux內核錯誤行為表現多樣的原因,并提出了對應的消除重復策略,但僅僅通過提取PoC系統調用進行相似對比難以結合程序運行上下文進行分析,分類結果仍然存在假陽性的問題.所以,現有的Linux內核crash分類方法粒度較粗,在準確性上存在較大的問題,難以實現對漏洞的可利用性評估.

本文針對上述存在的問題,基于對Linux內核源碼的基本了解和內核錯誤的基本觀察,提出了一種對象驅動的Linux內核crash分類方法.基于Linux內核源碼存在大量結構體來實現各種系統功能的基本事實,以及Linux內核錯誤大多與結構體成員變量的錯誤使用有關的基本觀察,本文提取與錯誤相關的內核對象近似代替根本原因指導crash的分類.首先,本文通過后向污點分析技術提取錯誤相關內核對象,根據內核對象之間的調用關系進一步構造調用依賴圖,度量內核對象與根本原因的相關性.最后,將內核crash與內核對象的關系抽象為二部圖,通過比較提取出的內核對象的相似性來確定crash的相似性.本文以Syzbot dashboard平臺報告的crash為數據集來評估crash分類方法的有效性.相較于之前的方法,分類的準確性有較大提升,自動化的分類方法顯著提高了對漏洞的可利用性評估,節省了安全分析人員的手動分析時間.

1 相關工作

持續化模糊測試平臺的出現,如谷歌的OSS Fuzz和微軟的模糊測試服務,證明了自動化漏洞挖掘工具的有效性.準確的crash分類對于持續化模糊測試平臺來說至關重要:

1)減少耗時的手動調試工作

2)描述自動化漏洞挖掘工具的有效性

3)對有趣的崩潰測試用例進行排序

然而,有效部署自動模糊測試技術的一個突出挑戰是在crash分類過程中準確識別獨特的缺陷.模糊測試工具通常會生成數千個崩潰輸入,最終對應于同一個bug.crash的巨大數量使手工檢查很困難,這是一個難題,同時也是一個研究的熱點領域.

模糊測試工具,例如SmartFuzz[6]、Vuzzr[7]、FuzzSim[8]和Syzkaller[4]等,使用調用堆棧上的函數名、行號和文件名生成堆棧散列的方法進行crash分類.王曉鵬等人[9]通過計算重復數據的堆棧編輯距離和TF-IDF來進行錯誤報告分類.基于AFL的模糊測試工具考慮執行路徑中的基本塊轉換.AURORA[10]、kAFL[11]等根據邊覆蓋的相似性來確定crash的唯一性.但是,Klees等人的研究[12]表明這種方法會產生過多的假陽性和假陰性.Pham等人[13]使用一種依賴于作為路徑約束的輸入的語義特征的聚類算法,特別適用于符號執行工具.但是此方法僅對bug本身的語義屬性敏感,不能根據路徑約束來分類crash.Chen等人[14]提出一種機器學習方法,對模糊測試工具輸出的有趣測試用例進行排序,并使用補丁作為基礎事實,將crash輸入映射到獨特的錯誤.Ton Der等人[15]使用補丁模板和來自程序的語義反饋來自動生成和應用錯誤的近似修復,從而代替補丁來精確地識別屬于同一個根本原因的crash.慕冬亮等人[5]針對Linux內核crash提出了分類策略,但仍存在假陽性的情況.

2 設計原理與方法概述

與上述的分類方法不同,僅是利用現有的錯誤信息,如堆棧跟蹤等可以保證分類的快速和高效,但并不能保證分類的準確性,本文的方法追求更加準確的分類.借鑒TonDer等人研究[15]的思想,追求一種近似修復來代替根本原因指導正確分類.本文則試圖尋找另一種近似代替根本原因指導分類的方法,此方法基于一個基本事實:根本原因與內核對象之間存在映射關系.

根本原因是指導致二進制可執行文件崩潰的根源,通常不是崩潰點的位置,可能在更加前面的地方.內核對象是指Linux內核開發人員實現大量的設計模式以及抽象設備和功能的結構體.根本原因與內核對象存在的映射關系可從以下兩個角度看出.

1)從操作系統源碼的角度來看

由于結構體“高內聚、低耦合”的特性以及較快的內存訪問速度,Linux操作系統的作者Linus及后續開發人員在實現操作系統時,大量地使用了結構體來存儲信息以及實現對各種設備的抽象.所以從操作系統源碼層次來看,內核中的錯誤必然會涉及到結構體,二者之間存在一定的映射關系.

2)從具體內核錯誤的角度來看

基于對很多Linux內核錯誤的觀察,可以發現:一個內核錯誤的根本原因通常是由兩種行為造成的.一種是對內核對象的不適當使用導致了內核錯誤,例如CVE-2022-0847臟管道漏洞(Dirty Pipe),該漏洞為變量未初始化漏洞.漏洞成因為 copy_page_to_iter_pipe()和 push_pipe()函數對pipe_buffer 結構的成員變量flag的不當使用(未初始化使用).由于沒有清除 PIPE_BUF_FLAG_CAN_MERGE 屬性,導致后續進行 pipe_write()時誤以為write操作可合并,從而將非法數據寫入了文件頁面緩存,導致任意文件覆蓋漏洞.另一種是由于內核對象計算錯誤,該值進一步傳播到一個關鍵的內核操作,導致內核發生錯誤.例如CVE-2022-0185 File System Context 整數溢出漏洞,由syzkaller發現,可以實現提權和容器逃逸.其漏洞成因為ctx結構的成員變量ctx->data_size計算錯誤整數溢出進而導致堆溢出.

基于以上兩點觀察,可以發現內核錯誤根本原因與內核對象之間存在一定的映射關系,一個內核錯誤關聯至少一個內核對象的不當使用或錯誤計算.林等人的研究[16]證明了錯誤相關的內核對象可能不止一個,與根本原因不表現出一一映射的關系.如圖3所示,同一個根本原因的crash關聯到一個內核對象的集合.林等人的研究[16]采用了提取內核對象的方法,旨在縮小根本原因相關的內核對象集合,尋找根本原因最相關的內核對象,從而指導內核模糊測試工具遠離與錯誤無關的路徑.但本文的目的在于盡可能挖掘與根本原因相關的所有內核對象,從而更準確的實現分類.

圖3 根本原因與內核對象關系圖Fig.3 Relationship between root cause and kernel object

為了實現上述想法,本文將技術方法設計為一個靜態分析提取結構體和二部圖結構建模對比crash相似性的過程.如圖2所示,首先,本文將內核錯誤報告以及相應內核源碼作為輸入,執行后向污點分析提取內核錯誤中涉及到的所有內核對象.其次,根據內核對象與根本原因之間的映射關系,內核對象集合近似等價于根本原因,具有相同內核對象集合的crash應該為同一個根本原因.所以本文將crash的相似性對比問題轉化為內核對象的相似性對比.但是僅比較內核對象集合成員之間的相似性缺少相關性度量(不同的內核對象與根本原因的的相關性程度不同),所以本文分析得到的所有內核結構體之間的調用關系,構造內核對象調用依賴圖,以pagerank算法計算內核對象的被調用程度,以此作為內核結構與根本原因的相關性的度量.最后,本文將crash與內核對象之間的引用關系以及相關度抽象為一個二部圖結構,并通過二部圖相似性比較算法實現最終的分類.在下一節,本文將詳細闡述這些技術細節.

3 技術細節

本節將詳細闡述內核對象驅動的crash分類方法的技術細節.首先,本節將詳細描述如何分析內核錯誤報告并提取錯誤相關的結構體.其次,本節描述如何對提取出的結構體應用pagerank算法進行相關度排序.最后,本節描述如何將crash的相似性轉化為引用結構體的相似性比較并構建二部圖模型進行分類.

3.1 提取內核對象

本文使用了后向污點分析技術來提取錯誤報告中涉及到的內核對象,下面詳細說明如何編譯Linux內核源碼進行靜態分析以及如何定義source點、sink點和污點傳播的規則.

3.1.1 Linux內核源碼編譯

從9.0版本開始,LLVM支持對Linux內核的編譯.LLVM 提供了完整的代碼靜態分析框架,包括編譯器、中間語言表示和大量的靜態分析和轉換程序.為了防止編譯優化對之后的靜態分析造成影響,本文使用 LLVM 編譯器框架提供的 Clang 編譯器編譯 Linux 內核源碼為 Bitcode[17](字節碼)形式的 IR(Intermediate Representation,中間表示).LLVM 的 IR 被設計用于編譯器優化,即代碼的靜態分析和轉換.LLVM采用靜態單賦值(SSA,Static Single Assignment)形式表示代碼中的變量,保留了變量的類型信息.這個特性使得自動靜態分析變得更為簡單.本文延續了之前工作的方法[16],對LLVM編譯器clang進行補丁,以便輸出編譯優化之前的 Bitcode文件.另外,在編譯內核時開啟了KASAN選項,便于下一步source點規則的定義.同時,編譯的Linux內核版本與錯誤報告對應的內核版本保持一致.

3.1.2 source點規則定義

本文使用Linux內核自帶的錯誤檢查機制定位錯誤變量從而確定source點.Linux 內核具有以不同方式實現的錯誤檢查功能(例如,BUG、WARN 和 KASAN),其中大多數遵循相同的實現模式.即在內核執行期間執行檢查,判斷是否滿足預定義的條件.如果條件不成立,那么內核將進入錯誤狀態,并記錄可能用于調試的關鍵信息.在記錄了關鍵信息之后,內核可能會采取進一步的措施使自己死機或終止當前進程.這些調試特性可以分為兩類,一類為在內核源碼中開發者預先定義的宏,一類為編譯器或者硬件完成的KASAN等錯誤檢查機制,所以本文對source點的選取主要以這兩類錯誤檢查為依據.

1)宏定義檢查

如表1所示,選取了CVE-2019-25045的錯誤報告進行分析.在第6行,內核檢查&net->xfrm.state_all變量,如果不為空,則內核程序繼續執行第7行,完成對sz的賦值操作.如果為空值,內核程序進入預先定義的WARN_ON宏中執行代碼并記錄錯誤行為.此例中,當且僅當!list_empty(&net->xfrm.state_all)為真時,內核程序進入錯誤狀態,所以&net->xfrm.state_all變量為后向污點分析的起點.

表1 宏定義錯誤檢查Table 1 Macro definition error checking

2)KASAN檢查

KASAN檢測每個存儲器的訪問,以便內核可以檢查對存儲器地址的訪問是否合法,KASAN 依賴影子內存來記錄內存狀態.例如,如果被檢測的內核接觸到被釋放的內存區域,KASAN將生成一個錯誤報告,指出觸發釋放后使用錯誤的指令.從這些KASAN調試機制生成的錯誤報告中可以很容易地識別出執行無效內存訪問的指令.本文在這些信息的基礎上,進一步識別與無效內存訪問相關的變量.由于報告中包含的二進制指令不包含類型信息,不便于定位污點變量,為了解決這個問題,本文從調試信息中將二進制指令與它們在源代碼中對應的語句進行映射.如果映射的源代碼只有一個加載或存儲的簡單語句,可以直接得出結論,該語句是導致非法內存訪問的語句,并將操作數變量視為污染源.但如果所識別的指令涉及多個存儲器加載和存儲的復合語句,例如表2所示,data.pscan_rep_mode=info-> pscan_rep_mode語句同時涉及到了對一個變量的加載和對另一個變量的存儲.本文檢查錯誤報告并查明捕獲內核錯誤的具體指令,然后將與錯誤捕獲指令相關聯的內存訪問視為污點源.錯誤報告指出錯誤是由info->pscan_rep_mode關聯的指令kasan_check_read(&info->bdaddr,sizeof(var))得到的,所以將變量info->pscan_rep_mode視為source點.

表2 KASAN錯誤檢查Table 2 KASAN error checking

3.1.3 污點傳播規則及sink點規則定義

錯誤報告中還包含了調用跟蹤,本文以此為基礎,構造錯誤的控制流圖,在圖上向后傳播污點.在污點傳播的過程中,本文進行了指針分析,以便將污點傳播到變量的別名上.

1)污點傳播規則

隨著污點向后傳播,本文使用以下策略來執行變量污染.如果被污染的變量是嵌套結構或聯合變量的字段,那就進一步污染其父結構變量,并將父結構視為關鍵結構,這是由于嵌套結構或聯合變量是內存中父結構變量的一部分.如果嵌套結構或聯合變量的字段帶有無效值,這可能是由于其父結構變量的使用不當造成的.

當后向污點傳播遇到循環時,如果污點源在循環內被更新,污點也將被傳播到循環計數器.這是由于存在這樣一種情況,一些越界訪問錯誤,其中循環計數器被破壞、意外擴大,并最終被用作到達無效內存區域的偏移量.通過將污點擴展到循環變量,可以找到損壞的變量,有助于進一步識別與損壞相關的其他結構變量.

2)Sink點定義

首先,如果污點傳播到已污染過的變量就停止污點分析.其次,如果污點傳播到系統調用的入口、中斷處理程序或者或啟動工作隊列調度程序的函數的入口,這代表已經傳播到這段內核程序的起始位置,也可以中止污點分析.本文將保存所有污點分析得到的結構體作為下一步進行內核crash分類的依據.

3.2 相關性計算

設計原理中已經提到,本文將crash與內核對象的關系建模為一個二部圖.通過分析具體的內核錯誤得知,不同的內核對象與crash的關聯程度也不同.所以構造的二部圖的邊需要賦予不同的權重,從而更準確的挖掘crash與內核對象的相關性.通過對內核錯誤的觀察發現,越是常用的結構體與crash的相關性越低,越是不太常用的結構體相關性越高.所以本文通過構造一個內核對象引用關系圖,進而應用pagerank算法計算內核對象節點所占的權重作為相關性的度量.

本節構建了描述內核結構之間的引用關系的圖.圖中的每個節點代表一個內核結構,節點之間的有向邊表示引用關系.首先,本文分析內核源代碼中定義的所有結構.給定一個結構,本文檢查它的所有成員變量.如果變量是指向另一個結構的指針,那么將給定的結構鏈接到被引用的結構.如果成員變量是嵌套結構體或共用體,那將不斷進入下一層進行識別,直到定義中不再有嵌套結構體或共用體.將給定的結構直接鏈接到最后一層結構體,忽略中間的過程以縮小圖的大小.例如表3所示的cred結構體,user是一個結構體user_struct的指針,本文將cred與user_struct鏈接起來.本文進一步識別共用體中的成員變量,rcu是一個結構體rcu_head的指針,那將cred直接關聯到rcu_head.

表3 Cred結構體定義Table 3 Cred structure definition

除了分析內核源碼中的結構體定義,本文還考慮了類型轉換問題.由于內核支持使用單一接口來描述不同設備和特性的多態,可以將一種抽象數據類型轉換為更具體的類型.因此,本文對此類類型轉換進行識別,對轉換前后涉及到的結構體進行鏈接,進一步完善結構體調用依賴圖.

在調用圖的基礎上,應用PageRank算法進行計算各個結構體的使用程度.基于對內核錯誤的觀察,使用程度高的結構體與根本原因的相關性越小.所以進一步對得到的pr值進行處理,定義相關度為cor=1/pr,計算并保存結構體對應的相關度數據.

3.3 內核crash分類

設計原理中已經提到,將crash相似性對比轉化為引用對象的相似性對比.針對此問題,本文將crash與內核對象的引用關系建模為一個二部圖.然后,基于此二部圖進行相似度的計算.

3.3.1 Crash與內核對象引用關系建模

二部圖又稱作二分圖,是圖論中的一種特殊模型.設G=(V,E)是一個無向圖,如果頂點V可分割為兩個互不相交的子集(A,B),并且圖中的每條邊(i,j)所關聯的兩個頂點i和j分別屬于這兩個不同的頂點集(i in A,j in B),則稱圖G為一個二部圖.本文構造crash與內核對象引用關系圖G={C,O,E,W},圖中的節點可以分為兩個集合,一個是crash集合C={c1,c2,…,cm},一個是內核對象集合O={o1,o2,…,om}.集合E表示邊的集合,由3.1提取出的引用關系所決定.矩陣W表示邊的權重,由3.2節得到的相關度決定.則二部圖的鄰接矩陣定義為:

(1)

3.3.2 分類算法

至此,本文將crash的相似性比較轉化為相關內核對象的比較.SimRank是一種基于圖的拓撲結構信息來衡量任意兩個對象間相似程度的模型.算法的核心思想為:如果兩個對象和被其相似的對象所引用(即它們有相似的入鄰邊結構),那么這兩個對象也相似.因此,使用此算法可以比較內核對象的相似性確定crash的相似性從而實現分類.I(cp)表示所有指向節點cp的節點集合(即入鄰點集合),I(cq)用表示所有指向節點cq的節點集合,用s(cp,cq)表示兩個內核crash的相似度,則數學定義式表達如下:

(2)

其中,C是一個阻尼系數(decay factor),通常取0.6～0.8.

算法1.crash分類算法

輸入：crash和內核對象帶權二部圖,C:阻尼系數,k:迭代次數,V:證據矩陣,T:相似性閾值

輸出：S:節點相似度矩陣,List:相似對列表,S1,…,Sn:相似的crash集合

1.S=In//計算相似度矩陣

2.For i=1:k,do

3.Temp=C PW SW //PW是轉移概率矩陣W的轉置矩陣

4.S=temp + In-Diag(diag(temp))

5.End

6.S=S×V

7.List={}

8.For sijin S do //篩選出相似度矩陣中的相似集合

9. If sij>T then

10. List=List + {(I,j)}

11.End

12.Union-Find(List) //并查集算法

13.End

14.Return S,List,S1,…,Sn

但是,由于相關程度的不同,樸素simrank算法由于沒有考慮邊的權重,并不能很好的實現分類.另外,關系越簡單(相連邊少)的節點更容易與其他節點相似,關系越復雜(相連邊多)的節點更難與其他節點相似,樸素SimRank缺乏考慮節點的共同相鄰點集的大小.本文進一步引入更加適合的simrank++算法,加入節點相似度證據和邊的權重以度量相關程度.

對于節點cp和cq,相似度證據可以表示為:

(3)

帶證據的相似度公式為:

Sevidence(cp,cq)=evidence(cp,cq)·s(cp,cq)

(4)

將相似度比較定義為運算⊕,若cp和cq相似,則cp⊕cq.⊕運算滿足傳遞性,若cp⊕cr,則cq⊕cr,由此可以將相似性集合進一步合并.基于以上推導,crash分類算法具體實現如算法1所示,以構建的內核crash和內核對象的二分圖以及simrank++算法相關的參數作為輸入,輸出相似的crash集合.首先使用simrank++算法計算出相似度矩陣,如算法1～6行所示.然后篩選出相似的crash集合,如算法7～11行所示.最后使用并查集算法合并具有相同元素的集合,如算法第12～14行所示.

4 評 估

本節首先介紹實驗的配置以及數據集的選取等,然后介紹本文所采取的基線和評估指標.最后,本文進行對比實驗驗證方法的有效性,進行消融實驗驗證各個組件的作用,在未修復的錯誤上應用本文的分類方法驗證可用性.

4.1 實驗設計

數據集和評估指標:首先,本文從syzbot平臺的已修復部分隨機選取了10組重復的crash,組內crash數量從2～9個不等,共45個重復的crash.另外,隨機選取了55個不存在重復的crash.總體來說,本文選取了100個crash.考慮到現有方法的輸入是成對的crash作為輸入的,所以本文將所選取的數據集分成104個重復對和4882個非重復對.評估指標設置為成功分類的重復crash和真實的重復crash的比率,即真陽性(TP),以及錯誤分類為非重復crash和真實非重復crash的比率,即假陽性(FP).

另外,除了與現有的方法對比分類的準確性之外,本文還從促進可利用性評估的角度進一步評估分類結果的有效性.如表4所示,本文根據crash的錯誤標題所表現出的危害性將可利用性分為3個等級.

表4 可利用性等級Table 4 Availability level

配置:本文進行實驗所用的操作系統系統為 Ubuntu-18.04 LTS,服務器配置為256GB內存和英特爾至強6248 20核CPU@2.50GHz×2.

4.2 有效性驗證

為了驗證本文分類方法的有效性,選取了當前兩種最先進的分類方法進行對比,均優于現有的方法.第1個方法為clusterfuzz使用的棧相似性對比算法[18],第2個方法為慕冬亮等人[5]使用的分類算法,這兩種分法以成對的crash作為輸入.分類效果如表5所示,本文提出的方法可以對104個重復crash對中的88個crash對成功進行分類,真陽性率為84.6%,高于前兩種方法的49.0%和79.8%.并且,本文提出的方法在所使用的數據集中并沒有產生誤報,不會產生假陽性,證明了此算法的有效性和可靠性.相比于棧相似性對比算法僅對比調用棧信息,無法深入程序的執行路徑.本文提出的算法執行后向污點分析,提取相關的內核對象更為接近程序崩潰的根本原因,更能指導crash的正確分類.相比于慕冬亮等人[5]提取的PoC中系統調用相似性對比方法需要crash提供PoC的局限性,本文的方法不需要PoC作為輸入,僅需要錯誤報告作為輸入,可以對一部分缺少PoC只有錯誤報告的crash對正確進行分類,例如表6中的crash實例68258ee和5b88fac.

表5 分類效果Table 5 Classifying quality

表6 Crash實例分析表Table 6 Crash case analysis

此外,本文的分類結果不僅以重復對的形式展現,而且可以將重復的對合并分組,可以更好的體現分類的意義.如圖4所示,本文所用的方法可以將9個分組分類成功,將100個crash分類為69個獨特的crash組,極大的縮小了獨特crash的數量,減少了分析人員的手工勞動,并且對同一個錯誤的不同崩潰路徑的分析更有助于分析人員確定根本原因和確定其可利用性等級,以便對漏洞進行更全面的修復.例如表6中的crash實例68258ee和5b88fac,根據表5中展示的可利用性等級為低可利用性和高可利用性.通過分組,可以將此crash定義為高可利用性的crash組,從而提高修復的優先級.例如表6中的crash實例e4be308、84a6b6d、4fbc4bf、37e6f6b、129e6b9b,分析人員可以更加全面的掌握觸發錯誤的不同路徑,以便對漏洞進行全面的補丁修復.

圖4 分類結果Fig.4 Classification results

4.3 組件有效性驗證

為了證明組件之間的有效性和必要性,本文進行了消融實驗.實驗設計為樸素分類法(不加入相關性度量和證據的算法)和加入相關性度量及證據的算法.

實驗結果如圖5所示,可以看出樸素分類算法分類準確率下降明顯.分析其原因,例如表6中crash實例e4be308、84a6b6d、4fbc4bf、37e6f6b、129e6b9b、68258ee和5b88fac15等類型的crash對,使用樸素分類算法依然可以正確分類.但對于表6中的crash實例df62b81和146653c,由于內核對象權重一致,樸素分類法不能排除ipvhdr、inet_sock和rtable等無關內核對象的影響,而加入相關性度量和證據可以將和等關鍵內核對象的權重提高,更適應多內核對象的分類情況從而實現正確分類.

圖5 組件效果對比Fig.5 Component effect comparison

4.4 未修復錯誤可用性驗證

上述實驗證實了本文方法的有效性,接下來將本文的方法應用于現實世界中的未修復錯誤,以檢測之前未知的重復.本文對syzbot平臺的未修復錯誤進行了分類,發現了8組重復的crash,包含25個錯誤標題,這些錯誤標題在正確的分類指導下可以成功合并到相同分組,以減少分析人員的手工勞動從而更快的確定的修復錯誤.其中一組例子展示在表6中,通過本文的方法將00b1cbe、d4ba8fd和aa3cd47正確分類后,分析人員將對此錯誤有一個更全面的認識.本文將所有檢測出的錯誤分類標題提交給了項目開發者,得到了開發者的積極響應.

5 總 結

本文發現Linux內核crash存在大量重復,這可能會導致內核錯誤修復的延遲.為此,本文提出了一種內核驅動的Linux內核crash分類方法.通過實驗結果分析,本文的方法優于現有的分類方法,且對真實世界的錯誤分類也有很好的效果.這項工作促進了漏洞的可利用性評估,未來將結合機器學習的方法進一步優化本文的算法,以更好的適應數量巨大crash的分類.