The Berkeley Packet Filter

When you use a packet analysis tool, like Wireshark or tcpdump, and you set up a capture filter to specify the packets you want to look at, you are actually using the Berkeley Packet filter.

The Berkeley Packet Filter was developed by Steven McCanne and Van Jacobson, and described in their 1992  article, The BSD Packet Filter: A New Architecture for User-level Packet Capture. Their goal was to speed up packet-capture processing by filtering packets in the kernel, so that only selected ones needed to be copied to user space. The existing filtering methods at the time were based on the PDP-11 architecture used by early Unix implementations and were not efficient on newer RISC hardware. BPF made packet capture 100 times faster in some cases.

You may be aware that the Java language is compiled into bytecode, a generic, assembly-language-like language that is then interpreted. This is how Java’s “write once, run everywhere” promise is fulfilled. To support Java on a new platform, it is necessary only to create a new bytecode interpreter, which is a lot easier than changing a compiler to emit the platform’s native instructions. The Microsoft .NET ecosystem does something similar: C#, C++/CLI, F#, and Visual Basic all compile into Common Intermediate Language, which is interpreted. Again, it is much easier to make an interpreter for a new platform than to change several compilers. Also, the code generated by the compilers can be sped up by optimizing the interpreter, rather than changing all four compilers.

The Berkeley Packet Filter also compiles filter expressions into bytecode. For example, if you want to capture HTTP packets, so you might enter a filter like this:

TCP Port 80

That gets compiled into a bytecode program that checks the specific fields and flags in each packet to determine whether it should be selected.

Here is the annotated bytecode for the above filter specification. The numbers in square brackets are decimal offsets into the packet.

As with Java and .NET, having a virtual machine makes it possible to port BPF to different hardware by just changing the interpreter, rather than having to redo all the code generation. It also makes it possible to optimize the code when necessary. Just as programs written in high-level languages can sometimes be sped up by rewriting short, heavily-used sections in assembly language, BPF filters can be optimized by optimizing the virtual assembly language they create. The bytecode is checked for validity before being accepted, in order to ensure safety. Things such as loops, recursion, backward jumps, and arbitrary memory accesses are forbidden. 

BPF has now been extended as eBPF, with 64-bit registers, endianness functions, and several other enhancements.

BPF can be used for more than just packet tracing; it can also be used as a fast way to filter packets. iptables, one of the available firewalls on Unix-like systems, has an xt_bpf module that makes it possible to attach BPF bytecode to a rule, and do complicated packet filtering. Here is an article about xt_bpf.

Large networking companies like Cloudflare use BPF extensively to filter packets from denial of service attacks. Here are some excellent blog posts about how they use BPF:

If BPF has piqued your interest, and who want to know everything there is to know about it, this reading list will not let you down:  Dive into BPF: a list of reading material


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *