基于XML中间模型以及缺陷模式匹配的静态检测系统

摘要

本发明属于软件安全技术领域，涉及一种基于XML中间模型以及缺陷模式匹配的软件静态检测方法。其特征在于构造基于关系存储模式的关系语法树，以及基于XML格式的中间数据存储模型，经过预处理、词法分析、语法分析模块对待检测的源代码文件进行解析，提取出程序代码的所有安全关键属性信息，利用XML生成模块存储在XML中间文件中，由漏洞检测模块根据规则配置文件，提取规则库中相应规则，对前端生成的XML中间文件执行规则检测。

说明书

技术领域

本发明属于软件检测技术领域，涉及一种基于XML中间模型以及缺陷模式匹配的静态检测方法。 

背景技术

目前，检测软件安全漏洞的方法主要有动态测试和静态分析。 

动态测试方法通过软件的实际执行来发现软件中的错误，由于只能对有限的测试用例进行检查，所以不能保证发现软件的所有安全漏洞。 

静态分析不编译运行程序，而是通过对程序源代码进行分析以发现其中的错误，能在早期发现30％～70％的逻辑设计和编码缺陷引入的安全漏洞而。静态分析技术通过对源代码进行检查，往往能在开发早期发现软件隐含的安全问题，提高程序的可靠性和健壮性。尽管静态分析方法可能产生一定的漏报(false negatives)或误报(false positives)，但仍然是当今最实用、最有效的安全漏洞检测方法之一。在实际使用中，静态测试能快速找到软件安全缺陷，比动态测试更有效率。目前，软件安全静态分析技术主要分为模型检测、词法分析、类型推导、符号执行、定理证明等。其中，模型检测是一种验证有限状态的并发系统的方法，基本思想是对于有限状态的系统构造状态机或者有向图等抽象模型，再对模型进行遍历以验证系统的某一性质。模型检测的难点在于如何避免状态空间爆炸。为此人们提出了多种方法。其中符号化模型检测方法是将抽象模型中的状态转换为逻辑公式，然后判定公式的可满足性。还可将模型转化成自动机，同时将需要检查的公式转换为一个等价的自动机，再将此自动机取补。这两个自动机的积构成了一个新的自动机，则判定模型是否具有某一属性的问题就转换成检查这个新自动机能接受的语言是否为空。 

发明内容

本发明提供了一种基于XML中间模型以及缺陷模式匹配的源代码静态检测方法，通过构造基于关系存储模式的关系语法树，以及基于XML的中间数据存储模型，将源代码安全属性信息提取并存储到XML中间模型中，以供规则检测器进行规则匹配和缺陷检测。 

本发明的技术方案如下： 

1、静态检测系统的整体架构建立 

本发明整体架构包括系统前端静态信息提取和系统后端漏洞检测两个功能模块。 

系统前端静态信息提取模块由预处理模块和源代码解析模块组成，负责对待检测代码源文件进行预处理和语法制导的解析，提取所需静态信息(即安全编程规则所涉及的所有代码信息)，构建关系语法树，并根据制定的XML中间模型生成XML文件；具体如下： 

1)预处理模块：完成对源代码文件的宏替换功能，该功能的实现借用G++的预处理器辅助完成。预处理后将生成.i文件。 

G++预处理将执行源代码中的所有预处理指令。由于源代码中的所有预处理指令均是规则检测的对象，所以我们需要将所有的预处理指令重新恢复到源代码文件中。同时，由于文件包含指令的执行，使源代码文件中被引入了大量的代码，尤其是引入了大量的C++标准库文件，但这是标准库文件中的代码并不是我们检测的对象，需要从将其删除。 

预处理模块首先将源代码文件读入内存，对源文件中的特殊区域添加标记，标记添加的原则是：标记只分为两种，BEGIN与END；BEGIN与END之间的内容是需要从后续的.i中恢复的内容；标记之外的内容是源代码中的所有预处 理指令。 

系统通过调用G++-E-C对添加了标记的代码文件进行预处理，生成含有标记信息的.i文件。通过分别从添入标记的源代码文件和带有标记的.i文件中分别提取相应信息，即可获得符合规定的预处理后的文件。其中，从添入标记的源代码文件中提取出所有预处理指令及它们在源代码文件中的各自的行号，从带有标记信息的.i文件中提取两个标记之间的所有代码。 

