杨佳，付才，韩兰胜，鲁宏伟，刘京亮

（1.华中科技大学计算机学院，湖北 武汉 430074；2.北京航空精密机械研究所，北京 100876)

1 引言

近年来，随着移动智能终端设备的迅速发展，Android 应用占据了移动应用市场的主要份额。据统计，2017 年已有超过15.5 亿部智能手机被使用，其中超过80%的手机搭载了Android 系统。海量规模的各类移动应用（App）投放在多个第三方应用市场供用户下载，例如谷歌应用市场中Android 应用数量已经接近140 万。这些移动应用已在办公、娱乐等各个方面深入人们的生活，成为不可或缺的一部分。

然而，由于Android 系统的开放性和Android 应用的易被破解性，许多非法开发者利用克隆技术或者反编译工具仿造出大量的克隆App。目前，应用重打包已经成为恶意软件传播的主要途径之一。目前，有超过85%的安卓应用存在重打包行为，这不仅侵害了原开发者的知识版权和利益，也对移动用户的安全和隐私造成危害。此外，一些攻击者会修改原始App中的函数逻辑，如去除App 中的支付函数、修改原App 中的广告库，甚至插入各种各样的恶意代码，再用一个新的签名重新打包这些恶意App。克隆App在第三方应用市场中大量地被下载使用，严重干扰了应用市场的正常环境。为保护合法用户和原创开发者的正当权益，如何实现高效准确的App 克隆检测是当前移动应用市场面临的技术挑战。

由于App 市场的规模庞大，App 的数量不断快速增长，仅基于本地的计算资源进行App 克隆检测会因为硬件配置较低而出现计算能力有限、电源功耗过高等问题，本地检测技术已不能满足百万数量级的App 分析需求。移动互联网中的云计算、大数据及虚拟化技术为解决大规模App 克隆检测问题提供了技术支撑。本文基于云环境提出了一种高效App 克隆检测方法，构建了检测原型系统，提高了App 克隆检测的效率，能有效应对大规模App 克隆检测挑战。

许多研究者提出了多种App 克隆检测技术，主要有以下三类：基于简单散列特征提取的技术[1]、基于静态语义特征提取的技术[2-6]、更加复杂有效的基于Android 应用UI 结构特征的提取技术[7-10]。第三类检测技术中基于UI 结构特征的检测方法主要分析用户接口之间的使用相似度进而判断App是否克隆。目前，Androguard[11]和FSquaDRA[12]是用于App 克隆检测的主要公用工具。Androguard 能够在Dalvik 字节码层进行比较，FSquaDRA 能够基于源文件进行相似度分析。然而这些研究还存在以下问题：基于散列值和某一特定静态语义分析方案的适应性还需增强，例如，在克隆中使用代码混淆可避免被基于静态语义特征的方法检测出来；而UI 结构特征提取方案需要提取整个App 的UI 调用结构，同时需要复杂的图匹配计算来比较App 相似度，因此对于小结构UI 图的App 难以达到较好的检测效果。

本文主要从以下3 个方面来讨论目前的工作。

1)二进制层函数克隆检测方案

在二进制层的克隆检测方案中，一种通用的方法是使用基于函数执行序列的路径进行代码相似度检测。这种方法能够检测控制流程图（CFG,control flow graph）的变化，但是不能准确地检测在不同平台或者代码混淆下的函数克隆。另一种方法是利用代码的静态特征进行App 克隆检测。但当恶意开发者对这些静态特征进行修改的时候，例如修改字段变量的常数或API Call 的调用序列等，这种方法的正确率就无法得到保障。Rendezvous[13]在二进制代码上使用代码搜索的办法进行克隆检测，这种方法有2 个限制：首先，需要代码的ngram 特征来提高准确率；其次，需要将整个CFG 分为几个子图来处理。Pewny 等[14]提出了一种基于已知的漏洞签名的搜索方案，该方案计算二进制代码块的语义散列来进行函数的克隆比较，然而这种方案并不高效。Feng 等[15]提出了基于控制流程图的恶意代码检测方案，但是需要复杂的图匹配过程。

2)App 克隆检测

传统方法检测恶意App 主要通过权重很大的静态和动态特征来进行黑白名单检测，但是不能检测未知的恶意代码，如果之前并没有收录这种恶意代码，则无法进行检测。例如，Zhou[16]利用软件权限、API 调用顺序等静态特征进行检测，但是仅利用这些静态特征进行检测会导致较低的准确率。David[17]能够自动划分一个函数调用图的社区结构，这些划分的社区结构能够用于新的恶意代码检测。Arp 等[18]提出一种新的轻量级的检测方案，这种方案从安卓应用中提取八类特征，然后对这些特征用SVM 进行分类实现检测[3]。

