Instead of outputting one BPF check per possible system call. Coalesce

sandbox/linux/seccomp-bpf/sandbox_bpf.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
 #include "sandbox/linux/seccomp-bpf/verifier.h"
 
 // The kernel gives us a sandbox, we turn it into a playground :-)
 // This is version 2 of the playground; version 1 was built on top of
 // pre-BPF seccomp mode.
@@ skipping 196 matching lines @@
   }
 
   // We can't handle stacked evaluators, yet. We'll get there eventually
   // though. Hang tight.
   if (evaluators_.size() != 1) {
     die("Not implemented");
   }
 
   // If the architecture doesn't match SECCOMP_ARCH, disallow the
   // system call.
-  std::vector<struct sock_filter> program;
+  Program program;
   program.push_back((struct sock_filter)
     BPF_STMT(BPF_LD+BPF_W+BPF_ABS, offsetof(struct arch_seccomp_data, arch)));
   program.push_back((struct sock_filter)
     BPF_JUMP(BPF_JMP+BPF_JEQ+BPF_K, SECCOMP_ARCH, 1, 0));
 
   // TODO: Instead of killing outright, we should raise a SIGSYS and
   //       report a useful error message. SIGKILL cannot be trapped by the
   //       debugger and essentially makes the program fail in a way that is
   //       almost impossible to debug.
   program.push_back((struct sock_filter)
@@ skipping 12 matching lines @@
     BPF_JUMP(BPF_JMP+BPF_JSET+BPF_K, 0x40000000, 1, 0));
 #else
   program.push_back((struct sock_filter)
     BPF_JUMP(BPF_JMP+BPF_JSET+BPF_K, 0x40000000, 0, 1));
 #endif
   // TODO: raise a suitable SIGSYS signal
   program.push_back((struct sock_filter)
     BPF_STMT(BPF_RET+BPF_K, SECCOMP_RET_KILL));
 #endif
 
