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

齊 鈞，陳 燈

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

?

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

齊 鈞1，陳 燈2

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

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

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

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

1 總體思路

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

圖1 安全規(guī)則MDBNamingConvention

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

2 特征對象表達式

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

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

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

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

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

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

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

3 安全規(guī)則過濾

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

3.1 特征對象表達式求解

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

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

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

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

3.2 對象存在性判斷

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

4 實驗

4.1 實驗設(shè)置

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

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

表1 實驗程序集

4.2 實驗結(jié)果分析

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

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

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

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

5 結(jié)論

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

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

2095-3852(2015)05-0585-04

A

TP311.5

10.3963/j.issn.2095-3852.2015.05.013