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
39struct cil_args_find {
40	enum cil_flavor flavor;
41	void *target;
42	struct cil_list *matching;
43	int match_self;
44};
45
46static 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
82static 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_type *t1 = (struct cil_type *)d1;
90		struct cil_type *t2 = (struct cil_type *)d2;
91		if (t1->value == t2->value) {
92			ebitmap_set_bit(matches, t1->value, 1);
93		}
94	} else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
95		struct cil_typeattribute *a = (struct cil_typeattribute *)d1;
96		struct cil_type *t = (struct cil_type *)d2;
97		if (ebitmap_get_bit(a->types, t->value)) {
98			ebitmap_set_bit(matches, t->value, 1);
99		}
100	} else if (f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
101		struct cil_type *t = (struct cil_type *)d1;
102		struct cil_typeattribute *a = (struct cil_typeattribute *)d2;
103		if (ebitmap_get_bit(a->types, t->value)) {
104			ebitmap_set_bit(matches, t->value, 1);
105		}
106	} else {
107		/* Both are attributes */
108		struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
109		struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
110		rc = ebitmap_and(matches, a1->types, a2->types);
111	}
112
113	return rc;
114}
115
116/* s1 is the src type that is matched with a self
117 * s2, and t2 are the source and type of the other rule
118 */
119static int cil_self_match_any(struct cil_symtab_datum *s1, struct cil_symtab_datum *s2, struct cil_symtab_datum *t2)
120{
121	int rc;
122	struct cil_tree_node *n1 = NODE(s1);
123	if (n1->flavor != CIL_TYPEATTRIBUTE) {
124		rc = cil_type_match_any(s1, t2);
125	} else {
126		struct cil_typeattribute *a = (struct cil_typeattribute *)s1;
127		ebitmap_t map;
128		ebitmap_init(&map);
129		rc = cil_type_matches(&map, s2, t2);
130		if (rc < 0) {
131			ebitmap_destroy(&map);
132			goto exit;
133		}
134		if (map.node == NULL) {
135			rc = CIL_FALSE;
136			goto exit;
137		}
138		rc = ebitmap_match_any(&map, a->types);
139		ebitmap_destroy(&map);
140	}
141
142exit:
143	return rc;
144}
145
146static int cil_classperms_match_any(struct cil_classperms *cp1, struct cil_classperms *cp2)
147{
148	struct cil_class *c1 = cp1->class;
149	struct cil_class *c2 = cp2->class;
150	struct cil_list_item *i1, *i2;
151
152	if (&c1->datum != &c2->datum) return CIL_FALSE;
153
154	cil_list_for_each(i1, cp1->perms) {
155		struct cil_perm *p1 = i1->data;
156		cil_list_for_each(i2, cp2->perms) {
157			struct cil_perm *p2 = i2->data;
158			if (&p1->datum == &p2->datum) return CIL_TRUE;
159		}
160	}
161	return CIL_FALSE;
162}
163
164static int __cil_classperms_list_match_any(struct cil_classperms *cp1, struct cil_list *cpl2)
165{
166	int rc;
167	struct cil_list_item *curr;
168
169	cil_list_for_each(curr, cpl2) {
170		if (curr->flavor == CIL_CLASSPERMS) {
171			struct cil_classperms *cp = curr->data;
172			if (FLAVOR(cp->class) == CIL_CLASS) {
173				rc = cil_classperms_match_any(cp1, cp);
174				if (rc == CIL_TRUE) return CIL_TRUE;
175			} else { /* MAP */
176				struct cil_list_item *i = NULL;
177				cil_list_for_each(i, cp->perms) {
178					struct cil_perm *cmp = i->data;
179					rc = __cil_classperms_list_match_any(cp1, cmp->classperms);
180					if (rc == CIL_TRUE) return CIL_TRUE;
181				}
182			}
183		} else { /* SET */
184			struct cil_classperms_set *cp_set = curr->data;
185			struct cil_classpermission *cp = cp_set->set;
186			rc = __cil_classperms_list_match_any(cp1, cp->classperms);
187			if (rc == CIL_TRUE) return CIL_TRUE;
188		}
189	}
190	return CIL_FALSE;
191}
192
193static int cil_classperms_list_match_any(struct cil_list *cpl1, struct cil_list *cpl2)
194{
195	int rc;
196	struct cil_list_item *curr;
197
198	cil_list_for_each(curr, cpl1) {
199		if (curr->flavor == CIL_CLASSPERMS) {
200			struct cil_classperms *cp = curr->data;
201			if (FLAVOR(cp->class) == CIL_CLASS) {
202				rc = __cil_classperms_list_match_any(cp, cpl2);
203				if (rc == CIL_TRUE) return CIL_TRUE;
204			} else { /* MAP */
205				struct cil_list_item *i = NULL;
206				cil_list_for_each(i, cp->perms) {
207					struct cil_perm *cmp = i->data;
208					rc = cil_classperms_list_match_any(cmp->classperms, cpl2);
209					if (rc == CIL_TRUE) return CIL_TRUE;
210				}
211			}
212		} else { /* SET */
213			struct cil_classperms_set *cp_set = curr->data;
214			struct cil_classpermission *cp = cp_set->set;
215			rc = cil_classperms_list_match_any(cp->classperms, cpl2);
216			if (rc == CIL_TRUE) return CIL_TRUE;
217		}
218	}
219	return CIL_FALSE;
220}
221
222static void __add_classes_from_classperms_list(struct cil_list *classperms, struct cil_list *class_list)
223{
224	struct cil_list_item *curr;
225
226	cil_list_for_each(curr, classperms) {
227		if (curr->flavor == CIL_CLASSPERMS) {
228			struct cil_classperms *cp = curr->data;
229			if (FLAVOR(cp->class) == CIL_CLASS) {
230				cil_list_append(class_list, CIL_CLASS, cp->class);
231			} else { /* MAP */
232				struct cil_list_item *i = NULL;
233				cil_list_for_each(i, cp->perms) {
234					struct cil_perm *cmp = i->data;
235					__add_classes_from_classperms_list(cmp->classperms, class_list);
236				}
237			}
238		} else { /* SET */
239			struct cil_classperms_set *cp_set = curr->data;
240			struct cil_classpermission *cp = cp_set->set;
241			__add_classes_from_classperms_list(cp->classperms, class_list);
242		}
243	}
244}
245
246static int __add_classes_from_map_perms(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, void *args)
247{
248	struct cil_list *class_list = args;
249	struct cil_perm *cmp = (struct cil_perm *)d;
250
251	__add_classes_from_classperms_list(cmp->classperms, class_list);
252
253	return SEPOL_OK;
254}
255
256struct cil_list *cil_expand_class(struct cil_class *class)
257{
258	struct cil_list *class_list;
259
260	cil_list_init(&class_list, CIL_CLASS);
261
262	if (FLAVOR(class) == CIL_CLASS) {
263		cil_list_append(class_list, CIL_CLASS, class);
264	} else { /* MAP */
265		cil_symtab_map(&class->perms, __add_classes_from_map_perms, class_list);
266	}
267
268	return class_list;
269}
270
271static int cil_permissionx_match_any(struct cil_permissionx *px1, struct cil_permissionx *px2)
272{
273	int rc = CIL_FALSE;
274	struct cil_list *cl1 = NULL;
275	struct cil_list *cl2 = NULL;
276
277	if (px1->kind != px2->kind) goto exit;
278
279	if (!ebitmap_match_any(px1->perms, px2->perms)) goto exit;
280
281	cl1 = cil_expand_class(px1->obj);
282	cl2 = cil_expand_class(px2->obj);
283
284	if (!cil_list_match_any(cl1, cl2)) goto exit;
285
286	rc = CIL_TRUE;
287
288exit:
289	cil_list_destroy(&cl1, CIL_FALSE);
290	cil_list_destroy(&cl2, CIL_FALSE);
291
292	return rc;
293}
294
295static 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)
296{
297	int rc = SEPOL_OK;
298	struct cil_symtab_datum *s1 = avrule->src;
299	struct cil_symtab_datum *t1 = avrule->tgt;
300	struct cil_symtab_datum *s2 = target->src;
301	struct cil_symtab_datum *t2 = target->tgt;
302
303	if (match_self != CIL_TRUE && avrule == target) goto exit;
304
305	if (avrule->rule_kind != target->rule_kind) goto exit;
306
307	if (avrule->is_extended != target->is_extended) goto exit;
308
309	if (!cil_type_match_any(s1, s2)) goto exit;
310
311	if (t1->fqn != CIL_KEY_SELF && t2->fqn != CIL_KEY_SELF) {
312		if (!cil_type_match_any(t1, t2)) goto exit;
313	} else {
314		if (t1->fqn == CIL_KEY_SELF && t2->fqn == CIL_KEY_SELF) {
315			/* The earlier check whether s1 and s2 matches is all that is needed */
316		} else if (t1->fqn == CIL_KEY_SELF) {
317			rc = cil_self_match_any(s1, s2, t2);
318			if (rc < 0) {
319				goto exit;
320			} else if (rc == CIL_FALSE) {
321				rc = SEPOL_OK;
322				goto exit;
323			}
324		} else if (t2->fqn == CIL_KEY_SELF) {
325			rc = cil_self_match_any(s2, s1, t1);
326			if (rc < 0) {
327				goto exit;
328			} else if (rc == CIL_FALSE) {
329				rc = SEPOL_OK;
330				goto exit;
331			}
332		}
333	}
334
335	if (!target->is_extended) {
336		if (cil_classperms_list_match_any(avrule->perms.classperms, target->perms.classperms)) {
337			cil_list_append(matching, CIL_NODE, node);
338		}
339	} else {
340		if (cil_permissionx_match_any(avrule->perms.x.permx, target->perms.x.permx)) {
341			cil_list_append(matching, CIL_NODE, node);
342		}
343	}
344
345	rc = SEPOL_OK;
346
347exit:
348	return rc;
349}
350
351static int __cil_find_matching_avrule_in_ast(struct cil_tree_node *node, uint32_t *finished, void *extra_args)
352{
353	int rc = SEPOL_OK;
354	struct cil_args_find *args = extra_args;
355
356	if (node->flavor == CIL_BLOCK) {
357		struct cil_block *blk = node->data;
358		if (blk->is_abstract == CIL_TRUE) {
359			*finished = CIL_TREE_SKIP_HEAD;
360			goto exit;
361		}
362	} else if (node->flavor == CIL_MACRO) {
363		*finished = CIL_TREE_SKIP_HEAD;
364		goto exit;
365	} else if (node->flavor == CIL_AVRULE || node->flavor == CIL_AVRULEX) {
366		if (node->flavor == args->flavor) {
367			rc = cil_find_matching_avrule(node, node->data, args->target, args->matching, args->match_self);
368		}
369	}
370
371exit:
372	return rc;
373}
374
375int cil_find_matching_avrule_in_ast(struct cil_tree_node *current, enum cil_flavor flavor, void *target, struct cil_list *matching, int match_self)
376{
377	int rc;
378	struct cil_args_find args;
379
380	args.flavor = flavor;
381	args.target = target;
382	args.matching = matching;
383	args.match_self = match_self;
384
385	rc = cil_tree_walk(current, __cil_find_matching_avrule_in_ast, NULL, NULL, &args);
386	if (rc) {
387		cil_log(CIL_ERR, "An error occurred while searching for avrule in AST\n");
388	}
389
390	return rc;
391}
392