如何利用Python實(shí)現(xiàn)簡(jiǎn)單C++程序范圍分析
1. 實(shí)驗(yàn)說(shuō)明
問(wèn)題要求：針對(duì)靜態(tài)單賦值（SSA）形式的函數(shù)中間代碼輸入，輸出函數(shù)返回值的范圍
實(shí)現(xiàn)思路： 基本根據(jù) 2013年在CGO會(huì)議上提出的“三步法”范圍分析法加以實(shí)現(xiàn)[3]，求得各個(gè)變量的范圍
算法優(yōu)勢(shì)：空間復(fù)雜度和時(shí)間復(fù)雜度都是 O(n)，效率高
算法瓶頸： “三步法”的功能存在較大局限，它只能分析各個(gè)變量的最大范圍，對(duì)活躍變量只做了最簡(jiǎn)單的考慮，因此最終得到的范圍比較不準(zhǔn)確，往往只能得到范圍的一個(gè)界
2. 項(xiàng)目使用
python main.py （ssa文件路徑在main.py中設(shè)置）
不需要安裝任何庫(kù)。
3. 算法原理
簡(jiǎn)單概括：采用三步法（2013年在CGO會(huì)議上提出）
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中保留了每一個(gè)函數(shù)的語(yǔ)句、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來(lái)表示一條Constraint。
# Constraint Graph類 ? ? ? class ConstraintGraph: ? ? def __init__(self, cfg): ? ? ? ? self.MyNodes = []?? ??? ??? ?#基本節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)是一個(gè)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ù)，一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的argument，意味著二者之間有邊相連 ? ? ? ? self.result = result ? ? ? ?#被用到哪，一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的result，意味著二者之間有邊相連 ? ? ? ? self.Conditions = [] ? ? ? ?#約束條件， 在后面E-SSA Constraint Graph中補(bǔ)充條件 ? ? ? ? self.fromBlock = fromBlock ?#在CFG的哪個(gè)Block中定義的 ? ? ? ? self.Statement = Statement ?#在SSA中的哪條Statement中 ? ? ? ? self.Range = Range()?? ??? ?#節(jié)點(diǎn)范圍 ? ? ? ? self.size = '' ? ? ? ? self.input = False # Range由兩個(gè)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
需要注意的是，在解決兩個(gè)函數(shù)之間的調(diào)用關(guān)系時(shí)，將被調(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ù)名和一個(gè)隨機(jī)數(shù)的分割符，\$的作用是為了區(qū)分多次調(diào)用同一個(gè)函數(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分別表示條件的兩個(gè)參數(shù)，op表示條件的比較運(yùn)算符。在Future Resolution這一步會(huì)進(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)完成。基于原理如下：可以形象的理解為：在進(jìn)行Φ操作時(shí)，如果發(fā)現(xiàn)變量范圍向上增加，就直接擴(kuò)大到inf，如果發(fā)現(xiàn)變量范圍向下減小，就直接減小到-inf。
這樣下來(lái)后，每一個(gè)MyNode的范圍都會(huì)擴(kuò)大到最大。
3.4.2 Future Resolution & Narrow
代碼：`\src\rangeAnalysis.py`
在Widen步驟中，只能解決每一個(gè)變量?jī)?nèi)部之間的賦值行為，在Future Resolution步驟，可以對(duì)變量之間的運(yùn)算、以及條件進(jìn)行處理。
我用了復(fù)雜的`ConditionHandle()`函數(shù)來(lái)解決條件變量的Constraint問(wèn)題。我在每一個(gè)MyNode中添加了Conditions結(jié)構(gòu)，用Condition約束來(lái)代替變量替換。這樣可以大大減少變量替換帶來(lái)的麻煩。
在`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. 實(shí)驗(yàn)結(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]
5. 總結(jié)
在本實(shí)驗(yàn)中，我采用python語(yǔ)言對(duì)SSA形式的C程序進(jìn)行解析，并采用三步法針對(duì)特定輸入進(jìn)行了相應(yīng)的范圍分析。收貨了寫代碼的樂(lè)趣，也為最后的效果遺憾。
最后的效果中，10個(gè)benchmark的結(jié)果中準(zhǔn)確結(jié)果寥寥無(wú)幾。尤其是上界，很多都直接到無(wú)窮了。這一方面是為了追求時(shí)間效率和空間效率，放棄了模擬執(zhí)行采用三步法的缺陷，另一方面也是因?yàn)槲覜](méi)有想到合適的改進(jìn)方法。
到此這篇關(guān)于如何利用Python實(shí)現(xiàn)簡(jiǎn)單C++程序范圍分析的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)簡(jiǎn)單C++程序范圍分析內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Python與C++中梯度方向直方圖的實(shí)現(xiàn)
- C++和python實(shí)現(xiàn)單鏈表及其原理
- c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)
- c++和python實(shí)現(xiàn)順序查找實(shí)例
- python?與c++相互調(diào)用實(shí)現(xiàn)
- python直接調(diào)用和使用swig法方調(diào)用c++庫(kù)
- 如何在C++中調(diào)用python代碼你知道嗎
- C++調(diào)用python(執(zhí)行py文件)的全過(guò)程
- C++通過(guò)內(nèi)嵌解釋器調(diào)用Python及間接調(diào)用Python三方庫(kù)
- Python 調(diào)用 C++ 傳遞numpy 數(shù)據(jù)詳情
相關(guān)文章
基于Python實(shí)現(xiàn)全自動(dòng)下載抖音視頻
這篇文章主要介紹了基于Python實(shí)現(xiàn)全自動(dòng)下載抖音視頻,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
這篇文章主要介紹了pycharm顯示行號(hào)的方法,需要的朋友可以參考下2014-06-06
在開(kāi)發(fā)Python程序的時(shí)候，有時(shí)候可能需要在不同版本的Python上進(jìn)行測(cè)試。pyenv就是這么一個(gè)管理多版本Python的工具，今天給大家分享Python版本管理工具Pyenv使用，感興趣的朋友一起看看吧2021-06-06
Python實(shí)現(xiàn)自動(dòng)化處理每月考勤缺卡數(shù)據(jù)
不管是上學(xué)還是上班都會(huì)統(tǒng)計(jì)考勤，有些學(xué)?；蚬緯?huì)對(duì)每月缺卡次數(shù)過(guò)多(比如三次以上)的人員進(jìn)行處罰。本文提供了Python自動(dòng)處理考勤和日志缺失的方法，需要的可以參考一下2022-06-06
Django集成Celery實(shí)現(xiàn)高效的異步任務(wù)處理的全過(guò)程
Django?作為一個(gè)強(qiáng)大的?Python?Web?框架,可以通過(guò)集成?Celery?這一異步任務(wù)隊(duì)列來(lái)優(yōu)化這些任務(wù)的處理,本文將深入探討如何在?Django?項(xiàng)目中集成?Celery,包括?Celery?的基本配置、定義任務(wù)、以及監(jiān)控任務(wù)執(zhí)行,需要的朋友可以參考下2023-11-11
今天有同學(xué)問(wèn)我,這種情況應(yīng)該怎么調(diào)用,才能讓remove_outdated_data.py正確導(dǎo)入models里面的模塊,下面通過(guò)本文介紹下Python工具腳本調(diào)用外層模塊的方法,感興趣的朋友一起看看吧2024-02-02
使用Python發(fā)送郵件附件以定時(shí)備份MySQL的教程
這篇文章主要介紹了使用Python發(fā)送郵件附件以定時(shí)備份MySQL的教程,本文的示例基于CentOS,需要的朋友可以參考下2015-04-04
詳解Python編程中基本的數(shù)學(xué)計(jì)算使用
這篇文章主要介紹了Python編程中基本的數(shù)學(xué)計(jì)算使用,其中重點(diǎn)講了除法運(yùn)算及相關(guān)division模塊的使用,需要的朋友可以參考下2016-02-02
Python爬蟲(chóng)必備技巧詳細(xì)總結(jié)
本篇文章介紹了我在爬蟲(chóng)過(guò)程中總結(jié)的幾個(gè)必備技巧，都是經(jīng)過(guò)實(shí)驗(yàn)的，通讀本篇對(duì)大家的學(xué)習(xí)或工作具有一定的價(jià)值，需要的朋友可以參考下2021-10-10
Python實(shí)現(xiàn)為圖片批量添加隨機(jī)水印
這篇文章主要為大家詳細(xì)介紹了如何使用Python實(shí)現(xiàn)為圖片批量添加隨機(jī)水印,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-11-11