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::kInstrSize;
19 : using nacl_mips_dec::kInstrAlign;
20 :
21 : using std::vector;
22 :
23 : namespace nacl_mips_val {
24 :
25 : /*
26 : * TODO(petarj): MIPS validator and runtime port need an external security
27 : * review before they are delivered in products.
28 : */
29 :
30 : /*********************************************************
31 : * Implementations of patterns used in the first pass.
32 : *
33 : * N.B. IF YOU ADD A PATTERN HERE, REGISTER IT BELOW.
34 : * See the list in apply_patterns.
35 : *********************************************************/
36 :
37 : // A possible result from a validator pattern.
38 : enum PatternMatch {
39 : // The pattern does not apply to the instructions it was given.
40 : NO_MATCH,
41 : // The pattern matches, and is safe; do not allow jumps to split it.
42 : PATTERN_SAFE,
43 : // The pattern matches, and has detected a problem.
44 : PATTERN_UNSAFE
45 : };
46 :
47 :
48 : /*********************************************************
49 : * One instruction patterns.
50 : *********************************************************/
51 :
52 : /*
53 : * Checks for instructions that are not allowed.
54 : */
55 118 : static PatternMatch CheckSafety(const SfiValidator &sfi,
56 : const DecodedInstruction &inst,
57 : ProblemSink *out) {
58 : UNREFERENCED_PARAMETER(sfi);
59 118 : if (nacl_mips_dec::MAY_BE_SAFE != inst.safety()) {
60 0 : out->ReportProblem(inst.addr(), inst.safety(), kProblemUnsafe);
61 0 : return PATTERN_UNSAFE;
62 : }
63 118 : return PATTERN_SAFE;
64 : }
65 :
66 : /*
67 : * Checks for instructions that alter read-only registers.
68 : */
69 118 : static PatternMatch CheckReadOnly(const SfiValidator &sfi,
70 : const DecodedInstruction &inst,
71 : ProblemSink *out) {
72 118 : if (inst.IsDestGprReg(sfi.read_only_registers())) {
73 0 : out->ReportProblem(inst.addr(), inst.safety(), kProblemReadOnlyRegister);
74 0 : return PATTERN_UNSAFE;
75 : }
76 118 : return NO_MATCH;
77 : }
78 :
79 : /*
80 : * Checks the location of linking branches -- in order to be correct, the
81 : * branches must be in the slot before the last slot.
82 : *
83 : */
84 118 : static PatternMatch CheckCallPosition(const SfiValidator &sfi,
85 : const DecodedInstruction &inst,
86 : ProblemSink *out) {
87 118 : if (inst.IsJal()) {
88 2 : uint32_t end_addr = sfi.BundleForAddress(inst.addr()).EndAddr();
89 2 : uint32_t branch_slot = end_addr - (2 * kInstrSize);
90 2 : if (inst.addr() != branch_slot) {
91 1 : out->ReportProblem(inst.addr(), inst.safety(), kProblemMisalignedCall);
92 1 : return PATTERN_UNSAFE;
93 : }
94 1 : return PATTERN_SAFE;
95 : }
96 116 : return NO_MATCH;
97 : }
98 :
99 : /*
100 : * Checks for jumps to unsafe area.
101 : */
102 118 : static PatternMatch CheckJumpDestAddr(const SfiValidator &sfi,
103 : const DecodedInstruction &instr,
104 : ProblemSink *out) {
105 118 : if (instr.IsDirectJump()) {
106 0 : uint32_t dest_addr = instr.DestAddr();
107 0 : if (dest_addr < sfi.trampoline_region_start()) {
108 : // Safe guard region, allow jumps if somebody is suicidal.
109 0 : return PATTERN_SAFE;
110 0 : } else if (dest_addr < sfi.code_region_start()) {
111 : // Trampoline region, allow only 0mod16.
112 0 : if ((dest_addr & (sfi.bytes_per_bundle() - 1)) != 0) {
113 : out->ReportProblem(instr.addr(), instr.safety(),
114 0 : kProblemUnalignedJumpToTrampoline);
115 0 : return PATTERN_UNSAFE;
116 : }
117 0 : return PATTERN_SAFE;
118 : } else {
119 : // Jumps outside of unsafe region are not allowed.
120 0 : if ((dest_addr & ~(sfi.code_address_mask())) != 0) {
121 : out->ReportProblem(instr.addr(), instr.safety(),
122 0 : kProblemBranchInvalidDest);
123 0 : return PATTERN_UNSAFE;
124 : }
125 : // Another pattern is responsible for checking if it lands inside of a
126 : // pseudo-instruction.
127 0 : return PATTERN_SAFE;
128 : }
129 : }
130 118 : return NO_MATCH;
131 : }
132 :
133 : /*********************************************************
134 : * Two instruction patterns.
135 : *********************************************************/
136 :
137 : /*
138 : * Checks if indirect jumps are guarded properly.
139 : */
140 148 : static PatternMatch CheckJmpReg(const SfiValidator &sfi,
141 : const DecodedInstruction &first,
142 : const DecodedInstruction &second,
143 : ProblemSink *out) {
144 : UNREFERENCED_PARAMETER(sfi);
145 148 : if (second.IsJmpReg()) {
146 4 : if (first.IsMask(second.TargetReg(), Register::JumpMask())) {
147 2 : return PATTERN_SAFE;
148 : }
149 : out->ReportProblem(second.addr(), second.safety(),
150 2 : kProblemUnsafeJumpRegister);
151 2 : return PATTERN_UNSAFE;
152 : }
153 144 : return NO_MATCH;
154 : }
155 :
156 :
157 : /*
158 : * Checks if change of the data register ($sp) is followed by load/store mask.
159 : */
160 148 : static PatternMatch CheckDataRegisterUpdate(const SfiValidator &sfi,
161 : const DecodedInstruction &first,
162 : const DecodedInstruction &second,
163 : ProblemSink *out) {
164 : UNREFERENCED_PARAMETER(sfi);
165 174 : if (first.DestGprReg().Equals(Register::Sp())
166 26 : && !first.IsMask(first.DestGprReg(), Register::LoadStoreMask())) {
167 15 : if (second.IsMask(first.DestGprReg(), Register::LoadStoreMask())) {
168 9 : return PATTERN_SAFE;
169 : }
170 6 : out->ReportProblem(first.addr(), first.safety(), kProblemUnsafeDataWrite);
171 6 : return PATTERN_UNSAFE;
172 : }
173 133 : return NO_MATCH;
174 : }
175 :
176 : /*
177 : * Checks if data register ($sp) change is in the delay slot.
178 : */
179 148 : static PatternMatch CheckDataRegisterDslot(const SfiValidator &sfi,
180 : const DecodedInstruction &first,
181 : const DecodedInstruction &second,
182 : ProblemSink *out) {
183 : UNREFERENCED_PARAMETER(sfi);
184 174 : if (second.DestGprReg().Equals(Register::Sp())
185 26 : && !second.IsMask(second.DestGprReg(), Register::LoadStoreMask())) {
186 15 : if (first.HasDelaySlot()) {
187 : out->ReportProblem(second.addr(), second.safety(),
188 0 : kProblemDataRegInDelaySlot);
189 0 : return PATTERN_UNSAFE;
190 : }
191 : }
192 148 : return NO_MATCH;
193 : }
194 :
195 : /*
196 : * Checks if load and store instructions are preceded by load/store mask.
197 : */
198 148 : static PatternMatch CheckLoadStore(const SfiValidator &sfi,
199 : const DecodedInstruction &first,
200 : const DecodedInstruction &second,
201 : ProblemSink *out) {
202 148 : if (second.IsLoadStore()) {
203 16 : Register base_addr_reg = second.BaseAddressRegister();
204 16 : if (!sfi.data_address_registers().
205 16 : ContainsAll(RegisterList(base_addr_reg))) {
206 10 : if (first.IsMask(base_addr_reg, Register::LoadStoreMask())) {
207 5 : return PATTERN_SAFE;
208 : }
209 : out->ReportProblem(second.addr(), second.safety(),
210 5 : kProblemUnsafeLoadStore);
211 5 : return PATTERN_UNSAFE;
212 : }
213 : }
214 138 : return NO_MATCH;
215 : }
216 :
217 :
218 : /*
219 : * Checks if there is jump/branch in the delay slot.
220 : */
221 148 : static PatternMatch CheckBranchInDelaySlot(const SfiValidator &sfi,
222 : const DecodedInstruction &first,
223 : const DecodedInstruction &second,
224 : ProblemSink *out) {
225 : UNREFERENCED_PARAMETER(sfi);
226 148 : if (first.HasDelaySlot() && second.HasDelaySlot()) {
227 : out->ReportProblem(second.addr(), second.safety(),
228 0 : kProblemBranchInDelaySlot);
229 0 : return PATTERN_UNSAFE;
230 : }
231 148 : return NO_MATCH;
232 : }
233 :
234 :
235 : /*********************************************************
236 : * Pseudo-instruction patterns.
237 : *********************************************************/
238 :
239 : /*
240 : * Checks if a pseudo-instruction that starts with instr will cross bundle
241 : * border (i.e. if it starts in one and ends in second).
242 : * The exception to this rule are pseudo-instructions altering the data register
243 : * value (because mask is the second instruction).
244 : */
245 6 : static PatternMatch CheckBundleCross(const SfiValidator &sfi,
246 : const DecodedInstruction instr,
247 : ProblemSink *out) {
248 6 : uint32_t begin_addr = sfi.BundleForAddress(instr.addr()).BeginAddr();
249 6 : if ((instr.addr() == begin_addr) && !instr.IsDataRegMask()) {
250 : out->ReportProblem(instr.addr(), instr.safety(),
251 0 : kProblemPatternCrossesBundle);
252 0 : return PATTERN_UNSAFE;
253 : }
254 6 : return PATTERN_SAFE;
255 : }
256 :
257 : /*
258 : * Checks if branch instruction will jump in the middle of pseudo-instruction.
259 : */
260 6 : static PatternMatch CheckJumpToPseudo(const SfiValidator &sfi,
261 : const std::vector<CodeSegment> &segms,
262 : const DecodedInstruction pseudoinstr,
263 : const AddressSet &branches,
264 : const AddressSet &branch_targets,
265 : ProblemSink *out) {
266 6 : uint32_t target_va = pseudoinstr.addr();
267 6 : if (branch_targets.Contains(target_va)) {
268 0 : std::vector<DecodedInstruction> instrs;
269 0 : if (sfi.FindBranch(segms, branches, target_va, &instrs)) {
270 0 : for (uint32_t i = 0; i < instrs.size(); i++) {
271 0 : out->ReportProblem(instrs[i].addr(), instrs[i].safety(),
272 0 : kProblemBranchSplitsPattern);
273 : }
274 0 : return PATTERN_UNSAFE;
275 : } else {
276 0 : assert(0);
277 0 : }
278 : }
279 6 : return PATTERN_SAFE;
280 : }
281 :
282 :
283 : /*********************************************************
284 : *
285 : * Implementation of SfiValidator itself.
286 : *
287 : *********************************************************/
288 10 : SfiValidator::SfiValidator(uint32_t bytes_per_bundle,
289 : uint32_t code_region_bytes,
290 : uint32_t data_region_bytes,
291 : RegisterList read_only_registers,
292 : RegisterList data_address_registers)
293 : : bytes_per_bundle_(bytes_per_bundle),
294 : code_region_bytes_(code_region_bytes),
295 : data_address_mask_(~(data_region_bytes - 1)),
296 : code_address_mask_((code_region_bytes - 1) & kInstrAlign), // 0x0FFFFFFC
297 : read_only_registers_(read_only_registers),
298 : data_address_registers_(data_address_registers),
299 10 : decode_state_(nacl_mips_dec::init_decode()),
300 20 : is_position_independent_(false) {}
301 :
302 30 : bool SfiValidator::Validate(const vector<CodeSegment> &segments,
303 : ProblemSink *out) {
304 30 : uint32_t base = segments[0].BeginAddr();
305 30 : uint32_t size = segments.back().EndAddr() - base;
306 30 : AddressSet branches(base, size);
307 30 : AddressSet branch_targets(base, size);
308 30 : AddressSet critical(base, size);
309 :
310 30 : bool complete_success = true;
311 :
312 120 : for (vector<CodeSegment>::const_iterator it = segments.begin();
313 60 : it != segments.end(); ++it) {
314 30 : complete_success &= ValidateFallthrough(*it, out, &branches,
315 60 : &branch_targets, &critical);
316 :
317 30 : if (!out->ShouldContinue()) {
318 0 : return false;
319 : }
320 : }
321 :
322 30 : if (segments.size() == 1) {
323 30 : bool external_target_addr = false;
324 60 : for (AddressSet::Iterator it = branch_targets.Begin();
325 30 : !it.Equals(branch_targets.End()); it.Next()) {
326 0 : if (!segments[0].ContainsAddress(it.GetAddress())) {
327 0 : external_target_addr = true;
328 0 : break;
329 : }
330 : }
331 30 : is_position_independent_ = !external_target_addr;
332 : }
333 :
334 : complete_success &= ValidatePseudos(*this, segments,
335 30 : branches, branch_targets, critical, out);
336 30 : return complete_success;
337 : }
338 :
339 30 : bool SfiValidator::ValidateFallthrough(const CodeSegment &segment,
340 : ProblemSink *out,
341 : AddressSet *branches,
342 : AddressSet *branch_targets,
343 : AddressSet *critical) {
344 30 : bool complete_success = true;
345 :
346 30 : nacl_mips_dec::Forbidden initial_decoder;
347 : // Initialize the previous instruction to a syscall, so patterns all fail.
348 : DecodedInstruction prev(
349 : 0, // Virtual address 0, which will be in a different bundle.
350 : Instruction(0x0000000c), // syscall.
351 30 : initial_decoder); // and ensure that it decodes as Forbidden.
352 :
353 148 : for (uint32_t va = segment.BeginAddr(); va != segment.EndAddr();
354 : va += kInstrSize) {
355 : DecodedInstruction inst(va, segment[va],
356 118 : nacl_mips_dec::decode(segment[va], decode_state_));
357 :
358 118 : complete_success &= ApplyPatterns(inst, out);
359 118 : if (!out->ShouldContinue()) return false;
360 :
361 118 : complete_success &= ApplyPatterns(prev, inst, critical, out);
362 118 : if (!out->ShouldContinue()) return false;
363 :
364 118 : if (inst.IsDirectJump()) {
365 0 : branches->Add(inst.addr());
366 0 : branch_targets->Add(inst.DestAddr());
367 : }
368 :
369 118 : prev = inst;
370 : }
371 :
372 : // Validate the last instruction, paired with a nop.
373 30 : const Instruction nop(nacl_mips_dec::kNop);
374 : DecodedInstruction one_past_end(segment.EndAddr(), nop,
375 30 : nacl_mips_dec::decode(nop, decode_state_));
376 30 : complete_success &= ApplyPatterns(prev, one_past_end, critical, out);
377 :
378 30 : return complete_success;
379 : }
380 :
381 30 : bool SfiValidator::ValidatePseudos(const SfiValidator &sfi,
382 : const std::vector<CodeSegment> &segments,
383 : const AddressSet &branches,
384 : const AddressSet &branch_targets,
385 : const AddressSet &critical,
386 : ProblemSink* out) {
387 30 : bool complete_success = true;
388 30 : vector<CodeSegment>::const_iterator seg_it = segments.begin();
389 :
390 36 : for (AddressSet::Iterator it = critical.Begin(); !it.Equals(critical.End());
391 : it.Next()) {
392 6 : uint32_t va = it.GetAddress();
393 :
394 12 : while (!seg_it->ContainsAddress(va)) {
395 0 : ++seg_it;
396 : }
397 :
398 6 : const CodeSegment &segment = *seg_it;
399 : DecodedInstruction inst_p(va,
400 : segment[va],
401 : nacl_mips_dec::decode(segment[va],
402 6 : decode_state_));
403 :
404 : // Check if the pseudo-instruction will cross bundle borders.
405 6 : complete_success &= CheckBundleCross(sfi, inst_p, out);
406 :
407 : // Check if direct jumps destination is inside of a pseudo-instruction.
408 : complete_success &= CheckJumpToPseudo(sfi, segments, inst_p, branches,
409 6 : branch_targets, out);
410 : }
411 :
412 30 : return complete_success;
413 : }
414 :
415 :
416 118 : bool SfiValidator::ApplyPatterns(const DecodedInstruction &inst,
417 : ProblemSink *out) {
418 : // Single-instruction patterns.
419 : typedef PatternMatch (*OneInstPattern)(const SfiValidator &,
420 : const DecodedInstruction &,
421 : ProblemSink *out);
422 : static const OneInstPattern one_inst_patterns[] = {
423 : &CheckSafety,
424 : &CheckReadOnly,
425 : &CheckCallPosition,
426 : &CheckJumpDestAddr
427 : };
428 :
429 118 : bool complete_success = true;
430 :
431 590 : for (uint32_t i = 0; i < NACL_ARRAY_SIZE(one_inst_patterns); i++) {
432 472 : PatternMatch r = one_inst_patterns[i](*this, inst, out);
433 472 : switch (r) {
434 : case PATTERN_SAFE:
435 : case NO_MATCH:
436 471 : break;
437 :
438 : case PATTERN_UNSAFE:
439 1 : complete_success = false;
440 1 : break;
441 : }
442 : }
443 118 : return complete_success;
444 : }
445 :
446 148 : bool SfiValidator::ApplyPatterns(const DecodedInstruction &first,
447 : const DecodedInstruction &second, AddressSet *critical, ProblemSink *out) {
448 : // Type for two-instruction pattern functions.
449 : typedef PatternMatch (*TwoInstPattern)(const SfiValidator &,
450 : const DecodedInstruction &first,
451 : const DecodedInstruction &second,
452 : ProblemSink *out);
453 : // The list of patterns -- defined in static functions up top.
454 : static const TwoInstPattern two_inst_patterns[] = {
455 : &CheckJmpReg,
456 : &CheckDataRegisterUpdate,
457 : &CheckDataRegisterDslot,
458 : &CheckLoadStore,
459 : &CheckBranchInDelaySlot
460 : };
461 :
462 148 : bool complete_success = true;
463 :
464 888 : for (uint32_t i = 0; i < NACL_ARRAY_SIZE(two_inst_patterns); i++) {
465 740 : PatternMatch r = two_inst_patterns[i](*this, first, second, out);
466 740 : switch (r) {
467 : case NO_MATCH:
468 711 : break;
469 : case PATTERN_UNSAFE:
470 : // Pattern is in charge of reporting specific issue.
471 13 : complete_success = false;
472 13 : break;
473 : case PATTERN_SAFE:
474 16 : critical->Add(second.addr());
475 16 : break;
476 : }
477 : }
478 148 : return complete_success;
479 : }
480 :
481 31 : bool SfiValidator::IsDataAddressRegister(Register reg) const {
482 31 : return data_address_registers_[reg];
483 : }
484 :
485 0 : bool SfiValidator::IsBundleHead(uint32_t address) const {
486 0 : return (address % bytes_per_bundle_) == 0;
487 : }
488 :
489 25 : const Bundle SfiValidator::BundleForAddress(uint32_t address) const {
490 25 : uint32_t base = address - (address % bytes_per_bundle_);
491 25 : return Bundle(base, bytes_per_bundle_);
492 : }
493 :
494 0 : bool SfiValidator::FindBranch(const std::vector<CodeSegment> &segments,
495 : const AddressSet &branches,
496 : uint32_t dest_address,
497 : std::vector<DecodedInstruction> *instrs) const {
498 0 : vector<CodeSegment>::const_iterator seg_it = segments.begin();
499 :
500 0 : for (AddressSet::Iterator it = branches.Begin(); !it.Equals(branches.End());
501 : it.Next()) {
502 0 : uint32_t va = it.GetAddress();
503 :
504 0 : while (!seg_it->ContainsAddress(va)) {
505 0 : ++seg_it;
506 : }
507 :
508 0 : const CodeSegment &segment = *seg_it;
509 : DecodedInstruction instr = DecodedInstruction(va, segment[va],
510 0 : nacl_mips_dec::decode(segment[va], decode_state_));
511 0 : if (instr.DestAddr() == dest_address) {
512 0 : instrs->push_back(instr);
513 : }
514 : }
515 0 : if (!instrs->empty()) return true;
516 0 : return false;
517 : }
518 : /*
519 : * DecodedInstruction.
520 : */
521 184 : DecodedInstruction::DecodedInstruction(uint32_t vaddr,
522 : Instruction inst,
523 : const ClassDecoder &decoder)
524 : : vaddr_(vaddr),
525 : inst_(inst),
526 : decoder_(&decoder),
527 184 : safety_(decoder.safety(inst_))
528 184 : {}
529 :
530 : } // namespace nacl_mips_val
|
