一种基于GCC抽象语法树的缓冲区溢出漏洞检测方法

摘要

本发明涉及一种缓冲区溢出漏洞的检测方法，特别涉及一种基于GCC抽象语法树的缓冲区溢出漏洞检测方法，属于信息安全技术领域。本发明利用GCC编译器对待分析源程序进行操作，生成抽象语法树；消除抽象语法树文本中所有与分析数据流、控制流无关的信息并保持有用信息的完整性；然后将其用于程序分析中，通过对抽象语法树上相关结点的监控来达到缓冲区溢出漏洞的分析和检测的目的。与传统的没有消除冗余的解析方法相比，本方法具有更好的实用性和更高的效率与准确率。

权利要求

1.一种基于GCC抽象语法树的缓冲区溢出漏洞检测方法，其特征在于：其具体操作步骤如下：步骤一、针对待分析源程序，直接利用GCC编译器生成抽象语法树AST；

所述待分析源程序为C/C++源程序；

步骤二、在步骤一的基础上，消除抽象语法树AST中的冗余信息；具体为：第1步：遍历抽象语法树AST中的所有结点，根据抽象语法树AST的结点中的“srcp”字段的情况将所有结点分为3种类型：a.如果“srcp”字段的值是源文件名，则将该节点标记为有用结点；

b.如果“srcp”字段不是源文件名，则将该节点标记为无用结点；

c.如果该结点中不含“srcp”字段，则将该节点标记为待定结点；

第2步：重新遍历抽象语法树AST中的所有结点，并将所有被标记为有用结点和无用结点的结点称为父结点；对于每一个父结点，依次查找它的各个子结点，并按照以下规则进行判定：a.若父结点为有用结点，其子结点为待定结点，则将该子结点标记为有用结点；

b.若父结点为有用结点，其子结点为无用结点，则将该子结点标记为无用结点；

c.若父结点为无用结点，其子结点为待定结点，则将该子结点标记为无用结点；

d.若父结点为无用结点，其子结点为有用结点，则将该子结点标记为有用结点；

重复本步骤直至待定结点的数量为零；

第3步：重新遍历抽象语法树AST中的所有结点，如果该节点或者其子节点包含“call_expr”，即该节点或者其子节点包含调用表达式，并且该节点或者其子节点被标记为无用结点，则将该节点及其子节点标记为有用结点；

经过步骤二的操作，即可得到消除冗余信息的抽象语法树AST′；

步骤三、遍历步骤二产生的去除冗余信息后的抽象语法树AST′，为每个缓冲区增加一个区间对，称该区间对为对应缓冲区的属性信息，该属性信息包括表示对应缓冲区的初始分配区间alloc和实际长度区间len；初始分配区间alloc表示为：alloc(var)＝[mvar，nvar]；实际长度区间len表示为：len(var)＝[xvar，yvar]；其中，var为缓冲区变量；mvar，nvar，xvar，yvar分别为正整数，mvar，nvar表示初始分配区间alloc的下限和上限；xvar，yvar表示实际长度区间len的下限和上限；

步骤四、在步骤三的基础上，将与缓冲区相关的待分析源程序语句和函数调用抽象为对缓冲区属性信息的操作，即对初始分配区间alloc和实际长度区间len进行更新；

步骤五、在步骤四的基础上，判断每个缓冲区的状态：具体为：a.若yvar≤nvar，则判断该缓冲区为安全状态，不会发生缓冲区溢出；

b.若xvar≤nvar≤yvar，则判断该缓冲区为不安全状态，可能会发生缓冲区溢出；

c.若nvar≤xvar，则判断该缓冲区为危险状态，肯定会发生缓冲区溢出；

对可能会和肯定会发生缓冲区溢的情况作出报警提示；

经过上述步骤的操作，即可检测出缓冲区溢出漏洞。

说明书

一种基于GCC抽象语法树的缓冲区溢出漏洞检测方法

技术领域

