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
40 typedef 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) \
60 int 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
99 static find_parent_template(type)
find_parent_template(role)100 static find_parent_template(role)
101 static find_parent_template(user)
102
103 static 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 */
check_type_hierarchy_callback(hashtab_key_t k,hashtab_datum_t d,void * args)125 static 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 */
check_avtab_hierarchy_callback(avtab_key_t * k,avtab_datum_t * d,void * args)157 static 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 */
pullup_unconditional_perms(cond_list_t * cond_list,hierarchy_args_t * args)267 static 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
317 oom4:
318 cond_av_list_destroy(expl_false);
319 oom3:
320 cond_av_list_destroy(expl_true);
321 oom2:
322 avtab_destroy(&expa_false);
323 oom1:
324 avtab_destroy(&expa_true);
325 oom0:
326 ERR(args->handle, "out of memory on conditional av list expansion");
327 return 1;
328 }
329
check_cond_avtab_hierarchy(cond_list_t * cond_list,hierarchy_args_t * args)330 static 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 */
check_role_hierarchy_callback(hashtab_key_t k,hashtab_datum_t d,void * args)402 static 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 */
check_user_hierarchy_callback(hashtab_key_t k,hashtab_datum_t d,void * args)428 static 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
hierarchy_check_constraints(sepol_handle_t * handle,policydb_t * p)450 int 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