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

CT-ISG：NIDS/NIPS 签名的替代表示形式，用于快速匹配

• 批准号: 0716538
• 负责人: Somesh Jha
• 金额: $ 35万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-07-15 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0716538&HistoricalAwards=false
• 关键词: CT; ISG; Alternate; representation; NIDS

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.

提案：0715358Cristina EstanUniversity of wisconsin - isg：用于快速匹配的NIDS/NIPS签名的替代表示网络入侵防御系统（ips）在保护计算机免受来自网络的攻击方面发挥着重要作用。签名匹配是每台IPS必须执行的一项性能关键操作，在将重组后的tcp级字节流或更高级别协议的字段存入缓冲区后，IPS需要判断是否匹配描述已知攻击的签名。这个项目研究了签名的表示方法，这些方法允许快速匹配，需要很少的内存，并且可以支持用正则表达式表示的复杂签名。目前使用的表征，如确定性有限状态自动机（dfa）和非确定性有限状态自动机（nfa），有严重的缺点。一般来说，dfa可以实现快速匹配，但空间效率低；nfa简洁，但匹配速度慢。基于多个dfa的解决方案具有中间匹配速度和内存需求。这种解决方案提供不利的速度与内存权衡的核心原因之一是状态空间爆炸问题。这个项目的重点是一种新的签名表示，它可以消除状态空间爆炸：扩展有限自动机（xfa）。xfa用几个字节的“临时存储器”扩展dfa，用于存储在匹配过程中记录辅助信息的位，或记录进度的计数器。当达到接受状态时，将检查暂存存储器，并仅在它包含合适的值时才声明匹配。Snort和cisco IPS对签名集的初步结果表明，与使用多个dfa的解决方案相比，xfasa可以小10倍，同时在软件上快5倍。