OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * Copyright (c) 2012 The Native Client Authors. All rights reserved. |
| 3 * Use of this source code is governed by a BSD-style license that can be |
| 4 * found in the LICENSE file. |
| 5 */ |
| 6 |
| 7 #include <assert.h> |
| 8 #include "native_client/src/trusted/service_runtime/nacl_config.h" |
| 9 #include "native_client/src/trusted/validator_mips/validator.h" |
| 10 #include "native_client/src/include/nacl_macros.h" |
| 11 |
| 12 |
| 13 using nacl_mips_dec::Instruction; |
| 14 using nacl_mips_dec::ClassDecoder; |
| 15 using nacl_mips_dec::Register; |
| 16 using nacl_mips_dec::RegisterList; |
| 17 |
| 18 using nacl_mips_dec::kRegisterJumpMask; |
| 19 using nacl_mips_dec::kRegisterLoadStoreMask; |
| 20 |
| 21 using nacl_mips_dec::kInstrSize; |
| 22 using nacl_mips_dec::kInstrAlign; |
| 23 |
| 24 using std::vector; |
| 25 |
| 26 namespace nacl_mips_val { |
| 27 |
| 28 /********************************************************* |
| 29 * Implementations of patterns used in the first pass. |
| 30 * |
| 31 * N.B. IF YOU ADD A PATTERN HERE, REGISTER IT BELOW. |
| 32 * See the list in apply_patterns. |
| 33 *********************************************************/ |
| 34 |
| 35 // A possible result from a validator pattern. |
| 36 enum PatternMatch { |
| 37 // The pattern does not apply to the instructions it was given. |
| 38 NO_MATCH, |
| 39 // The pattern matches, and is safe; do not allow jumps to split it. |
| 40 PATTERN_SAFE, |
| 41 // The pattern matches, and has detected a problem. |
| 42 PATTERN_UNSAFE |
| 43 }; |
| 44 |
| 45 |
| 46 /********************************************************* |
| 47 * One instruction patterns. |
| 48 *********************************************************/ |
| 49 |
| 50 /* |
| 51 * Checks for instructions that are not allowed. |
| 52 */ |
| 53 static PatternMatch check_safety(const SfiValidator &sfi, |
| 54 const DecodedInstruction &inst, |
| 55 ProblemSink *out) { |
| 56 UNREFERENCED_PARAMETER(sfi); |
| 57 if (nacl_mips_dec::MAY_BE_SAFE != inst.safety()) { |
| 58 out->report_problem(inst.addr(), inst.safety(), kProblemUnsafe); |
| 59 return PATTERN_UNSAFE; |
| 60 } |
| 61 return PATTERN_SAFE; |
| 62 } |
| 63 |
| 64 /* |
| 65 * Checks for instructions that alter read-only registers. |
| 66 */ |
| 67 static PatternMatch check_read_only(const SfiValidator &sfi, |
| 68 const DecodedInstruction &inst, |
| 69 ProblemSink *out) { |
| 70 if (inst.is_dest_gpr_reg(sfi.read_only_registers())) { |
| 71 out->report_problem(inst.addr(), inst.safety(), kProblemReadOnlyRegister); |
| 72 return PATTERN_UNSAFE; |
| 73 } |
| 74 return NO_MATCH; |
| 75 } |
| 76 |
| 77 /* |
| 78 * Checks the location of linking branches -- in order to be correct, the |
| 79 * branches must be in the slot before the last slot. |
| 80 * |
| 81 */ |
| 82 static PatternMatch check_call_position(const SfiValidator &sfi, |
| 83 const DecodedInstruction &inst, |
| 84 ProblemSink *out) { |
| 85 if (inst.is_jal()) { |
| 86 uint32_t end_addr = sfi.bundle_for_address(inst.addr()).end_addr(); |
| 87 uint32_t branch_slot = end_addr - (2 * kInstrSize); |
| 88 if (inst.addr() != branch_slot) { |
| 89 out->report_problem(inst.addr(), inst.safety(), kProblemMisalignedCall); |
| 90 return PATTERN_UNSAFE; |
| 91 } |
| 92 return PATTERN_SAFE; |
| 93 } |
| 94 return NO_MATCH; |
| 95 } |
| 96 |
| 97 /* |
| 98 * Checks for jumps to unsafe area. |
| 99 */ |
| 100 static PatternMatch check_jump_dest_addr(const SfiValidator &sfi, |
| 101 const DecodedInstruction &instr, |
| 102 ProblemSink *out) { |
| 103 if (instr.is_direct_jump()) { |
| 104 uint32_t dest_addr = instr.dest_addr(); |
| 105 if (dest_addr < sfi.trampoline_region_start()) { |
| 106 // Safe guard region, allow jumps if somebody is suicidal. |
| 107 return PATTERN_SAFE; |
| 108 } else if (dest_addr < sfi.code_region_start()) { |
| 109 // Trampoline region, allow only 0mod16. |
| 110 if ((dest_addr & (sfi.bytes_per_bundle() - 1)) != 0) { |
| 111 out->report_problem(instr.addr(), instr.safety(), |
| 112 kProblemUnalignedJumpToTrampoline); |
| 113 return PATTERN_UNSAFE; |
| 114 } |
| 115 return PATTERN_SAFE; |
| 116 } else { |
| 117 // Jumps outside of unsafe region are not allowed. |
| 118 if ((dest_addr & ~(sfi.code_address_mask())) != 0) { |
| 119 out->report_problem(instr.addr(), instr.safety(), |
| 120 kProblemBranchInvalidDest); |
| 121 return PATTERN_UNSAFE; |
| 122 } |
| 123 // Another pattern is responsible for checking if it lands inside of a |
| 124 // pseudo-instruction. |
| 125 return PATTERN_SAFE; |
| 126 } |
| 127 } |
| 128 return NO_MATCH; |
| 129 } |
| 130 |
| 131 /********************************************************* |
| 132 * Two instruction patterns. |
| 133 *********************************************************/ |
| 134 |
| 135 /* |
| 136 * Checks if indirect jumps are guarded properly. |
| 137 */ |
| 138 static PatternMatch check_jmp_reg(const SfiValidator &sfi, |
| 139 const DecodedInstruction &first, |
| 140 const DecodedInstruction &second, |
| 141 ProblemSink *out) { |
| 142 UNREFERENCED_PARAMETER(sfi); |
| 143 if (second.is_jmp_reg()) { |
| 144 if (first.is_mask(second.target_reg(), kRegisterJumpMask)) { |
| 145 return PATTERN_SAFE; |
| 146 } |
| 147 out->report_problem(second.addr(), second.safety(), |
| 148 kProblemUnsafeJumpRegister); |
| 149 return PATTERN_UNSAFE; |
| 150 } |
| 151 return NO_MATCH; |
| 152 } |
| 153 |
| 154 |
| 155 /* |
| 156 * Checks if change of the data register ($sp) is followed by load/store mask. |
| 157 */ |
| 158 static PatternMatch check_data_register_update(const SfiValidator &sfi, |
| 159 const DecodedInstruction &first, |
| 160 const DecodedInstruction &second, |
| 161 ProblemSink *out) { |
| 162 if (first.is_dest_gpr_reg(sfi.data_address_registers()) |
| 163 && !first.is_mask(first.dest_gpr_reg(), kRegisterLoadStoreMask)) { |
| 164 if (second.is_mask(first.dest_gpr_reg(), kRegisterLoadStoreMask)) { |
| 165 return PATTERN_SAFE; |
| 166 } |
| 167 out->report_problem(first.addr(), first.safety(), kProblemUnsafeDataWrite); |
| 168 return PATTERN_UNSAFE; |
| 169 } |
| 170 return NO_MATCH; |
| 171 } |
| 172 |
| 173 /* |
| 174 * Checks if data register ($sp) change is in the delay slot. |
| 175 */ |
| 176 static PatternMatch check_data_register_dslot(const SfiValidator &sfi, |
| 177 const DecodedInstruction &first, |
| 178 const DecodedInstruction &second, |
| 179 ProblemSink *out) { |
| 180 if (second.is_dest_gpr_reg(sfi.data_address_registers()) |
| 181 && !second.is_mask(second.dest_gpr_reg(), kRegisterLoadStoreMask)) { |
| 182 if (first.has_delay_slot()) { |
| 183 out->report_problem(second.addr(), second.safety(), |
| 184 kProblemDataRegInDelaySlot); |
| 185 return PATTERN_UNSAFE; |
| 186 } |
| 187 } |
| 188 return NO_MATCH; |
| 189 } |
| 190 |
| 191 /* |
| 192 * Checks if load and store instructions are preceded by load/store mask. |
| 193 */ |
| 194 static PatternMatch check_load_store(const SfiValidator &sfi, |
| 195 const DecodedInstruction &first, |
| 196 const DecodedInstruction &second, |
| 197 ProblemSink *out) { |
| 198 if (second.is_load_store()) { |
| 199 Register base_addr_reg = second.base_address_register(); |
| 200 if (!sfi.data_address_registers().contains_all(base_addr_reg)) { |
| 201 if (first.is_mask(base_addr_reg, kRegisterLoadStoreMask)) { |
| 202 return PATTERN_SAFE; |
| 203 } |
| 204 out->report_problem(second.addr(), second.safety(), |
| 205 kProblemUnsafeLoadStore); |
| 206 return PATTERN_UNSAFE; |
| 207 } |
| 208 } |
| 209 return NO_MATCH; |
| 210 } |
| 211 |
| 212 |
| 213 /********************************************************* |
| 214 * Pseudo-instruction patterns. |
| 215 *********************************************************/ |
| 216 |
| 217 /* |
| 218 * Checks if a pseudo-instruction that starts with instr will cross bundle |
| 219 * border (i.e. if it starts in one and ends in second). |
| 220 * The exception to this rule are pseudo-instructions altering the data register |
| 221 * value (because mask is the second instruction). |
| 222 */ |
| 223 static PatternMatch check_bundle_cross(const SfiValidator &sfi, |
| 224 const DecodedInstruction instr, |
| 225 ProblemSink *out) { |
| 226 uint32_t begin_addr = sfi.bundle_for_address(instr.addr()).begin_addr(); |
| 227 if ((instr.addr() == begin_addr) && !instr.is_data_reg_mask()) { |
| 228 out->report_problem(instr.addr(), instr.safety(), |
| 229 kProblemPatternCrossesBundle); |
| 230 return PATTERN_UNSAFE; |
| 231 } |
| 232 return PATTERN_SAFE; |
| 233 } |
| 234 |
| 235 /* |
| 236 * Checks if branch instruction will jump in the middle of pseudo-instruction. |
| 237 */ |
| 238 static PatternMatch check_jump_to_pseudo(const SfiValidator &sfi, |
| 239 const std::vector<CodeSegment> &segms, |
| 240 const DecodedInstruction pseudoinstr, |
| 241 const AddressSet &branches, |
| 242 const AddressSet &branch_targets, |
| 243 ProblemSink *out) { |
| 244 uint32_t target_va = pseudoinstr.addr(); |
| 245 if (branch_targets.contains(target_va)) { |
| 246 std::vector<DecodedInstruction> instrs; |
| 247 if (sfi.find_branch(segms, branches, target_va, instrs)) { |
| 248 for (uint32_t i = 0; i < instrs.size(); i++) { |
| 249 out->report_problem(instrs[i].addr(), instrs[i].safety(), |
| 250 kProblemBranchSplitsPattern); |
| 251 } |
| 252 return PATTERN_UNSAFE; |
| 253 } else { |
| 254 assert(0); |
| 255 } |
| 256 } |
| 257 return PATTERN_SAFE; |
| 258 } |
| 259 |
| 260 |
| 261 /********************************************************* |
| 262 * |
| 263 * Implementation of SfiValidator itself. |
| 264 * |
| 265 *********************************************************/ |
| 266 SfiValidator::SfiValidator(uint32_t bytes_per_bundle, |
| 267 uint32_t code_region_bytes, |
| 268 uint32_t data_region_bytes, |
| 269 RegisterList read_only_registers, |
| 270 RegisterList data_address_registers) |
| 271 : bytes_per_bundle_(bytes_per_bundle), |
| 272 code_region_bytes_(code_region_bytes), |
| 273 data_address_mask_(~(data_region_bytes - 1)), |
| 274 code_address_mask_((code_region_bytes - 1) & kInstrAlign), // 0x0FFFFFFC |
| 275 read_only_registers_(read_only_registers), |
| 276 data_address_registers_(data_address_registers), |
| 277 decode_state_(nacl_mips_dec::init_decode()) {} |
| 278 |
| 279 bool SfiValidator::validate(const vector<CodeSegment> &segments, |
| 280 ProblemSink *out) { |
| 281 uint32_t base = segments[0].begin_addr(); |
| 282 uint32_t size = segments.back().end_addr() - base; |
| 283 AddressSet branches(base, size); |
| 284 AddressSet branch_targets(base, size); |
| 285 AddressSet critical(base, size); |
| 286 |
| 287 bool complete_success = true; |
| 288 |
| 289 for (vector<CodeSegment>::const_iterator it = segments.begin(); |
| 290 it != segments.end(); ++it) { |
| 291 complete_success &= validate_fallthrough(*it, out, &branches, |
| 292 &branch_targets, &critical); |
| 293 |
| 294 if (!out->should_continue()) { |
| 295 return false; |
| 296 } |
| 297 } |
| 298 |
| 299 complete_success &= validate_pseudos(*this, segments, |
| 300 branches, branch_targets, critical, out); |
| 301 return complete_success; |
| 302 } |
| 303 |
| 304 bool SfiValidator::validate_fallthrough(const CodeSegment &segment, |
| 305 ProblemSink *out, |
| 306 AddressSet *branches, |
| 307 AddressSet *branch_targets, |
| 308 AddressSet *critical) { |
| 309 bool complete_success = true; |
| 310 |
| 311 nacl_mips_dec::Forbidden initial_decoder; |
| 312 // Initialize the previous instruction to a syscall, so patterns all fail. |
| 313 DecodedInstruction prev( |
| 314 0, // Virtual address 0, which will be in a different bundle. |
| 315 Instruction(0x0000000c), // syscall. |
| 316 initial_decoder); // and ensure that it decodes as Forbidden. |
| 317 |
| 318 for (uint32_t va = segment.begin_addr(); va != segment.end_addr(); |
| 319 va += kInstrSize) { |
| 320 DecodedInstruction inst(va, segment[va], |
| 321 nacl_mips_dec::decode(segment[va], decode_state_)); |
| 322 |
| 323 complete_success &= apply_patterns(inst, out); |
| 324 if (!out->should_continue()) return false; |
| 325 |
| 326 complete_success &= apply_patterns(prev, inst, critical, out); |
| 327 if (!out->should_continue()) return false; |
| 328 |
| 329 if (inst.is_direct_jump()) { |
| 330 branches->add(inst.addr()); |
| 331 branch_targets->add(inst.dest_addr()); |
| 332 } |
| 333 |
| 334 prev = inst; |
| 335 } |
| 336 return complete_success; |
| 337 } |
| 338 |
| 339 bool SfiValidator::validate_pseudos(const SfiValidator &sfi, |
| 340 const std::vector<CodeSegment> &segments, |
| 341 const AddressSet &branches, |
| 342 const AddressSet &branch_targets, |
| 343 const AddressSet &critical, |
| 344 ProblemSink* out) { |
| 345 bool complete_success = true; |
| 346 vector<CodeSegment>::const_iterator seg_it = segments.begin(); |
| 347 |
| 348 for (AddressSet::Iterator it = critical.begin(); it != critical.end(); ++it) { |
| 349 uint32_t va = *it; |
| 350 |
| 351 while (!seg_it->contains_address(va)) { |
| 352 ++seg_it; |
| 353 } |
| 354 |
| 355 const CodeSegment &segment = *seg_it; |
| 356 DecodedInstruction inst_p(va, |
| 357 segment[va], |
| 358 nacl_mips_dec::decode(segment[va], |
| 359 decode_state_)); |
| 360 |
| 361 // Check if the pseudo-instruction will cross bundle borders. |
| 362 complete_success &= check_bundle_cross(sfi, inst_p, out); |
| 363 |
| 364 // Check if direct jumps destination is inside of a pseudo-instruction. |
| 365 complete_success &= check_jump_to_pseudo(sfi, segments, inst_p, branches, |
| 366 branch_targets, out); |
| 367 } |
| 368 |
| 369 return complete_success; |
| 370 } |
| 371 |
| 372 |
| 373 bool SfiValidator::apply_patterns(const DecodedInstruction &inst, |
| 374 ProblemSink *out) { |
| 375 // Single-instruction patterns. |
| 376 typedef PatternMatch (*OneInstPattern)(const SfiValidator &, |
| 377 const DecodedInstruction &, |
| 378 ProblemSink *out); |
| 379 static const OneInstPattern one_inst_patterns[] = { |
| 380 &check_safety, |
| 381 &check_read_only, |
| 382 &check_call_position, |
| 383 &check_jump_dest_addr |
| 384 }; |
| 385 |
| 386 bool complete_success = true; |
| 387 |
| 388 for (uint32_t i = 0; i < NACL_ARRAY_SIZE(one_inst_patterns); i++) { |
| 389 PatternMatch r = one_inst_patterns[i](*this, inst, out); |
| 390 switch (r) { |
| 391 case PATTERN_SAFE: |
| 392 case NO_MATCH: |
| 393 break; |
| 394 |
| 395 case PATTERN_UNSAFE: |
| 396 complete_success = false; |
| 397 break; |
| 398 } |
| 399 } |
| 400 return complete_success; |
| 401 } |
| 402 |
| 403 bool SfiValidator::apply_patterns(const DecodedInstruction &first, |
| 404 const DecodedInstruction &second, AddressSet *critical, ProblemSink *out) { |
| 405 // Type for two-instruction pattern functions. |
| 406 typedef PatternMatch (*TwoInstPattern)(const SfiValidator &, |
| 407 const DecodedInstruction &first, |
| 408 const DecodedInstruction &second, |
| 409 ProblemSink *out); |
| 410 // The list of patterns -- defined in static functions up top. |
| 411 static const TwoInstPattern two_inst_patterns[] = { |
| 412 &check_jmp_reg, |
| 413 &check_data_register_update, |
| 414 &check_data_register_dslot, |
| 415 &check_load_store |
| 416 }; |
| 417 |
| 418 bool complete_success = true; |
| 419 |
| 420 for (uint32_t i = 0; i < NACL_ARRAY_SIZE(two_inst_patterns); i++) { |
| 421 PatternMatch r = two_inst_patterns[i](*this, first, second, out); |
| 422 switch (r) { |
| 423 case NO_MATCH: |
| 424 break; |
| 425 case PATTERN_UNSAFE: |
| 426 // Pattern is in charge of reporting specific issue. |
| 427 complete_success = false; |
| 428 break; |
| 429 case PATTERN_SAFE: |
| 430 critical->add(second.addr()); |
| 431 break; |
| 432 } |
| 433 } |
| 434 return complete_success; |
| 435 } |
| 436 |
| 437 bool SfiValidator::is_data_address_register(Register r) const { |
| 438 return data_address_registers_[r]; |
| 439 } |
| 440 |
| 441 bool SfiValidator::is_bundle_head(uint32_t address) const { |
| 442 return (address % bytes_per_bundle_) == 0; |
| 443 } |
| 444 |
| 445 const Bundle SfiValidator::bundle_for_address(uint32_t address) const { |
| 446 uint32_t base = address - (address % bytes_per_bundle_); |
| 447 return Bundle(base, bytes_per_bundle_); |
| 448 } |
| 449 |
| 450 bool SfiValidator::find_branch(const std::vector<CodeSegment> &segments, |
| 451 const AddressSet &branches, |
| 452 uint32_t dest_address, |
| 453 std::vector<DecodedInstruction> &instrs) const { |
| 454 vector<CodeSegment>::const_iterator seg_it = segments.begin(); |
| 455 |
| 456 for (AddressSet::Iterator it = branches.begin(); it != branches.end(); ++it) { |
| 457 uint32_t va = *it; |
| 458 |
| 459 while (!seg_it->contains_address(va)) { |
| 460 ++seg_it; |
| 461 } |
| 462 |
| 463 const CodeSegment &segment = *seg_it; |
| 464 DecodedInstruction instr = DecodedInstruction(va, segment[va], |
| 465 nacl_mips_dec::decode(segment[va], decode_state_)); |
| 466 if (instr.dest_addr() == dest_address) { |
| 467 instrs.push_back(instr); |
| 468 } |
| 469 } |
| 470 if (!instrs.empty()) return true; |
| 471 return false; |
| 472 } |
| 473 /* |
| 474 * DecodedInstruction. |
| 475 */ |
| 476 DecodedInstruction::DecodedInstruction(uint32_t vaddr, |
| 477 Instruction inst, |
| 478 const ClassDecoder &decoder) |
| 479 : vaddr_(vaddr), |
| 480 inst_(inst), |
| 481 decoder_(&decoder), |
| 482 safety_(decoder.safety(inst_)) |
| 483 {} |
| 484 |
| 485 } // namespace |
OLD | NEW |