Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code

论文下载

Abstract & Introdutcion

背景与SP’15类似(Cross-Architecture Bug Search in Binary Executables)

  • 源码bug检测难以满足需求,因为软件闭源和编译环境问题
  • 当前二进制相似代码检测的问题:
    • 动态方法难以跨架构
    • 基于语义特征的方法效率低下

Approach

  • 为了提高效率,只能静态分析
  • 分两步走,先用简单的特征向量缩小比较范围,而后用复杂的图同构比较方法进一步比较

Coarse Grain

  • 特征向量包括: Fig
  • 平均相关度越高,标准差越低,说明特征越鲁棒
  • 用KNN算法计算距离

Fine Grain

  • 最大子图同构匹配
  • 接下来是图论的问题;(原本看看图的表示方法觉得很高大上,刚才才发现就是{节点, 边})
  • (子图同构匹配是经典问题了,貌似最近有风声说复杂度要降低,反正这里还是当NP完全的)
  • 已有方法复杂度高,没法破,限定循环数量折中

Evaluation

Correctness

  • 将openssl 1.0.1e在不同编译环境、架构上编译,得到1293个函数
  • 随机选取函数,在代码库里搜索,重复100w次(?!)
  • 准确率高达93.93%

跨架构漏洞查找

  • 几乎照搬SP’15的实验
  • 结果从效率和效果双重打压对方