一種改進(jìn)的數(shù)據(jù)流分析方法

呂懷蓮

[摘要]首先討論傳統(tǒng)的數(shù)據(jù)流分析技術(shù);然后在引入分支依賴分析方法的基礎(chǔ)上,對(duì)廣泛應(yīng)用于工程中的迭代數(shù)據(jù)流方程求解方法進(jìn)行分析,提出一種改進(jìn)的數(shù)據(jù)流分析方法,并將其應(yīng)用到實(shí)際的程序分析中。

[關(guān)鍵詞]數(shù)據(jù)流分析數(shù)據(jù)流方程控制流語句塊

中圖分類號(hào):TP6文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1671-7597(2009)0710059-02

一、引言

基于源代碼靜態(tài)分析的數(shù)據(jù)流分析[1][2]作為程序分析的一種重要技術(shù),能夠從程序代碼中收集程序的語義信息,它不必實(shí)際運(yùn)行程序就能夠獲取程序運(yùn)行時(shí)的信息,更易于人們理解和分析程序,因此被廣泛用于解決編譯優(yōu)化、程序驗(yàn)證、調(diào)試、測試和并行編程環(huán)境等中的問題。

數(shù)據(jù)流分析獲取信息的方法有兩種,對(duì)于結(jié)構(gòu)化的程序可采用語法制導(dǎo)的求解方法,對(duì)于任意控制流的程序可采用迭代數(shù)據(jù)流方程求解的方法。迭代數(shù)據(jù)流方程求解方法首先要建立控制流圖,然后為每個(gè)控制流圖結(jié)點(diǎn)建立數(shù)據(jù)流方程,最后通過迭代求解數(shù)據(jù)流方程來獲取數(shù)據(jù)流信息,這種方法也被稱為到達(dá)-定值的迭代算法[1],在實(shí)際的工程中應(yīng)用較廣。到達(dá)-定值迭代算法需多次迭代計(jì)算控制流圖上所有結(jié)點(diǎn)的定值信息[3],時(shí)間復(fù)雜度較高。本文提出一種可應(yīng)用于一般數(shù)據(jù)流分析的改進(jìn)方法,在最小的迭代求解范圍內(nèi)以最小的迭代次數(shù)可獲取完整準(zhǔn)確的數(shù)據(jù)流信息。

本文通過引入軟件測試中分支依賴“語句塊”的劃分思想粗化分析粒度,對(duì)傳統(tǒng)的迭代數(shù)據(jù)流方程求解方法進(jìn)行改進(jìn),將控制流圖上所有結(jié)點(diǎn)定值的迭代求解過程轉(zhuǎn)化為局部的對(duì)循環(huán)語句塊內(nèi)結(jié)點(diǎn)定值的迭代求解過程。最后,對(duì)改進(jìn)方法進(jìn)行分析和對(duì)比并將其應(yīng)用到實(shí)際的程序分析中。

二、迭代數(shù)據(jù)流方程求解方法及其改進(jìn)思想

(一)數(shù)據(jù)流方程及其建立

對(duì)于每個(gè)語句對(duì)應(yīng)的控制流圖結(jié)點(diǎn)N,可以定義out[N],kill[N],gen[N]和in[N],其中g(shù)en[N]為N對(duì)應(yīng)語句處產(chǎn)生的定值集合,kill[N]為N對(duì)應(yīng)的語句在程序中注銷的定值集合;in[N]為N對(duì)應(yīng)語句前一點(diǎn)到達(dá)的定值集合,out[N]為N對(duì)應(yīng)語句后一點(diǎn)到達(dá)的定值集合。并且,產(chǎn)生和注銷的信息依賴于所需要的信息。若每個(gè)控制流圖結(jié)點(diǎn)的gen和kill已經(jīng)計(jì)算,則可建立如下兩組方程:

(2-1)

其中,P是N的控制流圖中的前驅(qū)結(jié)點(diǎn)。第一組方程表明,進(jìn)入語句開始點(diǎn)的定值是所有前驅(qū)結(jié)點(diǎn)到達(dá)的定值集合的并;第二組方程表明,控制流通過一個(gè)語句時(shí),語句末尾的定值是這個(gè)語句產(chǎn)生的定值,或是進(jìn)入語句開始點(diǎn)并且沒有被這個(gè)語句注銷的定值。這樣的方程叫做數(shù)據(jù)流方程。如果控制流圖有n個(gè)結(jié)點(diǎn),則從(2-1)可建立2n個(gè)方程。

(二)到達(dá)-定值迭代算法和語句塊

到達(dá)-定值迭代算法反復(fù)計(jì)算這2n個(gè)方程,直到所有結(jié)點(diǎn)的in和out集合都不再改變(即每一個(gè)控制流圖結(jié)點(diǎn)都到達(dá)平衡狀態(tài))。每一次的迭代求解都要對(duì)所有結(jié)點(diǎn)的in和out重新計(jì)算一次。

