Berkeley Packet Filter and Linux Socket Filtering

隨著電腦網路連線發展，需要分析封包傳了什麼，一開始百家爭鳴，直到 Berkeley Packet Filter (BPF) 造成轟動而變成 de-facto 標準。

1992 《The BSD Packet Filter: A New Architecture for User-level Packet Capture》發表，用簡單的虛擬機器改進封包在 kernel 過濾效率。之後一直擴展移植到其它平台和作業系統，成為 Berkeley Packet Filter (BPF)。(1992 好早喔，我那時候左右才知道 TANET，也才在師或長帶領下小用一兩次)

1997 透過 socket 引入 Linux kernel v2.1.75，稱為 Linux Socket Filter (LSF)，但還是常稱為 BPF，大部分實作放在 net/core/filter.c。

沈寂一段時間後，BPF 持續改善效能，也應用在更多的地方。

2011 Linux v3.0 開始，進一步使用 BPF just-in-time (JIT) 編譯器將 BPF 程式碼轉成原生機器碼的來加速執行。Linux v3.4 用在 SECCOMP，Linux v3.14 新增除錯工具 bpf_asm()、bpf_dbg()。

隨著處理器的演進，BPF 虛擬機器離可運用的原生機器碼越來越遠，對於 BPF 的應用也有更開闊的想法。

2014 Linux v3.15 開始稱為 extended BPF (eBPF) 的全新設計，傳統 BPF 保留為 classical BPF (cBPF)。

在 v3.17 加到 kernel/bpf 下。

Linux 核心封包過濾機制 Linux Socket Filtering (LSF) 源自 Berkeley Packet Filter (BPF)，讓 userspace 程式透過 socket SO_ATTACH_FILTER 選項附上過濾碼到任何 socket，給 kernel 過濾封包。此外，也用在 netfilter 的 xt_bpf、kernel qdisc layer 的 cls_bpf、SECCOMP-BPF、team driver、PTP code 等。

高階過濾指令如 `tcpdump -i em1 port 22`，加上參數 -ddd 可用 libpcap內部編譯器產生 SO_ATTACH_FILTER 用的過濾碼。但如果用到 BPF Linux 擴充，或者較為複雜或需要最佳化等，也可以用低階的 BPF 組合語言撰寫，用在 kernel tools/bpf/ 的工具 bpf_asm 編譯。BPF 組語 syntax 很接近原始的 BPF 論文。

BPF 引擎包括下列暫存器：

• A：32-bit accumulator
• X：32-bit X register
• M[16]：16 x 32-bit 記憶體

在 #include <linux/filter.h> 可看到過濾指令的結構：

struct sock_filter { /* Filter block */
  __u16 code;   /* Actual filter code */
  __u8 jt;      /* Jump offset for true */
  __u8 jf;      /* Jump offset for false */
  __u32 k;      /* Generic multiuse field depends on code */
};

code	定址模式	說明
Load
ld	1, 2, 3, 4, 10	Load 32-bit into A
ldi	4	Load word into A
ldh	1, 2	Load half-word into A
ldb	1, 2	Load byte into A
ldx	3, 4, 5, 10	Load word into X
ldxi	4	Load word into X
ldxb	5	Load byte into X
Store
st	3	Store A into M[]
stx	3	Store X into M[]
Branch
jmp	6	Jump to label
ja	6	Jump to label
jeq	7, 8	Jump on A == k
jneq	8	Jump on A != k
jne	8	Jump on A != k
jlt	8	Jump on A < k
jle	8	Jump on A <= k
jgt	7, 8	Jump on A > k
jge	7, 8	Jump on A >= k
jset	7, 8	Jump on A & k
ALU
add	0, 4	A + <x>
sub	0, 4	A - <x>
mul	0, 4	A * <x>
div	0, 4	A / <x>
mod	0, 4	A % <x>
neg	無	!A
and	0, 4	A & <x>
or	0, 4	A | <x>
xor	0, 4	A ^ <x>
lsh	0, 4	A << <x>
rsh	0, 4	A >> <x>
Miscellaneous
tax	無	Copy A into X
txa	無	Copy X into A
Return
ret	4, 9	Return

