Added a new Verifier class to the BPF compiler.

This class ensures that the generated BPF program does in fact represent the
filters that we were asked to compile. Having a verifier will allow us to make
more aggressive optimizations in the future without having to worry that we
generate invalid code.

BUG=130662
TEST=make && demo32 && demo64


Review URL: https://chromiumcodereview.appspot.com/10546041

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@142258 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 286 insertions, 8 deletions

diff --git a/sandbox/linux/seccomp-bpf/Makefile b/sandbox/linux/seccomp-bpf/Makefile
index 6519122..eb3cde6 100644
--- a/sandbox/linux/seccomp-bpf/Makefile
+++ b/sandbox/linux/seccomp-bpf/Makefile
@@ -2,7 +2,7 @@ CFLAGS = -g -O3 -Wall -Werror -Wextra -Wno-missing-field-initializers -fPIC -I.
 CPPFLAGS = -D_GNU_SOURCE -DSECCOMP_BPF_STANDALONE -iquote ../../..
 LDFLAGS = -g -lpthread
 DEPFLAGS = -MMD -MF .$@.d
-MODS := demo sandbox_bpf util
+MODS := demo sandbox_bpf util verifier
 OBJS64 := $(shell echo ${MODS} | xargs -n 1 | sed -e 's/$$/.o64/')
 OBJS32 := $(shell echo ${MODS} | xargs -n 1 | sed -e 's/$$/.o32/')
 ALL_OBJS = $(OBJS32) $(OBJS64)
diff --git a/sandbox/linux/seccomp-bpf/sandbox_bpf.cc b/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
index 043846d..ad87950 100644
--- a/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
+++ b/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
@@ -3,6 +3,7 @@
 // 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
@@ -296,7 +297,7 @@ void Sandbox::installFilter() {
   // O(log_2(M)) with M being the number of system calls that need special
   // treatment.
   EvaluateSyscall evaluateSyscall = evaluators_.begin()->first;
-  for (int sysnum = MIN_SYSCALL; sysnum <= MAX_SYSCALL; ++sysnum) {
+  for (uint32_t sysnum = MIN_SYSCALL; sysnum <= MAX_SYSCALL+1; ++sysnum) {
     ErrorCode err = evaluateSyscall(sysnum);
     int ret;
     switch (err) {
@@ -319,8 +320,15 @@ void Sandbox::installFilter() {
       }
       break;
     }
-    program->push_back((struct sock_filter)
-      BPF_JUMP(BPF_JMP+BPF_JEQ+BPF_K, sysnum, 0, 1));
+    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));
+    }
     program->push_back((struct sock_filter)
       BPF_STMT(BPF_RET+BPF_K, ret));
   }
