一种安卓市场中重包装应用的检测方法

摘要

本发明公开了一种安卓市场中重包装应用的检测方法，该方法根据各个安卓应用的dex文件计算出所使用字符串的长度，将此作为区分不同应用的特征码，通过计算不同应用的特征码之间的编辑距离得到不同安卓应用之间的相似度，并与给定阈值进行比较，从而确定是否为重包装应用。本发明可以作为检测安卓恶意软件的一种有效辅助手段。

权利要求

1.一种安卓市场中重包装应用的检测方法，其特征在于：包括以下步骤：(1)从各个安卓应用的dex文件中提取特征码；所述特征码为dex文件中所有字符串的长度按顺序组成；

(2)计算各个安卓应用的特征码之间的编辑距离；

(3)根据所述编辑距离计算各个安卓应用之间的相似度，并与给定阈值进行比较，从而确定是否为重包装应用；

所述dex文件中的字符串长度的计算方法为：在dex文件中找到字符串的起始偏移地址，然后读取不同字符串的地址，将两字符串的地址相减从而计算出字符串的长度；

所述编辑距离的计算采用如下的动态规划算法：设字符串为A和B，用一个矩阵M来表示A与B的编辑距离，其中Mij表示的是字符串A的前i个字符变成字符串B的前j个字符所需的最少编辑操作次数，算法如下：

1)分别计算字符串A和字符串B的长度，记为length1和length2；

2)判断length1和length2是否为0，若有一个为0，则返回另一个字符串的长度；若两个长度都为0，则返回0；若两者都不为0，则构建一个大小为(length1+1)*(length2+1)的矩阵M；M的行和列的编号均从0开始；

3)将矩阵M的第一行和第一列，分别进行初值为0步长为1的递增编号；

4)从M[1,1]开始，按照从左到右从上到下的顺序遍历整个矩阵，遍历过程中用变量i和j分别控制行和列的下标，同时A[i]和B[j]分别表示字符串A和字符串B的对应字符；

5)计算edit变量值，如果A[i]＝B[j]，则edit＝0，否则edit＝1；

6)计算M[i,j]＝min(M[i-1,j]+1,M[i,j-1]+1,M[i-1,j-1]+edit)；

7)重复5)和6)的操作，直到遍历到矩阵末尾，M[length1，length2]即为两字符串之间的编辑距离；

所述相似度的计算公式如下：

公式(1)中distance(A,B)为字符串A和字符串B的编辑距离，length1和length2为字符串A和字符串B的长度。

2.根据权利要求1所述的一种安卓市场中重包装应用的检测方法，其特征在于：所述给定阈值设为0.85。

说明书

一种安卓市场中重包装应用的检测方法

技术领域

[0001] 本发明涉及智能手机中的恶意软件检测技术，更具体的说，是在安卓（Android）智能手机应用市场中检测重包装应用的方法。

背景技术

[0002] 以安卓为平台的智能手机安全性令人担忧。自从2008年谷歌正式对外发布第一款安卓手机——HTC G1以来，短短4年的时间，安卓手机已经经历了多次的更新换代。安卓
手机应用市场正以惊人的速度发展着。据科技网站Engadget于2012年2月报道， Android
市场的应用程序数量已经达到45万。随着安卓手机的市场份额越来越大，安卓手机安全性
却越来越引人担忧。很多恶意软件制造者瞄准了这一规模庞大的市场，发布各种各样具有
破坏性的软件。据著名安全厂商McAfee于2012年5月24日发布的《迈克菲2012年第一
季度威胁报告》显示，在今年的第一季度，McAfee收集到了近7000个Android恶意软件。
由于有利可图，所以Android平台吸引了大量不法分子编写针对Android平台的恶意软件。
与2011年第4季度的600个安卓威胁样本相比，环比增长超过1200%。这些恶意软件一般
通过第三方市场传播，通常不会在官方市场出现。

