From: Daniel Borkmann <dan...@iogearbox.net> Date: Thu, 18 May 2017 03:00:06 +0200
> Current limits with regards to processing program paths do not > really reflect today's needs anymore due to programs becoming > more complex and verifier smarter, keeping track of more data > such as const ALU operations, alignment tracking, spilling of > PTR_TO_MAP_VALUE_ADJ registers, and other features allowing for > smarter matching of what LLVM generates. > > This also comes with the side-effect that we result in fewer > opportunities to prune search states and thus often need to do > more work to prove safety than in the past due to different > register states and stack layout where we mismatch. Generally, > it's quite hard to determine what caused a sudden increase in > complexity, it could be caused by something as trivial as a > single branch somewhere at the beginning of the program where > LLVM assigned a stack slot that is marked differently throughout > other branches and thus causing a mismatch, where verifier > then needs to prove safety for the whole rest of the program. > Subsequently, programs with even less than half the insn size > limit can get rejected. We noticed that while some programs > load fine under pre 4.11, they get rejected due to hitting > limits on more recent kernels. We saw that in the vast majority > of cases (90+%) pruning failed due to register mismatches. In > case of stack mismatches, majority of cases failed due to > different stack slot types (invalid, spill, misc) rather than > differences in spilled registers. > > This patch makes pruning more aggressive by also adding markers > that sit at conditional jumps as well. Currently, we only mark > jump targets for pruning. For example in direct packet access, > these are usually error paths where we bail out. We found that > adding these markers, it can reduce number of processed insns > by up to 30%. Another option is to ignore reg->id in probing > PTR_TO_MAP_VALUE_OR_NULL registers, which can help pruning > slightly as well by up to 7% observed complexity reduction as > stand-alone. Meaning, if a previous path with register type > PTR_TO_MAP_VALUE_OR_NULL for map X was found to be safe, then > in the current state a PTR_TO_MAP_VALUE_OR_NULL register for > the same map X must be safe as well. Last but not least the > patch also adds a scheduling point and bumps the current limit > for instructions to be processed to a more adequate value. > > Signed-off-by: Daniel Borkmann <dan...@iogearbox.net> > Acked-by: Alexei Starovoitov <a...@kernel.org> Ok, applied, but we should continue trying to make the pruner more effective.
