序言
男儿何不带吴钩，收取关山五十州。
从这篇文章开始，我会在我的博客中记录学习程序静态分析的点点滴滴。
PL？程序分析？
PL的三大模块
理论部分
- 程序是如何设计的
- 语言的类型系统
- 语言的形式语义与逻辑系统
支撑环境
- 编译器：对语言语法的解析，字节码转换等
- 运行时系统：Java，Python等，JVM虚拟机，内存分配，管理
语言应用
- 程序分析
- 程序验证
- 程序合成：例如如何自动生成一个程序
语言核心
核心无非分为三类：
命令式语言Imperative language：Java，C/C++等
把程序逻辑拆解成一条条指令，加载到内存，顺序执行下来。
函数式语言Functional language：Pascal，JS，Python
命令式与函数式相结合，把逻辑包装起来，形式化。
逻辑式语言Prolog：
声明，逻辑，与、或、非。
语言核心没有变，用语言写的程序变得复杂了。
#静态分析
定义
在程序运行前，在编译时刻就完成程序安全性，可靠性的检验。不用运行程序本身，就能检查出程序潜在的问题。
- 程序运行时会不会有隐私泄露？
- 空指针引用异常？
- cast安全吗？
- v1，v2两个变量会不会造成内存竞争？要不要加锁？
- assert运行时会不会fail掉？
- dead code？
Rice’s Theorem
程序分析不存在 exact answer
正常的递归可枚举语言，不存在某个方法，可以去判断其是否存在问题。
Sound & Complete
Sound > Truth > Complete
Sound：Overapproximate，肯定会包含Truth。
假如Truth就是代表有10个空指针异常，那么Sound可以有1k，1w个空指针异常，就是包含Truth的关系。
Complete：Underapproximate，一定在Truth里面。
上一个例子，无论Complete里面有几个空指针异常，只要存在的，就一定在Truth里面，是Truth子集的关系。
Useful static analysis
- 妥协Soundness：会产生【漏报】，False Negatives
- 妥协Completeness：会产生【误报】，False Positives
但是在绝大部分的静态分析中，绝大部分都【妥协Completeness】。
宁可误报，也不要漏报！
准则
在保证soundness的基础上，在【精度】和【速度】上作出权衡。
抽象+近似
- 抽象：判断变量的+/—/0符号。
- 近似：在抽象的基础上进行近似。
- Transfer function
- Control flows
Concrete Domain ——> Abstract Domain
不关心是具体数值，关心变量的符号位。
Transfer function：
在静态分析中，transfer fuction主要应用在于如何在程序语句的抽象值上进行运算。
根据你分析的程序的目标，和程序中每一个语句的语义，综合地设计分析方法。
Control flows：
控制流，就是程序执行的流。控制流图，程序如何跳转。
IR (Intermediate representation)
Compiler & Analysis
Compiler:
需要将人写的高级代码，【编译】成机器可以看懂的机器码。
在这个过程中，编译器做的工作不仅有【翻译】，还会有【检查】。
AST vs. IR:
3AC
3AC：三地址码。a = b + c
Control Flow Analysis
Basic Blocks
最大的、连续的、3AC指令块。
有且只有一个入口，并且是第一行指令是入口。
出口也是唯一的，是最后一个指令。
如何划分BB？
- 首先决定BB入口在哪：
- 程序中的第一行语句。
- 无条件跳转的目标语句也是入口。
- 紧接着条件/无条件跳转的语句也是个BB入口。
- 有了BB入口，接下来：
- 有了入口，那么整个BB包含入口开始的连续语句，直到下一个leader的位置。
CFG
控制流图。
控制流图的node其实就是BB代码块。
