[bpf,1/4] bpf: fix kfunc btf caching for modules

Commit Message

Toke Høiland-Jørgensen Oct. 8, 2024, 10:35 a.m. UTC

The verifier contains a cache for looking up module BTF objects when
calling kfuncs defined in modules. This cache uses a 'struct
bpf_kfunc_btf_tab', which contains a sorted list of BTF objects that
were already seen in the current verifier run, and the BTF objects are
looked up by the offset stored in the relocated call instruction using
bsearch().

The first time a given offset is seen, the module BTF is loaded from the
file descriptor passed in by libbpf, and stored into the cache. However,
there's a bug in the code storing the new entry: it stores a pointer to
the new cache entry, then calls sort() to keep the cache sorted for the
next lookup using bsearch(), and then returns the entry that was just
stored through the stored pointer. However, because sort() modifies the
list of entries in place *by value*, the stored pointer may no longer
point to the right entry, in which case the wrong BTF object will be
returned.

The end result of this is an intermittent bug where, if a BPF program
calls two functions with the same signature in two different modules,
the function from the wrong module may sometimes end up being called.
Whether this happens depends on the order of the calls in the BPF
program (as that affects whether sort() reorders the array of BTF
objects), making it especially hard to track down. Simon, credited as
reporter below, spent significant effort analysing and creating a
reproducer for this issue. The reproducer is added as a selftest in a
subsequent patch.

The fix is straight forward: simply don't use the stored pointer after
calling sort(). Since we already have an on-stack pointer to the BTF
object itself at the point where the function return, just use that, and
populate it from the cache entry in the branch where the lookup
succeeds.

Fixes: 2357672c54c3 ("bpf: Introduce BPF support for kernel module function calls")
Reported-by: Simon Sundberg <[e-mail]>
Signed-off-by: Toke Høiland-Jørgensen <[e-mail]>
---
 kernel/bpf/verifier.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

Comments

Jiri Olsa Oct. 8, 2024, 5:46 p.m. UTC | #1

On Tue, Oct 08, 2024 at 12:35:16PM +0200, Toke Høiland-Jørgensen wrote:
> The verifier contains a cache for looking up module BTF objects when
> calling kfuncs defined in modules. This cache uses a 'struct
> bpf_kfunc_btf_tab', which contains a sorted list of BTF objects that
> were already seen in the current verifier run, and the BTF objects are
> looked up by the offset stored in the relocated call instruction using
> bsearch().
> 
> The first time a given offset is seen, the module BTF is loaded from the
> file descriptor passed in by libbpf, and stored into the cache. However,
> there's a bug in the code storing the new entry: it stores a pointer to
> the new cache entry, then calls sort() to keep the cache sorted for the
> next lookup using bsearch(), and then returns the entry that was just
> stored through the stored pointer. However, because sort() modifies the
> list of entries in place *by value*, the stored pointer may no longer
> point to the right entry, in which case the wrong BTF object will be
> returned.
> 
> The end result of this is an intermittent bug where, if a BPF program
> calls two functions with the same signature in two different modules,
> the function from the wrong module may sometimes end up being called.
> Whether this happens depends on the order of the calls in the BPF
> program (as that affects whether sort() reorders the array of BTF
> objects), making it especially hard to track down. Simon, credited as
> reporter below, spent significant effort analysing and creating a
> reproducer for this issue. The reproducer is added as a selftest in a
> subsequent patch.
> 
> The fix is straight forward: simply don't use the stored pointer after
> calling sort(). Since we already have an on-stack pointer to the BTF
> object itself at the point where the function return, just use that, and
> populate it from the cache entry in the branch where the lookup
> succeeds.
> 
> Fixes: 2357672c54c3 ("bpf: Introduce BPF support for kernel module function calls")
> Reported-by: Simon Sundberg <[e-mail]>
> Signed-off-by: Toke Høiland-Jørgensen <[e-mail]>

nice catch

