Add domain-specific language for BPF policies

This CL adds basic support for equality testing of system call
arguments, and conjunctive and disjunctive combinations of tests.

BUG=375497

Review URL: https://codereview.chromium.org/299743002

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

9 files changed, 865 insertions, 0 deletions

diff --git a/sandbox/linux/BUILD.gn b/sandbox/linux/BUILD.gn
index faf25cd..9f481d6 100644
--- a/sandbox/linux/BUILD.gn
+++ b/sandbox/linux/BUILD.gn
@@ -92,6 +92,8 @@ test("sandbox_linux_unittests") {
   }
   if (use_seccomp_bpf) {
     sources += [
+      "bpf_dsl/bpf_dsl_unittest.cc",
+      "bpf_dsl/cons_unittest.cc",
       "seccomp-bpf-helpers/baseline_policy_unittest.cc",
       "seccomp-bpf/bpf_tests_unittest.cc",
       "seccomp-bpf/codegen_unittest.cc",
@@ -129,6 +131,9 @@ test("sandbox_linux_unittests") {
 
 component("seccomp_bpf") {
   sources = [
+    "bpf_dsl/bpf_dsl.cc",
+    "bpf_dsl/bpf_dsl.h",
+    "bpf_dsl/cons.h",
     "seccomp-bpf/basicblock.cc",
     "seccomp-bpf/basicblock.h",
     "seccomp-bpf/codegen.cc",
diff --git a/sandbox/linux/bpf_dsl/DEPS b/sandbox/linux/bpf_dsl/DEPS
new file mode 100644
index 0000000..01595a4
--- /dev/null
+++ b/sandbox/linux/bpf_dsl/DEPS
@@ -0,0 +1,3 @@
+include_rules = [
+  "+sandbox/linux/seccomp-bpf",
+]
diff --git a/sandbox/linux/bpf_dsl/bpf_dsl.cc b/sandbox/linux/bpf_dsl/bpf_dsl.cc
new file mode 100644
index 0000000..66cd09c
--- /dev/null
+++ b/sandbox/linux/bpf_dsl/bpf_dsl.cc
@@ -0,0 +1,278 @@
+// Copyright 2014 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/bpf_dsl/bpf_dsl.h"
+
+#include <errno.h>
+
+#include "base/logging.h"
+#include "base/memory/ref_counted.h"
+#include "sandbox/linux/seccomp-bpf/errorcode.h"
+#include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
+
+using namespace sandbox::bpf_dsl::internal;
+typedef ::sandbox::Trap::TrapFnc TrapFnc;
+
+namespace sandbox {
+namespace bpf_dsl {
+namespace {
+
+class AllowResultExprImpl : public ResultExprImpl {
+ public:
+  AllowResultExprImpl() {}
+  virtual ErrorCode Compile(SandboxBPF* sb) const OVERRIDE {
+    return ErrorCode(ErrorCode::ERR_ALLOWED);
+  }
+
+ private:
+  virtual ~AllowResultExprImpl() {}
+  DISALLOW_COPY_AND_ASSIGN(AllowResultExprImpl);
+};
+
+class ErrorResultExprImpl : public ResultExprImpl {
+ public:
+  explicit ErrorResultExprImpl(int err) : err_(err) {
+    CHECK(err_ >= ErrorCode::ERR_MIN_ERRNO && err_ <= ErrorCode::ERR_MAX_ERRNO);
+  }
+  virtual ErrorCode Compile(SandboxBPF* sb) const OVERRIDE {
+    return ErrorCode(err_);
+  }
+
+ private:
+  virtual ~ErrorResultExprImpl() {}
+  int err_;
+  DISALLOW_COPY_AND_ASSIGN(ErrorResultExprImpl);
+};
+
+class TrapResultExprImpl : public ResultExprImpl {
+ public:
+  TrapResultExprImpl(TrapFnc func, void* arg) : func_(func), arg_(arg) {
+    DCHECK(func_);
+  }
+  virtual ErrorCode Compile(SandboxBPF* sb) const OVERRIDE {
+    return sb->Trap(func_, arg_);
+  }
+
+ private:
+  virtual ~TrapResultExprImpl() {}
+  TrapFnc func_;
+  void* arg_;
+  DISALLOW_COPY_AND_ASSIGN(TrapResultExprImpl);
+};
+
+class IfThenResultExprImpl : public ResultExprImpl {
+ public:
+  IfThenResultExprImpl(BoolExpr cond,
+                       ResultExpr then_result,
+                       ResultExpr else_result)
+      : cond_(cond), then_result_(then_result), else_result_(else_result) {}
+  virtual ErrorCode Compile(SandboxBPF* sb) const OVERRIDE {
+    return cond_->Compile(
+        sb, then_result_->Compile(sb), else_result_->Compile(sb));
+  }
+
+ private:
+  virtual ~IfThenResultExprImpl() {}
+  BoolExpr cond_;
+  ResultExpr then_result_;
+  ResultExpr else_result_;
+  DISALLOW_COPY_AND_ASSIGN(IfThenResultExprImpl);
+};
+
+class PrimitiveBoolExprImpl : public BoolExprImpl {
+ public:
+  PrimitiveBoolExprImpl(int argno,
+                        ErrorCode::ArgType is_32bit,
+                        ErrorCode::Operation op,
+                        uint64_t value)
+      : argno_(argno), is_32bit_(is_32bit), op_(op), value_(value) {}
+  virtual ErrorCode Compile(SandboxBPF* sb,
+                            ErrorCode true_ec,
+                            ErrorCode false_ec) const OVERRIDE {
+    return sb->Cond(argno_, is_32bit_, op_, value_, true_ec, false_ec);
+  }
+
+ private:
+  virtual ~PrimitiveBoolExprImpl() {}
+  int argno_;
+  ErrorCode::ArgType is_32bit_;
+  ErrorCode::Operation op_;
+  uint64_t value_;
+  DISALLOW_COPY_AND_ASSIGN(PrimitiveBoolExprImpl);
+};
+
+class NegateBoolExprImpl : public BoolExprImpl {
+ public:
+  explicit NegateBoolExprImpl(BoolExpr cond) : cond_(cond) {}
+  virtual ErrorCode Compile(SandboxBPF* sb,
+                            ErrorCode true_ec,
+                            ErrorCode false_ec) const OVERRIDE {
+    return cond_->Compile(sb, false_ec, true_ec);
+  }
+
+ private:
+  virtual ~NegateBoolExprImpl() {}
+  BoolExpr cond_;
+  DISALLOW_COPY_AND_ASSIGN(NegateBoolExprImpl);
+};
+
+class AndBoolExprImpl : public BoolExprImpl {
+ public:
+  AndBoolExprImpl(BoolExpr lhs, BoolExpr rhs) : lhs_(lhs), rhs_(rhs) {}
+  virtual ErrorCode Compile(SandboxBPF* sb,
+                            ErrorCode true_ec,
+                            ErrorCode false_ec) const OVERRIDE {
+    return lhs_->Compile(sb, rhs_->Compile(sb, true_ec, false_ec), false_ec);
+  }
+
+ private:
+  virtual ~AndBoolExprImpl() {}
+  BoolExpr lhs_, rhs_;
+  DISALLOW_COPY_AND_ASSIGN(AndBoolExprImpl);
+};
+
+class OrBoolExprImpl : public BoolExprImpl {
+ public:
+  OrBoolExprImpl(BoolExpr lhs, BoolExpr rhs) : lhs_(lhs), rhs_(rhs) {}
+  virtual ErrorCode Compile(SandboxBPF* sb,
+                            ErrorCode true_ec,
+                            ErrorCode false_ec) const OVERRIDE {
+    return lhs_->Compile(sb, true_ec, rhs_->Compile(sb, true_ec, false_ec));
+  }
+
+ private:
+  virtual ~OrBoolExprImpl() {}
+  BoolExpr lhs_, rhs_;
+  DISALLOW_COPY_AND_ASSIGN(OrBoolExprImpl);
+};
+
+}  // namespace
+
+namespace internal {
+
+BoolExpr ArgEq(int num, size_t size, uint64_t mask, uint64_t val) {
+  CHECK(num >= 0 && num < 6);
+  CHECK(size >= 1 && size <= 8);
+  CHECK_NE(0U, mask) << "zero mask doesn't make sense";
+  CHECK_EQ(val, val & mask) << "val contains masked out bits";
+
+  // TODO(mdempsky): Should we just always use TP_64BIT?
+  const ErrorCode::ArgType arg_type =
+      (size <= 4) ? ErrorCode::TP_32BIT : ErrorCode::TP_64BIT;
+
+  if (mask == static_cast<uint64_t>(-1)) {
+    // Arg == Val
+    return BoolExpr(new const PrimitiveBoolExprImpl(
+        num, arg_type, ErrorCode::OP_EQUAL, val));
+  } else if (mask == val) {
+    // (Arg & Mask) == Mask
+    return BoolExpr(new const PrimitiveBoolExprImpl(
+        num, arg_type, ErrorCode::OP_HAS_ALL_BITS, mask));
+  } else if (val == 0) {
+    // (Arg & Mask) == 0, which is semantically equivalent to !((arg & mask) !=
+    // 0).
+    return !BoolExpr(new const PrimitiveBoolExprImpl(
+        num, arg_type, ErrorCode::OP_HAS_ANY_BITS, mask));
+  } else {
+    CHECK(false) << "Unimplemented ArgEq case";
+    return BoolExpr();
+  }
+}
+
+}  // namespace internal
+
+ResultExpr Allow() {
+  return ResultExpr(new const AllowResultExprImpl());
+}
+
+ResultExpr Error(int err) {
+  return ResultExpr(new const ErrorResultExprImpl(err));
+}
+
+ResultExpr Trap(TrapFnc trap_func, void* aux) {
+  return ResultExpr(new const TrapResultExprImpl(trap_func, aux));
+}
+
+BoolExpr operator!(BoolExpr cond) {
+  return BoolExpr(new const NegateBoolExprImpl(cond));
+}
+
+BoolExpr operator&&(BoolExpr lhs, BoolExpr rhs) {
+  return BoolExpr(new const AndBoolExprImpl(lhs, rhs));
+}
+
+BoolExpr operator||(BoolExpr lhs, BoolExpr rhs) {
+  return BoolExpr(new const OrBoolExprImpl(lhs, rhs));
+}
+
+Elser If(BoolExpr cond, ResultExpr then_result) {
+  return Elser(Cons<Elser::Clause>::List()).ElseIf(cond, then_result);
+}
+
+Elser::Elser(Cons<Clause>::List clause_list) : clause_list_(clause_list) {
+}
+
+Elser::Elser(const Elser& elser) : clause_list_(elser.clause_list_) {
+}
+
+Elser::~Elser() {
+}
+
+Elser Elser::ElseIf(BoolExpr cond, ResultExpr then_result) const {
+  return Elser(
+      Cons<Clause>::Make(std::make_pair(cond, then_result), clause_list_));
+}
+
+ResultExpr Elser::Else(ResultExpr else_result) const {
+  // We finally have the default result expression for this
+  // if/then/else sequence.  Also, we've already accumulated all
+  // if/then pairs into a list of reverse order (i.e., lower priority
+  // conditions are listed before higher priority ones).  E.g., an
+  // expression like
+  //
+  //    If(b1, e1).ElseIf(b2, e2).ElseIf(b3, e3).Else(e4)
+  //
+  // will have built up a list like
+  //
+  //    [(b3, e3), (b2, e2), (b1, e1)].
+  //
+  // Now that we have e4, we can walk the list and create a ResultExpr
+  // tree like:
+  //
+  //    expr = e4
+  //    expr = (b3 ? e3 : expr) = (b3 ? e3 : e4)
+  //    expr = (b2 ? e2 : expr) = (b2 ? e2 : (b3 ? e3 : e4))
+  //    expr = (b1 ? e1 : expr) = (b1 ? e1 : (b2 ? e2 : (b3 ? e3 : e4)))
+  //
+  // and end up with an appropriately chained tree.
+
+  ResultExpr expr = else_result;
+  for (Cons<Clause>::List it = clause_list_; it; it = it->tail()) {
+    Clause clause = it->head();
+    expr = ResultExpr(
+        new const IfThenResultExprImpl(clause.first, clause.second, expr));
+  }
+  return expr;
+}
+
+ResultExpr SandboxBPFDSLPolicy::InvalidSyscall() const {
+  return Error(ENOSYS);
+}
+
+ErrorCode SandboxBPFDSLPolicy::EvaluateSyscall(SandboxBPF* sb,
+                                               int sysno) const {
+  return EvaluateSyscall(sysno)->Compile(sb);
+}
+
+ErrorCode SandboxBPFDSLPolicy::InvalidSyscall(SandboxBPF* sb) const {
+  return InvalidSyscall()->Compile(sb);
+}
+
+ResultExpr SandboxBPFDSLPolicy::Trap(::sandbox::Trap::TrapFnc trap_func,
+                                     void* aux) {
+  return bpf_dsl::Trap(trap_func, aux);
+}
+
+}  // namespace bpf_dsl
+}  // namespace sandbox
diff --git a/sandbox/linux/bpf_dsl/bpf_dsl.h b/sandbox/linux/bpf_dsl/bpf_dsl.h
new file mode 100644
index 0000000..d46102a
--- /dev/null
+++ b/sandbox/linux/bpf_dsl/bpf_dsl.h
@@ -0,0 +1,246 @@
+// Copyright 2014 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 SANDBOX_LINUX_BPF_DSL_BPF_DSL_H_
+#define SANDBOX_LINUX_BPF_DSL_BPF_DSL_H_
+
+#include <stdint.h>
+
+#include <utility>
+
+#include "base/macros.h"
+#include "base/memory/ref_counted.h"
+#include "sandbox/linux/bpf_dsl/cons.h"
+#include "sandbox/linux/seccomp-bpf/sandbox_bpf_policy.h"
+#include "sandbox/linux/seccomp-bpf/trap.h"
+#include "sandbox/sandbox_export.h"
+
+namespace sandbox {
+class ErrorCode;
+class SandboxBPF;
+}
+
+// The sandbox::bpf_dsl namespace provides a domain-specific language
+// to make writing BPF policies more expressive.  In general, the
+// object types all have value semantics (i.e., they can be copied
+// around, returned from or passed to function calls, etc. without any
+// surprising side effects), though not all support assignment.
+//
+// An idiomatic and demonstrative (albeit silly) example of this API
+// would be:
+//
+//      #include "sandbox/linux/bpf_dsl/bpf_dsl.h"
+//
+//      using namespace sandbox::bpf_dsl;
+//
+//      class SillyPolicy : public SandboxBPFDSLPolicy {
+//       public:
+//        SillyPolicy() {}
+//        virtual ~SillyPolicy() {}
+//        virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+//          if (sysno == __NR_fcntl) {
+//            Arg<int> fd(0), cmd(1);
+//            Arg<unsigned long> flags(2);
+//            const unsigned long kBadFlags = ~(O_ACCMODE | O_NONBLOCK);
+//            return If(fd == 0 && cmd == F_SETFL && (flags & kBadFlags) == 0,
+//                      Allow())
+//                .ElseIf(cmd == F_DUPFD || cmd == F_DUPFD_CLOEXEC,
+//                        Error(EMFILE))
+//                .Else(Trap(SetFlagHandler, NULL));
+//          } else {
+//            return Allow();
+//          }
+//        }
+//
+//       private:
+//        DISALLOW_COPY_AND_ASSIGN(SillyPolicy);
+//      };
+//
+// More generally, the DSL currently supports the following grammar:
+//
+//   result = Allow() | Error(errno) | Trap(trap_func, arg)
+//          | If(bool, result)[.ElseIf(bool, result)].Else(result)
+//   bool   = arg == val | (arg & mask) == mask | (arg & mask) == 0
+//          | !bool | bool && bool | bool || bool
+//
+// The semantics of each function and operator are intended to be
+// intuitive, but are described in more detail below.
+//
+// (Credit to Sean Parent's "Inheritance is the Base Class of Evil"
+// talk at Going Native 2013 for promoting value semantics via shared
+// pointers to immutable state.)
+
+namespace sandbox {
+namespace bpf_dsl {
+
+// Forward declarations of classes; see below for proper documentation.
+class Elser;
+namespace internal {
+class ResultExprImpl;
+class BoolExprImpl;
+}
+
+// ResultExpr is an opaque reference to an immutable result expression tree.
+typedef scoped_refptr<const internal::ResultExprImpl> ResultExpr;
+
+// BoolExpr is an opaque reference to an immutable boolean expression tree.
+typedef scoped_refptr<const internal::BoolExprImpl> BoolExpr;
+
+// Helper class to make writing policies easier.
+class SANDBOX_EXPORT SandboxBPFDSLPolicy : public SandboxBPFPolicy {
+ public:
+  SandboxBPFDSLPolicy() : SandboxBPFPolicy() {}
+  virtual ~SandboxBPFDSLPolicy() {}
+
+  // User extension point for writing custom sandbox policies.
+  virtual ResultExpr EvaluateSyscall(int sysno) const = 0;
+
+  // Optional overload for specifying alternate behavior for invalid
+  // system calls.  The default is to return ENOSYS.
+  virtual ResultExpr InvalidSyscall() const;
+
+  // Override implementations from SandboxBPFPolicy.  Marked as FINAL
+  // to prevent mixups with child classes accidentally overloading
+  // these instead of the above methods.
+  virtual ErrorCode EvaluateSyscall(SandboxBPF* sb,
+                                    int sysno) const OVERRIDE FINAL;
+  virtual ErrorCode InvalidSyscall(SandboxBPF* sb) const OVERRIDE FINAL;
+
+  // Helper method so policies can just write Trap(func, aux).
+  static ResultExpr Trap(::sandbox::Trap::TrapFnc trap_func, void* aux);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(SandboxBPFDSLPolicy);
+};
+
+// Allow specifies a result that the system call should be allowed to
+// execute normally.
+SANDBOX_EXPORT ResultExpr Allow();
+
+// Error specifies a result that the system call should fail with
+// error number |err|.  As a special case, Error(0) will result in the
+// system call appearing to have succeeded, but without having any
+// side effects.
+SANDBOX_EXPORT ResultExpr Error(int err);
+
+// Trap specifies a result that the system call should be handled by
+// trapping back into userspace and invoking |trap_func|, passing
+// |aux| as the second parameter.
+SANDBOX_EXPORT ResultExpr Trap(::sandbox::Trap::TrapFnc trap_func, void* aux);
+
+template <typename T>
+class SANDBOX_EXPORT Arg {
+ public:
+  // Initializes the Arg to represent the |num|th system call
+  // argument (indexed from 0), which is of type |T|.
+  explicit Arg(int num) : num_(num), mask_(-1) {}
+
+  Arg(const Arg& arg) : num_(arg.num_), mask_(arg.mask_) {}
+
+  // Returns an Arg representing the current argument, but after
+  // bitwise-and'ing it with |rhs|.
+  Arg operator&(uint64_t rhs) const { return Arg(num_, mask_ & rhs); }
+
+  // Returns a boolean expression comparing whether the system call
+  // argument (after applying any bitmasks, if appropriate) equals |rhs|.
+  BoolExpr operator==(T rhs) const;
+
+ private:
+  Arg(int num, uint64_t mask) : num_(num), mask_(mask) {}
+  int num_;
+  uint64_t mask_;
+  DISALLOW_ASSIGN(Arg);
+};
+
+// Various ways to combine boolean expressions into more complex expressions.
+// They follow standard boolean algebra laws.
+SANDBOX_EXPORT BoolExpr operator!(BoolExpr cond);
+SANDBOX_EXPORT BoolExpr operator&&(BoolExpr lhs, BoolExpr rhs);
+SANDBOX_EXPORT BoolExpr operator||(BoolExpr lhs, BoolExpr rhs);
+
+// If begins a conditional result expression predicated on the
+// specified boolean expression.
+SANDBOX_EXPORT Elser If(BoolExpr cond, ResultExpr then_result);
+
+class SANDBOX_EXPORT Elser {
+ public:
+  Elser(const Elser& elser);
+  ~Elser();
+
+  // ElseIf extends the conditional result expression with another
+  // "if then" clause, predicated on the specified boolean expression.
+  Elser ElseIf(BoolExpr cond, ResultExpr then_result) const;
+
+  // Else terminates a conditional result expression using |else_result| as
+  // the default fallback result expression.
+  ResultExpr Else(ResultExpr else_result) const;
+
+ private:
+  typedef std::pair<BoolExpr, ResultExpr> Clause;
+  explicit Elser(Cons<Clause>::List clause_list);
+  Cons<Clause>::List clause_list_;
+  friend Elser If(BoolExpr, ResultExpr);
+  DISALLOW_ASSIGN(Elser);
+};
+
+// =====================================================================
+// Official API ends here.
+// =====================================================================
+
+// Definitions below are necessary here only for C++03 compatibility.
+// Once C++11 is available, they should be moved into bpf_dsl.cc via extern
+// templates.
+namespace internal {
+
+// Returns a boolean expression that represents whether system call
+// argument |num| of size |size| is equal to |val|, when masked
+// according to |mask|.  Users should use the Arg template class below
+// instead of using this API directly.
+SANDBOX_EXPORT BoolExpr
+    ArgEq(int num, size_t size, uint64_t mask, uint64_t val);
+
+// Internal interface implemented by BoolExpr implementations.
+class SANDBOX_EXPORT BoolExprImpl : public base::RefCounted<BoolExprImpl> {
+ public:
+  BoolExprImpl() {}
+  virtual ErrorCode Compile(SandboxBPF* sb,
+                            ErrorCode true_ec,
+                            ErrorCode false_ec) const = 0;
+
+ protected:
+  virtual ~BoolExprImpl() {}
+
+ private:
+  friend class base::RefCounted<BoolExprImpl>;
+  DISALLOW_COPY_AND_ASSIGN(BoolExprImpl);
+};
+
+// Internal interface implemented by ResultExpr implementations.
+class SANDBOX_EXPORT ResultExprImpl : public base::RefCounted<ResultExprImpl> {
+ public:
+  ResultExprImpl() {}
+  virtual ErrorCode Compile(SandboxBPF* sb) const = 0;
+
+ protected:
+  virtual ~ResultExprImpl() {}
+
+ private:
+  friend class base::RefCounted<ResultExprImpl>;
+  DISALLOW_COPY_AND_ASSIGN(ResultExprImpl);
+};
+
+}  // namespace internal
+
+// Definition requires ArgEq to have been declared.  Moved out-of-line
+// to minimize how much internal clutter users have to ignore while
+// reading the header documentation.
+template <typename T>
+BoolExpr Arg<T>::operator==(T rhs) const {
+  return internal::ArgEq(num_, sizeof(T), mask_, static_cast<uint64_t>(rhs));
+}
+
+}  // namespace bpf_dsl
+}  // namespace sandbox
+
+#endif  // SANDBOX_LINUX_BPF_DSL_BPF_DSL_H_
diff --git a/sandbox/linux/bpf_dsl/bpf_dsl_unittest.cc b/sandbox/linux/bpf_dsl/bpf_dsl_unittest.cc
new file mode 100644
index 0000000..74ade9f
--- /dev/null
+++ b/sandbox/linux/bpf_dsl/bpf_dsl_unittest.cc
@@ -0,0 +1,248 @@
+// Copyright 2014 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/bpf_dsl/bpf_dsl.h"
+
+#include <errno.h>
+#include <netinet/in.h>
+#include <sys/socket.h>
+#include <sys/utsname.h>
+
+#include "base/macros.h"
+#include "build/build_config.h"
+#include "sandbox/linux/seccomp-bpf/bpf_tests.h"
+#include "sandbox/linux/seccomp-bpf/errorcode.h"
+#include "sandbox/linux/seccomp-bpf/sandbox_bpf_policy.h"
+
+using namespace sandbox::bpf_dsl;
+
+// Helper macro to assert that expression |expr| returns -1 and sets
+// errno to |err|.
+#define BPF_ASSERT_ERROR(err, expr) \
+  do {                              \
+    errno = 0;                      \
+    BPF_ASSERT_EQ(-1, expr);        \
+    BPF_ASSERT_EQ(err, errno);      \
+  } while (0)
+
+namespace sandbox {
+namespace {
+
+class BasicPolicy : public SandboxBPFDSLPolicy {
+ public:
+  BasicPolicy() {}
+  virtual ~BasicPolicy() {}
+  virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+    if (sysno == __NR_getpgid) {
+      const Arg<pid_t> pid(0);
+      return If(pid == 0, Error(EPERM)).Else(Error(EINVAL));
+    }
+    return Allow();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(BasicPolicy);
+};
+
+BPF_TEST_C(BPFDSL, Basic, BasicPolicy) {
+  BPF_ASSERT_ERROR(EPERM, getpgid(0));
+  BPF_ASSERT_ERROR(EINVAL, getpgid(1));
+}
+
+/* On IA-32, socketpair() is implemented via socketcall(). :-( */
+#if !defined(ARCH_CPU_X86)
+class BooleanLogicPolicy : public SandboxBPFDSLPolicy {
+ public:
+  BooleanLogicPolicy() {}
+  virtual ~BooleanLogicPolicy() {}
+  virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+    if (sysno == __NR_socketpair) {
+      const Arg<int> domain(0), type(1), protocol(2);
+      return If(domain == AF_UNIX &&
+                    (type == SOCK_STREAM || type == SOCK_DGRAM) &&
+                    protocol == 0,
+                Error(EPERM)).Else(Error(EINVAL));
+    }
+    return Allow();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(BooleanLogicPolicy);
+};
+
+BPF_TEST_C(BPFDSL, BooleanLogic, BooleanLogicPolicy) {
+  int sv[2];
+
+  // Acceptable combinations that should return EPERM.
+  BPF_ASSERT_ERROR(EPERM, socketpair(AF_UNIX, SOCK_STREAM, 0, sv));
+  BPF_ASSERT_ERROR(EPERM, socketpair(AF_UNIX, SOCK_DGRAM, 0, sv));
+
+  // Combinations that are invalid for only one reason; should return EINVAL.
+  BPF_ASSERT_ERROR(EINVAL, socketpair(AF_INET, SOCK_STREAM, 0, sv));
+  BPF_ASSERT_ERROR(EINVAL, socketpair(AF_UNIX, SOCK_SEQPACKET, 0, sv));
+  BPF_ASSERT_ERROR(EINVAL, socketpair(AF_UNIX, SOCK_STREAM, IPPROTO_TCP, sv));
+
+  // Completely unacceptable combination; should also return EINVAL.
+  BPF_ASSERT_ERROR(EINVAL,
+                   socketpair(AF_INET, SOCK_SEQPACKET, IPPROTO_UDP, sv));
+}
+#endif  // !ARCH_CPU_X86
+
+class MoreBooleanLogicPolicy : public SandboxBPFDSLPolicy {
+ public:
+  MoreBooleanLogicPolicy() {}
+  virtual ~MoreBooleanLogicPolicy() {}
+  virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+    if (sysno == __NR_setresuid) {
+      const Arg<uid_t> ruid(0), euid(1), suid(2);
+      return If(ruid == 0 || euid == 0 || suid == 0, Error(EPERM))
+          .ElseIf(ruid == 1 && euid == 1 && suid == 1, Error(EAGAIN))
+          .Else(Error(EINVAL));
+    }
+    return Allow();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(MoreBooleanLogicPolicy);
+};
+
+BPF_TEST_C(BPFDSL, MoreBooleanLogic, MoreBooleanLogicPolicy) {
+  // Expect EPERM if any set to 0.
+  BPF_ASSERT_ERROR(EPERM, setresuid(0, 5, 5));
+  BPF_ASSERT_ERROR(EPERM, setresuid(5, 0, 5));
+  BPF_ASSERT_ERROR(EPERM, setresuid(5, 5, 0));
+
+  // Expect EAGAIN if all set to 1.
+  BPF_ASSERT_ERROR(EAGAIN, setresuid(1, 1, 1));
+
+  // Expect EINVAL for anything else.
+  BPF_ASSERT_ERROR(EINVAL, setresuid(5, 1, 1));
+  BPF_ASSERT_ERROR(EINVAL, setresuid(1, 5, 1));
+  BPF_ASSERT_ERROR(EINVAL, setresuid(1, 1, 5));
+  BPF_ASSERT_ERROR(EINVAL, setresuid(3, 4, 5));
+}
+
+static const uintptr_t kDeadBeefAddr =
+    static_cast<uintptr_t>(0xdeadbeefdeadbeefULL);
+
+class ArgSizePolicy : public SandboxBPFDSLPolicy {
+ public:
+  ArgSizePolicy() {}
+  virtual ~ArgSizePolicy() {}
+  virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+    if (sysno == __NR_uname) {
+      const Arg<uintptr_t> addr(0);
+      return If(addr == kDeadBeefAddr, Error(EPERM)).Else(Allow());
+    }
+    return Allow();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(ArgSizePolicy);
+};
+
+BPF_TEST_C(BPFDSL, ArgSizeTest, ArgSizePolicy) {
+  struct utsname buf;
+  BPF_ASSERT_EQ(0, uname(&buf));
+
+  BPF_ASSERT_ERROR(EPERM,
+                   uname(reinterpret_cast<struct utsname*>(kDeadBeefAddr)));
+}
+
+class TrappingPolicy : public SandboxBPFDSLPolicy {
+ public:
+  TrappingPolicy() {}
+  virtual ~TrappingPolicy() {}
+  virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+    if (sysno == __NR_uname) {
+      return Trap(UnameTrap, &count_);
+    }
+    return Allow();
+  }
+
+ private:
+  static intptr_t count_;
+
+  static intptr_t UnameTrap(const struct arch_seccomp_data& data, void* aux) {
+    BPF_ASSERT_EQ(&count_, aux);
+    return ++count_;
+  }
+
+  DISALLOW_COPY_AND_ASSIGN(TrappingPolicy);
+};
+
+intptr_t TrappingPolicy::count_;
+
+BPF_TEST_C(BPFDSL, TrapTest, TrappingPolicy) {
+  BPF_ASSERT_EQ(1, uname(NULL));
+  BPF_ASSERT_EQ(2, uname(NULL));
+  BPF_ASSERT_EQ(3, uname(NULL));
+}
+
+class MaskingPolicy : public SandboxBPFDSLPolicy {
+ public:
+  MaskingPolicy() {}
+  virtual ~MaskingPolicy() {}
+  virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+    if (sysno == __NR_setuid) {
+      const Arg<uid_t> uid(0);
+      return If((uid & 0xf) == 0, Error(EINVAL)).Else(Error(EACCES));
+    }
+    if (sysno == __NR_setgid) {
+      const Arg<gid_t> gid(0);
+      return If((gid & 0xf0) == 0xf0, Error(EINVAL)).Else(Error(EACCES));
+    }
+    return Allow();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(MaskingPolicy);
+};
+
+BPF_TEST_C(BPFDSL, MaskTest, MaskingPolicy) {
+  for (uid_t uid = 0; uid < 0x100; ++uid) {
+    const int expect_errno = (uid & 0xf) == 0 ? EINVAL : EACCES;
+    BPF_ASSERT_ERROR(expect_errno, setuid(uid));
+  }
+
+  for (gid_t gid = 0; gid < 0x100; ++gid) {
+    const int expect_errno = (gid & 0xf0) == 0xf0 ? EINVAL : EACCES;
+    BPF_ASSERT_ERROR(expect_errno, setgid(gid));
+  }
+}
+
+class ElseIfPolicy : public SandboxBPFDSLPolicy {
+ public:
+  ElseIfPolicy() {}
+  virtual ~ElseIfPolicy() {}
+  virtual ResultExpr EvaluateSyscall(int sysno) const OVERRIDE {
+    if (sysno == __NR_setuid) {
+      const Arg<uid_t> uid(0);
+      return If((uid & 0xfff) == 0, Error(0))
+          .ElseIf((uid & 0xff0) == 0, Error(EINVAL))
+          .ElseIf((uid & 0xf00) == 0, Error(EEXIST))
+          .Else(Error(EACCES));
+    }
+    return Allow();
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(ElseIfPolicy);
+};
+
+BPF_TEST_C(BPFDSL, ElseIfTest, ElseIfPolicy) {
+  BPF_ASSERT_EQ(0, setuid(0));
+
+  BPF_ASSERT_ERROR(EINVAL, setuid(0x0001));
+  BPF_ASSERT_ERROR(EINVAL, setuid(0x0002));
+
+  BPF_ASSERT_ERROR(EEXIST, setuid(0x0011));
+  BPF_ASSERT_ERROR(EEXIST, setuid(0x0022));
+
+  BPF_ASSERT_ERROR(EACCES, setuid(0x0111));
+  BPF_ASSERT_ERROR(EACCES, setuid(0x0222));
+}
+
+}  // namespace
+}  // namespace sandbox
diff --git a/sandbox/linux/bpf_dsl/cons.h b/sandbox/linux/bpf_dsl/cons.h
new file mode 100644
index 0000000..eb9e3aa
--- /dev/null
+++ b/sandbox/linux/bpf_dsl/cons.h
@@ -0,0 +1,46 @@
+// Copyright 2014 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 SANDBOX_LINUX_BPF_DSL_CONS_H_
+#define SANDBOX_LINUX_BPF_DSL_CONS_H_
+
+#include "base/memory/ref_counted.h"
+#include "sandbox/sandbox_export.h"
+
+namespace sandbox {
+
+// Cons provides an immutable linked list abstraction as commonly
+// provided in functional programming languages like Lisp or Haskell.
+template <typename T>
+class Cons : public base::RefCounted<Cons<T> > {
+ public:
+  // List provides an abstraction for referencing a list of zero or
+  // more Cons nodes.
+  typedef scoped_refptr<const Cons<T> > List;
+
+  // Return this node's head element.
+  const T& head() const { return head_; }
+
+  // Return this node's tail element.
+  List tail() const { return tail_; }
+
+  // Construct a new List using |head| and |tail|.
+  static List Make(const T& head, List tail) {
+    return make_scoped_refptr(new const Cons<T>(head, tail));
+  }
+
+ private:
+  Cons(const T& head, List tail) : head_(head), tail_(tail) {}
+  virtual ~Cons() {}
+
+  T head_;
+  List tail_;
+
+  friend class base::RefCounted<Cons<T> >;
+  DISALLOW_COPY_AND_ASSIGN(Cons);
+};
+
+}  // namespace sandbox
+
+#endif  // SANDBOX_LINUX_BPF_DSL_CONS_H_
diff --git a/sandbox/linux/bpf_dsl/cons_unittest.cc b/sandbox/linux/bpf_dsl/cons_unittest.cc
new file mode 100644
index 0000000..790cae0
--- /dev/null
+++ b/sandbox/linux/bpf_dsl/cons_unittest.cc
@@ -0,0 +1,34 @@
+// Copyright 2014 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/bpf_dsl/cons.h"
+
+#include <string>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace sandbox {
+namespace {
+
+std::string Join(Cons<char>::List char_list) {
+  std::string res;
+  for (Cons<char>::List it = char_list; it; it = it->tail()) {
+    res.push_back(it->head());
+  }
+  return res;
+}
+
+TEST(ConsListTest, Basic) {
+  Cons<char>::List ba =
+      Cons<char>::Make('b', Cons<char>::Make('a', Cons<char>::List()));
+  EXPECT_EQ("ba", Join(ba));
+
+  Cons<char>::List cba = Cons<char>::Make('c', ba);
+  Cons<char>::List dba = Cons<char>::Make('d', ba);
+  EXPECT_EQ("cba", Join(cba));
+  EXPECT_EQ("dba", Join(dba));
+}
+
+}  // namespace
+}  // namespace sandbox
diff --git a/sandbox/linux/sandbox_linux.gypi b/sandbox/linux/sandbox_linux.gypi
index 9ddcf0c..274d065 100644
--- a/sandbox/linux/sandbox_linux.gypi
+++ b/sandbox/linux/sandbox_linux.gypi
@@ -117,6 +117,9 @@
       'target_name': 'seccomp_bpf',
       'type': '<(component)',
       'sources': [
+        'bpf_dsl/bpf_dsl.cc',
+        'bpf_dsl/bpf_dsl.h',
+        'bpf_dsl/cons.h',
         'seccomp-bpf/basicblock.cc',
         'seccomp-bpf/basicblock.h',
         'seccomp-bpf/codegen.cc',
diff --git a/sandbox/linux/sandbox_linux_test_sources.gypi b/sandbox/linux/sandbox_linux_test_sources.gypi
index c72ef51..c2f365b 100644
--- a/sandbox/linux/sandbox_linux_test_sources.gypi
+++ b/sandbox/linux/sandbox_linux_test_sources.gypi
@@ -34,6 +34,8 @@
     }],
     [ 'use_seccomp_bpf==1', {
       'sources': [
+        'bpf_dsl/bpf_dsl_unittest.cc',
+        'bpf_dsl/cons_unittest.cc',
         'seccomp-bpf-helpers/baseline_policy_unittest.cc',
         'seccomp-bpf/bpf_tests_unittest.cc',
         'seccomp-bpf/codegen_unittest.cc',