面向c语言的静态分析

面向c语言的静态分析

0基于符号执行的软件静态测试方法随着软件产业的发展，恶意软件已成为一个焦点。软件测试分为动态测试和静态测试。静态测试是不执行程序代码而寻找程序代码中可能存在的缺陷或评估程序代码的过程,程序静态测试的目标不是证明程序完全正确,而是作为动态测试的补充,在程序运行前尽可能多地发现其中隐含的错误,提高程序的可靠性和健壮性。符号执行通常也被理解为符号预测,属于静态测试方法的一种,其基本思想是:将程序源代码中变量的值采用抽象化符号的形式表示,模拟程序执行,其适用于在对路径敏感的程序分析中。通常意义下的程序执行是给出具体的输入数据使得程序能够沿着某一特定路径执行并输出与之对应的具体结果。然而符号执行的目的是分析程序中变量之间的约束关系,不需制定具体的输入数据,将变量作为代数中的抽象符号处理结合程序的约束条件进行推理,结果是一些描述变量间关系的表达式。在符号执行的过程中,CFG中的分支导致了对于变量的不同的约束条件,而这些约束条件就描述了相应路径的测试数据间的约束关系。符号执行和约束求解方法的研究产生了基于符号执行和约束求解的测试用例产生标准和方法。文中利用现有的技术提出了一种改进的基于符号执行的软件静态测试方法,该方法根据C语言的文法,可对程序中潜在的错误进行报错。利用该方法中抽象语法树,可开展静态构架分析,同时利用约束求解工具完成了对于可执行路径的自动判别,最终得到程序按可执行路径运行后的符号执行结果。1基于c语言语法树的块的特征分析流程符号执行技术是一种融合了敏感性路径分析、抽象解释等理论的方法。因此其非常适合对路径敏感的程序源代码进行软件静态测试。文中实现了符号执行的静态分析工具SES,由解释分析和符号执行两个模块组成。解释分析模块完成读取程序源代码,提取程序中的信息要素的功能,主要由词法分析、语法分析、抽象语法树构成;符号执行模块主要功能是借助于约束求解器对抽象语法树进行遍历,完成对路径的符号执行,符号执行阶段由路径条件的约束求解和路径的符号执行构成,图1所示为其工作流程图。具体的分析流程如下:步骤1:将被测代码输入测试工具中;步骤2:根据C语言文法自定义一个关键词列表,并对照关键词列表对被测试代码进行词法分析;步骤3:根据C语言文法自定义函数结构模块、构造抽象语法树的生成算法,并对照词法分析的结果,利用“自下而上”的方法(即从语法树的末端开始,步步向上“归约”),对被测代码进行语法分析,最终得到程序静态分析树(PAT)作为一个中间表示形式,并且利用文档进行存储;步骤4:根据步骤2中的词法分析结果,以特定结构体的形式(包含变量名称及变量的符号值)建立变量列表、以链表的形式存储当前路径条件(便于回溯);步骤5:根据分析步骤3中的语法分析结果,对抽象语法树进行中序遍历,同时对变量列表中变量的符号值进行替换;将步骤4中存储的路径条件进行约束求解得到可执行路径,并且依照算法得到每个变量最终的符号执行结果,最终以文本的格式保存。2执行符号执行算法2.1小型、混合语言的语法分析解释分析模块是符号执行阶段的基础,主要功能是通过预处理、词法分析和语法分析等操作生成程序的抽象语法树。过去的经验是采用GCC等成熟编译工具,但这些工具的使用比较繁琐,在此借鉴现有的编译技术实现小型的词法语法分析,并用此生成抽象语法树。抽象语法树作为语法分析的中间结果表示方式,其构造过程是伴随着语法分析过程进行的。这里针对图2所示代码,并结合语法分析,重点对程序中循环语句结构while语法树的构造进行讨论。1提取运算符本例中运算符分别为“<”、“=”、“+”,以“a<5”为例进行描述。由语法分析算法可知,首先分析到运算符“<”的左操作数“a”,通过函数F1()分析其类型后,利用函数SyntaxTree建立一个根节点为“<”,子节点为null;其次分析运算符,先利用函数SyntaxTree建立一个根节点为“<”运算符,子节点为空的语法树,之后利用函数addLeft将左操作数“a”语法树作为该“<”语法树的左子树;最后分析“<”运算符的右操作数“5”,以“a”同样地方式建立“5”语法树并用函数addRight将“5”语法树作为“<”语法树的右子树。注意若运算符的左右两端不是操作数而是一个运算符表达式,则对左右两端需按照上述的运算符AST生成算法分析后再加入到运算符语法树左右子树中,即该运算符语法树的左右子树仍然是一个运算符AST。2循环条件及其生成利用函数SyntaxTree建立一个根节点为while,子节点为空的语法树;其次分析作为其左子树的循环条件表达式,该循环条件表达式可依据1)所述的算法获取,其对应的AST通过函数addLeft添加到while语法树的左子树中;最后分析作为其右子树的循环体,该循环体中包括两个运算符表达式,则可先依据1)所述的算法获取其对应的AST,并将其作为根节点为blk的语法树的左右子树,之后将blk语法树通过函数addRight添加到while语法树的右子树中。3非终结符号生成算法本例中非终结符号block只有一个,因而其AST生成算法即是关键字while的AST生成算法。若程序中在while循环语句下面仍然存在一条赋值语句,则存在另一个非终结符号block的抽象语法树,其算法可以参照1)所述。至此循环语句while的AST如图3所示。2.2结构体系统的路径规划符号执行模块是核心模块,其主要功能是结合对路径条件的约束求解对解释分析阶段得到的AST进行遍历,并在此过程中完成路径的符号执行。路径条件的可满足性判断主要通过对路径条件的约束求解来完成,具体实现定义了两个重要的结构体:结构体Symbol主要是用来保存程序变量及其符号表达式(初始化变量的符号值时,默认为与变量名相同)。借助于以结构体Symbol为节点的链表为该变量创建一个栈SymbolStack。将保存有变量的符号值的节点入栈作为栈顶元素,如果在符号执行过程中,程序语句涉及了该变量的引用,就从该变量的栈顶元素中取出其符号值;如果程序语句中该变量被重新赋值,就将保存有变量的当前符号值的新节点入栈;每次涉及到回溯,只需将保存含有变量最近一次被修改的符号值的栈顶节点出栈,从而满足符号执行过程中对于变量信息提取操作的需要。结构体PathNoder主要用于保存各类程序路径条件信息,借助于以结构体PathNoder为节点根据词法分析的结果用一个链表(便于回溯)表示的栈cur_pc来存储当前的路径条件,链表的节点是一个转换条件,条件之间是合取关系。得到当前的路径条件后用求解工具lp_solve对路径约束条件进行求解,来判断是否为可执行路径,将路径约束的求解问题转化为在路径约束变量上的先行规划问题。之后将变量列表SymStack中属于可执行路径的变量赋值记录进行处理。路径的符号执行完成对程序中可执行路径的遍历并追踪更新相关过程中变量值的符号表达式。以下将基于C语言程序中的语句结构并依照符号表达式创建与更新的顺序,对路径符号执行算法展开具体讨论:1)声明语句。对程序变量和数组的声明操作,也是为程序中变量创建相应的符号表达式的阶段。2)赋值语句。设计合理的递归遍历算法,具体采用中序遍历的方式,得到中缀表达式。针对变量值的符号表达式进行查找和替换,利用变量列表中每个变量对应的栈中信息,完成对赋值语句左侧表达式中变量的符号表达式的更新。3)函数调用语句。先保存当前程序中各种数据信息,并找到调用函数在程序中的位置,对其进行符号执行。当被调用函数分析结束后返回其函数摘要,继续原过程的分析。例如程序中存在函数声明为intFun(intx,inty)的函数,其调用处理详细说明如下:在解释分析层中,当检测到函数名为Fun,则会以结构体FunctionNode的形式为该函数创建节点,并将函数名(Fun)、函数的返回值(int)的类型以及函数中的形参列表(intx,inty)保存到此结构体相应的成员变量之中。这里假设函数Fun声明在main主函数之前。先在解释分析阶段为该函数建立一棵语法树Fun并进行初始化操作,利用抽象语法树生成模块归约出函数Fun所对应的完整语法树;之后沿着main函数中可执行路径依次完成对路径的符号执行,当遇到函数Fun的调用点,则利用已有算法遍历其对应的语法树Fun,并以实参与形参一一对应的方式,将变量列表m_SymStack中相应变量的当前符号值赋值给函数Fun的形参,之后便是采用与之前符号执行层所设计的相同方法对函数Fun内的路径进行符号执行,并最终将函数Fun的返回值赋予被调用处的语句。3符号型的验证图4左侧所示为测试用例Example2,利用工具SES对其进行测试。图4右侧是Example2的符号执行测试结果。通过观察可以发现变量c的符号表达式为(((a*b+1)*b+1)+b),而手动代码组查后得到的变量c的符号值为(a*b*b+2*b+1),通过比较这是一致的,验证了符号执行阶段算法设计的正确性,并且可以发现条件判断语句if(a<b+1)后的语句块没有被执行(为不可执行路径),验证了路径条件的约如表1所示,可以清楚看到Example2变量的符号表达式的形成过程,其中p表示执行程序某分支的路径选择条件,p1为(i<2),p2为(!(a<b+1))。借助于被测程序符号执行后的结果,即源代码中所有变量的符号值与手动计算结果相比较。测试人员可以通过对变量的符号值分析,在检验程序运算规律的基础上进一步了解变量间的约束关系,从而对路径敏感的程序设计测试用例时,可以基于这些描述变量间约束关系的表达式,设计出有效的、尽可能覆盖更多程序路径的测试输入。4模型求解算法设计及注意事项文中对符号执行技术应用与程序源代码的静态结构分析进行了研究,设计了符号执行的静态分析工具SES。基于C语言文法及编译原理构造了小型语法、词法分析模块,在分析过程中以叶子节点步步推进至根节点的思路,构造了抽象语法树生成算法。在符号执行阶段采用了灵活的信息提取机制对程序中信息进行实时处理与更新,采用了回溯方法完成对程序路径约束求解问题的