如何利用Python实现简单C++程序范围分析

目录
  • 1.实验说明
  • 2.项目使用
  • 3.算法原理
    • 3.1构建CFG
    • 3.2构建ConstraintGraph
    • 3.3构建E-SSAConstraintGraph
    • 3.4三步法
      • 3.4.1Widen
      • 3.4.2FutureResolution& Narrow
  • 4.实验结果
  • 5.总结

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++程序范围分析内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++通过内嵌解释器调用Python及间接调用Python三方库

    目录 1.移植Python解释器 2.VS配置(VS2017为例,此教程与VS版本无关) 3.C++调用程序样例 4.被调Python程序样例 本文章目的是脱离安装Python环境的前提下,由C++程序调用Python程序及Python相关三方库 1.移植Python解释器 Python环境的目录结构 路径详解 需要用的如下图 1.红色部分是生成路径下解释器运行时依赖 将红色部分拷贝到C++编译主ExE路径下即可 2.蓝色部分是VS配置编译时依赖 路径或文件名 作用 DLLs Python内部运

  • 如何在C++中调用python代码你知道吗

    目录 一.环境设置 二.VS项目中设置 (1)首先在acaconda中找到include文件夹和libs文件夹,如图所示 (2)点击链接器,然后输入,附加依赖项,添加python36_d.lib的路径 (3)python代码 三.可能会出现的问题 总结 一.环境设置 windows VS2015 python的话用的是acaconda自带的python环境,不同版本的acaconda自带的python不同,我的是python3.6(这一步很重要,如果使用acaconda创建的虚拟环境的pytho

  • Python与C/C++的相互调用案例

    一.问题 Python模块和C/C++的动态库间相互调用在实际的应用中会有所涉及,在此作一总结. 二.Python调用C/C++ 1.Python调用C动态链接库 Python调用C库比较简单,不经过任何封装打包成so,再使用python的ctypes调用即可. (1)C语言文件:pycall.c /***gcc -o libpycall.so -shared -fPIC pycall.c*/ #include <stdio.h> #include <stdlib.h> int f

  • python模块与C和C++动态库相互调用实现过程示例

    目录 Python调用C/C++ 1.Python调用C动态链接库 C语言文件:pycall.c gcc编译生成动态库libpycall.so Python调用动态库的文件:pycall.py 运行结果: 2.Python调用C/C++原生态导出 3.Python调用C/C++通过boost实现 4.Python调用C/C++通过导出类 5.Python调用C/C++通过导出变参函数 6.Python调用C/C++通过导出带Python对象的接口 Python调用C/C++ 1.Python调用

  • C++调用python(执行py文件)的全过程

    1.首先要配好vs开发工程 注意版本:我这使用32位的python那么我vs工程这边也选择32位的编译环境去配置 注意点:需要将python安装目录的一些文件拷过来作为vs工程使用. 2.C++调用Python结果 py代码 这里引用了cdll库也需要放置到运行目录,py文件也是需要放置到运行目录(也就是exe生成所在目录) import os import time from ctypes import * def testDLL(): pDll = CDLL("./pythonTestCDl

  • 如何利用Python实现简单C++程序范围分析

    目录 1.实验说明 2.项目使用 3.算法原理 3.1构建CFG 3.2构建ConstraintGraph 3.3构建E-SSAConstraintGraph 3.4三步法 3.4.1Widen 3.4.2FutureResolution& Narrow 4.实验结果 5.总结 1. 实验说明 问题要求:针对静态单赋值(SSA)形式的函数中间代码输入,输出函数返回值的范围 实现思路: 基本根据 2013年在CGO会议上提出的“三步法”范围分析法加以实现[3],求得各个变量的范围 算法优势:空间复

  • 利用Python实现批量打包程序的工具

    目录 程序调用cmd命令 os.system() os.popen() subprocess.run() 程序实现 GUI界面设计 逻辑设计 打包函数 最近看了一些大佬发的关于可视化打包工具auto-py-to-exe文章,auto-py-to-exe是基于pyinstaller,但相比于pyinstaller,它多了 GUI 界面.我自己也试了一下,感觉确实好用且方便,动动手指就能对程序进行打包. 但我发现auto-py-to-exe与pyinstaller都无法直接一次性打包多个程序,想打包

  • python实现简单socket程序在两台电脑之间传输消息的方法

    本文实例讲述了python实现简单socket程序在两台电脑之间传输消息的方法.分享给大家供大家参考.具体分析如下: python开发简单socket程序在两台电脑之间传输消息,分为客户端和服务端,分别在两台电脑上运行后即可进行简单的消息传输,也可以在一台电脑上测试,设置两个不同的端口即可. # Save as server.py 服务端代码 # Message Receiver import os from socket import * host = "" port = 13000

  • 利用python实现简单的邮件发送客户端示例

    脚本过于简单,供学习和参考.主要了解一下smtplib库的使用和超时机制的实现.使用signal.alarm实现超时机制. #!/usr/bin/env python # -*- coding: utf-8 -*- import time import sys import logging import smtplib import socket import signal import ConfigParser from datetime import datetime from email

  • 利用python实现简单的情感分析实例教程

    目录 1 数据导入及预处理 1.1 数据导入 1.2 数据描述 1.3 数据预处理 2 情感分析 2.1 情感分 2.2 情感分直方图 2.3 词云图 2.4 关键词提取 3 积极评论与消极评论 3.1 积极评论与消极评论占比 3.2 消极评论分析 总结 python实现简单的情感分析 1 数据导入及预处理 1.1 数据导入 # 数据导入 import pandas as pd data = pd.read_csv('../data/京东评论数据.csv') data.head() 1.2 数据

  • 利用Python实现简单的Excel统计函数

    目录 需求分析 解决步骤 最终结果 技术总结 需求分析 根据原始数据,计算出累计和.回撤.连续正确.连续错误.连续正确值与连续错误值6项数据,其中原始数据大于等于0认定为正确,原始数据小于0为错误.明白了要求,那我们就开始撸代码吧~ 解决步骤 import pandas as pd #创建一个计算数据的函数 def calculate(df): pass #读取原始数据,将索引列去除 df = pd.read_excel('需求0621.xlsx',index_col=0) #调用计算数据的函数

  • 利用Python实现简单的验证码处理

    目录 序言 环境模块 代码展示 完整代码 序言 我们在做采集数据的时候,过快或者访问频繁,或者一访问就给弹出验证码,然后就蚌珠了~ 今天就给大家来一个简单处理验证码的方法 环境模块 这里需要用到一个 ddddocr 模块 ,这是别人开源写好的一个东西,简单又好用,但是精确度差一点点,但是还是非常好用的. 如果你追求精确度的话,可以调用别人写好的一些API . 咱们直接 win+r 弹出搜索框后输入 cmd ,点击确定弹出命令提示符窗口, 输入pip install ddddocr 即可安装. 不

  • go语言简单网络程序实例分析

    本文实例分析了go语言简单网络程序.分享给大家供大家参考.具体分析如下: 服务端代码如下: 复制代码 代码如下: package main import (     "net"     "os" ) func serve(s net.Conn) {     var buf [1024]byte     for {         n, err := s.Read(&buf)         if err != nil || n == 0 {         

  • 利用Python实现简单的相似图片搜索的教程

    大概五年前吧,我那时还在为一家约会网站做开发工作.他们是早期创业公司,但他们也开始拥有了一些稳定用户量.不像其他约会网站,这家公司向来以洁身自好为主要市场形象.它不是一个供你鬼混的网站--是让你能找到忠实伴侣的地方. 由于投入了数以百万计的风险资本(在US大萧条之前),他们关于真爱并找寻灵魂伴侣的在线广告势如破竹.Forbes(福布斯,美国著名财经杂志)采访了他们.全国性电视节目也对他们进行了专访.早期的成功促成了事业起步时让人垂涎的指数级增长现象--他们的用户数量以每月加倍的速度增长.对他们而

  • 利用python实现简单的循环购物车功能示例代码

    本文主要给大家介绍了关于python实现循环购物车功能的相关内容,分享出来供大家参考学习,下面来一起看看详细的介绍: 示例代码 # -*- coding: utf-8 -*- __author__ = 'hujianli' shopping = [ ("iphone6s", 5000), ("book python", 81), ("iwach", 3200), ("电视机", 2200) ] def zero(name):

随机推荐