Added a new Verifier class to the BPF compiler.

sandbox/linux/seccomp-bpf/verifier.cc

Index: sandbox/linux/seccomp-bpf/verifier.cc
diff --git a/sandbox/linux/seccomp-bpf/verifier.cc b/sandbox/linux/seccomp-bpf/verifier.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c005c514cb30a9e6b72bc1d91888207bac3ff53d
--- /dev/null
+++ b/sandbox/linux/seccomp-bpf/verifier.cc
@@ -0,0 +1,175 @@
+// 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) {

[Chris Evans, 2012/06/11 19:20:41]

I think you need to check against insn.k + sizeof(state->accumulator) ?
You'll also probably need to check than insn.k+4 does not integer overflow.

[Markus (顧孟勤), 2012/06/11 20:58:43]

I think, this logic is already correct, as we are checking both size and
alignment.

BPF is a /very/ restrictive language. And we are possibly even more restrictive.
We only allow 32bit reads and only on 32bit boundaries.
No need to add 4. As I said, the alignment check takes care of that.

+    // We only allow loading of properly aligned 32bit quantities.
+    memcpy(&state->accumulator,
+           reinterpret_cast<const char *>(&state->data) + insn.k,
+           4);

[Chris Evans, 2012/06/11 19:20:41]

Use sizeof(state->accumulator) instead of 4 ?

[Markus (顧孟勤), 2012/06/11 20:58:43]

I want to be really explicit that BPF is defined with 32bit data types for
everything.

But if you think that sizeof() is more readable and does a better job of
conveying the intent, you can persuade me.

+  } 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) {
+    state->ip += insn.k;

[Chris Evans, 2012/06/11 19:20:41]

Missing check? You check to see if the addition is in-bounds for the other jumps
types.

[Markus (顧孟勤), 2012/06/11 20:58:43]

Done.

+  } 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()) {
+    compilation_failure:
+      *err = "Invalid BPF_JMP instruction";
+      return;
+    }
+    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