Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Detecting Code Clones in Binary Executables

Abstract & Introduction

测重的重要性,例如代码重构,检测bug以及保护知识产权。以往的方式是对源码进行检测,考虑到源码不易得到,本作提出了第一种针对二进制程序的可用的克隆检测算法。二进制文件导致了一些额外的问题,例如编译过程中的多变性导致的检测更为复杂,以及汇编代码的扁平式结构相比源码更难操作。

本作在tree similarity framework的基础上,通过模型化指令序列的必要的结构信息,构建数值化向量,归类相识向量来识别克隆。

Overview & Algorithm Description

  • Binary Disassembly

反汇编二进制文件,生成这些binary的中间表达(Our intermediate representation preserves all binary file information, including instructions, functions, header information, segments, etc.)。所谓的中间表达,通过给定window和stride对二进制文件中的每个函数切分成代码段。

  • Code Region Normalization

对抽取的每个代码段,创造规范化的指令序列,将指令规范化为<mnemonic, operands>的格式,并使用MEN[],REG[]以及VAL[]的数组,存储并替代格式中的指令操作数的信息。

  • Clone Detection

    • Exact Clone Detection:建立哈希表,对代码段进行哈希值比较,构建相应的clone cluster。
    • Inexact Clone Detection根据代码段中的指令特征构建相应代码段的特征向量,包括
      • M(Mnemonic)
      • OPTYPE(每个指令中的每个操作数类型)
      • M*OPTYPE(mnemonic和这个指令第一个操作数类型的结合)
      • OPTYPE*OPTYPE(指令中第一个操作数类型和第二个的结合)
      • OPTYPE*Nk(在操作数数组规定index范围k内的操作数)
    • 根据特征向量,使用LSH(locality-sensitive hashing),构建clone clusters。
  • Removing Trivial Clones:由于在对每个函数切分所得的代码段之间,存在着重复的指令片段,需要对这些代码段进行精简。

  • Finding Largest Clones:将检测出存在克隆的连续的代码段进行合并。

Experimental

  • 主要是window size即binary中代码段的分段长度对实验各个环节的影响
  • 对Windows XP中系统文件的一次检测,给出了一个看上去很厉害的图,其中绿色点表示存在代码克隆:

Fig

PS

整篇论文讨论的工作给出的几个算法其实看上去都比较一般,最关键的应该是其中构造特征向量时所收集的五个特征,以及特征向量相似检测时clusters的思想。 以上纯属个人想法