分布式漏洞檢測掃描調度算法

摘要:網絡漏洞掃描器是一個用來自動檢查本地或遠程主機的安全漏洞的程序#65377;依據漏洞檢測的要求和實現的特點，構造一個分布式掃描任務調度模型，提出相應的掃描任務分配算法#65377;該算法將掃描任務分配到與被檢測主機同在一個子網的掃描服務器中執行，或將掃描任務盡可能均衡地分配到各個掃描服務器中，從而提高漏洞檢測系統的運行效率#65377;最后，從理論上證明該模型和算法的可行性和優越性#65377;

關鍵詞:漏洞檢測;分布式;掃描;任務調度

中圖分類號:TP393.08文獻標識碼:A

1前言

網絡漏洞掃描器[1，2]是一個用來自動檢查本地或遠程主機的安全漏洞的程序#65377;對于單個掃描服務器，有限的帶寬和內存及其他因素使其在掃描大規模網絡時受到很大的限制，因此產生了分布式漏洞檢測[3]#65377;所謂分布式漏洞檢測就是使用多個掃描服務器同時對掃描目標進行漏洞檢測，以提高掃描速度#65377;要實現分布式漏洞檢測，就要涉及如何將掃描任務分配到多個掃描服務器中，既要保證掃描結果的準確性，又能平衡各掃描服務器的負載#65377;

基于網絡的漏洞檢測系統是通過網絡向目標主機發送數據，分析目標主機的響應信息從而發現漏洞的#65377;因此，執行漏洞檢測任務的掃描服務器和被檢測目標主機的位置關系對于掃描任務的執行時間和漏洞檢測結果的準確性有很大影響#65377;一般應將掃描任務集中的子任務分配到與目標主機同在一個子網的掃描服務器中執行，這樣可加快掃描速度，提高掃描準確率#65377;如果找不到同在一個子網的掃描服務器，則應將掃描任務盡可能均衡分配到各掃描服務器，盡量使各掃描服務器上的任務在同一時間完成，從而提高漏洞檢測系統的運行效率#65377;

任務分配與調度是公認的NP問題，一般人們不會盲目地去尋求解決這類問題的最優解#65377;對于分布式系統，在適當假設條件下尋找不一定最優但實際可行且有效的方法，仍是目前活躍的研究課題#65377;

2掃描任務調度模型

一個掃描任務S由掃描目標和掃描策略組成，即S=(A，H)#65377;其中:A = {a1，a2，…，an}表示被掃描目標主機地址的集合，n表示需進行漏洞檢測的主機數目;H={h1，h2，…，hm}表示需進行檢測的漏洞集合，m為需檢測的漏洞數目#65377;

在掃描任務集中，不同目標主機的漏洞檢測過程是相互獨立的，它們之間不用交換數據，因此對于不同目標主機的漏洞檢測可被多個掃描服務器同時執行#65377;將掃描任務分解成n個獨立子任務，一個子任務就是對掃描目標中的一個目標主機進行基于掃描策略的漏洞檢測#65377;這樣，掃描任務轉換為S ={s1，s2，…，sn}，其中si用二元組(ai，H)表示， ai表示一個目標主機地址，H表示掃描策略#65377;

假定各掃描服務器的處理能力是一樣的，則在漏洞檢測系統中，檢測一個漏洞所需執行時間為:分布式漏洞檢測掃描調度算法其中tcpu表示執行該漏洞所需的CPU處理時間，tnetwork表示數據在服務器和目標主機間傳輸的時間，μ表示進行網絡傳輸的次數#65377;由于tcpu和tnetwork相差幾個數量級，因此可忽略，即t(hi)≈μitnetwork#65377;掃描策略是由多個漏洞組成的集合，因此一個掃描策略的執行時間為其所包含的所有漏洞的執行時間總和，即:對于各掃描服務器與掃描任務中各目標主機的通信時間，用一個k×n的通信矩陣D表示#65377;

其中，dij(i∈[1，k]，j∈[1，n])表示掃描服務器i與目標主機j的通信時間#65377;定義位于同一子網內的掃描服務器和目標主機的通信時間為0，而目標主機沒有響應或者掃描服務器與目標主機之間無法建立連接時dij=∞(無窮大)#65377;

因此在不同的掃描服務器上，對不同的目標主機執行相同的掃描策略所花費的時間為:其中i∈[1，k]，j∈[1，n];tij(H)表示在掃描服務器i上對目標主機j執行掃描策略H所需時間#65377;

同一掃描任務集中的子任務執行的掃描策略都是相同的，即∑mv=1μv都是相同的，因此可用一個常整數λ代替，則子任務的執行時間可簡化為:

負載平衡的重要目標是縮短作業平均響應時間，均勻#65380;充分地利用整個學院的資源#65377;一個作業的響應時間依賴于其所運行的主機上的負載#65377;負載越重，其運行時間越長#65377;資源使用越平衡，作業響應時間就越短#65377;由于各掃描服務器的處理能力相同，因此掃描服務器上的負載指標主要考慮已分配在其上的掃描子任務數#65377;我們使用一個k維向量L表示某一時刻各個掃描服務器上的負載情況#65377;

