/src/selinux/libsepol/cil/src/cil_verify.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 <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <unistd.h>
#include <ctype.h>

#include <sepol/policydb/polcaps.h>
#include <sepol/errcodes.h>

#include "cil_internal.h"
#include "cil_flavor.h"
#include "cil_log.h"
#include "cil_mem.h"
#include "cil_tree.h"
#include "cil_list.h"
#include "cil_find.h"
#include "cil_stack.h"

#include "cil_verify.h"

static int __cil_is_reserved_name(const char *name, enum cil_flavor flavor)
{
  switch (flavor) {
  case CIL_BOOL:
  case CIL_TUNABLE:
    if ((name == CIL_KEY_EQ) || (name == CIL_KEY_NEQ))
      return CIL_TRUE;
    break;
  case CIL_PERM:
  case CIL_MAP_PERM:
  case CIL_USER:
  case CIL_USERATTRIBUTE:
  case CIL_ROLE:
  case CIL_ROLEATTRIBUTE:
    if (name == CIL_KEY_ALL)
      return CIL_TRUE;
    break;
  case CIL_TYPE:
  case CIL_TYPEATTRIBUTE:
  case CIL_TYPEALIAS:
    if ((name == CIL_KEY_ALL) || (name == CIL_KEY_SELF) || (name == CIL_KEY_NOTSELF)
      || (name == CIL_KEY_OTHER))
      return CIL_TRUE;
    break;
  case CIL_CAT:
  case CIL_CATSET:
  case CIL_CATALIAS:
  case CIL_PERMISSIONX:
    if ((name == CIL_KEY_ALL) || (name == CIL_KEY_RANGE))
      return CIL_TRUE;
    break;
  default:
    /* All of these are not used in expressions */
    return CIL_FALSE;
    break;
  }

  /* Everything not under the default case is also checked for these */
  if ((name == CIL_KEY_AND) || (name == CIL_KEY_OR) || (name == CIL_KEY_NOT) || (name == CIL_KEY_XOR)) {
    return CIL_TRUE;
  }

  return CIL_FALSE;
}

int cil_verify_name(const struct cil_db *db, const char *name, enum cil_flavor flavor)
{
  int rc = SEPOL_ERR;
  int len;
  int i = 0;

  if (name == NULL) {
    cil_log(CIL_ERR, "Name is NULL\n");
    goto exit;
  }

  len = strlen(name);
  if (len >= CIL_MAX_NAME_LENGTH) {
    cil_log(CIL_ERR, "Name length greater than max name length of %d", 
      CIL_MAX_NAME_LENGTH);
    rc = SEPOL_ERR;
    goto exit;
  }

  if (!isalpha(name[0])) {
      cil_log(CIL_ERR, "First character in %s is not a letter\n", name);
      goto exit;
  }

  if (db->qualified_names == CIL_FALSE) {
    for (i = 1; i < len; i++) {
      if (!isalnum(name[i]) && name[i] != '_' && name[i] != '-') {
        cil_log(CIL_ERR, "Invalid character \"%c\" in %s\n", name[i], name);
        goto exit;
      }
    }
  } else {
    for (i = 1; i < len; i++) {
      if (!isalnum(name[i]) && name[i] != '_' && name[i] != '-' && name[i] != '.') {
        cil_log(CIL_ERR, "Invalid character \"%c\" in %s\n", name[i], name);
        goto exit;
      }
    }
  }

  if (__cil_is_reserved_name(name, flavor)) {
    cil_log(CIL_ERR, "Name %s is a reserved word\n", name);
    goto exit;
  }

  return SEPOL_OK;

exit:
  cil_log(CIL_ERR, "Invalid name\n");
  return rc;
}

int __cil_verify_syntax(struct cil_tree_node *parse_current, enum cil_syntax s[], size_t len)
{
  struct cil_tree_node *c = parse_current;
  size_t i = 0;

  while (i < len && c != NULL) {
    if ((s[i] & CIL_SYN_STRING) && c->data != NULL && c->cl_head == NULL) {
      c = c->next;
      i++;
    } else if ((s[i] & CIL_SYN_LIST) && c->data == NULL && c->cl_head != NULL) {
      c = c->next;
      i++;
    } else if ((s[i] & CIL_SYN_EMPTY_LIST) && c->data == NULL && c->cl_head == NULL) {
      c = c->next;
      i++;
    } else if ((s[i] & CIL_SYN_N_LISTS) || (s[i] & CIL_SYN_N_STRINGS)) {
      while (c != NULL) {
        if ((s[i] & CIL_SYN_N_LISTS) && c->data == NULL && c->cl_head != NULL) {
          c = c->next;
        } else if ((s[i] & CIL_SYN_N_STRINGS) && c->data != NULL && c->cl_head == NULL) {
          c = c->next;
        } else {
          goto exit;
        }
      }
      i++;
      break; /* Only CIL_SYN_END allowed after these */
    } else {
      goto exit;
    }
  }

  if (i < len && (s[i] & CIL_SYN_END) && c == NULL) {
    return SEPOL_OK;
  }

exit:
  cil_log(CIL_ERR, "Invalid syntax\n");
  return SEPOL_ERR;
}

int cil_verify_expr_syntax(struct cil_tree_node *current, enum cil_flavor op, enum cil_flavor expr_flavor)
{
  int rc;
  enum cil_syntax syntax[] = {
    CIL_SYN_STRING,
    CIL_SYN_STRING | CIL_SYN_LIST,
    CIL_SYN_STRING | CIL_SYN_LIST,
    CIL_SYN_END
  };
  int syntax_len = sizeof(syntax)/sizeof(*syntax);

  switch (op) {
  case CIL_NOT:
    syntax[2] = CIL_SYN_END;
    syntax_len = 3;
    break;
  case CIL_AND:
  case CIL_OR:
  case CIL_XOR:
    break;
  case CIL_EQ:
  case CIL_NEQ:
    if (expr_flavor != CIL_BOOL && expr_flavor != CIL_TUNABLE ) {
      cil_log(CIL_ERR,"Invalid operator (%s) for set expression\n", (char*)current->data);
      goto exit;
    }
    break;
  case CIL_ALL:
    if (expr_flavor == CIL_BOOL || expr_flavor == CIL_TUNABLE) {
      cil_log(CIL_ERR,"Invalid operator (%s) for boolean or tunable expression\n", (char*)current->data);
      goto exit;
    }
    syntax[1] = CIL_SYN_END;
    syntax_len = 2;
    break;
  case CIL_RANGE:
    if (expr_flavor != CIL_CAT && expr_flavor != CIL_PERMISSIONX) {
      cil_log(CIL_ERR,"Operator (%s) only valid for catset and permissionx expression\n", (char*)current->data);
      goto exit;
    }
    syntax[1] = CIL_SYN_STRING;
    syntax[2] = CIL_SYN_STRING;
    break;
  case CIL_NONE: /* String or List */
    syntax[0] = CIL_SYN_N_STRINGS | CIL_SYN_N_LISTS;
    syntax[1] = CIL_SYN_END;
    syntax_len = 2;
    break;
  default:
    cil_log(CIL_ERR,"Unexpected value (%s) for expression operator\n", (char*)current->data);
    goto exit;
  }

  rc = __cil_verify_syntax(current, syntax, syntax_len);
  if (rc != SEPOL_OK) {
    goto exit;
  }

  return SEPOL_OK;

exit:
  return SEPOL_ERR;
}

