分布式漏洞检测扫描调度算法

摘要:网络漏洞扫描器是一个用来自动检查本地或远程主机的安全漏洞的程序｡依据漏洞检测的要求和实现的特点,构造一个分布式扫描任务调度模型,提出相应的扫描任务分配算法｡该算法将扫描任务分配到与被检测主机同在一个子网的扫描服务器中执行,或将扫描任务尽可能均衡地分配到各个扫描服务器中,从而提高漏洞检测系统的运行效率｡最后,从理论上证明该模型和算法的可行性和优越性｡

关键词:漏洞检测;分布式;扫描;任务调度

中图分类号:TP393.08文献标识码:A

1前言

网络漏洞扫描器[1,2]是一个用来自动检查本地或远程主机的安全漏洞的程序｡对于单个扫描服务器,有限的带宽和内存及其他因素使其在扫描大规模网络时受到很大的限制,因此产生了分布式漏洞检测[3]｡所谓分布式漏洞检测就是使用多个扫描服务器同时对扫描目标进行漏洞检测,以提高扫描速度｡要实现分布式漏洞检测,就要涉及如何将扫描任务分配到多个扫描服务器中,既要保证扫描结果的准确性,又能平衡各扫描服务器的负载｡

基于网络的漏洞检测系统是通过网络向目标主机发送数据,分析目标主机的响应信息从而发现漏洞的｡因此,执行漏洞检测任务的扫描服务器和被检测目标主机的位置关系对于扫描任务的执行时间和漏洞检测结果的准确性有很大影响｡一般应将扫描任务集中的子任务分配到与目标主机同在一个子网的扫描服务器中执行,这样可加快扫描速度,提高扫描准确率｡如果找不到同在一个子网的扫描服务器,则应将扫描任务尽可能均衡分配到各扫描服务器,尽量使各扫描服务器上的任务在同一时间完成,从而提高漏洞检测系统的运行效率｡

任务分配与调度是公认的NP问题,一般人们不会盲目地去寻求解决这类问题的最优解｡对于分布式系统,在适当假设条件下寻找不一定最优但实际可行且有效的方法,仍是目前活跃的研究课题｡

2扫描任务调度模型

一个扫描任务S由扫描目标和扫描策略组成,即S=(A,H)｡其中:A = {a1,a2,…,an}表示被扫描目标主机地址的集合,n表示需进行漏洞检测的主机数目;H={h1,h2,…,hm}表示需进行检测的漏洞集合,m为需检测的漏洞数目｡

在扫描任务集中,不同目标主机的漏洞检测过程是相互独立的,它们之间不用交换数据,因此对于不同目标主机的漏洞检测可被多个扫描服务器同时执行｡将扫描任务分解成n个独立子任务,一个子任务就是对扫描目标中的一个目标主机进行基于扫描策略的漏洞检测｡这样,扫描任务转换为S ={s1,s2,…,sn},其中si用二元组(ai,H)表示, ai表示一个目标主机地址,H表示扫描策略｡

假定各扫描服务器的处理能力是一样的,则在漏洞检测系统中,检测一个漏洞所需执行时间为:分布式漏洞检测扫描调度算法其中tcpu表示执行该漏洞所需的CPU处理时间,tnetwork表示数据在服务器和目标主机间传输的时间,μ表示进行网络传输的次数｡由于tcpu和tnetwork相差几个数量级,因此可忽略,即t(hi)≈μitnetwork｡扫描策略是由多个漏洞组成的集合,因此一个扫描策略的执行时间为其所包含的所有漏洞的执行时间总和,即:对于各扫描服务器与扫描任务中各目标主机的通信时间,用一个k×n的通信矩阵D表示｡

其中,dij(i∈[1,k],j∈[1,n])表示扫描服务器i与目标主机j的通信时间｡定义位于同一子网内的扫描服务器和目标主机的通信时间为0,而目标主机没有响应或者扫描服务器与目标主机之间无法建立连接时dij=∞(无穷大)｡

因此在不同的扫描服务器上,对不同的目标主机执行相同的扫描策略所花费的时间为:其中i∈[1,k],j∈[1,n];tij(H)表示在扫描服务器i上对目标主机j执行扫描策略H所需时间｡

同一扫描任务集中的子任务执行的扫描策略都是相同的,即∑mv=1μv都是相同的,因此可用一个常整数λ代替,则子任务的执行时间可简化为:

负载平衡的重要目标是缩短作业平均响应时间,均匀､充分地利用整个学院的资源｡一个作业的响应时间依赖于其所运行的主机上的负载｡负载越重,其运行时间越长｡资源使用越平衡,作业响应时间就越短｡由于各扫描服务器的处理能力相同,因此扫描服务器上的负载指标主要考虑已分配在其上的扫描子任务数｡我们使用一个k维向量L表示某一时刻各个扫描服务器上的负载情况｡

