1 /*
2 * Copyright 2011 Tresys Technology, LLC. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * 1. Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 *
10 * 2. Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY TRESYS TECHNOLOGY, LLC ``AS IS'' AND ANY EXPRESS
15 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
17 * EVENT SHALL TRESYS TECHNOLOGY, LLC OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
19 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
21 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
22 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
23 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 * The views and conclusions contained in the software and documentation are those
26 * of the authors and should not be interpreted as representing official policies,
27 * either expressed or implied, of Tresys Technology, LLC.
28 */
29
30 #include <sepol/policydb/ebitmap.h>
31
32 #include "cil_internal.h"
33 #include "cil_find.h"
34 #include "cil_flavor.h"
35 #include "cil_list.h"
36 #include "cil_log.h"
37 #include "cil_symtab.h"
38
39 struct cil_args_find {
40 enum cil_flavor flavor;
41 void *target;
42 struct cil_list *matching;
43 int match_self;
44 };
45
cil_type_match_any(struct cil_symtab_datum * d1,struct cil_symtab_datum * d2)46 static int cil_type_match_any(struct cil_symtab_datum *d1, struct cil_symtab_datum *d2)
47 {
48 enum cil_flavor f1 = FLAVOR(d1);
49 enum cil_flavor f2 = FLAVOR(d2);
50
51 if (f1 != CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
52 struct cil_type *t1 = (struct cil_type *)d1;
53 struct cil_type *t2 = (struct cil_type *)d2;
54 if (t1->value == t2->value) {
55 return CIL_TRUE;
56 }
57 } else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
58 struct cil_typeattribute *a = (struct cil_typeattribute *)d1;
59 struct cil_type *t = (struct cil_type *)d2;
60 if (ebitmap_get_bit(a->types, t->value)) {
61 return CIL_TRUE;
62 }
63 } else if (f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
64 struct cil_type *t = (struct cil_type *)d1;
65 struct cil_typeattribute *a = (struct cil_typeattribute *)d2;
66 if (ebitmap_get_bit(a->types, t->value)) {
67 return CIL_TRUE;
68 }
69 } else {
70 /* Both are attributes */
71 struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
72 struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
73 if (d1 == d2) {
74 return CIL_TRUE;
75 } else if (ebitmap_match_any(a1->types, a2->types)) {
76 return CIL_TRUE;
77 }
78 }
79 return CIL_FALSE;
80 }
81
cil_type_matches(ebitmap_t * matches,struct cil_symtab_datum * d1,struct cil_symtab_datum * d2)82 static int cil_type_matches(ebitmap_t *matches, struct cil_symtab_datum *d1, struct cil_symtab_datum *d2)
83 {
84 int rc = SEPOL_OK;
85 enum cil_flavor f1 = FLAVOR(d1);
86 enum cil_flavor f2 = FLAVOR(d2);
87
88 if (f1 == CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
89 struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
90 struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
91 rc = ebitmap_and(matches, a1->types, a2->types);
92 } else {
93 ebitmap_init(matches);
94 if (f1 != CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
95 struct cil_type *t1 = (struct cil_type *)d1;
96 struct cil_type *t2 = (struct cil_type *)d2;
97 if (t1->value == t2->value) {
98 rc = ebitmap_set_bit(matches, t1->value, 1);
99 }
100 } else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
101 struct cil_typeattribute *a = (struct cil_typeattribute *)d1;
102 struct cil_type *t = (struct cil_type *)d2;
103 if (ebitmap_get_bit(a->types, t->value)) {
104 rc = ebitmap_set_bit(matches, t->value, 1);
105 }
106 } else { // f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE
107 struct cil_type *t = (struct cil_type *)d1;
108 struct cil_typeattribute *a = (struct cil_typeattribute *)d2;
109 if (ebitmap_get_bit(a->types, t->value)) {
110 rc = ebitmap_set_bit(matches, t->value, 1);
111 }
112 }
113 if (rc != SEPOL_OK) {
114 ebitmap_destroy(matches);
115 }
116 }
117
118 return rc;
119 }
120
121 /* s1 is the src type that is matched with a self
122 * s2, and t2 are the source and type of the other rule
123 * Assumes there is a match between s1 and s2
124 */
cil_self_match_any(struct cil_symtab_datum * s1,struct cil_symtab_datum * s2,struct cil_symtab_datum * t2)125 static int cil_self_match_any(struct cil_symtab_datum *s1, struct cil_symtab_datum *s2, struct cil_symtab_datum *t2)
126 {
127 int rc;
128
129 if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
130 rc = cil_type_match_any(s1, t2);
131 } else {
132 struct cil_typeattribute *a = (struct cil_typeattribute *)s1;
133 ebitmap_t map;
134 rc = cil_type_matches(&map, s2, t2);
135 if (rc < 0) {
136 return rc;
137 }
138 if (ebitmap_is_empty(&map)) {
139 return CIL_FALSE;
140 }
141 rc = ebitmap_match_any(&map, a->types);
142 ebitmap_destroy(&map);
143 }
144
145 return rc;
146 }
147
148 /* s1 is the src type that is matched with a notself
149 * s2 and t2 are the source and type of the other rule
150 * Assumes there is a match between s1 and s2
151 */
cil_notself_match_any(struct cil_symtab_datum * s1,struct cil_symtab_datum * s2,struct cil_symtab_datum * t2)152 static int cil_notself_match_any(struct cil_symtab_datum *s1, struct cil_symtab_datum *s2, struct cil_symtab_datum *t2)
153 {
154 int rc;
155 ebitmap_node_t *snode, *tnode;
156 unsigned int s,t;
157
158 if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
159 struct cil_type *ts1 = (struct cil_type *)s1;
160 if (FLAVOR(t2) != CIL_TYPEATTRIBUTE) {
161 struct cil_type *tt2 = (struct cil_type *)t2;
162 if (ts1->value != tt2->value) {
163 return CIL_TRUE;
164 }
165 } else {
166 struct cil_typeattribute *at2 = (struct cil_typeattribute *)t2;
167 ebitmap_for_each_positive_bit(at2->types, tnode, t) {
168 if (t != (unsigned int)ts1->value) {
169 return CIL_TRUE;
170 }
171 }
172 }
173 } else {
174 ebitmap_t smap;
175 rc = cil_type_matches(&smap, s1, s2);
176 if (rc < 0) {
177 return rc;
178 }
179 if (ebitmap_is_empty(&smap)) {
180 return CIL_FALSE;
181 }
182 if (FLAVOR(t2) != CIL_TYPEATTRIBUTE) {
183 struct cil_type *tt2 = (struct cil_type *)t2;
184 ebitmap_for_each_positive_bit(&smap, snode, s) {
185 if (s != (unsigned int)tt2->value) {
186 ebitmap_destroy(&smap);
187 return CIL_TRUE;
188 }
189 }
190 } else {
191 struct cil_typeattribute *at2 = (struct cil_typeattribute *)t2;
192 ebitmap_for_each_positive_bit(&smap, snode, s) {
193 ebitmap_for_each_positive_bit(at2->types, tnode, t) {
194 if (s != t) {
195 ebitmap_destroy(&smap);
196 return CIL_TRUE;
197 }
198 }
199 }
200 }
201 ebitmap_destroy(&smap);
202 }
203
204 return CIL_FALSE;
205 }
206
207 /* s1 is the src type that is matched with an other
208 * s2, and t2 are the source and type of the other rule
209 * Assumes there is a match between s1 and s2
210 */
cil_other_match_any(struct cil_symtab_datum * s1,struct cil_symtab_datum * s2,struct cil_symtab_datum * t2)211 static int cil_other_match_any(struct cil_symtab_datum *s1, struct cil_symtab_datum *s2, struct cil_symtab_datum *t2)
212 {
213 int rc;
214 ebitmap_t smap, tmap;
215 ebitmap_node_t *snode, *tnode;
216 unsigned int s,t;
217
218 if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
219 return CIL_FALSE;
220 }
221
222 rc = cil_type_matches(&smap, s1, s2);
223 if (rc < 0) {
224 return rc;
225 }
226
227 if (ebitmap_is_empty(&smap)) {
228 return CIL_FALSE;
229 }
230
231 rc = cil_type_matches(&tmap, s1, t2);
232 if (rc < 0) {
233 ebitmap_destroy(&smap);
234 return rc;
235 }
236
237 if (ebitmap_is_empty(&tmap)) {
238 ebitmap_destroy(&smap);
239 return CIL_FALSE;
240 }
241
242 ebitmap_for_each_positive_bit(&smap, snode, s) {
243 ebitmap_for_each_positive_bit(&tmap, tnode, t) {
244 if (s != t) {
245 rc = CIL_TRUE;
246 goto exit;
247 }
248 }
249 }
250
251 rc = CIL_FALSE;
252
253 exit:
254 ebitmap_destroy(&smap);
255 ebitmap_destroy(&tmap);
256 return rc;
257 }
258
259 /* s2 is the src type that is matched with an other
260 * Assumes there is a match between s1 and s2
261 * s1 is not needed, since it is known that there is a match
262 */
cil_notself_other_match_any(struct cil_symtab_datum * s2)263 static int cil_notself_other_match_any(struct cil_symtab_datum *s2)
264 {
265 if (FLAVOR(s2) == CIL_TYPEATTRIBUTE) {
266 struct cil_typeattribute *as2 = (struct cil_typeattribute *)s2;
267 if (ebitmap_cardinality(as2->types) > 1) {
268 return CIL_TRUE;
269 }
270 }
271 return CIL_FALSE;
272 }
273
cil_classperms_match_any(struct cil_classperms * cp1,struct cil_classperms * cp2)274 static int cil_classperms_match_any(struct cil_classperms *cp1, struct cil_classperms *cp2)
275 {
276 struct cil_class *c1 = cp1->class;
277 struct cil_class *c2 = cp2->class;
278 struct cil_list_item *i1, *i2;
279
280 if (&c1->datum != &c2->datum) return CIL_FALSE;
281
282 cil_list_for_each(i1, cp1->perms) {
283 struct cil_perm *p1 = i1->data;
284 cil_list_for_each(i2, cp2->perms) {
285 struct cil_perm *p2 = i2->data;
286 if (&p1->datum == &p2->datum) return CIL_TRUE;
287 }
288 }
289 return CIL_FALSE;
290 }
291
__cil_classperms_list_match_any(struct cil_classperms * cp1,struct cil_list * cpl2)292 static int __cil_classperms_list_match_any(struct cil_classperms *cp1, struct cil_list *cpl2)
293 {
294 int rc;
295 struct cil_list_item *curr;
296
297 cil_list_for_each(curr, cpl2) {
298 if (curr->flavor == CIL_CLASSPERMS) {
299 struct cil_classperms *cp = curr->data;
300 if (FLAVOR(cp->class) == CIL_CLASS) {
301 rc = cil_classperms_match_any(cp1, cp);
302 if (rc == CIL_TRUE) return CIL_TRUE;
303 } else { /* MAP */
304 struct cil_list_item *i = NULL;
305 cil_list_for_each(i, cp->perms) {
306 struct cil_perm *cmp = i->data;
307 rc = __cil_classperms_list_match_any(cp1, cmp->classperms);
308 if (rc == CIL_TRUE) return CIL_TRUE;
309 }
310 }
311 } else { /* SET */
312 struct cil_classperms_set *cp_set = curr->data;
313 struct cil_classpermission *cp = cp_set->set;
314 rc = __cil_classperms_list_match_any(cp1, cp->classperms);
315 if (rc == CIL_TRUE) return CIL_TRUE;
316 }
317 }
318 return CIL_FALSE;
319 }
320
cil_classperms_list_match_any(struct cil_list * cpl1,struct cil_list * cpl2)321 static int cil_classperms_list_match_any(struct cil_list *cpl1, struct cil_list *cpl2)
322 {
323 int rc;
324 struct cil_list_item *curr;
325
326 cil_list_for_each(curr, cpl1) {
327 if (curr->flavor == CIL_CLASSPERMS) {
328 struct cil_classperms *cp = curr->data;
329 if (FLAVOR(cp->class) == CIL_CLASS) {
330 rc = __cil_classperms_list_match_any(cp, cpl2);
331 if (rc == CIL_TRUE) return CIL_TRUE;
332 } else { /* MAP */
333 struct cil_list_item *i = NULL;
334 cil_list_for_each(i, cp->perms) {
335 struct cil_perm *cmp = i->data;
336 rc = cil_classperms_list_match_any(cmp->classperms, cpl2);
337 if (rc == CIL_TRUE) return CIL_TRUE;
338 }
339 }
340 } else { /* SET */
341 struct cil_classperms_set *cp_set = curr->data;
342 struct cil_classpermission *cp = cp_set->set;
343 rc = cil_classperms_list_match_any(cp->classperms, cpl2);
344 if (rc == CIL_TRUE) return CIL_TRUE;
345 }
346 }
347 return CIL_FALSE;
348 }
349
__add_classes_from_classperms_list(struct cil_list * classperms,struct cil_list * class_list)350 static void __add_classes_from_classperms_list(struct cil_list *classperms, struct cil_list *class_list)
351 {
352 struct cil_list_item *curr;
353
354 cil_list_for_each(curr, classperms) {
355 if (curr->flavor == CIL_CLASSPERMS) {
356 struct cil_classperms *cp = curr->data;
357 if (FLAVOR(cp->class) == CIL_CLASS) {
358 cil_list_append(class_list, CIL_CLASS, cp->class);
359 } else { /* MAP */
360 struct cil_list_item *i = NULL;
361 cil_list_for_each(i, cp->perms) {
362 struct cil_perm *cmp = i->data;
363 __add_classes_from_classperms_list(cmp->classperms, class_list);
364 }
365 }
366 } else { /* SET */
367 struct cil_classperms_set *cp_set = curr->data;
368 struct cil_classpermission *cp = cp_set->set;
369 __add_classes_from_classperms_list(cp->classperms, class_list);
370 }
371 }
372 }
373
__add_classes_from_map_perms(hashtab_key_t k,hashtab_datum_t d,void * args)374 static int __add_classes_from_map_perms(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, void *args)
375 {
376 struct cil_list *class_list = args;
377 struct cil_perm *cmp = (struct cil_perm *)d;
378
379 __add_classes_from_classperms_list(cmp->classperms, class_list);
380
381 return SEPOL_OK;
382 }
383
cil_expand_class(struct cil_class * class)384 struct cil_list *cil_expand_class(struct cil_class *class)
385 {
386 struct cil_list *class_list;
387
388 cil_list_init(&class_list, CIL_CLASS);
389
390 if (FLAVOR(class) == CIL_CLASS) {
391 cil_list_append(class_list, CIL_CLASS, class);
392 } else { /* MAP */
393 cil_symtab_map(&class->perms, __add_classes_from_map_perms, class_list);
394 }
395
396 return class_list;
397 }
398
cil_permissionx_match_any(struct cil_permissionx * px1,struct cil_permissionx * px2)399 static int cil_permissionx_match_any(struct cil_permissionx *px1, struct cil_permissionx *px2)
400 {
401 int rc = CIL_FALSE;
402 struct cil_list *cl1 = NULL;
403 struct cil_list *cl2 = NULL;
404
405 if (px1->kind != px2->kind) goto exit;
406
407 if (!ebitmap_match_any(px1->perms, px2->perms)) goto exit;
408
409 cl1 = cil_expand_class(px1->obj);
410 cl2 = cil_expand_class(px2->obj);
411
412 if (!cil_list_match_any(cl1, cl2)) goto exit;
413
414 rc = CIL_TRUE;
415
416 exit:
417 cil_list_destroy(&cl1, CIL_FALSE);
418 cil_list_destroy(&cl2, CIL_FALSE);
419
420 return rc;
421 }
422
cil_find_matching_avrule(struct cil_tree_node * node,struct cil_avrule * avrule,struct cil_avrule * target,struct cil_list * matching,int match_self)423 static int cil_find_matching_avrule(struct cil_tree_node *node, struct cil_avrule *avrule, struct cil_avrule *target, struct cil_list *matching, int match_self)
424 {
425 int rc = SEPOL_OK;
426 struct cil_symtab_datum *s1 = avrule->src;
427 struct cil_symtab_datum *t1 = avrule->tgt;
428 struct cil_symtab_datum *s2 = target->src;
429 struct cil_symtab_datum *t2 = target->tgt;
430
431 if (match_self != CIL_TRUE && avrule == target) goto exit;
432
433 if (avrule->rule_kind != target->rule_kind) goto exit;
434
435 if (avrule->is_extended != target->is_extended) goto exit;
436
437 if (!cil_type_match_any(s1, s2)) goto exit;
438
439 if (t1->fqn == CIL_KEY_SELF) {
440 if (t2->fqn == CIL_KEY_SELF) {
441 /* The earlier check whether s1 and s2 matches is all that is needed */
442 rc = CIL_TRUE;
443 } else if (t2->fqn == CIL_KEY_NOTSELF || t2->fqn == CIL_KEY_OTHER) {
444 rc = CIL_FALSE;
445 } else {
446 rc = cil_self_match_any(s1, s2, t2);
447 }
448 } else if (t1->fqn == CIL_KEY_NOTSELF) {
449 if (t2->fqn == CIL_KEY_SELF) {
450 rc = CIL_FALSE;
451 } else if (t2->fqn == CIL_KEY_NOTSELF) {
452 /* The earlier check whether s1 and s2 matches is all that is needed */
453 rc = CIL_TRUE;
454 } else if (t2->fqn == CIL_KEY_OTHER) {
455 rc = cil_notself_other_match_any(s2);
456 } else {
457 rc = cil_notself_match_any(s1, s2, t2);
458 }
459 } else if (t1->fqn == CIL_KEY_OTHER) {
460 if (t2->fqn == CIL_KEY_SELF) {
461 rc = CIL_FALSE;
462 } else if (t2->fqn == CIL_KEY_NOTSELF) {
463 rc = cil_notself_other_match_any(s1);
464 } else if (t2->fqn == CIL_KEY_OTHER) {
465 /* The earlier check whether s1 and s2 matches is all that is needed */
466 rc = CIL_TRUE;
467 } else {
468 rc = cil_other_match_any(s1, s2, t2);
469 }
470 } else {
471 if (t2->fqn == CIL_KEY_SELF) {
472 rc = cil_self_match_any(s2, s1, t1);
473 } else if (t2->fqn == CIL_KEY_NOTSELF) {
474 rc = cil_notself_match_any(s2, s1, t1);
475 } else if (t2->fqn == CIL_KEY_OTHER) {
476 rc = cil_other_match_any(s2, s1, t1);
477 } else {
478 rc = cil_type_match_any(t1, t2);
479 }
480 }
481
482 if (rc < 0) {
483 goto exit;
484 } else if (rc == CIL_FALSE) {
485 rc = SEPOL_OK;
486 goto exit;
487 }
488
489 if (!target->is_extended) {
490 if (cil_classperms_list_match_any(avrule->perms.classperms, target->perms.classperms)) {
491 cil_list_append(matching, CIL_NODE, node);
492 }
493 } else {
494 if (cil_permissionx_match_any(avrule->perms.x.permx, target->perms.x.permx)) {
495 cil_list_append(matching, CIL_NODE, node);
496 }
497 }
498
499 rc = SEPOL_OK;
500
501 exit:
502 return rc;
503 }
504
__cil_find_matching_avrule_in_ast(struct cil_tree_node * node,uint32_t * finished,void * extra_args)505 static int __cil_find_matching_avrule_in_ast(struct cil_tree_node *node, uint32_t *finished, void *extra_args)
506 {
507 int rc = SEPOL_OK;
508 struct cil_args_find *args = extra_args;
509
510 if (node->flavor == CIL_BLOCK) {
511 struct cil_block *blk = node->data;
512 if (blk->is_abstract == CIL_TRUE) {
513 *finished = CIL_TREE_SKIP_HEAD;
514 goto exit;
515 }
516 } else if (node->flavor == CIL_MACRO) {
517 *finished = CIL_TREE_SKIP_HEAD;
518 goto exit;
519 } else if (node->flavor == CIL_AVRULE || node->flavor == CIL_AVRULEX) {
520 if (node->flavor == args->flavor) {
521 rc = cil_find_matching_avrule(node, node->data, args->target, args->matching, args->match_self);
522 }
523 }
524
525 exit:
526 return rc;
527 }
528
cil_find_matching_avrule_in_ast(struct cil_tree_node * current,enum cil_flavor flavor,void * target,struct cil_list * matching,int match_self)529 int cil_find_matching_avrule_in_ast(struct cil_tree_node *current, enum cil_flavor flavor, void *target, struct cil_list *matching, int match_self)
530 {
531 int rc;
532 struct cil_args_find args;
533
534 args.flavor = flavor;
535 args.target = target;
536 args.matching = matching;
537 args.match_self = match_self;
538
539 rc = cil_tree_walk(current, __cil_find_matching_avrule_in_ast, NULL, NULL, &args);
540 if (rc) {
541 cil_log(CIL_ERR, "An error occurred while searching for avrule in AST\n");
542 }
543
544 return rc;
545 }
546