int cil_verify_constraint_leaf_expr_syntax(enum cil_flavor l_flavor, enum cil_flavor r_flavor, enum cil_flavor op, enum cil_flavor expr_flavor)
{
  if (r_flavor == CIL_STRING || r_flavor == CIL_LIST) {
    if (l_flavor == CIL_CONS_L1 || l_flavor == CIL_CONS_L2 || l_flavor == CIL_CONS_H1 || l_flavor == CIL_CONS_H2 ) {
      cil_log(CIL_ERR, "l1, l2, h1, and h2 cannot be used on the left side with a string or list on the right side\n");
      goto exit;
    } else if (l_flavor == CIL_CONS_U3 || l_flavor == CIL_CONS_R3 || l_flavor == CIL_CONS_T3) {
      if (expr_flavor != CIL_VALIDATETRANS && expr_flavor != CIL_MLSVALIDATETRANS) {
        cil_log(CIL_ERR, "u3, r3, and t3 can only be used with (mls)validatetrans rules\n");
        goto exit;
      }
    }
  } else {
    if (r_flavor == CIL_CONS_U1 || r_flavor == CIL_CONS_R1 || r_flavor == CIL_CONS_T1) {
      cil_log(CIL_ERR, "u1, r1, and t1 are not allowed on the right side\n");
      goto exit;
    } else if (r_flavor == CIL_CONS_U3 || r_flavor == CIL_CONS_R3 || r_flavor == CIL_CONS_T3) {
      cil_log(CIL_ERR, "u3, r3, and t3 are not allowed on the right side\n");
      goto exit;
    } else if (r_flavor == CIL_CONS_U2) {
      if (op != CIL_EQ && op != CIL_NEQ) {
        cil_log(CIL_ERR, "u2 on the right side must be used with eq or neq as the operator\n");
        goto exit;
      } else if (l_flavor != CIL_CONS_U1) {
        cil_log(CIL_ERR, "u2 on the right side must be used with u1 on the left\n");
        goto exit;
      }
    } else if (r_flavor == CIL_CONS_R2) {
      if (l_flavor != CIL_CONS_R1) {
        cil_log(CIL_ERR, "r2 on the right side must be used with r1 on the left\n");
        goto exit;
      }
    } else if (r_flavor == CIL_CONS_T2) {
      if (op != CIL_EQ && op != CIL_NEQ) {
        cil_log(CIL_ERR, "t2 on the right side must be used with eq or neq as the operator\n");
        goto exit;
      } else if (l_flavor != CIL_CONS_T1) {
        cil_log(CIL_ERR, "t2 on the right side must be used with t1 on the left\n");
        goto exit;
      }
    } else if (r_flavor == CIL_CONS_L2) {
      if (l_flavor != CIL_CONS_L1 && l_flavor != CIL_CONS_H1) {
        cil_log(CIL_ERR, "l2 on the right side must be used with l1 or h1 on the left\n");
        goto exit;
      }
    } else if (r_flavor == CIL_CONS_H2) {
      if (l_flavor != CIL_CONS_L1 && l_flavor != CIL_CONS_L2 && l_flavor != CIL_CONS_H1 ) {
        cil_log(CIL_ERR, "h2 on the right side must be used with l1, l2, or h1 on the left\n");
        goto exit;
      }
    } else if (r_flavor == CIL_CONS_H1) {
      if (l_flavor != CIL_CONS_L1) {
        cil_log(CIL_ERR, "h1 on the right side must be used with l1 on the left\n");
        goto exit;
      }
    }
  }

  return SEPOL_OK;

exit:
  return SEPOL_ERR;
}

int cil_verify_constraint_expr_syntax(struct cil_tree_node *current, enum cil_flavor op)
{
  int rc;
  enum cil_syntax syntax[] = {
    CIL_SYN_STRING,
    CIL_SYN_END,
    CIL_SYN_END,
    CIL_SYN_END
  };
  int syntax_len = sizeof(syntax)/sizeof(*syntax);

  switch (op) {
  case CIL_NOT:
    syntax[1] = CIL_SYN_LIST;
    syntax_len--;
    break;
  case CIL_AND:
  case CIL_OR:
    syntax[1] = CIL_SYN_LIST;
    syntax[2] = CIL_SYN_LIST;
    break;
  case CIL_EQ:
  case CIL_NEQ:
    syntax[1] = CIL_SYN_STRING;
    syntax[2] = CIL_SYN_STRING | CIL_SYN_LIST;
    break;
  case CIL_CONS_DOM:
  case CIL_CONS_DOMBY:
  case CIL_CONS_INCOMP:
    syntax[1] = CIL_SYN_STRING;
    syntax[2] = CIL_SYN_STRING;
    break;
  default:
    cil_log(CIL_ERR, "Invalid operator (%s) for constraint expression\n", (char*)current->data);
    goto exit;
  }

  rc = __cil_verify_syntax(current, syntax, syntax_len);
  if (rc != SEPOL_OK) {
    cil_log(CIL_ERR, "Invalid constraint syntax\n");
    goto exit;
  }

  return SEPOL_OK;

exit:
  return SEPOL_ERR;
}

int cil_verify_conditional_blocks(struct cil_tree_node *current)
{
  int found_true = CIL_FALSE;
  int found_false = CIL_FALSE;

  if (current->cl_head->data == CIL_KEY_CONDTRUE) {
    found_true = CIL_TRUE;
  } else if (current->cl_head->data == CIL_KEY_CONDFALSE) {
    found_false = CIL_TRUE;
  } else {
    cil_tree_log(current, CIL_ERR, "Expected true or false block in conditional");
    return SEPOL_ERR;
  }

  current = current->next;
  if (current != NULL) {
    if (current->cl_head->data == CIL_KEY_CONDTRUE) {
      if (found_true) {
        cil_tree_log(current, CIL_ERR, "More than one true block in conditional");
        return SEPOL_ERR;
      }
    } else if (current->cl_head->data == CIL_KEY_CONDFALSE) {
      if (found_false) {
        cil_tree_log(current, CIL_ERR, "More than one false block in conditional");
        return SEPOL_ERR;
      }
    } else {
      cil_tree_log(current, CIL_ERR, "Expected true or false block in conditional");
      return SEPOL_ERR;
    }
  }

  return SEPOL_OK;
}

int cil_verify_decl_does_not_shadow_macro_parameter(struct cil_macro *macro, struct cil_tree_node *node, const char *name)
{
  struct cil_list_item *item;
  struct cil_list *param_list = macro->params;
  if (param_list != NULL) {
    cil_list_for_each(item, param_list) {
      struct cil_param *param = item->data;
      if (param->str == name) {
        if (param->flavor == node->flavor) {
          cil_log(CIL_ERR, "Declaration of %s %s shadows a macro parameter with the same flavor\n", cil_node_to_string(node), name);
          return SEPOL_ERR;
        } else {
          cil_log(CIL_WARN, "Declaration of %s %s has same name as a macro parameter with a different flavor\n", cil_node_to_string(node), name);
        }
      }
    }
  }
  return SEPOL_OK;
}

static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack);