[0001] 本发明涉及一种缓冲区溢出漏洞的检测方法，特别涉及一种基于GCC抽象语法树的缓冲区溢出漏洞检测方法，属于信息安全技术领域。

背景技术

[0002] 随着计算机技术的迅速发展，人类社会的信息化程度越来越高，整个社会的政治、经济、军事、文化以及其他领域对计算机信息系统的依赖程度也越来越高。在这种情况下，计算机系统的安全性得到了人们越来越多的关注。然而，大型软件、系统的编写需要许许多多程序员共同完成，他们将一个软件或系统分成若干板块，分工编写，然后再汇总，测试；最后再修补、发布，因此在软件中存在安全漏洞几乎是不可避免的。软件安全漏洞指软件设计实现过程中被引入的、在数据访问或行为逻辑等方面的缺陷。这些漏洞常常被攻击者利用，从而使程序行为违背一定的安全策略。基于上述原因，目前对软件安全漏洞检测技术的研究越来越受到重视。

[0003] 按照检测过程中是否需要执行程序的标准，软件安全漏洞检测技术分为动态检测和静态检测。

[0004] (1)静态检测

[0005] 静态检测方法大致可分为三类：

[0006] 第一类是基于词法分析的检测方法。对应于早期检测工具，例如Grep工具等。它出现的时间较长，且发展较成熟，其优点是：漏洞特征以数据的形式独立于分析程序存在，可以灵活扩展；另外，词法分析可以保证较好的执行效率。但它的缺点非常明显：以数据形式存在的特征库并不能对漏洞进行充分、完整的描述，从而造成漏洞信息收集的不完整，也限制了与之配合的相关算法仅能进行词法分析，因此影响了检测能力。

[0007] 第二类是注释驱动的约束分析和检测方法。它虽然引入了语法分析，却是基于程序验证系统的思想和方法进行的。这要求操作人员对检测目标非常熟悉，甚至需人工编写程序规范和注释，因此检测的自动化程度较低。David Evans以及David Larochelle所研究的Splint以及基于Splint所作的改进都是属于这种方法。

[0008] 第三类方法为将源码的特征进行抽象、建模，将漏洞检测问题转化为约束分析和求解的问题。它们一般基于已有的程序分析工具(如商业软件codesurfer)实现，其优点是：这些程序分析工具的功能非常强大，能够生成抽象语法树、函数调用关系图、控制流图甚至指针指向关系图等语法、语义信息。使用工具提供的编程接口，可以直接基于这些信息进行分析，从而减小了设计上的复杂度。目前，在该类方法中，有一种较为通用、检测效果也比较好的缓冲区溢出漏洞的检测方法，具体为：

[0009] 第1步：针对待分析源程序，直接利用GCC编译器生成抽象语法树AST。

[0010] 第2步：遍历第1步产生的抽象语法树AST，将每个缓冲区与一个整数对相关联，称该整数对为对应缓冲区的属性信息，该整数对包括分配空间大小max_length和已用长度used_length。

[0011] 第3步：将与缓冲区相关的待分析源程序语句和函数调用抽象为对缓冲区属性信息(分配空间大小max_length和已用长度used_length)的操作。

[0012] 第4步：判断分配空间大小max_length和已用长度used_length的大小关系。如果max_length＜used_length，则判断其发生缓冲区溢出。

[0013] 这种方法的缺点是：①直接针对GCC编译器生成的抽象语法树AST进行分析检测，而GCC产生的抽象语法树文本中包含许多有助于编译的细节信息，例如由“#include”命令产生的未被源程序用到的函数及结构，以及编译过程中产生的一些内部函数、类型声明、出错信息、常量等，这些信息不利于代码分析。在数量上，对一个很小的编译单位，大概能产生其1000倍的抽象语法树文本，最终产生的抽象语法树会占据整个内存。对于复杂的源程序，这些方法的检测效率将大大降低。②在第2步中，缓冲区的属性信息用一个整数对来表示，这种表示方法不够准确，会导致判定结果不准确。

