2022/12/01

土鳖云 | Wenjun's Academic Space (wenjunli.com)

1. CutTSS (wenjunli.com)
2. Observations (wenjunli.com)
3. CutSplit (wenjunli.com)
4. HybridTSS (wenjunli.com)
5. TabTree (wenjunli.com)
6. HybridCuts (wenjunli.com)

2022/11/16晚思考bit cutting

bit cutting 本质也是 Equi size cutting，但是不是一种“简单的”Equi size cutting，bit cutting 考虑了规则集的分布，Equi size cutting 并没有考虑规则集的分布（我认为 bit cutting 是可以较少 overlapping 的）。

bit cutting 通过不同的算法选择不同的 effective bits，对应着不同的切割方案，而规则的分布决定了如何选择 effective bits。bit cutting既可以减少overlapping，又可以加速索引。

effective bit 的多少决定了树的高低，effective bit 中 0、1 分布决定了树的平衡性，effective bit 中 * 的多少决定 overlapping 多少。我们期望 overlapping 越少越好，树高度越低越好，树越平衡越好。

由此得到，选择effective bits需要遵循以下原则：

1. 尽可能不选择含有通配符 * 的那一列 → 减少 overlapping（2021 MBitTree 启发得来）
2. 选的列 0 1 尽可能分布均匀 → 树会平衡（2021 MBitTree 启发得来）
3. 可以选多个 effective bit → 树的高度会降低

1 硬件

2 软件

2.1 决策树

2.1.1 规则集分组

事实上，规则集中部分规则之间存在明显的差异。对访问控制列表 ( access control list， ACL) 、防火墙 ( firewall，FW) 和 IP 链 ( IP chain， IPC) 类型规则集进行统计分析，结果如图 3 所示。从图中可得，IP 地址字段前缀长度为边缘分布，即大部分位于 0 附近或 32 附近。因此不加任何区分直接切割整个搜索空间将导致严重的规则复制，其中一个解决方案便是分治思想，即将具有相似特征的规则放到一个规则子集中，然后应用节点切割技术为每个子集单独构建决策树，最后形成多棵决策树。规则集分组方式分为：

1. 按字段大小分组。根据规则在每个字段覆盖的范围来划分规则子集，该类方法应用最广泛。
   • HiCuts(1999), HyperCuts(2004), Efficuts(2010), HyperSplit(2011), SmartSplit(2014), CutSplit(2018)
2. 按前缀长度分组。根据规则在特定字段的前缀长度来划分规则集。
   • HashTable
   • ByteCuts(2018)
3. 基于聚类算法分组。使用聚类算法来划分规则子集。
   • ParaSplit
4. 基于深度神经网络模型分组。将机器学习技术应用到报文分类问题中，如使用深度神经 网络模型来学习优化节点切割和规则集分组，以 获得最大的奖励函数( 分类速度、内存消耗等) ， 从而构建性能优异的决策树。
   • NeuroCuts(2019)

按字段大小、前缀长度分组等启发式策略建立在对规则集分布特征观察的基础之上，原理相 对简单、容易实现，但对于不同的规则集，往往需 要手动调整部分参数以获得理想结果; 聚类算法、 神经网络模型则可以使用机器学习来替代人工调 整，实现对规则子集的自适应划分，但需要经过大 量的训练和迭代才能收敛。

2.1.2 节点切割

节点切割基本思想是将整个多维规则集视为树的根节点，然后沿一个或多个特定的维度迭代地切割节点，直到每个叶节点包含的规则数不大于预定义的阈值时停止切割，从而构建单棵决策树。

各类决策树算法在节点切割方面的主要区别为:

1. 切割维度的选择。选择哪个维度切割最优; 一次选择单个维度还是多个维度进行切割。

2. 切割端点的选择

   1. Equi - size
      • 快速将节点等分为 \(2^n\) 个子节点，但会带来严重的规则复制问题,即同一条规则分布在多个子节点中
      • HiCuts(1999), HyperCuts(2004), Efficuts(2010)
   2. Equi-dense
      • 而等密切割能够缓解规则复制问题，但也存在树深度增加、节点索引复杂等问题。
      • HyperSplit(2011), SmartSplit(2014)
   3. Bit cutting
      • 利用规则每一位都可表示为 0、1 或者 * ( 通配符) 的特点，选择其中有效比特将规则映射到各个子节点中，从而避免了盲目地切割整个搜索空间。
      • BitCuts(2017), ByteCuts(2018), MBitTree(2021)

另一个角度看，等分切割也是一种特殊的比特切割，但只允许使用连续的最高有效位。

2.1.3 HiCuts

1. 思路： 一次选择单个维度，将搜索 空间划分为等大小的子空间
2. 规则集分组方式：无
3. 节点切割方式：equi-size
4. 优点：首个决策树分类算法，快速 切割规则空间
5. 缺点：树深度较大，规则复制问 题严重，内存消耗大

2.1.4 HyperCuts

1. 思路： 一次选择多个维度，将搜索 空间划分为等大小的子空间
2. 规则集分组方式：无
3. 节点切割方式：equi-size
4. 优点：HiCuts 的改进，树深度较小， 分类速度较快，规则复制相 比 HiCuts 有所优化
5. 缺点：内存消耗仍然较大，可扩展性较差

2.1.5 EffiCuts

1. 思路：
2. 规则集分组方式：
3. 节点切割方式：equi-size
4. 优点：大大减少了规则复制
5. 缺点：划分树的数目太多，查找速度慢

2.1.6 HyperSplit

HyperSplit 算法提出了等密切割的思路，进一 步缓解了规则复制问题，但由于算法构建的决策树 为二叉树，且每次只能判断一次维度，因此随着规 则集规模的扩大和维度的增加，树的深度也会增 加，相应的遍历决策树所需的访存次数也将增加。

1. 思路： 一次选择单个维度和特定的 端点，将搜索空间划分为两 个规则数几乎相等的子空间
2. 规则集分组方式：无
3. 节点切割方式：equi-dense
4. 优点：进一步优化规则复制问题， 内存消耗小
5. 缺点：树深度较大，遍历树所需 的访存次数较多

2.1.7 BitCuts

1. 思路： 选择规则中的有效比特来划分搜索空间
2. 规则集分组方式：无
3. 节点切割方式：bit-cutting
4. 优点：分类速度在 4 种算法中最快，吞吐量高
5. 缺点：树深度较大，规则复制问题严重，内存消耗大 ## 2.2 哈希表

2.3 决策树结合哈希表

2.4 机器学习

2.5 其他