@@ -331,6 +339,16 @@ void Sandbox::installFilter() {
   program->push_back((struct sock_filter)
     BPF_STMT(BPF_RET+BPF_K, SECCOMP_RET_KILL));
 
+  // 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.
+#ifndef NDEBUG
+  const char *err = NULL;
+  if (!Verifier::verifyBPF(*program, evaluators_, &err)) {
+    die(err);
+  }
+#endif
+
   // We want to be very careful in not imposing any requirements on the
   // policies that are set with setSandboxPolicy(). This means, as soon as
   // the sandbox is active, we shouldn't be relying on libraries that could
@@ -393,7 +411,6 @@ void Sandbox::sigSys(int nr, siginfo_t *info, void *void_context) {
 bool Sandbox::dryRun_                   = false;
 Sandbox::SandboxStatus Sandbox::status_ = STATUS_UNKNOWN;
 int    Sandbox::proc_fd_                = -1;
-std::vector<std::pair<Sandbox::EvaluateSyscall,
-                      Sandbox::EvaluateArguments> > Sandbox::evaluators_;
+Sandbox::Evaluators Sandbox::evaluators_;
 
 }  // namespace
diff --git a/sandbox/linux/seccomp-bpf/sandbox_bpf.h b/sandbox/linux/seccomp-bpf/sandbox_bpf.h
index f74072f7..0b66087 100644
--- a/sandbox/linux/seccomp-bpf/sandbox_bpf.h
+++ b/sandbox/linux/seccomp-bpf/sandbox_bpf.h
@@ -108,6 +108,10 @@ struct arch_seccomp_data {
 #ifdef SECCOMP_BPF_STANDALONE
 #define arraysize(x) sizeof(x)/sizeof(*(x)))
 #define HANDLE_EINTR TEMP_FAILURE_RETRY
+#define DISALLOW_IMPLICIT_CONSTRUCTORS(TypeName) \
+  TypeName();                                    \
+  TypeName(const TypeName&);                     \
+  void operator=(const TypeName&)
 #endif
 
 
@@ -115,6 +119,7 @@ namespace playground2 {
 
 class Sandbox {
   friend class Util;
+  friend class Verifier;
 
  public:
   enum SandboxStatus {
@@ -153,6 +158,7 @@ class Sandbox {
   typedef ErrorCode (*EvaluateSyscall)(int sysno);
   typedef int       (*EvaluateArguments)(int sysno, int arg,
                                          Constraint *constraint);
+  typedef std::vector<std::pair<EvaluateSyscall,EvaluateArguments> >Evaluators;
 
   // There are a lot of reasons why the Seccomp sandbox might not be available.
   // This could be because the kernel does not support Seccomp mode, or it
@@ -243,8 +249,7 @@ class Sandbox {
   static bool          dryRun_;
   static SandboxStatus status_;
   static int           proc_fd_;
-  static std::vector<std::pair<EvaluateSyscall,
-                               EvaluateArguments> > evaluators_;
+  static Evaluators    evaluators_;
 };
 
 }  // namespace
diff --git a/sandbox/linux/seccomp-bpf/verifier.cc b/sandbox/linux/seccomp-bpf/verifier.cc
new file mode 100644
index 0000000..3d100e6
--- /dev/null
+++ b/sandbox/linux/seccomp-bpf/verifier.cc
@@ -0,0 +1,179 @@
+// 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"
+
+
+namespace playground2 {
+
+bool Verifier::verifyBPF(const std::vector<struct sock_filter>& program,
+                         const Sandbox::Evaluators& evaluators,
+                         const char **err) {
+  *err = NULL;
+  if (evaluators.size() != 1) {
+    *err = "Not implemented";
+    return false;
+  }
+  Sandbox::EvaluateSyscall evaluateSyscall = evaluators.begin()->first;
+  for (int nr = MIN_SYSCALL-1; nr <= MAX_SYSCALL+1; ++nr) {
+    // We ideally want to iterate over the full system call range and values
+    // just above and just below this range. This gives us the full result set
+    // of the "evaluators".
+    // On Intel systems, this can fail in a surprising way, as a cleared bit 30
+    // indicates either i386 or x86-64; and a set bit 30 indicates x32. And
+    // unless we pay attention to setting this bit correctly, an early check in
+    // our BPF program will make us fail with a misleading error code.
+#if defined(__i386__) || defined(__x86_64__)
+#if defined(__x86_64__) && defined(__ILP32__)
+    int sysnum = nr |  0x40000000;
+#else
+    int sysnum = nr & ~0x40000000;
+#endif
+#else
+    int sysnum = nr;
+#endif
+
+    struct arch_seccomp_data data = { sysnum, SECCOMP_ARCH };
+    uint32_t expectedRet;
+    Sandbox::ErrorCode code = evaluateSyscall(sysnum);
+    switch (code) {
+    case Sandbox::SB_TRAP:
+      expectedRet = SECCOMP_RET_TRAP;
+      break;
+    case Sandbox::SB_ALLOWED:
+      expectedRet = SECCOMP_RET_ALLOW;
+      break;
+    case Sandbox::SB_INSPECT_ARG_1...Sandbox::SB_INSPECT_ARG_6:
+      *err = "Not implemented";
+      return false;
+    default:
+      if (code >= 1 && code < 4096) {
+        expectedRet = SECCOMP_RET_ERRNO + static_cast<int>(code);
+      } else {
+        *err = "Invalid errno value";
+        return false;
+      }
+      break;
+    }
+    uint32_t computedRet = evaluateBPF(program, data, err);
+    if (*err) {
+      return false;
+    } else if (computedRet != expectedRet) {
+      *err = "Exit code from BPF program doesn't match";
+      return false;
+    }
+  }
+  return true;
+}
+
+uint32_t Verifier::evaluateBPF(const std::vector<struct sock_filter>& program,
+                               const struct arch_seccomp_data& data,
+                               const char **err) {
+  *err = NULL;
+  for (State state(program, data); !*err; ++state.ip) {
+    if (state.ip >= program.size()) {
+      *err = "Invalid instruction pointer in BPF program";
+      break;
+    }
+    const struct sock_filter& insn = program[state.ip];
+    switch (BPF_CLASS(insn.code)) {
+    case BPF_LD:
+      ld(&state, insn, err);
+      break;
+    case BPF_JMP:
+      jmp(&state, insn, err);
+      break;
+    case BPF_RET:
+      return ret(&state, insn, err);
+    default:
+      *err = "Unexpected instruction in BPF program";
+      break;
+    }
+  }
+  return 0;
+}
+
+void Verifier::ld(State *state, const struct sock_filter& insn,
+                  const char **err) {
+  if (BPF_SIZE(insn.code) != BPF_W ||
+      BPF_MODE(insn.code) != BPF_ABS) {
+    *err = "Invalid BPF_LD instruction";
+    return;
+  }
+  if (insn.k < sizeof(struct arch_seccomp_data) && (insn.k & 3) == 0) {
+    // We only allow loading of properly aligned 32bit quantities.
+    memcpy(&state->accumulator,
+           reinterpret_cast<const char *>(&state->data) + insn.k,
+           4);
+  } else {
+    *err = "Invalid operand in BPF_LD instruction";
+    return;
+  }
+  state->accIsValid = true;
+  return;
+}
+
+void Verifier::jmp(State *state, const struct sock_filter& insn,
+                   const char **err) {
+  if (BPF_OP(insn.code) == BPF_JA) {
+    if (state->ip + insn.k + 1 >= state->program.size() ||
+        state->ip + insn.k + 1 <= state->ip) {
+    compilation_failure:
+      *err = "Invalid BPF_JMP instruction";
+      return;
+    }
+    state->ip += insn.k;
+  } else {
+    if (BPF_SRC(insn.code) != BPF_K ||
+        !state->accIsValid ||
+        state->ip + insn.jt + 1 >= state->program.size() ||
+        state->ip + insn.jf + 1 >= state->program.size()) {
+      goto compilation_failure;
+    }
+    switch (BPF_OP(insn.code)) {
+    case BPF_JEQ:
+      if (state->accumulator == insn.k) {
+        state->ip += insn.jt;
+      } else {
+        state->ip += insn.jf;
+      }
+      break;
+    case BPF_JGT:
+      if (state->accumulator > insn.k) {
+        state->ip += insn.jt;
+      } else {
+        state->ip += insn.jf;
+      }
+      break;
+    case BPF_JGE:
+      if (state->accumulator >= insn.k) {
+        state->ip += insn.jt;
+      } else {
+        state->ip += insn.jf;
+      }
+      break;
+    case BPF_JSET:
+      if (state->accumulator & insn.k) {
+        state->ip += insn.jt;
+      } else {
+        state->ip += insn.jf;
+      }
+      break;
+    default:
+      goto compilation_failure;
+    }
+  }
+}
+
+uint32_t Verifier::ret(State *state, const struct sock_filter& insn,
+                       const char **err) {
+  if (BPF_SRC(insn.code) != BPF_K) {
+    *err = "Invalid BPF_RET instruction";
+    return 0;
+  }
+  return insn.k;
+}
+
+}  // namespace
diff --git a/sandbox/linux/seccomp-bpf/verifier.h b/sandbox/linux/seccomp-bpf/verifier.h
new file mode 100644
index 0000000..a4e5086
--- /dev/null
+++ b/sandbox/linux/seccomp-bpf/verifier.h
@@ -0,0 +1,75 @@
+// 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.
+
+#ifndef VERIFIER_H__
+#define VERIFIER_H__
+
+#include <linux/filter.h>
+
+#include <utility>
+#include <vector>
+
+#include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
+
+
+namespace playground2 {
+
+class Verifier {
+ public:
+  // Evaluate the BPF program for all possible inputs and verify that it
+  // computes the correct result. We use the "evaluators" to determine
+  // the full set of possible inputs that we have to iterate over.
+  // Returns success, if the BPF filter accurately reflects the rules
+  // set by the "evaluators".
+  // Upon success, "err" is set to NULL. Upon failure, it contains a static
+  // error message that does not need to be free()'d.
+  static bool verifyBPF(const std::vector<struct sock_filter>& program,
+                        const Sandbox::Evaluators& evaluators,
+                        const char **err);
+
+  // Evaluate a given BPF program for a particular set of system call
+  // parameters. If evaluation failed for any reason, "err" will be set to
+  // a non-NULL error string. Otherwise, the BPF program's result will be
+  // returned by the function and "err" is NULL.
+  // We do not actually implement the full BPF state machine, but only the
+  // parts that can actually be generated by our BPF compiler. If this code
+  // is used for purposes other than verifying the output of the sandbox's
+  // BPF compiler, we might have to extend this BPF interpreter.
+  static uint32_t evaluateBPF(const std::vector<struct sock_filter>& program,
+                              const struct arch_seccomp_data& data,
+                              const char **err);
+
+ private:
+  struct State {
+    State(const std::vector<struct sock_filter>& p,
+          const struct arch_seccomp_data& d) :
+      program(p),
+      data(d),
+      ip(0),
+      accumulator(0),
+      accIsValid(false) {
+    }
+    const std::vector<struct sock_filter>& program;
+    const struct arch_seccomp_data&        data;
+    unsigned int                           ip;
+    uint32_t                               accumulator;
+    bool                                   accIsValid;
+
+   private:
+    DISALLOW_IMPLICIT_CONSTRUCTORS(State);
+  };
+
+  static void     ld (State *state, const struct sock_filter& insn,
+                      const char **err);
+  static void     jmp(State *state, const struct sock_filter& insn,
+                      const char **err);
+  static uint32_t ret(State *state, const struct sock_filter& insn,
+                      const char **err);
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(Verifier);
+};
+
+}  // namespace
+
+#endif  // VERIFIER_H__
diff --git a/sandbox/sandbox.gyp b/sandbox/sandbox.gyp
index 613e6e3..4158c01 100644
--- a/sandbox/sandbox.gyp
+++ b/sandbox/sandbox.gyp
@@ -159,6 +159,8 @@
               'sources': [
                 'linux/seccomp-bpf/sandbox_bpf.cc',
                 'linux/seccomp-bpf/sandbox_bpf.h',
+                'linux/seccomp-bpf/verifier.cc',
+                'linux/seccomp-bpf/verifier.h',
               ],
               'dependencies': [
                 '../base/base.gyp:base',