3)动态检测

该检测方式需要App 在一个虚拟的环境下运行，从动态特征中提取信息。Andrubis[19]即是动态地进行检测，但是耗时过长。Enck[20]提出了一个系统Taintdroid，通过追踪敏感信息的流动来进行克隆行为的检测，这种方法同样非常耗时，在效率上有所欠缺，无法应对大规模的检测。

实现云环境下高效的函数层App 克隆检测方案存在以下一些困难和挑战。

1)相比面向源代码的克隆分析，移动应用App中基于可执行字节码的克隆分析更为复杂。移动应用的源码并不能轻易获取，同时，Android 应用中大量使用的代码混淆技术也给重打包检测增加了难度。

2)海量的应用规模为克隆检测效率提出了更高的要求。随着各类Android 应用的普及，App应用数量呈现出飞速增长的趋势，通过App 的UI 调用图或者动态分析等方法都无法应对大规模级别的克隆分析。

3)移动应用中第三方库函数的大量使用干扰了克隆检测的效率与准确率。只有App 自身核心函数代码来源于其他应用才能认定是克隆App，之前的工作仅通过黑白名单过滤第三方库函数，在正确性和效率方面存在很大的问题。

4)系统需要具备良好的可扩展性。在有新应用添加到云端时，既要快速分析判断，又要将新应用特征快速融合到整体克隆特征库中，实现增量特征更新。如果需要和之前的App 克隆检测数据库同时学习与提炼，其应用效率会受到影响。

针对上述问题，本文面向云环境提出了一种基于函数编码的App 克隆检测方法，并实现了该方法的原型系统，称为Pentagon。该方法在App字节码层面对函数的控制流程图与基本代码块进行特征编码，从函数层面比较2 个App 之间的相似度。所有的特征提取过程和检测算法均在云环境下构建和实施。本文主要贡献如下。

1)设计了根据App 字节码提取函数基本代码块特征的方法。每个执行函数由多个基本代码块通过跳转连接组成，首先针对每个执行函数提取原始CFG，然后提取每个CFG 图形节点的特征，即基本代码块特征，这些特征值表示了该代码块的静态统计特征以及该代码在CFG 中调用跳转结构特征。

2)提出了融合代码块特征和函数CFG 特征的编码算法。该编码算法将App 中任一函数编码成几个关键值的特征向量，提取的函数CFG 有向图特征空间被压缩成低维的数字特征空间；然后，基于该特征空间使用高效的聚类方法过滤第三方库函数；同时，证明了算法中函数特征编码的单调性，一个特征编码仅代表一个函数。

3)解决了规模化App 增量更新的问题。Pentagon对App 中每个函数进行独立编码，对于新增加的应用程序，Pentagon 可单独编码该App 中所有函数特征，然后在数据库中对App 进行搜索比较，避免了同时整体提炼所有App 特征值的复杂过程。

4)从第三方应用市场收集了超过152 789个应用程序，对原型系统进行了大规模的实验验证。实验结果表明本文方法的预处理效率和克隆检测效率是目前典型App 克隆方案的8～100 倍。在1 000 个函数中一个克隆函数的平均搜索时间为7.9 ×10-9s。同时，App 克隆检测的正确率达到97.6%。

2 问题描述和方案总览

本节首先说明设计移动应用App 克隆检测系统需要解决的问题，然后介绍本文提出的面向云环境下的App 克隆检测方案。

2.1 问题描述

本文需要解决的关键问题是在云环境下如何快速判断一个未知App 是否为克隆App，并判断克隆App 中具体哪些函数是相似的及其相似度大小。判断App 是否克隆，需要满足以下条件。1)不同的开发源有相同的App 功能函数。通过查看 Android 应用的签名密钥和App 中所有函数的特征来判断该App 是否为克隆。如果这些不同签名的App具有相似或相同的核心函数特征，则说明是克隆App。2)相似的函数不能包括第三方库函数。App的代码中一般包含了许多相同的第三方库函数，这些库函数不能作为判断克隆的依据，克隆检测方案需要过滤这些第三方库函数。

