netdev - Re: [PATCH bpf-next 2/7] bpf: improve verification speed by droping states

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20190330032934.633zkp65tl2k7eua@ast-mbp.dhcp.thefacebook.com>
Date:   Fri, 29 Mar 2019 20:29:36 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Jakub Kicinski <jakub.kicinski@...ronome.com>
Cc:     Alexei Starovoitov <ast@...nel.org>, davem@...emloft.net,
        daniel@...earbox.net, jannh@...gle.com, netdev@...r.kernel.org,
        bpf@...r.kernel.org, kernel-team@...com
Subject: Re: [PATCH bpf-next 2/7] bpf: improve verification speed by droping
 states

On Fri, Mar 29, 2019 at 08:12:39PM -0700, Jakub Kicinski wrote:
> On Fri, 29 Mar 2019 17:16:07 -0700, Alexei Starovoitov wrote:
> > Branch instructions, branch targets and calls in a bpf program are
> > the places where the verifier remembers states that led to successful
> > verification of the program.
> > These states are used to prune brute force program analysis.
> > For unprivileged programs there is a limit of 64 states per such
> > 'branching' instructions (maximum length is tracked by max_states_per_insn
> > counter introduced in the previous patch).
> > Simply reducing this threshold to 32 or lower increases insn_processed
> > metric to the point that small valid programs get rejected.
> > For root programs there is no limit and cilium programs can have
> > max_states_per_insn to be 100 or higher.
> > Walking 100+ states multiplied by number of 'branching' insns during
> > verification consumes significant amount of cpu time.
> > Turned out simple LRU-like mechanism can be used to remove states
> > that unlikely will be helpful in future search pruning.
> > This patch introduces hit_cnt and miss_cnt counters:
> > hit_cnt - this many times this state successfully pruned the search
> > miss_cnt - this many times this state was not equivalent to other states
> > (and that other states were added to state list)
> > 
> > The heuristic introduced in this patch is:
> > if (sl->miss_cnt > sl->hit_cnt * 3 + 3)
> >   /* drop this state from future considerations */
> > 
> > Higher numbers increase max_states_per_insn (allow more states to be
> > considered for pruning) and slow verification speed, but do not meaningfully
> > reduce insn_processed metric.
> > Lower numbers drop too many states and insn_processed increases too much.
> > Many different formulas were considered.
> > This one is simple and works well enough in practice.
> > (the analysis was done on selftests/progs/* and on cilium programs)
> > 
> > The end result is this heuristic improves verification speed by 10 times.
> > Large synthetic programs that used to take a second more now take
> > 1/10 of a second.
> > In cases where max_states_per_insn used to be 100 or more, now it's ~10.
> > 
> > There is a slight increase in insn_processed for cilium progs:
> >                        before   after
> > bpf_lb-DLB_L3.o 	1831	1838
> > bpf_lb-DLB_L4.o 	3029	3218
> > bpf_lb-DUNKNOWN.o 	1064	1064
> > bpf_lxc-DDROP_ALL.o	26309	26935
> > bpf_lxc-DUNKNOWN.o	33517	34439
> > bpf_netdev.o		9713	9721
> > bpf_overlay.o		6184	6184
> > bpf_lcx_jit.o		37335	39389
> > And 2-3 times improvement in the verification speed.
> > 
> > Signed-off-by: Alexei Starovoitov <ast@...nel.org>
> 
> Reviewed-by: Jakub Kicinski <jakub.kicinski@...ronome.com>
> 
> > @@ -6182,8 +6185,35 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> >  				return err;
> >  			return 1;
> >  		}
> > -		sl = sl->next;
> >  		states_cnt++;
> > +		sl->miss_cnt++;
> > +		/* heuristic to determine whether this state is beneficial
> > +		 * to keep checking from state equivalence point of view.
> > +		 * Higher numbers increase max_states_per_insn and verification time,
> > +		 * but do not meaningfully decrease insn_processed.
> > +		 */
> > +		if (sl->miss_cnt > sl->hit_cnt * 3 + 3) {
> > +			/* the state is unlikely to be useful. Remove it to
> > +			 * speed up verification
> > +			 */
> > +			*pprev = sl->next;
> > +			if (sl->state.frame[0]->regs[0].live & REG_LIVE_DONE) {
> > +				free_verifier_state(&sl->state, false);
> > +				kfree(sl);
> > +				env->peak_states--;
> 
> nit: is peak_states always equal to number of states when verifier
>      exits?

yes.
I was thinking as a follow up to add peak_states-- in bpf_verifier_env free-ing
logic to check that there are no memory leaks.

Few other follow ups on my todo list:
. write a ton more tests for scalability
. remove few leftover global variables and drop mutex for root
. account all verifier memory in memcg
. may be introduce a limit for peak_states for unpriv
. continue exploring state merging ideas
. introduce explicit rcu_unlock + preempt_enable in the programs