* [PATCH bpf] bpf: fix precision tracking of stack slots
@ 2019-09-03 22:16 Alexei Starovoitov
2019-09-05 13:15 ` Daniel Borkmann
0 siblings, 1 reply; 2+ messages in thread
From: Alexei Starovoitov @ 2019-09-03 22:16 UTC (permalink / raw)
To: davem; +Cc: daniel, netdev, bpf, kernel-team
The problem can be seen in the following two tests:
0: (bf) r3 = r10
1: (55) if r3 != 0x7b goto pc+0
2: (7a) *(u64 *)(r3 -8) = 0
3: (79) r4 = *(u64 *)(r10 -8)
..
0: (85) call bpf_get_prandom_u32#7
1: (bf) r3 = r10
2: (55) if r3 != 0x7b goto pc+0
3: (7b) *(u64 *)(r3 -8) = r0
4: (79) r4 = *(u64 *)(r10 -8)
When backtracking need to mark R4 it will mark slot fp-8.
But ST or STX into fp-8 could belong to the same block of instructions.
When backtracing is done the parent state may have fp-8 slot
as "unallocated stack". Which will cause verifier to warn
and incorrectly reject such programs.
Writes into stack via non-R10 register are rare. llvm always
generates canonical stack spill/fill.
For such pathological case fall back to conservative precision
tracking instead of rejecting.
Reported-by: syzbot+c8d66267fd2b5955287e@syzkaller.appspotmail.com
Fixes: b5dc0163d8fd ("bpf: precise scalar_value tracking")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
tests will be submitted to bpf-next.
kernel/bpf/verifier.c | 23 ++++++++++++++---------
1 file changed, 14 insertions(+), 9 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b5c14c9d7b98..c36a719fee6d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1772,16 +1772,21 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
bitmap_from_u64(mask, stack_mask);
for_each_set_bit(i, mask, 64) {
if (i >= func->allocated_stack / BPF_REG_SIZE) {
- /* This can happen if backtracking
- * is propagating stack precision where
- * caller has larger stack frame
- * than callee, but backtrack_insn() should
- * have returned -ENOTSUPP.
+ /* the sequence of instructions:
+ * 2: (bf) r3 = r10
+ * 3: (7b) *(u64 *)(r3 -8) = r0
+ * 4: (79) r4 = *(u64 *)(r10 -8)
+ * doesn't contain jmps. It's backtracked
+ * as a single block.
+ * During backtracking insn 3 is not recognized as
+ * stack access, so at the end of backtracking
+ * stack slot fp-8 is still marked in stack_mask.
+ * However the parent state may not have accessed
+ * fp-8 and it's "unallocated" stack space.
+ * In such case fallback to conservative.
*/
- verbose(env, "BUG spi %d stack_size %d\n",
- i, func->allocated_stack);
- WARN_ONCE(1, "verifier backtracking bug");
- return -EFAULT;
+ mark_all_scalars_precise(env, st);
+ return 0;
}
if (func->stack[i].slot_type[0] != STACK_SPILL) {
--
2.20.0
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [PATCH bpf] bpf: fix precision tracking of stack slots
2019-09-03 22:16 [PATCH bpf] bpf: fix precision tracking of stack slots Alexei Starovoitov
@ 2019-09-05 13:15 ` Daniel Borkmann
0 siblings, 0 replies; 2+ messages in thread
From: Daniel Borkmann @ 2019-09-05 13:15 UTC (permalink / raw)
To: Alexei Starovoitov, davem; +Cc: netdev, bpf, kernel-team
On 9/4/19 12:16 AM, Alexei Starovoitov wrote:
> The problem can be seen in the following two tests:
> 0: (bf) r3 = r10
> 1: (55) if r3 != 0x7b goto pc+0
> 2: (7a) *(u64 *)(r3 -8) = 0
> 3: (79) r4 = *(u64 *)(r10 -8)
> ..
> 0: (85) call bpf_get_prandom_u32#7
> 1: (bf) r3 = r10
> 2: (55) if r3 != 0x7b goto pc+0
> 3: (7b) *(u64 *)(r3 -8) = r0
> 4: (79) r4 = *(u64 *)(r10 -8)
>
> When backtracking need to mark R4 it will mark slot fp-8.
> But ST or STX into fp-8 could belong to the same block of instructions.
> When backtracing is done the parent state may have fp-8 slot
> as "unallocated stack". Which will cause verifier to warn
> and incorrectly reject such programs.
>
> Writes into stack via non-R10 register are rare. llvm always
> generates canonical stack spill/fill.
> For such pathological case fall back to conservative precision
> tracking instead of rejecting.
>
> Reported-by: syzbot+c8d66267fd2b5955287e@syzkaller.appspotmail.com
> Fixes: b5dc0163d8fd ("bpf: precise scalar_value tracking")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Applied, thanks!
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2019-09-05 13:15 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-09-03 22:16 [PATCH bpf] bpf: fix precision tracking of stack slots Alexei Starovoitov
2019-09-05 13:15 ` Daniel Borkmann
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).