一种基于最大频繁子图挖掘的动态污点分析方法

摘要

本发明提供的是一种基于最大频繁子图挖掘的动态污点分析方法。包括动行为依赖图构建、最大频繁子图挖掘和行为依赖图匹配三个部分。采用邻接矩阵存储行为依赖图，其中顶点间的数据关联边用1表示，控制关联边用2表示，无相应依赖边用0表示。最大频繁子图挖掘算法即SPIN‑MBDGM算法的主要思想是首先使用FFSM算法从行为依赖图集中得到频繁子树，然后通过添加候选数据关联边和控制关联边的扩展算法生成最大频繁子图。该方法的主要优点是从同一恶意代码家族所有的行为依赖图中挖掘最大公共部分，在不丢失特征信息的情况下减少特征库中行为依赖图的数量，从而提高识别速度。

主权项

一种基于最大频繁子图挖掘的动态污点分析方法，包括动行为依赖图构建、最大频繁子图挖掘和行为依赖图匹配三个部分，其特征是：(1)、行为依赖图的构建，采用表示顶点之间相邻关系的邻接矩阵存储行为依赖图，其中顶点间的数据关联边用1表示、控制关联边用2表示、无相应依赖边用0表示，行为依赖图的生成过程包括：(1.1)分析由动态污点分析方法生成的污点文件，若已存在的污点数据都已被未污染的数据重新覆盖，则转(1.9)，否则，转(1.2)；(1.2)将所有含有污点参数的API作为邻接矩阵的顶点；(1.3)查询双向链表里的污点传播路径，得到两个API调用API_i与API_j，若API_i与API_j之间存在数据依赖关系，则转(1.4)，否则转(1.5)；(1.4)如API_i调用API_j，在邻接矩阵API_i和API_j间记1，添加数据关联边；(1.5)若API_j在某个污点数据通过控制转移指令能达到的范围内且API_i调用API_j，则转(1.6)，否则转(1.7)；(1.6)在邻接矩阵API_i和API_j间记2，添加控制关联边；(1.7)API_i和API_j间记0，两者无依赖关系；(1.8)当污点文件分析完成，将邻接矩阵的所有空闲位置补0，并根据邻接矩阵绘制行为依赖图；(1.9)生成行为依赖图结束；所述行为依赖图为G_beh表示行为依赖图，其中V表示图的顶点，DE表示数据关联边、CE表示控制关联边、是标号集，包括API名称、输入参数、输出参数和返回值，L为顶点V和标号集间的映射关系将总行为依赖图记为集合GG,GG＝{G_beh1,...,G_behi,...,G_behn},1≤i≤n；(2)、最大频繁子图挖掘具体过程包括：(2.1)利用FFSM算法从行为依赖图集中枚举候选频繁子树；(2.2)对得到的候选频繁子树进行自底向上的剪枝处理，即根据左子树优先迭代删掉叶子，若得到的树的支持度大于等于原树，则删掉叶子，否则不变；(2.3)对每一个频繁子树进行扩展一条候选数据关联边或控制关联边，即遍历候选边集合，对任意一条候选边，通过连接操作(⊕)，添加到频繁子树，若添加边后的子图依然频繁，则添加该边，否则不添加该边；(2.4)若添加候选数据关联边或控制关联边后依然频繁，则转(2.3)，否则转(2.5)；(2.5)对扩展生成的子图进行剪枝处理，如果删掉某条边不改变支持度的大小，则删掉该边；(2.6)若所有候选频繁子图之间存在子图同构关系，则转(2.7)，否则转(2.3)；(2.7)剩下的子图部分即为最大频繁子图；(3)、行为依赖图匹配部分中将最大频繁子图的边称为关键边、记为e，将挖掘完成的特征库中行为依赖图集记为GG，GG中的每个行为依赖图记为g，待测目标图记为G_target，G_target与GG中某个行为依赖图匹配的关键边数记为m，G_target中遗漏的关键边数为n，m和n初始值均为0，匹配过程包括：(3.1)选择图集GG中任意一个行为依赖图g；(3.2)选择每个行为依赖图g中的任意一条关键边e；(3.3)若e属于属于G_target，则转(3.4)，否则转(3.5)；(3.4)m的值加1；(3.5)n的值加1；(3.6)若遍历完g中的所有e，则转(3.7)，否则转(3.2)；(3.7)将m/(m+n)的值存在数组里；(3.8)若遍历完图集GG中所有行为依赖图g，则转(3.9)，否则转(3.1)；(3.9)将数组中的最大值作为匹配结果。