基于循環(huán)結(jié)構(gòu)的緩沖區(qū)溢出檢測(cè)方法的研究

摘要：緩沖區(qū)溢出影響了軟件的安全。檢測(cè)緩沖區(qū)溢出漏洞對(duì)于提高軟件安全性具有重要意義。本文從源代碼層面出發(fā)，針對(duì)循環(huán)結(jié)構(gòu)提出了一種緩沖區(qū)溢出檢測(cè)方法，以C語(yǔ)言為主要研究對(duì)象，通過(guò)對(duì)C程序中循環(huán)結(jié)構(gòu)進(jìn)行識(shí)別、簡(jiǎn)化、邊界分析等一系列操作，實(shí)現(xiàn)對(duì)C程序中循環(huán)結(jié)構(gòu)引起的緩沖區(qū)溢出漏洞進(jìn)行精準(zhǔn)檢測(cè)。

關(guān)鍵字：軟件安全；循環(huán)結(jié)構(gòu)；緩沖區(qū)溢出；緩沖區(qū)溢出檢測(cè)

一、 引言

緩沖區(qū)溢出是指輸入到計(jì)算機(jī)緩沖區(qū)的數(shù)據(jù)長(zhǎng)度超過(guò)了緩沖區(qū)大小，使得多余數(shù)據(jù)覆蓋緩沖區(qū)以外區(qū)域的現(xiàn)象。這種現(xiàn)象會(huì)影響原本在覆蓋區(qū)域內(nèi)的執(zhí)行指令。另外，緩沖區(qū)本身不具備邊界檢測(cè)機(jī)制，所以大部分程序在運(yùn)行時(shí)默認(rèn)輸入數(shù)據(jù)的長(zhǎng)度不會(huì)超過(guò)系統(tǒng)分配的緩沖區(qū)大小，這導(dǎo)致程序可能存在緩沖區(qū)溢出漏洞[1]。在計(jì)算機(jī)內(nèi)存中，棧和堆是操作系統(tǒng)常用的緩沖區(qū)，因此棧溢出和堆溢出是兩種常見(jiàn)的緩沖區(qū)溢出類(lèi)型。本文旨在分析緩沖區(qū)溢出產(chǎn)生的原因，并以C語(yǔ)言為例，在源代碼層面提出一種基于循環(huán)結(jié)構(gòu)的緩沖區(qū)溢出檢測(cè)方法，進(jìn)而從程序設(shè)計(jì)語(yǔ)言層面研究緩沖區(qū)溢出的檢測(cè)問(wèn)題。

二、 緩沖區(qū)溢出的原因

C語(yǔ)言具有強(qiáng)大的生命力，不僅因?yàn)樗哂兄羔?、操控?nèi)存、動(dòng)態(tài)分配內(nèi)存等優(yōu)點(diǎn)，而且它在各個(gè)領(lǐng)域都有廣泛應(yīng)用的優(yōu)勢(shì)。C語(yǔ)言功能強(qiáng)大且效率高，更重要的是它具更強(qiáng)大的底層操作能力，因此常被應(yīng)用于操作系統(tǒng)、各類(lèi)編輯器、瀏覽器、嵌入式、游戲引擎的開(kāi)發(fā)[2-3]。

然而，C語(yǔ)言在對(duì)安全性要求高的程序中并不是首選語(yǔ)言。它缺乏內(nèi)存檢測(cè)機(jī)制，容易出現(xiàn)非法指針解引用、內(nèi)存泄漏等安全問(wèn)題。大多數(shù)緩沖區(qū)溢出問(wèn)題來(lái)自標(biāo)準(zhǔn)C語(yǔ)言庫(kù)，其中包含了一些存在漏洞的危險(xiǎn)函數(shù)。開(kāi)發(fā)人員有時(shí)不清楚哪些函數(shù)是危險(xiǎn)函數(shù)[2]。

