CT-ISG: Alternate representation of NIDS/NIPS signatures for fast matching

建议：0715358 Cristina Estan威斯康星大学CT-ISG：用于快速匹配的NIDS/NIPS签名的替代表示网络入侵防御系统（IPS）在保护计算机免受来自网络的攻击方面发挥着重要作用。签名匹配是每个IPS必须执行的一项对性能至关重要的操作：在缓冲区中存储重新组装的TCP级别字节流或更高级别协议的字段后，IPS需要决定它是否与描述已知攻击的任何签名匹配。目前常用的表示方法，如确定性有限状态自动机（DFA）和非确定性有限状态自动机（NFA），都存在严重的缺陷。一般来说，DFA能够快速匹配，但空间效率低，NFA简洁，但匹配速度慢。基于多个DFA的解决方案具有中间匹配的速度和内存要求。这种解决方案提供不利的速度与内存权衡的核心原因之一是状态空间爆炸问题。本项目的重点是一种新的签名表示，中和状态空间爆炸：扩展有限自动机（XFA）。XFA用几个字节的“临时存储器”来扩展DFA，这些临时存储器用于存储在匹配过程中记录辅助信息的位，或者用于记录进度的计数器。当达到接受状态时，将检查暂存内存，并且仅当它持有合适的值时才声明匹配。来自Snort和Cisco IPS的签名集的初步结果表明，与使用多个DFA的解决方案相比，XFA可以小10倍，同时在软件上快5倍。

Proposal: 0715358Cristina EstanUniversity of WisconsinCT-ISG: Alternate Representation of NIDS/NIPS signatures for fast matchingNetwork intrusion prevention systems (IPSes) play an important role inprotecting computers against attacks originating from thenetwork. Signature matching is a performance-critical operation thateach IPS must perform: after storing a reassembled TCP-level bytestream or a field of a higher level protocol in a buffer, the IPSneeds to decide whether it matches any of the signatures that describeknown attacks. This project investigates methods for representingsignatures that allow fast matching, require little memory, and cansupport complex signatures expressed as regular expressions.Currently used representations, such as deterministic finite-stateautomata (DFAs) and non-deterministic finite-state automata (NFAs),have severe drawbacks. In general, DFAs enable fast matching but arespace inefficient and NFAs are concise but are slow to matchagainst. Solutions based on multiple DFAs have intermediary matchingspeeds and memory requirements. One of the core reasons why suchsolutions provide unfavorable speed versus memory tradeoffs is thestate-space explosion problem.This project focuses on a novel signature representation thatneutralizes statespace explosion: extended finite automata(XFAs). XFAs extend DFAs with a few bytes of "scratch memory" used tostore bits which record auxiliary information during the matching, orcounters which record progress. When an accepting state is reached,the scratch memory is checked and a match is declared only if it holdssuitable values. Preliminary results on signature sets from Snort andCisco IPS show that compared to solutions using multiple DFAs, XFAscan be 10 times smaller and at the same time 5 times faster insoftware.