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

[Dmitry V. Levin]

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:
> > [...]
> > > > We still can do better with test coverage of these new features, though.
> > > 
> > > Any specific cases you'd like us to test?
> > > 
> > > The third test case in tests/filter_seccomp.in should already be
> > > triggering the use of the new binary match strategy.  (Not that I think
> > > it's enough.)
> > 
> > From the test coverage I can see that bpf code is generated both for
> > linear and binary match strategies, and at least one of these strategies
> > generates bpf code that passes tests.  As far as I can tell, there is no
> > way to see whether the bpf code generated e.g. by the new binary match
> > strategy is actually tested.
> > 
> > > 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. :)


-- 
ldv
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: not available
URL: <http://lists.strace.io/pipermail/strace-devel/attachments/20191106/70ff70d8/attachment.bin>