基于深度增強學(xué)習(xí)的網(wǎng)絡(luò)數(shù)據(jù)包分類算法研究①

郭 鵬

(安徽電子信息職業(yè)技術(shù)學(xué)院 軟件學(xué)院，安徽 蚌埠 233000)

0 引 言

數(shù)據(jù)包分類是計算機網(wǎng)絡(luò)中的基本問題之一，是許多網(wǎng)絡(luò)功能的關(guān)鍵構(gòu)建塊，包括防火墻，訪問控制，流量工程和網(wǎng)絡(luò)測量[1-2]。數(shù)據(jù)包分類的目標(biāo)是將給定的數(shù)據(jù)包與一組規(guī)則中的一個規(guī)則進行匹配，并在規(guī)定的分類時間和/或內(nèi)存占用量進行匹配?，F(xiàn)有的方法依賴于人工對決策樹進行調(diào)整，缺乏一定的可擴展性。因此，設(shè)計一種基于深度增強學(xué)習(xí)方法[3]的數(shù)據(jù)包分類方法，避免人工參加所帶來的問題。

1 DEEPCUT設(shè)計

1.1 DeepCut 總體設(shè)計

本小節(jié)介紹了DeepCut的總體設(shè)計，DeepCut是一種新的基于深度增強學(xué)習(xí)的數(shù)據(jù)包分類算法。給定一個規(guī)則集和目標(biāo)函數(shù)，DeepCut將學(xué)習(xí)并建立最小化目標(biāo)函數(shù)的決策樹。

圖1是基于增強學(xué)習(xí)的DeepCut系統(tǒng)框架：環(huán)境由規(guī)則集和當(dāng)前決策樹組成，agent選擇最佳分割或分區(qū)的模型來逐步構(gòu)建決策樹。分割動作將沿選定維度(即SrcIP，DstIP，SrcPort，DstPort和協(xié)議之一)的節(jié)點劃分為多個子范圍(即2，4，8，16或32個范圍)，并且在樹中創(chuàng)建多個子節(jié)點。分區(qū)動作將節(jié)點的規(guī)則劃分為不相交的子集，并為每個子集創(chuàng)建新的子節(jié)點。環(huán)境在每次迭代中都會通告當(dāng)前節(jié)點的可用動作，agent從中選擇動作以生成樹。隨著時間的推移，agent將學(xué)習(xí)優(yōu)化其決策以最大程度地從環(huán)境中獲得回報。

圖1 系統(tǒng)框架

1.2 DeepCut 訓(xùn)練算法

增強學(xué)習(xí)算法的目標(biāo)是計算一個策略，以最大程度地從環(huán)境中獲得回報。環(huán)境定義了動作空間A和狀態(tài)空間S。Agent從初始策略開始，使用多個rollout對其進行評估，然后根據(jù)這些rollout的結(jié)果(回報)對其進行更新。重復(fù)此過程，直到對rollout滿意為止。

將決策樹生成視為單個馬爾可夫決策過程(MDP)。在此框架中，rollout從包含單個節(jié)點的決策樹開始，這是初始狀態(tài)s0∈S。在每個步驟t，agent執(zhí)行動作at∈A并獲得回報rt，然后環(huán)境從當(dāng)前狀態(tài)st∈S轉(zhuǎn)換到下一個狀態(tài)st+1∈S。目標(biāo)是最大化agent收到的總獎勵，即∑tγtrt，其中γ是折現(xiàn)因子。

樹節(jié)點的動作僅取決于節(jié)點本身，因此不必在環(huán)境狀態(tài)下對整個決策樹進行編碼。需要根據(jù)全局狀態(tài)做出決策，但這并不意味著狀態(tài)表示需要對整個決策樹進行編碼。給定一個樹節(jié)點，對該節(jié)點的動作只需做出最佳決策即可優(yōu)化以該節(jié)點為根的子樹，并不需要考慮決策樹中的其他樹節(jié)點。

給定一個樹節(jié)點n，令tn和sn分別表示節(jié)點n的分類時間和內(nèi)存使用量，令Tn和Sn分別表示以節(jié)點n為根的子樹的分類時間和內(nèi)存使用量。對于剪枝動作，有以下的關(guān)系：

