CN103473104B

CN103473104B - 一种基于关键词上下文频率矩阵的应用重打包辨别方法

Info

Publication number: CN103473104B
Application number: CN201310438444.9A
Authority: CN
Inventors: 郭耀; 吕骁博; 王浩宇; 刘梦馨; 陈向群
Original assignee: Peking University
Current assignee: Peking University
Priority date: 2013-09-24
Filing date: 2013-09-24
Publication date: 2016-10-05
Anticipated expiration: 2033-09-24
Also published as: CN103473104A

Abstract

一种基于关键词上下文频率矩阵的应用重打包辨别方法，应用于安卓系统，首先对应用程序文件进行处理，得到smali代码文件然后对smali代码处理，提取操作符序列，统计关键词信息，对每个特定类型的关键词构造上下文相关的特征三元组生成基于上下文频率的特征矩阵，对应用程序的特征矩阵进行两两对比，根据矩阵相似度得到两个应用程序的相似度。最后结合作者信息等内容判断应用程序间是否有重打包关系。用本发明提供的技术方案，可以对重打包的安卓应用程序进行判别，同时避免了对整个应用程序进行巨型字符串哈希处理的额外开销；不依赖原始文件二进制代码顺序；通过限制特征矩阵的大小，降低空间开销；提高了安卓应用程序重打包判别的执行效率。

Description

一种基于关键词上下文频率矩阵的应用重打包辨别方法

技术领域

本发明涉及一种基于关键词上下文频率矩阵的应用重打包辨别方法，具体涉及一种在安卓平台下，利用应用程序代码关键词频率矩阵，识别应用重打包的处理方法。

背景技术

安卓（Android）系统是谷歌公司开发并推广，基于Linux的自由及开放源代码的操作系统，主要使用于移动设备，例如智能手机或平板电脑。安卓系统是目前全球市场份额最大的移动手机操作系统，来自官方的数据显示，安卓系统上的应用程序已经超过975,000个。

通常，安卓系统应用程序由第三方开发者开发和发布，这就带来一个问题，即应用重打包。应用重打包是指，某些开发者通过不同渠道攫取其他开发者发布的应用，通过反编译，二进制代码插桩等技术，对现有应用程序进行修改（例如植入恶意代码，修改开发者信息，修改权限，对受保护内容进行破解等），再重新打包、发布。这就引发了关于版权，安全，著作权，隐私保护，恶意代码植入等诸多问题。

Silvio Cesare和Yang Xiang在《Software Similarity and Classification》一书中总结了若干关于软件相似度和聚类分析的解决方案：例如通过字符串分析，对代码文本进行相似度比较，进而得出软件相似度的信息；以及通过对代码词频进行统计，根据统计结果比较软件相似度。不过这些解决方案并没有考虑移动平台应用相关的特殊情况。

2012年，美国南加州大学Wu Zhou,Yajin Zhou等人提出了另一种解决方案（CODASPY’12论文）：利用混淆哈希技术，提取应用程序特征，然后利用混淆哈希生成应用的指纹，再采用滚动哈希技术，将指纹生成为一个特征向量，通过两个应用的特征向量相似度比较，判断是否存在软件重打包问题。该方法需要对所有代码进行分析，复杂低效，且依赖代码文本顺序，无法处理通过插入无用代码，代码混淆，函数重命名，改变代码顺序等对代码进行修改的情况。

发明内容

本发明的目的是提供一种新的方法，使得在较小开销，较快时间内，对给出的若干安卓应用程序进行预处理，得到一个基于关键词上下文频率的特征矩阵，通过对矩阵相似度的计算，进行聚类，得到这些安卓应用程序中哪些是重打包应用的信息。

本发明的原理是：首先对应用程序文件（apk文件）进行处理，得到smali代码文件，smali代码是原来应用程序二进制代码的一种中间表示。然后对smali代码处理，提取操作符序列，统计关键词信息，对每个特定类型的关键词构造上下文相关的特征三元组<K1,i,K2>，生成基于上下文频率的特征矩阵，对应用程序的特征矩阵进行两两对比，根据矩阵相似度得到两个应用程序的相似度。最后结合作者信息等内容判断应用程序间是否有重打包关系。

本发明提供的技术方案如下：

一种基于关键词上下文频率矩阵的应用重打包辨别方法，应用于安卓系统，其特征是，包括如下步骤（流程参见图9）：

A.对应用程序文件进行预处理，将二进制代码转换为smali代码文件、提取应用程序的作者签名信息并构造关键词向量；

B.对smali代码文件进行处理，生成smali操作符序列；

C.生成关键词上下文频率矩阵；

D.对比应用程序关键词上下文频率矩阵的相似度，判断该应用程序是否为重打包应用。

