bpf_dsl: support arbitrary (arg & mask) == val expressions

sandbox/linux/seccomp-bpf/verifier.cc

 // 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 <string.h>
 
+#include <limits>
+
 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
 #include "sandbox/linux/seccomp-bpf/sandbox_bpf_policy.h"
 #include "sandbox/linux/seccomp-bpf/syscall_iterator.h"
 #include "sandbox/linux/seccomp-bpf/verifier.h"
 
-
 namespace sandbox {
 
 namespace {
 
+const uint64_t kLower32Bits = std::numeric_limits<uint32_t>::max();
+const uint64_t kUpper32Bits = static_cast<uint64_t>(kLower32Bits) << 32;
+const uint64_t kFull64Bits = std::numeric_limits<uint64_t>::max();
+
 struct State {
   State(const std::vector<struct sock_filter>& p,
         const struct arch_seccomp_data& d)
       : program(p), data(d), ip(0), accumulator(0), acc_is_valid(false) {}
   const std::vector<struct sock_filter>& program;
   const struct arch_seccomp_data& data;
   unsigned int ip;
   uint32_t accumulator;
   bool acc_is_valid;
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(State);
 };
 
 uint32_t EvaluateErrorCode(SandboxBPF* sandbox,
                            const ErrorCode& code,
                            const struct arch_seccomp_data& data) {
   if (code.error_type() == ErrorCode::ET_SIMPLE ||
       code.error_type() == ErrorCode::ET_TRAP) {
     return code.err();
   } else if (code.error_type() == ErrorCode::ET_COND) {
     if (code.width() == ErrorCode::TP_32BIT &&
         (data.args[code.argno()] >> 32) &&
         (data.args[code.argno()] & 0xFFFFFFFF80000000ull) !=
             0xFFFFFFFF80000000ull) {
       return sandbox->Unexpected64bitArgument().err();
     }
-    switch (code.op()) {
-      case ErrorCode::OP_EQUAL:
-        return EvaluateErrorCode(sandbox,
-                                 (code.width() == ErrorCode::TP_32BIT
-                                      ? uint32_t(data.args[code.argno()])
-                                      : data.args[code.argno()]) == code.value()
-                                     ? *code.passed()
-                                     : *code.failed(),
-                                 data);
-      case ErrorCode::OP_HAS_ALL_BITS:
-        return EvaluateErrorCode(sandbox,
-                                 ((code.width() == ErrorCode::TP_32BIT
-                                       ? uint32_t(data.args[code.argno()])
-                                       : data.args[code.argno()]) &
-                                  code.value()) == code.value()
-                                     ? *code.passed()
-                                     : *code.failed(),
-                                 data);
-      case ErrorCode::OP_HAS_ANY_BITS:
-        return EvaluateErrorCode(sandbox,
-                                 (code.width() == ErrorCode::TP_32BIT
-                                      ? uint32_t(data.args[code.argno()])
-                                      : data.args[code.argno()]) &
-                                         code.value()
-                                     ? *code.passed()
-                                     : *code.failed(),
-                                 data);
-      default:
-        return SECCOMP_RET_INVALID;
-    }
+    bool equal = (data.args[code.argno()] & code.mask()) == code.value();
+    return EvaluateErrorCode(
+        sandbox, equal ? *code.passed() : *code.failed(), data);
   } else {
     return SECCOMP_RET_INVALID;
   }
 }
 
 bool VerifyErrorCode(SandboxBPF* sandbox,
                      const std::vector<struct sock_filter>& program,
                      struct arch_seccomp_data* data,
                      const ErrorCode& root_code,
                      const ErrorCode& code,
@@ skipping 12 matching lines @@
       // only way to compute the correct error code in that situation is by
       // calling EvaluateErrorCode().
       *err = "Exit code from BPF program doesn't match";
       return false;
     }
   } else if (code.error_type() == ErrorCode::ET_COND) {
     if (code.argno() < 0 || code.argno() >= 6) {
       *err = "Invalid argument number in error code";
       return false;
     }
-    switch (code.op()) {
-      case ErrorCode::OP_EQUAL:
-        // Verify that we can check a 32bit value (or the LSB of a 64bit value)
-        // for equality.
-        data->args[code.argno()] = code.value();
-        if (!VerifyErrorCode(
-                 sandbox, program, data, root_code, *code.passed(), err)) {
-          return false;
-        }
 
-        // Change the value to no longer match and verify that this is detected
-        // as an inequality.
-        data->args[code.argno()] = code.value() ^ 0x55AA55AA;
-        if (!VerifyErrorCode(
-                 sandbox, program, data, root_code, *code.failed(), err)) {
-          return false;
-        }
+    // Verify that we can check a value for simple equality.
+    data->args[code.argno()] = code.value();
+    if (!VerifyErrorCode(
+            sandbox, program, data, root_code, *code.passed(), err)) {
+      return false;
+    }
 
-        // BPF programs can only ever operate on 32bit values. So, we have
-        // generated additional BPF instructions that inspect the MSB. Verify
-        // that they behave as intended.
-        if (code.width() == ErrorCode::TP_32BIT) {
-          if (code.value() >> 32) {
-            SANDBOX_DIE(
-                "Invalid comparison of a 32bit system call argument "
-                "against a 64bit constant; this test is always false.");
-          }
+    // If mask ignores any bits, verify that setting those bits is still
+    // detected as equality.
+    uint64_t ignored_bits = ~code.mask();

[jln (very slow on Chromium), 2014/09/04 02:08:36]

Maybe it would add a little coverage to:

1. Doing the same with "some_ignored_bits = ignored_bits & 0x55AA55AA";

2. Below, to detect that changing bits in the mask is detected as inequality:
"some_considered_bits = code.mask() & 0x055AA55AA"

Either instead or in addition to what you're already doing?

[mdempsky, 2014/09/04 17:26:48]

The unfortunate thing is that this runs recursively, and adding too many extra
cases quickly causes an exponential explosion of test cases and starts causing
timeouts. :-(

In lieu of adding the extra test cases you suggested, I've added a TODO to note
that we should rework how this is implemented to avoid explosions.

+    if (code.width() == ErrorCode::TP_32BIT) {
+      ignored_bits = static_cast<uint32_t>(ignored_bits);
+    }
+    if ((ignored_bits & kLower32Bits) != 0) {
+      data->args[code.argno()] = code.value() | (ignored_bits & kLower32Bits);
+      if (!VerifyErrorCode(
+              sandbox, program, data, root_code, *code.passed(), err)) {
+        return false;
+      }
+    }
+    if ((ignored_bits & kUpper32Bits) != 0) {
+      data->args[code.argno()] = code.value() | (ignored_bits & kUpper32Bits);
+      if (!VerifyErrorCode(
+              sandbox, program, data, root_code, *code.passed(), err)) {
+        return false;
+      }
+    }
 
-          // If the system call argument was intended to be a 32bit parameter,
-          // verify that it is a fatal error if a 64bit value is ever passed
-          // here.
-          data->args[code.argno()] = 0x100000000ull;
-          if (!VerifyErrorCode(sandbox,
-                               program,
-                               data,
-                               root_code,
-                               sandbox->Unexpected64bitArgument(),
-                               err)) {
-            return false;
-          }
-        } else {
-          // If the system call argument was intended to be a 64bit parameter,
-          // verify that we can handle (in-)equality for the MSB. This is
-          // essentially the same test that we did earlier for the LSB.
-          // We only need to verify the behavior of the inequality test. We
-          // know that the equality test already passed, as unlike the kernel
-          // the Verifier does operate on 64bit quantities.
-          data->args[code.argno()] = code.value() ^ 0x55AA55AA00000000ull;
-          if (!VerifyErrorCode(
-                   sandbox, program, data, root_code, *code.failed(), err)) {
-            return false;
-          }
-        }
-        break;
-      case ErrorCode::OP_HAS_ALL_BITS:
-      case ErrorCode::OP_HAS_ANY_BITS:
-        // A comprehensive test of bit values is difficult and potentially
-        // rather
-        // time-expensive. We avoid doing so at run-time and instead rely on the
-        // unittest for full testing. The test that we have here covers just the
-        // common cases. We test against the bitmask itself, all zeros and all
-        // ones.
-        {
-          // Testing "any" bits against a zero mask is always false. So, there
-          // are some cases, where we expect tests to take the "failed()" branch
-          // even though this is a test that normally should take "passed()".
-          const ErrorCode& passed =
-              (!code.value() && code.op() == ErrorCode::OP_HAS_ANY_BITS) ||
+    // Verify that changing bits included in the mask is detected as inequality.
+    if ((code.mask() & kLower32Bits) != 0) {
+      data->args[code.argno()] = code.value() ^ (code.mask() & kLower32Bits);
+      if (!VerifyErrorCode(
+              sandbox, program, data, root_code, *code.failed(), err)) {
+        return false;
+      }
+    }
+    if ((code.mask() & kUpper32Bits) != 0) {
+      data->args[code.argno()] = code.value() ^ (code.mask() & kUpper32Bits);
+      if (!VerifyErrorCode(
+              sandbox, program, data, root_code, *code.failed(), err)) {
+        return false;
+      }
+    }
 
-                      // On a 32bit system, it is impossible to pass a 64bit
-                      // value as a
-                      // system call argument. So, some additional tests always
-                      // evaluate
-                      // as false.
-                      ((code.value() & ~uint64_t(uintptr_t(-1))) &&
-                       code.op() == ErrorCode::OP_HAS_ALL_BITS) ||
-                      (code.value() && !(code.value() & uintptr_t(-1)) &&
-                       code.op() == ErrorCode::OP_HAS_ANY_BITS)
-                  ? *code.failed()
-                  : *code.passed();
+    if (code.width() == ErrorCode::TP_32BIT) {
+      // For 32-bit system call arguments, we emit additional instructions to
+      // validate the upper 32-bits.  Here we test that validation.

[jln (very slow on Chromium), 2014/09/04 02:08:36]

Nit: there is an extra space in front of "Here".

[mdempsky, 2014/09/04 17:26:48]

Done. (I generally use two spaces between sentences out of habit, but prevailing
style in the seccomp-bpf directory seems to be one, so I'll be consistent here.)

 
-          // Similary, testing for "all" bits in a zero mask is always true. So,
-          // some cases pass despite them normally failing.
-          const ErrorCode& failed =
-              !code.value() && code.op() == ErrorCode::OP_HAS_ALL_BITS
-                  ? *code.passed()
-                  : *code.failed();
+      // Arbitrary 64-bit values should be rejected.
+      data->args[code.argno()] = 1ULL << 32;
+      if (!VerifyErrorCode(sandbox,
+                           program,
+                           data,
+                           root_code,
+                           sandbox->Unexpected64bitArgument(),
+                           err)) {
+        return false;
+      }
 
-          data->args[code.argno()] = code.value() & uintptr_t(-1);
-          if (!VerifyErrorCode(
-                   sandbox, program, data, root_code, passed, err)) {
-            return false;
-          }
-          data->args[code.argno()] = uintptr_t(-1);
-          if (!VerifyErrorCode(
-                   sandbox, program, data, root_code, passed, err)) {
-            return false;
-          }
-          data->args[code.argno()] = 0;
-          if (!VerifyErrorCode(
-                   sandbox, program, data, root_code, failed, err)) {
-            return false;
-          }
-        }
-        break;
-      default:  // TODO(markus): Need to add support for OP_GREATER
-        *err = "Unsupported operation in conditional error code";
+      // Upper 32-bits set without the MSB of the lower 32-bits set should be
+      // rejected too.
+      data->args[code.argno()] = kUpper32Bits;
+      if (!VerifyErrorCode(sandbox,
+                           program,
+                           data,
+                           root_code,
+                           sandbox->Unexpected64bitArgument(),
+                           err)) {
         return false;
+      }
     }
   } else {
     *err = "Attempting to return invalid error code from BPF program";
     return false;
   }
   return true;
 }
 
 void Ld(State* state, const struct sock_filter& insn, const char** err) {
   if (BPF_SIZE(insn.code) != BPF_W || BPF_MODE(insn.code) != BPF_ABS) {
@@ skipping 215 matching lines @@
         break;
       default:
         *err = "Unexpected instruction in BPF program";
         break;
     }
   }
   return 0;
 }
 
 }  // namespace sandbox