如何利用Python實現簡單C++程序范圍分析

Posted on by

1. 實驗說明

問題要求：針對靜態單賦值（SSA）形式的函數中間代碼輸入，輸出函數返回值的范圍

實現思路： 基本根據 2013年在CGO會議上提出的“三步法”范圍分析法加以實現[3]，求得各個變量的范圍

算法優勢：空間復雜度和時間復雜度都是 O(n)，效率高

算法瓶頸： “三步法”的功能存在較大局限，它隻能分析各個變量的最大范圍，對活躍變量隻做瞭最簡單的考慮，因此最終得到的范圍比較不準確，往往隻能得到范圍的一個界

2. 項目使用

python main.py （ssa文件路徑在main.py中設置）

不需要安裝任何庫。

3. 算法原理

簡單概括：采用三步法（2013年在CGO會議上提出）

3.1 構建CFG

代碼：\src\eSSAConstraintGraph.py; \src\structure.py

功能：解析SSA，構建CFG。

由於函數之間存在調用關系，因此首先把SSA劃分成不同的函數的SSA，再分別構建CFG。CFG中保留瞭每一個函數的語句、Block之間的關系，為下一步構建Constraint Graph打基礎。

CFG的結構如下：

# CFG類      
class CFG:
    def __init__(self):
        self.name = ''
        self.Blocks = []
        self.Edges = []
        self.Arguments = []

3.2 構建Constraint Graph

代碼：\src\eSSAConstraintGraph.py

三步法的前提是構建Constraint Graph。數據結構如下。在這一步中，我用自己定義的數據類型MyNode來表示一條Constraint。

# Constraint Graph類      
class ConstraintGraph:
    def __init__(self, cfg):
        self.MyNodes = []            #基本節點，每一個節點是一個Constraint
        self.MyConditions = []        #用於後面E-SSA Constraint Graph補充條件
        self.cfg = cfg             
        self.Arguments = []            #輸入參數
        self.returnName = ''        #輸出參數
# MyNode : Constraint Graph的節點，也就是保存變量范圍的地方
class MyNode:
    def __init__(self, t= "", name = "",  args = [], result = [], fromBlock = 0, Statement = ''):
        self.type = t             #節點類型：leave 葉節點存放范圍和值 #op運算符 #var變量名
        self.name = name.strip()  #節點名稱：運算名稱，或變量名稱
        self.args = args    #參數，一個節點是另一個節點的argument，意味著二者之間有邊相連
        self.result = result        #被用到哪，一個節點是另一個節點的result，意味著二者之間有邊相連
        self.Conditions = []        #約束條件， 在後面E-SSA Constraint Graph中補充條件
        self.fromBlock = fromBlock  #在CFG的哪個Block中定義的
        self.Statement = Statement  #在SSA中的哪條Statement中
        self.Range = Range()        #節點范圍
        self.size = ''
        self.input = False
# Range由兩個Bound組成 
class Range:
    def __init__(self ):
        self.lowBound = Bound()
        self.highBound = Bound()
# Bound由值和類型組成
class Bound:
    def __init__(self):
        self.value = 'None'      # inf 最大值 ； -inf 最小值; None 未設置； Not Exists 不存在
        self.size = 'None'       #邊界是 int or float

需要註意的是，在解決兩個函數之間的調用關系時，將被調用的函數**內聯進原函數**。我將被調用的函數的所有變量名都加入相應的後綴，比如`foo`調用`bar`函數，那麼`bar`中的變量`i_1`將被更名保存為`i_1#bar$1`，其中#是變量原名和後綴分割符，$是函數名和一個隨機數的分割符，\$的作用是為瞭區分多次調用同一個函數的情況。

3.3 構建E-SSA Constraint Graph

代碼：`\src\eSSAConstraintGraph.py`

這一步用於解決條件的添加。諸如`if (i_2 < j_3)`這樣的條件。在MyNode節點類型中，我設置瞭Conditions結構用於保存條件。Condition的數據結構如下：

 Class Description : Constraint Graph中的條件，附加在MyNode中

