编译拾遗（二）：揭秘污点追踪的困扰与对策

注意：污点分析是只有“安全领域”的概念，实际在编译领域并没有一个叫污点分析的概念。与之对应的过程应该叫“数据流分析”或者“变量支配分析”。

基本概念

我们使用一段伪代码来描述污点追踪的问题和挑战：

s = file.ReadFile("test.txt")~w = i => {    os.System(f"bash ${i}")}if e {    w(s)}

这段代码非常简单，那么我们总结一下这个过程：

要对这一段代码进行分析，需要思考如下几个问题：

在本篇文章中，我们尝试会对上面几个问题都有一个明确的解答，大家可以认真阅读，最后思考一下看看和自己想象的静态行为分析到底有没有差别。

从污点分析的角度看，这里存在两个重要概念：源(Source)和汇(Sink)。源是指数据可进入的地方，这里，源是 "ReadFile" 函数，用于读取外部用户可能控制的数据。汇，是指数据可以影响的地方，在这段代码中是 "System" 函数，它执行 bash 命令。

我们可以看到源（Source）是 ReadFile("test.txt")，这个读取的文件内容被赋值给了 s，然后 s 被传递给函数 w，最后作为命令参数在 System 这个汇（Sink）里执行。所以从源到汇形成了一个可能的污点传播路径。

污点追踪的“最大缺陷”

当我们明白了基本概念之后，本节内容将指出“污点追踪”这种思考逻辑的一个缺陷：思维方向固定是从 ReadFile()，但是我们有时候不能去观察所有的文件 IO 部分。如果读取了一个文件，并在内存中处理的链路非常长，那么分析过程将会无比痛苦。

很多时候，作为一个“人”，我们的思维实际上并不是“污点追踪”，而是“逆向污点追踪”，人去搜索源码，搜索到所有执行命令的地方，然后观察执行命令的地方在哪儿被使用了，一层一层向上追踪，观察输入的部分能不能控制执行命令。我们惊奇的发现，大多数人居然更愿意接受“逆向污点追踪”思考方式，毕竟面对动辄十几万行的源码，谁能从头说得清参数消亡在哪里了呢？

从安全代码审计引擎来说，“逆向污点追踪”一直是一个大家不愿意聊的话题，因为相对于正向思考的逻辑，逆向追踪的技术对 AST 分析太不友好了。

如果代码审计系统的研发水平卡在 AST 的层面的话，注定了“逆向污点追踪”一定是一个非常痛苦的过程。但是既然有这篇文章，我们肯定还是会提出相应的对策和正确的解答。

编译视角下的正逆向污点追踪

现在，我们忘掉我们是一个安全工程师的大背景，污点追踪这个话题，本质上是数据流追踪。熟悉编译拾遗（一）：代码静态行为分析内容的同学，可以很容易理解到“UD/DU链”这个层面，我们可以使用UD和DU链分析技术去追踪数据流。

1. Use-Def链分析一般描述的是，从使用到定义的分析技术，这是一种“支配方向的向上分析”的技术。

2. Def-Use链分析一般描述的是，从定义到使用到分析技术，一个变量在哪儿产生，最后消亡在哪里了，对应的就是“向下分析技术”。

我们解释到这里，我想读者已经明白为什么我们在前篇花了大量篇幅去解释基于Use-Def链和Def-Use链的静态分析技术和基本方法了。

向上分析经典案例

我们可以构造一个非常经典的案例，来展示“向上分析”和“过程间分析”的惊人效果。针对如下代码，分析 f 的值应该取决于谁？或者说，f被谁支配？

a = 1b = (c, d, e) => {    a = c + d    return d, c}f = b(2,3,4); dump(f)

这段代码非常容易理解，我们通过人脑简单观察发现，f的值应该是[3,2]。代码段中出现了1,2,3,4四个值，我们的分析目标是应该是，f，那么，f 和 1,4是无关的，我们在程序分析结果中不应该包含1或4。

