基于隨機森林的代碼路徑分支混淆技術研究?

劉 翌 潘小輝 胡潯惠

（1.國網江蘇電力有限公司 南京 210000）（2.國電南瑞南京控制系統有限公司 南京 210000）

1 引言

信息技術越來越融入生活的方方面面，基于網絡協議和嵌入式系統可以隨時隨地測量和處理數據［1］。一旦測量完成，就可以在傳感器上處理本地信息［2］或者將測量數據傳輸到中央服務器［3］。第一種方法需要在本地傳感器節點上具有一定的處理能力［4］，而第二種方法需要較大的網絡帶寬［5］。由于傳感器節點上的通信吞吐量有限，因此需要在傳輸到中心服務器之前對測量數據進行預過濾以便更徹底地檢查數據，即代碼路徑分支混淆技術［6］。其中，預過濾操作可以視為二進制分類問題，因此機器學習適用于代碼路徑分支混淆技術［7］。在隨機森林［8］中組合多個決策樹可以實現較高預測精度。因此，本文主要針對隨機森林進行代碼路徑分支混淆技術。

本文在介紹決策樹和隨機森林基本理論的基礎上，使用基于改進的馮·諾依曼體系結構的CPU理論模型來構建計算體系結構，并在FPGA 上實現隨機森林的應用。結合不同實現所使用的時鐘周期和資源構建所提出的理論模型來進行測量。最后使用Zedboard 的三種不同實現評估所提出的理論模型。

2 決策樹和隨機森林

本文考慮的傳感器數據的過濾是二進制分類問題。在二進制分類問題中，其目的是想找到預測模 型→{0,1} ，其 預 測 給 定 觀 測 值的 類。假設觀測是由傳感器的將模擬測量轉換為非標準化無符號整數。因此，傳感器測量值由d 維向量x→i∈Nd表示，其中每個維表示一個隨機變量，即一個特征。決策樹可以從標記的訓練數據中學習，其中每個由一個觀察和相應的標簽yi∈{0,±1}組成。

在決策樹中，函數f?由一個簡單的樹結構表示，在每個層上執行比較，并將預測與葉節點關聯。從根節點開始，開始將當前觀察值的特征xj與分割值sj進行比較。根據這個比較的結果，可以使用當前節點的左路徑或右路徑。重復此過程直到到達葉子節點并返回與葉子關聯的預測為止。通過從根節點開始并比較當前輸入的特征x2來進行分類，如果x2≤10 為真，則繼續進行下一級分類并進行下一級比較。此過程持續到到達葉子節點，如圖1所示。

圖1 用于三維輸入的簡單二叉決策樹

為了分析不同決策樹實現的預期運行時間，本文為每個節點分配一個唯一的標識符，則要求節點i 轉到左節點j 或右節點k 。令M 表示決策樹中的樹葉數量，則從根節點到樹葉節點有M 條不同的路徑。每次觀察從根節點到一個葉子節點只經過一條路徑。在路徑上執行的所有比較都是相互依賴。

路徑中執行的比較次數有效地表示了分類速度，即所需要執行的比較次數越少，對給定的觀測值x→進行分類的速度就越快。通過假設觀測值的特定分布，可以計算出給定樹所需的期望比較次數。本文將節點i 處的比較視為伯努利實驗，在這個實驗中，利用pi→j表示節點i 到達左邊的子節點j 的概率，pi→k表示節點i 到達左邊的子節點k 的概率。在訓練過程中，只需計算每個節點i 選取左路徑和右路徑的樣本個數，就可以估計出pi→j和pi→k的概率。此外，由于pi→j=1-pi→k。因此，遵循路徑由一系列伯努利實驗組成l=(p0→i1,pi1→i2,…,piL-1→iL)。對于給定的觀測值x→，選擇路徑l 的概率為

決策樹往往傾向于過度擬合，在極端情況下，決策樹每層只分類一個訓練數據點進行分類，因此，其高度為N 。將多個不同的模型組合成一個更大的模型可以防止方法過度擬合［9］。這些由許多相對較弱的分類器組成的集合優于更大、更復雜的模型。隨機森林通過訓練Ntree個決策樹將決策樹與集合結合起來，每個決策樹都具有不同的特征子集和觀測值。因此，隨機森林不會遭受過度擬合問題的影響，并在現實問題上提供最先進的分類精度。