class MyCondition:
    def __init__(self, condition, index):
        self.condition = condition
        self.arg1 = re.sub("\(.*\)", "",condition.split()[0].strip())
        self.arg2 = re.sub("\(.*\)", "",condition.split()[2].strip())
        self.op = condition.split()[1].strip()
        self.index = index

其中，arg1和arg2分別表示條件的兩個參數，op表示條件的比較運算符。在Future Resolution這一步會進行比較，進行范圍的約束。

以t7.ssa為例，得到的E-SSA Constraint Graph如下：

call bar$1  in 2 : |Arguments: i_2,|Result: |Conditions: 
var i_2  in 2 : |Arguments: |Result: bar$1,i#bar$1,i_2#bar$1,|Conditions: 
var j_4  in 2 : |Arguments: _1#bar$1,|Result: bar$2,i#bar$2,i_2#bar$2,|Conditions: 
ret bar$1  in 2 : |Arguments: |Result: j_4,|Conditions: 
call bar$2  in 2 : |Arguments: j_4,|Result: |Conditions: 
var k_6  in 2 : |Arguments: _1#bar$2,|Result: _7,|Conditions: 
ret bar$2  in 2 : |Arguments: |Result: k_6,|Conditions: 
var _7  in 2 : |Arguments: k_6,|Result: |Conditions: 
var i_2#bar$1  in 3 : |Arguments: i_2,|Result: +,-,|Conditions: 0#bar$1 0|
leaf 10  in 3 : |Arguments: |Result: +,|Conditions: 
op +  in 3 : |Arguments: i_2#bar$1,10,|Result: _3#bar$1,|Conditions: 0#bar$1 0|
var _3#bar$1  in 3 : |Arguments: +,|Result: PHI,|Conditions: 0#bar$1 0|
leaf 5  in 4 : |Arguments: |Result: -,|Conditions: 
op -  in 4 : |Arguments: 5,i_2#bar$1,|Result: _4#bar$1,|Conditions: 0#bar$1 1|
var _4#bar$1  in 4 : |Arguments: -,|Result: PHI,|Conditions: 0#bar$1 1|
op PHI  in 4 : |Arguments: _3#bar$1,_4#bar$1,|Result: _1#bar$1,|Conditions: 0#bar$1 1|
var _1#bar$1  in 4 : |Arguments: PHI,|Result: j_4,|Conditions: 0#bar$1 1|
leaf i#bar$1  in  : |Arguments: i_2,|Result: |Conditions: 
var i_2#bar$2  in 3 : |Arguments: j_4,|Result: +,-,|Conditions: 0#bar$2 0|
leaf 10  in 3 : |Arguments: |Result: +,|Conditions: 
op +  in 3 : |Arguments: i_2#bar$2,10,|Result: _3#bar$2,|Conditions: 0#bar$2 0|
var _3#bar$2  in 3 : |Arguments: +,|Result: PHI,|Conditions: 0#bar$2 0|
leaf 5  in 4 : |Arguments: |Result: -,|Conditions: 
op -  in 4 : |Arguments: 5,i_2#bar$2,|Result: _4#bar$2,|Conditions: 0#bar$2 1|
var _4#bar$2  in 4 : |Arguments: -,|Result: PHI,|Conditions: 0#bar$2 1|
op PHI  in 4 : |Arguments: _3#bar$2,_4#bar$2,|Result: _1#bar$2,|Conditions: 0#bar$2 1|
var _1#bar$2  in 4 : |Arguments: PHI,|Result: k_6,|Conditions: 0#bar$2 1|
leaf i#bar$2  in  : |Arguments: j_4,|Result: |Conditions: 