li(i∈[1，k])表示某一時刻t已分配到掃描服務器i上執行的掃描子任務數，有0≤li≤n#65377;在確定掃描任務集的調度方案時可用矩陣Wk×n描述，它的每一個元素Wiα= j (i∈[1，k]，j∈[1，n])，j代表一個子任務的編號，表示第j個子任務將在第i個節點的第α位次執行#65377;

矩陣W的行向量Wi表示分配到掃描服務器i上執行的掃描子任務集，有│Wi│= li#65377;基于上述的討論，掃描任務調度模型的目標可表述為:尋求一種掃描任務集在對應掃描服務器集上執行的最優調度矩陣W，使得為執行完分配在其上的全部子任務所需時間最小#65377;目標函數為:這里Fi表示掃描服務器 i 執行完所有分配在其上的掃描子任務所需的時間#65377;

3掃描任務調度算法

在任務調度中，調度算法的耗費直接影響系統的性能，因此一個調度算法需考慮的問題是算法在什么地方執行#65380;調度信息存儲在哪里以及調度算法所使用的技術到底有多復雜#65377;人們把調度問題分為“集中式調度”和“分布式調度”兩類，前者是由一個調度服務器負責搜集系統負載信息，并由它來決定負載平衡調度方案;后者是根據局部范圍內的一些負載信息來進行負載平衡操作，每臺計算機定期把它的負載信息廣播給其它計算機，去更新那些局部維護的負載向量#65377;由于集中式調度在進行調度決策時信息更充分，實現相對簡單，因此我們采用集中式調度方法來對掃描任務進行調度#65377;

對于一個掃描子任務sj(j∈[1，n])，我們將其分配到能最快完成它的掃描服務器上#65377;而sj在掃描服務器pi(i∈[1，k])中的完成時間由兩部份組成:一是完成在sj之前已分配給pi的所有子任務集Wi所需的時間;二是sj在pi的執行時間，即:

我們以式(2)為判斷標準將掃描子任務分配到各掃描服務器上#65377;依據式(2)確定調度矩陣W前首先還應有下列約束條件:掃描子任務必須分配到與其檢測的目標主機位于同一個子網的掃描服務器上，即查找D中滿足dij=0的掃描子任務和掃描服務器#65377;對于一個子任務，當存在滿足這個條件的多個掃描服務器集合P'(P'∈P)時，由于位于同一子網內的主機通信時間基本相同，則同一子網內掃描服務器對掃描子任務的執行時間也就基本相同，因此式(2)轉換成f*(sj， P')=λmin(li)，即可根據各掃描服務器上的任務數li作為標準來衡量掃描子任務的最快完成時間，將掃描子任務數分配到任務數最少，也就是具有最快完成時間的掃描服務器上#65377;具體算法描述如圖1框圖所示#65377;

4算法性能分析

掃描任務調度算法的性能主要以式(1)作為判定標準，目標函數越小，分布掃描任務調度系統性能越好#65377;假設在某一時刻t，各描服務器完成已分配在其上的所有子任務所耗費的最長時間為tmax，分配一個掃描子任務后最大完成時間變為t'max，兩者之差為△T=t'max-tmax，表示新分配一個子任務后最大完成時間的增量#65377;

本文算法將掃描子任務sj分配到能夠在最短時間f*(sj，P)=min(f(sj，pi))(j∈[1，n]，i∈[1，k])內完成的掃描服務器pv(0

(2) f*(sj，P) >tmax#65377;這樣，掃描服務器pv在分配了一個子任務后就成為執行完分配于其上子任務所耗費時間最長的節點，因此t'max=f*(sj，P)=f(sj，pv)，△Tv >0

第一種情況是最理想的，因為分配一個掃描子任務后最大完成時間沒有變化，滿足目標函數#65377;對于第二種情形，最大完成時間有所增加#65377;可證明以最小完成時間為判斷條件將子任務分配到某個掃描服務器上所造成的△T最小，證明如下#65377;

證明:設能最快完成掃描子任務sj(j∈[1，n])的掃描服務器為pv(0

如果掃描子任務分配到其它掃描服務器pu上，則最大完成時間為:即掃描子任務分配在掃描服務器pv上造成的△T小于分配在其他掃描服務器pu上造成的△T#65377;

所以可證得將子任務分配到具有最小完成時間的掃描服務器上會使 △T最小#65377;可以把整個掃描任務的最大完成時間看成是初始時刻的最大完成時間加上以后每分配一個掃描子任務后最大完成時間的增量△T (△T ≥0)之和，即max(Fi)=tmax+∑j=1△Tj#65377;在初始狀態時，掃描服務器上沒有任務，則tmax=0，因此max(Fi) =∑nj=1△Tj，那么目標函數變為:由式(3)可得，只要在每次分配子任務時，使△T最小就可以滿足目標函數的要求#65377;

由前面的證明可知，以最小完成時間為約束條件分配子任務是滿足目標函數的，說明依賴于這個掃描算法的分布式掃描調度模型的性能是較優的#65377;

5結束語

本文提出的漏洞檢測任務調度算法在設計過程中考慮到服務器和目標主機位置關系對掃描結果和掃描速度的影響，在保證掃描結果的前提下盡可能減少掃描任務的完成時間，滿足漏洞檢測產品性能上的要求，符合實際應用情況#65377;提出的分布式漏洞檢測模型便于大型和復雜網絡的安全管理#65377;

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。