《南大软件分析》读书笔记
2021-04-28 14:53:18 14 举报AI智能生成
《南大软件分析》思维导图大纲
作者其他创作
大纲/内容
P1
P2
Compilers and Static Analyzers
AST vs. IR
IR: Three-Address Code (3AC)
3AC in Real Static Analyzer: Soot
Static Single Assignment (SSA)
Basic Blocks (BB)
Control Flow Graphs (CFG)
P3-4
数据流分析概述
may analysis VS must analysis
数据流分析基础
Input and Output States
控制流约束的表示法
数据流分析应用
Reaching Definitions Analysis（定义可达分析）
定义
实例
算法
算法执行实例过程
Live Variables Analysis（活变量分析）
定义
实例
算法
算法执行实例过程
Available Expressions Analysis（可用表达式分析）
定义
实例
算法
算法执行实例过程
数据流分析3种应用的比较
P5-6
以另一种方式来看迭代算法
Partial Order（偏序）
Upper and Lower Bounds（上界和下界）
Lattice, Semilattice, Complete and Product Lattice
Lattice
Semilattice
Complete Lattice
Product Lattice
Data Flow Analysis Framework via Lattice
Monotonicity and Fixed Point Theorem
Monotonicity（单调性）
定义
Fixed-Point Theorem（不动点定理）
定义
两个证明
不动点的存在性
不动点是最小（最大）的
把迭代算法和不动点定理关联起来
将迭代算法和不动点定理联系起来
证明函数F是单调的
迭代算法什么时候会到达不动点
May/Must Analysis, A Lattice View
MOP and Distributivity
Meet-Over-All-Paths Solution (MOP)
Ours (Iterative Algorithm) vs. MOP
Constant Propagation
Worklist Algorithm
工作列表算法是迭代算法的一种优化
P7(Interprocedural Analysis)
Motivation
Call Graph Construction (CHA)
Call Graph（调用图）
构造CG图的4种方式，其中CHA最快，但最不精确。
Java中3种类型的方法调用
Class Hierarchy Analysis（CHA）//类层次分析
函数Resolve(𝑐𝑠) ：通过CHA解析调用点的可能目标方法
CHA针对Java中3种类型的方法调用进行解析的例子
CHA的特点
CG图的构造
通过CHA构造CG图的步骤
算法
算法对应的一个例子
Interprocedural Control-Flow Graph
CFG
ICFG
ICFG = CFGs + call & return edges
Interprocedural Data-Flow Analysis
Edge transfer（边传递）
调用边传递
返回边传递
Interprocedural Constant Propagation（过程间常量传播）
一个例子
call-to-return edge的作用
kill掉LHS变量的结果
没有kill掉LHS变量的结果（会造成结果的不精确）
过程内和过程间常量传播的比较
过程间常量传播比过程内常量传播更精确
P8(Pointer Analysis)
Motivation
CHA和Pointer Analysis的比较
Pointer Analysis能够解决CHA的不精确问题
Introduction to Pointer Analysis
指向分析的一个例子
Pointer Analysis 和 Alias Analysis（别名分析的比较）
指向分析的应用
Key Factors of Pointer Analysis
Heap Abstraction//堆抽象（How to model heap memory?）
动态执行和静态分析的区别
Allocation-Site Abstraction（分配点抽象）
Storeless（无存储）
Context Sensitivity//上下文敏感（How to model calling contexts?）
上下文敏感
区分方法的不同调用上下文，多次分析每种方法，每种情况分析一次。
上下文非敏感
合并方法的所有调用上下文，一次分析每种方法。
Flow Sensitivity//流敏感（How to model control flow?）
流敏感
遵守语句的执行顺序，在每个程序位置维护指向关系图（map of points-to relations）。
非流敏感
忽略控制流顺序，将程序视为一组无序语句，维护整个程序的一张指向关系图。
Analysis Scope//分析范围（Which parts of program should be analyzed?）
整个程序
计算程序中所有指针的指向信息，为所有可能的客户提供信息。
需求驱动
仅计算可能影响特定的需要（按需）的指针的指向信息，提供特定客户的信息。
本课程采用的指向分析
Allocation-Site Abstraction（分配点抽象）、上下文敏感/上下文非敏感、非流敏感、整个程序
Concerned Statements
Java中的指针
本地变量（Local variable）、静态域（Static field）、实例域（Instance field）、数组元素（Array element）
Pointer-Affecting Statements（指针影响语句）
New、Assign、Store、Load、Call
P9-10(Pointer Analysis Foundations)
Pointer Analysis: Rules
Pointer-Affecting Statements（指针影响的语句）
Domains and Notations（域和符号）
Rules（规则）
New
Assign
Store
Load
How to Implement Pointer Analysis
如何实现指向分析？
Pointer Flow Graph (PFG)
定义
PFG
节点
边
Pointer Analysis: Algorithms
算法
Worklist (WL)
Handling of New and Assign
Differential Propagation（差分传播）
Handling of Store and Load
算法的一个例子
Pointer Analysis with Method Calls
存在方法调用时的指向分析
Rule: Call
规则
符号的含义
Dispatch（𝑜𝑖，k）
𝑚𝑡ℎ𝑖𝑠
𝑚𝑝𝑗
𝑚𝑟𝑒𝑡
例子
Interprocedural Pointer Analysis（过程间指向分析）
算法
AddReachable(𝑚)
ProcessCall(𝑥, 𝑜𝑖)
Algorithms Output
Points-to Relations (pt)
Call Graph (CG)
算法的一个例子
P11-12(Pointer Analysis Context Sensitivity)
Introduction
Context Sensitive Pointer Analysis: Rules
Context Sensitive Pointer Analysis: Algorithms
Context Sensitivity Variants
P13(Static Analysis for Security)
Information Flow Security
Confidentiality and Integrity
Explicit Flows and Covert Channels
Taint Analysis
P14(Datalog-Based Program Analysis)
Motivation
Introduction to Datalog
Pointer Analysis via Datalog
Taint Analysis via Datalog
P15(CFL-Reachability and IFDS)
Feasible and Realizable Paths
CFL-Reachability
Overview of IFDS
Supergraph and Flow Functions
Exploded Supergraph and Tabulation Algorithm
Understanding the Distributivity of IFDS
P16(Soundiness)
Soundness and Soundiness
Hard Language Feature: Java Reflection
Hard Language Feature: Native Code
0 条评论
下一页
