《南大软件分析》读书笔记
2021-04-28 14:53:18 14 举报AI智能生成
《南大软件分析》思维导图大纲
作者其他创作
大纲/内容
P1-16
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 Lattice
Product Lattice
Data Flow Analysis Framework via Lattice
Monotonicity and Fixed Point Theorem
Monotonicity（单调性）
Fixed-Point Theorem（不动点定理）
两个证明
不动点的存在性
不动点是最小（最大）的
把迭代算法和不动点定理关联起来
将迭代算法和不动点定理联系起来
证明函数F是单调的
迭代算法什么时候会到达不动点
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)
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(𝑚)
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)
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 条评论
回复 删除
下一页
