Static Program Analysis Intruction

0x00 前言

静态分析的水太深，真的把握不住啊。

本文为我在学习《Static Program Analysis》时做的笔记，包含如下几部分内容：

1. PL and Static Analysis
2. Why We Learn Static Analysis?
3. What is Static Analysis?
4. 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）是本门课程中的主要内容。

编程语言通常分为三类：

1. 命令式编程语言（通俗理解，就是一条命令一条命令的执行下来，把语义结和逻辑拆解开来，字节码、汇编加载到内存中一条条的执行）：Java、C++、C 等
2. 函数式编程语言（将逻辑包装起来，形式化）：haskell、JavaScript 等（注：Python 为命令式和函数式相结合的编程语言。）
3. 逻辑式编程语言：SQL 等

0x02 Why We Learn Static Analysis?

静态程序分析的应用场景：

1. 程序的可靠性问题（Program Reliability）：
1. Null pointer dereference
2. memory leak
3. etc...
2. 程序的安全问题（Program Security）
1. Private information leak
2. injection attack
3. etc...
3. 编译优化（Complier Optimization）
1. Dead code elimination
2. code motion
3. etc...
4. Program Understanding
1. IDE call hierarchy
2. type indication
3. etc...

静态程序分析，故名思议就是说在静态、编译时刻完成针对所有安全性和可靠性的检查，而无需动态运行该程序。编译优化（Complier Optimization）为编译后端非常高级且复杂的部分。

静态分析的市场：

Semmle 就是被 GitHub 收购的 CodeQL，很强大，也是促使我想学习这门课程的原因之一。

顺便吐槽一句，国内某知名安全大厂的 SAST 产品竟然是拿 Fortity 套壳，有点失望。

深入学习静态程序分析的附加价值：

1. 可以更深入的理解编程语言的语法、语义（语义代表程序运行时的一种行为）
2. 自然而然的写出更可靠、更安全、更高效率的程序

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，我们将我们写的这个程序成为分析器。

1. 程序 P 是否包含任何隐私泄露的风险
2. 程序 P 是否存在空指针引用的异常
3. 所有的 cast 类型是否均正确
4. 程序 P 中两个变量 v1、v2 能否指向同一个内存地址
5. assert 声明是否会 fail
6. 是否存在死代码

不幸的是，根据大米定理，在静态程序分析领域，并不存在一个这样的方法，可以准确的判断，给出 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

1. Static Program Analysis - https://pascal-group.bitbucket.io/teaching.html