Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mason/linux...
[deliverable/linux.git] / Documentation / networking / filter.txt
1 Linux Socket Filtering aka Berkeley Packet Filter (BPF)
2 =======================================================
3
4 Introduction
5 ------------
6
7 Linux Socket Filtering (LSF) is derived from the Berkeley Packet Filter.
8 Though there are some distinct differences between the BSD and Linux
9 Kernel filtering, but when we speak of BPF or LSF in Linux context, we
10 mean the very same mechanism of filtering in the Linux kernel.
11
12 BPF allows a user-space program to attach a filter onto any socket and
13 allow or disallow certain types of data to come through the socket. LSF
14 follows exactly the same filter code structure as BSD's BPF, so referring
15 to the BSD bpf.4 manpage is very helpful in creating filters.
16
17 On Linux, BPF is much simpler than on BSD. One does not have to worry
18 about devices or anything like that. You simply create your filter code,
19 send it to the kernel via the SO_ATTACH_FILTER option and if your filter
20 code passes the kernel check on it, you then immediately begin filtering
21 data on that socket.
22
23 You can also detach filters from your socket via the SO_DETACH_FILTER
24 option. This will probably not be used much since when you close a socket
25 that has a filter on it the filter is automagically removed. The other
26 less common case may be adding a different filter on the same socket where
27 you had another filter that is still running: the kernel takes care of
28 removing the old one and placing your new one in its place, assuming your
29 filter has passed the checks, otherwise if it fails the old filter will
30 remain on that socket.
31
32 SO_LOCK_FILTER option allows to lock the filter attached to a socket. Once
33 set, a filter cannot be removed or changed. This allows one process to
34 setup a socket, attach a filter, lock it then drop privileges and be
35 assured that the filter will be kept until the socket is closed.
36
37 The biggest user of this construct might be libpcap. Issuing a high-level
38 filter command like `tcpdump -i em1 port 22` passes through the libpcap
39 internal compiler that generates a structure that can eventually be loaded
40 via SO_ATTACH_FILTER to the kernel. `tcpdump -i em1 port 22 -ddd`
41 displays what is being placed into this structure.
42
43 Although we were only speaking about sockets here, BPF in Linux is used
44 in many more places. There's xt_bpf for netfilter, cls_bpf in the kernel
45 qdisc layer, SECCOMP-BPF (SECure COMPuting [1]), and lots of other places
46 such as team driver, PTP code, etc where BPF is being used.
47
48 [1] Documentation/prctl/seccomp_filter.txt
49
50 Original BPF paper:
51
52 Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
53 architecture for user-level packet capture. In Proceedings of the
54 USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
55 Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
56 CA, USA, 2-2. [http://www.tcpdump.org/papers/bpf-usenix93.pdf]
57
58 Structure
59 ---------
60
61 User space applications include <linux/filter.h> which contains the
62 following relevant structures:
63
64 struct sock_filter { /* Filter block */
65 __u16 code; /* Actual filter code */
66 __u8 jt; /* Jump true */
67 __u8 jf; /* Jump false */
68 __u32 k; /* Generic multiuse field */
69 };
70
71 Such a structure is assembled as an array of 4-tuples, that contains
72 a code, jt, jf and k value. jt and jf are jump offsets and k a generic
73 value to be used for a provided code.
74
75 struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
76 unsigned short len; /* Number of filter blocks */
77 struct sock_filter __user *filter;
78 };
79
80 For socket filtering, a pointer to this structure (as shown in
81 follow-up example) is being passed to the kernel through setsockopt(2).
82
83 Example
84 -------
85
86 #include <sys/socket.h>
87 #include <sys/types.h>
88 #include <arpa/inet.h>
89 #include <linux/if_ether.h>
90 /* ... */
91
92 /* From the example above: tcpdump -i em1 port 22 -dd */
93 struct sock_filter code[] = {
94 { 0x28, 0, 0, 0x0000000c },
95 { 0x15, 0, 8, 0x000086dd },
96 { 0x30, 0, 0, 0x00000014 },
97 { 0x15, 2, 0, 0x00000084 },
98 { 0x15, 1, 0, 0x00000006 },
99 { 0x15, 0, 17, 0x00000011 },
100 { 0x28, 0, 0, 0x00000036 },
101 { 0x15, 14, 0, 0x00000016 },
102 { 0x28, 0, 0, 0x00000038 },
103 { 0x15, 12, 13, 0x00000016 },
104 { 0x15, 0, 12, 0x00000800 },
105 { 0x30, 0, 0, 0x00000017 },
106 { 0x15, 2, 0, 0x00000084 },
107 { 0x15, 1, 0, 0x00000006 },
108 { 0x15, 0, 8, 0x00000011 },
109 { 0x28, 0, 0, 0x00000014 },
110 { 0x45, 6, 0, 0x00001fff },
111 { 0xb1, 0, 0, 0x0000000e },
112 { 0x48, 0, 0, 0x0000000e },
113 { 0x15, 2, 0, 0x00000016 },
114 { 0x48, 0, 0, 0x00000010 },
115 { 0x15, 0, 1, 0x00000016 },
116 { 0x06, 0, 0, 0x0000ffff },
117 { 0x06, 0, 0, 0x00000000 },
118 };
119
120 struct sock_fprog bpf = {
121 .len = ARRAY_SIZE(code),
122 .filter = code,
123 };
124
125 sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
126 if (sock < 0)
127 /* ... bail out ... */
128
129 ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));
130 if (ret < 0)
131 /* ... bail out ... */
132
133 /* ... */
134 close(sock);
135
136 The above example code attaches a socket filter for a PF_PACKET socket
137 in order to let all IPv4/IPv6 packets with port 22 pass. The rest will
138 be dropped for this socket.
139
140 The setsockopt(2) call to SO_DETACH_FILTER doesn't need any arguments
141 and SO_LOCK_FILTER for preventing the filter to be detached, takes an
142 integer value with 0 or 1.
143
144 Note that socket filters are not restricted to PF_PACKET sockets only,
145 but can also be used on other socket families.
146
147 Summary of system calls:
148
149 * setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &val, sizeof(val));
150 * setsockopt(sockfd, SOL_SOCKET, SO_DETACH_FILTER, &val, sizeof(val));
151 * setsockopt(sockfd, SOL_SOCKET, SO_LOCK_FILTER, &val, sizeof(val));
152
153 Normally, most use cases for socket filtering on packet sockets will be
154 covered by libpcap in high-level syntax, so as an application developer
155 you should stick to that. libpcap wraps its own layer around all that.
156
157 Unless i) using/linking to libpcap is not an option, ii) the required BPF
158 filters use Linux extensions that are not supported by libpcap's compiler,
159 iii) a filter might be more complex and not cleanly implementable with
160 libpcap's compiler, or iv) particular filter codes should be optimized
161 differently than libpcap's internal compiler does; then in such cases
162 writing such a filter "by hand" can be of an alternative. For example,
163 xt_bpf and cls_bpf users might have requirements that could result in
164 more complex filter code, or one that cannot be expressed with libpcap
165 (e.g. different return codes for various code paths). Moreover, BPF JIT
166 implementors may wish to manually write test cases and thus need low-level
167 access to BPF code as well.
168
169 BPF engine and instruction set
170 ------------------------------
171
172 Under tools/net/ there's a small helper tool called bpf_asm which can
173 be used to write low-level filters for example scenarios mentioned in the
174 previous section. Asm-like syntax mentioned here has been implemented in
175 bpf_asm and will be used for further explanations (instead of dealing with
176 less readable opcodes directly, principles are the same). The syntax is
177 closely modelled after Steven McCanne's and Van Jacobson's BPF paper.
178
179 The BPF architecture consists of the following basic elements:
180
181 Element Description
182
183 A 32 bit wide accumulator
184 X 32 bit wide X register
185 M[] 16 x 32 bit wide misc registers aka "scratch memory
186 store", addressable from 0 to 15
187
188 A program, that is translated by bpf_asm into "opcodes" is an array that
189 consists of the following elements (as already mentioned):
190
191 op:16, jt:8, jf:8, k:32
192
193 The element op is a 16 bit wide opcode that has a particular instruction
194 encoded. jt and jf are two 8 bit wide jump targets, one for condition
195 "jump if true", the other one "jump if false". Eventually, element k
196 contains a miscellaneous argument that can be interpreted in different
197 ways depending on the given instruction in op.
198
199 The instruction set consists of load, store, branch, alu, miscellaneous
200 and return instructions that are also represented in bpf_asm syntax. This
201 table lists all bpf_asm instructions available resp. what their underlying
202 opcodes as defined in linux/filter.h stand for:
203
204 Instruction Addressing mode Description
205
206 ld 1, 2, 3, 4, 10 Load word into A
207 ldi 4 Load word into A
208 ldh 1, 2 Load half-word into A
209 ldb 1, 2 Load byte into A
210 ldx 3, 4, 5, 10 Load word into X
211 ldxi 4 Load word into X
212 ldxb 5 Load byte into X
213
214 st 3 Store A into M[]
215 stx 3 Store X into M[]
216
217 jmp 6 Jump to label
218 ja 6 Jump to label
219 jeq 7, 8 Jump on k == A
220 jneq 8 Jump on k != A
221 jne 8 Jump on k != A
222 jlt 8 Jump on k < A
223 jle 8 Jump on k <= A
224 jgt 7, 8 Jump on k > A
225 jge 7, 8 Jump on k >= A
226 jset 7, 8 Jump on k & A
227
228 add 0, 4 A + <x>
229 sub 0, 4 A - <x>
230 mul 0, 4 A * <x>
231 div 0, 4 A / <x>
232 mod 0, 4 A % <x>
233 neg 0, 4 !A
234 and 0, 4 A & <x>
235 or 0, 4 A | <x>
236 xor 0, 4 A ^ <x>
237 lsh 0, 4 A << <x>
238 rsh 0, 4 A >> <x>
239
240 tax Copy A into X
241 txa Copy X into A
242
243 ret 4, 9 Return
244
245 The next table shows addressing formats from the 2nd column:
246
247 Addressing mode Syntax Description
248
249 0 x/%x Register X
250 1 [k] BHW at byte offset k in the packet
251 2 [x + k] BHW at the offset X + k in the packet
252 3 M[k] Word at offset k in M[]
253 4 #k Literal value stored in k
254 5 4*([k]&0xf) Lower nibble * 4 at byte offset k in the packet
255 6 L Jump label L
256 7 #k,Lt,Lf Jump to Lt if true, otherwise jump to Lf
257 8 #k,Lt Jump to Lt if predicate is true
258 9 a/%a Accumulator A
259 10 extension BPF extension
260
261 The Linux kernel also has a couple of BPF extensions that are used along
262 with the class of load instructions by "overloading" the k argument with
263 a negative offset + a particular extension offset. The result of such BPF
264 extensions are loaded into A.
265
266 Possible BPF extensions are shown in the following table:
267
268 Extension Description
269
270 len skb->len
271 proto skb->protocol
272 type skb->pkt_type
273 poff Payload start offset
274 ifidx skb->dev->ifindex
275 nla Netlink attribute of type X with offset A
276 nlan Nested Netlink attribute of type X with offset A
277 mark skb->mark
278 queue skb->queue_mapping
279 hatype skb->dev->type
280 rxhash skb->rxhash
281 cpu raw_smp_processor_id()
282 vlan_tci vlan_tx_tag_get(skb)
283 vlan_pr vlan_tx_tag_present(skb)
284
285 These extensions can also be prefixed with '#'.
286 Examples for low-level BPF:
287
288 ** ARP packets:
289
290 ldh [12]
291 jne #0x806, drop
292 ret #-1
293 drop: ret #0
294
295 ** IPv4 TCP packets:
296
297 ldh [12]
298 jne #0x800, drop
299 ldb [23]
300 jneq #6, drop
301 ret #-1
302 drop: ret #0
303
304 ** (Accelerated) VLAN w/ id 10:
305
306 ld vlan_tci
307 jneq #10, drop
308 ret #-1
309 drop: ret #0
310
311 ** SECCOMP filter example:
312
313 ld [4] /* offsetof(struct seccomp_data, arch) */
314 jne #0xc000003e, bad /* AUDIT_ARCH_X86_64 */
315 ld [0] /* offsetof(struct seccomp_data, nr) */
316 jeq #15, good /* __NR_rt_sigreturn */
317 jeq #231, good /* __NR_exit_group */
318 jeq #60, good /* __NR_exit */
319 jeq #0, good /* __NR_read */
320 jeq #1, good /* __NR_write */
321 jeq #5, good /* __NR_fstat */
322 jeq #9, good /* __NR_mmap */
323 jeq #14, good /* __NR_rt_sigprocmask */
324 jeq #13, good /* __NR_rt_sigaction */
325 jeq #35, good /* __NR_nanosleep */
326 bad: ret #0 /* SECCOMP_RET_KILL */
327 good: ret #0x7fff0000 /* SECCOMP_RET_ALLOW */
328
329 The above example code can be placed into a file (here called "foo"), and
330 then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf
331 and cls_bpf understands and can directly be loaded with. Example with above
332 ARP code:
333
334 $ ./bpf_asm foo
335 4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,
336
337 In copy and paste C-like output:
338
339 $ ./bpf_asm -c foo
340 { 0x28, 0, 0, 0x0000000c },
341 { 0x15, 0, 1, 0x00000806 },
342 { 0x06, 0, 0, 0xffffffff },
343 { 0x06, 0, 0, 0000000000 },
344
345 In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF
346 filters that might not be obvious at first, it's good to test filters before
347 attaching to a live system. For that purpose, there's a small tool called
348 bpf_dbg under tools/net/ in the kernel source directory. This debugger allows
349 for testing BPF filters against given pcap files, single stepping through the
350 BPF code on the pcap's packets and to do BPF machine register dumps.
351
352 Starting bpf_dbg is trivial and just requires issuing:
353
354 # ./bpf_dbg
355
356 In case input and output do not equal stdin/stdout, bpf_dbg takes an
357 alternative stdin source as a first argument, and an alternative stdout
358 sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`.
359
360 Other than that, a particular libreadline configuration can be set via
361 file "~/.bpf_dbg_init" and the command history is stored in the file
362 "~/.bpf_dbg_history".
363
364 Interaction in bpf_dbg happens through a shell that also has auto-completion
365 support (follow-up example commands starting with '>' denote bpf_dbg shell).
366 The usual workflow would be to ...
367
368 > load bpf 6,40 0 0 12,21 0 3 2048,48 0 0 23,21 0 1 1,6 0 0 65535,6 0 0 0
369 Loads a BPF filter from standard output of bpf_asm, or transformed via
370 e.g. `tcpdump -iem1 -ddd port 22 | tr '\n' ','`. Note that for JIT
371 debugging (next section), this command creates a temporary socket and
372 loads the BPF code into the kernel. Thus, this will also be useful for
373 JIT developers.
374
375 > load pcap foo.pcap
376 Loads standard tcpdump pcap file.
377
378 > run [<n>]
379 bpf passes:1 fails:9
380 Runs through all packets from a pcap to account how many passes and fails
381 the filter will generate. A limit of packets to traverse can be given.
382
383 > disassemble
384 l0: ldh [12]
385 l1: jeq #0x800, l2, l5
386 l2: ldb [23]
387 l3: jeq #0x1, l4, l5
388 l4: ret #0xffff
389 l5: ret #0
390 Prints out BPF code disassembly.
391
392 > dump
393 /* { op, jt, jf, k }, */
394 { 0x28, 0, 0, 0x0000000c },
395 { 0x15, 0, 3, 0x00000800 },
396 { 0x30, 0, 0, 0x00000017 },
397 { 0x15, 0, 1, 0x00000001 },
398 { 0x06, 0, 0, 0x0000ffff },
399 { 0x06, 0, 0, 0000000000 },
400 Prints out C-style BPF code dump.
401
402 > breakpoint 0
403 breakpoint at: l0: ldh [12]
404 > breakpoint 1
405 breakpoint at: l1: jeq #0x800, l2, l5
406 ...
407 Sets breakpoints at particular BPF instructions. Issuing a `run` command
408 will walk through the pcap file continuing from the current packet and
409 break when a breakpoint is being hit (another `run` will continue from
410 the currently active breakpoint executing next instructions):
411
412 > run
413 -- register dump --
414 pc: [0] <-- program counter
415 code: [40] jt[0] jf[0] k[12] <-- plain BPF code of current instruction
416 curr: l0: ldh [12] <-- disassembly of current instruction
417 A: [00000000][0] <-- content of A (hex, decimal)
418 X: [00000000][0] <-- content of X (hex, decimal)
419 M[0,15]: [00000000][0] <-- folded content of M (hex, decimal)
420 -- packet dump -- <-- Current packet from pcap (hex)
421 len: 42
422 0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
423 16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
424 32: 00 00 00 00 00 00 0a 3b 01 01
425 (breakpoint)
426 >
427
428 > breakpoint
429 breakpoints: 0 1
430 Prints currently set breakpoints.
431
432 > step [-<n>, +<n>]
433 Performs single stepping through the BPF program from the current pc
434 offset. Thus, on each step invocation, above register dump is issued.
435 This can go forwards and backwards in time, a plain `step` will break
436 on the next BPF instruction, thus +1. (No `run` needs to be issued here.)
437
438 > select <n>
439 Selects a given packet from the pcap file to continue from. Thus, on
440 the next `run` or `step`, the BPF program is being evaluated against
441 the user pre-selected packet. Numbering starts just as in Wireshark
442 with index 1.
443
444 > quit
445 #
446 Exits bpf_dbg.
447
448 JIT compiler
449 ------------
450
451 The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC, PowerPC,
452 ARM and s390 and can be enabled through CONFIG_BPF_JIT. The JIT compiler is
453 transparently invoked for each attached filter from user space or for internal
454 kernel users if it has been previously enabled by root:
455
456 echo 1 > /proc/sys/net/core/bpf_jit_enable
457
458 For JIT developers, doing audits etc, each compile run can output the generated
459 opcode image into the kernel log via:
460
461 echo 2 > /proc/sys/net/core/bpf_jit_enable
462
463 Example output from dmesg:
464
465 [ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
466 [ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
467 [ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
468 [ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
469 [ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
470 [ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3
471
472 In the kernel source tree under tools/net/, there's bpf_jit_disasm for
473 generating disassembly out of the kernel log's hexdump:
474
475 # ./bpf_jit_disasm
476 70 bytes emitted from JIT compiler (pass:3, flen:6)
477 ffffffffa0069c8f + <x>:
478 0: push %rbp
479 1: mov %rsp,%rbp
480 4: sub $0x60,%rsp
481 8: mov %rbx,-0x8(%rbp)
482 c: mov 0x68(%rdi),%r9d
483 10: sub 0x6c(%rdi),%r9d
484 14: mov 0xd8(%rdi),%r8
485 1b: mov $0xc,%esi
486 20: callq 0xffffffffe0ff9442
487 25: cmp $0x800,%eax
488 2a: jne 0x0000000000000042
489 2c: mov $0x17,%esi
490 31: callq 0xffffffffe0ff945e
491 36: cmp $0x1,%eax
492 39: jne 0x0000000000000042
493 3b: mov $0xffff,%eax
494 40: jmp 0x0000000000000044
495 42: xor %eax,%eax
496 44: leaveq
497 45: retq
498
499 Issuing option `-o` will "annotate" opcodes to resulting assembler
500 instructions, which can be very useful for JIT developers:
501
502 # ./bpf_jit_disasm -o
503 70 bytes emitted from JIT compiler (pass:3, flen:6)
504 ffffffffa0069c8f + <x>:
505 0: push %rbp
506 55
507 1: mov %rsp,%rbp
508 48 89 e5
509 4: sub $0x60,%rsp
510 48 83 ec 60
511 8: mov %rbx,-0x8(%rbp)
512 48 89 5d f8
513 c: mov 0x68(%rdi),%r9d
514 44 8b 4f 68
515 10: sub 0x6c(%rdi),%r9d
516 44 2b 4f 6c
517 14: mov 0xd8(%rdi),%r8
518 4c 8b 87 d8 00 00 00
519 1b: mov $0xc,%esi
520 be 0c 00 00 00
521 20: callq 0xffffffffe0ff9442
522 e8 1d 94 ff e0
523 25: cmp $0x800,%eax
524 3d 00 08 00 00
525 2a: jne 0x0000000000000042
526 75 16
527 2c: mov $0x17,%esi
528 be 17 00 00 00
529 31: callq 0xffffffffe0ff945e
530 e8 28 94 ff e0
531 36: cmp $0x1,%eax
532 83 f8 01
533 39: jne 0x0000000000000042
534 75 07
535 3b: mov $0xffff,%eax
536 b8 ff ff 00 00
537 40: jmp 0x0000000000000044
538 eb 02
539 42: xor %eax,%eax
540 31 c0
541 44: leaveq
542 c9
543 45: retq
544 c3
545
546 For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful
547 toolchain for developing and testing the kernel's JIT compiler.
548
549 Misc
550 ----
551
552 Also trinity, the Linux syscall fuzzer, has built-in support for BPF and
553 SECCOMP-BPF kernel fuzzing.
554
555 Written by
556 ----------
557
558 The document was written in the hope that it is found useful and in order
559 to give potential BPF hackers or security auditors a better overview of
560 the underlying architecture.
561
562 Jay Schulist <jschlst@samba.org>
563 Daniel Borkmann <dborkman@redhat.com>
This page took 0.043344 seconds and 6 git commands to generate.