一种基于对象引用图的Android手机恶意软件检测方法，本发明涉及Android手机恶意软件检测方法。本发明是要解决内核级别监控方法涉及内核改动，系统检测花销大；仅提供有限系统服务的沙箱技术易被攻击；控制流方法易受代码混淆攻击，基于API调用建立动态胎记的方法需要较多API调用具有较大局限性以及ORGB提取方法和VF2算法检测效率的问题而提出的一种基于对象引用图的Android手机恶意软件检测方法。该方法是通过1提取对象引用关系图ORG；2得到恶意程序的ORGB；3筛选出未知程序的可能类别；4确定未知程序为某类匹配的恶意程序等步骤实现的。本发明应用于Android手机恶意软件检测领域。
1.一种基于对象引用图的Android手机恶意软件检测方法，其特征在于具体是按照以下步骤进行的：步骤一、将Android平台下已分类的恶意程序分别运行，从恶意程序堆内存中提取对象之间对应的引用关系图ORG；其中，ORG为对象引用图是一个二元组ORG＝(N，E)，N是图中节点的集合，N中的每一个元素表示的是产生对象的类；E∈N×N，是对象之间引用关系的集合；对象为ORG图中的节点，ORG包括用户类、系统类以及用户类和系统类的引用关系；
步骤二、利用改进的VF2算法将同一类恶意程序的所有引用关系图ORG进行子图同构，得到该类恶意程序中所有的ORG的最大公共部分即恶意程序的ORGB；其中，ORGB为引用关系胎记图；
步骤三、根据步骤一的方法提取未知程序的ORG，根据未知程序请求的应用权限和系统类，利用类别判断方法对未知程序类别进行筛选，筛选出未知程序的可能类别；
步骤四、选择未知程序的可能类别所对应的ORGB，利用改进的VF2算法依次将所对应的ORGB与未知程序的ORG进行子图同构检测，若某个ORGB与待检测ORG是子图同构关系，则表明未知程序为某类匹配的恶意程序；即完成了一种基于对象引用图的Android手机恶意软件检测方法。
2.根据权利要求1所述一种基于对象引用图的Android手机恶意软件检测方法，其特征在于：步骤一中从恶意程序堆内存中提取对象之间对应的引用关系图ORG的时机具体为：(1)随宿主程序启动；
3.根据权利要求1所述一种基于对象引用图的Android手机恶意软件检测方法，其特征在于：步骤一中将Android平台下已分类的恶意程序分别运行，从恶意程序堆内存中提取对象之间对应的引用关系图ORG具体过程：(1)对于Android2.3版本以下的系统使用kill-10processID得到进程的堆内存信息文件；android2.3版本以上的系统通过对堆数据监控的dumpheap工具获取堆内存信息文件；
(2)利用以JHAT为基础的分析工具AHAT，对堆内存信息文件进行格式转换；其中，堆内存文件的格式要求与JAVA的保持相同；
其中，AHAT整体结构有四个模块：Model、Parser、Util以及外界调用接口；
(3)对经过转换后的文件进行分析，利用分析工具AHAT提取引用关系图ORG。
4.根据权利要求1所述一种基于对象引用图的Android手机恶意软件检测方法，其特征在于：步骤二中改进的VF2算法具体为：
1)假设已知图G1(N1,E1)和G2(N2,E2)，寻找这两图G1和G2之间的同构映射M；M表示的是图G1中的节点n和图G2中的节点m之间的对应关系；其中，寻找映射M的过程是通过状态空间表示SSR来描述；G1表示引用关系图ORG，G2表示ORGB为引用关系胎记图，N1表示G1中的顶点集，E1表示G1中的边集，N2表示G2中的顶点集，E2表示表示G2中的边集；G1为G1(N1,E1)，G2为G2(N2,E2)；
2)匹配过程中的每一个状态s都是一个局部映射，用M(s)来表示，M(s)是M的一个子集；
G1(s)表示映射M(s)与G1相关的子图，G2(s)表示映射M(s)与G2相关的子图；N1(s)表示G1(s)中的顶点集，N2(s)表示G2(s)中的顶点集，E1(s)表示G1(s)中的边集，E2(s)分别表示G2(s)中的边集；
M(sp)是sp状态下的同构映射；N1(sp)是sp状态下G1中已匹配的节点集合；N2(sp)是sp状态下G2中已匹配的节点集合；E1(sp)是sp状态下G1中已匹配的边集合；E2(sp)是sp状态下G2中已匹配的边集合；
3)将名称相同的类名进行优先匹配改进为如果两个图中存在类名相同的节点对，并且这些类名属于系统类，则将这些节点对直接匹配得到名称相同的匹配节点加入到同构映射M作为同构映射M的初始状态；
4)名称不同的类名进行匹配，VF2算法在匹配过程中会产生多个状态，从一个状态s转换为另一个状态s’，即实际上在父亲节点s的基础上加入一对新的匹配节点得到孩子节点s’，通过在同构映射M中加入不同的节点对，状态s会转换为多个状态即多个孩子节点；
(1)T1out(s)：表示的是G1中一个顶点集合，是G1(s)中顶点的后继结点；
(2)T2out(s)：表示的是G2中一个顶点集合，是G2(s)中顶点的后继结点；
(3)T1in(s)：表示的是G1中一个顶点集合，是G1(s)中顶点的前驱结点；
(4)T2 (s)：表示的是G2中一个顶点集合，是G2(s)中顶点的前驱结点；
6)根据变量定义对H(s)进行选取的步骤如下所示：
(1)如果T1out(s)和T2out(s)不是空集，那么H(s)＝T1out(s)×T2out(s)；
(2)如果T1out(s)和T2out(s)都是空集，但是T1in(s)和T1in(s)不是空集，那么H(s)＝T1in(s) ×T2in(s)；
(3)如果T1out(s)，T2out(s)，T1in(s)和T2in(s)都是空集，那么H(s)＝(N1-T1out(s)-T1in(s))×(N2-T2out(s)-T2in(s))；H(s)是s状态的候选集合；
(4)其他情况，对状态s进行搜索剪枝；是指如果T1out(s)和T2out(s)之一为空集，或者T1in(s)和T2in(s)之一为空集，将状态s的搜索剪枝；
7)对于SSR中的每一个节点，首先计算出该节点对应的中间状态s的候选节点对，并将候选节点对H(s)排序，将与ORGB节点的度更相近的节点优先；然后递归的对H(s)中每个节点对进行搜索；其中，H(s)为状态s的候选节点对集；
采用语法可行性规则，用Fsyn(s,n,m)来表示；VF2算法中定义了5个语法可行性规则；
(Card(Succ(G1,n)∩T1in(s))≥Card(Succ(G2,m)∩T2in(s)))∧(Card(Pred(G1,n)∩T1in(s))≥Card(Pred(G2,m)∩T2in(s)))规则4：Rout(s,n,m)
(Card(Succ(G1,n)∩T1out(s))≥Card(Succ(G2,m)∩T2out(s)))∧(Card(Pred(G1,n)∩T1out(s))≥Card(Pred(G2,m)∩T2out(s)))规则5：Rnew(s,n,m)
(Card(N1'(s)∩Pred(G1,n))≥Card(N2'(s)∩Pred(G2,n)))∧(Card(N1'(s)∩Succ(G1,n))≥Card(N2'(s)∩Succ(G2,n)))其中，Fsyn(s,n,m)＝Rpred∧Rsucc∧Rin∧Rout∧Rnew，用Pred(G,n)代表图G中n的前in out驱节点的集合，用Succ(G，n)表示图G中n的后继节点的集合；同时使用T1(s)＝T1 (s)∨T1(s)，并使用N1'(s)＝N1–M1(s)–T1(s)；T2(s)和N2’(s)的定义类似为T2(s)＝T2in(s)∨T1out(s)和N2’(s)＝N2–M2(s)–T2(s)；Card(A)表示集合A的基数，即集合中元素的个数；n'是G1里不同于n的另一个节点，m'是G2里不同于m的一个节点；M1(s)指G1在s状态下的同构映射，M2(s)指G2在s状态下的同构映射，N1(s)是在s状态下G1中已匹配的节点集合，也就是在s状态下，用G2的节点集合N2减去已匹配的节点结合M2(s)再减去与已匹配节点有关联的节点结合T2(s)所剩下的节点；
当新加入的节点对符合这5条可行性规则后，则继续对新加入节点对后的状态进行搜索，在s的基础上加入一对新的匹配节点；通过加入不同的节点对，状态s会转换为多个状态；不断产生的新的状态空间可以使用树的结构来描述即SSR来描述；
8)利用树的结构即SSR来描述，找到最终的同构映射M；搜索所有的SSR来找到最终的同构映射M的终止条件为针对不同规模的ORGB设置自适应的调节参数λ达到80％～100％的节点对匹配。
5.根据权利要求1所述一种基于对象引用图的Android手机恶意软件检测方法，其特征在于：步骤二中利用改进的VF2算法将同一类恶意程序的所有引用关系图ORG进行子图同构，得到该类恶意程序中所有的ORG的最大公共部分即恶意程序的ORGB具体过程为：(1)去掉ORG图中的用户类孤立点的包名前缀后进行名称匹配，得到ORG图中的用户类孤立点公共图；其中，ORG图中的用户类孤立点是指存在于ORG图中的，与系统类以及其他用户类不存在引用关系的用户类；
(2)利用改进的VF2算法对去掉用户类孤立点的ORG图进行子图同构得到最大公共子图；
(3)将用户类孤立点公共图和最大公共子图组合作为该类别恶意程序的ORGB。
6.根据权利要求1所述一种基于对象引用图的Android手机恶意软件检测方法，其特征在于：步骤二中ORGB具体为：定义ORGB令p和q为两个程序或者程序的组件，令I为p或q的输入；ORGp是以I为输入，p运行时的对象引用图和ORGq是以I为输入，q运行时的对象引用图；令ORGBp为ORGp的子图；
当且仅当以下条件时，ORGBp是p的动态胎记得到满足：
(1)如果q是p的一部分，那么必有ORGBp子图同构于ORGq；
(2)如果q不是p的部分，那么必有ORGBp子图不同构于ORGq。
7.根据权利要求1所述一种基于对象引用图的Android手机恶意软件检测方法，其特征在于：步骤三中根据步骤一的方法提取未知程序的ORG，根据未知程序请求的应用权限和系统类，利用类别判断方法未知程序类别进行筛选，筛选出未知程序的可能类别具体过程为：选择程序请求的应用权限和程序运行过程中调用的系统类作为类别判断的依据；
Android系统要求Android应用需要在调用系统功能前申请权限；
(1)根据申请权限最终得到恶意程序类权限特征文件；其中，权限特征文件中包含该类恶意程序所包含的所有恶意程序的权限集合；此外，每一个权限均包含量化权限贡献度与区分度的数值；其中，区分度是指权限在所有恶意程序类权限特征文件中出现的频数的倒数；
(2)对于未知种类的未知程序进行分类时，首先得到未知程序的权限集合；再将未知程序的权限集合依次与步骤(1)得到的恶意程序类权限特征文件做匹配求和即将恶意程序类权限特征文件中出现在未知程序权限集合中的权限的贡献度*区分度的乘积相加，得到与各个恶意程序类权限特征文件匹配的结果，将匹配的结果排序筛选出未知程序的可能类别。
一种基于对象引用图的Android手机恶意软件检测方法
技术领域
[0001] 本发明涉及Android手机恶意软件检测技术，特别涉及一种基于对象引用图的Android手机恶意软件检测方法。
背景技术
[0002] 现有技术包括采用内核级别的监控方式，对Android程序的系统调用和信息进行记录。基于异常行为检测的Crowdroid系统，该系统是基于异常行为检测的分类器，采用的是轻量级的C/S架构。沙箱技术，这是分析Android恶意代码新的发展方向，有很大的研究空间。G.MylesandC.Collberg首先提出动态胎记，他们利用程序在运行过程中完整的控制流来识别软件。Tamadaetal提出了两种基于API函数调用建立动态胎记的方法。Wangetal.提出了基于系统调用依赖关系建立动态胎记的方法。通过程序运行时系统调用之间的依赖关系建立一张系统调用依赖关系(SCDG)。在SCDG中，每一个系统调用作为节点，系统调用之间的依赖关系(即存在数据交流)作为边。SCDG胎记作为整个SCDG的一个子图来识别程序。通过实验测试，该方法对于不同的编译选项，不同编译器以及代码混淆的攻击都具有很好的健壮性。
[0003] 通过内核级别监控识别恶意程序的方法实现难度较大，涉及系统底层内核的改动，并且需要较大的系统检测花销。而沙箱技术还不成熟，沙箱模拟操作系统为程序提供服务，但是沙箱能够提供的服务是有限的，恶意程序可以通过调用沙箱未提供的服务等方式使沙箱崩溃。
[0004] 在应对保留程序语义的攻击时，控制流方法比静态胎记技术更加有效。但如果程序受到代码混淆攻击，该技术就会失效。而且由于程序控制流庞大，对于较大的程序很难实现。基于API函数调用建立动态胎记的方法最大的问题是需要足够多的API调用，所以当程序的API数量不足时，该方法就无法建立有效的动态胎记，因此有较大的局限性。
[0005] 《基于对象引用关系图的Android恶意代码检测的研究》没有说明ORGB的提取过程，其仅仅指出“ORGB的建立需要一个恶意代码类的列表来过滤所得到的类。”而ORGB在系统进行检测时具有关键作用，ORGB提取效果的好坏对系统最终的检测漏报率，误报率有决定性的影响。
[0006] 《基于对象引用关系图的Android恶意代码检测的研究》中在检测过程中所使用的VF2算法无法在真实环境中应用，因为VF2算法的运行时间随着ORGB图中节点的数量成指数级增长，对于常见的图的一次匹配可能就需要10小时的时间。而这下实际应用环境中是无法接受的。
发明内容
[0007] 本发明的目的是为了解决核级别监控识别恶意程序的方法涉及系统底层内核的改动，需要较大的系统检测花销、沙箱提供服务、控制流方法程序受到代码混淆攻击、ORGB图中节点的数量成指数级增长没有说明ORGB的提取过程以及基于API函数调用建立动态胎记的方法需要足够多的API调用具有较大的局限性的问题而提出的一种基于对象引用图的Android手机恶意软件检测方法。
[0008] 上述的发明目的是通过以下技术方案实现的：
[0009] 步骤一、将Android平台下已分类的恶意程序分别运行，从恶意程序堆内存中提取对象之间对应的引用关系图ORG；其中，ORG为对象引用图是一个二元组ORG＝(N，E)，N是图中节点的集合，N中的每一个元素表示的是产生对象的类；E∈N×N，是对象之间引用关系的集合；对象为ORG图中的节点，边代表对象之间存在引用关系；ORG包括用户类、系统类以及用户类和系统类的引用关系；
[0010] 步骤二、利用改进的VF2算法将同一类恶意程序的所有引用关系图ORG进行子图同构，得到该类恶意程序中所有的ORG的最大公共部分即恶意程序的ORGB；其中，ORGB为引用关系胎记图；
[0011] 步骤三、根据步骤一的方法提取未知程序的ORG，根据未知程序请求的应用权限和系统类，利用类别判断方法对未知程序类别进行筛选，筛选出未知程序的可能类别；
[0012] 步骤四、选择未知程序的可能类别所对应的ORGB，利用改进的VF2算法依次将所对应的ORGB与未知程序的ORG进行子图同构检测，若某个ORGB与待检测ORG是子图同构关系，则表明未知程序为某类匹配的恶意程序；即完成了一种基于对象引用图的Android手机恶意软件检测方法。
[0013] 发明效果
[0014] 本发明提出基于对象引用图的恶意软件检测方法。通过提取程序运行过程中内存中对象的引用关系，将其作为程序的胎记。通过比对程序的胎记与恶意程序库中恶意程序胎记，判断程序是否为恶意程序。这种方法相对基于API调用通用性更好。
[0015] Android系统是当前最流行的移动设备操作系统之一。Android系统的开放性一方面为其快速的发展提供了强大的助力，另一方面也间接的有利于恶意软件的开发。根据谷歌最新发布的2014年Android安全报告，2014年被恶意软件感染的Android智能设备近1％。针对Android手机恶意软件的检测方法有静态检测与动态检测两种。静态检测方法准确率高，检测速度快，但无法应对代码混淆及加壳等攻击手段。动态检测方法能够应对代码混淆及加壳等攻击手段，但现有的动态检测方法仍存在一些问题。所以我们提出了基于对象引用图的动态检测方法。
[0016] 图3是使用上述方法对26类726个程序进行分类的结果。图3看出，上述方法的在我们把范围扩展到前五位时准确率已经达到了95％。图4展示的是不同类别各自的分类准确率，可以看到多数类别的准确率都很高，在考虑前五位的情况下接近100％。
[0017] 本发明方法不涉及系统底层的改动，系统开销小；本发明方法使用的是对象引用图ORG能够避免代码混淆的攻击；本方法使用的是程序运行过程中在堆内存中存放的对象信息，所以相比API调用具有更广泛的适用性。
[0018] 本发明找到了能够在所有版本的Android系统提取ORG的方法；具体方法在权力要求说明书中的第三部分ORG提取方法中做出了介绍。通过我们的方法，能够在目前所有版本的Android系统中提取ORG。
[0019] 本发明提取了使用改进的VF2算法提取ORGB的方法，具体方法在权力要求说明书中第五部分ORGB的提取有具体介绍。对于根据上述方法得到的ORGB的正确性，一方面通过实验比对验证确认，另一方面，系统最终的检测结果也能够对其进行证明。
[0020] 本发明首先提取基于应用权限与系统类的类别判断方法快速的锁定待检测程序可能的类别，排除无关类别的干扰，减少需要匹配的次数，该方法的具体介绍在权力要求说明书的第七部分，说明书附图中的图3是使用上述方法对26类726个程序进行分类的结果。从表中可以看出，上述方法的在我们把范围扩展到前五位时准确率已经达到了95％。说明书附图中的图4展示的是不同类别各自的分类准确率，可以看到多数类别的准确率都很高，在考虑前五位的情况下接近100％。而有少数几类的准确率较低，例如，Asroot，BaseBridge，通过分析发现其程序所需权限较少，有的程序仅包含一个权限，并且不同程序间的权限缺乏共性；然后，我们提出适用于恶意程序检测系统的改进的VF2算法，该算法能够极大的减少算法的运行时间，使系统能够实际的应用目前系统在检测时的平均检测时间为10s，最大检测时间<30s，最小检测时间<1s。
附图说明
[0021] 图1为具体实施方式三提出的ORG文件提取流程图；
[0022] 图2为具体实施方式五提出的ORGB提取示意图，其中，Com.A.a1、Com.A.c1、Com.A.d1、Com.A.f、Com.B.a1、Com.B.b1、Com.B.c1、Com.B.d1、Com.B.f、a、c、d和f均为对象名称；
[0023] 图3为具体实施方式一提出的使用权限进行分类的结果示意图；
[0024] 图4为具体实施方式七提出的不同类别前五位的分类准确率示意图；
[0025] 图5为具体实施方式四提出的修改前搜索树的一部分；其中，A.b.c、b.c.d、Int、long、java.class和com.a.b均为对象名称；
[0026] 图6为具体实施方式四提出的修改后搜索树的一部分；其中，A.b.c、b.c.d、Int、long、java.class和com.a.b均为对象名称；
[0027] 图7为具体实施方式四提出的ORGB图，其中，Bingder、X、A、B以及C指代对象名称；
[0028] 图8为具体实施方式四提出的待匹配ORG图，其中，Linker、Activity、X、A、B、C、D和E指代对象名称；
[0029] 图9为具体实施方式一提出的一种基于对象引用图的Android手机恶意软件检测方法流程图；
[0030] 图10为具体实施方式三提出的运行在Android上的AHAT流程图；
[0031] 图11为具体实施方式一提出的利用类别判断方法对未知程序类别筛选出未知程序的可能类别流程图；
[0032] 图12为具体实施方式一提出待检测ORG与病毒库中ORGB匹配流程图；
[0033] 图13为具体实施方式三提出的AHAT结构示意图；
[0034] 图14(a)为具体实施方式四提出的G1的ORG实例图；
[0035] 图14(b)为具体实施方式四提出的G2的ORGB实例图；
[0036] 图14(c)为具体实施方式四提出的G1在sp状态下实例图；
[0037] 图14(d)为具体实施方式四提出的G2在sp状态下实例图；
[0038] 图15(a)为具体实施方式四提出的SSR状态转换图；
[0039] 图15(b)为具体实施方式四提出的G1由sp状态转换到sq状态实例图；
[0040] 图15(c)为具体实施方式四提出的G2由sp状态转换到sq状态实例图。
具体实施方式
[0041] 具体实施方式一：本实施方式的一种基于对象引用图的Android手机恶意软件检测方法，具体是按照以下步骤制备的：
[0042] 步骤一、将Android平台下已分类的恶意程序分别运行，从恶意程序堆内存中提取对象之间对应的引用关系图ORG；其中，ORG(Object Reference Graph)为对象引用图是一个二元组ORG＝(N，E)，N是图中节点的集合，N中的每一个元素表示的是产生对象的类；E∈N×N，是对象之间引用关系的集合；对象为ORG图中的节点，边代表对象之间存在引用关系；ORG是对象引用图的简称；ORG是一个有向图，图中的节点代表对象，边代表对象之间存在引用关系；从同一个类产生的若干对象由一个节点代表，节点之间的多次引用仅由一条边来表示，一个对象发起的引用由代表这个对象的节点的出边来表示，同时忽略对象的自引用；
ORG包括用户类、系统类以及用户类和系统类的引用关系；
[0043] 步骤二、利用改进的VF2算法将同一类恶意程序的所有引用关系图ORG进行子图同构，得到该类恶意程序中所有的ORG的最大公共部分即恶意程序的ORGB(Object Reference Graph Birthmark)；其中，ORGB为引用关系胎记图；
[0044] 步骤三、根据步骤一的方法提取未知程序的ORG，根据未知程序请求的应用权限和系统类，利用类别判断方法对未知程序类别进行筛选，筛选出未知程序的可能类别(通过类别判断找到待检测程序可能属于的类别)如图11；
[0045] 步骤四、选择未知程序的可能类别所对应的ORGB，利用改进的VF2算法依次将所对应的ORGB与未知程序的ORG进行子图同构检测，若某个ORGB与待检测ORG是子图同构关系，则表明未知程序为某类匹配的恶意程序如图12；即完成了一种基于对象引用图的Android手机恶意软件检测技术如图9；
[0046] 本实施方式效果：
[0047] 本实施方式提出基于对象引用图的恶意软件检测方法。通过提取程序运行过程中内存中对象的引用关系，将其作为程序的胎记。通过比对程序的胎记与恶意程序库中恶意程序胎记，判断程序是否为恶意程序。这种方法相对基于API调用通用性更好。
[0048] Android系统是当前最流行的移动设备操作系统之一。Android系统的开放性一方面为其快速的发展提供了强大的助力，另一方面也间接的有利于恶意软件的开发。根据谷歌最新发布的2014年Android安全报告，2014年被恶意软件感染的Android智能设备近1％。针对Android手机恶意软件的检测方法有静态检测与动态检测两种。静态检测方法准确率高，检测速度快，但无法应对代码混淆及加壳等攻击手段。动态检测方法能够应对代码混淆及加壳等攻击手段，但现有的动态检测方法仍存在一些问题。所以我们提出了基于对象引用图的动态检测方法。
[0049] 图3是使用上述方法对26类726个程序进行分类的结果。图3看出，上述方法的在我们把范围扩展到前五位时准确率已经达到了95％。图4展示的是不同类别各自的分类准确率，可以看到多数类别的准确率都很高，在考虑前五位的情况下接近100％。
[0050] 本实施方式方法不涉及系统底层的改动，系统开销小；本实施方式方法使用的是对象引用图ORG能够避免代码混淆的攻击；本方法使用的是程序运行过程中在堆内存中存放的对象信息，所以相比API调用具有更广泛的适用性。
[0051] 本实施方式找到了能够在所有版本的Android系统提取ORG的方法；具体方法在权力要求说明书中的第三部分ORG提取方法中做出了介绍。通过我们的方法，能够在目前所有版本的Android系统中提取ORG。
[0052] 本实施方式提取了使用改进的VF2算法提取ORGB的方法，具体方法在权力要求说明书中第五部分ORGB的提取有具体介绍。对于根据上述方法得到的ORGB的正确性，一方面通过实验比对验证确认，另一方面，系统最终的检测结果也能够对其进行证明。
[0053] 本实施方式首先提取基于应用权限与系统类的类别判断方法快速的锁定待检测程序可能的类别，排除无关类别的干扰，减少需要匹配的次数，该方法的具体介绍在权力要求说明书的第七部分，说明书附图中的图3是使用上述方法对26类726个程序进行分类的结果。从表中可以看出，上述方法的在我们把范围扩展到前五位时准确率已经达到了95％。说明书附图中的图4展示的是不同类别各自的分类准确率，可以看到多数类别的准确率都很高，在考虑前五位的情况下接近100％。而有少数几类的准确率较低，例如，Asroot，BaseBridge，通过分析发现其程序所需权限较少，有的程序仅包含一个权限，并且不同程序间的权限缺乏共性；然后，我们提出适用于恶意程序检测系统的改进的VF2算法，该算法能够极大的减少算法的运行时间，使系统能够实际的应用目前系统在检测时的平均检测时间为10s，最大检测时间<30s，最小检测时间<1s。
[0054] 本实施方式实验使用的恶意程序种类有20种，恶意程序的数量有1139个。并且从多个第三方应用平台采集了1000正常程序进行了检测。表1为实验所使用的恶意程序种类介绍。
[0055] 表1实验使用的恶意程序种类及数量
[0056]
[0057]
[0058] 下表2展示了实验结果，其中漏报率＝本类别恶意程序漏报数量/本类别恶意程序数量。而误报率＝其他类别程序被误报为本类别的数量/(样本总量-本类别的数量)。从实验结果可以看出，本方法的检测效率是能够令人满意的。
[0059] 表2实验检测结果
[0060]
[0061] 具体实施方式二：本实施方式与具体实施方式一不同的是：步骤一中从恶意程序堆内存中提取对象之间对应的引用关系图ORG的时机具体为：
[0062] 恶意程序通常寄宿在正常程序中，在特定触发条件下，恶意代码才会被执行；并且不同的触发条件，恶意代码执行的程序会有所不同，这就导致在不同时期得到的ORG图会有所不同，所以需要对提取时机进行研究；
[0063] 通过对多个种类的恶意程序分析，我们发现，恶意程序的恶意行为通常在以下几个时机提取：
[0064] (1)随宿主程序启动；
[0065] (2)随开机启动；
[0066] (3)在程序被关闭后自启动；
[0067] (4)特定触发条件下启动，例如短信到达或者有来电到达等；
[0068] 所以需要提取不同的时期分的ORG，这样，在检测待检测程序时能够避免因提取时机不同造成的漏报。其它步骤及参数与具体实施方式一相同。
[0069] 具体实施方式三：本实施方式与具体实施方式一或二不同的是：步骤一中将Android平台下已分类的恶意程序分别运行，从恶意程序堆内存中提取对象之间对应的引用关系图ORG具体过程：
[0070] 对象引用图ORG的获取是在Android平台下完成的；这样做的主要原因是导出的原始堆内存文件(Hprof)过大，文件大小均以M为单位；因此，需要在Android平台下分析出原始文件中的有效信息，提取之后传输到服务器，从而减少传输的数据量；
[0071] Android平台下获得对象引用图分为3个步骤；如图1所示；
[0072] (1)导出原始堆内存文件；Android的SDK提供了功能丰富的内存监视工具，对于Android2.3版本以下的系统使用kill-10processID(PID)得到进程的堆内存信息文件(Hprof)；android2.3版本以上的系统通过对堆数据监控的dumpheap工具获取堆内存信息文件；
[0073] (2)利用以JHAT为基础的分析工具AHAT，对堆内存信息文件进行格式转换；其中，堆内存文件的格式要求与JAVA的保持相同；例如步骤(1)中生成的二进制内存文件的版本是1.0.3，而JHAT可以分析的版本是1.0.2，因此需要在Android平台下对文件格式从1.0.3转换为1.0.2；转换是通过编写格式转换工具Conventor实现的，Conventor的功能与SDT中的HprofConv工具实现的功能类似，区别在于Conventor运行在Android平台，而HprofConv运行与PC平台；
[0074] 其中，AHAT整体结构有四个模块：Model、Parser、Util以及外界调用接口；四个模块之间的关系如图13所示；
[0075] (1)Model：定义了可能涉及到的所有对象的类型(数据结构)，这些数据结构的对象组成了一个模型；共有29个类，对应着JAVA中的对象类型，其中最重要的类是Snapshot，是内存快照模型的最大单元；
[0076] (2)Parser：负责读取二进制文件，分析数据并将之填充到模型对象中，构建一个模型；共有7个类，最主要的类是HprofReader，负责读取堆二进制文件；
[0077] (3)Util：常用的工具包；
[0078] (4)外界调用接口：AHAT的框架，负责调用各个模块，使之正常工作起来；在Android中与用户交互的是Activity类，因此这块主要的类是MainActivity类，还有用于获取类引用关系的QueryClassInfo类；
[0079] (3)对经过转换后的文件进行分析，利用分析工具AHAT提取引用关系图ORG；
[0080] 步骤(3)的最终结果是产生仅仅包含对象引用关系数据的文件；其实现是通过编写分析工具AHAT实现的；AHAT是Android应用程序，运行在手机客户端，通过分析经过Convertor转换的二进制文件得到类之间的引用关系图ORG，并将这些关系信息写入文件中；AHAT是运行在Android上的JHAT精简版如图10。其它步骤及参数与具体实施方式一或二相同。
[0081] 具体实施方式四：本实施方式与具体实施方式一至三之一不同的是：步骤二中改进的VF2算法具体为：
[0082] 1)Cordella提出的VF2算法在匹配的过程中引用状态空间的概念(SSR)，同时也提出了5个可行的规则进行剪枝来缩小搜索空间；
[0083] 下面我们来介绍算法的主要思想；假设已知图G1(N1,E1)和G2(N2,E2)，寻找这两图G1和G2之间的同构映射M；通常映射M被描述为节点对(n,m)，M表示的是图G1中的节点n和图G2中的节点m之间的对应关系；其中，寻找映射M的过程是通过状态空间表示SSR来描述；G1表示引用关系图ORG，G2表示ORGB为引用关系胎记图，N1表示G1中的顶点集，E1表示G1中的边集，N2表示G2中的顶点集，E2表示表示G2中的边集；G1为G1(N1,E1)，G2为G2(N2,E2)；
[0084] 2)匹配过程中的每一个状态s都是一个局部映射，用M(s)来表示，M(s)是M的一个子集；G1(s)表示映射M(s)与G1相关的子图，G2(s)表示映射M(s)与G2相关的子图；N1(s)表示G1(s)中的顶点集，N2(s)表示G2(s)中的顶点集，E1(s)表示G1(s)中的边集，E2(s)分别表示G2(s)中的边集；
[0085] 在图14(a)～(d)中给出了两张图G1和G2，通过实例来说明SSR及其它基本概念；G1和G2同构映射为M，中间状态为sp；
[0086] M＝{(n1,m2),(n2,m1),(n3,m3),(n4,m6),(n5,m4),(n6,m5)}
[0087] M(sp)＝{(n1,m2),(n2,m1),(n3,m3),(n4,m6)}
[0088] N1(sp)＝{n1,n2,n3,n4}
[0089] N2(sp)＝{m2,m1,m3,m6}
[0090] E1(sp)＝{,,}
[0091] E2(sp)＝{,,}
[0092] M(sp)是sp状态下的同构映射；N1(sp)是sp状态下G1中已匹配的节点集合；N2(sp)是sp状态下G2中已匹配的节点集合；E1(sp)是sp状态下G1中已匹配的边集合；E2(sp)sp状态下G2中已匹配的边集合；(n1,m2),(n2,m1),(n3,m3),(n4,m6),(n5,m4),(n6,m5)是匹配的节点对；,,,,均表示边；
[0093] 3)VF2算法中提出的用于剪枝的5种可行性规则都是语法可行性规则，在应对具有较大规模，结构较复杂的图匹配问题时，依然会遇到运行时间过长的问题；所以，通过分析本系统的具体问题，考虑利用语义信息提高检测效率；对系统类的语义加以应用；
[0094] 将名称相同的类名进行优先匹配改进为如果两个图中存在类名相同的节点对，并且这些类名属于系统类，则将这些节点对直接匹配得到名称相同的匹配节点加入到同构映射M作为同构映射M的初始状态；如图5和图6所示，在搜索树中处理方式的改变；
[0095] 对于类名相同并且属于系统类直接匹配，而不需要再去尝试匹配其他节点原因为，首先，ORG图中不存在两个节点名称相同；其次，系统类名不会被混淆；(某些Android的系统类，编译器允许开发者创建与这些系统类名称完全相同的类，例如开发者可以自己创建一个包叫Android.os，然后再在里面创建一个类叫BinderProxy，但是系统中也有一个类叫Android .os .BinderProxy，但是对于同一个程序，其引用的名为Android.os.BinderProxy的类只可能为二者其一，而不会在两处引用的名为
Android.os.BinderProxy的类不是同一个，所以依然可以对应上；)
[0096] 其中，系统类名不会被混淆这个第二点也是保证图中必然存在很多类名是很有参考价值的，是提升算法效率的突破口；
[0097] 4)名称不同的类名进行匹配，VF2算法在匹配过程中会产生多个状态，从一个状态s转换为另一个状态s’，即实际上在父亲节点s的基础上加入一对新的匹配节点得到孩子节点s’，通过在同构映射M中加入不同的节点对，状态s会转换为多个状态即多个孩子节点；
[0098] 5)给出变量定义：
[0099] (1)T1out(s)：表示的是G1中一个顶点集合，集合中的顶点不属于G1(s)，但是G1(s)中顶点的后继结点；
[0100] (2)T2out(s)：表示的是G2中一个顶点集合，集合中的顶点不属于G2(s)，但是G2(s)中顶点的后继结点；
[0101] (3)T1in(s)：表示的是G1中一个顶点集合，集合中的顶点不属于G1(s)，但是G1(s)中顶点的前驱结点；
[0102] (4)T2in(s)：表示的是G2中一个顶点集合，集合中的顶点不属于G2(s)，但是G2(s)中顶点的前驱结点；
[0103] 6)根据变量定义对H(s)进行选取的步骤如下所示：
[0104] (1)如果T1out(s)和T2out(s)不是空集，那么H(s)＝T1out(s)×T2out(s)；
[0105] (2)如果T1out(s)和T2out(s)都是空集，但是T1in(s)和T1in(s)不是空集，那么H(s)＝T1in(s)×T2in(s)；
[0106] (3)如果T1out(s)，T2out(s)，T1in(s)和T2in(s)都是空集，那么H(s)＝(N1-T1out(s)-T1in(s))×(N2-T2out(s)-T2in(s))；H(s)是s状态的候选集合；
[0107] (4)其他情况，对状态s进行搜索剪枝；是指如果T1out(s)和T2out(s)之一为空集，或者T1in(s)和T2in(s)之一为空集，那么就表明状态s不能发展为最后的匹配映射，因而将状态s的搜索剪枝；
[0108] 7)VF2算法采用的深度优先搜索方式，对于SSR中的每一个节点，首先计算出该节点对应的中间状态s的候选节点对，并将候选节点对H(s)排序，将与ORGB中节点的度更相近的节点优先；然后递归的对H(s)中每个节点对进行搜索；候选节点对集合H(s)的计算是VF2算法的难点；其中，H(s)为每个状态s加入的节点对是有限的，而且并不是所有的节点对都需要一一搜索；根据剪枝规则去除加入不同的节点对中的一部分节点对，剩余的节点对则是需要遍历继续搜索的，这些节点对称作是状态s的候选节点对集；算法2-1是对VF2算法的详细描述；
[0109] 如图7和图8所示，应将ORGB中Binder节点与待匹配ORG图中的Linker节点匹配，因为Linker节点的度比Activity更接近Binder，否则会浪费大量时间在他们的子节点相互配对但是也找不到答案；
[0110] 这么做主要也是考虑到恶意程序模块中这些度较大的节点往往是核心部分，不会与其宿主打交道，因此恶意程序的胎记和程序运行时的两个图中这些节点的度应该是十分相近的；算法改进后，其检测效率较之前有了很大的提高；
[0111]
[0112]
[0113] 对于当前状态s，针对候选的节点对(n,m)，需要判断其加入的可行性；VF2算法中对节点对的判断是通过可行性函数F(s,n,m)来实现的；其中s表示当前状态，n表示图G1的一个顶点，m表示图G2的一个顶点；F(s,n,m)的返回值为布尔型，返回值为true则表示节点对可行；返回值为false则表示节点对不可行；如果判断出节点对不可行，则剪枝去掉该搜索路径；
[0114] 可行性规则分为语法可行性规则和语义可行性规则；语法可行性规则针对的是图的拓扑结构，而语义可行性规则针对的是图的顶点和边的属性；由于本发明的对象引用关系图不带有边和顶点的属性；因此，只采用语法可行性规则，用Fsyn(s,n,m)来表示；VF2算法中定义了5个语法可行性规则；
[0115] 规则1：Rpred(s,n,m)
[0116]
[0117] 规则2：Rsucc(s,n,m)
[0118]
[0119] 规则3：Rin(s,n,m)
[0120]
[0121] 规则4：Rout(s,n,m)
[0122]
[0123] 规则5：Rnew(s,n,m)
[0124]
[0125] 其中，Rpred和Rsucc考虑的是当前状态M(s)加入候选节点对(n,m)转换为s’后一致性问题而Rin、Rout和Rnew考虑的是对搜索空间的剪枝；Fsyn(s,n,m)＝Rpred∧Rsucc∧Rin∧Rout∧Rnew，用Pred(G,n)代表图G中n的前驱节点的集合，用Succ(G，n)表示图G中n的后继节点的集合；同时使用T1(s)＝T1in(s)∨T1out(s)，并使用N1'(s)＝N1–M1(s)–T1(s)；T2(s)和N2’(s)的定义类似为T2(s)＝T2in(s)∨T1out(s)和N2’(s)＝N2–M2(s)–T2(s)；Card(A)表示集合A的基数，即集合中元素的个数；n'是G1里不同于n的另一个节点，m'是G2里不同于m的一个节点；M1(s)指G1在s状态下的同构映射，M2(s)指G2在s状态下的同构映射，N1(s)是在s状态下G1中已匹配的节点集合，也就是在s状态下，用G2的节点集合N2减去已匹配的节点结合M2(s)再减去与已匹配节点有关联的节点结合T2(s)所剩下的节点；
[0126] 当新加入的节点对符合这5条可行性规则后，则继续对新加入节点对后的状态进行搜索，否则将不符合这5条可行性规则的节点对进行剪枝，不加入该节点对；通过这5条规则，可以降低搜索空间的大小，提高算法的执行效率；VF2算法在匹配过程中会产生多个状态，从一个状态s转换为另一个状态s’，实际上在s的基础上加入一对新的匹配节点；通过加入不同的节点对，状态s会转换为多个状态；这样，不断产生的新的状态空间可以使用树的结构来描述即SSR来描述；父亲节点表示原来的状态，孩子节点表示加入新节点后产生的新状态；以图14(a)～(d)所示的sp状态为例，当加入节点对(n5,m4)之后，状态转换为sq，如图15(a)～(c)所示；在图15(a)中可以看出，加入节点对(n5,m4)转换为sq状态只是多种可能性之一，还可以加入其他的节点对转换为状态sr，ss，st等等，这就需要回溯来选择合适的转换状态；从图15(b)与(c)可以看出，加入(n5,m4)成功转换为新的状态sq；
[0127] 8)这样，不断产生的新的状态空间利用树的结构即SSR来描述，找到最终的同构映射M；在搜索过程中，VF2算法引入了一些规则，以通过剪枝来缩小搜索空间，降低时间复杂度；其中，父亲节点表示原来的状态，孩子节点表示加入新节点后产生的新状态；搜索所有的SSR来找到最终的同构映射M的终止条件为针对不同规模的ORGB设置自适应的调节参数λ达到80％～100％的节点对匹配；不同种类的恶意程序提取的ORGB中所包含的类的个数具有较大的差距，需要根据具体情况设置相应的调节参数；主要原因如下：因为在检测未知程序时使用的是图结构匹配，所以，对于包含较多类的ORGB，一方面要做到100％匹配很难，若设置较高的调节参数，则该ORGB的漏报率将会增加；另一方面，当达到80％以上的节点对匹配时，未知程序属于该类的可能性很大；所以需要设置相对较小的调节参数；
[0128] 而对于具有较小类规模的ORGB，在进行图结构匹配时，若该ORGB的结构较普遍，则很容易在待检测程序中匹配到，设置较小的调节参数，则该ORGB的误报率将会大大增加；所以需要设置较大的调节参数。其它步骤及参数与具体实施方式一至三之一相同。
[0129] 具体实施方式五：本实施方式与具体实施方式一至四之一不同的是：步骤二中利用改进的VF2算法将同一类恶意程序的所有引用关系图ORG进行子图同构，得到该类恶意程序中所有的ORG的最大公共部分即恶意程序的ORGB具体过程为：
[0130] ORGB是一类恶意程序的所有的ORG的最大公共部分；ORGB的提取主要分为三步，图2为ORGB提取示意图；
[0131] (1)去掉ORG图中的用户类孤立点的包名前缀后进行名称匹配，得到ORG图中的用户类孤立点公共图；因为对于孤立点，无法使用结构匹配，所以只能使用名称匹配；又因为公共部分在不同程序中会存在于不同的包中，所以选择去掉包名前缀之后再进行名称匹配；其中，ORG图中的用户类孤立点是指存在于ORG图中的，与系统类以及其他用户类不存在引用关系的用户类；
[0132] (2)利用改进的VF2算法对去掉用户类孤立点的ORG图进行子图同构得到最大公共子图；
[0133] (3)将用户类孤立点公共图和最大公共子图组合作为该类别恶意程序的ORGB(Object Reference Graph Birthmark)；其中，ORGB实际上是ORG的一个子图，程序在运行时，会在内存中创建所有用到的对象；但是不能把所有对象作为程序识别的特征，只能够对其中有代表意义的对象建立对象引用图，形成程序的动态特征；这样产生的就是ORGB。其它步骤及参数与具体实施方式一至四之一相同。
[0134] 具体实施方式六：本实施方式与具体实施方式一至五之一不同的是：步骤二中ORGB具体为：
[0135] 1)定义动态胎记f(p，I)：假设p和q为两个程序或者程序的组件，I为p或q的输入；令f(p，I)为以I为p的输入时抽取的特征，f(p，I)是p的动态胎记当且仅当以下两个条件同时成立：
[0136] (1)当以I为p的输入时，f(p，I)仅仅是从p自身抽取的；
[0137] (2)如果q是p的一部分，那么必有f(p，I)＝f(q，I)；
[0138] 2)与步骤1)方法类似；定义ORGB令p和q为两个程序或者程序的组件，令I为p或q的输入；ORGp是以I为输入，p运行时的对象引用图和ORGq是以I为输入，q运行时的对象引用图；令ORGBp为ORGp的子图；当且仅当以下条件时，ORGBp是p的动态胎记得到满足：
[0139] (1)如果q是p的一部分，那么必有ORGBp子图同构于ORGq；
[0140] (2)如果q不是p的部分，那么必有ORGBp子图不同构于ORGq。其它步骤及参数与具体实施方式一至五之一相同。
[0141] 具体实施方式七：本实施方式与具体实施方式一至六之一不同的是：步骤三中根据步骤一的方法提取未知程序的ORG，根据未知程序请求的应用权限和系统类，利用类别判断方法未知程序类别进行筛选，筛选出未知程序的可能类别具体过程为：
[0142] 通过实验观察与理论分析，我们发现：待检测程序在与对应的恶意程序ORGB匹配时，检测效率快；若待检测程序与非对应的恶意程序ORGB匹配，则检测速度慢；基于该发现，提取了一种解决策略：
[0143] 在检测之前先判断待检测程序可能属于的类别，将可能属于的类别与这些类别的ORGB进行匹配；
[0144] 选择程序请求的应用权限和程序运行过程中调用的系统类作为类别判断的依据；Android系统要求Android应用需要在调用系统功能前申请权限；例如，某个Android应用想要发送短信，则需要android.perssion.SEND_SMS权限；这些权限申请一般都写在AndroidManifest.xml文件中；系统类是指Android应用在运行过程中使用的系统调用；例如，android.os.MessageQueue；权限和系统类对于不同类别的程序具有差异性，而对于同类别的程序会存在共性；所以我们使用权限和系统类对待检测的程序进行类别判断；
[0145] (1)根据申请权限最终得到恶意程序类权限特征文件；其中，权限特征文件中包含该类恶意程序所包含的所有恶意程序的权限集合；此外，每一个权限均包含量化权限贡献度与区分度的数值；即恶意程序类权限特征文件中的内容如下：
[0146] <权限1，贡献度1，区分度1>
[0147] <权限2，贡献度2，区分度2>
[0148] <权限n，贡献度n，区分度n>
[0149] 贡献度是指某个权限在该类恶意程序中出现的频率；例如，A类恶意程序中包含10个恶意程序，权限android.perssion.SEND_SMS在其中8个程序中出现，则其出现的频率为0.8；最后将所有权限的出现频率进行归一化处理，得到权限的贡献度；贡献度与出现的频率正相关；
[0150] 其中，区分度是指权限在所有恶意程序类权限特征文件中出现的频数的倒数；例如，当前有10个恶意程序类，权限android.perission.SEND_SMS在8个恶意程序类权限特征文件中出现，则其区分度为1/8；对于出现频数较少的权限其区分度较大，而对出现频数较多的权限其区分度较小；
[0151] (2)对于未知种类的未知程序进行分类时，首先得到未知程序的权限集合；再将未知程序的权限集合依次与步骤1)得到的恶意程序类权限特征文件做匹配求和即将恶意程序类权限特征文件中出现在未知程序权限集合中的权限的贡献度*区分度的乘积相加，得到与各个恶意程序类权限特征文件匹配的结果，将匹配的结果排序筛选出未知程序的可能类别；
[0152] 图3是利用步骤(1)和(2)对26类726个程序进行分类的结果；从图3看出，上述方法的在我们把范围扩展到前五位时准确率已经达到了95％；图4展示的是不同类别各自的分类准确率，可以看到多数类别的准确率都很高，在考虑前五位的情况下接近100％；而有少数几类的准确率较低，例如，Asroot，BaseBridge，通过分析发现其程序所需权限较少，有的程序仅包含一个权限，并且不同程序间的权限缺乏共性；
[0153] 对于使用系统类进行分类的方法与权限所使用的上述方法一致；最终我们将两种方法中得到的前五位进行组合，得到最终的匹配结果。其它步骤及参数与具体实施方式一至六之一相同。
