如何利用Python實現(xiàn)簡單C++程序范圍分析

更新時間：2022年02月20日 14:29:51 作者：biyezuopinvip

這篇文章主要介紹了如何利用Python實現(xiàn)簡單C++程序范圍分析,文章以舉例說明及過程實現(xiàn)思路的方式展開講解，具有一定的的參考價值，需要的小伙伴可以參考一下，希望對你有所幫助

1. 實驗說明

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

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

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

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

2. 項目使用

python main.py （ssa文件路徑在main.py中設(shè)置）

不需要安裝任何庫。

3. 算法原理

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

3.1 構(gòu)建CFG

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

功能：解析SSA，構(gòu)建CFG。

由于函數(shù)之間存在調(diào)用關(guān)系，因此首先把SSA劃分成不同的函數(shù)的SSA，再分別構(gòu)建CFG。CFG中保留了每一個函數(shù)的語句、Block之間的關(guān)系，為下一步構(gòu)建Constraint Graph打基礎(chǔ)。

CFG的結(jié)構(gòu)如下：

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

3.2 構(gòu)建Constraint Graph

代碼：\src\eSSAConstraintGraph.py

三步法的前提是構(gòu)建Constraint Graph。數(shù)據(jù)結(jié)構(gòu)如下。在這一步中，我用自己定義的數(shù)據(jù)類型MyNode來表示一條Constraint。

# Constraint Graph類 ? ? ?
class ConstraintGraph:
? ? def __init__(self, cfg):
? ? ? ? self.MyNodes = []?? ??? ??? ?#基本節(jié)點(diǎn)，每一個節(jié)點(diǎn)是一個Constraint
? ? ? ? self.MyConditions = []?? ??? ?#用于后面E-SSA Constraint Graph補(bǔ)充條件
? ? ? ? self.cfg = cfg?? ??? ??? ??
? ? ? ? self.Arguments = []?? ??? ??? ?#輸入?yún)?shù)
? ? ? ? self.returnName = ''?? ??? ?#輸出參數(shù)
# MyNode : Constraint Graph的節(jié)點(diǎn)，也就是保存變量范圍的地方
class MyNode:
? ? def __init__(self, t= "", name = "", ?args = [], result = [], fromBlock = 0, Statement = ''):
? ? ? ? self.type = t ?? ??? ??? ?#節(jié)點(diǎn)類型：leave 葉節(jié)點(diǎn)存放范圍和值 #op運(yùn)算符 #var變量名
? ? ? ? self.name = name.strip() ?#節(jié)點(diǎn)名稱：運(yùn)算名稱，或變量名稱
? ? ? ? self.args = args?? ?#參數(shù)，一個節(jié)點(diǎn)是另一個節(jié)點(diǎn)的argument，意味著二者之間有邊相連
? ? ? ? self.result = result ? ? ? ?#被用到哪，一個節(jié)點(diǎn)是另一個節(jié)點(diǎn)的result，意味著二者之間有邊相連
? ? ? ? self.Conditions = [] ? ? ? ?#約束條件， 在后面E-SSA Constraint Graph中補(bǔ)充條件
? ? ? ? self.fromBlock = fromBlock ?#在CFG的哪個Block中定義的
? ? ? ? self.Statement = Statement ?#在SSA中的哪條Statement中
? ? ? ? self.Range = Range()?? ??? ?#節(jié)點(diǎn)范圍
? ? ? ? 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 未設(shè)置； Not Exists 不存在
? ? ? ? self.size = 'None' ? ? ? #邊界是 int or float

需要注意的是，在解決兩個函數(shù)之間的調(diào)用關(guān)系時，將被調(diào)用的函數(shù)**內(nèi)聯(lián)進(jìn)原函數(shù)**。我將被調(diào)用的函數(shù)的所有變量名都加入相應(yīng)的后綴，比如`foo`調(diào)用`bar`函數(shù)，那么`bar`中的變量`i_1`將被更名保存為`i_1#bar$1`，其中#是變量原名和后綴分割符，$是函數(shù)名和一個隨機(jī)數(shù)的分割符，\$的作用是為了區(qū)分多次調(diào)用同一個函數(shù)的情況。

3.3 構(gòu)建E-SSA Constraint Graph

代碼：`\src\eSSAConstraintGraph.py`

這一步用于解決條件的添加。諸如`if (i_2 < j_3)`這樣的條件。在MyNode節(jié)點(diǎn)類型中，我設(shè)置了Conditions結(jié)構(gòu)用于保存條件。Condition的數(shù)據(jù)結(jié)構(gòu)如下：

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分別表示條件的兩個參數(shù)，op表示條件的比較運(yùn)算符。在Future Resolution這一步會進(jìn)行比較，進(jìn)行范圍的約束。

以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 步驟用于將變量范圍擴(kuò)大。此步驟可以在O(n)階段內(nèi)完成?；谠砣缦拢嚎梢孕蜗蟮睦斫鉃椋涸谶M(jìn)行Φ操作時，如果發(fā)現(xiàn)變量范圍向上增加，就直接擴(kuò)大到inf，如果發(fā)現(xiàn)變量范圍向下減小，就直接減小到-inf。

這樣下來后，每一個MyNode的范圍都會擴(kuò)大到最大。

3.4.2 Future Resolution & Narrow

代碼：`\src\rangeAnalysis.py`

在Widen步驟中，只能解決每一個變量內(nèi)部之間的賦值行為，在Future Resolution步驟，可以對變量之間的運(yùn)算、以及條件進(jìn)行處理。

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

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

以`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

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

4. 實驗結(jié)果

# 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]