编译拾遗（一）：代码静态行为分析

重新审视“编译”技术

编译技术实际上指的是语言转换的技术，从“高级”到“相对低级”的技术。从 Yaklang 编译到 YakVM 的 Opcode 本质上其实就算是一个经典“编译”过程。虽然这个过程相对完整，也取得了非常好的效果，但是实际上在编译技术的技术高塔中，并不算是非常艰深的过程，仅能算是“惊鸿一瞥”。

在Yak Project项目进行时，代码进行SSA化和对高级语言探索拾遗过程中，我们逐渐对“编译技术”衍生的其他子领域有了一些工程化和理论指导的新理解：合适的SSA化的HIR基础设施，可以让代码静态行为变得“具体”，上下文敏感，路径敏感或者说“污点分析”得到了降维打击式的新诠释。

基于Use-Def链的

交叉递归行为分析的探讨

我们用行为分析的思路来解释一下如下的代码，**注意：下面的代码是“完整的”，是完全可以分析的**，至少我们作为一个人去理解这段代码的时候，可以看到很多信息：

var a,cif f() {    c += a} else {    c += 1}sink(c)

a和c变量明显有关联，最后c变量被sink使用了。我们观察上面代码的时候，发现：a和c和1常量最终都消亡在了sink(c)这个位置。“人”在读出上述信息的时候，下意识会追踪Use-Def链。

我们相信，你可能并不懂Use-Def链究竟是什么，但是看到这个名字就应该能猜到它描述的是任意一个“量”的生命周期过程。在很多论文中，我们会看到Use-Def链条向上追踪，Def-Use链向下追踪，但是你并不能看到它结合具体案例或者模拟栈结构描述的分析结果，那他究竟的形态是啥样的呢？我们最近做的一些工作，可以给出一个明确的答案，或者非常具体和细节的观点：

Use-Def链一般描述的是单个变量的产生消亡，但是“静态行为分析”表面听起来是分析一个主体，真的就只分析一个“符号”吗？SSA在进行转换的时候，一个词法变量（Lexical Variable）在一个时刻的SSA变量名可能完全是另一个东西，那么在SSA守则下，一个“变量”分成了诸多的“版本（Versioned）”，Use-Def链（对多版本变量）这个时候已经变成了多条。

那么我们实际关心的a变量的（多版本）产生和消亡或者c变量（多版本）的产生和消亡，会转换成各种版本的SSA“单赋值符号”的生命周期。又因为单赋值符号结构出奇的简单，我们就可以把复杂的变量生命周期，拆解成很多条简单的单赋值符号的生命周期。

如果我们要对词法变量进行分析和追踪，在SSA的理念下，我们应该对词法变量的多版本单赋值符号的产生和消亡同时（交叉、综合上下文）递归进行分析。

更进一步，我们得出了一个结论：“词法变量追踪本质上是指多个静态单赋值变量Use-Def链的追踪”。

初级阶段：Use-Def链构建有向图

如果经过我们上述的小科普，你能理解到Use-Def链在分析过程中重要性，那么恭喜至少有了代码静态分析的基本思路：“程序/代码可以抽象成一个各种Use-Def关系和Def-Use关系构建的有向图结构（有向但是不一定无环，这个很重要，一定要记住）”。但是我们还需要补充一点：**Use-Def链构建的 DAG 并不是 CFG！！！**，他只表示数据依赖关系。我们可以管词法变量的生命产生和消亡过程生成的有向图，叫“词法变量支配图”

那么，有一些基础的同学就会马上反应到：我们可以用“图算法”直接解决词法变量的追踪和分析问题吗？答案当然是**可以的，但是也不完全可以**。但是你要相信我，理解到这一阶段，你对代码行为分析一定有了很强的信心！接下来我来简单解释一下为什么会出现这个中性结论：

你确实可以使用图算法直接计算，一个节点到另一个节点究竟是不是可达？并且歧义很少。但是这非常不精确，不精确的来源我可以明确指出：

1、因为Phi问题的存在，一些分支会被污染，如果不加以控制，复杂词法变量几乎会染指所有链，甚至会遇到“环”问题；

2、因为函数调用问题，你不确定返回值究竟和参数有没有关系，也不确定你的HIR指令到底能不能分辨哪些是有用的参数（形参和实参转换）；

3、高级语言中经常存在闭包函数的问题（Closure Function），将会造成“隐式修改”父词法域（Parent Lexical Scope）中符号含义；