static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_stack *stack)
{
  struct cil_list_item *item;
  int rc = SEPOL_OK;

  if (!expr) {
    return SEPOL_OK;
  }

  cil_list_for_each(item, expr) {
    if (item->flavor == CIL_DATUM) {
      struct cil_symtab_datum* datum = item->data;
      rc = cil_verify_no_self_reference(FLAVOR(datum), datum, stack);
    } else if (item->flavor == CIL_LIST) {
      rc = __verify_no_self_reference_in_expr(item->data, stack);
    }
    if (rc != SEPOL_OK) {
      return SEPOL_ERR;
    }
  }

  return SEPOL_OK;
}

static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack)
{
  struct cil_stack_item *item;
  int i = 0;
  int rc = SEPOL_OK;

  cil_stack_for_each(stack, i, item) {
    struct cil_symtab_datum *prev = item->data;
    if (datum == prev) {
      cil_tree_log(NODE(datum), CIL_ERR, "Self-reference found for %s", datum->name);
      return SEPOL_ERR;
    }
  }

  switch (flavor) {
  case CIL_USERATTRIBUTE: {
    struct cil_userattribute *attr = (struct cil_userattribute *)datum;
    cil_stack_push(stack, CIL_DATUM, datum);
    rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
    cil_stack_pop(stack);
    break;
  }
  case CIL_ROLEATTRIBUTE: {
    struct cil_roleattribute *attr = (struct cil_roleattribute *)datum;
    cil_stack_push(stack, CIL_DATUM, datum);
    rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
    cil_stack_pop(stack);
    break;
  }
  case CIL_TYPEATTRIBUTE: {
    struct cil_typeattribute *attr = (struct cil_typeattribute *)datum;
    cil_stack_push(stack, CIL_DATUM, datum);
    rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
    cil_stack_pop(stack);
    break;
  }
  case CIL_CATSET: {
    struct cil_catset *set = (struct cil_catset *)datum;
    cil_stack_push(stack, CIL_DATUM, datum);
    rc = __verify_no_self_reference_in_expr(set->cats->datum_expr, stack);
    cil_stack_pop(stack);
    break;
  }
  default:
    break;
  }

  return rc;
}

int __cil_verify_ranges(struct cil_list *list)
{
  int rc = SEPOL_ERR;
  struct cil_list_item *curr;
  struct cil_list_item *range = NULL;

  if (list == NULL || list->head == NULL) {
    goto exit;
  }

  cil_list_for_each(curr, list) {
    /* range */
    if (curr->flavor == CIL_LIST) {
      range = ((struct cil_list*)curr->data)->head;
      if (range == NULL || range->next == NULL || range->next->next != NULL) {
        goto exit;
      }
    }
  }

  return SEPOL_OK;

exit:
  cil_log(CIL_ERR,"Invalid Range syntax\n");
  return rc;
}

int cil_verify_completed_ordered_list(struct cil_list *complete, struct cil_list *ordered_lists)
{
  struct cil_list_item *cprev, *ccurr, *cnext;
  int found_prev, found_next;
  int rc = SEPOL_OK;

  found_prev = CIL_FALSE;
  found_next = CIL_FALSE;
  cprev = NULL;
  ccurr = complete->head;
  cnext = ccurr ? ccurr->next : NULL;
  while (ccurr) {
    struct cil_tree_node *node;
    struct cil_ordered *ordered;
    struct cil_list_item *curr_list, *oprev, *ocurr, *onext;
    int change = CIL_FALSE;
    cil_list_for_each(curr_list, ordered_lists) {
      node = curr_list->data;
      ordered = node->data;
      oprev = NULL;
      cil_list_for_each(ocurr, ordered->datums) {
        onext = ocurr ? ocurr->next : NULL;
        if (ccurr->data == ocurr->data) {
          if (found_prev == CIL_FALSE && ((!cprev && !oprev) ||
            (cprev && oprev && cprev->data == oprev->data))) {
            found_prev = CIL_TRUE;
            change = CIL_TRUE;
          }
          if (found_next == CIL_FALSE && ((!cnext && !onext) ||
            (cnext && onext && cnext->data == onext->data))) {
            found_next = CIL_TRUE;
            change = CIL_TRUE;
          }
          if (found_prev && found_next) {
            cprev = ccurr;
            ccurr = cnext;
            cnext = ccurr ? ccurr->next : NULL;
            found_prev = CIL_FALSE;
            found_next = CIL_FALSE;
            if (!ccurr) {
              /* Went through the whole list */
              return rc;
            }
          }
        }
        oprev = ocurr;
      }
    }
    if (!change) {
      rc = SEPOL_ERR;
      cil_log(CIL_ERR, "Unable to verify the order of %s\n", DATUM(ccurr->data)->fqn);
      cil_log(CIL_ERR, "Found in the following ordering rules:\n");
      cil_list_for_each(curr_list, ordered_lists) {
        node = curr_list->data;
        ordered = node->data;
        cil_list_for_each(ocurr, ordered->datums) {
          if (ccurr->data == ocurr->data) {
            cil_tree_log(node, CIL_ERR, "    ");
          }
        }
      }
      cprev = ccurr;
      ccurr = cnext;
      cnext = ccurr ? ccurr->next : NULL;
      found_prev = CIL_FALSE;
      found_next = CIL_FALSE;
    }
  }

  return rc;
}

struct cil_args_verify_order {
  uint32_t *flavor;
};

int __cil_verify_ordered_node_helper(struct cil_tree_node *node, __attribute__((unused)) uint32_t *finished, void *extra_args)
{
  struct cil_args_verify_order *args = extra_args;
  uint32_t *flavor = args->flavor;

  if (node->flavor == *flavor) {
    if (node->flavor == CIL_SID) {
      struct cil_sid *sid = node->data;
      if (sid->ordered == CIL_FALSE) {
        cil_tree_log(node, CIL_ERR, "SID %s not in sidorder statement", sid->datum.name);
        return SEPOL_ERR;
      }
    } else if (node->flavor == CIL_CLASS) {
      struct cil_class *class = node->data;
      if (class->ordered == CIL_FALSE) {
        cil_tree_log(node, CIL_ERR, "Class %s not in classorder statement", class->datum.name);
        return SEPOL_ERR;
      }
    } else if (node->flavor == CIL_CAT) {
      struct cil_cat *cat = node->data;
      if (cat->ordered == CIL_FALSE) {
        cil_tree_log(node, CIL_ERR, "Category %s not in categoryorder statement", cat->datum.name);
        return SEPOL_ERR;
      }
    } else if (node->flavor == CIL_SENS) {
      struct cil_sens *sens = node->data;
      if (sens->ordered == CIL_FALSE) {
        cil_tree_log(node, CIL_ERR, "Sensitivity %s not in sensitivityorder statement", sens->datum.name);
        return SEPOL_ERR;
      }
    }
  }

  return SEPOL_OK;
}

int __cil_verify_ordered(struct cil_tree_node *current, enum cil_flavor flavor)
{
  struct cil_args_verify_order extra_args;
  int rc = SEPOL_ERR;

  extra_args.flavor = &flavor;

  rc = cil_tree_walk(current, __cil_verify_ordered_node_helper, NULL, NULL, &extra_args);

  return rc;
}

