lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-ID: <d3ec87a6-9049-ee3e-d8f0-e55e40ba1104@fb.com> Date: Wed, 2 Jan 2019 05:25:49 +0000 From: Yonghong Song <yhs@...com> To: Jakub Kicinski <jakub.kicinski@...ronome.com>, "alexei.starovoitov@...il.com" <alexei.starovoitov@...il.com>, "daniel@...earbox.net" <daniel@...earbox.net> CC: "netdev@...r.kernel.org" <netdev@...r.kernel.org>, "oss-drivers@...ronome.com" <oss-drivers@...ronome.com> Subject: Re: [RFC bpf-next v4 03/12] bpf: verifier: remove dead code On 12/31/18 5:37 PM, Jakub Kicinski wrote: > Instead of overwriting dead code with jmp -1 instructions > remove it completely for root. Adjust verifier state and > line info appropriately. > > v2: > - adjust func_info (Alexei); > - make sure first instruction retains line info (Alexei). > v4: (Yonghong) > - remove unnecessary if (!insn to remove) checks; > - always keep last line info if first live instruction lacks one. > > Signed-off-by: Jakub Kicinski <jakub.kicinski@...ronome.com> > --- > include/linux/filter.h | 1 + > kernel/bpf/core.c | 12 +++ > kernel/bpf/verifier.c | 167 ++++++++++++++++++++++++++++++++++++++++- > 3 files changed, 177 insertions(+), 3 deletions(-) > > diff --git a/include/linux/filter.h b/include/linux/filter.h > index 8c8544b375eb..2cdb50bbf867 100644 > --- a/include/linux/filter.h > +++ b/include/linux/filter.h > @@ -782,6 +782,7 @@ static inline bool bpf_dump_raw_ok(void) > > struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, > const struct bpf_insn *patch, u32 len); > +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt); > > void bpf_clear_redirect_map(struct bpf_map *map); > > diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c > index a40057b2c556..cc6fa754627c 100644 > --- a/kernel/bpf/core.c > +++ b/kernel/bpf/core.c > @@ -461,6 +461,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, > return prog_adj; > } > > +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt) > +{ > + /* Branch offsets can't overflow when program is shrinking, no need > + * to call bpf_adj_branches(..., true) here > + */ > + memmove(prog->insnsi + off, prog->insnsi + off + cnt, > + sizeof(struct bpf_insn) * (prog->len - off - cnt)); > + prog->len -= cnt; > + > + return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false)); > +} > + > void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp) > { > int i; > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 30e2cd399b4a..2f786acb65ce 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -6233,6 +6233,141 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of > return new_prog; > } > > +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env, > + u32 off, u32 cnt) > +{ > + int i, j; > + > + /* find first prog starting at or after off (first to remove) */ > + for (i = 0; i < env->subprog_cnt; i++) > + if (env->subprog_info[i].start >= off) > + break; > + /* find first prog starting at or after off + cnt (first to stay) */ > + for (j = i; j < env->subprog_cnt; j++) > + if (env->subprog_info[j].start >= off + cnt) > + break; > + /* if j doesn't start exactly at off + cnt, we are just removing > + * the front of previous prog > + */ > + if (env->subprog_info[j].start != off + cnt) > + j--; It is possible that j = env->subprog_cnt here. Looks like the following case is not properly covered: for func1: insn1 insn2 func2: insn3 insn4 case (1): insn3 removed case (2): insn3 and insn4 removed, func2 subprog_info should be remeoved. Maybe a change like below will work to include handling of the last subprog: - if (env->subprog_info[j].start != off + cnt) + if ((j == env->subprog_cnt && env->prog->len > off) || + (j < env->subprog_cnt && env->subprog_info[j].start != off + cnt)) j--; > + > + if (j > i) { > + struct bpf_prog_aux *aux = env->prog->aux; > + int move; > + > + /* move fake 'exit' subprog as well */ > + move = env->subprog_cnt + 1 - j; > + > + memmove(env->subprog_info + i, > + env->subprog_info + j, > + sizeof(*env->subprog_info) * move); > + env->subprog_cnt -= j - i; > + > + /* remove func_info */ > + if (aux->func_info) { > + move = aux->func_info_cnt - j; > + > + memmove(aux->func_info + i, > + aux->func_info + j, > + sizeof(*aux->func_info) * move); > + aux->func_info_cnt -= j - i; > + } > + } else { > + /* convert i from "first prog to remove" to "first to adjust" */ > + if (env->subprog_info[i].start == off) > + i++; > + } > + > + /* update fake 'exit' subprog as well */ > + for (; i <= env->subprog_cnt; i++) > + env->subprog_info[i].start -= cnt; > + > + return 0; > +} > + > +static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off, > + u32 cnt) > +{ > + struct bpf_prog *prog = env->prog; > + u32 i, l_off, l_cnt, nr_linfo; > + struct bpf_line_info *linfo; > + > + nr_linfo = prog->aux->nr_linfo; > + if (!nr_linfo) > + return 0; > + > + linfo = prog->aux->linfo; > + > + /* find first line info to remove, count lines to be removed */ > + for (i = 0; i < nr_linfo; i++) > + if (linfo[i].insn_off >= off) > + break; > + > + l_off = i; > + l_cnt = 0; > + for (; i < nr_linfo; i++) > + if (linfo[i].insn_off < off + cnt) > + l_cnt++; > + else > + break; > + > + /* first live insn doesn't match first live linfo, inherit */ > + if (prog->len != off && l_cnt && > + (i == nr_linfo || linfo[i].insn_off != off + cnt)) { > + l_cnt--; > + linfo[--i].insn_off = off + cnt; The same here. The handling the last line_info seems not sufficient. It depends on whether all insns covered by last linfo have been removed or not. Maybe something like below? + if (l_cnt && + ((i == nr_linfo && prog->len > off) || + (i < nr_linfo && linfo[i].insn_off != off + cnt))) { l_cnt--; linfo[--i].insn_off = off + cnt; Please double check whether my suggested fix is correct or not. You may want to add test cases to cover these cases as well. Thanks! > + } > + > + /* remove the line info which refers to the removed instructions */ > + if (l_cnt) { > + memmove(linfo + l_off, linfo + i, > + sizeof(*linfo) * (nr_linfo - i)); > + > + prog->aux->nr_linfo -= l_cnt; > + nr_linfo = prog->aux->nr_linfo; > + } > + > + /* pull all linfo[i].insn_off >= off + cnt in by cnt */ > + for (i = l_off; i < nr_linfo; i++) > + linfo[i].insn_off -= cnt; > + > + /* fix up all subprogs (incl. 'exit') which start >= off */ > + for (i = 0; i <= env->subprog_cnt; i++) > + if (env->subprog_info[i].linfo_idx > l_off) { > + if (env->subprog_info[i].linfo_idx >= l_off + l_cnt) > + env->subprog_info[i].linfo_idx -= l_cnt; > + else > + env->subprog_info[i].linfo_idx = l_off; > + } > + > + return 0; > +} > + > +static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt) > +{ > + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; > + unsigned int orig_prog_len = env->prog->len; > + int err; > + > + err = bpf_remove_insns(env->prog, off, cnt); > + if (err) > + return err; > + > + err = adjust_subprog_starts_after_remove(env, off, cnt); > + if (err) > + return err; > + > + err = bpf_adj_linfo_after_remove(env, off, cnt); > + if (err) > + return err; > + > + memmove(aux_data + off, aux_data + off + cnt, > + sizeof(*aux_data) * (orig_prog_len - off - cnt)); > + > + return 0; > +} > + > /* The verifier does more data flow analysis than llvm and will not > * explore branches that are dead at run time. Malicious programs can > * have dead code too. Therefore replace all dead at-run-time code > @@ -6293,6 +6428,30 @@ static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env) > } > } > > +static int opt_remove_dead_code(struct bpf_verifier_env *env) > +{ > + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; > + int insn_cnt = env->prog->len; > + int i, err; > + > + for (i = 0; i < insn_cnt; i++) { > + int j; > + > + j = 0; > + while (i + j < insn_cnt && !aux_data[i + j].seen) > + j++; > + if (!j) > + continue; > + > + err = verifier_remove_insns(env, i, j); > + if (err) > + return err; > + insn_cnt = env->prog->len; > + } > + > + return 0; > +} > + > /* convert load instructions that access fields of a context type into a > * sequence of instructions that access fields of the underlying structure: > * struct __sk_buff -> struct sk_buff > @@ -7032,11 +7191,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, > if (is_priv) { > if (ret == 0) > opt_hard_wire_dead_code_branches(env); > + if (ret == 0) > + ret = opt_remove_dead_code(env); > + } else { > + if (ret == 0) > + sanitize_dead_code(env); > } > > - if (ret == 0) > - sanitize_dead_code(env); > - > if (ret == 0) > /* program is valid, convert *(u32*)(ctx + off) accesses */ > ret = convert_ctx_accesses(env); >
Powered by blists - more mailing lists