range_diff.c

00001 /**
00002  *  @file
00003  *  Implementation for computing semantic differences in ranges.
00004  *
00005  *  @author Jeremy A. Mowery jmowery@tresys.com
00006  *  @author Jason Tang jtang@tresys.com
00007  *
00008  *  Copyright (C) 2007 Tresys Technology, LLC
00009  *
00010  *  This library is free software; you can redistribute it and/or
00011  *  modify it under the terms of the GNU Lesser General Public
00012  *  License as published by the Free Software Foundation; either
00013  *  version 2.1 of the License, or (at your option) any later version.
00014  *
00015  *  This library is distributed in the hope that it will be useful,
00016  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00017  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018  *  Lesser General Public License for more details.
00019  *
00020  *  You should have received a copy of the GNU Lesser General Public
00021  *  License along with this library; if not, write to the Free Software
00022  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00023  */
00024 
00025 #include <config.h>
00026 
00027 #include "poldiff_internal.h"
00028 
00029 #include <apol/util.h>
00030 #include <assert.h>
00031 #include <errno.h>
00032 
00033 struct poldiff_range
00034 {
00035         apol_mls_range_t *orig_range;
00036         apol_mls_range_t *mod_range;
00037         /** a vector of poldiff_level_t */
00038         apol_vector_t *levels;
00039         apol_vector_t *min_added_cats;
00040         apol_vector_t *min_removed_cats;
00041         apol_vector_t *min_unmodified_cats;
00042 };
00043 
00044 apol_vector_t *poldiff_range_get_levels(const poldiff_range_t * range)
00045 {
00046         if (range == NULL) {
00047                 errno = EINVAL;
00048                 return NULL;
00049         }
00050         return range->levels;
00051 }
00052 
00053 const apol_mls_range_t *poldiff_range_get_original_range(const poldiff_range_t * range)
00054 {
00055         if (range == NULL) {
00056                 errno = EINVAL;
00057                 return NULL;
00058         }
00059         return range->orig_range;
00060 }
00061 
00062 const apol_mls_range_t *poldiff_range_get_modified_range(const poldiff_range_t * range)
00063 {
00064         if (range == NULL) {
00065                 errno = EINVAL;
00066                 return NULL;
00067         }
00068         return range->mod_range;
00069 }
00070 
00071 apol_vector_t *poldiff_range_get_min_added_cats(const poldiff_range_t * range)
00072 {
00073         if (range == NULL) {
00074                 errno = EINVAL;
00075                 return NULL;
00076         }
00077         return range->min_added_cats;
00078 }
00079 
00080 apol_vector_t *poldiff_range_get_min_removed_cats(const poldiff_range_t * range)
00081 {
00082         if (range == NULL) {
00083                 errno = EINVAL;
00084                 return NULL;
00085         }
00086         return range->min_removed_cats;
00087 }
00088 
00089 apol_vector_t *poldiff_range_get_min_unmodified_cats(const poldiff_range_t * range)
00090 {
00091         if (range == NULL) {
00092                 errno = EINVAL;
00093                 return NULL;
00094         }
00095         return range->min_unmodified_cats;
00096 }
00097 
00098 char *poldiff_range_to_string_brief(const poldiff_t * diff, const poldiff_range_t * range)
00099 {
00100         char *r1 = NULL, *r2 = NULL;
00101         char *s = NULL, *t = NULL, *sep = "", *cat;
00102         size_t len = 0, i;
00103         if (range->orig_range != NULL && (r1 = apol_mls_range_render(diff->orig_pol, range->orig_range)) == NULL) {
00104                 ERR(diff, "%s", strerror(errno));
00105                 goto cleanup;
00106         }
00107         if (range->mod_range != NULL && (r2 = apol_mls_range_render(diff->mod_pol, range->mod_range)) == NULL) {
00108                 ERR(diff, "%s", strerror(errno));
00109                 goto cleanup;
00110         }
00111         assert(r1 != NULL || r2 != NULL);
00112         if (r1 == NULL) {
00113                 if (apol_str_appendf(&s, &len, "   range: %s\n", r2) < 0) {
00114                         ERR(diff, "%s", strerror(errno));
00115                         goto cleanup;
00116                 }
00117         } else if (r2 == NULL) {
00118                 if (apol_str_appendf(&s, &len, "   range: %s\n", r1) < 0) {
00119                         ERR(diff, "%s", strerror(errno));
00120                         goto cleanup;
00121                 }
00122         } else {
00123                 if (apol_str_appendf(&s, &len, "   range: %s  -->  %s\n", r1, r2) < 0) {
00124                         ERR(diff, "%s", strerror(errno));
00125                         goto cleanup;
00126                 }
00127         }
00128         if ((range->min_added_cats != NULL && apol_vector_get_size(range->min_added_cats) > 0) ||
00129             (range->min_removed_cats != NULL && apol_vector_get_size(range->min_removed_cats) > 0) ||
00130             (range->min_unmodified_cats != NULL && apol_vector_get_size(range->min_unmodified_cats) > 0)) {
00131                 if (apol_str_append(&s, &len, "     minimum categories: ") < 0) {
00132                         ERR(diff, "%s", strerror(errno));
00133                         goto cleanup;
00134                 }
00135                 for (i = 0; range->min_unmodified_cats != NULL && i < apol_vector_get_size(range->min_unmodified_cats); i++) {
00136                         cat = apol_vector_get_element(range->min_unmodified_cats, i);
00137                         if (apol_str_appendf(&s, &len, "%s%s", sep, cat) < 0) {
00138                                 ERR(diff, "%s", strerror(errno));
00139                                 return NULL;
00140                         }
00141                         sep = ",";
00142                 }
00143                 for (i = 0; range->min_added_cats != NULL && i < apol_vector_get_size(range->min_added_cats); i++) {
00144                         cat = apol_vector_get_element(range->min_added_cats, i);
00145                         if (apol_str_appendf(&s, &len, "%s+%s", sep, cat) < 0) {
00146                                 ERR(diff, "%s", strerror(errno));
00147                                 return NULL;
00148                         }
00149                         sep = ",";
00150                 }
00151                 for (i = 0; range->min_removed_cats != NULL && i < apol_vector_get_size(range->min_removed_cats); i++) {
00152                         cat = apol_vector_get_element(range->min_removed_cats, i);
00153                         if (apol_str_appendf(&s, &len, "%s-%s", sep, cat) < 0) {
00154                                 ERR(diff, "%s", strerror(errno));
00155                                 return NULL;
00156                         }
00157                         sep = ",";
00158                 }
00159                 if (apol_str_append(&s, &len, "\n") < 0) {
00160                         ERR(diff, "%s", strerror(errno));
00161                         return NULL;
00162                 }
00163         }
00164         for (i = 0; i < apol_vector_get_size(range->levels); i++) {
00165                 poldiff_level_t *level = apol_vector_get_element(range->levels, i);
00166                 if ((t = poldiff_level_to_string_brief(diff, level)) == NULL) {
00167                         goto cleanup;
00168                 }
00169                 if (apol_str_appendf(&s, &len, "     %s", t) < 0) {
00170                         ERR(diff, "%s", strerror(errno));
00171                         goto cleanup;
00172                 }
00173                 free(t);
00174                 t = NULL;
00175         }
00176       cleanup:
00177         free(r1);
00178         free(r2);
00179         free(t);
00180         return s;
00181 }
00182 
00183 poldiff_range_t *range_create(const poldiff_t * diff, const qpol_mls_range_t * orig_range, const qpol_mls_range_t * mod_range,
00184                               poldiff_form_e form)
00185 {
00186         poldiff_range_t *pr = NULL;
00187         apol_policy_t *p;
00188         apol_mls_range_t *range;
00189         apol_vector_t *levels = NULL;
00190         poldiff_level_t *pl = NULL;
00191         size_t i;
00192         int retval = -1;
00193         if ((pr = calloc(1, sizeof(*pr))) == NULL || (pr->levels = apol_vector_create(level_free)) == NULL) {
00194                 ERR(diff, "%s", strerror(errno));
00195                 goto cleanup;
00196         }
00197         if (orig_range != NULL && (pr->orig_range = apol_mls_range_create_from_qpol_mls_range(diff->orig_pol, orig_range)) == NULL) {
00198                 goto cleanup;
00199         }
00200         if (mod_range != NULL && (pr->mod_range = apol_mls_range_create_from_qpol_mls_range(diff->mod_pol, mod_range)) == NULL) {
00201                 goto cleanup;
00202         }
00203         if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) {
00204                 p = diff->mod_pol;
00205                 range = pr->mod_range;
00206         } else if (form == POLDIFF_FORM_REMOVED || form == POLDIFF_FORM_REMOVE_TYPE) {
00207                 p = diff->orig_pol;
00208                 range = pr->orig_range;
00209         } else if (form == POLDIFF_FORM_MODIFIED) {
00210                 /* don't fill in the range's levels here */
00211                 return pr;
00212         } else {
00213                 /* should never get here */
00214                 assert(0);
00215                 return pr;
00216         }
00217         if ((levels = apol_mls_range_get_levels(p, range)) == NULL) {
00218                 goto cleanup;
00219         }
00220         for (i = 0; i < apol_vector_get_size(levels); i++) {
00221                 apol_mls_level_t *l = apol_vector_get_element(levels, i);
00222                 const char *sens = apol_mls_level_get_sens(l);
00223                 const apol_vector_t *cats = apol_mls_level_get_cats(l);
00224                 if ((pl = calloc(1, sizeof(*pl))) == NULL ||
00225                     (pl->name = strdup(sens)) == NULL || (pl->unmodified_cats = apol_vector_create_with_capacity(1, free)) == NULL)
00226                 {
00227                         ERR(diff, "%s", strerror(errno));
00228                         goto cleanup;
00229                 }
00230                 if (form == POLDIFF_FORM_ADDED) {
00231                         if ((pl->added_cats = apol_vector_create_from_vector(cats, apol_str_strdup, NULL, free)) == NULL ||
00232                             (pl->removed_cats = apol_vector_create_with_capacity(1, free)) == NULL) {
00233                                 ERR(diff, "%s", strerror(errno));
00234                                 goto cleanup;
00235                         }
00236                 } else if (form == POLDIFF_FORM_REMOVED) {
00237                         if ((pl->added_cats = apol_vector_create_with_capacity(1, free)) == NULL ||
00238                             (pl->removed_cats = apol_vector_create_from_vector(cats, apol_str_strdup, NULL, free)) == NULL) {
00239                                 ERR(diff, "%s", strerror(errno));
00240                                 goto cleanup;
00241                         }
00242                 }
00243                 if (apol_vector_append(pr->levels, pl) < 0) {
00244                         ERR(diff, "%s", strerror(errno));
00245                         goto cleanup;
00246                 }
00247                 pl = NULL;
00248         }
00249         retval = 0;
00250       cleanup:
00251         apol_vector_destroy(&levels);
00252         if (retval != 0) {
00253                 level_free(pl);
00254                 range_destroy(&pr);
00255                 return NULL;
00256         }
00257         return pr;
00258 }
00259 
00260 void range_destroy(poldiff_range_t ** range)
00261 {
00262         if (range != NULL && *range != NULL) {
00263                 apol_mls_range_destroy(&(*range)->orig_range);
00264                 apol_mls_range_destroy(&(*range)->mod_range);
00265                 apol_vector_destroy(&(*range)->levels);
00266                 apol_vector_destroy(&(*range)->min_added_cats);
00267                 apol_vector_destroy(&(*range)->min_removed_cats);
00268                 apol_vector_destroy(&(*range)->min_unmodified_cats);
00269                 free(*range);
00270                 *range = NULL;
00271         }
00272 }
00273 
00274 /**
00275  * Comparison function for two apol_mls_level_t objects from the same
00276  * apol_mls_range_t.  Sorts the levels in alphabetical order according
00277  * to sensitivity.
00278  */
00279 static int range_comp_alphabetize(const void *a, const void *b, void *data __attribute__ ((unused)))
00280 {
00281         const apol_mls_level_t *l1 = a;
00282         const apol_mls_level_t *l2 = b;
00283         const char *sens1 = apol_mls_level_get_sens(l1);
00284         const char *sens2 = apol_mls_level_get_sens(l2);
00285         return strcmp(sens1, sens2);
00286 }
00287 
00288 /**
00289  * Comparison function for two levels from the same poldiff_range_t.
00290  * Sorts the levels by form; within each form sort them by policy
00291  * order.
00292  */
00293 static int range_comp(const void *a, const void *b, void *data)
00294 {
00295         const poldiff_level_t *l1 = a;
00296         const poldiff_level_t *l2 = b;
00297         poldiff_t *diff = data;
00298         qpol_policy_t *q;
00299         const qpol_level_t *ql1, *ql2;
00300         uint32_t v1, v2;
00301         if (l1->form != l2->form) {
00302                 return l1->form - l2->form;
00303         }
00304         if (l1->form == POLDIFF_FORM_ADDED) {
00305                 q = diff->mod_qpol;
00306         } else {
00307                 q = diff->orig_qpol;
00308         }
00309         qpol_policy_get_level_by_name(q, l1->name, &ql1);
00310         qpol_policy_get_level_by_name(q, l2->name, &ql2);
00311         qpol_level_get_value(q, ql1, &v1);
00312         qpol_level_get_value(q, ql2, &v2);
00313         assert(v1 != 0 && v2 != 0);
00314         return v1 - v2;
00315 }
00316 
00317 int range_deep_diff(poldiff_t * diff, poldiff_range_t * range)
00318 {
00319         apol_vector_t *orig_levels = NULL, *mod_levels = NULL;
00320         apol_vector_t *added = NULL, *removed = NULL, *unmodified = NULL;
00321         apol_mls_level_t *l1, *l2;
00322         poldiff_level_t *pl1, *pl2;
00323         size_t i, j;
00324         int retval = -1, differences_found = 0, compval;
00325         if ((orig_levels = apol_mls_range_get_levels(diff->orig_pol, range->orig_range)) == NULL ||
00326             (mod_levels = apol_mls_range_get_levels(diff->mod_pol, range->mod_range)) == NULL) {
00327                 goto cleanup;
00328         }
00329         apol_vector_sort(orig_levels, range_comp_alphabetize, NULL);
00330         apol_vector_sort(mod_levels, range_comp_alphabetize, NULL);
00331         for (i = j = 0; i < apol_vector_get_size(orig_levels);) {
00332                 if (j >= apol_vector_get_size(mod_levels))
00333                         break;
00334                 l1 = (apol_mls_level_t *) apol_vector_get_element(orig_levels, i);
00335                 l2 = (apol_mls_level_t *) apol_vector_get_element(mod_levels, j);
00336                 pl1 = pl2 = NULL;
00337                 const char *sens1 = apol_mls_level_get_sens(l1);
00338                 const char *sens2 = apol_mls_level_get_sens(l2);
00339                 compval = strcmp(sens1, sens2);
00340                 if (compval < 0) {
00341                         if ((pl1 = level_create_from_apol_mls_level(l1, POLDIFF_FORM_REMOVED)) == NULL
00342                             || apol_vector_append(range->levels, pl1) < 0) {
00343                                 level_free(pl1);
00344                                 goto cleanup;
00345                         }
00346                         differences_found = 1;
00347                         i++;
00348                 } else if (compval > 0) {
00349                         if ((pl2 = level_create_from_apol_mls_level(l2, POLDIFF_FORM_ADDED)) == NULL
00350                             || apol_vector_append(range->levels, pl2) < 0) {
00351                                 level_free(pl2);
00352                                 goto cleanup;
00353                         }
00354                         differences_found = 1;
00355                         j++;
00356                 } else {
00357                         if (level_deep_diff_apol_mls_levels(diff, l1, l2, &pl1, &pl2) < 0) {
00358                                 goto cleanup;
00359                         }
00360                         assert(pl2 == NULL);
00361                         if (pl1 != NULL) {
00362                                 if (apol_vector_append(range->levels, pl1) < 0) {
00363                                         level_free(pl1);
00364                                         goto cleanup;
00365                                 }
00366                                 differences_found = 1;
00367                         }
00368                         i++;
00369                         j++;
00370                 }
00371         }
00372         for (; i < apol_vector_get_size(orig_levels); i++) {
00373                 l1 = (apol_mls_level_t *) apol_vector_get_element(orig_levels, i);
00374                 if ((pl1 = level_create_from_apol_mls_level(l1, POLDIFF_FORM_REMOVED)) == NULL
00375                     || apol_vector_append(range->levels, pl1) < 0) {
00376                         level_free(pl1);
00377                         goto cleanup;
00378                 }
00379                 differences_found = 1;
00380         }
00381         for (; j < apol_vector_get_size(mod_levels); j++) {
00382                 l2 = (apol_mls_level_t *) apol_vector_get_element(mod_levels, j);
00383                 if ((pl2 = level_create_from_apol_mls_level(l2, POLDIFF_FORM_ADDED)) == NULL
00384                     || apol_vector_append(range->levels, pl2) < 0) {
00385                         level_free(pl2);
00386                         goto cleanup;
00387                 }
00388                 differences_found = 1;
00389         }
00390         /* now check minimum category sets */
00391         const apol_mls_level_t *low1 = apol_mls_range_get_low(range->orig_range);
00392         const apol_vector_t *cats1 = apol_mls_level_get_cats(low1);
00393         const apol_mls_level_t *low2 = apol_mls_range_get_low(range->mod_range);
00394         const apol_vector_t *cats2 = apol_mls_level_get_cats(low2);
00395         compval = level_deep_diff_cats(diff, cats1, cats2, &added, &removed, &unmodified);
00396         if (compval < 0) {
00397                 goto cleanup;
00398         } else if (compval > 0) {
00399                 differences_found = 1;
00400                 range->min_added_cats = added;
00401                 range->min_removed_cats = removed;
00402                 range->min_unmodified_cats = unmodified;
00403                 added = NULL;
00404                 removed = NULL;
00405                 unmodified = NULL;
00406         }
00407         if (differences_found) {
00408                 apol_vector_sort(range->levels, range_comp, diff);
00409                 retval = 1;
00410         } else {
00411                 retval = 0;
00412         }
00413       cleanup:
00414         apol_vector_destroy(&orig_levels);
00415         apol_vector_destroy(&mod_levels);
00416         apol_vector_destroy(&added);
00417         apol_vector_destroy(&removed);
00418         apol_vector_destroy(&unmodified);
00419         return retval;
00420 }