1
2 /* Author : Stephen Smalley, <sds@tycho.nsa.gov> */
3
4 /*
5 * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
6 * Tuned number of hash slots for avtab to reduce memory usage
7 */
8
9 /* Updated: Frank Mayer <mayerf@tresys.com>
10 * and Karl MacMillan <kmacmillan@mentalrootkit.com>
11 *
12 * Added conditional policy language extensions
13 *
14 * Updated: Red Hat, Inc. James Morris <jmorris@redhat.com>
15 *
16 * Code cleanup
17 *
18 * Updated: Karl MacMillan <kmacmillan@mentalrootkit.com>
19 *
20 * Copyright (C) 2003 Tresys Technology, LLC
21 * Copyright (C) 2003,2007 Red Hat, Inc.
22 *
23 * This library is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU Lesser General Public
25 * License as published by the Free Software Foundation; either
26 * version 2.1 of the License, or (at your option) any later version.
27 *
28 * This library is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
31 * Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public
34 * License along with this library; if not, write to the Free Software
35 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
36 */
37
38 /* FLASK */
39
40 /*
41 * Implementation of the access vector table type.
42 */
43
44 #include <stdlib.h>
45 #include <sepol/policydb/avtab.h>
46 #include <sepol/policydb/policydb.h>
47 #include <sepol/errcodes.h>
48
49 #include "debug.h"
50 #include "private.h"
51
52 /* Based on MurmurHash3, written by Austin Appleby and placed in the
53 * public domain.
54 */
55 ignore_unsigned_overflow_
avtab_hash(struct avtab_key * keyp,uint32_t mask)56 static inline int avtab_hash(struct avtab_key *keyp, uint32_t mask)
57 {
58 static const uint32_t c1 = 0xcc9e2d51;
59 static const uint32_t c2 = 0x1b873593;
60 static const uint32_t r1 = 15;
61 static const uint32_t r2 = 13;
62 static const uint32_t m = 5;
63 static const uint32_t n = 0xe6546b64;
64
65 uint32_t hash = 0;
66
67 #define mix(input) do { \
68 uint32_t v = input; \
69 v *= c1; \
70 v = (v << r1) | (v >> (32 - r1)); \
71 v *= c2; \
72 hash ^= v; \
73 hash = (hash << r2) | (hash >> (32 - r2)); \
74 hash = hash * m + n; \
75 } while (0)
76
77 mix(keyp->target_class);
78 mix(keyp->target_type);
79 mix(keyp->source_type);
80
81 #undef mix
82
83 hash ^= hash >> 16;
84 hash *= 0x85ebca6b;
85 hash ^= hash >> 13;
86 hash *= 0xc2b2ae35;
87 hash ^= hash >> 16;
88
89 return hash & mask;
90 }
91
92 static avtab_ptr_t
avtab_insert_node(avtab_t * h,int hvalue,avtab_ptr_t prev,avtab_key_t * key,avtab_datum_t * datum)93 avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key,
94 avtab_datum_t * datum)
95 {
96 avtab_ptr_t newnode;
97 avtab_extended_perms_t *xperms;
98
99 newnode = (avtab_ptr_t) malloc(sizeof(struct avtab_node));
100 if (newnode == NULL)
101 return NULL;
102 memset(newnode, 0, sizeof(struct avtab_node));
103 newnode->key = *key;
104
105 if (key->specified & AVTAB_XPERMS) {
106 xperms = calloc(1, sizeof(avtab_extended_perms_t));
107 if (xperms == NULL) {
108 free(newnode);
109 return NULL;
110 }
111 if (datum->xperms) /* else caller populates xperms */
112 *xperms = *(datum->xperms);
113
114 newnode->datum.xperms = xperms;
115 /* data is usually ignored with xperms, except in the case of
116 * neverallow checking, which requires permission bits to be set.
117 * So copy data so it is set in the avtab
118 */
119 newnode->datum.data = datum->data;
120 } else {
121 newnode->datum = *datum;
122 }
123
124 if (prev) {
125 newnode->next = prev->next;
126 prev->next = newnode;
127 } else {
128 newnode->next = h->htable[hvalue];
129 h->htable[hvalue] = newnode;
130 }
131
132 h->nel++;
133 return newnode;
134 }
135
avtab_insert(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)136 int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
137 {
138 int hvalue;
139 avtab_ptr_t prev, cur, newnode;
140 uint16_t specified =
141 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
142
143 if (!h || !h->htable)
144 return SEPOL_ENOMEM;
145
146 hvalue = avtab_hash(key, h->mask);
147 for (prev = NULL, cur = h->htable[hvalue];
148 cur; prev = cur, cur = cur->next) {
149 if (key->source_type == cur->key.source_type &&
150 key->target_type == cur->key.target_type &&
151 key->target_class == cur->key.target_class &&
152 (specified & cur->key.specified)) {
153 /* Extended permissions are not necessarily unique */
154 if (specified & AVTAB_XPERMS)
155 break;
156 return SEPOL_EEXIST;
157 }
158 if (key->source_type < cur->key.source_type)
159 break;
160 if (key->source_type == cur->key.source_type &&
161 key->target_type < cur->key.target_type)
162 break;
163 if (key->source_type == cur->key.source_type &&
164 key->target_type == cur->key.target_type &&
165 key->target_class < cur->key.target_class)
166 break;
167 }
168
169 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
170 if (!newnode)
171 return SEPOL_ENOMEM;
172
173 return 0;
174 }
175
176 /* Unlike avtab_insert(), this function allow multiple insertions of the same
177 * key/specified mask into the table, as needed by the conditional avtab.
178 * It also returns a pointer to the node inserted.
179 */
180 avtab_ptr_t
avtab_insert_nonunique(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)181 avtab_insert_nonunique(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
182 {
183 int hvalue;
184 avtab_ptr_t prev, cur, newnode;
185 uint16_t specified =
186 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
187
188 if (!h || !h->htable)
189 return NULL;
190 hvalue = avtab_hash(key, h->mask);
191 for (prev = NULL, cur = h->htable[hvalue];
192 cur; prev = cur, cur = cur->next) {
193 if (key->source_type == cur->key.source_type &&
194 key->target_type == cur->key.target_type &&
195 key->target_class == cur->key.target_class &&
196 (specified & cur->key.specified))
197 break;
198 if (key->source_type < cur->key.source_type)
199 break;
200 if (key->source_type == cur->key.source_type &&
201 key->target_type < cur->key.target_type)
202 break;
203 if (key->source_type == cur->key.source_type &&
204 key->target_type == cur->key.target_type &&
205 key->target_class < cur->key.target_class)
206 break;
207 }
208 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
209
210 return newnode;
211 }
212
avtab_search(avtab_t * h,avtab_key_t * key)213 avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * key)
214 {
215 int hvalue;
216 avtab_ptr_t cur;
217 uint16_t specified =
218 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
219
220 if (!h || !h->htable)
221 return NULL;
222
223 hvalue = avtab_hash(key, h->mask);
224 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
225 if (key->source_type == cur->key.source_type &&
226 key->target_type == cur->key.target_type &&
227 key->target_class == cur->key.target_class &&
228 (specified & cur->key.specified))
229 return &cur->datum;
230
231 if (key->source_type < cur->key.source_type)
232 break;
233 if (key->source_type == cur->key.source_type &&
234 key->target_type < cur->key.target_type)
235 break;
236 if (key->source_type == cur->key.source_type &&
237 key->target_type == cur->key.target_type &&
238 key->target_class < cur->key.target_class)
239 break;
240 }
241
242 return NULL;
243 }
244
245 /* This search function returns a node pointer, and can be used in
246 * conjunction with avtab_search_next_node()
247 */
avtab_search_node(avtab_t * h,avtab_key_t * key)248 avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key)
249 {
250 int hvalue;
251 avtab_ptr_t cur;
252 uint16_t specified =
253 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
254
255 if (!h || !h->htable)
256 return NULL;
257
258 hvalue = avtab_hash(key, h->mask);
259 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
260 if (key->source_type == cur->key.source_type &&
261 key->target_type == cur->key.target_type &&
262 key->target_class == cur->key.target_class &&
263 (specified & cur->key.specified))
264 return cur;
265
266 if (key->source_type < cur->key.source_type)
267 break;
268 if (key->source_type == cur->key.source_type &&
269 key->target_type < cur->key.target_type)
270 break;
271 if (key->source_type == cur->key.source_type &&
272 key->target_type == cur->key.target_type &&
273 key->target_class < cur->key.target_class)
274 break;
275 }
276 return NULL;
277 }
278
avtab_search_node_next(avtab_ptr_t node,int specified)279 avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified)
280 {
281 avtab_ptr_t cur;
282
283 if (!node)
284 return NULL;
285
286 specified &= ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
287 for (cur = node->next; cur; cur = cur->next) {
288 if (node->key.source_type == cur->key.source_type &&
289 node->key.target_type == cur->key.target_type &&
290 node->key.target_class == cur->key.target_class &&
291 (specified & cur->key.specified))
292 return cur;
293
294 if (node->key.source_type < cur->key.source_type)
295 break;
296 if (node->key.source_type == cur->key.source_type &&
297 node->key.target_type < cur->key.target_type)
298 break;
299 if (node->key.source_type == cur->key.source_type &&
300 node->key.target_type == cur->key.target_type &&
301 node->key.target_class < cur->key.target_class)
302 break;
303 }
304 return NULL;
305 }
306
avtab_destroy(avtab_t * h)307 void avtab_destroy(avtab_t * h)
308 {
309 unsigned int i;
310 avtab_ptr_t cur, temp;
311
312 if (!h || !h->htable)
313 return;
314
315 for (i = 0; i < h->nslot; i++) {
316 cur = h->htable[i];
317 while (cur != NULL) {
318 if (cur->key.specified & AVTAB_XPERMS) {
319 free(cur->datum.xperms);
320 }
321 temp = cur;
322 cur = cur->next;
323 free(temp);
324 }
325 h->htable[i] = NULL;
326 }
327 free(h->htable);
328 h->htable = NULL;
329 h->nslot = 0;
330 h->mask = 0;
331 }
332
avtab_map(avtab_t * h,int (* apply)(avtab_key_t * k,avtab_datum_t * d,void * args),void * args)333 int avtab_map(avtab_t * h,
334 int (*apply) (avtab_key_t * k,
335 avtab_datum_t * d, void *args), void *args)
336 {
337 unsigned int i;
338 int ret;
339 avtab_ptr_t cur;
340
341 if (!h)
342 return 0;
343
344 for (i = 0; i < h->nslot; i++) {
345 cur = h->htable[i];
346 while (cur != NULL) {
347 ret = apply(&cur->key, &cur->datum, args);
348 if (ret)
349 return ret;
350 cur = cur->next;
351 }
352 }
353 return 0;
354 }
355
avtab_init(avtab_t * h)356 int avtab_init(avtab_t * h)
357 {
358 h->htable = NULL;
359 h->nel = 0;
360 return 0;
361 }
362
avtab_alloc(avtab_t * h,uint32_t nrules)363 int avtab_alloc(avtab_t *h, uint32_t nrules)
364 {
365 uint32_t mask = 0;
366 uint32_t shift = 0;
367 uint32_t work = nrules;
368 uint32_t nslot = 0;
369
370 if (nrules == 0)
371 goto out;
372
373 while (work) {
374 work = work >> 1;
375 shift++;
376 }
377 if (shift > 2)
378 shift = shift - 2;
379 nslot = UINT32_C(1) << shift;
380 if (nslot > MAX_AVTAB_HASH_BUCKETS)
381 nslot = MAX_AVTAB_HASH_BUCKETS;
382 mask = nslot - 1;
383
384 h->htable = calloc(nslot, sizeof(avtab_ptr_t));
385 if (!h->htable)
386 return -1;
387 out:
388 h->nel = 0;
389 h->nslot = nslot;
390 h->mask = mask;
391 return 0;
392 }
393
avtab_hash_eval(avtab_t * h,char * tag)394 void avtab_hash_eval(avtab_t * h, char *tag)
395 {
396 unsigned int i, chain_len, slots_used, max_chain_len;
397 avtab_ptr_t cur;
398
399 slots_used = 0;
400 max_chain_len = 0;
401 for (i = 0; i < h->nslot; i++) {
402 cur = h->htable[i];
403 if (cur) {
404 slots_used++;
405 chain_len = 0;
406 while (cur) {
407 chain_len++;
408 cur = cur->next;
409 }
410
411 if (chain_len > max_chain_len)
412 max_chain_len = chain_len;
413 }
414 }
415
416 printf
417 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
418 tag, h->nel, slots_used, h->nslot, max_chain_len);
419 }
420
421 /* Ordering of datums in the original avtab format in the policy file. */
422 static const uint16_t spec_order[] = {
423 AVTAB_ALLOWED,
424 AVTAB_AUDITDENY,
425 AVTAB_AUDITALLOW,
426 AVTAB_TRANSITION,
427 AVTAB_CHANGE,
428 AVTAB_MEMBER,
429 AVTAB_XPERMS_ALLOWED,
430 AVTAB_XPERMS_AUDITALLOW,
431 AVTAB_XPERMS_DONTAUDIT
432 };
433
avtab_read_item(struct policy_file * fp,uint32_t vers,avtab_t * a,int (* insertf)(avtab_t * a,avtab_key_t * k,avtab_datum_t * d,void * p),void * p)434 int avtab_read_item(struct policy_file *fp, uint32_t vers, avtab_t * a,
435 int (*insertf) (avtab_t * a, avtab_key_t * k,
436 avtab_datum_t * d, void *p), void *p)
437 {
438 uint8_t buf8;
439 uint16_t buf16[4], enabled;
440 uint32_t buf32[8], items, items2, val;
441 avtab_key_t key;
442 avtab_datum_t datum;
443 avtab_extended_perms_t xperms;
444 unsigned set;
445 unsigned int i;
446 int rc;
447
448 memset(&key, 0, sizeof(avtab_key_t));
449 memset(&datum, 0, sizeof(avtab_datum_t));
450 memset(&xperms, 0, sizeof(avtab_extended_perms_t));
451
452 if (vers < POLICYDB_VERSION_AVTAB) {
453 rc = next_entry(buf32, fp, sizeof(uint32_t));
454 if (rc < 0) {
455 ERR(fp->handle, "truncated entry");
456 return -1;
457 }
458 items2 = le32_to_cpu(buf32[0]);
459
460 if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) {
461 ERR(fp->handle, "invalid item count");
462 return -1;
463 }
464
465 rc = next_entry(buf32, fp, sizeof(uint32_t) * items2);
466 if (rc < 0) {
467 ERR(fp->handle, "truncated entry");
468 return -1;
469 }
470
471 items = 0;
472 val = le32_to_cpu(buf32[items++]);
473 key.source_type = (uint16_t) val;
474 if (key.source_type != val) {
475 ERR(fp->handle, "truncated source type");
476 return -1;
477 }
478 val = le32_to_cpu(buf32[items++]);
479 key.target_type = (uint16_t) val;
480 if (key.target_type != val) {
481 ERR(fp->handle, "truncated target type");
482 return -1;
483 }
484 val = le32_to_cpu(buf32[items++]);
485 key.target_class = (uint16_t) val;
486 if (key.target_class != val) {
487 ERR(fp->handle, "truncated target class");
488 return -1;
489 }
490
491 val = le32_to_cpu(buf32[items++]);
492 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
493
494 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
495 ERR(fp->handle, "null entry");
496 return -1;
497 }
498 if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) {
499 ERR(fp->handle, "entry has both access "
500 "vectors and types");
501 return -1;
502 }
503
504 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
505 if (val & spec_order[i]) {
506 if (items >= items2) { /* items is index, items2 is total number */
507 ERR(fp->handle, "entry has too many items (%d/%d)",
508 items + 1, items2);
509 return -1;
510 }
511 key.specified = spec_order[i] | enabled;
512 datum.data = le32_to_cpu(buf32[items++]);
513 rc = insertf(a, &key, &datum, p);
514 if (rc)
515 return rc;
516 }
517 }
518
519 if (items != items2) {
520 ERR(fp->handle, "entry only had %d items, "
521 "expected %d", items2, items);
522 return -1;
523 }
524 return 0;
525 }
526
527 rc = next_entry(buf16, fp, sizeof(uint16_t) * 4);
528 if (rc < 0) {
529 ERR(fp->handle, "truncated entry");
530 return -1;
531 }
532 items = 0;
533 key.source_type = le16_to_cpu(buf16[items++]);
534 key.target_type = le16_to_cpu(buf16[items++]);
535 key.target_class = le16_to_cpu(buf16[items++]);
536 key.specified = le16_to_cpu(buf16[items++]);
537
538 set = 0;
539 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
540 if (key.specified & spec_order[i])
541 set++;
542 }
543 if (!set || set > 1) {
544 ERR(fp->handle, "more than one specifier");
545 return -1;
546 }
547
548 if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) &&
549 (key.specified & AVTAB_XPERMS)) {
550 ERR(fp->handle, "policy version %u does not support extended "
551 "permissions rules and one was specified", vers);
552 return -1;
553 } else if (key.specified & AVTAB_XPERMS) {
554 rc = next_entry(&buf8, fp, sizeof(uint8_t));
555 if (rc < 0) {
556 ERR(fp->handle, "truncated entry");
557 return -1;
558 }
559 xperms.specified = buf8;
560 rc = next_entry(&buf8, fp, sizeof(uint8_t));
561 if (rc < 0) {
562 ERR(fp->handle, "truncated entry");
563 return -1;
564 }
565 xperms.driver = buf8;
566 rc = next_entry(buf32, fp, sizeof(uint32_t)*8);
567 if (rc < 0) {
568 ERR(fp->handle, "truncated entry");
569 return -1;
570 }
571 for (i = 0; i < ARRAY_SIZE(xperms.perms); i++)
572 xperms.perms[i] = le32_to_cpu(buf32[i]);
573 datum.xperms = &xperms;
574 } else {
575 rc = next_entry(buf32, fp, sizeof(uint32_t));
576 if (rc < 0) {
577 ERR(fp->handle, "truncated entry");
578 return -1;
579 }
580 datum.data = le32_to_cpu(*buf32);
581 }
582 return insertf(a, &key, &datum, p);
583 }
584
avtab_insertf(avtab_t * a,avtab_key_t * k,avtab_datum_t * d,void * p)585 static int avtab_insertf(avtab_t * a, avtab_key_t * k, avtab_datum_t * d,
586 void *p __attribute__ ((unused)))
587 {
588 return avtab_insert(a, k, d);
589 }
590
avtab_read(avtab_t * a,struct policy_file * fp,uint32_t vers)591 int avtab_read(avtab_t * a, struct policy_file *fp, uint32_t vers)
592 {
593 unsigned int i;
594 int rc;
595 uint32_t buf[1];
596 uint32_t nel;
597
598 rc = next_entry(buf, fp, sizeof(uint32_t));
599 if (rc < 0) {
600 ERR(fp->handle, "truncated table");
601 goto bad;
602 }
603 nel = le32_to_cpu(buf[0]);
604 if (!nel) {
605 ERR(fp->handle, "table is empty");
606 goto bad;
607 }
608
609 rc = avtab_alloc(a, nel);
610 if (rc) {
611 ERR(fp->handle, "out of memory");
612 goto bad;
613 }
614
615 for (i = 0; i < nel; i++) {
616 rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL);
617 if (rc) {
618 if (rc == SEPOL_ENOMEM)
619 ERR(fp->handle, "out of memory");
620 if (rc == SEPOL_EEXIST)
621 ERR(fp->handle, "duplicate entry");
622 ERR(fp->handle, "failed on entry %d of %u", i, nel);
623 goto bad;
624 }
625 }
626
627 return 0;
628
629 bad:
630 avtab_destroy(a);
631 return -1;
632 }
633