Index: src/trusted/validator_mips/validator.cc |
diff --git a/src/trusted/validator_mips/validator.cc b/src/trusted/validator_mips/validator.cc |
new file mode 100755 |
index 0000000000000000000000000000000000000000..8bff0fb7f95998dcc15ddf0bde8088a2f448c1d0 |
--- /dev/null |
+++ b/src/trusted/validator_mips/validator.cc |
@@ -0,0 +1,485 @@ |
+/* |
+ * 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 |