齊 鈞，陳 燈

(1.武漢數(shù)字工程研究所，湖北 武漢 430205；2.武漢工程大學(xué) 智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430205)

?

基于規(guī)則過(guò)濾的改進(jìn)靜態(tài)分析技術(shù)

齊 鈞1，陳 燈2

(1.武漢數(shù)字工程研究所，湖北 武漢 430205；2.武漢工程大學(xué) 智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430205)

針對(duì)主流的基于規(guī)則的靜態(tài)分析工具，提出了一種快速的規(guī)則檢查方法。由于一個(gè)代碼文件通常只包含有限類型的程序缺陷，根據(jù)規(guī)則的特征對(duì)象對(duì)待匹配的規(guī)則進(jìn)行過(guò)濾，可以極大地提高靜態(tài)分析的效率。在開(kāi)源靜態(tài)分析工具PMD上進(jìn)行了技術(shù)實(shí)現(xiàn)并開(kāi)展了相關(guān)對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該方法較PMD方法效率平均提升了28.7%。

靜態(tài)分析；軟件質(zhì)量；軟件驗(yàn)證；性能改進(jìn)

靜態(tài)分析是一種重要的軟件質(zhì)量保障技術(shù)。其通過(guò)掃描程序的源代碼、字節(jié)碼或者二進(jìn)制代碼，能夠在程序開(kāi)發(fā)階段發(fā)現(xiàn)潛藏在程序中的各類脆弱性問(wèn)題。近年來(lái)，大量的靜態(tài)開(kāi)發(fā)工具已經(jīng)在業(yè)界得到應(yīng)用，如FindBugs[1-4]、PMD[5-6]和CheckStyle[7]等開(kāi)發(fā)工具。然而，由于性能上的瓶頸，這些靜態(tài)分析工具很難被集成到軟件開(kāi)發(fā)過(guò)程中，提供交互式的應(yīng)用。為了提高靜態(tài)分析的效率，研究者提出了增量靜態(tài)分析及基于分布式的靜態(tài)分析技術(shù)。增量分析技術(shù)能夠自動(dòng)地分析出代碼之間的關(guān)聯(lián)關(guān)系。當(dāng)代碼被修改以后，增量分析技術(shù)只對(duì)關(guān)聯(lián)代碼進(jìn)行重新分析，從而減少了靜態(tài)分析的時(shí)間開(kāi)銷。然而，對(duì)關(guān)聯(lián)關(guān)系復(fù)雜的代碼進(jìn)行修改，仍然會(huì)導(dǎo)致對(duì)整個(gè)代碼的全面分析。分布式技術(shù)是解決效率問(wèn)題的常用方法，然而構(gòu)建一個(gè)穩(wěn)定的分布式靜態(tài)分析工具是一項(xiàng)復(fù)雜的系統(tǒng)工程。筆者對(duì)基于安全規(guī)則的靜態(tài)分析工具進(jìn)行了研究，提出了一種改進(jìn)的規(guī)則檢查方法。該方法根據(jù)安全規(guī)則的特征對(duì)象，進(jìn)行規(guī)則過(guò)濾，從而提高了規(guī)則檢查的效率。在開(kāi)源靜態(tài)分析工具PMD上進(jìn)行了實(shí)現(xiàn)并開(kāi)展了相關(guān)實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該方法較PMD方法效率平均提升了28.7%。

1 總體思路

