avrule_diff.c

00001 /**
00002  *  @file
00003  *  Implementation for computing semantic differences in AV and Type
00004  *  rules.
00005  *
00006  *  @author Jeremy A. Mowery jmowery@tresys.com
00007  *  @author Jason Tang jtang@tresys.com
00008  *
00009  *  Copyright (C) 2006-2007 Tresys Technology, LLC
00010  *
00011  *  This library is free software; you can redistribute it and/or
00012  *  modify it under the terms of the GNU Lesser General Public
00013  *  License as published by the Free Software Foundation; either
00014  *  version 2.1 of the License, or (at your option) any later version.
00015  *
00016  *  This library is distributed in the hope that it will be useful,
00017  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019  *  Lesser General Public License for more details.
00020  *
00021  *  You should have received a copy of the GNU Lesser General Public
00022  *  License along with this library; if not, write to the Free Software
00023  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00024  */
00025 
00026 #include <config.h>
00027 
00028 #include "poldiff_internal.h"
00029 
00030 #include <apol/policy-query.h>
00031 #include <apol/util.h>
00032 #include <qpol/policy_extend.h>
00033 #include <assert.h>
00034 #include <errno.h>
00035 #include <stdio.h>
00036 #include <string.h>
00037 
00038 struct poldiff_avrule_summary
00039 {
00040         size_t num_added;
00041         size_t num_removed;
00042         size_t num_modified;
00043         size_t num_added_type;
00044         size_t num_removed_type;
00045         int diffs_sorted;
00046         /** vector of poldiff_avrule_t */
00047         apol_vector_t *diffs;
00048 };
00049 
00050 struct poldiff_avrule
00051 {
00052         uint32_t spec;
00053         /* pointer into policy's symbol table */
00054         const char *source, *target;
00055         /** the class string is pointer into the class_bst BST */
00056         char *cls;
00057         poldiff_form_e form;
00058         /** vector of pointers into the perm_bst BST (char *) */
00059         apol_vector_t *unmodified_perms;
00060         /** vector of pointers into the perm_bst BST (char *) */
00061         apol_vector_t *added_perms;
00062         /** vector of pointers into the perm_bst BST (char *) */
00063         apol_vector_t *removed_perms;
00064         /** pointer into policy's conditional list, needed to render
00065          * conditional expressions */
00066         const qpol_cond_t *cond;
00067         uint32_t branch;
00068         /** vector of unsigned longs of line numbers from original policy */
00069         apol_vector_t *orig_linenos;
00070         /** vector of unsigned longs of line numbers from modified policy */
00071         apol_vector_t *mod_linenos;
00072         /** array of pointers for original rules */
00073         qpol_avrule_t **orig_rules;
00074         size_t num_orig_rules;
00075         /** array of pointers for modified rules */
00076         qpol_avrule_t **mod_rules;
00077         size_t num_mod_rules;
00078 };
00079 
00080 typedef struct pseudo_avrule
00081 {
00082         uint32_t spec;
00083         /** pseudo-type values */
00084         uint32_t source, target;
00085         /** pointer into the class_bst BST */
00086         char *cls;
00087         /** array of pointers into the perm_bst BST */
00088         /* (use an array here to save space) */
00089         char **perms;
00090         size_t num_perms;
00091         /** array of pointers into the bool_bst BST */
00092         char *bools[5];
00093         uint32_t bool_val;
00094         uint32_t branch;
00095         /** pointer into policy's conditional list, needed to render
00096          * conditional expressions */
00097         const qpol_cond_t *cond;
00098         /** array of qpol_avrule_t pointers, for showing line numbers */
00099         const qpol_avrule_t **rules;
00100         size_t num_rules;
00101 } pseudo_avrule_t;
00102 
00103 /******************** public avrule functions ********************/
00104 
00105 /**
00106  *  Get an array of statistics for the number of differences of each
00107  *  form for av rules.
00108  *
00109  *  @param diff The policy difference structure from which to get the
00110  *  stats.
00111  *  @param stats Array into which to write the numbers (array must be
00112  *  pre-allocated).  The order of the values written to the array is
00113  *  as follows:  number of items of form POLDIFF_FORM_ADDED, number of
00114  *  POLDIFF_FORM_REMOVED, number of POLDIFF_FORM_MODIFIED, number of
00115  *  POLDIFF_FORM_ADD_TYPE, and number of POLDIFF_FORM_REMOVE_TYPE.
00116  *  @param idx Index into the avrule differences specifying which
00117  *  avrule type to get, one of AVRULE_OFFSET_ALLOW, etc.
00118  */
00119 static void poldiff_avrule_get_stats(const poldiff_t * diff, size_t stats[5], avrule_offset_e idx)
00120 {
00121         if (diff == NULL || stats == NULL) {
00122                 ERR(diff, "%s", strerror(EINVAL));
00123                 errno = EINVAL;
00124                 return;
00125         }
00126         stats[0] = diff->avrule_diffs[idx]->num_added;
00127         stats[1] = diff->avrule_diffs[idx]->num_removed;
00128         stats[2] = diff->avrule_diffs[idx]->num_modified;
00129         stats[3] = diff->avrule_diffs[idx]->num_added_type;
00130         stats[4] = diff->avrule_diffs[idx]->num_removed_type;
00131 }
00132 
00133 void poldiff_avrule_get_stats_allow(const poldiff_t * diff, size_t stats[5])
00134 {
00135         poldiff_avrule_get_stats(diff, stats, AVRULE_OFFSET_ALLOW);
00136 }
00137 
00138 void poldiff_avrule_get_stats_neverallow(const poldiff_t * diff, size_t stats[5])
00139 {
00140         poldiff_avrule_get_stats(diff, stats, AVRULE_OFFSET_NEVERALLOW);
00141 }
00142 
00143 void poldiff_avrule_get_stats_dontaudit(const poldiff_t * diff, size_t stats[5])
00144 {
00145         poldiff_avrule_get_stats(diff, stats, AVRULE_OFFSET_DONTAUDIT);
00146 }
00147 
00148 void poldiff_avrule_get_stats_auditallow(const poldiff_t * diff, size_t stats[5])
00149 {
00150         poldiff_avrule_get_stats(diff, stats, AVRULE_OFFSET_AUDITALLOW);
00151 }
00152 
00153 char *poldiff_avrule_to_string(const poldiff_t * diff, const void *avrule)
00154 {
00155         const poldiff_avrule_t *pa = (const poldiff_avrule_t *)avrule;
00156         apol_policy_t *p;
00157         const char *rule_type;
00158         char *diff_char = "", *s = NULL, *perm_name, *cond_expr = NULL;
00159         size_t i, len = 0;
00160         int show_perm_sym = 0, error;
00161         if (diff == NULL || avrule == NULL) {
00162                 ERR(diff, "%s", strerror(EINVAL));
00163                 errno = EINVAL;
00164                 return NULL;
00165         }
00166         switch (pa->form) {
00167         case POLDIFF_FORM_ADDED:
00168         case POLDIFF_FORM_ADD_TYPE:
00169         {
00170                 diff_char = "+";
00171                 p = diff->mod_pol;
00172                 break;
00173         }
00174         case POLDIFF_FORM_REMOVED:
00175         case POLDIFF_FORM_REMOVE_TYPE:
00176         {
00177                 diff_char = "-";
00178                 p = diff->orig_pol;
00179                 break;
00180         }
00181         case POLDIFF_FORM_MODIFIED:
00182         {
00183                 diff_char = "*";
00184                 p = diff->orig_pol;
00185                 show_perm_sym = 1;
00186                 break;
00187         }
00188         default:
00189         {
00190                 ERR(diff, "%s", strerror(ENOTSUP));
00191                 errno = ENOTSUP;
00192                 return NULL;
00193         }
00194         }
00195         rule_type = apol_rule_type_to_str(pa->spec);
00196         if (apol_str_appendf(&s, &len, "%s %s %s %s : %s {", diff_char, rule_type, pa->source, pa->target, pa->cls) < 0) {
00197                 error = errno;
00198                 goto err;
00199         }
00200         for (i = 0; pa->unmodified_perms != NULL && i < apol_vector_get_size(pa->unmodified_perms); i++) {
00201                 perm_name = (char *)apol_vector_get_element(pa->unmodified_perms, i);
00202                 if (apol_str_appendf(&s, &len, " %s", perm_name) < 0) {
00203                         error = errno;
00204                         goto err;
00205                 }
00206         }
00207         for (i = 0; pa->added_perms != NULL && i < apol_vector_get_size(pa->added_perms); i++) {
00208                 perm_name = (char *)apol_vector_get_element(pa->added_perms, i);
00209                 if (apol_str_appendf(&s, &len, " %s%s", (show_perm_sym ? "+" : ""), perm_name) < 0) {
00210                         error = errno;
00211                         goto err;
00212                 }
00213         }
00214         for (i = 0; pa->removed_perms != NULL && i < apol_vector_get_size(pa->removed_perms); i++) {
00215                 perm_name = (char *)apol_vector_get_element(pa->removed_perms, i);
00216                 if (apol_str_appendf(&s, &len, " %s%s", (show_perm_sym ? "-" : ""), perm_name) < 0) {
00217                         error = errno;
00218                         goto err;
00219                 }
00220         }
00221         if (apol_str_append(&s, &len, " };") < 0) {
00222                 error = errno;
00223                 goto err;
00224         }
00225         if (pa->cond != NULL) {
00226                 if ((cond_expr = apol_cond_expr_render(p, pa->cond)) == NULL) {
00227                         error = errno;
00228                         goto err;
00229                 }
00230                 if (apol_str_appendf(&s, &len, "  [%s]:%s", cond_expr, (pa->branch ? "TRUE" : "FALSE")) < 0) {
00231                         error = errno;
00232                         goto err;
00233                 }
00234                 free(cond_expr);
00235         }
00236         return s;
00237       err:
00238         free(s);
00239         free(cond_expr);
00240         ERR(diff, "%s", strerror(error));
00241         errno = error;
00242         return NULL;
00243 }
00244 
00245 /**
00246  * Sort poldiff_avrule diff results in a mostly alphabetical order.
00247  */
00248 static int poldiff_avrule_cmp(const void *x, const void *y, void *data __attribute__ ((unused)))
00249 {
00250         const poldiff_avrule_t *a = (const poldiff_avrule_t *)x;
00251         const poldiff_avrule_t *b = (const poldiff_avrule_t *)y;
00252         int compval;
00253         if (a->spec != b->spec) {
00254                 const char *rule_type1 = apol_rule_type_to_str(a->spec);
00255                 const char *rule_type2 = apol_rule_type_to_str(b->spec);
00256                 compval = strcmp(rule_type1, rule_type2);
00257                 if (compval != 0) {
00258                         return compval;
00259                 }
00260         }
00261         if ((compval = strcmp(a->source, b->source)) != 0) {
00262                 return compval;
00263         }
00264         if ((compval = strcmp(a->target, b->target)) != 0) {
00265                 return compval;
00266         }
00267         if ((compval = strcmp(a->cls, b->cls)) != 0) {
00268                 return compval;
00269         }
00270         if (a->cond != b->cond) {
00271                 return (char *)a->cond - (char *)b->cond;
00272         }
00273         /* sort true branch before false branch */
00274         return b->branch - a->branch;
00275 }
00276 
00277 /**
00278  *  Get the vector of av rule differences from the av rule difference
00279  *  summary.
00280  *
00281  *  @param diff The policy difference structure associated with the av
00282  *  rule difference summary.
00283  *  @param idx Index into the avrule differences specifying which
00284  *  avrule type to get, one of AVRULE_OFFSET_ALLOW, etc.
00285  *
00286  *  @return A vector of elements of type poldiff_avrule_t, or NULL on
00287  *  error.  The caller should <b>not</b> destroy the vector returned.
00288  *  If the call fails, errno will be set.
00289  */
00290 static const apol_vector_t *poldiff_get_avrule_vector(const poldiff_t * diff, avrule_offset_e idx)
00291 {
00292         if (diff == NULL) {
00293                 errno = EINVAL;
00294                 return NULL;
00295         }
00296         if (diff->avrule_diffs[idx]->diffs_sorted == 0) {
00297                 apol_vector_sort(diff->avrule_diffs[idx]->diffs, poldiff_avrule_cmp, NULL);
00298                 diff->avrule_diffs[idx]->diffs_sorted = 1;
00299         }
00300         return diff->avrule_diffs[idx]->diffs;
00301 }
00302 
00303 const apol_vector_t *poldiff_get_avrule_vector_allow(const poldiff_t * diff)
00304 {
00305         return poldiff_get_avrule_vector(diff, AVRULE_OFFSET_ALLOW);
00306 }
00307 
00308 const apol_vector_t *poldiff_get_avrule_vector_auditallow(const poldiff_t * diff)
00309 {
00310         return poldiff_get_avrule_vector(diff, AVRULE_OFFSET_AUDITALLOW);
00311 }
00312 
00313 const apol_vector_t *poldiff_get_avrule_vector_dontaudit(const poldiff_t * diff)
00314 {
00315         return poldiff_get_avrule_vector(diff, AVRULE_OFFSET_DONTAUDIT);
00316 }
00317 
00318 const apol_vector_t *poldiff_get_avrule_vector_neverallow(const poldiff_t * diff)
00319 {
00320         return poldiff_get_avrule_vector(diff, AVRULE_OFFSET_NEVERALLOW);
00321 }
00322 
00323 poldiff_form_e poldiff_avrule_get_form(const void *avrule)
00324 {
00325         if (avrule == NULL) {
00326                 errno = EINVAL;
00327                 return 0;
00328         }
00329         return ((const poldiff_avrule_t *)avrule)->form;
00330 }
00331 
00332 uint32_t poldiff_avrule_get_rule_type(const poldiff_avrule_t * avrule)
00333 {
00334         if (avrule == NULL) {
00335                 errno = EINVAL;
00336                 return 0;
00337         }
00338         return avrule->spec;
00339 }
00340 
00341 const char *poldiff_avrule_get_source_type(const poldiff_avrule_t * avrule)
00342 {
00343         if (avrule == NULL) {
00344                 errno = EINVAL;
00345                 return 0;
00346         }
00347         return avrule->source;
00348 }
00349 
00350 const char *poldiff_avrule_get_target_type(const poldiff_avrule_t * avrule)
00351 {
00352         if (avrule == NULL) {
00353                 errno = EINVAL;
00354                 return 0;
00355         }
00356         return avrule->target;
00357 }
00358 
00359 const char *poldiff_avrule_get_object_class(const poldiff_avrule_t * avrule)
00360 {
00361         if (avrule == NULL) {
00362                 errno = EINVAL;
00363                 return 0;
00364         }
00365         return avrule->cls;
00366 }
00367 
00368 void poldiff_avrule_get_cond(const poldiff_t * diff, const poldiff_avrule_t * avrule,
00369                              const qpol_cond_t ** cond, uint32_t * which_list, const apol_policy_t ** p)
00370 {
00371         if (diff == NULL || avrule == NULL || cond == NULL || p == NULL) {
00372                 errno = EINVAL;
00373                 return;
00374         }
00375         *cond = avrule->cond;
00376         if (*cond == NULL) {
00377                 *which_list = 1;
00378                 *p = NULL;
00379         } else if (avrule->form == POLDIFF_FORM_ADDED || avrule->form == POLDIFF_FORM_ADD_TYPE) {
00380                 *which_list = avrule->branch;
00381                 *p = diff->mod_pol;
00382         } else {
00383                 *which_list = avrule->branch;
00384                 *p = diff->orig_pol;
00385         }
00386 }
00387 
00388 const apol_vector_t *poldiff_avrule_get_unmodified_perms(const poldiff_avrule_t * avrule)
00389 {
00390         if (avrule == NULL) {
00391                 errno = EINVAL;
00392                 return NULL;
00393         }
00394         return avrule->unmodified_perms;
00395 }
00396 
00397 const apol_vector_t *poldiff_avrule_get_added_perms(const poldiff_avrule_t * avrule)
00398 {
00399         if (avrule == NULL) {
00400                 errno = EINVAL;
00401                 return NULL;
00402         }
00403         return avrule->added_perms;
00404 }
00405 
00406 const apol_vector_t *poldiff_avrule_get_removed_perms(const poldiff_avrule_t * avrule)
00407 {
00408         if (avrule == NULL) {
00409                 errno = EINVAL;
00410                 return NULL;
00411         }
00412         return avrule->removed_perms;
00413 }
00414 
00415 const apol_vector_t *poldiff_avrule_get_orig_line_numbers(const poldiff_avrule_t * avrule)
00416 {
00417         if (avrule == NULL) {
00418                 errno = EINVAL;
00419                 return NULL;
00420         }
00421         return avrule->orig_linenos;
00422 }
00423 
00424 const apol_vector_t *poldiff_avrule_get_mod_line_numbers(const poldiff_avrule_t * avrule)
00425 {
00426         if (avrule == NULL) {
00427                 errno = EINVAL;
00428                 return NULL;
00429         }
00430         return avrule->mod_linenos;
00431 }
00432 
00433 /**
00434  * Get the line numbers from an array of qpol_avrule_t that contain
00435  * the given permission.
00436  */
00437 static apol_vector_t *avrule_get_line_numbers_for_perm(const poldiff_t * diff, const char *perm, const qpol_policy_t * q,
00438                                                        qpol_avrule_t ** rules, const size_t num_rules)
00439 {
00440         apol_vector_t *v = NULL;
00441         qpol_iterator_t *syn_iter = NULL, *perm_iter = NULL;
00442         size_t i;
00443         int error = 0;
00444 
00445         if ((v = apol_vector_create(NULL)) == NULL) {
00446                 error = errno;
00447                 ERR(diff, "%s", strerror(errno));
00448                 goto cleanup;
00449         }
00450         for (i = 0; i < num_rules; i++) {
00451                 if (qpol_avrule_get_syn_avrule_iter(q, rules[i], &syn_iter) < 0) {
00452                         error = errno;
00453                         goto cleanup;
00454                 }
00455                 for (; !qpol_iterator_end(syn_iter); qpol_iterator_next(syn_iter)) {
00456                         qpol_syn_avrule_t *syn_rule;
00457                         qpol_iterator_get_item(syn_iter, (void **)&syn_rule);
00458                         if (qpol_syn_avrule_get_perm_iter(q, syn_rule, &perm_iter) < 0) {
00459                                 error = errno;
00460                                 goto cleanup;
00461                         }
00462                         for (; !qpol_iterator_end(perm_iter); qpol_iterator_next(perm_iter)) {
00463                                 char *syn_perm;
00464                                 qpol_iterator_get_item(perm_iter, (void **)&syn_perm);
00465                                 if (strcmp(perm, syn_perm) == 0) {
00466                                         unsigned long lineno;
00467                                         qpol_syn_avrule_get_lineno(q, syn_rule, &lineno);
00468                                         if (apol_vector_append(v, (void *)lineno) < 0) {
00469                                                 ERR(diff, "%s", strerror(errno));
00470                                         }
00471                                         break;
00472                                 }
00473                         }
00474                         qpol_iterator_destroy(&perm_iter);
00475                 }
00476                 qpol_iterator_destroy(&syn_iter);
00477         }
00478         apol_vector_sort_uniquify(v, NULL, NULL);
00479       cleanup:
00480         qpol_iterator_destroy(&syn_iter);
00481         qpol_iterator_destroy(&perm_iter);
00482         if (error != 0) {
00483                 apol_vector_destroy(&v);
00484                 errno = error;
00485                 return NULL;
00486         }
00487         return v;
00488 }
00489 
00490 apol_vector_t *poldiff_avrule_get_orig_line_numbers_for_perm(const poldiff_t * diff, const poldiff_avrule_t * avrule,
00491                                                              const char *perm)
00492 {
00493         if (diff == NULL || avrule == NULL || perm == NULL) {
00494                 ERR(diff, "%s", strerror(EINVAL));
00495                 errno = EINVAL;
00496                 return NULL;
00497         }
00498         if (!diff->line_numbers_enabled || avrule->form == POLDIFF_FORM_ADDED || avrule->form == POLDIFF_FORM_ADD_TYPE) {
00499                 return NULL;
00500         }
00501         if (avrule->num_orig_rules == 0) {
00502                 return NULL;
00503         }
00504         return avrule_get_line_numbers_for_perm(diff, perm, diff->orig_qpol, avrule->orig_rules, avrule->num_orig_rules);
00505 }
00506 
00507 apol_vector_t *poldiff_avrule_get_mod_line_numbers_for_perm(const poldiff_t * diff, const poldiff_avrule_t * avrule,
00508                                                             const char *perm)
00509 {
00510         if (diff == NULL || avrule == NULL || perm == NULL) {
00511                 ERR(diff, "%s", strerror(EINVAL));
00512                 errno = EINVAL;
00513                 return NULL;
00514         }
00515         if (!diff->line_numbers_enabled || avrule->form == POLDIFF_FORM_REMOVED || avrule->form == POLDIFF_FORM_REMOVE_TYPE) {
00516                 return NULL;
00517         }
00518         if (avrule->num_mod_rules == 0) {
00519                 return NULL;
00520         }
00521         return avrule_get_line_numbers_for_perm(diff, perm, diff->mod_qpol, avrule->mod_rules, avrule->num_mod_rules);
00522 }
00523 
00524 /******************** protected functions below ********************/
00525 
00526 /**
00527  * Free all space used by a poldiff_avrule_t, including the pointer
00528  * itself.  Does nothing if the pointer is already NULL.
00529  *
00530  * @param elem Pointer to a poldiff_avrule_t.
00531  */
00532 static void poldiff_avrule_free(void *elem)
00533 {
00534         if (elem != NULL) {
00535                 poldiff_avrule_t *a = (poldiff_avrule_t *) elem;
00536                 apol_vector_destroy(&a->unmodified_perms);
00537                 apol_vector_destroy(&a->added_perms);
00538                 apol_vector_destroy(&a->removed_perms);
00539                 apol_vector_destroy(&a->orig_linenos);
00540                 apol_vector_destroy(&a->mod_linenos);
00541                 free(a->orig_rules);
00542                 free(a->mod_rules);
00543                 free(a);
00544         }
00545 }
00546 
00547 poldiff_avrule_summary_t *avrule_create(void)
00548 {
00549         poldiff_avrule_summary_t *rs = calloc(1, sizeof(*rs));
00550         if (rs == NULL) {
00551                 return NULL;
00552         }
00553         if ((rs->diffs = apol_vector_create(poldiff_avrule_free)) == NULL) {
00554                 avrule_destroy(&rs);
00555                 return NULL;
00556         }
00557         return rs;
00558 }
00559 
00560 void avrule_destroy(poldiff_avrule_summary_t ** rs)
00561 {
00562         if (rs != NULL && *rs != NULL) {
00563                 apol_vector_destroy(&(*rs)->diffs);
00564                 free(*rs);
00565                 *rs = NULL;
00566         }
00567 }
00568 
00569 /**
00570  * Reset the state of an AV rule differences.
00571  * @param diff The policy difference structure containing the differences
00572  * to reset.
00573  * @param idx Index into the avrule diffs array indicating which rule
00574  * type to reset, one of AVRULE_OFFSET_ALLOW, etc.
00575  * @return 0 on success and < 0 on error; if the call fails,
00576  * errno will be set and the user should call poldiff_destroy() on diff.
00577  */
00578 static int avrule_reset(poldiff_t * diff, avrule_offset_e idx)
00579 {
00580         int error = 0;
00581 
00582         avrule_destroy(&diff->avrule_diffs[idx]);
00583         diff->avrule_diffs[idx] = avrule_create();
00584         if (diff->avrule_diffs[idx] == NULL) {
00585                 error = errno;
00586                 ERR(diff, "%s", strerror(error));
00587                 errno = error;
00588                 return -1;
00589         }
00590 
00591         return 0;
00592 }
00593 
00594 int avrule_reset_allow(poldiff_t * diff)
00595 {
00596         return avrule_reset(diff, AVRULE_OFFSET_ALLOW);
00597 }
00598 
00599 int avrule_reset_auditallow(poldiff_t * diff)
00600 {
00601         return avrule_reset(diff, AVRULE_OFFSET_AUDITALLOW);
00602 }
00603 
00604 int avrule_reset_dontaudit(poldiff_t * diff)
00605 {
00606         return avrule_reset(diff, AVRULE_OFFSET_DONTAUDIT);
00607 }
00608 
00609 int avrule_reset_neverallow(poldiff_t * diff)
00610 {
00611         return avrule_reset(diff, AVRULE_OFFSET_NEVERALLOW);
00612 }
00613 
00614 static void avrule_free_item(void *item)
00615 {
00616         pseudo_avrule_t *a = (pseudo_avrule_t *) item;
00617         if (item != NULL) {
00618                 free(a->perms);
00619                 free(a->rules);
00620                 free(a);
00621         }
00622 }
00623 
00624 /**
00625  * Apply an ordering scheme to two pseudo-av rules.
00626  *
00627  * <ul>
00628  * <li>Sort by target pseudo-type value,
00629  * <li>Then by source pseudo-type value,
00630  * <li>Then by object class's BST's pointer value,
00631  * <li>Then by rule specified (allow, neverallow, etc.),
00632  * <li>Then choose unconditional rules over conditional rules,
00633  * <li>Then by conditional expression's BST's boolean pointer value.
00634  * </ul>
00635  *
00636  * If this function is being used for sorting (via avrule_get_items())
00637  * then sort by truth value, and then by branch (true branch, then
00638  * false branch).  Otherwise, when comparing rules (via avrule_comp())
00639  * then by truth value, inverting rule2's value if in the other
00640  * branch.
00641  */
00642 static int pseudo_avrule_comp(const pseudo_avrule_t * rule1, const pseudo_avrule_t * rule2, int is_sorting)
00643 {
00644         size_t i;
00645         uint32_t bool_val;
00646         if (rule1->target != rule2->target) {
00647                 return rule1->target - rule2->target;
00648         }
00649         if (rule1->source != rule2->source) {
00650                 return rule1->source - rule2->source;
00651         }
00652         if (rule1->cls != rule2->cls) {
00653                 return (int)(rule1->cls - rule2->cls);
00654         }
00655         if (rule1->spec != rule2->spec) {
00656                 return rule1->spec - rule2->spec;
00657         }
00658         if (rule1->bools[0] == NULL && rule2->bools[0] == NULL) {
00659                 /* both rules are unconditional */
00660                 return 0;
00661         } else if (rule1->bools[0] == NULL && rule2->bools[0] != NULL) {
00662                 /* unconditional rules come before conditional */
00663                 return -1;
00664         } else if (rule1->bools[0] != NULL && rule2->bools[0] == NULL) {
00665                 /* unconditional rules come before conditional */
00666                 return 1;
00667         }
00668         for (i = 0; i < (sizeof(rule1->bools) / sizeof(rule1->bools[0])); i++) {
00669                 if (rule1->bools[i] != rule2->bools[i]) {
00670                         return (int)(rule1->bools[i] - rule2->bools[i]);
00671                 }
00672         }
00673         if (is_sorting) {
00674                 if (rule1->branch != rule2->branch) {
00675                         return rule1->branch - rule2->branch;
00676                 }
00677                 return (int)rule1->bool_val - (int)rule2->bool_val;
00678         } else {
00679                 if (rule1->branch == rule2->branch) {
00680                         bool_val = rule2->bool_val;
00681                 } else {
00682                         bool_val = ~rule2->bool_val;
00683                 }
00684                 if (rule1->bool_val < bool_val) {
00685                         return -1;
00686                 } else if (rule1->bool_val > bool_val) {
00687                         return 1;
00688                 }
00689                 return 0;
00690         }
00691 }
00692 
00693 static int avrule_bst_comp(const void *x, const void *y, void *data __attribute__ ((unused)))
00694 {
00695         const pseudo_avrule_t *r1 = (const pseudo_avrule_t *)x;
00696         const pseudo_avrule_t *r2 = (const pseudo_avrule_t *)y;
00697         return pseudo_avrule_comp(r1, r2, 1);
00698 }
00699 
00700 /**
00701  * Given a conditional expression, convert its booleans to a sorted
00702  * array of pseudo-boolean values, assign that array to the
00703  * pseudo-avrule key, and then derive the truth table.
00704  *
00705  * @param diff Policy difference structure.
00706  * @param p Policy containing conditional.
00707  * @param cond Conditional expression to convert.
00708  * @param key Location to write converted expression.
00709  */
00710 static int avrule_build_cond(poldiff_t * diff, const apol_policy_t * p, const qpol_cond_t * cond, pseudo_avrule_t * key)
00711 {
00712         qpol_iterator_t *iter = NULL;
00713         qpol_cond_expr_node_t *node;
00714         uint32_t expr_type, truthiness;
00715         qpol_bool_t *bools[5] = { NULL, NULL, NULL, NULL, NULL }, *qbool;
00716         size_t i, j;
00717         size_t num_bools = 0;
00718         const char *bool_name;
00719         char *pseudo_bool, *t;
00720         qpol_policy_t *q = apol_policy_get_qpol(p);
00721         int retval = -1, error = 0, compval;
00722         if (qpol_cond_get_expr_node_iter(q, cond, &iter) < 0) {
00723                 error = errno;
00724                 goto cleanup;
00725         }
00726         for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
00727                 if (qpol_iterator_get_item(iter, (void **)&node) < 0 || qpol_cond_expr_node_get_expr_type(q, node, &expr_type) < 0) {
00728                         error = errno;
00729                         goto cleanup;
00730                 }
00731                 if (expr_type != QPOL_COND_EXPR_BOOL) {
00732                         continue;
00733                 }
00734                 if (qpol_cond_expr_node_get_bool(q, node, &qbool) < 0) {
00735                         error = errno;
00736                         goto cleanup;
00737                 }
00738                 for (i = 0; i < num_bools; i++) {
00739                         if (bools[i] == qbool) {
00740                                 break;
00741                         }
00742                 }
00743                 if (i >= num_bools) {
00744                         assert(i < 5);
00745                         bools[i] = qbool;
00746                         num_bools++;
00747                 }
00748         }
00749         for (i = 0; i < num_bools; i++) {
00750                 if (qpol_bool_get_name(q, bools[i], &bool_name) < 0) {
00751                         error = errno;
00752                         goto cleanup;
00753                 }
00754                 if (apol_bst_get_element(diff->bool_bst, (void *)bool_name, NULL, (void **)&pseudo_bool) < 0) {
00755                         error = EBADRQC;        /* should never get here */
00756                         ERR(diff, "%s", strerror(error));
00757                         assert(0);
00758                         goto cleanup;
00759                 }
00760                 key->bools[i] = pseudo_bool;
00761         }
00762 
00763         /* bubble sorth the pseudo bools (not bad because there are at
00764          * most five elements */
00765         for (i = num_bools; i > 1; i--) {
00766                 for (j = 1; j < i; j++) {
00767                         compval = strcmp(key->bools[j - 1], key->bools[j]);
00768                         if (compval > 0) {
00769                                 t = key->bools[j];
00770                                 key->bools[j] = key->bools[j - 1];
00771                                 key->bools[j - 1] = t;
00772                                 qbool = bools[j];
00773                                 bools[j] = bools[j - 1];
00774                                 bools[j - 1] = qbool;
00775                         }
00776                 }
00777         }
00778 
00779         /* now compute the truth table for the booleans */
00780         key->bool_val = 0;
00781         for (i = 0; i < 32; i++) {
00782                 for (j = 0; j < num_bools; j++) {
00783                         int state = ((i & (1 << j)) ? 1 : 0);
00784                         if (qpol_bool_set_state_no_eval(q, bools[j], state) < 0) {
00785                                 error = errno;
00786                                 goto cleanup;
00787                         }
00788                 }
00789                 if (qpol_cond_eval(q, cond, &truthiness) < 0) {
00790                         error = errno;
00791                         goto cleanup;
00792                 }
00793                 key->bool_val = (key->bool_val << 1) | truthiness;
00794         }
00795 
00796         key->cond = cond;
00797         retval = 0;
00798       cleanup:
00799         qpol_iterator_destroy(&iter);
00800         return retval;
00801 }
00802 
00803 /**
00804  * Bubble sort the permissions within a pseudo-avrule, sorted by
00805  * pointer value.  (Bubble-sort is fine because the number of
00806  * permissions will usually be less than 10.)  Then uniquify the list.
00807  *
00808  * @param key Rule whose permissions to sort.
00809  */
00810 static void sort_and_uniquify_perms(pseudo_avrule_t * key)
00811 {
00812         size_t i, j;
00813         char *t;
00814         for (i = key->num_perms; i > 1; i--) {
00815                 for (j = 1; j < i; j++) {
00816                         if (key->perms[j - 1] > key->perms[j]) {
00817                                 t = key->perms[j];
00818                                 key->perms[j] = key->perms[j - 1];
00819                                 key->perms[j - 1] = t;
00820                         }
00821                 }
00822         }
00823         for (i = 1; i < key->num_perms; i++) {
00824                 if (key->perms[i] == key->perms[i - 1]) {
00825                         memmove(key->perms + i, key->perms + i + 1, (key->num_perms - i - 1) * sizeof(key->perms[0]));
00826                         key->num_perms--;
00827                 }
00828         }
00829 }
00830 
00831 /**
00832  * Given a rule, construct a new pseudo-avrule and insert it into the
00833  * BST if not already there.
00834  *
00835  * @param diff Policy difference structure.
00836  * @param p Policy from which the rule came.
00837  * @param rule AV rule to insert.
00838  * @param source Source pseudo-type value.
00839  * @param target Target pseudo-type value.
00840  * @param b BST containing pseudo-avrules.
00841  *
00842  * @return 0 on success, < 0 on error.
00843  */
00844 static int avrule_add_to_bst(poldiff_t * diff, const apol_policy_t * p,
00845                              const qpol_avrule_t * rule, uint32_t source, uint32_t target, apol_bst_t * b)
00846 {
00847         pseudo_avrule_t *key, *inserted_key;
00848         const qpol_class_t *obj_class;
00849         qpol_iterator_t *perm_iter = NULL;
00850         const char *class_name;
00851         char *perm_name, *pseudo_perm, **t;
00852         size_t num_perms;
00853         const qpol_cond_t *cond;
00854         qpol_policy_t *q = apol_policy_get_qpol(p);
00855         int retval = -1, error = 0, compval;
00856         if ((key = calloc(1, sizeof(*key))) == NULL) {
00857                 error = errno;
00858                 ERR(diff, "%s", strerror(error));
00859                 goto cleanup;
00860         }
00861         if (qpol_avrule_get_rule_type(q, rule, &(key->spec)) < 0 ||
00862             qpol_avrule_get_object_class(q, rule, &obj_class) < 0 ||
00863             qpol_avrule_get_perm_iter(q, rule, &perm_iter) < 0 || qpol_avrule_get_cond(q, rule, &cond) < 0) {
00864                 error = errno;
00865                 goto cleanup;
00866         }
00867         if (qpol_class_get_name(q, obj_class, &class_name) < 0) {
00868                 error = errno;
00869                 goto cleanup;
00870         }
00871         if (apol_bst_get_element(diff->class_bst, (void *)class_name, NULL, (void **)&key->cls) < 0) {
00872                 error = EBADRQC;       /* should never get here */
00873                 ERR(diff, "%s", strerror(error));
00874                 assert(0);
00875                 goto cleanup;
00876         }
00877         key->source = source;
00878         key->target = target;
00879         if (cond != NULL && (qpol_avrule_get_which_list(q, rule, &(key->branch)) < 0 || avrule_build_cond(diff, p, cond, key) < 0)) {
00880                 error = errno;
00881                 goto cleanup;
00882         }
00883 
00884         /* insert this pseudo into the tree if not already there */
00885         if ((compval = apol_bst_insert_and_get(b, (void **)&key, NULL)) < 0) {
00886                 error = errno;
00887                 ERR(diff, "%s", strerror(error));
00888                 goto cleanup;
00889         }
00890         inserted_key = key;
00891         key = NULL;
00892 
00893         /* append and uniquify this rule's permissions */
00894         if (qpol_iterator_get_size(perm_iter, &num_perms) < 0) {
00895                 error = errno;
00896                 goto cleanup;
00897         }
00898         if ((t = realloc(inserted_key->perms, (inserted_key->num_perms + num_perms) * sizeof(*t))) == NULL) {
00899                 error = errno;
00900                 ERR(diff, "%s", strerror(error));
00901                 goto cleanup;
00902         }
00903         inserted_key->perms = t;
00904         for (; !qpol_iterator_end(perm_iter); qpol_iterator_next(perm_iter)) {
00905                 if (qpol_iterator_get_item(perm_iter, (void *)&perm_name) < 0) {
00906                         error = errno;
00907                         goto cleanup;
00908                 }
00909                 if (apol_bst_get_element(diff->perm_bst, perm_name, NULL, (void **)&pseudo_perm) < 0) {
00910                         error = EBADRQC;        /* should never get here */
00911                         ERR(diff, "%s", strerror(error));
00912                         assert(0);
00913                         free(perm_name);
00914                         goto cleanup;
00915                 }
00916                 free(perm_name);
00917                 inserted_key->perms[(inserted_key->num_perms)++] = pseudo_perm;
00918         }
00919         sort_and_uniquify_perms(inserted_key);
00920 
00921         /* store the rule pointer, to be used for showing line numbers */
00922         if (qpol_policy_has_capability(q, QPOL_CAP_LINE_NUMBERS)) {
00923                 const qpol_avrule_t **a = realloc(inserted_key->rules,
00924                                                   (inserted_key->num_rules + 1) * sizeof(*a));
00925                 if (a == NULL) {
00926                         error = errno;
00927                         ERR(diff, "%s", strerror(error));
00928                         goto cleanup;
00929                 }
00930                 inserted_key->rules = a;
00931                 inserted_key->rules[inserted_key->num_rules++] = rule;
00932         }
00933 
00934         retval = 0;
00935       cleanup:
00936         qpol_iterator_destroy(&perm_iter);
00937         if (retval < 0) {
00938                 avrule_free_item(key);
00939         }
00940         errno = error;
00941         return retval;
00942 }
00943 
00944 /**
00945  * Given a rule, expand its source and target types into individual
00946  * pseudo-type values.  Then add the expanded rules to the BST.  This
00947  * is needed for when the source and/or target is an attribute.
00948  *
00949  * @param diff Policy difference structure.
00950  * @param p Policy from which the rule came.
00951  * @param rule AV rule to insert.
00952  * @param b BST containing pseudo-avrules.
00953  *
00954  * @return 0 on success, < 0 on error.
00955  */
00956 static int avrule_expand(poldiff_t * diff, const apol_policy_t * p, const qpol_avrule_t * rule, apol_bst_t * b)
00957 {
00958         const qpol_type_t *source, *orig_target, *target;
00959         unsigned char source_attr, target_attr;
00960         qpol_iterator_t *source_iter = NULL, *target_iter = NULL;
00961         uint32_t source_val, target_val;
00962         qpol_policy_t *q = apol_policy_get_qpol(p);
00963         int which = (p == diff->orig_pol ? POLDIFF_POLICY_ORIG : POLDIFF_POLICY_MOD);
00964         int retval = -1, error = 0;
00965         if (qpol_avrule_get_source_type(q, rule, &source) < 0 ||
00966             qpol_avrule_get_target_type(q, rule, &orig_target) < 0 ||
00967             qpol_type_get_isattr(q, source, &source_attr) < 0 || qpol_type_get_isattr(q, orig_target, &target_attr)) {
00968                 error = errno;
00969                 goto cleanup;
00970         }
00971 #ifdef SETOOLS_DEBUG
00972         const char *orig_source_name, *orig_target_name;
00973         qpol_type_get_name(q, source, &orig_source_name);
00974         qpol_type_get_name(q, orig_target, &orig_target_name);
00975 #endif
00976 
00977         if (source_attr) {
00978                 if (qpol_type_get_type_iter(q, source, &source_iter) < 0) {
00979                         error = errno;
00980                         goto cleanup;
00981                 }
00982                 /* handle situation where a rule has as its source an
00983                  * attribute without any types */
00984                 if (qpol_iterator_end(source_iter)) {
00985                         retval = 0;
00986                         goto cleanup;
00987                 }
00988         }
00989         do {
00990                 if (source_attr) {
00991                         if (qpol_iterator_get_item(source_iter, (void **)&source) < 0) {
00992                                 error = errno;
00993                                 goto cleanup;
00994                         }
00995                         qpol_iterator_next(source_iter);
00996                 }
00997                 if (target_attr) {
00998                         if (qpol_type_get_type_iter(q, orig_target, &target_iter) < 0) {
00999                                 error = errno;
01000                                 goto cleanup;
01001                         }
01002                         /* handle situation where a rule has as its
01003                          * target an attribute without any types */
01004                         if (qpol_iterator_end(target_iter)) {
01005                                 retval = 0;
01006                                 goto cleanup;
01007                         }
01008                 } else {
01009                         target = orig_target;
01010                 }
01011                 do {
01012                         if (target_attr) {
01013                                 if (qpol_iterator_get_item(target_iter, (void **)&target) < 0) {
01014                                         error = errno;
01015                                         goto cleanup;
01016                                 }
01017                                 qpol_iterator_next(target_iter);
01018                         }
01019 #ifdef SETOOLS_DEBUG
01020                         const char *n1, *n2;
01021                         qpol_type_get_name(q, source, &n1);
01022                         qpol_type_get_name(q, target, &n2);
01023 #endif
01024                         if ((source_val = type_map_lookup(diff, source, which)) == 0 ||
01025                             (target_val = type_map_lookup(diff, target, which)) == 0 ||
01026                             avrule_add_to_bst(diff, p, rule, source_val, target_val, b) < 0) {
01027                                 error = errno;
01028                                 goto cleanup;
01029                         }
01030                 } while (target_attr && !qpol_iterator_end(target_iter));
01031                 qpol_iterator_destroy(&target_iter);
01032         } while (source_attr && !qpol_iterator_end(source_iter));
01033         retval = 0;
01034       cleanup:
01035         qpol_iterator_destroy(&source_iter);
01036         qpol_iterator_destroy(&target_iter);
01037         errno = error;
01038         return retval;
01039 }
01040 
01041 /**
01042  * Get a vector of avrules from the given policy, sorted.  This
01043  * function will remap source and target types to their pseudo-type
01044  * value equivalents.
01045  *
01046  * @param diff Policy diff error handler.
01047  * @param policy The policy from which to get the items.
01048  * @param which Kind of rule to get, one of QPOL_RULE_ALLOW, etc.
01049  *
01050  * @return A newly allocated vector of all av rules (of type
01051  * pseudo_avrule_t).  The caller is responsible for calling
01052  * apol_vector_destroy() afterwards.  On error, return NULL and set
01053  * errno.
01054  */
01055 static apol_vector_t *avrule_get_items(poldiff_t * diff, const apol_policy_t * policy, const unsigned int which)
01056 {
01057         apol_vector_t *bools = NULL, *bool_states = NULL;
01058         size_t i, num_rules, j;
01059         apol_bst_t *b = NULL;
01060         apol_vector_t *v = NULL;
01061         qpol_iterator_t *iter = NULL;
01062         const qpol_avrule_t *rule;
01063         qpol_policy_t *q = apol_policy_get_qpol(policy);
01064         int retval = -1, error = 0;
01065 
01066         /* special case:  if getting neverallow rules if the policy
01067            does not support it, then return an empty vector */
01068         if (which == QPOL_RULE_NEVERALLOW && !qpol_policy_has_capability(q, QPOL_CAP_NEVERALLOW)) {
01069                 v = apol_vector_create_with_capacity(1, avrule_free_item);
01070                 if (v == NULL) {
01071                         ERR(diff, "%s", strerror(error));
01072                 }
01073                 return v;
01074         }
01075 
01076         if (poldiff_build_bsts(diff) < 0) {
01077                 error = errno;
01078                 goto cleanup;
01079         }
01080 
01081         /* store original boolean values */
01082         if (apol_bool_get_by_query(policy, NULL, &bools) < 0) {
01083                 error = errno;
01084                 goto cleanup;
01085         }
01086         if ((bool_states = apol_vector_create_with_capacity(apol_vector_get_size(bools), NULL)) == NULL) {
01087                 error = errno;
01088                 ERR(diff, "%s", strerror(error));
01089                 goto cleanup;
01090         }
01091         for (i = 0; i < apol_vector_get_size(bools); i++) {
01092                 qpol_bool_t *qbool = apol_vector_get_element(bools, i);
01093                 int state;
01094                 if (qpol_bool_get_state(q, qbool, &state) < 0) {
01095                         error = errno;
01096                         goto cleanup;
01097                 }
01098                 if (apol_vector_append(bool_states, (void *)((size_t) state)) < 0) {
01099                         error = errno;
01100                         ERR(diff, "%s", strerror(error));
01101                         goto cleanup;
01102                 }
01103         }
01104         if ((b = apol_bst_create(avrule_bst_comp, avrule_free_item)) == NULL) {
01105                 error = errno;
01106                 ERR(diff, "%s", strerror(error));
01107                 goto cleanup;
01108         }
01109         if (qpol_policy_get_avrule_iter(q, which, &iter) < 0) {
01110 
01111                 error = errno;
01112                 goto cleanup;
01113         }
01114         qpol_iterator_get_size(iter, &num_rules);
01115         for (j = 0; !qpol_iterator_end(iter); qpol_iterator_next(iter), j++) {
01116                 if (qpol_iterator_get_item(iter, (void **)&rule) < 0 || avrule_expand(diff, policy, rule, b) < 0) {
01117                         error = errno;
01118                         goto cleanup;
01119                 }
01120                 if (!(j % 1024)) {
01121                         int percent = 50 * j / num_rules + (policy == diff->mod_pol ? 50 : 0);
01122                         INFO(diff, "Computing AV rule difference: %02d%% complete", percent);
01123                 }
01124         }
01125         if ((v = apol_bst_get_vector(b, 1)) == NULL) {
01126                 error = errno;
01127                 ERR(diff, "%s", strerror(error));
01128                 goto cleanup;
01129         }
01130         retval = 0;
01131       cleanup:
01132         /* restore boolean states */
01133         for (i = 0; i < apol_vector_get_size(bools); i++) {
01134                 qpol_bool_t *qbool = apol_vector_get_element(bools, i);
01135                 int state = (int)((size_t) apol_vector_get_element(bool_states, i));
01136                 qpol_bool_set_state_no_eval(q, qbool, state);
01137         }
01138         qpol_policy_reevaluate_conds(q);
01139         apol_vector_destroy(&bools);
01140         apol_vector_destroy(&bool_states);
01141         apol_bst_destroy(&b);
01142         qpol_iterator_destroy(&iter);
01143         if (retval < 0) {
01144                 apol_vector_destroy(&v);
01145                 errno = error;
01146                 return NULL;
01147         }
01148         return v;
01149 }
01150 
01151 apol_vector_t *avrule_get_items_allow(poldiff_t * diff, const apol_policy_t * policy)
01152 {
01153         return avrule_get_items(diff, policy, QPOL_RULE_ALLOW);
01154 }
01155 
01156 apol_vector_t *avrule_get_items_auditallow(poldiff_t * diff, const apol_policy_t * policy)
01157 {
01158         return avrule_get_items(diff, policy, QPOL_RULE_AUDITALLOW);
01159 }
01160 
01161 apol_vector_t *avrule_get_items_dontaudit(poldiff_t * diff, const apol_policy_t * policy)
01162 {
01163         return avrule_get_items(diff, policy, QPOL_RULE_DONTAUDIT);
01164 }
01165 
01166 apol_vector_t *avrule_get_items_neverallow(poldiff_t * diff, const apol_policy_t * policy)
01167 {
01168         return avrule_get_items(diff, policy, QPOL_RULE_NEVERALLOW);
01169 }
01170 
01171 int avrule_comp(const void *x, const void *y, const poldiff_t * diff __attribute__ ((unused)))
01172 {
01173         const pseudo_avrule_t *r1 = (const pseudo_avrule_t *)x;
01174         const pseudo_avrule_t *r2 = (const pseudo_avrule_t *)y;
01175         return pseudo_avrule_comp(r1, r2, 0);
01176 }
01177 
01178 /**
01179  * Allocate and return a new avrule difference object.  If the
01180  * pseudo-avrule's source and/or target expands to multiple read
01181  * types, then just choose the first one for display.
01182  *
01183  * @param diff Policy diff error handler.
01184  * @param form Form of the difference.
01185  * @param rule Pseudo avrule that changed.
01186  *
01187  * @return A newly allocated and initialized diff, or NULL upon error.
01188  * The caller is responsible for calling poldiff_avrule_free() upon
01189  * the returned value.
01190  */
01191 static poldiff_avrule_t *make_avdiff(poldiff_t * diff, poldiff_form_e form, pseudo_avrule_t * rule)
01192 {
01193         poldiff_avrule_t *pa = NULL;
01194         const char *n1, *n2;
01195         int error = 0;
01196         if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) {
01197                 n1 = type_map_get_name(diff, rule->source, POLDIFF_POLICY_MOD);
01198                 n2 = type_map_get_name(diff, rule->target, POLDIFF_POLICY_MOD);
01199         } else {
01200                 n1 = type_map_get_name(diff, rule->source, POLDIFF_POLICY_ORIG);
01201                 n2 = type_map_get_name(diff, rule->target, POLDIFF_POLICY_ORIG);
01202         }
01203         assert(n1 != NULL && n2 != NULL);
01204         if ((pa = calloc(1, sizeof(*pa))) == NULL) {
01205                 error = errno;
01206                 ERR(diff, "%s", strerror(error));
01207                 goto cleanup;
01208         }
01209         pa->spec = rule->spec;
01210         pa->source = n1;
01211         pa->target = n2;
01212         pa->cls = rule->cls;
01213         pa->form = form;
01214         pa->cond = rule->cond;
01215         pa->branch = rule->branch;
01216       cleanup:
01217         if (error != 0) {
01218                 poldiff_avrule_free(pa);
01219                 errno = error;
01220                 return NULL;
01221         }
01222         return pa;
01223 }
01224 
01225 /**
01226  * Create, initialize, and insert a new semantic difference entry for
01227  * a pseudo-av rule.
01228  *
01229  * @param diff The policy difference structure to which to add the entry.
01230  * @param form The form of the difference.
01231  * @param item Item for which the entry is being created.
01232  * @param idx Index into the avrule differences specifying into which
01233  * to place the constructed pseudo-av rule.
01234  *
01235  * @return 0 on success and < 0 on error; if the call fails, set errno
01236  * and leave the policy difference structure unchanged.
01237  */
01238 static int avrule_new_diff(poldiff_t * diff, poldiff_form_e form, const void *item, avrule_offset_e idx)
01239 {
01240         pseudo_avrule_t *rule = (pseudo_avrule_t *) item;
01241         poldiff_avrule_t *pa = NULL;
01242         const apol_vector_t *v1, *v2;
01243         apol_vector_t **target;
01244         apol_policy_t *p;
01245         size_t i;
01246         int retval = -1, error = errno;
01247 
01248         /* check if form should really become ADD_TYPE / REMOVE_TYPE,
01249          * by seeing if the /other/ policy's reverse lookup is
01250          * empty */
01251         if (form == POLDIFF_FORM_ADDED) {
01252                 if ((v1 = type_map_lookup_reverse(diff, rule->source, POLDIFF_POLICY_ORIG)) == NULL ||
01253                     (v2 = type_map_lookup_reverse(diff, rule->target, POLDIFF_POLICY_ORIG)) == NULL) {
01254                         error = errno;
01255                         goto cleanup;
01256                 }
01257                 if (apol_vector_get_size(v1) == 0 || apol_vector_get_size(v2) == 0) {
01258                         form = POLDIFF_FORM_ADD_TYPE;
01259                 }
01260                 p = diff->mod_pol;
01261         } else {
01262                 if ((v1 = type_map_lookup_reverse(diff, rule->source, POLDIFF_POLICY_MOD)) == NULL ||
01263                     (v2 = type_map_lookup_reverse(diff, rule->target, POLDIFF_POLICY_MOD)) == NULL) {
01264                         error = errno;
01265                         goto cleanup;
01266                 }
01267                 if (apol_vector_get_size(v1) == 0 || apol_vector_get_size(v2) == 0) {
01268                         form = POLDIFF_FORM_REMOVE_TYPE;
01269                 }
01270                 p = diff->orig_pol;
01271         }
01272 
01273         pa = make_avdiff(diff, form, rule);
01274         if (pa == NULL) {
01275                 return -1;
01276         }
01277 
01278         if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) {
01279                 if ((pa->removed_perms = apol_vector_create_with_capacity(1, NULL)) == NULL ||
01280                     (pa->unmodified_perms = apol_vector_create_with_capacity(1, NULL)) == NULL) {
01281                         error = errno;
01282                         ERR(diff, "%s", strerror(error));
01283                         goto cleanup;
01284                 }
01285                 target = &pa->added_perms;
01286         } else {
01287                 if ((pa->added_perms = apol_vector_create_with_capacity(1, NULL)) == NULL ||
01288                     (pa->unmodified_perms = apol_vector_create_with_capacity(1, NULL)) == NULL) {
01289                         error = errno;
01290                         ERR(diff, "%s", strerror(error));
01291                         goto cleanup;
01292                 }
01293                 target = &pa->removed_perms;
01294         }
01295         if ((*target = apol_vector_create_with_capacity(rule->num_perms, NULL)) == NULL) {
01296                 error = errno;
01297                 ERR(diff, "%s", strerror(error));
01298                 goto cleanup;
01299         }
01300         for (i = 0; i < rule->num_perms; i++) {
01301                 if (apol_vector_append(*target, rule->perms[i]) < 0) {
01302                         error = errno;
01303                         ERR(diff, "%s", strerror(error));
01304                         goto cleanup;
01305                 }
01306         }
01307         apol_vector_sort(*target, apol_str_strcmp, NULL);
01308 
01309         if (qpol_policy_has_capability(apol_policy_get_qpol(p), QPOL_CAP_LINE_NUMBERS)) {
01310                 /* calculate line numbers */
01311                 apol_vector_t *vl = NULL;
01312                 if ((vl = apol_vector_create(NULL)) == NULL) {
01313                         error = errno;
01314                         ERR(diff, "%s", strerror(error));
01315                         goto cleanup;
01316                 }
01317                 if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) {
01318                         pa->mod_linenos = vl;
01319                 } else {
01320                         pa->orig_linenos = vl;
01321                 }
01322 
01323                 /* copy rule pointers for delayed line number claculation */
01324                 if (form == POLDIFF_FORM_ADDED || form == POLDIFF_FORM_ADD_TYPE) {
01325                         pa->num_mod_rules = rule->num_rules;
01326                         pa->mod_rules = calloc(rule->num_rules, sizeof(qpol_avrule_t *));
01327                         if (!pa->mod_rules) {
01328                                 error = errno;
01329                                 ERR(diff, "%s", strerror(error));
01330                                 goto cleanup;
01331                         }
01332                         memcpy(pa->mod_rules, rule->rules, rule->num_rules * sizeof(qpol_avrule_t *));
01333                 } else {
01334                         pa->num_orig_rules = rule->num_rules;
01335                         pa->orig_rules = calloc(rule->num_rules, sizeof(qpol_avrule_t *));
01336                         if (!pa->orig_rules) {
01337                                 error = errno;
01338                                 ERR(diff, "%s", strerror(error));
01339                                 goto cleanup;
01340                         }
01341                         memcpy(pa->orig_rules, rule->rules, rule->num_rules * sizeof(qpol_avrule_t *));
01342                 }
01343         }
01344 
01345         if (apol_vector_append(diff->avrule_diffs[idx]->diffs, pa) < 0) {
01346                 error = errno;
01347                 ERR(diff, "%s", strerror(error));
01348                 goto cleanup;
01349         }
01350         switch (form) {
01351         case POLDIFF_FORM_ADDED:
01352                 diff->avrule_diffs[idx]->num_added++;
01353                 break;
01354         case POLDIFF_FORM_ADD_TYPE:
01355                 diff->avrule_diffs[idx]->num_added_type++;
01356                 break;
01357         case POLDIFF_FORM_REMOVED:
01358                 diff->avrule_diffs[idx]->num_removed++;
01359                 break;
01360         case POLDIFF_FORM_REMOVE_TYPE:
01361                 diff->avrule_diffs[idx]->num_removed_type++;
01362                 break;
01363         default:
01364                 error = EBADRQC;       /* should never get here */
01365                 ERR(diff, "%s", strerror(error));
01366                 assert(0);
01367                 goto cleanup;
01368         }
01369         diff->avrule_diffs[idx]->diffs_sorted = 0;
01370         retval = 0;
01371       cleanup:
01372         if (retval < 0) {
01373                 poldiff_avrule_free(pa);
01374         }
01375         errno = error;
01376         return retval;
01377 }
01378 
01379 int avrule_new_diff_allow(poldiff_t * diff, poldiff_form_e form, const void *item)
01380 {
01381         return avrule_new_diff(diff, form, item, AVRULE_OFFSET_ALLOW);
01382 }
01383 
01384 int avrule_new_diff_auditallow(poldiff_t * diff, poldiff_form_e form, const void *item)
01385 {
01386         return avrule_new_diff(diff, form, item, AVRULE_OFFSET_AUDITALLOW);
01387 }
01388 
01389 int avrule_new_diff_dontaudit(poldiff_t * diff, poldiff_form_e form, const void *item)
01390 {
01391         return avrule_new_diff(diff, form, item, AVRULE_OFFSET_DONTAUDIT);
01392 }
01393 
01394 int avrule_new_diff_neverallow(poldiff_t * diff, poldiff_form_e form, const void *item)
01395 {
01396         return avrule_new_diff(diff, form, item, AVRULE_OFFSET_NEVERALLOW);
01397 }
01398 
01399 /**
01400  * Compute the semantic difference of two pseudo-av rules for which
01401  * the compare callback returns 0.  If a difference is found then
01402  * allocate, initialize, and insert a new semantic difference entry
01403  * for that pseudo-av rule.
01404  *
01405  * @param diff The policy difference structure associated with both
01406  * pseudo-av rules and to which to add an entry if needed.
01407  * @param x The pseudo-av rule from the original policy.
01408  * @param y The pseudo-av rule from the modified policy.
01409  * @param idx Index into the avrule differences specifying into which
01410  * to place the constructed pseudo-av rule.
01411  *
01412  * @return 0 on success and < 0 on error; if the call fails, set errno
01413  * and leave the policy difference structure unchanged.
01414  */
01415 static int avrule_deep_diff(poldiff_t * diff, const void *x, const void *y, avrule_offset_e idx)
01416 {
01417         pseudo_avrule_t *r1 = (pseudo_avrule_t *) x;
01418         pseudo_avrule_t *r2 = (pseudo_avrule_t *) y;
01419         apol_vector_t *unmodified_perms = NULL, *added_perms = NULL, *removed_perms = NULL;
01420         size_t i, j;
01421         char *perm1, *perm2;
01422         poldiff_avrule_t *pa = NULL;
01423         int retval = -1, error = 0;
01424 
01425         if ((unmodified_perms = apol_vector_create(NULL)) == NULL ||
01426             (added_perms = apol_vector_create(NULL)) == NULL || (removed_perms = apol_vector_create(NULL)) == NULL) {
01427                 error = errno;
01428                 ERR(diff, "%s", strerror(error));
01429                 goto cleanup;
01430         }
01431         for (i = j = 0; i < r1->num_perms;) {
01432                 if (j >= r2->num_perms)
01433                         break;
01434                 perm1 = r1->perms[i];
01435                 perm2 = r2->perms[j];
01436                 if (perm2 > perm1) {
01437                         if (apol_vector_append(removed_perms, perm1) < 0) {
01438                                 error = errno;
01439                                 ERR(diff, "%s", strerror(error));
01440                                 goto cleanup;
01441                         }
01442                         i++;
01443                 } else if (perm1 > perm2) {
01444                         if (apol_vector_append(added_perms, perm2) < 0) {
01445                                 error = errno;
01446                                 ERR(diff, "%s", strerror(error));
01447                                 goto cleanup;
01448                         }
01449                         j++;
01450                 } else {
01451                         if (apol_vector_append(unmodified_perms, perm1) < 0) {
01452                                 error = errno;
01453                                 ERR(diff, "%s", strerror(error));
01454                                 goto cleanup;
01455                         }
01456                         i++;
01457                         j++;
01458                 }
01459         }
01460 
01461         for (; i < r1->num_perms; i++) {
01462                 perm1 = r1->perms[i];
01463                 if (apol_vector_append(removed_perms, perm1) < 0) {
01464                         error = errno;
01465                         ERR(diff, "%s", strerror(error));
01466                         goto cleanup;
01467                 }
01468         }
01469         for (; j < r2->num_perms; j++) {
01470                 perm2 = r2->perms[j];
01471                 if (apol_vector_append(added_perms, perm2) < 0) {
01472                         error = errno;
01473                         ERR(diff, "%s", strerror(error));
01474                         goto cleanup;
01475                 }
01476         }
01477         if (apol_vector_get_size(added_perms) > 0 || apol_vector_get_size(removed_perms) > 0) {
01478                 if ((pa = make_avdiff(diff, POLDIFF_FORM_MODIFIED, r1)) == NULL) {
01479                         error = errno;
01480                         goto cleanup;
01481                 }
01482                 pa->unmodified_perms = unmodified_perms;
01483                 pa->added_perms = added_perms;
01484                 pa->removed_perms = removed_perms;
01485                 unmodified_perms = NULL;
01486                 added_perms = NULL;
01487                 removed_perms = NULL;
01488                 apol_vector_sort(pa->unmodified_perms, apol_str_strcmp, NULL);
01489                 apol_vector_sort(pa->added_perms, apol_str_strcmp, NULL);
01490                 apol_vector_sort(pa->removed_perms, apol_str_strcmp, NULL);
01491 
01492                 /* calculate line numbers */
01493                 if (qpol_policy_has_capability(apol_policy_get_qpol(diff->orig_pol), QPOL_CAP_LINE_NUMBERS)) {
01494                         if ((pa->orig_linenos = apol_vector_create(NULL)) == NULL) {
01495                                 error = errno;
01496                                 ERR(diff, "%s", strerror(error));
01497                                 goto cleanup;
01498                         }
01499 
01500                         /* copy rule pointers for delayed line number claculation */
01501                         pa->num_orig_rules = r1->num_rules;
01502                         pa->orig_rules = calloc(r1->num_rules, sizeof(qpol_avrule_t *));
01503                         if (!pa->orig_rules) {
01504                                 error = errno;
01505                                 ERR(diff, "%s", strerror(error));
01506                                 goto cleanup;
01507                         }
01508                         memcpy(pa->orig_rules, r1->rules, r1->num_rules * sizeof(qpol_avrule_t *));
01509                 }
01510                 if (qpol_policy_has_capability(apol_policy_get_qpol(diff->mod_pol), QPOL_CAP_LINE_NUMBERS)) {
01511                         if ((pa->mod_linenos = apol_vector_create(NULL)) == NULL) {
01512                                 error = errno;
01513                                 ERR(diff, "%s", strerror(error));
01514                                 goto cleanup;
01515                         }
01516 
01517                         /* copy rule pointers for delayed line number claculation */
01518                         pa->num_mod_rules = r2->num_rules;
01519                         pa->mod_rules = calloc(r2->num_rules, sizeof(qpol_avrule_t *));
01520                         if (!pa->mod_rules) {
01521                                 error = errno;
01522                                 ERR(diff, "%s", strerror(error));
01523                                 goto cleanup;
01524                         }
01525                         memcpy(pa->mod_rules, r2->rules, r2->num_rules * sizeof(qpol_avrule_t *));
01526                 }
01527                 if (apol_vector_append(diff->avrule_diffs[idx]->diffs, pa) < 0) {
01528                         error = errno;
01529                         ERR(diff, "%s", strerror(error));
01530                         goto cleanup;
01531                 }
01532                 diff->avrule_diffs[idx]->num_modified++;
01533                 diff->avrule_diffs[idx]->diffs_sorted = 0;
01534         }
01535         retval = 0;
01536       cleanup:
01537         apol_vector_destroy(&unmodified_perms);
01538         apol_vector_destroy(&added_perms);
01539         apol_vector_destroy(&removed_perms);
01540         if (retval != 0) {
01541                 poldiff_avrule_free(pa);
01542         }
01543         errno = error;
01544         return retval;
01545 }
01546 
01547 int avrule_deep_diff_allow(poldiff_t * diff, const void *x, const void *y)
01548 {
01549         return avrule_deep_diff(diff, x, y, AVRULE_OFFSET_ALLOW);
01550 }
01551 
01552 int avrule_deep_diff_auditallow(poldiff_t * diff, const void *x, const void *y)
01553 {
01554         return avrule_deep_diff(diff, x, y, AVRULE_OFFSET_AUDITALLOW);
01555 }
01556 
01557 int avrule_deep_diff_dontaudit(poldiff_t * diff, const void *x, const void *y)
01558 {
01559         return avrule_deep_diff(diff, x, y, AVRULE_OFFSET_DONTAUDIT);
01560 }
01561 
01562 int avrule_deep_diff_neverallow(poldiff_t * diff, const void *x, const void *y)
01563 {
01564         return avrule_deep_diff(diff, x, y, AVRULE_OFFSET_NEVERALLOW);
01565 }
01566 
01567 int avrule_enable_line_numbers(poldiff_t * diff, avrule_offset_e idx)
01568 {
01569         const apol_vector_t *av = NULL;
01570         poldiff_avrule_t *avrule = NULL;
01571         size_t i, j;
01572         qpol_iterator_t *iter = NULL;
01573         qpol_syn_avrule_t *sav = NULL;
01574         int error = 0;
01575         unsigned long lineno = 0;
01576 
01577         av = poldiff_get_avrule_vector(diff, idx);
01578 
01579         for (i = 0; i < apol_vector_get_size(av); i++) {
01580                 avrule = apol_vector_get_element(av, i);
01581                 if (apol_vector_get_size(avrule->mod_linenos) || apol_vector_get_size(avrule->orig_linenos))
01582                         continue;
01583                 for (j = 0; j < avrule->num_orig_rules; j++) {
01584                         if (qpol_avrule_get_syn_avrule_iter(diff->orig_qpol, avrule->orig_rules[j], &iter)) {
01585                                 error = errno;
01586                                 goto err;
01587                         }
01588                         for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
01589                                 if (qpol_iterator_get_item(iter, (void **)&sav) < 0) {
01590                                         error = errno;
01591                                         ERR(diff, "%s", strerror(error));
01592                                         goto err;
01593                                 }
01594                                 if (qpol_syn_avrule_get_lineno(diff->orig_qpol, sav, &lineno) < 0) {
01595                                         error = errno;
01596                                         goto err;
01597                                 }
01598                                 if (apol_vector_append(avrule->orig_linenos, (void *)lineno) < 0) {
01599                                         error = errno;
01600                                         ERR(diff, "%s", strerror(error));
01601                                         goto err;
01602                                 }
01603                         }
01604                         qpol_iterator_destroy(&iter);
01605                 }
01606                 apol_vector_sort_uniquify(avrule->orig_linenos, NULL, NULL);
01607                 for (j = 0; j < avrule->num_mod_rules; j++) {
01608                         if (qpol_avrule_get_syn_avrule_iter(diff->mod_qpol, avrule->mod_rules[j], &iter)) {
01609                                 error = errno;
01610                                 goto err;
01611                         }
01612                         for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
01613                                 if (qpol_iterator_get_item(iter, (void **)&sav) < 0) {
01614                                         error = errno;
01615                                         ERR(diff, "%s", strerror(error));
01616                                         goto err;
01617                                 }
01618                                 if (qpol_syn_avrule_get_lineno(diff->mod_qpol, sav, &lineno) < 0) {
01619                                         error = errno;
01620                                         goto err;
01621                                 }
01622                                 if (apol_vector_append(avrule->mod_linenos, (void *)lineno) < 0) {
01623                                         error = errno;
01624                                         ERR(diff, "%s", strerror(error));
01625                                         goto err;
01626                                 }
01627                         }
01628                         qpol_iterator_destroy(&iter);
01629                 }
01630                 apol_vector_sort_uniquify(avrule->mod_linenos, NULL, NULL);
01631         }
01632         return 0;
01633       err:
01634         qpol_iterator_destroy(&iter);
01635         return -1;
01636 }