diff options
Diffstat (limited to 'libpoldiff/src/range_diff.c')
| -rw-r--r-- | libpoldiff/src/range_diff.c | 420 |
1 files changed, 420 insertions, 0 deletions
diff --git a/libpoldiff/src/range_diff.c b/libpoldiff/src/range_diff.c new file mode 100644 index 0000000..e6c7c3a --- /dev/null +++ b/libpoldiff/src/range_diff.c @@ -0,0 +1,420 @@ +/** + * @file + * Implementation for computing semantic differences in ranges. + * + * @author Jeremy A. Mowery jmowery@tresys.com + * @author Jason Tang jtang@tresys.com + * + * Copyright (C) 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/util.h> +#include <assert.h> +#include <errno.h> + +struct poldiff_range +{ + apol_mls_range_t *orig_range; + apol_mls_range_t *mod_range; + /** a vector of poldiff_level_t */ + apol_vector_t *levels; + apol_vector_t *min_added_cats; + apol_vector_t *min_removed_cats; + apol_vector_t *min_unmodified_cats; +}; + +apol_vector_t *poldiff_range_get_levels(const poldiff_range_t * range) +{ + if (range == NULL) { + errno = EINVAL; + return NULL; + } + return range->levels; +} + +const apol_mls_range_t *poldiff_range_get_original_range(const poldiff_range_t * range) +{ + if (range == NULL) { + errno = EINVAL; + return NULL; + } + return range->orig_range; +} + +const apol_mls_range_t *poldiff_range_get_modified_range(const poldiff_range_t * range) +{ + if (range == NULL) { + errno = EINVAL; + return NULL; + } + return range->mod_range; +} + +apol_vector_t *poldiff_range_get_min_added_cats(const poldiff_range_t * range) +{ + if (range == NULL) { + errno = EINVAL; + return NULL; + } + return range->min_added_cats; +} + +apol_vector_t *poldiff_range_get_min_removed_cats(const poldiff_range_t * range) +{ + if (range == NULL) { + errno = EINVAL; + return NULL; + } + return range->min_removed_cats; +} + +apol_vector_t *poldiff_range_get_min_unmodified_cats(const poldiff_range_t * range) +{ + if (range == NULL) { + errno = EINVAL; + return NULL; + } + return range->min_unmodified_cats; +} + +char *poldiff_range_to_string_brief(const poldiff_t * diff, const poldiff_range_t * range) +{ + char *r1 = NULL, *r2 = NULL; + char *s = NULL, *t = NULL, *sep = "", *cat; + size_t len = 0, i; + if (range->orig_range != NULL && (r1 = apol_mls_range_render(diff->orig_pol, range->orig_range)) == NULL) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + if (range->mod_range != NULL && (r2 = apol_mls_range_render(diff->mod_pol, range->mod_range)) == NULL) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + assert(r1 != NULL || r2 != NULL); + if (r1 == NULL) { + if (apol_str_appendf(&s, &len, " range: %s\n", r2) < 0) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + } else if (r2 == NULL) { + if (apol_str_appendf(&s, &len, " range: %s\n", r1) < 0) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + } else { + if (apol_str_appendf(&s, &len, " range: %s --> %s\n", r1, r2) < 0) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + } + if ((range->min_added_cats != NULL && apol_vector_get_size(range->min_added_cats) > 0) || + (range->min_removed_cats != NULL && apol_vector_get_size(range->min_removed_cats) > 0) || + (range->min_unmodified_cats != NULL && apol_vector_get_size(range->min_unmodified_cats) > 0)) { + if (apol_str_append(&s, &len, " minimum categories: ") < 0) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + for (i = 0; range->min_unmodified_cats != NULL && i < apol_vector_get_size(range->min_unmodified_cats); i++) { + cat = apol_vector_get_element(range->min_unmodified_cats, i); + if (apol_str_appendf(&s, &len, "%s%s", sep, cat) < 0) { + ERR(diff, "%s", strerror(errno)); + return NULL; + } + sep = ","; + } + for (i = 0; range->min_added_cats != NULL && i < apol_vector_get_size(range->min_added_cats); i++) { + cat = apol_vector_get_element(range->min_added_cats, i); + if (apol_str_appendf(&s, &len, "%s+%s", sep, cat) < 0) { + ERR(diff, "%s", strerror(errno)); + return NULL; + } + sep = ","; + } + for (i = 0; range->min_removed_cats != NULL && i < apol_vector_get_size(range->min_removed_cats); i++) { + cat = apol_vector_get_element(range->min_removed_cats, i); + if (apol_str_appendf(&s, &len, "%s-%s", sep, cat) < 0) { + ERR(diff, "%s", strerror(errno)); + return NULL; + } + sep = ","; + } + if (apol_str_append(&s, &len, "\n") < 0) { + ERR(diff, "%s", strerror(errno)); + return NULL; + } + } + for (i = 0; i < apol_vector_get_size(range->levels); i++) { + poldiff_level_t *level = apol_vector_get_element(range->levels, i); + if ((t = poldiff_level_to_string_brief(diff, level)) == NULL) { + goto cleanup; + } + if (apol_str_appendf(&s, &len, " %s", t) < 0) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + free(t); + t = NULL; + } + cleanup: + free(r1); + free(r2); + free(t); + return s; +} + +poldiff_range_t *range_create(const poldiff_t * diff, const qpol_mls_range_t * orig_range, const qpol_mls_range_t * mod_range, + poldiff_form_e form) +{ + poldiff_range_t *pr = NULL; + apol_policy_t *p; + apol_mls_range_t *range; + apol_vector_t *levels = NULL; + poldiff_level_t *pl = NULL; + size_t i; + int retval = -1; + if ((pr = calloc(1, sizeof(*pr))) == NULL || (pr->levels = apol_vector_create(level_free)) == NULL) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + if (orig_range != NULL && (pr->orig_range = apol_mls_range_create_from_qpol_mls_range(diff->orig_pol, orig_range)) == NULL) { + goto cleanup; + } + if (mod_range != NULL && (pr->mod_range = apol_mls_range_create_from_qpol_mls_range(diff->mod_pol, mod_range)) == NULL) { + goto cleanup; + } + if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) { + p = diff->mod_pol; + range = pr->mod_range; + } else if (form == POLDIFF_FORM_REMOVED || form == POLDIFF_FORM_REMOVE_TYPE) { + p = diff->orig_pol; + range = pr->orig_range; + } else if (form == POLDIFF_FORM_MODIFIED) { + /* don't fill in the range's levels here */ + return pr; + } else { + /* should never get here */ + assert(0); + return pr; + } + if ((levels = apol_mls_range_get_levels(p, range)) == NULL) { + goto cleanup; + } + for (i = 0; i < apol_vector_get_size(levels); i++) { + apol_mls_level_t *l = apol_vector_get_element(levels, i); + const char *sens = apol_mls_level_get_sens(l); + const apol_vector_t *cats = apol_mls_level_get_cats(l); + if ((pl = calloc(1, sizeof(*pl))) == NULL || + (pl->name = strdup(sens)) == NULL || (pl->unmodified_cats = apol_vector_create_with_capacity(1, free)) == NULL) + { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + if (form == POLDIFF_FORM_ADDED) { + if ((pl->added_cats = apol_vector_create_from_vector(cats, apol_str_strdup, NULL, free)) == NULL || + (pl->removed_cats = apol_vector_create_with_capacity(1, free)) == NULL) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + } else if (form == POLDIFF_FORM_REMOVED) { + if ((pl->added_cats = apol_vector_create_with_capacity(1, free)) == NULL || + (pl->removed_cats = apol_vector_create_from_vector(cats, apol_str_strdup, NULL, free)) == NULL) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + } + if (apol_vector_append(pr->levels, pl) < 0) { + ERR(diff, "%s", strerror(errno)); + goto cleanup; + } + pl = NULL; + } + retval = 0; + cleanup: + apol_vector_destroy(&levels); + if (retval != 0) { + level_free(pl); + range_destroy(&pr); + return NULL; + } + return pr; +} + +void range_destroy(poldiff_range_t ** range) +{ + if (range != NULL && *range != NULL) { + apol_mls_range_destroy(&(*range)->orig_range); + apol_mls_range_destroy(&(*range)->mod_range); + apol_vector_destroy(&(*range)->levels); + apol_vector_destroy(&(*range)->min_added_cats); + apol_vector_destroy(&(*range)->min_removed_cats); + apol_vector_destroy(&(*range)->min_unmodified_cats); + free(*range); + *range = NULL; + } +} + +/** + * Comparison function for two apol_mls_level_t objects from the same + * apol_mls_range_t. Sorts the levels in alphabetical order according + * to sensitivity. + */ +static int range_comp_alphabetize(const void *a, const void *b, void *data __attribute__ ((unused))) +{ + const apol_mls_level_t *l1 = a; + const apol_mls_level_t *l2 = b; + const char *sens1 = apol_mls_level_get_sens(l1); + const char *sens2 = apol_mls_level_get_sens(l2); + return strcmp(sens1, sens2); +} + +/** + * Comparison function for two levels from the same poldiff_range_t. + * Sorts the levels by form; within each form sort them by policy + * order. + */ +static int range_comp(const void *a, const void *b, void *data) +{ + const poldiff_level_t *l1 = a; + const poldiff_level_t *l2 = b; + poldiff_t *diff = data; + qpol_policy_t *q; + const qpol_level_t *ql1, *ql2; + uint32_t v1, v2; + if (l1->form != l2->form) { + return l1->form - l2->form; + } + if (l1->form == POLDIFF_FORM_ADDED) { + q = diff->mod_qpol; + } else { + q = diff->orig_qpol; + } + qpol_policy_get_level_by_name(q, l1->name, &ql1); + qpol_policy_get_level_by_name(q, l2->name, &ql2); + qpol_level_get_value(q, ql1, &v1); + qpol_level_get_value(q, ql2, &v2); + assert(v1 != 0 && v2 != 0); + return v1 - v2; +} + +int range_deep_diff(poldiff_t * diff, poldiff_range_t * range) +{ + apol_vector_t *orig_levels = NULL, *mod_levels = NULL; + apol_vector_t *added = NULL, *removed = NULL, *unmodified = NULL; + apol_mls_level_t *l1, *l2; + poldiff_level_t *pl1, *pl2; + size_t i, j; + int retval = -1, differences_found = 0, compval; + if ((orig_levels = apol_mls_range_get_levels(diff->orig_pol, range->orig_range)) == NULL || + (mod_levels = apol_mls_range_get_levels(diff->mod_pol, range->mod_range)) == NULL) { + goto cleanup; + } + apol_vector_sort(orig_levels, range_comp_alphabetize, NULL); + apol_vector_sort(mod_levels, range_comp_alphabetize, NULL); + for (i = j = 0; i < apol_vector_get_size(orig_levels);) { + if (j >= apol_vector_get_size(mod_levels)) + break; + l1 = (apol_mls_level_t *) apol_vector_get_element(orig_levels, i); + l2 = (apol_mls_level_t *) apol_vector_get_element(mod_levels, j); + pl1 = pl2 = NULL; + const char *sens1 = apol_mls_level_get_sens(l1); + const char *sens2 = apol_mls_level_get_sens(l2); + compval = strcmp(sens1, sens2); + if (compval < 0) { + if ((pl1 = level_create_from_apol_mls_level(l1, POLDIFF_FORM_REMOVED)) == NULL + || apol_vector_append(range->levels, pl1) < 0) { + level_free(pl1); + goto cleanup; + } + differences_found = 1; + i++; + } else if (compval > 0) { + if ((pl2 = level_create_from_apol_mls_level(l2, POLDIFF_FORM_ADDED)) == NULL + || apol_vector_append(range->levels, pl2) < 0) { + level_free(pl2); + goto cleanup; + } + differences_found = 1; + j++; + } else { + if (level_deep_diff_apol_mls_levels(diff, l1, l2, &pl1, &pl2) < 0) { + goto cleanup; + } + assert(pl2 == NULL); + if (pl1 != NULL) { + if (apol_vector_append(range->levels, pl1) < 0) { + level_free(pl1); + goto cleanup; + } + differences_found = 1; + } + i++; + j++; + } + } + for (; i < apol_vector_get_size(orig_levels); i++) { + l1 = (apol_mls_level_t *) apol_vector_get_element(orig_levels, i); + if ((pl1 = level_create_from_apol_mls_level(l1, POLDIFF_FORM_REMOVED)) == NULL + || apol_vector_append(range->levels, pl1) < 0) { + level_free(pl1); + goto cleanup; + } + differences_found = 1; + } + for (; j < apol_vector_get_size(mod_levels); j++) { + l2 = (apol_mls_level_t *) apol_vector_get_element(mod_levels, j); + if ((pl2 = level_create_from_apol_mls_level(l2, POLDIFF_FORM_ADDED)) == NULL + || apol_vector_append(range->levels, pl2) < 0) { + level_free(pl2); + goto cleanup; + } + differences_found = 1; + } + /* now check minimum category sets */ + const apol_mls_level_t *low1 = apol_mls_range_get_low(range->orig_range); + const apol_vector_t *cats1 = apol_mls_level_get_cats(low1); + const apol_mls_level_t *low2 = apol_mls_range_get_low(range->mod_range); + const apol_vector_t *cats2 = apol_mls_level_get_cats(low2); + compval = level_deep_diff_cats(diff, cats1, cats2, &added, &removed, &unmodified); + if (compval < 0) { + goto cleanup; + } else if (compval > 0) { + differences_found = 1; + range->min_added_cats = added; + range->min_removed_cats = removed; + range->min_unmodified_cats = unmodified; + added = NULL; + removed = NULL; + unmodified = NULL; + } + if (differences_found) { + apol_vector_sort(range->levels, range_comp, diff); + retval = 1; + } else { + retval = 0; + } + cleanup: + apol_vector_destroy(&orig_levels); + apol_vector_destroy(&mod_levels); + apol_vector_destroy(&added); + apol_vector_destroy(&removed); + apol_vector_destroy(&unmodified); + return retval; +} |