[0003] 研发智能手机上的恶意软件检测迫在眉睫。手机恶意软件虽然不会对手机系统造成毁灭性的破坏，但从某种程度上来说，危害比电脑病毒还要厉害。手机恶意软件主要有如
下几种恶意行为：

[0004] 1. 在后台自动给扣费号码发送短信，赚取经济利润。

[0005] 2. 拦截短信，不让用户觉察到异常。

[0006] 3. 后台自动联网，并下载应用软件，耗费大量流量。

[0007] 4. 读取手机联系人等用户隐私信息，并上传到服务器。

[0008] 5. 开机自行启动，并不断在通知栏弹出广告，影响用户的正常使用。

[0009] 可见手机恶意软件的破坏行为直接和经济挂钩。用户如果不提高防范意识，就会被“吸”走很多话费和流量。根据“警视”公司的调查报告。在2011年年底，有4%的安卓
用户很可能在本年中遭遇了恶意软件，而一年前这一数字为1%，恶意软件的破坏性以及传
播性已经不容小视。因此研发以Android为首的智能手机恶意软件检测的任务迫在眉睫。

[0010] 安卓应用软件市场上的重包装应用很大程度上是恶意软件。安卓操作系统的开源性大大激发了开发者的积极性，给了开发者足够的空间。同时，开源的编程环境也造成了恶
意软件的滋生。开发商发布软件的平台有谷歌的官方平台和形形色色的第三方平台。国内
比较著名的第三方市场有优亿市场、安智市场、木蚂蚁市场、360安卓市场、安卓飞鹏网、91
手机助手等等。由于官方市场的管理比较严格，理论上存在恶意软件的可能性很低。大多
数的恶意软件存在于第三方市场上。其中很大一部分是官方市场软件的重包装应用。

[0011] 重包装是指将官方安卓市场上的应用重新打包后发布在第三方市场。它们基于一个合法的安全版本，但是因为某种原因，又附加了一些特殊的功能或修改。由于安卓应用程
序使用的是Linux内核，一般采用Java语言编写。目前java语言的反编译功能比较成熟。
运用现有的工具，可以实现源代码几乎100%的还原。这使得修改别人的应用程序并添加自
己的代码成为可能。重包装应用发布一般发布在第三方应用平台，利用这些平台监管的不
严格，而将带有恶意代码的应用发布上去，给手机用户和原始开发者造成了不应用的损失，
严重破坏了智能手机应用生态系统。

[0012] 具体来说，重包装应用可能会带来以下问题：

[0013] （1）在官方应用中加入恶意代码，例如自动联网，自动发送短信，拦截短信等。这些行为大大损害了用户的利益。重包装应用一般选用的是比较热门的手机应用，比如手机
QQ，愤怒的小鸟等下载量达到几百万的应用。

[0014] （2）通过替换官方应用中的广告侵害开发者利益。官方应用的开发者可以通过广告获取收入。攻击者往往利用这一点，替换掉原始的广告，换上自己的广告，侵害了开发者
的权益。

[0015] 目前主流的杀毒软件还没有涉及智能手机重包装应用的检测。目前的杀毒软件主要分为静态检测和动态行为检测两种。其中，静态检测的产品数量更多。所谓静态检测，就
是将恶意软件的特征码提取出来，存放到数据库中。检测新的应用程序的时候，再通过提取
特征码，并与数据库中的特征码相比较的方式来判断。这种方法可以检测已知的恶意软件。
对于未知的恶意软件，目前主流的方法是启发式的行为分析法。通过已知恶意软件的特征
推导未知。但是这些产品主要是针对智能手机上已经安装的应用，无法检测安卓软件市场
上的重包装应用。

发明内容

