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 <string.h>
   6
   7 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
   8 #include "sandbox/linux/seccomp-bpf/syscall_iterator.h"
   9 #include "sandbox/linux/seccomp-bpf/verifier.h"
  10
  11
  12 namespace {
  13
  14 using playground2::ErrorCode;
  15 using playground2::Sandbox;
  16 using playground2::Verifier;
  17 using playground2::arch_seccomp_data;
  18
  19 struct State {
  20   State(const std::vector<struct sock_filter>& p,
  21         const struct arch_seccomp_data& d) :
  22     program(p),
  23     data(d),
  24     ip(0),
  25     accumulator(0),
  26     acc_is_valid(false) {
  27   }
  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(Sandbox *sandbox, const ErrorCode& code,
  39                            const struct arch_seccomp_data& data) {
  40   if (code.error_type() == ErrorCode::ET_SIMPLE ||
  41       code.error_type() == ErrorCode::ET_TRAP) {
  42     return code.err();
  43   } else if (code.error_type() == ErrorCode::ET_COND) {
  44     if (code.width() == ErrorCode::TP_32BIT &&
  45         (data.args[code.argno()] >> 32) &&
  46         (data.args[code.argno()] & 0xFFFFFFFF80000000ull) !=
  47         0xFFFFFFFF80000000ull) {
  48       return sandbox->Unexpected64bitArgument().err();
  49     }
  50     switch (code.op()) {
  51     case ErrorCode::OP_EQUAL:
  52       return EvaluateErrorCode(sandbox,
  53                                (code.width() == ErrorCode::TP_32BIT
  54                                 ? uint32_t(data.args[code.argno()])
  55                                 : data.args[code.argno()]) == code.value()
  56                                ? *code.passed()
  57                                : *code.failed(),
  58                                data);
  59     case ErrorCode::OP_HAS_ALL_BITS:
  60       return EvaluateErrorCode(sandbox,
  61                                ((code.width() == ErrorCode::TP_32BIT
  62                                  ? uint32_t(data.args[code.argno()])
  63                                  : data.args[code.argno()]) & code.value())
  64                                == code.value()
  65                                ? *code.passed()
  66                                : *code.failed(),
  67                                data);
  68     case ErrorCode::OP_HAS_ANY_BITS:
  69       return EvaluateErrorCode(sandbox,
  70                                (code.width() == ErrorCode::TP_32BIT
  71                                 ? uint32_t(data.args[code.argno()])
  72                                 : data.args[code.argno()]) & code.value()
  73                                ? *code.passed()
  74                                : *code.failed(),
  75                                data);
  76     default:
  77       return SECCOMP_RET_INVALID;
  78     }
  79   } else {
  80     return SECCOMP_RET_INVALID;
  81   }
  82 }
  83
  84 bool VerifyErrorCode(Sandbox *sandbox,
  85                      const std::vector<struct sock_filter>& program,
  86                      struct arch_seccomp_data *data,
  87                      const ErrorCode& root_code,
  88                      const ErrorCode& code,
  89                      const char **err) {
  90   if (code.error_type() == ErrorCode::ET_SIMPLE ||
  91       code.error_type() == ErrorCode::ET_TRAP) {
  92     uint32_t computed_ret = Verifier::EvaluateBPF(program, *data, err);
  93     if (*err) {
  94       return false;
  95     } else if (computed_ret != EvaluateErrorCode(sandbox, root_code, *data)) {
  96       // For efficiency's sake, we'd much rather compare "computed_ret"
  97       // against "code.err()". This works most of the time, but it doesn't
  98       // always work for nested conditional expressions. The test values
  99       // that we generate on the fly to probe expressions can trigger
 100       // code flow decisions in multiple nodes of the decision tree, and the
 101       // only way to compute the correct error code in that situation is by
 102       // calling EvaluateErrorCode().
 103       *err = "Exit code from BPF program doesn't match";
 104       return false;
 105     }
 106   } else if (code.error_type() == ErrorCode::ET_COND) {
 107     if (code.argno() < 0 || code.argno() >= 6) {
 108       *err = "Invalid argument number in error code";
 109       return false;
 110     }
 111     switch (code.op()) {
 112     case ErrorCode::OP_EQUAL:
 113       // Verify that we can check a 32bit value (or the LSB of a 64bit value)
 114       // for equality.
 115       data->args[code.argno()] = code.value();
 116       if (!VerifyErrorCode(sandbox, program, data, root_code,
 117                            *code.passed(), err)) {
 118         return false;
 119       }
 120
 121       // Change the value to no longer match and verify that this is detected
 122       // as an inequality.
 123       data->args[code.argno()] = code.value() ^ 0x55AA55AA;
 124       if (!VerifyErrorCode(sandbox, program, data, root_code,
 125                            *code.failed(), err)) {
 126         return false;
 127       }
 128
 129       // BPF programs can only ever operate on 32bit values. So, we have
 130       // generated additional BPF instructions that inspect the MSB. Verify
 131       // that they behave as intended.
 132       if (code.width() == ErrorCode::TP_32BIT) {
 133         if (code.value() >> 32) {
 134           SANDBOX_DIE("Invalid comparison of a 32bit system call argument "
 135                       "against a 64bit constant; this test is always false.");
 136         }
 137
 138         // If the system call argument was intended to be a 32bit parameter,
 139         // verify that it is a fatal error if a 64bit value is ever passed
 140         // here.
 141         data->args[code.argno()] = 0x100000000ull;
 142         if (!VerifyErrorCode(sandbox, program, data, root_code,
 143                              sandbox->Unexpected64bitArgument(),
 144                              err)) {
 145           return false;
 146         }
 147       } else {
 148         // If the system call argument was intended to be a 64bit parameter,
 149         // verify that we can handle (in-)equality for the MSB. This is
 150         // essentially the same test that we did earlier for the LSB.
 151         // We only need to verify the behavior of the inequality test. We
 152         // know that the equality test already passed, as unlike the kernel
 153         // the Verifier does operate on 64bit quantities.
 154         data->args[code.argno()] = code.value() ^ 0x55AA55AA00000000ull;
 155         if (!VerifyErrorCode(sandbox, program, data, root_code,
 156                              *code.failed(), err)) {
 157           return false;
 158         }
 159       }
 160       break;
 161     case ErrorCode::OP_HAS_ALL_BITS:
 162     case ErrorCode::OP_HAS_ANY_BITS:
 163       // A comprehensive test of bit values is difficult and potentially rather
 164       // time-expensive. We avoid doing so at run-time and instead rely on the
 165       // unittest for full testing. The test that we have here covers just the
 166       // common cases. We test against the bitmask itself, all zeros and all
 167       // ones.
 168       {
 169         // Testing "any" bits against a zero mask is always false. So, there
 170         // are some cases, where we expect tests to take the "failed()" branch
 171         // even though this is a test that normally should take "passed()".
 172         const ErrorCode& passed =
 173           (!code.value() && code.op() == ErrorCode::OP_HAS_ANY_BITS) ||
 174
 175           // On a 32bit system, it is impossible to pass a 64bit value as a
 176           // system call argument. So, some additional tests always evaluate
 177           // as false.
 178           ((code.value() & ~uint64_t(uintptr_t(-1))) &&
 179            code.op() == ErrorCode::OP_HAS_ALL_BITS) ||
 180           (code.value() && !(code.value() & uintptr_t(-1)) &&
 181            code.op() == ErrorCode::OP_HAS_ANY_BITS)
 182
 183           ? *code.failed() : *code.passed();
 184
 185         // Similary, testing for "all" bits in a zero mask is always true. So,
 186         // some cases pass despite them normally failing.
 187         const ErrorCode& failed =
 188           !code.value() && code.op() == ErrorCode::OP_HAS_ALL_BITS
 189           ? *code.passed() : *code.failed();
 190
 191         data->args[code.argno()] = code.value() & uintptr_t(-1);
 192         if (!VerifyErrorCode(sandbox, program, data, root_code, passed, err)) {
 193           return false;
 194         }
 195         data->args[code.argno()] = uintptr_t(-1);
 196         if (!VerifyErrorCode(sandbox, program, data, root_code, passed, err)) {
 197           return false;
 198         }
 199         data->args[code.argno()] = 0;
 200         if (!VerifyErrorCode(sandbox, program, data, root_code, failed, err)) {
 201           return false;
 202         }
 203       }
 204       break;
 205     default: // TODO(markus): Need to add support for OP_GREATER
 206       *err = "Unsupported operation in conditional error code";
 207       return false;
 208     }
 209   } else {
 210     *err = "Attempting to return invalid error code from BPF program";
 211     return false;
 212   }
 213   return true;
 214 }
 215
 216 void Ld(State *state, const struct sock_filter& insn, const char **err) {
 217   if (BPF_SIZE(insn.code) != BPF_W ||
 218       BPF_MODE(insn.code) != BPF_ABS) {
 219     *err = "Invalid BPF_LD instruction";
 220     return;
 221   }
 222   if (insn.k < sizeof(struct arch_seccomp_data) && (insn.k & 3) == 0) {
 223     // We only allow loading of properly aligned 32bit quantities.
 224     memcpy(&state->accumulator,
 225            reinterpret_cast<const char *>(&state->data) + insn.k,
 226            4);
 227   } else {
 228     *err = "Invalid operand in BPF_LD instruction";
 229     return;
 230   }
 231   state->acc_is_valid = true;
 232   return;
 233 }
 234
 235 void Jmp(State *state, const struct sock_filter& insn, const char **err) {
 236   if (BPF_OP(insn.code) == BPF_JA) {
 237     if (state->ip + insn.k + 1 >= state->program.size() ||
 238         state->ip + insn.k + 1 <= state->ip) {
 239     compilation_failure:
 240       *err = "Invalid BPF_JMP instruction";
 241       return;
 242     }
 243     state->ip += insn.k;
 244   } else {
 245     if (BPF_SRC(insn.code) != BPF_K ||
 246         !state->acc_is_valid ||
 247         state->ip + insn.jt + 1 >= state->program.size() ||
 248         state->ip + insn.jf + 1 >= state->program.size()) {
 249       goto compilation_failure;
 250     }
 251     switch (BPF_OP(insn.code)) {
 252     case BPF_JEQ:
 253       if (state->accumulator == insn.k) {
 254         state->ip += insn.jt;
 255       } else {
 256         state->ip += insn.jf;
 257       }
 258       break;
 259     case BPF_JGT:
 260       if (state->accumulator > insn.k) {
 261         state->ip += insn.jt;
 262       } else {
 263         state->ip += insn.jf;
 264       }
 265       break;
 266     case BPF_JGE:
 267       if (state->accumulator >= insn.k) {
 268         state->ip += insn.jt;
 269       } else {
 270         state->ip += insn.jf;
 271       }
 272       break;
 273     case BPF_JSET:
 274       if (state->accumulator & insn.k) {
 275         state->ip += insn.jt;
 276       } else {
 277         state->ip += insn.jf;
 278       }
 279       break;
 280     default:
 281       goto compilation_failure;
 282     }
 283   }
 284 }
 285
 286 uint32_t Ret(State *, const struct sock_filter& insn, const char **err) {
 287   if (BPF_SRC(insn.code) != BPF_K) {
 288     *err = "Invalid BPF_RET instruction";
 289     return 0;
 290   }
 291   return insn.k;
 292 }
 293
 294 void Alu(State *state, const struct sock_filter& insn, const char **err) {
 295   if (BPF_OP(insn.code) == BPF_NEG) {
 296     state->accumulator = -state->accumulator;
 297     return;
 298   } else {
 299     if (BPF_SRC(insn.code) != BPF_K) {
 300       *err = "Unexpected source operand in arithmetic operation";
 301       return;
 302     }
 303     switch (BPF_OP(insn.code)) {
 304     case BPF_ADD:
 305       state->accumulator += insn.k;
 306       break;
 307     case BPF_SUB:
 308       state->accumulator -= insn.k;
 309       break;
 310     case BPF_MUL:
 311       state->accumulator *= insn.k;
 312       break;
 313     case BPF_DIV:
 314       if (!insn.k) {
 315         *err = "Illegal division by zero";
 316         break;
 317       }
 318       state->accumulator /= insn.k;
 319       break;
 320     case BPF_MOD:
 321       if (!insn.k) {
 322         *err = "Illegal division by zero";
 323         break;
 324       }
 325       state->accumulator %= insn.k;
 326       break;
 327     case BPF_OR:
 328       state->accumulator |= insn.k;
 329       break;
 330     case BPF_XOR:
 331       state->accumulator ^= insn.k;
 332       break;
 333     case BPF_AND:
 334       state->accumulator &= insn.k;
 335       break;
 336     case BPF_LSH:
 337       if (insn.k > 32) {
 338         *err = "Illegal shift operation";
 339         break;
 340       }
 341       state->accumulator <<= insn.k;
 342       break;
 343     case BPF_RSH:
 344       if (insn.k > 32) {
 345         *err = "Illegal shift operation";
 346         break;
 347       }
 348       state->accumulator >>= insn.k;
 349       break;
 350     default:
 351       *err = "Invalid operator in arithmetic operation";
 352       break;
 353     }
 354   }
 355 }
 356
 357 }  // namespace
 358
 359 namespace playground2 {
 360
 361 bool Verifier::VerifyBPF(Sandbox *sandbox,
 362                          const std::vector<struct sock_filter>& program,
 363                          const Sandbox::Evaluators& evaluators,
 364                          const char **err) {
 365   *err = NULL;
 366   if (evaluators.size() != 1) {
 367     *err = "Not implemented";
 368     return false;
 369   }
 370   Sandbox::EvaluateSyscall evaluate_syscall = evaluators.begin()->first;
 371   void *aux                                 = evaluators.begin()->second;
 372   for (SyscallIterator iter(false); !iter.Done(); ) {
 373     uint32_t sysnum = iter.Next();
 374     // We ideally want to iterate over the full system call range and values
 375     // just above and just below this range. This gives us the full result set
 376     // of the "evaluators".
 377     // On Intel systems, this can fail in a surprising way, as a cleared bit 30
 378     // indicates either i386 or x86-64; and a set bit 30 indicates x32. And
 379     // unless we pay attention to setting this bit correctly, an early check in
 380     // our BPF program will make us fail with a misleading error code.
 381     struct arch_seccomp_data data = { static_cast<int>(sysnum),
 382                                       static_cast<uint32_t>(SECCOMP_ARCH) };
 383 #if defined(__i386__) || defined(__x86_64__)
 384 #if defined(__x86_64__) && defined(__ILP32__)
 385     if (!(sysnum & 0x40000000u)) {
 386       continue;
 387     }
 388 #else
 389     if (sysnum & 0x40000000u) {
 390       continue;
 391     }
 392 #endif
 393 #endif
 394     ErrorCode code = evaluate_syscall(sandbox, sysnum, aux);
 395     if (!VerifyErrorCode(sandbox, program, &data, code, code, err)) {
 396       return false;
 397     }
 398   }
 399   return true;
 400 }
 401
 402 uint32_t Verifier::EvaluateBPF(const std::vector<struct sock_filter>& program,
 403                                const struct arch_seccomp_data& data,
 404                                const char **err) {
 405   *err = NULL;
 406   if (program.size() < 1 || program.size() >= SECCOMP_MAX_PROGRAM_SIZE) {
 407     *err = "Invalid program length";
 408     return 0;
 409   }
 410   for (State state(program, data); !*err; ++state.ip) {
 411     if (state.ip >= program.size()) {
 412       *err = "Invalid instruction pointer in BPF program";
 413       break;
 414     }
 415     const struct sock_filter& insn = program[state.ip];
 416     switch (BPF_CLASS(insn.code)) {
 417     case BPF_LD:
 418       Ld(&state, insn, err);
 419       break;
 420     case BPF_JMP:
 421       Jmp(&state, insn, err);
 422       break;
 423     case BPF_RET: {
 424       uint32_t r = Ret(&state, insn, err);
 425       switch (r & SECCOMP_RET_ACTION) {
 426       case SECCOMP_RET_TRAP:
 427       case SECCOMP_RET_ERRNO:
 428       case SECCOMP_RET_ALLOW:
 429         break;
 430       case SECCOMP_RET_KILL:     // We don't ever generate this
 431       case SECCOMP_RET_TRACE:    // We don't ever generate this
 432       case SECCOMP_RET_INVALID:  // Should never show up in BPF program
 433       default:
 434         *err = "Unexpected return code found in BPF program";
 435         return 0;
 436       }
 437       return r; }
 438     case BPF_ALU:
 439       Alu(&state, insn, err);
 440       break;
 441     default:
 442       *err = "Unexpected instruction in BPF program";
 443       break;
 444     }
 445   }
 446   return 0;
 447 }
 448
 449 }  // namespace