一种基于非参数统计的僵尸网络发现方法，包括以下步骤：步骤1，建立非参数扫描统计模型；步骤2，树形先验，将图结构数据近似为便于处理的树结构形式，所述近似方式采用的树结构包括：宽度优先搜索树，随机扫描生成树，斯坦纳树；步骤3，基于树形先验的多层动态规划发现僵尸网络。
1.一种基于非参数统计的僵尸网络发现方法，其特征在于，包括以下步骤：步骤1，建立非参数扫描统计模型；步骤2，树形先验，将图结构数据近似为便于处理的树结构形式，所述近似方式采用的树结构包括：宽度优先搜索树，随机扫描生成树，斯坦纳树；步骤3，基于树形先验的多层动态规划发现僵尸网络；在所述步骤1中，建立非参数扫描统计模型的具体方式为，建立如下所示非参数扫描统计模型为：其中，Ω为检测到的僵尸网络，S为相应的异常特征的集合，N(Ω)和N(S)分别代表Ω中节点的个数和S中特征的个数，Nα (Ω，S)为在置信水平为α的前提下异常节点的个数，其中，当Z(•)中的输入为真时，Z(•)=1；当Z(•)中的输入为假时，Z(•)=0，F为非参数扫描统计函数，采用BJ统计函数测试经验p-value是否符合一个统一的或者分段常数分布，所述BJ统计如下所示：其中Nα (Ω，S)为Ω中节点有异常特征S并且其p-value 小于等于α的节点的个数，N(Ω)为Ω中节点的个数，N(S)为S中特征个数，所述以x，y为参数的KL函数为：
在所述步骤2中，将网络中的图结构G转化为树形结构，然后通过在该树结构中找到最优的子树来实现僵尸网络的快速发现，所述采用宽度优先搜索树的具体实现为，从候选根节点随机选出一个集合，并为每个候选根节点生成一个宽度优先树；所述采用随机扫描树的具体实现为，通过给每条边赋予权重得到一棵随机数并计算最小权重的生成树；所述斯坦纳树的具体实现为，如果异常的节点与尽可能少的正常节点存在关系，一棵树被认为是好的，把每个异常节点表示为终点节点，并且每个正常的节点作为斯坦纳节点，通过生成输入图的斯坦纳树，每棵树就能被标识；在所述步骤3中，根据所述步骤2树形先验之后，枚举生成树深度K，将生成树按此深度划分成若干子树，先在子树内部进行第一种动态规划，得到结果后存在子树的根节点上，随后每一棵子树看作一个节点进行第二种动态规划；所述在子树内部进行第一种动态规划的具体方式为：针对每一个特征值集合，记为{p1，p2，p3, …, pn}，其中n为提取的特征值数，pi=1表示集合中该特征值异常，pi=0 表示该特征值非异常；对于每个节点，如果对于集合中每一个pi=1，该节点对应的异常值p-value小于最大阈值，则这个节点是异常节点，否则就记为正常节点，每一个异常节点的消耗为0，收益为该点的异常特征数目；正常节点消耗为1，收益为0，进行树上的动态规划，F[i][j]为以节点i为根在允许有j个正常节点的情况下的最大异常程度，每一个孩子k更新父亲的答案F[i][j]，F[i][j]=max{F[i][j]，F[i][j-t]+F[k][t]}，所述max为取最大值的函数，大括号中的F[i][j] 为不选这个孩子节点，所述F[i][j-t]+F [k][t]为选择这个孩子的子树，并分配所述t的消耗；对于边界值，如果节点i是正常节点，F[i][0]=0，否则F[i][0]=1+ ∑F[j][0]，其中j是i的孩子，最终保存对于每一个特征子集的最大F[i][j]。
2.如权利要求1所述的方法，其特征在于，所述第二种动态规划中，在固定了消耗T之后，对于同一个孩子节点j，采用使F [j][T]最大的异常特征子集，j、T均为正整数。
一种基于非参数统计的僵尸网络发现方法
技术领域
[0001] 本发明涉及一种网络安全技术，主要涉及基于非参数统计的僵尸网络发现方法。
背景技术
[0002] 在网络安全领域，僵尸网络已经成为了一种很常见的威胁。成千上万的受损主机被编入僵尸网络，由攻击者通过命令和控制通道控制。僵尸网络已经引发了网络犯罪，包括分布式拒绝服务(DDoS)攻击、垃圾邮件、身份盗窃等。由于僵尸主人依赖于C&C通道来命令被攻击的机器并接收来自机器人的信息，C&C通道充当僵尸网络的关键元素。
[0003] C&C通道的常见结构包括集中式架构和P2P结构。在集中结构中，所有的机器人都连接到攻击者拥有的一个或一个非常有限的服务器。然而，这样的基础设施会导致一个潜在的缺点，单点故障。为了克服这一弱点，最近的攻击者转向了P2P结构，这是一种更灵活、更复杂、更可靠的为攻击者构建僵尸网络的方式。任何涉及P2P网络的成员(即任何受攻击的设备)都可以由僵尸主选择来分发恶意数据包或接收来自其他机器人的消息，换句话说，作为服务器。此外，P2P网络中的对等点可能来来去去，服务器也可能随着时间的推移而改变，从而加剧了结构的复杂性。
[0004] 网络的快速发展，导致了巨大的搜索空间，这使得僵尸网络的检测变得更加困难，此外，常传统的基于参数的方法假设网络结构中的节点(包含异常和非异常的节点)，并且将异常检测形式化假设检验问题，该方法的一个常用的建模方式是将顶点之间连接频率建模为一个计数过程。类似的传统的僵尸网络检测方法不能很好的检测出网络中的僵尸网络，并不能发现不同僵尸网络的变现特征，然而，一些非传统的数据资源使得标准的基于参数的统计方法变得不太试用。非参数扫描统计函数因其不受数据分布的限制而受到广泛的关注。
[0005] 僵尸网络的检测是非常重要的，然而P2P结构化僵尸网络中越来越多的成员使得目标子网的提取更加困难。仅用传统的统计方法(例如P2P相关网络特性，如同行流失率、流量等；或者节点或边缘级别上的特性，比如邻居数量、使用的协议类型、连接持续时间等，可能不足以精确检测僵尸网络，而且不能很好的反映整个图的动态。
发明内容
[0006] 为解决上述问题，本发明提出一个全新的高效的基于非参数统计的僵尸网络发现方法。该方法主要包括以下步骤：步骤1，建立非参数扫描统计模型；步骤2，树形先验，将图数据近似为便于处理的树形式，该装置中将采用宽度优先搜索树、随机扫描生成树和斯坦纳树；步骤3，基于树形先验的多层动态规划发现僵尸网络。
[0007] 本发明将会更简单准确的检测出网络中僵尸网络。其具备以下优势：快速发现网络中的僵尸网络并发现其异常特征；将传统的僵尸网络检测问题，转换为一个非参数扫描统计的问题，增进了该转置的普遍适用性；在近线性时间内解决僵尸网络子图发现该NP-hard问题。
附图说明
[0008] 图1为本发明的整体流程图；
[0009] 图2为一实施例的划分子树结构。
具体实施方式
[0010] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
[0011] 本发明提出一个全新的高效的基于非参数统计的僵尸网络发现方法。该方法主要包括以下步骤：步骤1，建立非参数扫描统计模型；步骤2，树形先验，将图数据近似为便于处理的树形式，该装置中将采用宽度优先搜索树、随机扫描生成树和斯坦纳树；步骤3，基于树形先验的多层动态规划发现僵尸网络。
[0012] 在步骤1中，实现高效网络中僵尸网络发现及其相应的僵尸网络特征发现，建立如下所示非参数扫描统计模型可为：
[0013]
[0014] 其中，Ω为检测到的僵尸网络，S为相应的异常特征的集合，N(Ω)和N(S分别代表集合Ω中节点的数量和S中特征的个数。Nα(Ω，S)＝∑v∈Ω，s∈SZ(ps(v)≤α)为在置信水平为α的前提下异常节点的个数，其中，当Z(·)中的输入为真时，Z(·)＝1；当Z(·)中的输入为假时，Z(·)＝0。F为非参数扫描统计函数，将采用Berk-Jones(BJ)统计函数，其为对数似然比统计，用于测试经验p-value是否符合一个统一的或者分段常数分布。BJ统计如下所示：
[0015]
[0016] 其中，Ω检测到的僵尸网络，Nα(Ω，S)为Ω中节点有异常特征S并且其p-value小于等于α的节点的个数，N(Ω)为Ω中节点的个数，N(S)为S中特征个数。KL是Kullback-Liebler检测的和预期的节点中p-value值小于α散的节点分布的散度。所述以x，y为参数的KL函数为：KL(x，y)＝xlog(x/y)+(1-x)log((1-x)/(1-y))。
[0017] 考虑的特征因素有：1每秒发送字节数，2每秒接收字节数，3每秒收发字节数，4每秒发包数，5每秒收包数，6每秒收发包数，7平均Flow Duration，8接收的平均包大小，9接收到的包的方差，10发送的包的方差，11发送的不同dst数量，12收发包中最大的包的大小等。
[0018] 在所述步骤2中，将网络中的图结构G为转化为树形结构，然后通过在该树结构中找到最优的子树来实现僵尸网络的快速发现，所述采用宽度优先搜索树：该方法从候选根节点随机选出一个集合，并为每个候选根节点生成一个宽度优先树；所述采用随机扫描树为通过给每条边赋予权重得到一棵随机数并计算最小权重的生成树；所述斯坦纳树为如果异常的节点与尽可能少的正常节点存在关系，一棵树可以被认为是好的，把每个异常节点表示为终点节点，并且每个正常的节点作为斯坦纳节点，通过生成输入图的斯坦纳树，每棵树就能被标识。
[0019] 在步骤3中，根据上述树形先验之后，生成有了一棵生成树以后，将原来的生成树按照深度K将其划分成若干子树。先在子树内部进行第一种动态规划，得到结果后存在子树的根节点上。随后每一棵子树看作一个节点进行第二种动态规划。如图2所示为一实施例的划分子树结构。
[0020] 首先，本发明考虑子树内部的动态规划
[0021] 每一个节点都有特征值集合(即提取的12个特征值)，那么用2^12的复杂度就可以枚举出所有的特征值子集。针对每一棵子树，首先枚举特征值集合，针对每一个特征值子集合，调用动态规划。
[0022] 记特征值子集合为{p1，p2，p3，…，pn}，其中pi＝1表示子集中该特征值异常。对于每个节点，如果对于集合中每一个pi＝1，该节点对应的异常值p-value
[0023] 记F[i][j]为以节点i为根在允许有j个正常节点(最大消耗为j)的情况下的最大异常程度。那么显然，节点i的答案可以被和它直接相连的所有孩子更新，而且是一个背包问题。先考虑非边界的情况，也就是所有的孩子都和父亲节点在同一棵子树里面的情况。
[0024] 每一个孩子k都可以更新父亲的答案F[i][j]，F[i][j]＝max{F[i][j](不选这个孩子节点)，F[i][j-t]+F[k][t](选择这个孩子的子树，并分配t的消耗，其中t需要枚举)}。对于边界值，F[i][0]＝0(如果节点i是正常节点，也就是说不能在这里什么消耗都没有就有收益)否则F[i][0]＝1+∑F[j][0]，其中j是i的孩子。最终保存对于每一个特征子集的最大F[i][j]。
[0025] 其次，考虑子树之间的动态规划
[0026] 上述针对子树内部的部分，对于子树之间，在固定了消耗T之后，对于同一个孩子节点j，会采用使F[j][T]最大的异常特征子集。
[0027] 最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。
