/src/selinux/libsepol/cil/src/cil_find.c

Source
/*
 * Copyright 2011 Tresys Technology, LLC. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *    1. Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *
 *    2. Redistributions in binary form must reproduce the above copyright notice,
 *       this list of conditions and the following disclaimer in the documentation
 *       and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY TRESYS TECHNOLOGY, LLC ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
 * EVENT SHALL TRESYS TECHNOLOGY, LLC OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * The views and conclusions contained in the software and documentation are those
 * of the authors and should not be interpreted as representing official policies,
 * either expressed or implied, of Tresys Technology, LLC.
 */

#include <sepol/policydb/ebitmap.h>

#include "cil_internal.h"
#include "cil_find.h"
#include "cil_flavor.h"
#include "cil_list.h"
#include "cil_log.h"
#include "cil_symtab.h"

struct cil_args_find {
  enum cil_flavor flavor;
  void *target;
  struct cil_list *matching;
  int match_self;
};

static int cil_type_match_any(struct cil_symtab_datum *d1,
            struct cil_symtab_datum *d2)
{
  enum cil_flavor f1 = FLAVOR(d1);
  enum cil_flavor f2 = FLAVOR(d2);

  if (f1 != CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
    struct cil_type *t1 = (struct cil_type *)d1;
    struct cil_type *t2 = (struct cil_type *)d2;
    if (t1->value == t2->value) {
      return CIL_TRUE;
    }
  } else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
    struct cil_typeattribute *a = (struct cil_typeattribute *)d1;
    struct cil_type *t = (struct cil_type *)d2;
    if (ebitmap_get_bit(a->types, t->value)) {
      return CIL_TRUE;
    }
  } else if (f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
    struct cil_type *t = (struct cil_type *)d1;
    struct cil_typeattribute *a = (struct cil_typeattribute *)d2;
    if (ebitmap_get_bit(a->types, t->value)) {
      return CIL_TRUE;
    }
  } else {
    /* Both are attributes */
    struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
    struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
    if (d1 == d2) {
      return CIL_TRUE;
    } else if (ebitmap_match_any(a1->types, a2->types)) {
      return CIL_TRUE;
    }
  }
  return CIL_FALSE;
}

static int cil_type_matches(ebitmap_t *matches, struct cil_symtab_datum *d1,
          struct cil_symtab_datum *d2)
{
  int rc = SEPOL_OK;
  enum cil_flavor f1 = FLAVOR(d1);
  enum cil_flavor f2 = FLAVOR(d2);

  if (f1 == CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
    struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
    struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
    rc = ebitmap_and(matches, a1->types, a2->types);
  } else {
    ebitmap_init(matches);
    if (f1 != CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
      struct cil_type *t1 = (struct cil_type *)d1;
      struct cil_type *t2 = (struct cil_type *)d2;
      if (t1->value == t2->value) {
        rc = ebitmap_set_bit(matches, t1->value, 1);
      }
    } else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
      struct cil_typeattribute *a =
        (struct cil_typeattribute *)d1;
      struct cil_type *t = (struct cil_type *)d2;
      if (ebitmap_get_bit(a->types, t->value)) {
        rc = ebitmap_set_bit(matches, t->value, 1);
      }
    } else { // f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE
      struct cil_type *t = (struct cil_type *)d1;
      struct cil_typeattribute *a =
        (struct cil_typeattribute *)d2;
      if (ebitmap_get_bit(a->types, t->value)) {
        rc = ebitmap_set_bit(matches, t->value, 1);
      }
    }
    if (rc != SEPOL_OK) {
      ebitmap_destroy(matches);
    }
  }

  return rc;
}

/* s1 is the src type that is matched with a self
 * s2, and t2 are the source and type of the other rule
 * Assumes there is a match between s1 and s2
 */
static int cil_self_match_any(struct cil_symtab_datum *s1,
            struct cil_symtab_datum *s2,
            struct cil_symtab_datum *t2)
{
  int rc;

  if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
    rc = cil_type_match_any(s1, t2);
  } else {
    struct cil_typeattribute *a = (struct cil_typeattribute *)s1;
    ebitmap_t map;
    rc = cil_type_matches(&map, s2, t2);
    if (rc < 0) {
      return rc;
    }
    if (ebitmap_is_empty(&map)) {
      return CIL_FALSE;
    }
    rc = ebitmap_match_any(&map, a->types);
    ebitmap_destroy(&map);
  }

  return rc;
}

/* s1 is the src type that is matched with a notself
 * s2 and t2 are the source and type of the other rule
 * Assumes there is a match between s1 and s2
 */
static int cil_notself_match_any(struct cil_symtab_datum *s1,
         struct cil_symtab_datum *s2,
         struct cil_symtab_datum *t2)
{
  int rc;
  ebitmap_node_t *snode, *tnode;
  unsigned int s, t;

