Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Rendezvous: A Search Engine for Binary Code

论文下载

Abstract && Introduction

  • 代码克隆检测在代码重用,软件著作权维护,识别代码中的相近漏洞具有重要意义。
  • 本作提出了一个能够在二进制程序中索引以及搜索代码的搜索引擎Rendezvous。Rendezvous通过使用一个包含指令助记符、控制流子图以及数据常量的统计模型来确认识别一段二进制代码。并通过一定的规范化来避免不同的编译以及优化方式造成的差别。

System Detail

  • First,将二进制程序反汇编,并以它的每段函数作为操作对象;
  • Second,从这些函数中抽取tokens包括指令助记符,控制流子图以及常量:
    1. Instruction mnemonics:使用了Dyninst动态二进制插桩工具来抽取指令助记符,并使用低位8bit来进行编码记录,来构造n-gram model。考虑到指令的顺序不一定对程序语义具有影响,同时构造n-perm model。
    2. Control Flow Sub-graph:不标记整个CFG,而是抽取k-graghs(k个BB的控制流关系),同时使用一个kk bits的数字来记录这个有向子图的邻接关系。通过构造一个external virtual node V ,来记录k个BB与其他BB的控制流关系,作为extended k-graghs。
    3. Data Constants:记录下作为操作数以及pointer offsets的32-bit整数(不包括与栈指针以及段指针相关的offsets),还有字符串常量。(仅记录第一次寻址所得到的数据)
  • Third,使用这些tokens构成的query terms来构建search query(查询系统)
    • 对于用户输入的Query,找到最相似的Document返回给用户。
    • 搜索引擎的关键步骤就是建立倒排索引,倒排索引一般表示为一个关键词,然后是它的频度(出现的次数),位置
  • Statistical Model

Evaluation

  • 对glibc以及coreutils进行了测试;
  • 全程讨论了特征参数对结果的影响。