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