Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

ByteWeight: Learning to Recognize Functions in Binary Code

论文下载

作者是来自CMU的Tiffany Bao, Jonathan Burket, Maverick Woo, 以及David Brumley还有University of Chicago的Rafael Turner等人。

发表于USENIX’14

Abs & Intro

  • 主要是介绍了函数识别对静态分析的重要性。
  • 其中Rosenblum 等人提出了一个开创性工作,他们将二进制程序中的函数识别问题当做supervised machine learning classification problem来进行解决。

Running Example

  • 给出了一个由于不存在直接的调用关系而导致IDA无法识别的例子

Fig

而本作给出的方法,相较于IDA具有更高的识别率,更低的错误率

Problem Definition and Challenges

  • 本文在此说明了,二进制程序中,函数是一系列指令的集合,并且这些指令不需要在一个连续的内存地址上。
  • 本文主要解决的问题就是:
    • Function Start Identification
    • Function Boundary Identification
    • Function Identification
  • 在解决这三个问题时,这其中存在着诸如以下的难点:

Challenges

  • Not every byte belongs to a function
  • Functions may be non-contiguous
  • Functions may not be reachable。由于间接调用导致的问题
  • Functions may have multiple entries:这里例子举得很奇怪,没有特别之处
  • Functions may be removed
  • Each compilation is different

BYTEWEIGHT

  • 利用机器学习的方法,BYTEWEIGHT在分析新的编译器以及新的编译条件产生的Binary,不需要依靠人工添加相关模式或者启发式策略,而是自动化地去生成可用于匹配的literal patterns
  • 这个系统的Overview如下图所示

Fig

  • 和解决传统的分类问题一样,首先需要一个training phase。在训练期间,BYTEWEIGHT利用由源码编译出大量的带有完全调试信息的二进制程序用于学习,在学习时,系统算法根据已知的函数起始时的字节或者指令序列,生成一个weighted prefix tree。作者通过计算从根节点到目标节点的指令序列在training set中出现这个指令序列时并作为函数入口指令的概率,作为这个点的权值。
  • 在实现的过程中,BYTEWEIGHT开发了两种模式:一种直接处理raw bytes;另一个种处理规范化后的指令。

Learning Phase

  • 可分为三步:
    • Extract first l elements for each function (Extraction):l是指定的一个长度值
    • Generate a prefix tree (Tree Generation):
    • Calculate tree weights (Weight Calculation):

Classification Phase

  • 利用在学习阶段建立Weighted Prefix Tree进行匹配。 对于一段指令序列,它的权重,是由它在这个prefix tree中匹配到的最后一个节点上的权值决定的。如果这段指令序列的权值大于一个预先定义的阈值,那么就可以认定这段指令序列是某个函数的入口。

The Function Identification Problem

  • 一旦获得了函数的入口点,就可以从入口点出发,根据指令中的跳转解决,包括直接跳转以及间接跳转(利用VSA来判定它的跳转目标),恢复出整个函数的CFG。

Recursive Function Call Resolution

  • 模式匹配的方式也可能出现遗漏,所以利用RFCR的方法,根据已知的一些函数调用,来判定没有被模式匹配方式所检测到的函数入口点。

Evaluation

  • 作者通过将BYTEWEIGHT与一些已知的二进制程序分析工具进行比较,并给出了一个比较好的结果:

Fig