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

sandbox/linux/seccomp-bpf/sandbox_bpf.cc

Index: sandbox/linux/seccomp-bpf/sandbox_bpf.cc
diff --git a/sandbox/linux/seccomp-bpf/sandbox_bpf.cc b/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
index 573d86e10c606e717b6b06fa16ac9a04decb9e32..937d9050b9b83f290222e7a2689fa53d554599a2 100644
--- a/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
+++ b/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
@@ -214,7 +214,7 @@ void Sandbox::installFilter() {
 
   // 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)
@@ -247,19 +247,93 @@ void Sandbox::installFilter() {
     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:
@@ -269,44 +343,25 @@ void Sandbox::installFilter() {
       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;
 }