[bpf,12/12] selftests/bpf: check if max number of bpf_loop iterations is tracked

Commit Message

Eduard Zingerman Nov. 16, 2023, 2:18 a.m. UTC

Check that even if bpf_loop() callback simulation does not converge to
a specific state, verification could proceed via "brute force"
simulation of maximal number of callback calls.

Signed-off-by: Eduard Zingerman <[e-mail]>
---
 .../bpf/progs/verifier_iterating_callbacks.c  | 67 +++++++++++++++++++
 1 file changed, 67 insertions(+)

Comments

Andrii Nakryiko Nov. 17, 2023, 4:47 p.m. UTC | #1

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <[e-mail]> wrote:
>
> Check that even if bpf_loop() callback simulation does not converge to
> a specific state, verification could proceed via "brute force"
> simulation of maximal number of callback calls.
>
> Signed-off-by: Eduard Zingerman <[e-mail]>
> ---
>  .../bpf/progs/verifier_iterating_callbacks.c  | 67 +++++++++++++++++++
>  1 file changed, 67 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> index 598c1e984b26..da10ce57da5e 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> @@ -164,4 +164,71 @@ int unsafe_find_vma(void *unused)
>         return choice_arr[loop_ctx.i];
>  }
>
> +static int iter_limit_cb(__u32 idx, struct num_context *ctx)
> +{
> +       ctx->i++;
> +       return 0;
> +}
> +
> +SEC("?raw_tp")
> +__success
> +int bpf_loop_iter_limit_ok(void *unused)
> +{
> +       struct num_context ctx = { .i = 0 };
> +
> +       bpf_loop(1, iter_limit_cb, &ctx, 0);
> +       return choice_arr[ctx.i];
> +}
> +
> +SEC("?raw_tp")
> +__failure __msg("invalid access to map value, value_size=2 off=2 size=1")
> +int bpf_loop_iter_limit_overflow(void *unused)
> +{
> +       struct num_context ctx = { .i = 0 };
> +
> +       bpf_loop(2, iter_limit_cb, &ctx, 0);
> +       return choice_arr[ctx.i];
> +}
> +
> +static int iter_limit_level2a_cb(__u32 idx, struct num_context *ctx)
> +{
> +       ctx->i += 100;
> +       return 0;
> +}
> +
> +static int iter_limit_level2b_cb(__u32 idx, struct num_context *ctx)
> +{
> +       ctx->i += 10;
> +       return 0;
> +}
> +
> +static int iter_limit_level1_cb(__u32 idx, struct num_context *ctx)
> +{
> +       ctx->i += 1;
> +       bpf_loop(1, iter_limit_level2a_cb, ctx, 0);
> +       bpf_loop(1, iter_limit_level2b_cb, ctx, 0);
> +       return 0;
> +}
> +
> +SEC("?raw_tp")
> +__success __log_level(2)
> +/* Check that last verified exit from the program visited each
> + * callback expected number of times: one visit per callback for each
> + * top level bpf_loop call.
> + */
> +__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
> +/* Ensure that read above is the last one by checking that there are
> + * no more reads for ctx.i.
> + */
> +__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")

can't you enforce that we don't go above 111111 just by making sure to
use r1 - 111111 + 1 as an index into choice_arr()?

We can then simplify the patch set by dropping __not_msg() parts (and
can add them separately).


> +int bpf_loop_iter_limit_nested(void *unused)
> +{
> +       struct num_context ctx = { .i = 0 };
> +
> +       bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
> +       ctx.i *= 1000;
> +       bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
> +       return choice_arr[ctx.i % 2];
> +}
> +
>  char _license[] SEC("license") = "GPL";
> --
> 2.42.0
>

Eduard Zingerman Nov. 17, 2023, 6:53 p.m. UTC | #2

