Minijail

Objective

Now that Minijail can load arbitrary seccomp-bpf programs, the possibility to move the compilation of the policy to a separate process is now open. Without the limitations of writing an in-process compiler that needs to be fast, small, simple, and have no build or runtime dependencies, we are introducing a new syntax that will only be supported by a separate out-of-process compiler that is more usable, less error-prone. The out-of-process compiler can also perform further optimizations to the generated code.

Background

Minijail currently parses and emits the seccomp-bpf program from a policy file as part of libminijail. Since this is done as part of a library and usually as part of the process of launching a new container, it needs to be very fast and not use a lot of additional resources. The way this is achieved is by doing a simple two-pass compilation: in the first pass, the policy file is parsed while the complete BPF filter is created in a two-layered singly-linked list with most jump sources/targets being encoded within the filter nodes themselves, using only an external dictionary of jump labels to filter entries to aid in the jump address resolution later. Since BPF forbids loops (i.e., there are no back edges), once the filter entries are allocated, they are copied into a contiguous array in reverse order so that all the jump targets are in the right place by the time when the jump sources need to be emitted.

The parser also tries to avoid compile-time complexity, since the project needs to be built in both Android and Chrome OS, which have different build systems.

Detailed design

Policy syntax definition

This is the new syntax in EBNF:

Frequency file syntax definition

This is the syntax in EBNF for the frequency file:

 New semantics

• Includes will now be relative to the path of the current file, instead of the CWD.
• The include depth limit will be increased to 10.
• A syscall descriptor can be defined multiple times, and all filters / actions will be evaluated in the order in which they were defined in the policy. This can allow for included policy files to perform common filters that are then refined in the main policy file. In order to prevent accidents, once a syscall is used with an unconditional action, any further filters that involve that syscall (either directly or through a libc function) will be a compilation error.
  So:

is acceptable, but the following is not:

• Similarly, the following syntax is introduced as a shorthand to express the previous case, where single syscall descriptor can have multiple filters/actions:

