| blob | 335c00209f746fb003d6133413a67a5ec68297bc |
1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
2 * Copyright (c) 2016 Facebook
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of version 2 of the GNU General Public
6 * License as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 */
13 #include <linux/kernel.h>
14 #include <linux/types.h>
15 #include <linux/slab.h>
16 #include <linux/bpf.h>
17 #include <linux/bpf_verifier.h>
18 #include <linux/filter.h>
19 #include <net/netlink.h>
20 #include <linux/file.h>
21 #include <linux/vmalloc.h>
23 /* bpf_check() is a static code analyzer that walks eBPF program
24 * instruction by instruction and updates register/stack state.
25 * All paths of conditional branches are analyzed until 'bpf_exit' insn.
26 *
27 * The first pass is depth-first-search to check that the program is a DAG.
28 * It rejects the following programs:
29 * - larger than BPF_MAXINSNS insns
30 * - if loop is present (detected via back-edge)
31 * - unreachable insns exist (shouldn't be a forest. program = one function)
32 * - out of bounds or malformed jumps
33 * The second pass is all possible path descent from the 1st insn.
34 * Since it's analyzing all pathes through the program, the length of the
35 * analysis is limited to 32k insn, which may be hit even if total number of
36 * insn is less then 4K, but there are too many branches that change stack/regs.
37 * Number of 'branches to be analyzed' is limited to 1k
38 *
39 * On entry to each instruction, each register has a type, and the instruction
40 * changes the types of the registers depending on instruction semantics.
41 * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is
42 * copied to R1.
43 *
44 * All registers are 64-bit.
45 * R0 - return register
46 * R1-R5 argument passing registers
47 * R6-R9 callee saved registers
48 * R10 - frame pointer read-only
49 *
50 * At the start of BPF program the register R1 contains a pointer to bpf_context
51 * and has type PTR_TO_CTX.
52 *
53 * Verifier tracks arithmetic operations on pointers in case:
54 * BPF_MOV64_REG(BPF_REG_1, BPF_REG_10),
55 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20),
56 * 1st insn copies R10 (which has FRAME_PTR) type into R1
57 * and 2nd arithmetic instruction is pattern matched to recognize
58 * that it wants to construct a pointer to some element within stack.
59 * So after 2nd insn, the register R1 has type PTR_TO_STACK
60 * (and -20 constant is saved for further stack bounds checking).
61 * Meaning that this reg is a pointer to stack plus known immediate constant.
62 *
63 * Most of the time the registers have UNKNOWN_VALUE type, which
64 * means the register has some value, but it's not a valid pointer.
65 * (like pointer plus pointer becomes UNKNOWN_VALUE type)
66 *
67 * When verifier sees load or store instructions the type of base register
68 * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, FRAME_PTR. These are three pointer
69 * types recognized by check_mem_access() function.
70 *
71 * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value'
72 * and the range of [ptr, ptr + map's value_size) is accessible.
73 *
74 * registers used to pass values to function calls are checked against
75 * function argument constraints.
76 *
77 * ARG_PTR_TO_MAP_KEY is one of such argument constraints.
78 * It means that the register type passed to this function must be
79 * PTR_TO_STACK and it will be used inside the function as
80 * 'pointer to map element key'
81 *
82 * For example the argument constraints for bpf_map_lookup_elem():
83 * .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL,
84 * .arg1_type = ARG_CONST_MAP_PTR,
85 * .arg2_type = ARG_PTR_TO_MAP_KEY,
86 *
87 * ret_type says that this function returns 'pointer to map elem value or null'
88 * function expects 1st argument to be a const pointer to 'struct bpf_map' and
89 * 2nd argument should be a pointer to stack, which will be used inside
90 * the helper function as a pointer to map element key.
91 *
92 * On the kernel side the helper function looks like:
93 * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
94 * {
95 * struct bpf_map *map = (struct bpf_map *) (unsigned long) r1;
96 * void *key = (void *) (unsigned long) r2;
97 * void *value;
98 *
99 * here kernel can access 'key' and 'map' pointers safely, knowing that
100 * [key, key + map->key_size) bytes are valid and were initialized on
101 * the stack of eBPF program.
102 * }
103 *
104 * Corresponding eBPF program may look like:
105 * BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), // after this insn R2 type is FRAME_PTR
106 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK
107 * BPF_LD_MAP_FD(BPF_REG_1, map_fd), // after this insn R1 type is CONST_PTR_TO_MAP
108 * BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
109 * here verifier looks at prototype of map_lookup_elem() and sees:
110 * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok,
111 * Now verifier knows that this map has key of R1->map_ptr->key_size bytes
112 *
113 * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far,
114 * Now verifier checks that [R2, R2 + map's key_size) are within stack limits
115 * and were initialized prior to this call.
116 * If it's ok, then verifier allows this BPF_CALL insn and looks at
117 * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets
118 * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function
119 * returns ether pointer to map value or NULL.
120 *
121 * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off'
122 * insn, the register holding that pointer in the true branch changes state to
123 * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false
124 * branch. See check_cond_jmp_op().
125 *
126 * After the call R0 is set to return type of the function and registers R1-R5
127 * are set to NOT_INIT to indicate that they are no longer readable.
128 */
130 /* verifier_state + insn_idx are pushed to stack when branch is encountered */
132 /* verifer state is 'st'
133 * before processing instruction 'insn_idx'
134 * and after processing instruction 'prev_insn_idx'
135 */
140 };
142 #define BPF_COMPLEXITY_LIMIT_INSNS 98304
143 #define BPF_COMPLEXITY_LIMIT_STACK 1024
151 };
153 /* verbose verifier prints what it's seeing
154 * bpf_check() is called under lock, so no race to access these global vars
155 */
161 /* log_level controls verbosity level of eBPF verifier.
162 * verbose() is used to dump the verification trace to the log, so the user
163 * can figure out what's wrong with the program
164 */
166 {
175 }
177 /* string representation of 'enum bpf_reg_type' */
191 };
194 {
225 }
230 }
232 }
243 };
260 };
267 };
280 };
284 {
295 else
315 else
321 }
331 }
349 /* At this point, we already made sure that the second
350 * part of the ldimm64 insn is accessible.
351 */
363 }
384 }
387 }
388 }
391 {
407 }
411 {
427 }
429 err:
430 /* pop all elements and return */
433 }
435 #define CALLER_SAVED_REGS 6
438 };
441 {
449 }
451 /* frame pointer */
454 /* 1st arg to a function */
456 }
459 {
463 }
466 {
469 }
472 {
475 }
480 DST_OP_NO_MARK /* same as above, check only, don't mark */
481 };
485 {
489 }
492 /* check whether register used as source operand can be read */
496 }
498 /* check whether register used as dest operand can be written to */
502 }
505 }
507 }
510 {
519 else
521 }
524 {
537 }
538 }
540 /* check_stack_read/write functions track spill/fill of registers,
541 * stack boundary and alignment are checked in check_mem_access()
542 */
546 {
548 /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
549 * so it's aligned access and [off, off + size) are within stack limits
550 */
555 /* register containing pointer is being spilled into stack */
559 }
561 /* save register state */
570 /* detected reuse of integer stack slot with a pointer
571 * which means either llvm is reusing stack slot or
572 * an attacker is trying to exploit CVE-2018-3639
573 * (speculative store bypass)
574 * Have to sanitize that slot with preemptive
575 * store of zero.
576 */
578 /* disallow programs where single insn stores
579 * into two different stack slots, since verifier
580 * cannot sanitize them
581 */
585 }
587 }
589 }
591 /* regular write of data into stack */
596 }
598 }
602 {
612 }
617 }
618 }
621 /* restore register state from stack */
631 }
632 }
634 /* have read misc data from the stack */
637 }
638 }
640 /* check read/write into map element returned by bpf_map_lookup_elem() */
643 {
650 }
652 }
654 #define MAX_PACKET_OFF 0xffff
658 {
670 }
671 }
675 {
684 }
686 }
688 /* check access to 'struct bpf_context' fields */
691 {
692 /* for analyzer ctx accesses are already validated and converted */
698 /* remember the offset of last byte accessed in ctx */
702 }
706 }
710 {
720 }
721 }
724 {
726 }
729 {
733 }
737 {
745 }
746 }
749 /* misaligned access to packet is ok on x86,arm,arm64 */
755 }
757 /* skb->data is NET_IP_ALIGN-ed */
763 }
765 }
767 /* check whether memory at (regno + off) is accessible for t = (read | write)
768 * if t==write, value_regno is a register which value is stored into memory
769 * if t==read, value_regno is a register which will receive the value from memory
770 * if t==write && value_regno==-1, some unknown value is stored into memory
771 * if t==read && value_regno==-1, don't care what we read from memory
772 */
776 {
798 }
800 /* If we adjusted the register to this map value at all then we
801 * need to change off and size to min_value and max_value
802 * respectively to make sure our theoretical access will be
803 * safe.
804 */
809 /* The minimum value is only important with signed
810 * comparisons where we can't assume the floor of a
811 * value is 0. If we are using signed variables for our
812 * index'es we need to make sure that whatever we use
813 * will have a set floor within our range.
814 */
817 regno);
819 }
821 size);
824 regno);
826 }
828 /* If we haven't set a max value then we need to bail
829 * since we can't be sure we won't do bad things.
830 */
833 regno);
835 }
837 }
849 }
853 /* note that reg.[id|off|range] == 0 */
855 }
861 }
868 }
873 }
878 }
883 }
891 }
895 /* 1 or 2 byte load zero-extends, determine the number of
896 * zero upper bits. Not doing it fo 4 byte load, since
897 * such values cannot be added to ptr_to_packet anyway.
898 */
900 }
902 }
905 {
913 }
915 /* check src1 operand */
920 /* check src2 operand */
928 }
934 }
936 /* check whether atomic_add can read the memory */
942 /* check whether atomic_add can write into the same memory */
945 }
947 /* when register 'regno' is passed into function that will read 'access_size'
948 * bytes from that pointer, make sure that it's within stack boundary
949 * and all elements of stack are initialized
950 */
954 {
969 }
977 }
983 }
990 }
991 }
993 }
998 {
1009 }
1015 }
1017 }
1022 }
1045 /* One exception here. In case function allows for NULL to be
1046 * passed in as argument, it's a CONST_IMM type. Final test
1047 * happens during stack boundary checking.
1048 */
1057 }
1060 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
1063 /* bpf_map_xxx(..., map_ptr, ..., key) call:
1064 * check that [key, key + map->key_size) are within
1065 * stack limits and initialized
1066 */
1068 /* in function declaration map_ptr must come before
1069 * map_key, so that it's verified and known before
1070 * we have to check map_key here. Otherwise it means
1071 * that kernel subsystem misconfigured verifier
1072 */
1075 }
1079 else
1084 /* bpf_map_xxx(..., map_ptr, ..., value) call:
1085 * check [value, value + map->value_size) validity
1086 */
1088 /* kernel subsystem misconfigured verifier */
1091 }
1095 else
1103 /* bpf_xxx(..., buf, len) call will access 'len' bytes
1104 * from stack pointer 'buf'. Check it
1105 * note: regno == len, regno - 1 == buf
1106 */
1108 /* kernel subsystem misconfigured verifier */
1111 }
1114 else
1117 }
1120 err_type:
1124 }
1127 {
1131 /* We need a two way check, first is from map perspective ... */
1153 }
1155 /* ... and second from the function itself. */
1177 }
1180 error:
1184 }
1187 {
1191 count++;
1193 count++;
1195 count++;
1197 count++;
1199 count++;
1202 }
1205 {
1224 }
1225 }
1228 {
1237 /* find function prototype */
1241 }
1249 }
1251 /* eBPF programs must be GPL compatible to use GPL-ed functions */
1255 }
1262 /* We only support one arg being in raw mode at the moment, which
1263 * is sufficient for the helper functions we have right now.
1264 */
1269 }
1271 /* check args */
1282 }
1284 }
1295 /* Mark slots with STACK_MISC in case of raw mode, stack offset
1296 * is inferred from register state.
1297 */
1302 }
1304 /* reset caller saved regs */
1309 }
1311 /* update return register */
1319 /* remember map_ptr, so that check_map_access()
1320 * can check 'value_size' boundary of memory access
1321 * to map element returned from bpf_map_lookup_elem()
1322 */
1326 }
1333 }
1342 }
1346 {
1351 s32 imm;
1354 /* pkt_ptr += imm */
1357 add_imm:
1361 }
1365 imm);
1367 }
1368 /* a constant was added to pkt_ptr.
1369 * Remember it while keeping the same 'id'
1370 */
1374 /* R6=pkt(id=0,off=0,r=62) R7=imm22; r7 += r6 */
1378 /* if the checks below reject it, the copy won't matter,
1379 * since we're rejecting the whole program. If all ok,
1380 * then imm22 state will be added to r7
1381 * and r7 will be pkt(id=0,off=22,r=62) while
1382 * r6 will stay as pkt(id=0,off=0,r=62)
1383 */
1384 }
1387 /* pkt_ptr += reg where reg is known constant */
1390 }
1391 /* disallow pkt_ptr += reg
1392 * if reg is not uknown_value with guaranteed zero upper bits
1393 * otherwise pkt_ptr may overflow and addition will become
1394 * subtraction which is not allowed
1395 */
1400 }
1405 }
1406 /* dst_reg stays as pkt_ptr type and since some positive
1407 * integer value was added to the pointer, increment its 'id'
1408 */
1411 /* something was added to pkt_ptr, set range and off to zero */
1414 }
1416 }
1419 {
1423 s64 imm_log2;
1425 /* for type == UNKNOWN_VALUE:
1426 * imm > 0 -> number of zero upper bits
1427 * imm == 0 -> don't track which is the same as all bits can be non-zero
1428 */
1435 /* dreg += sreg
1436 * where both have zero upper bits. Adding them
1437 * can only result making one more bit non-zero
1438 * in the larger value.
1439 * Ex. 0xffff (imm=48) + 1 (imm=63) = 0x10000 (imm=47)
1440 * 0xffff (imm=48) + 0xffff = 0x1fffe (imm=47)
1441 */
1445 }
1448 /* dreg += sreg
1449 * where dreg has zero upper bits and sreg is const.
1450 * Adding them can only result making one more bit
1451 * non-zero in the larger value.
1452 */
1457 }
1458 /* all other cases non supported yet, just mark dst_reg */
1461 }
1463 /* sign extend 32-bit imm into 64-bit to make sure that
1464 * negative values occupy bit 63. Note ilog2() would have
1465 * been incorrect, since sizeof(insn->imm) == 4
1466 */
1470 /* reg <<= imm
1471 * if reg was a result of 2 byte load, then its imm == 48
1472 * which means that upper 48 bits are zero and shifting this reg
1473 * left by 4 would mean that upper 44 bits are still zero
1474 */
1477 /* reg *= imm
1478 * if multiplying by 14 subtract 4
1479 * This is conservative calculation of upper zero bits.
1480 * It's not trying to special case insn->imm == 1 or 0 cases
1481 */
1484 /* reg &= imm */
1487 /* reg += imm */
1491 /* reg >>= imm
1492 * which means that after right shift, upper bits will be zero
1493 * note that verifier already checked that
1494 * 0 <= imm < 64 for shift insn
1495 */
1498 /* some dumb code did:
1499 * r2 = *(u32 *)mem;
1500 * r2 >>= 32;
1501 * and all bits are zero now */
1504 /* all other alu ops, means that we don't know what will
1505 * happen to the value, mark it with unknown number of zero bits
1506 */
1508 }
1511 /* all 64 bits of the register can contain non-zero bits
1512 * and such value cannot be added to ptr_to_packet, since it
1513 * may overflow, mark it as unknown to avoid further eval
1514 */
1516 }
1518 }
1522 {
1529 /* BPF_X code with src_reg->type UNKNOWN_VALUE here. */
1533 /* dreg += sreg
1534 * where both have zero upper bits. Adding them
1535 * can only result making one more bit non-zero
1536 * in the larger value.
1537 * Ex. 0xffff (imm=48) + 1 (imm=63) = 0x10000 (imm=47)
1538 * 0xffff (imm=48) + 0xffff = 0x1fffe (imm=47)
1539 */
1544 /* dreg &= sreg
1545 * AND can not extend zero bits only shrink
1546 * Ex. 0x00..00ffffff
1547 * & 0x0f..ffffffff
1548 * ----------------
1549 * 0x00..00ffffff
1550 */
1554 /* dreg |= sreg
1555 * OR can only extend zero bits
1556 * Ex. 0x00..00ffffff
1557 * | 0x0f..ffffffff
1558 * ----------------
1559 * 0x0f..00ffffff
1560 */
1567 /* These may be flushed out later */
1570 }
1573 }
1577 }
1581 {
1590 /* dst_reg->type == CONST_IMM here, simulate execution of 'add' insn.
1591 * Don't care about overflow or negative values, just add them
1592 */
1598 else
1601 }
1604 {
1610 }
1614 {
1627 /* If the source register is a random pointer then the
1628 * min_value/max_value values represent the range of the known
1629 * accesses into that value, not the actual min/max value of the
1630 * register itself. In this case we have to reset the reg range
1631 * values so we know it is not safe to look at.
1632 */
1637 }
1642 }
1644 /* We don't know anything about what was done to this register, mark it
1645 * as unknown. Also, if both derived bounds came from signed/unsigned
1646 * mixed compares and one side is unbounded, we cannot really do anything
1647 * with them as boundaries cannot be trusted. Thus, arithmetic of two
1648 * regs of such kind will get invalidated bounds on the dst side.
1649 */
1665 }
1667 /* If one of our values was at the end of our ranges then we can't just
1668 * do our normal operations to the register, we need to set the values
1669 * to the min/max since they are undefined.
1670 */
1676 }
1686 /* If one of our values was at the end of our ranges, then the
1687 * _opposite_ value in the dst_reg goes to the end of our range.
1688 */
1705 /* Disallow AND'ing of negative numbers, ain't nobody got time
1706 * for that. Otherwise the minimum is 0 and the max is the max
1707 * value we could AND against.
1708 */
1711 else
1716 /* Gotta have special overflow logic here, if we're shifting
1717 * more than MAX_RANGE then just assume we have an invalid
1718 * range.
1719 */
1731 /* RSH by a negative number is undefined, and the BPF_RSH is an
1732 * unsigned shift, so make the appropriate casts.
1733 */
1736 else
1745 }
1748 }
1750 /* check validity of 32-bit and 64-bit arithmetic operations */
1752 {
1764 }
1771 }
1772 }
1774 /* check src operand */
1783 }
1785 /* check dest operand */
1796 }
1798 /* check src operand */
1806 }
1807 }
1809 /* check dest operand */
1814 /* we are setting our register to something new, we need to
1815 * reset its range values.
1816 */
1821 /* case: R1 = R2
1822 * copy register state to dest reg
1823 */
1830 }
1832 }
1834 /* case: R = imm
1835 * remember the value we stored into this reg
1836 */
1837 u64 imm;
1841 else
1848 }
1860 }
1861 /* check src1 operand */
1869 }
1870 }
1872 /* check src2 operand */
1881 }
1886 }
1895 }
1896 }
1898 /* check dest operand */
1905 /* first we want to adjust our ranges. */
1908 /* pattern match 'bpf_add Rx, imm' instruction */
1921 /* check in case the register contains a big
1922 * 64-bit value
1923 */
1929 }
1932 /* safe against overflow: addition of 32-bit
1933 * numbers in 64-bit representation
1934 */
1936 }
1941 }
1948 /* ptr_to_packet += K|X */
1953 /* unknown += K|X */
1958 /* reg_imm += K|X */
1969 }
1971 /* If we did pointer math on a map value then just set it to our
1972 * PTR_TO_MAP_VALUE_ADJ type so we can deal with any stores or
1973 * loads to this register appropriately, otherwise just mark the
1974 * register as unknown.
1975 */
1981 else
1983 }
1986 }
1990 {
1994 /* LLVM can generate two kind of checks:
1995 *
1996 * Type 1:
1997 *
1998 * r2 = r3;
1999 * r2 += 8;
2000 * if (r2 > pkt_end) goto <handle exception>
2001 * <access okay>
2002 *
2003 * Where:
2004 * r2 == dst_reg, pkt_end == src_reg
2005 * r2=pkt(id=n,off=8,r=0)
2006 * r3=pkt(id=n,off=0,r=0)
2007 *
2008 * Type 2:
2009 *
2010 * r2 = r3;
2011 * r2 += 8;
2012 * if (pkt_end >= r2) goto <access okay>
2013 * <handle exception>
2014 *
2015 * Where:
2016 * pkt_end == dst_reg, r2 == src_reg
2017 * r2=pkt(id=n,off=8,r=0)
2018 * r3=pkt(id=n,off=0,r=0)
2019 *
2020 * Find register r3 and mark its range as r3=pkt(id=n,off=0,r=8)
2021 * so that range of bytes [r3, r3 + 8) is safe to access.
2022 */
2026 /* keep the maximum range already checked */
2035 }
2036 }
2038 /* Adjusts the register min/max values in the case that the dst_reg is the
2039 * variable register that we are working on, and src_reg is a constant or we're
2040 * simply doing a BPF_K check.
2041 */
2044 u8 opcode)
2045 {
2051 /* If this is false then we know nothing Jon Snow, but if it is
2052 * true then we know for sure.
2053 */
2058 /* If this is true we know nothing Jon Snow, but if it is false
2059 * we know the value for sure;
2060 */
2066 /* fallthrough */
2073 /* Unsigned comparison, the minimum value is 0. */
2075 }
2076 /* If this is false then we know the maximum val is val,
2077 * otherwise we know the min val is val+1.
2078 */
2086 /* fallthrough */
2093 /* Unsigned comparison, the minimum value is 0. */
2095 }
2096 /* If this is false then we know the maximum value is val - 1,
2097 * otherwise we know the mimimum value is val.
2098 */
2106 }
2115 }
2116 }
2118 /* Same as above, but for the case that dst_reg is a CONST_IMM reg and src_reg
2119 * is the variable reg.
2120 */
2123 u8 opcode)
2124 {
2130 /* If this is false then we know nothing Jon Snow, but if it is
2131 * true then we know for sure.
2132 */
2137 /* If this is true we know nothing Jon Snow, but if it is false
2138 * we know the value for sure;
2139 */
2145 /* fallthrough */
2152 /* Unsigned comparison, the minimum value is 0. */
2154 }
2155 /*
2156 * If this is false, then the val is <= the register, if it is
2157 * true the register <= to the val.
2158 */
2166 /* fallthrough */
2173 /* Unsigned comparison, the minimum value is 0. */
2175 }
2176 /* If this is false then constant < register, if it is true then
2177 * the register < constant.
2178 */
2186 }
2195 }
2196 }
2200 {
2205 /* We don't need id from this point onwards anymore, thus we
2206 * should better reset it, so that state pruning has chances
2207 * to take effect.
2208 */
2212 }
2213 }
2215 /* The logic is similar to find_good_pkt_pointers(), both could eventually
2216 * be folded together at some point.
2217 */
2220 {
2232 }
2233 }
2237 {
2246 }
2252 }
2254 /* check src1 operand */
2263 }
2268 }
2269 }
2271 /* check src2 operand */
2278 /* detect if R == 0 where R was initialized to zero earlier */
2283 /* if (imm == imm) goto pc+off;
2284 * only follow the goto, ignore fall-through
2285 */
2289 /* if (imm != imm) goto pc+off;
2290 * only follow fall-through branch, since
2291 * that's where the program will go
2292 */
2294 }
2295 }
2301 /* detect if we are comparing against a constant value so we can adjust
2302 * our min/max values for our dst register.
2303 */
2308 opcode);
2312 opcode);
2316 }
2318 /* detect if R == 0 where R is returned from bpf_map_lookup_elem() */
2322 /* Mark all identical map registers in each branch as either
2323 * safe or unknown depending R == 0 or R != 0 conditional.
2324 */
2340 }
2344 }
2346 /* return the map pointer stored inside BPF_LD_IMM64 instruction */
2348 {
2352 }
2354 /* verify BPF_LD_IMM64 instruction */
2356 {
2363 }
2367 }
2374 /* generic move 64-bit immediate into a register,
2375 * only analyzer needs to collect the ld_imm value.
2376 */
2385 }
2387 /* replace_map_fd_with_map_ptr() should have caught bad ld_imm64 */
2393 }
2396 {
2404 }
2405 }
2407 /* verify safety of LD_ABS|LD_IND instructions:
2408 * - they can only appear in the programs where ctx == skb
2409 * - since they are wrappers of function calls, they scratch R1-R5 registers,
2410 * preserve R6-R9, and store return value into R0
2411 *
2412 * Implicit input:
2413 * ctx == skb == R6 == CTX
2414 *
2415 * Explicit input:
2416 * SRC == any register
2417 * IMM == 32-bit immediate
2418 *
2419 * Output:
2420 * R0 - 8/16/32-bit skb data converted to cpu endianness
2421 */
2423 {
2432 }
2439 }
2441 /* check whether implicit source operand (register R6) is readable */
2449 }
2452 /* check explicit source operand */
2456 }
2458 /* reset caller saved regs to unreadable */
2463 }
2465 /* mark destination R0 register as readable, since it contains
2466 * the value fetched from the packet
2467 */
2470 }
2472 /* non-recursive DFS pseudo code
2473 * 1 procedure DFS-iterative(G,v):
2474 * 2 label v as discovered
2475 * 3 let S be a stack
2476 * 4 S.push(v)
2477 * 5 while S is not empty
2478 * 6 t <- S.pop()
2479 * 7 if t is what we're looking for:
2480 * 8 return t
2481 * 9 for all edges e in G.adjacentEdges(t) do
2482 * 10 if edge e is already labelled
2483 * 11 continue with the next edge
2484 * 12 w <- G.adjacentVertex(t,e)
2485 * 13 if vertex w is not discovered and not explored
2486 * 14 label e as tree-edge
2487 * 15 label w as discovered
2488 * 16 S.push(w)
2489 * 17 continue at 5
2490 * 18 else if vertex w is discovered
2491 * 19 label e as back-edge
2492 * 20 else
2493 * 21 // vertex w is explored
2494 * 22 label e as forward- or cross-edge
2495 * 23 label t as explored
2496 * 24 S.pop()
2497 *
2498 * convention:
2499 * 0x10 - discovered
2500 * 0x11 - discovered and fall-through edge labelled
2501 * 0x12 - discovered and fall-through and branch edges labelled
2502 * 0x20 - explored
2503 */
2510 };
2512 #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
2518 /* t, w, e - match pseudo-code above:
2519 * t - index of current instruction
2520 * w - next instruction
2521 * e - edge
2522 */
2524 {
2534 }
2537 /* mark branch target for state pruning */
2541 /* tree-edge */
2552 /* forward- or cross-edge */
2557 }
2559 }
2561 /* non-recursive depth-first-search to detect loops in BPF program
2562 * loop == back-edge in directed graph
2563 */
2565 {
2579 }
2585 peek_stack:
2607 }
2608 /* unconditional jump with single edge */
2615 /* tell verifier to check for equivalent states
2616 * after every call and jump
2617 */
2621 /* conditional jump with two edges */
2634 }
2636 /* all other non-branch instructions with single
2637 * fall-through edge
2638 */
2644 }
2646 mark_explored:
2652 }
2655 check_state:
2661 }
2662 }
2665 err_free:
2669 }
2671 /* the following conditions reduce the number of explored insns
2672 * from ~140k to ~80k for ultra large programs that use a lot of ptr_to_packet
2673 */
2676 {
2680 /* old ptr_to_packet is more conservative, since it allows smaller
2681 * range. Ex:
2682 * old(off=0,r=10) is equal to cur(off=0,r=20), because
2683 * old(off=0,r=10) means that with range=10 the verifier proceeded
2684 * further and found no issues with the program. Now we're in the same
2685 * spot with cur(off=0,r=20), so we're safe too, since anything further
2686 * will only be looking at most 10 bytes after this pointer.
2687 */
2691 /* old(off=20,r=10) is equal to cur(off=22,re=22 or 5 or 0)
2692 * since both cannot be used for packet access and safe(old)
2693 * pointer has smaller off that could be used for further
2694 * 'if (ptr > data_end)' check
2695 * Ex:
2696 * old(off=20,r=10) and cur(off=22,r=22) and cur(off=22,r=0) mean
2697 * that we cannot access the packet.
2698 * The safe range is:
2699 * [ptr, ptr + range - off)
2700 * so whenever off >=range, it means no safe bytes from this pointer.
2701 * When comparing old->off <= cur->off, it means that older code
2702 * went with smaller offset and that offset was later
2703 * used to figure out the safe range after 'if (ptr > data_end)' check
2704 * Say, 'old' state was explored like:
2705 * ... R3(off=0, r=0)
2706 * R4 = R3 + 20
2707 * ... now R4(off=20,r=0) <-- here
2708 * if (R4 > data_end)
2709 * ... R4(off=20,r=20), R3(off=0,r=20) and R3 can be used to access.
2710 * ... the code further went all the way to bpf_exit.
2711 * Now the 'cur' state at the mark 'here' has R4(off=30,r=0).
2712 * old_R4(off=20,r=0) equal to cur_R4(off=30,r=0), since if the verifier
2713 * goes further, such cur_R4 will give larger safe packet range after
2714 * 'if (R4 > data_end)' and all further insn were already good with r=20,
2715 * so they will be good with r=30 and we can prune the search.
2716 */
2722 }
2724 /* compare two verifier states
2725 *
2726 * all states stored in state_list are known to be valid, since
2727 * verifier reached 'bpf_exit' instruction through them
2728 *
2729 * this function is called when verifier exploring different branches of
2730 * execution popped from the state stack. If it sees an old state that has
2731 * more strict register state and more strict stack state then this execution
2732 * branch doesn't need to be explored further, since verifier already
2733 * concluded that more strict state leads to valid finish.
2734 *
2735 * Therefore two states are equivalent if register state is more conservative
2736 * and explored stack state is more conservative than the current one.
2737 * Example:
2738 * explored current
2739 * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC)
2740 * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC)
2741 *
2742 * In other words if current stack state (one being explored) has more
2743 * valid slots than old one that already passed validation, it means
2744 * the verifier can stop exploring and conclude that current state is valid too
2745 *
2746 * Similarly with registers. If explored state has register type as invalid
2747 * whereas register type in current state is meaningful, it means that
2748 * the current state will reach 'bpf_exit' instruction safely
2749 */
2753 {
2765 /* If the ranges were not the same, but everything else was and
2766 * we didn't do a variable access into a map then we are a-ok.
2767 */
2772 /* If we didn't map access then again we don't care about the
2773 * mismatched range values and it's ok if our old type was
2774 * UNKNOWN and we didn't go to a NOT_INIT'ed or pointer reg.
2775 */
2782 /* Don't care about the reg->id in this case. */
2793 }
2799 /* Ex: old explored (safe) state has STACK_SPILL in
2800 * this stack slot, but current has has STACK_MISC ->
2801 * this verifier states are not equivalent,
2802 * return false to continue verification of this path
2803 */
2810 /* when explored and current stack slot types are
2811 * the same, check that stored pointers types
2812 * are the same as well.
2813 * Ex: explored safe path could have stored
2814 * (bpf_reg_state) {.type = PTR_TO_STACK, .imm = -8}
2815 * but current path has stored:
2816 * (bpf_reg_state) {.type = PTR_TO_STACK, .imm = -16}
2817 * such verifier states are not equivalent.
2818 * return false to continue verification of this path
2819 */
2821 else
2823 }
2825 }
2828 {
2834 /* this 'insn_idx' instruction wasn't marked, so we will not
2835 * be doing state search here
2836 */
2841 /* reached equivalent register/stack state,
2842 * prune the search
2843 */
2846 }
2848 /* there were no equivalent states, remember current one.
2849 * technically the current state is not proven to be safe yet,
2850 * but it will either reach bpf_exit (which means it's safe) or
2851 * it will be rejected. Since there are no loops, we won't be
2852 * seeing this 'insn_idx' instruction again on the way to bpf_exit
2853 */
2858 /* add new state to the head of linked list */
2863 }
2867 {
2872 }
2875 {
2896 }
2903 insn_processed);
2905 }
2911 /* found equivalent state, can prune the search */
2916 else
2918 }
2920 }
2932 }
2937 }
2952 /* check for reserved fields is already done */
2954 /* check src operand */
2965 /* check that memory (src_reg + off) is readable,
2966 * the state of dst_reg will be updated by this func
2967 */
2977 insn_idx++;
2979 }
2984 /* saw a valid insn
2985 * dst_reg = *(u32 *)(src_reg + off)
2986 * save type to validate intersecting paths
2987 */
2993 /* ABuser program is trying to use the same insn
2994 * dst_reg = *(u32*) (src_reg + off)
2995 * with different pointer types:
2996 * src_reg == ctx in one branch and
2997 * src_reg == stack|map in some other branch.
2998 * Reject it.
2999 */
3002 }
3011 insn_idx++;
3013 }
3015 /* check src1 operand */
3019 /* check src2 operand */
3026 /* check that memory (dst_reg + off) is writeable */
3042 }
3049 }
3050 /* check src operand */
3059 }
3061 /* check that memory (dst_reg + off) is writeable */
3078 }
3091 }
3103 }
3105 /* eBPF calling convetion is such that R0 is used
3106 * to return the value from eBPF program.
3107 * Make sure that it's readable at this time
3108 * of bpf_exit, which means that program wrote
3109 * something into it earlier
3110 */
3118 }
3120 process_bpf_exit:
3127 }
3132 }
3146 insn_idx++;
3151 }
3156 }
3158 insn_idx++;
3159 }
3163 }
3168 {
3175 }
3177 }
3179 /* look for pseudo eBPF instructions that access map FDs and
3180 * replace them with actual map pointers
3181 */
3183 {
3193 }
3200 }
3211 }
3214 /* valid generic load 64-bit imm */
3220 }
3228 }
3234 }
3236 /* store map pointer inside BPF_LD_IMM64 instruction */
3240 /* check whether we recorded this map already */
3245 }
3250 }
3252 /* hold the map. If the program is rejected by verifier,
3253 * the map will be released by release_maps() or it
3254 * will be used by the valid program until it's unloaded
3255 * and all maps are released in free_used_maps()
3256 */
3261 }
3265 next_insn:
3266 insn++;
3267 i++;
3268 }
3269 }
3271 /* now all pseudo BPF_LD_IMM64 instructions load valid
3272 * 'struct bpf_map *' into a register instead of user map_fd.
3273 * These pointers will be used later by verifier to validate map access.
3274 */
3276 }
3278 /* drop refcnt of maps used by the rejected program */
3280 {
3285 }
3287 /* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */
3289 {
3297 }
3299 /* single env->prog->insni[off] instruction was replaced with the range
3300 * insni[off, off + cnt). Adjust corresponding insn_aux_data by copying
3301 * [0, off) and [off, end) to new locations, so the patched range stays zero
3302 */
3305 {
3322 }
3326 {
3335 }
3337 /* The verifier does more data flow analysis than llvm and will not explore
3338 * branches that are dead at run time. Malicious programs can have dead code
3339 * too. Therefore replace all dead at-run-time code with nops.
3340 */
3342 {
3353 }
3354 }
3356 /* convert load instructions that access fields of 'struct __sk_buff'
3357 * into sequence of instructions that access fields of 'struct sk_buff'
3358 */
3360 {
3381 }
3382 }
3396 else
3402 /* Sanitize suspicious stack slot with zero.
3403 * There are no memory dependencies for this store,
3404 * since it's only using frame pointer and immediate
3405 * constant of zero
3406 */
3410 /* the original STX instruction will immediately
3411 * overwrite the same stack slot with appropriate value
3412 */
3414 };
3425 }
3435 }
3443 /* keep walking new program and skip insns we just inserted */
3446 }
3449 }
3451 /* fixup insn->imm field of bpf_call instructions
3452 *
3453 * this function is called after eBPF program passed verification
3454 */
3456 {
3470 /* due to JIT bugs clear upper 32-bits of src register
3471 * before div/mod operation
3472 */
3484 }
3494 /* mark bpf_tail_call as different opcode to avoid
3495 * conditional branch in the interpeter for every normal
3496 * call and to prevent accidental JITing by JIT compiler
3497 * that doesn't support bpf_tail_call yet
3498 */
3502 /* instead of changing every JIT dealing with tail_call
3503 * emit two extra insns:
3504 * if (index >= max_entries) goto out;
3505 * index &= array->index_mask;
3506 * to avoid out-of-bounds cpu speculation
3507 */
3527 }
3530 /* all functions that have prototype and verifier allowed
3531 * programs to call them, must be real in-kernel functions
3532 */
3537 }
3539 }
3542 }
3545 {
3560 }
3561 }
3564 }
3567 {
3575 /* 'struct bpf_verifier_env' can be global, but since it's not small,
3576 * allocate/free it every time bpf_check() is called
3577 */
3589 /* grab the mutex to protect few globals used by verifier */
3593 /* user requested verbose verifier output
3594 * and supplied buffer to store the verification trace
3595 */
3602 /* log_* values have to be sane */
3613 }
3621 GFP_USER);
3634 skip_full_check:
3642 /* program is valid, convert *(u32*)(ctx + off) accesses */
3650 /* verifier log exceeded user supplied buffer */
3652 /* fall through to return what was recorded */
3653 }
3655 /* copy verifier log back to user space including trailing zero */
3659 }
3662 /* if program passed verifier, update used_maps in bpf_prog_info */
3665 GFP_KERNEL);
3670 }
3676 /* program is valid. Convert pseudo bpf_ld_imm64 into generic
3677 * bpf_ld_imm64 instructions
3678 */
3680 }
3682 free_log_buf:
3686 /* if we didn't copy map pointers into bpf_prog_info, release
3687 * them now. Otherwise free_used_maps() will release them.
3688 */
3691 err_unlock:
3694 err_free_env:
3697 }
3701 {
3718 /* grab the mutex to protect few globals used by verifier */
3725 GFP_KERNEL);
3738 skip_full_check:
3744 err_free_env:
3747 }