bpf: Fix abs(INT_MIN) undefined behavior in interpreter sdiv/smod
Subsystems (4)
v2 cover bpf: Fix abs(INT_MIN) undefined behavior in interpreter sdiv/smod
The BPF interpreter's signed 32-bit division and modulo handlers use abs() on s32 operands, which is undefined for S32_MIN. This causes the interpreter to compute wrong results, creating a mismatch with the verifier's range tracking.
For example, INT_MIN / 2 returns 0x40000000 instead of the correct 0xC0000000. The verifier tracks the correct range, so a crafted BPF program can exploit the mismatch for out-of-bounds map value access (confirmed by KASAN).
Patch 1 introduces __safe_abs32() which handles S32_MIN correctly and replaces all 8 abs((s32)...) call sites.
Patch 2 adds selftests covering sdiv32 and smod32 with INT_MIN dividend to prevent regression.
Changes since v1:
- Moved __safe_abs32() helper above the kerneldoc comment block for ___bpf_prog_run() to fix build warnings reported by kernel test robot (W=1 doc warnings)
Jenny Guanni Qu (2):
bpf: Fix undefined behavior in interpreter sdiv/smod for INT_MIN selftests/bpf: Add tests for sdiv32/smod32 with INT_MIN dividend
kernel/bpf/core.c | 23 ++++--- .../selftests/bpf/progs/verifier_sdiv.c | 58 +++++++++++++++++++ 2 files changed, 72 insertions(+), 9 deletions(-)
Signature · 1 line
2.34.1
PATCH v2 1/2 bpf: Fix undefined behavior in interpreter sdiv/smod for INT_MIN
The BPF interpreter's signed 32-bit division and modulo handlers use the kernel abs() macro on s32 operands. The abs() macro documentation (include/linux/math.h) explicitly states the result is undefined when the input is the type minimum. When DST contains S32_MIN (0x80000000), abs((s32)DST) triggers undefined behavior and returns S32_MIN unchanged on arm64/x86. This value is then sign-extended to u64 as 0xFFFFFFFF80000000, causing do_div() to compute the wrong result.
The verifier's abstract interpretation (scalar32_min_max_sdiv) computes the mathematically correct result for range tracking, creating a verifier/interpreter mismatch that can be exploited for out-of-bounds map value access.
Introduce __safe_abs32() which handles S32_MIN correctly and replace all 8 abs((s32)...) call sites in the interpreter's sdiv32/smod32 handlers.
--- kernel/bpf/core.c | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-)
kernel/bpf/core.c +14 -9
@@ -16,7 +16,6 @@* Andi Kleen - Fix a few bad bugs and races. * Kris Katterjohn - Added many additional checks in bpf_check_classic() */ -#include <uapi/linux/btf.h> #include <crypto/sha1.h> #include <linux/filter.h>
@@ -1736,6 +1735,12 @@ bool bpf_opcode_in_insntable(u8 code) }#ifndef CONFIG_BPF_JIT_ALWAYS_ON +/* Safe absolute value for s32 - abs() is undefined for S32_MIN */ +static inline u32 __safe_abs32 (s32 x) +{ +return x >=0 ? (u32 )x : x ==S32_MIN ? (u32 )S32_MIN : (u32)-x; +} +/** * ___bpf_prog_run - run eBPF program on a given context * @regs: is the array of MAX_BPF_EXT_REG eBPF pseudo-registers
@@ -1900,8 +1905,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST =do_div (AX , (u32 )SRC );break ;case 1 : -AX =abs ((s32 )DST ); -AX =do_div (AX ,abs ((s32 )SRC )); +AX =__safe_abs32 ((s32 )DST ); +AX =do_div (AX ,__safe_abs32 ((s32 )SRC ));if ((s32 )DST <0 )DST = (u32)-AX ;else
@@ -1928,8 +1933,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST =do_div (AX , (u32 )IMM );break ;case 1 : -AX =abs ((s32 )DST ); -AX =do_div (AX ,abs ((s32 )IMM )); +AX =__safe_abs32 ((s32 )DST ); +AX =do_div (AX ,__safe_abs32 ((s32 )IMM ));if ((s32 )DST <0 )DST = (u32)-AX ;else
@@ -1955,8 +1960,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST = (u32 )AX ;break ;case 1 : -AX =abs ((s32 )DST ); -do_div (AX ,abs ((s32 )SRC )); +AX =__safe_abs32 ((s32 )DST ); +do_div (AX ,__safe_abs32 ((s32 )SRC ));if (((s32 )DST <0 ) == ((s32 )SRC <0 ))DST = (u32 )AX ;else
@@ -1982,8 +1987,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST = (u32 )AX ;break ;case 1 : -AX =abs ((s32 )DST ); -do_div (AX ,abs ((s32 )IMM )); +AX =__safe_abs32 ((s32 )DST ); +do_div (AX ,__safe_abs32 ((s32 )IMM ));if (((s32 )DST <0 ) == ((s32 )IMM <0 ))DST = (u32 )AX ;else
Signature · 1 line
2.34.1
PATCH v2 2/2 selftests/bpf: Add tests for sdiv32/smod32 with INT_MIN dividend
In reply to Jenny Guanni QuAdd tests to verify that signed 32-bit division and modulo operations produce correct results when the dividend is INT_MIN (0x80000000).
These test the fix in the previous commit which replaced abs() with a safe helper to avoid undefined behavior for S32_MIN.
Test cases:
- SDIV32 INT_MIN / 2 = -1073741824 (imm and reg divisor)
- SMOD32 INT_MIN % 2 = 0 (positive and negative divisor)
--- .../selftests/bpf/progs/verifier_sdiv.c | 58 +++++++++++++++++++ 1 file changed, 58 insertions(+)
tools/testing/selftests/bpf/progs/verifier_sdiv.c +58 -0
@@ -1209,6 +1209,64 @@ __naked void smod32_ri_divisor_neg_1(void) : __clobber_all); } +SEC("socket") +__description("SDIV32, INT_MIN divided by 2, imm") +__success __success_unpriv __retval(-1073741824) +__naked void sdiv32_int_min_div_2_imm (void ) +{ + asmvolatile (" \ +w0 = %[int_min]; \ +w0 s/= 2; \ +exit; \ +" : + : __imm_const(int_min, INT_MIN) + : __clobber_all); +} + +SEC("socket") +__description("SDIV32, INT_MIN divided by 2, reg") +__success __success_unpriv __retval(-1073741824) +__naked void sdiv32_int_min_div_2_reg (void ) +{ + asmvolatile (" \ +w0 = %[int_min]; \ +w1 = 2; \ +w0 s/= w1; \ +exit; \ +" : + : __imm_const(int_min, INT_MIN) + : __clobber_all); +} + +SEC("socket") +__description("SMOD32, INT_MIN modulo 2, imm") +__success __success_unpriv __retval(0) +__naked void smod32_int_min_mod_2_imm(void) +{ + asmvolatile (" \ +w0 = %[int_min]; \ +w0 s%%= 2; \ +exit; \ +" : + : __imm_const(int_min, INT_MIN) + : __clobber_all); +} + +SEC("socket") +__description("SMOD32, INT_MIN modulo -2, imm") +__success __success_unpriv __retval(0) +__naked void smod32_int_min_mod_neg2_imm(void) +{ + asmvolatile (" \ +w0 = %[int_min]; \ +w0 s%%= -2; \ +exit; \ +" : + : __imm_const(int_min, INT_MIN) + : __clobber_all); +} + +#else SEC ("socket" )
Signature · 1 line
2.34.1
Re: [PATCH v2 1/2] bpf: Fix undefined behavior in interpreter sdiv/smod for INT_MIN
In reply to Jenny Guanni QuQuoted 36 lines · Jenny Guanni Qu
The BPF interpreter's signed 32-bit division and modulo handlers use the kernel
abs()macro on s32 operands. Theabs()macro documentation (include/linux/math.h) explicitly states the result is undefined when the input is the type minimum. When DST containsS32_MIN(0x80000000), abs((s32)DST) triggers undefined behavior and returnsS32_MINunchanged on arm64/x86. This value is then sign-extended to u64 as0xFFFFFFFF80000000, causingdo_div()to compute the wrong result.The verifier's abstract interpretation (
scalar32_min_max_sdiv) computes the mathematically correct result for range tracking, creating a verifier/interpreter mismatch that can be exploited for out-of-bounds map value access.Introduce
__safe_abs32()which handlesS32_MINcorrectly and replace all 8 abs((s32)...) call sites in the interpreter's sdiv32/smod32 handlers.Fixes ec0e2da95f72 ("bpf: Support new signed div/mod instructions.")Signed-off-by Jenny Guanni Qu <[email protected]>--- kernel/bpf/core.c | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-)kernel/bpf/core.c +0
-1@@ -16,7 +16,6 @@* Andi Kleen - Fix a few bad bugs and races. * Kris Katterjohn - Added many additional checks in bpf_check_classic() */ -#include <uapi/linux/btf.h> #include <crypto/sha1.h> #include <linux/filter.h>
kernel/bpf/core.c bool bpf_opcode_in_insntable(u8 code) · line 1741
Quoted 7 lines
kernel/bpf/core.c +4
-0@@ -1736,6 +1735,12 @@ bool bpf_opcode_in_insntable(u8 code) }#ifndef CONFIG_BPF_JIT_ALWAYS_ON +/* Safe absolute value for s32 - abs() is undefined for S32_MIN */ +static inline u32 __safe_abs32 (s32 x) +{ +return x >=0 ? (u32 )x : x ==S32_MIN ? (u32 )S32_MIN : (u32)-x;
can we write it as x >= 0 ? (u32)x : -(u32)x; ?
By casting to u32 first, the negation operates in unsigned arithmetic where overflow does not happen — it wraps.
Please correct me if I'm wrong.
Quoted 51 lines
kernel/bpf/core.c +10
-8+} +/** * ___bpf_prog_run - run eBPF program on a given context * @regs: is the array of MAX_BPF_EXT_REG eBPF pseudo-registers @@ -1900,8 +1905,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST =do_div (AX , (u32 )SRC );break ;case 1 : -AX =abs ((s32 )DST ); -AX =do_div (AX ,abs ((s32 )SRC )); +AX =__safe_abs32 ((s32 )DST ); +AX =do_div (AX ,__safe_abs32 ((s32 )SRC ));if ((s32 )DST <0 )DST = (u32)-AX ;else @@ -1928,8 +1933,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST =do_div (AX , (u32 )IMM );break ;case 1 : -AX =abs ((s32 )DST ); -AX =do_div (AX ,abs ((s32 )IMM )); +AX =__safe_abs32 ((s32 )DST ); +AX =do_div (AX ,__safe_abs32 ((s32 )IMM ));if ((s32 )DST <0 )DST = (u32)-AX ;else @@ -1955,8 +1960,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST = (u32 )AX ;break ;case 1 : -AX =abs ((s32 )DST ); -do_div (AX ,abs ((s32 )SRC )); +AX =__safe_abs32 ((s32 )DST ); +do_div (AX ,__safe_abs32 ((s32 )SRC ));if (((s32 )DST <0 ) == ((s32 )SRC <0 ))DST = (u32 )AX ;else @@ -1982,8 +1987,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST = (u32 )AX ;break ;case 1 : -AX =abs ((s32 )DST ); -do_div (AX ,abs ((s32 )IMM )); +AX =__safe_abs32 ((s32 )DST ); +do_div (AX ,__safe_abs32 ((s32 )IMM ));if (((s32 )DST <0 ) == ((s32 )IMM <0 ))DST = (u32 )AX ;else Signature · 1 line
2.34.1
Re: [PATCH v2 1/2] bpf: Fix undefined behavior in interpreter sdiv/smod for INT_MIN
You're right, casting to u32 before negating avoids the UB entirely without needing a special case for S32_MIN. Will send v3 with that simplification. Thanks!
Quoted 101 lines · Mykyta Yatsenko
Quoted 36 lines · Jenny Guanni Qu
The BPF interpreter's signed 32-bit division and modulo handlers use the kernel
abs()macro on s32 operands. Theabs()macro documentation (include/linux/math.h) explicitly states the result is undefined when the input is the type minimum. When DST containsS32_MIN(0x80000000), abs((s32)DST) triggers undefined behavior and returnsS32_MINunchanged on arm64/x86. This value is then sign-extended to u64 as0xFFFFFFFF80000000, causingdo_div()to compute the wrong result.The verifier's abstract interpretation (
scalar32_min_max_sdiv) computes the mathematically correct result for range tracking, creating a verifier/interpreter mismatch that can be exploited for out-of-bounds map value access.Introduce
__safe_abs32()which handlesS32_MINcorrectly and replace all 8 abs((s32)...) call sites in the interpreter's sdiv32/smod32 handlers.Fixes ec0e2da95f72 ("bpf: Support new signed div/mod instructions.")Signed-off-by Jenny Guanni Qu <[email protected]>--- kernel/bpf/core.c | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-)kernel/bpf/core.c +0
-1@@ -16,7 +16,6 @@* Andi Kleen - Fix a few bad bugs and races. * Kris Katterjohn - Added many additional checks in bpf_check_classic() */ -#include <uapi/linux/btf.h> #include <crypto/sha1.h> #include <linux/filter.h> kernel/bpf/core.c bool bpf_opcode_in_insntable(u8 code) · line 1741
Quoted 7 lines
kernel/bpf/core.c +4
-0@@ -1736,6 +1735,12 @@ bool bpf_opcode_in_insntable(u8 code) }#ifndef CONFIG_BPF_JIT_ALWAYS_ON +/* Safe absolute value for s32 - abs() is undefined for S32_MIN */ +static inline u32 __safe_abs32 (s32 x) +{ +return x >=0 ? (u32 )x : x ==S32_MIN ? (u32 )S32_MIN : (u32)-x;can we write it as x >= 0 ? (u32)x : -(u32)x; ?
By casting to u32 first, the negation operates in unsigned arithmetic where overflow does not happen — it wraps.
Please correct me if I'm wrong.Quoted 51 lines
kernel/bpf/core.c +10
-9+} +/** * ___bpf_prog_run - run eBPF program on a given context * @regs: is the array of MAX_BPF_EXT_REG eBPF pseudo-registers @@ -1900,8 +1905,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST =do_div (AX , (u32 )SRC );break ;case 1 : -AX =abs ((s32 )DST ); -AX =do_div (AX ,abs ((s32 )SRC )); +AX =__safe_abs32 ((s32 )DST ); +AX =do_div (AX ,__safe_abs32 ((s32 )SRC ));if ((s32 )DST <0 )DST = (u32)-AX ;else @@ -1928,8 +1933,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST =do_div (AX , (u32 )IMM );break ;case 1 : -AX =abs ((s32 )DST ); -AX =do_div (AX ,abs ((s32 )IMM )); +AX =__safe_abs32 ((s32 )DST ); +AX =do_div (AX ,__safe_abs32 ((s32 )IMM ));if ((s32 )DST <0 )DST = (u32)-AX ;else @@ -1955,8 +1960,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST = (u32 )AX ;break ;case 1 : -AX =abs ((s32 )DST ); -do_div (AX ,abs ((s32 )SRC )); +AX =__safe_abs32 ((s32 )DST ); +do_div (AX ,__safe_abs32 ((s32 )SRC ));if (((s32 )DST <0 ) == ((s32 )SRC <0 ))DST = (u32 )AX ;else @@ -1982,8 +1987,8 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)DST = (u32 )AX ;break ;case 1 : -AX =abs ((s32 )DST ); -do_div (AX ,abs ((s32 )IMM )); +AX =__safe_abs32 ((s32 )DST ); +do_div (AX ,__safe_abs32 ((s32 )IMM ));if (((s32 )DST <0 ) == ((s32 )IMM <0 ))DST = (u32 )AX ;else --2.34.1