空指引引用错误例解

空指引引用错误例解

指针是c、c.+和其他语言的灵活增加，但指针使用不充分会导致程序错误和安全隐患。其中,空指针引用(nullpointerdereference,NPD)是一种最常见的指针使用不当的表现。NPD错误不仅会导致程序崩溃,有时还可能成为安全漏洞。据中国国家信息安全漏洞库统计,由NPD错误造成的安全漏洞每年有70个左右被报告出来,这些漏洞甚至出现在Linux、WindowsServer、VMware、Apache等重要的基础软件中,造成拒绝服务、非法权限提升、执行任意代码等严重安全问题。一种直接预防NPD错误的方法是在每条指针解引用语句之前加入判断语句,确保指针不为空时再执行解引用操作。该方法虽然保险,但也会带来一些问题:1)在多线程执行的程序中有时并不有效目前的错误检测方法分为动态检测和静态检测。动态检测难以保证100%的代码覆盖率,且输入样例难以构造;静态检测则在代码覆盖率方面有优势,检测错误时更有针对性。在技术方面,静态检测除了传统的流分析,还常常与程序验证、模型检测、定理证明、符号执行等技术相结合,以获得更高的检测精度使用静态方法检测NPD错误是近年来研究的重点。Xie等综上,目前的工具和方法还有如下问题:要么过程间分析不完整,要么开销巨大;过程内分析不精确,路径覆盖率不够或者指针指向估计不准;对涉及调用库函数的代码普遍分析不准;无法解决由exit等函数造成的特殊控制流问题针对这些问题,本文提出一种过程内流敏感、路径敏感和过程间上下文敏感的多敏感NPD错误静态检测方法。该方法结合传统静态分析方法和符号执行方法,按照程序执行的顺序进行分析,记录并推断指针变量的指向信息,采用一种折中的路径敏感分析方法,在函数内进行路径遍历,将路径上的分支条件和指针信息转换成约束表达式,并用约束求解器求解可满足性来判断路径是否可达;利用在函数退出点进行信息合并的方法减少信息记录的数目,并减轻不能跨函数路径遍历造成的精度损失。另外,对没有源代码的库函数以及部分普通函数使用人工标注错误触发条件的手段,提高分析精确度和效率。与符号执行方法相比,本文方法减少了计算量和信息记录数量。实验证明该方法分析时间短、资源消耗少、检测精度高。1有限状态机fsm根据出错指针的可见域及其定值和解引用位置,NPD错误的具体形式可以归结为4种类型,分别是:1)局部变量为NULL;2)全局变量为NULL;3)函数参数为NULL;4)函数返回值为NULL。在实际编程中,特别是当使用他人编写的接口或者库函数时,后两种错误形式更易发生且更难检查。4种NPD错误代码的示例如图1所示。NPD错误仅与指针的指向有关,与其他类型变量的取值无关。为提高分析效率,本文方法只对指针类型变量(包括全局指针、局部指针以及作为函数参数的指针)进行建模,忽略其他类型的变量。本文用有限状态机(finitestatemachine,FSM)表示NPD错误模型。在检测NPD错误时,只需知道指针是否为空,所以指针的指向状态可简化为“空(Null)”和“非空(NotNull)”两种状态,考虑到静态分析的不确定性,再添加一种“可能为空(MayBeNull)”的状态。该FSM有{Null,NotNull,MaybeNull,MayBeError,Error}5种状态,其中Null是起始状态,MayBeError和Error为终态,完整的状态转换如图2所示。该FSM状态转换条件如表1所示。检测时每个指针变量都要记录一个FSM。全局指针在声明后会默认初始化为NULL,而局部指针变量在声明后根据内存栈上的当前值指向一个随机的地址。无论是指向NULL,还是指向随机的地址,此时对指针进行解引用都是不正确的。为减少状态,假设局部指针在声明时也默认初始化为NULL。因此,本文指定FSM的初始状态为Null,当某个FSM的状态变为Error或者MayBeError,则说明检测出了一个NPD错误或者可能的NPD错误。2路径敏感的分析方法在程序内,一条分支语句会形成两条可执行路径。随着分支语句的增多,组合后的可执行路径数量将呈指数级增长。图3是包含多路径程序的一个例子。其中,图3(a)代码对应的控制流图如图3(b)所示,两条分支语句组成“真-真”、“真-假”、“假-真”、“假-假”4条路径。路径不敏感的方法不区分路径,在分析到第9行时会认为p可能为空,然后对第10行报告NPD错误。这是一个误报,因为分析可知,要触发该NPD,需要执行“假-真”路径,但因为a不能既等于0又不等于0,所以“假-真”路径实际上不可能被执行。路径敏感的方法区分不同路径,同时考虑分支条件组合,可以避免该类误报。路径敏感的方法记录所有路径的信息,分析结果精确,但也面临路径组合爆炸的问题。为避免路径组合爆炸并减少误报,本文提出一种新型的路径敏感的分析方法。本文方法分析函数内路径的可达性并剪枝,只分析可达路径上存在的NPD错误,最后在函数退出点将多条路径的信息合并成一条,供调用函数使用。2.1路径可达性分析本文方法使用约束求解的方式计算路径可达性,剔除不可达的路径,以减少分析量,提高检测精度,减少误报。本文方法按照深度优先遍历函数控制流图(controlflowgraph,CFG)的顺序来分析函数。分析过程中需要记录从程序起点到当前分析的基本块之间的路径。每当分析完一个基本块并将要开始分析另一个基本块时,需计算路径的可达性。方法是将路径上的分支条件组合成一条布尔型的约束表达式,并用SMT-Solver求解该表达式的可满足性,若可满足则认为该路径可达。如图3(a)中的函数foo有5个基本块,图3(b)上已编号1~5。当分析路径为1→2时,即分析到第一个if的真分支,路径可达性表达式为a!=0,该表达式可满足,说明该路径可达。当分析路径为1→3→4→5(即“假-真”路径)时,则路径可达性的约束表达式为(a==0)&&(a!=0),由于该表达式不可满足,就说明该条路径不可达。当判断出某条路径不可达时,就放弃分析该条路径及由该路径向后延伸的路径。与符号执行的方法不同,由于本文方法只对指针建模,所以在分析时无法估算其他类型变量的范围。在建立路径可达性表达式时,如果分支条件中包含指针变量,则使用分析值替换变量(MaybeNull既可以是空,也可以非空),对于分支条件中其他类型的变量,不对其范围进行限制。2.2路径敏感的检验如果有多条可达路径会对函数下文造成更改(即修改了全局指针指向,通过函数参数中的高维指针修改了低维指针的指向,返回指针变量供调用函数使用),且更改不同,则需要在函数退出前进行信息合并。对某个指向会被修改的指针变量p,具体的合并规则如下:1)如果每条路径上都有修改且修改均为Null,则改为Null;2)如果每条路径上都有修改且修改均为NotNull,则改为NotNull;3)如果有某条路径上的修改为MayBeNull,则改为MayBeNull;4)如果p之前状态不为Null,有但不是所有路径上的修改为Null,则改为MayBeNull;5)如果p之前状态为Null,有但不是所有路径上的修改为NotNull,则改为MayBeNull;6)其他情况不做修改。比如某全局指针开始时的状态为Null,函数中有两条执行路径,一条路径上将状态改为了NotNull,而另一条未做修改,则根据上述规则5),在函数退出时将状态改为MayBeNull。因此,分析后面的程序时,如果直接出现对该指针的解引用,可以发现一个可能的NPD错误。路径敏感是可以跨函数的,对于有多条可执行路径的被调函数,要将所有路径的信息单独记录下来再回到调用函数去分析,该方法精确,但开销巨大。文献[7,9]中使用“可能指向”来表示多条分支对指针指向修改的不同,但它们的方法是路径不敏感的,等价于分层而不是深度优先遍历CFG,即每次分析一个分支语句,待分支汇合后再继续分析后面的程序,相当于每分析一个分支就进行一次信息合并,如果此时将某指针指向设为“可能为空”,且之后分支中出现该指针的解引用,则无法确定NPD错误是否发生在可达路径上。本文方法选择在函数退出点进行信息合并,相比不合并,本文方法开销更少,且精度相差不多,相比每个分支后合并,可以降低误报。3过程前后的性能敏感指针为参数或者返回值的函数普遍存在,分析这类函数中的NPD错误必须考虑函数被调位置的上下文。上下文不敏感的方法一般不考虑这些因素,如图1(c)中的foo函数,上下文不敏感的方法会对foo报告一个潜在的NPD错误,条件是假设foo的参数s可能为空。但如果程序中所有调用foo的位置传入的均不是空指针,就是误报。为减少误报,本文提出一种新型的上下文敏感的分析方法。本文方法在分析函数调用时将指针指向传递给被调函数,而当分析无源代码的库函数调用时,根据事先人工标注的行为进行处理。分析函数调用时的处理流程图如图4所示。3.1被调函数的位置分析被调函数时,首先记录主调函数的分析位置,然后向被调函数传入指针类型实参的状态,并跳转到被调函数进行路径敏感的过程内分析,分析完成后再跳回到主调函数之前记录的位置继续分析。如果被调函数返回指针,则将返回的指针状态传递给主调函数中接受返回值的变量。例如图1(c)中的代码,分析到第6行的foo(a)时,有一个局部指针a,其状态为Null。将a的状态作为实参传给foo,之后开始对foo函数进行分析。在foo中,有一个可见的指针,即其形参s,其状态与之前传入的实参相同,为Null。继续分析到第2行,在该处对s解引用,根据FSM转换规则,s的状态机变为Error,即发现一个NPD错误。3.2静态分析时程序的标定当被调函数为库函数或者内嵌函数(built-in)时,无法定位源代码。本文的做法是对这些函数事先进行人工标注,标注内容包括该函数是否返回空指针和触发该函数中NPD错误的条件。比如malloc函数通常会返回非空指针,但在内存不够分配时,会返回空指针,所以将malloc的返回值标为MayBeNull,在分析时如果遇到malloc函数调用,则直接将获得其返回值的指针变量状态设为MayBeNull。又比如计算字符串长度的strlen函数,在参数为空指针时就会触发NPD错误,所以将strlen函数的NPD错误触发条件标记为参数为空指针,在分析时如果遇到strlen,则直接判断实参指针的状态是否为Null或者MayBeNull。除了解决没有源代码的问题,本文还利用人工标注信息解决特殊控制流的问题。exit、assert等函数会改变程序正常的执行流,当程序执行到exit时就会退出,不再执行后面的代码。静态分析方法如果将这些函数当成普通函数继续分析,则不能得到正确的分析结果。本文的做法是对exit等影响程序正常执行的函数进行标注,分析中一旦遇到这些函数,就终止分析当前路径,并回溯到路径分叉点开始分析新路径。另外,人工标注还能减少分析工作量,对于普通的函数,即使有源代码,也可进行标注。分析已标注的函数时,可直接使用标注信息,不用再分析该函数,类似于提取函数摘要4实验与分析4.1真实工程检测方法评价使用LLVM编译框架从发现错误的能力和对真实工程的测试情况两方面对检测方法进行评价。使用Splint和ClangStaticAnalyzer作为比较对象。4.2执行程序中的误报测试工具检测能力的样例来自SAMATEReferenceDataset(SRD),该数据集由包含错误和漏洞的程序组成,被设计用于检测程序分析工具的能力。本文从SRD中选择了7个具有代表性的样例,每个样例包含1个真实的NPD错误以及若干个用来测试误报的“伪NPD错误”。3个工具对测试样例错误的检测情况如表2所示。由于Splint和ClangStaticAnalyzer可以检测多种错误,本文只统计其报告的NPD错误。同一个位置的NPD错误报告均按1次统计。需要说明的是,原始的34667号样例使用printf打印字符串触发NPD,但打印字符串空指针是未定义行为(undefinedbehavior)由表2可以看出:对所选的7个样例程序,NPD-Checker没有漏报,且误报很少,只在一个测试样例上出现了误报;Splint出现了较多的误报和漏报;ClangStaticAnalyzer则出现了一半漏报。ClangStaticAnalyzer漏报主要是因为对库函数调用的分析不准。比如对38733号样例,其没考虑到fopen可能返回NULL,以及fclose在接受NULL作为参数时会发生NPD错误;对38772和38997号样例,其没有考虑到calloc分配内存失败会返回NULL。Splint相比ClangStaticAnalyzer分析能力较弱,但是其约束条件较松,可将很多可能的NPD错误报出,减少了漏报,但增加了误报。Splint的误报主要是因为其只进行函数内分析,不进行跨函数分析,并且在函数内分析时没有考虑路径可达性。比如对38772号样例,其认为对goodB2G_sink函数传递空指针会触发NPD,但goodB2G_sink函数会先行判断指针是否为空。对34667号样例,程序在一个if语句的假分支中将指针设为NULL,在分支之后解引用,但分支条件是一个恒为真的表达式,所以不可能发生NPD错误。NPDChecker之所以会出现误报是因为本文方法只对指针建模,没有对其他变量建模。对34667号样例,由于if语句中的条件表达式是关于整形变量的,所以没有计算其范围,在使用SMT-Solver求解可满足性时约束太松,导致真假分支均可满足,所以产生了误报。4.3不同算法的analyze几个常见的开源代码的行数统计以及两个工具对它们的分析结果如表3所示。测试时没有使用Splint作为比较对象,主要是因为Splint只进行过程内分析,理论时间与另外两个工具不是一个数量级,且误报太多,对比性不强。从表3可以看出:1)NPDChecker检测时花费的时间小于ClangStaticAnalyzer,这是因为本文方法只需要记录指针变量的信息,且状态少,而ClangStaticAnalyzer使用符号执行的方法,需要计算各种变量的范围,计算量大。2)NPDChecker有几个误报,误报数量比ClangStaticAnalyzer稍多。分析代码发现这些误报均为不可达路径上的错误,误报原因如前所述。分析ClangStaticAnalyzer的检测结果后可找到一个有