  if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
    struct cil_type *ts1 = (struct cil_type *)s1;
    if (FLAVOR(t2) != CIL_TYPEATTRIBUTE) {
      struct cil_type *tt2 = (struct cil_type *)t2;
      if (ts1->value != tt2->value) {
        return CIL_TRUE;
      }
    } else {
      struct cil_typeattribute *at2 =
        (struct cil_typeattribute *)t2;
      ebitmap_for_each_positive_bit(at2->types, tnode, t) {
        if (t != (unsigned int)ts1->value) {
          return CIL_TRUE;
        }
      }
    }
  } else {
    ebitmap_t smap;
    rc = cil_type_matches(&smap, s1, s2);
    if (rc < 0) {
      return rc;
    }
    if (ebitmap_is_empty(&smap)) {
      return CIL_FALSE;
    }
    if (FLAVOR(t2) != CIL_TYPEATTRIBUTE) {
      struct cil_type *tt2 = (struct cil_type *)t2;
      ebitmap_for_each_positive_bit(&smap, snode, s) {
        if (s != (unsigned int)tt2->value) {
          ebitmap_destroy(&smap);
          return CIL_TRUE;
        }
      }
    } else {
      struct cil_typeattribute *at2 =
        (struct cil_typeattribute *)t2;
      ebitmap_for_each_positive_bit(&smap, snode, s) {
        ebitmap_for_each_positive_bit(at2->types, tnode,
                    t) {
          if (s != t) {
            ebitmap_destroy(&smap);
            return CIL_TRUE;
          }
        }
      }
    }
    ebitmap_destroy(&smap);
  }

  return CIL_FALSE;
}

/* s1 is the src type that is matched with an other
 * s2, and t2 are the source and type of the other rule
 * Assumes there is a match between s1 and s2
 */
static int cil_other_match_any(struct cil_symtab_datum *s1,
             struct cil_symtab_datum *s2,
             struct cil_symtab_datum *t2)
{
  int rc;
  ebitmap_t smap, tmap;
  ebitmap_node_t *snode, *tnode;
  unsigned int s, t;

  if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
    return CIL_FALSE;
  }

  rc = cil_type_matches(&smap, s1, s2);
  if (rc < 0) {
    return rc;
  }

  if (ebitmap_is_empty(&smap)) {
    return CIL_FALSE;
  }

  rc = cil_type_matches(&tmap, s1, t2);
  if (rc < 0) {
    ebitmap_destroy(&smap);
    return rc;
  }

  if (ebitmap_is_empty(&tmap)) {
    ebitmap_destroy(&smap);
    return CIL_FALSE;
  }

  ebitmap_for_each_positive_bit(&smap, snode, s) {
    ebitmap_for_each_positive_bit(&tmap, tnode, t) {
      if (s != t) {
        rc = CIL_TRUE;
        goto exit;
      }
    }
  }

  rc = CIL_FALSE;

exit:
  ebitmap_destroy(&smap);
  ebitmap_destroy(&tmap);
  return rc;
}

/* s2 is the src type that is matched with an other
 * Assumes there is a match between s1 and s2
 * s1 is not needed, since it is known that there is a match
 */
static int cil_notself_other_match_any(struct cil_symtab_datum *s2)
{
  if (FLAVOR(s2) == CIL_TYPEATTRIBUTE) {
    struct cil_typeattribute *as2 = (struct cil_typeattribute *)s2;
    if (ebitmap_cardinality(as2->types) > 1) {
      return CIL_TRUE;
    }
  }
  return CIL_FALSE;
}

static int cil_classperms_match_any(struct cil_classperms *cp1,
            struct cil_classperms *cp2)
{
  struct cil_class *c1 = cp1->class;
  struct cil_class *c2 = cp2->class;
  struct cil_list_item *i1, *i2;

  if (&c1->datum != &c2->datum)
    return CIL_FALSE;

  cil_list_for_each(i1, cp1->perms) {
    struct cil_perm *p1 = i1->data;
    cil_list_for_each(i2, cp2->perms) {
      struct cil_perm *p2 = i2->data;
      if (&p1->datum == &p2->datum)
        return CIL_TRUE;
    }
  }
  return CIL_FALSE;
}

static int __cil_classperms_list_match_any(struct cil_classperms *cp1,
             struct cil_list *cpl2)
{
  int rc;
  struct cil_list_item *curr;

  cil_list_for_each(curr, cpl2) {
    if (curr->flavor == CIL_CLASSPERMS) {
      struct cil_classperms *cp = curr->data;
      if (FLAVOR(cp->class) == CIL_CLASS) {
        rc = cil_classperms_match_any(cp1, cp);
        if (rc == CIL_TRUE)
          return CIL_TRUE;
      } else { /* MAP */
        struct cil_list_item *i = NULL;
        cil_list_for_each(i, cp->perms) {
          struct cil_perm *cmp = i->data;
          rc = __cil_classperms_list_match_any(
            cp1, cmp->classperms);
          if (rc == CIL_TRUE)
            return CIL_TRUE;
        }
      }
    } else { /* SET */
      struct cil_classperms_set *cp_set = curr->data;
      struct cil_classpermission *cp = cp_set->set;
      rc = __cil_classperms_list_match_any(cp1,
                   cp->classperms);
      if (rc == CIL_TRUE)
        return CIL_TRUE;
    }
  }
  return CIL_FALSE;
}

static int cil_classperms_list_match_any(struct cil_list *cpl1,
           struct cil_list *cpl2)
{
  int rc;
  struct cil_list_item *curr;