2)源代码解析模块：主要完成对源代码文件的转换，即将源代码文件转换成为XML文件。源代码解析模块按照功能可划分为词法分析模块、语法分析模块和XML生成模块。代码解析器以LEX、YACC描述脚本构造词法分析器和语法分析器，对通过GCC编译生成的.i文件进行解析，从中识别出代码类型、文本、行号以及变量、函数声明等数据信息。这些信息被存储在系统内部临时“数据池”中，经XML生成模块的处理，依据设计的XML中间模型的结构，将解析出的数据信息存储在XML文件中。 

系统后端漏洞检测模块：负责对系统前端生成的特定格式的XML文件执行规则检测。安全规则库中存储着安全规则，针对已经转换为XML中间文件的检测对象，规则以适宜检测XML文件的一种形式存储在安全规则库中。规则配置文件中存储每次规则检测时用户进行的一些系统配置信息。系统后端通过读入XML中间文件、规则配置文件以及安全知识库，输出检测结果。 

2、基于关系存储模式的关系语法树的构建 

鉴于GCC编译产生的AST文本中含有大量的静态检测价值极低的冗余信息，因此需要利用Lex、Yacc对源代码进行解析，对产生冗余信息的语句进行特殊处理。例如：对于源代码文件中的文件包含预处理指令，在关系语法树模型中，该指令对应一个普通节点。节点只记录该语句的文本内容和在源代码文 件中出现的位置信息，摒弃其对应的头文件的内容。通过类似的处理，去除绝大多数的冗余信息，继而降低后续信息提取的难度并提高信息检索的精度。 

编译器以源程序的过程为单位生成抽象语法树，语法树构造算法为过程中每一种语句构造定义相应的运算符，并以运算符作为树的内部节点。对于以关键字开头的构造，使用这个关键字作为对应的运算符。加减乘除等数学算法作为数学子表达式的运算符。 

关系存储模式根据终结符之间的依存关系建模，内部节点去除数学运算符，增加表达式、标识符等运算符。对于以关键字开头的构造，仍然使用这个关键字作为对应的运算符。表达式语句不以某个关键字开头，故定义一个新运算符expression表示表达式语句，用叶子节点null表示一个空语句序列。标识符的运算符分为variable、function等。树的节点之间存在父子或兄弟关系，使用相关指针进行链接。根据静态检查需要，分别生成ID树与STMT树。ID树存放词法单元的属性集，STMT树存放各类语句的语法结构信息。 

语法树构造算法的基本思想如下：给定文法G和Statement(语句)流s，记s＝s₁s₂...s_n(其中s_i∈VT，i＝1，2...n)，s_i＝t_1it_2i...t_mi(其中t_ki∈VT，k＝1，2...m)；识别器自左向右扫描s，每扫过一个t_ki，执行一个状态集P_i(P_i∈P)，其中每个状态形如＜A→α·β，Tree_id(t_i，d)，Tree_code(s_j，h)＞，A→α·β表示α为已分析部分，Tree_id(t_i，d)表示ID树当前最后加入节点为t_i，Tree_code(s_j，h)表示STMT树当前最后加入的节点为s_j，d等于ID树节点当前深度，h值指示STMT树语句块的当前嵌套层次，|d-h|≤1。 

其中，VT为非空终结符集合，VN为非终结符的非空集合， 为运算符集合，V_t”为非运算符集合， V_t’∪V_t”＝VT，CFG(上下文无关文法)G＝(VN，VT，S，P)，S∈VN，是文法G的开始符号，P是产生式集合： 

P＝{A→α|A∈VN，α∈(VNUVT)*}    (1) 

设VN中所有的非终结符A都可定义一个CFG GA＝(VN，VT，A，P)，其中A称为开始符号，GA产生一个上下文无关语言L(GX)，则L(GX)中的每个句子w对应一棵派生树，派生树也称生成树、分析树、语法树。 

设有CFG G＝(VN，VT，P，S)，G的语法树是满足如下条件的有序树：树的每个节点有一个标记X，且X∈VN∪VT∪{ε}，ε表示空；树根的标记为S，S∈V_t’；如果一个非叶子节点v标记为A，v的子节点从左到右依次为v₁，v₂，...，v_n，并且它们分别被标记为X₁，X₂，...X_n，则A→X₁X₂...X_n∈P；如果X是一个非叶子节点的标记，则X∈V_t’；如果一个节点v标记为ε，则v是该树的叶子，并且v是其父节点的唯一子节点。 

3、XML中间模型的建立 

将关系语法树以XML格式存储，构造XML中间模型。XML中间模型的设计包括以下几方面： 

1)XML文件模型 

