专利：一个基于应用程序编程接口的安卓重打包应用检测方法
适用于检测安卓平台的应用程序的一种安卓重打包应用检测方法
今天惊闻三年前申请的专利终于批准下来了，实在是让人高兴。
- 专利类型：发明专利
- 申请（专利）号：CN201310438647.8
- 申请日期：2013年9月24日
- 公开(公告)日：2013年12月25日
- 公开(公告)号：CN103473346A
- 申请（专利权）人：北京大学
- 发明（设计）人：郭耀,马子昂,王浩宇,陈向群
- 主分类号：G06F17/30,G06F17/00,G,G06,G06F,G06F17
- 分类号：G06F17/30,G06F17/00,G,G06,G06F,G06F17,G06F17/30,G06F17/00
- 主申请人地址：100871 北京市海淀区颐和园路5号
专利代理机构：北京万象新悦知识产权代理事务所(普通合伙) 11360 - 代理人：朱红涛
- 国别省市代码：北京;11
- 主权项：一种基于应用程序编程接口的安卓重打包应用检测方法，适用于检测安卓平台的应用程序，其特征是，包括如下步骤：A.对应用程序文件进行预处理，将二进制代码转换为smali代码文件、提取应用程序的作者签名信息并构造应用程序编程接口；B.对smali代码文件进行处理，以文件夹为单位，提取出安卓应用程序编程接口的调用情况以及对应的调用次数，组成特征向量；C.计算不同文件夹之间的特征向量的相似度，并进行聚类，去除第三方库；D.再次根据应用程序编程接口，计算应用程序的特征向量，对比应用程序的特征向量的相似度，聚类并判断哪些应用程序为重打包应用。
Abstract
一种基于应用程序编程接口的安卓重打包应用检测方法。首先对应用程序文件进行处理，得到smali代码文件；对于每一个文件夹，从smali代码中提取出安卓应用程序编程接口的使用情况，统计频率信息；然后通过文件夹之间的相互比较来进行聚类，将相似度高、重复数量多的文件夹视为第三方库；去除第三方库干扰之后，再以应用程序文件为单位，对相似度高的程序文件进行聚类；最后结合作者签名信息，判断应用程序之间是否具有重打包关系。利用本发明提供的技术方案，可以在大规模应用市场级别的应用中，对重打包应用进行自动的检测，有很高的效率以及准确性。
Description
一种基于应用程序编程接口的安卓重打包应用检测方法
技术领域
[0001] 本发明涉及一种基于应用程序编程接口的重打包应用检测方法，具体涉及一种在安卓平台下，利用应用程序代码中关键应用程序编程接口的使用频率，过滤第三方库以及检测重打包应用的方法。
背景技术
[0002] 近年来，移动设备(例如智能手机和平板)的发展十分迅速。Android平台占据了智能移动市场的主要份额，据统计每天有超过130万部搭载Android系统的移动设备被激活使用。随着移动设备的流行和普及，涌现出大量的移动应用。截止至2013年2月，谷歌官方市场中已经有超过80万个Android移动应用。这些移动应用不仅增强了移动设备的功能，还大大丰富了用户体验。用户逐渐习惯于使用多样的应用来娱乐和办公，智能移动设备和移动应用已经成为人们生活中不可或缺的一部分。
[0003] 由于Android系统的开放性，用户不仅能从谷歌官方市场下载和安装应用，也可以从任意的第三方市场甚至网站和论坛下载和安装应用。同时，应用的开发者可以将应用提交到任意的第三方市场来供用户下载。因此对于应用市场的管理者来说，只有管理好市场中应用的质量和提供一个良好的市场环境，才能吸引更多的用户和开发者。
[0004] 然而，Android应用很容易被破解，目前有很多开源的反编译工具可以使用。因此，一些恶意的开发者可以很容易破解应用市场中的合法应用，修改代码后重新打包并在市场中发布。付费的应用可以被破解然后免费发布出去，恶意的开发者也可以将原应用中的广告库替换掉来谋取利益。更为严重的是，恶意的开发者可以将恶意的代码植入到合法的应用中然后发布出去，以此来感染更多的用户。应用重打包的行为不仅侵犯了开发者的利益，也严重威胁到了用户的安全和隐私。
[0005] 应用市场的管理者需要控制市场中应用的质量，检测和移除这些潜在的威胁。然而，在应用市场中检测重打包应用是很困难的。一方面，管理者大多数时候只能通过手动比较来判断应用是否是重打包应用，并且很多时候手动比较也很难得到正确的结果。例如，重打包的应用可以在功能上包含了几个不同的应用，或者重打包的应用包含了恶意软件等等。另一方面，考虑到应用市场中海量数目的应用，手动进行重打包检测不可靠且没有可扩展性。因此，在应用市场级别的应用重打包检测需要一个自动化的系统来完成。
[0006] Wu Zhou等提出在Dalvik字节码层次上进行应用重打包检测(“DroidMOSS:Detecting Repackaged Smartphone Applications in Third-PartyAndroid Marketplaces”, C0DASPY’ 12)。DroidMOSS 提取 Dalvik 字节码中的操作码序列，使用模糊散列的方法对应用程序产生一个指纹签名并作为特征，通过比较应用程序指纹之间的编辑距离得到应用程序的相似度。类似的，Steve Hanna等提出了 Juxtapp (“ Juxtapp: AScalable System for Detecting Code Reuse Among Android Applications”,DIMVA’12),使用了特征散列的方法对应用程序产生指纹签名并且以它们之间的Jaccard距离作为重打包的判断依据。DroidMOSS和Juxtapp都是从Dalvik字节码中提取静态的特征信息,并且使用不同的散列技术来将这些静态信息表示成向量从而进行比较。这种比较方法的优点是简单快速，能够很容易扩展到大规模应用的比较。但是重打包应用很容易就能逃避这种检查技术，比如最简单的交换代码顺序或者增添删除操作码就会导致应用程序的指纹发生改变从而导致检测方法失效。
[0007] Jonathan Crussell 等提出 DNADroid (“Attack of the Clones !Detecting ClonedApplications on Android Markets”，ESORICS’12),通过比较应用的程序依赖图(PDG)来检测重打包应用。基于程序依赖图的检测技术是代码克隆检测中经常使用的方法。它使用了程序的语义信息，因此检测的准确率应该会比较高。但是基于程序依赖图的检测方法执行效率是个问题。在DNADroid中，作者使用Hadoop Mapreduce并行计算框架在四台机器上执行应用的重打包检测，但是平均每分钟只能比较0.71个应用对。因此，这种方法的扩展性不高，很难应用到应用市场级别数十万的应用检测。
[0008] 综上，现有的应用重打包检测方法主要存在两个问题:
[0009] I)安卓应用程序中的第三方库代码的使用对重打包应用的检测干扰很大，现有的做法大部分都是通过建立第三方库的白名单来过滤掉第三方库的代码。但是由于现有的应用程序中大多数都经过了代码混淆，因此这种方法对于代码混淆过后的应用程序是无效的。
[0010] 2)系统必须要保证准确性的同时具有很高的可扩展性，这就需要提出的检测方法有低误报率和高查全率，应该考虑到不同层面上的代码更改、添加和删除，并且能够快速地在海量应用中检测到重打包应用。但是现有的方法中没有做到这一点。
发明内容
[0011] 本发明的目的是提供一种新的方法，使得在较小开销，较快时间内，对给出的若干安卓应用程序进行预处理，得到一些关于应用程序编程接口的特征向量，通过相似度计算，进行聚类，去除第三方库，并得 到这些安卓应用程序中哪些是重打包应用的信息。
[0012] 本发明的原理是:首先对应用程序文件(apk文件)进行处理，得到smali代码文件，smali代码是原来应用程序二进制代码的一种中间表示。处理得到的smali文件是按照原始的文件夹层次组织的，对于每一个文件夹，从smali代码中提取出安卓应用程序编程接口的使用情况，统计频率信息。然后通过文件夹之间的相互比较来进行聚类，将相似度高、重复数量多的文件夹视为第三方库。去除第三方库干扰之后，再以应用程序文件为单位，对相似度高的程序文件进行聚类。最后结合作者签名信息，判断应用程序之间是否具有重打包关系。
[0013] 本发明提供的技术方案如下:
[0014] 一种基于应用程序编程接口的安卓重打包应用检测方法，适用于检测安卓平台的应用程序，其特征是，包括如下步骤(流程参照图1):
[0015] A.对应用程序文件进行预处理，将二进制代码转换为smali代码文件、提取应用程序的作者签名信息并构造应用程序编程接口；
[0016] B.对smali代码文件进行处理，以文件夹为单位，提取出安卓应用程序编程接口的调用情况以及对应的调用次数，组成特征向量；
[0017] C.计算不同文件夹之间的特征向量的相似度，并进行聚类，去除第三方库；[0018] D.再次根据应用程序编程接口，计算应用程序的特征向量，对比应用程序的特征向量的相似度，聚类并判断哪些应用程序为重打包应用。
[0019] 所述的安卓重打包应用检测方法，其特征是，步骤A包括:
[0020] Al.提取安卓应用程序二进制代码文件以及ΜΕΤΑ-1NFO文件中的作者签名信息文件；
[0021] A2.使用现有工具，将二进制代码转换为smali代码文件；
[0022] A3.使用现有工具，从相应文件提取作者签名内容。
[0023] 所述的安卓重打包应用检测方法，其特征是，步骤B包括:
[0024] B1.对步骤A中得到的smali代码文件进行处理,读取smali文件的内容,并用正则表达式进行匹配，将应用程序编程接口函数与其余信息剥离，并以文件夹为单位，统计汇总;
[0025] B2.把步骤BI中得到的应用程序编程接口数据转化为易于程序识别与操作的欧几里得空间的特征向量。
[0026] 所述的安卓重打包应用检测方法，其特征是，步骤C包括:
[0027] Cl.对每两个文件夹之间求向量距离。假设需要比较文件夹a和文件夹b的相似度。首先通过步骤B取得a和b的特征向量，分别为α和β在欧几里德空间中，若α在某一维度上有值，而β在该维度上没有值，则β在该维度上补充为0，反之亦然。对α和β，采用以下公式来求取向量距离:
Figure CN103473346AD00051
[0029] 其中η是α和β的维度。
[0030] C2.根据向量距离，确定阈值，进行聚类。在划分的众多类中，再将出现次数多的类视为第三方库中的类文件，并在步骤D的计算中除去。
[0031] 所述的安卓重打包应用检测方法，其特征是，步骤D包括:
[0032] Dl.根据每个文件夹的特征向量，把未经过第三方库过滤掉的文件夹的特征向量，使用加总的方法，整合为每个应用的特征向量。
[0033] D2.使用Cl中出现的公式，计算两两之间的距离，并以此为基础采用聚类算法，把距离低于某个阈值的应用聚合到一个类。
[0034] D3.对D2步骤中同一个类的应用，审查他们的作者信息。如果同一个类中的应用，其作者签名不同，则认定两个应用之间有重打包的关系。
[0035] 所述的安卓重打包应用检测方法，其特征是，步骤C2中，确定的阈值为0.05。
[0036] 所述的安卓重打包应用检测方法，其特征是，步骤D2中，确定的阈值为0.1。
[0037] 本发明的有益效果:利用本发明提供的技术方案，可以在大规模应用市场级别的应用中，对重打包应用进行自动的检测，有很高的效率以及准确性。
附图说明
[0038] 图1是本发明所述方法的总体流程图
[0039] 图2本发明的应用程序预处理流程图。
[0040] 图3本发明的计算特征向量的流程图。[0041] 图4本发明的过滤第三方库的流程图。
[0042] 图5本发明的重打包判断流程图。
[0043] 图6本发明实施例提供的应用程序预处流程图。[0044]图7本发明实施例提供的计算特征向量的流程图。
[0045] 图8本发明实施例提供的过滤第三方库的流程图。
[0046] 图9本发明实施例提供的重打包判断流程图。
具体实施方式
[0047] 本发明的具体实施方式如下:
[0048] A.在对应用程序文件进行预处理时，执行如下操作(如图2所示):
[0049] Al.使用现有工具，例如 keytool (JDK (Java Development Kit)开发组件工具)，从相应apk文件中提取作者签名内容；
[0050] A2.使用现有工具，例如 apktool (https://code, google, com/apktool/),将 apk包中的压缩的二进制代码提取并转换为smali代码文件。
[0051] B.在对smali文件进行处理组成特征向量时，执行如下操作(如图3所示):
[0052] B1.对步骤A2得到的smali代码文件进行处理,读取smali文件的内容,使用正则表达式进行匹配，将应用变成接口函数与其他信息进行剥离，并以文件夹为单位，统计汇
[0053] B2.把步骤BI中得到的应用程序编程接口数据转化为易于程序识别和操作的欧几里德空间特征向量。
[0054] C.计算不同文件夹之间的特征向量的相似度，并进行聚类，去除第三方库时，执行如下操作(如图4所示):
[0055] Cl.对每两个文件夹之间求向量距离。假设需要比较文件夹a和文件夹b的相似度。首先通过步骤B取得a和b的特征向量，分别为α和β。在欧几里德空间中，若α在某一维度上有值，而β在该维度上没有值，则β在该维度上补充为0，反之亦然。对α和β，采用以下公式来求取向量距离:
[0056]
Figure CN103473346AD00061
[0057] 其中n是α和β的维度。
[0058] C2.根据特征向量的距离，确定阈值，进行聚类。在划分的众多类中，再将出现次数多的类视为第三方库，并在步骤D的计算中除去。
[0059] D.在再次根据应用程序编程接口，计算应用程序的特征向量，对比应用程序的特征向量的相似度，聚类并判断哪些应用程序为重打包应用时，执行如下操作(如图5所示):
[0060] Dl.根据每个文件夹的特征向量，把未经过第三方库过滤掉的文件夹的特征向量，使用加总的方法，整合为每个应用的特征向量。
[0061] D2.使用Cl中出现的公式，计算两两之间的距离，并以此为基础采用聚类算法，把距离低于某个阈值的应用聚合到一个类。
[0062] D3.对D2步骤中同一个类的应用，审查他们的作者信息。如果同一个类中的应用，其作者签名不同，则认定两个应用之间有重打包的关系。[0063] 下面通过实例对本发明做进一步说明。
[0064] 实施例1:
[0065] 假定现有1000个安卓apk安装程序，需要从中找出具有重打包关系的软件。文件名分别是 1.apk, 2.apk 直到 1000.apk。
[0066] A.预处理的流程包括如下步骤(如图6所示):
[0067] Al.对任意一个apk文件,如1.apk,使用开源的keytool工具可以得到作者签名信息文件；把这些签名记录为一个列表，以备步骤D3使用。
[0068] A2.对任意一个apk文件，如1.apk,使用开源的apktool工具，可以将apk解压，解压包内有一个smali文件夹，文件夹内有相应的smali代码文件。
[0069] B.生成特征向量的流程，包括如下步骤(如图7所示):
[0070] B1.对任意一个apk文件，如1.apk,对预处理得到的smali代码文件处理,读取smali里的内容，获得关于应用程序编程接口函数的信息，以文件夹为单位，进行汇总。如
1.apk的smali文件夹下只有两个文件夹,那么就分别计算这两个文件夹内smali文件对应用程序编程接口函数的调用情况。
[0071] B2.得到上一步骤中的调用情况，根据调用的名称与次数，把调用情况整合成一个欧几里得空间中的多维的特征向量。如1.apk的第一个文件夹中，使用调用X有2次，使用调用y有5次，则多维特征向量在X上的分量就是2，在y上的分量就是5。
[0072] C.计算文件夹相似度并去除第三方库的流程，包括如下步骤(如图8所示):
[0073] Cl.对于两个文件夹，如1.apk中的文件夹一，与2.apk中的文件夹三，使用公式比较距离，得到一个distance的值。
[0074] C2.根据distance的值，如果这个值高于阈值0.05，就认为这两个文件夹不相似。以该阈值进行聚类。如果聚类的结果表明，某一类别的文件夹出现的次数多余某个次数(次数的阈值与进行比较的总apk数量有关)，那么就认为这个文件夹是一个第三方库的文件夹，应当在步骤D的比较中去除。否则就认为该文件夹不是第三方库，需要在步骤D中继续计算。
[0075] D.最终判断重打包的流程，包括如下步骤(如图9所示):
[0076] Dl.对于每一个apk文件，整合其所有的文件夹的特征向量，将未被过滤为第三方库的文件夹的特征向量加起来。如1.apk，如果它含有两个smali文件夹，而且两个文件夹均没有被步骤C2过滤，则直接把两个特征向量用加法加总，作为1.apk的特征向量。
[0077] D2.使用Cl步骤中的公式,计算任意两个apk应用之间的距离，如计算1.apk和
2.apk的距离。如果1.apk和2.apk计算所得的distance大于0.1,则认为1.apk与2.apk没有直接重打包的关系，否则认为1.apk与2.apk有重打包的嫌疑。以此为依据进行聚类。
[0078] D3.结合前面得到的作者签名信息，进一步对结果进行筛选排查，如若1.apk与
2.apk因为距离小于0.1被聚类到同一个类别，这时候就把1.apk在Al步骤得到的作者签名信息，与2.apk的作者签名信息进行比较，如果发现这两个应用程序的作者信息不同，则认定1.apk与2.apk这两个应用程序为重打包应用程序。如果发现这两个应用程序的作者信息一致，则认定1.apk与2.apk是同一个作者的相同作品，或同一个作者的不同版本作品O
Claims
1.一种基于应用程序编程接口的安卓重打包应用检测方法，适用于检测安卓平台的应用程序，其特征是，包括如下步骤: A.对应用程序文件进行预处理，将二进制代码转换为smali代码文件、提取应用程序的作者签名信息并构造应用程序编程接口； B.对smali代码文件进行处理，以文件夹为单位，提取出安卓应用程序编程接口的调用情况以及对应的调用次数，组成特征向量； C.计算不同文件夹之间的特征向量的相似度，并进行聚类，去除第三方库； D.再次根据应用程序编程接口，计算应用程序的特征向量，对比应用程序的特征向量的相似度，聚类并判断哪些应用程序为重打包应用。
2.如权利要求1所述的安卓重打包应用检测方法，其特征是，所述步骤A包括: Al.提取安卓应用程序二进制代码文件以及ΜΕΤΑ-1NFO文件中的作者签名信息文件； A2.使用现有工具，将二进制代码转换为smali代码文件； A3.使用现有工具，从相应文件提取作者签名内容。
3.如权利要求1所述的所述的安卓重打包应用检测方法，其特征是，所述步骤B包括: B1.对步骤A中得到的smali代码文件进行处理，读取smali文件的内容，并用正则表达式进行匹配，将应用程序编程接口函数与其余信息剥离，并以文件夹为单位，统计汇总；B2.把步骤BI中得到的应用程序编程接口数据转化为易于程序识别与操作的欧几里得空间的特征向量。
4.如权利要求1所述的安卓重打包应用检测方法，其特征是，所述步骤C包括: Cl.对每两个文件夹之间求向量距离，假设需要比较文件夹a和文件夹b的相似度，首先通过步骤B取得a和b的特征向量，分别为α和β在欧几里德空间中，若α在某一维度上有值，而β在该维度上没有值，则β在该维度上补充为0，反之亦然；对α和β，采用以下公式来求取向量距离: 
其中η是α和β的维度； C2.根据向量距离，确定阈值，进行聚类。
5.如权利要求4所述的安卓重打包应用检测方法，其特征是，步骤D包括: Dl.根据每个文件夹的特征向量，把未经过第三方库过滤掉的文件夹的特征向量，使用加总的方法，整合为每个应用的特征向量； D2.使用Cl中出现的公式，计算两两之间的距离，并以此为基础采用聚类算法，把距离低于某个阈值的应用聚合到一个类； D3.对步骤D2中同一个类的应用，审查他们的作者信息，如果同一个类中的应用，其作者签名不同，则认定两个应用之间有重打包的关系。
6.如权利要求4所述的安卓重打包应用检测方法，其特征是，步骤C2中所述的阈值为0.05。
7.如权利要求5所述的安卓重打包应用检测方法，其特征是，步骤D2中所述的阈值为`0.1。
