Static Program Analysis Intruction
0x00 前言
静态分析的水太深，真的把握不住啊。
本文为我在学习《Static Program Analysis》时做的笔记，包含如下几部分内容：
-
PL and Static Analysis
-
Why We Learn Static Analysis?
-
What is Static Analysis?
-
Static Analysis Features and Examples
0x01 PL and Static Analysis
PL（Programming Languages） 至今有 60 年左右的研究历史。
整体上分为如下 3 个部分，理论部分、环境部分以及应用部分：
理论部分包含如何设计一门编程语言，类型系统是什么，它的形式语义是什么，程序逻辑是什么，等等。
语言设计完成之后，需要将其编译运行起来，于是便有了支撑语言运行的一套系统，我们通常将其成为 Enviroment。这套环境系统包含解析语法，将软件工程师编写的语言翻译为字节码，这些均为编译部分做的事情。编译完成之后，对于一些高级编程语言，比如说 Python、Java 需要一个运行时环境（Runtime system），这部分又会涉及内存分配管理等内容。
在我们完成了编程语言的设计、实现及运行之后，由于语言本身是一个非常复杂的系统，为了保证系统本身的可靠性、安全性、运行效率，这便涉及到了编程语言的应用（Application）部分。应用（Application）部分包含了程序分析（Program analysis）、程序验证（Program verification）、程序合成（Program synthesis）等等，程序合成（Program synthesis）可以简单理解为如何生成一个程序，程序验证（Program verification）的很多知识在程序分析（Program analysis）部分都会讲到。
程序分析（Program analysis）是本门课程中的主要内容。
编程语言通常分为三类：
-
命令式编程语言（通俗理解，就是一条命令一条命令的执行下来，把语义结和逻辑拆解开来，字节码、汇编加载到内存中一条条的执行）：Java、C++、C 等
-
函数式编程语言（将逻辑包装起来，形式化）：haskell、JavaScript 等（注：Python 为命令式和函数式相结合的编程语言。）
-
逻辑式编程语言：SQL 等
0x02 Why We Learn Static Analysis?
静态程序分析的应用场景：
-
程序的可靠性问题（Program Reliability）：
-
Null pointer dereference
-
memory leak
-
etc...
-
程序的安全问题（Program Security）
-
Private information leak
-
injection attack
-
etc...
-
编译优化（Complier Optimization）
-
Dead code elimination
-
code motion
-
etc...
-
Program Understanding
-
IDE call hierarchy
-
type indication
-
etc...
静态程序分析，故名思议就是说在静态、编译时刻完成针对所有安全性和可靠性的检查，而无需动态运行该程序。编译优化（Complier Optimization）为编译后端非常高级且复杂的部分。
静态分析的市场：
Semmle 就是被 GitHub 收购的 CodeQL，很强大，也是促使我想学习这门课程的原因之一。
顺便吐槽一句，国内某知名安全大厂的 SAST 产品竟然是拿 Fortity 套壳，有点失望。
深入学习静态程序分析的附加价值：
-
可以更深入的理解编程语言的语法、语义（语义代表程序运行时的一种行为）
-
自然而然的写出更可靠、更安全、更高效率的程序
0x03 What is Static Analysis?
Static analysis analyzes a program P to reason about its behavious and determines whether it satisfies some properties before running P.
在运行一个程序 P 之前，了解程序相关的全部行为，并且可以知道关于这个程序行为的相关性质能否得以满足。简单理解，就是我们写一个程序，分析程序 P，我们将我们写的这个程序成为分析器。
-
程序 P 是否包含任何隐私泄露的风险
-
程序 P 是否存在空指针引用的异常
-
所有的 cast 类型是否均正确
-
程序 P 中两个变量 v1、v2 能否指向同一个内存地址
-
assert 声明是否会 fail
-
是否存在死代码
不幸的是，根据大米定理，在静态程序分析领域，并不存在一个这样的方法，可以准确的判断，给出 Yes 或 No 的答案。
递归可枚举的语言（r.e. language），就是图灵机可识别的语言，简单理解，我们能想到的现代编程语言均可归类为递归可枚举的语言（r.e. language）。
通过递归可枚举的语言（r.e. language）编写的程序其 non-trivial 属性的行为均是不可判断的。
通俗理解，跟程序运行时行为相关的属性，我们就可以称之为 non-trivial 属性。
举例来说，如下几条均为 non-trivial 属性：
一个完美的静态分析程序（可以给出明确的结论）是不存在的：
如果一个完美的静态分析程序，可以给出明确的结论（是或者不是），我们就可以称这个静态分析是既 Sound 又 Complete 的。
不存在一个既 Sound 又 Complete 的方法，可以准确的给出结论。
Sound 和 Complete 可以简单理解为误报和漏报。这一点还是蛮有意思的，有过 SAST 运营经验的师傅可能会对这个有比较深的体会，我们当然可以把所有的可疑漏洞都抛出来，但是随之而来的问题就是大量的误报率会让研发团队对这个 SAST 产品失望甚至不再使用该类产品，这当然不是我们想看到的结果，因此在使用和推广 SAST 产品时我们往往需要在漏报和误报之间找到一个平衡点，在牺牲一点可以预期的漏报之下，减少误报率。
大部分静态程序分析的场景下，是可以允许存在误报，避免漏报。（这就是目前 SAST 产品的现状，先把所有潜在的漏洞都抛出来，然后再人工分析有效漏洞。当然实际的业务场景要比这个复杂的多，也需要有对应的应对方案，这些我们通常称为甲方安全经验。）
在编译优化和程序验证领域，Soundness 是必须的。
一个程序验证的例子来说明为什么 Soundness 是必须的，如果不是 Soundness 的，则会得出错误的解决，这是我们不能接受的。
一句话概括静态程序分析，只要是 Sound 的，那结论就是正确的，在确保 Soundness 的情况下，在分析的精度和速度之间保持一个有效平衡。
0x04 Static Analysis Features and Examples
一个简单的例子，通过利用静态分析技术，判断一个程序中所有变量的符号。（其应用场景是，可以判断是否有除零错误，也可用用来判断数组索引是否为负值。）
第一步需要先抽象（Abstraction），抽象之后状态空间变小，分析速度加快。我们理想的结果通常是 +、-、0，但是会遇到 v = e?1:-1 等非预期的场景，为了保证 Sound，我们需要将其标记为 unknow。对于 v = w/0 这种场景，由于除零会导致程序错误，因此我们将其标记为 undefined。
接下来需要实现 Over-approximation，Transfer Functions，根据每一个不同的程序语句、以及分析目标定义转换规则。
此外，我们还需要继续做 Control Flows 的分析，在实际的应用程序中，由于程序的所有可能路径过于复杂，我们通常没有办法遍历所有的场景，通常采用 flow merging 作为 Control Flows 的一种抽象方式（默认采取，近似的一种方式）。
0x05 后记
下一节，我们再来聊一聊 IR（Intermediate Represenotation），相比 AST，采用 IR 有哪些好处，AST 又有哪些好处。
0x06 References
- Static Program Analysis - https://pascal-group.bitbucket.io/teaching.html
