src/sandbox/linux/seccomp-bpf/verifier.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "sandbox/linux/seccomp-bpf/verifier.h"
   6
   7 #include <string.h>
   8
   9 #include <limits>
  10
  11 #include "sandbox/linux/seccomp-bpf/linux_seccomp.h"
  12 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
  13 #include "sandbox/linux/seccomp-bpf/sandbox_bpf_policy.h"
  14 #include "sandbox/linux/seccomp-bpf/syscall_iterator.h"
  15
  16 namespace sandbox {
  17
  18 namespace {
  19
  20 const uint64_t kLower32Bits = std::numeric_limits<uint32_t>::max();
  21 const uint64_t kUpper32Bits = static_cast<uint64_t>(kLower32Bits) << 32;
  22 const uint64_t kFull64Bits = std::numeric_limits<uint64_t>::max();
  23
  24 struct State {
  25   State(const std::vector<struct sock_filter>& p,
  26         const struct arch_seccomp_data& d)
  27       : program(p), data(d), ip(0), accumulator(0), acc_is_valid(false) {}
  28   const std::vector<struct sock_filter>& program;
  29   const struct arch_seccomp_data& data;
  30   unsigned int ip;
  31   uint32_t accumulator;
  32   bool acc_is_valid;
  33
  34  private:
  35   DISALLOW_IMPLICIT_CONSTRUCTORS(State);
  36 };
  37
  38 uint32_t EvaluateErrorCode(SandboxBPF* sandbox,
  39                            const ErrorCode& code,
  40                            const struct arch_seccomp_data& data) {
  41   if (code.error_type() == ErrorCode::ET_SIMPLE ||
  42       code.error_type() == ErrorCode::ET_TRAP) {
  43     return code.err();
  44   } else if (code.error_type() == ErrorCode::ET_COND) {
  45     if (code.width() == ErrorCode::TP_32BIT &&
  46         (data.args[code.argno()] >> 32) &&
  47         (data.args[code.argno()] & 0xFFFFFFFF80000000ull) !=
  48             0xFFFFFFFF80000000ull) {
  49       return sandbox->Unexpected64bitArgument().err();
  50     }
  51     bool equal = (data.args[code.argno()] & code.mask()) == code.value();
  52     return EvaluateErrorCode(
  53         sandbox, equal ? *code.passed() : *code.failed(), data);
  54   } else {
  55     return SECCOMP_RET_INVALID;
  56   }
  57 }
  58
  59 bool VerifyErrorCode(SandboxBPF* sandbox,
  60                      const std::vector<struct sock_filter>& program,
  61                      struct arch_seccomp_data* data,
  62                      const ErrorCode& root_code,
  63                      const ErrorCode& code,
  64                      const char** err) {
  65   if (code.error_type() == ErrorCode::ET_SIMPLE ||
  66       code.error_type() == ErrorCode::ET_TRAP) {
  67     uint32_t computed_ret = Verifier::EvaluateBPF(program, *data, err);
  68     if (*err) {
  69       return false;
  70     } else if (computed_ret != EvaluateErrorCode(sandbox, root_code, *data)) {
  71       // For efficiency's sake, we'd much rather compare "computed_ret"
  72       // against "code.err()". This works most of the time, but it doesn't
  73       // always work for nested conditional expressions. The test values
  74       // that we generate on the fly to probe expressions can trigger
  75       // code flow decisions in multiple nodes of the decision tree, and the
  76       // only way to compute the correct error code in that situation is by
  77       // calling EvaluateErrorCode().
  78       *err = "Exit code from BPF program doesn't match";
  79       return false;
  80     }
  81   } else if (code.error_type() == ErrorCode::ET_COND) {
  82     if (code.argno() < 0 || code.argno() >= 6) {
  83       *err = "Invalid argument number in error code";
  84       return false;
  85     }
  86
  87     // TODO(mdempsky): The test values generated here try to provide good
  88     // coverage for generated BPF instructions while avoiding combinatorial
  89     // explosion on large policies. Ideally we would instead take a fuzzing-like
  90     // approach and generate a bounded number of test cases regardless of policy
  91     // size.
  92
  93     // Verify that we can check a value for simple equality.
  94     data->args[code.argno()] = code.value();
  95     if (!VerifyErrorCode(
  96             sandbox, program, data, root_code, *code.passed(), err)) {
  97       return false;
  98     }
  99
 100     // If mask ignores any bits, verify that setting those bits is still
 101     // detected as equality.
 102     uint64_t ignored_bits = ~code.mask();
 103     if (code.width() == ErrorCode::TP_32BIT) {
 104       ignored_bits = static_cast<uint32_t>(ignored_bits);
 105     }
 106     if ((ignored_bits & kLower32Bits) != 0) {
 107       data->args[code.argno()] = code.value() | (ignored_bits & kLower32Bits);
 108       if (!VerifyErrorCode(
 109               sandbox, program, data, root_code, *code.passed(), err)) {
 110         return false;
 111       }
 112     }
 113     if ((ignored_bits & kUpper32Bits) != 0) {
 114       data->args[code.argno()] = code.value() | (ignored_bits & kUpper32Bits);
 115       if (!VerifyErrorCode(
 116               sandbox, program, data, root_code, *code.passed(), err)) {
 117         return false;
 118       }
 119     }
 120
 121     // Verify that changing bits included in the mask is detected as inequality.
 122     if ((code.mask() & kLower32Bits) != 0) {
 123       data->args[code.argno()] = code.value() ^ (code.mask() & kLower32Bits);
 124       if (!VerifyErrorCode(
 125               sandbox, program, data, root_code, *code.failed(), err)) {
 126         return false;
 127       }
 128     }
 129     if ((code.mask() & kUpper32Bits) != 0) {
 130       data->args[code.argno()] = code.value() ^ (code.mask() & kUpper32Bits);
 131       if (!VerifyErrorCode(
 132               sandbox, program, data, root_code, *code.failed(), err)) {
 133         return false;
 134       }
 135     }
 136
 137     if (code.width() == ErrorCode::TP_32BIT) {
 138       // For 32-bit system call arguments, we emit additional instructions to
 139       // validate the upper 32-bits. Here we test that validation.
 140
 141       // Arbitrary 64-bit values should be rejected.
 142       data->args[code.argno()] = 1ULL << 32;
 143       if (!VerifyErrorCode(sandbox,
 144                            program,
 145                            data,
 146                            root_code,
 147                            sandbox->Unexpected64bitArgument(),
 148                            err)) {
 149         return false;
 150       }
 151
 152       // Upper 32-bits set without the MSB of the lower 32-bits set should be
 153       // rejected too.
 154       data->args[code.argno()] = kUpper32Bits;
 155       if (!VerifyErrorCode(sandbox,
 156                            program,
 157                            data,
 158                            root_code,
 159                            sandbox->Unexpected64bitArgument(),
 160                            err)) {
 161         return false;
 162       }
 163     }
 164   } else {
 165     *err = "Attempting to return invalid error code from BPF program";
 166     return false;
 167   }
 168   return true;
 169 }
 170
 171 void Ld(State* state, const struct sock_filter& insn, const char** err) {
 172   if (BPF_SIZE(insn.code) != BPF_W || BPF_MODE(insn.code) != BPF_ABS) {
 173     *err = "Invalid BPF_LD instruction";
 174     return;
 175   }
 176   if (insn.k < sizeof(struct arch_seccomp_data) && (insn.k & 3) == 0) {
 177     // We only allow loading of properly aligned 32bit quantities.
 178     memcpy(&state->accumulator,
 179            reinterpret_cast<const char*>(&state->data) + insn.k,
 180            4);
 181   } else {
 182     *err = "Invalid operand in BPF_LD instruction";
 183     return;
 184   }
 185   state->acc_is_valid = true;
 186   return;
 187 }
 188
 189 void Jmp(State* state, const struct sock_filter& insn, const char** err) {
 190   if (BPF_OP(insn.code) == BPF_JA) {
 191     if (state->ip + insn.k + 1 >= state->program.size() ||
 192         state->ip + insn.k + 1 <= state->ip) {
 193     compilation_failure:
 194       *err = "Invalid BPF_JMP instruction";
 195       return;
 196     }
 197     state->ip += insn.k;
 198   } else {
 199     if (BPF_SRC(insn.code) != BPF_K || !state->acc_is_valid ||
 200         state->ip + insn.jt + 1 >= state->program.size() ||
 201         state->ip + insn.jf + 1 >= state->program.size()) {
 202       goto compilation_failure;
 203     }
 204     switch (BPF_OP(insn.code)) {
 205       case BPF_JEQ:
 206         if (state->accumulator == insn.k) {
 207           state->ip += insn.jt;
 208         } else {
 209           state->ip += insn.jf;
 210         }
 211         break;
 212       case BPF_JGT:
 213         if (state->accumulator > insn.k) {
 214           state->ip += insn.jt;
 215         } else {
 216           state->ip += insn.jf;
 217         }
 218         break;
 219       case BPF_JGE:
 220         if (state->accumulator >= insn.k) {
 221           state->ip += insn.jt;
 222         } else {
 223           state->ip += insn.jf;
 224         }
 225         break;
 226       case BPF_JSET:
 227         if (state->accumulator & insn.k) {
 228           state->ip += insn.jt;
 229         } else {
 230           state->ip += insn.jf;
 231         }
 232         break;
 233       default:
 234         goto compilation_failure;
 235     }
 236   }
 237 }
 238
 239 uint32_t Ret(State*, const struct sock_filter& insn, const char** err) {
 240   if (BPF_SRC(insn.code) != BPF_K) {
 241     *err = "Invalid BPF_RET instruction";
 242     return 0;
 243   }
 244   return insn.k;
 245 }
 246
 247 void Alu(State* state, const struct sock_filter& insn, const char** err) {
 248   if (BPF_OP(insn.code) == BPF_NEG) {
 249     state->accumulator = -state->accumulator;
 250     return;
 251   } else {
 252     if (BPF_SRC(insn.code) != BPF_K) {
 253       *err = "Unexpected source operand in arithmetic operation";
 254       return;
 255     }
 256     switch (BPF_OP(insn.code)) {
 257       case BPF_ADD:
 258         state->accumulator += insn.k;
 259         break;
 260       case BPF_SUB:
 261         state->accumulator -= insn.k;
 262         break;
 263       case BPF_MUL:
 264         state->accumulator *= insn.k;
 265         break;
 266       case BPF_DIV:
 267         if (!insn.k) {
 268           *err = "Illegal division by zero";
 269           break;
 270         }
 271         state->accumulator /= insn.k;
 272         break;
 273       case BPF_MOD:
 274         if (!insn.k) {
 275           *err = "Illegal division by zero";
 276           break;
 277         }
 278         state->accumulator %= insn.k;
 279         break;
 280       case BPF_OR:
 281         state->accumulator |= insn.k;
 282         break;
 283       case BPF_XOR:
 284         state->accumulator ^= insn.k;
 285         break;
 286       case BPF_AND:
 287         state->accumulator &= insn.k;
 288         break;
 289       case BPF_LSH:
 290         if (insn.k > 32) {
 291           *err = "Illegal shift operation";
 292           break;
 293         }
 294         state->accumulator <<= insn.k;
 295         break;
 296       case BPF_RSH:
 297         if (insn.k > 32) {
 298           *err = "Illegal shift operation";
 299           break;
 300         }
 301         state->accumulator >>= insn.k;
 302         break;
 303       default:
 304         *err = "Invalid operator in arithmetic operation";
 305         break;
 306     }
 307   }
 308 }
 309
 310 }  // namespace
 311
 312 bool Verifier::VerifyBPF(SandboxBPF* sandbox,
 313                          const std::vector<struct sock_filter>& program,
 314                          const SandboxBPFPolicy& policy,
 315                          const char** err) {
 316   *err = NULL;
 317   for (SyscallIterator iter(false); !iter.Done();) {
 318     uint32_t sysnum = iter.Next();
 319     // We ideally want to iterate over the full system call range and values
 320     // just above and just below this range. This gives us the full result set
 321     // of the "evaluators".
 322     // On Intel systems, this can fail in a surprising way, as a cleared bit 30
 323     // indicates either i386 or x86-64; and a set bit 30 indicates x32. And
 324     // unless we pay attention to setting this bit correctly, an early check in
 325     // our BPF program will make us fail with a misleading error code.
 326     struct arch_seccomp_data data = {static_cast<int>(sysnum),
 327                                      static_cast<uint32_t>(SECCOMP_ARCH)};
 328 #if defined(__i386__) || defined(__x86_64__)
 329 #if defined(__x86_64__) && defined(__ILP32__)
 330     if (!(sysnum & 0x40000000u)) {
 331       continue;
 332     }
 333 #else
 334     if (sysnum & 0x40000000u) {
 335       continue;
 336     }
 337 #endif
 338 #endif
 339     ErrorCode code = iter.IsValid(sysnum)
 340                          ? policy.EvaluateSyscall(sandbox, sysnum)
 341                          : policy.InvalidSyscall(sandbox);
 342     if (!VerifyErrorCode(sandbox, program, &data, code, code, err)) {
 343       return false;
 344     }
 345   }
 346   return true;
 347 }
 348
 349 uint32_t Verifier::EvaluateBPF(const std::vector<struct sock_filter>& program,
 350                                const struct arch_seccomp_data& data,
 351                                const char** err) {
 352   *err = NULL;
 353   if (program.size() < 1 || program.size() >= SECCOMP_MAX_PROGRAM_SIZE) {
 354     *err = "Invalid program length";
 355     return 0;
 356   }
 357   for (State state(program, data); !*err; ++state.ip) {
 358     if (state.ip >= program.size()) {
 359       *err = "Invalid instruction pointer in BPF program";
 360       break;
 361     }
 362     const struct sock_filter& insn = program[state.ip];
 363     switch (BPF_CLASS(insn.code)) {
 364       case BPF_LD:
 365         Ld(&state, insn, err);
 366         break;
 367       case BPF_JMP:
 368         Jmp(&state, insn, err);
 369         break;
 370       case BPF_RET: {
 371         uint32_t r = Ret(&state, insn, err);
 372         switch (r & SECCOMP_RET_ACTION) {
 373           case SECCOMP_RET_TRAP:
 374           case SECCOMP_RET_ERRNO:
 375           case SECCOMP_RET_TRACE:
 376           case SECCOMP_RET_ALLOW:
 377             break;
 378           case SECCOMP_RET_KILL:     // We don't ever generate this
 379           case SECCOMP_RET_INVALID:  // Should never show up in BPF program
 380           default:
 381             *err = "Unexpected return code found in BPF program";
 382             return 0;
 383         }
 384         return r;
 385       }
 386       case BPF_ALU:
 387         Alu(&state, insn, err);
 388         break;
 389       default:
 390         *err = "Unexpected instruction in BPF program";
 391         break;
 392     }
 393   }
 394   return 0;
 395 }
 396
 397 }  // namespace sandbox