到達(dá)-定值迭代算法求解過程中,循環(huán)結(jié)點(diǎn)及其內(nèi)部循環(huán)語句結(jié)點(diǎn)不能到達(dá)平衡狀態(tài),導(dǎo)致了求解過程的多次迭代。對(duì)一個(gè)完整的控制流圖,循環(huán)結(jié)點(diǎn)一定存在一個(gè)不滿足循環(huán)條件(False分支)的出口,否則,該循環(huán)將陷入死循環(huán)而導(dǎo)致控制流圖的不完整。因此,本文通過“封裝”循環(huán)結(jié)點(diǎn)及其內(nèi)部循環(huán)語句結(jié)點(diǎn)來簡化數(shù)據(jù)流方程的迭代求解過程。到達(dá)-定值迭代算法的數(shù)據(jù)流分析方法是基于語句級(jí)別的程序分析。在軟件測試中,靜態(tài)分析技術(shù)——分支依賴分析是以語句塊為分析粒度的程序分析。分析粒度從語句級(jí)別粗化到語句塊級(jí)別,有助于獲取語句塊之間的依賴信息。

基于分支依賴分析中分析粒度可以粗化這一思想,本文將求解過程中遇到的循環(huán)結(jié)點(diǎn)及其內(nèi)部結(jié)點(diǎn)“封裝”成一個(gè)整體,稱作為一個(gè)循環(huán)語句塊,即沿著循環(huán)結(jié)點(diǎn)滿足循環(huán)條件(True分支)出口構(gòu)成的環(huán)上的所有語句結(jié)點(diǎn)組成的集合。對(duì)控制流圖而言,循環(huán)語句塊可被看作是一個(gè)虛的語句結(jié)點(diǎn),該語句結(jié)點(diǎn)的迭代結(jié)果即為循環(huán)語句塊中的循環(huán)結(jié)點(diǎn)到達(dá)平衡狀態(tài)的迭代結(jié)果;而對(duì)循環(huán)語句塊的內(nèi)部結(jié)點(diǎn)則是一個(gè)多次迭代數(shù)據(jù)流方程求解的過程。獲取循環(huán)語句結(jié)點(diǎn)最終的定值迭代求解結(jié)果后,沿著循環(huán)結(jié)點(diǎn)的False分支繼續(xù)進(jìn)行數(shù)據(jù)流方程求解。由此,可以認(rèn)為最好情況下只需一遍迭代數(shù)據(jù)流方程求解即可使控制流圖上所有結(jié)點(diǎn)到達(dá)平衡狀態(tài)。

含循環(huán)結(jié)點(diǎn)的循環(huán)語句塊(以while結(jié)點(diǎn)為例)的提取方式和數(shù)據(jù)流分析過程如下:

1.基本while語句結(jié)點(diǎn)(見圖2.1)

圖2.1中,結(jié)點(diǎn)1和結(jié)點(diǎn)3構(gòu)成環(huán),因此結(jié)點(diǎn)1和3構(gòu)成一個(gè)循環(huán)語句塊。根據(jù)結(jié)點(diǎn)1的第一次定值求解結(jié)果對(duì)該循環(huán)語句塊進(jìn)行到達(dá)-定值迭代求解,直到結(jié)點(diǎn)1和結(jié)點(diǎn)3到達(dá)平衡狀態(tài)。此時(shí)結(jié)點(diǎn)1的最后的迭代結(jié)果即為該循環(huán)語句塊的最終求解結(jié)果。

2.含break的while語句結(jié)點(diǎn)(見圖2.2)

圖2.2中,由于出現(xiàn)break結(jié)點(diǎn),沿著結(jié)點(diǎn)1的True路徑找不到環(huán),即該圖上沒有結(jié)點(diǎn)構(gòu)成循環(huán)語句塊。因此只需將圖中的結(jié)點(diǎn)按照一般語句的求解過程求解即可。

3.含分支結(jié)構(gòu)的while語句結(jié)點(diǎn)(見圖2.3)

圖2.3中,沿著結(jié)點(diǎn)1的True分支找環(huán),結(jié)點(diǎn)1、3、5、9構(gòu)成一個(gè)循環(huán)語句塊。根據(jù)結(jié)點(diǎn)1的第一次定值求解結(jié)果對(duì)該循環(huán)語句塊進(jìn)行到達(dá)-定值迭代求解,直到結(jié)點(diǎn)1、3、5、9到達(dá)平衡狀態(tài)。此時(shí)結(jié)點(diǎn)1的最后的迭代結(jié)果即為該循環(huán)語句塊的最終求解結(jié)果。

(三)分支結(jié)構(gòu)和迭代求解次數(shù)

