1 : /*
2 : * Copyright 2008 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can
4 : * be found in the LICENSE file.
5 : */
6 :
7 : /*
8 : * Exercise object proxy mapping. Don't actually use real objects,
9 : * but just made-up values.
10 : *
11 : * Use a simple array to hold object / name tuples to check that the
12 : * object proxy can do lookups properly of all entered values as well
13 : * as negative examples of objects that have never been entered /
14 : * names that had never been issued. This array is unsorted, so
15 : * searching it is inefficient, but should be obviously correct.
16 : */
17 :
18 : #include "native_client/src/include/portability.h"
19 :
20 : #include <stdio.h>
21 : #include <stdlib.h>
22 : #include <string.h>
23 :
24 : #include "native_client/src/shared/platform/nacl_log.h"
25 : #include "native_client/src/shared/platform/nacl_secure_random.h"
26 : #include "native_client/src/trusted/service_runtime/nacl_all_modules.h"
27 :
28 : #include "native_client/src/trusted/service_runtime/fs/obj_proxy.h"
29 :
30 : #define SEED_BYTES 16
31 :
32 : int verbose;
33 :
34 : struct TestObj {
35 : void *obj;
36 : uint8_t const *name;
37 : };
38 :
39 : struct TestData {
40 : struct TestObj *obj_tbl;
41 : int obj_tbl_size;
42 : int obj_tbl_used;
43 : int namelen;
44 : };
45 :
46 24 : void TestDataCtor(struct TestData *self, int namelen) {
47 24 : self->obj_tbl = NULL;
48 24 : self->obj_tbl_size = 0;
49 24 : self->obj_tbl_used = 0;
50 24 : self->namelen = namelen;
51 24 : }
52 :
53 24 : void TestDataDtor(struct TestData *self) {
54 24 : free(self->obj_tbl);
55 24 : }
56 :
57 49152 : void TestDataEnterObj(struct TestData *self, void *obj, uint8_t const *name) {
58 49152 : if (self->obj_tbl_used >= self->obj_tbl_size) {
59 192 : if (self->obj_tbl_size) {
60 168 : self->obj_tbl_size *= 2;
61 : } else {
62 24 : self->obj_tbl_size = 16;
63 : }
64 192 : self->obj_tbl = realloc(self->obj_tbl,
65 : self->obj_tbl_size * sizeof *self->obj_tbl);
66 192 : if (NULL == self->obj_tbl) {
67 0 : fprintf(stderr, "obj_tbl_enter: out of memory\n");
68 0 : exit(1);
69 : }
70 : }
71 49152 : self->obj_tbl[self->obj_tbl_used].obj = obj;
72 49152 : self->obj_tbl[self->obj_tbl_used].name = name;
73 49152 : ++self->obj_tbl_used;
74 49152 : }
75 :
76 196560 : uint8_t const *TestDataFindName(struct TestData *self, void *obj) {
77 : int i;
78 :
79 201424848 : for (i = 0; i < self->obj_tbl_used; ++i) {
80 201424848 : if (self->obj_tbl[i].obj == obj) {
81 196560 : return self->obj_tbl[i].name;
82 : }
83 : }
84 0 : return NULL;
85 : }
86 :
87 0 : void *TestDataFindObj(struct TestData *self, uint8_t const *name) {
88 : int i;
89 :
90 : /* the dirt simple, slow, but obviously correct algorithm */
91 0 : for (i = 0; i < self->obj_tbl_used; ++i) {
92 0 : if (!memcmp(self->obj_tbl[i].name, name, self->namelen)) {
93 0 : return self->obj_tbl[i].obj;
94 : }
95 : }
96 0 : return NULL;
97 : }
98 :
99 0 : void print_name(FILE *ostr, uint8_t const *name, int namelen) {
100 : int i;
101 : int v;
102 :
103 0 : for (i = 0; i < namelen; ++i) {
104 0 : v = name[i] & 0xff;
105 0 : if (0 == (i & 0x7)) {
106 0 : putc(' ', ostr);
107 : }
108 0 : fprintf(ostr, "%02x", v);
109 : }
110 0 : }
111 :
112 :
113 : int test_for_size(int namelen, int num_samples_init, int num_bogus_init,
114 24 : struct NaClSecureRngIf *rng) {
115 : struct TestData td;
116 : struct NaClObjProxy nop;
117 : uintptr_t samp;
118 : void *obj;
119 : uint8_t const *name;
120 : uint8_t const *true_name;
121 : void *found_obj;
122 24 : int passed = 0;
123 : uint8_t *bogus_name;
124 24 : uintptr_t num_samples = (uintptr_t)num_samples_init;
125 24 : uintptr_t num_bogus = (uintptr_t)num_bogus_init;
126 :
127 24 : bogus_name = malloc(namelen);
128 24 : printf("Testing for name length %d, %"NACL_PRIxPTR" legit samples, "
129 : "%"NACL_PRIxPTR" bogus lookups\n",
130 : namelen, num_samples, num_bogus);
131 24 : TestDataCtor(&td, namelen);
132 :
133 24 : NaClObjProxyCtor(&nop, rng, namelen);
134 :
135 24 : printf("insertion\n");
136 49176 : for (samp = 0; samp < num_samples; ++samp) {
137 49152 : obj = (void *) samp;
138 49152 : name = NaClObjProxyInsert(&nop, obj);
139 :
140 49152 : if (verbose) {
141 0 : printf("%4"NACL_PRIxPTR": ", samp);
142 0 : print_name(stdout, name, namelen);
143 0 : putchar('\n');
144 : }
145 :
146 49152 : TestDataEnterObj(&td, obj, name);
147 : }
148 :
149 24 : printf("lookup\n");
150 : /* now look up every one */
151 49176 : for (samp = 0; samp < num_samples; ++samp) {
152 49152 : obj = (void *) samp;
153 :
154 49152 : true_name = TestDataFindName(&td, obj);
155 49152 : if (NULL == true_name) {
156 0 : printf("`True name' for object %"NACL_PRIxPTR" not found\n", samp);
157 0 : goto cleanup;
158 : }
159 49152 : if (verbose) {
160 0 : printf("[ %4"NACL_PRIxPTR": ", samp);
161 0 : print_name(stdout, true_name, namelen);
162 0 : printf(" ]\n");
163 : }
164 :
165 49152 : name = NaClObjProxyFindNameByObj(&nop, obj);
166 49152 : if (NULL == name) {
167 0 : printf("Object %"NACL_PRIxPTR" not found!\n", samp);
168 0 : goto cleanup;
169 : }
170 :
171 49152 : if (memcmp(name, true_name, namelen)) {
172 0 : printf("Name mismatch! Expected ");
173 0 : print_name(stdout, true_name, namelen);
174 0 : printf(" got ");
175 0 : print_name(stdout, name, namelen);
176 0 : printf("\n");
177 0 : goto cleanup;
178 : }
179 : }
180 :
181 : /* now look up every one, backwards */
182 24 : printf("order reversed lookup\n");
183 49176 : for (samp = num_samples; --samp > 0; ) {
184 49128 : obj = (void *) samp;
185 :
186 49128 : true_name = TestDataFindName(&td, obj);
187 49128 : if (NULL == true_name) {
188 0 : printf("`True name' for object %"NACL_PRIxPTR" not found\n", samp);
189 0 : goto cleanup;
190 : }
191 49128 : if (verbose) {
192 0 : printf("[ %4"NACL_PRIxPTR": ", samp);
193 0 : print_name(stdout, true_name, namelen);
194 0 : printf(" ]\n");
195 : }
196 :
197 49128 : name = NaClObjProxyFindNameByObj(&nop, obj);
198 49128 : if (NULL == name) {
199 0 : printf("Object %"NACL_PRIxPTR" not found!\n", samp);
200 0 : goto cleanup;
201 : }
202 :
203 49128 : if (memcmp(name, true_name, namelen)) {
204 0 : printf("Name mismatch! Expected ");
205 0 : print_name(stdout, true_name, namelen);
206 0 : printf(" got ");
207 0 : print_name(stdout, name, namelen);
208 0 : printf("\n");
209 0 : goto cleanup;
210 : }
211 : }
212 :
213 24 : printf("lookup by name\n");
214 : /* now look up every one */
215 49176 : for (samp = 0; samp < num_samples; ++samp) {
216 49152 : obj = (void *) samp;
217 :
218 49152 : true_name = TestDataFindName(&td, obj);
219 49152 : if (NULL == true_name) {
220 0 : printf("`True name' for object %"NACL_PRIxPTR" not found\n", samp);
221 0 : goto cleanup;
222 : }
223 49152 : if (verbose) {
224 0 : printf("[ %4"NACL_PRIxPTR": ", samp);
225 0 : print_name(stdout, true_name, namelen);
226 0 : printf(" ]\n");
227 : }
228 :
229 49152 : found_obj = (void *) 0xdeadbeef;
230 49152 : if (!NaClObjProxyFindObjByName(&nop, true_name, &found_obj)) {
231 0 : printf("Object %"NACL_PRIxPTR" not found, name ", samp);
232 0 : print_name(stdout, true_name, namelen);
233 0 : printf("!\n");
234 0 : goto cleanup;
235 : }
236 :
237 49152 : if (found_obj != obj) {
238 0 : printf("Object mismatch! Expected 0x%08"
239 : NACL_PRIxPTR" got 0x%08"NACL_PRIxPTR"\n",
240 : (uintptr_t) obj, (uintptr_t) found_obj);
241 0 : goto cleanup;
242 : }
243 : }
244 :
245 24 : printf("lookup by name, rev order\n");
246 : /* now look up every one */
247 49176 : for (samp = num_samples; --samp > 0; ) {
248 49128 : obj = (void *) samp;
249 :
250 49128 : true_name = TestDataFindName(&td, obj);
251 49128 : if (NULL == true_name) {
252 0 : printf("`True name' for object %"NACL_PRIxPTR" not found\n", samp);
253 0 : goto cleanup;
254 : }
255 49128 : if (verbose) {
256 0 : printf("[ %4"NACL_PRIxPTR": ", samp);
257 0 : print_name(stdout, true_name, namelen);
258 0 : printf(" ]\n");
259 : }
260 :
261 49128 : if (!NaClObjProxyFindObjByName(&nop, true_name, &found_obj)) {
262 0 : printf("Object %"NACL_PRIxPTR" not found!\n", samp);
263 0 : goto cleanup;
264 : }
265 :
266 49128 : if (found_obj != obj) {
267 0 : printf("Object mismatch! Expected 0x%08"NACL_PRIxPTR
268 : " got 0x%08"NACL_PRIxPTR,
269 : (uintptr_t) obj, (uintptr_t) found_obj);
270 0 : goto cleanup;
271 : }
272 : }
273 :
274 24 : printf("Bogus objects\n");
275 24600 : for (samp = num_samples; samp < num_samples + num_bogus; ++samp) {
276 24576 : obj = (void *) samp;
277 24576 : name = NaClObjProxyFindNameByObj(&nop, obj);
278 24576 : if (NULL != name) {
279 0 : printf("Bogus object %"NACL_PRIxPTR" FOUND\n", samp);
280 0 : goto cleanup;
281 : }
282 : }
283 :
284 24 : printf("Bogus names\n");
285 24600 : for (samp = 0; samp < num_bogus; ++samp) {
286 24576 : (*rng->vtbl->GenBytes)(rng, bogus_name, namelen);
287 24576 : if (NaClObjProxyFindObjByName(&nop, bogus_name, &obj)) {
288 0 : printf("Bogus name");
289 0 : print_name(stdout, bogus_name, namelen);
290 0 : printf(" FOUND!\n");
291 0 : goto cleanup;
292 : }
293 : }
294 :
295 24 : printf("OK\n");
296 24 : passed = 1;
297 :
298 24 : cleanup:
299 24 : NaClObjProxyDtor(&nop);
300 24 : TestDataDtor(&td);
301 24 : free(bogus_name);
302 24 : return passed;
303 : }
304 :
305 :
306 : /*
307 : * A very weak linear congruential generator. Only use for testing.
308 : */
309 : struct WeakRng {
310 : struct NaClSecureRngIf base;
311 : uint32_t x;
312 : };
313 :
314 : static struct NaClSecureRngIfVtbl const kWeakRngVtbl;
315 :
316 0 : int WeakRngCtor(struct WeakRng *self) {
317 0 : self->base.vtbl = &kWeakRngVtbl;
318 0 : return 1;
319 : }
320 :
321 : int WeakRngTestingCtor(struct WeakRng *self,
322 : uint8_t *seed_material,
323 0 : size_t seed_bytes) {
324 0 : while (seed_bytes > 0) {
325 0 : self->x = (self->x * 263) ^ seed_material[--seed_bytes];
326 : }
327 0 : if (0 == self->x) {
328 0 : self->x = 263;
329 : }
330 0 : self->base.vtbl = &kWeakRngVtbl;
331 0 : return 1;
332 : }
333 :
334 0 : void WeakRngDtor(struct NaClSecureRngIf *vself) {
335 0 : vself->vtbl = NULL;
336 0 : }
337 :
338 0 : uint8_t WeakRngGenByte(struct NaClSecureRngIf *vself) {
339 0 : struct WeakRng *self = (struct WeakRng *) vself;
340 : uint64_t y;
341 :
342 0 : y = (uint64_t) self->x;
343 0 : y *= 16807;
344 0 : y = y + (y >> 31);
345 0 : y = y & ((1u << 31) - 1);
346 0 : self->x = (uint32_t) y;
347 0 : return self->x;
348 : }
349 :
350 : static struct NaClSecureRngIfVtbl const kWeakRngVtbl = {
351 : WeakRngDtor,
352 : WeakRngGenByte,
353 : NaClSecureRngDefaultGenUint32,
354 : NaClSecureRngDefaultGenBytes,
355 : NaClSecureRngDefaultUniform,
356 : };
357 :
358 :
359 : int RunTests(int namelen_start, int namelen_end, int namelen_inc,
360 : int num_samples, int num_bogus,
361 1 : struct NaClSecureRngIf *rng) {
362 1 : int pass = 1;
363 : int namelen;
364 :
365 25 : for (namelen = namelen_start; namelen < namelen_end; namelen += namelen_inc) {
366 24 : pass = pass && test_for_size(namelen, num_samples, num_bogus, rng);
367 : }
368 1 : return pass;
369 : }
370 :
371 1 : int main(int ac, char **av) {
372 : int opt;
373 1 : int namelen_start = 8;
374 1 : int namelen_end = 32;
375 1 : int namelen_inc = 1;
376 1 : int num_samples = 1 << 16;
377 1 : int num_bogus = 1024;
378 1 : int pass = 1;
379 :
380 1 : int seed_provided = 0;
381 : uint8_t seed_material[SEED_BYTES];
382 : size_t ix;
383 : unsigned int seed_byte;
384 :
385 : struct NaClSecureRng rng;
386 : struct NaClSecureRngIf *rp;
387 1 : int use_weak_rng = 0;
388 : struct WeakRng weak_rng;
389 1 : int fallback_to_weak = 1;
390 :
391 1 : memset(seed_material, 0, sizeof seed_material);
392 :
393 3 : while (-1 != (opt = getopt(ac, av, "s:e:i:n:b:vS:fFwW"))) {
394 1 : switch (opt) {
395 : case 's':
396 0 : namelen_start = strtol(optarg, (char **) 0, 0);
397 0 : break;
398 : case 'e':
399 0 : namelen_end = strtol(optarg, (char **) 0, 0);
400 0 : break;
401 : case 'i':
402 0 : namelen_inc = strtol(optarg, (char **) 0, 0);
403 0 : break;
404 : case 'n':
405 1 : num_samples = strtol(optarg, (char **) 0, 0);
406 1 : break;
407 : case 'b':
408 0 : num_bogus = strtol(optarg, (char **) 0, 0);
409 0 : break;
410 : case 'v':
411 0 : ++verbose;
412 0 : break;
413 : case 'S':
414 0 : for (ix = 0;
415 0 : (1 == sscanf(optarg + 2*ix, "%2x", &seed_byte))
416 : && ix < sizeof seed_material;
417 0 : ++ix) {
418 0 : seed_material[ix] = seed_byte;
419 : }
420 0 : seed_provided = 1;
421 0 : break;
422 : case 'f':
423 0 : fallback_to_weak = 1;
424 0 : break;
425 : case 'F':
426 0 : fallback_to_weak = 0;
427 0 : break;
428 : case 'w':
429 0 : use_weak_rng = 1;
430 0 : break;
431 : case 'W':
432 0 : use_weak_rng = 0;
433 0 : break;
434 : default:
435 0 : fprintf(stderr,
436 : "Usage: obj_proxy_test [-s start_namelen] [-e end_namelen]\n"
437 : " [-i incr_namelen] [-n num_samples]\n"
438 : " [-b num_bogus_samples]\n"
439 : " [-v]\n"
440 : " [-S] hex-seed-material\n"
441 : " [-fFwW]\n"
442 : " -v verbose mode\n"
443 : " -f fall back to a weak generator if deterministic seeding\n"
444 : " is not possible (default) \n"
445 : " -F fall back to non-deterministic seeding if\n"
446 : " deterministic seeding is not possible\n"
447 : " -w use a weak generator\n"
448 : " -W use the standard secure generator (default)\n"
449 : "\n"
450 : " NB: it is bad if num_samples >= 2**(4*start_namelen)\n"
451 : " since the birthday paradox will cause name collisions\n"
452 : );
453 0 : exit(1);
454 : }
455 : }
456 1 : NaClAllModulesInit();
457 1 : if (namelen_start > namelen_end || namelen_inc <= 0) {
458 0 : fprintf(stderr, "obj_proxy_test: name length parameters are bogus\n");
459 0 : exit(1);
460 : }
461 :
462 1 : if (!seed_provided) {
463 1 : NaClSecureRngCtor(&rng);
464 :
465 17 : for (ix = 0; ix < sizeof seed_material; ++ix) {
466 16 : seed_material[ix] = (*rng.base.vtbl->GenByte)(&rng.base);
467 : }
468 :
469 1 : (*rng.base.vtbl->Dtor)(&rng.base);
470 : }
471 :
472 1 : printf("TEST RNG SEED: ");
473 17 : for (ix = 0; ix < sizeof seed_material; ++ix) {
474 16 : printf("%02x", seed_material[ix]);
475 : }
476 1 : printf("\n");
477 :
478 1 : if (use_weak_rng) {
479 0 : if (verbose) {
480 0 : printf("Using weak generator\n");
481 : }
482 0 : WeakRngTestingCtor(&weak_rng, seed_material, sizeof seed_material);
483 0 : rp = &weak_rng.base;
484 : } else {
485 1 : if (!NaClSecureRngTestingCtor(&rng, seed_material, sizeof seed_material)) {
486 0 : if (fallback_to_weak) {
487 0 : printf("Cannot set seed. Reverting to weak generator.\n");
488 0 : WeakRngTestingCtor(&weak_rng, seed_material, sizeof seed_material);
489 0 : rp = &weak_rng.base;
490 : } else {
491 0 : printf("Cannot set seed. Reverting to nondeterministic generator.\n");
492 0 : NaClSecureRngCtor(&rng);
493 0 : rp = &rng.base;
494 : }
495 : } else {
496 1 : if (verbose) {
497 0 : printf("Using standard generator\n");
498 : }
499 1 : rp = &rng.base;
500 : }
501 : }
502 :
503 1 : pass = pass && RunTests(namelen_start, namelen_end, namelen_inc,
504 : num_samples, num_bogus, rp);
505 :
506 1 : (*rp->vtbl->Dtor)(rp);
507 :
508 1 : NaClAllModulesFini();
509 :
510 1 : printf("%s\n", pass ? "PASSED" : "FAILED");
511 :
512 1 : return !pass;
513 : }
|
