一種改進的數據流分析方法

呂懷蓮

[摘要]首先討論傳統的數據流分析技術;然后在引入分支依賴分析方法的基礎上,對廣泛應用于工程中的迭代數據流方程求解方法進行分析,提出一種改進的數據流分析方法,并將其應用到實際的程序分析中。

[關鍵詞]數據流分析數據流方程控制流語句塊

中圖分類號:TP6文獻標識碼:A文章編號:1671-7597(2009)0710059-02

一、引言

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

數據流分析獲取信息的方法有兩種,對于結構化的程序可采用語法制導的求解方法,對于任意控制流的程序可采用迭代數據流方程求解的方法。迭代數據流方程求解方法首先要建立控制流圖,然后為每個控制流圖結點建立數據流方程,最后通過迭代求解數據流方程來獲取數據流信息,這種方法也被稱為到達-定值的迭代算法[1],在實際的工程中應用較廣。到達-定值迭代算法需多次迭代計算控制流圖上所有結點的定值信息[3],時間復雜度較高。本文提出一種可應用于一般數據流分析的改進方法,在最小的迭代求解范圍內以最小的迭代次數可獲取完整準確的數據流信息。

本文通過引入軟件測試中分支依賴“語句塊”的劃分思想粗化分析粒度,對傳統的迭代數據流方程求解方法進行改進,將控制流圖上所有結點定值的迭代求解過程轉化為局部的對循環語句塊內結點定值的迭代求解過程。最后,對改進方法進行分析和對比并將其應用到實際的程序分析中。

二、迭代數據流方程求解方法及其改進思想

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

對于每個語句對應的控制流圖結點N,可以定義out[N],kill[N],gen[N]和in[N],其中gen[N]為N對應語句處產生的定值集合,kill[N]為N對應的語句在程序中注銷的定值集合;in[N]為N對應語句前一點到達的定值集合,out[N]為N對應語句后一點到達的定值集合。并且,產生和注銷的信息依賴于所需要的信息。若每個控制流圖結點的gen和kill已經計算,則可建立如下兩組方程:

(2-1)

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

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

到達-定值迭代算法反復計算這2n個方程,直到所有結點的in和out集合都不再改變(即每一個控制流圖結點都到達平衡狀態)。每一次的迭代求解都要對所有結點的in和out重新計算一次。

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

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

含循環結點的循環語句塊(以while結點為例)的提取方式和數據流分析過程如下:

1.基本while語句結點(見圖2.1)

圖2.1中,結點1和結點3構成環,因此結點1和3構成一個循環語句塊。根據結點1的第一次定值求解結果對該循環語句塊進行到達-定值迭代求解,直到結點1和結點3到達平衡狀態。此時結點1的最后的迭代結果即為該循環語句塊的最終求解結果。

2.含break的while語句結點(見圖2.2)

圖2.2中,由于出現break結點,沿著結點1的True路徑找不到環,即該圖上沒有結點構成循環語句塊。因此只需將圖中的結點按照一般語句的求解過程求解即可。

3.含分支結構的while語句結點(見圖2.3)

圖2.3中,沿著結點1的True分支找環,結點1、3、5、9構成一個循環語句塊。根據結點1的第一次定值求解結果對該循環語句塊進行到達-定值迭代求解,直到結點1、3、5、9到達平衡狀態。此時結點1的最后的迭代結果即為該循環語句塊的最終求解結果。

(三)分支結構和迭代求解次數

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

由上面討論可知,分支匯合結點的定值依賴于分支上結點的定值求解結果,因此,利用控制流信息,確立分支結構上結點的定值計算先于分支匯合結點定值計算的求解模式,能夠有效避免最大迭代次數的出現。

(四)到達-定值迭代算法的改進算法

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

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

三、實例分析和方法對比

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

1.全局的數據流迭代求解過程被轉化為局部的迭代求解過程;

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

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

四、結束語

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

參考文獻:

[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.