糟糕! 8月只剩最后一天啦! 而我的文章还是一篇没写
最近在忙于一个非常有意思的事情, 以至于没有时间搞出一篇正经点的文章, 草稿站里倒是有了几篇草稿, 今天抓着 8 月的尾巴更新一篇. (P.S. 王吓吓终于睡着啦.!!
早在很久以前, 具体一点说, 应该是在 2018 年 12 月 2 日看完 编译器设计 这本书时, 我就想着搞点什么东西出来, 来作为一次总结与回顾. 我就想啊想啊, 一直到了 2020 年 1 月份的时候, 终于想到要搞什么了: 要整一个工具, 能将 gdb disassemble 输出的反汇编代码转换为控制流图并展示出来了. 一个主要诱因是当时有几次线上 gdb 行为, 有时候一时半会没有可用的源码, 不得不从汇编入手, 根据当前执行指针结合着代码梳理出一个大概的执行流从而来完成问题的定位. 所以对于这个工具, 我们对其期望的行为是输入 gdb disassemble 输出的结果, 之后工具输出对应的控制流图. 对应的使用姿势可能是:
gdb --batch -ex 'disas MyAtoI' atoi.out | as2cfg | dot -Tsvg > atoi.cfg.svg
当然市面上已经有了 ida 这类成熟的反汇编工具存在了, 但我好像确实没有找到类似的开源工具, 好吧我当时也确实没有认真去找…
AT&T 与 Intel
在 Linux 中, 有两种最为常见的汇编表示方法: AT&T, Intel; 其中 AT&T 使用范围更广一些, 比如 gdb, objdump -D 在反汇编时默认使用的都是 AT&T 语法. 所以 as2cfg 一开始也是准备使用 AT&T 作为输入. 但随着实现的深入, 却发现好像没有一种快餐地方式来实现对 AT&T 的解析. 举个例子. 我定义了一个 InstAttr 的结构, 存放着一个特定指令的一些属性信息. 在完成一条指令的解析构造指令对应的 Instruction 对象之后. 现在需要将 Instruction 对象与其对应的 InstAddr 关联起来. 一种最为彻底的解决方案就是在语法解析时, 为每一条指令指定其对应的语法构造, 并在对应的语义动作中显式指定该指令对应的 InstAttr, 但是这样太麻烦了, 需要为 intel x86 指令集中每一条指令指定对应的语法构造, 不够快餐能让我快速验证. 另一种方法则是实现构造一个 hashmap, 以指令名为 key, 对应的 InstAttr 为值保存着所有支持的指令以及其对应的属性信息. 之后在根据 Instruction 中记录的指令名查找 hashmap 找到对应的 InstAttr 对象. 这种方法使得可以以一种统一的语法构造来解析所有指令, 比较利于快速验证. 但 AT&T 汇编语法对这种方法就不太友好了, 因为 AT&T 会对指令名加些额外的修饰符来表明额外的语义. 比如 movb, movs 都是指 mov 指令; b, s 这些修饰符指定了指令对应操作数的长度. 而且 AT&T 并不总是在指令名后面追加这些修饰符, 使得我们在处理时不能简单地移除指令末尾的 b,s 等字符来得到其真正的指令. 如下例子演示了对于 bts 这条指令, 这里 bts 是 intel x86 指令集中一条指令, 表明 bit test and set, 这里 s 并不是 AT&T 的修饰符. 可以看到这里这里反汇编输出时输出的并不是 btss.
$ cat test.S
bts %ax, %bx
$ gcc -c test.S
$ objdump -D test.o
Disassembly of section .text:
0000000000000000 <.text>:
0: 66 0f ab c3 bts %ax,%bx
最终, 在 as2cfg 中, 为了快速验证, 还是放弃了对 at&t 汇编语法的支持. 而开始使用 intel 语法, 毕竟在 Intel 语法中, 并不会对指令助记符本身做额外的修改. 这也是最初 commit 中 commit message 的由来:
commit a35e8f97d94509aee8e3c16fe055975be85e366a
Author: 盏一 <w@hidva.com>
Date: Sat Jan 4 14:27:04 2020 +0800
Add parser for intel syntax
I DO NOT LIKE AT&T SYNTAX AT ALL
拿到了线性表示
在确定采用 intel 语法之后, 接下来便是输出对应的 lex & yacc 文件来完成 intel 语法的解析. 这里并没有试图从 Intel 语法规范中来找到 intel 语法的精准定义, 事实上是找了一圈没有找到. 便直接从 gdb disassemble 链路负责输出 Intel 语法的相关代码中看了下 intel 语法的大致长相. 之后根据此编写了 lex & yacc 所需的输入文件. 这其中到没有太大的难度, 主要是一些琐碎的东西. 这部分主体部分便是 inst 了, 其负责指定了一条指令的语法构造. 这里 INST_MNEM 对应着指令助记符, operand 表明了操作数. 根据 INTEL MANUAL 可以看到, 一条指令最多三个操作数, 只需要一一列举出三种情况即可. 值得一提的是, 后续在实际使用上发现一条指令组成除了常规的指令 + 操作数之外. 还可能会有指令前缀, 比如: rep, lock 这些, 这也是哪些带有 inst_prefix 存在的原因.
inst:
INST_MNEM '\n'
{
$$ = *newInstruction($1)
}
| INST_MNEM operand '\n'
{
$$ = *newInstruction($1, $2)
}
| inst_prefix INST_MNEM '\n'
{
$$ = *newInstruction($2)
$$.Instprefix = $1
}
| inst_prefix INST_MNEM operand '\n'
{
$$ = *newInstruction($2, $3)
$$.Instprefix = $1
}
/* 省略了 2, 3 个操作数的情况 */
operand, 考虑到 intel 支持多种操作数寻址方式, 所以 operand 对应的语法构造稍微复杂了点, 这里不再列举, 感兴趣的直接去看源码吧.
至此, 我们便可以很轻松地将输入从 gdb 反汇编生成的文本形式转换为对应的线性表示了. 这里使用 []AddressedInst 来作为线性表示. AddressedInst 表示着一个带有地址的指令, 其定义如下:
type AddressedInst struct {
Addr uint64
Inst Instruction
}
可以转 cfg 了
as2cfg 在设计上接收的输入是一个函数反汇编的结果, 生成的也是该函数对应的控制流图. 这里并未涉及到任何函数间跳转的概念, as2cfg 会将 call 指令作为一个普通的, 类似与 add 这类指令来进行处理. 而且 gdb disassemble 在输出反汇编时已经帮我们确定了每条指令的起始地址, 以及对于 jmp/jcc 这类跳转指令, gdb disassemble 也已经帮助我们确定了这类指令的目的跳转地址了. 所以接下来的工作便是遍历线性表示, 然后生成 cfg.
这其中最核心的部分便是 CFGContext 这个结构了, 其负责维护着当前构造 cfg 所需的所有状态. 而且为了实现 one-pass 处理, 更是额外地引入了复杂度. 实际上, 我现在, 好像都看不懂这块代码了, 好在当时我留了不少的注释, 尤其是强调了每一个状态的语义. 除了 one-pass 之外, 我还整了一些额外的花哨功能.
其中一个便是尽量为边生成更加友好的说明. 如下图所示, 为了生成 dl == 0x9 这种表达式可是额外地引入了不少状态的.
这种情况一种朴素的做法是, 在遇到 je 0x400590 这条指令时, 我们知道当 eflags 中 zf 标志为 1 时, 控制流将跳转到 0x400590 处; 当 zf 标志为 0 时, 控制流将不会跳转, 继续往下走. 因此红色边, 蓝色边对应的说明可以分别是 zf=1, zf=0. 但很显然这样当我们看到 zf=1 时, 我们便需要继续分析之前的控制流, 来晓得这里 zf=1 究竟意味着什么. 对于图中的例子, 较短, 所以很容易看到 zf=1 意味着寄存器 dl 的值等于 9. 但如果之前的控制流过长, 很显然我们就需要费点功夫了. 因此这里 as2cfg 会尽量降低读者的负担, 尽量提供更直观的信息.
另外一个花哨的功能, 便是 SSA. 在引入了 SSA 的思想之后, 如果在一个 block 内看到了两个一样的名字, 那么这俩名字对应的值也一定是一样的. 这里 ssa 的实现基本上是比较简单的, 只需要我们维护好每条指令的输出操作数即可. 唯一让人稍微头秃点的是, Intel 中寄存器的一个部分可能对应着多个寄存器, 毕竟 rax, eax, ax, al 都引用着 al 这部分, 即 rax/eax/ax 值的变更同时也意味着 al 值的变更.
结语
凭心而论, as2cfg 确实是个挺鸡肋的小玩意的. 不过他在某些场合确实起到了作用, 比如在 指令级优化参考手册 中, as2cfg 让我一眼就看到了混用有符号无符号整数之后额外引入的复杂控制流. as2cfg 在几次线上 gdb 中也起到了至关重要的作用.
as2cfg 目前看仍有很多不足, 仍有很多想要的功能还来不及加入. 所以欢迎 pr, 提了就是 committer.