圖2.4是一個(gè)if分支語句片斷,結(jié)點(diǎn)6的定值計(jì)算可以先于結(jié)點(diǎn)4計(jì)算,也可以在結(jié)點(diǎn)4的定值計(jì)算后進(jìn)行。但是,結(jié)點(diǎn)6的定值計(jì)算依賴結(jié)點(diǎn)4的定值求解結(jié)果,因此,對(duì)整個(gè)程序片斷,前一種計(jì)算模式將比后一種的求解迭代次數(shù)至少多一次。而且,隨著分支結(jié)構(gòu)或分支嵌套的增多,求解的迭代次數(shù)將急劇增大。由此可見,分支結(jié)構(gòu)上語句的定值求解順序直接影響整個(gè)程序的定值求解迭代次數(shù)。

由上面討論可知,分支匯合結(jié)點(diǎn)的定值依賴于分支上結(jié)點(diǎn)的定值求解結(jié)果,因此,利用控制流信息,確立分支結(jié)構(gòu)上結(jié)點(diǎn)的定值計(jì)算先于分支匯合結(jié)點(diǎn)定值計(jì)算的求解模式,能夠有效避免最大迭代次數(shù)的出現(xiàn)。

(四)到達(dá)-定值迭代算法的改進(jìn)算法

基于2.2節(jié)和2.3節(jié)的討論,可得到如下由算法1和算法2組成的改進(jìn)算法。算法1是主入口算法,基本思想是對(duì)循環(huán)結(jié)點(diǎn)首先沿著它的True分支找環(huán),并且定值的迭代求解只在環(huán)上進(jìn)行;之后沿著它的False分支繼續(xù)定值求解。算法2是對(duì)含循環(huán)結(jié)點(diǎn)的循環(huán)語句塊中所有結(jié)點(diǎn)定值的求解。

其中,控制流圖是一個(gè)有向圖,它的每條邊都連接有兩個(gè)結(jié)點(diǎn):頭結(jié)點(diǎn)和尾結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)(開始結(jié)點(diǎn)和結(jié)束結(jié)點(diǎn)除外)都有至少一條入邊和至少一條出邊。并且,2.3節(jié)的討論包含在算法1步驟3中“選擇下一個(gè)可分析的結(jié)點(diǎn)”的操作中。

三、實(shí)例分析和方法對(duì)比

通過實(shí)例分析對(duì)比到達(dá)-定值迭代算法及其改進(jìn)算法,兩者的求解結(jié)果是一致的;并且,改進(jìn)算法利用語句塊劃分思想和控制流信息將迭代求解局限于循環(huán)語句塊內(nèi)部,對(duì)程序整體而言,只需一次迭代求解即可獲得所需的數(shù)據(jù)流信息。循環(huán)語句塊內(nèi)部的中間迭代求解結(jié)果無需保存,空間復(fù)雜度不會(huì)高于到達(dá)-定值迭代算法。實(shí)例分析對(duì)比結(jié)果,改進(jìn)算法時(shí)間開銷只是到達(dá)-定值迭代算法的最好時(shí)間開銷的一半左右,由此可見,改進(jìn)算法比到達(dá)-定值迭代算法更高效。并且,改進(jìn)的數(shù)據(jù)流分析方法在求解過程中有以下幾個(gè)優(yōu)點(diǎn):

1.全局的數(shù)據(jù)流迭代求解過程被轉(zhuǎn)化為局部的迭代求解過程;

2.粗化分析粒度,引入了語句塊的劃分思想,獲取數(shù)據(jù)流信息的流程更加清晰;

3.利用控制流信息確定求解順序,確保以最小的迭代次數(shù)獲取數(shù)據(jù)流信息。

四、結(jié)束語

數(shù)據(jù)流分析作為一種非常重要的靜態(tài)程序分析技術(shù),在保證軟件質(zhì)量與可靠性方面起到重要作用。本文通過引入軟件測試的部分思想,對(duì)廣泛應(yīng)用于工程中的傳統(tǒng)數(shù)據(jù)流分析方法進(jìn)行了分析,提出了一種可應(yīng)用于一般數(shù)據(jù)流分析的改進(jìn)方法,該方法通過粗化分析粒度和利用獲取的控制流信息,在最小的迭代求解范圍內(nèi)以最小的迭代次數(shù)獲取完整準(zhǔn)確的數(shù)據(jù)流信息。該方法已應(yīng)用到安全檢查工具XDCHECKER中。實(shí)踐證明,該改進(jìn)方法能夠有效地進(jìn)行數(shù)據(jù)流分析。

參考文獻(xiàn):

[1]Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman.Compilers:Principles,

Techniques,and Tools.Reading,MA:Addison Weslsy Publishing Company,1986:279-316.

[2]Flemming Nielson,Hanne R.Nielson,and Chris Hankin. Principles of Program Analysis.Springer-Verlag New York,Inc.,Secaucus,NJ,USA,1999.

[3]Gleb Naumovich.Using the Observer Design Pattern for Implementation of Data Flow Analyses.ACM SIGSOFT Software Engineering Notes,2003;28(1):61-68.