開(kāi)發(fā)人員在使用C語(yǔ)言時(shí)往往注重程序的可用性和邏輯性，很少注意到邊界檢測(cè)的問(wèn)題。比如，數(shù)組的下標(biāo)越界和指針的邊界問(wèn)題等等，這些問(wèn)題大部分出現(xiàn)在程序的循環(huán)結(jié)構(gòu)中。心臟滴血漏洞（CVE-2014-0160）就是缺少邊界檢測(cè)機(jī)制產(chǎn)生的漏洞[4]。由于C語(yǔ)言缺乏邊界檢測(cè)機(jī)制，采用相應(yīng)的措施勢(shì)必會(huì)影響C語(yǔ)言的效率。為了提高效率，開(kāi)發(fā)人員容易忽視編程語(yǔ)言的安全問(wèn)題。

緩沖區(qū)溢出雖然會(huì)影響軟件的安全性，但有時(shí)緩沖區(qū)溢出漏洞的產(chǎn)生并不都是軟件本身的問(wèn)題。除了開(kāi)發(fā)軟件使用的程序設(shè)計(jì)語(yǔ)言，計(jì)算機(jī)體系結(jié)構(gòu)、進(jìn)程及其他原因均會(huì)誘發(fā)緩沖區(qū)溢出[5]。比如，在大多數(shù)采用馮·諾依曼體系結(jié)構(gòu)的計(jì)算機(jī)中，數(shù)據(jù)和程序均保存在存儲(chǔ)器中，且沒(méi)有明確的分界線，因此當(dāng)數(shù)據(jù)或程序有一方發(fā)生變動(dòng)時(shí)，都會(huì)對(duì)另一方產(chǎn)生影響。

三、基于循環(huán)結(jié)構(gòu)的緩沖區(qū)溢出檢測(cè)方法

程序中的循環(huán)結(jié)構(gòu)會(huì)帶來(lái)數(shù)據(jù)移動(dòng)的情況，計(jì)算機(jī)會(huì)為循環(huán)體中的數(shù)組、指針或某些函數(shù)分配相應(yīng)的存儲(chǔ)空間，當(dāng)數(shù)據(jù)移動(dòng)操作超出存儲(chǔ)空間的邊界時(shí)，就會(huì)發(fā)生緩沖區(qū)溢出。因此，緩沖區(qū)溢出檢測(cè)方法從循環(huán)結(jié)構(gòu)出發(fā)，從循環(huán)體中的數(shù)據(jù)移動(dòng)和邊界問(wèn)題入手，如圖1所示，具體包含識(shí)別循環(huán)結(jié)構(gòu)、簡(jiǎn)化循環(huán)結(jié)構(gòu)、分析循環(huán)邊界和識(shí)別溢出循環(huán)四個(gè)部分。

（一）識(shí)別循環(huán)結(jié)構(gòu)

識(shí)別循環(huán)結(jié)構(gòu)是一個(gè)關(guān)鍵步驟，該步驟主要是識(shí)別出程序中的循環(huán)結(jié)構(gòu)關(guān)鍵字，如“for”和“while”。控制語(yǔ)句流圖可以描述程序的執(zhí)行順序，并反映關(guān)鍵字的執(zhí)行順序[6]。具體的識(shí)別過(guò)程如圖2所示。

1.控制語(yǔ)句流圖生成算法

void Tdentification（int arg）{

……

for（int a=i;a<=j;a++）

{

if（m.name==loop_node）{ //處理循環(huán)結(jié)構(gòu)

loopCSFG=new CSFG（）;

int clastid=getLoopLastId（m）; //獲取循環(huán)末尾節(jié)點(diǎn)

loopCSFG=constructloopsta（n， clastid）;

addCNode（loopCSFG.head， CSFG）; //向控制語(yǔ)句流圖添加節(jié)點(diǎn)

n= clastid+1;

}

else if（m.name== bran_node）{……} //處理分支結(jié)構(gòu)

else{……}//對(duì)其他結(jié)構(gòu)進(jìn)行處理

}

return CSFG; //輸出控制語(yǔ)句流圖

}

該算法的輸入是準(zhǔn)備檢測(cè)的源程序，對(duì)程序包含的循環(huán)、分支結(jié)構(gòu)的關(guān)鍵字進(jìn)行處理，當(dāng)源程序訪問(wèn)結(jié)束，以文本信息輸出控制語(yǔ)句流圖，并作為循環(huán)判定算法的輸入。

2.循環(huán)判定算法

h=CSFG.head; //頭節(jié)點(diǎn)

vector>cycles; //循環(huán)信息集合

