BPF

  • BPF (Berkeley Packet Filter) filters packets efficiently in kernel space; copying every packet to user space before filtering would be inefficient.
    • Packets come in at a very fast rate, and in most cases, the packets the user wants to see are only a few of the total packets.
    • Therefore, BPF first performs filtering in Kernel space before passing the packet to User space.
  • BPF runs a small filter program within the kernel and decides whether to forward the packet to user space based on the result.
  • Currently, the existing BPF is sometimes called Classic BPF or cBPF to distinguish it from eBPF.

Why BPF Is Needed

A packet capture tool should check the packets coming into the network interface.

For example, if a user executes the following command:

tcpdump port 80

The user does not want to see all packets, but only those related to port 80.

The simplest method is for the Kernel to copy all packets to User space and tcpdump to check conditions directly in User space.

But this method is inefficient.

  • Even unnecessary packets must be copied to user space.
  • There is a cost for copying data between Kernel space and User space.
  • As the number of packets increases, the load on the capture tool increases.
  • Unnecessary context switches and memory usage may increase.

To solve this problem, BPF first performs packet filtering in Kernel space.

In other words, the core purpose of BPF is to improve packet capture performance by delivering only necessary packets to user space.

Basic Structure of BPF

BPF does not simply mean the filter grammar, but also the entire structure for executing the packet filter.

BPF operates roughly as follows.

  1. User space program creates filter conditions.
  2. The filter condition is converted to BPF instruction.
  3. The converted BPF program is delivered to the Kernel.
  4. Kernel executes BPF program every time a packet comes in.
  5. Depending on the return value of the BPF program, the packet is discarded or delivered to user space.

For example, if you use the following filter in tcpdump:

tcpdump host 192.168.0.10

This filter condition is internally converted to the BPF instruction.

The BPF program reads the Ethernet header, IP header, and TCP header of the packet and checks whether the conditions are met.

If the conditions are met, the packet is delivered to User space. If the conditions are not met, the packet is not delivered to User space.

User Space and Kernel Space

When understanding BPF, important concepts are User space and Kernel space.

  • User space: Area where general programs run
  • Kernel space: Area where the operating system kernel runs

Programs such as tcpdump, Wireshark, and libpcap run in user space.

On the other hand, packets coming into the network interface are first processed by the Kernel.

Therefore, in order for a packet capture tool to view packets, packet data in Kernel space must be transferred to User space.

At this time, if all packets are passed on to user space as is, the cost is high.

Therefore, BPF first executes the filter in Kernel space and delivers only necessary packets to User space.

In other words, BPF can be viewed as a filtering layer that operates between the packet capture program in user space and the network processing path in the kernel.

BPF Program

BPF Program is a small program composed of BPF instruction.

Rather than performing complex logic like a typical C program, it has a simple structure that reads a specific offset of the packet, compares conditions, and finally returns a value.

The BPF program usually performs the following tasks.

  • Reads a value from a specific location in the packet.
  • Compare whether the read value is equal to a specific value.
  • If the conditions are met, move to the next instruction.
  • If the conditions are not met, it branches to another instruction.
  • Ultimately, it decides whether to accept or discard the packet.

For example, to check whether it is an IP packet, you must check the type field of the Ethernet header.

In an Ethernet frame, EtherType is usually located at offset 12.

The EtherType value of IPv4 is 0x0800.

The BPF program can operate roughly as follows.

Read 2 bytes from the 12th offset of the packet.
Compare whether the read value is 0x0800.
If correct, the packet is passed.
Otherwise, the packet is discarded.

From the perspective of BPF, it can be viewed as a small VM program that directly interprets packet data.

BPF Virtual Machine

BPF has a small virtual machine structure internally.

The BPF program is composed of the BPF instruction, not the actual CPU instruction.

Kernel interprets and executes this BPF instruction.

The traditional BPF VM has a very simple structure.

Representative elements include the following:

  • Accumulator Register
  • Index Register
  • Scratch Memory
  • Packet Data
  • BPF Instruction

BPF is not a complex general-purpose VM, but is designed to perform only the minimum operations required for packet filtering.

Therefore, the command structure is simple and the execution flow is limited.

Thanks to this structure, it can be executed relatively safely and quickly within the Kernel.

Accumulator Register and Index Register

Classic BPF mainly uses two registers.

  • A: Accumulator Register
  • X: Index Register

A Register is the register that is the center of calculation.

A Register is mainly used when reading values from packets, comparing them with constants, or performing arithmetic operations.

X Register is an auxiliary Index Register.

It can be used to calculate the variable position of a packet or to access a specific offset.

For example, the length of the IP header may not be fixed.

