From: Alexei Starovoitov Tests for the patch that recomputes a pointer after the jump that bounds its index. Since that patch a linked register of a conditional jump can be a pointer: an address base + the tested register + a constant on every path to the jump. Each prog adds an index to a pointer to 64 bytes, tests the index and reads through the result. What loads is run. - The add comes before the jump: loads. - Only the low 32 bits of the index are tested. Rejected. - base + index at a loop header: the add is at the end of an iteration, the jump at the header. Negative tests: it holds at loop entry only, on the backedge only. - In a prog with an arena 'r1 += r2' is trusted once the main pass has verified it without an arena pointer (prevent_zext): loads. The test with an arena is in verifier_arena.c, the others in verifier_scev.c. Signed-off-by: Alexei Starovoitov --- .../selftests/bpf/progs/verifier_arena.c | 3 +++ .../selftests/bpf/progs/verifier_scev.c | 25 +++++++++++++++++++ 2 files changed, 28 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/verifier_arena.c b/tools/testing/selftests/bpf/progs/verifier_arena.c index bf50413f6c08..3931a1d9b6da 100644 --- a/tools/testing/selftests/bpf/progs/verifier_arena.c +++ b/tools/testing/selftests/bpf/progs/verifier_arena.c @@ -663,6 +663,9 @@ ARENA_LINKED(arena_ptr_plus_constant, __failure, ARENA_LINKED(arena_ptr_plus_constant_on_two_paths, __failure, "if r8 == 0 goto 1f; r3 += 1; goto 2f; 1: r3 += 1; 2: r8 += 1; r3 = le64 r3; r7 = le64 r7;" "r2 = 0xffffffff ll; if r7 != r2 goto out_%=; r3 >>= 32; r3 -= 1; r1 = r6; r1 += r3;") +/* 'r1 += r2' was verified without a pointer to arena: it stays ALU64 */ +ARENA_LINKED(index_tested_after_the_add, __success __retval(0), + "r2 = r8; r2 &= 255; r1 = r6; r1 += r2; if r2 > 63 goto out_%=; r0 = *(u8 *)(r6 + 0);") SEC("syscall") __description("arena: a number is not an address in arena") diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c index 1047845c916b..8ffbe7bbdb0a 100644 --- a/tools/testing/selftests/bpf/progs/verifier_scev.c +++ b/tools/testing/selftests/bpf/progs/verifier_scev.c @@ -3341,12 +3341,37 @@ __naked void name(void) \ #define LINKED(name, expect, body) LINKED_SEC("socket", name, expect, body) #define VALID __success __retval(0) +#define MAP_OOB __failure __msg("invalid access to map value") #define UNBOUND __failure __msg("unbounded min value") /* r3 is the address in r1 as a scalar. It does not bound the offset of r1. */ LINKED(pointer_is_not_scalar, __failure, "r7 &= 127; r1 = r6; r1 += r7; r3 = r1; r3 = le64 r3; if r3 < 64 goto out_%=; r1 += -64;") +/* + * p = buf + i; if (i > 63) return 0; c = *p; + * The jump bounds i. r1 is r6 + r7 and r6 is live: r1 is recomputed. + */ +#define USE_R6 "r0 = *(u8 *)(r6 + 0);" + +LINKED(index_tested_after_the_add, VALID, "r1 = r6; r1 += r7; if r7 > 63 goto out_%=;" USE_R6) +LINKED(low_32_bits_of_the_index_tested, __failure __msg("R1 unbounded memory access"), + "r2 = 0x1000000ff ll; r2 &= r8; r1 = r6; r1 += r2; w3 = w2; if r3 > 63 goto out_%=;" USE_R6) + +/* + * p = buf; i = 0; do { if (i > 62) break; i = *(u16 *)p; p = buf + i; } while (i); + * r1 == r6 + r2 at the header in every iteration: it holds at loop entry, the backedge preserves it + */ +#define LOOP(add) \ + "l_%=: if r2 > 62 goto out_%=; r2 = *(u16 *)(r1 + 0);" add \ + "if r2 != 0 goto l_%=; r1 = r6;" + +LINKED(base_plus_index_at_loop_header, VALID, "r1 = r6; r2 = 0;" LOOP("r1 = r6; r1 += r2;")) +LINKED(base_plus_index_at_loop_entry_only, MAP_OOB, + "r1 = r6; r2 = 0;" LOOP("r1 = r6; r1 += r2; r2 >>= 1;")) +LINKED(base_plus_index_on_backedge_only, MAP_OOB, + "r1 = r6; r1 += r7; r2 = r8; r2 &= 255;" LOOP("r1 = r6; r1 += r2;")) + LINKED(sign_extension_that_fits, VALID, "r2 = (s8)r8; if r8 > 63 goto out_%=; r1 = r6; r1 += r2;") /* The low 3 bits of r3 are 5. It is r8 + 5 once r8 fits in s8: no overlap with [-2, 1]. */ -- 2.55.0