[0016] 本发明的目的是提供一种安卓平台下应用市场中的重包装应用检测技术,通过有效地提取特征码，以及计算特征码之间的编辑距离所得到的相似性来识别重包装应用。
本发明不仅可以检测到恶意代码的变形攻击，还可以作为检测重包装应用的引擎。由于很
多恶意软件是通过在官方下载的正常应用程序中植入恶意代码，因此检测出官方应用的重
包装应用可以作为查杀病毒的一种有效辅助手段。

[0017] 本发明采用的技术方案：一种安卓市场中重包装应用的检测方法,包括以下步骤：

[0018] （1）从各个安卓应用的dex文件中提取特征码。

[0019] 在安卓平台上，用户下载的可安装文件一般是以apk文件，类似于Windows操作系统中的exe文件，apk文件为手机上的可执行文件。而实际上，apk文件的本质是一个压缩
文件。把apk文件的后缀名改为zip然后进行解压缩操作。apk文件解压缩之后可以生成
多个文件，这些文件或多或少都保留了一定的代码特征，然而只有dex文件保留了几乎全
部的代码特征。因此，特征码的提取选用dex文件比较合适。dex文件有着固定的文件格
式，通过这些格式可以对每一个安卓应用的dex文件进行详细的分析，包括文件大小，文件
散列值，文件字符串和类的个数以及具体的内容。对这些内容进行一定的筛选即可得到文
件的特征码。

[0020] 作为优选，所述特征码为dex文件中的字符串长度。

[0021] dex文件包含了文件的几乎全部特征，而为了提高效率。只需要节选文件中的一部分作为特征码。可以用class来作为特征码，也可以用method来作为特征码，本发明采用
的是将字符串的信息作为特征码。用字符串作为特征码的好处很多。首先，这种方法可以
有效抵御类名的混淆替换攻击。基于很多杀毒软件以class名作为特征码。恶意代码的设
计人员往往对文件进行伪装，通过代换和置换的方式改变类名，从而逃避杀毒软件的检索。
而用字符串的方式，如果改变了类名也只能改变部分字符串。调用匹配函数检索的时候，仍
然可以有很高的匹配率。

[0022] 对于大型的文件来说，以所有的字符串作为特征码，虽然可以很好的区分不同的文件，但对于特征码检测来说，工作量过于庞大，程序运行效率很低。因此，本发明采取了一
种变通的方式，以所有字符串的长度按顺序组成特征码。字符串的长度可以用相邻两个字
符串的首地址相减得到，这样大大减少了特征码的长度，提高了重包装应用的检测效率。

[0023] （2）计算各个安卓应用的特征码之间的编辑距离。

[0024] 特征匹配是恶意代码检测的一个重要环节。匹配的度量方法有多种，通常把两段文本之间的差异称作距离，也就是将两段文本变成一致所需要的最少操作次数。常见的
度量方法有汉明距离(Hamming Distance)，插入距离(Insertion Distance)和编辑距离
（Edit Distance）。汉明距离仅允许替换操作，插入距离仅允许插入操作，而编辑距离将插
入，替换，删除均视为一次操作。本发明采用字符串之间的编辑距离，并在此基础上提出了
安卓应用之间相似度的计算方法。

[0025] 编辑距离的计算采用如下的动态规划算法。设字符串为A和B，用一个矩阵M来表示A与B的编辑距离，其中Mij表示的是字符串A的前i个字符变成字符串B的前j个字符
所需的最少编辑操作次数。算法如下：

[0026] 1）分别计算字符串A和字符串B的长度，记为length1和length2。

[0027] 2）判断length1和length2是否为0，若有一个为0，则返回另一个字符串的长度。若两个长度都为0，则返回0.若两者都不为0，则构建一个大小为
(length1+1)*(length2+1)的矩阵M。M的行和列的编号均从0开始。

[0028] 3）将矩阵M的第一行和第一列，分别进行初值为0步长为1的递增编号。

[0029] 4）从M[1,1]开始，按照从左到右从上到下的顺序遍历整个矩阵，遍历过程中用变量i和j分别控制行和列的下标，同时A[i]和B[j]分别表示字符串A和字符串B的对应
字符。