On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
[...]
> > +SEC("?raw_tp")
> > +__success __log_level(2)
> > +/* Check that last verified exit from the program visited each
> > + * callback expected number of times: one visit per callback for each
> > + * top level bpf_loop call.
> > + */
> > +__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
> > +/* Ensure that read above is the last one by checking that there are
> > + * no more reads for ctx.i.
> > + */
> > +__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")
> 
> can't you enforce that we don't go above 111111 just by making sure to
> use r1 - 111111 + 1 as an index into choice_arr()?
> 
> We can then simplify the patch set by dropping __not_msg() parts (and
> can add them separately).

Well, r1 could be 0 as well, so idx would be out of bounds.
But I like the idea, it is possible to check that r1 is either 00000,
100000, ..., 111111 and do something unsafe otherwise.
Thank you. I'll drop __not_msg() then.

Andrii Nakryiko Nov. 17, 2023, 8:32 p.m. UTC | #3

On Fri, Nov 17, 2023 at 1:53 PM Eduard Zingerman <[e-mail]> wrote:
>
> On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
> [...]
> > > +SEC("?raw_tp")
> > > +__success __log_level(2)
> > > +/* Check that last verified exit from the program visited each
> > > + * callback expected number of times: one visit per callback for each
> > > + * top level bpf_loop call.
> > > + */
> > > +__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
> > > +/* Ensure that read above is the last one by checking that there are
> > > + * no more reads for ctx.i.
> > > + */
> > > +__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")
> >
> > can't you enforce that we don't go above 111111 just by making sure to
> > use r1 - 111111 + 1 as an index into choice_arr()?
> >
> > We can then simplify the patch set by dropping __not_msg() parts (and
> > can add them separately).
>
> Well, r1 could be 0 as well, so idx would be out of bounds.
> But I like the idea, it is possible to check that r1 is either 00000,
> 100000, ..., 111111 and do something unsafe otherwise.

then why not `return choice_arr[r <= 111111 ? (r & 1) : -1];` or
something along those lines?

> Thank you. I'll drop __not_msg() then.

yep, thanks

>
>

Eduard Zingerman Nov. 17, 2023, 9:18 p.m. UTC | #4

On Fri, 2023-11-17 at 15:32 -0500, Andrii Nakryiko wrote:
[...]
> > Well, r1 could be 0 as well, so idx would be out of bounds.
> > But I like the idea, it is possible to check that r1 is either 00000,
> > 100000, ..., 111111 and do something unsafe otherwise.
> 
> then why not `return choice_arr[r <= 111111 ? (r & 1) : -1];` or
> something along those lines?

In theory, invalid value might be 100002 or something similar.
I'll try writing down something more precise, if that would look too
ugly would resort to the comparison that you suggest.

Patch

diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index 598c1e984b26..da10ce57da5e 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -164,4 +164,71 @@  int unsafe_find_vma(void *unused)
 	return choice_arr[loop_ctx.i];
 }
 
+static int iter_limit_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i++;
+	return 0;
+}
+
+SEC("?raw_tp")
+__success
+int bpf_loop_iter_limit_ok(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(1, iter_limit_cb, &ctx, 0);
+	return choice_arr[ctx.i];
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=2 size=1")
+int bpf_loop_iter_limit_overflow(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(2, iter_limit_cb, &ctx, 0);
+	return choice_arr[ctx.i];
+}
+
+static int iter_limit_level2a_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 100;
+	return 0;
+}
+
+static int iter_limit_level2b_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 10;
+	return 0;
+}
+
+static int iter_limit_level1_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 1;
+	bpf_loop(1, iter_limit_level2a_cb, ctx, 0);
+	bpf_loop(1, iter_limit_level2b_cb, ctx, 0);
+	return 0;
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+/* Check that last verified exit from the program visited each
+ * callback expected number of times: one visit per callback for each
+ * top level bpf_loop call.
+ */
+__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
+/* Ensure that read above is the last one by checking that there are
+ * no more reads for ctx.i.
+ */
+__not_msg("r1 = *(u64 *)(r10 -16)	; R1_w=")
+int bpf_loop_iter_limit_nested(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
+	ctx.i *= 1000;
+	bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
+	return choice_arr[ctx.i % 2];
+}
+
 char _license[] SEC("license") = "GPL";