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

Paul Chaignon paul.chaignon at gmail.com
Mon Nov 4 15:38:13 UTC 2019

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 :-)

> > I had a look at the Codecov reporting, but it looks kinda weird:
> > exec_or_die() is supposedly never executed, as if Codecov is only tracing
> > the tracer process...?
> This looks rather like a bug in gcov used in the travis build (maybe
> the gcc version is too old) because in local coverage tests I see that
> exec_or_die is covered.

Travis CI has gcc 4.8.4, which should have the required code [1].  Not
sure what else could be posing a problem here.

1 - https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=73673831c11755ce248066961df4ba25ba023ad9

> When gcc --coverage (or analogue) is used, it wraps all forks and execs
> in a special way, see
> https://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libgcc/libgcov-interface.c

More information about the Strace-devel mailing list