[0030] 5）计算edit变量值，如果A[i]=B[j]，则edit=0，否则edit=1。

[0031] 6）计算M[i,j]=min(M[i-1,j]+1,M[i,j-1]+1,M[i-1,j-1]+edit)。

[0032] 7）重复5）和6）的操作，直到遍历到矩阵末尾，M[length1，length2]即为两字符串之间的编辑距离。

[0033] （3）根据所述编辑距离计算各个安卓应用之间的相似度，并与给定阈值进行比较，从而确定是否为重包装应用。

[0034] 得到编辑距离后，还要计算特征码相似度，相似度的计算公式如下：

[0035] （1）

[0036] 公式（1）中distance（A,B）为字符串A和字符串B的编辑距离，length1和length2为字符串A和字符串B的长度。

[0037] 在公式（1）中之所以用长字符串作为分母，是由于如果用短字符串作为分母，会有结果为负数的可能性。

[0038] 确定公式之后，应该设定阈值，即相似度大于一定程度，可判断为某一应用为重包装应用，否则为不同应用。如果相似度为1，则两应用为相同应用。经过我们的试验，将判断
是否为重包装应用的阈值设为0.85。即两段特征码不同的部分在15%以内，即可认为两者
为重包装的应用软件。

附图说明

[0039] 图1是本发明安卓应用的特征码提取流程图；

[0040] 图2是本发明不同应用的特征码之间编辑距离计算流程图。

具体实施方式

[0041] 下面结合附图和具体实施方式对本发明作进一步说明：

[0042] 一种安卓市场中重包装应用的检测方法,包括以下步骤：

[0043] （1） 从各个安卓应用的dex文件中提取特征码；

[0044] （2） 计算各个安卓应用的特征码之间的编辑距离；

[0045] （3） 根据所述编辑距离计算各个安卓应用之间的相似度，并与给定阈值进行比较，从而确定是否为重包装应用。

[0046] 具体步骤详细介绍如下：

[0047] （1）、从各个安卓应用的dex文件中提取特征码

[0048] 前面已经提及，本发明采取的是以每个字符串的长度按顺序组成的特征码。这些信息可以从dex文件中获得。dex文件有着固定的文件格式，通过这些格式可以对每一个安
卓应用的dex文件进行详细的分析，包括文件大小，文件散列值，文件字符串和类的个数以
及具体的内容。对这些内容进行一定的筛选即可得到文件的特征码。dex文件的头文件格
式如表1所示。其中的字符串列表信息是本发明所使用的。dex头文件详细的标示出了字
符串的个数以及每一组字符串的首地址。按照首地址去搜索对应的位置可以得到相应的字
符串。

[0049] 表1 dex文件的头文件格式

[0050]0
本 是
版 也
的 里
构结 这，0
示 为
表 小
530 大的
的 段
中 接
其 连
，”0/530n/xed” 07x0=本版5 21436587x0=下 。接连态静是 果如。起算始开
如式 30,C 况情 示表 头件
格，段字数魔即， 度长总 5x0=本版900， 省缺，量常的序 就0为果如，小 文本从，置位始 址地 数个串符字的 址地基表 数个型类 址地值 名 的 度 顺 大 开 基 表 表 里 基
'cig 码 签1- 件文 长头 节字 的段 的段 据数 列串 列串 表列 表列
述描 aM' 验校 AHS xeD 件文 识标 接连 接连 pam 符字 符字 型类 型类
度 0
长 8 4 2 4 4 4 4 4 4 4 4 4 4
值
移偏 0x0 8x0 Cx0 02x0 42x0 82x0 C2x0 03x0 43x0 83x0 C3x0 04x0 44x0
ezis ffo ez f
m er e ezis gat ez f _sdi _sdi is_s fo_s
称名 ci uskc utan zis_ _red _nai is_k fo_k ffo_ _gni _gni di_e di_e
段字 gam ehc gis elfi aeh dne nil nil pam rts rts pyt pyt