When the starting position of the TCP header needs to be calculated by reading the IP header length value, an auxiliary register such as the X Register can be used.

In other words, the BPF VM is not a structure with many registers like the general CPU, but a simple structure with only the minimum registers necessary for packet filtering.

Scratch Memory

BPF can use small Scratch Memory.

Scratch Memory is a space for storing temporary values while the BPF program is executed.

It can be seen as similar to a local variable in a general program, but its size and usage are limited.

The BPF program stores the values read from the packet or intermediate calculation results in Scratch Memory and can be used again in later instructions.

However, because BPF is a restricted environment for packet filtering, it is not a structure that allows arbitrary memory access freely.

This restriction is necessary because the BPF program runs within the Kernel.

If the BPF program can arbitrarily read or write kernel memory, problems with kernel stability and security may occur.

BPF Instructions

BPF Instruction is an instruction that BPF VM executes.

BPF instructions can usually be divided into the following types.

  • Load instruction
  • Store instruction
  • ALU instruction
  • Jump instruction
  • Return instruction

Load instruction is an instruction that reads values from packet data or memory.

For example, you can read 1 byte, 2 byte, or 4 byte values at a specific offset of the packet.

Store instruction is an instruction that stores a value in Scratch Memory.

The ALU instruction is an instruction that performs operations such as addition, subtraction, AND, and OR.

Jump instructions are instructions that change the execution flow depending on conditions.

Return instruction is an instruction that returns the final result of the BPF program.

The return value of the BPF program is used to determine how many packets to receive.

BPF Return Values

BPF program returns a value at the end.

This return value becomes the standard for deciding whether to forward the packet to user space.

Generally, if the return value is 0, the packet is discarded.

If the return value is greater than 0, packets of that size are delivered.

For example, if the BPF program returns a value with the following meaning:

return 0

This packet is not delivered to user space.

Conversely, if you return the following value:

return 262144

This can be seen as meaning to let the packet pass.

In other words, the return value in BPF means the packet filtering result, not a simple function return value.

  • 0: Packet discarded
  • Value greater than 0: forward packets of that size

Because of this structure, the BPF program must decide at the end whether to receive the packet or not.

BPF and tcpdump

The easiest tool to view BPF is tcpdump.

tcpdump internally converts the filter expression entered by the user into the BPF instruction.

For example, if you have the following command:

tcpdump tcp port 80

The expression tcp port 80 is a filter syntax that is easy for humans to read.

However, the Kernel cannot execute this string as is.

So tcpdump or libpcap compiles this filter expression into BPF bytecode.

Afterwards, the generated BPF program is delivered to the Kernel.

When a packet comes in, the Kernel executes the corresponding BPF program to check whether this packet meets the tcp port 80 conditions.

If the conditions are met, the packet is delivered to tcpdump. If the conditions are not met, the packet is not delivered.

In other words, tcpdump’s filter grammar is internally converted to the BPF program and executed.

libpcap and BPF

libpcap is a library for packet capture.

tcpdump and other network analysis tools can capture packets using libpcap.

libpcap also plays the role of compiling user-written filter expressions into the BPF instruction.

For example, if a user creates a filter like this:

src host 10.0.0.1 and tcp port 443

libpcap analyzes this expression and converts it into BPF instruction.

After that, packet filtering is performed by attaching the corresponding BPF program to the kernel.

In other words, even if you do not write BPF directly, if you use tcpdump or libpcap, BPF will be used internally.

BPF Filter Example

For example, you can consider a situation where you only want to receive IPv4 packets.

If the EtherType value in the Ethernet header is 0x0800, it is an IPv4 packet.

Expressing this in terms that are easy for people to understand is as follows.

ether proto 0x0800

This condition can be internally converted into the BPF program with the following flow.

1. Read the packet[12:2] value.
2. Compare whether the read value is 0x0800.
3. If they are equal, the packet is passed.
4. If different, the packet is discarded.

From the BPF instruction perspective, it can be viewed roughly as follows.

ldh [12]
jeq #0x0800, pass, drop
pass:
ret #262144
drop:
ret #0

Here, ldh [12] means reading a half-word, that is, 2 bytes from the 12th offset of the packet.

jeq #0x0800 is a conditional branch that compares whether the read value is equal to 0x0800.

If the conditions are met, the packet is passed through with ret #262144. If the conditions are not met, the packet is discarded with ret #0.

In this way, BPF operates by reading a specific location in the packet and comparing conditions.

BPF and Packet Offset

BPF does not directly parse the packet like a structure, but reads the value based on the offset of the packet data.

For example, an Ethernet frame usually has the following structure.

