diff options
Diffstat (limited to 'src/conditional.c')
-rw-r--r-- | src/conditional.c | 905 |
1 files changed, 905 insertions, 0 deletions
diff --git a/src/conditional.c b/src/conditional.c new file mode 100644 index 0000000..1482387 --- /dev/null +++ b/src/conditional.c @@ -0,0 +1,905 @@ +/* Authors: Karl MacMillan <kmacmillan@tresys.com> + * Frank Mayer <mayerf@tresys.com> + * David Caplan <dac@tresys.com> + * + * Copyright (C) 2003 - 2005 Tresys Technology, LLC + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include <stdlib.h> + +#include <sepol/policydb/flask_types.h> +#include <sepol/policydb/conditional.h> + +#include "private.h" + +/* move all type rules to top of t/f lists to help kernel on evaluation */ +static void cond_optimize(cond_av_list_t ** l) +{ + cond_av_list_t *top, *p, *cur; + + top = p = cur = *l; + + while (cur) { + if ((cur->node->key.specified & AVTAB_TYPE) && (top != cur)) { + p->next = cur->next; + cur->next = top; + top = cur; + cur = p->next; + } else { + p = cur; + cur = cur->next; + } + } + *l = top; +} + +/* reorder t/f lists for kernel */ +void cond_optimize_lists(cond_list_t * cl) +{ + cond_list_t *n; + + for (n = cl; n != NULL; n = n->next) { + cond_optimize(&n->true_list); + cond_optimize(&n->false_list); + } +} + +static int bool_present(unsigned int target, unsigned int bools[], + unsigned int num_bools) +{ + unsigned int i = 0; + int ret = 1; + + if (num_bools > COND_MAX_BOOLS) { + return 0; + } + while (i < num_bools && target != bools[i]) + i++; + if (i == num_bools) + ret = 0; /* got to end w/o match */ + return ret; +} + +static int same_bools(cond_node_t * a, cond_node_t * b) +{ + unsigned int i, x; + + x = a->nbools; + + /* same number of bools? */ + if (x != b->nbools) + return 0; + + /* make sure all the bools in a are also in b */ + for (i = 0; i < x; i++) + if (!bool_present(a->bool_ids[i], b->bool_ids, x)) + return 0; + return 1; +} + +/* + * Determine if two conditional expressions are equal. + */ +int cond_expr_equal(cond_node_t * a, cond_node_t * b) +{ + cond_expr_t *cur_a, *cur_b; + + if (a == NULL || b == NULL) + return 0; + + if (a->nbools != b->nbools) + return 0; + + /* if exprs have <= COND_MAX_BOOLS we can check the precompute values + * for the expressions. + */ + if (a->nbools <= COND_MAX_BOOLS && b->nbools <= COND_MAX_BOOLS) { + if (!same_bools(a, b)) + return 0; + return (a->expr_pre_comp == b->expr_pre_comp); + } + + /* for long expressions we check for exactly the same expression */ + cur_a = a->expr; + cur_b = b->expr; + while (1) { + if (cur_a == NULL && cur_b == NULL) + return 1; + else if (cur_a == NULL || cur_b == NULL) + return 0; + if (cur_a->expr_type != cur_b->expr_type) + return 0; + if (cur_a->expr_type == COND_BOOL) { + if (cur_a->bool != cur_b->bool) + return 0; + } + cur_a = cur_a->next; + cur_b = cur_b->next; + } + return 1; +} + +/* Create a new conditional node, optionally copying + * the conditional expression from an existing node. + * If node is NULL then a new node will be created + * with no conditional expression. + */ +cond_node_t *cond_node_create(policydb_t * p, cond_node_t * node) +{ + cond_node_t *new_node; + unsigned int i; + + new_node = (cond_node_t *)malloc(sizeof(cond_node_t)); + if (!new_node) { + return NULL; + } + memset(new_node, 0, sizeof(cond_node_t)); + + if (node) { + new_node->expr = cond_copy_expr(node->expr); + if (!new_node->expr) { + free(new_node); + return NULL; + } + new_node->cur_state = cond_evaluate_expr(p, new_node->expr); + new_node->nbools = node->nbools; + for (i = 0; i < min(node->nbools, COND_MAX_BOOLS); i++) + new_node->bool_ids[i] = node->bool_ids[i]; + new_node->expr_pre_comp = node->expr_pre_comp; + } + + return new_node; +} + +/* Find a conditional (the needle) within a list of existing ones (the + * haystack) that has a matching expression. If found, return a + * pointer to the existing node, setting 'was_created' to 0. + * Otherwise create a new one and return it, setting 'was_created' to + * 1. */ +cond_node_t *cond_node_find(policydb_t * p, + cond_node_t * needle, cond_node_t * haystack, + int *was_created) +{ + while (haystack) { + if (cond_expr_equal(needle, haystack)) { + *was_created = 0; + return haystack; + } + haystack = haystack->next; + } + *was_created = 1; + + return cond_node_create(p, needle); +} + +/* return either a pre-existing matching node or create a new node */ +cond_node_t *cond_node_search(policydb_t * p, cond_node_t * list, + cond_node_t * cn) +{ + int was_created; + cond_node_t *result = cond_node_find(p, cn, list, &was_created); + if (result != NULL && was_created) { + /* add conditional node to policy list */ + result->next = p->cond_list; + p->cond_list = result; + } + return result; +} + +/* + * cond_evaluate_expr evaluates a conditional expr + * in reverse polish notation. It returns true (1), false (0), + * or undefined (-1). Undefined occurs when the expression + * exceeds the stack depth of COND_EXPR_MAXDEPTH. + */ +int cond_evaluate_expr(policydb_t * p, cond_expr_t * expr) +{ + + cond_expr_t *cur; + int s[COND_EXPR_MAXDEPTH]; + int sp = -1; + + s[0] = -1; + + for (cur = expr; cur != NULL; cur = cur->next) { + switch (cur->expr_type) { + case COND_BOOL: + if (sp == (COND_EXPR_MAXDEPTH - 1)) + return -1; + sp++; + s[sp] = p->bool_val_to_struct[cur->bool - 1]->state; + break; + case COND_NOT: + if (sp < 0) + return -1; + s[sp] = !s[sp]; + break; + case COND_OR: + if (sp < 1) + return -1; + sp--; + s[sp] |= s[sp + 1]; + break; + case COND_AND: + if (sp < 1) + return -1; + sp--; + s[sp] &= s[sp + 1]; + break; + case COND_XOR: + if (sp < 1) + return -1; + sp--; + s[sp] ^= s[sp + 1]; + break; + case COND_EQ: + if (sp < 1) + return -1; + sp--; + s[sp] = (s[sp] == s[sp + 1]); + break; + case COND_NEQ: + if (sp < 1) + return -1; + sp--; + s[sp] = (s[sp] != s[sp + 1]); + break; + default: + return -1; + } + } + return s[0]; +} + +cond_expr_t *cond_copy_expr(cond_expr_t * expr) +{ + cond_expr_t *cur, *head, *tail, *new_expr; + tail = head = NULL; + cur = expr; + while (cur) { + new_expr = (cond_expr_t *) malloc(sizeof(cond_expr_t)); + if (!new_expr) + goto free_head; + memset(new_expr, 0, sizeof(cond_expr_t)); + + new_expr->expr_type = cur->expr_type; + new_expr->bool = cur->bool; + + if (!head) + head = new_expr; + if (tail) + tail->next = new_expr; + tail = new_expr; + cur = cur->next; + } + return head; + + free_head: + while (head) { + tail = head->next; + free(head); + head = tail; + } + return NULL; +} + +/* + * evaluate_cond_node evaluates the conditional stored in + * a cond_node_t and if the result is different than the + * current state of the node it sets the rules in the true/false + * list appropriately. If the result of the expression is undefined + * all of the rules are disabled for safety. + */ +static int evaluate_cond_node(policydb_t * p, cond_node_t * node) +{ + int new_state; + cond_av_list_t *cur; + + new_state = cond_evaluate_expr(p, node->expr); + if (new_state != node->cur_state) { + node->cur_state = new_state; + if (new_state == -1) + printf + ("expression result was undefined - disabling all rules.\n"); + /* turn the rules on or off */ + for (cur = node->true_list; cur != NULL; cur = cur->next) { + if (new_state <= 0) { + cur->node->key.specified &= ~AVTAB_ENABLED; + } else { + cur->node->key.specified |= AVTAB_ENABLED; + } + } + + for (cur = node->false_list; cur != NULL; cur = cur->next) { + /* -1 or 1 */ + if (new_state) { + cur->node->key.specified &= ~AVTAB_ENABLED; + } else { + cur->node->key.specified |= AVTAB_ENABLED; + } + } + } + return 0; +} + +/* precompute and simplify an expression if possible. If left with !expression, change + * to expression and switch t and f. precompute expression for expressions with limited + * number of bools. + */ +int cond_normalize_expr(policydb_t * p, cond_node_t * cn) +{ + cond_expr_t *ne, *e; + cond_av_list_t *tmp; + unsigned int i, j, orig_value[COND_MAX_BOOLS]; + int k; + uint32_t test = 0x0; + avrule_t *tmp2; + + cn->nbools = 0; + + memset(cn->bool_ids, 0, sizeof(cn->bool_ids)); + cn->expr_pre_comp = 0x0; + + /* take care of !expr case */ + ne = NULL; + e = cn->expr; + + /* becuase it's RPN look at last element */ + while (e->next != NULL) { + ne = e; + e = e->next; + } + if (e->expr_type == COND_NOT) { + if (ne) { + ne->next = NULL; + } else { /* ne should never be NULL */ + printf + ("Found expr with no bools and only a ! - this should never happen.\n"); + return -1; + } + /* swap the true and false lists */ + tmp = cn->true_list; + cn->true_list = cn->false_list; + cn->false_list = tmp; + tmp2 = cn->avtrue_list; + cn->avtrue_list = cn->avfalse_list; + cn->avfalse_list = tmp2; + + /* free the "not" node in the list */ + free(e); + } + + /* find all the bools in the expression */ + for (e = cn->expr; e != NULL; e = e->next) { + switch (e->expr_type) { + case COND_BOOL: + i = 0; + /* see if we've already seen this bool */ + if (!bool_present(e->bool, cn->bool_ids, cn->nbools)) { + /* count em all but only record up to COND_MAX_BOOLS */ + if (cn->nbools < COND_MAX_BOOLS) + cn->bool_ids[cn->nbools++] = e->bool; + else + cn->nbools++; + } + break; + default: + break; + } + } + + /* only precompute for exprs with <= COND_AX_BOOLS */ + if (cn->nbools <= COND_MAX_BOOLS) { + /* save the default values for the bools so we can play with them */ + for (i = 0; i < cn->nbools; i++) { + orig_value[i] = + p->bool_val_to_struct[cn->bool_ids[i] - 1]->state; + } + + /* loop through all possible combinations of values for bools in expression */ + for (test = 0x0; test < (0x1U << cn->nbools); test++) { + /* temporarily set the value for all the bools in the + * expression using the corr. bit in test */ + for (j = 0; j < cn->nbools; j++) { + p->bool_val_to_struct[cn->bool_ids[j] - + 1]->state = + (test & (0x1 << j)) ? 1 : 0; + } + k = cond_evaluate_expr(p, cn->expr); + if (k == -1) { + printf + ("While testing expression, expression result " + "was undefined - this should never happen.\n"); + return -1; + } + /* set the bit if expression evaluates true */ + if (k) + cn->expr_pre_comp |= 0x1 << test; + } + + /* restore bool default values */ + for (i = 0; i < cn->nbools; i++) + p->bool_val_to_struct[cn->bool_ids[i] - 1]->state = + orig_value[i]; + } + return 0; +} + +int evaluate_conds(policydb_t * p) +{ + int ret; + cond_node_t *cur; + + for (cur = p->cond_list; cur != NULL; cur = cur->next) { + ret = evaluate_cond_node(p, cur); + if (ret) + return ret; + } + return 0; +} + +int cond_policydb_init(policydb_t * p) +{ + p->bool_val_to_struct = NULL; + p->cond_list = NULL; + if (avtab_init(&p->te_cond_avtab)) + return -1; + + return 0; +} + +void cond_av_list_destroy(cond_av_list_t * list) +{ + cond_av_list_t *cur, *next; + for (cur = list; cur != NULL; cur = next) { + next = cur->next; + /* the avtab_ptr_t node is destroy by the avtab */ + free(cur); + } +} + +void cond_expr_destroy(cond_expr_t * expr) +{ + cond_expr_t *cur_expr, *next_expr; + + if (!expr) + return; + + for (cur_expr = expr; cur_expr != NULL; cur_expr = next_expr) { + next_expr = cur_expr->next; + free(cur_expr); + } +} + +void cond_node_destroy(cond_node_t * node) +{ + if (!node) + return; + + cond_expr_destroy(node->expr); + avrule_list_destroy(node->avtrue_list); + avrule_list_destroy(node->avfalse_list); + cond_av_list_destroy(node->true_list); + cond_av_list_destroy(node->false_list); +} + +void cond_list_destroy(cond_list_t * list) +{ + cond_node_t *next, *cur; + + if (list == NULL) + return; + + for (cur = list; cur != NULL; cur = next) { + next = cur->next; + cond_node_destroy(cur); + free(cur); + } +} + +void cond_policydb_destroy(policydb_t * p) +{ + if (p->bool_val_to_struct != NULL) + free(p->bool_val_to_struct); + avtab_destroy(&p->te_cond_avtab); + cond_list_destroy(p->cond_list); +} + +int cond_init_bool_indexes(policydb_t * p) +{ + if (p->bool_val_to_struct) + free(p->bool_val_to_struct); + p->bool_val_to_struct = (cond_bool_datum_t **) + malloc(p->p_bools.nprim * sizeof(cond_bool_datum_t *)); + if (!p->bool_val_to_struct) + return -1; + return 0; +} + +int cond_destroy_bool(hashtab_key_t key, hashtab_datum_t datum, void *p + __attribute__ ((unused))) +{ + if (key) + free(key); + free(datum); + return 0; +} + +int cond_index_bool(hashtab_key_t key, hashtab_datum_t datum, void *datap) +{ + policydb_t *p; + cond_bool_datum_t *booldatum; + + booldatum = datum; + p = datap; + + if (!booldatum->s.value || booldatum->s.value > p->p_bools.nprim) + return -EINVAL; + + p->p_bool_val_to_name[booldatum->s.value - 1] = key; + p->bool_val_to_struct[booldatum->s.value - 1] = booldatum; + + return 0; +} + +static int bool_isvalid(cond_bool_datum_t * b) +{ + if (!(b->state == 0 || b->state == 1)) + return 0; + return 1; +} + +int cond_read_bool(policydb_t * p + __attribute__ ((unused)), hashtab_t h, + struct policy_file *fp) +{ + char *key = 0; + cond_bool_datum_t *booldatum; + uint32_t buf[3], len; + int rc; + + booldatum = malloc(sizeof(cond_bool_datum_t)); + if (!booldatum) + return -1; + memset(booldatum, 0, sizeof(cond_bool_datum_t)); + + rc = next_entry(buf, fp, sizeof(uint32_t) * 3); + if (rc < 0) + goto err; + + booldatum->s.value = le32_to_cpu(buf[0]); + booldatum->state = le32_to_cpu(buf[1]); + + if (!bool_isvalid(booldatum)) + goto err; + + len = le32_to_cpu(buf[2]); + + key = malloc(len + 1); + if (!key) + goto err; + rc = next_entry(key, fp, len); + if (rc < 0) + goto err; + key[len] = 0; + if (hashtab_insert(h, key, booldatum)) + goto err; + + return 0; + err: + cond_destroy_bool(key, booldatum, 0); + return -1; +} + +struct cond_insertf_data { + struct policydb *p; + cond_av_list_t *other; + cond_av_list_t *head; + cond_av_list_t *tail; +}; + +static int cond_insertf(avtab_t * a + __attribute__ ((unused)), avtab_key_t * k, + avtab_datum_t * d, void *ptr) +{ + struct cond_insertf_data *data = ptr; + struct policydb *p = data->p; + cond_av_list_t *other = data->other, *list, *cur; + avtab_ptr_t node_ptr; + uint8_t found; + + /* + * For type rules we have to make certain there aren't any + * conflicting rules by searching the te_avtab and the + * cond_te_avtab. + */ + if (k->specified & AVTAB_TYPE) { + if (avtab_search(&p->te_avtab, k)) { + printf + ("security: type rule already exists outside of a conditional."); + goto err; + } + /* + * If we are reading the false list other will be a pointer to + * the true list. We can have duplicate entries if there is only + * 1 other entry and it is in our true list. + * + * If we are reading the true list (other == NULL) there shouldn't + * be any other entries. + */ + if (other) { + node_ptr = avtab_search_node(&p->te_cond_avtab, k); + if (node_ptr) { + if (avtab_search_node_next + (node_ptr, k->specified)) { + printf + ("security: too many conflicting type rules."); + goto err; + } + found = 0; + for (cur = other; cur != NULL; cur = cur->next) { + if (cur->node == node_ptr) { + found = 1; + break; + } + } + if (!found) { + printf + ("security: conflicting type rules.\n"); + goto err; + } + } + } else { + if (avtab_search(&p->te_cond_avtab, k)) { + printf + ("security: conflicting type rules when adding type rule for true.\n"); + goto err; + } + } + } + + node_ptr = avtab_insert_nonunique(&p->te_cond_avtab, k, d); + if (!node_ptr) { + printf("security: could not insert rule."); + goto err; + } + node_ptr->parse_context = (void *)1; + + list = malloc(sizeof(cond_av_list_t)); + if (!list) + goto err; + memset(list, 0, sizeof(cond_av_list_t)); + + list->node = node_ptr; + if (!data->head) + data->head = list; + else + data->tail->next = list; + data->tail = list; + return 0; + + err: + cond_av_list_destroy(data->head); + data->head = NULL; + return -1; +} + +static int cond_read_av_list(policydb_t * p, void *fp, + cond_av_list_t ** ret_list, cond_av_list_t * other) +{ + unsigned int i; + int rc; + uint32_t buf[1], len; + struct cond_insertf_data data; + + *ret_list = NULL; + + len = 0; + rc = next_entry(buf, fp, sizeof(uint32_t)); + if (rc < 0) + return -1; + + len = le32_to_cpu(buf[0]); + if (len == 0) { + return 0; + } + + data.p = p; + data.other = other; + data.head = NULL; + data.tail = NULL; + for (i = 0; i < len; i++) { + rc = avtab_read_item(fp, p->policyvers, &p->te_cond_avtab, + cond_insertf, &data); + if (rc) + return rc; + + } + + *ret_list = data.head; + return 0; +} + +static int expr_isvalid(policydb_t * p, cond_expr_t * expr) +{ + if (expr->expr_type <= 0 || expr->expr_type > COND_LAST) { + printf + ("security: conditional expressions uses unknown operator.\n"); + return 0; + } + + if (expr->bool > p->p_bools.nprim) { + printf + ("security: conditional expressions uses unknown bool.\n"); + return 0; + } + return 1; +} + +static int cond_read_node(policydb_t * p, cond_node_t * node, void *fp) +{ + uint32_t buf[2]; + int len, i, rc; + cond_expr_t *expr = NULL, *last = NULL; + + rc = next_entry(buf, fp, sizeof(uint32_t)); + if (rc < 0) + goto err; + + node->cur_state = le32_to_cpu(buf[0]); + + len = 0; + rc = next_entry(buf, fp, sizeof(uint32_t)); + if (rc < 0) + goto err; + + /* expr */ + len = le32_to_cpu(buf[0]); + + for (i = 0; i < len; i++) { + rc = next_entry(buf, fp, sizeof(uint32_t) * 2); + if (rc < 0) + goto err; + + expr = malloc(sizeof(cond_expr_t)); + if (!expr) { + goto err; + } + memset(expr, 0, sizeof(cond_expr_t)); + + expr->expr_type = le32_to_cpu(buf[0]); + expr->bool = le32_to_cpu(buf[1]); + + if (!expr_isvalid(p, expr)) { + free(expr); + goto err; + } + + if (i == 0) { + node->expr = expr; + } else { + last->next = expr; + } + last = expr; + } + + if (p->policy_type == POLICY_KERN) { + if (cond_read_av_list(p, fp, &node->true_list, NULL) != 0) + goto err; + if (cond_read_av_list(p, fp, &node->false_list, node->true_list) + != 0) + goto err; + } else { + if (avrule_read_list(p, &node->avtrue_list, fp)) + goto err; + if (avrule_read_list(p, &node->avfalse_list, fp)) + goto err; + } + + return 0; + err: + cond_node_destroy(node); + free(node); + return -1; +} + +int cond_read_list(policydb_t * p, cond_list_t ** list, void *fp) +{ + cond_node_t *node, *last = NULL; + uint32_t buf[1]; + int i, len, rc; + + rc = next_entry(buf, fp, sizeof(uint32_t)); + if (rc < 0) + return -1; + + len = le32_to_cpu(buf[0]); + + rc = avtab_alloc(&p->te_cond_avtab, p->te_avtab.nel); + if (rc) + goto err; + + for (i = 0; i < len; i++) { + node = malloc(sizeof(cond_node_t)); + if (!node) + goto err; + memset(node, 0, sizeof(cond_node_t)); + + if (cond_read_node(p, node, fp) != 0) + goto err; + + if (i == 0) { + *list = node; + } else { + last->next = node; + } + last = node; + } + return 0; + err: + return -1; +} + +/* Determine whether additional permissions are granted by the conditional + * av table, and if so, add them to the result + */ +void cond_compute_av(avtab_t * ctab, avtab_key_t * key, + struct sepol_av_decision *avd) +{ + avtab_ptr_t node; + + if (!ctab || !key || !avd) + return; + + for (node = avtab_search_node(ctab, key); node != NULL; + node = avtab_search_node_next(node, key->specified)) { + if ((uint16_t) (AVTAB_ALLOWED | AVTAB_ENABLED) == + (node->key.specified & (AVTAB_ALLOWED | AVTAB_ENABLED))) + avd->allowed |= node->datum.data; + if ((uint16_t) (AVTAB_AUDITDENY | AVTAB_ENABLED) == + (node->key.specified & (AVTAB_AUDITDENY | AVTAB_ENABLED))) + /* Since a '0' in an auditdeny mask represents a + * permission we do NOT want to audit (dontaudit), we use + * the '&' operand to ensure that all '0's in the mask + * are retained (much unlike the allow and auditallow cases). + */ + avd->auditdeny &= node->datum.data; + if ((uint16_t) (AVTAB_AUDITALLOW | AVTAB_ENABLED) == + (node->key.specified & (AVTAB_AUDITALLOW | AVTAB_ENABLED))) + avd->auditallow |= node->datum.data; + } + return; +} + +avtab_datum_t *cond_av_list_search(avtab_key_t * key, + cond_av_list_t * cond_list) +{ + + cond_av_list_t *cur_av; + + for (cur_av = cond_list; cur_av != NULL; cur_av = cur_av->next) { + + if (cur_av->node->key.source_type == key->source_type && + cur_av->node->key.target_type == key->target_type && + cur_av->node->key.target_class == key->target_class) + + return &cur_av->node->datum; + + } + return NULL; + +} |