[0051] 由于dex文件按字节读取很长，而我们需要提取的特征码只是整个文件的很小的一部分。因此接下来要确定读取文件的长度。在前文的dex格式分析报告中可以看到，偏
移地址为0x38开始的4个字节存放的是字符串列表的字符串个数。因此，在读取之前需要
将文件读取的指针指向0x38地址。

[0052] 找到字符串的位置之后，由于按字节读取dex文件是高位在前，低位在后，因此读出来的字符串位置要进行转换。之后通过地址的差值很容易计算出字符串的长度，而不需
要读取字符串的具体内容。本发明以文件字符串长度作为特征码，不仅可以区分两个完全
不同的程序。也可以找到相似度很大的两个程序。这样可以找出与官方市场下载的应用软
件类似的重包装应用，也可以有效抵抗恶意软件的变形攻击。很多恶意软件会将自身的类
名做混淆，增加查杀的难度。而基于字符串长度的特征码可以通过比较相似度的方式找出
加入混淆措施的重包装恶意软件。

[0053] 提取特征码的流程如图1所示。

[0054] （2）、计算各个安卓应用的特征码之间的编辑距离

[0055] 编辑距离的计算采用如下的动态规划算法。设字符串为A和B，用一个矩阵M来表示A与B的编辑距离，其中Mij表示的是字符串A的前i个字符变成字符串B的前j个字符
所需的最少编辑操作次数。算法如下：

[0056] 1、分别计算字符串A和字符串B的长度，记为length1和length2。

[0057] 2、判断length1和length2是否为0，若有一个为0，则返回另一个字符串的长度。若两个长度都为0，则返回0.若两者都不为0，则构建一个大小为
(length1+1)*(length2+1)的矩阵M。M的行和列的编号均从0开始。

[0058] 3、将矩阵M的第一行和第一列，分别进行初值为0步长为1的递增编号。

[0059] 4、从M[1,1]开始，按照从左到右从上到下的顺序遍历整个矩阵，遍历过程中用变量i和j分别控制行和列的下标，同时A[i]和B[j]分别表示字符串A和字符串B的对应
字符。

[0060] 5、计算edit变量值，如果A[i]=B[j]，则edit=0，否则edit=1。

[0061] 6、计算M[i,j]=min(M[i-1,j]+1,M[i,j-1]+1,M[i-1,j-1]+edit)。

[0062] 7、重复5和6的操作，直到遍历到矩阵末尾，M[length1，length2]即为两字符串之间的编辑距离。

[0063] 计算两个应用特征码之间编辑距离的流程图如图2所示。

[0064] （3）、根据所述编辑距离计算各个安卓应用之间的相似度，并与给定阈值进行比较，从而确定是否为重包装应用

[0065] 得到编辑距离后，还要计算特征码相似度，相似度的计算公式如下：

[0066] （1）

[0067] 公式（1）中distance（A,B）为字符串A和字符串B的编辑距离，length1和length2为字符串A和字符串B的长度。

[0068] 在公式（1）中之所以用长字符串作为分母，是由于如果用短字符串作为分母，会有结果为负数的可能性。

[0069] 确定公式之后，应该设定阈值，即相似度大于一定程度，可判断为某一应用为重包装应用，否则为不同应用。如果相似度为1，则两应用为相同应用。经过我们的试验，将判断
是否为重包装应用的阈值设为0.85。即两段特征码不同的部分在15%以内，即可认为两者
为重包装的应用软件。

[0070] 本发明所描述的步骤为判断给定两个安卓应用是否为重包装应用，本发明可以很方便地扩展到从多个安卓应用中判断出重包装应用。

[0071] 应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未
明确的各组成部分均可用现有技术加以实现。