没有合适的资源?快使用搜索试试~ 我知道了~
首页图可达性方法下的精确程序间数据流分析
"《基于图可达性的精确过程间数据流分析》是一篇深入探讨程序间数据流分析方法的论文,由Thomas Reps、Susan Horwitz和Mooly Sagiv共同撰写。论文的核心内容是介绍了一种创新的解决方案,能够在多项式时间内解决一系列复杂的过程间数据流分析问题,从而实现精确求解。这种转化的关键在于将问题转换为图可达性问题,适用于诸如可达性分析、可用表达式问题和活变量问题等经典可分离问题,同时也处理了诸如真正活变量、复制常量传播以及可能未初始化变量等不可分离问题。 传统的精确过程间数据流分析通常追求在所有有效路径上都满足分析结果,而这里的“精确”意味着不仅考虑单个路径,而是所有可能的执行路径。该方法的独特之处在于,它突破了过去研究的局限,如针对特定问题的多项式时间算法(如恒定传播、流敏感分析和指针分析),以及仅限于局部可分问题(如经典的“位向量”或“gen/kill”问题版本)的算法。这些先前的研究要么只针对特定问题,要么处理的是一般性问题但缺乏多项式时间复杂度的解决方案。 论文作者通过从C程序的初步实验中验证了这种方法的有效性,特别关注了寻找可能未初始化变量的问题。相比于已有的工作,本文提出的算法具有普适性,可以处理一个广泛的问题类别,填补了多项式时间算法在一般过程间数据流分析中的空白。这一成果对于理解和优化复杂软件系统的性能和安全性具有重要意义,因为它能确保数据流分析的结果在所有可能的程序执行路径上都是准确无误的。" 这篇文章在数据流分析领域具有开创性价值,不仅提升了分析效率,还扩大了精确数据流分析的适用范围,使得开发者能够更深入地理解和控制程序的行为,有助于提高软件的质量和可靠性。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/12500474/bg6.jpg)
2.分配过程间数据流分析问题IFDS框架
IFDS
框架是
Sharir
和
Pnueli
的
“
功能方法
”
的变体,用于过程间数据流分析
[31]
,其
扩展类似于
Knoop
和
Steffen
给出的扩展,以便处理递归过程具有局部变量和参数的程序
[21]
。这些框架将
Kildall
关于过程内数据流分析问题的
“
全路径满足
”
解决方案
[20]
的概
念推广到过程间数据流分析问题的
“
全路径满足
”
解决方案。
IFDS
框架的设计尽可能笼统(特别是支持有程序调用、参数以及全局和局部变量
的语言)。在这个框架中可以指定的任何问题都可以使用我们的算法有效地解决;语
义正确性是一个正交问题。希望利用我们的结果的问题设计者有两个义务:(
Ⅰ)
对问题
进行编码,使其满足我们框架的条件;
(Ⅱ
)表明编码与编程语言的语义一致
[9
,
10]
。
在
IFDS
框架中对问题进行编码可能会导致精度的损失。例如,在通过引用传递参数的
语言中,存在别名的问题实例可能会失去精度。但是,找到
IFDS
问题的解决方案的过
程不会带来精度的进一步损失。
要指定
IFDS
框架,我们需要以下定义:
定义
2.1
在
IFDS
框架中,程序
a
使用称为超图的有向图
G*=(N*
,
E*)
表示。
G*
由流图集合
G1
,
G2,···
(每个程序一个)组成,其中一个,
G
main
代表程序的主要程序。每个流程图
G
p
都有一个唯一的开始节点
s
p
,和一个唯一的
退出节点
e
p
。流图的其他节点以通常的方式表示过程的语句和谓词,只是过程调用由
两个节点表示,一个调用节点和一个返回点节点
(
过程
p
的调用和返回点节点集分别用
Call
p
和
Ret
p
表示;超图中所有调用和返回站点节点集分别用
Call
和
Ret
表示
)
。
除了连接单个流图节点的普通过程内边外,对于每个程序调用,用调用节点
c
和返
回点节点
r
表示,
G*
有三个边:
一种过程内的从
c
到
r
的
“
调用
-
返回点边
”
(
call-to-return-siteedge
);
一种从
c
到程序调用开始节点的
“
过程间调用
-
开始边
”
(
call-to-startedge
);
一种过程间的从程序退出点到
r
的
“
退出
-
返回点边
”
(
exit-to-return-site
)。
![](https://csdnimg.cn/release/download_crawler_static/12500474/bg7.jpg)
(call-to-return-site
也包括在内,这样
IFDS
框架就可以处理带有本地变量和参数的程
序。在
call-to-return-site
和
exit-to-return-site
边上的数据流函数允许有关保存在调用站点
上的局部变量的信息与保存在被调用过程末尾的全局变量的信息相结合)。
在讨论时间和空间需求时,我们使用集合的名称来表示集合的大小。例如,我们
使用
Call
,而不是
|Call|
来表示图
G
中的调用节点数
(
我们与本约定有两个小的偏差,分
别使用
|N*|
和
|E*|)
。
例图
1
显示了一个示例程序及其超图
G*
。
定义
2.2
一个长度为
j
的
path
从节点
m
到节点
n
的路径是一个
j
边的(可能是空的)序
列,可以表示为
[e
1
,
e
2
,
···
,
e
j
]
,其中对于所有的
i
,
1≤i≤j-1
,边
e
i
是边
e
i+1
的来源。
“(
程序间
)
有效路径
”
(
interprocedurallyvalidpath
)的概念抓住了这样一个概念
:
并不是
G
中的所有路径都代表潜在的执行路径。
定义
2.3
令
G*
中的每个调用节点都有一个惟一的索引
i
。对于每个这样的索引调用节
点
c
i
,用符号
“(
i
”
标记
c
i
的
call-to-start
边出口;用符号
“)
i
”
标记相应的
exit-to-return-site
节点的入
口。
对于同一过程中的每一对节点
m
,
n
,从
m
到
n
的路径是一个相同
同级有效路径
,如
果路径中标记的边序列
是由以下无上下文语法匹配的非终端生成的平衡括号语
言中的字
符串:
对于超图
G*
中的每一对节点
m,n
,一条从
m
到
n
的路径是一个
有效路径
,如果路径
中标记边的序列是一个由非终结符产生的语言字符串,在以下语法中是
有效的
(
在这里
匹配的定义如上所示
):
我们用
IVP(m
,
n)
表示从
m
到
n
的所有有效路径的集合。
*
无效路径例子(译注):
剩余30页未读,继续阅读
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
attitude_y
- 粉丝: 2
- 资源: 2
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)