1 /*
2 * Author: Ondrej Mosnacek <[email protected]>
3 *
4 * Copyright (C) 2019 Red Hat Inc.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 /*
22 * Binary policy optimization.
23 *
24 * Defines the policydb_optimize() function, which finds and removes
25 * redundant rules from the binary policy to reduce its size and potentially
26 * improve rule matching times. Only rules that are already covered by a
27 * more general rule are removed. The resulting policy is functionally
28 * equivalent to the original one.
29 */
30
31 #include <sepol/policydb/policydb.h>
32 #include <sepol/policydb/conditional.h>
33
34 #include "debug.h"
35 #include "private.h"
36
37 #define TYPE_VEC_INIT_SIZE 16
38
39 struct type_vec {
40 uint32_t *types;
41 unsigned int count, capacity;
42 };
43
type_vec_init(struct type_vec * v)44 static int type_vec_init(struct type_vec *v)
45 {
46 v->capacity = TYPE_VEC_INIT_SIZE;
47 v->count = 0;
48 v->types = calloc(v->capacity, sizeof(*v->types));
49 if (!v->types)
50 return -1;
51 return 0;
52 }
53
type_vec_destroy(struct type_vec * v)54 static void type_vec_destroy(struct type_vec *v)
55 {
56 free(v->types);
57 }
58
type_vec_append(struct type_vec * v,uint32_t type)59 static int type_vec_append(struct type_vec *v, uint32_t type)
60 {
61 if (v->capacity == v->count) {
62 unsigned int new_capacity = v->capacity * 2;
63 uint32_t *new_types = reallocarray(v->types,
64 new_capacity,
65 sizeof(*v->types));
66 if (!new_types)
67 return -1;
68
69 v->types = new_types;
70 v->capacity = new_capacity;
71 }
72
73 v->types[v->count++] = type;
74 return 0;
75 }
76
type_vec_contains(const struct type_vec * v,uint32_t type)77 static int type_vec_contains(const struct type_vec *v, uint32_t type)
78 {
79 unsigned int s = 0, e = v->count;
80
81 while (s != e) {
82 unsigned int mid = (s + e) / 2;
83
84 if (v->types[mid] == type)
85 return 1;
86
87 if (v->types[mid] < type)
88 s = mid + 1;
89 else
90 e = mid;
91 }
92 return 0;
93 }
94
95 /* builds map: type/attribute -> {all attributes that are a superset of it} */
build_type_map(const policydb_t * p)96 static struct type_vec *build_type_map(const policydb_t *p)
97 {
98 unsigned int i, k;
99 ebitmap_node_t *n;
100 struct type_vec *map = calloc(p->p_types.nprim, sizeof(*map));
101 if (!map)
102 return NULL;
103
104 for (i = 0; i < p->p_types.nprim; i++) {
105 if (type_vec_init(&map[i]))
106 goto err;
107
108 if (!p->type_val_to_struct[i])
109 continue;
110
111 if (p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
112 ebitmap_for_each_positive_bit(&p->type_attr_map[i],
113 n, k) {
114 if (type_vec_append(&map[i], k))
115 goto err;
116 }
117 } else {
118 ebitmap_t *types_i = &p->attr_type_map[i];
119
120 for (k = 0; k < p->p_types.nprim; k++) {
121 const ebitmap_t *types_k;
122
123 if (!p->type_val_to_struct[k] || p->type_val_to_struct[k]->flavor != TYPE_ATTRIB)
124 continue;
125
126 types_k = &p->attr_type_map[k];
127
128 if (ebitmap_contains(types_k, types_i)) {
129 if (type_vec_append(&map[i], k))
130 goto err;
131 }
132 }
133 }
134 }
135 return map;
136 err:
137 for (k = 0; k <= i; k++)
138 type_vec_destroy(&map[k]);
139 free(map);
140 return NULL;
141 }
142
destroy_type_map(const policydb_t * p,struct type_vec * type_map)143 static void destroy_type_map(const policydb_t *p, struct type_vec *type_map)
144 {
145 unsigned int i;
146 for (i = 0; i < p->p_types.nprim; i++)
147 type_vec_destroy(&type_map[i]);
148 free(type_map);
149 }
150
process_xperms(uint32_t * p1,const uint32_t * p2)151 static int process_xperms(uint32_t *p1, const uint32_t *p2)
152 {
153 size_t i;
154 int ret = 1;
155
156 for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
157 p1[i] &= ~p2[i];
158 if (p1[i] != 0)
159 ret = 0;
160 }
161 return ret;
162 }
163
process_avtab_datum(uint16_t specified,avtab_datum_t * d1,const avtab_datum_t * d2)164 static int process_avtab_datum(uint16_t specified,
165 avtab_datum_t *d1, const avtab_datum_t *d2)
166 {
167 /* inverse logic needed for AUDITDENY rules */
168 if (specified & AVTAB_AUDITDENY)
169 return (d1->data |= ~d2->data) == UINT32_C(0xFFFFFFFF);
170
171 if (specified & AVTAB_AV)
172 return (d1->data &= ~d2->data) == 0;
173
174 if (specified & AVTAB_XPERMS) {
175 avtab_extended_perms_t *x1 = d1->xperms;
176 const avtab_extended_perms_t *x2 = d2->xperms;
177
178 if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
179 if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
180 if (x1->driver != x2->driver)
181 return 0;
182 return process_xperms(x1->perms, x2->perms);
183 }
184 if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
185 return xperm_test(x1->driver, x2->perms);
186 } else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
187 if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
188 return 0;
189
190 if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
191 return process_xperms(x1->perms, x2->perms);
192 } else if (x1->specified == AVTAB_XPERMS_NLMSG
193 && x2->specified == AVTAB_XPERMS_NLMSG) {
194 if (x1->driver != x2->driver)
195 return 0;
196 return process_xperms(x1->perms, x2->perms);
197 }
198 return 0;
199 }
200 return 0;
201 }
202
203 /* checks if avtab contains a rule that covers the given rule */
is_avrule_redundant(avtab_ptr_t entry,avtab_t * tab,const struct type_vec * type_map,unsigned char not_cond)204 static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
205 const struct type_vec *type_map,
206 unsigned char not_cond)
207 {
208 unsigned int i, k, s_idx, t_idx;
209 uint32_t st, tt;
210 avtab_datum_t *d1, *d2;
211 avtab_key_t key;
212
213 /* we only care about AV rules */
214 if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
215 return 0;
216
217 s_idx = entry->key.source_type - 1;
218 t_idx = entry->key.target_type - 1;
219
220 key.target_class = entry->key.target_class;
221 key.specified = entry->key.specified;
222
223 d1 = &entry->datum;
224
225 for (i = 0; i < type_map[s_idx].count; i++) {
226 st = type_map[s_idx].types[i];
227 key.source_type = st + 1;
228
229 for (k = 0; k < type_map[t_idx].count; k++) {
230 tt = type_map[t_idx].types[k];
231
232 if (not_cond && s_idx == st && t_idx == tt)
233 continue;
234
235 key.target_type = tt + 1;
236
237 d2 = avtab_search(tab, &key);
238 if (!d2)
239 continue;
240
241 if (process_avtab_datum(key.specified, d1, d2))
242 return 1;
243 }
244 }
245 return 0;
246 }
247
is_type_attr(policydb_t * p,unsigned int id)248 static int is_type_attr(policydb_t *p, unsigned int id)
249 {
250 return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
251 }
252
is_avrule_with_attr(avtab_ptr_t entry,policydb_t * p)253 static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
254 {
255 unsigned int s_idx = entry->key.source_type - 1;
256 unsigned int t_idx = entry->key.target_type - 1;
257
258 return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
259 }
260
261 /* checks if conditional list contains a rule that covers the given rule */
is_cond_rule_redundant(avtab_ptr_t e1,cond_av_list_t * list,const struct type_vec * type_map)262 static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
263 const struct type_vec *type_map)
264 {
265 unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
266
267 /* we only care about AV rules */
268 if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
269 return 0;
270
271 s1 = e1->key.source_type - 1;
272 t1 = e1->key.target_type - 1;
273 c1 = e1->key.target_class;
274 k1 = e1->key.specified;
275
276 for (; list; list = list->next) {
277 avtab_ptr_t e2 = list->node;
278
279 s2 = e2->key.source_type - 1;
280 t2 = e2->key.target_type - 1;
281 c2 = e2->key.target_class;
282 k2 = e2->key.specified;
283
284 if (k1 != k2 || c1 != c2)
285 continue;
286
287 if (s1 == s2 && t1 == t2)
288 continue;
289 if (!type_vec_contains(&type_map[s1], s2))
290 continue;
291 if (!type_vec_contains(&type_map[t1], t2))
292 continue;
293
294 if (process_avtab_datum(k1, &e1->datum, &e2->datum))
295 return 1;
296 }
297 return 0;
298 }
299
optimize_avtab(policydb_t * p,const struct type_vec * type_map)300 static void optimize_avtab(policydb_t *p, const struct type_vec *type_map)
301 {
302 avtab_t *tab = &p->te_avtab;
303 unsigned int i;
304 avtab_ptr_t *cur;
305
306 for (i = 0; i < tab->nslot; i++) {
307 cur = &tab->htable[i];
308 while (*cur) {
309 if (is_avrule_redundant(*cur, tab, type_map, 1)) {
310 /* redundant rule -> remove it */
311 avtab_ptr_t tmp = *cur;
312
313 *cur = tmp->next;
314 if (tmp->key.specified & AVTAB_XPERMS)
315 free(tmp->datum.xperms);
316 free(tmp);
317
318 tab->nel--;
319 } else {
320 /* rule not redundant -> move to next rule */
321 cur = &(*cur)->next;
322 }
323 }
324 }
325 }
326
327 /* find redundant rules in (*cond) and put them into (*del) */
optimize_cond_av_list(cond_av_list_t ** cond,cond_av_list_t ** del,policydb_t * p,const struct type_vec * type_map)328 static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
329 policydb_t *p, const struct type_vec *type_map)
330 {
331 cond_av_list_t **listp = cond;
332 cond_av_list_t *pcov = NULL;
333 cond_av_list_t **pcov_cur;
334
335 /*
336 * Separate out all "potentially covering" rules (src or tgt is an attr)
337 * and move them to the end of the list. This is needed to avoid
338 * polynomial complexity when almost all rules are expanded.
339 */
340 while (*cond) {
341 if (is_avrule_with_attr((*cond)->node, p)) {
342 cond_av_list_t *tmp = *cond;
343
344 *cond = tmp->next;
345 tmp->next = pcov;
346 pcov = tmp;
347 } else {
348 cond = &(*cond)->next;
349 }
350 }
351 /* link the "potentially covering" rules to the end of the list */
352 *cond = pcov;
353
354 /* now go through the list and find the redundant rules */
355 cond = listp;
356 pcov_cur = &pcov;
357 while (*cond) {
358 /* needed because pcov itself may get deleted */
359 if (*cond == pcov)
360 pcov_cur = cond;
361 /*
362 * First check if covered by an unconditional rule, then also
363 * check if covered by another rule in the same list.
364 */
365 if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map, 0) ||
366 is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
367 cond_av_list_t *tmp = *cond;
368
369 *cond = tmp->next;
370 tmp->next = *del;
371 *del = tmp;
372 } else {
373 cond = &(*cond)->next;
374 }
375 }
376 }
377
optimize_cond_avtab(policydb_t * p,const struct type_vec * type_map)378 static void optimize_cond_avtab(policydb_t *p, const struct type_vec *type_map)
379 {
380 avtab_t *tab = &p->te_cond_avtab;
381 unsigned int i;
382 avtab_ptr_t *cur;
383 cond_node_t **cond;
384 cond_av_list_t **avcond, *del = NULL;
385
386 /* First go through all conditionals and collect redundant rules. */
387 cond = &p->cond_list;
388 while (*cond) {
389 optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map);
390 optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
391 /* TODO: maybe also check for rules present in both lists */
392
393 /* nothing left in both lists -> remove the whole conditional */
394 if (!(*cond)->true_list && !(*cond)->false_list) {
395 cond_node_t *cond_tmp = *cond;
396
397 *cond = cond_tmp->next;
398 cond_node_destroy(cond_tmp);
399 free(cond_tmp);
400 } else {
401 cond = &(*cond)->next;
402 }
403 }
404
405 if (!del)
406 return;
407
408 /*
409 * Now go through the whole cond_avtab and remove all rules that are
410 * found in the 'del' list.
411 */
412 for (i = 0; i < tab->nslot; i++) {
413 cur = &tab->htable[i];
414 while (*cur) {
415 int redundant = 0;
416 avcond = &del;
417 while (*avcond) {
418 if ((*avcond)->node == *cur) {
419 cond_av_list_t *cond_tmp = *avcond;
420
421 *avcond = cond_tmp->next;
422 free(cond_tmp);
423 redundant = 1;
424 break;
425 } else {
426 avcond = &(*avcond)->next;
427 }
428 }
429 if (redundant) {
430 avtab_ptr_t tmp = *cur;
431
432 *cur = tmp->next;
433 if (tmp->key.specified & AVTAB_XPERMS)
434 free(tmp->datum.xperms);
435 free(tmp);
436
437 tab->nel--;
438 } else {
439 cur = &(*cur)->next;
440 }
441 }
442 }
443 }
444
policydb_optimize(policydb_t * p)445 int policydb_optimize(policydb_t *p)
446 {
447 struct type_vec *type_map;
448
449 if (p->policy_type != POLICY_KERN)
450 return -1;
451
452 if (p->policyvers >= POLICYDB_VERSION_AVTAB && p->policyvers <= POLICYDB_VERSION_PERMISSIVE) {
453 /*
454 * For policy versions between 20 and 23, attributes exist in the policy,
455 * but only in the type_attr_map. This means that there are gaps in both
456 * the type_val_to_struct and p_type_val_to_name arrays and policy rules
457 * can refer to those gaps.
458 */
459 ERR(NULL, "Optimizing policy versions between 20 and 23 is not supported");
460 return -1;
461 }
462
463 type_map = build_type_map(p);
464 if (!type_map)
465 return -1;
466
467 optimize_avtab(p, type_map);
468 optimize_cond_avtab(p, type_map);
469
470 destroy_type_map(p, type_map);
471 return 0;
472 }
473