int __cil_verify_initsids(struct cil_list *sids)
{
  int rc = SEPOL_OK;
  struct cil_list_item *i;

  if (sids->head == NULL) {
    cil_log(CIL_ERR, "At least one initial sid must be defined in the policy\n");
    return SEPOL_ERR;
  }

  cil_list_for_each(i, sids) {
    struct cil_sid *sid = i->data;
    if (sid->context == NULL) {
      struct cil_tree_node *node = sid->datum.nodes->head->data;
      cil_tree_log(node, CIL_INFO, "No context assigned to SID %s, omitting from policy",sid->datum.name);
    }
  }

  return rc;
}

static int __cil_is_cat_in_cats(struct cil_cat *cat, struct cil_cats *cats)
{
  struct cil_list_item *i;

  cil_list_for_each(i, cats->datum_expr) {
    struct cil_cat *c = i->data;
    if (c == cat) {
      return CIL_TRUE;
    }
  }

  return CIL_FALSE;
}


static int __cil_verify_cat_in_cats(struct cil_cat *cat, struct cil_cats *cats)
{
  if (__cil_is_cat_in_cats(cat, cats) != CIL_TRUE) {
    cil_log(CIL_ERR, "Failed to find category %s in category list\n", cat->datum.name);
    return SEPOL_ERR;
  }

  return SEPOL_OK;
}

static int __cil_verify_cats_associated_with_sens(struct cil_sens *sens, struct cil_cats *cats)
{
  int rc = SEPOL_OK;
  struct cil_list_item *i, *j;

  if (!cats) {
    return SEPOL_OK;
  }

  if (!sens->cats_list) {
    cil_log(CIL_ERR, "No categories can be used with sensitivity %s\n", sens->datum.name);
    return SEPOL_ERR;
  }

  cil_list_for_each(i, cats->datum_expr) {
    struct cil_cat *cat = i->data;
    int ok = CIL_FALSE;
    cil_list_for_each(j, sens->cats_list) {
      if (__cil_is_cat_in_cats(cat, j->data) == CIL_TRUE) {
        ok = CIL_TRUE;
        break;
      }
    }

    if (ok != CIL_TRUE) {
      cil_log(CIL_ERR, "Category %s cannot be used with sensitivity %s\n", 
          cat->datum.name, sens->datum.name);
      rc = SEPOL_ERR;
    }
  }

  return rc;
}

static int __cil_verify_levelrange_sensitivity(struct cil_db *db, struct cil_sens *low, struct cil_sens *high)
{
  struct cil_list_item *curr;
  int found = CIL_FALSE;
  int rc = SEPOL_ERR;

  cil_list_for_each(curr, db->sensitivityorder) {
    if (curr->data == low) {
      found = CIL_TRUE;
    }

    if ((found == CIL_TRUE) && (curr->data == high)) {
      break;
    }
  }

  if (found != CIL_TRUE || curr == NULL) {
    goto exit;
  }

  return SEPOL_OK;

exit:
  cil_log(CIL_ERR, "Sensitivity %s does not dominate %s\n", 
    high->datum.name, low->datum.name);
  return rc;

}

