基于循环结构的缓冲区溢出检测方法的研究

摘要：缓冲区溢出影响了软件的安全。检测缓冲区溢出漏洞对于提高软件安全性具有重要意义。本文从源代码层面出发，针对循环结构提出了一种缓冲区溢出检测方法，以C语言为主要研究对象，通过对C程序中循环结构进行识别、简化、边界分析等一系列操作，实现对C程序中循环结构引起的缓冲区溢出漏洞进行精准检测。

关键字：软件安全；循环结构；缓冲区溢出；缓冲区溢出检测

一、 引言

缓冲区溢出是指输入到计算机缓冲区的数据长度超过了缓冲区大小，使得多余数据覆盖缓冲区以外区域的现象。这种现象会影响原本在覆盖区域内的执行指令。另外，缓冲区本身不具备边界检测机制，所以大部分程序在运行时默认输入数据的长度不会超过系统分配的缓冲区大小，这导致程序可能存在缓冲区溢出漏洞[1]。在计算机内存中，栈和堆是操作系统常用的缓冲区，因此栈溢出和堆溢出是两种常见的缓冲区溢出类型。本文旨在分析缓冲区溢出产生的原因，并以C语言为例，在源代码层面提出一种基于循环结构的缓冲区溢出检测方法，进而从程序设计语言层面研究缓冲区溢出的检测问题。

二、 缓冲区溢出的原因

C语言具有强大的生命力，不仅因为它具有指针、操控内存、动态分配内存等优点，而且它在各个领域都有广泛应用的优势。C语言功能强大且效率高，更重要的是它具更强大的底层操作能力，因此常被应用于操作系统、各类编辑器、浏览器、嵌入式、游戏引擎的开发[2-3]。

然而，C语言在对安全性要求高的程序中并不是首选语言。它缺乏内存检测机制，容易出现非法指针解引用、内存泄漏等安全问题。大多数缓冲区溢出问题来自标准C语言库，其中包含了一些存在漏洞的危险函数。开发人员有时不清楚哪些函數是危险函数[2]。

开发人员在使用C语言时往往注重程序的可用性和逻辑性，很少注意到边界检测的问题。比如，数组的下标越界和指针的边界问题等等，这些问题大部分出现在程序的循环结构中。心脏滴血漏洞（CVE-2014-0160）就是缺少边界检测机制产生的漏洞[4]。由于C语言缺乏边界检测机制，采用相应的措施势必会影响C语言的效率。为了提高效率，开发人员容易忽视编程语言的安全问题。

缓冲区溢出虽然会影响软件的安全性，但有时缓冲区溢出漏洞的产生并不都是软件本身的问题。除了开发软件使用的程序设计语言，计算机体系结构、进程及其他原因均会诱发缓冲区溢出[5]。比如，在大多数采用冯·诺依曼体系结构的计算机中，数据和程序均保存在存储器中，且没有明确的分界线，因此当数据或程序有一方发生变动时，都会对另一方产生影响。

三、基于循环结构的缓冲区溢出检测方法

程序中的循环结构会带来数据移动的情况，计算机会为循环体中的数组、指针或某些函数分配相应的存储空间，当数据移动操作超出存储空间的边界时，就会发生缓冲区溢出。因此，缓冲区溢出检测方法从循环结构出发，从循环体中的数据移动和边界问题入手，如图1所示，具体包含识别循环结构、简化循环结构、分析循环边界和识别溢出循环四个部分。

（一）识别循环结构

识别循环结构是一个关键步骤，该步骤主要是识别出程序中的循环结构关键字，如“for”和“while”。控制语句流图可以描述程序的执行顺序，并反映关键字的执行顺序[6]。具体的识别过程如图2所示。

1.控制语句流图生成算法

void Tdentification（int arg）{

……

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

{

if（m.name==loop_node）{ //处理循环结构

loopCSFG=new CSFG（）;

int clastid=getLoopLastId（m）; //获取循环末尾节点

loopCSFG=constructloopsta（n， clastid）;

addCNode（loopCSFG.head， CSFG）; //向控制语句流图添加节点

n= clastid+1;

}

else if（m.name== bran_node）{……} //处理分支结构

else{……}//对其他结构进行处理

}

return CSFG; //输出控制语句流图

}

该算法的输入是准备检测的源程序，对程序包含的循环、分支结构的关键字进行处理，当源程序访问结束，以文本信息输出控制语句流图，并作为循环判定算法的输入。

2.循环判定算法

h=CSFG.head; //头节点

vector>cycles; //循环信息集合

traverse（h.id）; //开始遍历

traverse（id）;

if（id==0） return;

d=CSFG.getNode（id）;

flag= has（loop，d）; //判断是否循环

if（flag）{

p=index（loop，node）; //下标

cycles[p].push（id）;

}

return cycles; //循环信息集合

使用上一步骤的输出信息作为输入，识别出控制语句流图中的循环结构的关键字信息，进而识别出循环结构，得出程序中包含循环结构的结论。

（二）简化循环结构

在识别出循环结构后，为了提高检测效率，需要对循环体进行简化，减少源代码行数[7]。在此环节使用程切片对循环体进行简化，虽然不能精准定位到出错位置，但是可以确定出一个相对较小的范围。在使用程序切片时，以基本块为单位，每个基本块都有入口和出口代码，并按照切片规则即基本块的出口影响某一变量的切片、指令的某一变量中存在切片变量和基本块的某一指令影响某一变量的切片进行简化过程。

