Paul Chaignon's GSoC status report - #12 of 12

[Paul Chaignon]

Hi all,

Accomplishments:
- 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
  each target.
  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
  programs).
  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).

Priorities:
- 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.

Paul

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

x86-64:
                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