3 計算體系結構

硬件環境提供了許多不同的處理器和嵌入式計算設備，它們具有不同的特性和獨特的優缺點。只有在考慮到給定需求的情況下，才能對這種情況進行全面的分析。本文使用CPU 理論模型和FP?GA來構建計算體系結構。

3.1 CPU理論模型

絕大多數CPU都是使用馮·諾依曼體系結構來實現［10］，其中代碼和數據駐留在相同的內存中，馮·諾依曼體系結構主要是將通信總線連接主存儲器和高速緩存并與CPU 連接。CPU 使用算術邏輯單元（ALU）對寄存器值執行算術邏輯運算。矢量化指令由矢量化單元在特殊矢量寄存器上執行，并控制邏輯管理寄存器的訪問和指令執行，如圖2 所示。

圖2 馮·諾依曼體系結構

使用公共通信總線可獲取代碼指令和數據，CPU的控制邏輯可對代碼指令進行解碼，并相應地將數據加載到寄存器中。隨著CPU 處理速度的不斷提升，內存訪問速度和內存傳輸速率都無法匹配CPU 處理速度，這使得對主內存的訪問速度低于CPU內部的數據處理速度。同時，每個代碼指令的執行與一個公共時鐘同步。CPU 處理的本質是單指令單數據（SISD）系統［11］，其中一條代碼指令對每個時鐘的一個數據項執行一個操作。為了提升數據處理速度，本文將對傳統的馮·諾依曼體系結構下的CPU理論模型進行擴展改進。

1）內存層次結構：內存按層次結構排列，以便從不同的層次結構級別提取代碼指令和數據。在較低的層次結構級別上，可以找到較小但速度較快的內存（如緩存），而在較高的層次結構級別上，可以放置較大但速度較慢的內存（如主內存）。

2）并行內存訪問：CPU 對稱為字符的bit 包執行操作。因此，CPU的字符大小表示CPU可以訪問單個bit 的細粒度。為了減少地址查找，內存訪問是在每個內存訪問加載相鄰字符的bit包上執行。

3）矢量化：隨著越來越多的晶體管使用，更多的專用硬件可以添加到同一個CPU電路中。因此，許多CPU 提供額外的單指令多數據操作（SIMD）。這些矢量化單元使用特殊的寄存器和指令，同時對多個數據項執行單個操作。

本文將CPU 可用的代碼指令與執行這些指令所需的時鐘數量形式化。CPU 通過公共通信總線連接到主存儲器和外圍設備。CPU 對大小為sw的字符進行操作，并且使用大小為Mc的寄存器進行緩存，并在大小為sc（sw的倍數）的緩存線路中傳輸。

矢量化單元對大小為sv=v ?sw的矢量化寄存器進行操作，其中v 表示矢量化的程度。可以使用load 和store 指令從緩存中加載并得到存儲值。對于矢量化單元，加載操作只能將連續內存從緩存加載到矢量寄存器中。

如果要從不同的非連續內存位置加載存儲值，則需要使用加載（load）指令將相應的內存地址存儲到一個向量寄存器中。一旦地址出現在一個寄存器中，則可以使用采集（gather）指令將位于不同內存地址的值加載到一個向量寄存器中。為了從向量寄存器中提取標量值，可以從寄存器單元加載特定的通道。

矢量比較的結果保存到矢量寄存器中。由于單個比較的結果可以用1 個bit 保存，所以只需要v個bit 來保存向量比較。為了訪問這些v 個比較bit，本文使用extract 指令，將v 個比較bit 加載到標量寄存器中。對于數組，本文假設它們存儲在連續內存中。如果將特定索引保存在寄存器中，也可以通過單個load操作對任意索引執行內存訪問。

本文的理論CPU 也采用計時方式，用CCPU表示時鐘頻率。為了進一步簡化分析，假設完整的隨機森林將適合于緩存，并且將只對保存在寄存器和緩存中的元素進行操作。則本文使用以下成本模型：

1）加載（load）：訪問緩存中已經存在的大小為sw的特定字符需要一個時鐘周期。將連續內存加載到向量寄存器也需要一個時鐘周期。加載小于sw的字符需要一個加載指令和一個額外的lane 訪問來提取更小的字符。

