[MIPS] Adding validator for MIPS architecture.

src/trusted/validator_mips/validator.cc

+/*
+ * Copyright (c) 2012 The Native Client 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 <assert.h>
+#include "native_client/src/trusted/service_runtime/nacl_config.h"
+#include "native_client/src/trusted/validator_mips/validator.h"
+#include "native_client/src/include/nacl_macros.h"
+
+
+using nacl_mips_dec::Instruction;
+using nacl_mips_dec::ClassDecoder;
+using nacl_mips_dec::Register;
+using nacl_mips_dec::RegisterList;
+
+using nacl_mips_dec::kRegisterJumpMask;
+using nacl_mips_dec::kRegisterLoadStoreMask;
+
+using nacl_mips_dec::kInstrSize;
+using nacl_mips_dec::kInstrAlign;
+
+using std::vector;
+
+namespace nacl_mips_val {
+
+/*********************************************************
+ * Implementations of patterns used in the first pass.
+ *
+ * N.B. IF YOU ADD A PATTERN HERE, REGISTER IT BELOW.
+ * See the list in apply_patterns.
+ *********************************************************/
+
+// A possible result from a validator pattern.
+enum PatternMatch {
+  // The pattern does not apply to the instructions it was given.
+  NO_MATCH,
+  // The pattern matches, and is safe; do not allow jumps to split it.
+  PATTERN_SAFE,
+  // The pattern matches, and has detected a problem.
+  PATTERN_UNSAFE
+};
+
+
+/*********************************************************
+ * One instruction patterns.
+ *********************************************************/
+
+/*
+ * Checks for instructions that are not allowed.
+ */
+static PatternMatch check_safety(const SfiValidator &sfi,
+                                 const DecodedInstruction &inst,
+                                 ProblemSink *out) {
+  UNREFERENCED_PARAMETER(sfi);
+  if (nacl_mips_dec::MAY_BE_SAFE != inst.safety()) {
+    out->report_problem(inst.addr(), inst.safety(), kProblemUnsafe);
+    return PATTERN_UNSAFE;
+  }
+  return PATTERN_SAFE;
+}
+
+/*
+ * Checks for instructions that alter read-only registers.
+ */
+static PatternMatch check_read_only(const SfiValidator &sfi,
+                                    const DecodedInstruction &inst,
+                                    ProblemSink *out) {
+  if (inst.is_dest_gpr_reg(sfi.read_only_registers())) {
+    out->report_problem(inst.addr(), inst.safety(), kProblemReadOnlyRegister);
+    return PATTERN_UNSAFE;
+  }
+  return NO_MATCH;
+}
+
+/*
+ * Checks the location of linking branches -- in order to be correct, the
+ * branches must be in the slot before the last slot.
+ *
+ */
+static PatternMatch check_call_position(const SfiValidator &sfi,
+                                        const DecodedInstruction &inst,
+                                        ProblemSink *out) {
+  if (inst.is_jal()) {
+    uint32_t end_addr = sfi.bundle_for_address(inst.addr()).end_addr();
+    uint32_t branch_slot = end_addr - (2 * kInstrSize);
+    if (inst.addr() != branch_slot) {
+      out->report_problem(inst.addr(), inst.safety(), kProblemMisalignedCall);
+      return PATTERN_UNSAFE;
+    }
+    return PATTERN_SAFE;
+  }
+  return NO_MATCH;
+}
+
+/*
+ * Checks for jumps to unsafe area.
+ */
+static PatternMatch check_jump_dest_addr(const SfiValidator &sfi,
+                                         const DecodedInstruction &instr,
+                                         ProblemSink *out) {
+  if (instr.is_direct_jump()) {
+    uint32_t dest_addr = instr.dest_addr();
+    if (dest_addr < sfi.trampoline_region_start()) {
+      //  Safe guard region, allow jumps if somebody is suicidal.
+      return PATTERN_SAFE;
+    } else if (dest_addr < sfi.code_region_start()) {
+      //  Trampoline region, allow only 0mod16.
+      if ((dest_addr & (sfi.bytes_per_bundle() - 1)) != 0) {
+        out->report_problem(instr.addr(), instr.safety(),
+                            kProblemUnalignedJumpToTrampoline);
+        return PATTERN_UNSAFE;
+      }
+      return PATTERN_SAFE;
+    } else {
+      // Jumps outside of unsafe region are not allowed.
+      if ((dest_addr & ~(sfi.code_address_mask())) != 0) {
+        out->report_problem(instr.addr(), instr.safety(),
+                            kProblemBranchInvalidDest);
+        return PATTERN_UNSAFE;
+      }
+      //  Another pattern is responsible for checking if it lands inside of a
+      //  pseudo-instruction.
+      return PATTERN_SAFE;
+    }
+  }
+  return NO_MATCH;
+}
+
+/*********************************************************
+ * Two instruction patterns.
+ *********************************************************/
+
+/*
+ * Checks if indirect jumps are guarded properly.
+ */
+static PatternMatch check_jmp_reg(const SfiValidator &sfi,
+                            const DecodedInstruction &first,
+                            const DecodedInstruction &second,
+                            ProblemSink *out) {
+  UNREFERENCED_PARAMETER(sfi);
+  if (second.is_jmp_reg()) {
+    if (first.is_mask(second.target_reg(), kRegisterJumpMask)) {
+      return PATTERN_SAFE;
+    }
+    out->report_problem(second.addr(), second.safety(),
+                        kProblemUnsafeJumpRegister);
+    return PATTERN_UNSAFE;
+  }
+  return NO_MATCH;
+}
+
+
+/*
+ * Checks if change of the data register ($sp) is followed by load/store mask.
+ */
+static PatternMatch check_data_register_update(const SfiValidator &sfi,
+                                               const DecodedInstruction &first,
+                                               const DecodedInstruction &second,
+                                               ProblemSink *out) {
+  if (first.is_dest_gpr_reg(sfi.data_address_registers())
+      && !first.is_mask(first.dest_gpr_reg(), kRegisterLoadStoreMask)) {
+    if (second.is_mask(first.dest_gpr_reg(), kRegisterLoadStoreMask)) {
+      return PATTERN_SAFE;
+    }
+    out->report_problem(first.addr(), first.safety(), kProblemUnsafeDataWrite);
+    return PATTERN_UNSAFE;
+  }
+  return NO_MATCH;
+}
+
+/*
+ * Checks if data register ($sp) change is in the delay slot.
+ */
+static PatternMatch check_data_register_dslot(const SfiValidator &sfi,
+                                              const DecodedInstruction &first,
+                                              const DecodedInstruction &second,
+                                              ProblemSink *out) {
+  if (second.is_dest_gpr_reg(sfi.data_address_registers())
+      && !second.is_mask(second.dest_gpr_reg(), kRegisterLoadStoreMask)) {
+    if (first.has_delay_slot()) {
+      out->report_problem(second.addr(), second.safety(),
+                          kProblemDataRegInDelaySlot);
+      return PATTERN_UNSAFE;
+    }
+  }
+  return NO_MATCH;
+}
+
+/*
+ * Checks if load and store instructions are preceded by load/store mask.
+ */
+static PatternMatch check_load_store(const SfiValidator &sfi,
+                                     const DecodedInstruction &first,
+                                     const DecodedInstruction &second,
+                                     ProblemSink *out) {
+  if (second.is_load_store()) {
+    Register base_addr_reg = second.base_address_register();
+    if (!sfi.data_address_registers().contains_all(base_addr_reg)) {
+      if (first.is_mask(base_addr_reg, kRegisterLoadStoreMask)) {
+        return PATTERN_SAFE;
+      }
+      out->report_problem(second.addr(), second.safety(),
+                          kProblemUnsafeLoadStore);
+      return PATTERN_UNSAFE;
+      }
+  }
+  return NO_MATCH;
+}
+
+
+/*********************************************************
+ * Pseudo-instruction patterns.
+ *********************************************************/
+
+/*
+ * Checks if a pseudo-instruction that starts with instr will cross bundle
+ * border (i.e. if it starts in one and ends in second).
+ * The exception to this rule are pseudo-instructions altering the data register
+ * value (because mask is the second instruction).
+ */
+static PatternMatch check_bundle_cross(const SfiValidator &sfi,
+                                       const DecodedInstruction instr,
+                                       ProblemSink *out) {
+  uint32_t begin_addr = sfi.bundle_for_address(instr.addr()).begin_addr();
+  if ((instr.addr() == begin_addr) && !instr.is_data_reg_mask()) {
+    out->report_problem(instr.addr(), instr.safety(),
+                        kProblemPatternCrossesBundle);
+    return PATTERN_UNSAFE;
+  }
+  return PATTERN_SAFE;
+}
+
+/*
+ * Checks if branch instruction will jump in the middle of pseudo-instruction.
+ */
+static PatternMatch check_jump_to_pseudo(const SfiValidator &sfi,
+                                         const std::vector<CodeSegment> &segms,
+                                         const DecodedInstruction pseudoinstr,
+                                         const AddressSet &branches,
+                                         const AddressSet &branch_targets,
+                                         ProblemSink *out) {
+  uint32_t target_va = pseudoinstr.addr();
+  if (branch_targets.contains(target_va)) {
+    std::vector<DecodedInstruction> instrs;
+    if (sfi.find_branch(segms, branches, target_va, instrs)) {
+      for (uint32_t i = 0; i < instrs.size(); i++) {
+        out->report_problem(instrs[i].addr(), instrs[i].safety(),
+                            kProblemBranchSplitsPattern);
+      }
+      return PATTERN_UNSAFE;
+    } else {
+      assert(0);
+    }
+  }
+  return PATTERN_SAFE;
+}
+
+
+/*********************************************************
+ *
+ * Implementation of SfiValidator itself.
+ *
+ *********************************************************/
+SfiValidator::SfiValidator(uint32_t bytes_per_bundle,
+                           uint32_t code_region_bytes,
+                           uint32_t data_region_bytes,
+                           RegisterList read_only_registers,
+                           RegisterList data_address_registers)
+    : bytes_per_bundle_(bytes_per_bundle),
+      code_region_bytes_(code_region_bytes),
+      data_address_mask_(~(data_region_bytes - 1)),
+      code_address_mask_((code_region_bytes - 1) & kInstrAlign),  // 0x0FFFFFFC
+      read_only_registers_(read_only_registers),
+      data_address_registers_(data_address_registers),
+      decode_state_(nacl_mips_dec::init_decode()) {}
+
+bool SfiValidator::validate(const vector<CodeSegment> &segments,
+                            ProblemSink *out) {
+  uint32_t base = segments[0].begin_addr();
+  uint32_t size = segments.back().end_addr() - base;
+  AddressSet branches(base, size);
+  AddressSet branch_targets(base, size);
+  AddressSet critical(base, size);
+
+  bool complete_success = true;
+
+  for (vector<CodeSegment>::const_iterator it = segments.begin();
+      it != segments.end(); ++it) {
+    complete_success &= validate_fallthrough(*it, out, &branches,
+                                             &branch_targets, &critical);
+
+    if (!out->should_continue()) {
+      return false;
+    }
+  }
+
+  complete_success &= validate_pseudos(*this, segments,
+                                       branches, branch_targets, critical, out);
+  return complete_success;
+}
+
+bool SfiValidator::validate_fallthrough(const CodeSegment &segment,
+                                        ProblemSink *out,
+                                        AddressSet *branches,
+                                        AddressSet *branch_targets,
+                                        AddressSet *critical) {
+  bool complete_success = true;
+
+  nacl_mips_dec::Forbidden initial_decoder;
+  // Initialize the previous instruction to a syscall, so patterns all fail.
+  DecodedInstruction prev(
+      0,         // Virtual address 0, which will be in a different bundle.
+      Instruction(0x0000000c),  // syscall.
+      initial_decoder);         // and ensure that it decodes as Forbidden.
+
+  for (uint32_t va = segment.begin_addr(); va != segment.end_addr();
+       va += kInstrSize) {
+    DecodedInstruction inst(va, segment[va],
+                            nacl_mips_dec::decode(segment[va], decode_state_));
+
+    complete_success &= apply_patterns(inst, out);
+    if (!out->should_continue()) return false;
+
+    complete_success &= apply_patterns(prev, inst, critical, out);
+    if (!out->should_continue()) return false;
+
+    if (inst.is_direct_jump()) {
+      branches->add(inst.addr());
+      branch_targets->add(inst.dest_addr());
+    }
+
+    prev = inst;
+  }
+  return complete_success;
+}
+
+bool SfiValidator::validate_pseudos(const SfiValidator &sfi,
+                                    const std::vector<CodeSegment> &segments,
+                                    const AddressSet &branches,
+                                    const AddressSet &branch_targets,
+                                    const AddressSet &critical,
+                                    ProblemSink* out) {
+  bool complete_success = true;
+  vector<CodeSegment>::const_iterator seg_it = segments.begin();
+
+  for (AddressSet::Iterator it = critical.begin(); it != critical.end(); ++it) {
+    uint32_t va = *it;
+
+    while (!seg_it->contains_address(va)) {
+      ++seg_it;
+    }
+
+    const CodeSegment &segment = *seg_it;
+    DecodedInstruction inst_p(va,
+                              segment[va],
+                              nacl_mips_dec::decode(segment[va],
+                              decode_state_));
+
+    //  Check if the pseudo-instruction will cross bundle borders.
+    complete_success &= check_bundle_cross(sfi, inst_p, out);
+
+    //  Check if direct jumps destination is inside of a pseudo-instruction.
+    complete_success &= check_jump_to_pseudo(sfi, segments, inst_p, branches,
+                                             branch_targets, out);
+  }
+
+  return complete_success;
+}
+
+
+bool SfiValidator::apply_patterns(const DecodedInstruction &inst,
+    ProblemSink *out) {
+  //  Single-instruction patterns.
+  typedef PatternMatch (*OneInstPattern)(const SfiValidator &,
+                                         const DecodedInstruction &,
+                                         ProblemSink *out);
+  static const OneInstPattern one_inst_patterns[] = {
+    &check_safety,
+    &check_read_only,
+    &check_call_position,
+    &check_jump_dest_addr
+  };
+
+  bool complete_success = true;
+
+  for (uint32_t i = 0; i < NACL_ARRAY_SIZE(one_inst_patterns); i++) {
+    PatternMatch r = one_inst_patterns[i](*this, inst, out);
+    switch (r) {
+      case PATTERN_SAFE:
+      case NO_MATCH:
+        break;
+
+      case PATTERN_UNSAFE:
+        complete_success = false;
+        break;
+    }
+  }
+  return complete_success;
+}
+
+bool SfiValidator::apply_patterns(const DecodedInstruction &first,
+    const DecodedInstruction &second, AddressSet *critical, ProblemSink *out) {
+  //  Type for two-instruction pattern functions.
+  typedef PatternMatch (*TwoInstPattern)(const SfiValidator &,
+                                         const DecodedInstruction &first,
+                                         const DecodedInstruction &second,
+                                         ProblemSink *out);
+  //  The list of patterns -- defined in static functions up top.
+  static const TwoInstPattern two_inst_patterns[] = {
+    &check_jmp_reg,
+    &check_data_register_update,
+    &check_data_register_dslot,
+    &check_load_store
+  };
+
+  bool complete_success = true;
+
+  for (uint32_t i = 0; i < NACL_ARRAY_SIZE(two_inst_patterns); i++) {
+    PatternMatch r = two_inst_patterns[i](*this, first, second, out);
+    switch (r) {
+      case NO_MATCH:
+         break;
+      case PATTERN_UNSAFE:
+        // Pattern is in charge of reporting specific issue.
+        complete_success = false;
+        break;
+      case PATTERN_SAFE:
+        critical->add(second.addr());
+        break;
+    }
+  }
+  return complete_success;
+}
+
+bool SfiValidator::is_data_address_register(Register r) const {
+  return data_address_registers_[r];
+}
+
+bool SfiValidator::is_bundle_head(uint32_t address) const {
+  return (address % bytes_per_bundle_) == 0;
+}
+
+const Bundle SfiValidator::bundle_for_address(uint32_t address) const {
+  uint32_t base = address - (address % bytes_per_bundle_);
+  return Bundle(base, bytes_per_bundle_);
+}
+
+bool SfiValidator::find_branch(const std::vector<CodeSegment> &segments,
+                               const AddressSet &branches,
+                               uint32_t dest_address,
+                               std::vector<DecodedInstruction> &instrs) const {
+  vector<CodeSegment>::const_iterator seg_it = segments.begin();
+
+  for (AddressSet::Iterator it = branches.begin(); it != branches.end(); ++it) {
+    uint32_t va = *it;
+
+    while (!seg_it->contains_address(va)) {
+      ++seg_it;
+    }
+
+    const CodeSegment &segment = *seg_it;
+    DecodedInstruction instr = DecodedInstruction(va, segment[va],
+                             nacl_mips_dec::decode(segment[va], decode_state_));
+    if (instr.dest_addr() == dest_address) {
+      instrs.push_back(instr);
+    }
+  }
+  if (!instrs.empty()) return true;
+  return false;
+}
+/*
+ * DecodedInstruction.
+ */
+DecodedInstruction::DecodedInstruction(uint32_t vaddr,
+                                       Instruction inst,
+                                       const ClassDecoder &decoder)
+    : vaddr_(vaddr),
+      inst_(inst),
+      decoder_(&decoder),
+      safety_(decoder.safety(inst_))
+{}
+
+}  // namespace