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

建议：0715358威斯康星大学克里斯蒂娜·埃斯坦CT-ISG：用于快速匹配的NIDS/NIPS签名的替代表示网络入侵防御系统(IPSS)在保护计算机免受来自网络的攻击方面发挥着重要作用。签名匹配是每个IPS必须执行的一项关键性能操作：在将重组的TCP级字节流或更高级别协议的字段存储在缓冲区中后，IPS需要确定它是否与描述已知攻击的签名中的任何一个匹配。目前常用的签名表示方法，如确定性有限状态自动机(DFAS)和非确定性有限状态自动机(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.