static int __cil_verify_levelrange_cats(struct cil_cats *low, struct cil_cats *high)
{
  int rc = SEPOL_ERR;
  struct cil_list_item *item;

  if (low == NULL || (low == NULL && high == NULL)) {
    return SEPOL_OK;
  }

  if (high == NULL) {
    rc = SEPOL_ERR;
    goto exit;
  }

  cil_list_for_each(item, low->datum_expr) {
    rc = __cil_verify_cat_in_cats(item->data, high);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_log(CIL_ERR, "Low level category set must be a subset of the high level category set\n");
  return rc;
}

static int __cil_verify_levelrange(struct cil_db *db, struct cil_levelrange *lr)
{
  int rc = SEPOL_ERR;

  rc = __cil_verify_levelrange_sensitivity(db, lr->low->sens, lr->high->sens);
  if (rc != SEPOL_OK) {
    goto exit;
  }

  rc = __cil_verify_levelrange_cats(lr->low->cats, lr->high->cats);
  if (rc != SEPOL_OK) {
    goto exit;
  }

  rc = __cil_verify_cats_associated_with_sens(lr->low->sens, lr->low->cats);
  if (rc != SEPOL_OK) {
    cil_log(CIL_ERR, "Low level sensitivity and categories are not associated\n");
    goto exit;
  }

  rc = __cil_verify_cats_associated_with_sens(lr->high->sens, lr->high->cats);
  if (rc != SEPOL_OK) {
    cil_log(CIL_ERR, "High level sensitivity and categories are not associated\n");
    goto exit;
  }
  
  return SEPOL_OK;

exit:
  return rc;
}

static int __cil_verify_named_levelrange(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_levelrange *lr = node->data;

  rc = __cil_verify_levelrange(db, lr);
  if (rc != SEPOL_OK) {
    goto exit;
  }

  return SEPOL_OK;
exit:
  cil_tree_log(node, CIL_ERR, "Invalid named range");
  return rc;
}

static int __cil_verify_user_pre_eval(struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_user *user = node->data;

  if (user->dftlevel == NULL) {
    cil_log(CIL_ERR, "User %s does not have a default level\n", user->datum.name);
    goto exit;
  } else if (user->range == NULL) {
    cil_log(CIL_ERR, "User %s does not have a level range\n", user->datum.name);
    goto exit;
  } else if (user->bounds != NULL) {
    int steps = 0;
    int limit = 2;
    struct cil_user *u1 = user;
    struct cil_user *u2 = user->bounds;

    while (u2 != NULL) {
      if (u1 == u2) {
        cil_log(CIL_ERR, "Circular bounds found for user %s\n", u1->datum.name);
        goto exit;
      }

      if (steps == limit) {
        steps = 0;
        limit *= 2;
        u1 = u2;
      }

      u2 = u2->bounds;
      steps++;
    }
  }

  return SEPOL_OK;
exit:
  cil_tree_log(node, CIL_ERR, "Invalid user");
  return rc;
}

static int __cil_verify_user_post_eval(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_user *user = node->data;

  /* Verify user range only if anonymous */
  if (user->range->datum.name == NULL) {
    rc = __cil_verify_levelrange(db, user->range);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;
exit:
  cil_tree_log(node, CIL_ERR, "Invalid user");
  return rc;
}

static int __cil_verify_role(struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_role *role = node->data;
  int steps = 0;
  int limit = 2;
  struct cil_role *r1 = role;
  struct cil_role *r2 = role->bounds;

  while (r2 != NULL) {
    if (r1 == r2) {
      cil_log(CIL_ERR, "Circular bounds found for role %s\n", r1->datum.name);
      goto exit;
    }

    if (steps == limit) {
      steps = 0;
      limit *= 2;
      r1 = r2;
    }

    r2 = r2->bounds;
    steps++;
  }

  return SEPOL_OK;
exit:
  cil_tree_log(node, CIL_ERR, "Invalid role");
  return rc;
}

static int __cil_verify_type(struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_type *type = node->data;
  int steps = 0;
  int limit = 2;
  struct cil_type *t1 = type;
  struct cil_type *t2 = type->bounds;

  while (t2 != NULL) {
    if (t1 == t2) {
      cil_log(CIL_ERR, "Circular bounds found for type %s\n", t1->datum.name);
      goto exit;
    }

    if (steps == limit) {
      steps = 0;
      limit *= 2;
      t1 = t2;
    }

    t2 = t2->bounds;
    steps++;
  }

  return SEPOL_OK;
exit:
  cil_tree_log(node, CIL_ERR, "Invalid type");
  return rc;
}

static int __cil_verify_context(struct cil_db *db, struct cil_context *ctx)
{
  int rc = SEPOL_ERR;
  struct cil_user *user = ctx->user;
  struct cil_role *role = ctx->role;
  struct cil_type *type = ctx->type;
  struct cil_level *user_low = user->range->low;
  struct cil_level *user_high = user->range->high;
  struct cil_level *ctx_low = ctx->range->low;
  struct cil_level *ctx_high = ctx->range->high;
  struct cil_list *sensitivityorder = db->sensitivityorder;
  struct cil_list_item *curr;
  int found = CIL_FALSE;

  if (user->roles != NULL) {
    if (!ebitmap_get_bit(user->roles, role->value)) {
      cil_log(CIL_ERR, "Role %s is invalid for user %s\n", ctx->role_str, ctx->user_str);
      rc = SEPOL_ERR;
      goto exit;
    }
  } else {
    cil_log(CIL_ERR, "No roles given to the user %s\n", ctx->user_str);
    rc = SEPOL_ERR;
    goto exit;
  }

  if (role->types != NULL) {
    if (!ebitmap_get_bit(role->types, type->value)) {
      cil_log(CIL_ERR, "Type %s is invalid for role %s\n", ctx->type_str, ctx->role_str);
      rc = SEPOL_ERR;
      goto exit;
    }
  } else {
    cil_log(CIL_ERR, "No types associated with role %s\n", ctx->role_str);
    rc = SEPOL_ERR;
    goto exit;
  }

  /* Verify range only when anonymous */
  if (ctx->range->datum.name == NULL) {
    rc = __cil_verify_levelrange(db, ctx->range);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  for (curr = sensitivityorder->head; curr != NULL; curr = curr->next) {
    struct cil_sens *sens = curr->data;

    if (found == CIL_FALSE) {
      if (sens == user_low->sens) {
        found = CIL_TRUE;
      } else if (sens == ctx_low->sens) {
        cil_log(CIL_ERR, "Range %s is invalid for user %s\n", 
          ctx->range_str, ctx->user_str);
        rc = SEPOL_ERR;
        goto exit;
      }
    }

    if (found == CIL_TRUE) {
      if (sens == ctx_high->sens) {
        break;
      } else if (sens == user_high->sens) {
        cil_log(CIL_ERR, "Range %s is invalid for user %s\n", 
          ctx->range_str, ctx->user_str);
        rc = SEPOL_ERR;
        goto exit;
      }
    }
  }

  return SEPOL_OK;
exit:
  cil_log(CIL_ERR, "Invalid context\n");
  return rc;
}

static int __cil_verify_named_context(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_context *ctx = node->data;

  rc = __cil_verify_context(db, ctx);
  if (rc != SEPOL_OK) {
    goto exit;
  }

  return SEPOL_OK;
exit:
  cil_tree_log(node, CIL_ERR, "Invalid named context");
  return rc;
}

/*
static int __cil_verify_rule(struct cil_tree_node *node, struct cil_complex_symtab *symtab)
{

  int rc = SEPOL_ERR;
  struct cil_type_rule *typerule = NULL;
  struct cil_roletransition *roletrans = NULL;
  struct cil_complex_symtab_key ckey;

  switch (node->flavor) {
  case CIL_ROLETRANSITION: {
    roletrans = node->data;
    ckey.key1 = (intptr_t)roletrans->src;
    ckey.key2 = (intptr_t)roletrans->tgt;
    ckey.key3 = (intptr_t)roletrans->obj;
    ckey.key4 = CIL_ROLETRANSITION;
    break;
  }
  case CIL_TYPE_RULE: {
    typerule = node->data;
    ckey.key1 = (intptr_t)typerule->src;
    ckey.key2 = (intptr_t)typerule->tgt;
    ckey.key3 = (intptr_t)typerule->obj;
    ckey.key4 = (intptr_t)typerule->rule_kind;
    break;
  }
  default:
    break;
  }


  rc = cil_complex_symtab_insert(symtab, &ckey, NULL);
  if (rc == SEPOL_EEXIST) {
    struct cil_complex_symtab_datum *datum = NULL;
    cil_complex_symtab_search(symtab, &ckey, &datum);
    if (datum == NULL) {
      cil_tree_log(node, CIL_ERR, "Duplicate rule defined");
      rc = SEPOL_ERR;
      goto exit;
    }
  }

  return SEPOL_OK;
exit:
  cil_tree_log(node, CIL_ERR, "Invalid rule");
  return rc;
}
*/

static int __cil_verify_booleanif_helper(struct cil_tree_node *node, __attribute__((unused)) uint32_t *finished, __attribute__((unused)) void *extra_args)
{
  int rc = SEPOL_ERR;
  struct cil_tree_node *rule_node = node;
  struct cil_booleanif *bif = node->parent->parent->data;

  switch (rule_node->flavor) {
  case CIL_AVRULE:
  case CIL_AVRULEX: {
    struct cil_avrule *avrule = NULL;
    avrule = rule_node->data;
    if (avrule->rule_kind == CIL_AVRULE_NEVERALLOW) {
      if (bif->preserved_tunable) {
        cil_tree_log(node, CIL_ERR, "Neverallow found in tunableif block (treated as a booleanif due to preserve-tunables)");
      } else {
        cil_tree_log(node, CIL_ERR, "Neverallow found in booleanif block");
      }
      rc = SEPOL_ERR;
      goto exit;
    }
    break;
  }
  case CIL_DENY_RULE:
    if (bif->preserved_tunable) {
      cil_tree_log(node, CIL_ERR, "Not allowed to have a deny rule in a tunableif block (treated as a booleanif due to preserve-tunables)");
    } else {
      cil_tree_log(node, CIL_ERR, "Not allowed to have deny rule in a booleanif block");
    }
    rc = SEPOL_ERR;
    goto exit;
    break;
  case CIL_TYPE_RULE: /*
  struct cil_type_rule *typerule = NULL;
  struct cil_tree_node *temp_node = NULL;
  struct cil_complex_symtab *symtab = extra_args;
  struct cil_complex_symtab_key ckey;
  struct cil_complex_symtab_datum datum;
    typerule = rule_node->data;

    ckey.key1 = (intptr_t)typerule->src;
    ckey.key2 = (intptr_t)typerule->tgt;
    ckey.key3 = (intptr_t)typerule->obj;
    ckey.key4 = (intptr_t)typerule->rule_kind;

    datum.data = node;

    rc = cil_complex_symtab_insert(symtab, &ckey, &datum);
    if (rc != SEPOL_OK) {
      goto exit;
    }

    for (temp_node = rule_node->next;
      temp_node != NULL;
      temp_node = temp_node->next) {

      if (temp_node->flavor == CIL_TYPE_RULE) {
        typerule = temp_node->data;
        if ((intptr_t)typerule->src == ckey.key1 &&
          (intptr_t)typerule->tgt == ckey.key2 &&
          (intptr_t)typerule->obj == ckey.key3 &&
          (intptr_t)typerule->rule_kind == ckey.key4) {
          cil_log(CIL_ERR, "Duplicate type rule found (line: %d)\n", node->line);
          rc = SEPOL_ERR;
          goto exit;
        }
      }
    }
    break;*/

    //TODO Fix duplicate type_rule detection
    break;
  case CIL_CALL:
    //Fall through to check content of call
    break;
  case CIL_TUNABLEIF:
    //Fall through
    break;
  case CIL_NAMETYPETRANSITION:
    /* While type transitions with file component are not allowed in
       booleanif statements if they don't have "*" as the file. We
       can't check that here. Or at least we won't right now. */
    break;
  case CIL_SRC_INFO:
    //Fall through
    break;
  default: {
    const char * flavor = cil_node_to_string(node);
    if (bif->preserved_tunable) {
      cil_tree_log(node, CIL_ERR, "Invalid %s statement in tunableif (treated as a booleanif due to preserve-tunables)", flavor);
    } else {
      cil_tree_log(node, CIL_ERR, "Invalid %s statement in booleanif", flavor);
    }
    goto exit;
  }
  }

  rc = SEPOL_OK;
exit:
  return rc;
}

static int __cil_verify_booleanif(struct cil_tree_node *node, struct cil_complex_symtab *symtab)
{
  int rc = SEPOL_ERR;
  struct cil_booleanif *bif = (struct cil_booleanif*)node->data;
  struct cil_tree_node *cond_block = node->cl_head;

  while (cond_block != NULL) {
    rc = cil_tree_walk(cond_block, __cil_verify_booleanif_helper, NULL, NULL, symtab);
    if (rc != SEPOL_OK) {
      goto exit;
    }
    cond_block = cond_block->next;
  }

  return SEPOL_OK;
exit:
  if (bif->preserved_tunable) {
    cil_tree_log(node, CIL_ERR, "Invalid tunableif (treated as a booleanif due to preserve-tunables)");
  } else {
    cil_tree_log(node, CIL_ERR, "Invalid booleanif");
  }
  return rc;
}

static int __cil_verify_netifcon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_netifcon *netif = node->data;
  struct cil_context *if_ctx = netif->if_context;
  struct cil_context *pkt_ctx = netif->packet_context;

  /* Verify only when anonymous */
  if (if_ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, if_ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  /* Verify only when anonymous */
  if (pkt_ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, pkt_ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  if (strcmp(netif->interface_str, "?") == 0 ||
      strcmp(netif->interface_str, "*") == 0) {
    goto exit;
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid netifcon");
  return rc;
}

static int __cil_verify_ibendportcon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_ibendportcon *ib_end_port = node->data;
  struct cil_context *ctx = ib_end_port->context;

  /* Verify only when anonymous */
  if (!ctx->datum.name) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK)
      goto exit;
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid ibendportcon");
  return rc;
}

static int __cil_verify_genfscon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_genfscon *genfs = node->data;
  struct cil_context *ctx = genfs->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid genfscon");
  return rc;
}

static int __cil_verify_filecon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_filecon *file = node->data;
  struct cil_context *ctx = file->context;

  if (ctx == NULL) {
    rc = SEPOL_OK;
    goto exit;
  }

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      cil_tree_log(node, CIL_ERR, "Invalid filecon");
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  return rc;
}

static int __cil_verify_nodecon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_nodecon *nodecon = node->data;
  struct cil_context *ctx = nodecon->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid nodecon");
  return rc;
}

