Problem
=======
Currently register equality tracking and propagation only works for full
64-bits (with additional constant offset). It is missing the
relationship: "these two regs share only their low 32-bits".
An illustrative snippet:
| r6 = ... /* full 64-bit unknown */
| w7 = w6 /* 32-bit zero-extend mov from wide src */
| if w6 != 0 goto .Lxx /* branch not taken, src narrowed */
| if w7 == 0 goto .Lok <-- missing
It works if the register is narrow to begin with, e.g.
| r6 = *(u32 *)(...)
Rephrased in verifier speak:
The linked-scalar equality relation sync_linked_regs() maintains is full
64-bit only; there is no subregister (low-32) equality link.
A 32-bit mov (w1 = w2) is therefore either promoted to a full-64-bit link
when the source is provably u32, or the link is dropped entirely when the
wider source has unknown high bits. A later narrowing of the source to its
low 32 bits never reaches dst, causing safe programs to be rejected. Note that
the ADD_CONST32 machinery only applies to += const offset, not to equality.
This was seen with bpf-gcc codegen that tends to reuse "w0 = idx" for
"return 0" on an idx==0 path, for bpf_loop callbacks.
Solution
========
- Introduce a low-32-only link, BPF_FLAG_SUBREG_ZEXT, added to BPF_FLAG_LINK.
- For a wide-source 32-bit mov, mark dst with BPF_FLAG_SUBREG_ZEXT instead
of clearing it (when src carries a scalar id).
- On a later low-32 narrowing sync_linked_regs() re-derives such a register as
the zero-extension of the base's low 32 bits: it copies the base (keeping its
precise low-32 tnum) and re-applies zext_32_to_64() -- the same helper the
32-bit mov used -- which is sound even when the source has unknown high bits.
This is applied only when neither side carries an ADD_CONST delta (the
combined subreg+delta case is not modeled).
- Sites that group a subreg-linked register by its scalar id compare ->id
directly: no masking is needed, since BPF_FLAG_SUBREG_ZEXT lives in
->flags.
The reconstruction copies the base wholesale, so it must put back the fields
that identify reg rather than known_reg -- ->id and, now, the link flag. This
mirrors what the ADD_CONST arm below already does ("Must preserve off and id,
otherwise another sync_linked_regs() will be incorrect"). Dropping the flag
while keeping the ->id would be worse than losing the link: the register would
claim a full 64-bit equality with a base whose high bits are unknown, and the
next sync driven by it would copy a narrowed low-32 value straight onto the
base's high half.
The link_flags_match() helper added by the previous patch is widened from
BPF_FLAG_ADD_CONST to BPF_FLAG_LINK, so regs_exact() -- and through it
states_maybe_looping() -- discriminates the new flavour as well. regsafe()
additionally checks it early, before the explore_alu_limits and !precise
short-circuits, which the helper's call site below them does not cover.
Note: the sync_linked_regs() reconstruction is wrapped in an extra block that
looks redundant here. It is a placeholder for the sign-extension counterpart
patch, which turns it into the else arm of an if/else on the link flavour;
keeping it now avoids re-indenting the whole body there.
Results
=======
Improves verifier tracking (seen in the next selftest).
selftest runs:
- clang: no new regressions (-mcpu=v3 and v4)
- bpf-gcc: no new regressions; the measurable selftest pass improvements
come with the sign-extension counterpart patch.
Signed-off-by: Vineet Gupta <[email protected]>
---
include/linux/bpf_verifier.h | 10 ++++
kernel/bpf/states.c | 23 ++++++++-
kernel/bpf/verifier.c | 91 ++++++++++++++++++++++++++++++++----
3 files changed, 114 insertions(+), 10 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 2b03fdba9acf..a4cba5c5099e 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -169,10 +169,20 @@ struct bpf_reg_state {
*
* BPF_FLAG_ADD_CONST{32,64}: this register is (base + ->delta) within
* its ->id set, computed with a 32- or 64-bit ALU add.
+ * BPF_FLAG_SUBREG_ZEXT: low-32-bit-only equality (as opposed to the
+ * full equality implied by a bare shared ->id): this register shares
+ * only the base's low 32 bits, and its high bits are zero (32-bit
+ * zero-extending mov).
+ * sync_linked_regs() propagates the low 32-bit subrange and rebuilds
+ * the high half accordingly, so this is sound even when the base has
+ * unknown high bits.
*/
#define BPF_FLAG_ADD_CONST32 (1U << 0)
#define BPF_FLAG_ADD_CONST64 (1U << 1)
#define BPF_FLAG_ADD_CONST (BPF_FLAG_ADD_CONST32 | BPF_FLAG_ADD_CONST64)
+#define BPF_FLAG_SUBREG_ZEXT (1U << 2)
+/* Every flag describing how this register relates to its ->id set. */
+#define BPF_FLAG_LINK (BPF_FLAG_ADD_CONST | BPF_FLAG_SUBREG_ZEXT)
#define BPF_FLAG_PRECISE (1U << 7)
u8 flags;
};
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index d3105b9a9965..ef71999c4695 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -490,6 +490,9 @@ static int clean_verifier_state(struct bpf_verifier_env
*env,
*
* Only meaningful when rold carries an id: the flags are only ever set
* together with one, so rold->id == 0 implies none of them is set.
+ *
+ * BPF_FLAG_LINK covers every flavour, so this widens automatically as new
+ * ones are added.
*/
static bool link_flags_match(const struct bpf_reg_state *rold,
const struct bpf_reg_state *rcur)
@@ -497,7 +500,7 @@ static bool link_flags_match(const struct bpf_reg_state
*rold,
if (!rold->id)
return true;
- return (rold->flags & BPF_FLAG_ADD_CONST) == (rcur->flags &
BPF_FLAG_ADD_CONST);
+ return (rold->flags & BPF_FLAG_LINK) == (rcur->flags & BPF_FLAG_LINK);
}
static bool regs_exact(const struct bpf_reg_state *rold,
@@ -554,6 +557,24 @@ static bool regsafe(struct bpf_verifier_env *env, struct
bpf_reg_state *rold,
switch (base_type(rold->type)) {
case SCALAR_VALUE:
+ /*
+ * A low-32-bit-only link has different sync_linked_regs()
+ * semantics than a full/ADD_CONST equality. check_scalar_ids()
+ * only ever sees the plain ->id and never looks at ->flags, so
a
+ * mismatch must be rejected explicitly.
+ * Check it here, before the explore_alu_limits and !precise
+ * short-circuits below (neither of which tests it). Note the
+ * pre-existing BPF_FLAG_ADD_CONST check sits after those
+ * short-circuits instead. The argument for checking early
+ * applies to it equally, but moving it makes regsafe() stricter
+ * on a path that predates this series, which is a pruning
change
+ * that wants measuring on its own; it is deliberately left
+ * alone here.
+ */
+ if (rold->id &&
+ (rold->flags & BPF_FLAG_SUBREG_ZEXT) != (rcur->flags &
BPF_FLAG_SUBREG_ZEXT))
+ return false;
+
if (env->explore_alu_limits) {
/* explore_alu_limits disables tnum_in() and
range_within()
* logic and requires everything to be strict
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 93e69116ca9e..8a802d49d0a4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1806,7 +1806,7 @@ static void __mark_reg_known(struct bpf_reg_state *reg,
u64 imm)
offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
reg->id = 0;
reg->parent_id = 0;
- reg->flags &= ~BPF_FLAG_ADD_CONST;
+ reg->flags &= ~BPF_FLAG_LINK;
___mark_reg_known(reg, imm);
}
@@ -3309,7 +3309,7 @@ static void clear_scalar_id(struct bpf_reg_state *reg)
{
reg->id = 0;
reg->delta = 0;
- reg->flags &= ~BPF_FLAG_ADD_CONST;
+ reg->flags &= ~BPF_FLAG_LINK;
}
static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
@@ -15076,15 +15076,42 @@ static int check_alu_op(struct bpf_verifier_env *env,
struct bpf_insn *insn)
if (insn->off == 0) {
bool is_src_reg_u32 =
get_reg_width(src_reg) <= 32;
- if (is_src_reg_u32)
+ /*
+ * *dst_reg = *src_reg below
copies src's id into dst, a
+ * full 64-bit equality link.
That is only sound when src
+ * fits in u32: a 32-bit mov
zero-extends dst, so for a
+ * wider src the link would let
sync_linked_regs()
+ * propagate dst's [0, U32_MAX]
range back onto src's
+ * unknown high bits. For a
wide src drop the full link
+ * and form a low-32-only
BPF_FLAG_SUBREG_ZEXT link instead, so a
+ * later narrowing of src's low
32 bits still reaches dst.
+ *
+ * wide_subreg_link gates that
low-32 link and excludes:
+ * - a self-mov (w6 = w6): src
== dst, nothing to link;
+ * forming one would only
mint an id and a spurious
+ * self-link (inert in
sync_linked_regs()).
+ * - an ADD_CONST-linked src
(rX = base + K):
+ *
assign_scalar_id_before_mov() would clear its
+ * base+delta link, and a
combined subreg+delta link
+ * isn't modeled anyway
(sync_linked_regs() skips it).
+ * In both cases src is left
untouched and dst is cleared,
+ * as before this feature.
+ */
+ bool wide_subreg_link =
!is_src_reg_u32 &&
+ src_reg != dst_reg &&
+ !(src_reg->flags &
BPF_FLAG_ADD_CONST);
+
+ if (is_src_reg_u32 ||
wide_subreg_link)
assign_scalar_id_before_mov(env, src_reg);
*dst_reg = *src_reg;
- /* Make sure ID is cleared if
src_reg is not in u32
- * range otherwise dst_reg
min/max could be incorrectly
- * propagated into src_reg by
sync_linked_regs()
- */
- if (!is_src_reg_u32)
-
clear_scalar_id(dst_reg);
+ if (!is_src_reg_u32) {
+ if (wide_subreg_link &&
src_reg->id) {
+ /* ->id already
copied above */
+ dst_reg->flags
|= BPF_FLAG_SUBREG_ZEXT;
+ } else {
+
clear_scalar_id(dst_reg);
+ }
+ }
} else {
/* case: W1 = (s8, s16)W2 */
bool no_sext =
reg_umax(src_reg) < (1ULL << (insn->off - 1));
@@ -15953,6 +15980,52 @@ static void sync_linked_regs(struct bpf_verifier_env
*env, struct bpf_verifier_s
continue;
if (reg->id != known_reg->id)
continue;
+ /*
+ * A low-32 linked register shares only the base's low 32 bits;
+ * the flag says how its high bits are derived. For
+ * BPF_FLAG_SUBREG_ZEXT they are zero (32-bit zero-extending
mov).
+ * Rebuild it from known_reg's low 32 bits accordingly, but only
+ * when neither side carries an ADD_CONST delta -- with a delta
+ * the low bits differ from the base by that delta and the
combined
+ * subreg+ADD_CONST reconstruction isn't modeled here, so leave
reg
+ * unchanged (sound, just less precise).
+ */
+ if (reg->flags & BPF_FLAG_SUBREG_ZEXT) {
+ if (!((reg->flags | known_reg->flags) &
BPF_FLAG_ADD_CONST)) {
+ {
+ u32 saved_id = reg->id;
+ u8 saved_subreg = reg->flags &
BPF_FLAG_SUBREG_ZEXT;
+
+ /*
+ * reg = zext32(known_reg): its low 32
bits come from
+ * the base and its high 32 are zero.
Rather than
+ * rebuild the value by hand, copy the
base (keeping
+ * its precise low-32 tnum) and
re-clear the high half
+ * with the same zext_32_to_64() the
32-bit
+ * zero-extending mov used -- the zero
high half is a
+ * fallout of it, so no dedicated
reconstruction is
+ * needed.
+ */
+ *reg = *known_reg;
+ reg->id = saved_id;
+ reg->flags = (reg->flags &
~BPF_FLAG_SUBREG_ZEXT) | saved_subreg;
+ zext_32_to_64(reg);
+ reg_bounds_sync(reg);
+ }
+ if (e->is_reg)
+ mark_reg_scratched(env, e->regno);
+ else
+ mark_stack_slot_scratched(env, e->spi);
+ }
+ continue;
+ }
+ /*
+ * Dest-driven direction (known_reg is subreg-linked, reg is
not):
+ * copying known_reg's low-32-only state into a full register
would
+ * be unsound, so leave reg unchanged.
+ */
+ if (known_reg->flags & BPF_FLAG_SUBREG_ZEXT)
+ continue;
/*
* Skip mixed 32/64-bit links: the delta relationship doesn't
* hold across different ALU widths.
--
2.53.0-Meta