Tn=tn+maxiTi

(1)

Sn=sn+maxiSi

(2)

同理，對于分區(qū)動作，有：

Tn=tn+sumiTi

(3)

Sn=sn+sumiSi

(4)

節(jié)點n的動作a只需要根據(jù)公式(5)來優(yōu)化其子樹。

Vn=argmaxa∈A-(cTn+(1-c)Sn)

(5)

其中，權(quán)重參數(shù)c(c∈[0,1])用來權(quán)衡分類時間和內(nèi)存使用量之間的重要性。

總而言之，僅需要對當(dāng)前節(jié)點進行編碼，并作為agent的輸入狀態(tài)。這是因為環(huán)境是以逐個節(jié)點的方式來構(gòu)建決策樹，節(jié)點只需要考慮自己的狀態(tài)來選擇相應(yīng)的動作，并且每個節(jié)點都包含其父節(jié)點的規(guī)則子集。給定d個維度，使用長度為2d的編碼來對一個樹節(jié)點的狀態(tài)進行編碼，節(jié)點的狀態(tài)還需要描述節(jié)點上的分區(qū)。另外，節(jié)點狀態(tài)并沒有包含數(shù)據(jù)包分類器的規(guī)則集。DeepCut通過從環(huán)境中獲得的回報來隱式地解釋數(shù)據(jù)包分類器規(guī)則。

使用Actor-Critic算法來訓(xùn)練agent的策略。DeepCut從決策樹的根節(jié)點s*開始運行，最終目標(biāo)是學(xué)習(xí)一個優(yōu)化隨機策略函數(shù)π(a|s;θ)。DeepCut首先初始化所有參數(shù)，然后運行N次rollout以對策略和值函數(shù)進行訓(xùn)練。在每次rollout后，它都會將決策樹重新初始化到根節(jié)點。然后，根據(jù)當(dāng)前策略，通過在每個非葉子節(jié)點上重復(fù)選擇并執(zhí)行動作，以逐步構(gòu)建樹。葉子節(jié)點是指規(guī)則數(shù)量低于給定閾值的節(jié)點。

更具體地說，DeepCut以深度優(yōu)先搜索(DFS)順序遍歷樹節(jié)點，即算法遞歸地對當(dāng)前節(jié)點的子節(jié)點進行剪枝，直到該節(jié)點成為葉子節(jié)點為止。構(gòu)建決策樹后，將重置梯度，然后算法對所有樹節(jié)點進行迭代以聚合梯度。最后，DeepCut使用梯度來更新Actor-Critic網(wǎng)絡(luò)的參數(shù)，然后進行下一個rollout。

第一個梯度計算對應(yīng)于策略梯度損失的計算。該損失定義了更新θ以改善預(yù)期回報的方向。從rollout回報R中減去狀態(tài)值V(s;θv)的估計值，以減小梯度方差[4]。與此同時，訓(xùn)練V以使其預(yù)測誤差達到最小。

除了剪枝動作之外，DeepCut還包括了兩種類型的分區(qū)動作。一種是簡單分區(qū)動作，即當(dāng)前節(jié)點沿著一個維度進行分區(qū)。另一種分區(qū)動作是基于啟發(fā)式的分區(qū)方法。Neuro-Cut的單線程實現(xiàn)對于小型分類器就足夠了。但是對于具有數(shù)以萬計的規(guī)則的大型分類器，并行性可以顯著提高訓(xùn)練速度。

圖2 分類時間

圖3 內(nèi)存占用

2 實現(xiàn)過程

在Python中實現(xiàn)了DeepCut的決策樹數(shù)據(jù)結(jié)構(gòu)。為了確保實現(xiàn)上的細微差別不會影響結(jié)果，使用相同的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)每個基準(zhǔn)算法以及實現(xiàn)DeepCut。

