Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions
报告人:
Patrick Crowley
Associate professor, in the Department of Computer Science and Engineering at Washington University in St. Louis
报告时间:
2009-06-24 10:30
报告地点:
FIT 1-315
主办单位:
Department of Computer Science and Technology
简介:
Abstract:
Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of two types of finite state machines. Non-deterministic finite automata (NFAs) have minimal storage demand but have high memory bandwidth requirements. Deterministic finite automata (DFAs) exhibit low and deterministic memory bandwidth requirements at the cost of increased memory space. It has already been shown how the presence of wildcards and repetitions of large character classes can render DFAs and NFAs impractical. Additionally, recent security-oriented rule-sets include patterns with advanced features, namely back-references, which add to the expressive power of traditional regular expressions and cannot therefore be supported through classical finite automata.
In this work, we propose and evaluate an extended finite automaton designed to address these shortcomings. First, the automaton provides an alternative approach to handle character repetitions that limits memory space and bandwidth requirements. Second, it supports back-references without the need for backtracking in the input string. In our discussion of this proposal, we address practical implementation issues and evaluate the automaton on real-world rule-sets. To our knowledge, this is the first high-speed automaton that can accommodate all the Perl-compatible regular expressions present in the Snort network intrusion and detection system.
Bio: Patrick Crowley is associate professor in the Department of Computer Science and Engineering at Washington University in St. Louis, where he is a member of the Applied Research Laboratory. Prof. Crowley's research career began at the University of Washington where he earned a Ph.D. in 2003 for his work in the design and study of processor and memory architectures for high-performance networking, a line of research that predated and subsequently influenced the development of commercial network processors. Prof. Crowley is co-editor of the three-book series, Network Processor Design, and co-founded the ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), a premier research conference in the area of high-speed networking systems. His research interest is in computer and network systems architecture, with a current focus on A) designing multicore processors and memory systems, B) building fast, programmable network routers with multicore processors, and C) building novel networks that use fast, programmable network routers. Currently, he serves as a co-chair of the NSF GENI substrate working group. In 2007, Crowley was chosen to join the DARPA Computer Science Study Group. More information is available at: http://www.arl.wustl.edu/~pcrowley.