检测App 是否克隆的基本步骤如下。从非结构化的App 字节码中提取CFG 特征，然后将每个含有基本代码块特征信息的CFG编码为一个低维数字特征，该特征向量表示App 中的函数特征。通过不同App中所有的函数特征匹配来实现App 函数层的克隆检测。App 克隆检测问题数学描述如下。

问题1如何设计一个函数f计算每个App 函数的编码特征。通过App 中所有函数的编码特征获得App 的矩阵表示，即其中，表示整个函数的编码特征向量，j=1,2,…,m，也是矩阵A中第j列列向量；m表示App中函数的个数。在函数f中，表示CFG 中基本代码块i的特征，|v|表示一个CFG 中代码块的个数。

问题2如何设计一个有效的过滤函数F以去除App 中第三方库函数。这是提高App 克隆检测正确率的重点问题，由于App 克隆检测需要比较所有的代码块特征，如果不同App 中有大量相同的第三方库函数，一方面会增加克隆检测时间，另一方面会干扰克隆检测的准确率，相同的第三方库函数不能作为克隆的检测依据。

2.2 方案总览

本节主要介绍函数层的特征编码方案，并说明本文方案如何解决第2.1 节中提出的问题。本文的App 克隆检测方案的基本思想是：首先，提取App反编译smali 文件中每个函数的CFG；然后，针对每个CFG 中的每个基本代码块提取关键特征值，并根据编码算法将所有的基本代码块特征和CFG 跳转结构编码为低维的向量表示，将该向量存储到App 特征数据库中；最后，用余弦相似度计算2 个函数特征之间的向量距离，通过该距离判断App 是否克隆。

如图1 所示，Pentagon 有以下3 个检测步骤。1)CFG 提取云环境，包括安卓市场下载App、反编译和CFG 提取过程。2）函数特征生成及过滤云环境，主要为Pentagon 编码过程，Pentagon 编码的函数特征用来进行第三方库函数过滤。3）云环境下App 克隆检测，主要为特征向量相似度比较。每一个步骤都在云环境下实现，具体实现过程为：首先编写自动下载App 的爬虫引擎，将下载的App 存储到对应的服务区中；然后通过并发方式对每个下载的App 进行CFG 提取以及函数特征编码；结合云环境下内存流计算方式并行地处理这些App，获得App 中每个函数的低维数据表示，并将编码特征存储在云端的非结构化数据库中。

上述检测步骤中，第一步，主要提取函数CFG中的基本代码块属性。在Pentagon 中，CFG 的每一个节点提取5 个属性值，这5 个属性值分别表示字节码特征和该基本代码块在CFG 中的拓扑结构。第二步，根据CFG 的拓扑结构，设计了一种基于图形嵌入的编码算法，将CFG 中的所有节点特征编码为一个单调的低维数字特征，并通过反证法证明其单调性；使用函数编码特征进一步过滤第三方库函数，在过滤之前，先删除每个App 中重复的函数，然后通过聚类算法删除第三方库函数。第三步，给定一个待检测的App，使用局部敏感散列（LSH,local sensitive hash）搜索算法实现高效的函数特征匹配。由于函数特征是独立编码，不需要更新之前的App函数特征库，只需在数据库中增加新的App 特征。

3 Pentagon 函数编码

本节重点描述Pentagon 函数特征编码算法，该算法将App 中每个函数编码为一个一维向量，该一维向量能够单调表示App 中的函数特征。

3.1 原始CFG 提取

Android 应用一般是由开发者将所有的源码和资源打包成APK (Android package)文件，然后发布供用户下载。APK 文件是一个压缩包，解压缩之后的文件夹内主要包含该应用的Dalvik 字节码、UI资源、UI 布局、配置文件、签名信息等。其中，Dalvik 字节码是App 的可执行函数文件。Android应用程序通常用Java 语言实现，然后被编译成Dalvik 字节码。

APK 文件本质上是一个压缩文件。反编译的classes.dex 文件是App 主要的代码文件，源代码编译成class 后，转成jar，再压缩成dex 文件。dex 文件是可以直接在Android 虚拟机上运行的文件。smali语言是davlik 的寄存器语言，语法上和汇编语言相似，一个smali 文件中包含了很多函数，每个函数中包含了一系列的操作码及该操作码对应的寄存器和处理数据。本方案首先对smali 文件提取CFG。CFG 中的每个节点代表函数中的一个代码块。CFG中跳转结构开始于一个代码块，结束于另一个代码块，有向边表示控制流程图的跳转结构。

