Intial Thumb2 Sandbox (naclrev 6680)

src/trusted/validator_arm/validator.cc

Index: src/trusted/validator_arm/validator.cc
diff --git a/src/trusted/validator_arm/validator.cc b/src/trusted/validator_arm/validator.cc
index 782abb191efc143ffb721e086b91f3f912766854..4f5c522eb2e0846e706c5f320fd2b2bdc357362c 100644
--- a/src/trusted/validator_arm/validator.cc
+++ b/src/trusted/validator_arm/validator.cc
@@ -1,14 +1,14 @@
 /*
- * Copyright 2009 The Native Client Authors.  All rights reserved.
+ * Copyright (c) 2011 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.
- * Copyright 2009, Google Inc.
+ * Copyright (c) 2011, Google Inc.
  */
 
 #include "native_client/src/trusted/service_runtime/nacl_config.h"
 #include "native_client/src/trusted/validator_arm/validator.h"
 #include "native_client/src/include/nacl_macros.h"
-
+#include <assert.h>
 using nacl_arm_dec::Instruction;
 using nacl_arm_dec::ClassDecoder;
 using nacl_arm_dec::Register;
@@ -28,15 +28,12 @@ namespace nacl_arm_val {
  * 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
-};
+// A few convenience items for return values.
+PatternMatch NO_MATCH = {NO_MATCH_MODE, 0};
+PatternMatch PATTERN_UNSAFE = {PATTERN_UNSAFE_MODE, 0};
+PatternMatch PATTERN_SAFE_3 = {PATTERN_SAFE_MODE, 3};
+PatternMatch PATTERN_SAFE_2 = {PATTERN_SAFE_MODE, 2};
+PatternMatch PATTERN_SAFE_1 = {PATTERN_SAFE_MODE, 1};
 
 /*
  * Ensures that all stores use a safe base address.  A base address is safe if
@@ -49,9 +46,11 @@ enum PatternMatch {
  * This pattern concerns itself with case #1, early-exiting if it finds #2.
  */
 static PatternMatch check_store_mask(const SfiValidator &sfi,
-                                     const DecodedInstruction &first,
-                                     const DecodedInstruction &second,
+                                     DecodedInstruction insns[],
                                      ProblemSink *out) {
+  const DecodedInstruction first  = insns[kMaxPattern - 2];
+  const DecodedInstruction second = insns[kMaxPattern - 1];
+
   if (second.base_address_register() == kRegisterNone /* not a store */
       || sfi.is_data_address_register(second.base_address_register())) {
     return NO_MATCH;
@@ -60,13 +59,13 @@ static PatternMatch check_store_mask(const SfiValidator &sfi,
   if (first.defines(second.base_address_register())
       && first.clears_bits(sfi.data_address_mask())
       && first.always_precedes(second)) {
-    return PATTERN_SAFE;
+    return PATTERN_SAFE_2;
   }
 
   if (first.sets_Z_if_bits_clear(second.base_address_register(),
                                  sfi.data_address_mask())
       && second.is_conditional_on(first)) {
-    return PATTERN_SAFE;
+    return PATTERN_SAFE_2;
   }
 
   out->report_problem(second.addr(), second.safety(), kProblemUnsafeStore);
@@ -79,15 +78,28 @@ static PatternMatch check_store_mask(const SfiValidator &sfi,
  * immediate predecessor.
  */
 static PatternMatch check_branch_mask(const SfiValidator &sfi,
-                                      const DecodedInstruction &first,
-                                      const DecodedInstruction &second,
+                                      DecodedInstruction insns[],
                                       ProblemSink *out) {
+  const DecodedInstruction zeroth = insns[kMaxPattern - 3];
+  const DecodedInstruction first  = insns[kMaxPattern - 2];
+  const DecodedInstruction second = insns[kMaxPattern - 1];
   if (second.branch_target_register() == kRegisterNone) return NO_MATCH;
 
-  if (first.defines(second.branch_target_register())
+
+  if ((sfi.code_address_ormask() == 0)
+      && first.defines(second.branch_target_register())
       && first.clears_bits(sfi.code_address_mask())
       && first.always_precedes(second)) {
-    return PATTERN_SAFE;
+    return PATTERN_SAFE_2;
+  }
+
+  if (first.defines(second.branch_target_register())
+      && first.sets_bits(sfi.code_address_ormask())
+      && first.always_precedes(second)
+      && zeroth.defines(second.branch_target_register())
+      && zeroth.clears_bits(sfi.code_address_mask())
+      && zeroth.always_precedes(first)) {
+    return PATTERN_SAFE_3;
   }
 
   out->report_problem(second.addr(), second.safety(), kProblemUnsafeBranch);
@@ -99,9 +111,10 @@ static PatternMatch check_branch_mask(const SfiValidator &sfi,
  * immediately followed by a mask.
  */
 static PatternMatch check_data_register_update(const SfiValidator &sfi,
-                                               const DecodedInstruction &first,
-                                               const DecodedInstruction &second,
+                                               DecodedInstruction insns[],
                                                ProblemSink *out) {
+  const DecodedInstruction first  = insns[kMaxPattern - 2];
+  const DecodedInstruction second = insns[kMaxPattern - 1];
   if (!first.defines_any(sfi.data_address_registers())) return NO_MATCH;
 
   // A single safe data register update doesn't affect control flow.
@@ -117,7 +130,7 @@ static PatternMatch check_data_register_update(const SfiValidator &sfi,
   if (second.defines_all(data_addr_defs)
       && second.clears_bits(sfi.data_address_mask())
       && second.always_follows(first)) {
-    return PATTERN_SAFE;
+    return PATTERN_SAFE_2;
   }
 
   out->report_problem(first.addr(), first.safety(), kProblemUnsafeDataWrite);
@@ -131,6 +144,10 @@ static PatternMatch check_data_register_update(const SfiValidator &sfi,
  * This is not a security check per se, more of a guard against Stupid Compiler
  * Tricks.
  */
+// This function is currently thumb-unsafe due to the -4. Will re-enable when it
+// is 100% clear how to handle, as this is not a safety issue.
+// TODO(mrm) re-enable

[bsy, 2011/09/16 18:35:52]

s/mrm/jasonwkim/  cannot assign TODO to people who aren't working on the code.

+#if 0
 static PatternMatch check_call_position(const SfiValidator &sfi,
                                         const DecodedInstruction &inst,
                                         ProblemSink *out) {
@@ -144,13 +161,15 @@ static PatternMatch check_call_position(const SfiValidator &sfi,
   }
   return NO_MATCH;
 }
+#endif
 
 /*
  * Checks for instructions that alter any read-only register.
  */
 static PatternMatch check_read_only(const SfiValidator &sfi,
-                                    const DecodedInstruction &inst,
+                                    DecodedInstruction insns[],
                                     ProblemSink *out) {
+  DecodedInstruction inst = insns[kMaxPattern - 1];
   if (inst.defines_any(sfi.read_only_registers())) {
     out->report_problem(inst.addr(), inst.safety(), kProblemReadOnlyRegister);
     return PATTERN_UNSAFE;
@@ -163,8 +182,9 @@ static PatternMatch check_read_only(const SfiValidator &sfi,
  * Checks writes to r15 from instructions that aren't branches.
  */
 static PatternMatch check_pc_writes(const SfiValidator &sfi,
-                                    const DecodedInstruction &inst,
+                                    DecodedInstruction insns[],
                                     ProblemSink *out) {
+  DecodedInstruction inst = insns[kMaxPattern - 1];
   if (inst.is_relative_branch()
       || inst.branch_target_register() != kRegisterNone) {
     // It's a branch.
@@ -172,15 +192,53 @@ static PatternMatch check_pc_writes(const SfiValidator &sfi,
   }
 
   if (!inst.defines(nacl_arm_dec::kRegisterPc)) return NO_MATCH;
-
+// TODO(mrm) The clears_bits thing here doesn't save us, secvuln

[bsy, 2011/09/16 18:35:52]

explain/expand on this please.  if there is really a security vulnerability,
there should be an explanation for why and a bug filed, ideally w/ the details
in the issue and the issue # in here.

ditto on mrm.

   if (inst.clears_bits(sfi.code_address_mask())) {
-    return PATTERN_SAFE;
+    return PATTERN_SAFE_1;
   } else {
     out->report_problem(inst.addr(), inst.safety(), kProblemUnsafeBranch);
     return PATTERN_UNSAFE;
   }
 }
 
+/*
+ * Groups IT blocks together, sets appropriate condition flags on them.
+ */
+static PatternMatch check_it(const SfiValidator &sfi,
+                             DecodedInstruction insns[],
+                             ProblemSink *out) {
+  UNREFERENCED_PARAMETER(sfi);
+  DecodedInstruction insn_it = insns[0];
+  nacl_arm_dec::ITCond it = insn_it.it();
+  if (!it)
+    return NO_MATCH;  // Not an IT instruction.
+  Instruction::Condition cond = insn_it.condition();
+  if ((cond == Instruction::AL) || (cond == Instruction::UNCONDITIONAL)) {
+    out->report_problem(insn_it.addr(), insn_it.safety(),
+                        kProblemUnconditionalIT);
+    return PATTERN_UNSAFE;  // This is nonsense, but encodeable.
+  }
+  // This is an IT instruction. We inform the affected instructions
+  // of their affectedness, and accept the pattern.
+  uint8_t conddex = 0;
+  for (; nacl_arm_dec::it_select(conddex, it) != nacl_arm_dec::NONE; conddex++)
+    if (nacl_arm_dec::it_select(conddex, it) == nacl_arm_dec::THEN)
+      insns[conddex + 1].set_condition(cond);
+    else if (nacl_arm_dec::it_select(conddex, it) == nacl_arm_dec::ELSE)
+      insns[conddex + 1].set_condition((Instruction::Condition)(cond ^ 1));
+    else return PATTERN_UNSAFE; /* Should never be reached */
+    // Check that this insn is allowed at this point in an IT
+    switch (insns[conddex + 1].it_safe()) {
+      default:
+      case nacl_arm_dec::NEVER: return PATTERN_UNSAFE;
+      case nacl_arm_dec::END:
+        if (nacl_arm_dec::it_select(conddex + 1, it) != nacl_arm_dec::NONE)
+          return PATTERN_UNSAFE;
+      case nacl_arm_dec::ALWAYS: {}  // Fall through, we're fine.
+    }
+  PatternMatch p = {PATTERN_SAFE_MODE, -(conddex + 1)};
+  return p;
+}
 /*********************************************************
  *
  * Implementation of SfiValidator itself.
@@ -191,14 +249,21 @@ 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)
+                           RegisterList data_address_registers,
+                           bool thumb)
     : bytes_per_bundle_(bytes_per_bundle),
       data_address_mask_(~(data_region_bytes - 1)),
-      code_address_mask_(~(code_region_bytes - 1) | (bytes_per_bundle - 1)),
+      code_address_mask_(thumb
+                        ? ~(code_region_bytes - 1)
+                        : ~(code_region_bytes - 1) | (bytes_per_bundle - 1)),
+      code_address_ormask_(thumb
+                        ? (bytes_per_bundle - 1)
+                        : 0),
       code_region_bytes_(code_region_bytes),
       read_only_registers_(read_only_registers),
       data_address_registers_(data_address_registers),
-      decode_state_(nacl_arm_dec::init_decode()) {}
+      thumb_(thumb ? 1 : 0),
+      decode_state_(nacl_arm_dec::init_decode(thumb)) {}
 
 bool SfiValidator::validate(const vector<CodeSegment> &segments,
                             ProblemSink *out) {
@@ -228,50 +293,108 @@ bool SfiValidator::validate_fallthrough(const CodeSegment &segment,
                                         AddressSet *branches,
                                         AddressSet *critical) {
   bool complete_success = true;
+// The list of initial patterns to run (during the first window)
+  static const Pattern pre_patterns[] = {&check_it};
+
+// The list of patterns to run in the second window.
+  static const Pattern patterns[] = {
+    &check_read_only,
+    &check_pc_writes,
+// TODO(mrm) re-enable (see comment on actual function)

[bsy, 2011/09/16 18:35:52]

"

[jasonwkim, 2011/09/16 20:09:17]

All TODO(mrm) haver been replaceds

+    // &check_call_position,
+    &check_store_mask,
+    &check_branch_mask,
+    &check_data_register_update,
+  };
 
   nacl_arm_dec::Forbidden initial_decoder;
   // Initialize the previous instruction to a scary BKPT, so patterns all fail.
-  DecodedInstruction pred(
+  DecodedInstruction bkpt(
       0,  // Virtual address 0, which will be in a different bundle;
       Instruction(0xE1277777),  // The literal-pool-header BKPT instruction;
       initial_decoder);  // and ensure that it decodes as Forbidden.
-
-  for (uint32_t va = segment.begin_addr(); va != segment.end_addr(); va += 4) {
-    DecodedInstruction inst(va, segment[va],
+// TODO(mrm) Figure out how to make this vary automatically
+  DecodedInstruction insns[kMaxPattern] = {bkpt, bkpt, bkpt, bkpt, bkpt};
+  DecodedInstruction pre_insns[kMaxPattern] = {bkpt, bkpt, bkpt, bkpt, bkpt};
+  uint8_t insn_size = 0;
+  uint8_t flush = 0;
+  uint32_t va = segment.begin_addr();
+  uint32_t va_code = va + thumb_;
+  while (flush < kMaxPattern) {
+    va_code = va + thumb_;
+    if (va != segment.end_addr()) {
+      DecodedInstruction inst(va_code, segment[va],
                             nacl_arm_dec::decode(segment[va], decode_state_));
-
-    if (inst.safety() != nacl_arm_dec::MAY_BE_SAFE) {
-      out->report_problem(va, inst.safety(), kProblemUnsafe);
+      pre_insns[kMaxPattern - 1] = inst;
+      insn_size = inst.size();
+      if (inst.safety() != nacl_arm_dec::MAY_BE_SAFE) {
+        out->report_problem(va_code, inst.safety(), kProblemUnsafe);
+        if (!out->should_continue()) {
+          return false;
+        }
+        complete_success = false;
+      }
+    } else {
+      pre_insns[kMaxPattern - 1] = bkpt;
+      flush++;
+    }
+    if (va > segment.end_addr()) {
+      out->report_problem(va_code - insn_size, nacl_arm_dec::FORBIDDEN,
+                          kProblemStraddlesSegment);
+      complete_success = false;
       if (!out->should_continue()) {
         return false;
       }
-      complete_success = false;
     }
-
-    complete_success &= apply_patterns(inst, out);
-    if (!out->should_continue()) return false;
-
-    complete_success &= apply_patterns(pred, inst, critical, out);
+    complete_success &= apply_patterns(pre_insns, pre_patterns,
+                                   NACL_ARRAY_SIZE(pre_patterns),
+                                   critical, out);
+    complete_success &= apply_patterns(insns, patterns,
+                                   NACL_ARRAY_SIZE(patterns), critical, out);
     if (!out->should_continue()) return false;
 
-    if (inst.is_relative_branch()) {
-      branches->add(inst.addr());
+    if (insns[kMaxPattern - 1].is_relative_branch()) {
+      branches->add(insns[kMaxPattern - 1].addr());
     }
 
-    if (inst.is_literal_pool_head()
-        && is_bundle_head(inst.addr())) {
+    if (pre_insns[kMaxPattern - 1].is_literal_pool_head()
+        && is_bundle_head(pre_insns[kMaxPattern - 1].addr())) {
       // Add each instruction in this bundle to the critical set.
-      uint32_t last_data_addr = bundle_for_address(va).end_addr();
-      for (; va != last_data_addr; va += 4) {
+      // Note, we increment va by 2 every time to deal with
+      // variable width instructions.
+      va = pre_insns[kMaxPattern - 1].addr() - thumb_;
+      uint32_t last_data_addr =
+          bundle_for_address(va + thumb_).end_addr()
+          - thumb_;
+      // last_data_addr cannot go beyond our segment
+      if (last_data_addr > segment.end_addr())
+        last_data_addr = segment.end_addr();
+
+      assert((last_data_addr - va <= bytes_per_bundle_ &&
+             ((last_data_addr - va) & 1) == 0) &&
+             "va and last_data_addr must be even (even in thumb2");
+
+
+      for (; va != last_data_addr; va += 2) {
         critical->add(va);
       }
-
+      // Wipe our slate clean with unsafe breakpoints
+      for (uint8_t i = 0; i < kMaxPattern - 1; i++) {
+        insns[i] = bkpt;
+        pre_insns[i] = bkpt;
+      }
       // Decrement the virtual address by one instruction, so the for
       // loop can bump it back forward.  This is slightly dirty.
-      va -= 4;
+      va -= insn_size;
     }
-
-    pred = inst;
+    // Pushback
+    for (uint8_t i = 0; i < kMaxPattern - 1; i++)
+      insns[i] = insns[i + 1];
+    insns[kMaxPattern - 1] = pre_insns[0];
+    for (uint8_t i = 0; i < kMaxPattern - 1; i++)
+      pre_insns[i] = pre_insns[i + 1];
+    if (flush == 0)
+      va += insn_size;
   }
 
   return complete_success;
@@ -290,6 +413,7 @@ bool SfiValidator::validate_branches(const vector<CodeSegment> &segments,
                                      const AddressSet &critical,
                                      ProblemSink *out) {
   bool complete_success = true;
+  const uint32_t low_bitmask = 0xFFFFFFFE;
 
   vector<CodeSegment>::const_iterator seg_it = segments.begin();
 
@@ -309,8 +433,8 @@ bool SfiValidator::validate_branches(const vector<CodeSegment> &segments,
 
     // We know it is_relative_branch(), so we can simply call:
     uint32_t target_va = inst.branch_target();
-    if (address_contained(target_va, segments)) {
-      if (critical.contains(target_va)) {
+    if (address_contained(target_va & low_bitmask, segments)) {
+      if (critical.contains(target_va & low_bitmask)) {
         out->report_problem(va, inst.safety(), kProblemBranchSplitsPattern,
                             target_va);
         if (!out->should_continue()) {
@@ -318,11 +442,15 @@ bool SfiValidator::validate_branches(const vector<CodeSegment> &segments,
         }
         complete_success = false;
       }
-    } else if ((target_va & code_address_mask()) == 0) {
-      // Allow bundle-aligned, in-range direct jump.
+    } else if ((((target_va & (~code_address_mask()))
+               | code_address_ormask()) & low_bitmask) ==
+               (target_va & low_bitmask)) {
+      // If the masking operations would not modify the va, it is allowed
+      // Subltety: A non-register branch cannot transition between thumb and
+      // non-thumb mode, so we intentionally omit the low bit.
     } else {
-      out->report_problem(va, inst.safety(), kProblemBranchInvalidDest,
-                          target_va);
+      out->report_problem(va | thumb_, inst.safety(),
+                          kProblemBranchInvalidDest, target_va);
       if (!out->should_continue()) {
         return false;
       }
@@ -333,71 +461,48 @@ bool SfiValidator::validate_branches(const vector<CodeSegment> &segments,
   return complete_success;
 }
 
-bool SfiValidator::apply_patterns(const DecodedInstruction &inst,
+bool SfiValidator::apply_patterns(DecodedInstruction insns[],
+    const Pattern patterns[], unsigned int nPatterns, AddressSet *critical,
     ProblemSink *out) {
-  // Single-instruction patterns
-  typedef PatternMatch (*OneInstPattern)(const SfiValidator &,
-                                         const DecodedInstruction &,
-                                         ProblemSink *out);
-  static const OneInstPattern one_inst_patterns[] = {
-    &check_read_only,
-    &check_pc_writes,
-    &check_call_position,
-  };
-
-  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_store_mask,
-    &check_branch_mask,
-    &check_data_register_update,
-  };
 
   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;
+  for (uint32_t i = 0; i < nPatterns; i++) {
+    PatternMatch r = patterns[i](*this, insns, out);
+    switch (r.pm_mode) {
+      case NO_MATCH_MODE: break;
 
-      case PATTERN_UNSAFE:
+      case PATTERN_UNSAFE_MODE:
         // Pattern is in charge of reporting specific issue.
         complete_success = false;
         break;
 
-      case PATTERN_SAFE:
-        if (bundle_for_address(first.addr())
-            != bundle_for_address(second.addr())) {
-          complete_success = false;
-          out->report_problem(first.addr(), first.safety(),
-                              kProblemPatternCrossesBundle);
+      case PATTERN_SAFE_MODE:
+        bool in_bundle = true;
+        if (r.size >= 0) {
+          for (int8_t i = kMaxPattern - 2; i >= kMaxPattern - r.size; i--) {
+            in_bundle &= (bundle_for_address(insns[i].addr()) ==
+                          bundle_for_address(insns[i + 1].addr()));
+            critical->add(insns[i + 1].addr());
+          }
+          if (!in_bundle) {
+            complete_success = false;
+            out->report_problem(insns[kMaxPattern-r.size].addr(),
+                                insns[kMaxPattern-r.size].safety(),
+                                kProblemPatternCrossesBundle);
+          }
         } else {
-          critical->add(second.addr());
+          for (int8_t i = 1; i < (-r.size); i++) {
+            in_bundle &= (bundle_for_address(insns[i].addr()) ==
+                          bundle_for_address(insns[i - 1].addr()));
+            critical->add(insns[i].addr());
+          }
+          if (!in_bundle) {
+            complete_success = false;
+            out->report_problem(insns[0].addr(),
+                                insns[0].safety(),
+                                kProblemPatternCrossesBundle);
+          }
         }
         break;
     }
@@ -410,12 +515,14 @@ bool SfiValidator::is_data_address_register(Register r) const {
 }
 
 const Bundle SfiValidator::bundle_for_address(uint32_t address) const {
-  uint32_t base = address - (address % bytes_per_bundle_);
-  return Bundle(base, bytes_per_bundle_);
+// TODO(mrm) Is it a security flaw that this can point at below entry?
+  uint32_t shift_address = address - code_address_ormask_;
+  uint32_t base = shift_address - (shift_address % bytes_per_bundle_);
+  return Bundle(base + code_address_ormask_, bytes_per_bundle_);
 }
 
 bool SfiValidator::is_bundle_head(uint32_t address) const {
-  return (address % bytes_per_bundle_) == 0;
+  return (address % bytes_per_bundle_) == code_address_ormask_;
 }
 
 
@@ -430,7 +537,8 @@ DecodedInstruction::DecodedInstruction(uint32_t vaddr,
       inst_(inst),
       decoder_(&decoder),
       safety_(decoder.safety(inst_)),
-      defs_(decoder.defs(inst_))
+      defs_(decoder.defs(inst_)),
+      condition_(Instruction::UNCONDITIONAL)
 {}
 
 }  // namespace