traverse（h.id）; //開(kāi)始遍歷

traverse（id）;

if（id==0） return;

d=CSFG.getNode（id）;

flag= has（loop，d）; //判斷是否循環(huán)

if（flag）{

p=index（loop，node）; //下標(biāo)

cycles[p].push（id）;

}

return cycles; //循環(huán)信息集合

使用上一步驟的輸出信息作為輸入，識(shí)別出控制語(yǔ)句流圖中的循環(huán)結(jié)構(gòu)的關(guān)鍵字信息，進(jìn)而識(shí)別出循環(huán)結(jié)構(gòu)，得出程序中包含循環(huán)結(jié)構(gòu)的結(jié)論。

（二）簡(jiǎn)化循環(huán)結(jié)構(gòu)

在識(shí)別出循環(huán)結(jié)構(gòu)后，為了提高檢測(cè)效率，需要對(duì)循環(huán)體進(jìn)行簡(jiǎn)化，減少源代碼行數(shù)[7]。在此環(huán)節(jié)使用程切片對(duì)循環(huán)體進(jìn)行簡(jiǎn)化，雖然不能精準(zhǔn)定位到出錯(cuò)位置，但是可以確定出一個(gè)相對(duì)較小的范圍。在使用程序切片時(shí)，以基本塊為單位，每個(gè)基本塊都有入口和出口代碼，并按照切片規(guī)則即基本塊的出口影響某一變量的切片、指令的某一變量中存在切片變量和基本塊的某一指令影響某一變量的切片進(jìn)行簡(jiǎn)化過(guò)程。

按照切片規(guī)則有三種切片方式，首先按照順序切片規(guī)則，將循環(huán)體中符合規(guī)則的指令放入指令集合中，并更新變量集。然后判斷依賴的基本塊，并生成新的切片規(guī)則，在對(duì)分支結(jié)構(gòu)進(jìn)行切片時(shí)，若某一指令不是某一基本款的入口指令，則該基本塊所在分支對(duì)應(yīng)一個(gè)順序結(jié)構(gòu)基本塊，調(diào)用順序切片過(guò)程進(jìn)行切片，否則把基本塊的控制指令添加到指令集中，更新變量集，查找依賴的基本塊，生成新的切片規(guī)則。在循環(huán)結(jié)構(gòu)中，循環(huán)體大多是由順序和分支結(jié)構(gòu)組成，在對(duì)循環(huán)結(jié)構(gòu)進(jìn)行切片時(shí)則是將上述兩個(gè)過(guò)程相結(jié)合。

圖3右側(cè)的程序是左側(cè)程序切片后的結(jié)果，是具有嵌套結(jié)構(gòu)的for循環(huán)，循環(huán)變量不是唯一的，存在一個(gè)與數(shù)組有關(guān)的數(shù)據(jù)移動(dòng)，數(shù)組的下標(biāo)隨著循環(huán)次數(shù)的增加而增大，進(jìn)行程序切片后只保留與循環(huán)變量和數(shù)組相關(guān)的語(yǔ)句，使得循環(huán)結(jié)構(gòu)更加簡(jiǎn)潔清楚。

（三）分析循環(huán)邊界

獲取緩沖區(qū)的大小，并判斷外部輸入能否影響循環(huán)次數(shù)和緩沖區(qū)大小，是分析邊界環(huán)節(jié)的主要任務(wù)。這是分析程序是否存在緩沖區(qū)溢出漏洞的前提，針對(duì)循環(huán)體中的內(nèi)容，主要使用靜態(tài)污點(diǎn)分析技術(shù)與數(shù)據(jù)流分技術(shù)[8][9]。以數(shù)組為例，具體的邊界分析框架如圖4所示。C語(yǔ)言的數(shù)組名代表數(shù)組的指針，因此可以使用數(shù)據(jù)流分析技術(shù)找到數(shù)組的下標(biāo)范圍，再結(jié)合污點(diǎn)分析技術(shù)檢測(cè)外部輸入情況。

仍然以基本塊為單位，用“Ent”表示一個(gè)基本塊的入口狀態(tài)，即出口狀態(tài)的集合，用“Exp”表示一個(gè)基本塊的出口狀態(tài)，即某種入口狀態(tài)產(chǎn)生的結(jié)果。進(jìn)行向上分析，并使用公式（1）與（2），分析對(duì)象是數(shù)組名，“c”為基本塊的后繼信息集合。

