一種利用數(shù)據(jù)流分析算法分析C代碼中的內(nèi)存安全的方法 技術(shù)領(lǐng)域 [0001] 本發(fā)明涉及數(shù)據(jù)流分析算法、靜態(tài)分析工具開發(fā)領(lǐng)域，特別涉及一種利用數(shù)據(jù)流分析算法分析C代碼中的內(nèi)存安全的方法。 背景技術(shù) [0002] 現(xiàn)代程序語言對于堆上內(nèi)存空間的回收，無外乎兩種方式：一種是使用者在代碼中顯式地調(diào)用內(nèi)存回收函數(shù)，手動釋放內(nèi)存；另一種是引入自動的垃圾回收機(jī)制。Rust內(nèi)存管理的核心是通過所有權(quán)，規(guī)定堆上的每塊內(nèi)存在同一時刻只具有一個所有權(quán)擁有者,Rust通過靜態(tài)分析的方法，精確分析出每個變量的作用域，當(dāng)所有權(quán)擁有者的作用域結(jié)束后，堆上的這塊內(nèi)存空間也會被自動釋放掉；而C則需要手動地解決堆上內(nèi)存空間的申請和釋放，容易造成很多內(nèi)存安全問題。 [0003] Rust在內(nèi)存安全方面比C做得相對更好，但大部分Linux內(nèi)核代碼都用C寫成，短時間內(nèi)不會改為Rust?，F(xiàn)存分析技術(shù)包括Plural，但它主要針對的是java的引用。另一個針對C的內(nèi)存分析工具是微軟的Checked?c，但它針對的是數(shù)組或緩沖區(qū)越界問題，而非變量所有權(quán)。 發(fā)明內(nèi)容 [0004] 為了解決上述技術(shù)問題，本發(fā)明中披露了一種利用數(shù)據(jù)流分析算法分析C代碼中的內(nèi)存安全的方法，本發(fā)明的技術(shù)方案是這樣實(shí)施的： [0005] 一種利用數(shù)據(jù)流分析算法分析C代碼中的內(nèi)存安全的方法，將C語言內(nèi)存指令定義成形式化后的指令集，然后進(jìn)行如下操作， [0006] 靜態(tài)分析出代碼需要并給對應(yīng)指針添加標(biāo)記的位置，并為代碼自動添加標(biāo)記； [0007] 將上述代碼轉(zhuǎn)化成抽象語法樹，并對其每一個指令進(jìn)行類型檢查，同時對涉及到的指針權(quán)限轉(zhuǎn)移或借用語句進(jìn)行修改，使之在靜態(tài)單賦值中有所區(qū)分； [0008] 對抽象語法樹進(jìn)行線性化，得到靜態(tài)單賦值形式的控制流圖，進(jìn)行數(shù)據(jù)流分析，得到收斂的權(quán)限映射表的結(jié)果； [0009] 利用數(shù)據(jù)流分析算法迭代穩(wěn)定后的結(jié)果，利用錯誤檢查函數(shù)檢查是否存在內(nèi)存安全問題。 [0010] 優(yōu)選地，所述指針包括擁有所有權(quán)和不擁有所有權(quán)兩種類型。 [0011] 優(yōu)選地，所述指令集包括內(nèi)存分配、內(nèi)存釋放、內(nèi)存所有權(quán)轉(zhuǎn)移、內(nèi)存所有權(quán)借用、強(qiáng)制類型轉(zhuǎn)化、指針離開作用域、取指令、存指令、合并指令和函數(shù)調(diào)用指令。 [0012] 優(yōu)選地，錯誤檢測方法包括內(nèi)存泄漏檢測、多次釋放檢查、在被借走時轉(zhuǎn)移或釋放檢查、釋放后使用。 [0013] 優(yōu)選地，所述抽象語法樹包括函數(shù)參數(shù)和返回值的信息，并基于此建立了函數(shù)對應(yīng)的指針權(quán)限映射表，指針權(quán)限映射表包含了所有從變量到它所具有的指針權(quán)限的映射。 [0014] 優(yōu)選地，分析前，對傳入的文件進(jìn)行預(yù)處理，遍歷整個文件的代碼，查找其中全部的指針并觀測指針的行為，對指針是否有內(nèi)存分配或釋放的行為進(jìn)行分析，添加不同的指針標(biāo)記；如果有內(nèi)存釋放或分配、或?qū)哂兴袡?quán)的指針進(jìn)行轉(zhuǎn)移的行為，代表它對一塊內(nèi)存具有所有權(quán)，應(yīng)為這個指針添加具有所有權(quán)的標(biāo)記；反之，認(rèn)為這個指針僅借走了所有權(quán)，添加不具有所有權(quán)的標(biāo)記。 [0015] 優(yōu)選地，對于抽象語法樹中的每一個函數(shù)，便利其中的每一條指令，如果涉及到所有權(quán)轉(zhuǎn)移，如將擁有一塊空間的指針轉(zhuǎn)移給另一個擁有所有權(quán)的指針，添加指針?biāo)袡?quán)需要轉(zhuǎn)移的注釋；如果涉及到所有權(quán)借出，如一個沒有所有權(quán)的指針借走了另一個指針的權(quán)限，添加指針?biāo)袡?quán)被借出的注釋。 [0016] 優(yōu)選地，數(shù)據(jù)分析的具體步驟如下， [0017] 對每個函數(shù)逐一進(jìn)行分析，分別記錄它們參數(shù)和返回值的權(quán)限種類，即擁有所有權(quán)還是不擁有所有權(quán)； [0018] 如果是擁有所有權(quán)的參數(shù)和返回值，在函數(shù)調(diào)用時轉(zhuǎn)移所有權(quán)； [0019] 如果是不擁有所有權(quán)的參數(shù)和返回值，由于不知道函數(shù)內(nèi)部的情況，在函數(shù)調(diào)用時將權(quán)限記為“*”； [0020] 如果不是指針，不涉及到所有權(quán)的變化，記為“非指針”； [0021] 然后為每條涉及內(nèi)存的指令定義權(quán)限映射表的轉(zhuǎn)移方程，即由一個指針權(quán)限經(jīng)過一條指令后可能轉(zhuǎn)變?yōu)榈闹羔槞?quán)限，以及不同權(quán)限映射表的合并操作； [0022] 將抽象語法樹轉(zhuǎn)化為靜態(tài)單賦值，對于每個函數(shù)分別進(jìn)行分析。 [0023] 優(yōu)選地，內(nèi)存錯誤檢查具體算法如下： [0024] (a)將函數(shù)入口點(diǎn)的指針權(quán)限映射表初始化為函數(shù)參數(shù)權(quán)限，其余每個基本塊的入口點(diǎn)的指針權(quán)限映射表初始化為空； [0025] (b)對于每個基本塊的每條指令進(jìn)行順序分析，得到一條指令結(jié)束后的指針權(quán)限映射表并傳遞給下一條指令，直至基本塊出口處，同時，記錄是否有基本塊的指針權(quán)限映射表發(fā)生了變化； [0026] (c)如果指針權(quán)限映射表發(fā)生變化，將位于每個基本塊父節(jié)點(diǎn)處的基本塊的出口處指針權(quán)限映射表合并，并且傳遞給這個塊，作為該基本塊的入口處權(quán)限映射表。重復(fù)(b)和(c)操作； [0027] (d)如果指針權(quán)限映射表沒有發(fā)生變化，結(jié)束迭代，此時得到的結(jié)果是收斂的指針權(quán)限映射表；

