Overview

This tool, BPF Exam, illustrates the theory of Berkeley Packet Filter compilation and the practice of its reference implementation in libpcap. It can be used for troubleshooting and debugging as well. To understand what it does, just press the "examine" button below, see some outputs and continue reading.

Compilation of a BPF expression consists of several steps. The first step translates the expression string into a control flow graph (CFG). The second step is conditional, as specified using the optimize argument to pcap_compile(3PCAP); it optimizes the CFG as discussed in detail in this document. The third step translates the CFG into binary bytecode, which can be used by the OS kernel.

Given a set of input parameters below, BPF Exam tries to produce a number of outputs. The first output, which is specific to the DLT_EN10MB link-layer header type only, is a filter expression that should have the same effect as the input filter expression, but includes all the implied predicates explicitly as determined using Caper, which implements the theory set out in this document. The second output, also produced using Caper, is present only if the first output is present and is an automatic English interpretation of the filter expression. Then follows the compiled filter (also known as "filter program" or "packet-matching code") as a sequence of BPF instructions in three formats: an output of tcpdump -d (which is explained in detail in this document), a disassembly produced by Radare2 and a version generated by Caper (again, for DLT_EN10MB only). BPF Exam also tries to reconstruct the final CFG using Radare2 and Graphviz. All these outputs stand for the unoptimized compilation of the filter.

Then, if the optimization attempt has not failed (which can happen, for example, because the filter rejects all packets), BPF Exam displays respective outputs for the optimized compilation plus a snapshot of the CFG for every step of the optimization procedure. The procedure may be internally skipped by libpcap code for some link-layer header types or filter keywords, in which case the unoptimized and the optimized outputs are exactly the same and there are no step-by-step CFG snapshots.

The default filter expression is simple, but representative of everyday BPF usage. You are welcome to experiment with different filter expressions and link-layer header types. If you have any feedback about this tool, please send it to the mailing list.

Input parameters

Equivalent filter (Caper expansion)


        ether proto \ip 
          &&  
        (ip proto \tcp   ||   ip proto \udp)
      ||  
        ether proto \ip6
          &&  
        (ip6 proto \tcp   ||   ip6 proto \udp)

English meaning (Caper translation)

(ethernet that has a proto of IPv4, and (IPv4 that has a proto of tcp, or IPv4 that has a proto of udp)), or (ethernet that has a proto of IPv6, and (IPv6 that has a proto of tcp, or IPv6 that has a proto of udp))

Final packet-matching code

without optimization (libpcap dump)

(000) ldh      [12]
(001) jeq      #0x800           jt 2	jf 4
(002) ldb      [23]
(003) jeq      #0x6             jt 24	jf 4
(004) ldh      [12]
(005) jeq      #0x86dd          jt 6	jf 12
(006) ldb      [20]
(007) jeq      #0x6             jt 24	jf 8
(008) ldb      [20]
(009) jeq      #0x2c            jt 10	jf 12
(010) ldb      [54]
(011) jeq      #0x6             jt 24	jf 12
(012) ldh      [12]
(013) jeq      #0x800           jt 14	jf 16
(014) ldb      [23]
(015) jeq      #0x11            jt 24	jf 16
(016) ldh      [12]
(017) jeq      #0x86dd          jt 18	jf 25
(018) ldb      [20]
(019) jeq      #0x11            jt 24	jf 20
(020) ldb      [20]
(021) jeq      #0x2c            jt 22	jf 25
(022) ldb      [54]
(023) jeq      #0x11            jt 24	jf 25
(024) ret      #65535
(025) ret      #0

with optimization (libpcap dump)

(000) ldh      [12]
(001) jeq      #0x800           jt 2	jf 4
(002) ldb      [23]
(003) jeq      #0x6             jt 11	jf 10
(004) jeq      #0x86dd          jt 5	jf 12
(005) ldb      [20]
(006) jeq      #0x6             jt 11	jf 7
(007) jeq      #0x2c            jt 8	jf 10
(008) ldb      [54]
(009) jeq      #0x6             jt 11	jf 10
(010) jeq      #0x11            jt 11	jf 12
(011) ret      #65535
(012) ret      #0