XML模型需具备良好结构，且XML模型中各节点和属性项的含义均具有确定性和唯一性。通过对C++安全规则中所提取的具有检测价值的静态属性进行分析，使用XML Schema构建如附图3的XML文件模型的结构。 

每个关系语法树在XML中间模型中均对应一个SOURCEFILE节点，SOURCEFILE节点是XML模型的顶层节点，具有两个属性：文件路径(FILEPATH)和文件类型(FILETYPE)。 

XML文件模型下引出四个子模型：头文件引入模型(FILEINCLUDE)、注释信息模型(COMMENTS)、语句结构模型(CODELINES)、标识符信息模型(INDENTIFIERS)。 

头文件引入模型存储关系语法树中文件包含语句的信息，包含文件可能是用户自定义文件或系统文件，通过设定FILEINCLUDE的属性节点TYPE来区分包含文件的不同类型。 

注释信息模型以语句为单位集中记录所有注释内容，源代码中每行注释都映射为一个CODELINE子节点。 

语句结构模型以语句为单位结构化地描述代码组织形式，源代码中每条语句映射为一个CODELINE子节点，使用SUBLINE标签划分嵌套子语句。 

标识符信息模型记录文件中定义的标识符信息，包括所有变量、函数名、类名及标号等，每个标识符生成一个相应的ID子节点。 

2)语句结构模型 

语句结构信息以C++语言语句为单位，能够体现源代码中每一行代码的具体含义及其所在行的上下文环境信息。源代码中每一条语句在XML中间模型中都对应一个CODELINE节点。每一个语句信息单元需要包含语句类型、行号、语句文本及可选的子语句信息。语句结构模型用WSDL表示如附图4所示。 

所有语句在XML中间模型中均映射为一个CODELINE节点，包含属性节点CODETYPE和LINENUMBER，以及节点CODETEXT和可选节点SUBLINES。复合语句以SUBLINES为父节点进行扩展，内部嵌套的多条语句统一置于子节点SUBLINES下。语句结构模型的XML Schema结构具体设计如下： 

A.语句类型：CODETYPE 

XML中间模型将C++语句类型划分为76类，使C++语言中的所有语句均有一个唯一的名称。 

B.行号：LINENUMBER 

系统在检测出违反安全规则的软件缺陷后，需要向用户提供源代码中违反规则的缺陷所在行号。 

C.语句文本：CODETEXT 

某些规则的实现需要通过正则表达式分析语句文本，例如规则中禁止使用二合字母词，所以XML中间模型用专门节点标记语句文本。 

D.子语句：SUBLINES 

SUBLINES通常含有大量CODELINE子节点，代表复合语句中的子语句。 

3)标识符信息模型 

标识符信息模型描述源代码中标识符的属性集和作用域信息。XML中间模型中，源代码定义的每个标识符都映射到IDENTIFERS节点下的一个ID子节点，ID节点的每个属性节点和子节点记录了对应标识符的名字、类型、存储类型等信息。标识符信息模型用WSDL表示如附图5所示。 

标识符信息模型详细设计如下： 

A.标识符类型：IDTYPE 

在源代码中，标识符可能是变量名、函数名或者是自定义类型等，通过设定属性节点IDTYPE区分不同标识符。IDTYPE可取值包括、量、函数定义、类、类模板等35种类型。 

B.行号：LINENUMBER 

ID的属性节点，记录标识符第一次出现的位置。ID含有许多子节点，均作为可选项，是否使用由IDTYPE以及标识符在源代码中的上下文环境而定。 

C.名字：NAME 

记录标识符的名称。 

D.类型：TYPE 

可选子节点TYPE根据IDTYPE的取值不同具有不同的含义，可以使变量声明的数据类型、函数返回类型或结构类型等。 

E.存储类型标识：STORETYPE 

该节点只应用在变量和函数中，用于记录变量和函数在声明时的存储类别。 

F.赋值记录：ASSIGNMENT 

记录变量初始化值以及初始化后的再赋值，记录项之间使用分号隔开。 

G.常量：CONST 

用于记录类的成员函数是否是被const修饰的常量成员函数，写在函数的最后来修饰。XML中间模型中，CONST节点不用于指示普通常量。 

H.访问标号：ACCESS 

记录类、结构体和联合体成员的访问标号。ACCESS有private、public、protected三个取值。 

I.所属结构：OWNER 

记录类、结构体、联合体和命名空间成员的所在类、结构体、联合体或命名空间的名称。 

J.虚函数标记：VIRTUAL 

用于指示类成员函数是否是虚函数。 

K.运算符重载：OPERATE 

用于记录C++中可重载的42种重载操作符。 

