From: Xu Kuohai <xukuohai@xxxxxxxxxx>
dst_reg is marked as unknown when BPF_MOD instruction is verified, causing
the following bpf prog to be incorrectly rejected.
0: r0 = 0
1: r0 %= 10 // r0 is marked as unknown
2: r1 = 0
3: r1 += 1
4: if r1 < r0 goto pc-2 // verifier concludes the loop is unbounded
5: exit
To teach verifier to accept the above prog, this patch adds bound tracking
for BPF_MOD, based on the following observation.
BPF_MOD is unsigned and for a given unsigned divisor x:
1. when x != 0, dst_reg bits are in the range [0, x);
2. when x == 0, dst_reg is truncated to 32 bits by mod32 or remains
unchanged by mod64.
Signed-off-by: Xu Kuohai <xukuohai@xxxxxxxxxx>
---
kernel/bpf/verifier.c | 98 ++++++++++++++++++++++++++++++++++++++++---
1 file changed, 93 insertions(+), 5 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 272563a0b770..d44a33a53e8e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -11257,6 +11257,87 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
__update_reg_bounds(dst_reg);
}
+static void scalar32_min_max_mod(struct bpf_reg_state *dst_reg,
+ struct bpf_reg_state *src_reg)
+{
+ u32 val = (u32)src_reg->var_off.value; /* src_reg is const */
+ u32 umax = dst_reg->u32_max_value;
+ u32 umin = dst_reg->u32_min_value;
+ u32 umax_rem, umin_rem;
+
+ /* dst_reg is 32-bit truncated when mod32 zero, since
+ * adjust_scalar_min_max_vals calls zext_32_to_64 to do truncation for
+ * all alu32 ops, here we do nothing and just return.
+ */
+ if (!val)
+ return;
+
+ umax_rem = do_div(umax, val);
+ umin_rem = do_div(umin, val);
+
+ /* no winding */
+ if (umax - umin < val && umin_rem <= umax_rem) {
+ dst_reg->var_off = tnum_range(umin_rem, umax_rem);
+ dst_reg->u32_min_value = umin_rem;
+ dst_reg->u32_max_value = umax_rem;
+ } else {
+ dst_reg->var_off = tnum_range(0, val - 1);
+ dst_reg->u32_min_value = 0;
+ dst_reg->u32_max_value = val - 1;
+ }
+
+ /* cross the sign boundary */
+ if ((s32)dst_reg->u32_min_value > (s32)dst_reg->u32_max_value) {
+ dst_reg->s32_min_value = S32_MIN;
+ dst_reg->s32_max_value = S32_MAX;
+ } else {
+ dst_reg->s32_min_value = (s32)dst_reg->u32_min_value;
+ dst_reg->s32_max_value = (s32)dst_reg->u32_max_value;
+ }
+
+ /* mark reg64 unbounded to deduce 64-bit bounds from var_off */
+ __mark_reg64_unbounded(dst_reg);
+}
+
+static void scalar_min_max_mod(struct bpf_reg_state *dst_reg,
+ struct bpf_reg_state *src_reg)
+{
+ u64 val = src_reg->var_off.value; /* src_reg is const */
+ u64 umax = dst_reg->umax_value;
+ u64 umin = dst_reg->umin_value;
+ u64 umax_rem, umin_rem;
+
+ /* dst_reg is untouched when mod64 zero */
+ if (!val)
+ return;
+
+ div64_u64_rem(umin, val, &umin_rem);
+ div64_u64_rem(umax, val, &umax_rem);
+
+ /* no winding */
+ if (umax - umin < val && umin_rem <= umax_rem) {
+ dst_reg->var_off = tnum_range(umin_rem, umax_rem);
+ dst_reg->umin_value = umin_rem;
+ dst_reg->umax_value = umax_rem;
+ } else {
+ dst_reg->var_off = tnum_range(0, val - 1);
+ dst_reg->umin_value = 0;
+ dst_reg->umax_value = val - 1;
+ }
+
+ /* cross the sign boundary */
+ if ((s64)dst_reg->umin_value > (s64)dst_reg->umax_value) {
+ dst_reg->smin_value = S64_MIN;
+ dst_reg->smax_value = S64_MAX;
+ } else {
+ dst_reg->smin_value = (s64)dst_reg->umin_value;
+ dst_reg->smax_value = (s64)dst_reg->umax_value;
+ }
+
+ /* mark reg32 unbounded to deduce 32-bit bounds from var_off */
+ __mark_reg32_unbounded(dst_reg);
+}
+
/* WARNING: This function does calculations on 64-bit values, but the actual
* execution may occur on 32-bit values. Therefore, things like bitshifts
* need extra checks in the 32-bit case.
@@ -11331,11 +11412,12 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
* and BPF_OR. This is possible because these ops have fairly easy to
* understand and calculate behavior in both 32-bit and 64-bit alu ops.
* See alu32 verifier tests for examples. The second class of
- * operations, BPF_LSH, BPF_RSH, and BPF_ARSH, however are not so easy
- * with regards to tracking sign/unsigned bounds because the bits may
- * cross subreg boundaries in the alu64 case. When this happens we mark
- * the reg unbounded in the subreg bound space and use the resulting
- * tnum to calculate an approximation of the sign/unsigned bounds.
+ * operations, BPF_LSH, BPF_RSH, BPF_ARSH and BPF_MOD, however are not
+ * so easy with regards to tracking sign/unsigned bounds because the
+ * bits may cross subreg boundaries in the alu64 case. When this happens
+ * we mark the reg unbounded in the subreg bound space and use the
+ * resulting tnum to calculate an approximation of the sign/unsigned
+ * bounds.
*/
switch (opcode) {
case BPF_ADD:
@@ -11407,6 +11489,12 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
else
scalar_min_max_arsh(dst_reg, &src_reg);
break;
+ case BPF_MOD:
+ if (alu32)
+ scalar32_min_max_mod(dst_reg, &src_reg);
+ else
+ scalar_min_max_mod(dst_reg, &src_reg);
+ break;
default:
mark_reg_unknown(env, regs, insn->dst_reg);
break;
--
2.30.2
