PL(Programing Language)程序语言
PL(Programing Language)大致可以分成三部分：
- 理论部分：语言设计、类型系统、形式语义和程序逻辑等。即在理论上构建出一个语言。
- 环境部分：编译、运行时系统等。即相应的支撑语言运行的一套系统。
- 应用部分：程序分析、程序验证、程序合成等。在语言层面谈到程序分析，实际上指的就是静态程序分析。
从软工的角度来看很多人做的程序分析是动态分析，但在PL领域的程序分析是静态分析。
为什么需要静态分析
静态分析也就是在程序运行之前，在编译时期完成所有的分析过程，”静态”即不用去运行程序就能进行分析。
- 检测可靠性相关的问题
例如，要避免空指针引用(null pointer dereference)，如Java运行时的NullPointerException。又如，要避免内存泄漏(memory leak)，如C中malloc的空间一直没有free掉。
- 检测安全性相关的问题
例如，要避免私有信息泄漏(private information leak)，如在安卓某个应用中输入的账号密码不应被其它应用劫持。又如，要避免注入攻击(injection attack)，如SQL注入可以恶意操作服务器数据库。
- 编译优化(compiler optimization)
编译优化是编译器后端的部分，大部分的编译优化（除了JIT那种在线的）用的都是静态分析的技术。例如，死代码消除(dead code elimination)，即将永远不可能执行到的代码删除。又如，代码移动(code motion)，如将循环内部和循环无关的重复计算提到循环的外面。
- 程序理解(program understanding)
如很多IDE中能追踪函数调用的层级关系(IDE call hierarchy)。又如类型提示(type indication)，对动态类型的语言这个尤为重要。
当下静态程序分析的市场情况
在工业界中，微软等一线国际互联网工业大厂都开始进行了SPA的研究吗，也有了诸多解决方案工具的问世。在国外有着Oracle, Google, Microsoft, IBM, Facebook等公司，而国内有着华为、阿里巴巴、腾讯、网易、字节跳动、京东、美团、航空航天研究院、国家电网研究院、中国电信、央行金融研究院等企业单位同样做出了一定的成果。目前有着不少专门做静态分析解决方案SAST、SCA的公司崛起，他们主要有龙智科技、寻臻科技、安势信息、鸿渐科技、比瓴科技等。
学术届对此类方向一直保持着高度的热情。曾经有很多图灵奖的获得者都是凭借着在程序语言的方向做出了推动计算机界的成果才获此荣誉。其实程序分析并不是一个全新的方向，早在编译的研究中就已经出现，比如《编译原理》中我们耳熟能详的词法分析、语法分析、语义分析、可达定义分析、变量活性分析等等。随着技术的发展，我们也可以在AST，或者IR中进行指针指向分析、流敏感分析、上下文敏感分析等更细致的分析。
IR中间表示
IR,中间代码(Intermediate Representation,有时也称为Intermediate Code,IC)，它是编译器中很重要的一种数据结构。编译器在做完前端工作以后，首先就生成IR,并在此基础上执行各种优化算法，最后再生成目标代码。
中间代码表示形式：
- 树和有向无环图（DAG）
高层表示，适用于程序源代码；
- 三地址码（3-address code）
低层表示，靠近目标机器；
- 控制流图（CFG）
更精细的三地址码，程序的图状表示适合做程序分析、程序优化等；
- 静态单赋值形式（SSA）
更精细的控制流图同时编码控制流信息和数据流信息；
- 连续传递风格（CPS）
更一般的SSA，可以表达跨函数、跨模块的控制跳转，而SSA一般是函数内部。
中间语言高级抽象化
在AST、三地址码、SSA（静态单赋值）形式之上，还有着更高级的表现形式。如CFG、ICFG、VFG、SVFG、PDG等等。（CFG: Control Flow Graph; ICFG: Inter- Control Flow Graph; VFG: Value Flow Graph; SVFG: Spare Value Flow Graph）
当我们有了更高级的表示之后，就可以在其抽象数据结构上总结规律、执行算法，甚至是将复杂的问题转化为图上的结点、路径规划问题等方式。
解决方案实体化
在有了前面的介绍之后，我们就可以介绍具体的应用部分了。我们的核心思想是：将复杂的判定问题转化为图上的路径布尔可满足性问题。在将IR转换成图中的结点和边后，中间的路径约束也随之构建而成。实际的应用之中，要么按需在图上添加、删除部分结点、边，要么在已经按需构建的图上选取一对或多对结点寻找路径。
第一个案例就是前者所描述的场景——指针分析：
指针分析是数据流分析的一种，主要目的是计算运行时指针可能指向的内存区域。输入为我们的高级抽象图，输出为points-to set（指针指向集合），即哪些变量指向同一个指针内存区域的集合。
图中案例为指针分析最经典的Andersen算法，它采用worklist的工作思想。在执行过程中，对于指针变量流向的位置，添加边将两点之间连接，直到遍历完全部的结点。至此，所有指向同一指针内存区域的相关变量均已连通，故将其提取出points-to set。
- 指针分析可以应用于：
建立变量之间的数据依赖关系。 - 变量别名分析：在下面代码中p = &a; q = p; *p = x; y = *q;。因为 p、q都指向同一块内存，所以 y 的值和 x 一样。
- 编译优化和bug检测：
常量传播：*p = 1; x = *q; 中，如果 p 和 q 在任意情况下都是别名（must-aliases，在每个执行路径 p 和 q 都指向同一块内存）那么 x 就是常量 1。
污点分析：*p = errorInput; x = *q; 如果 p 、q 是别名那么 x 可能受污点影响。
第二个案例是后者所描述的场景——特定异常分析：
对于特定漏洞分析我们重点强调Memory Leak、Double Free、Null Pointer Dereferences等漏洞。
主要的思路是:
1、进行指针分析和value flow分析建立sparse value flow graph.
2、基于sparse value flow graph（svfg）进行some path分析，即在value flow graph上进行source-sink分析（从 malloc 到 free 的svfg路径）。如果一个source点不能在svfg上到达sink点，那么表示该 malloc 从没有被 free，一定存在内存泄漏，报出 NeverFree 错误。
3、接下来进行all path分析，主要目的是确保在每个control-flow路径上source点都能达到sink点，如果存在一个control-flow路径source点没有到达sink点，那么报出 PartialLeak 错误。
图中（a）为程序的源程序代码，（b）为全稀疏的静态单赋值表示形式以及约束点，（c）为简化版的稀疏值流图（路径上已经构造了约束）。我们可以发现指向二级指针的声明点， 指向一级指针的声明点，指向二级指针的释放点，指向一级指针的时放点。两条路径连通，即每个指针都能够有声明和释放，即没有错误产生。对于这种判定方式，我们称之为source-sink分析。如果这两条路径有一条没有连通，即发生了Memory Leak错误；如果有其中一条路径从起始点（假设为）出发，同时走到了两个终点（），则判定为double free错误；如果程序发生改变，即为空指针变量初始化的位置，为空指针变量解引用的位置，那么如果路径可达，则判定为发生了空指针解引用的操作。
经典非商用程序分析框架（C/C++、Java生态）
对于经典的非商用程序分析框架，有很多开源工具给学术界和工业界做了不少的参考。其中JAVA生态中的经典当属SOOT，C/C++效果好的则是Yelei Sui老师团队开发的SVF。
静态程序分析趋势
当下的静态程序分析还是国外做的好一些，国内的SAST、SCA产品还有很长的路要走。
