From: Yazhou Tang Now BPF_DIV has value tracking support via interval and tnum analysis. This patch adds selftests to cover various cases of signed and unsigned division operations, including edge cases like division by zero and signed division overflow. Specifically, these selftests are based on dead code elimination: If the BPF verifier can precisely analyze the result of a division operation, it can prune the path that leads to an error (here we use invalid memory access as the error case), allowing the program to pass verification. Co-developed-by: Shenghao Yuan Signed-off-by: Shenghao Yuan Co-developed-by: Tianci Cao Signed-off-by: Tianci Cao Signed-off-by: Yazhou Tang --- Hello everyone, Thanks for reviewing our patch! This patch adds the necessary selftests for the BPF_DIV range tracking enhancements. Regarding the test implementation: I noticed multiple patterns for BPF selftests (e.g., out-of-bounds read in `verifier_bounds.c`, illegal return value in `verifier_mul.c` and `verifier_precision.v`). I have opted for the invalid memory access approach with `__msg` label as it is concise and straightforward. If the community prefers these tests to be integrated into existing files or follow a different pattern, please let me know and I will gladly refactor them. Best, Yazhou Tang .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_div_bounds.c | 404 ++++++++++++++++++ 2 files changed, 406 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_div_bounds.c diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c index 5829ffd70f8f..d892ad7b688e 100644 --- a/tools/testing/selftests/bpf/prog_tests/verifier.c +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c @@ -33,6 +33,7 @@ #include "verifier_direct_packet_access.skel.h" #include "verifier_direct_stack_access_wraparound.skel.h" #include "verifier_div0.skel.h" +#include "verifier_div_bounds.skel.h" #include "verifier_div_overflow.skel.h" #include "verifier_global_subprogs.skel.h" #include "verifier_global_ptr_args.skel.h" @@ -174,6 +175,7 @@ void test_verifier_d_path(void) { RUN(verifier_d_path); } void test_verifier_direct_packet_access(void) { RUN(verifier_direct_packet_access); } void test_verifier_direct_stack_access_wraparound(void) { RUN(verifier_direct_stack_access_wraparound); } void test_verifier_div0(void) { RUN(verifier_div0); } +void test_verifier_div_bounds(void) { RUN(verifier_div_bounds); } void test_verifier_div_overflow(void) { RUN(verifier_div_overflow); } void test_verifier_global_subprogs(void) { RUN(verifier_global_subprogs); } void test_verifier_global_ptr_args(void) { RUN(verifier_global_ptr_args); } diff --git a/tools/testing/selftests/bpf/progs/verifier_div_bounds.c b/tools/testing/selftests/bpf/progs/verifier_div_bounds.c new file mode 100644 index 000000000000..7a8b6905de56 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/verifier_div_bounds.c @@ -0,0 +1,404 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include +#include +#include +#include "bpf_misc.h" + +/* This file contains unit tests for signed/unsigned division + * operations, focusing on verifying whether BPF verifier's + * tnum and interval analysis modules soundly and precisely + * compute the results. + */ + +SEC("socket") +__description("UDIV32, non-zero divisor") +__success __retval(0) __log_level(2) +__msg("w1 /= w2 {{.*}}; R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))") +__naked void udiv32_non_zero(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + w1 = w0; \ + w2 = w0; \ + w1 &= 8; \ + w1 |= 1; \ + w2 &= 1; \ + w2 |= 2; \ + w1 /= w2; \ + if w1 <= 4 goto l0_%=; \ + /* Precise analysis will prune the path with error code */\ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("UDIV32, zero divisor") +__success __retval(0) __log_level(2) +__msg("w1 /= w2 {{.*}}; R1=0 R2=0") +__naked void udiv32_zero_divisor(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + w1 = w0; \ + w1 &= 8; \ + w1 |= 1; \ + w2 = 0; \ + w1 /= w2; \ + if w1 == 0 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("UDIV64, non-zero divisor") +__success __retval(0) __log_level(2) +__msg("r1 /= r2 {{.*}}; R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))") +__naked void udiv64_non_zero(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r2 = r0; \ + r1 &= 8; \ + r1 |= 1; \ + r2 &= 1; \ + r2 |= 2; \ + r1 /= r2; \ + if r1 <= 4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("UDIV64, zero divisor") +__success __retval(0) __log_level(2) +__msg("r1 /= r2 {{.*}}; R1=0 R2=0") +__naked void udiv64_zero_divisor(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r1 &= 8; \ + r1 |= 1; \ + r2 = 0; \ + r1 /= r2; \ + if r1 == 0 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV32, non-zero divisor") +__success __retval(0) __log_level(2) +__msg("w1 s/= w2 {{.*}}; R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))") +__naked void sdiv32_non_zero(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + w1 = w0; \ + w2 = w0; \ + w1 &= 8; \ + w1 |= 1; \ + w2 &= 1; \ + w2 |= 2; \ + w1 s/= w2; \ + if w1 s<= 4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV32, non-zero divisor, negative dividend") +__success __retval(0) __log_level(2) +__msg("w1 s/= w2 {{.*}}; R1=scalar(smin=0,smax=umax=0xffffffff,smin32=-4,smax32=0,var_off=(0x0; 0xffffffff))") +__naked void sdiv32_negative_dividend(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + w1 = w0; \ + w2 = w0; \ + w1 &= 8; \ + w1 |= 1; \ + w1 = -w1; \ + w2 &= 1; \ + w2 |= 2; \ + w1 s/= w2; \ + if w1 s>= -4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV32, non-zero divisor, negative divisor") +__success __retval(0) __log_level(2) +__msg("w1 s/= w2 {{.*}}; R1=scalar(smin=0,smax=umax=0xffffffff,smin32=-4,smax32=0,var_off=(0x0; 0xffffffff))") +__naked void sdiv32_negative_divisor(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + w1 = w0; \ + w2 = w0; \ + w1 &= 8; \ + w1 |= 1; \ + w2 &= 1; \ + w2 |= 2; \ + w2 = -w2; \ + w1 s/= w2; \ + if w1 s>= -4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV32, non-zero divisor, both negative") +__success __retval(0) __log_level(2) +__msg("w1 s/= w2 {{.*}}; R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))") +__naked void sdiv32_both_negative(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + w1 = w0; \ + w2 = w0; \ + w1 &= 8; \ + w1 |= 1; \ + w2 &= 1; \ + w2 |= 2; \ + w1 = -w1; \ + w2 = -w2; \ + w1 s/= w2; \ + if w1 s<= 4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV32, zero divisor") +__success __retval(0) __log_level(2) +__msg("w1 s/= w2 {{.*}}; R1=0 R2=0") +__naked void sdiv32_zero_divisor(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + w1 = w0; \ + w1 &= 8; \ + w1 |= 1; \ + w2 = 0; \ + w1 s/= w2; \ + if w1 == 0 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV32, S32_MIN/-1") +__success __retval(0) __log_level(2) +__msg("w2 s/= -1 {{.*}}; R2=0x80000000") +__naked void sdiv32_overflow(void) +{ + asm volatile (" \ + w1 = %[int_min]; \ + w2 = w1; \ + w2 s/= -1; \ + if w1 == w2 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm_const(int_min, INT_MIN) + : __clobber_all); +} + + +SEC("socket") +__description("SDIV64, non-zero divisor") +__success __retval(0) __log_level(2) +__msg("r1 s/= r2 {{.*}}; R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))") +__naked void sdiv64_non_zero(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r2 = r0; \ + r1 &= 8; \ + r1 |= 1; \ + r2 &= 1; \ + r2 |= 2; \ + r1 s/= r2; \ + if r1 s<= 4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV64, non-zero divisor, negative dividend") +__success __retval(0) __log_level(2) +__msg("r1 s/= r2 {{.*}}; R1=scalar(smin=smin32=-4,smax=smax32=0)") +__naked void sdiv64_negative_dividend(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r2 = r0; \ + r1 &= 8; \ + r1 |= 1; \ + r1 = -r1; \ + r2 &= 1; \ + r2 |= 2; \ + r1 s/= r2; \ + if r1 s>= -4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV64, non-zero divisor, negative divisor") +__success __retval(0) __log_level(2) +__msg("r1 s/= r2 {{.*}}; R1=scalar(smin=smin32=-4,smax=smax32=0)") +__naked void sdiv64_negative_divisor(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r2 = r0; \ + r1 &= 8; \ + r1 |= 1; \ + r2 &= 1; \ + r2 |= 2; \ + r2 = -r2; \ + r1 s/= r2; \ + if r1 s>= -4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV64, non-zero divisor, both negative") +__success __retval(0) __log_level(2) +__msg("r1 s/= r2 {{.*}}; R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))") +__naked void sdiv64_both_negative(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r2 = r0; \ + r1 &= 8; \ + r1 |= 1; \ + r2 &= 1; \ + r2 |= 2; \ + r1 = -r1; \ + r2 = -r2; \ + r1 s/= r2; \ + if r1 s<= 4 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV64, zero divisor") +__success __retval(0) __log_level(2) +__msg("r1 s/= r2 {{.*}}; R1=0 R2=0") +__naked void sdiv64_zero_divisor(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r1 &= 8; \ + r1 |= 1; \ + r2 = 0; \ + r1 s/= r2; \ + if r1 == 0 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("SDIV64, S64_MIN/-1") +__success __retval(0) __log_level(2) +__msg("r2 s/= -1 {{.*}}; R2=0x8000000000000000") +__naked void sdiv64_overflow(void) +{ + asm volatile (" \ + r1 = %[llong_min] ll; \ + r2 = r1; \ + r2 s/= -1; \ + if r1 == r2 goto l0_%=; \ + r0 = *(u64 *)(r1 + 0); \ + exit; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm_const(llong_min, LLONG_MIN) + : __clobber_all); +} \ No newline at end of file -- 2.52.0