Information Technology
Faster, Smaller Alternative (XFAs) for Use in Network Intrusion
Detection Systems to Identify Malware
WARF: P07258US
Inventors: Somesh Jha, Cristian Estan, Randy Smith
The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing software that provides a small and fast alternative to the finite state automata currently used to recognize patterns and signatures in intrusion detection systems.
Overview
Network intrusion detection systems (NIDS) help protect computer and telecommunication networks from worms, viruses and other malicious software, known as malware. NIDS rely on a set of signatures to identify malicious network traffic. If the network activity matches one of the signatures, the system blocks the intrusion and alerts the network administrator.
Finite state automata (FSAs) are used to recognize suspicious patterns in data when matched against signatures of malicious software. Deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) are two common categories of FSAs used to compare program signatures to known intruders. NFAs take up little system space but are computationally expensive and run slowly. DFAs run quickly but require vast amounts of memory. As signatures become increasingly complex, matching them against traffic using NFAs or DFAs becomes a performance bottleneck for intrusion detection systems.
Finite state automata (FSAs) are used to recognize suspicious patterns in data when matched against signatures of malicious software. Deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) are two common categories of FSAs used to compare program signatures to known intruders. NFAs take up little system space but are computationally expensive and run slowly. DFAs run quickly but require vast amounts of memory. As signatures become increasingly complex, matching them against traffic using NFAs or DFAs becomes a performance bottleneck for intrusion detection systems.
The Invention
UW-Madison researchers have developed systems and methods for creating extended finite automata (XFAs), a smaller and faster alternative to DFAs and NFAs. The XFAs operate similarly to DFAs but use small amounts of “scratch memory,” a partition of memory that records the progress made in matching signatures. The signature matches are recorded as values stored in scratch memory, rather than distinctly and redundantly as in DFAs. As a result, required memory space grows linearly rather than exponentially.
Applications
- Intrusion detection systems in computer and telecommunication networks
Key Benefits
- Prototype implementation showed that XFAs are at least 10,000 times smaller than comprehensive DFAs.
- XFAs are up to 10 times smaller and five times faster or five times smaller and 20 times faster than multiple DFA systems.
- Memory requirements are small, similar to those of NFAs.
- Performance is similar to that of DFAs.
- Usable during deep packet inspection
- Tracks process of recognizing signatures
- Contains small programs that update variables in scratch memory
- Cost is similar to DFAs.
- Requires no custom hardware
- XFAs are deterministic.
Additional Information
For More Information About the Inventors
Publications
For current licensing status, please contact Emily Bauer at [javascript protected email address] or 608-960-9842
- Kong S., Smith S. and Estan C. 2008. Efficient Signature Matching with Multiple Alphabet Compression Tables. Conf. SecureComm.