type_map.c

00001 /**
00002  *  @file
00003  *  Implementation of type equivalence mapping for semantic
00004  *  difference calculations.
00005  *  The mapping of types is handled by creating a list of pseudo type
00006  *  values to represent the set of all semantically unique types in
00007  *  both the original and modified policies.  This mapping takes into
00008  *  account both inferred and user specified mappings of types and may
00009  *  contain holes where a type does not exist in one of the policies.
00010  *
00011  *  @author Jeremy A. Mowery jmowery@tresys.com
00012  *  @author Jason Tang jtang@tresys.com
00013  *
00014  *  Copyright (C) 2006-2007 Tresys Technology, LLC
00015  *
00016  *  This library is free software; you can redistribute it and/or
00017  *  modify it under the terms of the GNU Lesser General Public
00018  *  License as published by the Free Software Foundation; either
00019  *  version 2.1 of the License, or (at your option) any later version.
00020  *
00021  *  This library is distributed in the hope that it will be useful,
00022  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00023  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00024  *  Lesser General Public License for more details.
00025  *
00026  *  You should have received a copy of the GNU Lesser General Public
00027  *  License along with this library; if not, write to the Free Software
00028  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00029  */
00030 
00031 #include "poldiff_internal.h"
00032 
00033 #include <apol/policy-query.h>
00034 #include <apol/util.h>
00035 #include <assert.h>
00036 #include <errno.h>
00037 #include <stdio.h>
00038 #include <string.h>
00039 
00040 /**
00041  * A poldiff's type map consists of maps between policies' types to a
00042  * unified pseudo-type value.
00043  */
00044 struct type_map
00045 {
00046         /** array of size num_orig_types mapping types by (value - 1)
00047             to pseudo value */
00048         uint32_t *orig_to_pseudo;
00049         /** array of size num_mod_types mapping types by (value - 1)
00050             to pseudo value */
00051         uint32_t *mod_to_pseudo;
00052         /** vector of vector of qpol_type_t that reverse map pseudo
00053             value to orig_pol value(s) */
00054         apol_vector_t *pseudo_to_orig;
00055         /** vector of vector of qpol_type_t that reverse map pseudo
00056             value to mod_pol value(s) */
00057         apol_vector_t *pseudo_to_mod;
00058         size_t num_orig_types;
00059         size_t num_mod_types;
00060         /** vector of poldiff_type_remap_entry_t */
00061         apol_vector_t *remap;
00062 };
00063 
00064 /**
00065  * Each map entry consists of 2 vectors, each vector being a list of
00066  * qpol_type_t.
00067  */
00068 struct poldiff_type_remap_entry
00069 {
00070         /** vector of names of qpol_type_t in original qpolicy */
00071         apol_vector_t *orig_types;
00072         /** vector of names of qpol_type_t in the modified qpolicy */
00073         apol_vector_t *mod_types;
00074         int inferred;
00075         int enabled;
00076 };
00077 
00078 /**
00079  * Free the space associated with a singly type remap entry.
00080  *
00081  * @param elem Pointer to a type remap entry to free.  If NULL then do
00082  * nothing.
00083  */
00084 static void type_remap_entry_free(void *elem)
00085 {
00086         poldiff_type_remap_entry_t *entry = (poldiff_type_remap_entry_t *) elem;
00087         if (entry != NULL) {
00088                 apol_vector_destroy(&entry->orig_types);
00089                 apol_vector_destroy(&entry->mod_types);
00090                 free(entry);
00091         }
00092 }
00093 
00094 /**
00095  * Allocate a new poldiff type remap entry, append it to the current
00096  * type remap vector, enable it, and return the entry.
00097  *
00098  * @param diff Policy diff structure containing remap vector.
00099  *
00100  * @return a new entry, or NULL on error.
00101  */
00102 static poldiff_type_remap_entry_t *poldiff_type_remap_entry_create(poldiff_t * diff)
00103 {
00104         poldiff_type_remap_entry_t *e = NULL;
00105         if ((e = calloc(1, sizeof(*e))) == NULL ||
00106             (e->orig_types = apol_vector_create_with_capacity(1, free)) == NULL ||
00107             (e->mod_types = apol_vector_create_with_capacity(1, free)) == NULL || apol_vector_append(diff->type_map->remap, e) < 0)
00108         {
00109                 type_remap_entry_free(e);
00110                 return NULL;
00111         }
00112         diff->remapped = 1;
00113         e->enabled = 1;
00114         return e;
00115 }
00116 
00117 int poldiff_type_remap_create(poldiff_t * diff, const apol_vector_t * orig_names, const apol_vector_t * mod_names)
00118 {
00119         poldiff_type_remap_entry_t *entry = NULL;
00120         size_t i;
00121         char *name;
00122         const qpol_type_t *type;
00123         unsigned char isalias, isattr;
00124         int retval = -1, error = 0;
00125         if (diff == NULL || orig_names == NULL || mod_names == NULL) {
00126                 error = EINVAL;
00127                 ERR(diff, "%s", strerror(error));
00128                 goto cleanup;
00129         }
00130         if (apol_vector_get_size(orig_names) == 0 ||
00131             apol_vector_get_size(mod_names) == 0 || (apol_vector_get_size(orig_names) > 1 && apol_vector_get_size(mod_names) > 1)) {
00132                 error = EINVAL;
00133                 ERR(diff, "%s", strerror(error));
00134                 goto cleanup;
00135         }
00136         if ((entry = calloc(1, sizeof(*entry))) == NULL ||
00137             (entry->orig_types = apol_vector_create_with_capacity(1, free)) == NULL ||
00138             (entry->mod_types = apol_vector_create_with_capacity(1, free)) == NULL) {
00139                 error = ENOMEM;
00140                 ERR(diff, "%s", strerror(error));
00141                 goto cleanup;
00142         }
00143         for (i = 0; i < apol_vector_get_size(orig_names); i++) {
00144                 name = (char *)apol_vector_get_element(orig_names, i);
00145                 if (qpol_policy_get_type_by_name(diff->orig_qpol, name, &type) < 0 ||
00146                     qpol_type_get_isalias(diff->orig_qpol, type, &isalias) < 0 ||
00147                     qpol_type_get_isattr(diff->orig_qpol, type, &isattr) < 0) {
00148                         error = errno;
00149                         goto cleanup;
00150                 }
00151                 if (isalias || isattr) {
00152                         error = EINVAL;
00153                         ERR(diff, "%s is not a primary type.", name);
00154                         goto cleanup;
00155                 }
00156                 if ((name = strdup(name)) == NULL || apol_vector_append(entry->orig_types, (void *)name) < 0) {
00157                         error = ENOMEM;
00158                         free(name);
00159                         ERR(diff, "%s", strerror(error));
00160                         goto cleanup;
00161                 }
00162         }
00163         apol_vector_sort_uniquify(entry->orig_types, apol_str_strcmp, NULL);
00164         for (i = 0; i < apol_vector_get_size(mod_names); i++) {
00165                 name = (char *)apol_vector_get_element(mod_names, i);
00166                 if (qpol_policy_get_type_by_name(diff->mod_qpol, name, &type) < 0 ||
00167                     qpol_type_get_isalias(diff->mod_qpol, type, &isalias) < 0 ||
00168                     qpol_type_get_isattr(diff->mod_qpol, type, &isattr) < 0) {
00169                         error = errno;
00170                         goto cleanup;
00171                 }
00172                 if (isalias || isattr) {
00173                         error = EINVAL;
00174                         ERR(diff, "%s is not a primary type.", name);
00175                         goto cleanup;
00176                 }
00177                 if ((name = strdup(name)) == NULL || apol_vector_append(entry->mod_types, (void *)name) < 0) {
00178                         error = ENOMEM;
00179                         free(name);
00180                         ERR(diff, "%s", strerror(error));
00181                         goto cleanup;
00182                 }
00183         }
00184         apol_vector_sort_uniquify(entry->mod_types, apol_str_strcmp, NULL);
00185         entry->enabled = 1;
00186         if (apol_vector_append(diff->type_map->remap, entry) < 0) {
00187                 error = ENOMEM;
00188                 ERR(diff, "%s", strerror(error));
00189                 goto cleanup;
00190         }
00191         retval = 0;
00192         diff->remapped = 1;
00193       cleanup:
00194         if (retval < 0) {
00195                 type_remap_entry_free(entry);
00196         }
00197         errno = error;
00198         return retval;
00199 }
00200 
00201 apol_vector_t *poldiff_type_remap_get_entries(const poldiff_t * diff)
00202 {
00203         if (diff == NULL || diff->type_map == NULL) {
00204                 ERR(diff, "%s", strerror(EINVAL));
00205                 errno = EINVAL;
00206                 return NULL;
00207         }
00208         return diff->type_map->remap;
00209 }
00210 
00211 void poldiff_type_remap_entry_remove(poldiff_t * diff, poldiff_type_remap_entry_t * entry)
00212 {
00213         size_t idx;
00214         if (diff == NULL || entry == NULL) {
00215                 ERR(diff, "%s", strerror(EINVAL));
00216                 errno = EINVAL;
00217                 return;
00218         }
00219         if (apol_vector_get_index(diff->type_map->remap, entry, NULL, NULL, &idx) < 0) {
00220                 ERR(diff, "%s", strerror(EINVAL));
00221                 errno = EINVAL;
00222                 return;
00223         }
00224         apol_vector_remove(diff->type_map->remap, idx);
00225         diff->remapped = 1;
00226 }
00227 
00228 apol_vector_t *poldiff_type_remap_entry_get_original_types(const poldiff_t * diff, const poldiff_type_remap_entry_t * entry)
00229 {
00230         if (diff == NULL || entry == NULL) {
00231                 ERR(diff, "%s", strerror(EINVAL));
00232                 errno = EINVAL;
00233                 return NULL;
00234         }
00235         return apol_vector_create_from_vector(entry->orig_types, NULL, NULL, NULL);
00236 }
00237 
00238 apol_vector_t *poldiff_type_remap_entry_get_modified_types(const poldiff_t * diff, const poldiff_type_remap_entry_t * entry)
00239 {
00240         if (diff == NULL || entry == NULL) {
00241                 ERR(diff, "%s", strerror(EINVAL));
00242                 errno = EINVAL;
00243                 return NULL;
00244         }
00245         return apol_vector_create_from_vector(entry->mod_types, NULL, NULL, NULL);
00246 }
00247 
00248 int poldiff_type_remap_entry_get_is_inferred(const poldiff_type_remap_entry_t * entry)
00249 {
00250         if (entry == NULL) {
00251                 errno = EINVAL;
00252                 return -1;
00253         }
00254         return entry->inferred;
00255 }
00256 
00257 int poldiff_type_remap_entry_get_is_enabled(const poldiff_type_remap_entry_t * entry)
00258 {
00259         if (entry == NULL) {
00260                 errno = EINVAL;
00261                 return -1;
00262         }
00263         return entry->enabled;
00264 }
00265 
00266 void poldiff_type_remap_entry_set_enabled(poldiff_type_remap_entry_t * entry, int enabled)
00267 {
00268         if (entry == NULL) {
00269                 errno = EINVAL;
00270                 return;
00271         }
00272         if (enabled) {
00273                 entry->enabled = 1;
00274         } else {
00275                 entry->enabled = 0;
00276         }
00277 }
00278 
00279 type_map_t *type_map_create(void)
00280 {
00281         type_map_t *map = calloc(1, sizeof(*map));
00282         if (map == NULL) {
00283                 return NULL;
00284         }
00285         if ((map->remap = apol_vector_create(type_remap_entry_free)) == NULL) {
00286                 type_map_destroy(&map);
00287                 return NULL;
00288         }
00289         return map;
00290 }
00291 
00292 void type_map_destroy(type_map_t ** map)
00293 {
00294         if (map != NULL && *map != NULL) {
00295                 free((*map)->orig_to_pseudo);
00296                 free((*map)->mod_to_pseudo);
00297                 apol_vector_destroy(&(*map)->pseudo_to_orig);
00298                 apol_vector_destroy(&(*map)->pseudo_to_mod);
00299                 apol_vector_destroy(&(*map)->remap);
00300                 free(*map);
00301                 *map = NULL;
00302         }
00303 }
00304 
00305 /**
00306  * If --enable-debug is given, then dump to stdout the type map from
00307  * policy's types -> pseudo-types.
00308  */
00309 static void type_map_dump(poldiff_t * diff)
00310 {
00311 #ifdef SETOOLS_DEBUG
00312         size_t i, j;
00313         apol_vector_t *v;
00314         const qpol_type_t *t;
00315         const char *name;
00316         printf("# type map debug dump (qpol_type_t -> pseudo-type):\norig:\n");
00317         for (i = 0; i < diff->type_map->num_orig_types; i++) {
00318                 printf("%3zd:%5d", i, diff->type_map->orig_to_pseudo[i]);
00319                 if ((i + 1) % 5 == 0) {
00320                         printf("\n");
00321                 } else {
00322                         printf("\t");
00323                 }
00324         }
00325         for (i = 0; i < apol_vector_get_size(diff->type_map->pseudo_to_orig); i++) {
00326                 v = apol_vector_get_element(diff->type_map->pseudo_to_orig, i);
00327                 printf("\n%3zd->", i);
00328                 for (j = 0; j < apol_vector_get_size(v); j++) {
00329                         t = apol_vector_get_element(v, j);
00330                         qpol_type_get_name(diff->orig_qpol, t, &name);
00331                         printf(" %s", name);
00332                 }
00333         }
00334         printf("\nmod:\n");
00335         for (i = 0; i < diff->type_map->num_mod_types; i++) {
00336                 printf("%3zd:%5d", i, diff->type_map->mod_to_pseudo[i]);
00337                 if ((i + 1) % 5 == 0) {
00338                         printf("\n");
00339                 } else {
00340                         printf("\t");
00341                 }
00342         }
00343         for (i = 0; i < apol_vector_get_size(diff->type_map->pseudo_to_mod); i++) {
00344                 v = apol_vector_get_element(diff->type_map->pseudo_to_mod, i);
00345                 printf("\n%3zd->", i);
00346                 for (j = 0; j < apol_vector_get_size(v); j++) {
00347                         t = apol_vector_get_element(v, j);
00348                         qpol_type_get_name(diff->mod_qpol, t, &name);
00349                         printf(" %s", name);
00350                 }
00351         }
00352         printf("\n");
00353 #endif
00354 }
00355 
00356 /**
00357  * Free a vector of qpol_type_t pointers.
00358  */
00359 static void type_map_vector_free(void *elem)
00360 {
00361         apol_vector_t *v = (apol_vector_t *) elem;
00362         if (v != NULL) {
00363                 apol_vector_destroy(&v);
00364         }
00365 }
00366 
00367 int type_map_build(poldiff_t * diff)
00368 {
00369         type_map_t *map;
00370         apol_vector_t *ov = NULL, *mv = NULL;
00371         int retval = -1, error = 0;
00372         size_t i, j;
00373         const qpol_type_t *t;
00374         uint32_t val, max_val, next_val;
00375         apol_vector_t *reverse_v = NULL;
00376 
00377         map = diff->type_map;
00378         free(map->orig_to_pseudo);
00379         map->orig_to_pseudo = NULL;
00380         map->num_orig_types = 0;
00381         free(map->mod_to_pseudo);
00382         map->mod_to_pseudo = NULL;
00383         map->num_mod_types = 0;
00384         apol_vector_destroy(&map->pseudo_to_orig);
00385         apol_vector_destroy(&map->pseudo_to_mod);
00386 
00387         if (apol_type_get_by_query(diff->orig_pol, NULL, &ov) < 0 || apol_type_get_by_query(diff->mod_pol, NULL, &mv) < 0) {
00388                 error = errno;
00389                 goto cleanup;
00390         }
00391 
00392         /* there is no guarantee that the number of types is equal to
00393          * the highest type value (because a policy could have
00394          * attributes), so calculate them here */
00395         max_val = 0;
00396         for (i = 0; i < apol_vector_get_size(ov); i++) {
00397                 t = (qpol_type_t *) apol_vector_get_element(ov, i);
00398                 if (qpol_type_get_value(diff->orig_qpol, t, &val) < 0) {
00399                         error = errno;
00400                         goto cleanup;
00401                 }
00402                 if (val > max_val) {
00403                         max_val = val;
00404                 }
00405         }
00406         if ((map->orig_to_pseudo = calloc(max_val, sizeof(*(map->orig_to_pseudo)))) == NULL) {
00407                 error = errno;
00408                 ERR(diff, "%s", strerror(error));
00409                 goto cleanup;
00410         }
00411         map->num_orig_types = max_val;
00412         max_val = 0;
00413         for (i = 0; i < apol_vector_get_size(mv); i++) {
00414                 t = (qpol_type_t *) apol_vector_get_element(mv, i);
00415                 if (qpol_type_get_value(diff->mod_qpol, t, &val) < 0) {
00416                         error = errno;
00417                         goto cleanup;
00418                 }
00419                 if (val > max_val) {
00420                         max_val = val;
00421                 }
00422         }
00423         if ((map->mod_to_pseudo = calloc(max_val, sizeof(*(map->mod_to_pseudo)))) == NULL) {
00424                 error = errno;
00425                 ERR(diff, "%s", strerror(error));
00426                 goto cleanup;
00427         }
00428         map->num_mod_types = max_val;
00429 
00430         if ((map->pseudo_to_orig = apol_vector_create(type_map_vector_free)) == NULL
00431             || (map->pseudo_to_mod = apol_vector_create(type_map_vector_free)) == NULL) {
00432                 error = errno;
00433                 ERR(diff, "%s", strerror(error));
00434                 goto cleanup;
00435         }
00436 
00437         next_val = 1;
00438         for (i = 0; i < apol_vector_get_size(map->remap); i++) {
00439                 poldiff_type_remap_entry_t *e;
00440                 const char *name;
00441                 e = (poldiff_type_remap_entry_t *) apol_vector_get_element(map->remap, i);
00442                 if (!e->enabled) {
00443                         continue;
00444                 }
00445 
00446                 if ((reverse_v = apol_vector_create_with_capacity(1, NULL)) == NULL) {
00447                         error = errno;
00448                         ERR(diff, "%s", strerror(error));
00449                         goto cleanup;
00450                 }
00451                 for (j = 0; j < apol_vector_get_size(e->orig_types); j++) {
00452                         name = (const char *)apol_vector_get_element(e->orig_types, j);
00453                         if (qpol_policy_get_type_by_name(diff->orig_qpol, name, &t) < 0 ||
00454                             qpol_type_get_value(diff->orig_qpol, t, &val) < 0) {
00455                                 error = errno;
00456                                 goto cleanup;
00457                         }
00458                         if (map->orig_to_pseudo[val - 1] != 0) {
00459                                 error = EINVAL;
00460                                 ERR(diff, "Type %s is already remapped.", name);
00461                                 goto cleanup;
00462                         }
00463                         map->orig_to_pseudo[val - 1] = next_val;
00464                         if (apol_vector_append(reverse_v, (void *)t) < 0) {
00465                                 error = errno;
00466                                 ERR(diff, "%s", strerror(error));
00467                                 goto cleanup;
00468                         }
00469                 }
00470                 if (apol_vector_append(map->pseudo_to_orig, reverse_v) < 0) {
00471                         error = errno;
00472                         ERR(diff, "%s", strerror(error));
00473                         goto cleanup;
00474                 }
00475                 reverse_v = NULL;
00476 
00477                 if ((reverse_v = apol_vector_create_with_capacity(1, NULL)) == NULL) {
00478                         error = errno;
00479                         ERR(diff, "%s", strerror(error));
00480                         goto cleanup;
00481                 }
00482                 for (j = 0; j < apol_vector_get_size(e->mod_types); j++) {
00483                         name = (const char *)apol_vector_get_element(e->mod_types, j);
00484                         if (qpol_policy_get_type_by_name(diff->mod_qpol, name, &t) < 0 ||
00485                             qpol_type_get_value(diff->mod_qpol, t, &val) < 0) {
00486                                 error = errno;
00487                                 goto cleanup;
00488                         }
00489                         if (map->mod_to_pseudo[val - 1] != 0) {
00490                                 error = EINVAL;
00491                                 ERR(diff, "Type %s is already remapped.", name);
00492                                 goto cleanup;
00493                         }
00494                         map->mod_to_pseudo[val - 1] = next_val;
00495                         if (apol_vector_append(reverse_v, (void *)t) < 0) {
00496                                 error = errno;
00497                                 ERR(diff, "%s", strerror(error));
00498                                 goto cleanup;
00499                         }
00500                 }
00501                 if (apol_vector_append(map->pseudo_to_mod, reverse_v) < 0) {
00502                         error = errno;
00503                         ERR(diff, "%s", strerror(error));
00504                         goto cleanup;
00505                 }
00506                 reverse_v = NULL;
00507 
00508                 next_val++;
00509         }
00510 
00511         /* all remaining types (both from orig and mod) get their own
00512          * values */
00513         for (i = 0; i < apol_vector_get_size(ov); i++) {
00514                 t = apol_vector_get_element(ov, i);
00515                 if (qpol_type_get_value(diff->orig_qpol, t, &val) < 0) {
00516                         error = errno;
00517                         goto cleanup;
00518                 }
00519                 if (map->orig_to_pseudo[val - 1] == 0) {
00520                         map->orig_to_pseudo[val - 1] = next_val;
00521                         if ((reverse_v = apol_vector_create_with_capacity(1, NULL)) == NULL ||
00522                             apol_vector_append(reverse_v, (void *)t) < 0 ||
00523                             apol_vector_append(map->pseudo_to_orig, reverse_v) < 0) {
00524                                 error = errno;
00525                                 ERR(diff, "%s", strerror(error));
00526                                 goto cleanup;
00527                         }
00528                         reverse_v = NULL;
00529                         if ((reverse_v = apol_vector_create_with_capacity(1, NULL)) == NULL ||
00530                             apol_vector_append(map->pseudo_to_mod, reverse_v) < 0) {
00531                                 error = errno;
00532                                 ERR(diff, "%s", strerror(error));
00533                                 goto cleanup;
00534                         }
00535                         reverse_v = NULL;
00536                         next_val++;
00537                 }
00538         }
00539         for (i = 0; i < apol_vector_get_size(mv); i++) {
00540                 t = apol_vector_get_element(mv, i);
00541                 if (qpol_type_get_value(diff->mod_qpol, t, &val) < 0) {
00542                         error = errno;
00543                         goto cleanup;
00544                 }
00545                 if (map->mod_to_pseudo[val - 1] == 0) {
00546                         map->mod_to_pseudo[val - 1] = next_val;
00547                         if ((reverse_v = apol_vector_create_with_capacity(1, NULL)) == NULL ||
00548                             apol_vector_append(reverse_v, (void *)t) < 0 || apol_vector_append(map->pseudo_to_mod, reverse_v) < 0) {
00549                                 error = errno;
00550                                 ERR(diff, "%s", strerror(error));
00551                                 goto cleanup;
00552                         }
00553                         reverse_v = NULL;
00554                         if ((reverse_v = apol_vector_create_with_capacity(1, NULL)) == NULL ||
00555                             apol_vector_append(map->pseudo_to_orig, reverse_v) < 0) {
00556                                 error = errno;
00557                                 ERR(diff, "%s", strerror(error));
00558                                 goto cleanup;
00559                         }
00560                         reverse_v = NULL;
00561                         next_val++;
00562                 }
00563         }
00564 
00565         type_map_dump(diff);
00566 
00567         retval = 0;
00568       cleanup:
00569         apol_vector_destroy(&ov);
00570         apol_vector_destroy(&mv);
00571         apol_vector_destroy(&reverse_v);
00572         error = errno;
00573         return retval;
00574 }
00575 
00576 void poldiff_type_remap_flush(poldiff_t * diff)
00577 {
00578         if (diff == NULL || diff->type_map == NULL) {
00579                 ERR(diff, "%s", strerror(EINVAL));
00580                 errno = EINVAL;
00581                 return;
00582         }
00583         apol_vector_destroy(&(diff->type_map->remap));
00584         /* no error checking below */
00585         diff->type_map->remap = apol_vector_create(type_remap_entry_free);
00586         diff->remapped = 1;
00587 }
00588 
00589 /**
00590  * Convenience struct for comparing elements within arrays of primary types.
00591  */
00592 struct type_map_comp
00593 {
00594         poldiff_t *diff;
00595         /** from which policy the first element came, either
00596          * POLDIFF_POLICY_ORIG or POLDIFF_POLICY_MOD */
00597         int dir;
00598 };
00599 
00600 /**
00601  * Given two qpol_type_t pointers, both of which are primary types,
00602  * compare their names for equivalence.
00603  *
00604  * @param a Pointer to a qpol_type_t from a policy.
00605  * @param b Pointer to a qpol_type_t from a policy.
00606  * @param data Pointer to a type_map_comp struct.
00607  *
00608  * @return 0 if the names match, non-zero if not.
00609  */
00610 static int type_map_primary_comp(const void *a, const void *b, void *data)
00611 {
00612         const qpol_type_t *ta = a;
00613         const qpol_type_t *tb = b;
00614         struct type_map_comp *c = (struct type_map_comp *)data;
00615         poldiff_t *diff = c->diff;
00616         int dir = c->dir;
00617         const char *na, *nb;
00618         if (dir == POLDIFF_POLICY_ORIG) {
00619                 if (qpol_type_get_name(diff->orig_qpol, ta, &na) < 0 || qpol_type_get_name(diff->mod_qpol, tb, &nb) < 0) {
00620                         return -1;
00621                 }
00622         } else {
00623                 if (qpol_type_get_name(diff->mod_qpol, ta, &na) < 0 || qpol_type_get_name(diff->orig_qpol, tb, &nb) < 0) {
00624                         return -1;
00625                 }
00626         }
00627         return strcmp(na, nb);
00628 }
00629 
00630 /**
00631  * Given two qpol_type_t pointers, both of which are primary types,
00632  * see if the first type matches any of the other type's aliases.
00633  *
00634  * @param a Pointer to a qpol_type_t from a policy.
00635  * @param b Pointer to a qpol_type_t from a policy.
00636  * @param data Pointer to a type_map_comp struct.
00637  *
00638  * @return 0 if b is a member of a's aliases, non-zero if not.
00639  */
00640 static int type_map_prim_alias_comp(const void *a, const void *b, void *data)
00641 {
00642         const qpol_type_t *ta = a;
00643         const qpol_type_t *tb = b;
00644         struct type_map_comp *c = (struct type_map_comp *)data;
00645         poldiff_t *diff = c->diff;
00646         int dir = c->dir;
00647         const char *prim, *alias;
00648         qpol_iterator_t *iter = NULL;
00649         if (dir == POLDIFF_POLICY_ORIG) {
00650                 if (qpol_type_get_alias_iter(diff->orig_qpol, ta, &iter) < 0 || qpol_type_get_name(diff->mod_qpol, tb, &prim) < 0) {
00651                         qpol_iterator_destroy(&iter);
00652                         return -1;
00653                 }
00654         } else {
00655                 if (qpol_type_get_alias_iter(diff->mod_qpol, ta, &iter) < 0 || qpol_type_get_name(diff->orig_qpol, tb, &prim) < 0) {
00656                         qpol_iterator_destroy(&iter);
00657                         return -1;
00658                 }
00659         }
00660         for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
00661                 if (qpol_iterator_get_item(iter, (void **)&alias) < 0) {
00662                         qpol_iterator_destroy(&iter);
00663                         return -1;
00664                 }
00665                 if (strcmp(prim, alias) == 0) {
00666                         qpol_iterator_destroy(&iter);
00667                         return 0;
00668                 }
00669         }
00670         qpol_iterator_destroy(&iter);
00671         return -1;
00672 }
00673 
00674 /**
00675  * Given two qpol_type_t pointers, both of which are primary types,
00676  * see if the first type's aliases matches the second type's aliases.
00677  *
00678  * @param a Pointer to a qpol_type_t from a policy.
00679  * @param b Pointer to a qpol_type_t from a policy.
00680  * @param data Pointer to a type_map_comp struct.
00681  *
00682  * @return 0 if b is a member of a's aliases, non-zero if not.
00683  */
00684 static int type_map_prim_aliases_comp(const void *a, const void *b, void *data)
00685 {
00686         qpol_type_t *ta = (qpol_type_t *) a;
00687         qpol_type_t *tb = (qpol_type_t *) b;
00688         struct type_map_comp *c = (struct type_map_comp *)data;
00689         poldiff_t *diff = c->diff;
00690         int dir = c->dir;
00691         qpol_policy_t *p1, *p2;
00692         qpol_iterator_t *iter1 = NULL, *iter2 = NULL;
00693         apol_vector_t *v1 = NULL, *v2 = NULL;
00694         size_t i;
00695         int retval = -1, error = 0;
00696         if (dir == POLDIFF_POLICY_ORIG) {
00697                 p1 = diff->orig_qpol;
00698                 p2 = diff->mod_qpol;
00699         } else {
00700                 p1 = diff->mod_qpol;
00701                 p2 = diff->orig_qpol;
00702         }
00703         if (qpol_type_get_alias_iter(p1, ta, &iter1) < 0) {
00704                 error = errno;
00705                 goto cleanup;
00706         }
00707         if ((v1 = apol_vector_create_from_iter(iter1, NULL)) == NULL) {
00708                 error = errno;
00709                 ERR(diff, "%s", strerror(error));
00710                 goto cleanup;
00711         }
00712         if (qpol_type_get_alias_iter(p2, tb, &iter2) < 0) {
00713                 error = errno;
00714                 goto cleanup;
00715         }
00716         if ((v2 = apol_vector_create_from_iter(iter2, NULL)) == NULL) {
00717                 error = errno;
00718                 ERR(diff, "%s", strerror(error));
00719                 goto cleanup;
00720         }
00721         if (apol_vector_get_size(v1) == 0 || apol_vector_get_size(v2) == 0) {
00722                 retval = 1;
00723                 goto cleanup;
00724         } else {
00725                 apol_vector_sort_uniquify(v1, apol_str_strcmp, NULL);
00726                 apol_vector_sort_uniquify(v2, apol_str_strcmp, NULL);
00727                 retval = apol_vector_compare(v1, v2, apol_str_strcmp, NULL, &i);
00728         }
00729       cleanup:
00730         qpol_iterator_destroy(&iter1);
00731         qpol_iterator_destroy(&iter2);
00732         apol_vector_destroy(&v1);
00733         apol_vector_destroy(&v2);
00734         errno = error;
00735         return retval;
00736 }
00737 
00738 /**
00739  * If --enable-debug is given, then dump to stdout the type-map from
00740  * pseudo-types to the policy's type(s).
00741  */
00742 static void type_remap_vector_dump(poldiff_t * diff)
00743 {
00744 #ifdef SETOOLS_DEBUG
00745         apol_vector_t *v, *w;
00746         size_t i, j;
00747         poldiff_type_remap_entry_t *e;
00748         char *name;
00749         printf("# type remap vector debug dump (pseudo-type -> qpol_type_t(s):\n");
00750         v = poldiff_type_remap_get_entries(diff);
00751         for (i = 0; i < apol_vector_get_size(v); i++) {
00752                 e = apol_vector_get_element(v, i);
00753                 printf("%zd\t%s\t", i, poldiff_type_remap_entry_get_is_enabled(e) ? "en" : "dis");
00754                 w = poldiff_type_remap_entry_get_original_types(diff, e);
00755                 for (j = 0; j < apol_vector_get_size(w); j++) {
00756                         name = apol_vector_get_element(w, j);
00757                         printf("%s ", name);
00758                 }
00759                 apol_vector_destroy(&w);
00760                 printf("-> ");
00761                 w = poldiff_type_remap_entry_get_modified_types(diff, e);
00762                 for (j = 0; j < apol_vector_get_size(w); j++) {
00763                         name = apol_vector_get_element(w, j);
00764                         printf("%s ", name);
00765                 }
00766                 apol_vector_destroy(&w);
00767                 printf("\n");
00768         }
00769 #endif
00770 }
00771 
00772 static int type_map_entry_append_qtypes(poldiff_t * diff, poldiff_type_remap_entry_t * entry, const qpol_type_t * t,
00773                                         const qpol_type_t * u)
00774 {
00775         const char *name;
00776         char *dup_name;
00777         if (qpol_type_get_name(diff->orig_qpol, t, &name) < 0) {
00778                 return -1;
00779         }
00780         if ((dup_name = strdup(name)) == NULL || apol_vector_append(entry->orig_types, (void *)dup_name) < 0) {
00781                 free(dup_name);
00782                 return -1;
00783         }
00784 
00785         if (qpol_type_get_name(diff->mod_qpol, u, &name) < 0) {
00786                 return -1;
00787         }
00788         if ((dup_name = strdup(name)) == NULL || apol_vector_append(entry->mod_types, (void *)dup_name) < 0) {
00789                 free(dup_name);
00790                 return -1;
00791         }
00792         return 0;
00793 }
00794 
00795 int type_map_infer(poldiff_t * diff)
00796 {
00797         apol_vector_t *ov = NULL, *mv = NULL;
00798         char *orig_done = NULL, *mod_done = NULL;
00799         size_t num_orig, num_mod, i, j;
00800         qpol_type_t *t, *u;
00801         struct type_map_comp c = { diff, 0 };
00802         poldiff_type_remap_entry_t *entry = NULL;
00803         int retval = -1, error = 0;
00804 
00805         INFO(diff, "%s", "Inferring type remap.");
00806         if (apol_type_get_by_query(diff->orig_pol, NULL, &ov) < 0 || apol_type_get_by_query(diff->mod_pol, NULL, &mv) < 0) {
00807                 error = errno;
00808                 goto cleanup;
00809         }
00810         num_orig = apol_vector_get_size(ov);
00811         num_mod = apol_vector_get_size(mv);
00812         if ((orig_done = calloc(1, num_orig)) == NULL || (mod_done = calloc(1, num_mod)) == NULL) {
00813                 error = errno;
00814                 ERR(diff, "%s", strerror(error));
00815                 goto cleanup;
00816         }
00817 
00818         /* first map primary <--> primary */
00819         c.dir = POLDIFF_POLICY_MOD;
00820         for (i = 0; i < num_orig; i++) {
00821                 t = (qpol_type_t *) apol_vector_get_element(ov, i);
00822                 if (apol_vector_get_index(mv, t, type_map_primary_comp, &c, &j) < 0) {
00823                         continue;
00824                 }
00825                 assert(!mod_done[j]);
00826                 u = (qpol_type_t *) apol_vector_get_element(mv, j);
00827                 if ((entry = poldiff_type_remap_entry_create(diff)) == NULL || type_map_entry_append_qtypes(diff, entry, t, u) < 0) {
00828                         error = errno;
00829                         ERR(diff, "%s", strerror(error));
00830                         goto cleanup;
00831                 }
00832                 entry->inferred = 1;
00833                 orig_done[i] = 1;
00834                 mod_done[j] = 1;
00835         }
00836 
00837         /* now map primary -> primary's alias */
00838         c.dir = POLDIFF_POLICY_MOD;
00839         for (i = 0; i < num_orig; i++) {
00840                 if (orig_done[i]) {
00841                         continue;
00842                 }
00843                 t = (qpol_type_t *) apol_vector_get_element(ov, i);
00844                 u = NULL;
00845                 for (j = 0; j < num_mod; j++) {
00846                         if (mod_done[j]) {
00847                                 continue;
00848                         }
00849                         u = (qpol_type_t *) apol_vector_get_element(mv, j);
00850                         if (type_map_prim_alias_comp(u, t, &c) == 0) {
00851                                 break;
00852                         }
00853                 }
00854                 if (j >= num_mod) {
00855                         continue;
00856                 }
00857                 if ((entry = poldiff_type_remap_entry_create(diff)) == NULL || type_map_entry_append_qtypes(diff, entry, t, u) < 0) {
00858                         error = errno;
00859                         ERR(diff, "%s", strerror(error));
00860                         goto cleanup;
00861                 }
00862                 entry->inferred = 1;
00863                 orig_done[i] = 1;
00864                 mod_done[j] = 1;
00865         }
00866 
00867         /* then map primary's alias <- primary */
00868         c.dir = POLDIFF_POLICY_ORIG;
00869         for (j = 0; j < num_mod; j++) {
00870                 if (mod_done[j]) {
00871                         continue;
00872                 }
00873                 u = (qpol_type_t *) apol_vector_get_element(mv, j);
00874                 t = NULL;
00875                 for (i = 0; i < num_orig; i++) {
00876                         if (orig_done[i]) {
00877                                 continue;
00878                         }
00879                         t = (qpol_type_t *) apol_vector_get_element(ov, i);
00880                         if (type_map_prim_alias_comp(t, u, &c) == 0) {
00881                                 break;
00882                         }
00883                 }
00884                 if (i >= num_orig) {
00885                         continue;
00886                 }
00887                 if ((entry = poldiff_type_remap_entry_create(diff)) == NULL || type_map_entry_append_qtypes(diff, entry, t, u) < 0) {
00888                         error = errno;
00889                         ERR(diff, "%s", strerror(error));
00890                         goto cleanup;
00891                 }
00892                 entry->inferred = 1;
00893                 orig_done[i] = 1;
00894                 mod_done[j] = 1;
00895         }
00896 
00897         /* map alias <-> alias */
00898         c.dir = POLDIFF_POLICY_MOD;
00899         for (i = 0; i < num_orig; i++) {
00900                 if (orig_done[i]) {
00901                         continue;
00902                 }
00903                 t = (qpol_type_t *) apol_vector_get_element(ov, i);
00904                 u = NULL;
00905                 for (j = 0; j < num_mod; j++) {
00906                         if (mod_done[j]) {
00907                                 continue;
00908                         }
00909                         u = (qpol_type_t *) apol_vector_get_element(mv, j);
00910                         if (type_map_prim_aliases_comp(u, t, &c) == 0) {
00911                                 break;
00912                         }
00913                 }
00914                 if (j >= num_mod) {
00915                         continue;
00916                 }
00917                 if ((entry = poldiff_type_remap_entry_create(diff)) == NULL || type_map_entry_append_qtypes(diff, entry, t, u) < 0) {
00918                         error = errno;
00919                         ERR(diff, "%s", strerror(error));
00920                         goto cleanup;
00921                 }
00922                 entry->inferred = 1;
00923                 orig_done[i] = 1;
00924                 mod_done[j] = 1;
00925         }
00926 
00927         type_remap_vector_dump(diff);
00928 
00929         retval = 0;
00930         diff->remapped = 1;
00931       cleanup:
00932         apol_vector_destroy(&ov);
00933         apol_vector_destroy(&mv);
00934         free(orig_done);
00935         free(mod_done);
00936         errno = error;
00937         return retval;
00938 }
00939 
00940 uint32_t type_map_lookup(const poldiff_t * diff, const qpol_type_t * type, int which_pol)
00941 {
00942         uint32_t val;
00943         if (which_pol == POLDIFF_POLICY_ORIG) {
00944                 if (qpol_type_get_value(diff->orig_qpol, type, &val) < 0) {
00945                         return 0;
00946                 }
00947                 assert(val <= diff->type_map->num_orig_types);
00948                 assert(diff->type_map->orig_to_pseudo[val - 1] != 0);
00949                 return diff->type_map->orig_to_pseudo[val - 1];
00950         } else {
00951                 if (qpol_type_get_value(diff->mod_qpol, type, &val) < 0) {
00952                         return 0;
00953                 }
00954                 assert(val <= diff->type_map->num_mod_types);
00955                 assert(diff->type_map->mod_to_pseudo[val - 1] != 0);
00956                 return diff->type_map->mod_to_pseudo[val - 1];
00957         }
00958 }
00959 
00960 const apol_vector_t *type_map_lookup_reverse(const poldiff_t * diff, uint32_t val, int which_pol)
00961 {
00962         if (which_pol == POLDIFF_POLICY_ORIG) {
00963                 return apol_vector_get_element(diff->type_map->pseudo_to_orig, val - 1);
00964         } else {
00965                 return apol_vector_get_element(diff->type_map->pseudo_to_mod, val - 1);
00966         }
00967 }
00968 
00969 const char *type_map_get_name(const poldiff_t * diff, const uint32_t pseudo_val, int pol)
00970 {
00971         const apol_vector_t *v = NULL;
00972         const char *name = NULL;
00973         const qpol_type_t *t;
00974 
00975         v = type_map_lookup_reverse(diff, pseudo_val, pol);
00976         if (apol_vector_get_size(v) == 0) {
00977                 return NULL;
00978         }
00979         t = apol_vector_get_element(v, 0);
00980         if (pol == POLDIFF_POLICY_ORIG)
00981                 qpol_type_get_name(diff->orig_qpol, t, &name);
00982         else
00983                 qpol_type_get_name(diff->mod_qpol, t, &name);
00984         return name;
00985 }