安全規(guī)則是靜態(tài)分析工具的一個(gè)重要組成部分。其通常采用特定的規(guī)則語(yǔ)言進(jìn)行描述，如：PQL[8-9]、DATALOG[10-12]和XPath表達(dá)式等[13]。將安全規(guī)則與程序的中間表示形式(如抽象語(yǔ)法樹(shù))進(jìn)行匹配能夠發(fā)現(xiàn)潛藏在程序中的各類脆弱性問(wèn)題。安全規(guī)則表達(dá)形式如圖1所示，其展示了一個(gè)采用XPath表達(dá)式進(jìn)行描述的安全規(guī)則MDBNamingConvention，該規(guī)則來(lái)自PMD的規(guī)則庫(kù)。該規(guī)則要求所有實(shí)現(xiàn)了接口MessageDrivenBean或者SessionBean的類，都必須以“Bean”作為名稱的后綴。然而，將該規(guī)則與所有的代碼文件(或者抽象語(yǔ)法樹(shù)上的所有節(jié)點(diǎn))進(jìn)行匹配會(huì)導(dǎo)致較大的時(shí)間開(kāi)銷。通過(guò)觀察發(fā)現(xiàn)，接口MessageDrivenBean或者SessionBean構(gòu)成了該規(guī)則的一個(gè)必要條件，即一個(gè)代碼文件中如果沒(méi)有使用接口MessageDrivenBean和SessionBean，則該代碼文件中不可能存在規(guī)則MDBNamingConvention的違例。鑒于以上分析，將一個(gè)安全規(guī)則中涉及的類稱之為該規(guī)則的特征對(duì)象，并構(gòu)造特征對(duì)象表達(dá)式對(duì)特征對(duì)象及對(duì)象之間的關(guān)系進(jìn)行描述。給定一條安全規(guī)則r，e為r的特征對(duì)象表達(dá)式，f為待檢查的代碼文件，通過(guò)求解χ(e,f)可以判斷出f中是否包含r的違例。由于一個(gè)代碼文件通常只包含有限類型的規(guī)則違例，根據(jù)χ(e,f)的結(jié)果對(duì)規(guī)則進(jìn)行過(guò)濾，可以減少檢查的規(guī)則數(shù)量，從而提高靜態(tài)分析工具的性能。

圖1 安全規(guī)則MDBNamingConvention

面向?qū)ο蟪绦蛟谑褂妙悤r(shí)，首先會(huì)采用導(dǎo)入命令導(dǎo)入類所在的包，如Java程序中的import語(yǔ)句和C++程序中的include預(yù)編譯指令等。以代碼文件中的導(dǎo)入語(yǔ)句作為輸入，對(duì)χ(e,f)進(jìn)行近似求解，可以避免對(duì)整個(gè)代碼文件進(jìn)行掃描，極大地減少了該方法的時(shí)間開(kāi)銷。

2 特征對(duì)象表達(dá)式

規(guī)則的特征對(duì)象之間可能存在各種各樣的關(guān)系，如圖1所示規(guī)則的特征對(duì)象MessageDrivenBean與SessionBean之間存在析取關(guān)系。為了對(duì)特征對(duì)象及其之間的關(guān)系進(jìn)行描述，構(gòu)造了一種特征對(duì)象表達(dá)式。

特征對(duì)象表達(dá)式由特征對(duì)象的全限定名稱、逗號(hào)、括號(hào)，以及運(yùn)算符構(gòu)成。其遞歸定義如下：給定一個(gè)特征對(duì)象λ和兩個(gè)特征對(duì)象表達(dá)式R和S，有以下特征對(duì)象表達(dá)式：

(1)exist(λ)表示存在性判定，即特征對(duì)象λ是否被一個(gè)代碼文件導(dǎo)入；

(2)neg(R)表示取反操作，即對(duì)一個(gè)布爾值取反；

(3)and(R,S)表示合取操作，即對(duì)兩個(gè)布爾值進(jìn)行合??；

(4)or(R,S)表示析取操作，即對(duì)兩個(gè)布爾值進(jìn)行析取。

