[PATCH v3 0/2] filter_seccomp: new bpf generation strategy

[Paul Chaignon]

On Wed, Nov 06, 2019 at 02:12:05AM +0300, Dmitry V. Levin wrote:
> On Mon, Nov 04, 2019 at 04:38:13PM +0100, Paul Chaignon wrote:
> > On Mon, Nov 04, 2019 at 03:14:12PM +0300, Dmitry V. Levin wrote:
> > > On Mon, Nov 04, 2019 at 12:36:07PM +0100, Paul Chaignon wrote:

[...]

> > > > Some of the corner cases are also a bit hard to test (e.g., jump offset
> > > > overflow and oversized filter) because I currently am unable to come up
> > > > with a trace set that triggers them.
> > > 
> > > Could you prove they cannot be triggered? ;)
> > 
> > Informally and at the algorithm level, yes.
> > 
> > Let's take Ni and Ns to be the number of instructions in the filter and
> > the total number of syscalls (traced + not traced) for a given arch and
> > personality.  For the jump offset overflow, we only need Ni > 255
> > instructions for a single personality.
> > 
> > With the linear strategy, in the worst case (pattern of 2 traced syscalls
> > followed by 1 syscall not traced), Ni = 2/3 * Ns + 5.  With the binary
> > match strategy, Ni = 11 + 3 * Ns / 32 (3 instructions required to match a
> > bitarray encoding 32 syscalls).
> > 
> > So we would need 375 syscalls in a single personality to generate a jump
> > offset overflow (linear strategy), 2602 syscalls for both strategies to
> > fail with overflows.  If jump offset overflows are maybe possible,
> > oversized programs seem much less likely:  if we suppose 3 personalities
> > and count the 2 additional instructions, we would need 1360 syscalls for
> > the linear strategy to generate an oversized program in the worst case,
> > 14439 for the binary match one.
> > 
> > That is, if the implementation of the algorithms is correct of course :-)
> 
> If we need that many filterable syscalls, then mips should to be
> the architecture of choice. :)

Good call!  I found a bug in the implementation of the binary match
algorithm using a mips server from project compile farm.  The check for
jump offset overflows was missing; I sent a patch.

I have yet to find the right set of syscalls that triggers a jump offset
overflow for the linear algorithm (I forced the use of the binary match
one to find the bug), but if/when I do, I'll probably add a mips-specific
test case for that.

Paul