[PATCH RFC 0/9] filter_seccomp: new bpf generation strategies

Fri Aug 23 09:42:05 UTC 2019

This patchset proposes two new BPF generation strategies for
seccomp-filter, as well as some necessary code refactoring.  Since
seccomp-filter isn't merged yet, I've included the four patches of the
seccomp-filter patchset in addition to the five new patches, to ease
testing for reviewers.  I'll only discuss the five new patches here.

The first patch replaces check_bpf_program_size() with
init_seccomp_filter().  The second refactors the code to use a list of BPF
program generators.  The third and fourth introduce the reverse linear and
the binary match generation strategies.  The last patch optimizes the
binary match strategy.

The following tables compare the generation strategies for diverse
filters, under x86-64, aarch64, and arm.  Each number counts the lines of
the generated program.  lin. refers to the linear generation strategy,
rev. the reverse linear, and bin. the binary match one.  The second column
points to the best strategy for each filter, to get a quick impression.

x86-64:
		best	lin.	rev.	bin.
none		lin.	36	47	84
ptrace		lin.	39	51	88
!ptrace		rev.	32	23	66
%desc		bin.	239	274	172
%file		bin.	173	213	172
%fstat		lin.	44	63	107
%ipc		lin.	49	63	111
!%ipc		rev.	42	33	87
%lstat		lin.	41	57	96
%memory,%ipc,%pure,%signal,%network	bin.	193	246	176

aarch64:
		best	lin.	rev.	bin.
none		lin.	26	35	60
ptrace		lin.	28	39	65
!ptrace		rev.	20	14	42
%desc		bin.	140	171	107
%file		bin.	114	134	104
%fstat		lin.	32	45	74
%ipc		lin.	32	43	70
!%ipc		rev.	24	18	52
%lstat		lin.	29	41	67
%memory,%ipc,%pure,%signal,%network	bin.	111	139	107

arm:
		best	lin.	rev.	bin.
none		lin.	8	14	26
ptrace		lin.	9	16	26
!ptrace		rev.	8	5	18
%desc		bin.	84	110	55
%file		bin.	61	79	55
%fstat		lin.	12	22	35
%ipc		lin.	12	20	34
!%ipc		rev.	12	8	24
%lstat		lin.	11	20	33
%memory,%ipc,%pure,%signal,%network	bin.	70	95	56

First, one can note that the winning strategy for a given filter is the
same across all architectures, because the strategies don't impact the
arch-specific part of the bytecode.  The reverse linear strategy is the
most efficient only when almost all syscalls are being traced, and
generally by a small amount compared to the linear strategy.  The binary
match strategy is most efficient when there's a large number of traced
syscalls.  Finally, all generated programs are far below both BPF_MAXINSNS
and the maximum conditional jump offset.

>From these evaluations, it's not clear whether the reverse linear strategy
is worth keeping?  The binary match strategy may be worth keeping, but
probably not its optimization; I think it adds unnecessary complexity, as
it optimizes cases for which the linear strategy is more efficient anyway.

Chen Jingpiao (2):
  Introduce seccomp-assisted syscall filtering
  tests: test cases for seccomp-assisted syscall filtering

Paul Chaignon (7):
  Add seccomp-filter syscall flag
  filter_seccomp: skip seccomp setup when there's nothing to filter
  filter_seccomp: use init_sock_filter to check number of BPF
    instructions
  filter_seccomp: list of seccomp-filter generation strategies
  filter_seccomp: reverse linear generation strategy
  filter_seccomp: binary match generation strategy
  filter_seccomp: optimize binary match

 Makefile.am                    |   2 +
 NEWS                           |   2 +
 filter_seccomp.c               | 703 +++++++++++++++++++++++++++++++++
 filter_seccomp.h               |  21 +
 linux/32/syscallent.h          |   4 +-
 linux/64/syscallent.h          |   4 +-
 linux/aarch64/arch_defs_.h     |   2 +
 linux/alpha/syscallent.h       |   4 +-
 linux/arch_defs_.h             |   4 +
 linux/arm/syscallent.h         |   8 +-
 linux/avr32/syscallent.h       |   6 +-
 linux/bfin/syscallent.h        |   8 +-
 linux/hppa/syscallent.h        |   4 +-
 linux/i386/syscallent.h        |   8 +-
 linux/ia64/arch_defs_.h        |   1 +
 linux/ia64/syscallent.h        |   4 +-
 linux/m68k/syscallent.h        |   8 +-
 linux/microblaze/syscallent.h  |   8 +-
 linux/mips/syscallent-n32.h    |   4 +-
 linux/mips/syscallent-n64.h    |   4 +-
 linux/mips/syscallent-o32.h    |  10 +-
 linux/powerpc/syscallent.h     |   8 +-
 linux/powerpc64/arch_defs_.h   |   2 +
 linux/powerpc64/syscallent.h   |   8 +-
 linux/riscv/arch_defs_.h       |   2 +
 linux/s390/syscallent.h        |   8 +-
 linux/s390x/arch_defs_.h       |   2 +
 linux/s390x/syscallent.h       |   8 +-
 linux/sh/syscallent.h          |   8 +-
 linux/sh64/syscallent.h        |   8 +-
 linux/sparc/syscallent.h       |  10 +-
 linux/sparc64/arch_defs_.h     |   2 +
 linux/sparc64/syscallent.h     |  10 +-
 linux/tile/arch_defs_.h        |   2 +
 linux/x32/arch_defs_.h         |   2 +
 linux/x32/syscallent.h         |   4 +-
 linux/x86_64/arch_defs_.h      |   3 +
 linux/x86_64/syscallent.h      |   4 +-
 linux/xtensa/syscallent.h      |   4 +-
 number_set.c                   |  12 +
 number_set.h                   |   4 +
 strace.1.in                    |  17 +-
 strace.c                       |  76 +++-
 sysent.h                       |   1 +
 sysent_shorthand_defs.h        |   2 +
 tests/.gitignore               |   2 +
 tests/Makefile.am              |   3 +
 tests/filter_seccomp-perf.c    |  33 ++
 tests/filter_seccomp-perf.test |  17 +
 tests/filter_seccomp.in        |   4 +
 tests/gen_tests.in             |   2 +
 tests/init.sh                  |   5 +
 tests/pure_executables.list    |   1 +
 tests/status-none-f.c          |  19 +
 trace_event.h                  |   5 +
 55 files changed, 1030 insertions(+), 87 deletions(-)
 create mode 100644 filter_seccomp.c
 create mode 100644 filter_seccomp.h
 create mode 100644 tests/filter_seccomp-perf.c
 create mode 100755 tests/filter_seccomp-perf.test
 create mode 100644 tests/filter_seccomp.in
 create mode 100644 tests/status-none-f.c

-- 
2.17.1