GSoC 2019: Efficient syscall tracing for strace

[Dmitry V. Levin]

On Wed, Apr 10, 2019 at 11:29:33AM +0200, Paul Chaignon wrote:
[...]
> Even taking personalities into account, it doesn't look like we might
> exceed BPF_MAXINSNS (4096 on older kernels).  The number of instructions
> might also not always be a good indicator of the filter's overhead.  At
> least for binary search, the number of instructions will likely be similar
> to a linear search with ranges, but the average runtime will be lower.
> 
> I'm expecting we will have to choose between linear search (for small
> filters) and only one of bitwise match and binary search.  In that case we
> can try linear first and fallback to what we've determined to be best
> between bitwise and binary search if linear produces a "too large" number
> of instructions.  We'll know more with a PoC and evaluations.

In a corner case scenario, e.g. when every second syscall number is
filtered, both linear search and binary search implementations are going
to be quite bulky with total of O(nsyscalls) comparisons.  Given that on
x86_64 we have 3 personalities and therefore 3 syscall tables, plus on x86
personality we also have socket subcall, I wouldn't be so sure about
BPF_MAXINSNS.

It might be a good choice indeed to use bitset search for implementing
non-trivial filters as it doesn't have these corner case issues.

> Reading libseccomp's code, I realized we may have to rewrite jumps for
> large filters.  cBPF enables conditional jumps of <=255.  We'll have to
> rewrite any jump>255 to use an inconditional jump.

Yes, we have to take this limitation into account.  I don't think a bitset
search is going to suffer from this limit, but e.g. AUDIT_ARCH_* jump can
easily exceed 255.

> In general, I think we should always fallback to the usual ptrace behavior
> if seccomp filter doesn't work for any reason (eventually with a warning).

Definitely.


-- 
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/20190411/7e51a485/attachment.bin>