2）采集（gather）：采集指令需要一個時鐘周期。

3）存儲（store）：在緩存中保存一個大小為sw或更小的數據項需要一個時鐘周期。將矢量寄存器保存到連續存儲器中也需要一個時鐘周期。

4）比較（compare）：馮-諾伊曼體系結構中的比較包括兩個操作：以一個時鐘周期進行比較；根據比較的結果執行下一條指令的條件跳轉并循環操作。

5）算術和邏輯操作（arithmetic and logic opera?tions）：布爾操作以及訪問矢量化寄存器的特定部分需要一個時鐘周期。

3.2 FPGA體系結構

FPGA 作為可重新配置的硬件，其功能編碼在硬件中可以在執行之前或執行期間進行重新編程［12］。邏輯門與觸發器組合成可配置的邏輯單元，如圖3所示。

圖3 FPGA的可配置邏輯塊（CLB）

每個邏輯單元包含一個大小為2t的真值表并保存布爾函數f:{0,1}t→{0,1}。通過對邏輯表進行編程，邏輯塊可以對大小為t 的每個布爾函數進行映像。此外，可配置邏輯塊（CLB）可以作為配置內存［13］。因此，圖3 中所示的邏輯塊由一個包含4個輸入和一個觸發器的查找表組成。因此，它可以代表任何有4個輸入或存儲1bit的布爾函數。

為了實現更復雜的電路，CLB 通過信號線路相互連接。邏輯單元之間的信號路由由觸發器和靜態啟用或禁用信號路由的晶體管操作，如圖4 所示。

圖4 FPGA中的信號路由

通過對信號路由查找表和觸發器的編程，可以充分指定FPGA 的功能邏輯，有效地使FPGA 成為可重新配置的電路，且FPGA 功能完備。因此，圖4中所示的每個交叉口都有6 個晶體管控制著每條信道，晶體管采用1bit的SRAM單元編程。

4 在FPGA上實現隨機森林

4.1 原生樹（Native-Tree）的實現

與CPU 不同，本文可以在FPGA 上同時發出兩條加載指令，但是由于在地址解析過程中每次加載需要兩個時鐘周期。因此，可以在r1 和r2 上并行執行第一次load 操作。而的load 指令相互依賴并按順序執行，從而在while-loop 內產生4 個加載指令序列。此外，執行兩個比較，每個比較需要1 個時鐘周期，從而Native-Tree的總時鐘周期為

為了估計這個實現所使用的資源，需要兩個功能單元用于比較和兩個功能單元用于地址解析，還需要3個寄存器使用的資源：

其中，raddr表示實現一個時鐘周期的恒定延遲的地址解析機制可以使用最多的CLB 資源量，req表示CLB 實現函數eq:{0,1}2→{0,1}的資源量，rle表示決策樹內部節點數量為ni的資源量。

4.2 If-else樹的實現

本文需要訪問在編譯時已知的常量s_i，類似的需要訪問x[c_i]其中c_i 也是常數。因此，x[c_i]的內存地址在編譯時是已知的，不需要地址解析單元。

本文假設觀測值x→已經復制到CPU 緩存和FPGA 塊內存中，由于在任何情況下都需要與FP?GA 通信，因此可以直接將其復制到FPGA CLB 單元中。本文可以將x→中的條目及其分割值s_i 直接連接到相應的比較器中，進而不需要加載用于比較的操作數，只需要執行比較本身，總共需要1 個時鐘周期：

由于將常量連接到比較塊中，因此不能重用任何比較單元。此外，本文需要將所有分割值s_i 以及整個觀察值存儲在FPGA CLB 單元中。則實現了具有n 個節點的樹需要的資源為

4.3 SIMD的實現

為了觀測SIMD 實現的資源消耗情況，總共需要v 個功能單元來進行地址查找，這是由于運行gather 指令需要并行執行v 個查找。同樣，還需要使用v 比較器來執行v 比較。此外，還需要另一個比較器將r1 與固定值進行比較。最后，需要將所有節點以及向量寄存器和r1 和i 與FPGA 邏輯單元具體化，則最終需要的資源為：

