🪴 晓灰

程序静态分析

Jan 05, 202513 min read

基于AST的前端组件库代码漏洞诊断实现研究

1. 目标

分析引擎将用户输入的源代码转换为编译器中间表示(IR)；基于中间表示进行流敏感分析，过程间分析，上下文敏感分析和对象敏感分析；在各种分析的基础上结合符号执行和形式化验证等手段，检测用户输入程序是否存在各类缺陷或者安全漏洞，是否存在违反各类源代码安全编码规范或用户自定义规则的代码。最好以流图（Flow Graph）的方式，展示问题是如何从源头引入，一步步推进，并最终会在什么位置触发。

2. 概念

2.1. 编译原理过程

parser,语义分析，代码优化，类型推导，静态检查，机器代码生成

  1. A programming language consists of a grammmer/syntax plus an execution model. The execution model specifies the behavior of elements of the language. By applying it, one can derive the behavior of a program that was written in terms of that programming language.

3. 具体技术

3.1. AST

抽象语法树是程序源代码结构的树状表示。程序源代码经过词法分析器（Lexer）得到各种不同种类的单词（Token），再由语法分析器（Parser1）分析和语法检查后得到抽象语法树(AST)。 抽象语法树的根节点表示整个程序，内部节点是抽象语法结构或者单词。AST的核心在于它能与输入源代码中的各个语法元素一一对应。

while(i < n){  
sum += A[i++];
}

640

3.2. IR

IR是编译系统或程序静态分析系统的核心，它是源程序在编译器或者静态分析器的内部表示，所有的代码分析，优化和转换工作都是基于中间表示进行的。IR一般由AST经过类型检查和规范化后转换而来。对编译器来说，它在中间表示上做完分析和优化工作后，将中间表示转换为其他语言源代码或者汇编/目标语言。而静态分析工具则会在中间表示上进行语义或未定义的行为分析，然后结合各种预定义规则或者用户自定义规则检测源代码的各种漏洞或缺陷。在现代编译器和静态分析工具中，通常会使用控制流图（Control Flow Graph，CFG）来表示程序的控制流，使用静态单赋值（Static Single Assignment，SSA）来表示程序中数据的使用-定义链（Use-Def Chain），这两个关键数据结构都是AST中没有的。

IR描述的是程序的实际执行过程

3.3. 比较

对AST进行类型检查和规范化，即可转换为IR.

3.3.1. 优势

  1. 准确性更高

AST作为输入源代码的树状表示，本身缺乏表示控制流和控制流的方式。AST是非规范化的，相同语义的结构如果写法不同，它们在AST上的表示也会不同。例如C语言中使用for、while和if/goto表达的循环结构，它们的AST是不一样的；而转换为IR后产生的控制流图是一样的。

  1. 输入语言无关

通常AST都是输入语言相关的，比如C程序有对应的C AST，Java程序有对应的Java AST,IR一般来说是输入语言无关的，不管是C源代码、Java源代码或者其他语言的源代码，它们都能被转换到一个语言无关的IR上。

  1. IR更稳定

例如现在C++规范每3年就会出一个新标准，引入新的语法结构，意味着AST每3年就会出现新的节点需要处理。如果将分析引擎建立在AST基础上，那么分析引擎也需要每3年更新一次处理这些新节点；而如果将分析引擎建立在IR基础上，则仅需将新的AST节点转换为已有的IR结构或操作，从而保持分析引擎基本不受影响。

3.3.2. AST适用场景

AST上适合做一些代码规范的检查，图模式匹配:

  • 标识符命名规范检查
  • 常见的编码惯用法检查

3.3.3. IR适用场景

IR上能进行更深层次的

  • 流敏感分析
  • 过程间分析
  • 上下文敏感分析
  • 对象敏感分析

从而实现各种更高难度的程序漏洞检查

4. 程序静态分析与其他技术的关系

4.1. 声明式编程与函数式编程

命令式编程允许对地址内存直接进行操作,对于涉及二进制运算的问题尤其可以直接解决. 如计算图中二进制数中1的个数,可以直接右移位>>(最好是无符号右移位>>>).通过取模运算（i % 2）或者 AND 操作（i & 1）检查最右位是否为 1,每一个被检查过后的位数会直接右移出边界而被屏蔽,最左边的空位则用0填充.

4.2. 逆向工程

