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#include "debug.h" 35#include "private.h" 36 37#define TYPE_VEC_INIT_SIZE 16 38 39struct type_vec { 40 uint32_t *types; 41 unsigned int count, capacity; 42}; 43 44static 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 54static void type_vec_destroy(struct type_vec *v) 55{ 56 free(v->types); 57} 58 59static 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 77static 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} */ 96static 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; 136err: 137 for (k = 0; k <= i; k++) 138 type_vec_destroy(&map[k]); 139 free(map); 140 return NULL; 141} 142 143static 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 151static 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 164static 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 } 193 return 0; 194 } 195 return 0; 196} 197 198/* checks if avtab contains a rule that covers the given rule */ 199static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab, 200 const struct type_vec *type_map, 201 unsigned char not_cond) 202{ 203 unsigned int i, k, s_idx, t_idx; 204 uint32_t st, tt; 205 avtab_datum_t *d1, *d2; 206 avtab_key_t key; 207 208 /* we only care about AV rules */ 209 if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS))) 210 return 0; 211 212 s_idx = entry->key.source_type - 1; 213 t_idx = entry->key.target_type - 1; 214 215 key.target_class = entry->key.target_class; 216 key.specified = entry->key.specified; 217 218 d1 = &entry->datum; 219 220 for (i = 0; i < type_map[s_idx].count; i++) { 221 st = type_map[s_idx].types[i]; 222 key.source_type = st + 1; 223 224 for (k = 0; k < type_map[t_idx].count; k++) { 225 tt = type_map[t_idx].types[k]; 226 227 if (not_cond && s_idx == st && t_idx == tt) 228 continue; 229 230 key.target_type = tt + 1; 231 232 d2 = avtab_search(tab, &key); 233 if (!d2) 234 continue; 235 236 if (process_avtab_datum(key.specified, d1, d2)) 237 return 1; 238 } 239 } 240 return 0; 241} 242 243static int is_type_attr(policydb_t *p, unsigned int id) 244{ 245 return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB; 246} 247 248static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p) 249{ 250 unsigned int s_idx = entry->key.source_type - 1; 251 unsigned int t_idx = entry->key.target_type - 1; 252 253 return is_type_attr(p, s_idx) || is_type_attr(p, t_idx); 254} 255 256/* checks if conditional list contains a rule that covers the given rule */ 257static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list, 258 const struct type_vec *type_map) 259{ 260 unsigned int s1, t1, c1, k1, s2, t2, c2, k2; 261 262 /* we only care about AV rules */ 263 if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS))) 264 return 0; 265 266 s1 = e1->key.source_type - 1; 267 t1 = e1->key.target_type - 1; 268 c1 = e1->key.target_class; 269 k1 = e1->key.specified; 270 271 for (; list; list = list->next) { 272 avtab_ptr_t e2 = list->node; 273 274 s2 = e2->key.source_type - 1; 275 t2 = e2->key.target_type - 1; 276 c2 = e2->key.target_class; 277 k2 = e2->key.specified; 278 279 if (k1 != k2 || c1 != c2) 280 continue; 281 282 if (s1 == s2 && t1 == t2) 283 continue; 284 if (!type_vec_contains(&type_map[s1], s2)) 285 continue; 286 if (!type_vec_contains(&type_map[t1], t2)) 287 continue; 288 289 if (process_avtab_datum(k1, &e1->datum, &e2->datum)) 290 return 1; 291 } 292 return 0; 293} 294 295static void optimize_avtab(policydb_t *p, const struct type_vec *type_map) 296{ 297 avtab_t *tab = &p->te_avtab; 298 unsigned int i; 299 avtab_ptr_t *cur; 300 301 for (i = 0; i < tab->nslot; i++) { 302 cur = &tab->htable[i]; 303 while (*cur) { 304 if (is_avrule_redundant(*cur, tab, type_map, 1)) { 305 /* redundant rule -> remove it */ 306 avtab_ptr_t tmp = *cur; 307 308 *cur = tmp->next; 309 if (tmp->key.specified & AVTAB_XPERMS) 310 free(tmp->datum.xperms); 311 free(tmp); 312 313 tab->nel--; 314 } else { 315 /* rule not redundant -> move to next rule */ 316 cur = &(*cur)->next; 317 } 318 } 319 } 320} 321 322/* find redundant rules in (*cond) and put them into (*del) */ 323static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del, 324 policydb_t *p, const struct type_vec *type_map) 325{ 326 cond_av_list_t **listp = cond; 327 cond_av_list_t *pcov = NULL; 328 cond_av_list_t **pcov_cur; 329 330 /* 331 * Separate out all "potentially covering" rules (src or tgt is an attr) 332 * and move them to the end of the list. This is needed to avoid 333 * polynomial complexity when almost all rules are expanded. 334 */ 335 while (*cond) { 336 if (is_avrule_with_attr((*cond)->node, p)) { 337 cond_av_list_t *tmp = *cond; 338 339 *cond = tmp->next; 340 tmp->next = pcov; 341 pcov = tmp; 342 } else { 343 cond = &(*cond)->next; 344 } 345 } 346 /* link the "potentially covering" rules to the end of the list */ 347 *cond = pcov; 348 349 /* now go through the list and find the redundant rules */ 350 cond = listp; 351 pcov_cur = &pcov; 352 while (*cond) { 353 /* needed because pcov itself may get deleted */ 354 if (*cond == pcov) 355 pcov_cur = cond; 356 /* 357 * First check if covered by an unconditional rule, then also 358 * check if covered by another rule in the same list. 359 */ 360 if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map, 0) || 361 is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) { 362 cond_av_list_t *tmp = *cond; 363 364 *cond = tmp->next; 365 tmp->next = *del; 366 *del = tmp; 367 } else { 368 cond = &(*cond)->next; 369 } 370 } 371} 372 373static void optimize_cond_avtab(policydb_t *p, const struct type_vec *type_map) 374{ 375 avtab_t *tab = &p->te_cond_avtab; 376 unsigned int i; 377 avtab_ptr_t *cur; 378 cond_node_t **cond; 379 cond_av_list_t **avcond, *del = NULL; 380 381 /* First go through all conditionals and collect redundant rules. */ 382 cond = &p->cond_list; 383 while (*cond) { 384 optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map); 385 optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map); 386 /* TODO: maybe also check for rules present in both lists */ 387 388 /* nothing left in both lists -> remove the whole conditional */ 389 if (!(*cond)->true_list && !(*cond)->false_list) { 390 cond_node_t *cond_tmp = *cond; 391 392 *cond = cond_tmp->next; 393 cond_node_destroy(cond_tmp); 394 free(cond_tmp); 395 } else { 396 cond = &(*cond)->next; 397 } 398 } 399 400 if (!del) 401 return; 402 403 /* 404 * Now go through the whole cond_avtab and remove all rules that are 405 * found in the 'del' list. 406 */ 407 for (i = 0; i < tab->nslot; i++) { 408 cur = &tab->htable[i]; 409 while (*cur) { 410 int redundant = 0; 411 avcond = &del; 412 while (*avcond) { 413 if ((*avcond)->node == *cur) { 414 cond_av_list_t *cond_tmp = *avcond; 415 416 *avcond = cond_tmp->next; 417 free(cond_tmp); 418 redundant = 1; 419 break; 420 } else { 421 avcond = &(*avcond)->next; 422 } 423 } 424 if (redundant) { 425 avtab_ptr_t tmp = *cur; 426 427 *cur = tmp->next; 428 if (tmp->key.specified & AVTAB_XPERMS) 429 free(tmp->datum.xperms); 430 free(tmp); 431 432 tab->nel--; 433 } else { 434 cur = &(*cur)->next; 435 } 436 } 437 } 438} 439 440int policydb_optimize(policydb_t *p) 441{ 442 struct type_vec *type_map; 443 444 if (p->policy_type != POLICY_KERN) 445 return -1; 446 447 if (p->policyvers >= POLICYDB_VERSION_AVTAB && p->policyvers <= POLICYDB_VERSION_PERMISSIVE) { 448 /* 449 * For policy versions between 20 and 23, attributes exist in the policy, 450 * but only in the type_attr_map. This means that there are gaps in both 451 * the type_val_to_struct and p_type_val_to_name arrays and policy rules 452 * can refer to those gaps. 453 */ 454 ERR(NULL, "Optimizing policy versions between 20 and 23 is not supported"); 455 return -1; 456 } 457 458 type_map = build_type_map(p); 459 if (!type_map) 460 return -1; 461 462 optimize_avtab(p, type_map); 463 optimize_cond_avtab(p, type_map); 464 465 destroy_type_map(p, type_map); 466 return 0; 467} 468