1.一種利用數(shù)據(jù)流分析算法分析C代碼中的內(nèi)存安全的方法，其特征在于：將C語言內(nèi)存指令定義成形式化后的指令集，然后進(jìn)行如下操作： 靜態(tài)分析出代碼對應(yīng)指針添加標(biāo)記的位置，并為代碼自動添加標(biāo)記； 分析前，對傳入的文件進(jìn)行預(yù)處理，遍歷整個文件的代碼，查找其中全部的指針并觀測指針的行為，對指針是否有內(nèi)存分配或釋放的行為進(jìn)行分析，添加不同的指針標(biāo)記；如果有內(nèi)存釋放或分配、或?qū)哂兴袡?quán)的指針進(jìn)行轉(zhuǎn)移的行為，代表它對一塊內(nèi)存具有所有權(quán)，應(yīng)為這個指針添加具有所有權(quán)的標(biāo)記；反之，認(rèn)為這個指針僅借走了所有權(quán)，添加不具有所有權(quán)的標(biāo)記； 將上述代碼轉(zhuǎn)化成抽象語法樹，并對其每一個指令進(jìn)行類型檢查，同時對涉及到的指針權(quán)限轉(zhuǎn)移或借用語句進(jìn)行修改，使之在靜態(tài)單賦值中有所區(qū)分； 對于抽象語法樹中的每一個函數(shù)，遍歷其中的每一條指令，如果涉及到所有權(quán)轉(zhuǎn)移，即將擁有一塊空間的指針轉(zhuǎn)移給另一個擁有所有權(quán)的指針，添加指針?biāo)袡?quán)需要轉(zhuǎn)移的注釋；如果涉及到所有權(quán)借出，即一個沒有所有權(quán)的指針借走了另一個指針的權(quán)限，添加指針?biāo)袡?quán)被借出的注釋； 對抽象語法樹進(jìn)行線性化，得到靜態(tài)單賦值形式的控制流圖，進(jìn)行數(shù)據(jù)流分析，得到收斂的指針權(quán)限映射表的結(jié)果； 所述抽象語法樹包括函數(shù)參數(shù)和返回值的信息，數(shù)據(jù)流分析算法根據(jù)抽象語法樹計(jì)算函數(shù)對應(yīng)的指針權(quán)限映射表，指針權(quán)限映射表包含了所有從變量到它所具有的指針權(quán)限的映射； 利用數(shù)據(jù)流分析算法迭代穩(wěn)定后的結(jié)果，利用內(nèi)存錯誤檢測方法檢查是否存在內(nèi)存安全問題； 所述指令集包括內(nèi)存分配、內(nèi)存釋放、內(nèi)存所有權(quán)轉(zhuǎn)移、內(nèi)存所有權(quán)借用、強(qiáng)制類型轉(zhuǎn)化、指針離開作用域、取指令、存指令、合并指令和函數(shù)調(diào)用指令； 所述指針包括擁有所有權(quán)和不擁有所有權(quán)兩種類型； 數(shù)據(jù)流分析的具體步驟如下： 對每個函數(shù)逐一進(jìn)行分析，分別記錄它們參數(shù)和返回值的權(quán)限種類，即擁有所有權(quán)還是不擁有所有權(quán)； 如果是擁有所有權(quán)的參數(shù)和返回值，在函數(shù)調(diào)用時轉(zhuǎn)移所有權(quán)； 如果是不擁有所有權(quán)的參數(shù)和返回值，由于不知道函數(shù)內(nèi)部的情況，在函數(shù)調(diào)用時將權(quán)限記為“*”； 如果不是指針，不涉及到所有權(quán)的變化，記為“非指針”； 然后為每條涉及內(nèi)存的指令定義指針權(quán)限映射表的轉(zhuǎn)移方程，即由一個指針權(quán)限經(jīng)過一條指令后轉(zhuǎn)變?yōu)榈闹羔槞?quán)限以及不同指針權(quán)限映射表的合并操作； 將抽象語法樹轉(zhuǎn)化為靜態(tài)單賦值，對于每個函數(shù)分別進(jìn)行分析。