国庆节看学弟们在参与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还是很好用的,用来画流程图非常好用。
手写一个还是很有成就感的!