From: Jann Horn <[email protected]>
[ Upstream commit 604dca5e3af1db98bd123b7bfc02b017af99e3a0 ]
The BPF verifier tried to track values based on 32-bit comparisons by
(ab)using the tnum state via 581738a681b6 ("bpf: Provide better register
bounds after jmp32 instructions"). The idea is that after a check like
this:
if ((u32)r0 > 3)
exit
We can't meaningfully constrain the arithmetic-range-based tracking, but
we can update the tnum state to (value=0,mask=0xffff'ffff'0000'0003).
However, the implementation from 581738a681b6 didn't compute the tnum
constraint based on the fixed operand, but instead derives it from the
arithmetic-range-based tracking. This means that after the following
sequence of operations:
if (r0 >= 0x1'0000'0001)
exit
if ((u32)r0 > 7)
exit
The verifier assumed that the lower half of r0 is in the range (0, 0)
and apply the tnum constraint (value=0,mask=0xffff'ffff'0000'0000) thus
causing the overall tnum to be (value=0,mask=0x1'0000'0000), which was
incorrect. Provide a fixed implementation.
Fixes: 581738a681b6 ("bpf: Provide better register bounds after jmp32 instructions")
Signed-off-by: Jann Horn <[email protected]>
Signed-off-by: Daniel Borkmann <[email protected]>
Signed-off-by: Alexei Starovoitov <[email protected]>
Link: https://lore.kernel.org/bpf/[email protected]
Signed-off-by: Sasha Levin <[email protected]>
---
kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++--------------
1 file changed, 72 insertions(+), 36 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a0b76b360d6f7..013780ef0bd7d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5325,6 +5325,70 @@ static bool cmp_val_with_extended_s64(s64 sval, struct bpf_reg_state *reg)
reg->smax_value <= 0 && reg->smin_value >= S32_MIN);
}
+/* Constrain the possible values of @reg with unsigned upper bound @bound.
+ * If @is_exclusive, @bound is an exclusive limit, otherwise it is inclusive.
+ * If @is_jmp32, @bound is a 32-bit value that only constrains the low 32 bits
+ * of @reg.
+ */
+static void set_upper_bound(struct bpf_reg_state *reg, u64 bound, bool is_jmp32,
+ bool is_exclusive)
+{
+ if (is_exclusive) {
+ /* There are no values for `reg` that make `reg<0` true. */
+ if (bound == 0)
+ return;
+ bound--;
+ }
+ if (is_jmp32) {
+ /* Constrain the register's value in the tnum representation.
+ * For 64-bit comparisons this happens later in
+ * __reg_bound_offset(), but for 32-bit comparisons, we can be
+ * more precise than what can be derived from the updated
+ * numeric bounds.
+ */
+ struct tnum t = tnum_range(0, bound);
+
+ t.mask |= ~0xffffffffULL; /* upper half is unknown */
+ reg->var_off = tnum_intersect(reg->var_off, t);
+
+ /* Compute the 64-bit bound from the 32-bit bound. */
+ bound += gen_hi_max(reg->var_off);
+ }
+ reg->umax_value = min(reg->umax_value, bound);
+}
+
+/* Constrain the possible values of @reg with unsigned lower bound @bound.
+ * If @is_exclusive, @bound is an exclusive limit, otherwise it is inclusive.
+ * If @is_jmp32, @bound is a 32-bit value that only constrains the low 32 bits
+ * of @reg.
+ */
+static void set_lower_bound(struct bpf_reg_state *reg, u64 bound, bool is_jmp32,
+ bool is_exclusive)
+{
+ if (is_exclusive) {
+ /* There are no values for `reg` that make `reg>MAX` true. */
+ if (bound == (is_jmp32 ? U32_MAX : U64_MAX))
+ return;
+ bound++;
+ }
+ if (is_jmp32) {
+ /* Constrain the register's value in the tnum representation.
+ * For 64-bit comparisons this happens later in
+ * __reg_bound_offset(), but for 32-bit comparisons, we can be
+ * more precise than what can be derived from the updated
+ * numeric bounds.
+ */
+ struct tnum t = tnum_range(bound, U32_MAX);
+
+ t.mask |= ~0xffffffffULL; /* upper half is unknown */
+ reg->var_off = tnum_intersect(reg->var_off, t);
+
+ /* Compute the 64-bit bound from the 32-bit bound. */
+ bound += gen_hi_min(reg->var_off);
+ }
+ reg->umin_value = max(reg->umin_value, bound);
+}
+
/* Adjusts the register min/max values in the case that the dst_reg is the
* variable register that we are working on, and src_reg is a constant or we're
* simply doing a BPF_K check.
@@ -5380,15 +5444,8 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
case BPF_JGE:
case BPF_JGT:
{
- u64 false_umax = opcode == BPF_JGT ? val : val - 1;
- u64 true_umin = opcode == BPF_JGT ? val + 1 : val;
-
- if (is_jmp32) {
- false_umax += gen_hi_max(false_reg->var_off);
- true_umin += gen_hi_min(true_reg->var_off);
- }
- false_reg->umax_value = min(false_reg->umax_value, false_umax);
- true_reg->umin_value = max(true_reg->umin_value, true_umin);
+ set_upper_bound(false_reg, val, is_jmp32, opcode == BPF_JGE);
+ set_lower_bound(true_reg, val, is_jmp32, opcode == BPF_JGT);
break;
}
case BPF_JSGE:
@@ -5409,15 +5466,8 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
case BPF_JLE:
case BPF_JLT:
{
- u64 false_umin = opcode == BPF_JLT ? val : val + 1;
- u64 true_umax = opcode == BPF_JLT ? val - 1 : val;
-
- if (is_jmp32) {
- false_umin += gen_hi_min(false_reg->var_off);
- true_umax += gen_hi_max(true_reg->var_off);
- }
- false_reg->umin_value = max(false_reg->umin_value, false_umin);
- true_reg->umax_value = min(true_reg->umax_value, true_umax);
+ set_lower_bound(false_reg, val, is_jmp32, opcode == BPF_JLE);
+ set_upper_bound(true_reg, val, is_jmp32, opcode == BPF_JLT);
break;
}
case BPF_JSLE:
@@ -5492,15 +5542,8 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
case BPF_JGE:
case BPF_JGT:
{
- u64 false_umin = opcode == BPF_JGT ? val : val + 1;
- u64 true_umax = opcode == BPF_JGT ? val - 1 : val;
-
- if (is_jmp32) {
- false_umin += gen_hi_min(false_reg->var_off);
- true_umax += gen_hi_max(true_reg->var_off);
- }
- false_reg->umin_value = max(false_reg->umin_value, false_umin);
- true_reg->umax_value = min(true_reg->umax_value, true_umax);
+ set_lower_bound(false_reg, val, is_jmp32, opcode == BPF_JGE);
+ set_upper_bound(true_reg, val, is_jmp32, opcode == BPF_JGT);
break;
}
case BPF_JSGE:
@@ -5518,15 +5561,8 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
case BPF_JLE:
case BPF_JLT:
{
- u64 false_umax = opcode == BPF_JLT ? val : val - 1;
- u64 true_umin = opcode == BPF_JLT ? val + 1 : val;
-
- if (is_jmp32) {
- false_umax += gen_hi_max(false_reg->var_off);
- true_umin += gen_hi_min(true_reg->var_off);
- }
- false_reg->umax_value = min(false_reg->umax_value, false_umax);
- true_reg->umin_value = max(true_reg->umin_value, true_umin);
+ set_upper_bound(false_reg, val, is_jmp32, opcode == BPF_JLE);
+ set_lower_bound(true_reg, val, is_jmp32, opcode == BPF_JLT);
break;
}
case BPF_JSLE:
--
2.20.1
Hey Sasha, hey Greg,
On 4/7/20 12:21 PM, Greg Kroah-Hartman wrote:
> From: Jann Horn <[email protected]>
>
> [ Upstream commit 604dca5e3af1db98bd123b7bfc02b017af99e3a0 ]
>
> The BPF verifier tried to track values based on 32-bit comparisons by
> (ab)using the tnum state via 581738a681b6 ("bpf: Provide better register
> bounds after jmp32 instructions"). The idea is that after a check like
> this:
>
> if ((u32)r0 > 3)
> exit
>
> We can't meaningfully constrain the arithmetic-range-based tracking, but
> we can update the tnum state to (value=0,mask=0xffff'ffff'0000'0003).
> However, the implementation from 581738a681b6 didn't compute the tnum
> constraint based on the fixed operand, but instead derives it from the
> arithmetic-range-based tracking. This means that after the following
> sequence of operations:
>
> if (r0 >= 0x1'0000'0001)
> exit
> if ((u32)r0 > 7)
> exit
>
> The verifier assumed that the lower half of r0 is in the range (0, 0)
> and apply the tnum constraint (value=0,mask=0xffff'ffff'0000'0000) thus
> causing the overall tnum to be (value=0,mask=0x1'0000'0000), which was
> incorrect. Provide a fixed implementation.
>
> Fixes: 581738a681b6 ("bpf: Provide better register bounds after jmp32 instructions")
> Signed-off-by: Jann Horn <[email protected]>
> Signed-off-by: Daniel Borkmann <[email protected]>
> Signed-off-by: Alexei Starovoitov <[email protected]>
> Link: https://lore.kernel.org/bpf/[email protected]
> Signed-off-by: Sasha Levin <[email protected]>
We've already addressed this issue (CVE-2020-8835) on 5.4/5.5/5.6 kernels through
the following backports:
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.4.y&id=8d62a8c7489a68b5738390b008134a644aa9b383
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.5.y&id=0ebc01466d98d016eb6a3780ec8edb0c86fa48bc
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.6.y&id=6797143df51c8ae259aa4bfe4e99c832b20bde8a
Given the severity of the issue, we concluded that revert-only is the best and
most straight forward way to address it for stable.
Was this selected via Sasha's ML mechanism? Should there be a commit tag to opt-out
for some commits being selected? E.g. this one 581738a681b6 ("bpf: Provide better
register bounds after jmp32 instructions") already fell through our radar and wrongly
made its way into 5.4 where it should have never landed. :/
Thanks,
Daniel
On Tue, Apr 07, 2020 at 12:45:23PM +0200, Daniel Borkmann wrote:
> Hey Sasha, hey Greg,
>
> On 4/7/20 12:21 PM, Greg Kroah-Hartman wrote:
> > From: Jann Horn <[email protected]>
> >
> > [ Upstream commit 604dca5e3af1db98bd123b7bfc02b017af99e3a0 ]
> >
> > The BPF verifier tried to track values based on 32-bit comparisons by
> > (ab)using the tnum state via 581738a681b6 ("bpf: Provide better register
> > bounds after jmp32 instructions"). The idea is that after a check like
> > this:
> >
> > if ((u32)r0 > 3)
> > exit
> >
> > We can't meaningfully constrain the arithmetic-range-based tracking, but
> > we can update the tnum state to (value=0,mask=0xffff'ffff'0000'0003).
> > However, the implementation from 581738a681b6 didn't compute the tnum
> > constraint based on the fixed operand, but instead derives it from the
> > arithmetic-range-based tracking. This means that after the following
> > sequence of operations:
> >
> > if (r0 >= 0x1'0000'0001)
> > exit
> > if ((u32)r0 > 7)
> > exit
> >
> > The verifier assumed that the lower half of r0 is in the range (0, 0)
> > and apply the tnum constraint (value=0,mask=0xffff'ffff'0000'0000) thus
> > causing the overall tnum to be (value=0,mask=0x1'0000'0000), which was
> > incorrect. Provide a fixed implementation.
> >
> > Fixes: 581738a681b6 ("bpf: Provide better register bounds after jmp32 instructions")
> > Signed-off-by: Jann Horn <[email protected]>
> > Signed-off-by: Daniel Borkmann <[email protected]>
> > Signed-off-by: Alexei Starovoitov <[email protected]>
> > Link: https://lore.kernel.org/bpf/[email protected]
> > Signed-off-by: Sasha Levin <[email protected]>
>
> We've already addressed this issue (CVE-2020-8835) on 5.4/5.5/5.6 kernels through
> the following backports:
>
> https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.4.y&id=8d62a8c7489a68b5738390b008134a644aa9b383
> https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.5.y&id=0ebc01466d98d016eb6a3780ec8edb0c86fa48bc
> https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.6.y&id=6797143df51c8ae259aa4bfe4e99c832b20bde8a
>
> Given the severity of the issue, we concluded that revert-only is the best and
> most straight forward way to address it for stable.
>
> Was this selected via Sasha's ML mechanism? Should there be a commit tag to opt-out
> for some commits being selected? E.g. this one 581738a681b6 ("bpf: Provide better
> register bounds after jmp32 instructions") already fell through our radar and wrongly
> made its way into 5.4 where it should have never landed. :/
Oops, yeah, I think this came from Sasha's simple "Fixes:" script, and
wasn't aware that it was already resolved. I'll go drop these patches
now, thanks for catching this.
greg k-h