diff options
Diffstat (limited to 'libpoldiff/src/terule_diff.c')
-rw-r--r-- | libpoldiff/src/terule_diff.c | 1329 |
1 files changed, 1329 insertions, 0 deletions
diff --git a/libpoldiff/src/terule_diff.c b/libpoldiff/src/terule_diff.c new file mode 100644 index 0000000..2857403 --- /dev/null +++ b/libpoldiff/src/terule_diff.c @@ -0,0 +1,1329 @@ +/** + * @file + * Implementation for computing semantic differences in AV and Type + * rules. + * + * @author Jeremy A. Mowery jmowery@tresys.com + * @author Jason Tang jtang@tresys.com + * + * Copyright (C) 2006-2007 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 <config.h> + +#include "poldiff_internal.h" + +#include <apol/policy-query.h> +#include <apol/util.h> +#include <qpol/policy_extend.h> +#include <assert.h> +#include <errno.h> +#include <stdio.h> +#include <string.h> + +struct poldiff_terule_summary +{ + size_t num_added; + size_t num_removed; + size_t num_modified; + size_t num_added_type; + size_t num_removed_type; + int diffs_sorted; + /** vector of poldiff_terule_t */ + apol_vector_t *diffs; +}; + +struct poldiff_terule +{ + uint32_t spec; + /* pointer into policy's symbol table */ + const char *source, *target; + /** the class string is pointer into the class_bst BST */ + const char *cls; + poldiff_form_e form; + /* pointer into policy's symbol table */ + const char *orig_default, *mod_default; + /** pointer into policy's conditional list, needed to render + * conditional expressions */ + const qpol_cond_t *cond; + uint32_t branch; + /** vector of unsigned longs of line numbers from original policy */ + apol_vector_t *orig_linenos; + /** vector of unsigned longs of line numbers from modified policy */ + apol_vector_t *mod_linenos; + /** array of pointers for original rules */ + qpol_terule_t **orig_rules; + size_t num_orig_rules; + /** array of pointers for modified rules */ + qpol_terule_t **mod_rules; + size_t num_mod_rules; +}; + +typedef struct pseudo_terule +{ + uint32_t spec; + /** pseudo-type values */ + uint32_t source, target, default_type; + /** pointer into the class_bst BST */ + const char *cls; + /** array of pointers into the bool_bst BST */ + const char *bools[5]; + uint32_t bool_val; + uint32_t branch; + /** pointer into policy's conditional list, needed to render + * conditional expressions */ + const qpol_cond_t *cond; + /** array of qpol_terule_t pointers, for showing line numbers */ + const qpol_terule_t **rules; + size_t num_rules; +} pseudo_terule_t; + +/******************** public terule functions ********************/ + +/** + * Get an array of statistics for the number of differences of each + * form for te rules. + * + * @param diff The policy difference structure from which to get the + * stats. + * @param stats Array into which to write the numbers (array must be + * pre-allocated). The order of the values written to the array is + * as follows: number of items of form POLDIFF_FORM_ADDED, number of + * POLDIFF_FORM_REMOVED, number of POLDIFF_FORM_MODIFIED, number of + * POLDIFF_FORM_ADD_TYPE, and number of POLDIFF_FORM_REMOVE_TYPE. + * @param idx Index into the terule diffs array indicating which rule + * type to reset, one of TERULE_OFFSET_MEMBER, etc. + */ +static void poldiff_terule_get_stats(const poldiff_t * diff, size_t stats[5], unsigned int idx) +{ + if (diff == NULL || stats == NULL) { + ERR(diff, "%s", strerror(EINVAL)); + errno = EINVAL; + return; + } + stats[0] = diff->terule_diffs[idx]->num_added; + stats[1] = diff->terule_diffs[idx]->num_removed; + stats[2] = diff->terule_diffs[idx]->num_modified; + stats[3] = diff->terule_diffs[idx]->num_added_type; + stats[4] = diff->terule_diffs[idx]->num_removed_type; +} + +void poldiff_terule_get_stats_change(const poldiff_t * diff, size_t stats[5]) +{ + poldiff_terule_get_stats(diff, stats, TERULE_OFFSET_CHANGE); +} + +void poldiff_terule_get_stats_member(const poldiff_t * diff, size_t stats[5]) +{ + poldiff_terule_get_stats(diff, stats, TERULE_OFFSET_MEMBER); +} + +void poldiff_terule_get_stats_trans(const poldiff_t * diff, size_t stats[5]) +{ + poldiff_terule_get_stats(diff, stats, TERULE_OFFSET_TRANS); +} + +char *poldiff_terule_to_string(const poldiff_t * diff, const void *terule) +{ + const poldiff_terule_t *pt = (const poldiff_terule_t *)terule; + apol_policy_t *p; + const char *rule_type; + char *diff_char = "", *s = NULL, *cond_expr = NULL; + size_t len = 0; + int error; + if (diff == NULL || terule == NULL) { + ERR(diff, "%s", strerror(EINVAL)); + errno = EINVAL; + return NULL; + } + switch (pt->form) { + case POLDIFF_FORM_ADDED: + case POLDIFF_FORM_ADD_TYPE: + { + diff_char = "+"; + p = diff->mod_pol; + break; + } + case POLDIFF_FORM_REMOVED: + case POLDIFF_FORM_REMOVE_TYPE: + { + diff_char = "-"; + p = diff->orig_pol; + break; + } + case POLDIFF_FORM_MODIFIED: + { + diff_char = "*"; + p = diff->orig_pol; + break; + } + default: + { + ERR(diff, "%s", strerror(ENOTSUP)); + errno = ENOTSUP; + return NULL; + } + } + rule_type = apol_rule_type_to_str(pt->spec); + if (apol_str_appendf(&s, &len, "%s %s %s %s : %s ", diff_char, rule_type, pt->source, pt->target, pt->cls) < 0) { + error = errno; + s = NULL; + goto err; + } + switch (pt->form) { + case POLDIFF_FORM_ADDED: + case POLDIFF_FORM_ADD_TYPE: + { + if (apol_str_append(&s, &len, pt->mod_default) < 0) { + error = errno; + goto err; + } + break; + } + case POLDIFF_FORM_REMOVED: + case POLDIFF_FORM_REMOVE_TYPE: + { + if (apol_str_append(&s, &len, pt->orig_default) < 0) { + error = errno; + goto err; + } + break; + } + case POLDIFF_FORM_MODIFIED: + { + if (apol_str_appendf(&s, &len, "{ -%s +%s }", pt->orig_default, pt->mod_default) < 0) { + error = errno; + goto err; + } + break; + } + default: + { + ERR(diff, "%s", strerror(ENOTSUP)); + errno = ENOTSUP; + return NULL; + } + } + if (apol_str_append(&s, &len, ";") < 0) { + error = errno; + goto err; + } + if (pt->cond != NULL) { + if ((cond_expr = apol_cond_expr_render(p, pt->cond)) == NULL) { + error = errno; + goto err; + } + if (apol_str_appendf(&s, &len, " [%s]:%s", cond_expr, (pt->branch ? "TRUE" : "FALSE")) < 0) { + error = errno; + goto err; + } + free(cond_expr); + } + return s; + err: + free(s); + free(cond_expr); + ERR(diff, "%s", strerror(error)); + errno = error; + return NULL; +} + +/** + * Sort poldiff_terule diff results in a mostly alphabetical order. + */ +static int poldiff_terule_cmp(const void *x, const void *y, void *data __attribute__ ((unused))) +{ + const poldiff_terule_t *a = (const poldiff_terule_t *)x; + const poldiff_terule_t *b = (const poldiff_terule_t *)y; + int compval; + if (a->spec != b->spec) { + const char *rule_type1 = apol_rule_type_to_str(a->spec); + const char *rule_type2 = apol_rule_type_to_str(b->spec); + compval = strcmp(rule_type1, rule_type2); + if (compval != 0) { + return compval; + } + } + if ((compval = strcmp(a->source, b->source)) != 0) { + return compval; + } + if ((compval = strcmp(a->target, b->target)) != 0) { + return compval; + } + if ((compval = strcmp(a->cls, b->cls)) != 0) { + return compval; + } + if (a->cond != b->cond) { + return (int)((char *)a->cond - (char *)b->cond); + } + /* sort true branch before false branch */ + return b->branch - a->branch; +} + +/** + * Get the vector of te rule differences from the te rule difference + * summary. + * + * @param diff The policy difference structure associated with the te + * rule difference summary. + * @param idx Index into the terule diffs array indicating which rule + * type to reset, one of TERULE_OFFSET_MEMBER, etc. + * + * @return A vector of elements of type poldiff_terule_t, or NULL on + * error. The caller should <b>not</b> destroy the vector returned. + * If the call fails, errno will be set. + */ +static const apol_vector_t *poldiff_get_terule_vector(const poldiff_t * diff, terule_offset_e idx) +{ + if (diff == NULL) { + errno = EINVAL; + return NULL; + } + if (diff->terule_diffs[idx]->diffs_sorted == 0) { + apol_vector_sort(diff->terule_diffs[idx]->diffs, poldiff_terule_cmp, NULL); + diff->terule_diffs[idx]->diffs_sorted = 1; + } + return diff->terule_diffs[idx]->diffs; +} + +const apol_vector_t *poldiff_get_terule_vector_member(const poldiff_t * diff) +{ + return poldiff_get_terule_vector(diff, TERULE_OFFSET_MEMBER); +} + +const apol_vector_t *poldiff_get_terule_vector_change(const poldiff_t * diff) +{ + return poldiff_get_terule_vector(diff, TERULE_OFFSET_CHANGE); +} + +const apol_vector_t *poldiff_get_terule_vector_trans(const poldiff_t * diff) +{ + return poldiff_get_terule_vector(diff, TERULE_OFFSET_TRANS); +} + +poldiff_form_e poldiff_terule_get_form(const void *terule) +{ + if (terule == NULL) { + errno = EINVAL; + return 0; + } + return ((const poldiff_terule_t *)terule)->form; +} + +uint32_t poldiff_terule_get_rule_type(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return 0; + } + return terule->spec; +} + +const char *poldiff_terule_get_source_type(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return 0; + } + return terule->source; +} + +const char *poldiff_terule_get_target_type(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return 0; + } + return terule->target; +} + +const char *poldiff_terule_get_object_class(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return 0; + } + return terule->cls; +} + +void poldiff_terule_get_cond(const poldiff_t * diff, const poldiff_terule_t * terule, + const qpol_cond_t ** cond, uint32_t * which_list, const apol_policy_t ** p) +{ + if (diff == NULL || terule == NULL || cond == NULL || p == NULL) { + errno = EINVAL; + return; + } + *cond = terule->cond; + if (*cond == NULL) { + *which_list = 1; + *p = NULL; + } else if (terule->form == POLDIFF_FORM_ADDED || terule->form == POLDIFF_FORM_ADD_TYPE) { + *which_list = terule->branch; + *p = diff->mod_pol; + } else { + *which_list = terule->branch; + *p = diff->orig_pol; + } +} + +const char *poldiff_terule_get_original_default(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return 0; + } + return terule->orig_default; +} + +const char *poldiff_terule_get_modified_default(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return 0; + } + return terule->mod_default; +} + +apol_vector_t *poldiff_terule_get_orig_line_numbers(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return NULL; + } + return terule->orig_linenos; +} + +apol_vector_t *poldiff_terule_get_mod_line_numbers(const poldiff_terule_t * terule) +{ + if (terule == NULL) { + errno = EINVAL; + return NULL; + } + return terule->mod_linenos; +} + +/*************** protected functions ***************/ + +/** + * Free all space used by a poldiff_terule_t, including the pointer + * itself. Does nothing if the pointer is already NULL. + * + * @param elem Pointer to a poldiff_terule_t. + */ +static void poldiff_terule_free(void *elem) +{ + if (elem != NULL) { + poldiff_terule_t *t = elem; + apol_vector_destroy(&t->orig_linenos); + apol_vector_destroy(&t->mod_linenos); + free(t->orig_rules); + free(t->mod_rules); + free(elem); + } +} + +poldiff_terule_summary_t *terule_create(void) +{ + poldiff_terule_summary_t *rs = calloc(1, sizeof(*rs)); + if (rs == NULL) { + return NULL; + } + if ((rs->diffs = apol_vector_create(poldiff_terule_free)) == NULL) { + terule_destroy(&rs); + return NULL; + } + return rs; +} + +void terule_destroy(poldiff_terule_summary_t ** rs) +{ + if (rs != NULL && *rs != NULL) { + apol_vector_destroy(&(*rs)->diffs); + free(*rs); + *rs = NULL; + } +} + +/** + * Reset the state of all TE rule differences. + * @param diff The policy difference structure containing the differences + * to reset. + * @param idx Index into the terule diffs array indicating which rule + * type to reset, one of TERULE_OFFSET_CHANGE, etc. + * @return 0 on success and < 0 on error; if the call fails, + * errno will be set and the user should call poldiff_destroy() on diff. + */ +static int terule_reset(poldiff_t * diff, terule_offset_e idx) +{ + int error = 0; + terule_destroy(&diff->terule_diffs[idx]); + diff->terule_diffs[idx] = terule_create(); + if (diff->terule_diffs[idx] == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + errno = error; + return -1; + } + return 0; +} + +int terule_reset_change(poldiff_t * diff) +{ + return terule_reset(diff, TERULE_OFFSET_CHANGE); +} + +int terule_reset_member(poldiff_t * diff) +{ + return terule_reset(diff, TERULE_OFFSET_MEMBER); +} + +int terule_reset_trans(poldiff_t * diff) +{ + return terule_reset(diff, TERULE_OFFSET_TRANS); +} + +static void terule_free_item(void *item) +{ + pseudo_terule_t *t = (pseudo_terule_t *) item; + if (item != NULL) { + free(t->rules); + free(t); + } +} + +/** + * Apply an ordering scheme to two pseudo-te rules. + * + * <ul> + * <li>Sort by target pseudo-type value, + * <li>Then by source pseudo-type value, + * <li>Then by object class's BST's pointer value, + * <li>Then by rule specified (allow, neverallow, etc.), + * <li>Then choose unconditional rules over conditional rules, + * <li>Then by conditional expression's BST's boolean pointer value. + * </ul> + * + * If this function is being used for sorting (via terule_get_items()) + * then sort by truth value, and then by branch (true branch, then + * false branch). Otherwise, when comparing rules (via terule_comp()) + * then by truth value, inverting rule2's value if in the other + * branch. + */ +static int pseudo_terule_comp(const pseudo_terule_t * rule1, const pseudo_terule_t * rule2, int is_sorting) +{ + size_t i; + uint32_t bool_val; + if (rule1->target != rule2->target) { + return rule1->target - rule2->target; + } + if (rule1->source != rule2->source) { + return rule1->source - rule2->source; + } + if (rule1->cls != rule2->cls) { + return (int)(rule1->cls - rule2->cls); + } + if (rule1->spec != rule2->spec) { + return rule1->spec - rule2->spec; + } + if (rule1->bools[0] == NULL && rule2->bools[0] == NULL) { + /* both rules are unconditional */ + return 0; + } else if (rule1->bools[0] == NULL && rule2->bools[0] != NULL) { + /* unconditional rules come before conditional */ + return -1; + } else if (rule1->bools[0] != NULL && rule2->bools[0] == NULL) { + /* unconditional rules come before conditional */ + return 1; + } + for (i = 0; i < (sizeof(rule1->bools) / sizeof(rule1->bools[0])); i++) { + if (rule1->bools[i] != rule2->bools[i]) { + return (int)(rule1->bools[i] - rule2->bools[i]); + } + } + if (is_sorting) { + if (rule1->branch != rule2->branch) { + return rule1->branch - rule2->branch; + } + return (int)rule1->bool_val - (int)rule2->bool_val; + } else { + if (rule1->branch == rule2->branch) { + bool_val = rule2->bool_val; + } else { + bool_val = ~rule2->bool_val; + } + if (rule1->bool_val < bool_val) { + return -1; + } else if (rule1->bool_val > bool_val) { + return 1; + } + return 0; + } +} + +static int terule_bst_comp(const void *x, const void *y, void *data) +{ + const pseudo_terule_t *r1 = (const pseudo_terule_t *)x; + const pseudo_terule_t *r2 = (const pseudo_terule_t *)y; + poldiff_t *diff = data; + int retv; + retv = pseudo_terule_comp(r1, r2, 1); + if (!retv && r1->default_type != r2->default_type) + WARN(diff, "Multiple %s rules for %s %s %s with different default types", apol_rule_type_to_str(r1->spec), + type_map_get_name(diff, r1->source, POLDIFF_POLICY_ORIG), type_map_get_name(diff, r1->target, + POLDIFF_POLICY_ORIG), r1->cls); + return retv; +} + +/** + * Given a conditional expression, convert its booleans to a sorted + * array of pseudo-boolean values, assign that array to the + * pseudo-terule key, and then derive the truth table. + * + * @param diff Policy difference structure. + * @param p Policy containing conditional. + * @param cond Conditional expression to convert. + * @param key Location to write converted expression. + */ +static int terule_build_cond(const poldiff_t * diff, const apol_policy_t * p, const qpol_cond_t * cond, pseudo_terule_t * key) +{ + qpol_iterator_t *iter = NULL; + qpol_cond_expr_node_t *node; + uint32_t expr_type, truthiness; + qpol_bool_t *bools[5] = { NULL, NULL, NULL, NULL, NULL }, *qbool; + size_t i, j; + size_t num_bools = 0; + const char *bool_name, *pseudo_bool, *t; + qpol_policy_t *q = apol_policy_get_qpol(p); + int retval = -1, error = 0, compval; + if (qpol_cond_get_expr_node_iter(q, cond, &iter) < 0) { + error = errno; + goto cleanup; + } + for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) { + if (qpol_iterator_get_item(iter, (void **)&node) < 0 || qpol_cond_expr_node_get_expr_type(q, node, &expr_type) < 0) { + error = errno; + goto cleanup; + } + if (expr_type != QPOL_COND_EXPR_BOOL) { + continue; + } + if (qpol_cond_expr_node_get_bool(q, node, &qbool) < 0) { + error = errno; + goto cleanup; + } + for (i = 0; i < num_bools; i++) { + if (bools[i] == qbool) { + break; + } + } + if (i >= num_bools) { + assert(i < 5); + bools[i] = qbool; + num_bools++; + } + } + for (i = 0; i < num_bools; i++) { + if (qpol_bool_get_name(q, bools[i], &bool_name) < 0) { + error = errno; + goto cleanup; + } + if (apol_bst_get_element(diff->bool_bst, (void *)bool_name, NULL, (void **)&pseudo_bool) < 0) { + error = EBADRQC; /* should never get here */ + ERR(diff, "%s", strerror(error)); + assert(0); + goto cleanup; + } + key->bools[i] = pseudo_bool; + } + + /* bubble sorth the pseudo bools (not bad because there are at + * most five elements */ + for (i = num_bools; i > 1; i--) { + for (j = 1; j < i; j++) { + compval = strcmp(key->bools[j - 1], key->bools[j]); + if (compval > 0) { + t = key->bools[j]; + key->bools[j] = key->bools[j - 1]; + key->bools[j - 1] = t; + qbool = bools[j]; + bools[j] = bools[j - 1]; + bools[j - 1] = qbool; + } + } + } + + /* now compute the truth table for the booleans */ + key->bool_val = 0; + for (i = 0; i < 32; i++) { + for (j = 0; j < num_bools; j++) { + int state = ((i & (1 << j)) ? 1 : 0); + if (qpol_bool_set_state_no_eval(q, bools[j], state) < 0) { + error = errno; + goto cleanup; + } + } + if (qpol_cond_eval(q, cond, &truthiness) < 0) { + error = errno; + goto cleanup; + } + key->bool_val = (key->bool_val << 1) | truthiness; + } + + key->cond = cond; + retval = 0; + cleanup: + qpol_iterator_destroy(&iter); + return retval; +} + +/** + * Given a rule, construct a new pseudo-terule and insert it into the + * BST if not already there. + * + * @param diff Policy difference structure. + * @param p Policy from which the rule came. + * @param rule TE rule to insert. + * @param source Source pseudo-type value. + * @param target Target pseudo-type value. + * @param b BST containing pseudo-terules. + * + * @return 0 on success, < 0 on error. + */ +static int terule_add_to_bst(poldiff_t * diff, const apol_policy_t * p, + const qpol_terule_t * rule, uint32_t source, uint32_t target, apol_bst_t * b) +{ + pseudo_terule_t *key, *inserted_key; + const qpol_class_t *obj_class; + const qpol_type_t *default_type; + const char *class_name; + const qpol_cond_t *cond; + qpol_policy_t *q = apol_policy_get_qpol(p); + int retval = -1, error = 0, compval; + int which = (p == diff->orig_pol ? POLDIFF_POLICY_ORIG : POLDIFF_POLICY_MOD); + if ((key = calloc(1, sizeof(*key))) == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + if (qpol_terule_get_rule_type(q, rule, &(key->spec)) < 0 || + qpol_terule_get_object_class(q, rule, &obj_class) < 0 || + qpol_terule_get_default_type(q, rule, &default_type) < 0 || qpol_terule_get_cond(q, rule, &cond) < 0) { + error = errno; + goto cleanup; + } + if (qpol_class_get_name(q, obj_class, &class_name) < 0) { + error = errno; + goto cleanup; + } + if (apol_bst_get_element(diff->class_bst, (void *)class_name, NULL, (void **)&key->cls) < 0) { + error = EBADRQC; /* should never get here */ + ERR(diff, "%s", strerror(error)); + assert(0); + goto cleanup; + } + if ((key->default_type = type_map_lookup(diff, default_type, which)) == 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + key->source = source; + key->target = target; + if (cond != NULL && (qpol_terule_get_which_list(q, rule, &(key->branch)) < 0 || terule_build_cond(diff, p, cond, key) < 0)) { + error = errno; + goto cleanup; + } + + /* insert this pseudo into the tree if not already there */ + if ((compval = apol_bst_insert_and_get(b, (void **)&key, diff)) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + inserted_key = key; + key = NULL; + + /* store the rule pointer, to be used for showing line numbers */ + if (qpol_policy_has_capability(q, QPOL_CAP_LINE_NUMBERS)) { + const qpol_terule_t **t = realloc(inserted_key->rules, + (inserted_key->num_rules + 1) * sizeof(*t)); + if (t == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + inserted_key->rules = t; + inserted_key->rules[inserted_key->num_rules++] = rule; + } + + retval = 0; + cleanup: + if (retval < 0) { + terule_free_item(key); + } + errno = error; + return retval; +} + +/** + * Given a rule, expand its source and target types into individual + * pseudo-type values. Then add the expanded rule to the BST. This + * is needed for when the source and/or target is an attribute. + * + * @param diff Policy difference structure. + * @param p Policy from which the rule came. + * @param rule TE rule to insert. + * @param b BST containing pseudo-terules. + * + * @return 0 on success, < 0 on error. + */ +static int terule_expand(poldiff_t * diff, const apol_policy_t * p, const qpol_terule_t * rule, apol_bst_t * b) +{ + const qpol_type_t *source, *orig_target, *target; + unsigned char source_attr, target_attr; + qpol_iterator_t *source_iter = NULL, *target_iter = NULL; + uint32_t source_val, target_val; + qpol_policy_t *q = apol_policy_get_qpol(p); + int which = (p == diff->orig_pol ? POLDIFF_POLICY_ORIG : POLDIFF_POLICY_MOD); + int retval = -1, error = 0; + if (qpol_terule_get_source_type(q, rule, &source) < 0 || + qpol_terule_get_target_type(q, rule, &orig_target) < 0 || + qpol_type_get_isattr(q, source, &source_attr) < 0 || qpol_type_get_isattr(q, orig_target, &target_attr)) { + error = errno; + goto cleanup; + } + if (source_attr && qpol_type_get_type_iter(q, source, &source_iter) < 0) { + error = errno; + goto cleanup; + } + do { + if (source_attr) { + if (qpol_iterator_get_item(source_iter, (void **)&source) < 0) { + error = errno; + goto cleanup; + } + qpol_iterator_next(source_iter); + } + if (target_attr) { + if (qpol_type_get_type_iter(q, orig_target, &target_iter) < 0) { + error = errno; + goto cleanup; + } + } else { + target = orig_target; + } + do { + if (target_attr) { + if (qpol_iterator_get_item(target_iter, (void **)&target) < 0) { + error = errno; + goto cleanup; + } + qpol_iterator_next(target_iter); + } + const char *n1, *n2; + qpol_type_get_name(q, source, &n1); + qpol_type_get_name(q, target, &n2); + if ((source_val = type_map_lookup(diff, source, which)) == 0 || + (target_val = type_map_lookup(diff, target, which)) == 0 || + terule_add_to_bst(diff, p, rule, source_val, target_val, b) < 0) { + error = errno; + goto cleanup; + } + } while (target_attr && !qpol_iterator_end(target_iter)); + qpol_iterator_destroy(&target_iter); + } while (source_attr && !qpol_iterator_end(source_iter)); + retval = 0; + cleanup: + qpol_iterator_destroy(&source_iter); + qpol_iterator_destroy(&target_iter); + errno = error; + return retval; +} + +/** + * Get a vector of terules from the given policy, sorted. This + * function will remap source and target types to their pseudo-type + * value equivalents. + * + * @param diff Policy diff error handler. + * @param policy The policy from which to get the items. + * @param which Kind of rule to get, one of QPOL_RULE_TYPE_TRANS, etc. + * + * @return A newly allocated vector of all te rules (of type + * pseudo_terule_t). The caller is responsible for calling + * apol_vector_destroy() afterwards. On error, return NULL and set + * errno. + */ +static apol_vector_t *terule_get_items(poldiff_t * diff, const apol_policy_t * policy, unsigned int which) +{ + apol_vector_t *bools = NULL, *bool_states = NULL; + size_t i, num_rules, j; + apol_bst_t *b = NULL; + apol_vector_t *v = NULL; + qpol_iterator_t *iter = NULL; + qpol_terule_t *rule; + qpol_policy_t *q = apol_policy_get_qpol(policy); + int retval = -1, error = 0; + if (poldiff_build_bsts(diff) < 0) { + error = errno; + goto cleanup; + } + + /* store original boolean values */ + if (apol_bool_get_by_query(policy, NULL, &bools) < 0) { + error = errno; + goto cleanup; + } + if ((bool_states = apol_vector_create_with_capacity(apol_vector_get_size(bools), NULL)) == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + for (i = 0; i < apol_vector_get_size(bools); i++) { + qpol_bool_t *qbool = apol_vector_get_element(bools, i); + int state; + if (qpol_bool_get_state(q, qbool, &state) < 0) { + error = errno; + goto cleanup; + } + if (apol_vector_append(bool_states, (void *)((size_t) state)) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + } + if ((b = apol_bst_create(terule_bst_comp, terule_free_item)) == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + if (qpol_policy_get_terule_iter(q, which, &iter) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + qpol_iterator_get_size(iter, &num_rules); + for (j = 0; !qpol_iterator_end(iter); qpol_iterator_next(iter), j++) { + if (qpol_iterator_get_item(iter, (void **)&rule) < 0 || terule_expand(diff, policy, rule, b) < 0) { + error = errno; + goto cleanup; + } + if (!(j % 1024)) { + int percent = 50 * j / num_rules + (policy == diff->mod_pol ? 50 : 0); + INFO(diff, "Computing TE rule difference: %02d%% complete", percent); + } + } + if ((v = apol_bst_get_vector(b, 1)) == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + retval = 0; + cleanup: + /* restore boolean states */ + for (i = 0; bools != NULL && i < apol_vector_get_size(bools); i++) { + qpol_bool_t *qbool = apol_vector_get_element(bools, i); + int state = (int)((size_t) apol_vector_get_element(bool_states, i)); + qpol_bool_set_state_no_eval(q, qbool, state); + } + apol_vector_destroy(&bools); + apol_vector_destroy(&bool_states); + qpol_policy_reevaluate_conds(q); + apol_bst_destroy(&b); + qpol_iterator_destroy(&iter); + if (retval < 0) { + apol_vector_destroy(&v); + errno = error; + return NULL; + } + return v; +} + +apol_vector_t *terule_get_items_change(poldiff_t * diff, const apol_policy_t * policy) +{ + return terule_get_items(diff, policy, QPOL_RULE_TYPE_CHANGE); +} + +apol_vector_t *terule_get_items_member(poldiff_t * diff, const apol_policy_t * policy) +{ + return terule_get_items(diff, policy, QPOL_RULE_TYPE_MEMBER); +} + +apol_vector_t *terule_get_items_trans(poldiff_t * diff, const apol_policy_t * policy) +{ + return terule_get_items(diff, policy, QPOL_RULE_TYPE_TRANS); +} + +int terule_comp(const void *x, const void *y, const poldiff_t * diff __attribute__ ((unused))) +{ + const pseudo_terule_t *r1 = (const pseudo_terule_t *)x; + const pseudo_terule_t *r2 = (const pseudo_terule_t *)y; + return pseudo_terule_comp(r1, r2, 0); +} + +/** + * Allocate and return a new terule difference object. If the + * pseudo-terule's source and/or target expands to multiple read + * types, then just choose the first one for display. + * + * @param diff Policy diff error handler. + * @param form Form of the difference. + * @param rule Pseudo terule that changed. + * + * @return A newly allocated and initialized diff, or NULL upon error. + * The caller is responsible for calling poldiff_terule_free() upon + * the returned value. + */ +static poldiff_terule_t *make_tediff(const poldiff_t * diff, poldiff_form_e form, const pseudo_terule_t * rule) +{ + poldiff_terule_t *pt; + const char *n1, *n2; + int error; + if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) { + n1 = type_map_get_name(diff, rule->source, POLDIFF_POLICY_MOD); + n2 = type_map_get_name(diff, rule->target, POLDIFF_POLICY_MOD); + } else { + n1 = type_map_get_name(diff, rule->source, POLDIFF_POLICY_ORIG); + n2 = type_map_get_name(diff, rule->target, POLDIFF_POLICY_ORIG); + } + assert(n1 != NULL && n2 != NULL); + if ((pt = calloc(1, sizeof(*pt))) == NULL) { + error = errno; + poldiff_terule_free(pt); + ERR(diff, "%s", strerror(error)); + errno = error; + return NULL; + } + pt->spec = rule->spec; + pt->source = n1; + pt->target = n2; + pt->cls = rule->cls; + pt->form = form; + pt->cond = rule->cond; + pt->branch = rule->branch; + return pt; +} + +/** + * Create, initialize, and insert a new semantic difference entry for + * a pseudo-te rule. + * + * @param diff The policy difference structure to which to add the entry. + * @param form The form of the difference. + * @param item Item for which the entry is being created. + * @param idx Index into the terule differences specifying int which + * to place the constructed pseudo-te rule. + * @return 0 on success and < 0 on error; if the call fails, set errno + * and leave the policy difference structure unchanged. + */ +static int terule_new_diff(poldiff_t * diff, poldiff_form_e form, const void *item, terule_offset_e idx) +{ + pseudo_terule_t *rule = (pseudo_terule_t *) item; + poldiff_terule_t *pt = NULL; + const apol_vector_t *v1, *v2; + apol_policy_t *p; + const char *orig_default = NULL, *mod_default = NULL; + int retval = -1, error = errno; + + /* check if form should really become ADD_TYPE / REMOVE_TYPE, + * by seeing if the /other/ policy's reverse lookup is + * empty */ + if (form == POLDIFF_FORM_ADDED) { + if ((v1 = type_map_lookup_reverse(diff, rule->source, POLDIFF_POLICY_ORIG)) == NULL || + (v2 = type_map_lookup_reverse(diff, rule->target, POLDIFF_POLICY_ORIG)) == NULL || + (mod_default = type_map_get_name(diff, rule->default_type, POLDIFF_POLICY_MOD)) == NULL) { + error = errno; + goto cleanup; + } + if (apol_vector_get_size(v1) == 0 || apol_vector_get_size(v2) == 0) { + form = POLDIFF_FORM_ADD_TYPE; + } + p = diff->mod_pol; + } else { + if ((v1 = type_map_lookup_reverse(diff, rule->source, POLDIFF_POLICY_MOD)) == NULL || + (v2 = type_map_lookup_reverse(diff, rule->target, POLDIFF_POLICY_MOD)) == NULL || + (orig_default = type_map_get_name(diff, rule->default_type, POLDIFF_POLICY_ORIG)) == NULL) { + error = errno; + goto cleanup; + } + if (apol_vector_get_size(v1) == 0 || apol_vector_get_size(v2) == 0) { + form = POLDIFF_FORM_REMOVE_TYPE; + } + p = diff->orig_pol; + } + + pt = make_tediff(diff, form, rule); + if (pt == NULL) { + return -1; + } + pt->orig_default = orig_default; + pt->mod_default = mod_default; + + /* calculate line numbers */ + if (qpol_policy_has_capability(apol_policy_get_qpol(p), QPOL_CAP_LINE_NUMBERS)) { + apol_vector_t *vl = NULL; + if ((vl = apol_vector_create(NULL)) == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) { + pt->mod_linenos = vl; + } else { + pt->orig_linenos = vl; + } + + /* copy rule pointers for delayed line number claculation */ + if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) { + pt->num_mod_rules = rule->num_rules; + pt->mod_rules = calloc(rule->num_rules, sizeof(qpol_terule_t *)); + if (!pt->mod_rules) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + memcpy(pt->mod_rules, rule->rules, rule->num_rules * sizeof(qpol_terule_t *)); + } else { + pt->num_orig_rules = rule->num_rules; + pt->orig_rules = calloc(rule->num_rules, sizeof(qpol_terule_t *)); + if (!pt->orig_rules) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + memcpy(pt->orig_rules, rule->rules, rule->num_rules * sizeof(qpol_terule_t *)); + } + } + + if (apol_vector_append(diff->terule_diffs[idx]->diffs, pt) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + switch (form) { + case POLDIFF_FORM_ADDED: + diff->terule_diffs[idx]->num_added++; + break; + case POLDIFF_FORM_ADD_TYPE: + diff->terule_diffs[idx]->num_added_type++; + break; + case POLDIFF_FORM_REMOVED: + diff->terule_diffs[idx]->num_removed++; + break; + case POLDIFF_FORM_REMOVE_TYPE: + diff->terule_diffs[idx]->num_removed_type++; + break; + default: + error = EBADRQC; /* should never get here */ + ERR(diff, "%s", strerror(error)); + assert(0); + goto cleanup; + } + diff->terule_diffs[idx]->diffs_sorted = 0; + retval = 0; + cleanup: + if (retval < 0) { + poldiff_terule_free(pt); + } + errno = error; + return retval; +} + +int terule_new_diff_change(poldiff_t * diff, poldiff_form_e form, const void *item) +{ + return terule_new_diff(diff, form, item, TERULE_OFFSET_CHANGE); +} + +int terule_new_diff_member(poldiff_t * diff, poldiff_form_e form, const void *item) +{ + return terule_new_diff(diff, form, item, TERULE_OFFSET_MEMBER); +} + +int terule_new_diff_trans(poldiff_t * diff, poldiff_form_e form, const void *item) +{ + return terule_new_diff(diff, form, item, TERULE_OFFSET_TRANS); +} + +/** + * Compute the semantic difference of two pseudo-te rules for which + * the compare callback returns 0. If a difference is found then + * allocate, initialize, and insert a new semantic difference entry + * for that pseudo-te rule. + * + * @param diff The policy difference structure associated with both + * pseudo-te rules and to which to add an entry if needed. + * @param x The pseudo-te rule from the original policy. + * @param y The pseudo-te rule from the modified policy. + * @param idx Index into the terule differences specifying into which + * to place the constructed pseudo-ate rule. + * + * @return 0 on success and < 0 on error; if the call fails, set errno + * and leave the policy difference structure unchanged. + */ +static int terule_deep_diff(poldiff_t * diff, const void *x, const void *y, terule_offset_e idx) +{ + pseudo_terule_t *r1 = (pseudo_terule_t *) x; + pseudo_terule_t *r2 = (pseudo_terule_t *) y; + poldiff_terule_t *pt = NULL; + int retval = -1, error = 0; + + if (r1->default_type != r2->default_type) { + if ((pt = make_tediff(diff, POLDIFF_FORM_MODIFIED, r1)) == NULL) { + error = errno; + goto cleanup; + } + pt->orig_default = type_map_get_name(diff, r1->default_type, POLDIFF_POLICY_ORIG); + pt->mod_default = type_map_get_name(diff, r2->default_type, POLDIFF_POLICY_MOD); + + /* calculate line numbers */ + if (qpol_policy_has_capability(apol_policy_get_qpol(diff->orig_pol), QPOL_CAP_LINE_NUMBERS)) { + if ((pt->orig_linenos = apol_vector_create(NULL)) == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + + /* copy rule pointers for delayed line number claculation */ + pt->num_orig_rules = r1->num_rules; + pt->orig_rules = calloc(r1->num_rules, sizeof(qpol_terule_t *)); + if (!pt->orig_rules) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + memcpy(pt->orig_rules, r1->rules, r1->num_rules * sizeof(qpol_terule_t *)); + } + if (qpol_policy_has_capability(apol_policy_get_qpol(diff->mod_pol), QPOL_CAP_LINE_NUMBERS)) { + if ((pt->mod_linenos = apol_vector_create(NULL)) == NULL) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + + /* copy rule pointers for delayed line number claculation */ + pt->num_mod_rules = r2->num_rules; + pt->mod_rules = calloc(r2->num_rules, sizeof(qpol_terule_t *)); + if (!pt->mod_rules) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + memcpy(pt->mod_rules, r2->rules, r2->num_rules * sizeof(qpol_terule_t *)); + } + + if (apol_vector_append(diff->terule_diffs[idx]->diffs, pt) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto cleanup; + } + diff->terule_diffs[idx]->num_modified++; + diff->terule_diffs[idx]->diffs_sorted = 0; + } + retval = 0; + cleanup: + if (retval != 0) { + poldiff_terule_free(pt); + } + errno = error; + return retval; +} + +int terule_deep_diff_change(poldiff_t * diff, const void *x, const void *y) +{ + return terule_deep_diff(diff, x, y, TERULE_OFFSET_CHANGE); +} + +int terule_deep_diff_member(poldiff_t * diff, const void *x, const void *y) +{ + return terule_deep_diff(diff, x, y, TERULE_OFFSET_MEMBER); +} + +int terule_deep_diff_trans(poldiff_t * diff, const void *x, const void *y) +{ + return terule_deep_diff(diff, x, y, TERULE_OFFSET_TRANS); +} + +int terule_enable_line_numbers(poldiff_t * diff, terule_offset_e idx) +{ + const apol_vector_t *te = NULL; + poldiff_terule_t *terule = NULL; + size_t i, j; + qpol_iterator_t *iter = NULL; + qpol_syn_terule_t *ste = NULL; + int error = 0; + unsigned long lineno = 0; + + te = poldiff_get_terule_vector(diff, idx); + + for (i = 0; i < apol_vector_get_size(te); i++) { + terule = apol_vector_get_element(te, i); + if (apol_vector_get_size(terule->mod_linenos) || apol_vector_get_size(terule->orig_linenos)) + continue; + for (j = 0; j < terule->num_orig_rules; j++) { + if (qpol_terule_get_syn_terule_iter(diff->orig_qpol, terule->orig_rules[j], &iter)) { + error = errno; + goto err; + } + for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) { + if (qpol_iterator_get_item(iter, (void **)&ste) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto err; + } + if (qpol_syn_terule_get_lineno(diff->orig_qpol, ste, &lineno) < 0) { + error = errno; + goto err; + } + if (apol_vector_append(terule->orig_linenos, (void *)lineno) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto err; + } + } + qpol_iterator_destroy(&iter); + } + apol_vector_sort_uniquify(terule->orig_linenos, NULL, NULL); + for (j = 0; j < terule->num_mod_rules; j++) { + if (qpol_terule_get_syn_terule_iter(diff->mod_qpol, terule->mod_rules[j], &iter)) { + error = errno; + goto err; + } + for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) { + if (qpol_iterator_get_item(iter, (void **)&ste) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto err; + } + if (qpol_syn_terule_get_lineno(diff->mod_qpol, ste, &lineno) < 0) { + error = errno; + goto err; + } + if (apol_vector_append(terule->mod_linenos, (void *)lineno) < 0) { + error = errno; + ERR(diff, "%s", strerror(error)); + goto err; + } + } + qpol_iterator_destroy(&iter); + } + apol_vector_sort_uniquify(terule->mod_linenos, NULL, NULL); + } + + return 0; + err: + qpol_iterator_destroy(&iter); + return -1; +} |