基于规则过滤的改进静态分析技术

齐 钧，陈 灯

(1.武汉数字工程研究所，湖北 武汉 430205；2.武汉工程大学 智能机器人湖北省重点实验室，湖北 武汉 430205)



基于规则过滤的改进静态分析技术

齐 钧1，陈 灯2

(1.武汉数字工程研究所，湖北 武汉 430205；2.武汉工程大学 智能机器人湖北省重点实验室，湖北 武汉 430205)

针对主流的基于规则的静态分析工具，提出了一种快速的规则检查方法。由于一个代码文件通常只包含有限类型的程序缺陷，根据规则的特征对象对待匹配的规则进行过滤，可以极大地提高静态分析的效率。在开源静态分析工具PMD上进行了技术实现并开展了相关对比实验，实验结果表明，该方法较PMD方法效率平均提升了28.7%。

静态分析；软件质量；软件验证；性能改进

静态分析是一种重要的软件质量保障技术。其通过扫描程序的源代码、字节码或者二进制代码，能够在程序开发阶段发现潜藏在程序中的各类脆弱性问题。近年来，大量的静态开发工具已经在业界得到应用，如FindBugs[1-4]、PMD[5-6]和CheckStyle[7]等开发工具。然而，由于性能上的瓶颈，这些静态分析工具很难被集成到软件开发过程中，提供交互式的应用。为了提高静态分析的效率，研究者提出了增量静态分析及基于分布式的静态分析技术。增量分析技术能够自动地分析出代码之间的关联关系。当代码被修改以后，增量分析技术只对关联代码进行重新分析，从而减少了静态分析的时间开销。然而，对关联关系复杂的代码进行修改，仍然会导致对整个代码的全面分析。分布式技术是解决效率问题的常用方法，然而构建一个稳定的分布式静态分析工具是一项复杂的系统工程。笔者对基于安全规则的静态分析工具进行了研究，提出了一种改进的规则检查方法。该方法根据安全规则的特征对象，进行规则过滤，从而提高了规则检查的效率。在开源静态分析工具PMD上进行了实现并开展了相关实验。实验结果表明，该方法较PMD方法效率平均提升了28.7%。

1 总体思路

安全规则是静态分析工具的一个重要组成部分。其通常采用特定的规则语言进行描述，如：PQL[8-9]、DATALOG[10-12]和XPath表达式等[13]。将安全规则与程序的中间表示形式(如抽象语法树)进行匹配能够发现潜藏在程序中的各类脆弱性问题。安全规则表达形式如图1所示，其展示了一个采用XPath表达式进行描述的安全规则MDBNamingConvention，该规则来自PMD的规则库。该规则要求所有实现了接口MessageDrivenBean或者SessionBean的类，都必须以“Bean”作为名称的后缀。然而，将该规则与所有的代码文件(或者抽象语法树上的所有节点)进行匹配会导致较大的时间开销。通过观察发现，接口MessageDrivenBean或者SessionBean构成了该规则的一个必要条件，即一个代码文件中如果没有使用接口MessageDrivenBean和SessionBean，则该代码文件中不可能存在规则MDBNamingConvention的违例。鉴于以上分析，将一个安全规则中涉及的类称之为该规则的特征对象，并构造特征对象表达式对特征对象及对象之间的关系进行描述。给定一条安全规则r，e为r的特征对象表达式，f为待检查的代码文件，通过求解χ(e,f)可以判断出f中是否包含r的违例。由于一个代码文件通常只包含有限类型的规则违例，根据χ(e,f)的结果对规则进行过滤，可以减少检查的规则数量，从而提高静态分析工具的性能。

图1 安全规则MDBNamingConvention

面向对象程序在使用类时，首先会采用导入命令导入类所在的包，如Java程序中的import语句和C++程序中的include预编译指令等。以代码文件中的导入语句作为输入，对χ(e,f)进行近似求解，可以避免对整个代码文件进行扫描，极大地减少了该方法的时间开销。

2 特征对象表达式

规则的特征对象之间可能存在各种各样的关系，如图1所示规则的特征对象MessageDrivenBean与SessionBean之间存在析取关系。为了对特征对象及其之间的关系进行描述，构造了一种特征对象表达式。

