基于多类特征的Android 应用重打包检测方法
2017-04-22邹慕蓉胡勇
邹慕蓉，胡勇
（四川大学电子信息学院，成都 610064）
基于多类特征的Android 应用重打包检测方法
邹慕蓉，胡勇
（四川大学电子信息学院，成都 610064）
针对Android系统的应用重打包安全威胁，提出一种基于多类特征的Android应用重打包检测方法，结合简化的图特征向量检测算法与图片相似度算法，在保证应用相似度计算准确率的基础上提高计算效率。通过原型系统的实验，表明该系统能抵抗多种代码混淆带来的影响，准确地识别重打包应用程序,同时在运算效率上优于原重打包检测方案。
Android应用；重打包；图特征向量；感知哈希；抗混淆
0 引言
近年来，随着移动智能设备的广泛普及，移动应用的数目迅速增长。据著名互联网流量监测机构Net Applications[1]发布的移动操作系统市场份额占比显示，Android系统市场份额高达68.54%，比排名第二的iOS高出近43个百分点。与此同时，有别于iOS系统应用来源的单一性，Android平台用户不仅可从官方应用市场下载和安装应用，如在手机的设置中勾选了“允许安装未知来源的应用程序”选项，还可以安装任意来源的应用程序。
Android平台的开放性吸引了众多开发者的加入，手机的功能也不断地被丰富和扩充。Android应用程序安装包（APK）是包含可执行DEX文件、签名文件、资源文件等文件的压缩归档文件。使用反编译工具如Apktool，可以将其解析出类似于汇编的语言的Smali语言文件，甚至能反编译为与源码类似的Java文件。APK拆包与重组的便捷性降低了应用重打包的技术门槛，使得利用重打包篡改应用程序很容易实现。
应用重打包是指非授权开发者通过反编译工具将APK反编译后，对其代码进行注入或修改，对资源文件进行删改，再对修改后的目录再次进行签名和打包，生成篡改后APK文件的操作。
重打包应用与原应用实现的关键功能大都一致，而重打包后对应用进行重新签名，会使得二者的签名信息有所不同。由于一般用户无法对重打包操作的可靠性和安全性进行鉴别，用户在不知情的情况下可能安装这些被篡改的应用。如果这种篡改是恶意的，一方面会对用户的安全和隐私造成威胁，另一方面侵犯了应用开发者的知识产权利益。因此，针对应用的重打包检测是很有必要的。应用重打包检测相关的研究成果按照特征点的选取可分为以下三类：
（1）通过应用代码特征进行相似度计算。文献[2]提出DroidMOSS，通过反编译应用的DEX文件到Dalvik字节码，对其中的操作码序列进行模糊散列，生成应用指纹特征，根据特征间的编辑距离来计算应用的相似程度。文献[3]提出一种基于图特征向量的检测方法，依据解析应用中的类依赖关系建立基于图的特征向量模型，再比较降维后的向量相似程度来实现检测。
（2）通过应用资源文件的特征进行相似度计算。文献[4]提出ImageStruct，通过计算不同应用多个图片间的相似程度来得到应用的相似程度。文献[5]提出DroidEagle，其中的RepoEagle模块通过对应用的布局文件建立树状结构，由树间的编辑距离来实现检测。
（3）通过多类特征进行相似度计算。文献[6]提出一种通过提取函数调用关系图的节点数、边数、平均度、网络直径等图属性特征，结合音频、图片文件特征实现相似性检测的方法。
单独提取某一类型的特征信息的相似度计算方法存在一定的局限性。仅针对代码特征进行相似度计算，对于不能反编译为Smali文件的APK或加壳的APK就完全不起作用。而仅提取APK资源文件特征进行相似度计算，虽然能很好地抵抗代码混淆，但对于加载了同样广告库的应用，其资源文件可能会出现很大程度的相似，造成误判。反之，对于特征信息的过多提取，则会在准确率提高的同时降低相似度判别的效率。因此需要在保证应用相似度计算准确率的基础上，尽量提高计算效率。
本文提出一种基于多类特征的Android应用重打包检测方法，结合简化的基于代码特征的图特征向量检测算法与资源图片文件相似度算法，在保证应用相似度计算准确率的基础上提高计算效率。同时加入了应用签名信息的比较，提高系统的准确性。图1为系统流程图。
图1 系统流程
1 特征提取
本文提取三类特征作为应用相似度的判别依据：由反编译解析出的应用程序类依赖关系生成的图特征向量序列、使用感知哈希生成的图片的指纹序列，以及应用签名信息串。特征提取部分流程图如图2所示。
图2 特征提取流程
1.1 图片特征提取
在相似图片搜索领域采用较多的算法包括：尺度不变特征变换匹配算法（SIFT）、平均哈希算法、感知哈希算法等。其中的感知哈希算法是一类比较哈希方法的统称，它使用离散余弦变换来获取图片的低频成分，相对于平均哈希算法受均值的影响更小。许多在线的“以图搜图”的引擎（如Google和Tineye）都采用该算法进行图像匹配。因此本文选择感知哈希算法来实现图片文件特征的提取。
提取过程中，对APK文件“res/”目录下的所有图片文件，通过感知哈希算法进行计算，每幅图片对应一个散列值，所有图片散列值的集合作为应用的图片特征。
1.2 代码特征提取
常见的Android应用的相似度计算方法往往将应用相似度转换为抽象语法树的相似度或图的相似度来计算，例如生成程序依赖图PDG或控制流图CFG、生成抽象语法树，或对代码分片执行模糊哈希算法。模糊哈希算法在分片大小不恰当时，简单的语句删改都会造成相似度误判。而将文件相似度转化为图或语法树的相似度，其保留的信息量越大，方法的准确性越高，而执行效率也随之降低。
类依赖图是指通过解析反编译后的Android应用程序，由类间的互调关系生成的有向图G=
使用Graphviz软件分别对某应用混淆前后的类依赖关系进行解析并绘图，截取其中相应的部分，可得混淆前的图3（a）和混淆后的图3（b），从中可以看出，混淆操作虽然改变了类的名称，但类之间的调用关系并未发生变化，即混淆前后生成的图仅顶点名称不同，顶点间的映射关系并未发生改变。因此通过类依赖图来构建代码特征是具备一定程度的抗混淆特性的。
图特征向量算法是指由类依赖图中的类依赖关系生成转移概率矩阵，对转移概率矩阵进行拉普拉斯变换，将输出的矩阵映射为一个多维特征向量进行Android应用相似性分析的算法。转移概率的计算方法如公式（1）所示，其中A、B表示有向图G中的两个顶点，A与B的out和in属性分别表示顶点出度（由该顶点指向其他顶点的边数）和入度（由其他顶点指向该顶点的边数）。计算出有向图G中所有节点的转移概率后，就构成了图的转移概率矩阵，随后按行依次取出其中的非零值，就构成了该图的特征向量。
图3
由于算法的输出结果是一个包含浮点数的序列，做比较的两个序列长度越长，后续进行相似度计算的耗时越久。为了提升计算效率，本文使用了简化后的图特征向量检测算法，由原算法中提取应用所有包中的类依赖关系，简化为仅对APK文件包名对应路径下的类依赖关系进行解析，减少了输出序列的长度。同时在实验中观察到原算法中对转移概率矩阵做拉普拉斯变换这一步骤对算法性能提升效果不明显，省略该步骤。代码特征提取流程如图4所示。
图4 代码特征提取流程
APK文件的包名通过查询反编译后的清单文件AndroidManifest.xml得到，该文件中存放了应用的包名、版本、申请的权限、组件信息等描述信息。一般情况下包名对应的应用路径下存放了应用组件相关文件，调用的其他类往往单独存放在其它包中。解析该路径下所有类间的类依赖关系，可以减少解析类的数目，同时保留了相对关键的一些类间的类依赖关系。如解析某应用得到的类名为“com.grumoon.volleydemo”，则解析反编译得到的smali文件的路径为“/smali/com/grumoon/volleydemo/”，需要解析的类数目由原来的97缩减至35。
1.3 应用签名信息提取
同一应用的不同版本，其代码部分的特征及资源文件的特征极为相似，但与重打包应用的区别是，二者的签名信息是一致的。若不对不同版本加以判断，会误判为重打包应用。因此，本文引入对应用签名信息的提取，降低误判率。在对应用相似度进行比较后，进一步对二者的应用签名信息进行比对。本文假设应用原开发者的签名是私有的，不能被别人获取到。因此同一应用的不同版本尽管相似度很高，由于签名信息一致，并不会被判定为重打包应用。APK的“META-INF/”目录下包含完整的开发者证书，提供开发者相关信息以及公开密钥的指纹信息，其中描述证书所有者的字符串作为签名信息的比对依据。
2 相似度计算
相似度计算部分包括代码特征相似度计算和图片特征相似度计算，其产生的结果分别用sim（code）和sim（pic）表示，最终给出的相似度根据这两部分结果加权得到，用sim（APK）表示。具体的计算公式如式（2）所示，其中，ra和rb分别表示两项特征被赋予的权值，满足ra+rb=1。对实验中计算出的特征值进行Logistic回归分析，得到ra=0.34，rb=0.66，阈值选取为0.45。
2.1 代码特征相似度计算
代码特征提取得到一个图特征向量序列，实质是一个包含浮点型数字的数组，不同应用间的代码特征相似度最终由数组间的相似度表示。常用的相似度比较算法包括：余弦相似度算法、编辑距离算法、最长公共子串算法等，每种算法在不同情况下的适用性和效率都有所不同。
由于重打包应用程序的主要功能与原应用程序相似，其内部的功能代码可能会有所删改，但大体结构不变，其连续性可能会由于插入的代码而改变。因此本文选择最长公共子序列算法来计算两个图特征向量序列间的相同特征数。图特征向量序列由代码特征提取模块生成，其实质是一个包含浮点数的序列。
最长公共子序列（LCS）算法在保持图特征向量的顺序特性的同时，提取了两个向量序列的公共特征值，使用动态规划的思想实现的算法时间复杂度最优可至O（nlogn）。本文仅需要通过该算法得到两个向量序列公共部分的长度来计算相似度，而不需要回溯数组得到公共部分的内容，进一步提高计算效率。
代码特征相似度计算公式如公式（3）所示，其中|LCS（X，Y）|表示通过LCS算法得到的序列X与Y间最长公共子序列长度，max（|X|，|Y|）表示两序列长度中的较大值。使用较大的序列长度作为分母使得计算结果与比较次序无关，并且不会因为某一方序列长度过小而产生误报。
2.2 图片特征相似度计算
本文采用图片指纹间的汉明距离作为图片特征相似度，然后通过计算杰卡德相似系数得到两个应用的图片特征序列的相似程度。每幅图生成的图片指纹长度为16位，一般情况下认为图片指纹间的汉明距离小于5位，就认为两幅图像是相似的，也就近似地认为两幅图是相同的。实际计算中进行比较的两组指纹序列的长度往往是不一样的，因此使用公式（4）所示的杰卡德相似系数来计算最终两集合的相似程度。其中cnt表示近似相等的图片数目，m和n分别表示做比较的两图片特征序列的长度。
3 实验分析
根据本文提出的重打包检测方法实现了一个原型系统，同时实现了一个使用未经简化的图特征向量提取算法进行检测的系统（下文简称为Full系统）与之对比。通过抗混淆能力检测和效率检测两项实验来验证原型系统的抗混淆能力与执行效率。
3.1 实验环境
实验环境为Win7 64位操作系统，4G内存，使用Apktool v2.0.0-RC4进行应用的反编译，使用Python 2.7版本进行代码编写。
3.2 抗混淆能力检测
选取三种Android混淆工具ProGuard、APKProtect和Allatori分别对Github上较热门的15个Android开源应用程序进行混淆，通过检测原应用与混淆后的应用相似度，来验证原型系统的抗代码混淆效果。实验结果如表1所示，计算出的相似度均高于阈值，验证了原型系统的抗混淆能力。
表1 抗混淆能力检测
3.3 执行效率检测
使用原型系统与Full系统对来自Android恶意代码应用收集平台Contagiodump的三组应用分别进行相似度检测，每组中的应用数分别为55、78和105，记录计算过程中的平均耗时情况（包括反编译时间），如表2所示。从中可以看出，原型系统在不同组应用的相似度计算中具备更高的运算效率。
表2 执行效率检测
4 结语
通过对应用相似度计算的有效性和可靠性进行权衡，本文提出一种基于多类特征的Android应用重打包检测方法，结合简化的图特征向量检测算法与图片相似度算法，在保证应用相似度计算准确率的基础上提高计算效率。使用该方法实现原型系统进行实验，实验结果表明该系统能抵抗多种代码混淆带来的影响，准确地识别重打包应用程序。同时，在运算效率上优于原重打包检测方案，是一种有效的重打包检测方法。
本文提出的检测方法在执行过程中还存在一些不足之处，如不能正常解析使用了加壳或加密技术的应用，同时代码部分的简化方式不够智能，仅简单地解析了APK包名对应路径下所有类间的依赖关系。在后续的工作中会尽力完善这些不足之处，在尽可能细化算法粒度的同时提高算法的效率和可用性。
[1]NetMarketShare,Mobile/Tablet Top Operating System Share Trend[EB/OL].http://www.netmarketshare.com/operating-system-marketshare.aspx?qprid=8&qpcustomd=1,2016.
[2]Zhou W,Zhou Y,Grace M,et al.Fast,Scalable Detection of"Piggybacked"Mobile Applications[C].ACM Conference on Data and Application Security and Privacy，2013:185-196.
[3]颜克文.基于图特征向量的Android程序相似性检测算法研究[D].湘潭大学,2014.
[4]Jiao S,Cheng Y,Ying L,et al.A Rapid and Scalable Method for Android Application Repackaging Detection[M].Information Security Practice and Experience.Springer International Publishing,2015:349-364.5
[5]Sun M,Li M,Lui J C S.DroidEagle:Seamless Detection of Visually Similar Android Apps[C]，2015:1-12.
[6]王兆国,李城龙,关毅,等.抗混淆的Android应用相似性检测方法[J].华中科技大学学报（自然科学版）,2016（3）:60-64.
A Repackaging Detection Method of Android Applications Based on Multiple Features
ZOU Mu-rong，HU Yong
（College of Electonics and Information Engineering,Sichuan University,Chengdu 610064）
According to the security threats from Android repackage application,proposes a repackaging detection method of android applications based on multiple features,which combines the graph eigenvector algorithm for code detection and perceptual hash algorithm for image detection.This method improves the calculation efficiency on the basis of ensuring the similarity calculation accuracy.The experiment result of the prototype system indicates that this method can withstand the effects of a variety of code confusion,accurately identify the repackaged Android application.The similarity detection computation efficiency is better than the original method using Graph Eigenvector.
Android Application;Repackage;Graph Eigenvector;Perceptual Hash;Anti Obsfucation
1007-1423（2017）07-0050-04
10.3969/j.issn.1007-1423.2017.07.013
邹慕蓉（1992-），女，陕西宝鸡人，在读研究生，研究方向为Android安全
2017-01-04
2017-03-01
胡勇（1973-），男，四川成都人，博士，副教授，研究方向为信息安全