static int __cil_verify_ibpkeycon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_ibpkeycon *pkey = node->data;
  struct cil_context *ctx = pkey->context;

  /* Verify only when anonymous */
  if (!ctx->datum.name) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK)
      goto exit;
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid ibpkeycon");
  return rc;
}

static int __cil_verify_portcon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_portcon *port = node->data;
  struct cil_context *ctx = port->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid portcon");
  return rc;
}

static int __cil_verify_pirqcon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_pirqcon *pirq = node->data;
  struct cil_context *ctx = pirq->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid pirqcon");
  return rc;
}

static int __cil_verify_iomemcon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_iomemcon *iomem = node->data;
  struct cil_context *ctx = iomem->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid iomemcon");
  return rc;
}

static int __cil_verify_ioportcon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_ioportcon *ioport = node->data;
  struct cil_context *ctx = ioport->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid ioportcon");
  return rc;
}

static int __cil_verify_pcidevicecon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_pcidevicecon *pcidev = node->data;
  struct cil_context *ctx = pcidev->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid pcidevicecon");
  return rc;
}

static int __cil_verify_devicetreecon(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_devicetreecon *dt = node->data;
  struct cil_context *ctx = dt->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid devicetreecon");
  return rc;
}

static int __cil_verify_fsuse(struct cil_db *db, struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_fsuse *fsuse = node->data;
  struct cil_context *ctx = fsuse->context;

  /* Verify only when anonymous */
  if (ctx->datum.name == NULL) {
    rc = __cil_verify_context(db, ctx);
    if (rc != SEPOL_OK) {
      goto exit;
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid fsuse");
  return rc;
}

static int __cil_verify_permissionx(struct cil_permissionx *permx, struct cil_tree_node *node)
{
  int rc;
  struct cil_list *classes = NULL;
  struct cil_list_item *item;
  struct cil_class *class;
  struct cil_symtab_datum *perm_datum;
  char *kind_str;

  switch (permx->kind) {
    case CIL_PERMX_KIND_IOCTL:
      kind_str = CIL_KEY_IOCTL;
      break;
    case CIL_PERMX_KIND_NLMSG:
      kind_str = CIL_KEY_NLMSG;
      break;
    default:
      cil_tree_log(node, CIL_ERR, "Invalid permissionx kind (%d)", permx->kind);
      rc = SEPOL_ERR;
      goto exit;
  }

  classes = cil_expand_class(permx->obj);

  cil_list_for_each(item, classes) {
    class = item->data;
    rc = cil_symtab_get_datum(&class->perms, kind_str, &perm_datum);
    if (rc == SEPOL_ENOENT) {
      if (class->common != NULL) {
        rc = cil_symtab_get_datum(&class->common->perms, kind_str, &perm_datum);
      }

      if (rc == SEPOL_ENOENT) {
        cil_tree_log(node, CIL_ERR, "Invalid permissionx: %s is not a permission of class %s", kind_str, class->datum.name);
        rc = SEPOL_ERR;
        goto exit;
      }
    }
  }

  rc = SEPOL_OK;

exit:
  if (classes != NULL) {
    cil_list_destroy(&classes, CIL_FALSE);
  }

  return rc;
}

static int __cil_verify_avrulex(struct cil_tree_node *node)
{
  struct cil_avrule *avrulex = node->data;
  return __cil_verify_permissionx(avrulex->perms.x.permx, node);
}

static int __cil_verify_class(struct cil_tree_node *node)
{
  int rc = SEPOL_ERR;
  struct cil_class *class = node->data;

  if (class->common != NULL) {
    struct cil_class *common = class->common;
    struct cil_tree_node *common_node = common->datum.nodes->head->data;
    struct cil_tree_node *curr_com_perm = NULL;

    for (curr_com_perm = common_node->cl_head;
      curr_com_perm != NULL;
      curr_com_perm = curr_com_perm->next) {
      struct cil_perm *com_perm = curr_com_perm->data;
      struct cil_tree_node *curr_class_perm = NULL;

      for (curr_class_perm = node->cl_head;
        curr_class_perm != NULL;
        curr_class_perm = curr_class_perm->next) {
        struct cil_perm *class_perm = curr_class_perm->data;

        if (com_perm->datum.name == class_perm->datum.name) {
          cil_log(CIL_ERR, "Duplicate permissions between %s common and class declarations\n", class_perm->datum.name);
          goto exit;
        }
      }
    }
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid class");
  return rc;
}

static int __cil_verify_policycap(struct cil_tree_node *node)
{
  int rc;
  struct cil_policycap *polcap = node->data;

  rc = sepol_polcap_getnum((const char*)polcap->datum.name);
  if (rc == SEPOL_ERR) {
    goto exit;
  }

  return SEPOL_OK;

exit:
  cil_tree_log(node, CIL_ERR, "Invalid policycap (%s)", (const char*)polcap->datum.name);
  return rc;
}

int __cil_verify_helper(struct cil_tree_node *node, uint32_t *finished, void *extra_args)
{
  int rc = SEPOL_ERR;
  int *avrule_cnt = 0;
  int *handleunknown;
  int *mls;
  int *nseuserdflt = 0;
  int *pass = 0;
  struct cil_args_verify *args = extra_args;
  struct cil_complex_symtab *csymtab = NULL;
  struct cil_db *db = NULL;

  if (node == NULL || extra_args == NULL) {
    goto exit;
  }

  db = args->db;
  avrule_cnt = args->avrule_cnt;
  handleunknown = args->handleunknown;
  mls = args->mls;
  nseuserdflt = args->nseuserdflt;
  csymtab = args->csymtab;
  pass = args->pass;

  if (node->flavor == CIL_MACRO) {
    *finished = CIL_TREE_SKIP_HEAD;
    rc = SEPOL_OK;
    goto exit;
  } else if (node->flavor == CIL_BLOCK) {
    struct cil_block *blk = node->data;
    if (blk->is_abstract == CIL_TRUE) {
      *finished = CIL_TREE_SKIP_HEAD;
    }
    rc = SEPOL_OK;
    goto exit;
  }

  switch (*pass) {
  case 0: {
    switch (node->flavor) {
    case CIL_USER:
      rc = __cil_verify_user_post_eval(db, node);
      break;
    case CIL_SELINUXUSERDEFAULT:
      (*nseuserdflt)++;
      rc = SEPOL_OK;
      break;
    case CIL_ROLE:
      rc = __cil_verify_role(node);
      break;
    case CIL_TYPE:
      rc = __cil_verify_type(node);
      break;
    case CIL_AVRULE:
      (*avrule_cnt)++;
      rc = SEPOL_OK;
      break;
    case CIL_HANDLEUNKNOWN:
      if (*handleunknown != -1) {
        cil_log(CIL_ERR, "Policy can not have more than one handleunknown\n");
        rc = SEPOL_ERR;
      } else {
        *handleunknown = ((struct cil_handleunknown*)node->data)->handle_unknown;
        rc = SEPOL_OK;
      }
      break;
    case CIL_MLS:
      if (*mls != -1) {
        cil_log(CIL_ERR, "Policy can not have more than one mls\n");
        rc = SEPOL_ERR;
      } else {
        *mls = ((struct cil_mls*)node->data)->value;
        rc = SEPOL_OK;
      }
      break;
    case CIL_ROLETRANSITION:
      rc = SEPOL_OK; //TODO __cil_verify_rule doesn't work quite right
      //rc = __cil_verify_rule(node, csymtab);
      break;
    case CIL_TYPE_RULE:
      rc = SEPOL_OK; //TODO __cil_verify_rule doesn't work quite right
      //rc = __cil_verify_rule(node, csymtab);
      break;
    case CIL_BOOLEANIF:
      rc = __cil_verify_booleanif(node, csymtab);
      *finished = CIL_TREE_SKIP_HEAD;
      break;
    case CIL_LEVELRANGE:
      rc = __cil_verify_named_levelrange(db, node);
      break;
    case CIL_CLASS:
      rc = __cil_verify_class(node);
      break;
    case CIL_POLICYCAP:
      rc = __cil_verify_policycap(node);
      break;
    default:
      rc = SEPOL_OK;
      break;
    }
    break;
  }
  case 1: {
    switch (node->flavor) {
    case CIL_CONTEXT:
      rc = __cil_verify_named_context(db, node);
      break;
    case CIL_NETIFCON:
      rc = __cil_verify_netifcon(db, node);
      break;
    case CIL_GENFSCON:
      rc = __cil_verify_genfscon(db, node);
      break;
    case CIL_FILECON:
      rc = __cil_verify_filecon(db, node);
      break;
    case CIL_NODECON:
      rc = __cil_verify_nodecon(db, node);
      break;
    case CIL_IBPKEYCON:
      rc = __cil_verify_ibpkeycon(db, node);
      break;
    case CIL_IBENDPORTCON:
      rc = __cil_verify_ibendportcon(db, node);
      break;
    case CIL_PORTCON:
      rc = __cil_verify_portcon(db, node);
      break;
    case CIL_PIRQCON:
      rc = __cil_verify_pirqcon(db, node);
      break;
    case CIL_IOMEMCON:
      rc = __cil_verify_iomemcon(db, node);
      break;
    case CIL_IOPORTCON:
      rc = __cil_verify_ioportcon(db, node);
      break;
    case CIL_PCIDEVICECON:
      rc = __cil_verify_pcidevicecon(db, node);
      break;
    case CIL_DEVICETREECON:
      rc = __cil_verify_devicetreecon(db, node);
      break;
    case CIL_FSUSE:
      rc = __cil_verify_fsuse(db, node);
      break;
    case CIL_AVRULEX:
      rc = __cil_verify_avrulex(node);
      break;
    case CIL_PERMISSIONX:
      rc = __cil_verify_permissionx(node->data, node);
      break;
    case CIL_RANGETRANSITION:
      rc = SEPOL_OK;
      break;
    default:
      rc = SEPOL_OK;
      break;
    }
    break;
  }
  default:
    rc = SEPOL_ERR;
  }

exit:
  return rc;
}

static int __add_perm_to_list(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, void *args)
{
  struct cil_list *perm_list = (struct cil_list *)args;

  cil_list_append(perm_list, CIL_DATUM, d);

  return SEPOL_OK;
}

static int __cil_verify_classperms(struct cil_list *classperms, struct cil_symtab_datum *orig, struct cil_symtab_datum *cur, unsigned steps, unsigned limit);

static int __cil_verify_map_perm(struct cil_class *class, struct cil_perm *perm, struct cil_symtab_datum *orig, unsigned steps, unsigned limit)
{
  int rc;

  if (!perm->classperms) {
    cil_tree_log(NODE(class), CIL_ERR, "No class permissions for map class %s, permission %s", DATUM(class)->name, DATUM(perm)->name);
    goto exit;
  }

  rc = __cil_verify_classperms(perm->classperms, orig, &perm->datum, steps, limit);
  if (rc != SEPOL_OK) {
    cil_tree_log(NODE(class), CIL_ERR, "There was an error verifying class permissions for map class %s, permission %s", DATUM(class)->name, DATUM(perm)->name);
    goto exit;
  }

  return SEPOL_OK;

exit:
  return SEPOL_ERR;
}


static int __cil_verify_perms(struct cil_class *class, struct cil_list *perms, struct cil_symtab_datum *orig, unsigned steps, unsigned limit)
{
  int rc = SEPOL_ERR;
  int count = 0;
  struct cil_list_item *i = NULL;

  if (!perms) {
    cil_tree_log(NODE(class), CIL_ERR, "No permissions for class %s in class permissions", DATUM(class)->name);
    goto exit;
  }

  cil_list_for_each(i, perms) {
    count++;
    if (i->flavor == CIL_LIST) {
      rc = __cil_verify_perms(class, i->data, orig, steps, limit);
      if (rc != SEPOL_OK) {
        goto exit;
      }
    } else if (i->flavor == CIL_DATUM) {
      struct cil_perm *perm = i->data;
      if (FLAVOR(perm) == CIL_MAP_PERM) {
        rc = __cil_verify_map_perm(class, perm, orig, steps, limit);
        if (rc != SEPOL_OK) {
          goto exit;
        }
      }
    } else if (i->flavor == CIL_OP) {
      enum cil_flavor op = (enum cil_flavor)(uintptr_t)i->data;
      if (op == CIL_ALL) {
        struct cil_list *perm_list;
        struct cil_list_item *j = NULL;
        int count2 = 0;
        cil_list_init(&perm_list, CIL_MAP_PERM);
        cil_symtab_map(&class->perms, __add_perm_to_list, perm_list);
        if (class->common != NULL) {
          cil_symtab_map(&class->common->perms, __add_perm_to_list, perm_list);
        }
        cil_list_for_each(j, perm_list) {
          count2++;
          struct cil_perm *perm = j->data;
          if (FLAVOR(perm) == CIL_MAP_PERM) {
            rc = __cil_verify_map_perm(class, perm, orig, steps, limit);
            if (rc != SEPOL_OK) {
              cil_list_destroy(&perm_list, CIL_FALSE);
              goto exit;
            }
          }
        }
        cil_list_destroy(&perm_list, CIL_FALSE);
        if (count2 == 0) {
          cil_tree_log(NODE(class), CIL_ERR, "Operator \"all\" used for %s which has no permissions associated with it", DATUM(class)->name);
          goto exit;
        }
      }
    } else {
      cil_tree_log(NODE(class), CIL_ERR, "Permission list for %s has an unexpected flavor: %d", DATUM(class)->name, i->flavor);
      goto exit;
    }
  }

  if (count == 0) {
    cil_tree_log(NODE(class), CIL_ERR, "Empty permissions list for class %s in class permissions", DATUM(class)->name);
    goto exit;
  }

  return SEPOL_OK;

exit:
  return SEPOL_ERR;
}

static int __cil_verify_classperms(struct cil_list *classperms, struct cil_symtab_datum *orig, struct cil_symtab_datum *cur, unsigned steps, unsigned limit)
{
  int rc;
  struct cil_list_item *i;

  if (classperms == NULL) {
    goto exit;
  }

  if (steps > 0 && orig == cur) {
    cil_tree_log(NODE(cur), CIL_ERR, "Found circular class permissions involving %s", cur->name);
    goto exit;
  } else {
    steps++;
    if (steps > limit) {
      steps = 1;
      limit *= 2;
      orig = cur;
    }
  }

  cil_list_for_each(i, classperms) {
    if (i->flavor == CIL_CLASSPERMS) {
      struct cil_classperms *cp = i->data;
      rc = __cil_verify_perms(cp->class, cp->perms, orig, steps, limit);
      if (rc != SEPOL_OK) {
        goto exit;
      }
    } else { /* SET */
      struct cil_classperms_set *cp_set = i->data;
      struct cil_classpermission *cp = cp_set->set;
      if (!cp->classperms) {
        cil_tree_log(NODE(cur), CIL_ERR, "Classpermission %s does not have a classpermissionset", DATUM(cp)->name);
      }
      rc = __cil_verify_classperms(cp->classperms, orig, &cp->datum, steps, limit);
      if (rc != SEPOL_OK) {
        goto exit;
      }
    }
  }

  return SEPOL_OK;

exit:
  return SEPOL_ERR;
}

static int __cil_verify_classpermission(struct cil_tree_node *node)
{
  int rc;
  struct cil_classpermission *cp = node->data;

  rc = __cil_verify_classperms(cp->classperms, &cp->datum, &cp->datum, 0, 2);
  if (rc != SEPOL_OK) {
    cil_tree_log(node, CIL_ERR, "Error verifying class permissions for classpermission %s", DATUM(cp)->name);
  }

  return rc;
}

struct cil_verify_map_args {
  struct cil_class *class;
  struct cil_tree_node *node;
  int rc;
};

static int __verify_map_perm_classperms(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, void *args)
{
  struct cil_verify_map_args *map_args = args;
  struct cil_perm *cmp = (struct cil_perm *)d;
  int rc;

  rc = __cil_verify_classperms(cmp->classperms, &cmp->datum, &cmp->datum, 0, 2);
  if (rc != SEPOL_OK) {
    cil_tree_log(NODE(cmp), CIL_ERR, "Error verifying class permissions for map class %s, permission %s", DATUM(map_args->class)->name, DATUM(cmp)->name);
    map_args->rc = rc;
  }

  return SEPOL_OK;
}

static int __cil_verify_map_class(struct cil_tree_node *node)
{
  struct cil_class *mc = node->data;
  struct cil_verify_map_args map_args;

  map_args.class = mc;
  map_args.node = node;
  map_args.rc = SEPOL_OK;

  cil_symtab_map(&mc->perms, __verify_map_perm_classperms, &map_args);

  if (map_args.rc != SEPOL_OK) {
    return SEPOL_ERR;
  }

  return SEPOL_OK;
}

int __cil_pre_verify_helper(struct cil_tree_node *node, uint32_t *finished, __attribute__((unused)) void *extra_args)
{
  int rc = SEPOL_OK;

  switch (node->flavor) {
  case CIL_MACRO: {
    *finished = CIL_TREE_SKIP_HEAD;
    break;
  }
  case CIL_BLOCK: {
    struct cil_block *blk = node->data;
    if (blk->is_abstract == CIL_TRUE) {
      *finished = CIL_TREE_SKIP_HEAD;
    }
    break;
  }
  case CIL_USER:
    rc = __cil_verify_user_pre_eval(node);
    break;
  case CIL_MAP_CLASS:
    rc = __cil_verify_map_class(node);
    break;
  case CIL_CLASSPERMISSION:
    rc = __cil_verify_classpermission(node);
    break;
  case CIL_USERATTRIBUTE:
  case CIL_ROLEATTRIBUTE:
  case CIL_TYPEATTRIBUTE:
  case CIL_CATSET: {
    struct cil_stack *stack;
    cil_stack_init(&stack);
    rc = cil_verify_no_self_reference(node->flavor, node->data, stack);
    cil_stack_destroy(&stack);
    break;
  }
  default:
    rc = SEPOL_OK;
    break;
  }

  return rc;
}

Coverage Report

Created: 2026-05-30 06:31