分布式漏洞檢測掃描調(diào)度算法

摘要:網(wǎng)絡(luò)漏洞掃描器是一個用來自動檢查本地或遠(yuǎn)程主機(jī)的安全漏洞的程序#65377;依據(jù)漏洞檢測的要求和實現(xiàn)的特點，構(gòu)造一個分布式掃描任務(wù)調(diào)度模型，提出相應(yīng)的掃描任務(wù)分配算法#65377;該算法將掃描任務(wù)分配到與被檢測主機(jī)同在一個子網(wǎng)的掃描服務(wù)器中執(zhí)行，或?qū)呙枞蝿?wù)盡可能均衡地分配到各個掃描服務(wù)器中，從而提高漏洞檢測系統(tǒng)的運(yùn)行效率#65377;最后，從理論上證明該模型和算法的可行性和優(yōu)越性#65377;

關(guān)鍵詞:漏洞檢測;分布式;掃描;任務(wù)調(diào)度

中圖分類號:TP393.08文獻(xiàn)標(biāo)識碼:A

1前言

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

基于網(wǎng)絡(luò)的漏洞檢測系統(tǒng)是通過網(wǎng)絡(luò)向目標(biāo)主機(jī)發(fā)送數(shù)據(jù)，分析目標(biāo)主機(jī)的響應(yīng)信息從而發(fā)現(xiàn)漏洞的#65377;因此，執(zhí)行漏洞檢測任務(wù)的掃描服務(wù)器和被檢測目標(biāo)主機(jī)的位置關(guān)系對于掃描任務(wù)的執(zhí)行時間和漏洞檢測結(jié)果的準(zhǔn)確性有很大影響#65377;一般應(yīng)將掃描任務(wù)集中的子任務(wù)分配到與目標(biāo)主機(jī)同在一個子網(wǎng)的掃描服務(wù)器中執(zhí)行，這樣可加快掃描速度，提高掃描準(zhǔn)確率#65377;如果找不到同在一個子網(wǎng)的掃描服務(wù)器，則應(yīng)將掃描任務(wù)盡可能均衡分配到各掃描服務(wù)器，盡量使各掃描服務(wù)器上的任務(wù)在同一時間完成，從而提高漏洞檢測系統(tǒng)的運(yùn)行效率#65377;

任務(wù)分配與調(diào)度是公認(rèn)的NP問題，一般人們不會盲目地去尋求解決這類問題的最優(yōu)解#65377;對于分布式系統(tǒng)，在適當(dāng)假設(shè)條件下尋找不一定最優(yōu)但實際可行且有效的方法，仍是目前活躍的研究課題#65377;

2掃描任務(wù)調(diào)度模型

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

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

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

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

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

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

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

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

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

3掃描任務(wù)調(diào)度算法

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

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

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

4算法性能分析

掃描任務(wù)調(diào)度算法的性能主要以式(1)作為判定標(biāo)準(zhǔn)，目標(biāo)函數(shù)越小，分布掃描任務(wù)調(diào)度系統(tǒng)性能越好#65377;假設(shè)在某一時刻t，各描服務(wù)器完成已分配在其上的所有子任務(wù)所耗費(fèi)的最長時間為tmax，分配一個掃描子任務(wù)后最大完成時間變?yōu)閠'max，兩者之差為△T=t'max-tmax，表示新分配一個子任務(wù)后最大完成時間的增量#65377;

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

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

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

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

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

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

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

5結(jié)束語

本文提出的漏洞檢測任務(wù)調(diào)度算法在設(shè)計過程中考慮到服務(wù)器和目標(biāo)主機(jī)位置關(guān)系對掃描結(jié)果和掃描速度的影響，在保證掃描結(jié)果的前提下盡可能減少掃描任務(wù)的完成時間，滿足漏洞檢測產(chǎn)品性能上的要求，符合實際應(yīng)用情況#65377;提出的分布式漏洞檢測模型便于大型和復(fù)雜網(wǎng)絡(luò)的安全管理#65377;

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