4、Use-Def 链和 Def-Use 链在“过程间”（函数间跳转）其实隐藏了巨量的信息，如何让分析过程跨越函数？需要增加复杂的上下文控制，对函数（过程）内的 Phi 节点还有递归情况都需要做额外处理。

5、大量的高级语言都有“复合类型”或“OOP”的概念，类OOP的成员追踪和成员变量修改需要明确区分追踪的对象，“静态”和“动态”成员的处理方案在 SSA HIR 中是不一样的，需要额外做一些“重命名消解”工作。

6、...

这些都是目前一些代码行为分析中，需要逐个思考进化的技术点，这些点共同造成了一个：“词法变量支配图”并不能完全解决全局问题，只能解决“小局部”问题。

但是大多数论文只讨论“支配关系”或“CFG”对“三地址IR”的分析，并没有成体系完整串联这些高级领域，其实挺令人惋惜的。所以大家在阅读论文的时候，一定要有所甄别论文中的“隐藏前提”。上述提到的内容，但凡有一个不解决，都无法拿出一个“工业级”的分析方案。

如何解决

这些复杂词法变量追踪问题？

虽然我们基本已经都有了明确的解决办法，但是还是要卖个关子，同时上述内容信息量已经挺多了，对领域了解并不深入的同学并不能在几分钟内读懂，并且这篇文章主要是面向对“静态行为分析”感兴趣的研究人员的。这些明确的解决办法，几乎每一个问题解决的方案都足够写一篇案例扎实的实现记录了。

如果有人愿意了解，我们会在后面的文章继续为大家更深入讲解“支配图”为啥不是通解。如果并没有人对这些内容感兴趣，作为指导性科普文来说，这个深度已经足够了。

上面的问题每一个都是代码解析的重要拼图碎片，为了让大家对静态行为分析有一个直观感受，我们以一个简单的案例为大家介绍我们实现的一些行为分析技术：

var a = 1;b = i => i+1c = b(a)e = c+1sink = i => {    println(i)}sink(e)

我们在上述案例中，既有箭头函数，也有最后 sink 的点，上述代码显然也不完整，但是丝毫不影响我们对变量成员的分析。如果我们使用“Def-Use链”进行分析，希望得到一个问题的答案：a 变量最后在哪里被使用了呢？

人阅读代码的话，很容易知道a的最后被使用应该是在println(i)换句话说就是，a变量会影响println执行。

首先我们需要把上述代码编译成 SSA HIR（Yaklang SSA HIR）:

main type: ( ) -> nullentry-0: (true)        <any> t1 = call <(any ) -> any> main$1 (<number> 1) []        <number> t3 = <any> t1 add <number> 1        <null> t4 = call <(any ) -> null> main$1 (<number> t3) []extern type:extern Value:main$1 <any> iparent: maintype: (any ) -> anyentry-0: (true)        <number> t7 = <any> i add <number> 1        ret <number> t7extern type:extern Value:main$1 <any> iparent: maintype: (any ) -> nullentry-0: (true)        <any> t10 = undefined-println        <any> t11 = call <any> t10 (<any> i) []

因为静态单赋值的IR实现，只有在 For 自旋 Phi 的时候才会出现环，其他大部分都是单向流动的数据流和依赖关系，虽然看起来 HIR 有点怪怪的，但是我们大致有一些印象：

1、t1 - t11都是 IR 指令对应的值

2、这一小段代码包含了 3 个执行过程，我们的分析在这三个过程都需要“穿透”

3、大致可以直接按指令从上到下直接分析，因为静态单赋值，流动方向大致都是“单向的”

有这种印象就足够了，我们使用 Yaklang 的 SSA API 可以写下面代码支持分析过程

prog.Ref("a").ForEach(func(value *Value) {    log.Infof("%v: %s", refName, value.String())    value.GetBottomUses().ForEach(func(value *Value) {       log.Infof("%v Bottom Uses: %s", refName, value.String())       if strings.Contains(value.String(), "println(") {          foundDeepSink = true       }    })})

上述代码意思是：

1、找到 Ref(a)对应的值

2、使用这个值的“最底级使用”的位置

执行效果为：

[INFO] 2024-01-09 23:39:56 [exclusive_bottom_callstack_test:33] a: 1[INFO] 2024-01-09 23:39:56 [exclusive_bottom_callstack_test:35] a Bottom Uses: println(i)

我们发现，直接通过 a关联到了println(i)，我们找到了a最深的使用位置，直接找到了sink的内部的println函数。这个过程确实比人快。

