GSoC 2019: Efficient syscall tracing for strace

[Paul Chaignon]

On Tue, Apr 09, 2019 at 07:33:24AM +0200, Paul Chaignon wrote:
> On Mon, Apr 08, 2019 at 11:53:34PM +0300, Dmitry V. Levin wrote:

[...]

> > > There are several opportunities to improve the current cBPF filter: it
> > > currently contains a few unnecessary instructions and implements a linear
> > > matching algorithm over the syscall numbers (although it takes ranges of
> > > continuous numbers into account).  To limit the number of instructions,
> > > the cBPF program could also match on the reverse set of syscalls (match
> > > against syscalls that should be RET_ALLOWed instead of RET_TRACEd) when
> > > that makes sense.
> > 
> > I suppose libseccomp might be a good source of ideas for generating a more
> > optimal cBPF program.
> 
> Thanks for the suggestion, I'll have a look.  At the moment, I was
> thinking we could either use binary search or a simple bit-matching
> algorithm (see mail to Chen Jingpiao on the mailing list for details) to
> match filtered syscalls.

I've checked libseccomp's code [1] and run a small PoC.  They implement a
linear match over the list of filtered syscalls.  They don't even have
range matching as Chen's current prototype.  They have to work with
different constraints though as users can give different priorities to
different syscalls and they match high-priority syscalls first.

They had several discussions on performance of the BPF program [2, 3].
One contributor is working on a binary search patchset.  I guess they
can't use bitwise AND if they want to abide by the user's priorities.

1 - https://github.com/seccomp/libseccomp/blob/7fbf639526eb37a011318736587c3a6f8206b888/src/gen_bpf.c#L1229
2 - https://groups.google.com/forum/#!topic/libseccomp/pX6QkVF0F74/discussion
3 - https://github.com/seccomp/libseccomp/issues/116

[...]

--
Paul