P11-12
2021-04-30 15:58:40 1 举报AI智能生成
南大软件分析P11-12
作者其他创作
大纲/内容
Introduction
引入
上下文无关（非敏感）的指向分析的问题
多个上下文的情况下，会造成误报和常量传播结果的不准确。
上下文相关（敏感）指向分析能够有效解决上下文无关（非敏感）指向分析存在的问题
上下文非敏感（Context Insensitivity (C.I.)）的不精确
在动态执行中，一个方法可能在不同的调用上下文下被多次调用。
在不同的调用上下文下，方法的变量可能指向不同的对象。
在C.I. 指向分析中，将不同上下文下的对象混合并传播到程序的其他部分（通过返回值或副作用），会导致虚假的数据流。
上下文敏感（Context Sensitivity (C.S.)）
上下文敏感模型通过区分不同上下文的不同数据流来调用上下文，以提高精度。
最古老和最著名的上下文敏感策略是调用点敏感（call-site sensitivity (call-string)）。
它将方法的每个上下文表示为一系列调用点，即
a call site of the method,
a call site of the caller,
a call site of caller of caller, etc.
a call site of the caller,
a call site of caller of caller, etc.
（动态执行中的抽象调用堆栈）
后面将会讲到上下文敏感的其他变体。
基于克隆的上下文敏感（Cloning-Based Context Sensitivity）
实现上下文敏感最直接的方法。
在基于克隆的上下文相关指向分析中，
每种方法都由一个或多个上下文限定。
变量也由上下文限定（从声明它们的方法继承）。
本质上，每种方法及其变量都是克隆的，每个上下文对应一个克隆。
上下文敏感堆（Context-Sensitive Heap）
OO程序（例如Java）通常是堆密集型的
在实践中，为了提高精度，还应将上下文敏感度应用于堆抽象。
抽象对象也由上下文（称为堆上下文）限定。
最常见的选择是从分配对象的方法中继承上下文。
上下文敏感的堆抽象提供了比分配点抽象更细粒度的堆模型。
为什么上下文相关堆可以提高精度？
在动态执行中，分配点可以在不同的调用上下文下创建多个对象。
可以使用不同的数据流来操作不同的对象（由同一站点分配），例如，将不同的值存储到其字段中。
在指向分析中，通过将不同上下文的数据流合并到一个抽象对象，来分析没有堆上下文的代码，可能会失去精度。
相反，通过堆上下文区分同一分配点中的不同对象，将获得更高的精度。
一个例子
过程
结果
由于缺少C.S.堆而导致虚假数据流。上下文敏感的堆提高了精度。
上下文敏感（C.S.）和上下文敏感堆（C.S.heap）的区分
没有C.S.，C.S.堆也无法提高精度。
个人注释：上下文敏感（C.S.）是针对普通变量的，
上下文敏感堆（C.S.heap）是针对分配点抽象（Allocation-site abstraction）的。
上下文敏感堆（C.S.heap）是针对分配点抽象（Allocation-site abstraction）的。
Context Sensitive Pointer Analysis: Rules
Domains and Notations（域和符号）
在上下文相关的分析中，程序元素由上下文限定。
Rules（规则）
总览
上下文非敏感
上下文敏感
New
Assign
Store
Load
总结
Call
规则
符号的含义
Dispatch(oi, k)
将Oi上的 k 的虚拟分派解析为目标方法（基于Oi 的类型）。
Select(c, l, c':oi)
根据调用点 l 上可用的信息，选择目标方法 m 的上下文。
ct: mthis
ct: m的this变量
ct: mpj
ct: m的第 j 个参数
ct: mret
保存ct: m的返回值的变量
Context Sensitive Pointer Analysis: Algorithms
How to Implement Context-Sensitive Pointer Analysis
上下文非敏感指向分析和上下文敏感指向分析
Pointer Flow Graph with C.S.
上下文敏感的指向流图（C.S.PFG）
定义
程序的指向流图是一个有向图，它表示对象在程序中的指针之间如何流动。
节点
CSPointer = (C × V) ⋃ (C × O × F)
节点n表示上下文敏感的变量或上下文敏感的抽象对象的字段。
对于C.S.，节点（指针）由上下文限定。
边
CSPointer × CSPointer
边 x-> y 表示指针x指向的对象可能会流向指针y（也被指针y指向）。
一个例子
PFG在方法id()中包含变量 n 的两个节点，每个上下文一个节点。
边
PFG边是根据程序的语句和相应的规则添加的。
Call
算法
C.I. Pointer Analysis: Algorithm
C.S. Pointer Analysis: Algorithm
和C.I.指向分析区别的地方/C.S.算法执行的大致过程
Solve(mentry)
AddReachable(c: m)//处理New、Assign
AddEdge(s,t)/Propagate(n,pts)和C.I.指向分析相同
//处理Store、Load
ProcessCall(c: x, c': oi)
Context Sensitivity Variants
引入
Context Sensitivity Variants（上下文敏感的变体）
Context Insensitivity（上下文非敏感）
可以视为C.S.分析框架中上下文敏感的一种特殊情况
Call-Site Sensitivity*（调用点敏感）
每个上下文都包含一个调用点列表（调用链）
在方法调用中，将调用点作为被调用者上下文附加到调用者上下文中
本质上是调用栈的抽象
也称为 call-string 敏感，或k-CFA。
例子
k-Limiting Context Abstraction
Motivation
确保指向分析的终止。
避免在实际的程序中，过多的上下文（长调用链）破坏指向分析。
方法：设置上下文长度的上限，用k表示
对于调用点敏感，每个上下文由调用链中的最后k个调用点组成。
实际上，k是一个很小的数字（通常≤3）。
方法上下文和堆上下文可以使用不同的k
例如，对于方法上下文，k = 2，对于堆上下文，k = 1。
k-Call-Site Sensitivity/k-CFA
1-call-site/1-CFA
Select _,l,_ = [l]
2-call-site/2-CFA
Select c,l,_ = [l", l] where c = [l', l"]
1-Call-Site的1个例子
为简单起见，这里不应用C.S.heap并忽略C.id（Number）的this变量。
结果
C.I. vs C.S. (1-Call-Site)
Object Sensitivity*（对象敏感）
引入
每个上下文都包含一个抽象对象列表（由其分配位置表示）
在方法调用时，将接收对象及其堆上下文用作被调用者上下文。
区分不同对象上数据流的操作。
本质上是“分配点的敏感性”。
Object Sensitivity的一个例子
结果
C.S. (1-Object) vs C.S. (1-Call-Site)
从理论上讲，它们的精度是无与伦比的。
实际上，对于OO语言（例如Java），对象敏感通常胜过调用点敏感。
对于所有数字，越低越好（就效率或精度而言）
一般来说
•精度：object > call-site
•效率：object > call-site
•精度：object > call-site
•效率：object > call-site
Type Sensitivity*（类型敏感）
每个上下文都包含一个类型列表
在方法调用中，使用包含接收对象分配点的类型及其堆上下文作为被调用者上下文。
对对象敏感的粗略抽象
Type vs. Object Sensitivity
在相同的k限制下，类型敏感的精度不比对象敏感高。
类型敏感是对象敏感的粗略抽象。
与对象敏感相比，类型敏感通过合并上下文中相同类型的分配点来权衡精度，以提高效率。
实际上，类型敏感比对象敏感更不精确，但效率更高。
一般来说
•精度：object > Type
•效率：Type > object
•精度：object > Type
•效率：Type > object
一个例子
Call-Site vs. Object vs. Type Sensitivity
对于所有数字，越低越好（就效率或精度而言）
一般来说
•精度：object>type>call-site
•效率：type>object>call-site
•精度：object>type>call-site
•效率：type>object>call-site
0 条评论
下一页
