Guest Talk: Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection Abstract

Wednesday, May 16, 2018, 10:15am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

 

Speaker: Dr. Milan Češka

 

We consider the problem of approximate reduction of non-deterministic automata that appear in hardware-accelerated network intrusion detection systems „NIDSes“. We define an error distance of a reduced automaton from the original one as the probability of packets being incorrectly classified by the reduced automaton, wrt the probabilistic distribution of packets in the network traffic. We use this notion to design an approximate reduction procedure that achieves a great size reduction, much beyond the state-of-the-art language preserving techniques, with a controlled and small error. We have implemented our approach and evaluated it on use cases from SNORT, a popular NIDS. Our results provide experimental evidence that the method can be highly efficient in practice, allowing NIDSes to follow the rapid growth in the speed of networks.

 

Short biography:

Dr. Milan Češka has completed his Ph.D. thesis in the area of data-parallel algorithms for model checking at the Faculty of Informatics, Masaryk University, Brno, Czech Republic in June 2012. Afterwards, he was a research assistant in the Systems Biology Laboratory at the same faculty under supervision of prof. Lubos Brim. From February 2014, he was a postdoctoral researcher at Department of Computer Science at Oxford University in the group led by prof. Marta Kwiatkowska. In May 2016, he returned to Czech Republic as an assistant professor at Faculty of Information Technology, Brno University of Technology. His current research interests include formal methods for automated design of probabilistic and approximate systems, and formal analysis of biochemical systems.