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 : /*
8 : * Unit tests for the MIPS validator
9 : *
10 : * These tests use the google-test framework (gtest for short) to exercise the
11 : * MIPS validator. The tests currently fall into two rough categories:
12 : * 1. Simple method-level tests that exercise the validator's primitive
13 : * capabilities, and
14 : * 2. Instruction pattern tests that run the entire validator.
15 : *
16 : * All instruction pattern tests use hand-assembled machine code fragments,
17 : * embedded as byte arrays. This is somewhat ugly, but deliberate: it isolates
18 : * these tests from gas, which may be buggy or not installed. It also lets us
19 : * hand-craft malicious bit patterns that gas may refuse to produce.
20 : *
21 : * To write a new instruction pattern, or make sense of an existing one, use
22 : * MIPS32 Instruction Set Reference (available online). Instructions in this
23 : * file are written as 32-bit integers so the hex encoding matches the docs.
24 : */
25 :
26 : #include <vector>
27 : #include <string>
28 : #include <sstream>
29 :
30 : #include "gtest/gtest.h"
31 : #include "native_client/src/include/nacl_macros.h"
32 :
33 : #include "native_client/src/trusted/validator_mips/validator.h"
34 :
35 : using std::vector;
36 : using std::string;
37 : using std::ostringstream;
38 :
39 : using nacl_mips_dec::Register;
40 : using nacl_mips_dec::RegisterList;
41 : using nacl_mips_dec::Instruction;
42 :
43 : using nacl_mips_val::SfiValidator;
44 : using nacl_mips_val::ProblemSink;
45 : using nacl_mips_val::CodeSegment;
46 : using nacl_mips_dec::kInstrSize;
47 : using nacl_mips_dec::kNop;
48 :
49 : namespace {
50 :
51 : typedef uint32_t mips_inst;
52 :
53 : /*
54 : * We use these parameters to initialize the validator, below. They are
55 : * somewhat different from the parameters used in real NaCl systems, to test
56 : * degrees of validator freedom that we don't currently exercise in prod.
57 : */
58 : // Number of bytes in each bundle.
59 : static const uint32_t kBytesPerBundle = 16;
60 : // Limit code to 256MiB.
61 : static const uint32_t kCodeRegionSize = 0x10000000;
62 : // Limit data to 1GiB.
63 : static const uint32_t kDataRegionSize = 0x40000000;
64 :
65 :
66 : /*
67 : * Support code
68 : */
69 :
70 : // Simply records the arguments given to report_problem, below.
71 72 : struct ProblemRecord {
72 : uint32_t vaddr;
73 : nacl_mips_dec::SafetyLevel safety;
74 : nacl::string problem_code;
75 : uint32_t ref_vaddr;
76 : };
77 :
78 : // A ProblemSink that records all calls (implementation of the Spy pattern)
79 60 : class ProblemSpy : public ProblemSink {
80 : public:
81 14 : virtual void ReportProblem(uint32_t vaddr, nacl_mips_dec::SafetyLevel safety,
82 : const nacl::string &problem_code, uint32_t ref_vaddr = 0) {
83 : _problems.push_back(
84 14 : (ProblemRecord) { vaddr, safety, problem_code, ref_vaddr });
85 14 : }
86 :
87 : /*
88 : * We want *all* the errors that the validator produces. Note that this means
89 : * we're not testing the should_continue functionality. This is probably
90 : * okay.
91 : */
92 266 : virtual bool ShouldContinue() { return true; }
93 :
94 30 : vector<ProblemRecord> &problems() { return _problems; }
95 :
96 : private:
97 : vector<ProblemRecord> _problems;
98 : };
99 :
100 : /*
101 : * Coordinates the fixture objects used by test cases below. This is
102 : * forward-declared to the greatest extent possible so we can get on to the
103 : * important test stuff below.
104 : */
105 10 : class ValidatorTests : public ::testing::Test {
106 : protected:
107 : ValidatorTests();
108 :
109 : // Utility method for validating a sequence of bytes.
110 : bool Validate(const mips_inst *pattern,
111 : size_t inst_count,
112 : uint32_t start_addr,
113 : ProblemSink *sink);
114 :
115 : /*
116 : * Tests a pattern that's expected to pass.
117 : */
118 : void ValidationShouldPass(const mips_inst *pattern,
119 : size_t inst_count,
120 : uint32_t base_addr,
121 : const string &msg);
122 :
123 : /*
124 : * Tests a pattern that is forbidden in the SFI model.
125 : *
126 : * Note that the 'msg1' and 'msg2' parameters are merely concatentated in the
127 : * output.
128 : */
129 : vector<ProblemRecord> ValidationShouldFail(const mips_inst *pattern,
130 : size_t inst_count,
131 : uint32_t base_addr,
132 : const string &msg);
133 :
134 : SfiValidator _validator;
135 : };
136 :
137 :
138 : /*
139 : * Primitive tests checking various constructor properties. Any of these
140 : * failing would be a very bad sign indeed.
141 : */
142 :
143 5 : TEST_F(ValidatorTests, RecognizesDataAddressRegisters) {
144 : /*
145 : * Note that the logic below needs to be kept in sync with the implementation
146 : * of RegisterList::DataAddrRegs().
147 : *
148 : * This test is pretty trivial -- we can exercise the data_address_register
149 : * functionality more deeply with pattern tests below.
150 : */
151 32 : for (int i = 0; i < 31; i++) {
152 31 : Register reg(i);
153 31 : if (reg.Equals(Register::Sp()) || reg.Equals(Register::Tls())) {
154 2 : EXPECT_TRUE(_validator.IsDataAddressRegister(reg))
155 0 : << "Stack pointer and TLS register must be data address registers.";
156 : } else {
157 29 : EXPECT_FALSE(_validator.IsDataAddressRegister(reg))
158 : << "Only the stack pointer and TLS register are data "
159 0 : "address registers.";
160 : }
161 : }
162 1 : }
163 :
164 : /*
165 : * Code validation tests
166 : */
167 :
168 : // This is where untrusted code starts. Most tests use this.
169 : static const uint32_t kDefaultBaseAddr = 0x20000;
170 :
171 : /*
172 : * Here are some examples of safe stores permitted in a Native Client
173 : * program for MIPS32.
174 : */
175 :
176 : struct AnnotatedInstruction {
177 : mips_inst inst;
178 : const char *about;
179 : };
180 :
181 : static const AnnotatedInstruction examples_of_safe_stores[] = {
182 : { 0xa1490200, "sb t1, 1024(t2) : store byte" },
183 : { 0xad490200, "sw t1, 1024(t2) : store word" },
184 : { 0xa5490200, "sh t1, 1024(t2) : store halfword" },
185 : { 0xa9490200, "swl t1, 1024(t2) : store word left" },
186 : { 0xb9490200, "swr t1, 1024(t2) : store word right" },
187 : };
188 :
189 : static const AnnotatedInstruction examples_of_safe_masks[] = {
190 : { (10 << 21 | 15 << 16 | 10 << 11 | 36),
191 : "and t2,t2,t7 : simple store masking" },
192 : };
193 :
194 5 : TEST_F(ValidatorTests, SafeMaskedStores) {
195 : /*
196 : * Produces examples of masked stores using the safe store table (above)
197 : * and the list of possible masking instructions (above).
198 : */
199 :
200 2 : for (unsigned m = 0; m < NACL_ARRAY_SIZE(examples_of_safe_masks); m++) {
201 6 : for (unsigned s = 0; s < NACL_ARRAY_SIZE(examples_of_safe_stores);
202 : s++) {
203 5 : ostringstream message;
204 5 : message << examples_of_safe_masks[m].about
205 5 : << ", "
206 10 : << examples_of_safe_stores[s].about;
207 : mips_inst program[] = {
208 : examples_of_safe_masks[m].inst,
209 : examples_of_safe_stores[s].inst,
210 5 : };
211 : ValidationShouldPass(program,
212 : 2,
213 : kDefaultBaseAddr,
214 5 : message.str());
215 5 : }
216 : }
217 1 : }
218 :
219 5 : TEST_F(ValidatorTests, IncorrectStores) {
220 : /*
221 : * Produces incorrect examples of masked stores using the safe store table
222 : * (above) and the list of possible masking instructions (above).
223 : * By switching order of instructions (first store, then mask instruction)
224 : * we form incorrect pseudo-instruction.
225 : */
226 :
227 6 : for (unsigned m = 0; m < NACL_ARRAY_SIZE(examples_of_safe_stores); m++) {
228 10 : for (unsigned s = 0; s < NACL_ARRAY_SIZE(examples_of_safe_masks); s++) {
229 5 : ostringstream bad_message;
230 5 : bad_message << examples_of_safe_stores[m].about
231 5 : << ", "
232 10 : << examples_of_safe_masks[s].about;
233 : mips_inst bad_program[] = {
234 : examples_of_safe_stores[m].inst,
235 : examples_of_safe_masks[s].inst,
236 5 : };
237 :
238 : ValidationShouldFail(bad_program,
239 : 2,
240 : kDefaultBaseAddr,
241 5 : bad_message.str());
242 5 : }
243 : }
244 1 : }
245 :
246 : static const AnnotatedInstruction examples_of_safe_jump_masks[] = {
247 : { (10 << 21 | 14 << 16 | 10 << 11 | 36),
248 : "and t2,t2,t6 : simple jump masking" },
249 : };
250 :
251 : static const AnnotatedInstruction examples_of_safe_jumps[] = {
252 : { ((10<<21| 31 << 11 |9) ), "simple jump jalr t2" },
253 : { (10<<21|8), "simple jump jr t2" },
254 : };
255 :
256 5 : TEST_F(ValidatorTests, SafeMaskedJumps) {
257 : /*
258 : * Produces examples of masked jumps using the safe jump table
259 : * (above) and the list of possible masking instructions (above).
260 : */
261 2 : for (unsigned m = 0; m < NACL_ARRAY_SIZE(examples_of_safe_jump_masks); m++) {
262 3 : for (unsigned s = 0; s < NACL_ARRAY_SIZE(examples_of_safe_jumps); s++) {
263 2 : ostringstream message;
264 2 : message << examples_of_safe_jump_masks[m].about
265 2 : << ", "
266 4 : << examples_of_safe_jumps[s].about;
267 : mips_inst program[] = {
268 : kNop,
269 : examples_of_safe_jump_masks[m].inst,
270 : examples_of_safe_jumps[s].inst,
271 2 : };
272 : ValidationShouldPass(program,
273 : 3,
274 : kDefaultBaseAddr,
275 2 : message.str());
276 2 : }
277 : }
278 1 : }
279 :
280 5 : TEST_F(ValidatorTests, IncorrectJumps) {
281 : /*
282 : * Produces examples of incorrect jumps using the safe jump table
283 : * (above) and the list of possible masking instructions (above).
284 : * By switching order of instructions (first jump, then mask instruction)
285 : * we form incorrect pseudo-instruction.
286 : */
287 3 : for (unsigned m = 0; m < NACL_ARRAY_SIZE(examples_of_safe_jumps); m++) {
288 4 : for (unsigned s = 0; s < NACL_ARRAY_SIZE(examples_of_safe_jump_masks);
289 : s++) {
290 2 : ostringstream bad_message;
291 2 : bad_message << examples_of_safe_jumps[m].about
292 2 : << ", "
293 4 : << examples_of_safe_jump_masks[s].about;
294 :
295 : mips_inst bad_program[] = {
296 : examples_of_safe_jumps[m].inst,
297 : examples_of_safe_jump_masks[s].inst,
298 2 : };
299 :
300 : ValidationShouldFail(bad_program,
301 : 3,
302 : kDefaultBaseAddr,
303 2 : bad_message.str());
304 2 : }
305 : }
306 1 : }
307 :
308 : static const AnnotatedInstruction examples_of_safe_stack_masks[] = {
309 : { (29 << 21 | 15 << 16 | 29 << 11 | 36),
310 : "and sp,sp,t7 : simple stack masking" },
311 : };
312 :
313 :
314 : static const AnnotatedInstruction examples_of_safe_stack_ops[] = {
315 : { (29<<21|8<<16|29<<11|32), "add sp,sp,t0 : stack addition" },
316 : { (29<<21|8<<16|29<<11|34), "sub sp,sp,t0 : stack substraction" },
317 : };
318 :
319 5 : TEST_F(ValidatorTests, SafeMaskedStack) {
320 : /*
321 : * Produces examples of safe pseudo-ops on stack using the safe stack op table
322 : * and the list of possible masking instructions (above).
323 : */
324 3 : for (unsigned m = 0; m < NACL_ARRAY_SIZE(examples_of_safe_stack_ops); m++) {
325 4 : for (unsigned s = 0; s < NACL_ARRAY_SIZE(examples_of_safe_stack_masks);
326 : s++) {
327 2 : ostringstream message;
328 2 : message << examples_of_safe_stack_ops[m].about
329 2 : << ", "
330 4 : << examples_of_safe_stack_masks[s].about;
331 : mips_inst program[] = {
332 : examples_of_safe_stack_ops[m].inst,
333 : examples_of_safe_stack_masks[s].inst,
334 2 : };
335 : ValidationShouldPass(program,
336 : 2,
337 : kDefaultBaseAddr,
338 2 : message.str());
339 2 : }
340 : }
341 1 : }
342 :
343 5 : TEST_F(ValidatorTests, IncorrectStackOps) {
344 : /*
345 : * Produces examples of incorrect pseudo-ops on stack using the safe stack op
346 : * table and the list of possible masking instructions (above).
347 : * With switching order of instructions (first mask instruction, then stack
348 : * operation) we form incorrect pseudo-instruction.
349 : */
350 2 : for (unsigned m = 0; m < NACL_ARRAY_SIZE(examples_of_safe_stack_masks); m++) {
351 3 : for (unsigned s = 0; s < NACL_ARRAY_SIZE(examples_of_safe_stack_ops); s++) {
352 2 : ostringstream bad_message;
353 2 : bad_message << examples_of_safe_stack_masks[m].about
354 2 : << ", "
355 4 : << examples_of_safe_stack_ops[s].about;
356 : mips_inst bad_program[] = {
357 : examples_of_safe_stack_masks[m].inst,
358 : examples_of_safe_stack_ops[s].inst,
359 : kNop
360 2 : };
361 :
362 : ValidationShouldFail(bad_program,
363 : 3,
364 : kDefaultBaseAddr,
365 2 : bad_message.str());
366 2 : }
367 : }
368 1 : }
369 :
370 5 : TEST_F(ValidatorTests, NopBundle) {
371 1 : vector<mips_inst> code(_validator.bytes_per_bundle() / kInstrSize, kNop);
372 1 : ValidationShouldPass(&code[0], code.size(), kDefaultBaseAddr,
373 2 : "NOP bundle");
374 1 : }
375 :
376 5 : TEST_F(ValidatorTests, UnmaskedSpUpdate) {
377 1 : vector<mips_inst> code(_validator.bytes_per_bundle() / kInstrSize, kNop);
378 5 : for (vector<mips_inst>::size_type i = 0; i < code.size(); ++i) {
379 4 : std::fill(code.begin(), code.end(), kNop);
380 4 : code[i] = 0x8fbd0000; // lw $sp, 0($sp)
381 4 : ValidationShouldFail(&code[0], code.size(), kDefaultBaseAddr,
382 8 : "unmasked SP update");
383 1 : }
384 1 : }
385 :
386 5 : TEST_F(ValidatorTests, MaskedSpUpdate) {
387 1 : vector<mips_inst> code((_validator.bytes_per_bundle() / kInstrSize) * 2,
388 2 : kNop);
389 8 : for (vector<mips_inst>::size_type i = 0; i < code.size() - 1; ++i) {
390 7 : std::fill(code.begin(), code.end(), kNop);
391 7 : code[i] = examples_of_safe_stack_ops[0].inst;
392 7 : code[i + 1] = examples_of_safe_stack_masks[0].inst;
393 7 : ValidationShouldPass(&code[0], code.size(), kDefaultBaseAddr,
394 14 : "masked SP update");
395 1 : }
396 1 : }
397 :
398 : /*
399 : * Implementation of the ValidatorTests utility methods. These are documented
400 : * toward the top of this file.
401 : */
402 10 : ValidatorTests::ValidatorTests()
403 : : _validator(kBytesPerBundle,
404 : kCodeRegionSize,
405 : kDataRegionSize,
406 : RegisterList::ReservedRegs(),
407 10 : RegisterList::DataAddrRegs()) {}
408 :
409 30 : bool ValidatorTests::Validate(const mips_inst *pattern,
410 : size_t inst_count,
411 : uint32_t start_addr,
412 : ProblemSink *sink) {
413 : // We think in instructions; CodeSegment thinks in bytes.
414 30 : const uint8_t *bytes = reinterpret_cast<const uint8_t *>(pattern);
415 30 : CodeSegment segment(bytes, start_addr, inst_count * sizeof(mips_inst));
416 :
417 30 : vector<CodeSegment> segments;
418 30 : segments.push_back(segment);
419 :
420 30 : return _validator.Validate(segments, sink);
421 : }
422 :
423 17 : void ValidatorTests::ValidationShouldPass(const mips_inst *pattern,
424 : size_t inst_count,
425 : uint32_t base_addr,
426 : const string &msg) {
427 17 : ASSERT_TRUE(
428 : _validator.BundleForAddress(base_addr).BeginAddr() == base_addr)
429 0 : << "base_addr parameter must be bundle-aligned";
430 :
431 17 : ProblemSpy spy;
432 :
433 17 : bool validation_result = Validate(pattern, inst_count, base_addr, &spy);
434 17 : ASSERT_TRUE(validation_result) << msg << " should pass at " << base_addr;
435 17 : vector<ProblemRecord> &problems = spy.problems();
436 17 : EXPECT_EQ(0U, problems.size()) << msg
437 17 : << " should have no problems when located at " << base_addr;
438 : }
439 :
440 13 : vector<ProblemRecord> ValidatorTests::ValidationShouldFail(
441 : const mips_inst *pattern,
442 : size_t inst_count,
443 : uint32_t base_addr,
444 : const string &msg) {
445 :
446 13 : ProblemSpy spy;
447 13 : bool validation_result = Validate(pattern, inst_count, base_addr, &spy);
448 13 : EXPECT_FALSE(validation_result) << "Expected to fail: " << msg;
449 :
450 13 : vector<ProblemRecord> problems = spy.problems();
451 : // Would use ASSERT here, but cannot ASSERT in non-void functions :-(
452 13 : EXPECT_NE(0U, problems.size())
453 0 : << "Must report validation problems: " << msg;
454 :
455 : // The rest of the checking is done in the caller.
456 13 : return problems;
457 : }
458 :
459 : }; // anonymous namespace
460 :
461 : // Test driver function.
462 1 : int main(int argc, char *argv[]) {
463 1 : testing::InitGoogleTest(&argc, argv);
464 1 : return RUN_ALL_TESTS();
465 3 : }
|
