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)
(the proto of the ethernet header is IPv4 and (the proto of the IPv4 header is tcp or the proto of the IPv4 header is udp)) or (the proto of the ethernet header is IPv6 and (the proto of the IPv6 header is tcp or the proto of the IPv6 header is 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 |
|
with optimization (Radare2 bytecode disassembly)0x00000000 280000000c000000 ldh [12] ; 0xc |
|
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()