• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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