所述的应用重打包辨别方法，其特征是，步骤A包括：

A1.提取安卓应用程序二进制代码文件以及META-INFO文件中的作者签名信息文件；

A2.使用现有工具，将二进制代码转换为smali代码文件；

A3.使用现有工具，从相应文件提取作者签名内容；

A4.构造关键词向量。

所述的应用重打包辨别方法，其特征是，步骤B包括：

B1.对步骤A中得到的smali代码文件进行处理，去掉第三方库文件（主要是一些广告库，社交平台库等内容）；

B2.对步骤B1中得到的smali代码文件处理，将每条语句中的操作符以外的其他所有信息剥离，得到一个应用程序的smali操作符序列。

所述的应用重打包辨别方法，其特征是，步骤C包括：

C1.构造关键词上下文频率矩阵Max；

C2.根据选定的关键词向量，对每一个关键词，在步骤B得到的smali操作符序列中的每一次出现，采用哈希算法，将其上文的K条语句和下文的K条语句分别映射为整数K1和K2，其中，所述关键词在关键词向量中对应下标为i；

C3.增加特征矩阵对应位置Max[i][K1][K2]计数。

所述的应用重打包辨别方法，其特征是，步骤D包括：

D1.对给定的安卓应用程序，计算其关键词上下文频率矩阵的相似度，以此作为标准，对两个安卓应用程序进行两两比较；

D2.将关键词上下文频率矩阵的相似度计算结果超过指定阈值的安卓应用程序聚类，认为这一类的安卓应用程序可能存在重打包问题；

D3.结合步骤A中得到的作者签名信息，进一步对步骤D2的判定结果进行筛选排查。

所述的应用重打包辨别方法，其特征是，步骤D1中，计算其关键词上下文频率矩阵的相似度的方法为：设原应用程序（即未重打包的原始应用程序）和待判断的应用程序的关键词上下文频率矩阵分别为Max1，Max2，对两个矩阵的每一位，分别用Max1[i][j][k]和Max2[i][j][k]表示，计算这两个数的最小值Min[i][j][k]，用score来表示其相似度得分，score=200*ΣMin[i][j][k]/Σ(Max1[i][j][k]+Max2[i][j][k])。

所述的应用重打包辨别方法，其特征是，步骤D2中，所述的阈值为70。

所述的应用重打包辨别方法，其特征是，步骤A4中，选择如下指令对应的操作符作为关键词：转移指令、函数调用指令、比较指令、声明类指令、运算指令、传送指令、抛出异常指令。

所述的应用重打包辨别方法，其特征是，步骤A4中，选择如下操作符作为关键词：if、goto、invoke_virtual、invoke_static、invoke_direct、add-int/lit8、move_result_object、new-array、const/4、const/16、const-string、throw、new-instance、cmpl-float、and-int/lit1。

本发明的有益效果：利用本发明提供的技术方案，可以对重打包的安卓应用程序进行判别，同时避免了对整个应用程序进行巨型字符串哈希处理的额外开销；不依赖原始文件二进制代码顺序；通过限制特征矩阵的大小，降低空间开销；提高了安卓应用程序重打包判别的执行效率。

附图说明

图1本发明的应用程序预处理流程。

图2本发明的生成smali操作符序列流程。

图3本发明的生成关键词上下文频率矩阵流程。

图4本发明的重打包结果判断流程。

图5本发明实施例提供的应用程序预处流程图。

图6本发明实施例提供的生成smali操作符序列流程图。

图7本发明实施例提供的生成关键词上下文频率矩阵流程图。

图8本发明实施例提供的重打包结果判断流程图。

图9本发明所述方法的流程图。

具体实施方式

本发明的具体实施方式如下：

A.在对应用程序文件进行预处理时，执行如下操作：

A2.使用现有工具，例如backsmali（https://code.google.com/p/smali/），将二进制代码（.dex文件）转换为smali代码文件；

A3.使用现有工具，例如keytool（JDK（Java Development Kit）开发组件工具），从相应文件（CERT.RSA）提取作者签名内容；

A4.构造关键词向量，关键词的选择依据是，选取出现频率比较高的语句；关键词在语义上没有明显的重复，即关键词集合可以覆盖不同功能的语句；选取语义上比较重要的指令，例如运算指令、函数调用指令等。

B.在生成smali操作符序列部分，执行如下操作：

B1.对步骤A2得到的smali代码文件进行处理，去掉第三方库文件，主要是一些广告库，例如Admob，AirPush，LeadBolt，InMobi等，社交平台库，例如Facebook,OpenFeint,HeyZap等，以及其他开发所使用的第三方库；

B2.对步骤B1得到的smali代码文件处理，将每条语句中的操作符以外的其他所有信息剥离，这些其他信息包括操作数，以及一些其他的标示符，例如‘#’，‘.’等，得到一个应用程序的smali操作符序列。