  cil_list_for_each(curr, cpl1) {
    if (curr->flavor == CIL_CLASSPERMS) {
      struct cil_classperms *cp = curr->data;
      if (FLAVOR(cp->class) == CIL_CLASS) {
        rc = __cil_classperms_list_match_any(cp, cpl2);
        if (rc == CIL_TRUE)
          return CIL_TRUE;
      } else { /* MAP */
        struct cil_list_item *i = NULL;
        cil_list_for_each(i, cp->perms) {
          struct cil_perm *cmp = i->data;
          rc = cil_classperms_list_match_any(
            cmp->classperms, cpl2);
          if (rc == CIL_TRUE)
            return CIL_TRUE;
        }
      }
    } else { /* SET */
      struct cil_classperms_set *cp_set = curr->data;
      struct cil_classpermission *cp = cp_set->set;
      rc = cil_classperms_list_match_any(cp->classperms,
                 cpl2);
      if (rc == CIL_TRUE)
        return CIL_TRUE;
    }
  }
  return CIL_FALSE;
}

static void __add_classes_from_classperms_list(struct cil_list *classperms,
                 struct cil_list *class_list)
{
  struct cil_list_item *curr;

  cil_list_for_each(curr, classperms) {
    if (curr->flavor == CIL_CLASSPERMS) {
      struct cil_classperms *cp = curr->data;
      if (FLAVOR(cp->class) == CIL_CLASS) {
        cil_list_append(class_list, CIL_CLASS,
            cp->class);
      } else { /* MAP */
        struct cil_list_item *i = NULL;
        cil_list_for_each(i, cp->perms) {
          struct cil_perm *cmp = i->data;
          __add_classes_from_classperms_list(
            cmp->classperms, class_list);
        }
      }
    } else { /* SET */
      struct cil_classperms_set *cp_set = curr->data;
      struct cil_classpermission *cp = cp_set->set;
      __add_classes_from_classperms_list(cp->classperms,
                 class_list);
    }
  }
}

static int __add_classes_from_map_perms(__attribute__((unused)) hashtab_key_t k,
          hashtab_datum_t d, void *args)
{
  struct cil_list *class_list = args;
  struct cil_perm *cmp = (struct cil_perm *)d;

  __add_classes_from_classperms_list(cmp->classperms, class_list);

  return SEPOL_OK;
}

struct cil_list *cil_expand_class(struct cil_class *class)
{
  struct cil_list *class_list;

  cil_list_init(&class_list, CIL_CLASS);

  if (FLAVOR(class) == CIL_CLASS) {
    cil_list_append(class_list, CIL_CLASS, class);
  } else { /* MAP */
    cil_symtab_map(&class->perms, __add_classes_from_map_perms,
             class_list);
  }

  return class_list;
}

static int cil_permissionx_match_any(struct cil_permissionx *px1,
             struct cil_permissionx *px2)
{
  int rc = CIL_FALSE;
  struct cil_list *cl1 = NULL;
  struct cil_list *cl2 = NULL;

  if (px1->kind != px2->kind)
    goto exit;

  if (!ebitmap_match_any(px1->perms, px2->perms))
    goto exit;

  cl1 = cil_expand_class(px1->obj);
  cl2 = cil_expand_class(px2->obj);

  if (!cil_list_match_any(cl1, cl2))
    goto exit;

  rc = CIL_TRUE;

exit:
  cil_list_destroy(&cl1, CIL_FALSE);
  cil_list_destroy(&cl2, CIL_FALSE);

  return rc;
}

static int cil_find_matching_avrule(struct cil_tree_node *node,
            struct cil_avrule *avrule,
            struct cil_avrule *target,
            struct cil_list *matching, int match_self)
{
  int rc = SEPOL_OK;
  struct cil_symtab_datum *s1 = avrule->src;
  struct cil_symtab_datum *t1 = avrule->tgt;
  struct cil_symtab_datum *s2 = target->src;
  struct cil_symtab_datum *t2 = target->tgt;

  if (match_self != CIL_TRUE && avrule == target)
    goto exit;

  if (avrule->rule_kind != target->rule_kind)
    goto exit;

  if (avrule->is_extended != target->is_extended)
    goto exit;

  if (!cil_type_match_any(s1, s2))
    goto exit;

  if (t1->fqn == CIL_KEY_SELF) {
    if (t2->fqn == CIL_KEY_SELF) {
      /* The earlier check whether s1 and s2 matches is all that is needed */
      rc = CIL_TRUE;
    } else if (t2->fqn == CIL_KEY_NOTSELF ||
         t2->fqn == CIL_KEY_OTHER) {
      rc = CIL_FALSE;
    } else {
      rc = cil_self_match_any(s1, s2, t2);
    }
  } else if (t1->fqn == CIL_KEY_NOTSELF) {
    if (t2->fqn == CIL_KEY_SELF) {
      rc = CIL_FALSE;
    } else if (t2->fqn == CIL_KEY_NOTSELF) {
      /* The earlier check whether s1 and s2 matches is all that is needed */
      rc = CIL_TRUE;
    } else if (t2->fqn == CIL_KEY_OTHER) {
      rc = cil_notself_other_match_any(s2);
    } else {
      rc = cil_notself_match_any(s1, s2, t2);
    }
  } else if (t1->fqn == CIL_KEY_OTHER) {
    if (t2->fqn == CIL_KEY_SELF) {
      rc = CIL_FALSE;
    } else if (t2->fqn == CIL_KEY_NOTSELF) {
      rc = cil_notself_other_match_any(s1);
    } else if (t2->fqn == CIL_KEY_OTHER) {
      /* The earlier check whether s1 and s2 matches is all that is needed */
      rc = CIL_TRUE;
    } else {
      rc = cil_other_match_any(s1, s2, t2);
    }
  } else {
    if (t2->fqn == CIL_KEY_SELF) {
      rc = cil_self_match_any(s2, s1, t1);
    } else if (t2->fqn == CIL_KEY_NOTSELF) {
      rc = cil_notself_match_any(s2, s1, t1);
    } else if (t2->fqn == CIL_KEY_OTHER) {
      rc = cil_other_match_any(s2, s1, t1);
    } else {
      rc = cil_type_match_any(t1, t2);
    }
  }

