1 隨機森林

       人工智能的研究歷史有著一條從以“推理”為重點，到以“知識”為重點，再到以“學習”為重點的自然、清晰的脈絡。機器學習作為人工智能的一部分，主要是設計和分析一些讓計算機可以自動“學習”的算法，旨在構建能夠根據所使用的數據進行學習或改進性能的系統。

       隨機森林（Random Forest，簡稱RF）屬于集成算法的一種，其由很多決策樹組成完全相應的決策策略。決策樹（Decision tree）采用樹形結構，使用層層推理來實現最終的分類。決策樹作為最簡單的機器學習算法，它易于實現，可解釋性強，完全符合人類的直觀思維，是一種基于if-else規則的有監督學習算法。

圖一 決策樹

       隨機森林作為基于決策樹的集成算法，根據各決策樹的推理結構進行相應的決策策略，得到最終的推理結果。由于其可解釋性強、高度靈活、準確率高、能夠有效地運行在大數據集上等多個特點，隨機森林擁有廣泛的應用前景，比如在金融領域用于投資決策，市場營銷中用來模擬建模、預測客戶行為并提供個性化服務，醫療行業中用來預測疾病的風險和病患者的易感性等等。近期在網絡安全領域也有不錯的使用，比如網絡安全防火墻。下面主要講其在網絡安全流域中流量識別的應用。

2 網絡安全應用

2.1 背景

       流量識別技術在網絡監控與管理、流量計費、用戶行為分析等方面有重要的應用。例如，入侵防御系統及防火墻使用該技術識別惡意流量，及時阻斷惡意連接；企業借助流量識別技術控制應用訪問；相關機構通過識別用戶移動設備流量推測用戶信息與行為等。毋庸置疑，實現準確高效的流量識別具有極其重要的意義。

       基于機器學習的流量識別技術成為近些年流量識別領域最受關注的方法。研究工作開始利用流量在應用級別的通訊模式或統計特征識別流量，基于機器學習的流量識別方法取得了極大的進展，并表現出不依賴負載、準確率高、計算迅速、可擴展性強等特點。本文只關注利用統計特征進行流量識別這類方法。

2.2 應用流程

       基于不同的協議或應用流量具有不同的統計特征，本方法首先收集大量的流量實例，提取流量中與負載內容無關的統計量，然后結合機器學習算法訓練識別模型，生成用于新樣本識別的分類器，該分類器是隨機森林模型，由多個統計特征參量及其閾值構建。該方法流程如下圖所示。

圖二 基于隨機森林的流量識別方法流程

       該方法使用三個隨機森林實現分類器功能。一條待識別的流量樣本進入分類器后，經過粗篩、粗識、細識，最終完成整個決策過程。下圖是分類器的流程。

圖三 分類器

2.3 問題及挑戰

       1）實時性。由于實際應用場景中常需要對流量進行實時識別，而網絡帶寬增長日新月異，如何設計滿足高速網絡實時分類的識別模型是極具挑戰性的任務；

       2）動態更新。由于新協議新應用的出現，或原協議應用改進等原因，流量特征隨時可能發生變化，使用過時的流量數據學習的分類器無法有效處理這些新流量。因此，有必要使用新數據持續更新分類器。除此之外，網絡環境的多樣性也導致分類器在不同環境中移植性較差。

       由于決策樹的層級計算結果依賴關系，決策樹中每一層算完之后需要把該層所有的輸出信息作為下一層的輸入，此時該層將會停止運作，直至當前的數據流被決策樹完全計算完。對于CPU來說，對于層級較多或者模型較大的隨機森林，由于計算延時和線程資源的約束，CPU較難滿足高速網絡實時分類和分類器實時更新的要求。

       FPGA不同于CPU，FPGA上的硬件模塊可以同時進行運算，并且計算延時是ns級，因此如果決策樹在FPGA上的實現采用流水結構可以大大提高計算效率和資源的使用效率。同時，FPGA片上有存儲資源可以對模型進行存儲，可以動態的更新維護分類器。所以使用FPGA進行分類器的實現有一定優勢。

3 FPGA實現方案

3.1 架構

       FPGA針對該方案訓練的隨機森林模型（圖二中的分類器）進行加速實現。FPGA實現架構如下圖所示。

圖四 FPGA實現架構

       FPGA通過三個數據通道分別實現模型的更新，統計特征參量的輸入、提取、分配，以及模型的計算。

       Processor通過Update Channel可實時更新隨機森林模型，將模型參數下載并分配到FPGA的計算單元；

       Flow Channel接收并提取網絡流量中相應的特征參量進入FPGA的計算單元用于計算；

       Computer Channel完成隨機森林的流水計算，計算的識別結果繼續通過網絡端口輸出。

3.2 計算

       在FPGA中，每一個隨機森林由若干決策樹計算單元（Tree_Calc_Unit）組成，每一個計算單元以層級流水的方式完成一棵決策樹的計算。當一個流量樣本進入FPGA，所有的計算單元被同時激活進行并行計算，同時對每個計算單元的結果進行對齊，最終實現該方案中的三個隨機森林組成的分類器。

圖五 決策樹計算單元

3.3 更新

       該方法支持兩種更新模式，半靈活方式每棵決策樹的層數有要求上限（20層），計算延時更低；全靈活方式在不超過計算單元規模下，決策樹的層數和棵樹可完全靈活配置，計算延時相對要高。用戶可根據需要自行選擇。

圖六 半靈活配置方式

圖七 全靈活配置方式

4 測試結果

       該方法中分類器模型由多統計特征參量訓練完成，采用intel PAC A10實現一個95棵決策樹組成的隨機森林模型分類器，完成流量的粗篩、粗識、細識。

       最終在每條測試流特征參量集為144byte的情況下，單張FPGA板卡可以達到約150M/s的QPS，而同等條件下，CPU在scikit-learn庫中對該模型的QPS為0.29M/s。

       在識別延時方面，FPGA加速效果也很明顯，單條流量識別結果延時在1us以內。

5 總結及展望

       隨機森林因其可解釋性強、準確率高等優勢，擁有廣泛的應用前景，比如網絡安全、結果預測、推薦引擎、決策分析等。由于FPGA在并行計算方面的優勢，相信在基于隨機森林的多個應用場景，FPGA均可以發揮其高速和靈活性的優點。