3.2 函数特征编码

编码函数特征的主要思想是从App 的smali 文件的字节码中提取一个带有代码块特征的CFG，并将该特征CFG 投影编码为一个包含5 个属性值的低维向量特征。与函数代码块的其他特征（如I/O特征和其他语义特征[16]）不同，CFG 能更加全面地匹配函数的执行流程特征。CFG 中的边表示基本代码块之间的调用关系，CFG 中的每个代码块包含了一系列的操作码和数据。本文基于图形嵌入的思想来编码带有代码块信息的 CFG 结构。Pentagon 融合了CFG 拓扑结构和基本代码块的静态特征综合完成函数特征编码。图2 表示CFG 的抽象图，一个圆圈表示一个基本代码块，也是CFG图中的一个节点，圆圈中的字母表示该基本代码块的序号，圆圈旁边每一行表示一行dex 汇编代码，其中包含了操作码及使用的寄存器（v0～v4表示寄存器），图中的箭头表示2 个代码块跳转的一条有向边。

图1 Pentagon 检测步骤

图2 CFG 抽象图

定义CFG 为一个有向图(V,E)，其中，V是一个函数的代码块集合，E⊆V×V是一系列代码块之间的连接边。每个基本代码块的特征表示为一个一维向量。其中，si为代码块i在CFGj中的使用序列，pi为代码块i的操作码的数目，ai为调用不同的API Call 的个数，oi为代码块i的出度，l i为代码块的循环结构的个数，并定义代码块i有唯一的权重ωi。根据提出的算法，使用权重ωi编码所有的节点特征。具体的计算过程如式(1)所示。

其中，e(i,k)表示Gj中节点i到节点j之间的一条边|V|表示节点数。计算结果是每个函数的特征，其中，c js、cjp、cja表示代码块的统计特征，cjo、cjl表示CFG 拓扑结构的跳转结构。

3.3 权重参数生成

Pentagon 的关键是计算每个节点i的权重ωi，ωi用于函数特征的融合编码。为了得到每个节点的权重，首先定义带有代码块特征的CFG 一级跳转结构和全局跳转结构[21-22]。

1)一级跳转结构。一级跳转结构L描述CFG中任意2 个节点之间的跳转情况。

如果节点i和k之间至少有一条有向边，则e(i,k)=1；否则e(i,k)=0。一级跳转结构对CFG 编码非常重要，表示在函数代码中CFG 结构代码块的一级继承和调用情况。

2)全局跳转结构。全局跳转结构N描述了节点与CFG 中的其他节点之间的一级跳转情况。

其中，Nu表示节点u和CFG 图中其他节点的一级跳转，节点的总数为|V|。比较Nu和Nv之间的相似度，获得节点u与节点v之间的全局跳转N(u,v)。直观来说，全局跳转结构表示如果2 个节点连接了更多相同的节点，则它们之间的联系会更加紧密，这些设想在很多领域都被合理证明。

在CFG 的有向边e(i,k)中，定义从节点i到节点k之间的跳转概率为

其中，

经验概率表示节点i和k在图CFG 的实际跳转概率。为了计算权重参数，本文将跳转概率分布和经验概率分布之间的距离函数作为目标函数，通过计算2 个概率之间 KL（Kullback-Leibler）距离，得到损失函数O1。

全局跳转结构定义了代码块和CFG 中其他节点的连接情况，以及该代码块在CFG 中的上下文。本文定义全局跳转结构的连接概率为

其中，|V| 表示节点的个数。为了保留图CFG 中的全局跳转结构，需要上下文条件概率分布接近于经验概率分布，上下文经验概率为

其中，oi表示节点i的出度。同样根据KL 距离定义以下的损失函数。

Pentagon 在编码函数之前，需要先计算每个节点的权重ωi。根据一级跳转结构和全局跳转结构获得的损失函数O1和O2，对CFG 中的所有边进行取样，然后对目标函数进行求导，如式(3)所示。

由于损失函数是凸函数[19]，当式(3)中导数为0时，可得到损失函数的最小值。令其一阶导数趋近于0，求得所有的权重参数ωi。然后，使用权重序列Ω={ω1,ω2,…,ω n}编码整个CFG 获得函数的特征。

3.4 Pentagon 的单调性

由Ω编码 CFG 结构计算的函数特征为。编码过程需要确保每个特征向量能唯一表示一个函数特征。

