一种基于单元空间划分的快速防火墙包分类算法

摘要

针对现有包分类算法存在分类时间长和需要较大存储空间的问题,提出一种基于单元空间划分的快速防火墙包分类方法(Uscuts).方法主要包括规则预处理、规则空间划分以及决策树构建阶段.首先,基于多维矩阵设计模型,将原始规则按逆序依次映射到多维矩阵,得到与原始规则语义相同但规则空间相互独立的目标规则.随后,对目标规则对应空间进行划分并构建分类决策树,决策树的每条树支与各独立多维规则子空间一一对应,即决策树的每个叶子节点恰好只关联1条规则.因此,在Uscuts包分类方法中,当数据包匹配到叶子节点时,可以直接判定数据包的分类决策为"accept",不同于传统包分类方法需要在叶子节点关联的规则分组内继续执行顺序匹配,该性质显著地提高了包分类速度.此外,在划分规则空间时,Uscuts方法采用基于单元空间边界的划分方式,比传统分类算法的平均划分方式,有效减少了规则子空间数目,节省了存储空间.为验证方法的包分类效果,设计了不同规模大小的规则和数据集测试方法的有效性.由测试结果可以看出,Uscuts分类方法的时间复杂度在一般情况下能达到(0.75·lb()),即便在最坏情况下也不超过(·lb()),其中,和分别为规则条数和维数.理论分析表明,与现有基于决策树的分类方法相比,Uscuts方法具有更高的分类效率,且所需存储空间更小.