“最底级使用”刚刚被提及了，这是个什么 API 呢？

实际上在 Yak SSA HIR 的 API 中，有两个 Use-Def 和 Def-Use 链的核心操作接口，分别是：

1、“最顶级声明”：一个符号跨函数过程的被支配的最顶级节点

2、“最底级使用”：一个符号跨函数过程的被使用的最底级节点

最复杂的定语其实是“跨函数过程”：Yaklang SSA HIR 中，我们通过上下文敏感的递归分析，可以穿越函数进入函数内的执行过程，实现形参到实参的转换，并且还能跳出，实现返回值到上一个执行过程（栈）分析。如何证明我们做了这个分析呢？除了最终结果之外，我们还可以通过 value.ShowBacktrack()去回溯上个函数执行过程：

===================== Backtrack from [t11]`println(i)` =====================: ->main$1  ->i    ->println(i)

有兴趣的同学，可以参考common/yak/ssaapi/analyze_context.go 和 exclusive_*.go中的技术实现来直接观察 SSA HIR 是如何递归交叉分析的，本文就不做过多的赘述了。

安全代码审计的父学科：

静态行为分析

很多安全审计人员会被思维的高山阻碍：“代码的安全审计是一门深奥的学问”。实际上不熟悉编译技术的同学，很容易因为不熟悉这个学科导致思维受限：编译技术对代码静态行为分析的支持已经达到了相当高的高度，静态的流追踪，模拟调用栈的上下文追踪这些都是在基础设施具备之后，几乎可以说“唾手可得”的技术。

实际上我们追求的“审计”，本质上只是代码的“静态行为”的基础的用法而已。大家觉得IDE用来审计代码非常好用，其实并不是因为他专门为安全审计设计的，因为静态行为分析是IDE对代码把控的基本功；反观号称安全代码审计的工具和产品多数很难具备完整的编译器级的“静态行为分析”技术基础设施。以至于出现“代码环境必须完整”的“潜在要求”（Are You Kidding ME？）

"劝退指南"

静态行为分析其实并不是前期技能。类比游戏设计的技能机制来说，静态行为分析属于中后期的技能，是需要点量大量的基础学科和编译基础前置技能才可以点出来：

例如你没有办法理解词法究竟是怎么完整切词的，甚至连代码解析都无法继续下去；

例如：如果你无法理解语法解析是如何解析出“幂等”的AST（抽象语法树），那么你也只能用别人“年久失修”的AST了，那么数据断流或者无法找到“引用”都是家常便饭，甚至更别提HIR或者LIR构建了；

例如，你没有办法理解“闭包”的准确含义以及对程序本身执行的各种负面影响，那你在处理“闭包行为”的时候将会遇到前所未有的障碍；

例如，你遇到了 yield from 的问题，没有办法把 yield 抽象成更初级的可被解决的形态，那对高级语法语言的分析可以说是如鲠在喉了；

如果你不理解我上面几个问题来源，那么你需要去学习一下编译技术的大学基本课程，并且找到大量的高级语言编译过程的案例来理解它们。当然，这个本身词法语法的学科已经属实“艰深”，LL(*)算法，以及改良SLL；甚至还有困扰了我有一段时间的语法歧义和EcmaScript ASI问题。

未来

我们讨厌故作高深，我们讨厌“机密”，我们希望像普罗米修斯一样，去先进的编译技术中拾遗，去盗取火种，去开源，去传播。我们是一个很讲“工程”的团队，落地开源和产品化是我们的核心驱动模式。

Happy Coding！

JOIN US 

当然，如果你有兴趣来我们这里实习，做一些“编译技术”的工作，可以简历交给我们。

如果你有兴趣参与我们“另类”的编译过程，也可以投简历给我们。

简历可邮箱投递至[email protected]

END

  YAK官方资源 

Yak 语言官方教程：
https://yaklang.com/docs/intro/
Yakit 视频教程：
https://space.bilibili.com/437503777
Github下载地址：
https://github.com/yaklang/yakit
Yakit官网下载地址：
https://yaklang.com/
Yakit安装文档：
https://yaklang.com/products/download_and_install
Yakit使用文档：
https://yaklang.com/products/intro/
常见问题速查：
https://yaklang.com/products/FAQ

长按识别添加工作人员

开启Yakit进阶之旅

原文始发于微信公众号（Yak Project）：编译拾遗（一）：代码静态行为分析