1/* Authors: Joshua Brindle <jbrindle@tresys.com>
2 * 	    Jason Tang <jtang@tresys.com>
3 *
4 * Updates: KaiGai Kohei <kaigai@ak.jp.nec.com>
5 *          adds checks based on newer boundary facility.
6 *
7 * A set of utility functions that aid policy decision when dealing
8 * with hierarchal namespaces.
9 *
10 * Copyright (C) 2005 Tresys Technology, LLC
11 *
12 * Copyright (c) 2008 NEC Corporation
13 *
14 *  This library is free software; you can redistribute it and/or
15 *  modify it under the terms of the GNU Lesser General Public
16 *  License as published by the Free Software Foundation; either
17 *  version 2.1 of the License, or (at your option) any later version.
18 *
19 *  This library is distributed in the hope that it will be useful,
20 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
21 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
22 *  Lesser General Public License for more details.
23 *
24 *  You should have received a copy of the GNU Lesser General Public
25 *  License along with this library; if not, write to the Free Software
26 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
27 */
28
29#include <string.h>
30#include <stdlib.h>
31#include <assert.h>
32#include <sepol/policydb/policydb.h>
33#include <sepol/policydb/conditional.h>
34#include <sepol/policydb/hierarchy.h>
35#include <sepol/policydb/expand.h>
36#include <sepol/policydb/util.h>
37
38#include "debug.h"
39
40typedef struct hierarchy_args {
41	policydb_t *p;
42	avtab_t *expa;		/* expanded avtab */
43	/* This tells check_avtab_hierarchy to check this list in addition to the unconditional avtab */
44	cond_av_list_t *opt_cond_list;
45	sepol_handle_t *handle;
46	int numerr;
47} hierarchy_args_t;
48
49/*
50 * find_parent_(type|role|user)
51 *
52 * This function returns the parent datum of given XXX_datum_t
53 * object or NULL, if it doesn't exist.
54 *
55 * If the given datum has a valid bounds, this function merely
56 * returns the indicated object. Otherwise, it looks up the
57 * parent based on the based hierarchy.
58 */
59#define find_parent_template(prefix)				\
60int find_parent_##prefix(hierarchy_args_t *a,			\
61			 prefix##_datum_t *datum,		\
62			 prefix##_datum_t **parent)		\
63{								\
64	char *parent_name, *datum_name, *tmp;			\
65								\
66	if (datum->bounds)						\
67		*parent = a->p->prefix##_val_to_struct[datum->bounds - 1]; \
68	else {								\
69		datum_name = a->p->p_##prefix##_val_to_name[datum->s.value - 1]; \
70									\
71		tmp = strrchr(datum_name, '.');				\
72		/* no '.' means it has no parent */			\
73		if (!tmp) {						\
74			*parent = NULL;					\
75			return 0;					\
76		}							\
77									\
78		parent_name = strdup(datum_name);			\
79		if (!parent_name)					\
80			return -1;					\
81		parent_name[tmp - datum_name] = '\0';			\
82									\
83		*parent = hashtab_search(a->p->p_##prefix##s.table, parent_name); \
84		if (!*parent) {						\
85			/* Orphan type/role/user */			\
86			ERR(a->handle,					\
87			    "%s doesn't exist, %s is an orphan",	\
88			    parent_name,				\
89			    a->p->p_##prefix##_val_to_name[datum->s.value - 1]); \
90			free(parent_name);				\
91			return -1;					\
92		}							\
93		free(parent_name);					\
94	}								\
95									\
96	return 0;							\
97}
98
99static find_parent_template(type)
100static find_parent_template(role)
101static find_parent_template(user)
102
103static void compute_avtab_datum(hierarchy_args_t *args,
104				avtab_key_t *key,
105				avtab_datum_t *result)
106{
107	avtab_datum_t *avdatp;
108	uint32_t av = 0;
109
110	avdatp = avtab_search(args->expa, key);
111	if (avdatp)
112		av = avdatp->data;
113	if (args->opt_cond_list) {
114		avdatp = cond_av_list_search(key, args->opt_cond_list);
115		if (avdatp)
116			av |= avdatp->data;
117	}
118
119	result->data = av;
120}
121
122/* This function verifies that the type passed in either has a parent or is in the
123 * root of the namespace, 0 on success, 1 on orphan and -1 on error
124 */
125static int check_type_hierarchy_callback(hashtab_key_t k, hashtab_datum_t d,
126					 void *args)
127{
128	hierarchy_args_t *a;
129	type_datum_t *t, *tp;
130
131	a = (hierarchy_args_t *) args;
132	t = (type_datum_t *) d;
133
134	if (t->flavor == TYPE_ATTRIB) {
135		/* It's an attribute, we don't care */
136		return 0;
137	}
138	if (find_parent_type(a, t, &tp) < 0)
139		return -1;
140
141	if (tp && tp->flavor == TYPE_ATTRIB) {
142		/* The parent is an attribute but the child isn't, not legal */
143		ERR(a->handle, "type %s is a child of an attribute %s",
144		    (char *) k, a->p->p_type_val_to_name[tp->s.value - 1]);
145		a->numerr++;
146		return -1;
147	}
148	return 0;
149}
150
151/* This function only verifies that the avtab node passed in does not violate any
152 * hiearchy constraint via any relationship with other types in the avtab.
153 * it should be called using avtab_map, returns 0 on success, 1 on violation and
154 * -1 on error. opt_cond_list is an optional argument that tells this to check
155 * a conditional list for the relationship as well as the unconditional avtab
156 */
157static int check_avtab_hierarchy_callback(avtab_key_t * k, avtab_datum_t * d,
158					  void *args)
159{
160	avtab_key_t key;
161	hierarchy_args_t *a = (hierarchy_args_t *) args;
162	type_datum_t *s, *t1 = NULL, *t2 = NULL;
163	avtab_datum_t av;
164
165	if (!(k->specified & AVTAB_ALLOWED)) {
166		/* This is not an allow rule, no checking done */
167		return 0;
168	}
169
170	/* search for parent first */
171	s = a->p->type_val_to_struct[k->source_type - 1];
172	if (find_parent_type(a, s, &t1) < 0)
173		return -1;
174	if (t1) {
175		/*
176		 * search for access allowed between type 1's
177		 * parent and type 2.
178		 */
179		key.source_type = t1->s.value;
180		key.target_type = k->target_type;
181		key.target_class = k->target_class;
182		key.specified = AVTAB_ALLOWED;
183		compute_avtab_datum(a, &key, &av);
184
185		if ((av.data & d->data) == d->data)
186			return 0;
187	}
188
189	/* next we try type 1 and type 2's parent */
190	s = a->p->type_val_to_struct[k->target_type - 1];
191	if (find_parent_type(a, s, &t2) < 0)
192		return -1;
193	if (t2) {
194		/*
195		 * search for access allowed between type 1 and
196		 * type 2's parent.
197		 */
198		key.source_type = k->source_type;
199		key.target_type = t2->s.value;
200		key.target_class = k->target_class;
201		key.specified = AVTAB_ALLOWED;
202		compute_avtab_datum(a, &key, &av);
203
204		if ((av.data & d->data) == d->data)
205			return 0;
206	}
207
208	if (t1 && t2) {
209		/*
210                 * search for access allowed between type 1's parent
211                 * and type 2's parent.
212                 */
213		key.source_type = t1->s.value;
214		key.target_type = t2->s.value;
215		key.target_class = k->target_class;
216		key.specified = AVTAB_ALLOWED;
217		compute_avtab_datum(a, &key, &av);
218
219		if ((av.data & d->data) == d->data)
220			return 0;
221	}
222
223	/*
224	 * Neither one of these types have parents and
225	 * therefore the hierarchical constraint does not apply
226	 */
227	if (!t1 && !t2)
228		return 0;
229
230	/*
231	 * At this point there is a violation of the hierarchal
232	 * constraint, send error condition back
233	 */
234	ERR(a->handle,
235	    "hierarchy violation between types %s and %s : %s { %s }",
236	    a->p->p_type_val_to_name[k->source_type - 1],
237	    a->p->p_type_val_to_name[k->target_type - 1],
238	    a->p->p_class_val_to_name[k->target_class - 1],
239	    sepol_av_to_string(a->p, k->target_class, d->data & ~av.data));
240	a->numerr++;
241	return 0;
242}
243
244/*
245 * If same permissions are allowed for same combination of
246 * source and target, we can evaluate them as unconditional
247 * one.
248 * See the following example. A_t type is bounds of B_t type,
249 * so B_t can never have wider permissions then A_t.
250 * A_t has conditional permission on X_t, however, a part of
251 * them (getattr and read) are unconditionaly allowed to A_t.
252 *
253 * Example)
254 * typebounds A_t B_t;
255 *
256 * allow B_t X_t : file { getattr };
257 * if (foo_bool) {
258 *     allow A_t X_t : file { getattr read };
259 * } else {
260 *     allow A_t X_t : file { getattr read write };
261 * }
262 *
263 * We have to pull up them as unconditional ones in this case,
264 * because it seems to us B_t is violated to bounds constraints
265 * during unconditional policy checking.
266 */
267static int pullup_unconditional_perms(cond_list_t * cond_list,
268				      hierarchy_args_t * args)
269{
270	cond_list_t *cur_node;
271	cond_av_list_t *cur_av, *expl_true = NULL, *expl_false = NULL;
272	avtab_t expa_true, expa_false;
273	avtab_datum_t *avdatp;
274	avtab_datum_t avdat;
275	avtab_ptr_t avnode;
276
277	for (cur_node = cond_list; cur_node; cur_node = cur_node->next) {
278		if (avtab_init(&expa_true))
279			goto oom0;
280		if (avtab_init(&expa_false))
281			goto oom1;
282		if (expand_cond_av_list(args->p, cur_node->true_list,
283					&expl_true, &expa_true))
284			goto oom2;
285		if (expand_cond_av_list(args->p, cur_node->false_list,
286					&expl_false, &expa_false))
287			goto oom3;
288		for (cur_av = expl_true; cur_av; cur_av = cur_av->next) {
289			avdatp = avtab_search(&expa_false,
290					      &cur_av->node->key);
291			if (!avdatp)
292				continue;
293
294			avdat.data = (cur_av->node->datum.data
295				      & avdatp->data);
296			if (!avdat.data)
297				continue;
298
299			avnode = avtab_search_node(args->expa,
300						   &cur_av->node->key);
301			if (avnode) {
302				avnode->datum.data |= avdat.data;
303			} else {
304				if (avtab_insert(args->expa,
305						 &cur_av->node->key,
306						 &avdat))
307					goto oom4;
308			}
309		}
310		cond_av_list_destroy(expl_false);
311		cond_av_list_destroy(expl_true);
312		avtab_destroy(&expa_false);
313		avtab_destroy(&expa_true);
314	}
315	return 0;
316
317oom4:
318	cond_av_list_destroy(expl_false);
319oom3:
320	cond_av_list_destroy(expl_true);
321oom2:
322	avtab_destroy(&expa_false);
323oom1:
324	avtab_destroy(&expa_true);
325oom0:
326	ERR(args->handle, "out of memory on conditional av list expansion");
327        return 1;
328}
329
330static int check_cond_avtab_hierarchy(cond_list_t * cond_list,
331				      hierarchy_args_t * args)
332{
333	int rc;
334	cond_list_t *cur_node;
335	cond_av_list_t *cur_av, *expl = NULL;
336	avtab_t expa;
337	hierarchy_args_t *a = (hierarchy_args_t *) args;
338	avtab_datum_t avdat, *uncond;
339
340	for (cur_node = cond_list; cur_node; cur_node = cur_node->next) {
341		/*
342		 * Check true condition
343		 */
344		if (avtab_init(&expa))
345			goto oom;
346		if (expand_cond_av_list(args->p, cur_node->true_list,
347					&expl, &expa)) {
348			avtab_destroy(&expa);
349			goto oom;
350		}
351		args->opt_cond_list = expl;
352		for (cur_av = expl; cur_av; cur_av = cur_av->next) {
353			avdat.data = cur_av->node->datum.data;
354			uncond = avtab_search(a->expa, &cur_av->node->key);
355			if (uncond)
356				avdat.data |= uncond->data;
357			rc = check_avtab_hierarchy_callback(&cur_av->node->key,
358							    &avdat, args);
359			if (rc)
360				args->numerr++;
361		}
362		cond_av_list_destroy(expl);
363		avtab_destroy(&expa);
364
365		/*
366		 * Check false condition
367		 */
368		if (avtab_init(&expa))
369			goto oom;
370		if (expand_cond_av_list(args->p, cur_node->false_list,
371					&expl, &expa)) {
372			avtab_destroy(&expa);
373			goto oom;
374		}
375		args->opt_cond_list = expl;
376		for (cur_av = expl; cur_av; cur_av = cur_av->next) {
377			avdat.data = cur_av->node->datum.data;
378			uncond = avtab_search(a->expa, &cur_av->node->key);
379			if (uncond)
380				avdat.data |= uncond->data;
381
382			rc = check_avtab_hierarchy_callback(&cur_av->node->key,
383							    &avdat, args);
384			if (rc)
385				a->numerr++;
386		}
387		cond_av_list_destroy(expl);
388		avtab_destroy(&expa);
389	}
390
391	return 0;
392
393      oom:
394	ERR(args->handle, "out of memory on conditional av list expansion");
395	return 1;
396}
397
398/* The role hierarchy is defined as: a child role cannot have more types than it's parent.
399 * This function should be called with hashtab_map, it will return 0 on success, 1 on
400 * constraint violation and -1 on error
401 */
402static int check_role_hierarchy_callback(hashtab_key_t k
403					 __attribute__ ((unused)),
404					 hashtab_datum_t d, void *args)
405{
406	hierarchy_args_t *a;
407	role_datum_t *r, *rp;
408
409	a = (hierarchy_args_t *) args;
410	r = (role_datum_t *) d;
411
412	if (find_parent_role(a, r, &rp) < 0)
413		return -1;
414
415	if (rp && !ebitmap_contains(&rp->types.types, &r->types.types)) {
416		/* hierarchical constraint violation, return error */
417		ERR(a->handle, "Role hierarchy violation, %s exceeds %s",
418		    (char *) k, a->p->p_role_val_to_name[rp->s.value - 1]);
419		a->numerr++;
420	}
421	return 0;
422}
423
424/* The user hierarchy is defined as: a child user cannot have a role that
425 * its parent doesn't have.  This function should be called with hashtab_map,
426 * it will return 0 on success, 1 on constraint violation and -1 on error.
427 */
428static int check_user_hierarchy_callback(hashtab_key_t k
429					 __attribute__ ((unused)),
430					 hashtab_datum_t d, void *args)
431{
432	hierarchy_args_t *a;
433	user_datum_t *u, *up;
434
435	a = (hierarchy_args_t *) args;
436	u = (user_datum_t *) d;
437
438	if (find_parent_user(a, u, &up) < 0)
439		return -1;
440
441	if (up && !ebitmap_contains(&up->roles.roles, &u->roles.roles)) {
442		/* hierarchical constraint violation, return error */
443		ERR(a->handle, "User hierarchy violation, %s exceeds %s",
444		    (char *) k, a->p->p_user_val_to_name[up->s.value - 1]);
445		a->numerr++;
446	}
447	return 0;
448}
449
450int hierarchy_check_constraints(sepol_handle_t * handle, policydb_t * p)
451{
452	hierarchy_args_t args;
453	avtab_t expa;
454
455	if (avtab_init(&expa))
456		goto oom;
457	if (expand_avtab(p, &p->te_avtab, &expa)) {
458		avtab_destroy(&expa);
459		goto oom;
460	}
461
462	args.p = p;
463	args.expa = &expa;
464	args.opt_cond_list = NULL;
465	args.handle = handle;
466	args.numerr = 0;
467
468	if (hashtab_map(p->p_types.table, check_type_hierarchy_callback, &args))
469		goto bad;
470
471	if (pullup_unconditional_perms(p->cond_list, &args))
472		return -1;
473
474	if (avtab_map(&expa, check_avtab_hierarchy_callback, &args))
475		goto bad;
476
477	if (check_cond_avtab_hierarchy(p->cond_list, &args))
478		goto bad;
479
480	if (hashtab_map(p->p_roles.table, check_role_hierarchy_callback, &args))
481		goto bad;
482
483	if (hashtab_map(p->p_users.table, check_user_hierarchy_callback, &args))
484		goto bad;
485
486	if (args.numerr) {
487		ERR(handle, "%d total errors found during hierarchy check",
488		    args.numerr);
489		goto bad;
490	}
491
492	avtab_destroy(&expa);
493	return 0;
494
495      bad:
496	avtab_destroy(&expa);
497	return -1;
498
499      oom:
500	ERR(handle, "Out of memory");
501	return -1;
502}
503