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

劉 翌 潘小輝 胡潯惠

（1.國網(wǎng)江蘇電力有限公司 南京 210000）（2.國電南瑞南京控制系統(tǒng)有限公司 南京 210000）

1 引言

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

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

2 決策樹和隨機森林

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

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

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

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

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

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

3 計算體系結(jié)構(gòu)

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

3.1 CPU理論模型

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

圖2 馮·諾依曼體系結(jié)構(gòu)

使用公共通信總線可獲取代碼指令和數(shù)據(jù)，CPU的控制邏輯可對代碼指令進行解碼，并相應(yīng)地將數(shù)據(jù)加載到寄存器中。隨著CPU 處理速度的不斷提升，內(nèi)存訪問速度和內(nèi)存?zhèn)鬏斔俾识紵o法匹配CPU 處理速度，這使得對主內(nèi)存的訪問速度低于CPU內(nèi)部的數(shù)據(jù)處理速度。同時，每個代碼指令的執(zhí)行與一個公共時鐘同步。CPU 處理的本質(zhì)是單指令單數(shù)據(jù)（SISD）系統(tǒng)［11］，其中一條代碼指令對每個時鐘的一個數(shù)據(jù)項執(zhí)行一個操作。為了提升數(shù)據(jù)處理速度，本文將對傳統(tǒng)的馮·諾依曼體系結(jié)構(gòu)下的CPU理論模型進行擴展改進。

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

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

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

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

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

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

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

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

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

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

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

4）比較（compare）：馮-諾伊曼體系結(jié)構(gòu)中的比較包括兩個操作：以一個時鐘周期進行比較；根據(jù)比較的結(jié)果執(zhí)行下一條指令的條件跳轉(zhuǎn)并循環(huán)操作。

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

3.2 FPGA體系結(jié)構(gòu)

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

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

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

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

圖4 FPGA中的信號路由

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

4 在FPGA上實現(xiàn)隨機森林

4.1 原生樹（Native-Tree）的實現(xiàn)

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

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

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

4.2 If-else樹的實現(xiàn)

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

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

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

4.3 SIMD的實現(xiàn)

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

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

4.4 DNF的實現(xiàn)

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

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

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

4.4 隨機森林的實現(xiàn)

使用的資源量為

5 代碼生成

5.1 代碼生成器

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

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

5.2 數(shù)據(jù)選取

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

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

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

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

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

6 實驗分析

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)語

本文將傳輸?shù)街行姆?wù)器之前對測量數(shù)據(jù)進行預(yù)過濾轉(zhuǎn)化為代碼路徑分支混淆技術(shù)，并將其視為二進制分類問題，使用基于改進的馮·諾依曼體系結(jié)構(gòu)的CPU理論模型來構(gòu)建計算體系結(jié)構(gòu)，并在FPGA上實現(xiàn)隨機森林的應(yīng)用。利用決策樹和隨機森林構(gòu)建了每種體系結(jié)構(gòu)并提出了不同的實現(xiàn)方案。根據(jù)所提出的理論模型，在觀測值分布已知的情況下估計給定樹所需的時鐘周期數(shù)。