[0014] (2)动态检测

[0015] 动态检测是在程序运行过程中注入测试数据，通过对程序的运行环境(包括环境变量、内存、堆和栈等)进行分析，观察程序运行是否正常、程序行为是否满足要求，来检测程序是否存在漏洞。动态检测技术的优点是不直接面对源代码，不需要修改目标程序源代码，这在一定程度上提高程序的保密性。但其明显的不足是动态检测技术对输入的依赖性，只有当特定的输入是程序执行到危险点时，漏洞才会被发现，因此，定位不准确、漏报率高。

发明内容

[0016] 本发明的目的是针对上述已有技术存在的不足，提出一种基于GCC抽象语法树的缓冲区溢出漏洞检测方法。本发明的基本思想是：利用GCC编译器对待分析源程序进行操作，生成抽象语法树；消除抽象语法树文本中所有与分析数据流、控制流无关的信息并保持有用信息的完整性；然后将其用于程序分析中，通过对抽象语法树上相关结点的监控来达到缓冲区溢出漏洞的分析和检测的目的。与传统的没有消除冗余的解析方法相比，本方法具有更好的实用性和更高的效率与准确率。

[0017] 本发明的目的是通过下述技术方案实现的。

[0018] 一种基于GCC抽象语法树的缓冲区溢出漏洞检测方法，其具体操作步骤如下：

[0019] 步骤一、针对待分析源程序，直接利用GCC编译器生成抽象语法树AST。

[0020] 所述待分析源程序为C/C++源程序。

[0021] 步骤二、在步骤一的基础上，消除抽象语法树AST中的冗余信息。具体为：

[0022] 第1步：遍历抽象语法树AST中的所有结点，根据抽象语法树AST的结点中的“srcp”字段(“srcp”字段标识了该结点的来源)的情况将所有结点分为3种类型：

[0023] a.如果“srcp”字段的值是源文件名，则判断该节点为与分析程序数据流、控制流相关的结点，标记为有用结点；

[0024] b.如果“srcp”字段不是源文件名，则判断该结点为与分析程序数据流、控制流无关的结点，标记为无用结点；

[0025] c.如果该结点中不含“srcp”字段，说明该结点暂时不能确定其来源，需要进一步检查确定，标记为待定结点。

[0026] 第2步：重新遍历抽象语法树AST中的所有结点，并将所有被标记为有用结点和无用结点的结点称为父结点；对于每一个父结点，依次查找它的各个子结点，并按照以下规则进行判定：

[0027] a.若父结点为有用结点，其子结点为待定结点，则将该子结点标记为有用结点；

[0028] b.若父结点为有用结点，其子结点为无用结点，则将该子结点标记为无用结点；

[0029] c.若父结点为无用结点，其子结点为待定结点，则将该子结点标记为无用结点；

[0030] d.若父结点为无用结点，其子结点为有用结点，则将该子结点标记为有用结点；

[0031] 重复本步骤直至待定结点的数量为零。

[0032] 第3步：由于第1步和第2步的操作将所有的库函数、内部函数及其相关信息都删除了，还需要找回源文件用到的库函数。因此重新遍历抽象语法树AST中的所有结点，如果该节点或者其子节点包含“call_expr”，即该节点或者其子节点包含调用表达式，并且该节点或者其子节点被标记为无用结点，则将该节点及其子节点标记为有用结点。

[0033] 经过步骤二的操作，即可得到消除冗余信息的抽象语法树AST′。

[0034] 步骤三、遍历步骤二产生的去除冗余信息后的抽象语法树AST′，对每个缓冲区增加一个区间对，称该区间对为对应缓冲区的属性信息，该属性信息包括表示对应缓冲区的初始分配区间alloc和实际长度区间len；初始分配区间alloc表示为：alloc(var)＝[mvar，nvar]；实际长度区间len表示为：len(var)＝[xvar，yvar]；其中，var为缓冲区变量；mvar，nvar，xvar，yvar分别为正整数，mvar，nvar表示初始分配区间alloc的下限和上限；xvar，yvar表示实际长度区间len的下限和上限。