我们使用 Yaklang SSA API 进行分析，通过UD关系，得到一个图：

strict digraph {  rankdir = "BT";  n0 [label="t9: f=main$1(t6,t7,t8)"]  n1 [label="main$1"]  n2 [label="t7: 3"]  n3 [label="t6: 2"]  n5 [label="c"]  n6 [label="d"]  n0 -> n3 [label=""]  n5 -> n3 [label=""]  n1 -> n3 [label=""]  n1 -> n5 [label=""]  n0 -> n1 [label=""]  n1 -> n6 [label=""]  n0 -> n2 [label=""]  n6 -> n2 [label=""]  n1 -> n2 [label=""]}

上图渲染之后为：

我们发现，如果要得出正确的结论，不去进行“过程间分析”是不可能的。如果我们不进入b函数，那么我们就会认为，2,3,4都是b的参数，都会支配f。这显然是不可以接受的。那么我们如何解决这个问题？

我们需要跨越b函数内部，并且还是从“返回值进入”，并且从“形式参数”穿越出来，才能确定结果到底是2,3还是2,3,4。那么我们具体的分析过程是什么，因为大家对 SSA IR 的熟悉程度有限，我们以 AST 为视角介绍这个过程：

如果你的目标是 AST 的话，首先，你需要知道 b 对应的 AST 的结构是什么，找到他的 RETURN 语句，RETURN 对应的变量分别为 b, c，我们分别分析 b和c的用法，发现，a = c + b和 f几乎没有啥关联，跳过，c,d最终是通过形参传入的，那么就应该去找 b 对应的 (2,3,4) 中 c,d 的位置为2,3了，分析到常量了（Terminal Node）意味着已经没有再向寻找支配的必要了。

一般来说跨过程的 AST 需要能识别函数在 AST 中是在哪里定义的，AST 中的函数本身也十分复杂，比如说 lambda / anonymous 函数，标准函数，闭包函数，甚至每一个语言的 AST 对函数的定义都不一样，如果基于 AST 去分析过程间数据流，就需要多语言，多过程均支持。

听到这个过程，可能你已经不是特别想去操作 AST 了，摸清楚一个语言的 AST 的分析过程都十分痛苦，更不用说实现一个通用编译器过程，并在过程中追踪数据流了。

难题对策：过程间分析

过程间分析经过我们最近的探索，实际上它并不适合 AST 视角去做，具体的原因我们在上节末尾有提到。实际我们更适合分析“指令集”的“跨过程”。

IR 如果不熟悉的话，我们可以以汇编举例子：函数参数压栈跳转实际上对应需要进行两个分析操作：

1. 压栈的指令需要记下来，因为他们会弹出之后作为参数使用。

2. 最后计算完成，执行完指令之后，返回值再压栈，跳回原位置，处理栈中返回值。

最重要的是，“指令”级别的过程间分析基本只有一种形式，他的形参传递方式非常单一；同样的“返回值”的传递方式也十分单一。

我们使用“类汇编”的指令函数执行过程描述过程间分析，方便用户可以直观理解“指令函数间”和“AST函数间”分析的两个区别。当然我们知道这两个有区别，但是不一定必须使用汇编级过程间分析技术，因为这显然也并不是一个好分析方向，因为寄存器对数据流分析的干扰实在有点大。

如果我们可以有一种产物，可以同时兼具 AST 的“易理解”的优势，又同时具备“指令”的线性逻辑和过程间形式简单，那就可以提出通用解决方案来解决“过程间分析”的老大难题。当然，这个产物就是 SSA IR，他可以既保持中间产物的单一流向（不必受重复值干扰），同时也能把上层各式各样的 AST 抽象成同一种过程间转换逻辑。

重新审视过程间分析案例

a = 1b = (c, d, e) => {    a = c + d    return d, c}f = b(2,3,4)