Exp（b）={Ent（s）|s∈c（b） }? ? ? ? ? ? ? ?（1）

Ent（b）=G（b）∪（Exp（b）-K（b））? ? ? ? ? ? ? （2）

在確定數(shù)組的下標(biāo)范圍信息后，結(jié)合污點(diǎn)分析技術(shù)，仍用“Ent”表示一個(gè)基本塊的入口狀態(tài)，用“Exp”表示一個(gè)基本塊的出口狀態(tài)。并根據(jù)污點(diǎn)傳播規(guī)則修改前面的兩個(gè)公式，即公式（3）與（4），“p”是指前驅(qū)的基本塊信息，并利用循環(huán)結(jié)構(gòu)不斷執(zhí)行的特點(diǎn)，不斷檢測(cè)外部輸入情況，循環(huán)結(jié)構(gòu)不再執(zhí)行時(shí)停止。

Ent（b）={Exp（s） | s∈p（b）}? ? ? ? ? ? ? （3）

Ent（b）=G（b）∪（Exp（b）-K（b））? ? ? ? ? ? ? （4）

（四）識(shí)別溢出循環(huán)

在上述三個(gè)過(guò)程的基礎(chǔ)上，具體識(shí)別出被檢測(cè)循環(huán)是否存在溢出情況。循環(huán)體是一個(gè)較復(fù)雜的結(jié)構(gòu)，并結(jié)合程序切片過(guò)程，可以將循環(huán)分為非嵌套無(wú)路徑循環(huán)、非嵌套有路徑循環(huán)、嵌套無(wú)路徑循環(huán)和嵌套有路徑循環(huán)四種類(lèi)型。

針對(duì)無(wú)路徑循環(huán)，v是循環(huán)變量，A是步進(jìn)值函數(shù)，首先對(duì)無(wú)路徑非嵌套循環(huán)進(jìn)行步進(jìn)值計(jì)算[10]，即公式（5）。

A=A（v）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

然后用T表示循環(huán)結(jié)束條件，計(jì)算循環(huán)執(zhí)行次數(shù)（E），即公式（6）。

E=E（A（v），T）? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

在嵌套無(wú)路徑循環(huán)中，存在兩個(gè)或者兩個(gè)以上的循環(huán)變量和結(jié)束條件，若要計(jì)算循環(huán)執(zhí)行次數(shù)（N），需要計(jì)算求解每一個(gè)循環(huán)的執(zhí)行次數(shù)，即公式（7）。

N=N（A1（v），A2 （v），…Ak（v），T1， T2，……，Tk ），k=1，2，3，…? ?（7）

數(shù)組或者指針?biāo)饕畲笾到Y(jié)合循環(huán)執(zhí)行次數(shù)進(jìn)行計(jì)算，如果索引的最大值超出了緩沖區(qū)的大小，也就是超出了緩沖區(qū)邊界，那么說(shuō)明被檢測(cè)循環(huán)結(jié)構(gòu)存在緩沖區(qū)溢出。

對(duì)于有路徑循環(huán)，步進(jìn)值計(jì)算依然是前面提及的公式，計(jì)算循環(huán)執(zhí)行次數(shù)需結(jié)合路徑中影響循環(huán)變量的邏輯條件（B）和循環(huán)結(jié)束條件（T），得到循環(huán)執(zhí)行次數(shù)（E），即公式（8）；

E=E（A（v）， Ti ）， i=1，2，3，…? ? ? ? ? ? ? ? ? ? ? （8）

同樣，若在嵌套有路徑循環(huán)中，存在兩個(gè)或者兩個(gè)以上的循環(huán)變量和結(jié)束條件，若要計(jì)算循環(huán)執(zhí)行次數(shù)（N），需要計(jì)算求解每一個(gè)循環(huán)的執(zhí)行次數(shù)，即公式（9）。

N=N（A1（v），A2 （v），…Ak（v），E1， E2，…，Ek ）， k=1，2，3，…? ? （9）

將循環(huán)執(zhí)行次數(shù)與目標(biāo)緩沖區(qū)數(shù)組或指針的索引極值比較，找出具有緩沖區(qū)溢出的循環(huán)結(jié)構(gòu)。