Conditions:
i_2(D) >= 0#bar$1 0#bar$1,i_2(D) >= 0#bar$2 0#bar$2,
```http://www.biyezuopin.vip

3.4 三步法

3.4.1 Widen

代碼：`\src\rangeAnalysis.py`

Widen 步驟用於將 變量范圍擴大。此步驟可以在O(n)階段內完成。基於原理如下：可以形象的理解為：在進行Φ操作時，如果發現變量范圍向上增加，就直接擴大到inf，如果發現變量范圍向下減小，就直接減小到-inf。

這樣下來後，每一個MyNode的范圍都會擴大到最大。

3.4.2 Future Resolution &  Narrow

代碼：`\src\rangeAnalysis.py`

在Widen步驟中，隻能解決每一個變量內部之間的賦值行為，在Future Resolution步驟，可以對變量之間的運算、以及條件進行處理。

我用瞭復雜的`ConditionHandle()`函數來解決條件變量的Constraint問題。我在每一個MyNode中添加瞭Conditions結構，用Condition約束來代替變量替換。這樣可以大大減少變量替換帶來的麻煩。

在`ConditionHandle()`中，我將條件拆分成`arg1` `arg2`和`op`三部分，將他們組合成條件為真的范圍，和條件為假的范圍。並把相應的范圍賦給相應的變量，以及檢查此路徑是否可以相通。

以`t7.ssa`為例，三步法得到的所有變量的范圍如下：

Enter Range For i: -10 10
bar$1 None None | Range:  Not Exists Not Exists
i_2 int int | Range:  -10 10
j_4 int int | Range:  0 20
bar$1 None None | Range:  Not Exists Not Exists
bar$2 None None | Range:  Not Exists Not Exists
k_6 int int | Range:  5 30
bar$2 None None | Range:  Not Exists Not Exists
_7 int int | Range:  5 30
i_2#bar$1 int int | Range:  -10 10
10 None None | Range:  10 10
+ int int | Range:  0 20
_3#bar$1 int int | Range:  0 20
5 None None | Range:  5 5
- int int | Range:  Not Exists Not Exists
_4#bar$1 int int | Range:  15 -5
PHI int int | Range:  0 20
_1#bar$1 int int | Range:  0 20
i#bar$1 None None | Range:  Not Exists Not Exists
i_2#bar$2 int int | Range:  0 20
10 None None | Range:  10 10
+ int int | Range:  10 30
_3#bar$2 int int | Range:  10 30
5 None None | Range:  5 5
- int int | Range:  Not Exists Not Exists
_4#bar$2 int int | Range:  5 -15
PHI int int | Range:  5 30
_1#bar$2 int int | Range:  5 30
i#bar$2 None None | Range:  Not Exists Not Exists

可以直接得到結果變量_7的范圍為：_7 int int | Range: 5 30

4. 實驗結果

# t1.SSA
Reference Range:[100, 100]
Output Range: [100, +inf]
# t2.SSA
Reference Range:[200, 300]
Output Range: [200, +inf]
# t3.SSA
Reference Range:[20, 50]
Output Range: [20, +inf]
# t4.SSA
Reference Range:[0, +inf]
Output Range: [0, +inf]
# t5.SSA
Reference Range:[210, 210]
Output Range: [0, +inf]
# t6.SSA
Reference Range:[-9, 10]
Output Range: [-9, 10]
# t7.SSA
Reference Range:[16, 30]
Output Range: [5, 30]
# t8.SSA
Reference Range:[-3.2192308, 5.94230769]
Output Range: [-0.41923075526423315, 14.700000286102295]
# t9.SSA
Reference Range:[9791, 9791]
Output Range: [-10, +inf]
# t10.SSA
Reference Range:[-10, 40]
Output Range: [1, 1]

5. 總結

在本實驗中，我采用python語言對SSA形式的C程序進行解析，並采用三步法針對特定輸入進行瞭相應的范圍分析。收貨瞭寫代碼的樂趣，也為最後的效果遺憾。

最後的效果中，10個benchmark的結果中準確結果寥寥無幾。尤其是上界，很多都直接到無窮瞭。這一方面是為瞭追求時間效率和空間效率，放棄瞭模擬執行采用三步法的缺陷，另一方面也是因為我沒有想到合適的改進方法。

到此這篇關於如何利用Python實現簡單C++程序范圍分析的文章就介紹到這瞭,更多相關Python實現簡單C++程序范圍分析內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：