L.参数：PARAMETER 

记录函数定义和声明的参数信息。函数参数列表的每个参数项都被映射为PARAMETER节点下的一个ID子节点，按参数顺序存放。 

M.域：FIELD 

复合语句中定义的变量是局部变量，XML中间模型中使用FIELD记录这些变量，变量的可见域不超过所属FIELD块的作用域。 

N.基类：PARENT 

记录派生类继承自哪些基类。PARENT节点有一个用于记录类派生列表中派生类对每个基类的继承权限的属性节点。 

O.模板：TEMPLATE 

记录模板定义和声明的模板参数信息。模板参数列表的每个参数项都被映射为TEMPLATE节点下的一个ID子节点，按参数顺序存放。 

本发明的有益效果是： 

(1)高效性：在遵守XML中间模型定义的前提下，可实现系统前端静态信息提取和后端漏洞检测模块的并行开发。 

(2)面向对象语言的可扩展性：由于XML中间模型与检测语言和开发平台无关，在检测由其他编程语言开发的软件时，只需更换与开发语言适应的系统前端解析器，即可实现特定语言的源代码静态检测，具有多语言可拓展性。 

(3)支持《MISRA C++2008》安全编程规范：本发明对软件安全缺陷检测的实现建立在《MISRA C++2008》安全子集的基础上，适合用于安全苛刻性系统，如航空航天软件系统、医疗系统、汽车电子系统和核工业系统等，对《MISRA C++2008》具有良好支持性。 

附图说明

图1是本发明的系统架构图。 

图2是预处理模块的执行流程图。 

图3是XML文件模型的结构示意图。 

图4是语句结构模型用WSDL表示结构示意图。 

图5是标识符信息模型用WSDL表示结构示意图。 

图6是ID树结构示意图。 

具体实施方式

以下结合技术方案和附图，详细叙述本发明的具体实施方式。 

下面的算法1描述了语法树的产生过程。 

算法1. 

输入：CFG G＝(V_N，V_T，S，P)和语句流Statements＝s₁s₂...s_n，其中s_i＝t_1it_2i...t_mi. 

输出：Tree_id和Tree_stmt

过程：RST_ree(G，s) 

1 begin 

2 

3 procedure CreateStmt{构造Stmt树} 

4 for i：＝1 to n do 

5 procedure CreateId{构造Id树} 

6 for j：＝1 to m do 

7 begin/^*begin of CreateId^*/ 

8 on current state P_k：＝＜A→αXβ，Treeid(t_y，d)，Tree_stmt(s_i-1，h)＞ 

9 gettoken； 

10 if d≠h then 

11 d＝h； 

12 if X∈V_N then 

13 goto P_h(P_h∈P，h≠k)：＝＜X→η，Tree_id(t_y，d)，Tree_stmt(s_i-1，h)＞ 

14 else if X∈V_T’and X＝t_ij then 

15 createIdLeaf(Tree_id(t_y，d)，X)； 

16 set Tree_id(t_ij，d)； 

17 else if X＝t_ij and X∈VT’or X∈VT”’and X＝‘{‘then 

18 d＝d+1； 

19 else if X∈VT and X＝‘}‘ 

20 d＝d-1； 

21 else if Xβ＝εthen 

22 break； 

23 j＝j-1； 

24 end/^*end of CreateId^*/ 

25 begin/^*begin of CreateStmt^*/ 

26 CreateId； 

27 createStmtLeaf(Tree_stmt(s_i-1，h)，s_i)； 

28 ifh≠d then 

29 h＝d； 

30 i＝i-1； 

31 end/^*end of CreateStmt^*/ 

32 end/^*end ofRSTree^*/ 

给定如下所示的输入语句流s： 

s0：static int findMax(int arr[30]) 

s1：{ 

s2：int max＝arr[0]； 

s3：for(int i＝1；i＜30；i++) 

s4：max＝(arr[i]＞max)？arr[i]：max； 

s5：return max； 

s6：} 

s经过语法树构造算法1的运算后，分别生成了附图6(a)所示的STMT树和附图6图(b)所示的ID树。分析可知，关系语法树拥有节点11个，包括两个头指针节点Tree_Stmt和Tree_Id。但若将输入s使用G++生成传统抽象语法树，分析其语法树文本GXL，可发现语法树的节点数达到了20万多个。可见，基于关系存储模式的关系语法树有效简化了传统语法树的规模。 

根据技术方案要点3所述的XML中间模型结构，输入语句流s的关系语法树以XML格式存储，经XML生成模块的处理，最终转换为如下的XML文件：