BPF pruning follow-up
Subsystems (6)
Daniel Borkmann
maintainercover BPF pruning follow-up
Follow-up to fix incorrect pruning when alignment tracking is in use and to properly clear regs after call to not leave stale data behind. For details, please see individual patches.
Thanks!
Daniel Borkmann (3):
bpf: fix incorrect pruning decision when alignment must be tracked
bpf: properly reset caller saved regs after helper call and ld_abs/ind
bpf: add various verifier test cases
include/linux/filter.h | 10 ++ kernel/bpf/verifier.c | 44 +++-- tools/include/linux/filter.h | 10 ++ tools/testing/selftests/bpf/test_verifier.c | 239 +++++++++++++++++++++++++++- 4 files changed, 275 insertions(+), 28 deletions(-)
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 1/3 bpf: fix incorrect pruning decision when alignment must be tracked
Currently, when we enforce alignment tracking on direct packet access, the verifier lets the following program pass despite doing a packet write with unaligned access:
0: (61) r2 = *(u32 *)(r1 +76)
1: (61) r3 = *(u32 *)(r1 +80)
2: (61) r7 = *(u32 *)(r1 +8)
3: (bf) r0 = r2
4: (07) r0 += 14
5: (25) if r7 > 0x1 goto pc+4
R0=pkt(id=0,off=14,r=0) R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R7=inv,min_value=0,max_value=1 R10=fp
6: (2d) if r0 > r3 goto pc+1
R0=pkt(id=0,off=14,r=14) R1=ctx R2=pkt(id=0,off=0,r=14) R3=pkt_end R7=inv,min_value=0,max_value=1 R10=fp
7: (63) *(u32 *)(r0 -4) = r0
8: (b7) r0 = 0
9: (95) exit
from 6 to 8:
R0=pkt(id=0,off=14,r=0) R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R7=inv,min_value=0,max_value=1 R10=fp
8: (b7) r0 = 0
9: (95) exit
from 5 to 10:
R0=pkt(id=0,off=14,r=0) R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R7=inv,min_value=2 R10=fp
10: (07) r0 += 1
11: (05) goto pc-6
6: safe <----- here, wrongly found safe
processed 15 insns
However, if we enforce a pruning mismatch by adding state into r8 which is then being mismatched in states_equal(), we find that for the otherwise same program, the verifier detects a misaligned packet access when actually walking that path:
0: (61) r2 = *(u32 *)(r1 +76)
1: (61) r3 = *(u32 *)(r1 +80)
2: (61) r7 = *(u32 *)(r1 +8)
3: (b7) r8 = 1
4: (bf) r0 = r2
5: (07) r0 += 14
6: (25) if r7 > 0x1 goto pc+4
R0=pkt(id=0,off=14,r=0) R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R7=inv,min_value=0,max_value=1 R8=imm1,min_value=1,max_value=1,min_align=1 R10=fp
7: (2d) if r0 > r3 goto pc+1
R0=pkt(id=0,off=14,r=14) R1=ctx R2=pkt(id=0,off=0,r=14) R3=pkt_end R7=inv,min_value=0,max_value=1 R8=imm1,min_value=1,max_value=1,min_align=1 R10=fp
8: (63) *(u32 *)(r0 -4) = r0
9: (b7) r0 = 0
10: (95) exit
from 7 to 9:
R0=pkt(id=0,off=14,r=0) R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R7=inv,min_value=0,max_value=1 R8=imm1,min_value=1,max_value=1,min_align=1 R10=fp
9: (b7) r0 = 0
10: (95) exit
from 6 to 11:
R0=pkt(id=0,off=14,r=0) R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R7=inv,min_value=2 R8=imm1,min_value=1,max_value=1,min_align=1 R10=fp
11: (07) r0 += 1
12: (b7) r8 = 0
13: (05) goto pc-7 <----- mismatch due to r8
7: (2d) if r0 > r3 goto pc+1
R0=pkt(id=0,off=15,r=15) R1=ctx R2=pkt(id=0,off=0,r=15) R3=pkt_end R7=inv,min_value=2 R8=imm0,min_value=0,max_value=0,min_align=2147483648 R10=fp
8: (63) *(u32 *)(r0 -4) = r0
misaligned packet access off 2+15+-4 size 4
The reason why we fail to see it in states_equal() is that the third test in compare_ptrs_to_packet() ...
if (old->off <= cur->off &&
old->off >= old->range && cur->off >= cur->range)
return true;... will let the above pass. The situation we run into is that old->off <= cur->off (14 <= 15), meaning that prior walked paths went with smaller offset, which was later used in the packet access after successful packet range check and found to be safe already.
For example: Given is R0=pkt(id=0,off=0,r=0). Adding offset 14 as in above program to it, results in R0=pkt(id=0,off=14,r=0) before the packet range test. Now, testing this against R3=pkt_end with 'if r0 > r3 goto out' will transform R0 into R0=pkt(id=0,off=14,r=14) for the case when we're within bounds. A write into the packet at offset *(u32 *)(r0 -4), that is, 2 + 14 -4, is valid and aligned (2 is for NET_IP_ALIGN). After processing this with all fall-through paths, we later on check paths from branches. When the above skb->mark test is true, then we jump near the end of the program, perform r0 += 1, and jump back to the
'if r0 > r3 goto out' test we've visited earlier already. This time, R0 is of type R0=pkt(id=0,off=15,r=0), and we'll prune that part because this time we'll have a larger safe packet range, and we already found that with off=14 all further insn were already safe, so it's safe as well with a larger off. However, the problem is that the subsequent write into the packet with 2 + 15 -4 is then unaligned, and not caught by the alignment tracking. Note that min_align, aux_off, and aux_off_align were all 0 in this example.
Since we cannot tell at this time what kind of packet access was performed in the prior walk and what minimal requirements it has (we might do so in the future, but that requires more complexity), fix it to disable this pruning case for strict alignment for now, and let the verifier do check such paths instead. With that applied, the test cases pass and reject the program due to misalignment.
Reference: http://patchwork.ozlabs.org/patch/761909/
--- kernel/bpf/verifier.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +4 -3
@@ -2696,7 +2696,8 @@ static int check_cfg(struct bpf_verifier_env *env)/* the following conditions reduce the number of explored insns * from ~140k to ~80k for ultra large programs that use a lot of ptr_to_packet */ -static bool compare_ptrs_to_packet (struct bpf_reg_state *old, +static bool compare_ptrs_to_packet (struct bpf_verifier_env *env, +struct bpf_reg_state *old,struct bpf_reg_state *cur) {if (old->id != cur->id)
@@ -2739,7 +2740,7 @@ static bool compare_ptrs_to_packet(struct bpf_reg_state *old,* 'if (R4 > data_end)' and all further insn were already good with r=20, * so they will be good with r=30 and we can prune the search. */ -if (old->off <= cur->off && +if (!env->strict_alignment && old->off <= cur->off && old->off >= old->range && cur->off >= cur->range)return true;
@@ -2810,7 +2811,7 @@ static bool states_equal(struct bpf_verifier_env *env,continue ;if (rold->type ==PTR_TO_PACKET && rcur->type ==PTR_TO_PACKET && -compare_ptrs_to_packet (rold, rcur)) +compare_ptrs_to_packet (env, rold, rcur))continue ;return false;
Signature · 1 line
1.9.3
David Miller
maintainerRe: [PATCH net 1/3] bpf: fix incorrect pruning decision when alignment must be tracked
From: Daniel Borkmann <[email protected]>
Date: Tue, 23 May 2017 18:30:41 +0200
kernel/bpf/verifier.c static bool compare_ptrs_to_packet(struct bpf_reg_state *old, · line 2743
Quoted 1 line
kernel/bpf/verifier.c +1
-0+ if (!env->strict_alignment && old->off <= cur->off &&
You can't just test env->strict_alignment by itself, that's just an override and doesn't determine the actual "strict" value we use which is a combination of env->strict_alignment and "!CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS".
So you'll have to update this test.
Daniel Borkmann
maintainerRe: [PATCH net 1/3] bpf: fix incorrect pruning decision when alignment must be tracked
Quoted 11 lines · David Miller
From: Daniel Borkmann <[email protected]>
Date: Tue, 23 May 2017 18:30:41 +0200kernel/bpf/verifier.c static bool compare_ptrs_to_packet(struct bpf_reg_state *old, · line 2743
Quoted 1 line
kernel/bpf/verifier.c +1
-0+ if (!env->strict_alignment && old->off <= cur->off &&You can't just test
env->strict_alignmentby itself, that's just an override and doesn't determine the actual "strict" value we use which is a combination ofenv->strict_alignmentand "!CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS".So you'll have to update this test.
Argh, good point, true. Will respin with a v2.
Daniel Borkmann
maintainerPATCH 2/3 bpf: properly reset caller saved regs after helper call and ld_abs/ind
In reply to Daniel BorkmannCurrently, after performing helper calls, we clear all caller saved registers, that is r0 - r5 and fill r0 depending on struct bpf_func_proto specification. The way we reset these regs can affect pruning decisions in later paths, since we only reset register's imm to 0 and type to NOT_INIT. However, we leave out clearing of other variables such as id, min_value, max_value, etc, which can later on lead to pruning mismatches due to stale data.
--- kernel/bpf/verifier.c | 37 ++++++++++++++++--------------------- 1 file changed, 16 insertions(+), 21 deletions(-)
kernel/bpf/verifier.c +16 -21
@@ -463,19 +463,22 @@ static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env, BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5 }; +static void mark_reg_not_init (struct bpf_reg_state *regs,u32 regno) +{ +BUG_ON (regno >=MAX_BPF_REG ); + +memset (®s[regno],0 ,sizeof (regs[regno])); + regs[regno].type =NOT_INIT ; + regs[regno].min_value =BPF_REGISTER_MIN_RANGE ; + regs[regno].max_value =BPF_REGISTER_MAX_RANGE ; +} +static void init_reg_state (struct bpf_reg_state *regs) {int i; -for (i =0 ; i <MAX_BPF_REG ; i++) { - regs[i].type =NOT_INIT ; - regs[i].imm =0 ; - regs[i].min_value =BPF_REGISTER_MIN_RANGE ; - regs[i].max_value =BPF_REGISTER_MAX_RANGE ; - regs[i].min_align =0 ; - regs[i].aux_off =0 ; - regs[i].aux_off_align =0 ; - } +for (i =0 ; i <MAX_BPF_REG ; i++) +mark_reg_not_init (regs, i);/* frame pointer */ regs[BPF_REG_FP ].type =FRAME_PTR ;
@@ -1349,7 +1352,6 @@ static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx)struct bpf_verifier_state *state = &env->cur_state;const struct bpf_func_proto *fn =NULL ;struct bpf_reg_state *regs = state->regs; -struct bpf_reg_state *reg;struct bpf_call_arg_meta meta;bool changes_data;int i, err;
@@ -1416,11 +1418,8 @@ static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx) }/* reset caller saved regs */ -for (i =0 ; i <CALLER_SAVED_REGS ; i++) { - reg = regs + caller_saved[i]; - reg->type =NOT_INIT ; - reg->imm =0 ; - } +for (i =0 ; i <CALLER_SAVED_REGS ; i++) +mark_reg_not_init (regs, caller_saved[i]);/* update return register */ if (fn->ret_type ==RET_INTEGER ) {
@@ -2448,7 +2447,6 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) {struct bpf_reg_state *regs = env->cur_state.regs;u8 mode =BPF_MODE (insn->code); -struct bpf_reg_state *reg;int i, err;if (!may_access_skb (env->prog->type)) {
@@ -2481,11 +2479,8 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) }/* reset caller saved regs to unreadable */ -for (i =0 ; i <CALLER_SAVED_REGS ; i++) { - reg = regs + caller_saved[i]; - reg->type =NOT_INIT ; - reg->imm =0 ; - } +for (i =0 ; i <CALLER_SAVED_REGS ; i++) +mark_reg_not_init (regs, caller_saved[i]);/* mark destination R0 register as readable, since it contains * the value fetched from the packet
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 3/3 bpf: add various verifier test cases
In reply to Daniel BorkmannThis patch adds various verifier test cases:
1) A test case for the pruning issue when tracking alignment is used.
2) Various PTR_TO_MAP_VALUE_OR_NULL tests to make sure pointer arithmetic turns such register into UNKNOWN_VALUE type.
3) Test cases for the special treatment of LD_ABS/LD_IND to make sure verifier doesn't break calling convention here. Latter is needed, since f.e. arm64 JIT uses r1 - r5 for storing temporary data, so they really must be marked as NOT_INIT.
--- include/linux/filter.h | 10 ++ tools/include/linux/filter.h | 10 ++ tools/testing/selftests/bpf/test_verifier.c | 239 +++++++++++++++++++++++++++- 3 files changed, 255 insertions(+), 4 deletions(-)
include/linux/filter.h +10 -0
@@ -272,6 +272,16 @@ .off = OFF, \ .imm = IMM }) +/* Unconditional jumps, goto pc + off16 */ + +#define BPF_JMP_A (OFF ) \ + ((struct bpf_insn) { \ + .code = BPF_JMP | BPF_JA, \ + .dst_reg = 0, \ + .src_reg = 0, \ + .off = OFF, \ + .imm = 0 }) +/* Function call */ #define BPF_EMIT_CALL (FUNC ) \
tools/include/linux/filter.h +10 -0
@@ -208,6 +208,16 @@ .off = OFF, \ .imm = IMM }) +/* Unconditional jumps, goto pc + off16 */ + +#define BPF_JMP_A (OFF ) \ + ((struct bpf_insn) { \ + .code = BPF_JMP | BPF_JA, \ + .dst_reg = 0, \ + .src_reg = 0, \ + .off = OFF, \ + .imm = 0 }) +/* Function call */ #define BPF_EMIT_CALL (FUNC ) \
tools/testing/selftests/bpf/test_verifier.c +235 -4
269 lines not on this page · raw message
Signature · 1 line
1.9.3