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..6e706960441c392fb730afc92c50d72c5b88fc6d
--- /dev/null
+++ b/sandbox/linux/seccomp-bpf/verifier.cc
@@ -0,0 +1,145 @@
+// 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 {
+
+void Verifier::verifyBPF(const std::vector<struct sock_filter>& program,
+                         const Sandbox::Evaluators& evaluators) {
+  // Evaluate the BPF filter program for all possible inputs and

[jln (very slow on Chromium), 2012/06/07 22:55:17]

Could you document the API in the interface instead?

+  // verify that it computes the correct result.

[jln (very slow on Chromium), 2012/06/07 22:55:17]

We will probably never iterate over all possible input, especially with
arguments, right?

There is some room to iterate over some really large sets, but that especially
works if we make this part of a unit test, rather than something that will run
every time we compile a new policy.

+  // We do not implement the full BPF syntax, but only the parts that
+  // can actually be generated by our BPF compiler. If we encounter an
+  // unsupported instruction, we fail.
+  // This method is called after compiling the entire BPF filter
+  // program. It either completes without making any state changes, or
+  // it terminates the program by calling Sandbox::die().

[jln (very slow on Chromium), 2012/06/07 22:55:17]

See my remark about dying in the interface

+  if (evaluators.size() != 1) {
+    Sandbox::die("Not implemented");
+  }
+  Sandbox::EvaluateSyscall evaluateSyscall = evaluators.begin()->first;
+  for (int sysnum = MIN_SYSCALL-1; sysnum <= MAX_SYSCALL+1; ++sysnum) {
+    // Iterate through the entire BPF program until we either return
+    // or hit an invalid instruction pointer.
+    for (State state(program, sysnum, evaluateSyscall(sysnum));
+         ;

[jln (very slow on Chromium), 2012/06/07 22:55:17]

This is roughly an emulator. Can be very useful. Do you mind having this as a
separate function ?

+         ++state.ip) {
+      if (state.ip >= program.size()) {
+        Sandbox::die("Invalid instruction pointer in BPF program");
+      }
+      const struct sock_filter& insn = program[state.ip];
+      switch (BPF_CLASS(insn.code)) {
+      case BPF_LD:
+        ld(&state, insn);
+        break;
+      case BPF_JMP:
+        jmp(&state, insn);
+        break;
+      case BPF_RET:
+        ret(&state, insn);
+        goto returned;
+      default:
+        Sandbox::die("Unexpected instruction in BPF program");
+      }
+    }
+  returned:;
+  }
+}
+
+void Verifier::ld(State *state, const struct sock_filter& insn) {
+  if (BPF_SIZE(insn.code) != BPF_W ||
+      BPF_MODE(insn.code) != BPF_ABS) {
+  compilation_failure:
+    Sandbox::die("Invalid BPF_LD instruction");
+  }
+  switch (insn.k) {
+  case offsetof(struct arch_seccomp_data, arch):
+    state->accumulator = SECCOMP_ARCH;
+    break;
+  case offsetof(struct arch_seccomp_data, nr):
+    state->accumulator = state->sysnum;
+    break;
+  default:
+    goto compilation_failure;
+  }
+  state->accIsValid = true;
+}
+
+void Verifier::jmp(State *state, const struct sock_filter& insn) {
+  if (BPF_OP(insn.code) == BPF_JA) {
+    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()) {
+    compilation_failure:
+      Sandbox::die("Invalid BPF_JMP instruction");
+    }
+    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;
+    }
+  }
+}
+
+void Verifier::ret(State *state, const struct sock_filter& insn) {
+  if (BPF_SRC(insn.code) != BPF_K) {
+  compilation_failure:
+    Sandbox::die("Invalid BPF_RET instruction");
+  }
+  switch (state->err) {
+  case Sandbox::SB_TRAP:
+    if (insn.k != SECCOMP_RET_TRAP) {
+      goto compilation_failure;
+    }
+    break;
+  case Sandbox::SB_ALLOWED:
+    if (insn.k != SECCOMP_RET_ALLOW) {
+      goto compilation_failure;
+    }
+    break;
+  case Sandbox::SB_INSPECT_ARG_1...Sandbox::SB_INSPECT_ARG_6:
+    Sandbox::die("Not implemented");
+    break;
+  default:
+    if (insn.k != SECCOMP_RET_ERRNO + state->err) {
+      goto compilation_failure;
+    }
+    break;
+  }
+}
+
+}  // namespace