定址模式	Syntax	說明
0	x/%x	Register X
1	[k]	BHW at byte offset k in the packet
2	[x + k]	BHW at the offset X + k in the packet
3	M[k]	Word at offset k in M[]
4	#k	Literal value stored in k
5	4*([k]&0xf)	Lower nibble * 4 at byte offset k in the packet
6	L	Jump label L
7	#k,Lt,Lf	Jump to Lt if true, otherwise jump to Lf
8	#k,Lt	Jump to Lt if predicate is true
9	a/%a	Accumulator A
10	extension	BPF extension

Linux 還有 BPF 擴充對載入到 A 指令 "overloading" the k argument with a negative offset + a particular extension offset.

  len                      skb->len
  proto                    skb->protocol
  type                     skb->pkt_type
  poff                     Payload start offset
  ifidx                    skb->dev->ifindex
  nla                      Netlink attribute of type X with offset A
  nlan                     Nested Netlink attribute of type X with offset A
  mark                     skb->mark
  queue                    skb->queue_mapping
  hatype                   skb->dev->type
  rxhash                   skb->hash
  cpu                      raw_smp_processor_id()
  vlan_tci                 skb_vlan_tag_get(skb)
  vlan_avail               skb_vlan_tag_present(skb)
  vlan_tpid                skb->vlan_proto
  rand                     prandom_u32()

BPF 組合語言範例：
ARP 封包: (檔案 foo)

      ldh [12]         /* Load half word offset 12 into A */
      jne #0x806, drop /* Jump to drop if != 0x0806 */
      ret #-1
drop: ret #0

經過 bpf_asm 轉換成 bytecode：

$ ./bpf_asm foo
4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,

C 語言格式輸出方便複製貼上：

$ ./bpf_asm -c foo
{ 0x28,  0,  0, 0x0000000c },
{ 0x15,  0,  1, 0x00000806 },
{ 0x06,  0,  0, 0xffffffff },
{ 0x06,  0,  0, 0000000000 },

IPv4 TCP packets:

      ldh [12]
      jne #0x800, drop
      ldb [23]
      jneq #6, drop
      ret #-1
drop: ret #0

(Accelerated) VLAN w/ id 10:

ld vlan_tci
jneq #10, drop
ret #-1
drop: ret #0

icmp random packet sampling, 1 in 4

ldh [12]
jne #0x800, drop
ldb [23]
jneq #1, drop
# get a random uint32 number
ld rand
mod #4
jneq #1, drop
ret #-1
drop: ret #0

SECCOMP filter example:

ld [4] /* offsetof(struct seccomp_data, arch) */
jne #0xc000003e, bad /* AUDIT_ARCH_X86_64 */
ld [0] /* offsetof(struct seccomp_data, nr) */
jeq #15, good /* __NR_rt_sigreturn */
jeq #231, good /* __NR_exit_group */
jeq #60, good /* __NR_exit */
jeq #0, good /* __NR_read */
jeq #1, good /* __NR_write */
jeq #5, good /* __NR_fstat */
jeq #9, good /* __NR_mmap */
jeq #14, good /* __NR_rt_sigprocmas
k */ jeq #13, good /* __NR_rt_sigaction */
jeq #35, good /* __NR_nanosleep */
bad: ret #0 /* SECCOMP_RET_KILL_THREAD */
good: ret #0x7fff0000 /* SECCOMP_RET_ALLOW */

參考

1. BPF - the forgotten bytecode

• http://sharkfest.wireshark.org/sharkfest.11/ 的 Keynote (Steven McCanne 發展 BPF 的心路歷程)
• Linux Socket Filtering aka Berkeley Packet Filter (BPF) (Linux 也是用 BPF，透過 SO_ATTACH_FILTER 傳送 byte code，但有一些擴展)
• tools/net/bpf_asm：BPF 組譯器，可使用 Linux 擴展，可用來處理對 libpcap 太複雜的過濾或人工的最佳化
• packet mmap (透過 mmap() 加速封包傳收)
• A JIT for packet filters 或 eBPF
• xt_bpf
• cls_bpf (用 BPF 來作流量分類)
• seccomp-bpf (用 BPF 作 system call 過濾)