其中，nodet表示單個節點所具有的的資源量。

4.4 DNF的實現

給定樹中的n 個節點必須在1 個時鐘周期內并行執行n 次比較。因此，決策樹的DNF 計算由三個操作組成：1）需要對必要的變量進行逆運算；2）計算連接；3）計算析取。因此，需要3 個時鐘周期，但是由于樹結構是已知的，可以直接將其編碼到FPGA的查找表中。因此，計算dnf只需要1個時鐘周期。添加另一個時鐘周期來返回預測值，則dnf樹需要時鐘周期為

為了在1 個時鐘周期內遍歷完整的樹，本文在運行時交換了空間。即需要n 個比較器并行執行比較。此外，還需要n ?sw個bit 來實現所有使用FPGA CLB和d ?sw個bit存儲觀測值x→的分割值。

計算樹的DNF 可以視為使用布爾函數2E[L]的輸入變量DNF:{0,1}n→{0,1}。本文將它分布在多個邏輯塊上。則實現所需要的資源為

4.4 隨機森林的實現

使用的資源量為

5 代碼生成

5.1 代碼生成器

本文給定一個經過訓練的決策樹分類器或隨機森林分類器，在不改變其精度的前提下，為給定的體系結構生成一個有效的分類器。對于CPU，可以通過匯編程序直接使用處理器的ISA，也可以使用C/C++等高級語言。由于編譯器優化有助于提高總體吞吐量，所以本文為給定的體系結構生成C++代碼，并將其編譯為特定的處理器。

對于FPGA，可以直接生成VHDL代碼，也可以使用C/C++代碼作為基礎并執行高級合成。VHDL對生成的代碼提供了良好的控制，并能夠完全控制FPGA 資源。C/C++允許高級合成工具充分利用塊RAM 和DPS 單元，這是因為它生成特定于主板的代碼。此外，可以構造生成的C/C++代碼，以便高級合成工具能夠執行進一步的優化［14］。因此，將使用C/C++代碼與FPGA 代碼生成的高級合成工具相結合，用C/C++中的代碼模板在Python 中實現代碼生成器［15］。代碼生成器將sklearn 中的決策樹或隨機林加載到內部結構中，并自動檢測特征和拆分所需的數據范圍。此外，它可能直接從JSON 文件加載決策和隨機森林。生成的實現可以使用標準的C/C++編譯器或高級合成工具編譯。

5.2 數據選取

本文采用1440個傳感器進行300次測量，每個傳感器的分辨率為12bit，數據速率為4.944Mbps。為了過濾不需要的事件，本文在包含非標準化原始數據的N = 6000 個訓練實例上訓練了一個具有NTree= 50 個決策樹的隨機森林分類器。為了提高決策樹的性能，本文準備了包含50%背景噪聲和50%所需事件的訓練數據，使用sklearn庫的學習進行決策樹的歸納。每個決策樹平均包含1349 個節點，從根節點到葉節點大約有675條不同的路徑。

本文重點關注正確篩選事件的數量。如果隨機森林分類器在其分類中為已知確定，則將決策樹葉中的正標簽和負標簽的數量解釋為相應類的概率，并且對于隨機森林可以對所有的決策樹的概率進行平均，從而為分類提供預測可靠性。因此，本文只過篩選出事件，其中預測類的概率至少為0.68。在進一步處理之前過濾掉大約12%的數據，同時不執行錯誤分類，將數據速率降低到4.35Mb?ps。

從時鐘周期的數量分析，如果實現if-else樹或SIMD 合成工具，則FPGA 具有優勢。對于if-else樹，每 個 樹 需 要CLB。因此，可以認為if-else 樹不適用于較小的FPGA。

在SIMD合成工具的情況下，可以發現dnf樹也不使用，這是因為與if-else 樹相比，dnf樹需要使用更多的CLB。SIMD 樹所需的資源數量取決于v 。當v=8 時，一個決策樹需要1)+8 ?1+1348 ?node_t+2cdot2 ?12+2 ?12+1440 ?12=8 ?raddr+1348 ?nodet+17464 個 邏 輯 塊。由 于樹中有1348 個節點，則需要至少11 個bit來索引每個節點。為了索引1440 個特性，還需要11 個bit。假設node_t=47。則FPGA 上實現SIMD 至少需要1348 ?47+17464=80820 CLB，這也不適用于較小的FPGA。

