从汇编语句生成CFG：以balsnctf2019 Hack Compiler为例

Posted on Edited on In

国庆节看学弟们在参与balsnctf2019，有一个逆向是给一段汇编，要求拿到flag，这段汇编是一种自定义的，因此没有现成的工具来处理它。我只是凑个热闹，虽然我没有做出来，但练习了一下手绘CFG，挺有意思的，本文讲一下CFG的基础知识和如何手绘CFG。

本文使用到的环境：python2、win10、graphviz-2.38、pypi: graphviz 本文涉及到的代码：https://gist.github.com/LeadroyaL/4e068787e075e9ff030c4937f5c113bd

一、 使用和安装graphviz，选择合适的binding

graphviz是一款很好用的软件，本体是 http://graphviz.org/ ，包含一系列套件，我们用到的是它的 "dot" 工具，用于输入.dot文件，输出pdf/png等便于观察的格式。

.dot文件其实是一个文本文件，用文本来描述各个区块、它们的联系，例如下方的dot就是可以描述一张图

1
2
3
4
5
6
cat 1.dot
graph example1 {
Server1 -- Server2
Server2 -- Server3
Server3 -- Server1
}

在Mac上，有一款非常好用的软件叫 http://www.pixelglow.com/graphviz/ 用于加载.dot文件，本文展示的是windows上的，没找到合适的软件，于是使用自带的渲染成pdf的功能。

在Windows上安装很简单，直接下载到某个目录，再将bin目录添加到PATH里，就完成安装了，效果如下

1
2
3
4
5
6
7
PS C:UsersLeadroyaL> dot --help
Error: dot: option -- unrecognized
Usage: dot [-Vv?] [-(GNE)name=val] [-(KTlso)<val>] <dot files>
(additional options for neato) [-x] [-n<v>]
(additional options for fdp) [-L(gO)] [-L(nUCT)<val>]
(additional options for memtest) [-m<v>]
(additional options for config) [-cv]

本文的目的是：输入一段汇编，尽可能绘制出它的CFG，因此对文本处理还是比较多的，于是使用python的binding，具体使用的是 https://github.com/xflr6/graphviz ，稍微有点demo用起来比较顺手，使用

1
pip install graphviz

就可以成功安装。

二、CFG简介

科普一下静态代码分析的基础，CFG 全称是 Control Flow Graph，控制流图。

本身是一个抽象的概念，有两个很形象的地方，一个是IDA里、F5之前的图形模式，那个图就是CFG，另一个是在llvm开发Pass的时候，IR层面的Function包含一个函数，叫viewCFG，会自动调用系统的graphviz功能绘制当前函数IR级别的CFG，非常优雅。

有一个比较抽象的地方，就是soot的BriefCallGraph，会对Java的Method生成一份CFG。

例如下方的两张图，摘自我其他文章中出现过的图片

用LLVM的IR层举例最为合适，LLVM会将函数分为N个BasicBlock，入口是一个BasicBlock，每个BasicBlock包含N个Instruction，最后一个Instruction表示下一个BasicBlock是如何产生的，最常见的就是直接跳转和条件跳转指令，直接跳转一定会发生，因此只有一个successor（后继），而条件跳转会有两个successor，在简单的分析时是无法知道走哪个分支的，因此在CFG中会出现分支的现象。各个BasicBlock共同组成这个函数，出口BasicBlock可能不止一个。

BasicBlock的划分，意思是，第一句指令被调用后，整个BasicBlock都会被完完整整地执行一遍，因此是静态代码分析中的较为基础的一个单位。

之前有过手动构造过CFG的想法，但是没有实际操作过，主要是因为需要考虑的case太多，第一个难点是函数范围判定，自己是很难实现的，另一个难点是，对控制流造成影响的汇编指令不一定全，例如ARM汇编，最常见的是B/BX等函数，其他少见的指令可能也可能会导致PC发生跳变。

因此，本文讲述的是使用朴素的思路，只处理直接跳转和条件跳转两种case。

三、理解并解析汇编指令，使用python解析汇编

balsnctf2019 Hack Compiler 正题来了，这是国庆节假期的某一天，看到群里有学弟在做逆向，本来想练习一下使用机器来辅助逆向，结果发现是个汇编阅读的硬核题目，使用C和一些自定义的方式，生成自定义汇编语言，flag就在里面。估计学弟们搞不定，汇编太长了逻辑很不清晰，于是就想练习花一个CFG稍微帮他们一下。

先声明，这题我没做出来，只是出于兴趣画一下CFG而已。

题目简介在这里：

