基于随机森林的代码路径分支混淆技术研究∗

刘 翌 潘小辉 胡浔惠

（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上实现随机森林的应用。利用决策树和随机森林构建了每种体系结构并提出了不同的实现方案。根据所提出的理论模型，在观测值分布已知的情况下估计给定树所需的时钟周期数。