四、實(shí)驗(yàn)結(jié)果

在對(duì)68個(gè)由循環(huán)結(jié)構(gòu)引起的緩沖區(qū)溢出程序進(jìn)行對(duì)比實(shí)驗(yàn)后，本文提出的檢測(cè)方法成功識(shí)別出58個(gè)引起緩沖區(qū)溢出的循環(huán)結(jié)構(gòu)，其中包括43個(gè)成功檢測(cè)出溢出漏洞的程序和15個(gè)未成功檢測(cè)出溢出漏洞的程序。另外兩個(gè)工具Flawfinder和Splint檢測(cè)成功的數(shù)量分別為23個(gè)和30個(gè)，檢測(cè)失敗的數(shù)量分別為45個(gè)和38個(gè)。由此可見(jiàn)，本文提出緩沖區(qū)溢出檢測(cè)方法的循環(huán)覆蓋率、準(zhǔn)確率和誤報(bào)率優(yōu)于另外兩個(gè)檢測(cè)工具。

五、結(jié)束語(yǔ)

本文提出了一種基于循環(huán)結(jié)構(gòu)的緩沖區(qū)溢出檢測(cè)方法，并進(jìn)行了對(duì)比實(shí)驗(yàn)。由實(shí)驗(yàn)結(jié)果看出，該方法確實(shí)可以有效檢測(cè)出循環(huán)結(jié)構(gòu)中的緩沖區(qū)溢出問(wèn)題，但仍然存在一些問(wèn)題需要進(jìn)一步解決。比如，識(shí)別循環(huán)結(jié)構(gòu)的效率不高，不僅花費(fèi)的時(shí)間長(zhǎng)且存在未能識(shí)別的情況，以及因循環(huán)嵌套層數(shù)過(guò)多，可能出現(xiàn)漏報(bào)和錯(cuò)報(bào)情況等，這些問(wèn)題將是下一步研究的重點(diǎn)。

作者單位：劉佳琳 吉林建筑科技學(xué)院

參? 考? 文? 獻(xiàn)

[1]賈疏桐，桂燦，蘇星宇.緩沖區(qū)溢出漏洞分析及檢測(cè)技術(shù)進(jìn)展[J].電腦知識(shí)與技術(shù)，2020，16（13）：57-59.

[2]楊東曉.代碼安全[M].北京：清華大學(xué)出版社，2020.

[3]TIOBE.V TIOBE Index for December 2022[EB/OL].2022[2022-12-13].https：//www.tiobe.com/tiobe-index/

[4]Zhao Xianda，Huang Shuguang，Pan Zulie，Hui Huang.Buffer Overflow Vulnerability Detection Based on Unsafe Function Invocation[J].Journal of Physics：Conference Series，2020，1549（2）：1-5.

[5]Nicula T，Zota R D.Exploiting stack-based buffer overflow using modern day techniques[J].Procedia Computer Science，2019，160：9-14.

[6]張慶晨.基于數(shù)據(jù)控制流圖的緩沖區(qū)溢出漏洞檢測(cè)方法[D].鎮(zhèn)江：江蘇大學(xué)，2019.

[7]劉強(qiáng)，況曉輝，陳華，等.一種基于程序切片相似度匹配的脆弱性發(fā)現(xiàn)方法[J].計(jì)算機(jī)科學(xué)，2019，46（07）：126-132.

[8]梅瑞，嚴(yán)寒冰，沈元，等.二進(jìn)制代碼切片技術(shù)在惡意代碼檢測(cè)中的應(yīng)用研究[J].信息安全學(xué)報(bào)，2021，6（03）：125-140.

[9]Schubert Philipp Dominik，Gazzillo Paul，Patterson Zach，Braha Julian，Schiebel Fabian，Hermann Ben，Wei Shiyi，Bodden Eric.Static data-flow analysis for software product lines in C[J].Automated Software Engineering，2022，29（1）：1-37.

[10]Pereira Jose DAbruzzo，Ivaki Naghmeh，Vieira Marco.Characterizing Buffer Overflow Vulnerabilities in Large C/C plus plus Projects[J].IEEE ACCESS，2021，9：142879-142892.