《Achicving accuracy and scalability simultaneously in detetcing application clone on Android markets》
来源：ICSE 2014
关键词：Software analysis, Android, clone detection, centroid
摘要：
本文针对安卓市场上的重打包问题，提出了基于opcode相似性的检测方案。参考物理学中的“质心”（centroid）概念，此文定义了一个图的几何特征， 构建了基于权重的3D-CFG图，用于测量两个APP的methods的相似度，根据相似度得出是否为APP克隆的结论，有较高的精确度(accuracy)及较大的应用规模(scalability)。
参考官方讲解
1. 背景简介
App Clones的特征：
（1）A billion opcode problem：opcode量大
（2) code fragment clones and app clones： code fragment相似不代表是克隆APP，可能是相同三方库。只有核心代码相同才算克隆
(3) Type 2 and Type 3 clones are prevalent on Android markets： 目前市场的APP clone大多是2,3类型的。
四种克隆类型：
（1）大部分代码完全相同
（2）大部分代码语义完全相同
（3）代码有改动，增添或删减部分代码
（4）相同的算法，但应用的形式有变化
2. 现状分析
很多方法只能区分1类型，对于2,3类型的分析准确度不足,例如String-based, token-basedand AST (Abstract Syntax Tree)-based等等
PDG（program dependence graph）等依靠图的同态来分析的方法，对于2,3类型的准确度足够，但存在效率不足的问题。
table 1是对之前的检测方法的对比，之前的方法都是对code fragment的相似性进行检测，并不能保证代码是克隆的。
结论：
（1）依靠图来分析方法，如果能够避免利用图的同态性（graph isomorphism）来分析，会大大提高效率
（2）分辨app clone需要比较不同市场中的APP，代码量巨大。一对一比较的复杂度为C（2，M），M为method个数。需要降低这个复杂度
特点：
（1）在保证针对2,3类型的准确率的同时，不用同态性比较，大大提高了效率。
（2）在比较之前进行分类，不需要一对一的比较，复杂度降低，提升效率。
（3）只比较core functionalities，可以有效针对添加库和广告的克隆
3. 文章方法centroid
PDG（program dependence graph） -> CFG(control flow graph) -> 3D-CFG -> centroid(重心坐标)
centroid相同，method一定相同，同时具有单调性，centroid相差大，method相差一定大。
*定义了Application Similarity Degree(ASD)
*定义了可能是克隆的分组规则Clone Group，将centroid相近的分在一起，用于比较。
主要思想：
*3D-CFG：CFG的每一个节点都有唯一的一个坐标(x,y,z)。x代表CFG中的序列号，y代表出度，z代表参与的loop个数。
序列号x的选择：从1开始，按照更多statement->更大binary值 来给分支中的节点标号，最后的return语句代表stop节点。
*centroid的定义：
其中wp代表在基本块p中的statement数量
*method级别的相似性度量Centroid Difference Degree(CDD)：
若两个method相同，则CDD=0
*通过去除同一作者的app，和公开的framework和第三方库，来集中寻找cloned apps。
流程：
（1）在不同市场下载APP，转化为smali
（2）转化为centroid，存入数据库，包含market name,app file name, class name, method name and centroid
（3）将每个method只与Clone Group中的method相比较，复杂度为 M*c, c << M
4.实验评估
第三方Android应用市场（apk数据来源）：
2 American markets (Pandaapp and Slideme)
2 Chinese markets (Anzhi and Dangle)
1 European market (Opera).
结果：
误报率：<1%
漏报率：0.4—0.7%
同时具有较高的效率，一个小时可以处理150145个APP,每个method只需同组内小于8个其他的method进行比较。
如果有新的APP与数据库中已有数据比较，效率也是很快。。
limitations
(1)不能检测到Type 4的app clone，但实际上没有在应用市场中找到第四种类型的app
(2)在较小的CFG中添加一个节点会很大的改变centroid，但实际上小CFG只占2.3%。
(3)app clone通过值克隆一小部分method而逃逸检测
(4)若app clone的opcode比原始app多，则可能不会检测到。