[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:
> > > > On Sun, Nov 03, 2019 at 07:01:24PM +0300, Dmitry V. Levin wrote:
> > > > > On Thu, Oct 31, 2019 at 08:55:12PM +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. :)

Yep.  I've been trying to get my hands on a mips board/server where I
could install strace to take a closer look, but no luck so far :(

Paul