按照切片规则有三种切片方式，首先按照顺序切片规则，将循环体中符合规则的指令放入指令集合中，并更新变量集。然后判断依赖的基本块，并生成新的切片规则，在对分支结构进行切片时，若某一指令不是某一基本款的入口指令，则该基本块所在分支对应一个顺序结构基本块，调用顺序切片过程进行切片，否则把基本块的控制指令添加到指令集中，更新变量集，查找依赖的基本块，生成新的切片规则。在循环结构中，循环体大多是由顺序和分支结构组成，在对循环结构进行切片时则是将上述两个过程相结合。

图3右侧的程序是左侧程序切片后的结果，是具有嵌套结构的for循环，循环变量不是唯一的，存在一個与数组有关的数据移动，数组的下标随着循环次数的增加而增大，进行程序切片后只保留与循环变量和数组相关的语句，使得循环结构更加简洁清楚。

（三）分析循环边界

获取缓冲区的大小，并判断外部输入能否影响循环次数和缓冲区大小，是分析边界环节的主要任务。这是分析程序是否存在缓冲区溢出漏洞的前提，针对循环体中的内容，主要使用静态污点分析技术与数据流分技术[8][9]。以数组为例，具体的边界分析框架如图4所示。C语言的数组名代表数组的指针，因此可以使用数据流分析技术找到数组的下标范围，再结合污点分析技术检测外部输入情况。

仍然以基本块为单位，用“Ent”表示一个基本块的入口状态，即出口状态的集合，用“Exp”表示一个基本块的出口状态，即某种入口状态产生的结果。进行向上分析，并使用公式（1）与（2），分析对象是数组名，“c”为基本块的后继信息集合。

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

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

在确定数组的下标范围信息后，结合污点分析技术，仍用“Ent”表示一个基本块的入口状态，用“Exp”表示一个基本块的出口状态。并根据污点传播规则修改前面的两个公式，即公式（3）与（4），“p”是指前驱的基本块信息，并利用循环结构不断执行的特点，不断检测外部输入情况，循环结构不再执行时停止。

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

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

（四）识别溢出循环

在上述三个过程的基础上，具体识别出被检测循环是否存在溢出情况。循环体是一个较复杂的结构，并结合程序切片过程，可以将循环分为非嵌套无路径循环、非嵌套有路径循环、嵌套无路径循环和嵌套有路径循环四种类型。

针对无路径循环，v是循环变量，A是步进值函数，首先对无路径非嵌套循环进行步进值计算[10]，即公式（5）。

A=A（v）                              （5）

然后用T表示循环结束条件，计算循环执行次数（E），即公式（6）。

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

在嵌套无路径循环中，存在两个或者两个以上的循环变量和结束条件，若要计算循环执行次数（N），需要计算求解每一个循环的执行次数，即公式（7）。

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

数组或者指针索引最大值结合循环执行次数进行计算，如果索引的最大值超出了缓冲区的大小，也就是超出了缓冲区边界，那么说明被检测循环结构存在缓冲区溢出。

对于有路径循环，步进值计算依然是前面提及的公式，计算循环执行次数需结合路径中影响循环变量的逻辑条件（B）和循环结束条件（T），得到循环执行次数（E），即公式（8）；

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

同样，若在嵌套有路径循环中，存在两个或者两个以上的循环变量和结束条件，若要计算循环执行次数（N），需要计算求解每一个循环的执行次数，即公式（9）。

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

将循环执行次数与目标缓冲区数组或指针的索引极值比较，找出具有缓冲区溢出的循环结构。

四、实验结果

在对68个由循环结构引起的缓冲区溢出程序进行对比实验后，本文提出的检测方法成功识别出58个引起缓冲区溢出的循环结构，其中包括43个成功检测出溢出漏洞的程序和15个未成功检测出溢出漏洞的程序。另外两个工具Flawfinder和Splint检测成功的数量分别为23个和30个，检测失败的数量分别为45个和38个。由此可见，本文提出缓冲区溢出检测方法的循环覆盖率、准确率和误报率优于另外两个检测工具。

五、结束语

本文提出了一种基于循环结构的缓冲区溢出检测方法，并进行了对比实验。由实验结果看出，该方法确实可以有效检测出循环结构中的缓冲区溢出问题，但仍然存在一些问题需要进一步解决。比如，识别循环结构的效率不高，不仅花费的时间长且存在未能识别的情况，以及因循环嵌套层数过多，可能出现漏报和错报情况等，这些问题将是下一步研究的重点。

作者单位：刘佳琳 吉林建筑科技学院

参  考  文  献

[1]贾疏桐，桂灿，苏星宇.缓冲区溢出漏洞分析及检测技术进展[J].电脑知识与技术，2020，16（13）：57-59.

[2]杨东晓.代码安全[M].北京：清华大学出版社，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]張庆晨.基于数据控制流图的缓冲区溢出漏洞检测方法[D].镇江：江苏大学，2019.

[7]刘强，况晓辉，陈华，等.一种基于程序切片相似度匹配的脆弱性发现方法[J].计算机科学，2019，46（07）：126-132.

[8]梅瑞，严寒冰，沈元，等.二进制代码切片技术在恶意代码检测中的应用研究[J].信息安全学报，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.