###
工程科学与技术:2018,50(4):144-152
←前一篇   |   后一篇→
本文二维码信息
码上扫一扫!
一种基于单元空间划分的快速防火墙包分类算法
(中南大学 信息科学与工程学院, 湖南 长沙 410083)
A Fast Firewall Packet Classification Algorithm Using Unit Space Partitions
(School of Info. Sci. and Eng., Central South Univ., Changsha 410083, China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 1816次   下载 1024
投稿时间:2017-08-01    修订日期:2018-06-15
中文摘要: 针对现有包分类算法存在分类时间长和需要较大存储空间的问题,提出一种基于单元空间划分的快速防火墙包分类方法(Uscuts)。方法主要包括规则预处理、规则空间划分以及决策树构建阶段。首先,基于多维矩阵设计模型,将原始规则按逆序依次映射到多维矩阵,得到与原始规则语义相同但规则空间相互独立的目标规则。随后,对目标规则对应空间进行划分并构建分类决策树,决策树的每条树支与各独立多维规则子空间一一对应,即决策树的每个叶子节点恰好只关联1条规则。因此,在Uscuts包分类方法中,当数据包匹配到叶子节点时,可以直接判定数据包的分类决策为“accept”,不同于传统包分类方法需要在叶子节点关联的规则分组内继续执行顺序匹配,该性质显著地提高了包分类速度。此外,在划分规则空间时,Uscuts方法采用基于单元空间边界的划分方式,比传统分类算法的平均划分方式,有效减少了规则子空间数目,节省了存储空间。为验证方法的包分类效果,设计了不同规模大小的规则和数据集测试方法的有效性。由测试结果可以看出,Uscuts分类方法的时间复杂度在一般情况下能达到O(0.75k·lb(n)),即便在最坏情况下也不超过Ok·lb(n)),其中,nk分别为规则条数和维数。理论分析表明,与现有基于决策树的分类方法相比,Uscuts方法具有更高的分类效率,且所需存储空间更小。
中文关键词: 包分类  防火墙  单元空间  决策树算法
Abstract:In order to solve the problems of long classification time and large storage space incurrent packet classification algorithms, a fast packet classification approach (Uscuts) based on unit space partition was proposed. The method mainly includes rule preprocessing, rule space partition and decision tree construction stage. First, based on the multidimensional matrix design model, the original rules were mapped in reverse order to the multidimensional matrix, and the target rules which have the same semantics with the original rules and mutually independent rule spaces were obtained. Then, the corresponding space of the target rules was divided and a classification decision tree was constructed. Each branch of the decision tree corresponds to an independent multidimensional rule subspace, which means each leaf node of the decision tree just relates only one rule. Therefore, when the packet was matched to the leaf node, the classification decision of the packet can be directly determined to be accept. Unlike the traditional packet classification methods, the sequence matching should be continued within the rule group associated with the leaf nodes, which significantly raised the speed of packet classification. In addition, when dividing the rules space, Uscuts used the division method based on the unit space boundary. Compared with the current classification algorithms, the number of the rule subspace was effectively reduced and the storage space was saved. To further validate the efficiency and effectiveness of the proposed algorithm, different sizes of rules and packets were generated to test the time required for packet classification. The test results showed that the time complexity of Uscuts could reach O(0.75k·lb(n)), even in the worst case, it was not more than O(k·lb(n)), here n and k were the number and dimension of the rules, respectively. Theoretical analysis and experimental results demonstrated that, compared with existing classification methods based on decision tree, Uscuts method has higher classification efficiency and smaller storage space.
文章编号:201700608     中图分类号:TP393    文献标志码:
基金项目:国家自然科学基金资助项目(61672543);湖南省研究生科研创新项目资助(CX2014B081);湖南省科技计划重点研发计划资助项目(2016JC2009);湖南省教育厅科研项目资助(17B022)
作者简介:程玉柱(1980-),男,博士生.研究方向:网络信息安全.E-mail:peter_cheng@csu.edu.cn
引用文本:
程玉柱,王伟平,王建新.一种基于单元空间划分的快速防火墙包分类算法[J].工程科学与技术,2018,50(4):144-152.
CHENG Yuzhu,WANG Weiping,WANG Jianxin.A Fast Firewall Packet Classification Algorithm Using Unit Space Partitions[J].Advanced Engineering Sciences,2018,50(4):144-152.