li(i∈[1,k])表示某一时刻t已分配到扫描服务器i上执行的扫描子任务数,有0≤li≤n｡在确定扫描任务集的调度方案时可用矩阵Wk×n描述,它的每一个元素Wiα= j (i∈[1,k],j∈[1,n]),j代表一个子任务的编号,表示第j个子任务将在第i个节点的第α位次执行｡

矩阵W的行向量Wi表示分配到扫描服务器i上执行的扫描子任务集,有│Wi│= li｡基于上述的讨论,扫描任务调度模型的目标可表述为:寻求一种扫描任务集在对应扫描服务器集上执行的最优调度矩阵W,使得为执行完分配在其上的全部子任务所需时间最小｡目标函数为:这里Fi表示扫描服务器 i 执行完所有分配在其上的扫描子任务所需的时间｡

3扫描任务调度算法

在任务调度中,调度算法的耗费直接影响系统的性能,因此一个调度算法需考虑的问题是算法在什么地方执行､调度信息存储在哪里以及调度算法所使用的技术到底有多复杂｡人们把调度问题分为“集中式调度”和“分布式调度”两类,前者是由一个调度服务器负责搜集系统负载信息,并由它来决定负载平衡调度方案;后者是根据局部范围内的一些负载信息来进行负载平衡操作,每台计算机定期把它的负载信息广播给其它计算机,去更新那些局部维护的负载向量｡由于集中式调度在进行调度决策时信息更充分,实现相对简单,因此我们采用集中式调度方法来对扫描任务进行调度｡

对于一个扫描子任务sj(j∈[1,n]),我们将其分配到能最快完成它的扫描服务器上｡而sj在扫描服务器pi(i∈[1,k])中的完成时间由两部份组成:一是完成在sj之前已分配给pi的所有子任务集Wi所需的时间;二是sj在pi的执行时间,即:

我们以式(2)为判断标准将扫描子任务分配到各扫描服务器上｡依据式(2)确定调度矩阵W前首先还应有下列约束条件:扫描子任务必须分配到与其检测的目标主机位于同一个子网的扫描服务器上,即查找D中满足dij=0的扫描子任务和扫描服务器｡对于一个子任务,当存在满足这个条件的多个扫描服务器集合P'(P'∈P)时,由于位于同一子网内的主机通信时间基本相同,则同一子网内扫描服务器对扫描子任务的执行时间也就基本相同,因此式(2)转换成f*(sj, P')=λmin(li),即可根据各扫描服务器上的任务数li作为标准来衡量扫描子任务的最快完成时间,将扫描子任务数分配到任务数最少,也就是具有最快完成时间的扫描服务器上｡具体算法描述如图1框图所示｡

4算法性能分析

扫描任务调度算法的性能主要以式(1)作为判定标准,目标函数越小,分布扫描任务调度系统性能越好｡假设在某一时刻t,各描服务器完成已分配在其上的所有子任务所耗费的最长时间为tmax,分配一个扫描子任务后最大完成时间变为t'max,两者之差为T=t'max-tmax,表示新分配一个子任务后最大完成时间的增量｡

本文算法将扫描子任务sj分配到能够在最短时间f*(sj,P)=min(f(sj,pi))(j∈[1,n],i∈[1,k])内完成的扫描服务器pv(0

(2) f*(sj,P) >tmax｡这样,扫描服务器pv在分配了一个子任务后就成为执行完分配于其上子任务所耗费时间最长的节点,因此t'max=f*(sj,P)=f(sj,pv),Tv >0

第一种情况是最理想的,因为分配一个扫描子任务后最大完成时间没有变化,满足目标函数｡对于第二种情形,最大完成时间有所增加｡可证明以最小完成时间为判断条件将子任务分配到某个扫描服务器上所造成的T最小,证明如下｡

证明:设能最快完成扫描子任务sj(j∈[1,n])的扫描服务器为pv(0

如果扫描子任务分配到其它扫描服务器pu上,则最大完成时间为:即扫描子任务分配在扫描服务器pv上造成的T小于分配在其他扫描服务器pu上造成的T｡

所以可证得将子任务分配到具有最小完成时间的扫描服务器上会使 T最小｡可以把整个扫描任务的最大完成时间看成是初始时刻的最大完成时间加上以后每分配一个扫描子任务后最大完成时间的增量T (T ≥0)之和,即max(Fi)=tmax+∑j=1Tj｡在初始状态时,扫描服务器上没有任务,则tmax=0,因此max(Fi) =∑nj=1Tj,那么目标函数变为:由式(3)可得,只要在每次分配子任务时,使T最小就可以满足目标函数的要求｡

由前面的证明可知,以最小完成时间为约束条件分配子任务是满足目标函数的,说明依赖于这个扫描算法的分布式扫描调度模型的性能是较优的｡

5结束语

本文提出的漏洞检测任务调度算法在设计过程中考虑到服务器和目标主机位置关系对扫描结果和扫描速度的影响,在保证扫描结果的前提下尽可能减少扫描任务的完成时间,满足漏洞检测产品性能上的要求,符合实际应用情况｡提出的分布式漏洞检测模型便于大型和复杂网络的安全管理｡

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。