1
2
3
4
5
6
7
8
9
10
11
12
There is a password checker on a Hack machine. [https://www.nand2tetris.org/]
Can you solve it?

Compiler: https://github.com/qazwsxedcrfvtg14/Hack-Assembly-Language-Compiler

download link: here [https://static.balsnctf.com/hack-compiler/7iJOgwN2bDm9ssTTjy6L3iKW9i9qntUZ/main.asm]

Hint:
https://github.com/johnchen902/nand2tetrisVM2
https://static.balsnctf.com/hack-compiler/7iJOgwN2bDm9ssTTjy6L3iKW9i9qntUZ/program

Author: qazwsxedcrfvtg14

汇编也比较好理解，直接看几个跳转例子吧：

直接跳转，跳到label:@XUSTACSN

1
2
@XUSTACSN
0;JMP

条件跳转，跳到label:@MZEDYMGF

1
2
@MZEDYMGF
D;JNE

间接跳转（无法预测）：

1
2
3
4
5
@15617
M=M-1
AM=M-1
A=M
0;JMP

其他语句都不影响的，于是思路如下

1、先解析label，放好label->addr的映射，如果多个label同时标记同一个地址，按照第一个label记录。

2、将Function拆分为N个BasicBlock，遍历一遍，跳转语句的目标地址、跳转语句的下一句的地址，标记为BB的初始位置。

3、按照初始位置，将asm分成多个BB。

4、遍历每个BB的最后一个指令，进行跳转的预测，可以获得各个BasicBlock的后继，有三种情况： 绝对跳转，后继就是目的地址 条件跳转，后继是目的地址和下一句 非跳转语句，后继是下一句 之后将这个关系保存为有向图，使用.dot进行描述，也比较简单，就标记各个BB的范围，描述各个BB指向的下一个BB，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# coding:utf-8
from graphviz import Digraph

# 先加载asm文件，按照列表的方式去存

fd = open("main.asm")
lines = [l.strip('n') for l in fd.readlines()]
fd.close()

# 遍历label，找到label对应的addr（应该是第一个label的addr）
label_addrs = dict()

for i in range(len(lines)):
    a = lines[i]
    if a[0] == '(' and a[-1] == ')':
        j = i - 1
        while True:
            if lines[j][0] == '(' and lines[j][-1] == ')':
                j -= 1
                continue
            label_addrs[a.strip("()")] = j + 1
            break

# 按顺序遍历汇编，以 branch 语句作为BB的结束，以 branch 语句的目的地作为BB的开始
# sps存放各个BB的开头地址
sps = set()
sps.add(0)
sps.add(len(lines))
for i in range(len(lines) - 1):
    a, b = lines[i], lines[i + 1]
    if "JMP" in b or "JLT" in b or "JEQ" in b or "JGT" in b or "JLE" in b or "JNE" in b or "JGE" in b:
        if "@" in a:
            # 找到label对应的addr
            print "Branch at", b, "to", a, label_addrs[a.strip('@')]
            # 检查是不是最后一个指令
            if i + 2 < len(lines):
                sps.add(i + 2)
            sps.add(label_addrs[a.strip('@')])
        else:
            print "Indirect Branch:", a, b
sps = list(sps)
sps.sort()
print sps

bbs = []
for i in range(len(sps) - 1):
    a, b = sps[i], sps[i + 1]
    bbs.append((a, b))

  使用graphviz的python-binding，绘制它，最后效果如下（太小了，大图见pdf文件）

# 使用API，按地址从小到大顺序创建各个BB
dot = Digraph(comment='The Round Table')
for start, end in bbs:
    dot.node('Node%d' % start, 'Some data %d~%d' % (start, end), shape='box')

# 创建连接关系：如果末尾是普通语句，就连接到下一个，如果末尾是跳转语句，就连接到跳转的位置
for start, end in bbs:
    bb = lines[start:end]
    a, b = bb[-2], bb[-1]
    if "JMP" in b and '@' in a:
        nextBB = label_addrs[a.strip('@')]
        dot.edge('Node%d' % start, 'Node%d' % nextBB)
    elif ("JLT" in b or "JEQ" in b or "JGT" in b or "JLE" in b or "JNE" in b or "JGE" in b) and '@' in a:
        nextBB = label_addrs[a.strip('@')]
        dot.edge('Node%d' % start, 'Node%d' % nextBB)
        dot.edge('Node%d' % start, 'Node%d' % end)
    else:
        dot.edge('Node%d' % start, 'Node%d' % end)
print dot.source
dot.view()  # 后面这句就注释了，也可以使用这个命令查看效果

ok 目的达成，程序的大致流程已经看懂，对逆向还是稍微有点帮助的，心里稍微有点B数

四、总结

CFG是一个很朴素的东西，不要害怕这个概念，就是一个描述程序执行逻辑的有向图，是静态代码分析很基础的概念。

graphviz还是很好用的，用来画流程图非常好用。

手写一个还是很有成就感的！