Re: [PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program

[Anton Protopopov <a.s.protopopov@gmail.com>]

On 26/09/09 10:40PM, Daniel Borkmann wrote:
> Every gotox instruction gets its own copy of the jump table of the subprog
> containing it, and each distinct target in that table is a CFG successor
> of the instruction. The number of such edges is therefore the number of
> gotox instructions times the number of distinct targets, and neither
> factor is bounded by anything except the instruction limit.
> 
> What is expensive is a BPF prog whose gotox instructions are themselves
> the targets, which makes the edge count quadratic. 1024 such gotox are
> already ~1e6 edges and about 4s of CPU to load.
> 
> Bound the total across the program at BPF_COMPLEXITY_LIMIT_INSNS, aka
> the limit as the number of instructions the verifier processes. Progs
> with real switch statements are orders of magnitude below this.
> 
> Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
> Reported-by: STAR Labs SG <info@starlabs.sg>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---
>  include/linux/bpf_verifier.h |  1 +
>  kernel/bpf/cfg.c             | 15 +++++++++++++++
>  2 files changed, 16 insertions(+)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 36b65797877d..04bb8f71cabe 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -977,6 +977,7 @@ struct bpf_verifier_env {
>  		int cur_stack;
>  		/* current position in the insn_postorder vector */
>  		int cur_postorder;
> +		u32 gotox_edges;
>  	} cfg;
>  	struct backtrack_state bt;
>  	struct bpf_jmp_history_entry *cur_hist_ent;
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 081f7003eae6..e9910228da58 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -9,6 +9,8 @@
>  
>  #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
>  
> +#define BPF_MAX_GOTOX_EDGES	BPF_COMPLEXITY_LIMIT_INSNS
> +
>  /* non-recursive DFS pseudo code
>   * 1  procedure DFS-iterative(G,v):
>   * 2      label v as discovered
> @@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
>  			return PTR_ERR(jt);
>  
>  		env->insn_aux_data[t].jt = jt;
> +
> +		if (check_add_overflow(env->cfg.gotox_edges, jt->cnt,
> +				       &env->cfg.gotox_edges) ||
> +		    env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) {
> +			verbose(env, "number of indirect jump edges in the program exceeds %u\n",
> +				BPF_MAX_GOTOX_EDGES);
> +			bpf_diag_program_structure(
> +				env, t, "too many indirect jump edges",
> +				"Reduce the number of indirect jumps, or the number of distinct targets they can reach.",
> +				"The program has more than %u indirect jump edges in total, counted over every gotox instruction.",
> +				BPF_MAX_GOTOX_EDGES);
> +			return -E2BIG;
> +		}
>  	}
>  
>  	mark_prune_point(env, t);
> -- 
> 2.43.0

Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>