函数特征由Ω组成的一系列的线性等式函数计算而得。由于不同的CFG 有不同的跳转结构，所以当Ω不同时，即有不同的线性等式，可以使用反证法来证明单调性。假设不同的CFG 有相同的特征，即对于CGFi和CFGj考虑到节点个数不同其Ω也不同，本文使用反证法，假设2 个CFG的节点个数相同，根据和式(1)，得到式(4)。

其中，n表示CFGi和CFGj的节点的个数，ωik表示CFGi中的节点k的权重。由于式(2)中，sigmoid 是单调函数，并且当2 个CFG 的结构不同时，这2个CFG 的实际边分布概率也不相同，即pi≠pj，p是单调函数，则对任意k，CFGi和CFGj中每个节点的权重ωik≠ωjk。当节点的数目相同时，节点的序列集是相同的，但是每一对有相同的调用序列的函数对都有不同的权重参数序列，并且由于CFG的结构不同，即oik≠ojk且lik≠ljk，因此，式(4)不成立。

通过上述反证法，证明了不同的CFG 能编码为不同的特征，Pentagon 编码的函数是单调的。证毕。

3.5 CFG 编码举例

根据图2 提取的原始CFG，以下用i，j表示该CFG 中基本代码块的编号，首先根据一级跳转结构和全局跳转结构计算权重参数，具体的计算过程如下。

考虑到kω iωj≫1，令

并且CFG 结构中最后一个出口节点的权重ω5=0，然后对导数两边同时取对数，有以下的等式。

最后，得到权重参数为Ω=[1,2,3,1,0]，计算函数的特征如下

3.6 基于函数编码特征的App 表示

一个完整App的smali文件中包含了很多函数，每个函数被编码成一维向量特征根据App 中所有函数的编码特征，获取每个App 的矩阵表示A，对于不同大小的App，所包含函数的个数m不同，由于App 中会有重复函数，重复函数的字符串特征和CFG 拓扑结构相同，重复的函数编码表现为矩阵A中有相同的列。

大量的重复函数需要重复比对，降低了效率和正确率。根据统计调研，App 所包含的函数个数集中在2 000～20 000，实验的预处理过程首先要删除重复的函数。使用python 库的numpy 包中的“unique()"函数来删除每个App 矩阵中的重复函数。最后App 的矩阵表示为

4 Pentagon 的第三方库函数过滤

App 的代码中一般包含了许多相同的第三方库函数，这些相同函数不能作为克隆依据，克隆检测方案需要过滤这些第三方库函数。本节描述如何根据聚类算法删除第三方库函数。

假设App 数据库足够大，并且第三方库函数在许多App 中都被使用。由于编码之后的函数特征能够单调表示App 中的函数，这些函数特征可用于过滤第三方库函数。为了提高效率和准确度，本文主要通过两大步骤来过滤第三方库函数：第一步根据每个函数特征对应的平均权重参数进行粗粒度过滤；第二步在第一步的基础上，进行严格比对聚类。具体如下。

第一步，统计所有函数中相同ω出现的频率，使带有相同的ω的函数特征聚集在同一类中，第三方库函数会被聚集到一个远远大于其他类别的类中，计算所有不同ω的类中的函数个数，选取其中聚类函数个数在前60%的聚类作为下一步需要比较的对象。第二步，实施严格比对，只有当2 个函数向量特征完全对应相同时，才会重新将这些函数放置到同一类别中，最后将聚类中函数数目较多的一些函数作为第三方库函数，删除每个App 表示矩阵中包含这些第三方库函数的特征，剩下的就是App 核心功能的函数。

5 Pentagon 克隆决策

Pentagon 系统克隆决策由2 个层面的相似度比较功能构成，首先是函数级别的特征相似度比较，其次是App 之间的相似度比较。

5.1 函数特征相似度比较

本系统使用余弦相似度函数进行相似度计算，每个函数特征向量有5 个值。任意2 个函数的特征向量的相似度定义如下

其中，δf表示函数之间差异度阈值。如果2个函数相同，则Sf=1。

根据Pentagon 的函数特征编码过程，如果修改了原始执行代码块中操作码的一小部分，函数特征的编码结果不会更改过多；如果改变某一个代码块中操作码的执行顺序，同样也不会过多地改变函数特征；但如果整个CFG 的跳转结构发生了大量的变化，或者代码块的统计特征改变了很多，对函数特征就会产生相应的影响。

5.2 App 相似度比较