4.2.1. 密码破解

  1. 程序运行时查找字符串
  2. 找到对应程序指令,如加载用户名与密码,以及匹配的函数
  3. 将对应指令,如比对的函数改变成nop,即空操作;
  4. 改变返回的参数,并维护对应逻辑,如某个跳转

4.2.2. 资源替换

使用工具找到对应资源,并替换

4.3. 结构化编辑器

4.3.1. Parser构建

  1. 尽量拿别人写的 parser 来用。维护一个 parser 是相当繁琐耗时，回报很低的事情。一旦语言有所改动，你的 parser 就得跟着改。所以如果你能找到免费的 parser，那就最好不要自己写。现在的趋势是越来越多的语言在标准库里提供可以 parse 它自己的 parser，比如 Python 和 Ruby。这样你就可以用那语言写一小段代码调用标准的 parser，然后把它转换成一种常用的数据交换格式，比如 JSON。然后你就可以用通用的 JSON parser 解析出你想要的数据结构了。

如果你直接使用别人的 parser，最好不要使用它原来的数据结构。因为一旦 parser 的作者在新版本改变了他的数据结构，你所有的代码都会需要修改。我的秘诀是做一个“AST 转换器”，先把别人的 AST 结构转换成自己的 AST 结构，然后在自己的 AST 结构之上写其它的代码，这样如果别人的 parser 修改了，你可以只改动 AST 转换器，其它的代码基本不需要修改。

用别人的 parser 也会有一些小麻烦。比如 Python 之类语言自带的 parser，丢掉了很多我需要的信息，比如函数名的位置，等等。我需要进行一些 hack，找回我需要的数据。相对来说，这样小的修补还是比从头写一个 parser 要划得来。但是如果你实在找不到一个好的 parser，那就只好自己写一个。

  1. 很多人写 parser，很在乎所谓的“one-pass parser”。他们试图扫描一遍代码文本就构造出最终的 AST 结构。可是如果你放松这个条件，允许用多 pass 的parser，就会容易很多。你可以在第一遍用很容易的办法构造一个粗略的树结构，然后再写一个递归树遍历过程，把某些在第一遍的时候没法确定的结构进行小规模的转换，最后得到正确的 AST。

想要一遍就 parse 出最终的 AST，可以说是一种过早优化（premature optimization）。有些人盲目地认为只扫描一遍代码，会比扫描两遍要快一些。然而由于你必须在这一遍扫描里进行多度复杂的操作，最终的性能也许还不如很快的扫完第一遍，然后再很快的遍历转换由此生成的树结构。

  1. 另外一些人试图在 parse 的过程中做一些本来不属于 parser 职责的事情，比如进行一些基本的语义检查。有些人会让 parser 检查“使用未定义的变量”等语义错误，一旦发现就在当时报错，终止。这种做法混淆了 parser 的作用，造成了不必要的复杂性。

就像我说的，parser 只是一个解码器。parser 要做的事情，应该是**从无结构的字符串里面，解码产生有结构的数据结构。**而像“使用未定义的变量”这样的语义检查，应该是在生成了 AST 之后，使用单独的树遍历来进行的。人们常常混淆“解码”，“语法”和“语义”三者的不同，导致他们写出过度复杂，效率低下，难以维护的 parser。

  1. Recursive descent 和 parser combinator 写出来的 parser 可以非常强大，你甚至可以把上下文传递到递归函数里，然后根据上下文来决定对当前的节点做什么事情。而且由于代码可以得到很多的上下文信息，如果输入的代码有语法错误，你可以根据这些信息生成非常人性化的出错信息。

4.3.2. 编辑器插件

如果一种编辑器可以让你直接编辑程序的 AST 结构，而不是停留于文本。每一个界面上的“操作”，对应的是一个对 AST 结构的转换，而不是对文本字符的“编辑”;并且能够直接把程序语言保存为结构化的数据（如JSON），之后再对应“解码”，则可以不需要针对不同的程序语言进行不同的 parse。最终,这一个IDE有望实现支持所有的程序语言。2

4.4. LLVM

llvm是low level virtual machine的简称，其实是一个编译器框架

Footnotes

  1. parser除了转化程序文本成AST这样的数据结构，也有用于处理 CSV，JSON，XML 之类的格式。 ↩

  2. 编辑器与IDE ↩

Graph View

Backlinks

  • No backlinks found