1 /*
2 * Author: Ondrej Mosnacek <omosnacek@gmail.com>
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 /* builds map: type/attribute -> {all attributes that are a superset of it} */
build_type_map(const policydb_t * p)35 static ebitmap_t *build_type_map(const policydb_t *p)
36 {
37 unsigned int i, k;
38 ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
39 if (!map)
40 return NULL;
41
42 for (i = 0; i < p->p_types.nprim; i++) {
43 if (p->type_val_to_struct[i] &&
44 p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
45 if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
46 goto err;
47 } else {
48 ebitmap_t *types_i = &p->attr_type_map[i];
49
50 ebitmap_init(&map[i]);
51 for (k = 0; k < p->p_types.nprim; k++) {
52 ebitmap_t *types_k = &p->attr_type_map[k];
53
54 if (ebitmap_contains(types_k, types_i)) {
55 if (ebitmap_set_bit(&map[i], k, 1))
56 goto err;
57 }
58 }
59 }
60 }
61 return map;
62 err:
63 for (k = 0; k <= i; k++)
64 ebitmap_destroy(&map[k]);
65 free(map);
66 return NULL;
67 }
68
destroy_type_map(const policydb_t * p,ebitmap_t * type_map)69 static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
70 {
71 unsigned int i;
72 for (i = 0; i < p->p_types.nprim; i++)
73 ebitmap_destroy(&type_map[i]);
74 free(type_map);
75 }
76
process_xperms(uint32_t * p1,const uint32_t * p2)77 static int process_xperms(uint32_t *p1, const uint32_t *p2)
78 {
79 size_t i;
80 int ret = 1;
81
82 for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
83 p1[i] &= ~p2[i];
84 if (p1[i] != 0)
85 ret = 0;
86 }
87 return ret;
88 }
89
process_avtab_datum(uint16_t specified,avtab_datum_t * d1,const avtab_datum_t * d2)90 static int process_avtab_datum(uint16_t specified,
91 avtab_datum_t *d1, const avtab_datum_t *d2)
92 {
93 /* inverse logic needed for AUDITDENY rules */
94 if (specified & AVTAB_AUDITDENY)
95 return (d1->data |= ~d2->data) == UINT32_C(0xFFFFFFFF);
96
97 if (specified & AVTAB_AV)
98 return (d1->data &= ~d2->data) == 0;
99
100 if (specified & AVTAB_XPERMS) {
101 avtab_extended_perms_t *x1 = d1->xperms;
102 const avtab_extended_perms_t *x2 = d2->xperms;
103
104 if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
105 if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
106 if (x1->driver != x2->driver)
107 return 0;
108 return process_xperms(x1->perms, x2->perms);
109 }
110 if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
111 return xperm_test(x1->driver, x2->perms);
112 } else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
113 if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
114 return 0;
115
116 if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
117 return process_xperms(x1->perms, x2->perms);
118 }
119 return 0;
120 }
121 return 0;
122 }
123
124 /* checks if avtab contains a rule that covers the given rule */
is_avrule_redundant(avtab_ptr_t entry,avtab_t * tab,const ebitmap_t * type_map,unsigned char not_cond)125 static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
126 const ebitmap_t *type_map, unsigned char not_cond)
127 {
128 unsigned int i, k, s_idx, t_idx;
129 ebitmap_node_t *snode, *tnode;
130 avtab_datum_t *d1, *d2;
131 avtab_key_t key;
132
133 /* we only care about AV rules */
134 if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
135 return 0;
136
137 s_idx = entry->key.source_type - 1;
138 t_idx = entry->key.target_type - 1;
139
140 key.target_class = entry->key.target_class;
141 key.specified = entry->key.specified;
142
143 d1 = &entry->datum;
144
145 ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
146 key.source_type = i + 1;
147
148 ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
149 if (not_cond && s_idx == i && t_idx == k)
150 continue;
151
152 key.target_type = k + 1;
153
154 d2 = avtab_search(tab, &key);
155 if (!d2)
156 continue;
157
158 if (process_avtab_datum(key.specified, d1, d2))
159 return 1;
160 }
161 }
162 return 0;
163 }
164
is_type_attr(policydb_t * p,unsigned int id)165 static int is_type_attr(policydb_t *p, unsigned int id)
166 {
167 return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
168 }
169
is_avrule_with_attr(avtab_ptr_t entry,policydb_t * p)170 static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
171 {
172 unsigned int s_idx = entry->key.source_type - 1;
173 unsigned int t_idx = entry->key.target_type - 1;
174
175 return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
176 }
177
178 /* 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 ebitmap_t * type_map)179 static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
180 const ebitmap_t *type_map)
181 {
182 unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
183
184 /* we only care about AV rules */
185 if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
186 return 0;
187
188 s1 = e1->key.source_type - 1;
189 t1 = e1->key.target_type - 1;
190 c1 = e1->key.target_class;
191 k1 = e1->key.specified;
192
193 for (; list; list = list->next) {
194 avtab_ptr_t e2 = list->node;
195
196 s2 = e2->key.source_type - 1;
197 t2 = e2->key.target_type - 1;
198 c2 = e2->key.target_class;
199 k2 = e2->key.specified;
200
201 if (k1 != k2 || c1 != c2)
202 continue;
203
204 if (s1 == s2 && t1 == t2)
205 continue;
206 if (!ebitmap_get_bit(&type_map[s1], s2))
207 continue;
208 if (!ebitmap_get_bit(&type_map[t1], t2))
209 continue;
210
211 if (process_avtab_datum(k1, &e1->datum, &e2->datum))
212 return 1;
213 }
214 return 0;
215 }
216
optimize_avtab(policydb_t * p,const ebitmap_t * type_map)217 static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
218 {
219 avtab_t *tab = &p->te_avtab;
220 unsigned int i;
221 avtab_ptr_t *cur;
222
223 for (i = 0; i < tab->nslot; i++) {
224 cur = &tab->htable[i];
225 while (*cur) {
226 if (is_avrule_redundant(*cur, tab, type_map, 1)) {
227 /* redundant rule -> remove it */
228 avtab_ptr_t tmp = *cur;
229
230 *cur = tmp->next;
231 if (tmp->key.specified & AVTAB_XPERMS)
232 free(tmp->datum.xperms);
233 free(tmp);
234
235 tab->nel--;
236 } else {
237 /* rule not redundant -> move to next rule */
238 cur = &(*cur)->next;
239 }
240 }
241 }
242 }
243
244 /* 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 ebitmap_t * type_map)245 static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
246 policydb_t *p, const ebitmap_t *type_map)
247 {
248 cond_av_list_t **listp = cond;
249 cond_av_list_t *pcov = NULL;
250 cond_av_list_t **pcov_cur;
251
252 /*
253 * Separate out all "potentially covering" rules (src or tgt is an attr)
254 * and move them to the end of the list. This is needed to avoid
255 * polynomial complexity when almost all rules are expanded.
256 */
257 while (*cond) {
258 if (is_avrule_with_attr((*cond)->node, p)) {
259 cond_av_list_t *tmp = *cond;
260
261 *cond = tmp->next;
262 tmp->next = pcov;
263 pcov = tmp;
264 } else {
265 cond = &(*cond)->next;
266 }
267 }
268 /* link the "potentially covering" rules to the end of the list */
269 *cond = pcov;
270
271 /* now go through the list and find the redundant rules */
272 cond = listp;
273 pcov_cur = &pcov;
274 while (*cond) {
275 /* needed because pcov itself may get deleted */
276 if (*cond == pcov)
277 pcov_cur = cond;
278 /*
279 * First check if covered by an unconditional rule, then also
280 * check if covered by another rule in the same list.
281 */
282 if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map, 0) ||
283 is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
284 cond_av_list_t *tmp = *cond;
285
286 *cond = tmp->next;
287 tmp->next = *del;
288 *del = tmp;
289 } else {
290 cond = &(*cond)->next;
291 }
292 }
293 }
294
optimize_cond_avtab(policydb_t * p,const ebitmap_t * type_map)295 static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
296 {
297 avtab_t *tab = &p->te_cond_avtab;
298 unsigned int i;
299 avtab_ptr_t *cur;
300 cond_node_t **cond;
301 cond_av_list_t **avcond, *del = NULL;
302
303 /* First go through all conditionals and collect redundant rules. */
304 cond = &p->cond_list;
305 while (*cond) {
306 optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map);
307 optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
308 /* TODO: maybe also check for rules present in both lists */
309
310 /* nothing left in both lists -> remove the whole conditional */
311 if (!(*cond)->true_list && !(*cond)->false_list) {
312 cond_node_t *cond_tmp = *cond;
313
314 *cond = cond_tmp->next;
315 cond_node_destroy(cond_tmp);
316 free(cond_tmp);
317 } else {
318 cond = &(*cond)->next;
319 }
320 }
321
322 if (!del)
323 return;
324
325 /*
326 * Now go through the whole cond_avtab and remove all rules that are
327 * found in the 'del' list.
328 */
329 for (i = 0; i < tab->nslot; i++) {
330 cur = &tab->htable[i];
331 while (*cur) {
332 int redundant = 0;
333 avcond = &del;
334 while (*avcond) {
335 if ((*avcond)->node == *cur) {
336 cond_av_list_t *cond_tmp = *avcond;
337
338 *avcond = cond_tmp->next;
339 free(cond_tmp);
340 redundant = 1;
341 break;
342 } else {
343 avcond = &(*avcond)->next;
344 }
345 }
346 if (redundant) {
347 avtab_ptr_t tmp = *cur;
348
349 *cur = tmp->next;
350 if (tmp->key.specified & AVTAB_XPERMS)
351 free(tmp->datum.xperms);
352 free(tmp);
353
354 tab->nel--;
355 } else {
356 cur = &(*cur)->next;
357 }
358 }
359 }
360 }
361
policydb_optimize(policydb_t * p)362 int policydb_optimize(policydb_t *p)
363 {
364 ebitmap_t *type_map;
365
366 if (p->policy_type != POLICY_KERN)
367 return -1;
368
369 type_map = build_type_map(p);
370 if (!type_map)
371 return -1;
372
373 optimize_avtab(p, type_map);
374 optimize_cond_avtab(p, type_map);
375
376 destroy_type_map(p, type_map);
377 return 0;
378 }
379