without optimization (Radare2 bytecode disassembly)

                                   0x00000000      280000000c000000   ldh [12] ; 0xc
                            ╭─╭──< 0x00000008      1500000200080000   jeq 0x800, 0x00000010, 0x00000020
                            ╰────> 0x00000010      3000000017000000   ldb [23] ; 0x17
                            ╭────< 0x00000018      1500140006000000   jeq 0x6, 0x000000c0, 0x00000020
                            │ ╰──> 0x00000020      280000000c000000   ldh [12] ; 0xc
                          ╭───╭──< 0x00000028      15000006dd860000   jeq 0x86dd, 0x00000030, 0x00000060
                          ╰──────> 0x00000030      3000000014000000   ldb [20] ; 0x14
                          ╭──────< 0x00000038      1500100006000000   jeq 0x6, 0x000000c0, 0x00000040
                          │ │ │    0x00000040      3000000014000000   ldb [20] ; 0x14
                      ╭─╭────────< 0x00000048      150000022c000000   jeq 0x2c, 0x00000050, 0x00000060
                      ╰──────────> 0x00000050      3000000036000000   ldb [54] ; 0x36
                      ╭──────────< 0x00000058      15000c0006000000   jeq 0x6, 0x000000c0, 0x00000060
                      │ ╰─────╰──> 0x00000060      280000000c000000   ldh [12] ; 0xc
                      │ ╭─────╭──< 0x00000068      1500000200080000   jeq 0x800, 0x00000070, 0x00000080
                      │ ╰────────> 0x00000070      3000000017000000   ldb [23] ; 0x17
                      │ ╭────────< 0x00000078      1500080011000000   jeq 0x11, 0x000000c0, 0x00000080
                      │ │ │ │ ╰──> 0x00000080      280000000c000000   ldh [12] ; 0xc
                    ╭─────────╭──< 0x00000088      15000007dd860000   jeq 0x86dd, 0x00000090, 0x000000c8
                    ╰────────────> 0x00000090      3000000014000000   ldb [20] ; 0x14
                    ╭────────────< 0x00000098      1500040011000000   jeq 0x11, 0x000000c0, 0x000000a0
                    │ │ │ │ │ │    0x000000a0      3000000014000000   ldb [20] ; 0x14
                ╭─╭──────────────< 0x000000a8      150000032c000000   jeq 0x2c, 0x000000b0, 0x000000c8
                ╰────────────────> 0x000000b0      3000000036000000   ldb [54] ; 0x36
              ╭─╭────────────────< 0x000000b8      1500000111000000   jeq 0x11, 0x000000c0, 0x000000c8
              ╰─────╰─╰─╰─╰─╰────> 0x000000c0      06000000ffff0000   ret 0xffff
                ╰─╰───────────╰──> 0x000000c8      0600000000000000   ret 0

with optimization (Radare2 bytecode disassembly)

                                   0x00000000      280000000c000000   ldh [12] ; 0xc
                            ╭─╭──< 0x00000008      1500000200080000   jeq 0x800, 0x00000010, 0x00000020
                            ╰────> 0x00000010      3000000017000000   ldb [23] ; 0x17
                          ╭─╭────< 0x00000018      1500070606000000   jeq 0x6, 0x00000058, 0x00000050
                      ╭─╭─────╰──> 0x00000020      15000007dd860000   jeq 0x86dd, 0x00000028, 0x00000060
                      ╰──────────> 0x00000028      3000000014000000   ldb [20] ; 0x14
                        │ │ │ ╭──< 0x00000030      1500040006000000   jeq 0x6, 0x00000058, 0x00000038
                    ╭─╭──────────< 0x00000038      150000022c000000   jeq 0x2c, 0x00000040, 0x00000050
                    ╰────────────> 0x00000040      3000000036000000   ldb [54] ; 0x36
                    ╭────────────< 0x00000048      1500010006000000   jeq 0x6, 0x00000058, 0x00000050
                ╭─╭───╰─────╰────> 0x00000050      1500000111000000   jeq 0x11, 0x00000058, 0x00000060
                ╰───╰─────╰───╰──> 0x00000058      06000000ffff0000   ret 0xffff
                  ╰─────╰────────> 0x00000060      0600000000000000   ret 0

without optimization (Caper BPF generator)

l000: ldh [12]
l001: jeq #0x800 , l002 , l004
l002: ldb [23]
l003: jeq #0x6 , l024 , l004
l004: ldh [12]
l005: jeq #0x800 , l006 , l008
l006: ldb [23]
l007: jeq #0x11 , l024 , l008
l008: ldh [12]
l009: jeq #0x86dd , l010 , l016
l010: ldb [20]
l011: jeq #0x6 , l024 , l012
l012: ldb [20]
l013: jeq #0x2c , l014 , l016
l014: ldb [54]
l015: jeq #0x6 , l024 , l016
l016: ldh [12]
l017: jeq #0x86dd , l018 , l025
l018: ldb [20]
l019: jeq #0x11 , l024 , l020
l020: ldb [20]
l021: jeq #0x2c , l022 , l025
l022: ldb [54]
l023: jeq #0x11 , l024 , l025
l024: ret #65535
l025: ret #0

with optimization (Caper BPF generator)

l000: ldh [12]
l001: jeq #0x800 , l002 , l005
l002: ldb [23]
l003: jeq #0x6 , l013 , l004
l004: jeq #0x11 , l013 , l014
l005: jeq #0x86dd , l006 , l014
l006: ldb [20]
l007: jeq #0x6 , l013 , l008
l008: jeq #0x2c , l009 , l011
l009: ldb [54]
l010: jeq #0x6 , l013 , l012
l011: jeq #0x11 , l013 , l014
l012: jeq #0x11 , l013 , l014
l013: ret #65535
l014: ret #0

Final control flow graph (Radare2)

without optimization

with optimization

Optimization step-by-step (libpcap)

1. opt_loop(root, 0) begin

2. opt_loop(root, 0) bottom, done=0

3. opt_loop(root, 0) bottom, done=0

4. opt_loop(root, 0) bottom, done=0

5. opt_loop(root, 0) bottom, done=1

6. opt_loop(root, 1) begin

7. opt_loop(root, 1) bottom, done=1

8. after intern_blocks()

9. after opt_root()