特征对象表达式由特征对象的全限定名称、逗号、括号，以及运算符构成。其递归定义如下：给定一个特征对象λ和两个特征对象表达式R和S，有以下特征对象表达式：

(1)exist(λ)表示存在性判定，即特征对象λ是否被一个代码文件导入；

(2)neg(R)表示取反操作，即对一个布尔值取反；

(3)and(R,S)表示合取操作，即对两个布尔值进行合取；

(4)or(R,S)表示析取操作，即对两个布尔值进行析取。

通过将各种基本运算符进行嵌套和组合，特征对象表达式能够表达各种复杂的特征对象之间的逻辑关系。如图1所示，规则的特征对象表达式为or(exist(javax.ejb.SessionBean),exist(javax.ejb.MessageDrivenBean))。其表示：如果一个代码文件导入了类MessageDrivenBean或者SessionBean，则该文件可能包含规则MDBNamingConvention的违例。为了对特征对象表达式的表达能力进行验证，考查了PMD规则库中的所有规则，发现所有规则均可以采用该表达式进行描述。值得注意的是特征对象表达式可能无法处理某些特殊关系，如对象之间if-then的关系。

3 安全规则过滤

给定一个安全规则r，e为该规则的特征对象表达式，f为一个待检测的代码文件，χ(e,f)表示根据f的导入语句对表达式e进行求解。规则过滤的方法为：如果χ(e,f)的结果为逻辑真，则应用规则r对f进行检测；反之则滤掉规则r。以下分别对特征对象表达式求解及对象存在性判断方法进行说明。

3.1 特征对象表达式求解

由于特征对象表达式是一种后缀表达式，故可以采用经典的后缀表达式求解方法进行求解。给定一个特征对象表达式e，求解方法为从右向左对e进行扫描，对于每个碰到的符号η，执行以下操作：

(1)若η是一个操作数，将其压入到栈T中；

(2)若η是一个操作符，则从T中按顺序取出操作数并进行相应的运行，然后将运算结果压入栈T中；

(3)当e中所有符号被处理完之后，T中取出的布尔值即为表达式的计算结果。

3.2 对象存在性判断

特征对象表达式中共包含4类操作符：neg、and、or和exist。其中前3种为逻辑运算符，其运算规则与传统的逻辑运算符相同。exist运算符的功能是判断一个特征对象是否被一个代码文件导入。考虑到一个代码文件中的导入语句集合通常较小，采用线性搜索的方法对exist运算符进行求解。给定一个特征对象λ，I为代码文件f中对象导入语句的集合，判断方法为顺序地在I中查找λ，找到则表示计算结果为真，反之为假。值得注意的是，Java程序可以采用多种方式导入特征对象，如为了导入特征对象SessionBean，可以采用语句import javax.ejb.SessionBean或者import javax.ejb.*。前者表示导入一个特征对象，后者表示导入特征对象所在包的所有类。

4 实验

4.1 实验设置

为了对笔者提出方法进行评估，在开源静态分析工具PMD上进行了技术实现并将扩展后的PMD称为EPMD。

实验程序集如表1所示，其中包含4个开源的Java应用程序。这些程序来自不同的应用领域，其大小从73 k代码行到2 675 k代码行不等。实验程序集的多样性为获得普遍性的实验结果奠定了基础。大型应用程序可过滤掉更多的规则，从而获得显著的实验结果。实验环境配置如下：CPU为Intel(R) Core (TM) i3-2100 3.1 GHz；内存为3 GB；操作系统为Windows XP。

表1 实验程序集

4.2 实验结果分析

实验以EPMD为基础，分别采用规则集RS和RS*对表1所示的程序集进行分析。规则集RS和RS*包含45条相同内容的规则，不同的是RS*中的规则含有特征对象表达式，而RS中的规则不含有该表达式。因此EPMD只对RS*中的规则启用规则过滤技术，而RS中的规则仍采用PMD的方法进行规则检查。为了获得准确的实验结果，对每个应用程序分别采用规则集RS和RS*进行5次重复分析。静态分析性能如表2所示。

由实验结果可知，在各组实验中采用规则集RS*进行静态分析的时间开销均小于在规则集RS下的开销。在对实验程序Eclipse进行分析时效率提高了15.6%。在对程序PMD进行分析时效率提高了45.3%。笔者提出的方法较PMD中原始的规则检查方法效率平均提高了28.7%。在各组对比实验中，比较了静态分析的错误报告，发现采用规则集RS和RS*所输出的错误报告完全相同。

