Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

安全论文每日读-- 2015.03.12

今天介绍一篇2015年NDSS会议上的论文:No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations,文章主要讨论了现有反编译工具的不足,并提出了相关的改进。

  • 作者:Khaled Yakdan, Sebastian Eschweiler, Elmar Gerhards-Padilla, Matthew Smith
  • 单位:德国波恩大学

Overview

  • 当前的问题:反编译对于安全应用的分析有着举足轻重的作用,然而当前的反编译器都依靠结构分析(structure analysis)这种模式匹配的方法,使得恢复出的源码中存在大量goto,严重影响可读性。
  • 问题的意义:优质的反编译可以有效取代低效的人工软件逆向,反馈出源码后,就可以借助已有的源码分析工具进行进一步的分析,包括漏洞分析、污点分析等
  • 文章的方法:提出与模式无关的控制流结构化算法,使得反编译得到的源码中不存在goto等影响阅读的元素

Toy Example

Toy_1

Toy_2

  • 上述Figure 5是对Figure 3中控制流图回复的源码比较,其中Figure 5左边的是文章提出的方法,而右边的是Hex-Rays恢复的源码

Architecture of the Approach

Alt text

  • 如图, 因为第一部分是文章的重点,以下将会着重介绍控制流结构化的步骤:模式无关的控制流结构化算法

Pattern-Independent Structuring

  • 输入:划分好区域、定义好起始结束点的控制流图(CFG)
  • 输出:抽象语法树(AST)

一些需要预先解释的

  • 这里介绍的算法处理的是只有一个入口、一个出口的有向无环图
  • 对于循环,先无视backward edge,当做无环处理
  • 起始点、结束点:即Dominator,如例子中的$b_1, n_7, c_1, n_9, d_1, n_8$
  • 区域:Dominator以及其间点和边的集合,如例子中的$R_1, R_2, R_3$

Reaching Condition

  • 即程序要到达每个程序点需要满足的条件,比如例子中,$n_5$的Reaching Condition是 !b_1 || b_1 && !b_2
  • 在确定起始、结束点的情况下,只需要简单的深搜(DFS)就可以得到每个点的可达条件

Structuring Acyclic Regions

Alt text

  • 如图,道理上,直接将最左处理成连续 if(condition){body} 也是正确的
  • 但为了提高可读性,会做一些合并处理,如 $n_5, n_6$ 的条件是相反的,可以合并成 if(condition){n_5}else{n_6} 形式

Structuring Cyclic Regions

  • latching node:循环中的最后一个点,即将起始点作为直接后继的点。如例子中的 $c_3$
  • loop node:起始点和latching node间路径上的点
  • successor node: 离开循环后执行的第一个点

由上,可以把循环中的点分类,其中直接前驱是loop node的点也被认为是loop node, 和无环情况类似,以上已经可以得到正确的AST了,但有很大提升可读性的空间,这就是需要长期积淀的工作了

Alt text

上图的简化过程都是平时经验的总结(具体规则见附录)

Semantics-Preserving Control-Flow Transformations

以上都是针对单入口、单出口的CFG的处理,但实际中的循环有很多多入口、多出口的情况,如例子中的$R_1$就是多出口,所以这里目的把多入口、出口情况转化成单入口、出口情况,就可以统一处理了。

多入口:原本while(c){...}的循环检测就变成while(c || i){...},循环体会重置标识位$i$的值

Alt text

多出口:想法就是把原来循环体中的条件放到循环体外检测

Alt text

Evaluation

Metrics

  1. Correctness:语义等价
  2. Structuredness:反编译出的代码中的goto数量衡量
  3. Compactness:反编译器输出的代码的总行数

Experiment && Results

  • 正确性的测试将GNU Coreutils作为实验对象,用准备好的testcase分别测试已有的二进制文件和反编译出来的源码编译成的二进制,比较二者的结果。

Alt text

  • 结果总共1738个函数,编译成功的1530个函数全部通过了测试
  • 因为文章的方法的目的是没有goto,所以Structuredness的统计显然是0;而没有了goto和label了之后,这里恢复出的代码的规模(代码行数)也显然少于其他反编译器(如IDA)

Appendix

Alt text