Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Finding Software License Violations Through Binary Code Clone Detection

论文下载

Abstract

  • 有很多软件使用一些第三方开源代码库的代码,却不遵循其开源协议的规定。文章作者创建了一个工具Binary Analysis Tool(BAT)来检测程序、硬件固件中的违反开源协议的情况。

Introduction

  • 问题

    • 有很多设备(路由器,电视)的固件,包含了基于linux内核,busybox,samba,但是其本身却违反了开源协议,没有将源代码全部开放。(Linksys WRT54G被发现)
    • 有一些下游厂商,会将上游厂商的设备重新贴牌后销售,他们也有了解上游厂商提供的固件是否违反开源协议的需求。
  • BAT的检测方法:

    • 基于字符串的检测
    • 基于压缩相似性的检测
    • 基于Binary Delta(Binary Diff)的检测

Background and Related Work

  • 论述了GPL Violations产生的原因,目前已有的源代码、二进制代码级别的code clone的检测手段,包括开源licenses的分析
  • 与本文相关:
    • ISSTA09 的Detecting code clones in binary executables 需要对不同架构有不同的反汇编器,太麻烦
    • 对开源liceses的分析不在本文讨论范文之内

检测方法

  1. 基于字符串的检测:
    • 对第三方库的源代码进行处理,去除注释,宏等等之后,提取第三方源代码中出现的所有的字符串。
    • 直接利用strings命令提取二进制文件中的字符串,比较是否出现在第三方源代码中
    • 根据字符串的稀有程度,字符串的长度,来综合产生最后的结果,最后将得分大于100的第三方库作为结果
  2. 基于压缩相似性的检测:
    • x=待检测文件,y=某一三方库的二进制代码,C=某一压缩算法
    • reuse(x, y) = (|C(x)| + |C(y)| – |C(xy)|)/C(y) 用来定义“y中的多少出现在了x中”
    • 问题:
      • 需要一个压缩窗口足够大的压缩算法。选用xz算法,窗口为100MB级别
      • 如果y的长度过小,公式改为reuse(x, y) = (|C(x)| + |C(y)| – |C(xy)| – beta)/C(y) , beta定为1000(Byte)
  3. 基于Binary Delta的检测:
    • linux下有一些针对二进制文件的diff工具,他们会尝试利用x中部分内容构建出y,生成一个patch文件,patch中只有两种指令,一种是“将x的某一段数据输出”,另一种是“将0x112233445566aabbccee输出”
    • 定义reuse(x, y) = 1 – D(x, y)/D(全0文件, y)

实验

  • 三个方法分别对一些二进制程序实验 recall分别为 0.83 0.72 0.64, precision 0.85 0.91 0.89
  • 字符串方法对两个固件和core dump of an obfuscated executable,发现大的二进制文件字符串太多了。。。所有第三方代码库的评分都特别高,所以分别区top 88、38、88作为结果, presicion 为0.48 0.68 0.31