表2 静态分析性能

综上所述，所提出的方法能对规则进行有效的过滤，从而在保证静态分析结果准确性的前提下提高效率。

5 结论

鉴于当前大部分静态分析器均采用安全规则作为错误检测的基础，笔者提出采用规则过滤的方法提升静态分析的性能。为此，采用编译器技术构造了特征对象表达式对安全规则的必要条件进行描述。通过对特征对象表达式进行求解，从而实现安全规则过滤。基于开源静态分析工具PMD进行了技术实现并采用4个实际的应用程序作为实验对象开展了对比实验。实验结果表明，所提出的方法能够在不影响实验结果正确性的前提下提高了效率。

[1] HOVEMEYER D， PUGH W. Finding bugs is easy [C]∥Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications. Vancouver:[s.n.],2004:92-106.

[2] ARAUJO J E M, SOUZA S, VALENTE M T. Study on the relevance of the warnings reported by Java bug-finding tools[J]. IET Software, 2011,5(4):366-374.

[3] AYEWAH N, PUGH W, MORGENTHALER J D, et al. Evaluating static analysis defect warnings on production software [C]∥Proceedings of the 2007 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools & Engineering.[S.l.]:[s.n.],2007:1-7.

[4] HOVEMEYER D, PUGH W. Finding more null pointer bugs, but not too many[C]∥Proceedings of the 2007 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools & Engineering.[S.l.]:[s.n.],2007:9-14.

[5] PLOESCH R, GRUBER H, HENTSCHEL A, et al. On the relation between external software quality and static code analysis [C]∥Proceedings of the 32nd Annual IEEE Software Engineering Workshop.[S.l.]:[s.n.], 2009:169-174.

[6] HELMICK M T. Interface-based programming assignments and automatic grading of Java programs [C]∥The 12th Annual Conference on Innovation & Technology in Computer Science Education.[S.l.]:[s.n.],2007:63-67.

[7] LOVELAND S. Using open source tools to prevent write-only code [C]∥Proceedings of the Sixth International Conference on Information Technology.[S.l.]:[s.n.],2009:671-677.

[8] MARTIN M, LIVSHITS B, LAM M S. Finding application errors and security flaws using PQL: a program query language [C]∥Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming Systems, Languages and Applications.[S.l.]:[s.n.],2005:365-383.

[9] JARZABEK S. Design of flexible static program analyzers with PQL[J]. IEEE Transactions on Software Engineering, 1998, 24(3):197-215.

[10] HAJIYEV E, VERBAERE M, MOOR D O. Scalable source code queries with datalog[C]∥ECOOP 2006:Object Oriented Programming. [S.l.]: [s.n.], 2006:2-27.

[11] ALPUENTE M, FELIU M A, JOUBERT C, et al. Using datalog and boolean equation systems for program analysis[J].Formal Methods for Industrial Critical Systems, 2009(5596):215-231.

[12] ZOOK D, PASALIC E, SARNA-STAROSTA B. Typed datalog[J].Practical Aspects of Declarative Languages, 2009(1):168-182.

[13] CHEN D, HUANG R, QU B, et al. Improving static analysis performance using rule-filtering technique[C]∥The 26th International Conference on Software Engineering and Knowledge Engineering.[S.l.]: [s.n.],2014:19-24.

QI Jun:Senior Engineer; Wuhan Digital Engineering Institute, Wuhan 430205, China.

[编辑：王志全]

Static Analysis Based on Rule-filtering Technique

QIJun,CHENDeng

Based on rule-based static analysis tools, an optimized rule-checking algorithm was proposed to improve their performance. This work was based on the observation that a source file generally contains limited types of vulnerabilities. Therefore, performance can be improved by filtering rules according to their characteristic objects. Comparative experiments were conducted against an open source static analysis tool PMD. Experimental results show that the proposed technique outperforms PMD by 28.7% in average.

static analysis; software quality; software verification; performance improvement

2015-03-18.

齐钧(1963-)，男，湖北武汉人,武汉数字工程研究所高级工程师.

湖北省自然科学基金资助项目(2014CFB1006).

2095-3852(2015)05-0585-04

A

TP311.5

10.3963/j.issn.2095-3852.2015.05.013