Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

WuKong: A Scalable and Accurate Two-Phase Approach to Android App Clone Detection

ISSTA’15

论文下载

Abstrat

  • 本文介绍的是一种重打包检测的框架,相比以往的重打包检测,本文的特点是:分类粗粒度和细粒度两种检测模式,兼顾效率与精度,在检测初始可以排除第三方库,自动识别不需要白名单,提高检测准确率。
  • 对于效率与精度,之前有过的方法,主要是基于hashing的方法和程序依赖图方法,前者速度快精度差,后者精度搞速度慢。
  • 第三方库的处理上,现有的方法都是白名单过滤,但建立白名单需要预先知识,无法完全自动化。

Overview

本文针对上述问题给出的核心方法是两个,一是用聚类的方法实现自动化的第三方库识别,二是使用两步方式进行相似性检测,先通过粗粒度筛选找出备选APP,然后再进行细粒度比较。

Fig

第三方库识别中采用了聚类的方法,先反编译成SMALI代码,然后提取smali代码中的特征,这里的特征指的是不同API调用的次数

两步检测方法

  1. 粗粒度检测:
    • 特征向量为每个API调用的频率,使用曼哈顿距离,如果两个APP的距离超过阈值且签名不同则列为进一步检测对。
    • 在进行大规模比较的时候作者提到了一个技巧,两两比较计算量很大,实际操作中,如果两个APP的API种类数相差很大,那么就退出对比。
  2. 细粒度检测:
    • 细粒度检测的方法是分析一个context下的变量出现的次数,计数方法有三种,一种是简单的记录出现次数,一种是in-statement的计数,例如每个变量if判断下出现的次数,变量进行加操作的次数,最后一种是inter-statement的计数,例如循环展开,变量在每次循环中涉及的次数。

Evaluation

Fig

实验选取了一共10W个APP,来自5个不同的应用市场,预处理中,一共收集了440W个sub-package,图6是每个subpackage调用的API数量

Fig

预处理结果,过滤第三方库聚类的效果

Fig

Fig

处理之前超过70%的app包含有8到127个非空的sub-package,平均每个app包含41.8个。处理之后,大部分app包含1-32个subpackage,平均只有15.8个。

Fig

粗粒度检测

一共需要检测的app pairs大约50亿,经过粗粒度检测,剩下9W多app pairs需要检测。涉及的app为14702个。

Fig

结果验证,对于false positives,作者随机选取了2W个APP,将分析结果与Androguard的结果进行对比,结果显示,所有检出的重打包应用均为真实的重打包,所以作者说他们的工具没有false positive,此外他们还检测出了一些Androguard没有检测出的重打包应用。

此外作者在设计样本时人工生成了一些重打包应用,放到样本集中,最终没有一个漏报。由于无法建立ground truth,所以无法做false negative的实验