C.在生成关键词上下文频率矩阵部分，执行如下操作：

C1.构造关键词上下文频率矩阵Max，这是一个三维矩阵，大小为sz_kv*sz_hash*sz_hash，其中sz_kv为选定的关键词向量的大小，sz_hash是步骤C2中采取的哈希算法结果的取值范围大小，将Max的每一位初始化为0；

C2.根据选定的关键词向量，对每一个关键词（在关键词向量中对应下标为i）在步骤B2得到的smali操作符序列中的每一次出现，采用特定哈希算法，将其上文的K（K为自定义的一个整数）条语句和下文的K条语句分别映射为整数K1和K2;

C3.增加特征矩阵对应位置Max[i][K1][K2]计数。

D.在重打包结果判断时，执行如下操作：

D1.对给定的安卓应用程序，采用特定算法计算其关键词上下文频率矩阵的相似度，以此作为标准，对两个安卓应用程序进行两两比较；这里比较关键词上下文频率矩阵的相似度的算法是，设两个矩阵分别为Max1，Max2，对两个矩阵的每一位，分别用Max1[i][j][k]和Max2[i][j][k]表示，计算这两个数的最小值Min[i][j][k]，用score来表示其相似度得分，score=200*ΣMin[i][j][k]/Σ(Max1[i][j][k]+Max2[i][j][k])；

D2.将关键词上下文频率矩阵的相似度计算结果（即步骤D1中的score）超过某个阈值的安卓应用程序聚类，根据经验性结果，阈值选为70时最优，认为这一类的安卓应用程序可能存在重打包问题。

D3.结合步骤A3得到的作者签名信息，进一步对步骤D2的结果进行筛选排查，作者信息相同的相似应用程序一般是同一应用程序的不同版本，不属于重打包应用，而作者信息不同的相似应用程序则判断为重打包应用程序。

下面通过实例对本发明做进一步说明。

实施例1：

假定一个安卓应用程序，其中文名为“自动桌面照片滤镜”，需要检测它是否是一个重打包应用，其程序包名为AutodeskzhaopianlvjingPixlr_o_matic_V2.2.1_mumayi_ac32a.apk。

A.预处理的流程包括如下步骤：

A1.将apk程序包解压之后，可以得到若干文件和文件夹，其中class.dex文件是应用程序的二进制代码文件，META-INFO文件夹下的CERT.RSA文件是作者的签名信息；

A2.使用backsmali工具，将class.dex文件转换为smali代码文件，会生成一个文件夹，其中包括多个.smali文件；

A3.使用keytool工具，从CERT.RSA提取作者签名内容，输入keytool-printcert-fileCERT.RSA命令，可以得到若干关于应用程序的信息，包括所有者，发布者，序列号，有效期以及证书指纹。

A4.构造关键词向量，根据实验得到的经验性结果，我们选择如下15个操作符作为关键字，分别是if、goto、invoke_virtual、invoke_static、invoke_direct、add-int/lit8、move_result_object、new-array、const/4、const/16、const-string、throw、new-instance、cmpl-float、and-int/lit1，这15个操作符代表了多种指令，包括转移指令、函数调用指令、比较指令、声明类指令、运算指令、传送指令、抛出异常指令，每个操作符对应关键字向量的一个下标；

B.生成smali操作符序列流程，包括如下步骤：

B1.对预处理得到的smali代码文件处理，去掉第三方库文件，例如该apk中包含admob广告库，则将对应的所有smali文件删除；

B2.对B1得到的smali代码文件处理，将每条语句中的操作符以外的其他所有信息剥离，这些其他信息包括操作数，以及一些其他的标示符，例如‘#’，‘.’等，得到一个应用程序的smali操作符序列。smali文件中，每条语句的格式为“操作符操作数”，操作数为具体操作的变量名或者寄存器的名字，可以通过字符串处理的方式自动完成，这一步之后，得到一个smali操作符序列文本，其中每一行是一个操作符，其中某些操作符可能与我们选定的关键词匹配。

C.生成关键词上下文频率矩阵流程，包括如下步骤：

C1.构造关键词上下文频率矩阵Max，这是一个三维矩阵，大小为sz_kv*sz_hash*sz_hash，其中sz_kv为选定的关键词向量的大小，已确定为15，sz_hash是下一步中采取的哈希算法结果的取值范围大小，根据经验性结果，将其设置为67，将Max的每一位初始化为0；

