国庆节看学弟们在参与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:\Users\LeadroyaL> 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 |
# 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文件）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# 使用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还是很好用的，用来画流程图非常好用。
手写一个还是很有成就感的！