綜上所述，對于特定問題情況下，不能使用FP?GA。對于經典CPU 情況下，if-else 樹可提供快速可靠的時鐘延遲。對于呈現的樹，平均需要4·13+1=53 個時鐘周期，因此計算整個森林總共需要2650 個時鐘。由于每秒需要評估300個測量值，所以需要一個至少795000MHz 的處理器。因此，時鐘速度約為1MHz 的小型嵌入式系統可以完成這項工作。

6 實驗分析

為了評估所提出的理論模型，本文比較了使用Zedboard 的三種不同實現。Zedboard 包含一個ARM Cortex-A9，具有666MHz、512Mb DDR RAM和512 Kb 緩存。此外，該主板包含一個Xilinx Ar?tix-7 Z-7020 FPGA 與53200 個 查 找 表，106400 個觸發器（FF）以及4.9 Mb RAM 和220 DSP 單元。Zedboard 包含4 個先進的擴展接口（AXI）端口，每個端口以142MHz的速度運行，32位bit大小導致聚合帶寬高達3.8GB/s。

本文使用2016.2 版本的SDSoC 軟件來運行和編譯實驗，在版本2016.2 中使用Vivado 估計了功耗。所有的實驗都是在單機模式下獨立運行，因此在測量過程中不涉及任何操作系統。本文激活了最積極的優化。FPGA實現的時鐘頻率為100MHz，實際帶寬高達1.6GB/s。表1 描述了隨機森林和單個決策樹的平均分類吞吐量（單位：bit/ms），所有測試重復20次。

表1 隨機森林和不同決策樹所實現的吞吐量比較

可以觀察到，if-else 樹為單個樹以及隨機森林提供了最高的吞吐量。Native-Tree 實現在CPU 上也實現了較高的吞吐量，而dnf-tree 僅實現最小的吞吐量。

從FPGA 角度出發，首先可以看到隨機森林實現不適合FPGA。因此，表1 中相應的數值丟失，而決策樹都實現了適合于吞吐量在1100～1480 之間的FPGA。其中，if-else 樹表現最快，dnf-tree 表現最慢。

表2 給出了所有實現的資源使用情況。對于FPGA，本文描述了合成工具報告的資源使用情況。對于CPU，本文給出了二進制大小，它是由第一階段引導加載程序在主板上通電后直接加載。由于主板是在獨立模式下運行，二進制文件包含所有必要的庫，例如用于時間測量和通過UART 輸出的函數。

可以看到，Native-Tree 在隨機森林中利用40個樹時使用的資源最少，dnf-tree 和if-else 樹也適用于FPGA，但是使用的資源比Native-Tree 多。因此，可以在FPGA上大致容納5個樹。

從CPU 角度出發，可以看到二進制大小在1.3MB～2.4MB 之間，dnf-tree-forest 使用的RAM 僅為6.8MB。表3 給出了所有組合的功耗，考慮到諸如音頻控制器或VGA 控制器之類的外接設備，而在部署期間不需要這些設備。因此，本文重點關注ARM處理器和FPGA的能耗。

表2 隨機森林和不同決策樹所實現的資源比較

表3 隨機森林和不同決策樹所實現的功耗比較

由于這些設備均集成在主板上直接測量這些數值較為困難，所以本文將依賴于合成工具給出功耗估計。本文測試了滿載期間最大功耗的所有估計值。整個芯片在所有配置中使用的總功率小于2W，ARM 處理器使用的總功率為1.53W。FPGA實現的功耗在0.008W～0.068W之間變化很大，但都比ARM處理器需要的低2～3個量級。

7 結語

本文將傳輸到中心服務器之前對測量數據進行預過濾轉化為代碼路徑分支混淆技術，并將其視為二進制分類問題，使用基于改進的馮·諾依曼體系結構的CPU理論模型來構建計算體系結構，并在FPGA上實現隨機森林的應用。利用決策樹和隨機森林構建了每種體系結構并提出了不同的實現方案。根據所提出的理論模型，在觀測值分布已知的情況下估計給定樹所需的時鐘周期數。