  if (rc < 0) {
    goto exit;
  } else if (rc == CIL_FALSE) {
    rc = SEPOL_OK;
    goto exit;
  }

  if (!target->is_extended) {
    if (cil_classperms_list_match_any(avrule->perms.classperms,
              target->perms.classperms)) {
      cil_list_append(matching, CIL_NODE, node);
    }
  } else {
    if (cil_permissionx_match_any(avrule->perms.x.permx,
                target->perms.x.permx)) {
      cil_list_append(matching, CIL_NODE, node);
    }
  }

  rc = SEPOL_OK;

exit:
  return rc;
}

static int __cil_find_matching_avrule_in_ast(struct cil_tree_node *node,
               uint32_t *finished,
               void *extra_args)
{
  int rc = SEPOL_OK;
  struct cil_args_find *args = extra_args;

  if (node->flavor == CIL_BLOCK) {
    struct cil_block *blk = node->data;
    if (blk->is_abstract == CIL_TRUE) {
      *finished = CIL_TREE_SKIP_HEAD;
      goto exit;
    }
  } else if (node->flavor == CIL_MACRO) {
    *finished = CIL_TREE_SKIP_HEAD;
    goto exit;
  } else if (node->flavor == CIL_AVRULE || node->flavor == CIL_AVRULEX) {
    if (node->flavor == args->flavor) {
      rc = cil_find_matching_avrule(node, node->data,
                  args->target,
                  args->matching,
                  args->match_self);
    }
  }

exit:
  return rc;
}

int cil_find_matching_avrule_in_ast(struct cil_tree_node *current,
            enum cil_flavor flavor, void *target,
            struct cil_list *matching, int match_self)
{
  int rc;
  struct cil_args_find args;

  args.flavor = flavor;
  args.target = target;
  args.matching = matching;
  args.match_self = match_self;

  rc = cil_tree_walk(current, __cil_find_matching_avrule_in_ast, NULL,
         NULL, &args);
  if (rc) {
    cil_log(CIL_ERR,
      "An error occurred while searching for avrule in AST\n");
  }

  return rc;
}

Coverage Report

Created: 2026-07-15 06:42