C2.根据选定的关键词向量，对每一个关键词（在关键词向量中对应下标为i）在上一步得到的smali操作符序列中的每一次出现，采用BKDRHash算法（BKDRHash算法参见http://www.nocow.cn/index.php/BKDRHash；这里也可以采用其它字符串哈希算法，如ELFHASH，SDBMHash，RSHash等），将其上文的K条语句和下文的K条语句分别映射为整数K1和K2，例如根据字符串匹配，检测到对应关键词向量下标i=3的关键词invoke-static的一次出现，其上下文为如下指令序列，

line

try_start_0

iget_object

invoke-static

move-result-object

const-string

invoke-virtual;

根据BKDRHash算法，分别对上下文做hash运算，得到K1=17，K2=33;

C3.增加特征矩阵对应位置Max[i][K1][K2]计数，在本例子中，执行Max[3][17][33]++的操作。

D.重打包结果判断流程，执行如下操作：

D1.对给定的安卓应用程序，采用特定算法计算其关键词上下文频率矩阵的相似度，以此作为标准，对两个安卓应用程序进行两两比较，假设根据前面的类似步骤，我们得到了Autodeskzhaopiantexiaochulihanhuaban_Pixlr_o_matic_V2.1.2_mumayi_1f341.apk这一应用程序以及AutodeskzhaopianlvjingPixlr_o_matic_V2.2.1_mumayi_ac32a.apk这一应用程序的关键词上下文频率矩阵，设两个矩阵分别为Max1，Max2，对两个矩阵的的每一位，分别用Max1[i][j][k]和Max2[i][j][k]表示，计算这两个数的最小值Min[i][j][k]，用score来表示其相似度得分，score=200*ΣMin[i][j][k]/Σ(Max1[i][j][k]+Max2[i][j][k])，根据运算，score=86.8871；

D2.将关键词上下文频率矩阵的相似度计算结果，即步骤D1中的score，超过某个阈值的安卓应用程序聚类，根据经验性结果，阈值选为70时最优，这里86.8871大于70，因此判断这两个安卓应用程序可能存在重打包问题。

D3.结合前面得到的作者签名信息，进一步对结果进行筛选排查，发现这两个应用程序的作者信息不同，进一步确定这两个应用程序为重打包应用程序。

Claims

1.一种基于关键词上下文频率矩阵的应用重打包辨别方法，应用于安卓系统，其特征是，包括如下步骤：

A.对应用程序文件进行预处理，将二进制代码转换为smali代码文件、同时提取应用程序的作者签名信息，构造应用程序关键词向量，关键词的选择依据是，选取出现频率高的语句；关键词在语义上没有明显的重复，即关键词集合覆盖不同功能的语句；选取语义上重要的指令；

B.对smali代码文件进行处理，生成smali操作符序列；

C.生成关键词上下文频率矩阵；

2.如权利要求1所述的应用重打包辨别方法，其特征是，步骤A包括：

A2.使用现有工具，将二进制代码转换为smali代码文件；

A3.使用现有工具，从相应文件提取作者签名内容；

A4.构造应用程序关键词向量。

3.如权利要求1所述的应用重打包辨别方法，其特征是，步骤B包括：

B1.对步骤A中得到的smali代码文件进行处理，去掉第三方库文件；

4.如权利要求1所述的应用重打包辨别方法，其特征是，步骤C包括：

C1.构造关键词上下文频率矩阵Max；

C3.增加特征矩阵对应位置Max[i][K1][K2]计数。

5.如权利要求1所述的应用重打包辨别方法，其特征是，步骤D包括：

D2.将关键词上下文频率矩阵的相似度计算结果超过指定阈值的安卓应用程序聚类，认为这一类的安卓应用程序可能存在重打包问题。

6.如权利要求5所述的应用重打包辨别方法，其特征是，步骤D进一步包括：

7.如权利要求5所述的应用重打包辨别方法，其特征是，步骤D1中，计算其关键词上下文频率矩阵的相似度的方法为：设原应用程序和待判断的应用程序的关键词上下文频率矩阵分别为Max1，Max2，对两个矩阵的每一位，分别用Max1[i][j][k]和Max2[i][j][k]表示，计算这两个数的最小值Min[i][j][k]，用score来表示其相似度得分，score＝200*ΣMin[i][j][k]/Σ(Max1[i][j][k]+Max2[i][j][k])。

8.如权利要求5所述的应用重打包辨别方法，其特征是，步骤D2中，所述的阈值为70。

9.如权利要求2所述的应用重打包辨别方法，其特征是，步骤A4中，选择如下指令对应的操作符作为关键词：转移指令、函数调用指令、比较指令、声明类指令、运算指令、传送指令、抛出异常指令。

10.如权利要求2所述的应用重打包辨别方法，其特征是，步骤A4中，选择如下操作符作为关键词：if、goto、invoke_virtual、invoke_static、invoke_direct、add-int/lit8、move_result_object、new-array、const/4、const/16、const-string、throw、new-instance、cmpl-float、and-int/lit1。