DeepCut以遞歸的方式計算所有子狀態(tài)的回報，該過程難以采用一個單獨的MDP進行建模。因此，將DeepCut的環(huán)境看作一系列互相獨立的一步?jīng)Q策問題，每一個決策問題都能產(chǎn)生一個即時回報。當(dāng)子樹的rollout完成后，就可以得到一步?jīng)Q策的真實回報。

例如，假設(shè)從樹的根節(jié)點s1進行rollout。基于策略πθ，agent采用動作a1后，將根節(jié)點s1分裂為子節(jié)點s2，s3以及s4。在這三個子節(jié)點中，假設(shè)采用動作a2將子節(jié)點s4分裂為s5和s6。這兩個rollout操作包括了兩個一步?jīng)Q策，即(s1,a1)和(s4,a2)。假設(shè)參數(shù)c為1，折扣因子為1。那么，這兩個rollout的總回報分別為2和1。

由于一步?jīng)Q策是互相獨立，因此DeepCut在多agent環(huán)境中實現(xiàn)，每個節(jié)點的獨立地進行一步?jīng)Q策問題的求解。由于要為所有狀態(tài)學(xué)習(xí)策略πθ，因此所有的agent都需要使用相同的隨機神經(jīng)網(wǎng)絡(luò)策略。這確保了所有經(jīng)驗都可以優(yōu)化單個共享策略πθ。在利用現(xiàn)成的增強學(xué)習(xí)算法庫，可以實現(xiàn)DeepCut的一步?jīng)Q策。假設(shè)使用簡單的actor-critic算法，并展示了單線程實現(xiàn)的偽代碼。

發(fā)現(xiàn)DeepCut通常會在幾百次rollout中收斂到其最佳解決方案。規(guī)則集的大小不會影響收斂所需的rollout數(shù)量，但會影響每個rollout的運行時間。對于較小的問題(例如1000條規(guī)則)，這可能需要幾分鐘的CPU計算時間。大規(guī)模問題的計算開銷由分類器的大小決定。

在學(xué)習(xí)的初始階段，沒被優(yōu)化的策略會產(chǎn)生一個規(guī)模龐大的決策樹。DeepCut只有在決策樹構(gòu)建完成后才開始進行學(xué)習(xí)，因此需要對rollout進行剪枝以加快決策樹的構(gòu)建。由于有效解決方案所對應(yīng)的決策樹樹高不會太高，因此當(dāng)決策樹達到一定的高度，就需要進行剪枝。為了增強學(xué)習(xí)的穩(wěn)定性和效率，采用Proximal Policy Optimization (PPO)[5]算法來計算actor-critic的誤差。

3 實驗評估

在亞馬遜云服務(wù)平臺中運行DeepCut，所使用的計算機實例為m4.16xl。由于神經(jīng)網(wǎng)絡(luò)和數(shù)據(jù)集的規(guī)模均比較小，因此本實驗并沒有使用GPU。DeepCut的最大迭代次數(shù)是100萬次。將DeepCut與EffiCuts[6]算法進行對比。采用Classbench，通過分析控制接入列表、防火墻以及IP鏈來生成分類規(guī)則庫和測試所需的trace文件[2]。探討了算法在分類時間和內(nèi)存占用方面的表現(xiàn)，結(jié)果分別如圖2和圖3所示。DeepCut在學(xué)習(xí)的過程中，以最小化分類時間和內(nèi)存占用為目標(biāo)。由實驗結(jié)果可知，與現(xiàn)有的方法EffiCuts相比，DeepCut的確可以有效地減少分類時間和內(nèi)存占用。

4 結(jié) 語

本研究設(shè)計了一個基于深度增強學(xué)習(xí)的網(wǎng)絡(luò)數(shù)據(jù)包分類算法，以減少內(nèi)存占用和分類時間為目標(biāo)。給定一系列的規(guī)則和目標(biāo)，本方法能夠自適應(yīng)地學(xué)習(xí)最優(yōu)的數(shù)據(jù)包分類策略，避免了基于人工選擇特征的方法所帶來的問題。實驗的結(jié)果驗證了深度學(xué)習(xí)方法在數(shù)據(jù)包分類方面的有效性，說明深度學(xué)習(xí)方法適用于數(shù)據(jù)包分類問題。