-  // Evaluate all possible system calls and depending on their
-  // exit codes generate a BPF filter.
-  // This is very inefficient right now. We need to be much smarter
-  // eventually.
-  // We currently incur a O(N) overhead on each system call, with N
-  // being the number of system calls. It is easy to get this down to
-  // O(log_2(M)) with M being the number of system calls that need special
-  // treatment.
+  // Evaluate all possible system calls and group their ErrorCodes into
+  // ranges of identical codes.
+  Ranges ranges;
+  findRanges(&ranges);
+
+  // Compile the system call ranges to an optimized BPF program
+  rangesToBPF(&program, ranges);
+
+  // Everything that isn't allowed is forbidden. Eventually, we would
+  // like to have a way to log forbidden calls, when in debug mode.
+  program.push_back((struct sock_filter)
+    BPF_STMT(BPF_RET+BPF_K, SECCOMP_RET_ERRNO + SECCOMP_DENY_ERRNO));
+
+  // Make sure compilation resulted in BPF program that executes
+  // correctly. Otherwise, there is an internal error in our BPF compiler.
+  // There is really nothing the caller can do until the bug is fixed.
+  const char *err;
+  if (!Verifier::verifyBPF(program, evaluators_, &err)) {
+    die(err);
+  }
+
+  // Install BPF filter program
+  const struct sock_fprog prog = { program.size(), &program[0] };
+  if (prctl(PR_SET_NO_NEW_PRIVS, 1, 0, 0, 0) ||
+      prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, &prog)) {
+    goto filter_failed;
+  }
+
+  return;
+}
+
+void Sandbox::findRanges(Ranges *ranges) {
+  // Please note that "struct seccomp_data" defines system calls as a signed
+  // int32_t, but BPF instructions always operate on unsigned quantities. We
+  // deal with this disparity by enumerating from MIN_SYSCALL to MAX_SYSCALL,
+  // and then verifying that the rest of the number range (both positive and
+  // negative) all return the same ErrorCode.
+  // We don't actually iterate over all possible 2^32 values, though. We just
+  // perform spot checks at the boundaries.
   EvaluateSyscall evaluateSyscall = evaluators_.begin()->first;
-  for (int sysnum = MIN_SYSCALL; sysnum <= MAX_SYSCALL+1; ++sysnum) {
-    ErrorCode err = evaluateSyscall(sysnum);
+  uint32_t oldSysnum              = 0;
+  ErrorCode oldErr                = evaluateSyscall(oldSysnum);
+  for (uint32_t sysnum = std::max(1u, MIN_SYSCALL);
+       sysnum <= MAX_SYSCALL;
+       ++sysnum) {
+    ErrorCode err = evaluateSyscall(static_cast<int>(sysnum));
+    if (err != oldErr) {
+      ranges->push_back(Range(oldSysnum, sysnum-1, oldErr));
+      oldSysnum = sysnum;
+      oldErr    = err;
+    }
+  }
+  if (oldErr != evaluateSyscall(std::numeric_limits<int>::max()) ||

[jln (very slow on Chromium), 2012/06/08 22:38:21]

This makes it hard to review.

I would either:
- Have a comment somewhere, that we don't support negative system call numbers,
with the proper assert.
- Add asserts in case the system call number is negative or after MAX_SYSCALL
explaining this is untested.

I would prefer the first solution much more. Simplicity! :)

Also it's extremely unlikely that the caller will want to do that, ever, and I
would rather err on the side of catching mistakes.

I can already see bugs pop-up where callers expected "unknown" syscalls to be
denied by default.

[Markus (顧孟勤), 2012/06/09 00:30:58]

This is just a glorified assert() statement. Unfortunately, it's a little
verbose to actually write what we want to write.

I added another set of checks to the place where the user first hands us the
policy evaluator. And I explicitly deny negative system calls.

Hopefully, this addresses your concern. But if you need more, or if you think
there is something else that makes this code easier for you to review, please
speak up.

+      oldErr != evaluateSyscall(std::numeric_limits<int>::max() + 1) ||
+      oldErr != evaluateSyscall(std::numeric_limits<unsigned>::max())) {
+    die("Invalid seccomp policy");
+  }
+  ranges->push_back(
+    Range(oldSysnum, std::numeric_limits<unsigned>::max(), oldErr));
+}
+
+void Sandbox::rangesToBPF(Program *program, const Ranges& ranges) {
+  // TODO: We currently search linearly through all ranges. An improved
+  //       algorithm should be doing a binary search.
+
+  // System call ranges must cover the entire number range.
+  if (ranges.empty() ||
+      ranges.begin()->from != 0 ||
+      ranges.back().to != std::numeric_limits<unsigned>::max()) {
+  rangeError:
+    die("Invalid set of system call ranges");
+  }
+  uint32_t last = static_cast<uint32_t>(-1);

[jln (very slow on Chromium), 2012/06/08 22:38:21]

I know this is correct and allowed by standards, but it's more readable with
std::numeric_limits<uint32_t>::max (), no ?

If you think it makes the code below more readable, add a comment: "guaranteed
to be UINT32_MAX"

[Markus (顧孟勤), 2012/06/09 00:30:58]

I slightly changed the logic, and can thus avoid this issue.

+  for (Ranges::const_iterator iter = ranges.begin();
+       iter != ranges.end();
+       ++iter) {
+    // Ranges most be contiguous and monotonically increasing.

[jln (very slow on Chromium), 2012/06/08 22:38:21]

s/most/must

[Markus (顧孟勤), 2012/06/09 00:30:58]

Done.

+    if (iter->from > iter->to ||
+        iter->from != last+1) {

[jln (very slow on Chromium), 2012/06/08 22:38:21]

nit: last + 1 (spaces)

also add a comment explaining that last + 1 will be 0 on the first iteration.
I don't like having to rely on (defined but poorly known) behavior such as
unsigned overflow. Agreed it allows us to not unroll the loop so that's good.

+      goto rangeError;
+    }
+    last = iter->to;
+
+    // Convert ErrorCodes to return values that are acceptable for
+    // BPF filters.
     int ret;
-    switch (err) {
+    switch (iter->err) {
     case SB_INSPECT_ARG_1...SB_INSPECT_ARG_6:
       die("Not implemented");
     case SB_TRAP:
       ret = SECCOMP_RET_TRAP;
       break;
     case SB_ALLOWED:
       ret = SECCOMP_RET_ALLOW;
       break;
     default:
-      if (err >= static_cast<ErrorCode>(1) &&
-          err <= static_cast<ErrorCode>(4096)) {
+      if (iter->err >= static_cast<ErrorCode>(1) &&
+          iter->err <= static_cast<ErrorCode>(4096)) {
         // We limit errno values to a reasonable range. In fact, the Linux ABI
         // doesn't support errno values outside of this range.
-        ret = SECCOMP_RET_ERRNO + err;
+        ret = SECCOMP_RET_ERRNO + iter->err;
       } else {
         die("Invalid ErrorCode reported by sandbox system call evaluator");
       }
       break;
     }
-    if (sysnum <= MAX_SYSCALL) {
-      // We compute the default behavior (e.g. fail open or fail closed) by
-      // calling the system call evaluator with a system call bigger than
-      // MAX_SYSCALL.
-      // In other words, the very last iteration in our loop becomes the
-      // fallback case and we don't need to do any comparisons.
-      program.push_back((struct sock_filter)
-        BPF_JUMP(BPF_JMP+BPF_JEQ+BPF_K, sysnum, 0, 1));
+
+    // Emit BPF instructions matching this range.
+    if (iter->to != std::numeric_limits<unsigned>::max()) {
+      program->push_back((struct sock_filter)
+        BPF_JUMP(BPF_JMP+BPF_JGT+BPF_K, iter->to, 1, 0));
     }
-    program.push_back((struct sock_filter)
+    program->push_back((struct sock_filter)
       BPF_STMT(BPF_RET+BPF_K, ret));
   }
-
-  // Make sure compilation resulted in BPF program that executes
-  // correctly. Otherwise, there is an internal error in our BPF compiler.
-  // There is really nothing the caller can do until the bug is fixed.
-  const char *err;
-  if (!Verifier::verifyBPF(program, evaluators_, &err)) {
-    die(err);
-  }
-
-  // Install BPF filter program
-  const struct sock_fprog prog = { program.size(), &program[0] };
-  if (prctl(PR_SET_NO_NEW_PRIVS, 1, 0, 0, 0) ||
-      prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, &prog)) {
-    goto filter_failed;
-  }
-
   return;
 }
 
 void Sandbox::sigSys(int nr, siginfo_t *info, void *void_context) {
   if (nr != SIGSYS || info->si_code != SYS_SECCOMP || !void_context) {
     // die() can call LOG(FATAL). This is not normally async-signal safe
     // and can lead to bugs. We should eventually implement a different
     // logging and reporting mechanism that is safe to be called from
     // the sigSys() handler.
     die("Unexpected SIGSYS received");
@@ skipping 20 matching lines @@
   return;
 }
 
 
 bool Sandbox::suppressLogging_          = false;
 Sandbox::SandboxStatus Sandbox::status_ = STATUS_UNKNOWN;
 int    Sandbox::proc_fd_                = -1;
 Sandbox::Evaluators Sandbox::evaluators_;
 
 }  // namespace