函数层相似度比较用于检测相似的App，但是相似的App 不一定是克隆的App。有以下2 种情况不属于App 克隆。1)2 个App 中，一个App 相比另一个App 有超过某一固定数目的不同的核心函数。2)App 来自相同的作者，仅是不同的版本。

首先，比较2 个App 中函数的个数。Appa和Appa′中包含的函数个数分别为|c|和|c′| 。如果

则判定这2 个App 不是克隆的。其中，σ是任意2个App 的函数数目比例常数，具体根据实验App中的函数数目决定，。

其次，需要通过使用函数层的相似度来比较App 的相似度，具体计算式如下

设定δa是App 相似度阈值，如果S a＞δa，这2个App 定义为克隆App。

6 性能测试与分析

本文实验分为以下3 个主要部分：App 中所有函数CFG 特征提取、函数编码、App 克隆检测。在准备阶段，使用Python 语言编写爬虫程序，该程序自动在6 个Android 市场中下载App。然后，使用Androgurad 工具，将App 文件反编译为smali 文件。根据smali文件提取每个函数的CFG，使用Pentagon对每个函数的CFG 进行特征编码。由于函数间的编码互不影响，Pentagon 能够并行编码每个App 中的函数。在克隆检测部分，比较2 个待检测的App中的所有函数，来确定这2 个App 是否为克隆App以及其中具体的克隆函数。

本文提出的原型系统在Linux 平台实现，并且添加了对OS X 平台的支持。在应用程序预处理模块，使用了3 个开源工具Androguard、Keytool、Dex2jar。Androgurad 工具用来反编译App 产生原始CFG，Keytool 用来提取应用程序的签名信息，Dex2jar 用来将得到的Dalvik 字节码文件反编译成JAR 包。通过编写脚本，将这些工具组合成一个自动化的工具链，可以批量对应用程序进行预处理。Pentagon 特征提取和相似度分析主要用Python 来实现。App 样本库的特征提取后保存在云端文件系统中，所有应用的预处理和特征提取只需要进行一次。

6.1 实验环境与数据来源

本文共进行了2 个阶段的实验，第一阶段是小规模实验，用来验证第三方库函数过滤的效率及本文方法的准确性；第二阶段是大规模实验，用来测试系统的可扩展性和性能。实验数据集包含以下几个数据库：游戏App 数据库、社交App 数据库、娱乐App数据库、金融数据库和其他数据库。在这5 个数据库中共下载了152 789 个应用程序，其中，包含的函数个数为7 490 721 877 个。数据库1 中函数个数为1 596 096 888 个，数据库2 中函数个数为1 142 135 436 个，数据库3 中函数个数为2 151 246 841个，数据库4 中函数个数为1 120 121 321 个，数据库5 中函数个数为1 481 121 391 个。

测试数据包含两部分。一部分是从网络中下载的克隆App，从知名的Android 第三方应用市场以及各种Android 论坛下载有可能是重打包的应用（通过名字、描述来判断，如破解版、修改版等），并且从其他官方市场寻找可能对应的原版应用。另一部分是通过人工重打包应用获取的克隆App。对下载的合法应用进行一些简单修改（更改变量和函数名、添加删除代码和第三方库等），最后将修改后的应用重新签名并且打包。本文选取大小在 50 KB 到 68 MB 之间的App 做实验，这个区间的App 大小基本能代表Android 市场中一般应用程序的大小。在实验之后手动安装和检查应用代码来验证结果的准确性。实验运行在12 核 1.6 GHz 的Linux 服务器，内存为16 GB，硬盘为7 TB，同时开启4 个线程并行处理。

6.2 实验比较

在函数层的克隆分析方面，本文在准确率和效率上对比目前一种较好的基于函数层的App 克隆检测方法：基于CFG 质心运算提取特征的App 克隆检测方案Centroid[23]。在App 克隆检测层面，本文对比当前较好的工作：FSquaDRA[12]、Wukong[24]、Centroid[23]。

6.3 重复函数删除

图3 表示删除重复函数前不同函数数目的App出现的次数，也就是对应于某一具体函数数目App的个数，横坐标表示每个App 中函数的数目，纵坐标表示这一函数数目的App 的出现频率。图4 表示删除重复函数之后不同函数数目的App 出现的次数。可以看出在整个样本中函数的个数下降了17.07%～67.27%。某些App 中，重复函数的个数超过了一半，一些大的App 中包含了更多的重复函数。可以看出，重复函数的个数和App 的大小呈现下降的趋势。一些只含有20 个函数的App 中基本没有重复函数。删除一个含有17 863 个函数的App中的重复函数的平均时间少于1 s。