Acked-by: Jiri Olsa <[e-mail]>

jirka

> ---
>  kernel/bpf/verifier.c | 8 +++++++-
>  1 file changed, 7 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 434de48cd24bd8d9fb008e4a1e9e0ab4d75ef90a..98d866ba90bf92e3666fb9a07b36f48d452779c6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2750,10 +2750,16 @@ static struct btf *__find_kfunc_desc_btf(struct bpf_verifier_env *env,
>  		b->module = mod;
>  		b->offset = offset;
>  
> +		/* sort() reorders entries by value, so b may no longer point
> +		 * to the right entry after this
> +		 */
>  		sort(tab->descs, tab->nr_descs, sizeof(tab->descs[0]),
>  		     kfunc_btf_cmp_by_off, NULL);
> +	} else {
> +		btf = b->btf;
>  	}
> -	return b->btf;
> +
> +	return btf;
>  }
>  
>  void bpf_free_kfunc_btf_tab(struct bpf_kfunc_btf_tab *tab)
> 
> -- 
> 2.47.0
>

Kumar Kartikeya Dwivedi Oct. 9, 2024, 1:43 a.m. UTC | #2

On Tue, 8 Oct 2024 at 12:35, Toke Høiland-Jørgensen <[e-mail]> wrote:
>
> The verifier contains a cache for looking up module BTF objects when
> calling kfuncs defined in modules. This cache uses a 'struct
> bpf_kfunc_btf_tab', which contains a sorted list of BTF objects that
> were already seen in the current verifier run, and the BTF objects are
> looked up by the offset stored in the relocated call instruction using
> bsearch().
>
> The first time a given offset is seen, the module BTF is loaded from the
> file descriptor passed in by libbpf, and stored into the cache. However,
> there's a bug in the code storing the new entry: it stores a pointer to
> the new cache entry, then calls sort() to keep the cache sorted for the
> next lookup using bsearch(), and then returns the entry that was just
> stored through the stored pointer. However, because sort() modifies the
> list of entries in place *by value*, the stored pointer may no longer
> point to the right entry, in which case the wrong BTF object will be
> returned.
>
> The end result of this is an intermittent bug where, if a BPF program
> calls two functions with the same signature in two different modules,
> the function from the wrong module may sometimes end up being called.
> Whether this happens depends on the order of the calls in the BPF
> program (as that affects whether sort() reorders the array of BTF
> objects), making it especially hard to track down. Simon, credited as
> reporter below, spent significant effort analysing and creating a
> reproducer for this issue. The reproducer is added as a selftest in a
> subsequent patch.
>
> The fix is straight forward: simply don't use the stored pointer after
> calling sort(). Since we already have an on-stack pointer to the BTF
> object itself at the point where the function return, just use that, and
> populate it from the cache entry in the branch where the lookup
> succeeds.
>
> Fixes: 2357672c54c3 ("bpf: Introduce BPF support for kernel module function calls")
> Reported-by: Simon Sundberg <[e-mail]>
> Signed-off-by: Toke Høiland-Jørgensen <[e-mail]>
> ---

Acked-by: Kumar Kartikeya Dwivedi <[e-mail]>

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 434de48cd24bd8d9fb008e4a1e9e0ab4d75ef90a..98d866ba90bf92e3666fb9a07b36f48d452779c6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2750,10 +2750,16 @@  static struct btf *__find_kfunc_desc_btf(struct bpf_verifier_env *env,
 		b->module = mod;
 		b->offset = offset;
 
+		/* sort() reorders entries by value, so b may no longer point
+		 * to the right entry after this
+		 */
 		sort(tab->descs, tab->nr_descs, sizeof(tab->descs[0]),
 		     kfunc_btf_cmp_by_off, NULL);
+	} else {
+		btf = b->btf;
 	}
-	return b->btf;
+
+	return btf;
 }
 
 void bpf_free_kfunc_btf_tab(struct bpf_kfunc_btf_tab *tab)