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

点击翻译按钮获取中文摘要

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.