快速的过了一遍课程视频，大体了解了一下，打算看第二遍，并记下笔记。🙏感谢南大两位老师

课程地址

thinking.md

01.Course Introduction

• Course Introduction
  • PL and Static Analysis
  • Why We Lean Static Analysis
  • What is Static Analysis
  • Static Analysis Features and Examples
    • soundness
    • 如何实现
    • 一个栗子
    • 精度与速度平衡
  • Teaching Plan
  • Evalution Criteria

02.Intermediate-Representation.md

• Intermediate Representation
  • 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)

03.Data-Flow-Analysis-I.md

• Data Flow Analysis I
  • Overview of Data Flow Analysis
  • Preliminaries of Data Flow Analysis
  • Reaching Definitions Analysis
    • Reaching Definitions的定义
    • 用bit vectors去表示是否可达
    • Transfer function and Control flow
    • 算法
    • 栗子
    • 为什么会最终不变

04.Data-Flow-Analysis-II.md

• Data Flow Analysis II
  • Live Variables Analysis
    • 定义
    • transfer func and control flow merge
    • 算法
    • 栗子
  • Available Expressons Analysis
    • 定义
    • transfer func and control flow merge
    • 算法
  • 三种算法对比

05.Data-Flow-Analysis-Foundations-I.md

• Data Flow Analysis - Foundations I
  • Iterative Algorithm, Another View
  • Partial Order
    • 偏序
  • Upper and Lower Bounds
    • 定义
    • poset性质
  • Lattice, Semilattce,Complete and Product Lattice
    • Lattice
    • Complete Lattice
    • Product Lattice
  • Data Flow Analysis Framework Via Lattic
  • Monotonicity and Fixed Point Theorem
    • 定义
    • 证明-Existence of fixed point
    • 证明-The fixed point is the least
    • lattice 上数学运算与data analyse

06.Data-Flow-Analysis-Foundations-II.md

• Data Flow Analysis Foundations II
  • Relate Iterative Algorithm to Fixed Point Theorem
    • 格与迭代算法对应
    • 证明迭代算法中F的monotonic
    • 什么时候到达fixed-point
  • May/Must Analysis, A Lattice View
  • Mop and Distributivity
    • mop定义
    • mop与迭代算法区别
  • Constant Propagation
    • 非distributive的问题，must analysis
    • 问题映射到lattice上
  • Worklist Algorithm

07.Interprocedural-Analysis.md

• Interprocedural Analysis
  • Motivation
    • Call Graph
  • Call Graph Construction(CHA)
    • Call Graph算法对比
    • Dispatch
      • Java中的method invoke
      • method signature
      • virtual call dispatch
    • CHA
      • 定义
      • Resolve
      • 全程序算法
  • Interprocedural Control-Flow Graph
    • 定义
  • Interprocedural Data-Flow Analysis
    • 过程间分析组成
    • Interprocedural Constant Propagation
      • 组成
      • 栗子

08.Pointer-Analysis.md

• Pointer Analysis
  • Motivation
  • Introduction to Pointer Analysis
    • Pointer Analysis 简述
    • /Pointer Analysis 和 Alias Analysis 的区别
    • 指针分析在静态分析地位
  • Key Factors of Pointer Analysis
    • Pointer Analysis的四个取舍要素
    • Heap Abstraction
      • 为什么堆抽象
      • Allocation-Site Abstraction
    • Context Sensitivity
    • Flow Sensitivity
    • Analysis Scope
    • 课程涉及的特性
  • Concerned Statements
    • Pointer Analysis面向的指针类型
    • Pointer Analysis面向的语句

09.Pointer-Analysis-Foundations-I.md

• Pointer Analysis - Foundations I
  • Pointer Analysis:Rules
    • 影响指针的statements
    • Domains and Notations
    • Rule
  • How to implement Pointer Analysis
    • PFG
    • 实现Pointer Analysis
  • Pointer Analysis:Algorithms

10.Pointer-Analysis-Foundations-II.md

• Pointer Analysis with Method Calls
  • call rule
  • 不加x到this
  • Interprocedure Pointer Anaylsis Algorithm

11.Pointer-Analysis-Context-Sensitivity-I.md

• Pointer Analysis Context Sensitivity
  • Introduction
    • Why Context Sensitivity
    • Cloning-Based Context Sensitivity
    • Why Context-Sensitive Heap
    • Context-Sensitive Heap
  • Context Sensitive Pointer Analysis:Rules
    • Domains and Notations
  • Rules

12.Pointer Analysis Context Sensitivity II

• Context Sensitive Pointer Analysis : Algorithms
  • 定义
  • algorithms
• Context Sensitivity Variants
  • Call-Site Sensitivity
    • 栗子
  • Object Sensitivity
    • 栗子
  • Type Sensitivity
  • 对比

13.Static Analysis for Security

• Information Flow Security
  • Access Control vs. Information Flow Security
  • Security Levels
  • Information Flow Policy
• Confidentiality and Integrity
  • Confidentiality vs. Integrity
  • Integrity, Broad Definition
• Explicit Flows and Covert Channels
  • Implicit Flow
  • Covert Channels
• Taint Analysis
  • 定义
  • 解决confidentiality、Integrity
  • Taint 与Pointer Analysis结合
  • Domains and Notations
  • Taint Analysis Input & Output
  • Taint analysis:rule
• 其他

14.Datalog-Based-Program-Analysis.md

• Motivation
  • 命令式 vs 声明示
• Introduction to Datalog
  • Datalog 的 data
    • predicates
    • 通过Atoms表示predicates
  • Datalog 的 rule
  • EDB and IDB
  • Logical
    • Logical Or
    • Negation
  • Recursion
  • Rule safety
  • Excution of Datalog Programs
• Pointer Analysis via Datalog
  • EDB/IDB Model
  • Rule TO Datalog
  • Example without method call
• Taint Analysis via Datalog
• Datalog Pros vs Cons

15.IFDS.md

• Feasible and Realizable Paths
• CFL-Reachability
• Overview of IFDS
  • MOP & MRP
  • overview
• Supergraph and Flow Funcations
  • supergraph
  • flow functions
• Exploded Supergraph and Tabulation Algorithm
  • exploded supegraph
  • 0 -> 0
  • exploded supegraph example
  • tabulation algorithm
• Understanding the Distributivity of IFDS
  • Can we do constant propagation using IFDS
  • Can we do pointer analysis useing IFDS
• 待解决问题

16.Soundiness.md

• Soundness and Soundiness
  • Soundness
  • 常见Hardness Feature
  • 提出Soundiness
  • Soundness,soundiness,Unsoundness
• Hard Language Feature : Java Reflection
  • 反射难论文
  • 解决反射
    • String Constant analysis
    • 通过调用处的信息查找
    • Assisted By Dynamic Analysis
• Hard Language Feature : Native Code
  • Native code 原理
  • 解决方案