通過(guò)將各種基本運(yùn)算符進(jìn)行嵌套和組合，特征對(duì)象表達(dá)式能夠表達(dá)各種復(fù)雜的特征對(duì)象之間的邏輯關(guān)系。如圖1所示，規(guī)則的特征對(duì)象表達(dá)式為or(exist(javax.ejb.SessionBean),exist(javax.ejb.MessageDrivenBean))。其表示：如果一個(gè)代碼文件導(dǎo)入了類MessageDrivenBean或者SessionBean，則該文件可能包含規(guī)則MDBNamingConvention的違例。為了對(duì)特征對(duì)象表達(dá)式的表達(dá)能力進(jìn)行驗(yàn)證，考查了PMD規(guī)則庫(kù)中的所有規(guī)則，發(fā)現(xiàn)所有規(guī)則均可以采用該表達(dá)式進(jìn)行描述。值得注意的是特征對(duì)象表達(dá)式可能無(wú)法處理某些特殊關(guān)系，如對(duì)象之間if-then的關(guān)系。

3 安全規(guī)則過(guò)濾

給定一個(gè)安全規(guī)則r，e為該規(guī)則的特征對(duì)象表達(dá)式，f為一個(gè)待檢測(cè)的代碼文件，χ(e,f)表示根據(jù)f的導(dǎo)入語(yǔ)句對(duì)表達(dá)式e進(jìn)行求解。規(guī)則過(guò)濾的方法為：如果χ(e,f)的結(jié)果為邏輯真，則應(yīng)用規(guī)則r對(duì)f進(jìn)行檢測(cè)；反之則濾掉規(guī)則r。以下分別對(duì)特征對(duì)象表達(dá)式求解及對(duì)象存在性判斷方法進(jìn)行說(shuō)明。

3.1 特征對(duì)象表達(dá)式求解

由于特征對(duì)象表達(dá)式是一種后綴表達(dá)式，故可以采用經(jīng)典的后綴表達(dá)式求解方法進(jìn)行求解。給定一個(gè)特征對(duì)象表達(dá)式e，求解方法為從右向左對(duì)e進(jìn)行掃描，對(duì)于每個(gè)碰到的符號(hào)η，執(zhí)行以下操作：

(1)若η是一個(gè)操作數(shù)，將其壓入到棧T中；

(2)若η是一個(gè)操作符，則從T中按順序取出操作數(shù)并進(jìn)行相應(yīng)的運(yùn)行，然后將運(yùn)算結(jié)果壓入棧T中；

(3)當(dāng)e中所有符號(hào)被處理完之后，T中取出的布爾值即為表達(dá)式的計(jì)算結(jié)果。

3.2 對(duì)象存在性判斷

特征對(duì)象表達(dá)式中共包含4類操作符：neg、and、or和exist。其中前3種為邏輯運(yùn)算符，其運(yùn)算規(guī)則與傳統(tǒng)的邏輯運(yùn)算符相同。exist運(yùn)算符的功能是判斷一個(gè)特征對(duì)象是否被一個(gè)代碼文件導(dǎo)入?？紤]到一個(gè)代碼文件中的導(dǎo)入語(yǔ)句集合通常較小，采用線性搜索的方法對(duì)exist運(yùn)算符進(jìn)行求解。給定一個(gè)特征對(duì)象λ，I為代碼文件f中對(duì)象導(dǎo)入語(yǔ)句的集合，判斷方法為順序地在I中查找λ，找到則表示計(jì)算結(jié)果為真，反之為假。值得注意的是，Java程序可以采用多種方式導(dǎo)入特征對(duì)象，如為了導(dǎo)入特征對(duì)象SessionBean，可以采用語(yǔ)句import javax.ejb.SessionBean或者import javax.ejb.*。前者表示導(dǎo)入一個(gè)特征對(duì)象，后者表示導(dǎo)入特征對(duì)象所在包的所有類。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

為了對(duì)筆者提出方法進(jìn)行評(píng)估，在開(kāi)源靜態(tài)分析工具PMD上進(jìn)行了技術(shù)實(shí)現(xiàn)并將擴(kuò)展后的PMD稱為EPMD。