• libc function names can be specified with the @libc suffix (e.g. open@libc will use the openat syscall instead of the legacy open in recent versions of libc). An entry that uses a libc function will apply to all the system calls invoked by that libc function.
• In order to allow a single policy file to be defined for all architectures, metadata can be added to specify the arch of a syscall / function. Although this pattern can be mitigated by using libc functions instead, this feature is still desirable for programs that directly call system calls in an architecture-specific way (e.g. syscalls that don't have a libc wrapper):

• The frequency file is a simple key-value pair list of syscall descriptors to frequencies. Frequencies can be obtained by running strace /  perf trace / some version of global syscall aggregation. The frequencies will then influence the optimizer so it can make minimize the overhead of the syscall invocation making more frequently-used syscalls cheaper.

Off-process compiler / optimizer

There is an implementation of an optimizing compiler written in Python. It needs to know the mapping of syscall names to numbers, as well as the libc function names to syscalls per-architecture and can be obtained by running parse-seccomp-policy --dump. Similar to the current implementation, the emitted code is structured into three contiguous sections:

• A program epilogue, that detects the arch of the syscall and denies it if it does not match the one that is expected. This is used to prevent x86 syscalls in a x86_64 context.
• A syscall decision tree. The syscall number is loaded into the BPF register and the appropriate action for each syscalls (allow, filter, return errno) is chosen based on the syscall number. This decision tree can be structured in various ways, described in the Syscall decision tree cost model section. If the policy did not explicitly specify an action for a particular syscall, at the end of the syscall decision tree will be a catch-all default action. Any action that requires evaluating an expression will be handled by jumping into the corresponding filter in the filter section.
• A filter section. This section contains all the code that was emitted by the filter expressions. A filter expression compiles down to a series of instructions that load a register into the BPF register (or one 32-bit half of a register in 64-bit architectures), compares it to a value, and jumps into another comparison or the final action for that filter.

The following optimizations are considered:

• All BPF comparison instructions perform near jumps (< 256 instructions). There is also an unconditional jump instruction to handle far jumps. Since the new compiler uses an intermediate representation of the generated program, once the jump targets are computed, the jump style can be chosen depending on the distance between the source and the target for each comparison operator.
• For the syscall decision tree:

• Given a policy, it tries to build the BPF program with the least cost given the Syscall decision tree cost model.

• For the individual filters:

• In 64-bit architectures, given that BPF can only operate on 32-bit register halves, the optimizer omits certain comparisons on the upper half if they will always result in success / failure. e.g. for the set-inclusion operator, if the upper 32 bits of the mask are zero, the upper 32 bits of the register don't even need to be loaded into the register.
• Common subexpression elimination. If a particular comparison was evaluated before and the result is known, there is no point in performing the same comparison again:

Syscall decision tree cost model

The cost to evaluate a BPF program has been experimentally measured^[2] to be proportional to the number of filter blocks in it. There are two ways to encode a decision tree in BPF: a linear comparison chain (which is just a series of equality comparisons between the register and syscall numbers), and a binary search tree. The intermediate nodes of the BST can also be modeled in the same way, so it is possible to embed a linear comparison chain into a BST node if it would perform fewer operations overall. The nodes of the BST can also be rotated so that syscalls that are called more frequently appear higher in the tree.

The compiler produces the syscall decision tree that minimizes the number of operations that would need to be done if each syscall in the policy was invoked, multiplied by the frequency of that syscall. The compiler does this the following way, given a list of syscalls as input:

• Estimates the cost of a linear comparison chain for the list of syscalls:

• Sorts the syscalls by their frequency.
• Emits an equality comparison for each syscall in the sorted list.

• Estimates the cost of a BST (if the list has more than one syscall):

• Sorts the syscalls by their number.
• Collapses runs of syscalls with contiguous syscall numbers and identical actions.
• For each one of the O(n) possible cuts of the syscall run list, it emits a greater-than-or-equal comparison against the cut and for each half of the remaining syscalls, it recursively applies the same overall operation. Memoization is used to compute each of the O(n²) subintervals at most once.

This last step of choosing all of the possible cuts results in evaluating all interesting tree rotations, which translates to the compiler being able to choose the BST configuration that minimizes the overall cost, while preserving the BST property.

libc function-to-syscall mapping

This can be obtained by running static analysis over libc.so. There is a prototype written using llvm's MCDisassembler that is promising so far.

Alternatives considered

libseccomp

libseccomp has a concept of pseudo-syscalls, which are aliases for syscalls in each architecture, but it doesn't keep track of the latest libc implementation. This is more complicated for Android since it uses a different implementation of libc. libseccomp also does not perform optimizations on the generated code beyond what Minijail already does: ordering the syscalls by frequency.

clang's eBPF backend

clang can compile C code to eBPF programs, which is mostly used for Linux tracing. Unfortunately, both of the outputs that can be obtained by clang are not usable:

• LLVM IR

• Since the IR is machine-independent, the register allocation phase still hasn't happened, so there would be a need to have a separate compiler to perform that or emit suboptimal code that wastes a lot of cycles loading stuff from the context.
• For any realistic number of whitelisted syscalls, the LLVM IR will most likely use a switch instruction, which defeats most of the purpose of offloading the optimization to clang.
• The registers in the generated IR are 64-bit wide, so there are no optimizations for dealing with 32-bit words in cBPF.
• clang also emits code that does a lot of (clever) arithmetic, which would make the tool significantly more complex since most operations are not available in cBPF.

• converting eBPF to cBPF (the one used in seccomp-bpf) is not trivial.

• eBPF is a superset of cBPF, so all the features that are not available in cBPF would need an additional compilation phase.

It also would not be able to perform optimizations w.r.t. the order of the syscalls since there is no way to express this simply in C unless the compiler would generate the code in an optimized fashion, which defeats most of the purpose of offloading the optimization to clang.