Paul Chaignon's GSoC status report - #12 of 12
paul.chaignon at gmail.com
Mon Aug 19 18:03:22 UTC 2019
- I finished addressing comments on v2 patchset and sent a v3.
- I wrote a lot of code to try and handle cases of jump offset overflows.
In cBPF, jump offsets are encoded on 8 bits. During the generation of
BPF programs, we use placeholders for the jump offsets; the actual
offsets are computed at the end of each personality section. Jumps
larger than 255 may however overflow and need to be complemented with
unconditional jumps whose offset is encoded on 32 bits (the actual jump
happens in two steps as the unconditional jump makes a short jump to the
long unconditional one).
One naive approach to the problem could then be to complement *each*
overflowed jump with their own unconditional jump. Since all jumps
target the same 2-3 instructions, we can do better and use a single
unconditional jump per target. I implemented this, but the ended up
with something quite complex, as there are a lot of cases to handle.
Wherever we add the long jump, we need to check it did not replace a
previous jump target. We also need to update the jump offsets of other
jumps and remember where the placed the last long jump instruction for
At that point I stopped and considered whether we really needed this.
Jump offset overflows can only happen within the section of code for a
single personality; we don't jump across sections. So we need >255
instructions in a single personality section for an overflow to happen.
With the linear program generation, we would need about 380 traced
syscalls, with 2 syscalls traced every 3 syscalls. In practice, that
rarely happens (see number at the end of the email, for entire
Thus, I instead simply disabled seccomp-filter whenever an overflow
happens. We can always handle them later if they become more common
(e.g., if the program sizes grow because we handle more cases). If that
happens we could try to place the long jumps ahead of time, before the
rest of the bytecode. It seems easier to implement.
- I optimized the binary match generation of BPF programs. In case few or
lots of syscalls were being traced, the BPF program would match syscalls
against many all-O or all-1 bit arrays. Since we know the result of
these two cases, we can replace them with direct jumps to RET_TRACE or
RET_ALLOW. We then end up with sequences of direct jumps (e.g., jeq for
bit arrays 0, 1, 2, 3). Using a similar algorithm as in the linear
strategy (except for bit array indexes instead of syscall numbers), we
can squash these sequences of direct jumps into inequalities.
- I wrote a quick script to get the size of programs generated by the
three strategies: linear, reverse linear (same but trying to match
syscalls we don't want to trace), and binary match. The results are
below, for arm and x86-64. The binary match strategy, with the above
optimization, only outperforms the other two strategies in 3 cases on
the 19 tested (for %desc, %file, and the combination).
- I am rebasing my seccomp-strategies branch (contains the multiple
strategies) on top of my seccomp branch; the two had diverged. Once
that is done, I'll send an RFC patchset for the multiple strategies with
evaluations of the program sizes.
- I've retrieved an old MIPS device I'll use to test the generation of
programs under MIPS.
lin. rev. bin.
none, 8 14 26
ptrace, 9 16 26
!ptrace, 8 5 18
%desc, 84 110 55
%file, 61 79 55
%fstat, 12 22 35
%fstatfs, 10 17 31
%ipc, 12 20 34
%lstat, 11 20 33
%memory, 33 52 52
%network, 17 26 45
%process, 18 31 42
%pure, 19 27 40
%signal, 28 46 49
%stat, 11 20 31
%statfs, 10 18 31
%%stat, 17 28 37
%%statfs, 13 19 33
%memory,%ipc,%pure,%signal,%network 70 95 56
lin. rev. bin.
none, 36 47 84
ptrace, 39 51 88
!ptrace, 32 23 66
%desc, 239 274 172
%file, 173 212 172
%fstat, 44 63 107
%fstatfs, 40 54 99
%ipc, 49 63 111
%lstat, 41 57 96
%memory, 98 136 160
%network, 62 81 120
%process, 63 94 139
%pure, 62 80 116
%signal, 87 126 157
%stat, 41 57 94
%statfs, 40 55 99
%%stat, 53 73 113
%%statfs, 45 56 101
%memory,%ipc,%pure,%signal,%network 193 246 176
More information about the Strace-devel