Destination MAC: 6 bytes
Source MAC: 6 bytes
EtherType: 2 bytes
Payload: variable

EtherType is located at the 12th offset of the Ethernet header.

So, the BPF program reads 2 bytes at packet offset 12 to check whether it is an IPv4 packet.

To check the TCP port, you must calculate the location of the TCP header through the Ethernet header and IP header.

At this time, the length of the IP header may vary depending on whether options are available.

So, instead of simply using a fixed offset, there are cases where the header length value must be read to calculate the position of the next header.

In other words, to accurately understand the BPF filter, you must understand the header structure of the network protocol and offset calculation.

Where BPF Runs

BPF is executed in Kernel space before the packet is delivered to User space.

When a packet comes into the network interface, the Kernel executes the BPF filter attached to the socket while processing the packet.

Depending on the result of the BPF filter, it is determined whether the packet will be delivered to the socket.

This structure can be expressed simply as follows.

Network Interface
        ↓
Kernel Network Stack
        ↓
BPF Filter
        ↓
User space Program

Packets that do not meet the conditions in the BPF Filter do not go up to the User space Program.

Therefore, the user space program receives only the packets it needs.

This is the key reason why BPF can improve packet capture performance.

BPF Interpreter and JIT

The BPF program consists of the BPF instruction.

Kernel can interpret and execute this BPF instruction.

This method of reading and executing instructions one by one can be considered the interpreter method.

However, the interpreter method may be slower than directly executing the actual CPU instruction.

So, in some environments, the BPF instruction can be converted to actual machine code and executed.

This is called JIT(Just-In-Time) Compilation.

Using JIT, you can convert the BPF instruction into a native instruction that CPU can execute without interpreting it every time.

In other words, BPF can be executed in the Interpreter method, or it can be executed faster through JIT.

Safety of BPF

Safety is important because the BPF program runs within the Kernel.

If the BPF program runs in an infinite loop, accesses kernel memory incorrectly, or branches to an arbitrary location, the stability of the entire kernel may be affected.

So BPF has more limitations than a typical program.

The traditional BPF has the following characteristics.

  • Uses a limited instruction set.
  • Only limited registers and memory are used.
  • Packet data access is restricted.
  • The execution flow is relatively simple.
  • Run a small program suitable for filtering purposes.

Because of these limitations, BPF is closer to a limited VM for packet filtering rather than a general-purpose program execution environment.

BPF and Packet Capture

BPF plays an important role in packet capture.

Packet capture tools usually do not save or print all traffic.

In many cases, only packets that fit the purpose of analysis are selected and checked.

For example, you could use a filter like this:

tcpdump host 10.0.0.1
tcpdump port 53
tcpdump tcp
tcpdump udp and port 123

Although these filters appear to be simple strings to humans, they are internally converted to the BPF program.

And the Kernel executes the BPF program for each packet and delivers only packets that meet the conditions to user space.

In other words, BPF can be considered a core underlying technology responsible for the filtering performance of packet capture tools.

BPF and Wireshark

Wireshark can also use the BPF filter during the packet capture process.

Wireshark mainly has Capture Filter and Display Filter.

  • Capture Filter: Filter applied when capturing packets
  • Display Filter: Filter applied when already captured packets are displayed on the screen.

Directly related to BPF is Capture Filter.

Capture Filter determines which packets to retrieve at the time of capture.

In other words, packets that do not meet the conditions are not captured in the first place.

On the other hand, Display Filter selects only the packets to be displayed on the screen among packets that have already been captured.

For example, if you set the Capture Filter in Wireshark as follows:

tcp port 80

Only the TCP packet related to port 80 is captured.

However, when set to Display Filter, only packets related to port 80 among the already captured packets are displayed on the screen.

In other words, BPF is more related to the Capture Filter, which filters packets before capturing them.

BPF and seccomp

BPF was created for network packet filtering, but was later used for other purposes as well.

A representative example is seccomp.

seccomp is a security feature in Linux that limits the system calls that a process can use.

The seccomp filter can allow or block system calls using a BPF format filter.

For example, a program can be restricted to using only system calls such as read, write, and exit, and blocks other system calls.

At this time, BPF performs filtering on system call information, not packets.

In other words, BPF was initially created for packet filtering, but because of its structure of checking conditions in limited VMs and returning results, it could also be used for security functions such as system call filtering.

Summary

BPF stands for Berkeley Packet Filter, and is a technology for efficiently filtering packets in kernel space.

If the packet capture tool imports all packets into user space and then filters them, unnecessary copying and processing costs are incurred.

Before passing packets to user space, BPF first performs filtering in kernel space and delivers only necessary packets.