825 lines · plain
1 2=============3eBPF verifier4=============5 6The safety of the eBPF program is determined in two steps.7 8First step does DAG check to disallow loops and other CFG validation.9In particular it will detect programs that have unreachable instructions.10(though classic BPF checker allows them)11 12Second step starts from the first insn and descends all possible paths.13It simulates execution of every insn and observes the state change of14registers and stack.15 16At the start of the program the register R1 contains a pointer to context17and has type PTR_TO_CTX.18If verifier sees an insn that does R2=R1, then R2 has now type19PTR_TO_CTX as well and can be used on the right hand side of expression.20If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,21since addition of two valid pointers makes invalid pointer.22(In 'secure' mode verifier will reject any type of pointer arithmetic to make23sure that kernel addresses don't leak to unprivileged users)24 25If register was never written to, it's not readable::26 27 bpf_mov R0 = R228 bpf_exit29 30will be rejected, since R2 is unreadable at the start of the program.31 32After kernel function call, R1-R5 are reset to unreadable and33R0 has a return type of the function.34 35Since R6-R9 are callee saved, their state is preserved across the call.36 37::38 39 bpf_mov R6 = 140 bpf_call foo41 bpf_mov R0 = R642 bpf_exit43 44is a correct program. If there was R1 instead of R6, it would have45been rejected.46 47load/store instructions are allowed only with registers of valid types, which48are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.49For example::50 51 bpf_mov R1 = 152 bpf_mov R2 = 253 bpf_xadd *(u32 *)(R1 + 3) += R254 bpf_exit55 56will be rejected, since R1 doesn't have a valid pointer type at the time of57execution of instruction bpf_xadd.58 59At the start R1 type is PTR_TO_CTX (a pointer to generic ``struct bpf_context``)60A callback is used to customize verifier to restrict eBPF program access to only61certain fields within ctx structure with specified size and alignment.62 63For example, the following insn::64 65 bpf_ld R0 = *(u32 *)(R6 + 8)66 67intends to load a word from address R6 + 8 and store it into R068If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know69that offset 8 of size 4 bytes can be accessed for reading, otherwise70the verifier will reject the program.71If R6=PTR_TO_STACK, then access should be aligned and be within72stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,73so it will fail verification, since it's out of bounds.74 75The verifier will allow eBPF program to read data from stack only after76it wrote into it.77 78Classic BPF verifier does similar check with M[0-15] memory slots.79For example::80 81 bpf_ld R0 = *(u32 *)(R10 - 4)82 bpf_exit83 84is invalid program.85Though R10 is correct read-only register and has type PTR_TO_STACK86and R10 - 4 is within stack bounds, there were no stores into that location.87 88Pointer register spill/fill is tracked as well, since four (R6-R9)89callee saved registers may not be enough for some programs.90 91Allowed function calls are customized with bpf_verifier_ops->get_func_proto()92The eBPF verifier will check that registers match argument constraints.93After the call register R0 will be set to return type of the function.94 95Function calls is a main mechanism to extend functionality of eBPF programs.96Socket filters may let programs to call one set of functions, whereas tracing97filters may allow completely different set.98 99If a function made accessible to eBPF program, it needs to be thought through100from safety point of view. The verifier will guarantee that the function is101called with valid arguments.102 103seccomp vs socket filters have different security restrictions for classic BPF.104Seccomp solves this by two stage verifier: classic BPF verifier is followed105by seccomp verifier. In case of eBPF one configurable verifier is shared for106all use cases.107 108See details of eBPF verifier in kernel/bpf/verifier.c109 110Register value tracking111=======================112 113In order to determine the safety of an eBPF program, the verifier must track114the range of possible values in each register and also in each stack slot.115This is done with ``struct bpf_reg_state``, defined in include/linux/116bpf_verifier.h, which unifies tracking of scalar and pointer values. Each117register state has a type, which is either NOT_INIT (the register has not been118written to), SCALAR_VALUE (some value which is not usable as a pointer), or a119pointer type. The types of pointers describe their base, as follows:120 121 122 PTR_TO_CTX123 Pointer to bpf_context.124 CONST_PTR_TO_MAP125 Pointer to struct bpf_map. "Const" because arithmetic126 on these pointers is forbidden.127 PTR_TO_MAP_VALUE128 Pointer to the value stored in a map element.129 PTR_TO_MAP_VALUE_OR_NULL130 Either a pointer to a map value, or NULL; map accesses131 (see maps.rst) return this type, which becomes a132 PTR_TO_MAP_VALUE when checked != NULL. Arithmetic on133 these pointers is forbidden.134 PTR_TO_STACK135 Frame pointer.136 PTR_TO_PACKET137 skb->data.138 PTR_TO_PACKET_END139 skb->data + headlen; arithmetic forbidden.140 PTR_TO_SOCKET141 Pointer to struct bpf_sock_ops, implicitly refcounted.142 PTR_TO_SOCKET_OR_NULL143 Either a pointer to a socket, or NULL; socket lookup144 returns this type, which becomes a PTR_TO_SOCKET when145 checked != NULL. PTR_TO_SOCKET is reference-counted,146 so programs must release the reference through the147 socket release function before the end of the program.148 Arithmetic on these pointers is forbidden.149 150However, a pointer may be offset from this base (as a result of pointer151arithmetic), and this is tracked in two parts: the 'fixed offset' and 'variable152offset'. The former is used when an exactly-known value (e.g. an immediate153operand) is added to a pointer, while the latter is used for values which are154not exactly known. The variable offset is also used in SCALAR_VALUEs, to track155the range of possible values in the register.156 157The verifier's knowledge about the variable offset consists of:158 159* minimum and maximum values as unsigned160* minimum and maximum values as signed161 162* knowledge of the values of individual bits, in the form of a 'tnum': a u64163 'mask' and a u64 'value'. 1s in the mask represent bits whose value is unknown;164 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both165 mask and value; no bit should ever be 1 in both. For example, if a byte is read166 into a register from memory, the register's top 56 bits are known zero, while167 the low 8 are unknown - which is represented as the tnum (0x0; 0xff). If we168 then OR this with 0x40, we get (0x40; 0xbf), then if we add 1 we get (0x0;169 0x1ff), because of potential carries.170 171Besides arithmetic, the register state can also be updated by conditional172branches. For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch173it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false'174branch it will have a umax_value of 8. A signed compare (with BPF_JSGT or175BPF_JSGE) would instead update the signed minimum/maximum values. Information176from the signed and unsigned bounds can be combined; for instance if a value is177first tested < 8 and then tested s> 4, the verifier will conclude that the value178is also > 4 and s< 8, since the bounds prevent crossing the sign boundary.179 180PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all181pointers sharing that same variable offset. This is important for packet range182checks: after adding a variable to a packet pointer register A, if you then copy183it to another register B and then add a constant 4 to A, both registers will184share the same 'id' but the A will have a fixed offset of +4. Then if A is185bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is186now known to have a safe range of at least 4 bytes. See 'Direct packet access',187below, for more on PTR_TO_PACKET ranges.188 189The 'id' field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of190the pointer returned from a map lookup. This means that when one copy is191checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs.192As well as range-checking, the tracked information is also used for enforcing193alignment of pointer accesses. For instance, on most systems the packet pointer194is 2 bytes after a 4-byte alignment. If a program adds 14 bytes to that to jump195over the Ethernet header, then reads IHL and adds (IHL * 4), the resulting196pointer will have a variable offset known to be 4n+2 for some n, so adding the 2197bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through198that pointer are safe.199The 'id' field is also used on PTR_TO_SOCKET and PTR_TO_SOCKET_OR_NULL, common200to all copies of the pointer returned from a socket lookup. This has similar201behaviour to the handling for PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE, but202it also handles reference tracking for the pointer. PTR_TO_SOCKET implicitly203represents a reference to the corresponding ``struct sock``. To ensure that the204reference is not leaked, it is imperative to NULL-check the reference and in205the non-NULL case, and pass the valid reference to the socket release function.206 207Direct packet access208====================209 210In cls_bpf and act_bpf programs the verifier allows direct access to the packet211data via skb->data and skb->data_end pointers.212Ex::213 214 1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */215 2: r3 = *(u32 *)(r1 +76) /* load skb->data */216 3: r5 = r3217 4: r5 += 14218 5: if r5 > r4 goto pc+16219 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp220 6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */221 222this 2byte load from the packet is safe to do, since the program author223did check ``if (skb->data + 14 > skb->data_end) goto err`` at insn #5 which224means that in the fall-through case the register R3 (which points to skb->data)225has at least 14 directly accessible bytes. The verifier marks it226as R3=pkt(id=0,off=0,r=14).227id=0 means that no additional variables were added to the register.228off=0 means that no additional constants were added.229r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.230Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points231to the packet data, but constant 14 was added to the register, so232it now points to ``skb->data + 14`` and accessible range is [R5, R5 + 14 - 14)233which is zero bytes.234 235More complex packet access may look like::236 237 238 R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp239 6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */240 7: r4 = *(u8 *)(r3 +12)241 8: r4 *= 14242 9: r3 = *(u32 *)(r1 +76) /* load skb->data */243 10: r3 += r4244 11: r2 = r1245 12: r2 <<= 48246 13: r2 >>= 48247 14: r3 += r2248 15: r2 = r3249 16: r2 += 8250 17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */251 18: if r2 > r1 goto pc+2252 R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp253 19: r1 = *(u8 *)(r3 +4)254 255The state of the register R3 is R3=pkt(id=2,off=0,r=8)256id=2 means that two ``r3 += rX`` instructions were seen, so r3 points to some257offset within a packet and since the program author did258``if (r3 + 8 > r1) goto err`` at insn #18, the safe range is [R3, R3 + 8).259The verifier only allows 'add'/'sub' operations on packet registers. Any other260operation will set the register state to 'SCALAR_VALUE' and it won't be261available for direct packet access.262 263Operation ``r3 += rX`` may overflow and become less than original skb->data,264therefore the verifier has to prevent that. So when it sees ``r3 += rX``265instruction and rX is more than 16-bit value, any subsequent bounds-check of r3266against skb->data_end will not give us 'range' information, so attempts to read267through the pointer will give "invalid access to packet" error.268 269Ex. after insn ``r4 = *(u8 *)(r3 +12)`` (insn #7 above) the state of r4 is270R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits271of the register are guaranteed to be zero, and nothing is known about the lower2728 bits. After insn ``r4 *= 14`` the state becomes273R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit274value by constant 14 will keep upper 52 bits as zero, also the least significant275bit will be zero as 14 is even. Similarly ``r2 >>= 48`` will make276R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign277extending. This logic is implemented in adjust_reg_min_max_vals() function,278which calls adjust_ptr_min_max_vals() for adding pointer to scalar (or vice279versa) and adjust_scalar_min_max_vals() for operations on two scalars.280 281The end result is that bpf program author can access packet directly282using normal C code as::283 284 void *data = (void *)(long)skb->data;285 void *data_end = (void *)(long)skb->data_end;286 struct eth_hdr *eth = data;287 struct iphdr *iph = data + sizeof(*eth);288 struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);289 290 if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)291 return 0;292 if (eth->h_proto != htons(ETH_P_IP))293 return 0;294 if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)295 return 0;296 if (udp->dest == 53 || udp->source == 9)297 ...;298 299which makes such programs easier to write comparing to LD_ABS insn300and significantly faster.301 302Pruning303=======304 305The verifier does not actually walk all possible paths through the program. For306each new branch to analyse, the verifier looks at all the states it's previously307been in when at this instruction. If any of them contain the current state as a308subset, the branch is 'pruned' - that is, the fact that the previous state was309accepted implies the current state would be as well. For instance, if in the310previous state, r1 held a packet-pointer, and in the current state, r1 holds a311packet-pointer with a range as long or longer and at least as strict an312alignment, then r1 is safe. Similarly, if r2 was NOT_INIT before then it can't313have been used by any path from that point, so any value in r2 (including314another NOT_INIT) is safe. The implementation is in the function regsafe().315Pruning considers not only the registers but also the stack (and any spilled316registers it may hold). They must all be safe for the branch to be pruned.317This is implemented in states_equal().318 319Some technical details about state pruning implementation could be found below.320 321Register liveness tracking322--------------------------323 324In order to make state pruning effective, liveness state is tracked for each325register and stack slot. The basic idea is to track which registers and stack326slots are actually used during subseqeuent execution of the program, until327program exit is reached. Registers and stack slots that were never used could be328removed from the cached state thus making more states equivalent to a cached329state. This could be illustrated by the following program::330 331 0: call bpf_get_prandom_u32()332 1: r1 = 0333 2: if r0 == 0 goto +1334 3: r0 = 1335 --- checkpoint ---336 4: r0 = r1337 5: exit338 339Suppose that a state cache entry is created at instruction #4 (such entries are340also called "checkpoints" in the text below). The verifier could reach the341instruction with one of two possible register states:342 343* r0 = 1, r1 = 0344* r0 = 0, r1 = 0345 346However, only the value of register ``r1`` is important to successfully finish347verification. The goal of the liveness tracking algorithm is to spot this fact348and figure out that both states are actually equivalent.349 350Data structures351~~~~~~~~~~~~~~~352 353Liveness is tracked using the following data structures::354 355 enum bpf_reg_liveness {356 REG_LIVE_NONE = 0,357 REG_LIVE_READ32 = 0x1,358 REG_LIVE_READ64 = 0x2,359 REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,360 REG_LIVE_WRITTEN = 0x4,361 REG_LIVE_DONE = 0x8,362 };363 364 struct bpf_reg_state {365 ...366 struct bpf_reg_state *parent;367 ...368 enum bpf_reg_liveness live;369 ...370 };371 372 struct bpf_stack_state {373 struct bpf_reg_state spilled_ptr;374 ...375 };376 377 struct bpf_func_state {378 struct bpf_reg_state regs[MAX_BPF_REG];379 ...380 struct bpf_stack_state *stack;381 }382 383 struct bpf_verifier_state {384 struct bpf_func_state *frame[MAX_CALL_FRAMES];385 struct bpf_verifier_state *parent;386 ...387 }388 389* ``REG_LIVE_NONE`` is an initial value assigned to ``->live`` fields upon new390 verifier state creation;391 392* ``REG_LIVE_WRITTEN`` means that the value of the register (or stack slot) is393 defined by some instruction verified between this verifier state's parent and394 verifier state itself;395 396* ``REG_LIVE_READ{32,64}`` means that the value of the register (or stack slot)397 is read by a some child state of this verifier state;398 399* ``REG_LIVE_DONE`` is a marker used by ``clean_verifier_state()`` to avoid400 processing same verifier state multiple times and for some sanity checks;401 402* ``->live`` field values are formed by combining ``enum bpf_reg_liveness``403 values using bitwise or.404 405Register parentage chains406~~~~~~~~~~~~~~~~~~~~~~~~~407 408In order to propagate information between parent and child states, a *register409parentage chain* is established. Each register or stack slot is linked to a410corresponding register or stack slot in its parent state via a ``->parent``411pointer. This link is established upon state creation in ``is_state_visited()``412and might be modified by ``set_callee_state()`` called from413``__check_func_call()``.414 415The rules for correspondence between registers / stack slots are as follows:416 417* For the current stack frame, registers and stack slots of the new state are418 linked to the registers and stack slots of the parent state with the same419 indices.420 421* For the outer stack frames, only callee saved registers (r6-r9) and stack422 slots are linked to the registers and stack slots of the parent state with the423 same indices.424 425* When function call is processed a new ``struct bpf_func_state`` instance is426 allocated, it encapsulates a new set of registers and stack slots. For this427 new frame, parent links for r6-r9 and stack slots are set to nil, parent links428 for r1-r5 are set to match caller r1-r5 parent links.429 430This could be illustrated by the following diagram (arrows stand for431``->parent`` pointers)::432 433 ... ; Frame #0, some instructions434 --- checkpoint #0 ---435 1 : r6 = 42 ; Frame #0436 --- checkpoint #1 ---437 2 : call foo() ; Frame #0438 ... ; Frame #1, instructions from foo()439 --- checkpoint #2 ---440 ... ; Frame #1, instructions from foo()441 --- checkpoint #3 ---442 exit ; Frame #1, return from foo()443 3 : r1 = r6 ; Frame #0 <- current state444 445 +-------------------------------+-------------------------------+446 | Frame #0 | Frame #1 |447 Checkpoint +-------------------------------+-------------------------------+448 #0 | r0 | r1-r5 | r6-r9 | fp-8 ... |449 +-------------------------------+450 ^ ^ ^ ^451 | | | |452 Checkpoint +-------------------------------+453 #1 | r0 | r1-r5 | r6-r9 | fp-8 ... |454 +-------------------------------+455 ^ ^ ^456 |_______|_______|_______________457 | | |458 nil nil | | | nil nil459 | | | | | | |460 Checkpoint +-------------------------------+-------------------------------+461 #2 | r0 | r1-r5 | r6-r9 | fp-8 ... | r0 | r1-r5 | r6-r9 | fp-8 ... |462 +-------------------------------+-------------------------------+463 ^ ^ ^ ^ ^464 nil nil | | | | |465 | | | | | | |466 Checkpoint +-------------------------------+-------------------------------+467 #3 | r0 | r1-r5 | r6-r9 | fp-8 ... | r0 | r1-r5 | r6-r9 | fp-8 ... |468 +-------------------------------+-------------------------------+469 ^ ^470 nil nil | |471 | | | |472 Current +-------------------------------+473 state | r0 | r1-r5 | r6-r9 | fp-8 ... |474 +-------------------------------+475 \476 r6 read mark is propagated via these links477 all the way up to checkpoint #1.478 The checkpoint #1 contains a write mark for r6479 because of instruction (1), thus read propagation480 does not reach checkpoint #0 (see section below).481 482Liveness marks tracking483~~~~~~~~~~~~~~~~~~~~~~~484 485For each processed instruction, the verifier tracks read and written registers486and stack slots. The main idea of the algorithm is that read marks propagate487back along the state parentage chain until they hit a write mark, which 'screens488off' earlier states from the read. The information about reads is propagated by489function ``mark_reg_read()`` which could be summarized as follows::490 491 mark_reg_read(struct bpf_reg_state *state, ...):492 parent = state->parent493 while parent:494 if state->live & REG_LIVE_WRITTEN:495 break496 if parent->live & REG_LIVE_READ64:497 break498 parent->live |= REG_LIVE_READ64499 state = parent500 parent = state->parent501 502Notes:503 504* The read marks are applied to the **parent** state while write marks are505 applied to the **current** state. The write mark on a register or stack slot506 means that it is updated by some instruction in the straight-line code leading507 from the parent state to the current state.508 509* Details about REG_LIVE_READ32 are omitted.510 511* Function ``propagate_liveness()`` (see section :ref:`read_marks_for_cache_hits`)512 might override the first parent link. Please refer to the comments in the513 ``propagate_liveness()`` and ``mark_reg_read()`` source code for further514 details.515 516Because stack writes could have different sizes ``REG_LIVE_WRITTEN`` marks are517applied conservatively: stack slots are marked as written only if write size518corresponds to the size of the register, e.g. see function ``save_register_state()``.519 520Consider the following example::521 522 0: (*u64)(r10 - 8) = 0 ; define 8 bytes of fp-8523 --- checkpoint #0 ---524 1: (*u32)(r10 - 8) = 1 ; redefine lower 4 bytes525 2: r1 = (*u32)(r10 - 8) ; read lower 4 bytes defined at (1)526 3: r2 = (*u32)(r10 - 4) ; read upper 4 bytes defined at (0)527 528As stated above, the write at (1) does not count as ``REG_LIVE_WRITTEN``. Should529it be otherwise, the algorithm above wouldn't be able to propagate the read mark530from (3) to checkpoint #0.531 532Once the ``BPF_EXIT`` instruction is reached ``update_branch_counts()`` is533called to update the ``->branches`` counter for each verifier state in a chain534of parent verifier states. When the ``->branches`` counter reaches zero the535verifier state becomes a valid entry in a set of cached verifier states.536 537Each entry of the verifier states cache is post-processed by a function538``clean_live_states()``. This function marks all registers and stack slots539without ``REG_LIVE_READ{32,64}`` marks as ``NOT_INIT`` or ``STACK_INVALID``.540Registers/stack slots marked in this way are ignored in function ``stacksafe()``541called from ``states_equal()`` when a state cache entry is considered for542equivalence with a current state.543 544Now it is possible to explain how the example from the beginning of the section545works::546 547 0: call bpf_get_prandom_u32()548 1: r1 = 0549 2: if r0 == 0 goto +1550 3: r0 = 1551 --- checkpoint[0] ---552 4: r0 = r1553 5: exit554 555* At instruction #2 branching point is reached and state ``{ r0 == 0, r1 == 0, pc == 4 }``556 is pushed to states processing queue (pc stands for program counter).557 558* At instruction #4:559 560 * ``checkpoint[0]`` states cache entry is created: ``{ r0 == 1, r1 == 0, pc == 4 }``;561 * ``checkpoint[0].r0`` is marked as written;562 * ``checkpoint[0].r1`` is marked as read;563 564* At instruction #5 exit is reached and ``checkpoint[0]`` can now be processed565 by ``clean_live_states()``. After this processing ``checkpoint[0].r1`` has a566 read mark and all other registers and stack slots are marked as ``NOT_INIT``567 or ``STACK_INVALID``568 569* The state ``{ r0 == 0, r1 == 0, pc == 4 }`` is popped from the states queue570 and is compared against a cached state ``{ r1 == 0, pc == 4 }``, the states571 are considered equivalent.572 573.. _read_marks_for_cache_hits:574 575Read marks propagation for cache hits576~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~577 578Another point is the handling of read marks when a previously verified state is579found in the states cache. Upon cache hit verifier must behave in the same way580as if the current state was verified to the program exit. This means that all581read marks, present on registers and stack slots of the cached state, must be582propagated over the parentage chain of the current state. Example below shows583why this is important. Function ``propagate_liveness()`` handles this case.584 585Consider the following state parentage chain (S is a starting state, A-E are586derived states, -> arrows show which state is derived from which)::587 588 r1 read589 <------------- A[r1] == 0590 C[r1] == 0591 S ---> A ---> B ---> exit E[r1] == 1592 |593 ` ---> C ---> D594 |595 ` ---> E ^596 |___ suppose all these597 ^ states are at insn #Y598 |599 suppose all these600 states are at insn #X601 602* Chain of states ``S -> A -> B -> exit`` is verified first.603 604* While ``B -> exit`` is verified, register ``r1`` is read and this read mark is605 propagated up to state ``A``.606 607* When chain of states ``C -> D`` is verified the state ``D`` turns out to be608 equivalent to state ``B``.609 610* The read mark for ``r1`` has to be propagated to state ``C``, otherwise state611 ``C`` might get mistakenly marked as equivalent to state ``E`` even though612 values for register ``r1`` differ between ``C`` and ``E``.613 614Understanding eBPF verifier messages615====================================616 617The following are few examples of invalid eBPF programs and verifier error618messages as seen in the log:619 620Program with unreachable instructions::621 622 static struct bpf_insn prog[] = {623 BPF_EXIT_INSN(),624 BPF_EXIT_INSN(),625 };626 627Error::628 629 unreachable insn 1630 631Program that reads uninitialized register::632 633 BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),634 BPF_EXIT_INSN(),635 636Error::637 638 0: (bf) r0 = r2639 R2 !read_ok640 641Program that doesn't initialize R0 before exiting::642 643 BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),644 BPF_EXIT_INSN(),645 646Error::647 648 0: (bf) r2 = r1649 1: (95) exit650 R0 !read_ok651 652Program that accesses stack out of bounds::653 654 BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),655 BPF_EXIT_INSN(),656 657Error::658 659 0: (7a) *(u64 *)(r10 +8) = 0660 invalid stack off=8 size=8661 662Program that doesn't initialize stack before passing its address into function::663 664 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),665 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),666 BPF_LD_MAP_FD(BPF_REG_1, 0),667 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),668 BPF_EXIT_INSN(),669 670Error::671 672 0: (bf) r2 = r10673 1: (07) r2 += -8674 2: (b7) r1 = 0x0675 3: (85) call 1676 invalid indirect read from stack off -8+0 size 8677 678Program that uses invalid map_fd=0 while calling to map_lookup_elem() function::679 680 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),681 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),682 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),683 BPF_LD_MAP_FD(BPF_REG_1, 0),684 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),685 BPF_EXIT_INSN(),686 687Error::688 689 0: (7a) *(u64 *)(r10 -8) = 0690 1: (bf) r2 = r10691 2: (07) r2 += -8692 3: (b7) r1 = 0x0693 4: (85) call 1694 fd 0 is not pointing to valid bpf_map695 696Program that doesn't check return value of map_lookup_elem() before accessing697map element::698 699 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),700 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),701 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),702 BPF_LD_MAP_FD(BPF_REG_1, 0),703 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),704 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),705 BPF_EXIT_INSN(),706 707Error::708 709 0: (7a) *(u64 *)(r10 -8) = 0710 1: (bf) r2 = r10711 2: (07) r2 += -8712 3: (b7) r1 = 0x0713 4: (85) call 1714 5: (7a) *(u64 *)(r0 +0) = 0715 R0 invalid mem access 'map_value_or_null'716 717Program that correctly checks map_lookup_elem() returned value for NULL, but718accesses the memory with incorrect alignment::719 720 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),721 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),722 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),723 BPF_LD_MAP_FD(BPF_REG_1, 0),724 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),725 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),726 BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),727 BPF_EXIT_INSN(),728 729Error::730 731 0: (7a) *(u64 *)(r10 -8) = 0732 1: (bf) r2 = r10733 2: (07) r2 += -8734 3: (b7) r1 = 1735 4: (85) call 1736 5: (15) if r0 == 0x0 goto pc+1737 R0=map_ptr R10=fp738 6: (7a) *(u64 *)(r0 +4) = 0739 misaligned access off 4 size 8740 741Program that correctly checks map_lookup_elem() returned value for NULL and742accesses memory with correct alignment in one side of 'if' branch, but fails743to do so in the other side of 'if' branch::744 745 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),746 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),747 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),748 BPF_LD_MAP_FD(BPF_REG_1, 0),749 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),750 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),751 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),752 BPF_EXIT_INSN(),753 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),754 BPF_EXIT_INSN(),755 756Error::757 758 0: (7a) *(u64 *)(r10 -8) = 0759 1: (bf) r2 = r10760 2: (07) r2 += -8761 3: (b7) r1 = 1762 4: (85) call 1763 5: (15) if r0 == 0x0 goto pc+2764 R0=map_ptr R10=fp765 6: (7a) *(u64 *)(r0 +0) = 0766 7: (95) exit767 768 from 5 to 8: R0=imm0 R10=fp769 8: (7a) *(u64 *)(r0 +0) = 1770 R0 invalid mem access 'imm'771 772Program that performs a socket lookup then sets the pointer to NULL without773checking it::774 775 BPF_MOV64_IMM(BPF_REG_2, 0),776 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),777 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),778 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),779 BPF_MOV64_IMM(BPF_REG_3, 4),780 BPF_MOV64_IMM(BPF_REG_4, 0),781 BPF_MOV64_IMM(BPF_REG_5, 0),782 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),783 BPF_MOV64_IMM(BPF_REG_0, 0),784 BPF_EXIT_INSN(),785 786Error::787 788 0: (b7) r2 = 0789 1: (63) *(u32 *)(r10 -8) = r2790 2: (bf) r2 = r10791 3: (07) r2 += -8792 4: (b7) r3 = 4793 5: (b7) r4 = 0794 6: (b7) r5 = 0795 7: (85) call bpf_sk_lookup_tcp#65796 8: (b7) r0 = 0797 9: (95) exit798 Unreleased reference id=1, alloc_insn=7799 800Program that performs a socket lookup but does not NULL-check the returned801value::802 803 BPF_MOV64_IMM(BPF_REG_2, 0),804 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),805 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),806 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),807 BPF_MOV64_IMM(BPF_REG_3, 4),808 BPF_MOV64_IMM(BPF_REG_4, 0),809 BPF_MOV64_IMM(BPF_REG_5, 0),810 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),811 BPF_EXIT_INSN(),812 813Error::814 815 0: (b7) r2 = 0816 1: (63) *(u32 *)(r10 -8) = r2817 2: (bf) r2 = r10818 3: (07) r2 += -8819 4: (b7) r3 = 4820 5: (b7) r4 = 0821 6: (b7) r5 = 0822 7: (85) call bpf_sk_lookup_tcp#65823 8: (95) exit824 Unreleased reference id=1, alloc_insn=7825