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