[0035] 步骤四、在步骤三的基础上，将与缓冲区相关的待分析源程序语句和函数调用抽象为对缓冲区属性信息的操作，即对初始分配区间alloc和实际长度区间len进行更新。

[0036] 步骤五、在步骤四的基础上，判断每个缓冲区的状态：具体为：

[0037] a.若yvar≤nvar，则判断该缓冲区为安全状态，不会发生缓冲区溢出；

[0038] b.若xvar≤nvar≤yvar，则判断该缓冲区为不安全状态，可能会发生缓冲区溢出；

[0039] c.若nvar≤xvar，则判断该缓冲区为危险状态，肯定会发生缓冲区溢出。

[0040] 对可能会和肯定会发生缓冲区溢的情况作出报警提示。

[0041] 经过上述步骤的操作，即可检测出缓冲区溢出漏洞。

[0042] 有益效果

[0043] 本发明提出的方法与已有技术相比较，有如下优点：

[0044] ①消除了抽象语法树中的冗余信息并保持有用信息的完整性因此具有更好的实用性和更高的效率；

[0045] ②解决了已有方法中抽象语法树占用大量空间的问题；

[0046] ③本发明将已有技术中缓冲区的属性信息的整数对替换为两个区间alloc和len，表示更为准确，导致判定结果更为准确。

具体实施方式

[0047] 下面结合具体实施例对本发明技术方案进行详细描述。

[0048] 本实施例采用本发明方法对一段7行的C语言源程序进行测试，源程序代码如下：

[0049]

[0050]

[0051] 其操作过程如下：

[0052] 步骤一、针对待分析源程序，直接利用GCC编译器生成抽象语法树AST，其包含2280结点数。

[0053] 步骤二、在步骤一的基础上，消除抽象语法树AST中的冗余信息。具体为：

[0054] 第1步：遍历抽象语法树AST中的所有结点，根据抽象语法树AST的结点中的“srcp”字段的情况将所有结点分为3种类型：

[0055] a.如果“srcp”字段的值是源文件名，则判断该节点为与分析程序数据流、控制流相关的结点，标记为有用结点；

[0056] b.如果“srcp”字段不是源文件名，则判断该结点为与分析程序数据流、控制流无关的结点，标记为无用结点；

[0057] c.如果该结点中不含“srcp”字段，说明该结点暂时不能确定其来源，需要进一步检查确定，标记为待定结点。

[0058] 第2步：重新遍历抽象语法树AST中的所有结点，并将所有被标记为有用结点和无用结点的结点称为父结点；对于每一个父结点，依次查找它的各个子结点，并按照以下规则进行判定：

[0059] a.若父结点为有用结点，其子结点为待定结点，则将该子结点标记为有用结点；

[0060] b.若父结点为有用结点，其子结点为无用结点，则将该子结点标记为无用结点；

[0061] c.若父结点为无用结点，其子结点为待定结点，则将该子结点标记为无用结点；

[0062] d.若父结点为无用结点，其子结点为有用结点，则将该子结点标记为有用结点；

[0063] 重复本步骤直至待定结点的数量为零。

[0064] 第3步：由于第1步和第2步的操作将所有的库函数、内部函数及其相关信息都删除了，还需要找回源文件用到的库函数。因此重新遍历抽象语法树AST中的所有结点，如果该节点或者其子节点包含“call_expr”，即该节点或者其子节点包含调用表达式，并且该节点或者其子节点被标记为无用结点，则将该节点及其子节点标记为有用结点。

[0065] 经过步骤二的操作，即可得到消除冗余信息的抽象语法树AST′，其包含82个结点。

[0066] 步骤三、遍历步骤二产生的去除冗余信息后的抽象语法树AST′，将每个缓冲区