经过我们上面的提示，对 IR 进行过程间分析实际上是正途，那么 IR 具体长什么样子呢？

main type: ( ) -> nullentry-0: (true)        <any> t10 = undefined-dump        <[]any> t9: f = call <(any,any,any ) -> []any> main$1<b> (<number> 2, <number> 3, <number> 4) []        ......        ......        <any> t11: _ = call <any> t10: dump (<[]any> t9(f)) []extern type:extern Value:main$1 <any> c, <any> d, <any> eparent: mainsideEffects: atype: (any,any,any ) -> []anyentry-0: (true)        <any> t4 = <any> c add <any> d        ret <any> d, <any> cextern type:extern Value:Values: 1        0:  Call: main$1(2,3,4)

在上述 Yaklang SSA HIR 指令集中，我们删除了一些干扰项，可以做如下解释，main$1指的是b函数，真正主程序入口只有三个相关指令：

1.声明一个 undefined dump <any>: t10 = undefined-dump

2.函数调用：f = call(2,3,4)编译为：t9(f) = call main$1(b) (2,3,4)

3.函数调用：dump

实际上，我们只从第二个指令分析，进入main$1后直接跟随d,c即可找到参数。我们只分析这个指令，完全不关心这个顶层语言是谁，因为在前置的编译过程中，我们已经实现了 AST 到 HIR 的编译。

并且我们这么去做过程间分析，只需要处理一种过程跳转，并且指令也相对不受寄存器干扰，非常简单易懂并且振奋人心。

过程间分析的工程化技巧

上述的过程实际不太依靠“人脑”，是完全可以编程实现这个分析过程的，因此我们可以编写一个可以进入 CI 的测试案例，在过程间分析技术迭代过程中，这个测试案例能运行通过，即可以认为我们这个过程间分析的基本技术是具备的，并且能得到一个比较好的效果：

func TestFunctionTrace_FormalParametersCheck_2(t *testing.T) {    prog, err := Parse(`a = 1b = (c, d, e) => {    a = c + d    return d, c}f = b(2,3,4);dump(f)`)    if err != nil {       t.Fatal(err)    }    prog.Show()    check2 := false    check3 := false    noCheck4 := true    prog.Ref("f").Show().ForEach(func(value *Value) {       value.GetTopDefs().ForEach(func(value *Value) {          d := value.Dot()          _ = d          value.ShowDot()          if value.IsConstInst() {             if value.GetConstValue() == 2 {                check2 = true             }             if value.GetConstValue() == 3 {                check3 = true             }             if value.GetConstValue() == 4 {                noCheck4 = false             }          }       })    })    if !noCheck4 {       t.Fatal("literal 4 should not be traced")    }    if !check2 {       t.Fatal("the literal 2 trace failed")    }    if !check3 {       t.Fatal("the literal 3 trace failed")    }}

这个案例中，我们会对 f进行顶级定义的追踪，如果追踪过程中，发现缺少 2,3字面量，说明基本分析流程失效，如果发现分析结果包含4说明过程间分析失效。

我们可以用同样的技术，构建很多的代码段（代码案例）：MVP，然后这些 MVP 必须明确审计出正确的结果，以证明我们的分析技术实际上都生效了，并且可以追踪到特殊的情况。

当然，因为篇幅问题，我们省略掉了一些具体代码如何保持上下文传递的技术方案，你可以随时查看我们的开源代码获得这方面的信息。

结语

文章描述到这里，我想你对污点追踪应该有了非常清醒的认知，原本各种模糊的含糊其辞，充满公式的污点追踪过程应该可以变成了“代码”的过程。并且实际上，你应该抛弃掉“污点追踪”带给你的误导，直接看到污点追踪技术的分析本质。

END

长按识别添加工作人员

开启Yakit进阶之旅

原文始发于微信公众号（Yak Project）：编译拾遗（二）：揭秘污点追踪的困扰与对策