本发明公开了一种抗加固的Android平台克隆应用程序快速检测方法，包括预处理阶段和精确检测两个阶段。在预处理阶段，通过使用自然语言处理技术从应用程序的功能描述中提取关键字构造向量，利用改进的基于平衡二叉树的搜索方法快速查找功能相似的可疑克隆应用程序对。在正式检测阶段，本发明提出了一种基于界面布局特征且完全独立于源代码的应用程序胎记，能够有效抵抗加固技术的影响，最后使用基于树的编辑距离的相似度计算方法，能够精确计算出可疑克隆程序对之间的相似性。本发明能够有效抵抗加固技术的干扰，同时实现克隆应用的快速检测，具有很强的实用性。
1.一种抗加固的Android平台克隆应用程序快速检测方法，其特征在于，包括以下步骤：
2)输入目标应用的功能描述，利用Stanford Parser提取动态维度的关键字向量；
3)在平衡二叉树索引中利用关键字向量快速搜索功能描述相似的应用程序，加入备选集合；具体实现过程包括：i.输入平衡二叉树索引节点；
ii.若当前节点是非叶子节点，且若相关性计算得分RScore(u.V,Q)大于阈值γ，则计算该节点左右子节点的相关性得分，然后按照子节点得分高低，依次递归执行搜索操作；否则，终止当前搜索；若当前节点u是叶子节点，且若相关性得分RScore(u.V,Q)大于阈值γ，则在结果集合RList中插入新元素；u.V＝u’.V∪u”.V，u’和u”为节点集合CurrentNodeSet集合中的两个叶子节点；V为关键字向量集合；
iii.返回结果集合RList，即得到初步筛选的结果集合；Q为目标关键字向量；
4)对所述备选集合中的应用程序分别进行解压缩以及转换操作，得到/res/layout目录下的所有的XML格式布局文件；
5)对所述布局文件进行过滤，筛除第三方库引入的外部布局文件；
6)将过滤后的布局文件转化为对应结构的布局树，加载到内存中；
7)对加载的布局树依次执行归并操作，从根节点开始，按层次将不同布局树中的相同元素进行合并，生成最终的程序胎记；
8)使用基于树的编辑距离的计算方法对最终生成的程序胎记的相似性进行计算，相似度超过阈值的程序对存在克隆问题；
步骤1)中，平衡二叉树索引的构造方法包括以下步骤：
(2)针对关键字向量集合V中的任意向量Vi，构造叶子节点ui，其中ui.V＝Vi；
(3)将节点ui插入到节点集合CurrentNodeSet中；
(4)若节点集合CurrentNodeSet中存在未处理节点时，循环执行步骤5)～步骤7)；
(5)任意选取CurrentNodeSet集合中两个叶子节点u’和u”，根据叶子节点u’和u”构造节点u作为父节点，其中u.V＝u’.V∪u”.V；
(6)将父节点u插入到暂存集合TempNodeSet中；
(7)将TempNodeSet集合中的节点全部插入CurrentNodeSet集合中，清除TempNodeSet中的数据；
(8)判断CurrentNodeSet集合大小为1时，结束循环；返回CurrentNodeSet集合中唯一节点作为根节点。
2.根据权利要求1所述的抗加固的Android平台克隆应用程序快速检测方法，其特征在于，步骤2)中，使用基于贪心的深度优先搜索算法在索引树中快速搜索功能描述相似的应用程序。
3.根据权利要求1所述的抗加固的Android平台克隆应用程序快速检测方法，其特征在于，阈值γ＝0.75。
4.根据权利要求1所述的抗加固的Android平台克隆应用程序快速检测方法，其特征在于，步骤7)中，按层次将不同布局树中的相同元素进行合并的具体实现过程包括：
1)对于两棵布局树lt1和lt2，初始化参数depth为布局树lt1与lt2高度的最小值加1；
初始化匹配树的根节点为root；设置根节点root左子树为lt1；设置根节点root右子树为lt2；
2)从根节点root开始，将匹配树在第i层的所有子节点添加到集合Ni中；
3)按照贪心规则从集合Ni中搜索同构节点对(va,vb)；
4)将节点vb的全部子节点复制到同构节点va下，删除节点vb；
5.根据权利要求1所述的抗加固的Android平台克隆应用程序快速检测方法，其特征在于，步骤8)中，对最终生成的程序胎记的相似性进行计算的具体实现过程包括：每个应用程序对应生成一个树形结构的程序胎记b，使用基于树的编辑距离的相似度计算方法计算出两个程序胎记bi和bj之间的距离Tedij，经过归一化处理后得到相似度rij，如果rij超过了相似性阈值θ,则确认原应用程序之间存在克隆关系。
6.根据权利要求5所述的抗加固的Android平台克隆应用程序快速检测方法，其特征在于，相似性阈值θ＝0.9。
一种抗加固的Android平台克隆应用程序快速检测方法
技术领域
[0001] 本发明涉及移动安全、克隆软件检测领域，特别是一种抗加固的Android平台克隆应用程序快速检测方法。
背景技术
[0002] Android逐渐占据了移动市场的主导地位，但同时也吸引了大量的恶意攻击。其中大部分的恶意程序通过克隆已有应用的方式进行快速传播，不仅对用户安全造成了威胁，同时也影响了合法开发者的收入。目前，针对Android平台克隆应用的检测方法可以分为两类：一类是基于代码重用的检测方法：通过对程序代码进行静态分析，构造特定的程序胎记如程序依赖图、程序流程图等，完成相似度的计算；另一类则是基于界面相似的检测方法：通过比较用户界面的相似性，如资源文件、布局特征等，进行克隆检测。
[0003] 上述克隆检测方法存在一些缺陷使得它们不能得到广泛的应用。其中，基于代码重用的检测方法依赖于对代码特征的分析，而目前越来越多的克隆攻击者使用加固技术来隐藏克隆程序中的DEX代码文件，使得基于代码重用的检测方法失效；而基于界面特征的方法在界面特征提取以及执行相似度计算时的时间开销大，具有很大的局限性。
发明内容
[0004] 本发明旨在提供一种抗加固的Android平台克隆应用程序快速检测方法，有效规避代码加固技术的影响，使得克隆检测方法更具有实用性。
[0005] 为解决上述技术问题，本发明所采用的技术方案是：一种抗加固的Android平台克隆应用程序快速检测方法，包括以下步骤：
[0006] 1)构造基于关键字向量的平衡二叉树索引；
[0007] 2)输入目标应用的功能描述，利用Stanford Parser提取动态维度的关键字向量；
[0008] 3)在平衡二叉树索引中利用关键字向量快速搜索功能描述相似的应用程序，加入备选集合；
[0009] 4)对所述备选集合中的应用程序分别进行解压缩以及转换操作，得到/res/layout目录下的所有的XML格式布局文件；
[0010] 5)对所述布局文件进行过滤，筛除第三方库引入的外部布局文件；
[0011] 6)将过滤后的布局文件转化为对应结构的布局树，加载到内存中；
[0012] 7)对加载的布局树依次执行归并操作，从根节点开始，按层次将不同布局树中的相同元素进行合并，生成最终的程序胎记；
[0013] 8)使用基于树的编辑距离的计算方法对最终生成的程序胎记的相似性进行计算，相似度超过阈值的程序对存在克隆问题。
[0014] 步骤1)中，平衡二叉树索引的构造方法包括以下步骤：
[0015] 1)输入n个应用程序对应的关键字向量集合V；
[0016] 2)针对关键字向量集合V中的任意向量Vi，构造叶子节点ui，其中ui.V＝Vi；
[0017] 3)将节点ui插入到节点集合CurrentNodeSet中；
[0018] 4)若节点集合CurrentNodeSet中存在未处理节点时，循环执行步骤5)～步骤7)；
[0019] 5)任意选取CurrentNodeSet集合中两个叶子节点u’和u”，根据叶子节点u’和u’’构造节点u作为父节点，其中u.V＝u’.V∪u”.V；
[0020] 6)将父节点u插入到暂存集合TempNodeSet中；
[0021] 7)将TempNodeSet集合中的节点全部插入CurrentNodeSet集合中，清除TempNodeSet中的数据；
[0022] 8)判断CurrentNodeSet集合大小为1时，结束循环；返回CurrentNodeSet集合中唯一节点作为根节点。
[0023] 步骤2)中，使用基于贪心的深度优先搜索算法在索引树中快速搜索功能描述相似的应用程序。
[0024] 步骤3)的具体实现过程包括：
[0025] 1)输入平衡二叉树索引节点；
[0026] 2)若当前节点是非叶子节点，且若相关性计算得分RScore(u.V,Q)大于阈值γ，则计算该节点左右子节点的相关性得分，然后按照子节点得分高低，依次递归执行搜索操作；否则，终止当前搜索；若当前节点u是叶子节点，且若相关性得分RScore(u.V,Q)大于阈值γ，则在结果集合RList中插入新元素；
[0027] 3)返回结果集合RList，即得到初步筛选的结果集合。
[0028] 阈值γ＝0.75。
[0029] 步骤7)中，按层次将不同布局树中的相同元素进行合并的具体实现过程包括：
[0030] 1)对于两棵布局树lt1和lt2，初始化参数depth为布局树lt1与lt2高度的最小值加1；初始化匹配树的根节点为root；设置根节点root左子树为lt1；设置根节点root右子树为lt2；
[0031] 2)从根节点root开始，将匹配树在第i层的所有子节点添加到集合Ni中；
[0032] 3)按照贪心规则从集合Ni中搜索同构节点对(va,vb)；
[0033] 4)将节点vb的全部子节点复制到同构节点va下，删除节点vb；
[0034] 5)返回匹配树的根节点root。
[0035] 步骤8)中，采用基于树的编辑距离的计算方法对最终生成的程序胎记的相似性进行计算。
[0036] 对最终生成的程序胎记的相似性进行计算的具体实现过程包括：每个应用程序对应生成一个树形结构的程序胎记b，使用基于树的编辑距离的相似度计算方法计算出两个程序胎记bi和bj之间的距离Tedij，经过归一化处理后得到相似度rij，如果rij超过了相似性阈值θ,则确认原应用程序之间存在克隆关系。
[0037] 相似性阈值θ＝0.9。
[0038] 与现有技术相比，本发明所具有的有益效果为：本发明利用应用的界面布局特征进行程序胎记的构造，因此能够有效规避代码加固技术的影响；同时在预处理阶段，利用克隆应用之间存在的功能相似性，通过构造树形索引的方式，完成可疑克隆应用的快速筛选，有效提高了检测方法的检测速度，使得克隆检测方法更具有实用性。
附图说明
[0039] 图1为本发明方法流程图；
[0040] 图2为基于统计的外部文件过滤方法的流程图。
具体实施方式
[0041] 如图1所示，本发明包括以下步骤：
[0042] 1.初始化：构造基于关键字向量的平衡二叉树索引；
[0043] 2.输入目标应用的功能描述，利用Stanford Parser提取动态维度的关键字向量；
[0044] 3.使用基于贪心的深度优先搜索算法，在索引树中快速搜索功能描述相似的应用程序，加入备选集合；
[0045] 4.对得到的可疑克隆应用程序集合中的应用程序分别进行解压缩以及各式转换操作，得到/res/layout目录下的所有的XML格式布局文件；
[0046] 5.对布局文件进行过滤，使用基于统计的方法筛除第三方库引入的外部布局文件；
[0047] 6.将过滤后的布局文件转化为对应结构的布局树，加载到内存中；
[0048] 7.对加载的布局树依次执行归并操作，采取简单贪心策略从根节点开始，按层次将不同布局树中的相同元素进行合并，生成最终的程序胎记；
[0049] 8.使用基于树的编辑距离(Tree edit distance)的计算方法对最终生成的程序胎记的相似性进行计算，相似度超过阈值的程序对存在克隆问题。
[0050] 本发明提出了一种抗加固的Android克隆应用快速检测方法，该方法在预处理阶段利用克隆程序功能相似性实现了可疑程序的快速搜索，降低后续检测算法的计算量，从而提高了检测方法的整体检测速度。在正式检测阶段，通过构造完全基于界面布局特征的程序胎记来完成相似性计算，从而能够有效抵抗代码加固技术的影响。预处理阶段的操作包括关键字提取、索引树构建以及关键字向量快速搜索；正式检测阶段的操作包括布局文件提取、外部文件过滤、程序胎记构造以及相似性计算。
[0051] 关键字提取：对于输入的应用程序功能描述，我们使用自然语言处理工具对原始描述进行预处理，只提取与应用功能最相关的一组名词性的关键字。
[0052] 索引树构建：在原始应用程序集合中，为每个应用程序提取出一个动态维度的关键字向量，作为索引树的叶子节点，然后以递归的方式自底向上，两两逐层进行合并后，构造出一棵基于关键字的平衡二叉树，用来保存所有的关键字向量。具体算法如下：
[0053]
[0054]
[0055] 关键字向量快速搜索：从索引树的耿介点开始执行关键字向量的搜索，计算当前节点左右子节点中保存的特征向量与目标向量间的相关，选取相关性超过特定阈值γ的子节点递归进行搜索，当搜索到叶子节点或子节点相关性低于阈值γ时终止搜索。具体算法如下所示，其中RScore(V1,V2)函数返回向量V1和V2间的相关性：
[0056]
[0057] 布局文件提取过滤：输入一个Android应用程序，利用文件解压缩命令对安装文件进行解压后，直接得到二进制格式的布局文件；利用格式转换工具可以将二进制布局文件转换为可读的XML格式文档。。
[0058] 外部文件过滤：对于提取得到的所有布局文件，计算出文件的MD5哈希值，依次与数据库中的保存的MD5值进行比较，如果MD5值已存在且对应文件出现的频率大于特定阈值时，则认定该布局文件为外部引入的文件。基于统计的外部文件过滤方法的流程如下：
[0059] 程序胎记构造：从过滤后的布局文档中构造出对应的布局树载入内存，然后使用基于贪心的宽度优先的归并(GWFM)规则依次对布局树进行归并操作，最终合并生成一个唯一的树形程序胎记。归并生成的程序胎记与应用界面布局特征之间存在唯一对应关系，布局树的归并顺序不会影响程序胎记的最终结构。基于贪心的归并算法如下所示：
[0060]
[0061] 相似性计算：每个应用程序对应生成一个树形结构的程序胎记b，使用基于树的编辑距离(Tree Edit Distance)的相似度计算方法计算出两个程序胎记bi和bj之间的距离Tedij，经过归一化处理后得到相似度rij，如果rij超过了相似性阈值θ,则确认原应用程序之间存在克隆关系。
