Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Achieving Accuracy and Scalability Simultaneously in Detecting Application Clones on Android Markets

论文下载

1 Introduction

本论文定义了一个图的几何特征 —— centdroid,用于测量两个APP的methods的相似度,根据相似度得出是否为APP克隆的结论,有较高的精确度(accuracy)及较大的应用规模(scalability)。

Unique Characteristics of App Clones

  • A billion opcode problem:opcode量大
  • code fragment clones and app clones: code fragment相似不代表是克隆APP,可能是相同三方库。只有核心代码相同才算克隆
  • Type 2 and Type 3 clones are prevalent on Android markets: 目前市场的APP clone大多是2,3类型的。

四种克隆类型:

  1. 大部分代码完全相同
  2. 大部分代码语义完全相同
  3. 代码有改动,增添或删减部分代码
  4. 相同的算法,但应用的形式有变化

现状分析

很多方法只能区分1类型,对于2,3类型的分析准确度不足,例如String-based, token-basedand AST (Abstract Syntax Tree)-based等等

PDG(program dependence graph)等依靠图的同态来分析的方法,对于2,3类型的准确度足够,但存在效率不足的问题。

结论:

  • 依靠图来分析方法,如果能够避免利用图的同态性(graph isomorphism)来分析,会大大提高效率
  • 分辨app clone需要比较不同市场中的APP,代码量巨大。一对一比较的复杂度为C(2,M),M为method个数。需要降低这个复杂度

特点

  • 在保证针对2,3类型的准确率的同时,不用同态性比较,大大提高了效率。
  • 在比较之前进行分类,不需要一对一的比较,复杂度降低,提升效率。
  • 只比较core functionalities,可以有效针对添加库和广告的克隆

2 Detail

centroid

PDG(program dependence graph) ->  CFG(control flow graph) -> 3D-CFG ->  centroid(重心坐标)

centroid相同,method一定相同,同时具有单调性,centroid相差大,method相差一定大。

ASD

定义了Application Similarity Degree

Clone Group

定义了可能是克隆的分组规则,将centroid相近的分在一起,用于比较。

流程

  • 在不同市场下载APP,转化为smali
  • 转化为centroid,存入数据库,包含market name,app file name, class name, method name and centroid
  • 将每个method只与Clone Group中的method相比较,复杂度为 M*c, c << M

3 Evaluation

Five typical third-party Android markets:

  • two American markets (Pandaapp and Slideme)
  • two Chinese markets (Anzhi and Dangle)
  • one European market (Opera).

Figure 1

  • 误报率:<1%
  • 漏报率:0.4—0.7%
  • 同时具有较高的效率,一个小时可以处理150145个APP,每个method只需同组内小于8个其他的method进行比较。
  • 如果有新的APP与数据库中已有数据比较,效率也是很快。。