对Linux系统中的iptables过滤模块的改进

The Improvement of Iptables Filter Module in Linux Operating System

为了改善现有linux系统内核iptables模块在数据包过滤中线性匹配规则的效率。采用了散列表和动态平衡树来组织过滤表,提出了按照三层递进式的搜索规则,减少了原来的线性查找重复匹配的次数,改进了过滤效率,并确保原有功能不变。把A个IP地址、B个网络设备和C个协议规则的过滤表查找时间复杂度从O(A*B*C)降低到m*O(log2A)+n*O(B)+k*O(log2C),(m,n,k为系数因子)。通过适当增加数据结构,安排合理的搜索规则,在有限的系统开销内,可以提高数据包过滤的规则匹配效率。

In this paper, the filter efficiency of iptables filter module in Linux kernel is analyzed. In order to improve the filter efficiency, new data structures are proposed including hash tables and height balanced trees.New three-layer incremental filter rules are propssed instead of linear matching rules foreduce the number of iterative matching.It guarantees that the original functions of iptables filter module remainun changed. In a system consisting of A IP addresses, B net devices and C protocols , matching time complexity decreases from O (A*B*C) to m*O(log_2A)+n*O(B)+k*O(log_2C)(m,n and k are coefficients).