一种面向深度包检测的DFA压缩算法

DFA（确定性有限自动机）对于实现深度包检测（deeppacketinspection，DPI）技术具有重要作用。随着深度包检测规则的不断增多，DFA所需的存储空间急剧增大。为此，提出了一种基于字符替换的DFA压缩算法，利用状态转换表中每个状态通常只有少数几个不同跳转的特点，将状态转换表分解为剩余表和字符替换表，减少了存储空间。此外，通过使相似的状态可以共享相同的字符替换表以进一步压缩存储空间，给出了复杂度为O（n2）的压缩算法，n为DFA的状态数。实验结果表明，该算法在L7-filter和Snort规则集上具有较稳定的压缩率，压缩率都在5%以下。