图3 删除前的函数分布

图4 删除后的函数分布

6.4 第三方库函数过滤

本节实验对数据集中所有App 编码的函数特征进行聚类，用于第三方库函数的过滤，前文说明了不同的权重代表不同的函数，即如果则i和j表示2 个不同的函数，首先，计算所有不同的权重的出现次数。图5 中分别展示了所有ω值对应的所有函数特征的函数数目分布，以及所有ω值对应的不同的函数特征的函数数目的分布。比如，同一个ω可能出现多个函数特征，即有ω的函数特征可能相同也可能不同，因此要区分同一个权重ω对应的函数特征是否相同。图5 横坐标表示出现的所有ω的值，纵坐标表示权重为该ω的函数数目，也就是函数的出现频率。从图中可以看出，出现频率较高的函数数目的权重ω为1～103。然后选择权重ω为1～103对应的函数特征作为第三方库函数的特征。其次，在相同ω的聚类中严格比较函数特征，选取聚类中函数各数较大的类作为第三方库函数，并查看这些函数特征对应的函数名和函数可执行代码。实验显示函数个数在前十的聚类都是安卓支持库，或者广告支持库，这些都不在白名单中。为了删除第三方库函数，在聚类之后需要求得聚类大小的阈值作为下一步聚类的条件。

图5 不同权重中所有的函数和不同的函数的数目分布

本实验使用2 种方法来决定第三方库函数的过滤阈值。首先，下载300 个App，这些App 中包含超过14 个不同的已经确定的第三方库。手动反编译这些App，对相应的函数进行标记，在最后的检测结果中，将出现的频率数目的前29.02%的聚类作为第三方库函数进行过滤。其次，将所有数据库的App 的函数特征进行聚类，选择大小在前29.02%的聚类，手动检测这些类别的函数特征对应的函数，标记为“第三方库函数”“关键代码”或者“不能确定”。根据这些标记判断聚类阈值选择的准确性。

结合上述的2 种方法，最终选择聚类大小的数目为1 610，如果相同函数特征的聚类数目超过了1 610，则判定为第三方库函数。过滤了第三方库函数后，整个App 数据库中的函数数目下降了79.26%。过滤前，有超过63.60%的App 中包含的函数数目在504～5 973 之间，平均每个App 有2 259个函数；过滤后，大部分的App 包含的函数数目为84～1 976，平均每个App 只有627 个函数，超过249、419、203 个函数被过滤。

6.5 准确率

为了表示App 函数检测的正确率，用以下2 个参数来评估实验的好坏，即TPR（true positive rate）和FPR（false positive rate），TPR 是在搜索问题中正确找到克隆函数的比例，FPR 表示找到的克隆匹配是不正确的匹配函数的比例，由TPR 和FPR 的数据组成的曲线为ROC 曲线。从测试数据库随机选取一些检测样本序列q，一个样本实际上有m个克隆函数，在样本函数数目L中，如果认为前F个函数是检测出来的克隆函数，实际上，F个函数中正确匹配的克隆函数有c个，剩下的L-c，就是误报率。设当F越大的时候，TPR 和FPR 都会逐渐变高，这两者的相加值不为1。

由于本文是基于函数层编码的App 克隆检测方法，为了说明本文的准确率，本文将和目前的函数克隆检测的方案进行比较，根据本文提供的测试集，将这些测试集的App 反编译的函数编码成一维特征后作为输入，进行App 克隆搜索检测，同时与本文前面提到的方法进行比较，图6 表示数据库中不同大小的App 对应的数目。图7 表示设置不同的函数向量差异阈值时，对应的失败率大小。从图中可以看出，如果函数差异阈值小于0.005 7，则在函数层的检测失败率为2.4%。如果函数差异阈值大于0.02，则函数的错误率大于20%。函数差异阈值越大，则FPR 越大。阈值需要确保相似的函数有相近的特征，由于Pentagon 编码的特征是单调的，不同的函数之间的特征差异比较大，如果阈值被设置得过大，那么相似的函数就被认为不同的函数，这样就会增加FPR。

图6 不同大小的 App 的总数

Pentagon 系统在当前已经投放市场正在使用的游戏App 中检测发现了2 个克隆样本（为了保护版权，本文不对这2 个App 样本进行具体说明）。这2 个App 在应用市场都显示为具有自主知识产权，但经过本文系统检测发现，它们之间存在克隆关系，并且通过动态调试，也确认了这2 个App 中存在克隆关系，表现出本文方案的实际应用效果。

