关于静态分析工具误漏报的思考

作者:胡婉莉

      漏报率通常是用户在选择静态分析工具时的重要考察参数,然而漏报往往很难被发现。低漏报意味着分析工具必须尽可能的覆盖更多程序执行路径,然而这些执行路径中有一些是在实际程序执行中一定不可达的执行路径,这样就会引起一些误报,即会降低工具的准确度。
      用户通常希望分析工具的漏报率尽量低,尽可能的精准,而且需要能测试尽可能大的工程。然而,在实际的工程测试中,出于效率上的折衷,现有的静态分析工具经常会有意放弃更多路径的执行以牺牲漏报来换取低误报率。比如忽略复杂的语言特性以换取更高的准确度和更快的速度,更小的负荷等。下面举例来说明。

            

      对于上面的例子。如果要考虑完全,则必须分别考虑a[0]=100,a[1]=100,a[2]=100… 的情况。这无疑极大的降低了效率,增大了资源占有率。
      因此,在实际静态分析工具开发中。一方面,对于常见的语言特性会考虑的很完善,当遇到难以选择的多条路径(条件判断的多个分支,多条数据流)时,就逐条路径加以分析以保证准确度;另一方面,对于有些复杂的语言特性,因为如果完全充分的分析这些特性,误报会高到不可用的程度,或者导致效率大幅下降,所以会选择适当的忽略这些特性。这也意味着静态分析有时候无法模拟程序的所有行为,漏报不可避免。
      例如静态分析中的区间分析涉及上下文敏感问题,如果想要足够精确的求出一个变量的值的可能区间,就需要考虑函数调用时的上下文关系以及调用实参的影响。但是如果完全的实现上下文敏感的分析,那么对于每一次函数的调用,需要将函数体复制一次,使每次调用互不影响,而且还涉及递归等复杂的情况,这会极大的降低效率,与增加的精度相比是不划算的。所以一般的静态分析工具在找到更好的技术解决这个问题之前,会找到一些折中方案解决部分情况。
      下面列出了一些代码分析中通常会忽略的特性,及其后果。


 

语言

通常会忽略的特性

忽略这些特性的后果

C/C++

 

setjmp/longjmp

指针运算的结果

人造指针

在堆上会产生副作用

对象的多层嵌套关系

最多只能跟踪2层,无法做到Object-sensitive,导致一些不可达路径,从而带来一系列

指针的流敏感

指针指向关系在保证效率的情况下,只能在函数结束时给出总体结果,如果按构成别名的函数给出结果往往效率过低

Java/C#

反射

JNI

带来很多无法分析的代码

带来很多不可见的副作用

JavaScript

eval,动态加载代码

通过DOM的数据流

跳过了相应的执行路径

缺少程序中的数据流


      如何解决这个问题呢?目前认为可以使用多种不完全分析的技术,然后对结果进行整合。
      下面是某国外著名商业静态分析工具K的一个漏报例子:

            

      main函数中三次调用foo()函数,传入不同的参数,而在foo(int m)函数中,通过调用f(m)(见15行),将f(m)结果传入数组下标,从而可能引起数组越界(见16行)。为了精确的检查是否数组越界,我们需要对于每一次foo()的调用,将foo()复制一份,然后对于每份foo()中每一次f()的调用,将f()复制一份,分别独立的运算对应的index的区间范围,这是相当消耗内存的。仅仅在这个小例子中,就复制了3份foo()和1*3份f(0)。而在实际工程中,随着函数嵌套的加深,函数调用次数的增加,需要复制的函数份数会呈指数上涨,这会成倍地增加工具消耗的内存,无疑是不可取的。在工程中可以选择只处理两层的函数调用,这样能在较小的内存代价下减少一些漏报,而更深层次的漏报很难避免,如上述漏报。静态分析工具很难做到完全的上下文敏感,这也是静态分析工具的通病。
      如何在各种折衷中找到平衡、最大限度的减少误漏报,是静态分析工具开发中长期以来面临的问题。
      在研究界,论文中往往更多地强调效率和误报率,不强调漏报率。针对这个问题,库博提供了一个新的功能,综合对比各个工具的对同一个项目的检测结果,这样一来可以综合比较国内外各工具的测试结果,二来可以融合各工具结果集,从而得到一个近似缺陷集合,以帮助用户针对同一个工程,更多更准的发现缺陷。
      此外,COBOT通过Juliet测试套件提供的标准结果,更准确可靠的评估工具的误漏报率。
      我们通过库博一年多的部署和实践,还在不断增加和完善缺陷模式。使用户更清晰了解到当前版本忽略的语言特性及其可能带来的漏报,使工具更容易被用户理解和使用。