Line	Count	Source
1		/*
2		* Copyright 2011 Tresys Technology, LLC. All rights reserved.
3		*
4		* Redistribution and use in source and binary forms, with or without
5		* modification, are permitted provided that the following conditions are met:
6		*
7		* 1. Redistributions of source code must retain the above copyright notice,
8		* this list of conditions and the following disclaimer.
9		*
10		* 2. Redistributions in binary form must reproduce the above copyright notice,
11		* this list of conditions and the following disclaimer in the documentation
12		* and/or other materials provided with the distribution.
13		*
14		* THIS SOFTWARE IS PROVIDED BY TRESYS TECHNOLOGY, LLC ``AS IS'' AND ANY EXPRESS
15		* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16		* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
17		* EVENT SHALL TRESYS TECHNOLOGY, LLC OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18		* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
19		* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20		* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
21		* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
22		* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
23		* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24		*
25		* The views and conclusions contained in the software and documentation are those
26		* of the authors and should not be interpreted as representing official policies,
27		* either expressed or implied, of Tresys Technology, LLC.
28		*/
29
30		#include <sepol/policydb/ebitmap.h>
31
32		#include "cil_internal.h"
33		#include "cil_find.h"
34		#include "cil_flavor.h"
35		#include "cil_list.h"
36		#include "cil_log.h"
37		#include "cil_symtab.h"
38
39		struct cil_args_find {
40		enum cil_flavor flavor;
41		void *target;
42		struct cil_list *matching;
43		int match_self;
44		};
45
46		static int cil_type_match_any(struct cil_symtab_datum *d1,
47		struct cil_symtab_datum *d2)
48	0	{
49	0	enum cil_flavor f1 = FLAVOR(d1);
50	0	enum cil_flavor f2 = FLAVOR(d2);
51
52	0	if (f1 != CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
53	0	struct cil_type t1 = (struct cil_type )d1;
54	0	struct cil_type t2 = (struct cil_type )d2;
55	0	if (t1->value == t2->value) {
56	0	return CIL_TRUE;
57	0	}
58	0	} else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
59	0	struct cil_typeattribute a = (struct cil_typeattribute )d1;
60	0	struct cil_type t = (struct cil_type )d2;
61	0	if (ebitmap_get_bit(a->types, t->value)) {
62	0	return CIL_TRUE;
63	0	}
64	0	} else if (f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
65	0	struct cil_type t = (struct cil_type )d1;
66	0	struct cil_typeattribute a = (struct cil_typeattribute )d2;
67	0	if (ebitmap_get_bit(a->types, t->value)) {
68	0	return CIL_TRUE;
69	0	}
70	0	} else {
71		/* Both are attributes */
72	0	struct cil_typeattribute a1 = (struct cil_typeattribute )d1;
73	0	struct cil_typeattribute a2 = (struct cil_typeattribute )d2;
74	0	if (d1 == d2) {
75	0	return CIL_TRUE;
76	0	} else if (ebitmap_match_any(a1->types, a2->types)) {
77	0	return CIL_TRUE;
78	0	}
79	0	}
80	0	return CIL_FALSE;
81	0	}
82
83		static int cil_type_matches(ebitmap_t matches, struct cil_symtab_datum d1,
84		struct cil_symtab_datum *d2)
85	0	{
86	0	int rc = SEPOL_OK;
87	0	enum cil_flavor f1 = FLAVOR(d1);
88	0	enum cil_flavor f2 = FLAVOR(d2);
89
90	0	if (f1 == CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
91	0	struct cil_typeattribute a1 = (struct cil_typeattribute )d1;
92	0	struct cil_typeattribute a2 = (struct cil_typeattribute )d2;
93	0	rc = ebitmap_and(matches, a1->types, a2->types);
94	0	} else {
95	0	ebitmap_init(matches);
96	0	if (f1 != CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
97	0	struct cil_type t1 = (struct cil_type )d1;
98	0	struct cil_type t2 = (struct cil_type )d2;
99	0	if (t1->value == t2->value) {
100	0	rc = ebitmap_set_bit(matches, t1->value, 1);
101	0	}
102	0	} else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
103	0	struct cil_typeattribute *a =
104	0	(struct cil_typeattribute *)d1;
105	0	struct cil_type t = (struct cil_type )d2;
106	0	if (ebitmap_get_bit(a->types, t->value)) {
107	0	rc = ebitmap_set_bit(matches, t->value, 1);
108	0	}
109	0	} else { // f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE
110	0	struct cil_type t = (struct cil_type )d1;
111	0	struct cil_typeattribute *a =
112	0	(struct cil_typeattribute *)d2;
113	0	if (ebitmap_get_bit(a->types, t->value)) {
114	0	rc = ebitmap_set_bit(matches, t->value, 1);
115	0	}
116	0	}
117	0	if (rc != SEPOL_OK) {
118	0	ebitmap_destroy(matches);
119	0	}
120	0	}
121
122	0	return rc;
123	0	}
124
125		/* s1 is the src type that is matched with a self
126		* s2, and t2 are the source and type of the other rule
127		* Assumes there is a match between s1 and s2
128		*/
129		static int cil_self_match_any(struct cil_symtab_datum *s1,
130		struct cil_symtab_datum *s2,
131		struct cil_symtab_datum *t2)
132	0	{
133	0	int rc;
134
135	0	if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
136	0	rc = cil_type_match_any(s1, t2);
137	0	} else {
138	0	struct cil_typeattribute a = (struct cil_typeattribute )s1;
139	0	ebitmap_t map;
140	0	rc = cil_type_matches(&map, s2, t2);
141	0	if (rc < 0) {
142	0	return rc;
143	0	}
144	0	if (ebitmap_is_empty(&map)) {
145	0	return CIL_FALSE;
146	0	}
147	0	rc = ebitmap_match_any(&map, a->types);
148	0	ebitmap_destroy(&map);
149	0	}
150
151	0	return rc;
152	0	}
153
154		/* s1 is the src type that is matched with a notself
155		* s2 and t2 are the source and type of the other rule
156		* Assumes there is a match between s1 and s2
157		*/
158		static int cil_notself_match_any(struct cil_symtab_datum *s1,
159		struct cil_symtab_datum *s2,
160		struct cil_symtab_datum *t2)
161	0	{
162	0	int rc;
163	0	ebitmap_node_t snode, tnode;
164	0	unsigned int s, t;
165
166	0	if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
167	0	struct cil_type ts1 = (struct cil_type )s1;
168	0	if (FLAVOR(t2) != CIL_TYPEATTRIBUTE) {
169	0	struct cil_type tt2 = (struct cil_type )t2;
170	0	if (ts1->value != tt2->value) {
171	0	return CIL_TRUE;
172	0	}
173	0	} else {
174	0	struct cil_typeattribute *at2 =
175	0	(struct cil_typeattribute *)t2;
176	0	ebitmap_for_each_positive_bit(at2->types, tnode, t) {
177	0	if (t != (unsigned int)ts1->value) {
178	0	return CIL_TRUE;
179	0	}
180	0	}
181	0	}
182	0	} else {
183	0	ebitmap_t smap;
184	0	rc = cil_type_matches(&smap, s1, s2);
185	0	if (rc < 0) {
186	0	return rc;
187	0	}
188	0	if (ebitmap_is_empty(&smap)) {
189	0	return CIL_FALSE;
190	0	}
191	0	if (FLAVOR(t2) != CIL_TYPEATTRIBUTE) {
192	0	struct cil_type tt2 = (struct cil_type )t2;
193	0	ebitmap_for_each_positive_bit(&smap, snode, s) {
194	0	if (s != (unsigned int)tt2->value) {
195	0	ebitmap_destroy(&smap);
196	0	return CIL_TRUE;
197	0	}
198	0	}
199	0	} else {
200	0	struct cil_typeattribute *at2 =
201	0	(struct cil_typeattribute *)t2;
202	0	ebitmap_for_each_positive_bit(&smap, snode, s) {
203	0	ebitmap_for_each_positive_bit(at2->types, tnode,
204	0	t) {
205	0	if (s != t) {
206	0	ebitmap_destroy(&smap);
207	0	return CIL_TRUE;
208	0	}
209	0	}
210	0	}
211	0	}
212	0	ebitmap_destroy(&smap);
213	0	}
214
215	0	return CIL_FALSE;
216	0	}
217
218		/* s1 is the src type that is matched with an other
219		* s2, and t2 are the source and type of the other rule
220		* Assumes there is a match between s1 and s2
221		*/
222		static int cil_other_match_any(struct cil_symtab_datum *s1,
223		struct cil_symtab_datum *s2,
224		struct cil_symtab_datum *t2)
225	0	{
226	0	int rc;
227	0	ebitmap_t smap, tmap;
228	0	ebitmap_node_t snode, tnode;
229	0	unsigned int s, t;
230
231	0	if (FLAVOR(s1) != CIL_TYPEATTRIBUTE) {
232	0	return CIL_FALSE;
233	0	}
234
235	0	rc = cil_type_matches(&smap, s1, s2);
236	0	if (rc < 0) {
237	0	return rc;
238	0	}
239
240	0	if (ebitmap_is_empty(&smap)) {
241	0	return CIL_FALSE;
242	0	}
243
244	0	rc = cil_type_matches(&tmap, s1, t2);
245	0	if (rc < 0) {
246	0	ebitmap_destroy(&smap);
247	0	return rc;
248	0	}
249
250	0	if (ebitmap_is_empty(&tmap)) {
251	0	ebitmap_destroy(&smap);
252	0	return CIL_FALSE;
253	0	}
254
255	0	ebitmap_for_each_positive_bit(&smap, snode, s) {
256	0	ebitmap_for_each_positive_bit(&tmap, tnode, t) {
257	0	if (s != t) {
258	0	rc = CIL_TRUE;
259	0	goto exit;
260	0	}
261	0	}
262	0	}
263
264	0	rc = CIL_FALSE;
265
266	0	exit:
267	0	ebitmap_destroy(&smap);
268	0	ebitmap_destroy(&tmap);
269	0	return rc;
270	0	}
271
272		/* s2 is the src type that is matched with an other
273		* Assumes there is a match between s1 and s2
274		* s1 is not needed, since it is known that there is a match
275		*/
276		static int cil_notself_other_match_any(struct cil_symtab_datum *s2)
277	0	{
278	0	if (FLAVOR(s2) == CIL_TYPEATTRIBUTE) {
279	0	struct cil_typeattribute as2 = (struct cil_typeattribute )s2;
280	0	if (ebitmap_cardinality(as2->types) > 1) {
281	0	return CIL_TRUE;
282	0	}
283	0	}
284	0	return CIL_FALSE;
285	0	}
286
287		static int cil_classperms_match_any(struct cil_classperms *cp1,
288		struct cil_classperms *cp2)
289	0	{
290	0	struct cil_class *c1 = cp1->class;
291	0	struct cil_class *c2 = cp2->class;
292	0	struct cil_list_item i1, i2;
293
294	0	if (&c1->datum != &c2->datum)
295	0	return CIL_FALSE;
296
297	0	cil_list_for_each(i1, cp1->perms) {
298	0	struct cil_perm *p1 = i1->data;
299	0	cil_list_for_each(i2, cp2->perms) {
300	0	struct cil_perm *p2 = i2->data;
301	0	if (&p1->datum == &p2->datum)
302	0	return CIL_TRUE;
303	0	}
304	0	}
305	0	return CIL_FALSE;
306	0	}
307
308		static int __cil_classperms_list_match_any(struct cil_classperms *cp1,
309		struct cil_list *cpl2)
310	0	{
311	0	int rc;
312	0	struct cil_list_item *curr;
313
314	0	cil_list_for_each(curr, cpl2) {
315	0	if (curr->flavor == CIL_CLASSPERMS) {
316	0	struct cil_classperms *cp = curr->data;
317	0	if (FLAVOR(cp->class) == CIL_CLASS) {
318	0	rc = cil_classperms_match_any(cp1, cp);
319	0	if (rc == CIL_TRUE)
320	0	return CIL_TRUE;
321	0	} else { /* MAP */
322	0	struct cil_list_item *i = NULL;
323	0	cil_list_for_each(i, cp->perms) {
324	0	struct cil_perm *cmp = i->data;
325	0	rc = __cil_classperms_list_match_any(
326	0	cp1, cmp->classperms);
327	0	if (rc == CIL_TRUE)
328	0	return CIL_TRUE;
329	0	}
330	0	}
331	0	} else { /* SET */
332	0	struct cil_classperms_set *cp_set = curr->data;
333	0	struct cil_classpermission *cp = cp_set->set;
334	0	rc = __cil_classperms_list_match_any(cp1,
335	0	cp->classperms);
336	0	if (rc == CIL_TRUE)
337	0	return CIL_TRUE;
338	0	}
339	0	}
340	0	return CIL_FALSE;
341	0	}
342
343		static int cil_classperms_list_match_any(struct cil_list *cpl1,
344		struct cil_list *cpl2)
345	0	{
346	0	int rc;
347	0	struct cil_list_item *curr;
348
349	0	cil_list_for_each(curr, cpl1) {
350	0	if (curr->flavor == CIL_CLASSPERMS) {
351	0	struct cil_classperms *cp = curr->data;
352	0	if (FLAVOR(cp->class) == CIL_CLASS) {
353	0	rc = __cil_classperms_list_match_any(cp, cpl2);
354	0	if (rc == CIL_TRUE)
355	0	return CIL_TRUE;
356	0	} else { /* MAP */
357	0	struct cil_list_item *i = NULL;
358	0	cil_list_for_each(i, cp->perms) {
359	0	struct cil_perm *cmp = i->data;
360	0	rc = cil_classperms_list_match_any(
361	0	cmp->classperms, cpl2);
362	0	if (rc == CIL_TRUE)
363	0	return CIL_TRUE;
364	0	}
365	0	}
366	0	} else { /* SET */
367	0	struct cil_classperms_set *cp_set = curr->data;
368	0	struct cil_classpermission *cp = cp_set->set;
369	0	rc = cil_classperms_list_match_any(cp->classperms,
370	0	cpl2);
371	0	if (rc == CIL_TRUE)
372	0	return CIL_TRUE;
373	0	}
374	0	}
375	0	return CIL_FALSE;
376	0	}
377
378		static void __add_classes_from_classperms_list(struct cil_list *classperms,
379		struct cil_list *class_list)
380	0	{
381	0	struct cil_list_item *curr;
382
383	0	cil_list_for_each(curr, classperms) {
384	0	if (curr->flavor == CIL_CLASSPERMS) {
385	0	struct cil_classperms *cp = curr->data;
386	0	if (FLAVOR(cp->class) == CIL_CLASS) {
387	0	cil_list_append(class_list, CIL_CLASS,
388	0	cp->class);
389	0	} else { /* MAP */
390	0	struct cil_list_item *i = NULL;
391	0	cil_list_for_each(i, cp->perms) {
392	0	struct cil_perm *cmp = i->data;
393	0	__add_classes_from_classperms_list(
394	0	cmp->classperms, class_list);
395	0	}
396	0	}
397	0	} else { /* SET */
398	0	struct cil_classperms_set *cp_set = curr->data;
399	0	struct cil_classpermission *cp = cp_set->set;
400	0	__add_classes_from_classperms_list(cp->classperms,
401	0	class_list);
402	0	}
403	0	}
404	0	}
405
406		static int __add_classes_from_map_perms(__attribute__((unused)) hashtab_key_t k,
407		hashtab_datum_t d, void *args)
408	0	{
409	0	struct cil_list *class_list = args;
410	0	struct cil_perm cmp = (struct cil_perm )d;
411
412	0	__add_classes_from_classperms_list(cmp->classperms, class_list);
413
414	0	return SEPOL_OK;
415	0	}
416
417		struct cil_list cil_expand_class(struct cil_class class)
418	0	{
419	0	struct cil_list *class_list;
420
421	0	cil_list_init(&class_list, CIL_CLASS);
422
423	0	if (FLAVOR(class) == CIL_CLASS) {
424	0	cil_list_append(class_list, CIL_CLASS, class);
425	0	} else { /* MAP */
426	0	cil_symtab_map(&class->perms, __add_classes_from_map_perms,
427	0	class_list);
428	0	}
429
430	0	return class_list;
431	0	}
432
433		static int cil_permissionx_match_any(struct cil_permissionx *px1,
434		struct cil_permissionx *px2)
435	0	{
436	0	int rc = CIL_FALSE;
437	0	struct cil_list *cl1 = NULL;
438	0	struct cil_list *cl2 = NULL;
439
440	0	if (px1->kind != px2->kind)
441	0	goto exit;
442
443	0	if (!ebitmap_match_any(px1->perms, px2->perms))
444	0	goto exit;
445
446	0	cl1 = cil_expand_class(px1->obj);
447	0	cl2 = cil_expand_class(px2->obj);
448
449	0	if (!cil_list_match_any(cl1, cl2))
450	0	goto exit;
451
452	0	rc = CIL_TRUE;
453
454	0	exit:
455	0	cil_list_destroy(&cl1, CIL_FALSE);
456	0	cil_list_destroy(&cl2, CIL_FALSE);
457
458	0	return rc;
459	0	}
460
461		static int cil_find_matching_avrule(struct cil_tree_node *node,
462		struct cil_avrule *avrule,
463		struct cil_avrule *target,
464		struct cil_list *matching, int match_self)
465	0	{
466	0	int rc = SEPOL_OK;
467	0	struct cil_symtab_datum *s1 = avrule->src;
468	0	struct cil_symtab_datum *t1 = avrule->tgt;
469	0	struct cil_symtab_datum *s2 = target->src;
470	0	struct cil_symtab_datum *t2 = target->tgt;
471
472	0	if (match_self != CIL_TRUE && avrule == target)
473	0	goto exit;
474
475	0	if (avrule->rule_kind != target->rule_kind)
476	0	goto exit;
477
478	0	if (avrule->is_extended != target->is_extended)
479	0	goto exit;
480
481	0	if (!cil_type_match_any(s1, s2))
482	0	goto exit;
483
484	0	if (t1->fqn == CIL_KEY_SELF) {
485	0	if (t2->fqn == CIL_KEY_SELF) {
486		/* The earlier check whether s1 and s2 matches is all that is needed */
487	0	rc = CIL_TRUE;
488	0	} else if (t2->fqn == CIL_KEY_NOTSELF \|\|
489	0	t2->fqn == CIL_KEY_OTHER) {
490	0	rc = CIL_FALSE;
491	0	} else {
492	0	rc = cil_self_match_any(s1, s2, t2);
493	0	}
494	0	} else if (t1->fqn == CIL_KEY_NOTSELF) {
495	0	if (t2->fqn == CIL_KEY_SELF) {
496	0	rc = CIL_FALSE;
497	0	} else if (t2->fqn == CIL_KEY_NOTSELF) {
498		/* The earlier check whether s1 and s2 matches is all that is needed */
499	0	rc = CIL_TRUE;
500	0	} else if (t2->fqn == CIL_KEY_OTHER) {
501	0	rc = cil_notself_other_match_any(s2);
502	0	} else {
503	0	rc = cil_notself_match_any(s1, s2, t2);
504	0	}
505	0	} else if (t1->fqn == CIL_KEY_OTHER) {
506	0	if (t2->fqn == CIL_KEY_SELF) {
507	0	rc = CIL_FALSE;
508	0	} else if (t2->fqn == CIL_KEY_NOTSELF) {
509	0	rc = cil_notself_other_match_any(s1);
510	0	} else if (t2->fqn == CIL_KEY_OTHER) {
511		/* The earlier check whether s1 and s2 matches is all that is needed */
512	0	rc = CIL_TRUE;
513	0	} else {
514	0	rc = cil_other_match_any(s1, s2, t2);
515	0	}
516	0	} else {
517	0	if (t2->fqn == CIL_KEY_SELF) {
518	0	rc = cil_self_match_any(s2, s1, t1);
519	0	} else if (t2->fqn == CIL_KEY_NOTSELF) {
520	0	rc = cil_notself_match_any(s2, s1, t1);
521	0	} else if (t2->fqn == CIL_KEY_OTHER) {
522	0	rc = cil_other_match_any(s2, s1, t1);
523	0	} else {
524	0	rc = cil_type_match_any(t1, t2);
525	0	}
526	0	}
527
528	0	if (rc < 0) {
529	0	goto exit;
530	0	} else if (rc == CIL_FALSE) {
531	0	rc = SEPOL_OK;
532	0	goto exit;
533	0	}
534
535	0	if (!target->is_extended) {
536	0	if (cil_classperms_list_match_any(avrule->perms.classperms,
537	0	target->perms.classperms)) {
538	0	cil_list_append(matching, CIL_NODE, node);
539	0	}
540	0	} else {
541	0	if (cil_permissionx_match_any(avrule->perms.x.permx,
542	0	target->perms.x.permx)) {
543	0	cil_list_append(matching, CIL_NODE, node);
544	0	}
545	0	}
546
547	0	rc = SEPOL_OK;
548
549	0	exit:
550	0	return rc;
551	0	}
552
553		static int __cil_find_matching_avrule_in_ast(struct cil_tree_node *node,
554		uint32_t *finished,
555		void *extra_args)
556	0	{
557	0	int rc = SEPOL_OK;
558	0	struct cil_args_find *args = extra_args;
559
560	0	if (node->flavor == CIL_BLOCK) {
561	0	struct cil_block *blk = node->data;
562	0	if (blk->is_abstract == CIL_TRUE) {
563	0	*finished = CIL_TREE_SKIP_HEAD;
564	0	goto exit;
565	0	}
566	0	} else if (node->flavor == CIL_MACRO) {
567	0	*finished = CIL_TREE_SKIP_HEAD;
568	0	goto exit;
569	0	} else if (node->flavor == CIL_AVRULE \|\| node->flavor == CIL_AVRULEX) {
570	0	if (node->flavor == args->flavor) {
571	0	rc = cil_find_matching_avrule(node, node->data,
572	0	args->target,
573	0	args->matching,
574	0	args->match_self);
575	0	}
576	0	}
577
578	0	exit:
579	0	return rc;
580	0	}
581
582		int cil_find_matching_avrule_in_ast(struct cil_tree_node *current,
583		enum cil_flavor flavor, void *target,
584		struct cil_list *matching, int match_self)
585	0	{
586	0	int rc;
587	0	struct cil_args_find args;
588
589	0	args.flavor = flavor;
590	0	args.target = target;
591	0	args.matching = matching;
592	0	args.match_self = match_self;
593
594	0	rc = cil_tree_walk(current, __cil_find_matching_avrule_in_ast, NULL,
595	0	NULL, &args);
596	0	if (rc) {
597	0	cil_log(CIL_ERR,
598	0	"An error occurred while searching for avrule in AST\n");
599	0	}
600
601	0	return rc;
602	0	}