A&S Departments and Programs   • Graduate Study Offered   American Studies • Anthropology • Applied Science • Art & Art History Biology • Black Studies Chemistry • Classical Studies Computer Science • Economics English Environmental Science & Policy Film Studies Geology Global Studies Government History • International Relations Kinesiology Linguistics Literary & Cultural Studies Mathematics Medieval & Renaissance Studies Military Science Modern Languages Music Neuroscience Philosophy Physics • Psychology • Public Policy • Religious Studies Sociology Theater, Speech & Dance Women's Studies

Search

Find People

Computer Science Department

Computer Science Department

Fast Packet Filtering by Exploiting CISC and SIMD ISA

Zhenyu Wu
Wednesday, April 18, 12:00PM McGl 002

Packet filtering is a kernel facility for classifying network packets according to criteria specified by user applications, and conveying the captured packets from network interfaces directly to the designated userspace without traversing normal network stack. Since the birth of the seminal BSD Packet Filter (BPF), packet filters have become critical infrastructure for network monitoring, engineering and security applications. In recent years, packet filters are facing intensified challenges posed by dramatically increasing network speed and escalating network application complexity. However, existing packet filter systems have not yet fully addressed these challenges in an efficient and secure manner.

This thesis presents the New Packet Filter (NPF), a packet filter for high performance packet capture on commercial off-the-shelf hardware. The key features of NPF include (1) extremely low filter update latency with a strong security model for dynamic packet filtering; and (2) Gbps high speed packet processing. NPF achieves the former by employing a finite-state automata model as the pseudo-machine abstraction; and the latter by adopting CISC (Complex Instruction Set Computer) and SIMD (Single Instruction, Multiple Data) Instruction Set Architecture. The userspace library of NPF provides two sets of APIs (Application Programming Interfaces). One is to exploit the advantages of NPF in speed and security, while the other is for backward compatibility with existing BPF-based applications. We implement NPF in the latest 2.6 Linux kernel for both i386 and x86_64 architectures. We extensively evaluate its static and dynamic filtering performance on multiple machines with various hardware setups, and compare with BPF (the BSD packet filter), which is the de facto standard for packet filtering in modern operating systems, and optimized C filters that are used as the ceiling on performance. For static filtering tasks, NPF can be up to three times as fast as BPF; for dynamic filtering tasks, NPF can capture many more packets and data sessions than BPF, and is three orders of magnitude faster than BPF in terms of filter update latency.