| Message ID | 20220513190821.431762-1-tadeusz.struk@linaro.org (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | [v3] bpf: Fix KASAN use-after-free Read in compute_effective_progs | expand |
On Fri, May 13, 2022 at 12:08 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote: > > Syzbot found a Use After Free bug in compute_effective_progs(). > The reproducer creates a number of BPF links, and causes a fault > injected alloc to fail, while calling bpf_link_detach on them. > Link detach triggers the link to be freed by bpf_link_free(), > which calls __cgroup_bpf_detach() and update_effective_progs(). > If the memory allocation in this function fails, the function restores > the pointer to the bpf_cgroup_link on the cgroup list, but the memory > gets freed just after it returns. After this, every subsequent call to > update_effective_progs() causes this already deallocated pointer to be > dereferenced in prog_list_length(), and triggers KASAN UAF error. > > To fix this issue don't preserve the pointer to the prog or link in the > list, but remove it and replace it with a dummy prog without shrinking > the table. The subsequent call to __cgroup_bpf_detach() or > __cgroup_bpf_detach() will correct it. > > Cc: "Alexei Starovoitov" <ast@kernel.org> > Cc: "Daniel Borkmann" <daniel@iogearbox.net> > Cc: "Andrii Nakryiko" <andrii@kernel.org> > Cc: "Martin KaFai Lau" <kafai@fb.com> > Cc: "Song Liu" <songliubraving@fb.com> > Cc: "Yonghong Song" <yhs@fb.com> > Cc: "John Fastabend" <john.fastabend@gmail.com> > Cc: "KP Singh" <kpsingh@kernel.org> > Cc: <netdev@vger.kernel.org> > Cc: <bpf@vger.kernel.org> > Cc: <stable@vger.kernel.org> > Cc: <linux-kernel@vger.kernel.org> > > Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4 > Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment") > Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com> > Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org> > --- > v2: Add a fall back path that removes a prog from the effective progs > table in case detach fails to allocate memory in compute_effective_progs(). > > v3: Implement the fallback in a separate function purge_effective_progs > --- > kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------ > 1 file changed, 56 insertions(+), 8 deletions(-) > > diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c > index 128028efda64..9d3af4d6c055 100644 > --- a/kernel/bpf/cgroup.c > +++ b/kernel/bpf/cgroup.c > @@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs, > return ERR_PTR(-ENOENT); > } > > +/** > + * purge_effective_progs() - After compute_effective_progs fails to alloc new > + * cgrp->bpf.inactive table we can recover by > + * recomputing the array in place. > + * > + * @cgrp: The cgroup which descendants to traverse > + * @link: A link to detach > + * @atype: Type of detach operation > + */ > +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog, > + enum cgroup_bpf_attach_type atype) > +{ > + struct cgroup_subsys_state *css; > + struct bpf_prog_array_item *item; > + struct bpf_prog *tmp; > + struct bpf_prog_array *array; > + int index = 0, index_purge = -1; > + > + if (!prog) > + return; > + > + /* recompute effective prog array in place */ > + css_for_each_descendant_pre(css, &cgrp->self) { > + struct cgroup *desc = container_of(css, struct cgroup, self); > + > + array = desc->bpf.effective[atype]; ../kernel/bpf/cgroup.c:748:23: warning: incorrect type in assignment (different address spaces) ../kernel/bpf/cgroup.c:748:23: expected struct bpf_prog_array *array ../kernel/bpf/cgroup.c:748:23: got struct bpf_prog_array [noderef] __rcu * you need rcu_dereference here? but also see suggestions below to avoid iterating effective directly (it's ambiguous to search by prog only) > + item = &array->items[0]; > + > + /* Find the index of the prog to purge */ > + while ((tmp = READ_ONCE(item->prog))) { > + if (tmp == prog) { I think comparing just prog isn't always correct, as the same program can be in effective array multiple times if attached through bpf_link. Looking at replace_effective_prog() I think we can do a very similar (and tested) approach: 1. restore original pl state in __cgroup_bpf_detach (so we can find it by comparing pl->prog == prog && pl->link == link) 2. use replace_effective_prog's approach to find position of pl in effective array (using this nested for loop over cgroup parents and list_for_each_entry inside) 3. then instead of replacing one prog with another do bpf_prog_array_delete_safe_at ? I'd feel more comfortable using the same tested overall approach of replace_effective_prog. > + index_purge = index; > + break; > + } > + item++; > + index++; > + } > + > + /* Check if we found what's needed for removing the prog */ > + if (index_purge == -1 || index_purge == index - 1) > + continue; the search shouldn't fail, should it? > + > + /* Remove the program from the array */ > + WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge), > + "Failed to purge a prog from array at index %d", index_purge); > + > + index = 0; > + index_purge = -1; > + } > +} > + > /** > * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and > * propagate the change to descendants > @@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog, > pl->link = NULL; > > err = update_effective_progs(cgrp, atype); > - if (err) > - goto cleanup; > + if (err) { > + struct bpf_prog *prog_purge = prog ? prog : link->link.prog; > + so here we shouldn't forget link, instead pass both link and prog (one of them will have to be NULL) into purge_effective_progs > + purge_effective_progs(cgrp, prog_purge, atype); > + } > > /* now can actually delete it from this cgroup list */ > list_del(&pl->node); > @@ -736,12 +790,6 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog, > bpf_prog_put(old_prog); > static_branch_dec(&cgroup_bpf_enabled_key[atype]); > return 0; > - > -cleanup: > - /* restore back prog or link */ > - pl->prog = old_prog; > - pl->link = link; > - return err; > } > > static int cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog, > -- > 2.36.1 >
On 5/16/22 16:16, Andrii Nakryiko wrote: > On Fri, May 13, 2022 at 12:08 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote: >> kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------ >> 1 file changed, 56 insertions(+), 8 deletions(-) >> >> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c >> index 128028efda64..9d3af4d6c055 100644 >> --- a/kernel/bpf/cgroup.c >> +++ b/kernel/bpf/cgroup.c >> @@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs, >> return ERR_PTR(-ENOENT); >> } >> >> +/** >> + * purge_effective_progs() - After compute_effective_progs fails to alloc new >> + * cgrp->bpf.inactive table we can recover by >> + * recomputing the array in place. >> + * >> + * @cgrp: The cgroup which descendants to traverse >> + * @link: A link to detach >> + * @atype: Type of detach operation >> + */ >> +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog, >> + enum cgroup_bpf_attach_type atype) >> +{ >> + struct cgroup_subsys_state *css; >> + struct bpf_prog_array_item *item; >> + struct bpf_prog *tmp; >> + struct bpf_prog_array *array; >> + int index = 0, index_purge = -1; >> + >> + if (!prog) >> + return; >> + >> + /* recompute effective prog array in place */ >> + css_for_each_descendant_pre(css, &cgrp->self) { >> + struct cgroup *desc = container_of(css, struct cgroup, self); >> + >> + array = desc->bpf.effective[atype]; > > ../kernel/bpf/cgroup.c:748:23: warning: incorrect type in assignment > (different address spaces) > ../kernel/bpf/cgroup.c:748:23: expected struct bpf_prog_array *array > ../kernel/bpf/cgroup.c:748:23: got struct bpf_prog_array [noderef] __rcu * > > > you need rcu_dereference here? but also see suggestions below to avoid > iterating effective directly (it's ambiguous to search by prog only) I didn't check it with sparse so I didn't see this warning. Will fix in the next version. > >> + item = &array->items[0]; >> + >> + /* Find the index of the prog to purge */ >> + while ((tmp = READ_ONCE(item->prog))) { >> + if (tmp == prog) { > > I think comparing just prog isn't always correct, as the same program > can be in effective array multiple times if attached through bpf_link. > > Looking at replace_effective_prog() I think we can do a very similar > (and tested) approach: > > 1. restore original pl state in __cgroup_bpf_detach (so we can find it > by comparing pl->prog == prog && pl->link == link) > 2. use replace_effective_prog's approach to find position of pl in > effective array (using this nested for loop over cgroup parents and > list_for_each_entry inside) > 3. then instead of replacing one prog with another do > bpf_prog_array_delete_safe_at ? > > I'd feel more comfortable using the same tested overall approach of > replace_effective_prog. Ok, I can try that. > >> + index_purge = index; >> + break; >> + } >> + item++; >> + index++; >> + } >> + >> + /* Check if we found what's needed for removing the prog */ >> + if (index_purge == -1 || index_purge == index - 1) >> + continue; > > the search shouldn't fail, should it? I wasn't if the prog will be present in all parents so I decided to add this check to make sure it is found. > >> + >> + /* Remove the program from the array */ >> + WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge), >> + "Failed to purge a prog from array at index %d", index_purge); >> + >> + index = 0; >> + index_purge = -1; >> + } >> +} >> + >> /** >> * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and >> * propagate the change to descendants >> @@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog, >> pl->link = NULL; >> >> err = update_effective_progs(cgrp, atype); >> - if (err) >> - goto cleanup; >> + if (err) { >> + struct bpf_prog *prog_purge = prog ? prog : link->link.prog; >> + > > so here we shouldn't forget link, instead pass both link and prog (one > of them will have to be NULL) into purge_effective_progs ok, I will pass in both.
On Mon, May 16, 2022 at 4:35 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote: > > On 5/16/22 16:16, Andrii Nakryiko wrote: > > On Fri, May 13, 2022 at 12:08 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote: > >> kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------ > >> 1 file changed, 56 insertions(+), 8 deletions(-) > >> > >> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c > >> index 128028efda64..9d3af4d6c055 100644 > >> --- a/kernel/bpf/cgroup.c > >> +++ b/kernel/bpf/cgroup.c > >> @@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs, > >> return ERR_PTR(-ENOENT); > >> } > >> > >> +/** > >> + * purge_effective_progs() - After compute_effective_progs fails to alloc new > >> + * cgrp->bpf.inactive table we can recover by > >> + * recomputing the array in place. > >> + * > >> + * @cgrp: The cgroup which descendants to traverse > >> + * @link: A link to detach > >> + * @atype: Type of detach operation > >> + */ > >> +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog, > >> + enum cgroup_bpf_attach_type atype) > >> +{ > >> + struct cgroup_subsys_state *css; > >> + struct bpf_prog_array_item *item; > >> + struct bpf_prog *tmp; > >> + struct bpf_prog_array *array; > >> + int index = 0, index_purge = -1; > >> + > >> + if (!prog) > >> + return; > >> + > >> + /* recompute effective prog array in place */ > >> + css_for_each_descendant_pre(css, &cgrp->self) { > >> + struct cgroup *desc = container_of(css, struct cgroup, self); > >> + > >> + array = desc->bpf.effective[atype]; > > > > ../kernel/bpf/cgroup.c:748:23: warning: incorrect type in assignment > > (different address spaces) > > ../kernel/bpf/cgroup.c:748:23: expected struct bpf_prog_array *array > > ../kernel/bpf/cgroup.c:748:23: got struct bpf_prog_array [noderef] __rcu * > > > > > > you need rcu_dereference here? but also see suggestions below to avoid > > iterating effective directly (it's ambiguous to search by prog only) > > I didn't check it with sparse so I didn't see this warning. > Will fix in the next version. > > > > >> + item = &array->items[0]; > >> + > >> + /* Find the index of the prog to purge */ > >> + while ((tmp = READ_ONCE(item->prog))) { > >> + if (tmp == prog) { > > > > I think comparing just prog isn't always correct, as the same program > > can be in effective array multiple times if attached through bpf_link. > > > > Looking at replace_effective_prog() I think we can do a very similar > > (and tested) approach: > > > > 1. restore original pl state in __cgroup_bpf_detach (so we can find it > > by comparing pl->prog == prog && pl->link == link) > > 2. use replace_effective_prog's approach to find position of pl in > > effective array (using this nested for loop over cgroup parents and > > list_for_each_entry inside) > > 3. then instead of replacing one prog with another do > > bpf_prog_array_delete_safe_at ? > > > > I'd feel more comfortable using the same tested overall approach of > > replace_effective_prog. > > Ok, I can try that. > > > > >> + index_purge = index; > >> + break; > >> + } > >> + item++; > >> + index++; > >> + } > >> + > >> + /* Check if we found what's needed for removing the prog */ > >> + if (index_purge == -1 || index_purge == index - 1) > >> + continue; > > > > the search shouldn't fail, should it? > > I wasn't if the prog will be present in all parents so I decided to add this > check to make sure it is found. Looking at replace_effective_prog (it's been a while since I touched this code) it has to be present, otherwise it's a bug > > > > >> + > >> + /* Remove the program from the array */ > >> + WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge), > >> + "Failed to purge a prog from array at index %d", index_purge); > >> + > >> + index = 0; > >> + index_purge = -1; > >> + } > >> +} > >> + > >> /** > >> * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and > >> * propagate the change to descendants > >> @@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog, > >> pl->link = NULL; > >> > >> err = update_effective_progs(cgrp, atype); > >> - if (err) > >> - goto cleanup; > >> + if (err) { > >> + struct bpf_prog *prog_purge = prog ? prog : link->link.prog; > >> + > > > > so here we shouldn't forget link, instead pass both link and prog (one > > of them will have to be NULL) into purge_effective_progs > > ok, I will pass in both. > > -- > Thanks, > Tadeusz
diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c index 128028efda64..9d3af4d6c055 100644 --- a/kernel/bpf/cgroup.c +++ b/kernel/bpf/cgroup.c @@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs, return ERR_PTR(-ENOENT); } +/** + * purge_effective_progs() - After compute_effective_progs fails to alloc new + * cgrp->bpf.inactive table we can recover by + * recomputing the array in place. + * + * @cgrp: The cgroup which descendants to traverse + * @link: A link to detach + * @atype: Type of detach operation + */ +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog, + enum cgroup_bpf_attach_type atype) +{ + struct cgroup_subsys_state *css; + struct bpf_prog_array_item *item; + struct bpf_prog *tmp; + struct bpf_prog_array *array; + int index = 0, index_purge = -1; + + if (!prog) + return; + + /* recompute effective prog array in place */ + css_for_each_descendant_pre(css, &cgrp->self) { + struct cgroup *desc = container_of(css, struct cgroup, self); + + array = desc->bpf.effective[atype]; + item = &array->items[0]; + + /* Find the index of the prog to purge */ + while ((tmp = READ_ONCE(item->prog))) { + if (tmp == prog) { + index_purge = index; + break; + } + item++; + index++; + } + + /* Check if we found what's needed for removing the prog */ + if (index_purge == -1 || index_purge == index - 1) + continue; + + /* Remove the program from the array */ + WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge), + "Failed to purge a prog from array at index %d", index_purge); + + index = 0; + index_purge = -1; + } +} + /** * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and * propagate the change to descendants @@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog, pl->link = NULL; err = update_effective_progs(cgrp, atype); - if (err) - goto cleanup; + if (err) { + struct bpf_prog *prog_purge = prog ? prog : link->link.prog; + + purge_effective_progs(cgrp, prog_purge, atype); + } /* now can actually delete it from this cgroup list */ list_del(&pl->node); @@ -736,12 +790,6 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog, bpf_prog_put(old_prog); static_branch_dec(&cgroup_bpf_enabled_key[atype]); return 0; - -cleanup: - /* restore back prog or link */ - pl->prog = old_prog; - pl->link = link; - return err; } static int cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
Syzbot found a Use After Free bug in compute_effective_progs(). The reproducer creates a number of BPF links, and causes a fault injected alloc to fail, while calling bpf_link_detach on them. Link detach triggers the link to be freed by bpf_link_free(), which calls __cgroup_bpf_detach() and update_effective_progs(). If the memory allocation in this function fails, the function restores the pointer to the bpf_cgroup_link on the cgroup list, but the memory gets freed just after it returns. After this, every subsequent call to update_effective_progs() causes this already deallocated pointer to be dereferenced in prog_list_length(), and triggers KASAN UAF error. To fix this issue don't preserve the pointer to the prog or link in the list, but remove it and replace it with a dummy prog without shrinking the table. The subsequent call to __cgroup_bpf_detach() or __cgroup_bpf_detach() will correct it. Cc: "Alexei Starovoitov" <ast@kernel.org> Cc: "Daniel Borkmann" <daniel@iogearbox.net> Cc: "Andrii Nakryiko" <andrii@kernel.org> Cc: "Martin KaFai Lau" <kafai@fb.com> Cc: "Song Liu" <songliubraving@fb.com> Cc: "Yonghong Song" <yhs@fb.com> Cc: "John Fastabend" <john.fastabend@gmail.com> Cc: "KP Singh" <kpsingh@kernel.org> Cc: <netdev@vger.kernel.org> Cc: <bpf@vger.kernel.org> Cc: <stable@vger.kernel.org> Cc: <linux-kernel@vger.kernel.org> Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4 Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment") Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org> --- v2: Add a fall back path that removes a prog from the effective progs table in case detach fails to allocate memory in compute_effective_progs(). v3: Implement the fallback in a separate function purge_effective_progs --- kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------ 1 file changed, 56 insertions(+), 8 deletions(-)