Yes, this is a one-line change.
Once we've rewritten all jumps that went to instruction X to go to instruction
Y instead, we don't need to then check if we can also rewrite them to go to
instruction Z.
Tested with `--config=race` and Coverage enabled, which is the worst case
as far as performance goes:
```
$ make test BAZEL_TEST_OUTPUT=all BAZEL_OPTIONS='--config=race --collect_code_coverage --instrumentation_filter=//pkg/..,-//pkg/sentry/platform,-//pkg/ring0,-//pkg/coverage:coverage,-//pkg/sleep:sleep,-//pkg/sync:sync,-//pkg/syncevent:syncevent --test_arg=-test.bench=BenchmarkSentrySystrap/Postgres --test_arg=-test.benchtime=1x' TARGETS=//runsc/boot/filter:filter_bench_test
```
... with some extra timing code to check the time spent in
`optimizeJumpsToSmallestSetOfReturns` which reduced from ~750ms to ~120ms on
my machine.
PiperOrigin-RevId: 644195759
This introduces a `codeRemoval` type which acts as a tracker for removal of
instructions during execution of an optimizer.
This simplifies optimizers that use it, notably to avoid having to do
backwards iterations in all of them.
No heap allocations are performed unless code is actually removed, and only
one allocation is performed when code is to be removed.
PiperOrigin-RevId: 595575409
This changes one of the tradeoffs that this optimization pass used to do
to be more greedy when removing `return` instructions between passes.
Also change `rewriteAllJumpsToReturn` to not use closures.
Together, these changes save a whole **30 seconds** on e.g.
`socket_ip_udp_loopback_non_blocking_test`
with `gotsan` enabled (which really doesn't like repeatedly calling
functions like these, especially those with embedded closures).
PiperOrigin-RevId: 586053438
This adds an optimization pass which looks for jumps that go to return
statements that return the same value, and looks for opportunities to
make them jump to as few of these return statements as possible. This makes
the other return statements safely removable, which in turn minimizes the
program and allows more unconditional => conditional jump translations.
This optimization is particularly useful in syscall filter programs, which
tend to have a structure like follows (either through linear or binary
search):
```
.. if (foo) goto A else goto B
A: return rejected
B: if (bar) goto C else goto D
C: return rejected
D: if (baz) goto E else goto F
E: return rejected
F: return accepted
...
(Another set of rules in the program):
.. if (foo2) goto G else goto H
G: return accepted
H: if (bar2) goto I else goto J
I: return accepted
J: return rejected
```
After this optimization pass, this can be reduced to:
```
.. if (foo) goto J else goto B
B: if (bar) goto J else goto D
D: if (baz) goto J else goto I
...
.. if (foo2) goto I else goto H
H: if (bar2) goto I else goto J
I: return accepted
J: return rejected
```
Benchmarks:
```
│ before │ after │
│ sec/op │ sec/op vs base │
SentrySystrap 71.28n ± 5% 68.35n ± 9% ~ (p=0.222 n=140+141)
SentryKVM 59.31n ± 7% 57.93n ± 5% ~ (p=0.454 n=141)
NVProxyIoctl 97.63n ± 1% 97.13n ± 1% ~ (p=0.104 n=141+142)
│ before │ after │
│ build-sec │ build-sec vs base │
SentrySystrap 13.65m ± 0% 13.67m ± 0% ~ (p=0.144 n=142)
SentryKVM 16.26m ± 0% 16.31m ± 0% +0.29% (p=0.004 n=141+142)
NVProxyIoctl 42.50m ± 0% 42.55m ± 0% ~ (p=0.113 n=141+142)
│ before │ after │
│ compression-ratio │ compression-ratio vs base │
SentrySystrap 2.165 ± 0% 2.678 ± 0% +23.70% (p=0.000 n=142)
SentryKVM 2.132 ± 0% 2.630 ± 0% +23.36% (p=0.000 n=141+142)
NVProxyIoctl 1.958 ± 0% 2.275 ± 0% +16.19% (p=0.000 n=141+142)
│ before │ after │
│ gen-instr │ gen-instr vs base │
SentrySystrap 1.288k ± 0% 1.288k ± 0% ~ (p=1.000 n=142) ¹
SentryKVM 1.373k ± 0% 1.373k ± 0% ~ (p=1.000 n=141+142) ¹
NVProxyIoctl 2.250k ± 0% 2.250k ± 0% ~ (p=1.000 n=141+142) ¹
¹ all samples are equal
│ before │ after │
│ opt-instr │ opt-instr vs base │
SentrySystrap 595.0 ± 0% 481.0 ± 0% -19.16% (n=142)
SentryKVM 644.0 ± 0% 522.0 ± 0% -18.94% (n=141+142)
NVProxyIoctl 1149.0 ± 0% 989.0 ± 0% -13.93% (n=141+142)
│ before │ after │
│ opt-sec │ opt-sec vs base │
SentrySystrap 845.6µ ± 0% 107267.0µ ± 0% +12584.84% (p=0.000 n=142)
SentryKVM 927.2µ ± 0% 100663.4µ ± 1% +10756.86% (p=0.000 n=141+142)
NVProxyIoctl 2.118m ± 0% 399.395m ± 1% +18755.80% (p=0.000 n=141+142)
```
PiperOrigin-RevId: 584484054
This adds a `precompiledseccomp` library which provides tooling to compile
`seccomp-bpf` programs and generate Go source code that contains the
resulting bytecode embedded into it. In turn, this bytecode can be used in
Go libraries.
This avoids spending time compiling and optimizing `seccomp-bpf` programs
at runsc container creation time.
This library also contains support for "variables", which are `uint32`s whose
values are part of the seccomp filters but only known at runtime. To support
this, the program is compiled twice with placeholder values for these
variables, and we verify that the offsets at which these values show up in the
bytecode is consistent across these two compilation attempts.
PiperOrigin-RevId: 583117683
This change adds a `filter_fuzz_golden.bpf` BPF program that was generated
manually prior to my recent set of changes to seccomp bytecode and rule
optimization changes. It represents the "reference logic"; the new test
verifies that the current seccomp-bpf library produces BPF bytecode that
has the same behavior, using fuzz testing with full line-based coverage.
PiperOrigin-RevId: 582914572
This records the precise behavior of "return" instructions in the fragment,
rather than simply recording whether there was a "return" instruction at
all. In turn, this allows a caller to verify which return value is returned.
This is useful in an upcoming change to the BST struct, where the fragment
being recorded now has the potential to return (not just jump), and so it
becomes useful to check that the return values it can return are those we
expect.
PiperOrigin-RevId: 581422796
This is useful for value matching rules which look for the value of the `A`
register. If they do not modify this value, then we do not need to reload it
between sequential matchers over the same data.
PiperOrigin-RevId: 577266390
This creates a duplicate BPF interpreter which keeps track of the
instructions and input bytes it accesses.
Having such a mode is useful for the following reasons:
- For seccomp-bpf programs that the Sentry enforces from the sandboxed
application, this allows it to check whether the program is
deterministic based solely on the syscall number. For such syscalls,
we can cache the result of executing the program, and never run the
interpreter during syscall execution. (This optimization is not yet
implemented, but this change enables it to be.)
- For verification of correctness, coverage-based fuzzing is necessary.
I plan to implement a fuzz-based test which verifies that the
optimized and unoptimized versions of the same seccomp-bpf programs
have the same behavior, and ensuring that the corpus achieves full
coverage is necessary to ensure a good degree of correctness.
However, this mode is slower than it needs to when evaluating the
program in an application syscall (which is a very hot path), so this
has to live in a separate (sadly duplicated) function. The tests are
expanded to verify the for instrumented output, but also verify that
the "fast" version (aka the previous implementation) behaves the exact
same way, so this prevents the risk that code from one will drift away
behavior-wise.
To illustrate how much slower (not to mention it does allocations):
```
│ with_binary_order_removed │
│ sec/op │
Interpreter 14.26n ± 0%
InstrumentedInterpreter 98.37n ± 3%
```
PiperOrigin-RevId: 576562506
This removes the interface indirection from BPF evaluation, which is
a very hot path (runs for every application syscall for seccomp'd containers)
and simplifies the code in general.
```
│ initial │ hey_look_no_interfaces │
│ sec/op │ sec/op vs base │
Interpreter 26.31n ± 0% 21.12n ± 0% -19.73% (p=0.000 n=21+20)
```
PiperOrigin-RevId: 576375947
This is a very hot path, as it is used for packet filtering and all syscalls
of applications that set a seccomp-bpf filter on themselves.
This is useful to quantify the benefit of removing its use of interfaces,
and in the future if anything else can be done to improve it further.
Initial data:
```
│ initial │
│ sec/op │
Interpreter 26.31n ± 0%
```
PiperOrigin-RevId: 574201377
This adds a new `Record` function to `bpf.ProgramBuilder`, which returns a
function to stop recording that returns the "fragment" of the program made
of the instructions that were added between the time `Record` was called and
the time the stop function was called.
This fragment can in turn be interrogated for which `Outcomes` may happen
from executing it: returning a value, jumping to a label, jumping away from
the fragment, falling through.
This is useful while building complex BPF programs with nested rules. By
recording instructions added by a possibly-nested set of rules (the final
outcome of which is to jump to a known set of labels), we can now actually
verify the assertion that the instructions that were added indeed end up
jumping to one of the expected labels, and nothing else.
This is useful not just for safety but also optimization purposes. In an
upcoming refactor to argument matching code, I plan to add a "value matcher"
interface that renders rules that verify the value of the `A` register. Some
matchers may need to modify the `A` register in order to work, but others
don't. By checking whether the set of instructions modifies `A` or not, the
higher-level code can determine whether or not it needs to add code to reload
the value of the `A` register or not before moving on to the next matcher.
PiperOrigin-RevId: 571087694
This performs a few lossless optimizations passes over BPF programs.
This change does minimal testing and does not test for correctness.
The next change incorporates this optimizer in the program builder which *is*
tested for correctness.
It is not used anywhere yet, but when putting it on the Sentry filters:
```
│ before │ opt │
│ sec/op │ sec/op vs base │
SentrySystrap/Postgres/futex 88.82n ± 2% 81.29n ± 2% -8.48% (p=0.000 n=519+510)
SentrySystrap/Postgres/nanosleep 116.9n ± 19% 115.9n ± 17% ~ (p=0.859 n=350+317)
SentrySystrap/Postgres/sendmmsg 88.68n ± 1% 81.56n ± 1% -8.04% (n=519+510)
SentrySystrap/Postgres/fstat 24.47n ± 3% 24.31n ± 6% ~ (p=0.832 n=514+502)
[...]
SentrySystrap/Postgres-48 71.00n ± 8% 63.00n ± 6% -11.27% (p=0.002 n=183+181)
```
PiperOrigin-RevId: 570900358
`bpf.Instruction` is the same type as `linux.BPFInstruction`, except that it
uses the BPF instruction-to-string decoder to give a nice human-readable
stringification.
PiperOrigin-RevId: 570499020
Jing Chen
Etienne PerotandgVisor bot
Jing ChenandgVisor bot
Adin ScannellandgVisor bot
Ayush RanjanandgVisor bot
Rahat MahmoodandgVisor bot