bpf: Fix indirect var_off stack access support
Subsystems (6)
v3 cover bpf: Fix indirect var_off stack access support
v2->v3:
- sanity check max value for variable offset.
v1->v2:
- rely on meta = NULL to reject var_off stack access to uninit buffer.
This patch set is a follow-up for discussion [1].
It fixes variable offset stack access handling for raw and unprivileged mode, rejecting both of them, and sanity checks max variable offset value.
Patch 1 handles raw (uninitialized) mode.
Patch 2 adds test for raw mode.
Patch 3 handles unprivileged mode.
Patch 4 adds test for unprivileged mode.
Patch 5 adds sanity check for max value of variable offset. Patch 6 adds test for variable offset max value checking. Patch 7 is a minor fix in verbose log.
Unprivileged mode is an interesting case since one (and only?) way to come up with variable offset is to use pointer arithmetics. Though pointer arithmetics is already prohibited for unprivileged mode. I'm not sure if it's enough though and it seems like a good idea to still reject variable offset for unpriv in check_stack_boundary(). Please see patches 3 and 4 for more details on this.
[1] https://marc.info/?l=linux-netdev&m=155419526427742&w=2
Andrey Ignatov (7):
bpf: Reject indirect var_off stack access in raw mode selftests/bpf: Test indirect var_off stack access in raw mode
bpf: Reject indirect var_off stack access in unpriv mode selftests/bpf: Test indirect var_off stack access in unpriv mode
bpf: Sanity check max value for var_off stack access selftests/bpf: Test unbounded var_off stack access
bpf: Add missed newline in verifier verbose log
kernel/bpf/verifier.c | 45 ++++++- .../testing/selftests/bpf/verifier/var_off.c | 111 +++++++++++++++++- 2 files changed, 150 insertions(+), 6 deletions(-)
Signature · 1 line
2.17.1
PATCH v3 1/7 bpf: Reject indirect var_off stack access in raw mode
It's hard to guarantee that whole memory is marked as initialized on helper return if uninitialized stack is accessed with variable offset since specific bounds are unknown to verifier. This may cause uninitialized stack leaking.
Reject such an access in check_stack_boundary to prevent possible leaking.
There are no known use-cases for indirect uninitialized stack access with variable offset so it shouldn't break anything.
--- kernel/bpf/verifier.c | 9 +++++++++ 1 file changed, 9 insertions(+)
kernel/bpf/verifier.c +9 -0
@@ -2226,6 +2226,15 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,if (err)return err; }else { +/* Only initialized buffer on stack is allowed to be accessed +* with variable offset. With uninitialized buffer it's hard to +* guarantee that whole memory is marked as initialized on +* helper return since specific bounds are unknown what may +* cause uninitialized stack leaking. +*/ +if (meta && meta->raw_mode) + meta =NULL ; + min_off = reg->smin_value + reg->off; max_off = reg->umax_value + reg->off; err = __check_stack_boundary(env, regno, min_off, access_size,
Signature · 1 line
2.17.1
PATCH v3 2/7 selftests/bpf: Test indirect var_off stack access in raw mode
In reply to Andrey IgnatovTest that verifier rejects indirect access to uninitialized stack with variable offset.
Example of output:
# ./test_verifier ... #859/p indirect variable-offset stack access, uninitialized OK
--- .../testing/selftests/bpf/verifier/var_off.c | 27 +++++++++++++++++++ 1 file changed, 27 insertions(+)
tools/testing/selftests/bpf/verifier/var_off.c +27 -0
@@ -114,6 +114,33 @@ .result = REJECT, .prog_type = BPF_PROG_TYPE_LWT_IN, }, +{ + "indirect variable-offset stack access, uninitialized", + .insns = { +BPF_MOV64_IMM (BPF_REG_2 ,6 ), +BPF_MOV64_IMM (BPF_REG_3 ,28 ), +/* Fill the top 16 bytes of the stack. */ +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-16 ,0 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +/* Get an unknown value. */ +BPF_LDX_MEM (BPF_W ,BPF_REG_4 ,BPF_REG_1 ,0 ), +/* Make it small and 4-byte aligned. */ +BPF_ALU64_IMM (BPF_AND ,BPF_REG_4 ,4 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_4 ,16 ), +/* Add it to fp. We now have either fp-12 or fp-16, we don't know +* which, but either way it points to initialized stack. +*/ +BPF_ALU64_REG (BPF_ADD ,BPF_REG_4 ,BPF_REG_10 ), +BPF_MOV64_IMM (BPF_REG_5 ,8 ), +/* Dereference it indirectly. */ +BPF_EMIT_CALL (BPF_FUNC_getsockopt), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .errstr ="invalid indirect read from stack var_off" , + .result = REJECT, + .prog_type = BPF_PROG_TYPE_SOCK_OPS, +}, {"indirect variable-offset stack access, ok" , .insns = {
Signature · 1 line
2.17.1
PATCH v3 3/7 bpf: Reject indirect var_off stack access in unpriv mode
In reply to Andrey IgnatovProper support of indirect stack access with variable offset in unprivileged mode (!root) requires corresponding support in Spectre masking for stack ALU in retrieve_ptr_limit().
There are no use-case for variable offset in unprivileged mode though so make verifier reject such accesses for simplicity.
Pointer arithmetics is one (and only?) way to cause variable offset and it's already rejected in unpriv mode so that verifier won't even get to helper function whose argument contains variable offset, e.g.:
0: (7a) *(u64 *)(r10 -16) = 0
1: (7a) *(u64 *)(r10 -8) = 0
2: (61) r2 = *(u32 *)(r1 +0)
3: (57) r2 &= 4
4: (17) r2 -= 16
5: (0f) r2 += r10
variable stack access var_off=(0xfffffffffffffff0; 0x4) off=-16 size=1R2 stack pointer arithmetic goes out of range, prohibited for !root
Still it looks like a good idea to reject variable offset indirect stack access for unprivileged mode in check_stack_boundary() explicitly.
--- kernel/bpf/verifier.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
kernel/bpf/verifier.c +16 -0
@@ -2226,6 +2226,19 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,if (err)return err; }else { +/* Variable offset is prohibited for unprivileged mode for +* simplicity since it requires corresponding support in +* Spectre masking for stack ALU. +* See also retrieve_ptr_limit(). +*/ +if (!env->allow_ptr_leaks) { +char tn_buf[48 ]; + +tnum_strn (tn_buf,sizeof (tn_buf), reg->var_off); +verbose (env,"R%d indirect variable offset stack access prohibited for !root, var_off=%s\n" , + regno, tn_buf); +return -EACCES ; + }/* Only initialized buffer on stack is allowed to be accessed * with variable offset. With uninitialized buffer it's hard to * guarantee that whole memory is marked as initialized on
@@ -3368,6 +3381,9 @@ static int retrieve_ptr_limit(const struct bpf_reg_state *ptr_reg,switch (ptr_reg->type) {case PTR_TO_STACK : +/* Indirect variable offset stack access is prohibited in +* unprivileged mode so it's not handled here. +*/ off = ptr_reg->off + ptr_reg->var_off.value;if (mask_to_left) *ptr_limit =MAX_BPF_STACK + off;
Signature · 1 line
2.17.1
PATCH v3 4/7 selftests/bpf: Test indirect var_off stack access in unpriv mode
In reply to Andrey IgnatovTest that verifier rejects indirect stack access with variable offset in unprivileged mode and accepts same code in privileged mode.
Since pointer arithmetics is prohibited in unprivileged mode verifier should reject the program even before it gets to helper call that uses variable offset, at the time when that variable offset is trying to be constructed.
Example of output:
# ./test_verifier ... #859/u indirect variable-offset stack access, priv vs unpriv OK #859/p indirect variable-offset stack access, priv vs unpriv OK
--- .../testing/selftests/bpf/verifier/var_off.c | 27 +++++++++++++++++++ 1 file changed, 27 insertions(+)
tools/testing/selftests/bpf/verifier/var_off.c +27 -0
@@ -114,6 +114,33 @@ .result = REJECT, .prog_type = BPF_PROG_TYPE_LWT_IN, }, +{ + "indirect variable-offset stack access, priv vs unpriv", + .insns = { +/* Fill the top 16 bytes of the stack. */ +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-16 ,0 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +/* Get an unknown value. */ +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 ,0 ), +/* Make it small and 4-byte aligned. */ +BPF_ALU64_IMM (BPF_AND ,BPF_REG_2 ,4 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_2 ,16 ), +/* Add it to fp. We now have either fp-12 or fp-16, we don't know +* which, but either way it points to initialized stack. +*/ +BPF_ALU64_REG (BPF_ADD ,BPF_REG_2 ,BPF_REG_10 ), +/* Dereference it indirectly. */ +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_8b = { 6 }, + .errstr_unpriv = "R2 stack pointer arithmetic goes out of range, prohibited for !root", + .result_unpriv = REJECT, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, +}, {"indirect variable-offset stack access, uninitialized" , .insns = {
Signature · 1 line
2.17.1
PATCH v3 5/7 bpf: Sanity check max value for var_off stack access
In reply to Andrey IgnatovAs discussed in [1] max value of variable offset has to be checked for overflow on stack access otherwise verifier would accept code like this:
0: (b7) r2 = 6 1: (b7) r3 = 28 2: (7a) *(u64 *)(r10 -16) = 0 3: (7a) *(u64 *)(r10 -8) = 0 4: (79) r4 = *(u64 *)(r1 +168) 5: (c5) if r4 s< 0x0 goto pc+4 R1=ctx(id=0,off=0,imm=0) R2=inv6 R3=inv28 R4=inv(id=0,umax_value=9223372036854775807,var_off=(0x0; 0x7fffffffffffffff)) R10=fp0,call_-1 fp-8=mmmmmmmm fp-16=mmmmmmmm 6: (17) r4 -= 16 7: (0f) r4 += r10 8: (b7) r5 = 8 9: (85) call bpf_getsockopt#57 10: (b7) r0 = 0 11: (95) exit
, where R4 obviosly has unbounded max value.
Fix it by checking that reg->smax_value is inside (-BPF_MAX_VAR_OFF; BPF_MAX_VAR_OFF) range.
reg->smax_value is used instead of reg->umax_value because stack pointers are calculated using negative offset from fp. This is opposite to e.g. map access where offset must be non-negative and where umax_value is used.
Also dedicated verbose logs are added for both min and max bound check failures to have diagnostics consistent with variable offset handling in check_map_access().
[1] https://marc.info/?l=linux-netdev&m=155433357510597&w=2
--- kernel/bpf/verifier.c | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +15 -3
@@ -2248,16 +2248,28 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,if (meta && meta->raw_mode) meta =NULL ; +if (reg->smax_value >=BPF_MAX_VAR_OFF || + reg->smax_value <= -BPF_MAX_VAR_OFF ) { +verbose (env,"R%d unbounded indirect variable offset stack access\n" , + regno); +return -EACCES ; + } min_off = reg->smin_value + reg->off; - max_off = reg->umax_value + reg->off; + max_off = reg->smax_value + reg->off; err =__check_stack_boundary (env, regno, min_off, access_size, zero_size_allowed); -if (err) +if (err) { +verbose (env,"R%d min value is outside of stack bound\n" , + regno);return err; + } err =__check_stack_boundary (env, regno, max_off, access_size, zero_size_allowed); -if (err) +if (err) { +verbose (env,"R%d max value is outside of stack bound\n" , + regno);return err; + } }if (meta && meta->raw_mode) {
Signature · 1 line
2.17.1
PATCH v3 6/7 selftests/bpf: Test unbounded var_off stack access
In reply to Andrey IgnatovTest the case when reg->smax_value is too small/big and can overflow, and separately min and max values outside of stack bounds.
Example of output:
# ./test_verifier #856/p indirect variable-offset stack access, unbounded OK #857/p indirect variable-offset stack access, max out of bound OK #858/p indirect variable-offset stack access, min out of bound OK
--- .../testing/selftests/bpf/verifier/var_off.c | 57 ++++++++++++++++++- 1 file changed, 55 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/verifier/var_off.c +55 -2
@@ -40,7 +40,35 @@ .prog_type = BPF_PROG_TYPE_LWT_IN, }, { - "indirect variable-offset stack access, out of bound", + "indirect variable-offset stack access, unbounded", + .insns = { +BPF_MOV64_IMM (BPF_REG_2 ,6 ), +BPF_MOV64_IMM (BPF_REG_3 ,28 ), +/* Fill the top 16 bytes of the stack. */ +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-16 ,0 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +/* Get an unknown value. */ +BPF_LDX_MEM (BPF_DW ,BPF_REG_4 ,BPF_REG_1 , offsetof(struct bpf_sock_ops , + bytes_received)), +/* Check the lower bound but don't check the upper one. */ +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_4 ,0 ,4 ), +/* Point the lower bound to initialized stack. Offset is now in range +* from fp-16 to fp+0x7fffffffffffffef, i.e. max value is unbounded. +*/ +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_4 ,16 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_4 ,BPF_REG_10 ), +BPF_MOV64_IMM (BPF_REG_5 ,8 ), +/* Dereference it indirectly. */ +BPF_EMIT_CALL (BPF_FUNC_getsockopt), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .errstr ="R4 unbounded indirect variable offset stack access" , + .result = REJECT, + .prog_type = BPF_PROG_TYPE_SOCK_OPS, +}, +{ +"indirect variable-offset stack access, max out of bound" , .insns = {/* Fill the top 8 bytes of the stack */ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
@@ -60,7 +88,32 @@ BPF_EXIT_INSN(), }, .fixup_map_hash_8b = { 5 }, - .errstr = "invalid stack type R2 var_off", + .errstr = "R2 max value is outside of stack bound", + .result = REJECT, + .prog_type = BPF_PROG_TYPE_LWT_IN, +}, +{ + "indirect variable-offset stack access, min out of bound", + .insns = { +/* Fill the top 8 bytes of the stack */ +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +/* Get an unknown value */ +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 ,0 ), +/* Make it small and 4-byte aligned */ +BPF_ALU64_IMM (BPF_AND ,BPF_REG_2 ,4 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_2 ,516 ), +/* add it to fp. We now have either fp-516 or fp-512, but +* we don't know which +*/ +BPF_ALU64_REG (BPF_ADD ,BPF_REG_2 ,BPF_REG_10 ), +/* dereference it indirectly */ +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_8b = { 5 }, + .errstr = "R2 min value is outside of stack bound", .result = REJECT, .prog_type = BPF_PROG_TYPE_LWT_IN, },
Signature · 1 line
2.17.1
PATCH v3 7/7 bpf: Add missed newline in verifier verbose log
In reply to Andrey Ignatovcheck_stack_access() that prints verbose log is used in adjust_ptr_min_max_vals() that prints its own verbose log and now they stick together, e.g.:
variable stack access var_off=(0xfffffffffffffff0; 0x4) off=-16 size=1R2 stack pointer arithmetic goes out of range, prohibited for !root
Add missing newline so that log is more readable:
variable stack access var_off=(0xfffffffffffffff0; 0x4) off=-16 size=1 R2 stack pointer arithmetic goes out of range, prohibited for !root
--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
@@ -1426,7 +1426,7 @@ static int check_stack_access(struct bpf_verifier_env *env,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" , +verbose (env,"variable stack access var_off=%s off=%d size=%d\n" , tn_buf, off, size);return -EACCES ; }
Signature · 1 line
2.17.1
Quoted 38 lines · Andrey Ignatov
v2->v3:
- sanity check max value for variable offset.
v1->v2:
- rely on meta = NULL to rejectvar_offstack access to uninit buffer.This patch set is a follow-up for discussion [1].
It fixes variable offset stack access handling for raw and unprivileged mode, rejecting both of them, and sanity checks max variable offset value.
Patch 1 handles raw (uninitialized) mode.
Patch 2 adds test for raw mode.
Patch 3 handles unprivileged mode.
Patch 4 adds test for unprivileged mode.
Patch 5 adds sanity check for max value of variable offset. Patch 6 adds test for variable offset max value checking. Patch 7 is a minor fix in verbose log.Unprivileged mode is an interesting case since one (and only?) way to come up with variable offset is to use pointer arithmetics. Though pointer arithmetics is already prohibited for unprivileged mode. I'm not sure if it's enough though and it seems like a good idea to still reject variable offset for unpriv in
check_stack_boundary(). Please see patches 3 and 4 for more details on this.[1] https://marc.info/?l=linux-netdev&m=155419526427742&w=2
Andrey Ignatov (7):
bpf: Reject indirectvar_offstack access in raw mode selftests/bpf: Test indirectvar_offstack access in raw mode
bpf: Reject indirectvar_offstack access in unpriv mode selftests/bpf: Test indirectvar_offstack access in unpriv mode
bpf: Sanity check max value forvar_offstack access selftests/bpf: Test unboundedvar_offstack access
bpf: Add missed newline in verifier verbose log
Quoted 4 lines
kernel/bpf/verifier.c | 45 ++++++- .../testing/selftests/bpf/verifier/var_off.c | 111 +++++++++++++++++- 2 files changed, 150 insertions(+), 6 deletions(-)
Applied, thanks!