图7 错误率和阈值之间的关系

图8 展示了实验结果的ROC 曲线，可以看到本文提出的 Pentagon 编码方式的正确率高于Centroid 方案，取App 差异阈值为图7 所示的约为0.01 时候，根据ROC 曲线可以看到检测的准确率可以达到97.6%。由于Pentagon 是单调的，而且对函数的信息编码得更完整，不仅获取了每个代码块的主要统计特征信息，还获取了每个CFG 的结构特征，所以Pentagon 的准确率很高。Centroid 并不是严格单调地表示特征，相比较，本文提出的编码方案能更正确地表示函数的特征。

图8 ROC 曲线

6.6 函数层效率

本文主要从以下3 个方面对系统效率进行比较：CFG 特征的提取效率；Pentagon 编码时间；函数克隆检测时间。这三方面指标表示App 克隆检测的预处理效率。本文有关效率的实验使用全部的152 789 个App，对所有的App 提取特征进行存储，并生成用于App 克隆检测的数据库。

1)CFG 特征提取时间。图9 展示了Pentagon 的CFG提取时间。该特征提取时间不包含App生成CFG时间，因为Pentagon 的编码只需要给CFG 的每个代码块提取5 个值，Centroid 给CFG 的每个代码块提取3 个值，但Centroid 在给CFG 中的基本代码块进行编号的过程稍微复杂一些，所以需要更多的时间，但总体来说，2 种方案的CFG 特征提取时间相差不大。

图9 每个函数的 CFG 中代码块的特征提取时间

2)Pentagon 编码时间。图10 展示了Pentagon生成时间随着函数的数目增加而增长。Pentagon 将APP中一个函数的CFG编码为一个特征，Pentagon是一种线性计算的编码，当函数个数有20 000 个时，即使串行编码，Pentagon 的编码时间仅仅需要1 h。由于Pentagon 的编码方式是解耦合的，因此利用并行的方式可以大大缩短编码时间。

图10 Pentagon 编码时间

3)搜索时间。图11 表示Pentagon 的编码特征用于App 克隆检测出的搜索时间，使用6 个不同度量的样本大小来检测搜索效率，这6 个文本中函数个数c为1 03～108，随机选择1 到10 000 个函数序列作为提交的搜索序列，平均搜索时间随着函数数目的增加持续增长，在1 000 个函数中平均的搜索时间为7.9 ×10-9s。

图11 Pentagon 函数层的克隆搜索检测时间

6.7 App 克隆检测时间

当获取了所有的App 函数特征之后，先按照本文方案删除第三方库函数，每个App 大概需要0.01 s去除重复的函数，删除了第三方库函数之后，检测一个App，需要比较检测的App 和待检测的App之间所有的函数，实验表明，本文方案计算2 个App 之间的相似值需要0.079 s。表1 比较了当前几个比较好的App 克隆检测方案FSquaDRA[5]、Wukong[20]、Centroid[4]和本文方案之间的效率。

表1 App 克隆检测效率

7 结束语

与现有的App 克隆检测方案相比较，本系统具有以下2 个突出的优势。1）在对第三方库函数过滤的方案中，不局限于已有的白名单进行过滤，过滤更为精确有效。现有方案使用白名单通过App 函数中的包名来过滤第三方库函数，在准确性上面存在问题，因为首先不可能完整全面地确定第三方库函数，其次，混淆可能改变包函数的名字，使过滤方案失效，本文发现部分第三方库函数没有具体的名称。 2）本文方案不仅考虑了基本代码块之间的静态特征，同时也考虑了CFG 中代码块之间的跳转结构，现有的App 检测方案主要考虑静态特征，比如提取不同的API Call 调用顺序来检测克隆，这些特征同样会因为混淆而失效。本文的方法采用CFG 函数结构编码，并融合代码块属性特征，相比较其他方案在克隆分析上可靠性更高，实验结果也验证了上述结论。

Pentagon 能够快速应用于云环境下大规模App函数层克隆检测，实现了更准确高效地查找克隆App 以及定位具体克隆函数的目标，对维护移动互联网应用知识产权的良好生态具有积极支撑意义。下一步将在特征自动化提取、第三方函数库优化、跨平台克隆检测等方面做进一步工作，以促进Pentagon 系统应用推广。