實(shí)驗(yàn)程序集如表1所示，其中包含4個(gè)開(kāi)源的Java應(yīng)用程序。這些程序來(lái)自不同的應(yīng)用領(lǐng)域，其大小從73 k代碼行到2 675 k代碼行不等。實(shí)驗(yàn)程序集的多樣性為獲得普遍性的實(shí)驗(yàn)結(jié)果奠定了基礎(chǔ)。大型應(yīng)用程序可過(guò)濾掉更多的規(guī)則，從而獲得顯著的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)環(huán)境配置如下：CPU為Intel(R) Core (TM) i3-2100 3.1 GHz；內(nèi)存為3 GB；操作系統(tǒng)為Windows XP。

表1 實(shí)驗(yàn)程序集

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)以EPMD為基礎(chǔ)，分別采用規(guī)則集RS和RS*對(duì)表1所示的程序集進(jìn)行分析。規(guī)則集RS和RS*包含45條相同內(nèi)容的規(guī)則，不同的是RS*中的規(guī)則含有特征對(duì)象表達(dá)式，而RS中的規(guī)則不含有該表達(dá)式。因此EPMD只對(duì)RS*中的規(guī)則啟用規(guī)則過(guò)濾技術(shù)，而RS中的規(guī)則仍采用PMD的方法進(jìn)行規(guī)則檢查。為了獲得準(zhǔn)確的實(shí)驗(yàn)結(jié)果，對(duì)每個(gè)應(yīng)用程序分別采用規(guī)則集RS和RS*進(jìn)行5次重復(fù)分析。靜態(tài)分析性能如表2所示。

由實(shí)驗(yàn)結(jié)果可知，在各組實(shí)驗(yàn)中采用規(guī)則集RS*進(jìn)行靜態(tài)分析的時(shí)間開(kāi)銷均小于在規(guī)則集RS下的開(kāi)銷。在對(duì)實(shí)驗(yàn)程序Eclipse進(jìn)行分析時(shí)效率提高了15.6%。在對(duì)程序PMD進(jìn)行分析時(shí)效率提高了45.3%。筆者提出的方法較PMD中原始的規(guī)則檢查方法效率平均提高了28.7%。在各組對(duì)比實(shí)驗(yàn)中，比較了靜態(tài)分析的錯(cuò)誤報(bào)告，發(fā)現(xiàn)采用規(guī)則集RS和RS*所輸出的錯(cuò)誤報(bào)告完全相同。

表2 靜態(tài)分析性能

綜上所述，所提出的方法能對(duì)規(guī)則進(jìn)行有效的過(guò)濾，從而在保證靜態(tài)分析結(jié)果準(zhǔn)確性的前提下提高效率。

5 結(jié)論

鑒于當(dāng)前大部分靜態(tài)分析器均采用安全規(guī)則作為錯(cuò)誤檢測(cè)的基礎(chǔ)，筆者提出采用規(guī)則過(guò)濾的方法提升靜態(tài)分析的性能。為此，采用編譯器技術(shù)構(gòu)造了特征對(duì)象表達(dá)式對(duì)安全規(guī)則的必要條件進(jìn)行描述。通過(guò)對(duì)特征對(duì)象表達(dá)式進(jìn)行求解，從而實(shí)現(xiàn)安全規(guī)則過(guò)濾?；陂_(kāi)源靜態(tài)分析工具PMD進(jìn)行了技術(shù)實(shí)現(xiàn)并采用4個(gè)實(shí)際的應(yīng)用程序作為實(shí)驗(yàn)對(duì)象開(kāi)展了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，所提出的方法能夠在不影響實(shí)驗(yàn)結(jié)果正確性的前提下提高了效率。

[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-)，男，湖北武漢人,武漢數(shù)字工程研究所高級(jí)工程師.

湖北省自然科學(xué)基金資助項(xiàng)目(2014CFB1006).

2095-3852(2015)05-0585-04

A

TP311.5

10.3963/j.issn.2095-3852.2015.05.013