[PATCH 0/9 v3] Add CIL Deny Rule

[PATCH 0/9 v3] Add CIL Deny Rule

[James Carter]

This patch series depends on the "Add support for notself and other to
CIL" patch series from April 12th.

These patches add a deny rule to CIL. Deny rules will be processed after
everything except for neverallow rules. Unlike neverallow rules, they
remove the permissions in the deny rule rather than reporting an error.

See the individual patches for an explanation of what they do.

Patches 2, 5, 6, and 7 are unchanged from v2. For the other patches, see
the patch for a list of the changes from v2.

James Carter (9):
  libsepol/cil: Parse and add deny rule to AST, but do not process
  libsepol/cil: Add cil_list_is_empty macro
  libsepol/cil: Add cil_tree_node_remove function
  libsepol/cil: Process deny rules
  libsepol/cil: Add cil_write_post_ast function
  libsepol: Export the cil_write_post_ast function
  secilc/secil2tree: Add option to write CIL AST after post processing
  secilc/test: Add deny rule tests
  secilc/docs: Add deny rule to CIL documentation

 libsepol/cil/include/cil/cil.h         |    1 +
 libsepol/cil/src/cil.c                 |   68 ++
 libsepol/cil/src/cil_build_ast.c       |   56 +
 libsepol/cil/src/cil_build_ast.h       |    2 +
 libsepol/cil/src/cil_copy_ast.c        |   19 +
 libsepol/cil/src/cil_copy_ast.h        |    1 +
 libsepol/cil/src/cil_deny.c            | 1413 ++++++++++++++++++++++++
 libsepol/cil/src/cil_deny.h            |   36 +
 libsepol/cil/src/cil_flavor.h          |    1 +
 libsepol/cil/src/cil_internal.h        |   10 +
 libsepol/cil/src/cil_list.h            |    3 +
 libsepol/cil/src/cil_post.c            |    7 +
 libsepol/cil/src/cil_reset_ast.c       |    8 +
 libsepol/cil/src/cil_resolve_ast.c     |   48 +
 libsepol/cil/src/cil_resolve_ast.h     |    1 +
 libsepol/cil/src/cil_tree.c            |   35 +
 libsepol/cil/src/cil_tree.h            |    1 +
 libsepol/cil/src/cil_verify.c          |    9 +
 libsepol/cil/src/cil_write_ast.c       |   10 +
 libsepol/cil/src/cil_write_ast.h       |    1 +
 libsepol/src/libsepol.map.in           |    5 +
 secilc/docs/cil_access_vector_rules.md |   67 ++
 secilc/secil2tree.c                    |    8 +-
 secilc/test/deny_rule_test1.cil        |  580 ++++++++++
 secilc/test/deny_rule_test2.cil        |  418 +++++++
 25 files changed, 2807 insertions(+), 1 deletion(-)
 create mode 100644 libsepol/cil/src/cil_deny.c
 create mode 100644 libsepol/cil/src/cil_deny.h
 create mode 100644 secilc/test/deny_rule_test1.cil
 create mode 100644 secilc/test/deny_rule_test2.cil

-- 
2.39.2

[PATCH 1/9 v3] libsepol/cil: Parse and add deny rule to AST, but do not process

[James Carter]

Adds the ability to parse a deny rule, add it to the AST, and
write it out when writing the AST, but the deny rule is otherwise
ignored and does nothing.

When it is fully supported, the deny rule will work like a neverallow
except that it will remove permissions rather than give an error.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
v3: Allow notself and other keywords when resolving deny rule

 libsepol/cil/src/cil.c             | 18 ++++++++++
 libsepol/cil/src/cil_build_ast.c   | 56 ++++++++++++++++++++++++++++++
 libsepol/cil/src/cil_build_ast.h   |  2 ++
 libsepol/cil/src/cil_copy_ast.c    | 19 ++++++++++
 libsepol/cil/src/cil_copy_ast.h    |  1 +
 libsepol/cil/src/cil_flavor.h      |  1 +
 libsepol/cil/src/cil_internal.h    | 10 ++++++
 libsepol/cil/src/cil_reset_ast.c   |  8 +++++
 libsepol/cil/src/cil_resolve_ast.c | 48 +++++++++++++++++++++++++
 libsepol/cil/src/cil_resolve_ast.h |  1 +
 libsepol/cil/src/cil_verify.c      |  9 +++++
 libsepol/cil/src/cil_write_ast.c   | 10 ++++++
 12 files changed, 183 insertions(+)

diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c
index ed97ff44..4876752a 100644
--- a/libsepol/cil/src/cil.c
+++ b/libsepol/cil/src/cil.c
@@ -227,6 +227,7 @@ char *CIL_KEY_SRC_CIL;
 char *CIL_KEY_SRC_HLL_LMS;
 char *CIL_KEY_SRC_HLL_LMX;
 char *CIL_KEY_SRC_HLL_LME;
+char *CIL_KEY_DENY_RULE;
 
 static void cil_init_keys(void)
 {
@@ -398,6 +399,7 @@ static void cil_init_keys(void)
 	CIL_KEY_SRC_HLL_LMS = cil_strpool_add("lms");
 	CIL_KEY_SRC_HLL_LMX = cil_strpool_add("lmx");
 	CIL_KEY_SRC_HLL_LME = cil_strpool_add("lme");
+	CIL_KEY_DENY_RULE = cil_strpool_add("deny");
 }
 
 void cil_db_init(struct cil_db **db)
@@ -927,6 +929,9 @@ void cil_destroy_data(void **data, enum cil_flavor flavor)
 	case CIL_PERMISSIONX:
 		cil_destroy_permissionx(*data);
 		break;
+	case CIL_DENY_RULE:
+		cil_destroy_deny_rule(*data);
+		break;
 	case CIL_ROLETRANSITION:
 		cil_destroy_roletransition(*data);
 		break;
@@ -1303,6 +1308,8 @@ const char * cil_node_to_string(struct cil_tree_node *node)
 		break;
 	case CIL_PERMISSIONX:
 		return CIL_KEY_PERMISSIONX;
+	case CIL_DENY_RULE:
+		return CIL_KEY_DENY_RULE;
 	case CIL_ROLETRANSITION:
 		return CIL_KEY_ROLETRANSITION;
 	case CIL_TYPE_RULE:
@@ -2482,6 +2489,17 @@ void cil_permissionx_init(struct cil_permissionx **permx)
 	(*permx)->perms = NULL;
 }
 
+void cil_deny_rule_init(struct cil_deny_rule **rule)
+{
+	*rule = cil_malloc(sizeof(**rule));
+
+	(*rule)->src_str = NULL;
+	(*rule)->src = NULL;
+	(*rule)->tgt_str = NULL;
+	(*rule)->tgt = NULL;
+	(*rule)->classperms = NULL;
+}
+
 void cil_type_rule_init(struct cil_type_rule **type_rule)
 {
 	*type_rule = cil_malloc(sizeof(**type_rule));
diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
index ca9f80c7..8976c254 100644
--- a/libsepol/cil/src/cil_build_ast.c
+++ b/libsepol/cil/src/cil_build_ast.c
@@ -2289,6 +2289,60 @@ exit:
 	return rc;
 }
 
+int cil_gen_deny_rule(struct cil_tree_node *parse_current, struct cil_tree_node *ast_node)
+{
+	enum cil_syntax syntax[] = {
+		CIL_SYN_STRING,
+		CIL_SYN_STRING,
+		CIL_SYN_STRING,
+		CIL_SYN_STRING | CIL_SYN_LIST,
+		CIL_SYN_END
+	};
+	size_t syntax_len = sizeof(syntax)/sizeof(*syntax);
+	struct cil_deny_rule *rule = NULL;
+	int rc = SEPOL_ERR;
+
+	if (parse_current == NULL || ast_node == NULL) {
+		goto exit;
+	}
+
+	rc = __cil_verify_syntax(parse_current, syntax, syntax_len);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	cil_deny_rule_init(&rule);
+
+	rule->src_str = parse_current->next->data;
+	rule->tgt_str = parse_current->next->next->data;
+
+	rc = cil_fill_classperms_list(parse_current->next->next->next, &rule->classperms);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	ast_node->data = rule;
+	ast_node->flavor = CIL_DENY_RULE;
+
+	return SEPOL_OK;
+
+exit:
+	cil_tree_log(parse_current, CIL_ERR, "Bad deny rule");
+	cil_destroy_deny_rule(rule);
+	return rc;
+}
+
+void cil_destroy_deny_rule(struct cil_deny_rule *rule)
+{
+	if (rule == NULL) {
+		return;
+	}
+
+	cil_destroy_classperms_list(&rule->classperms);
+
+	free(rule);
+}
+
 int cil_gen_type_rule(struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, uint32_t rule_kind)
 {
 	enum cil_syntax syntax[] = {
@@ -6369,6 +6423,8 @@ static struct cil_tree_node * parse_statement(struct cil_db *db, struct cil_tree
 		rc = cil_gen_avrulex(parse_current, new_ast_node, CIL_AVRULE_NEVERALLOW);
 	} else if (parse_current->data == CIL_KEY_PERMISSIONX) {
 		rc = cil_gen_permissionx(db, parse_current, new_ast_node);
+	} else if (parse_current->data == CIL_KEY_DENY_RULE) {
+		rc = cil_gen_deny_rule(parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_TYPETRANSITION) {
 		rc = cil_gen_typetransition(db, parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_TYPECHANGE) {
diff --git a/libsepol/cil/src/cil_build_ast.h b/libsepol/cil/src/cil_build_ast.h
index fd9053ce..aca84b24 100644
--- a/libsepol/cil/src/cil_build_ast.h
+++ b/libsepol/cil/src/cil_build_ast.h
@@ -116,6 +116,8 @@ void cil_destroy_avrule(struct cil_avrule *rule);
 int cil_gen_avrulex(struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, uint32_t rule_kind);
 int cil_gen_permissionx(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
 void cil_destroy_permissionx(struct cil_permissionx *permx);
+int cil_gen_deny_rule(struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
+void cil_destroy_deny_rule(struct cil_deny_rule *rule);
 int cil_gen_type_rule(struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, uint32_t rule_kind);
 void cil_destroy_type_rule(struct cil_type_rule *rule);
 int cil_gen_type(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
diff --git a/libsepol/cil/src/cil_copy_ast.c b/libsepol/cil/src/cil_copy_ast.c
index 17f05021..bc972f03 100644
--- a/libsepol/cil/src/cil_copy_ast.c
+++ b/libsepol/cil/src/cil_copy_ast.c
@@ -854,6 +854,22 @@ static int cil_copy_permissionx(struct cil_db *db, void *data, void **copy, symt
 	return SEPOL_OK;
 }
 
+int cil_copy_deny_rule(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab)
+{
+	struct cil_deny_rule *orig = data;
+	struct cil_deny_rule *new = NULL;
+
+	cil_deny_rule_init(&new);
+
+	new->src_str = orig->src_str;
+	new->tgt_str = orig->tgt_str;
+	cil_copy_classperms_list(orig->classperms, &new->classperms);
+
+	*copy = new;
+
+	return SEPOL_OK;
+}
+
 int cil_copy_type_rule(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab)
 {
 	struct cil_type_rule  *orig = data;
@@ -1860,6 +1876,9 @@ static int __cil_copy_node_helper(struct cil_tree_node *orig, uint32_t *finished
 	case CIL_PERMISSIONX:
 		copy_func = &cil_copy_permissionx;
 		break;
+	case CIL_DENY_RULE:
+		copy_func = &cil_copy_deny_rule;
+		break;
 	case CIL_TYPE_RULE:
 		copy_func = &cil_copy_type_rule;
 		break;
diff --git a/libsepol/cil/src/cil_copy_ast.h b/libsepol/cil/src/cil_copy_ast.h
index a50c3708..9f695ec5 100644
--- a/libsepol/cil/src/cil_copy_ast.h
+++ b/libsepol/cil/src/cil_copy_ast.h
@@ -80,6 +80,7 @@ int cil_copy_nametypetransition(struct cil_db *db, void *data, void **copy, symt
 int cil_copy_rangetransition(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_bool(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_avrule(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
+int cil_copy_deny_rule(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab);
 int cil_copy_type_rule(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_sens(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_sensalias(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
diff --git a/libsepol/cil/src/cil_flavor.h b/libsepol/cil/src/cil_flavor.h
index c2f0cee7..89ab7875 100644
--- a/libsepol/cil/src/cil_flavor.h
+++ b/libsepol/cil/src/cil_flavor.h
@@ -86,6 +86,7 @@ enum cil_flavor {
 	CIL_ROLEALLOW,
 	CIL_AVRULE,
 	CIL_AVRULEX,
+	CIL_DENY_RULE,
 	CIL_ROLETRANSITION,
 	CIL_TYPE_RULE,
 	CIL_NAMETYPETRANSITION,
diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h
index d727c352..9e492cb9 100644
--- a/libsepol/cil/src/cil_internal.h
+++ b/libsepol/cil/src/cil_internal.h
@@ -244,6 +244,7 @@ extern char *CIL_KEY_SRC_CIL;
 extern char *CIL_KEY_SRC_HLL_LMS;
 extern char *CIL_KEY_SRC_HLL_LMX;
 extern char *CIL_KEY_SRC_HLL_LME;
+extern char *CIL_KEY_DENY_RULE;
 
 /*
 	Symbol Table Array Indices
@@ -636,6 +637,14 @@ struct cil_permissionx {
 	ebitmap_t *perms;
 };
 
+struct cil_deny_rule {
+	char *src_str;
+	void *src; /* type, alias, or attribute */
+	char *tgt_str;
+	void *tgt; /* type, alias, or attribute */
+	struct cil_list *classperms;
+};
+
 #define CIL_TYPE_TRANSITION 16
 #define CIL_TYPE_MEMBER     32
 #define CIL_TYPE_CHANGE     64
@@ -1041,6 +1050,7 @@ void cil_tunable_init(struct cil_tunable **ciltun);
 void cil_tunif_init(struct cil_tunableif **tif);
 void cil_avrule_init(struct cil_avrule **avrule);
 void cil_permissionx_init(struct cil_permissionx **permx);
+void cil_deny_rule_init(struct cil_deny_rule **rule);
 void cil_type_rule_init(struct cil_type_rule **type_rule);
 void cil_roletransition_init(struct cil_roletransition **roletrans);
 void cil_roleallow_init(struct cil_roleallow **role_allow);
diff --git a/libsepol/cil/src/cil_reset_ast.c b/libsepol/cil/src/cil_reset_ast.c
index 0864d7ef..9069317e 100644
--- a/libsepol/cil/src/cil_reset_ast.c
+++ b/libsepol/cil/src/cil_reset_ast.c
@@ -218,6 +218,11 @@ static void cil_reset_avrule(struct cil_avrule *rule)
 	cil_reset_classperms_list(rule->perms.classperms);
 }
 
+static void cil_reset_deny_rule(struct cil_deny_rule *rule)
+{
+	cil_reset_classperms_list(rule->classperms);
+}
+
 static void cil_reset_rangetransition(struct cil_rangetransition *rangetrans)
 {
 	if (rangetrans->range_str == NULL) {
@@ -545,6 +550,9 @@ static int __cil_reset_node(struct cil_tree_node *node,  __attribute__((unused))
 	case CIL_AVRULE:
 		cil_reset_avrule(node->data);
 		break;
+	case CIL_DENY_RULE:
+		cil_reset_deny_rule(node->data);
+		break;
 	case CIL_SENS:
 		cil_reset_sens(node->data);
 		break;
diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c
index 96dd4054..33b9d321 100644
--- a/libsepol/cil/src/cil_resolve_ast.c
+++ b/libsepol/cil/src/cil_resolve_ast.c
@@ -375,6 +375,51 @@ exit:
 	return rc;
 }
 
+int cil_resolve_deny_rule(struct cil_tree_node *current, void *extra_args)
+{
+	struct cil_args_resolve *args = extra_args;
+	struct cil_db *db = NULL;
+
+	struct cil_deny_rule *rule = current->data;
+	struct cil_symtab_datum *src_datum = NULL;
+	struct cil_symtab_datum *tgt_datum = NULL;
+	int rc = SEPOL_ERR;
+
+	if (args != NULL) {
+		db = args->db;
+	}
+
+	rc = cil_resolve_name(current, rule->src_str, CIL_SYM_TYPES, args, &src_datum);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+	rule->src = src_datum;
+
+	if (rule->tgt_str == CIL_KEY_SELF) {
+		rule->tgt = db->selftype;
+	} else if (rule->tgt_str == CIL_KEY_NOTSELF) {
+		rule->tgt = db->notselftype;
+	} else if (rule->tgt_str == CIL_KEY_OTHER) {
+		rule->tgt = db->othertype;
+	} else {
+		rc = cil_resolve_name(current, rule->tgt_str, CIL_SYM_TYPES, args, &tgt_datum);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		rule->tgt = tgt_datum;
+	}
+
+	rc = cil_resolve_classperms_list(current, rule->classperms, extra_args);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	return SEPOL_OK;
+
+exit:
+	return rc;
+}
+
 int cil_resolve_type_rule(struct cil_tree_node *current, void *extra_args)
 {
 	struct cil_args_resolve *args = extra_args;
@@ -3783,6 +3828,9 @@ static int __cil_resolve_ast_node(struct cil_tree_node *node, void *extra_args)
 		case CIL_PERMISSIONX:
 			rc = cil_resolve_permissionx(node, (struct cil_permissionx*)node->data, args);
 			break;
+		case CIL_DENY_RULE:
+			rc = cil_resolve_deny_rule(node, args);
+			break;
 		case CIL_TYPE_RULE:
 			rc = cil_resolve_type_rule(node, args);
 			break;
diff --git a/libsepol/cil/src/cil_resolve_ast.h b/libsepol/cil/src/cil_resolve_ast.h
index 1d971fd6..78357993 100644
--- a/libsepol/cil/src/cil_resolve_ast.h
+++ b/libsepol/cil/src/cil_resolve_ast.h
@@ -40,6 +40,7 @@ int cil_resolve_classperms(struct cil_tree_node *current, struct cil_classperms
 int cil_resolve_classpermissionset(struct cil_tree_node *current, struct cil_classpermissionset *cps, void *extra_args);
 int cil_resolve_classperms_list(struct cil_tree_node *current, struct cil_list *cp_list, void *extra_args);
 int cil_resolve_avrule(struct cil_tree_node *current, void *extra_args);
+int cil_resolve_deny_rule(struct cil_tree_node *current, void *extra_args);
 int cil_resolve_type_rule(struct cil_tree_node *current, void *extra_args);
 int cil_resolve_typeattributeset(struct cil_tree_node *current, void *extra_args);
 int cil_resolve_typealias(struct cil_tree_node *current, void *extra_args);
diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c
index 3445507e..c268291d 100644
--- a/libsepol/cil/src/cil_verify.c
+++ b/libsepol/cil/src/cil_verify.c
@@ -1041,6 +1041,15 @@ static int __cil_verify_booleanif_helper(struct cil_tree_node *node, __attribute
 		}
 		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;
diff --git a/libsepol/cil/src/cil_write_ast.c b/libsepol/cil/src/cil_write_ast.c
index b75784ef..4da7a77c 100644
--- a/libsepol/cil/src/cil_write_ast.c
+++ b/libsepol/cil/src/cil_write_ast.c
@@ -1144,6 +1144,16 @@ void cil_write_ast_node(FILE *out, struct cil_tree_node *node)
 		fprintf(out, ")\n");
 		break;
 	}
+	case CIL_DENY_RULE: {
+		struct cil_deny_rule *rule = node->data;
+		fprintf(out, "(deny ");
+
+		fprintf(out, "%s ", datum_or_str(DATUM(rule->src), rule->src_str));
+		fprintf(out, "%s ", datum_or_str(DATUM(rule->tgt), rule->tgt_str));
+		write_classperms_list(out, rule->classperms);
+		fprintf(out, ")\n");
+		break;
+	}
 	case CIL_TYPE_RULE: {
 		struct cil_type_rule *rule = node->data;
 		if (rule->rule_kind == AVRULE_TRANSITION)
-- 
2.39.2

[PATCH 2/9 v3] libsepol/cil: Add cil_list_is_empty macro

[James Carter]

Add a macro, called cil_list_is_empty, that returns true if the
list pointer or list head is NULL.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_list.h | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/libsepol/cil/src/cil_list.h b/libsepol/cil/src/cil_list.h
index 6b4708a0..f974fddc 100644
--- a/libsepol/cil/src/cil_list.h
+++ b/libsepol/cil/src/cil_list.h
@@ -44,6 +44,9 @@ struct cil_list_item {
 	void *data;
 };
 
+#define cil_list_is_empty(list) \
+	((list) == NULL || (list)->head == NULL)
+
 #define cil_list_for_each(item, list) \
 	for (item = (list)->head; item != NULL; item = item->next)
 
-- 
2.39.2

[PATCH 3/9 v3] libsepol/cil: Add cil_tree_node_remove function

[James Carter]

Add the function cil_tree_node_remove() which takes a node pointer
as an input, finds the parent, walks the list of nodes to the node
prior to the given node, updates that node's next pointer to remove
the given node from the tree, and then destroys the node.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
v3:
 - Check for cl_tail pointing to the node
 - Destroy the node before returning if cl_head points to the node

 libsepol/cil/src/cil_tree.c | 35 +++++++++++++++++++++++++++++++++++
 libsepol/cil/src/cil_tree.h |  1 +
 2 files changed, 36 insertions(+)

diff --git a/libsepol/cil/src/cil_tree.c b/libsepol/cil/src/cil_tree.c
index 6376c208..1155e311 100644
--- a/libsepol/cil/src/cil_tree.c
+++ b/libsepol/cil/src/cil_tree.c
@@ -248,6 +248,41 @@ void cil_tree_node_destroy(struct cil_tree_node **node)
 	*node = NULL;
 }
 
+void cil_tree_node_remove(struct cil_tree_node *node)
+{
+	struct cil_tree_node *parent, *curr;
+
+	if (node == NULL || node->parent == NULL) {
+		return;
+	}
+
+	parent = node->parent;
+
+	if (parent->cl_head == node) {
+		if (parent->cl_tail == node) {
+			parent->cl_tail = NULL;
+		}
+		parent->cl_head = node->next;
+		cil_tree_node_destroy(&node);
+		return;
+	}
+
+	curr = parent->cl_head;
+	while (curr && curr->next != node) {
+		curr = curr->next;
+	}
+
+	if (curr == NULL) {
+		return;
+	}
+
+	if (parent->cl_tail == node) {
+		parent->cl_tail = curr;
+	}
+	curr->next = node->next;
+	cil_tree_node_destroy(&node);
+}
+
 /* Perform depth-first walk of the tree
    Parameters:
    start_node:          root node to start walking from
diff --git a/libsepol/cil/src/cil_tree.h b/libsepol/cil/src/cil_tree.h
index 5a98da55..cb6a0d24 100644
--- a/libsepol/cil/src/cil_tree.h
+++ b/libsepol/cil/src/cil_tree.h
@@ -63,6 +63,7 @@ void cil_tree_children_destroy(struct cil_tree_node *node);
 
 void cil_tree_node_init(struct cil_tree_node **node);
 void cil_tree_node_destroy(struct cil_tree_node **node);
+void cil_tree_node_remove(struct cil_tree_node *node);
 
 //finished values
 #define CIL_TREE_SKIP_NOTHING	0
-- 
2.39.2

[PATCH 4/9 v3] libsepol/cil: Process deny rules

[James Carter]

A deny rule is like a neverallow rule, except that permissions are
removed rather than an error reported.

(allow S1 T1 P1)
(deny  S2 T2 P2)

First, write the allow rule with all of the permissions not in the deny rule
P3 = P1 and not P2
(allow S1 T1 P3)

Obviously, the rule is only written if P3 is not an empty list. This goes
for the rest of the rules as well--they are only written if the source and
target exist.

The remaining rules will only involve the common permissions
P4 = P1 and P2

Next, write the allow rule for any types in S1 that are not in S2
S3 = S1 and not S2
(allow S3 T1 P4)

Finally, write the allow rules needed to cover the types in T1 that are
not in T2. Since, T1 and T2 might be "self", "notself", or "other", this
requires more complicated handling. Any rule with "self" will not match
a rule with either "notself" or "other".

if (T1 is self and T2 is self) or (T1 is notself and T2 is notself) then
  Nothing more needs to be done.

The rest of the rules will depend on the intersection of S1 and S2
which cannot be the empty set since the allow and deny rules match.
S4 = S1 and S2

if T1 is notself or T1 is other or T2 is notself or T2 is other then
  if T1 is notself then
    if T2 is other then
      T = ALL and not S2
      (allow S4 T P4)
    else [T2 is not self, notself, or other]
      S5 = S4 and not T2
      S6 = S4 and T2
      TA = ALL and not T2
      TB = TA and not S4
      (allow S6 TA P4)
      (allow S5 TB P4)
      if cardinality(S5) > 1 then
        (allow S5 other P4)
  else if T1 is other then
    (allow S3 S4 P4)
    if T2 is notself then
      [Nothing else is needed]
    else if T2 is other then
      (allow S4 S3 P4)
    else [T2 is not self, notself, or other]
      S5 = S4 and not T2
      S6 = S4 and T2
      TC = S1 and not T2
      TD = S3 and not T2
      (allow S6 TC P4)
      (allow S5 TD P4)
      if cardinality(S5) > 1 then
        (allow S5 other P4)
  else [T1 is not self, notself, or other]
    S8 = S4 and T1
    (allow S8 self P4)
    if T2 is notself then
      [Nothing else is needed]
    else [T2 is other]
      T = T1 and not S2
      (allow S4 T P4)
else [Neither T1 nor T2 are notself or other]
  if T1 is self and T2 is not self then
    S5 = S4 and not T2
    (allow S5 self P4)
  else if T1 is not self and T2 is self then
    S7 = S4 and not T1
    S8 = S4 and T1
    T8 = T1 and not S4
    (allow S7 T1 P4)
    (allow S8 T8 P4)
    if cardinality(S8) > 1 then
      (allow S8 other P4)
  else [Neither T1 nor T2 is self]
    T3 = T1 and not T2
    (allow S4 T3 P4)

Signed-off-by: James Carter <jwcart2@gmail.com>
---
v3:
 - Add support for notself and other keywords
 - Add support for checking for previously defined attribute
 - Update comment explaining the logic
 - Added cil_datum_cardinality() function
 - Added cil_datum_not() function
 - For functions cil_create_and_expr_list() and cil_create_andnot_expr_list()
   have a flavor parameter for both value parameters.
 - Add functions cil_check_attribute_in_symtab() and
   cil_check_for_previously_defined_attribute().
 - Add function cil_create_attribute_all_and_not_d()
 - For function cil_create_attribute_d1_and_not_d2(), removed prev parameter,
   just return d1 if d2 is NULL, and check for a previously defined attribute
   before creating a new one.
 - For function cil_create_attribute_d1_and_d2(), removed the prev parameter,
   just return NULL if either d1 or d2 is NULL, and check for a previously
   defined attribute before creating a new one.
 - For function cil_create_and_add_avrule(), don't add a node if either src
   or tgt is NULL;
 - Added function cil_remove_permissions_from_special_rule() to handle
   rule with notself and other.
 - For function cil_remove_permissions_from_rule(), reworked the logic
   to account for the use of notself and other and to make it easier to
   understand.

 libsepol/cil/src/cil_deny.c | 1413 +++++++++++++++++++++++++++++++++++
 libsepol/cil/src/cil_deny.h |   36 +
 libsepol/cil/src/cil_post.c |    7 +
 3 files changed, 1456 insertions(+)
 create mode 100644 libsepol/cil/src/cil_deny.c
 create mode 100644 libsepol/cil/src/cil_deny.h

diff --git a/libsepol/cil/src/cil_deny.c b/libsepol/cil/src/cil_deny.c
new file mode 100644
index 00000000..8db6177d
--- /dev/null
+++ b/libsepol/cil/src/cil_deny.c
@@ -0,0 +1,1413 @@
+/*
+ * This file is public domain software, i.e. not copyrighted.
+ *
+ * Warranty Exclusion
+ * ------------------
+ * You agree that this software is a non-commercially developed program
+ * that may contain "bugs" (as that term is used in the industry) and
+ * that it may not function as intended. The software is licensed
+ * "as is". NSA makes no, and hereby expressly disclaims all, warranties,
+ * express, implied, statutory, or otherwise with respect to the software,
+ * including noninfringement and the implied warranties of merchantability
+ * and fitness for a particular purpose.
+ *
+ * Limitation of Liability
+ *-----------------------
+ * In no event will NSA be liable for any damages, including loss of data,
+ * lost profits, cost of cover, or other special, incidental, consequential,
+ * direct or indirect damages arising from the software or the use thereof,
+ * however caused and on any theory of liability. This limitation will apply
+ * even if NSA has been advised of the possibility of such damage. You
+ * acknowledge that this is a reasonable allocation of risk.
+ *
+ * Original author: James Carter
+ */
+
+#include <sepol/policydb/ebitmap.h>
+
+#include "cil_internal.h"
+#include "cil_find.h"
+#include "cil_flavor.h"
+#include "cil_list.h"
+#include "cil_strpool.h"
+#include "cil_log.h"
+#include "cil_symtab.h"
+#include "cil_build_ast.h"
+#include "cil_copy_ast.h"
+#include "cil_deny.h"
+
+#define CIL_DENY_ATTR_PREFIX "deny_rule_attr"
+
+/*
+ * A deny rule is like a neverallow rule, except that permissions are
+ * removed rather than an error reported.
+ *
+ * (allow S1 T1 P1)
+ * (deny  S2 T2 P2)
+ *
+ * First, write the allow rule with all of the permissions not in the deny rule
+ * P3 = P1 and not P2
+ * (allow S1 T1 P3)
+ *
+ * Obviously, the rule is only written if P3 is not an empty list. This goes
+ * for the rest of the rules as well--they are only written if the source and
+ * target exist.
+ *
+ * The remaining rules will only involve the common permissions
+ * P4 = P1 and P2
+ *
+ * Next, write the allow rule for any types in S1 that are not in S2
+ * S3 = S1 and not S2
+ * (allow S3 T1 P4)
+ *
+ * Finally, write any allow rules needed to cover the types in T1 that are
+ * not in T2. Since, T1 and T2 might be "self", "notself", or "other", this
+ * requires more complicated handling. Any rule with "self" will not match
+ * a rule with either "notself" or "other".
+ *
+ * if (T1 is self and T2 is self) or (T1 is notself and T2 is notself) then
+ *   Nothing more needs to be done.
+ *
+ * The rest of the rules will depend on the intersection of S1 and S2
+ * which cannot be the empty set since the allow and deny rules match.
+ * S4 = S1 and S2
+ *
+ * if T1 is notself or T1 is other or T2 is notself or T2 is other then
+ *   if T1 is notself then
+ *     if T2 is other then
+ *       T = ALL and not S2
+ *       (allow S4 T P4)
+ *     else [T2 is not self, notself, or other]
+ *       S5 = S4 and not T2
+ *       S6 = S4 and T2
+ *       TA = ALL and not T2
+ *       TB = TA and not S4
+ *       (allow S6 TA P4)
+ *       (allow S5 TB P4)
+ *       if cardinality(S5) > 1 then
+ *         (allow S5 other P4)
+ *   else if T1 is other then
+ *     (allow S3 S4 P4)
+ *     if T2 is notself then
+ *       [Nothing else is needed]
+ *     else if T2 is other then
+ *       (allow S4 S3 P4)
+ *     else [T2 is not self, notself, or other]
+ *       S5 = S4 and not T2
+ *       S6 = S4 and T2
+ *       TC = S1 and not T2
+ *       TD = S3 and not T2
+ *       (allow S6 TC P4)
+ *       (allow S5 TD P4)
+ *       if cardinality(S5) > 1 then
+ *         (allow S5 other P4)
+ *   else [T1 is not self, notself, or other]
+ *     S8 = S4 and T1
+ *     (allow S8 self P4)
+ *     if T2 is notself then
+ *       [Nothing else is needed]
+ *     else [T2 is other]
+ *       T = T1 and not S2
+ *       (allow S4 T P4)
+ * else [Neither T1 nor T2 are notself or other]
+ *   if T1 is self and T2 is not self then
+ *     S5 = S4 and not T2
+ *     (allow S5 self P4)
+ *   else if T1 is not self and T2 is self then
+ *     S7 = S4 and not T1
+ *     S8 = S4 and T1
+ *     T8 = T1 and not S4
+ *     (allow S7 T1 P4)
+ *     (allow S8 T8 P4)
+ *     if cardinality(S8) > 1 then
+ *       (allow S8 other P4)
+ *   else [Neither T1 nor T2 is self]
+ *     T3 = T1 and not T2
+ *     (allow S4 T3 P4)
+ */
+
+static int cil_perm_match(const struct cil_perm *p1, const struct cil_list *pl2)
+{
+	struct cil_list_item *curr;
+
+	cil_list_for_each(curr, pl2) {
+		struct cil_perm *p = curr->data;
+		if (p == p1) {
+			return CIL_TRUE;
+		}
+	}
+	return CIL_FALSE;
+}
+
+static int cil_class_perm_match(const struct cil_class *c1, const struct cil_perm *p1, const struct cil_list *cpl2)
+{
+	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) {
+				if (cp->class == c1) {
+					if (cil_perm_match(p1, cp->perms)) {
+						return CIL_TRUE;
+					}
+				}
+			} else { /* MAP */
+				struct cil_list_item *p;
+				cil_list_for_each(p, cp->perms) {
+					struct cil_perm *cmp = p->data;
+					if (cil_class_perm_match(c1, p1, cmp->classperms)) {
+						return CIL_TRUE;
+					}
+				}
+			}
+		} else { /* SET */
+			struct cil_classperms_set *cp_set = curr->data;
+			struct cil_classpermission *cp = cp_set->set;
+			if (cil_class_perm_match(c1, p1, cp->classperms)) {
+				return CIL_TRUE;
+			}
+		}
+	}
+	return CIL_FALSE;
+}
+
+static int cil_classperms_match_any(const struct cil_classperms *cp1, const struct cil_list *cpl2)
+{
+	struct cil_list_item *curr;
+
+	cil_list_for_each(curr, cp1->perms) {
+		struct cil_perm *perm = curr->data;
+		if (cil_class_perm_match(cp1->class, perm, cpl2)) {
+			return CIL_TRUE;
+		}
+	}
+	return CIL_FALSE;
+}
+
+int cil_classperms_list_match_any(const struct cil_list *cpl1, const struct cil_list *cpl2)
+{
+	struct cil_list_item *curr;
+
+	if (!cpl1 || !cpl2) {
+		return (!cpl1 && !cpl2) ? CIL_TRUE : CIL_FALSE;
+	}
+
+	cil_list_for_each(curr, cpl1) {
+		if (curr->flavor == CIL_CLASSPERMS) {
+			struct cil_classperms *cp = curr->data;
+			if (FLAVOR(cp->class) == CIL_CLASS) {
+				if (cil_classperms_match_any(cp, cpl2)) {
+					return CIL_TRUE;
+				}
+			} else { /* MAP */
+				struct cil_list_item *p;
+				cil_list_for_each(p, cp->perms) {
+					struct cil_perm *cmp = p->data;
+					if (cil_classperms_list_match_any(cmp->classperms, cpl2)) {
+						return CIL_TRUE;
+					}
+				}
+			}
+		} else { /* SET */
+			struct cil_classperms_set *cp_set = curr->data;
+			struct cil_classpermission *cp = cp_set->set;
+			if (cil_classperms_list_match_any(cp->classperms, cpl2)) {
+				return CIL_TRUE;
+			}
+		}
+	}
+	return CIL_FALSE;
+}
+
+static int cil_classperms_match_all(const struct cil_classperms *cp1, const struct cil_list *cpl2)
+{
+	struct cil_list_item *curr;
+
+	cil_list_for_each(curr, cp1->perms) {
+		struct cil_perm *perm = curr->data;
+		if (!cil_class_perm_match(cp1->class, perm, cpl2)) {
+			return CIL_FALSE;
+		}
+	}
+	return CIL_TRUE;
+}
+
+int cil_classperms_list_match_all(const struct cil_list *cpl1, const struct cil_list *cpl2)
+{
+	struct cil_list_item *curr;
+
+	if (!cpl1 || !cpl2) {
+		return (!cpl1 && !cpl2) ? CIL_TRUE : CIL_FALSE;
+	}
+
+	cil_list_for_each(curr, cpl1) {
+		if (curr->flavor == CIL_CLASSPERMS) {
+			struct cil_classperms *cp = curr->data;
+			if (FLAVOR(cp->class) == CIL_CLASS) {
+				if (!cil_classperms_match_all(cp, cpl2)) {
+					return CIL_FALSE;
+				}
+			} else { /* MAP */
+				struct cil_list_item *p;
+				cil_list_for_each(p, cp->perms) {
+					struct cil_perm *cmp = p->data;
+					if (!cil_classperms_list_match_all(cmp->classperms, cpl2)) {
+						return CIL_FALSE;
+					}
+				}
+			}
+		} else { /* SET */
+			struct cil_classperms_set *cp_set = curr->data;
+			struct cil_classpermission *cp = cp_set->set;
+			if (!cil_classperms_list_match_all(cp->classperms, cpl2)) {
+				return CIL_FALSE;
+			}
+		}
+	}
+	return CIL_TRUE;
+}
+
+static void cil_classperms_copy(struct cil_classperms **new, const struct cil_classperms *old)
+{
+	cil_classperms_init(new);
+	(*new)->class_str = old->class_str;
+	(*new)->class = old->class;
+	cil_copy_list(old->perm_strs, &(*new)->perm_strs);
+	cil_copy_list(old->perms, &(*new)->perms);
+}
+
+static void cil_classperms_set_copy(struct cil_classperms_set **new, const struct cil_classperms_set *old)
+{
+	cil_classperms_set_init(new);
+	(*new)->set_str = old->set_str;
+	(*new)->set = old->set;
+}
+
+void cil_classperms_list_copy(struct cil_list **new, const struct cil_list *old)
+{
+	struct cil_list_item *curr;
+
+	if (!new) {
+		return;
+	}
+
+	if (!old) {
+		*new = NULL;
+		return;
+	}
+
+	cil_list_init(new, CIL_LIST);
+
+	cil_list_for_each(curr, old) {
+		if (curr->flavor == CIL_CLASSPERMS) {
+			struct cil_classperms *new_cp;
+			cil_classperms_copy(&new_cp, curr->data);
+			cil_list_append(*new, CIL_CLASSPERMS, new_cp);
+		} else { /* SET */
+			struct cil_classperms_set *new_cps;
+			cil_classperms_set_copy(&new_cps, curr->data);
+			cil_list_append(*new, CIL_CLASSPERMS_SET, new_cps);
+		}
+	}
+
+	if (cil_list_is_empty(*new)) {
+		cil_list_destroy(new, CIL_FALSE);
+	}
+}
+
+/* Append cp1 and cpl2 to result */
+static void cil_classperms_and(struct cil_list **result, const struct cil_classperms *cp1, const struct cil_list *cpl2)
+{
+	struct cil_classperms *new_cp = NULL;
+	struct cil_list_item *curr;
+
+	if (cil_classperms_match_all(cp1, cpl2)) {
+		cil_classperms_copy(&new_cp, cp1);
+		cil_list_append(*result, CIL_CLASSPERMS, new_cp);
+		return;
+	}
+
+	cil_list_for_each(curr, cp1->perms) {
+		struct cil_perm *perm = curr->data;
+		if (cil_class_perm_match(cp1->class, perm, cpl2)) {
+			if (new_cp == NULL) {
+				cil_classperms_init(&new_cp);
+				new_cp->class_str = cp1->class_str;
+				new_cp->class = cp1->class;
+				cil_list_init(&new_cp->perm_strs, CIL_PERM);
+				cil_list_init(&new_cp->perms, CIL_PERM);
+				cil_list_append(*result, CIL_CLASSPERMS, new_cp);
+			}
+			cil_list_append(new_cp->perm_strs, CIL_STRING, perm->datum.fqn);
+			cil_list_append(new_cp->perms, CIL_DATUM, perm);
+		}
+	}
+}
+
+/* Append cp1 and cpl2 to result */
+static void cil_classperms_map_and(struct cil_list **result, const struct cil_classperms *cp1, const struct cil_list *cpl2)
+{
+	struct cil_classperms *new_cp = NULL;
+	struct cil_list_item *p;
+
+	cil_list_for_each(p, cp1->perms) {
+		struct cil_perm *map_perm = p->data;
+		if (cil_classperms_list_match_all(map_perm->classperms, cpl2)) {
+			if (new_cp == NULL) {
+				cil_classperms_init(&new_cp);
+				new_cp->class_str = cp1->class_str;
+				new_cp->class = cp1->class;
+				cil_list_init(&new_cp->perm_strs, CIL_PERM);
+				cil_list_init(&new_cp->perms, CIL_PERM);
+				cil_list_append(*result, CIL_CLASSPERMS, new_cp);
+			}
+			cil_list_append(new_cp->perm_strs, CIL_STRING, map_perm->datum.fqn);
+			cil_list_append(new_cp->perms, CIL_DATUM, map_perm);
+		} else {
+			struct cil_list *new_cpl = NULL;
+			cil_classperms_list_and(&new_cpl, map_perm->classperms, cpl2);
+			if (new_cpl) {
+				struct cil_list_item *i;
+				cil_list_for_each(i, new_cpl) {
+					cil_list_append(*result, i->flavor, i->data);
+				}
+				cil_list_destroy(&new_cpl, CIL_FALSE);
+			}
+		}
+	}
+}
+
+/* Append cps1 and cpl2 to result */
+static void cil_classperms_set_and(struct cil_list **result, const struct cil_classperms_set *cps1, const struct cil_list *cpl2)
+{
+	struct cil_classpermission *cp = cps1->set;
+
+	if (cil_classperms_list_match_all(cp->classperms, cpl2)) {
+		struct cil_classperms_set *new_cps;
+		cil_classperms_set_copy(&new_cps, cps1);
+		cil_list_append(*result, CIL_CLASSPERMS_SET, new_cps);
+	} else {
+		struct cil_list *new_cpl;
+		cil_classperms_list_and(&new_cpl, cp->classperms, cpl2);
+		if (new_cpl) {
+			struct cil_list_item *i;
+			cil_list_for_each(i, new_cpl) {
+				cil_list_append(*result, i->flavor, i->data);
+			}
+			cil_list_destroy(&new_cpl, CIL_FALSE);
+		}
+	}
+}
+
+/* result = cpl1 and cpl2 */
+void cil_classperms_list_and(struct cil_list **result, const struct cil_list *cpl1, const struct cil_list *cpl2)
+{
+	struct cil_list_item *curr;
+
+	if (!result) {
+		return;
+	}
+
+	if (!cpl1 || !cpl2) {
+		*result = NULL;
+		return;
+	}
+
+	if (cil_classperms_list_match_all(cpl1, cpl2)) {
+		cil_classperms_list_copy(result, cpl1);
+		return;
+	}
+
+	cil_list_init(result, CIL_LIST);
+
+	cil_list_for_each(curr, cpl1) {
+		if (curr->flavor == CIL_CLASSPERMS) {
+			struct cil_classperms *cp = curr->data;
+			if (FLAVOR(cp->class) == CIL_CLASS) {
+				cil_classperms_and(result, cp, cpl2);
+			} else { /* MAP */
+				cil_classperms_map_and(result, cp, cpl2);
+			}
+		} else { /* SET */
+			struct cil_classperms_set *cps = curr->data;
+			cil_classperms_set_and(result, cps, cpl2);
+		}
+	}
+
+	if (cil_list_is_empty(*result)) {
+		cil_list_destroy(result, CIL_FALSE);
+	}
+}
+
+/* Append cp1 and not cpl2 to result */
+static void cil_classperms_andnot(struct cil_list **result, const struct cil_classperms *cp1, const struct cil_list *cpl2)
+{
+	struct cil_classperms *new_cp = NULL;
+	struct cil_list_item *curr;
+
+	if (!cil_classperms_match_any(cp1, cpl2)) {
+		cil_classperms_copy(&new_cp, cp1);
+		cil_list_append(*result, CIL_CLASSPERMS, new_cp);
+		return;
+	}
+
+	cil_list_for_each(curr, cp1->perms) {
+		struct cil_perm *perm = curr->data;
+		if (!cil_class_perm_match(cp1->class, perm, cpl2)) {
+			if (new_cp == NULL) {
+				cil_classperms_init(&new_cp);
+				new_cp->class_str = cp1->class_str;
+				new_cp->class = cp1->class;
+				cil_list_init(&new_cp->perm_strs, CIL_PERM);
+				cil_list_init(&new_cp->perms, CIL_PERM);
+				cil_list_append(*result, CIL_CLASSPERMS, new_cp);
+			}
+			cil_list_append(new_cp->perm_strs, CIL_STRING, perm->datum.fqn);
+			cil_list_append(new_cp->perms, CIL_DATUM, perm);
+		}
+	}
+}
+
+/* Append cp1 and not cpl2 to result */
+static void cil_classperms_map_andnot(struct cil_list **result, const struct cil_classperms *cp1, const struct cil_list *cpl2)
+{
+	struct cil_classperms *new_cp = NULL;
+	struct cil_list_item *p;
+
+	cil_list_for_each(p, cp1->perms) {
+		struct cil_perm *map_perm = p->data;
+		if (!cil_classperms_list_match_any(map_perm->classperms, cpl2)) {
+			if (new_cp == NULL) {
+				cil_classperms_init(&new_cp);
+				new_cp->class_str = cp1->class_str;
+				new_cp->class = cp1->class;
+				cil_list_init(&new_cp->perm_strs, CIL_PERM);
+				cil_list_init(&new_cp->perms, CIL_PERM);
+				cil_list_append(*result, CIL_CLASSPERMS, new_cp);
+			}
+			cil_list_append(new_cp->perm_strs, CIL_STRING, map_perm->datum.fqn);
+			cil_list_append(new_cp->perms, CIL_DATUM, map_perm);
+		} else {
+			struct cil_list *new_cpl = NULL;
+			cil_classperms_list_andnot(&new_cpl, map_perm->classperms, cpl2);
+			if (new_cpl) {
+				struct cil_list_item *i;
+				cil_list_for_each(i, new_cpl) {
+					cil_list_append(*result, i->flavor, i->data);
+				}
+				cil_list_destroy(&new_cpl, CIL_FALSE);
+			}
+		}
+	}
+}
+
+/* Append cps1 and not cpl2 to result */
+static void cil_classperms_set_andnot(struct cil_list **result, const struct cil_classperms_set *cps1, const struct cil_list *cpl2)
+{
+	struct cil_classpermission *cp = cps1->set;
+
+	if (!cil_classperms_list_match_any(cp->classperms, cpl2)) {
+		struct cil_classperms_set *new_cps;
+		cil_classperms_set_copy(&new_cps, cps1);
+		cil_list_append(*result, CIL_CLASSPERMS_SET, new_cps);
+	} else {
+		struct cil_list *new_cpl;
+		cil_classperms_list_andnot(&new_cpl, cp->classperms, cpl2);
+		if (new_cpl) {
+			struct cil_list_item *i;
+			cil_list_for_each(i, new_cpl) {
+				cil_list_append(*result, i->flavor, i->data);
+			}
+			cil_list_destroy(&new_cpl, CIL_FALSE);
+		}
+	}
+}
+
+/* result = cpl1 and not cpl2 */
+void cil_classperms_list_andnot(struct cil_list **result, const struct cil_list *cpl1, const struct cil_list *cpl2)
+{
+	struct cil_list_item *curr;
+
+	if (!result) {
+		return;
+	}
+
+	if (!cpl1) {
+		*result = NULL;
+		return;
+	}
+
+	if (!cpl2 || !cil_classperms_list_match_any(cpl1, cpl2)) {
+		cil_classperms_list_copy(result, cpl1);
+		return;
+	}
+
+	cil_list_init(result, CIL_LIST);
+
+	cil_list_for_each(curr, cpl1) {
+		if (curr->flavor == CIL_CLASSPERMS) {
+			struct cil_classperms *cp = curr->data;
+			if (FLAVOR(cp->class) == CIL_CLASS) {
+				cil_classperms_andnot(result, cp, cpl2);
+			} else { /* MAP */
+				cil_classperms_map_andnot(result, cp, cpl2);
+			}
+		} else { /* SET */
+			struct cil_classperms_set *cps = curr->data;
+			cil_classperms_set_andnot(result, cps, cpl2);
+		}
+	}
+
+	if (cil_list_is_empty(*result)) {
+		cil_list_destroy(result, CIL_FALSE);
+	}
+}
+
+static int cil_datum_cardinality(const struct cil_symtab_datum *d)
+{
+	if (!d) {
+		return 0;
+	}
+	if (FLAVOR(d) != CIL_TYPEATTRIBUTE) {
+		return 1;
+	} else {
+		struct cil_typeattribute *a = (struct cil_typeattribute *)d;
+		return ebitmap_cardinality(a->types);
+	}
+}
+
+/* result = ALL and not d2 */
+static int cil_datum_not(ebitmap_t *result, const struct cil_symtab_datum *d, int max)
+{
+	int rc = SEPOL_OK;
+
+	if (FLAVOR(d) != CIL_TYPEATTRIBUTE) {
+		struct cil_type *t = (struct cil_type *)d;
+		ebitmap_t e;
+
+		ebitmap_init(&e);
+		rc = ebitmap_set_bit(&e, t->value, 1);
+		if (rc != SEPOL_OK) {
+			ebitmap_destroy(&e);
+			goto exit;
+		}
+
+		ebitmap_init(result);
+		rc = ebitmap_not(result, &e, max);
+		if (rc != SEPOL_OK) {
+			ebitmap_destroy(&e);
+			ebitmap_destroy(result);
+			goto exit;
+		}
+		ebitmap_destroy(&e);
+	} else {
+		struct cil_typeattribute *a = (struct cil_typeattribute *)d;
+
+		ebitmap_init(result);
+		rc = ebitmap_not(result, a->types, max);
+		if (rc != SEPOL_OK) {
+			ebitmap_destroy(result);
+			goto exit;
+		}
+	}
+exit:
+	return rc;
+}
+
+/* result = d1 and d2 */
+static int cil_datums_and(ebitmap_t *result, const struct cil_symtab_datum *d1, const 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_type *t1 = (struct cil_type *)d1;
+		struct cil_type *t2 = (struct cil_type *)d2;
+		ebitmap_init(result);
+		if (t1->value == t2->value) {
+			rc = ebitmap_set_bit(result, t1->value, 1);
+			if (rc != SEPOL_OK) {
+				ebitmap_destroy(result);
+				goto exit;
+			}
+		}
+	} else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
+		struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
+		struct cil_type *t2 = (struct cil_type *)d2;
+		ebitmap_init(result);
+		if (ebitmap_get_bit(a1->types, t2->value)) {
+			rc = ebitmap_set_bit(result, t2->value, 1);
+			if (rc != SEPOL_OK) {
+				ebitmap_destroy(result);
+				goto exit;
+			}
+		}
+	} else if (f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
+		struct cil_type *t1 = (struct cil_type *)d1;
+		struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
+		ebitmap_init(result);
+		if (ebitmap_get_bit(a2->types, t1->value)) {
+			rc = ebitmap_set_bit(result, t1->value, 1);
+			if (rc != SEPOL_OK) {
+				ebitmap_destroy(result);
+				goto exit;
+			}
+		}
+	} else {
+		/* Both are attributes */
+		struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
+		struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
+		rc = ebitmap_and(result, a1->types, a2->types);
+		if (rc != SEPOL_OK) {
+			ebitmap_destroy(result);
+			goto exit;
+		}
+	}
+exit:
+	return rc;
+}
+
+/* result = d1 and not d2 */
+static int cil_datums_andnot(ebitmap_t *result, const struct cil_symtab_datum *d1, const 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_type *t1 = (struct cil_type *)d1;
+		struct cil_type *t2 = (struct cil_type *)d2;
+		ebitmap_init(result);
+		if (t1->value != t2->value) {
+			rc = ebitmap_set_bit(result, t1->value, 1);
+			if (rc != SEPOL_OK) {
+				ebitmap_destroy(result);
+				goto exit;
+			}
+		}
+	} else if (f1 == CIL_TYPEATTRIBUTE && f2 != CIL_TYPEATTRIBUTE) {
+		struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
+		struct cil_type *t2 = (struct cil_type *)d2;
+		rc = ebitmap_cpy(result, a1->types);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		rc = ebitmap_set_bit(result, t2->value, 0);
+		if (rc != SEPOL_OK) {
+			ebitmap_destroy(result);
+			goto exit;
+		}
+	} else if (f1 != CIL_TYPEATTRIBUTE && f2 == CIL_TYPEATTRIBUTE) {
+		struct cil_type *t1 = (struct cil_type *)d1;
+		struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
+		ebitmap_init(result);
+		if (!ebitmap_get_bit(a2->types, t1->value)) {
+			rc = ebitmap_set_bit(result, t1->value, 1);
+			if (rc != SEPOL_OK) {
+				ebitmap_destroy(result);
+				goto exit;
+			}
+		}
+	} else {
+		/* Both are attributes */
+		struct cil_typeattribute *a1 = (struct cil_typeattribute *)d1;
+		struct cil_typeattribute *a2 = (struct cil_typeattribute *)d2;
+		rc = ebitmap_andnot(result, a1->types, a2->types, a1->types->highbit);
+		if (rc != SEPOL_OK) {
+			ebitmap_destroy(result);
+			goto exit;
+		}
+	}
+exit:
+	return rc;
+}
+
+static size_t num_digits(unsigned n)
+{
+	size_t num = 1;
+	while (n >= 10) {
+		n /= 10;
+		num++;
+	}
+	return num;
+}
+
+static char *cil_create_new_attribute_name(unsigned num)
+{
+	char *s1 = NULL;
+	char *s2 = NULL;
+	size_t len_num = num_digits(num);
+	size_t len = strlen(CIL_DENY_ATTR_PREFIX) + 1 + len_num + 1;
+	int rc;
+
+	if (len >= CIL_MAX_NAME_LENGTH) {
+		cil_log(CIL_ERR, "Name length greater than max name length of %d",
+				CIL_MAX_NAME_LENGTH);
+		goto exit;
+	}
+
+	s1 = cil_malloc(len);
+	rc = snprintf(s1, len, "%s_%u", CIL_DENY_ATTR_PREFIX, num);
+	if (rc < 0 || (size_t)rc >= len) {
+		cil_log(CIL_ERR, "Error creating new attribute name");
+		free(s1);
+		goto exit;
+	}
+
+	s2 = cil_strpool_add(s1);
+	free(s1);
+
+exit:
+	return s2;
+}
+
+static struct cil_list *cil_create_and_expr_list(enum cil_flavor f1, void *v1, enum cil_flavor f2, void *v2)
+{
+	struct cil_list *expr;
+
+	cil_list_init(&expr, CIL_TYPE);
+	cil_list_append(expr, CIL_OP, (void *)CIL_AND);
+	cil_list_append(expr, f1, v1);
+	cil_list_append(expr, f2, v2);
+
+	return expr;
+}
+
+static struct cil_list *cil_create_andnot_expr_list(enum cil_flavor f1, void *v1, enum cil_flavor f2, void *v2)
+{
+	struct cil_list *expr, *sub_expr;
+
+	cil_list_init(&expr, CIL_TYPE);
+	cil_list_append(expr, CIL_OP, (void *)CIL_AND);
+	cil_list_append(expr, f1, v1);
+	cil_list_init(&sub_expr, CIL_TYPE);
+	cil_list_append(sub_expr, CIL_OP, (void *)CIL_NOT);
+	cil_list_append(sub_expr, f2, v2);
+	cil_list_append(expr, CIL_LIST, sub_expr);
+
+	return expr;
+}
+
+static struct cil_tree_node *cil_create_and_insert_node(struct cil_tree_node *prev, enum cil_flavor flavor, void *data)
+{
+	struct cil_tree_node *new;
+
+	cil_tree_node_init(&new);
+	new->parent = prev->parent;
+	new->line = prev->line;
+	new->hll_offset = prev->hll_offset;
+	new->flavor = flavor;
+	new->data = data;
+	new->next = prev->next;
+	prev->next = new;
+
+	return new;
+}
+
+static int cil_create_and_insert_attribute_and_set(struct cil_db *db, struct cil_tree_node *prev, struct cil_list *str_expr, struct cil_list *datum_expr, ebitmap_t *types, struct cil_symtab_datum **d)
+{
+	struct cil_tree_node *attr_node = NULL;
+	char *name;
+	struct cil_typeattribute *attr = NULL;
+	struct cil_tree_node *attrset_node = NULL;
+	struct cil_typeattributeset *attrset = NULL;
+	symtab_t *symtab = NULL;
+	int rc = SEPOL_ERR;
+
+	name = cil_create_new_attribute_name(db->num_types_and_attrs);
+	if (!name) {
+		goto exit;
+	}
+
+	cil_typeattributeset_init(&attrset);
+	attrset->attr_str = name;
+	attrset->str_expr = str_expr;
+	attrset->datum_expr = datum_expr;
+
+	cil_typeattribute_init(&attr);
+	cil_list_init(&attr->expr_list, CIL_TYPE);
+	cil_list_append(attr->expr_list, CIL_LIST, datum_expr);
+	attr->types = types;
+	attr->used = CIL_ATTR_AVRULE;
+	attr->keep = (ebitmap_cardinality(types) < db->attrs_expand_size) ? CIL_FALSE : CIL_TRUE;
+
+	attr_node = cil_create_and_insert_node(prev, CIL_TYPEATTRIBUTE, attr);
+	attrset_node = cil_create_and_insert_node(attr_node, CIL_TYPEATTRIBUTESET, attrset);
+
+	rc = cil_get_symtab(prev->parent, &symtab, CIL_SYM_TYPES);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	rc = cil_symtab_insert(symtab, name, &attr->datum, attr_node);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	db->num_types_and_attrs++;
+
+	*d = &attr->datum;
+
+	return SEPOL_OK;
+
+exit:
+	if (attr_node) {
+		cil_destroy_typeattribute(attr_node->data); // This will not destroy datum_expr
+		free(attr_node);
+	}
+	if (attrset_node) {
+		prev->next = attrset_node->next;
+		free(attrset_node);
+	}
+	return rc;
+}
+
+struct attr_symtab_map_data {
+	struct cil_symtab_datum *d;
+	ebitmap_t *types;
+};
+
+static int cil_check_attribute_in_symtab(__attribute__((unused))hashtab_key_t k, hashtab_datum_t d, void *args)
+{
+	struct attr_symtab_map_data *data = args;
+
+	if (FLAVOR(d) == CIL_TYPEATTRIBUTE) {
+		struct cil_typeattribute *attr = (struct cil_typeattribute *)d;
+		if (ebitmap_cmp(data->types, attr->types)) {
+			data->d = d;
+		}
+	}
+	return SEPOL_OK;
+}
+
+static struct cil_symtab_datum *cil_check_for_previously_defined_attribute(struct cil_db *db, ebitmap_t *types, struct cil_symtab_datum *d)
+{
+	symtab_t *local_symtab, *root_symtab;
+	struct attr_symtab_map_data data;
+	int rc;
+
+	data.d = NULL;
+	data.types = types;
+
+	local_symtab = d->symtab;
+	root_symtab = &((struct cil_root *)db->ast->root->data)->symtab[CIL_SYM_TYPES];
+
+	if (local_symtab != root_symtab) {
+		rc = cil_symtab_map(local_symtab, cil_check_attribute_in_symtab, &data);
+		if (rc != SEPOL_OK) {
+			return NULL;
+		}
+	}
+
+	if (!data.d) {
+		rc = cil_symtab_map(root_symtab, cil_check_attribute_in_symtab, &data);
+		if (rc != SEPOL_OK) {
+			return NULL;
+		}
+	}
+
+	return data.d;
+}
+
+static int cil_create_attribute_all_and_not_d(struct cil_db *db, struct cil_symtab_datum *d, struct cil_symtab_datum **d3)
+{
+	struct cil_list *str_expr;
+	struct cil_list *datum_expr;
+	ebitmap_t *types;
+	int rc;
+
+	*d3 = NULL;
+
+	if (!d) {
+		return SEPOL_ERR;
+	}
+
+	str_expr = cil_create_andnot_expr_list(CIL_OP, (void *)CIL_ALL, CIL_STRING, d->fqn);
+	datum_expr = cil_create_andnot_expr_list(CIL_OP, (void *)CIL_ALL, CIL_DATUM, d);
+
+	types = cil_malloc(sizeof(*types));
+	rc = cil_datum_not(types, d, db->num_types);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	if (ebitmap_is_empty(types)) {
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	if (ebitmap_cardinality(types) == 1) {
+		unsigned i = ebitmap_highest_set_bit(types);
+		*d3 = DATUM(db->val_to_type[i]);
+		ebitmap_destroy(types);
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	*d3 = cil_check_for_previously_defined_attribute(db, types, d);
+	if (*d3) {
+		ebitmap_destroy(types);
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	rc = cil_create_and_insert_attribute_and_set(db, NODE(d), str_expr, datum_expr, types, d3);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	return SEPOL_OK;
+
+exit:
+	cil_list_destroy(&str_expr, CIL_FALSE);
+	cil_list_destroy(&datum_expr, CIL_FALSE);
+	free(types);
+	return rc;
+}
+
+static int cil_create_attribute_d1_and_not_d2(struct cil_db *db, struct cil_symtab_datum *d1, struct cil_symtab_datum *d2, struct cil_symtab_datum **d3)
+{
+	struct cil_list *str_expr;
+	struct cil_list *datum_expr;
+	ebitmap_t *types;
+	int rc;
+
+	if (!d2) {
+		*d3 = d1;
+		return SEPOL_OK;
+	}
+
+	*d3 = NULL;
+
+	if (!d1 || d1 == d2) {
+		return SEPOL_OK;
+	}
+
+	str_expr = cil_create_andnot_expr_list(CIL_STRING, d1->fqn, CIL_STRING, d2->fqn);
+	datum_expr = cil_create_andnot_expr_list(CIL_DATUM, d1, CIL_DATUM, d2);
+
+	types = cil_malloc(sizeof(*types));
+	rc = cil_datums_andnot(types, d1, d2);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+	if (ebitmap_is_empty(types)) {
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	if (ebitmap_cardinality(types) == 1) {
+		unsigned i = ebitmap_highest_set_bit(types);
+		*d3 = DATUM(db->val_to_type[i]);
+		ebitmap_destroy(types);
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	*d3 = cil_check_for_previously_defined_attribute(db, types, d1);
+	if (*d3) {
+		ebitmap_destroy(types);
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	rc = cil_create_and_insert_attribute_and_set(db, NODE(d1), str_expr, datum_expr, types, d3);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	return SEPOL_OK;
+
+exit:
+	cil_list_destroy(&str_expr, CIL_FALSE);
+	cil_list_destroy(&datum_expr, CIL_FALSE);
+	free(types);
+	return rc;
+}
+
+static int cil_create_attribute_d1_and_d2(struct cil_db *db, struct cil_symtab_datum *d1, struct cil_symtab_datum *d2, struct cil_symtab_datum **d3)
+{
+	struct cil_list *str_expr;
+	struct cil_list *datum_expr;
+	ebitmap_t *types;
+	int rc;
+
+	if (d1 == d2) {
+		*d3 = d1;
+		return SEPOL_OK;
+	}
+
+	*d3 = NULL;
+
+	if (!d1 || !d2) {
+		return SEPOL_OK;
+	}
+
+	str_expr = cil_create_and_expr_list(CIL_STRING, d1->fqn, CIL_STRING, d2->fqn);
+	datum_expr = cil_create_and_expr_list(CIL_DATUM, d1, CIL_DATUM, d2);
+
+	types = cil_malloc(sizeof(*types));
+	rc = cil_datums_and(types, d1, d2);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+	if (ebitmap_is_empty(types)) {
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	if (ebitmap_cardinality(types) == 1) {
+		unsigned i = ebitmap_highest_set_bit(types);
+		*d3 = DATUM(db->val_to_type[i]);
+		ebitmap_destroy(types);
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	*d3 = cil_check_for_previously_defined_attribute(db, types, d1);
+	if (*d3) {
+		ebitmap_destroy(types);
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	rc = cil_create_and_insert_attribute_and_set(db, NODE(d1), str_expr, datum_expr, types, d3);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	return SEPOL_OK;
+
+exit:
+	cil_list_destroy(&str_expr, CIL_FALSE);
+	cil_list_destroy(&datum_expr, CIL_FALSE);
+	free(types);
+	return rc;
+}
+
+static struct cil_avrule *cil_create_avrule(struct cil_symtab_datum *src, struct cil_symtab_datum *tgt, struct cil_list *classperms)
+{
+	struct cil_avrule *new;
+
+	cil_avrule_init(&new);
+	new->is_extended = CIL_FALSE;
+	new->rule_kind = CIL_AVRULE_ALLOWED;
+	new->src_str = src->name;
+	new->src = src;
+	new->tgt_str = tgt->name;
+	new->tgt = tgt;
+	new->perms.classperms = classperms;
+
+	return new;
+}
+
+static struct cil_tree_node *cil_create_and_add_avrule(struct cil_tree_node *curr, struct cil_symtab_datum *src, struct cil_symtab_datum *tgt, struct cil_list *classperms)
+{
+	struct cil_avrule *new_avrule;
+	struct cil_list *new_cp_list;
+
+	if (!src || !tgt) {
+		return curr;
+	}
+
+	cil_classperms_list_copy(&new_cp_list, classperms);
+	new_avrule = cil_create_avrule(src, tgt, new_cp_list);
+	return cil_create_and_insert_node(curr, CIL_AVRULE, new_avrule);
+}
+
+static int cil_remove_permissions_from_special_rule(struct cil_db *db, struct cil_tree_node *curr, struct cil_symtab_datum *s1, struct cil_symtab_datum *t1, struct cil_symtab_datum *s2, struct cil_symtab_datum *t2, struct cil_list *p4, struct cil_symtab_datum *s3, struct cil_symtab_datum *s4)
+{
+	int rc;
+
+	if (t1 == DATUM(db->notselftype)) {
+		if (t2 == DATUM(db->othertype)) {
+			struct cil_symtab_datum *t;
+			rc = cil_create_attribute_all_and_not_d(db, s2, &t);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			curr = cil_create_and_add_avrule(curr, s4, t, p4);
+		} else {
+			struct cil_symtab_datum *s5, *s6, *ta, *tb;
+			rc = cil_create_attribute_d1_and_not_d2(db, s4, t2, &s5);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			rc = cil_create_attribute_d1_and_d2(db, s4, t2, &s6);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			rc = cil_create_attribute_all_and_not_d(db, t2, &ta);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			rc = cil_create_attribute_d1_and_not_d2(db, ta, s4, &tb);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			curr = cil_create_and_add_avrule(curr, s6, ta, p4);
+			curr = cil_create_and_add_avrule(curr, s5, tb, p4);
+			if (cil_datum_cardinality(s5) > 1) {
+				curr = cil_create_and_add_avrule(curr, s5, DATUM(db->othertype), p4);
+			}
+		}
+	} else if (t1 == DATUM(db->othertype)) {
+		curr = cil_create_and_add_avrule(curr, s3, s4, p4);
+		if (t2 == DATUM(db->notselftype)) {
+			/* Nothing else is needed */
+		} else if (t2 == DATUM(db->othertype)) {
+			curr = cil_create_and_add_avrule(curr, s4, s3, p4);
+		} else {
+			struct cil_symtab_datum *s5, *s6, *tc, *td;
+			rc = cil_create_attribute_d1_and_not_d2(db, s4, t2, &s5);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			rc = cil_create_attribute_d1_and_d2(db, s4, t2, &s6);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			rc = cil_create_attribute_d1_and_not_d2(db, s1, t2, &tc);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			rc = cil_create_attribute_d1_and_not_d2(db, s3, t2, &td);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			curr = cil_create_and_add_avrule(curr, s6, tc, p4);
+			curr = cil_create_and_add_avrule(curr, s5, td, p4);
+			if (cil_datum_cardinality(s5) > 1) {
+				curr = cil_create_and_add_avrule(curr, s5, DATUM(db->othertype), p4);
+			}
+		}
+	} else {
+		struct cil_symtab_datum *s8;
+		rc = cil_create_attribute_d1_and_d2(db, s4, t1, &s8);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		curr = cil_create_and_add_avrule(curr, s8, DATUM(db->selftype), p4);
+		if (t2 == DATUM(db->notselftype)) {
+			/* Nothing else is needed */
+		} else { /* t2 == DATUM(db->othertype) */
+			struct cil_symtab_datum *t;
+			rc = cil_create_attribute_d1_and_not_d2(db, t1, s2, &t);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+			curr = cil_create_and_add_avrule(curr, s4, t, p4);
+		}
+	}
+	return SEPOL_OK;
+
+exit:
+	return rc;
+}
+
+static int cil_remove_permissions_from_rule(struct cil_db *db, struct cil_tree_node *allow_node, const struct cil_tree_node *deny_node)
+{
+	struct cil_avrule *allow_rule = allow_node->data;
+	struct cil_deny_rule *deny_rule = deny_node->data;
+	struct cil_symtab_datum *s1 = allow_rule->src;
+	struct cil_symtab_datum *t1 = allow_rule->tgt;
+	struct cil_list *p1 = allow_rule->perms.classperms;
+	struct cil_symtab_datum *s2 = deny_rule->src;
+	struct cil_symtab_datum *t2 = deny_rule->tgt;
+	struct cil_list *p2 = deny_rule->classperms;
+	struct cil_list *p3 = NULL;
+	struct cil_list *p4 = NULL;
+	struct cil_symtab_datum *s3, *s4;
+	struct cil_tree_node *curr = allow_node;
+	int rc;
+
+	cil_classperms_list_andnot(&p3, p1, p2);
+	if (!cil_list_is_empty(p3)) {;
+		curr = cil_create_and_add_avrule(curr, s1, t1, p3);
+	}
+	cil_destroy_classperms_list(&p3);
+	p3 = NULL;
+
+	cil_classperms_list_and(&p4, p1, p2);
+	if (cil_list_is_empty(p4)) {
+		cil_tree_log(allow_node, CIL_ERR, "Allow rule did not match deny rule: No matching class and permissions");
+		cil_tree_log((struct cil_tree_node *)deny_node, CIL_ERR, "Deny rule");
+		rc = SEPOL_ERR;
+		goto exit;
+	}
+
+	rc = cil_create_attribute_d1_and_not_d2(db, s1, s2, &s3);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+	curr = cil_create_and_add_avrule(curr, s3, t1, p4);
+
+	if ((t1 == DATUM(db->selftype) && t2 == DATUM(db->selftype)) ||
+		(t1 == DATUM(db->notselftype) && t2 == DATUM(db->notselftype))) {
+		/* Nothing more needs to be done */
+		rc = SEPOL_OK;
+		goto exit;
+	}
+
+	rc = cil_create_attribute_d1_and_d2(db, s1, s2, &s4);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	if (t1 == DATUM(db->notselftype) || t1 == DATUM(db->othertype) ||
+		t2 == DATUM(db->notselftype) || t2 == DATUM(db->othertype)) {
+		rc = cil_remove_permissions_from_special_rule(db, curr, s1, t1, s2, t2, p4, s3, s4);
+		goto exit;
+	}
+
+	if (t1 == DATUM(db->selftype) && t2 != DATUM(db->selftype)) {
+		struct cil_symtab_datum *s5;
+		rc = cil_create_attribute_d1_and_not_d2(db, s4, t2, &s5);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		curr = cil_create_and_add_avrule(curr, s5, DATUM(db->selftype), p4);
+	} else if (t1 != DATUM(db->selftype) && t2 == DATUM(db->selftype)) {
+		struct cil_symtab_datum *s7, *s8, *t8;
+		rc = cil_create_attribute_d1_and_not_d2(db, s4, t1, &s7);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		rc = cil_create_attribute_d1_and_d2(db, s4, t1, &s8);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		rc = cil_create_attribute_d1_and_not_d2(db, t1, s4, &t8);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		curr = cil_create_and_add_avrule(curr, s7, t1, p4);
+		curr = cil_create_and_add_avrule(curr, s8, t8, p4);
+		if (cil_datum_cardinality(s8) > 1) {
+			curr = cil_create_and_add_avrule(curr, s8, DATUM(db->othertype), p4);
+		}
+	} else {
+		struct cil_symtab_datum *t3;
+		rc = cil_create_attribute_d1_and_not_d2(db, t1, t2, &t3);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		curr = cil_create_and_add_avrule(curr, s4, t3, p4);
+	}
+
+exit:
+	if (p4) {
+		cil_destroy_classperms_list(&p4);
+	}
+	return rc;
+}
+
+static int cil_find_matching_allow_rules(struct cil_list *matching, struct cil_tree_node *start, struct cil_tree_node *deny_node)
+{
+	struct cil_deny_rule *deny_rule = deny_node->data;
+	struct cil_avrule target;
+
+	target.rule_kind = CIL_AVRULE_ALLOWED;
+	target.is_extended = CIL_FALSE;
+	target.src = deny_rule->src;
+	target.tgt = deny_rule->tgt;
+	target.perms.classperms = deny_rule->classperms;
+
+	return cil_find_matching_avrule_in_ast(start, CIL_AVRULE, &target, matching, CIL_FALSE);
+}
+
+static int cil_process_deny_rule(struct cil_db *db, struct cil_tree_node *start, struct cil_tree_node *deny_node)
+{
+	struct cil_list *matching;
+	struct cil_list_item *item;
+	int rc;
+
+	cil_list_init(&matching, CIL_NODE);
+
+	rc = cil_find_matching_allow_rules(matching, start, deny_node);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	cil_list_for_each(item, matching) {
+		struct cil_tree_node *allow_node = item->data;
+		rc = cil_remove_permissions_from_rule(db, allow_node, deny_node);
+		cil_tree_node_remove(allow_node);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+
+	}
+
+exit:
+	cil_list_destroy(&matching, CIL_FALSE);
+	return rc;
+}
+
+static int cil_process_deny_rules(struct cil_db *db, struct cil_tree_node *start, struct cil_list *deny_rules)
+{
+	struct cil_list_item *item;
+	int rc;
+
+	cil_list_for_each(item, deny_rules) {
+		struct cil_tree_node *deny_node = item->data;
+		rc = cil_process_deny_rule(db, start, deny_node);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
+		cil_tree_node_remove(deny_node);
+	}
+
+exit:
+	return rc;
+}
+
+static int __cil_find_deny_rules(struct cil_tree_node *node,  uint32_t *finished, void *extra_args)
+{
+	struct cil_list *deny_rules = extra_args;
+
+	if (node->flavor == CIL_BLOCK) {
+		struct cil_block *block = node->data;
+		if (block->is_abstract == CIL_TRUE) {
+			*finished = CIL_TREE_SKIP_HEAD;
+		}
+	} else if (node->flavor == CIL_MACRO) {
+		*finished = CIL_TREE_SKIP_HEAD;
+	} else if (node->flavor == CIL_DENY_RULE) {
+		cil_list_append(deny_rules, CIL_DENY_RULE, node);
+	}
+	return SEPOL_OK;
+}
+
+int cil_process_deny_rules_in_ast(struct cil_db *db)
+{
+	struct cil_tree_node *start;
+	struct cil_list *deny_rules;
+	int rc = SEPOL_ERR;
+
+	cil_list_init(&deny_rules, CIL_DENY_RULE);
+
+	if (!db) {
+		cil_log(CIL_ERR, "No CIL db provided to process deny rules\n");
+		goto exit;
+	}
+
+	start = db->ast->root;
+	rc = cil_tree_walk(start, __cil_find_deny_rules, NULL, NULL, deny_rules);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "An error occurred while getting deny rules\n");
+		goto exit;
+	}
+
+	rc = cil_process_deny_rules(db, start, deny_rules);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "An error occurred while processing deny rules\n");
+		goto exit;
+	}
+
+exit:
+	cil_list_destroy(&deny_rules, CIL_FALSE);
+	return rc;
+}
diff --git a/libsepol/cil/src/cil_deny.h b/libsepol/cil/src/cil_deny.h
new file mode 100644
index 00000000..f22e8bf1
--- /dev/null
+++ b/libsepol/cil/src/cil_deny.h
@@ -0,0 +1,36 @@
+/*
+ * This file is public domain software, i.e. not copyrighted.
+ *
+ * Warranty Exclusion
+ * ------------------
+ * You agree that this software is a non-commercially developed program
+ * that may contain "bugs" (as that term is used in the industry) and
+ * that it may not function as intended. The software is licensed
+ * "as is". NSA makes no, and hereby expressly disclaims all, warranties,
+ * express, implied, statutory, or otherwise with respect to the software,
+ * including noninfringement and the implied warranties of merchantability
+ * and fitness for a particular purpose.
+ *
+ * Limitation of Liability
+ *-----------------------
+ * In no event will NSA be liable for any damages, including loss of data,
+ * lost profits, cost of cover, or other special, incidental, consequential,
+ * direct or indirect damages arising from the software or the use thereof,
+ * however caused and on any theory of liability. This limitation will apply
+ * even if NSA has been advised of the possibility of such damage. You
+ * acknowledge that this is a reasonable allocation of risk.
+ *
+ * Original author: James Carter
+ */
+
+#ifndef CIL_DENY_H_
+#define CIL_DENY_H_
+
+int cil_classperms_list_match_any(const struct cil_list *cpl1, const struct cil_list *cpl2);
+int cil_classperms_list_match_all(const struct cil_list *cpl1, const struct cil_list *cpl2);
+void cil_classperms_list_copy(struct cil_list **new, const struct cil_list *old);
+void cil_classperms_list_and(struct cil_list **result, const struct cil_list *cpl1, const struct cil_list *cpl2);
+void cil_classperms_list_andnot(struct cil_list **result, const struct cil_list *cpl1, const struct cil_list *cpl2);
+int cil_process_deny_rules_in_ast(struct cil_db *db);
+
+#endif /* CIL_DENY_H_ */
diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c
index a7c66ead..da97a392 100644
--- a/libsepol/cil/src/cil_post.c
+++ b/libsepol/cil/src/cil_post.c
@@ -47,6 +47,7 @@
 #include "cil_policy.h"
 #include "cil_verify.h"
 #include "cil_symtab.h"
+#include "cil_deny.h"
 
 #define GEN_REQUIRE_ATTR "cil_gen_require" /* Also in libsepol/src/module_to_cil.c */
 #define TYPEATTR_INFIX "_typeattr_"        /* Also in libsepol/src/module_to_cil.c */
@@ -2551,6 +2552,12 @@ int cil_post_process(struct cil_db *db)
 		goto exit;
 	}
 
+	rc = cil_process_deny_rules_in_ast(db);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "Failed to process deny rules\n");
+		goto exit;
+	}
+
 	rc = cil_post_verify(db);
 	if (rc != SEPOL_OK) {
 		cil_log(CIL_ERR, "Failed to verify cil database\n");
-- 
2.39.2

[PATCH 5/9 v3] libsepol/cil: Add cil_write_post_ast function

[James Carter]

The function cil_write_post_ast() will write the CIL AST after
post processing is done. Most post processing does not change the
CIL AST, this is where deny rules are processed (because to process
them, type attributes have to have been evaluated.)

When processed, deny rules may add new rules and attributes and the
deny rule itself will be removed from the AST, so using this new
function will show the results of the deny rule processing.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/include/cil/cil.h   |  1 +
 libsepol/cil/src/cil.c           | 50 ++++++++++++++++++++++++++++++++
 libsepol/cil/src/cil_write_ast.h |  1 +
 3 files changed, 52 insertions(+)

diff --git a/libsepol/cil/include/cil/cil.h b/libsepol/cil/include/cil/cil.h
index 482ca522..88e47e79 100644
--- a/libsepol/cil/include/cil/cil.h
+++ b/libsepol/cil/include/cil/cil.h
@@ -64,6 +64,7 @@ extern void cil_write_policy_conf(FILE *out, struct cil_db *db);
 extern int cil_write_parse_ast(FILE *out, cil_db_t *db);
 extern int cil_write_build_ast(FILE *out, cil_db_t *db);
 extern int cil_write_resolve_ast(FILE *out, cil_db_t *db);
+extern int cil_write_post_ast(FILE *out, cil_db_t *db);
 
 enum cil_log_level {
 	CIL_ERR = 1,
diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c
index 4876752a..2021187d 100644
--- a/libsepol/cil/src/cil.c
+++ b/libsepol/cil/src/cil.c
@@ -687,6 +687,56 @@ exit:
 	return rc;
 }
 
+int cil_write_post_ast(FILE *out, cil_db_t *db)
+{
+	int rc = SEPOL_ERR;
+
+	if (db == NULL) {
+		goto exit;
+	}
+
+	cil_log(CIL_INFO, "Building AST from Parse Tree\n");
+	rc = cil_build_ast(db, db->parse->root, db->ast->root);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "Failed to build ast\n");
+		goto exit;
+	}
+
+	cil_log(CIL_INFO, "Destroying Parse Tree\n");
+	cil_tree_destroy(&db->parse);
+
+	cil_log(CIL_INFO, "Resolving AST\n");
+	rc = cil_resolve_ast(db, db->ast->root);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "Failed to resolve ast\n");
+		goto exit;
+	}
+
+	cil_log(CIL_INFO, "Qualifying Names\n");
+	rc = cil_fqn_qualify(db->ast->root);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "Failed to qualify names\n");
+		goto exit;
+	}
+
+	cil_log(CIL_INFO, "Compile post process\n");
+	rc = cil_post_process(db);
+	if (rc != SEPOL_OK ) {
+		cil_log(CIL_ERR, "Post process failed\n");
+		goto exit;
+	}
+
+	cil_log(CIL_INFO, "Writing Post AST\n");
+	rc = cil_write_ast(out, CIL_WRITE_AST_PHASE_POST, db->ast->root);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "Failed to write post ast\n");
+		goto exit;
+	}
+
+exit:
+	return rc;
+}
+
 int cil_build_policydb(cil_db_t *db, sepol_policydb_t **sepol_db)
 {
 	int rc;
diff --git a/libsepol/cil/src/cil_write_ast.h b/libsepol/cil/src/cil_write_ast.h
index 3f4b9d95..6b3274a8 100644
--- a/libsepol/cil/src/cil_write_ast.h
+++ b/libsepol/cil/src/cil_write_ast.h
@@ -38,6 +38,7 @@ enum cil_write_ast_phase {
 	CIL_WRITE_AST_PHASE_PARSE = 0,
 	CIL_WRITE_AST_PHASE_BUILD,
 	CIL_WRITE_AST_PHASE_RESOLVE,
+	CIL_WRITE_AST_PHASE_POST,
 };
 
 void cil_write_ast_node(FILE *out, struct cil_tree_node *node);
-- 
2.39.2

[PATCH 6/9 v3] libsepol: Export the cil_write_post_ast function

[James Carter]

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/src/libsepol.map.in | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
index 844924fc..6ad68f0b 100644
--- a/libsepol/src/libsepol.map.in
+++ b/libsepol/src/libsepol.map.in
@@ -289,3 +289,8 @@ LIBSEPOL_3.4 {
 	sepol_string_to_security_class;
 	sepol_validate_transition_reason_buffer;
 } LIBSEPOL_3.0;
+
+LIBSEPOL_3.5 {
+  global:
+	cil_write_post_ast;
+} LIBSEPOL_3.4;
-- 
2.39.2

[PATCH 7/9 v3] secilc/secil2tree: Add option to write CIL AST after post processing

[James Carter]

This will show the resulting CIL AST after deny rules have been
processed.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 secilc/secil2tree.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/secilc/secil2tree.c b/secilc/secil2tree.c
index e5cdf6bd..ff0fc92b 100644
--- a/secilc/secil2tree.c
+++ b/secilc/secil2tree.c
@@ -45,6 +45,7 @@ enum write_ast_phase {
 	WRITE_AST_PHASE_PARSE = 0,
 	WRITE_AST_PHASE_BUILD,
 	WRITE_AST_PHASE_RESOLVE,
+	WRITE_AST_PHASE_POST,
 };
 
 static __attribute__((__noreturn__)) void usage(const char *prog)
@@ -58,7 +59,7 @@ static __attribute__((__noreturn__)) void usage(const char *prog)
 	printf("                           Blocks, blockinherits, blockabstracts, and\n");
 	printf("                           in-statements will not be allowed.\n");
 	printf("  -A, --ast-phase=<phase>  write AST of phase <phase>. Phase must be parse, \n");
-	printf("                           build, or resolve. (default: resolve)\n");
+	printf("                           build, resolve, or post. (default: resolve)\n");
 	printf("  -v, --verbose            increment verbosity level\n");
 	printf("  -h, --help               display usage information\n");
 	exit(1);
@@ -115,6 +116,8 @@ int main(int argc, char *argv[])
 					write_ast = WRITE_AST_PHASE_BUILD;
 				} else if (!strcasecmp(optarg, "resolve")) {
 					write_ast = WRITE_AST_PHASE_RESOLVE;
+				} else if (!strcasecmp(optarg, "post")) {
+					write_ast = WRITE_AST_PHASE_POST;
 				} else {
 					fprintf(stderr, "Invalid AST phase: %s\n", optarg);
 					usage(argv[0]);
@@ -197,6 +200,9 @@ int main(int argc, char *argv[])
 	case WRITE_AST_PHASE_RESOLVE:
 		rc = cil_write_resolve_ast(file, db);
 		break;
+	case WRITE_AST_PHASE_POST:
+		rc = cil_write_post_ast(file, db);
+		break;
 	}
 
 	if (rc != SEPOL_OK) {
-- 
2.39.2

[PATCH 8/9 v3] secilc/test: Add deny rule tests

[James Carter]

Signed-off-by: James Carter <jwcart2@gmail.com>
---
v3:
 - Completely changed the tests. Now testing use in blocks, optionals,
   booleanifs, and tunableifs.

 secilc/test/deny_rule_test1.cil | 580 ++++++++++++++++++++++++++++++++
 secilc/test/deny_rule_test2.cil | 418 +++++++++++++++++++++++
 2 files changed, 998 insertions(+)
 create mode 100644 secilc/test/deny_rule_test1.cil
 create mode 100644 secilc/test/deny_rule_test2.cil

diff --git a/secilc/test/deny_rule_test1.cil b/secilc/test/deny_rule_test1.cil
new file mode 100644
index 00000000..4a01921a
--- /dev/null
+++ b/secilc/test/deny_rule_test1.cil
@@ -0,0 +1,580 @@
+(class CLASS (PERM))
+(class ca (pa1 pa2 pa3 pa4 pa5 pa6 pa7 pa8 pa9))
+(class cb (pb1 pb2 pb3 pb4 pb5 pb6 pb7 pb8 pb9))
+(class cc (pc1 pc2 pc3 pc4 pc5 pc6 pc7 pc8 pc9))
+(class cd (pd1 pd2 pd3 pd4 pd5 pd6 pd7 pd8 pd9))
+(class ce (pe1 pe2 pe3 pe4 pe5 pe6 pe7 pe8 pe9))
+(class cf (pf1 pf2 pf3 pf4 pf5 pf6 pf7 pf8 pf9))
+(class cg (pg1 pg2 pg3 pg4 pg5 pg6 pg7 pg8 pg9))
+(class ch (ph1 ph2 ph3 ph4 ph5 ph6 ph7 ph8 ph9))
+(class ci (pi1 pi2 pi3 pi4 pi5 pi6 pi7 pi8 pi9))
+(class cj (pj1 pj2 pj3 pj4 pj5 pj6 pj7 pj8 pj9))
+(classorder (CLASS ca cb cc cd ce cf cg ch ci cj))
+(sid SID)
+(sidorder (SID))
+(user USER)
+(role ROLE)
+(type TYPE)
+(category CAT)
+(categoryorder (CAT))
+(sensitivity SENS)
+(sensitivityorder (SENS))
+(sensitivitycategory SENS (CAT))
+(allow TYPE self (CLASS (PERM)))
+(roletype ROLE TYPE)
+(userrole USER ROLE)
+(userlevel USER (SENS))
+(userrange USER ((SENS)(SENS (CAT))))
+(sidcontext SID (USER ROLE TYPE ((SENS)(SENS))))
+
+(classmap cma (mpa1 mpa2))
+(classmapping cma mpa1
+	      (cc (pc1 pc2)))
+(classmapping cma mpa2
+	      (cc (pc3 pc4)))
+
+(classmap cmb (mpb1 mpb2))
+(classmapping cmb mpb1
+	      (cd (pd1 pd2)))
+(classmapping cmb mpb2
+	      (cd (pd3 pd4)))
+
+(classpermission cpsa)
+(classpermissionset cpsa (cd (pd5 pd6)))
+(classpermissionset cpsa (cd (pd7 pd8)))
+
+(classpermission cpsb)
+(classpermissionset cpsb (cd (pd1 pd2)))
+(classpermissionset cpsb (cd (pd3 pd4)))
+
+(type ta)
+(type tb)
+(type tc)
+(type td)
+(type te)
+(type tf)
+(type tg)
+(type th)
+(type ti)
+(type tj)
+(type tk)
+(type tl)
+(type tm)
+(type tn)
+(type to)
+(type tp)
+(type tq)
+(type tr)
+(type ts)
+(type tt)
+(type tu)
+(type tv)
+(type tw)
+(type tx)
+(type ty)
+(type tz)
+
+(typeattribute a_s1)
+(typeattributeset a_s1 (ta tb tc td te tf tg th tk tl tm tn ts tt))
+(typeattribute a_t1)
+(typeattributeset a_t1 (ta tb tc td te tf ti tj tk tl to tp tu tv))
+(typeattribute a_s2)
+(typeattributeset a_s2 (ta tb tc td tg th ti tj tm tn tq tr tw tx))
+(typeattribute a_t2)
+(typeattributeset a_t2 (ta tb te tf tg th ti tj to tp tq tr ty tz))
+(typeattribute a_s3)
+(typeattributeset a_s3 (and a_s1 (not a_s2)))
+(typeattribute a_s4)
+(typeattributeset a_s4 (and a_s1 a_s2))
+(typeattribute a_t3)
+(typeattributeset a_t3 (and a_t1 (not a_t2)))
+
+
+(typeattribute aab)
+(typeattributeset aab (ta tb))
+
+(typeattribute aNab)
+(typeattributeset aNab (and (all) (not (ta tb))))
+
+(typeattribute aNac)
+(typeattributeset aNac (and (all) (not (ta tc))))
+
+(typeattribute aNbc)
+(typeattributeset aNbc (and (all) (not (tb tc))))
+
+(typeattribute acd)
+(typeattributeset acd (tc td))
+
+(typeattribute aNacd)
+(typeattributeset aNacd (and (all) (not (ta tc td))))
+
+(typeattribute aabc)
+(typeattributeset aabc (ta tb tc))
+
+
+; Test 01
+(allow ta tb (ca (pa1)))
+(deny ta tb (ca (pa1)))
+(neverallow ta tb (ca (pa1)))
+
+; Test 02
+(allow ta tb (ca (pa2 pa3)))
+(deny ta tb (ca (pa2)))
+(neverallow ta tb (ca (pa2)))
+; (neverallow ta tb (ca (pa3))) ; This check should fail
+
+; Test 03
+(allow tc td (ca (pa2)))
+(deny tc td (ca (pa2 pa3)))
+(neverallow tc td (ca (pa2 pa3)))
+
+; Test 04
+(allow aab acd (ca (pa4)))
+(deny aab acd (ca (pa4)))
+(neverallow aab acd (ca (pa4)))
+
+; Test 05
+(allow ta tc (ca (pa5)))
+(deny aab acd (ca (pa5)))
+(neverallow aab acd (ca (pa5)))
+
+; Test 06
+(allow aab acd (ca (pa6)))
+(deny ta tc (ca (pa6)))
+(neverallow ta tc (ca (pa6)))
+; (neverallow tb td (ca (pa6))) ; This check should fail
+
+; Test 07
+(allow ta self (ca (pa7)))
+(deny ta self (ca (pa7)))
+(neverallow ta self (ca (pa7)))
+
+; Test 08
+(allow ta self (ca (pa8)))
+(deny ta ta (ca (pa8)))
+(neverallow ta ta (ca (pa8)))
+
+; Test 09
+(allow ta ta (ca (pa9)))
+(deny ta self (ca (pa9)))
+(neverallow ta self (ca (pa9)))
+
+; Test 11
+(allow aab self (cb (pb1)))
+(deny aab self (cb (pb1)))
+(neverallow aab self (cb (pb1)))
+
+; Test 12
+(allow ta self (cb (pb2)))
+(deny aab self (cb (pb2)))
+(neverallow aab self (cb (pb2)))
+
+; Test 13
+(allow aab self (cb (pb3)))
+(deny ta self (cb (pb3)))
+(neverallow ta self (cb (pb3)))
+; (neverallow tb self (cb (pb3))) ; This check should fail
+
+; Test 14
+(allow aab self (cb (pb4)))
+(deny aab aab (cb (pb4)))
+(neverallow aab aab (cb (pb4)))
+
+; Test 15
+(allow aab aab (cb (pb5)))
+(deny aab self (cb (pb5)))
+(neverallow aab self (cb (pb5)))
+; (neverallow ta tb (cb (pb5))) ; This check should fail
+; (neverallow tb ta (cb (pb5))) ; This check should fail
+
+; Test 16
+(allow aab self (cb (pb6)))
+(deny ta ta (cb (pb6)))
+(neverallow ta ta (cb (pb6)))
+; (neverallow tb tb (cb (pb6))) ; This check should fail
+
+; Test 17
+(allow ta ta (cb (pb7)))
+(deny aab self (cb (pb7)))
+(neverallow aab self (cb (pb7)))
+
+; Test 18
+(allow ta self (cb (pb8)))
+(deny aab aab (cb (pb8)))
+(neverallow aab aab (cb (pb8)))
+
+; Test 19
+(allow aab aab (cb (pb9)))
+(deny ta self (cb (pb9)))
+(neverallow ta self (cb (pb9)))
+; (neverallow ta tb (cb (pb9))) ; This check should fail
+; (neverallow tb ta (cb (pb9))) ; This check should fail
+
+; Test 21
+(allow ta tb (cma (mpa1)))
+(deny ta tb (cma (mpa1)))
+(neverallow ta tb (cma (mpa1)))
+
+; Test 22
+(allow tc td (cma (mpa1 mpa2)))
+(deny tc td (cma (mpa1)))
+(neverallow tc td (cma (mpa1)))
+; (neverallow tc td (cma (mpa2))) ; This check should fail
+
+; Test 23
+(allow te tf (cma (mpa1)))
+(deny te tf (cma (mpa1 mpa2)))
+(neverallow te tf (cma (mpa1 mpa2)))
+
+; Test 24
+(allow tg th (cc (pc1)))
+(deny tg th (cma (mpa1)))
+(neverallow tg th (cma (mpa1)))
+
+; Test 25
+(allow ti tj (cma (mpa1)))
+(deny ti tj (cc (pc1)))
+(neverallow ti tj (cc (pc1)))
+; (neverallow ti tj (cc (pc2))) ; This check should fail
+
+; Test 31
+(allow ta tb cpsa)
+(deny ta tb cpsa)
+(neverallow ta tb cpsa)
+
+; Test 32
+(allow tc td cpsa)
+(deny tc td (cd (pd5 pd6)))
+(neverallow tc td (cd (pd5 pd6)))
+; (neverallow tc td (cd (pd7 pd8))) ; This check should fail
+
+; Test 33
+(allow te tf (cd (pd5 pd6)))
+(deny te tf cpsa)
+(neverallow te tf cpsa)
+
+; Test 34
+(allow tg th cpsb)
+(deny tg th (cmb (mpb1 mpb2)))
+(neverallow tg th (cmb (mpb1 mpb2)))
+
+; Test 35
+(allow ti tj (cmb (mpb1 mpb2)))
+(deny ti tj cpsb)
+(neverallow ti tj cpsb)
+
+; Test 36
+(allow tk tl cpsb)
+(deny tk tl (cmb (mpb1)))
+(neverallow tk tl (cmb (mpb1)))
+; (neverallow tk tl (cmb (mpb2))) ; This check should fail
+
+; Test 37
+(allow tm tn (cmb (mpb1)))
+(deny tm tn cpsb)
+(neverallow tm tn cpsb)
+
+; Test 41
+(block b41
+  (allow ta tb (ce (pe1)))
+  (deny ta tb (ce (pe1)))
+  (neverallow ta tb (ce (pe1)))
+)
+
+; Test 42
+(block b42
+  (type ta)
+  (type tb)
+  (type tc)
+  (type td)
+  (type te)
+  (type tf)
+  (type tg)
+  (typeattribute aa)
+  (typeattribute ab)
+  (typeattribute ac)
+  (typeattribute ad)
+  (typeattribute s3)
+  (typeattribute s4)
+  (typeattribute t3)
+  (typeattributeset aa (ta tb td))
+  (typeattributeset ab (ta tc te))
+  (typeattributeset ac (ta tb tf))
+  (typeattributeset ad (ta tc tg))
+  (typeattributeset s3 (and aa (not ac)))
+  (typeattributeset s4 (and aa ac))
+  (typeattributeset t3 (and ab (not ad)))
+  (allow aa ab (ce (pe2)))
+  (deny ac ad (ce (pe2)))
+  (neverallow ac ad (ce (pe2)))
+  ;(neverallow s3 ab (ce (pe2))) ; This check should fail
+  ;(neverallow s4 t3 (ce (pe2))) ; This check should fail
+)
+
+; Test 43
+(block b43
+  (type ta)
+  (type tb)
+  (allow ta tb (ce (pe3)))
+)
+(deny b43.ta b43.tb (ce (pe3)))
+(neverallow b43.ta b43.tb (ce (pe3)))
+
+; Test 44
+(block b44
+  (type ta)
+  (type tb)
+  (allow ta tb (ce (pe4)))
+)
+
+(block b44a
+  (blockinherit b44)
+  (deny ta tb (ce (pe4)))
+  (neverallow ta tb (ce (pe4)))
+)
+
+(block b44b
+  (blockinherit b44)
+)
+(deny b44b.ta b44b.tb (ce (pe4)))
+(neverallow b44b.ta b44b.tb (ce (pe4)))
+
+
+; Test 45
+(optional opt45
+  (allow aab acd (ce (pe5)))
+  (deny aab acd (ce (pe5)))
+  (neverallow aab acd (ce (pe5)))
+)
+
+; Test 46
+(allow ta tc (ce (pe6)))
+(optional opt46
+  (deny aab acd (ce (pe6)))
+  (neverallow aab acd (ce (pe6)))
+)
+
+; Test 47
+(optional opt47
+  (allow aab acd (ce (pe7)))
+)
+(deny ta tc (ce (pe7)))
+(neverallow ta tc (ce (pe7)))
+
+; Test 51
+(boolean b51 true)
+(booleanif b51
+  (true
+    (allow ta tb (cf (pf1)))
+  )
+)
+(deny ta tb (cf (pf1)))
+(neverallow ta tb (cf (pf1)))
+
+; Test 52
+(boolean b52 true)
+(booleanif b52
+  (false
+    (allow ta tb (cf (pf2)))
+  )
+)
+(deny ta tb (cf (pf2)))
+(neverallow ta tb (cf (pf2)))
+
+; Test 53
+(boolean b53 false)
+(booleanif b53
+  (true
+    (allow ta tb (cf (pf3)))
+  )
+)
+(deny ta tb (cf (pf3)))
+(neverallow ta tb (cf (pf3)))
+
+; Test 54
+(boolean b54 false)
+(booleanif b54
+  (true
+    (allow ta tb (cf (pf4)))
+  )
+)
+(deny ta tb (cf (pf4)))
+(neverallow ta tb (cf (pf4)))
+
+; Test 55
+(tunable b55 true)
+(tunableif b55
+  (true
+    (allow ta tb (cf (pf5)))
+  )
+)
+(deny ta tb (cf (pf5)))
+(neverallow ta tb (cf (pf5)))
+
+; Test 56
+(tunable b56 true)
+(tunableif b56
+  (false
+    (allow ta tb (cf (pf6)))
+  )
+)
+(deny ta tb (cf (pf6)))
+(neverallow ta tb (cf (pf6)))
+
+; Test 57
+(tunable b57 false)
+(tunableif b57
+  (true
+    (allow ta tb (cf (pf7)))
+  )
+)
+(deny ta tb (cf (pf7)))
+(neverallow ta tb (cf (pf7)))
+
+; Test 58
+(tunable b58 false)
+(tunableif b58
+  (true
+    (allow ta tb (cf (pf8)))
+  )
+)
+(deny ta tb (cf (pf8)))
+(neverallow ta tb (cf (pf8)))
+
+; Test 61
+(allow a_s1 a_t1 (cg (pg1)))
+(deny a_s2 a_t2 (cg (pg1)))
+(neverallow a_s2 a_t2 (cg (pg1)))
+; (neverallow a_s3 a_t1 (cg (pg1))) ; This check should fail
+; (neverallow a_s4 a_t3 (cg (pg1))) ; This check should fail
+
+; Test 62
+(allow tm a_t1 (cg (pg2)))
+(deny a_s2 a_t2 (cg (pg2)))
+(neverallow a_s2 a_t2 (cg (pg2)))
+; (neverallow tm a_t3 (cg (pg2))) ; This check should fail
+
+; Test 63
+(allow a_s1 to (cg (pg3)))
+(deny a_s2 a_t2 (cg (pg3)))
+(neverallow a_s2 a_t2 (cg (pg3)))
+; (neverallow a_s3 to (cg (pg3))) ; This check should fail
+
+; Test 64
+(allow a_s1 a_t1 (cg (pg4)))
+(deny tm a_t2 (cg (pg4)))
+(neverallow tm a_t2 (cg (pg4)))
+; (neverallow a_s3 a_t1 (cg (pg4))) ; This check should fail
+; (neverallow tm a_t3 (cg (pg4)))   ; This check should fail
+
+; Test 65
+(allow a_s1 a_t1 (cg (pg5)))
+(deny a_s2 to (cg (pg5)))
+(neverallow a_s2 to (cg (pg5)))
+; (neverallow a_s3 a_t1 (cg (pg5))) ; This check should fail
+; (neverallow a_s4 a_t3 (cg (pg5))) ; This check should fail
+
+; Test 71
+(allow a_s1 self (ch (ph1)))
+(deny a_s2 a_t2 (ch (ph1)))
+(neverallow a_s2 a_t2 (ch (ph1)))
+; Below should fail
+(typeattribute a71)
+(typeattributeset a71 (and a_s4 (not a_t2)))
+; (neverallow a_s3 self (ch (ph1))) ; This check should fail
+; (neverallow a71 self (ch (ph1)))  ; This check should fail
+
+; Test 72
+(allow tg self (ch (ph2)))
+(deny a_s2 a_t2 (ch (ph2)))
+(neverallow a_s2 a_t2 (ch (ph2)))
+
+; Test 73
+(allow a_s1 self (ch (ph3)))
+(deny tg a_t2 (ch (ph3)))
+(neverallow tg a_t2 (ch (ph3)))
+; (neverallow a_s3 self (ch (ph3))) ; This check should fail
+
+; Test 74
+(allow a_s1 self (ch (ph4)))
+(deny a_s2 tg (ch (ph4)))
+(neverallow a_s2 tg (ch (ph4)))
+; Below should fail
+(typeattribute a74)
+(typeattributeset a74 (and a_s4 (not tg)))
+; (neverallow a_s3 self (ch (ph4))) ; This check should fail
+; (neverallow a74 self (ch (ph4)))  ; This check should fail
+
+; Test 81
+(allow a_s1 a_t1 (ci (pi1)))
+(deny a_s2 self (ci (pi1)))
+(neverallow a_s2 self (ci (pi1)))
+; Below should fail
+(typeattribute a81a)
+(typeattribute a81b)
+(typeattribute a81c)
+(typeattribute a81b01)
+(typeattribute a81b02)
+(typeattribute a81b03)
+(typeattribute a81b04)
+(typeattributeset a81a (and a_s4 (not a_t1)))
+(typeattributeset a81b (and a_s4 a_t1))
+(typeattributeset a81c (and a_t1 (not a_s4)))
+(typeattributeset a81b01 (and a81b (not ta)))
+(typeattributeset a81b02 (and a81b (not tb)))
+(typeattributeset a81b03 (and a81b (not tc)))
+(typeattributeset a81b04 (and a81b (not td)))
+; (neverallow a_s3 a_t1 (ci (pi1))) ; This check should fail
+; (neverallow a81a a_t1 (ci (pi1))) ; This check should fail
+; (neverallow a81b a81c (ci (pi1))) ; This check should fail
+; (neverallow ta a81b01 (ci (pi1))) ; This check should fail
+; (neverallow tb a81b02 (ci (pi1))) ; This check should fail
+; (neverallow tc a81b03 (ci (pi1))) ; This check should fail
+; (neverallow td a81b04 (ci (pi1))) ; This check should fail
+
+; Test 82
+(allow tc a_t1 (ci (pi2)))
+(deny a_s2 self (ci (pi2)))
+(neverallow a_s2 self (ci (pi2)))
+; Below should fail
+(typeattribute a82)
+(typeattributeset a82 (and a_t1 (not a_s4)))
+; (neverallow tc a82 (ci (pi2))) ; This check should fail
+
+; Test 83
+(allow a_s1 tc (ci (pi3)))
+(deny a_s2 self (ci (pi3)))
+(neverallow a_s2 self (ci (pi3)))
+; Below should fail
+(typeattribute a83)
+(typeattributeset a83 (and a_s4 (not tc)))
+; (neverallow a_s3 tc (ci (pi3))) ; This check should fail
+; (neverallow a83 tc (ci (pi3)))  ; This check should fail
+
+
+; Test 84
+(allow a_s1 a_t1 (ci (pi4)))
+(deny tc self (ci (pi4)))
+(neverallow tc self (ci (pi4)))
+; Below should fail
+(typeattribute a84)
+(typeattributeset a84 (and a_t1 (not a_s4)))
+; (neverallow a_s3 a_t1 (ci (pi4))) ; This check should fail
+; (neverallow tc a84 (ci (pi4)))    ; This check should fail
+
+; Test 91
+(allow a_s1 self (cj (pj1)))
+(deny a_s2 self (cj (pj1)))
+(neverallow a_s2 self (cj (pj1)))
+; (neverallow a_s3 self (cj (pj1))) ; This check should fail
+
+; Test 92
+(allow tm self (cj (pj2)))
+(deny a_s2 self (cj (pj2)))
+(neverallow a_s2 self (cj (pj2)))
+
+; Test 93
+(allow a_s1 self (cj (pj3)))
+(deny tm self (cj (pj3)))
+(neverallow tm self (cj (pj3)))
+; (neverallow a_s3 self (cj (pj3))) ; This check should fail
diff --git a/secilc/test/deny_rule_test2.cil b/secilc/test/deny_rule_test2.cil
new file mode 100644
index 00000000..7750db73
--- /dev/null
+++ b/secilc/test/deny_rule_test2.cil
@@ -0,0 +1,418 @@
+(class CLASS (PERM))
+(class ca (pa1 pa2 pa3 pa4 pa5 pa6 pa7 pa8 pa9))
+(class cb (pb1 pb2 pb3 pb4 pb5 pb6 pb7 pb8 pb9))
+(class cc (pc1 pc2 pc3 pc4 pc5 pc6 pc7 pc8 pc9))
+(class cd (pd1 pd2 pd3 pd4 pd5 pd6 pd7 pd8 pd9))
+(class ce (pe1 pe2 pe3 pe4 pe5 pe6 pe7 pe8 pe9))
+(class cf (pf1 pf2 pf3 pf4 pf5 pf6 pf7 pf8 pf9))
+(class cg (pg1 pg2 pg3 pg4 pg5 pg6 pg7 pg8 pg9))
+(class ch (ph1 ph2 ph3 ph4 ph5 ph6 ph7 ph8 ph9))
+(class ci (pi1 pi2 pi3 pi4 pi5 pi6 pi7 pi8 pi9))
+(class cj (pj1 pj2 pj3 pj4 pj5 pj6 pj7 pj8 pj9))
+(classorder (CLASS ca cb cc cd ce cf cg ch ci cj))
+(sid SID)
+(sidorder (SID))
+(user USER)
+(role ROLE)
+(type TYPE)
+(category CAT)
+(categoryorder (CAT))
+(sensitivity SENS)
+(sensitivityorder (SENS))
+(sensitivitycategory SENS (CAT))
+(allow TYPE self (CLASS (PERM)))
+(roletype ROLE TYPE)
+(userrole USER ROLE)
+(userlevel USER (SENS))
+(userrange USER ((SENS)(SENS (CAT))))
+(sidcontext SID (USER ROLE TYPE ((SENS)(SENS))))
+
+(type ta)
+(type tb)
+(type tc)
+(type td)
+(type te)
+(type tf)
+(type tg)
+(type th)
+(type ti)
+(type tj)
+(type tk)
+(type tl)
+(type tm)
+(type tn)
+(type to)
+(type tp)
+(type tq)
+(type tr)
+(type ts)
+(type tt)
+(type tu)
+(type tv)
+(type tw)
+(type tx)
+(type ty)
+(type tz)
+
+(typeattribute a_s1)
+(typeattributeset a_s1 (ta tb tc td te tf tg th tk tl tm tn ts tt))
+(typeattribute a_t1)
+(typeattributeset a_t1 (ta tb tc td te tf ti tj tk tl to tp tu tv))
+(typeattribute a_s2)
+(typeattributeset a_s2 (ta tb tc td tg th ti tj tm tn tq tr tw tx))
+(typeattribute a_t2)
+(typeattributeset a_t2 (ta tb te tf tg th ti tj to tp tq tr ty tz))
+(typeattribute a_s3)
+(typeattributeset a_s3 (and a_s1 (not a_s2)))
+(typeattribute a_s4)
+(typeattributeset a_s4 (and a_s1 a_s2))
+
+
+(typeattribute aab)
+(typeattributeset aab (ta tb))
+
+(typeattribute aNab)
+(typeattributeset aNab (and (all) (not (ta tb))))
+
+(typeattribute aNac)
+(typeattributeset aNac (and (all) (not (ta tc))))
+
+(typeattribute aNbc)
+(typeattributeset aNbc (and (all) (not (tb tc))))
+
+(typeattribute acd)
+(typeattributeset aab (tc td))
+
+(typeattribute aNacd)
+(typeattributeset aNacd (and (all) (not (ta tc td))))
+
+(typeattribute aabc)
+(typeattributeset aabc (ta tb tc))
+
+
+; Test 01
+(allow ta notself (ca (pa1)))
+(deny ta notself (ca (pa1)))
+(neverallow ta notself (ca (pa1)))
+
+; Test 02
+(allow aab notself (ca (pa2)))
+(deny aab notself (ca (pa2)))
+(neverallow aab notself (ca (pa2)))
+
+; Test 03
+(allow ta notself (ca (pa3)))
+(deny aab notself (ca (pa3)))
+(neverallow aab notself (ca (pa3)))
+
+; Test 04
+(allow aab notself (ca (pa4)))
+(deny ta notself (ca (pa4)))
+(neverallow ta notself (ca (pa4)))
+; (neverallow tb notself (ca (pa4))) ; This check should fail
+
+; Test 11
+(allow ta notself (cb (pb1)))
+(deny ta tb (cb (pb1)))
+(neverallow ta tb (cb (pb1)))
+; (neverallow ta aNab (cb (pb1))) ; This check should fail
+
+; Test 12
+(allow ta tb (cb (pb2)))
+(deny ta notself (cb (pb2)))
+(neverallow ta notself (cb (pb2)))
+
+; Test 13
+(allow aab notself (cb (pb3)))
+(deny ta tb (cb (pb3)))
+(neverallow ta tb (cb (pb3)))
+; (neverallow ta aNab (cb (pb3)))    ; This check should fail
+; (neverallow tb notself (cb (pb3))) ; This check should fail
+
+; Test 14
+(allow ta tb (cb (pb4)))
+(deny aab notself (cb (pb4)))
+(neverallow aab notself (cb (pb4)))
+
+; Test 15
+(allow aab notself (cb (pb5)))
+(deny aab tc (cb (pb5)))
+(neverallow aab tc (cb (pb5)))
+; (neverallow ta aNac (cb (pb5)))    ; This check should fail
+; (neverallow tb aNbc (cb (pb5)))    ; This check should fail
+
+; Test 16
+(allow aab tc (cb (pb6)))
+(deny aab notself (cb (pb6)))
+(neverallow aab notself (cb (pb6)))
+
+; Test 17
+(allow aab notself (cb (pb7)))
+(deny aab acd (cb (pb7)))
+(neverallow aab acd (cb (pb7)))
+; (neverallow aab aNacd (cb (pb7)))    ; This check should fail
+
+; Test 18
+(allow aab acd (cb (pb7)))
+(deny aab notself (cb (pb7)))
+(neverallow aab notself (cb (pb7)))
+
+; Test 21
+(allow aab other (cc (pc1)))
+(deny aab other (cc (pc1)))
+(neverallow aab other (cc (pc1)))
+
+; Test 22
+(allow aabc other (cc (pc2)))
+(deny aab other (cc (pc2)))
+(neverallow aab other (cc (pc2)))
+; (neverallow tc aab (cc (pc2))) ; This check should fail
+
+; Test 23
+(allow aab other (cc (pc3)))
+(deny aabc other (cc (pc3)))
+(neverallow aabc other (cc (pc3)))
+
+; Test 31
+(allow aab other (cd (pd1)))
+(deny aab aab (cd (pd1)))
+(neverallow aab aab (cd (pd1)))
+
+; Test 32
+(allow aab aab (cd (pd2)))
+(deny aab other (cd (pd2)))
+(neverallow aab other (cd (pd2)))
+; (neverallow aab self (cd (pd2))) ; This check should fail
+
+; Test 33
+(allow ta tb (cd (pd3)))
+(deny aab other (cd (pd3)))
+(neverallow aab other (cd (pd3)))
+
+; Test 34
+(allow aab other (cd (pd4)))
+(deny ta tb (cd (pd4)))
+(neverallow ta tb (cd (pd4)))
+; (neverallow tb ta (cd (pd4))) ; This check should fail
+
+
+; Test 61
+(allow a_s1 notself (ce (pe1)))
+(deny a_s2 a_t2 (ce (pe1)))
+(neverallow a_s2 a_t2 (ce (pe1)))
+; Below should fail
+(typeattribute a61a)
+(typeattributeset a61a (and a_s4 (not a_t2)))
+(typeattribute a61b)
+(typeattributeset a61b (and a_s4 a_t2))
+(typeattribute a61c)
+(typeattributeset a61c (and (all) (not a_t2)))
+(typeattribute a61d)
+(typeattributeset a61d (and a61c (not a_s4)))
+; (neverallow a_s3 notself (ce (pe1))) ; This check should fail
+; (neverallow a61a other (ce (pe1)))   ; This check should fail
+; (neverallow a61a a61d (ce (pe1)))    ; This check should fail
+; (neverallow a61b a61c (ce (pe1)))    ; This check should fail
+
+; Test 62
+(allow tg notself (ce (pe2)))
+(deny a_s2 a_t2 (ce (pe2)))
+(neverallow a_s2 a_t2 (ce (pe2)))
+
+; Test 63
+(allow tm notself (ce (pe3)))
+(deny a_s2 a_t2 (ce (pe3)))
+(neverallow a_s2 a_t2 (ce (pe3)))
+
+; Test 64
+(allow a_s1 notself (ce (pe4)))
+(deny tg a_t2 (ce (pe4)))
+(neverallow tg a_t2 (ce (pe4)))
+
+; Test 65
+(allow a_s1 notself (ce (pe5)))
+(deny tm a_t2 (ce (pe5)))
+(neverallow tm a_t2 (ce (pe5)))
+
+; Test 66
+(allow a_s1 notself (ce (pe6)))
+(deny a_s2 tg (ce (pe6)))
+(neverallow a_s2 tg (ce (pe6)))
+; (neverallow a_s3 notself (ce (pe6))) ; This check should fail
+
+; Test 67
+(allow a_s1 notself (ce (pe7)))
+(deny a_s2 ty (ce (pe7)))
+(neverallow a_s2 ty (ce (pe7)))
+; (neverallow a_s3 notself (ce (pe7))) ; This check should fail
+
+; Test 68
+(typeattribute a68)
+(typeattributeset a68 (tg tm))
+(allow a68 notself (ce (pe8)))
+(deny a_s2 a_t2 (ce (pe8)))
+(neverallow a_s2 a_t2 (ce (pe8)))
+
+; Test 71
+(allow a_s1 a_t1 (cf (pf1)))
+(deny a_s2 notself (cf (pf1)))
+(neverallow a_s2 notself (cf (pf1)))
+; Below should fail
+(typeattribute a71a)
+(typeattributeset a71a (and a_s4 a_t1))
+; (neverallow a_s3 a_t1 (cf (pf1))) ; This check should fail
+; (neverallow a71a self (cf (pf1))) ; This check should fail
+
+; Test 72
+(allow tc a_t1 (cf (pf2)))
+(deny a_s2 notself (cf (pf2)))
+(neverallow a_s2 notself (cf (pf2)))
+
+; Test 73
+(allow tm a_t1 (cf (pf3)))
+(deny a_s2 notself (cf (pf3)))
+(neverallow a_s2 notself (cf (pf3)))
+
+; Test 74
+(allow a_s1 a_t1 (cf (pf4)))
+(deny tc notself (cf (pf4)))
+(neverallow tc notself (cf (pf4)))
+
+; Test 75
+(allow a_s1 a_t1 (cf (pf5)))
+(deny tm notself (cf (pf5)))
+(neverallow tm notself (cf (pf5)))
+
+; Test 76
+(allow a_s1 tc (cf (pf6)))
+(deny a_s2 notself (cf (pf6)))
+(neverallow a_s2 notself (cf (pf6)))
+; (neverallow a_s3 tc (cf (pf6))) ; This check should fail
+
+; Test 77
+(allow a_s1 tu (cf (pf7)))
+(deny a_s2 notself (cf (pf7)))
+(neverallow a_s2 notself (cf (pf7)))
+; (neverallow a_s3 tu (cf (pf7))) ; This check should fail
+
+; Test 78
+(typeattribute a78)
+(typeattributeset a78 (tc tm))
+(allow a_s1 a_t1 (cf (pf8)))
+(deny a78 notself (cf (pf8)))
+(neverallow a78 notself (cf (pf8)))
+
+; Test 81
+(allow a_s1 other (cg (pg1)))
+(deny a_s2 a_t2 (cg (pg1)))
+(neverallow a_s2 a_t2 (cg (pg1)))
+; Below should fail
+(typeattribute a81a)
+(typeattributeset a81a (and a_s4 (not a_t2)))
+(typeattribute a81b)
+(typeattributeset a81b (and a_s4 a_t2))
+(typeattribute a81c)
+(typeattributeset a81c (and a_s1 (not a_t2)))
+(typeattribute a81d)
+(typeattributeset a81d (and a_s3 (not a_t2)))
+; (neverallow a_s3 other (cg (pg1))) ; This check should fail
+; (neverallow a81a other (cg (pg1))) ; This check should fail
+; (neverallow a81a a81d (cg (pg1)))  ; This check should fail
+; (neverallow a81b a81c (cg (pg1)))  ; This check should fail
+
+; Test 82
+(allow a_s1 other (cg (pg2)))
+(deny tg a_t2 (cg (pg2)))
+(neverallow tg a_t2 (cg (pg2)))
+
+; Test 83
+(allow a_s1 other (cg (pg3)))
+(deny tm a_t2 (cg (pg3)))
+(neverallow tm a_t2 (cg (pg3)))
+
+; Test 84
+(allow a_s1 other (cg (pg4)))
+(deny a_s2 tg (cg (pg4)))
+(neverallow a_s2 tg (cg (pg4)))
+; (neverallow a_s3 other (cg (pg4))) ; This check should fail
+
+; Test 85
+(allow a_s1 other (cg (pg5)))
+(deny a_s2 ty (cg (pg5)))
+(neverallow a_s2 ty (cg (pg5)))
+; (neverallow a_s3 other (cg (pg5))) ; This check should fail
+
+; Test 86
+(typeattribute a86)
+(typeattributeset a86 (tg tm ts))
+(allow a86 other (cg (pg6)))
+(deny a_s2 a_t2 (cg (pg6)))
+(neverallow a_s2 a_t2 (cg (pg6)))
+
+; Test 91
+(allow a_s1 a_t1 (ch (ph1)))
+(deny a_s2 other (ch (ph1)))
+(neverallow a_s2 other (ch (ph1)))
+; Below should fail
+(typeattribute a91a)
+(typeattributeset a91a (and a_s4 a_t1))
+(typeattribute a91b)
+(typeattributeset a91b (and a_t1 a_s2))
+; (neverallow a_s3 a_t1 (ch (ph1))) ; This check should fail
+; (neverallow a_s4 a91b (ch (ph1))) ; This check should fail
+; (neverallow a91a self (ch (ph1))) ; This check should fail
+
+; Test 92
+(allow tc a_t1 (ch (ph2)))
+(deny a_s2 other (ch (ph2)))
+(neverallow a_s2 other (ch (ph2)))
+
+; Test 93
+(allow tm a_t1 (ch (ph3)))
+(deny a_s2 other (ch (ph3)))
+(neverallow a_s2 other (ch (ph3)))
+
+; Test 94
+(allow a_s1 tc (ch (ph4)))
+(deny a_s2 other (ch (ph4)))
+(neverallow a_s2 other (ch (ph4)))
+; (neverallow a_s3 tc (ch (ph4))) ; This check should fail
+
+; Test 95
+(allow a_s1 tu (ch (ph5)))
+(deny a_s2 other (ch (ph5)))
+(neverallow a_s2 other (ch (ph5)))
+; (neverallow a_s3 tu (ch (ph5))) ; This check should fail
+
+; Test 96
+(typeattribute a96)
+(typeattributeset a96 (tc tm tw))
+(allow a_s1 a_t1 (ch (ph6)))
+(deny a96 other (ch (ph6)))
+(neverallow a96 other (ch (ph6)))
+
+; Test 101
+(allow a_s1 other (ci (pi1)))
+(deny a_s2 other (ci (pi1)))
+(neverallow a_s2 other (ci (pi1)))
+; (neverallow a_s3 other (ci (pi1))) ; This check should fail
+; (neverallow a_s4 a_s3 (ci (pi1)))  ; This check should fail
+
+; Test 102
+(allow a_s1 notself (ci (pi2)))
+(deny a_s2 other (ci (pi2)))
+(neverallow a_s2 other (ci (pi2)))
+; (neverallow a_s3 notself (ci (pi2))) ; This check should fail
+; (neverallow a_s4 a_s3 (ci (pi2)))    ; This check should fail
+
+; Test 103
+(allow a_s1 other (ci (pi3)))
+(deny a_s2 notself (ci (pi3)))
+(neverallow a_s2 notself (ci (pi3)))
+; (neverallow a_s3 other (ci (pi3))) ; This check should fail
+
+; Test 104
+(allow a_s1 notself (ci (pi4)))
+(deny a_s2 notself (ci (pi4)))
+(neverallow a_s2 notself (ci (pi4)))
+; (neverallow a_s3 notself (ci (pi4))) ; This check should fail
-- 
2.39.2

[PATCH 9/9 v3] secilc/docs: Add deny rule to CIL documentation

[James Carter]

Signed-off-by: James Carter <jwcart2@gmail.com>
---
v3: Remove the "*Where" section, since the notself patch series moves all of
    that to beginning of the access vector section before talking about specific
    rules.

 secilc/docs/cil_access_vector_rules.md | 67 ++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)

diff --git a/secilc/docs/cil_access_vector_rules.md b/secilc/docs/cil_access_vector_rules.md
index 034185da..385c4f4a 100644
--- a/secilc/docs/cil_access_vector_rules.md
+++ b/secilc/docs/cil_access_vector_rules.md
@@ -175,6 +175,73 @@ This example will not compile as `type_3` is not allowed to be a source type for
         (allow type_3 self (property_service (set)))
     )
 ```
+deny
+----------
+
+Remove the access rights defined from any matching allow rules. These rules are processed before [`neverallow`](cil_access_vector_rules.md#neverallow) checking.
+
+**Rule definition:**
+
+```secil
+    (deny source_id target_id|self classpermissionset_id ...)
+```
+
+**Where:**
+
+<table>
+<colgroup>
+<col width="27%" />
+<col width="72%" />
+</colgroup>
+<tbody>
+<tr class="odd">
+<td align="left"><p><code>deny</code></p></td>
+<td align="left"><p>The <code>deny</code> keyword.</p></td>
+</tr>
+<tr class="even">
+<td align="left"><p><code>source_id</code></p></td>
+<td align="left"><p>A single previously defined source <code>type</code>, <code>typealias</code> or <code>typeattribute</code> identifier.</p></td>
+</tr>
+<tr class="odd">
+<td align="left"><p><code>target_id</code></p></td>
+<td align="left"><p>A single previously defined target <code>type</code>, <code>typealias</code> or <code>typeattribute</code> identifier.</p>
+<p>The <code>self</code> keyword may be used instead to signify that source and target are the same.</p></td>
+</tr>
+<tr class="even">
+<td align="left"><p><code>classpermissionset_id</code></p></td>
+<td align="left"><p>A single named or anonymous <code>classpermissionset</code> or a single set of <code>classmap</code>/<code>classmapping</code> identifiers.</p></td>
+</tr>
+</tbody>
+</table>
+
+**Example:**
+
+```secil
+    (class class1 (perm1 perm2))
+
+    (type type1)
+    (type type2)
+    (allow type1 type2 (class1 (perm1))) ; Allow-1
+    (deny type1 type2 (class1 (perm1)))  ; Deny-1
+    ; Allow-1 will be complete removed by Deny-1.
+
+    (type type3)
+    (type type4)
+    (allow type3 type4 (class1 (perm1 perm2))) ; Allow-2
+    (deny type3 type4 (class1 (perm1)))        ; Deny-2
+    ; Allow-2 will be removed and replaced with the following when Deny-2 is evaluated
+    ; (allow type3 type4 (class1 (perm2)))
+
+    (type type5)
+    (type type6)
+    (typeattribute attr1)
+    (typeattributeset attr1 (type5 type6))
+    (allow attr1 attr1 (class1 (perm1))) ; Allow-3
+    (deny type5 type6 (class1 (perm1)))  ; Deny-3
+    ; Allow-3 will be removed and replaced with the following when Deny-3 is evaluated
+    ; (allow type6 attr1 (class1 (perm1)))
+    ; (allow type5 type5 (class1 (perm1)))
+```
 
 allowx
 ------
-- 
2.39.2

Re: [PATCH 9/9 v3] secilc/docs: Add deny rule to CIL documentation

[Daniel Burgener]

On 4/13/2023 3:34 PM, James Carter wrote:
> Signed-off-by: James Carter <jwcart2@gmail.com>
> ---
> v3: Remove the "*Where" section, since the notself patch series moves all of
>      that to beginning of the access vector section before talking about specific
>      rules.

It doesn't look to me like the patch matches this description.  I still 
see a "where" section added.

(Presumably the updated patch should also add deny to the "av_flavor" 
portion of the new common "Where" section)

-Daniel

> 
>   secilc/docs/cil_access_vector_rules.md | 67 ++++++++++++++++++++++++++
>   1 file changed, 67 insertions(+)
> 
> diff --git a/secilc/docs/cil_access_vector_rules.md b/secilc/docs/cil_access_vector_rules.md
> index 034185da..385c4f4a 100644
> --- a/secilc/docs/cil_access_vector_rules.md
> +++ b/secilc/docs/cil_access_vector_rules.md
> @@ -175,6 +175,73 @@ This example will not compile as `type_3` is not allowed to be a source type for
>           (allow type_3 self (property_service (set)))
>       )
>   ```
> +deny
> +----------
> +
> +Remove the access rights defined from any matching allow rules. These rules are processed before [`neverallow`](cil_access_vector_rules.md#neverallow) checking.
> +
> +**Rule definition:**
> +
> +```secil
> +    (deny source_id target_id|self classpermissionset_id ...)
> +```
> +
> +**Where:**
> +
> +<table>
> +<colgroup>
> +<col width="27%" />
> +<col width="72%" />
> +</colgroup>
> +<tbody>
> +<tr class="odd">
> +<td align="left"><p><code>deny</code></p></td>
> +<td align="left"><p>The <code>deny</code> keyword.</p></td>
> +</tr>
> +<tr class="even">
> +<td align="left"><p><code>source_id</code></p></td>
> +<td align="left"><p>A single previously defined source <code>type</code>, <code>typealias</code> or <code>typeattribute</code> identifier.</p></td>
> +</tr>
> +<tr class="odd">
> +<td align="left"><p><code>target_id</code></p></td>
> +<td align="left"><p>A single previously defined target <code>type</code>, <code>typealias</code> or <code>typeattribute</code> identifier.</p>
> +<p>The <code>self</code> keyword may be used instead to signify that source and target are the same.</p></td>
> +</tr>
> +<tr class="even">
> +<td align="left"><p><code>classpermissionset_id</code></p></td>
> +<td align="left"><p>A single named or anonymous <code>classpermissionset</code> or a single set of <code>classmap</code>/<code>classmapping</code> identifiers.</p></td>
> +</tr>
> +</tbody>
> +</table>
> +
> +**Example:**
> +
> +```secil
> +    (class class1 (perm1 perm2))
> +
> +    (type type1)
> +    (type type2)
> +    (allow type1 type2 (class1 (perm1))) ; Allow-1
> +    (deny type1 type2 (class1 (perm1)))  ; Deny-1
> +    ; Allow-1 will be complete removed by Deny-1.
> +
> +    (type type3)
> +    (type type4)
> +    (allow type3 type4 (class1 (perm1 perm2))) ; Allow-2
> +    (deny type3 type4 (class1 (perm1)))        ; Deny-2
> +    ; Allow-2 will be removed and replaced with the following when Deny-2 is evaluated
> +    ; (allow type3 type4 (class1 (perm2)))
> +
> +    (type type5)
> +    (type type6)
> +    (typeattribute attr1)
> +    (typeattributeset attr1 (type5 type6))
> +    (allow attr1 attr1 (class1 (perm1))) ; Allow-3
> +    (deny type5 type6 (class1 (perm1)))  ; Deny-3
> +    ; Allow-3 will be removed and replaced with the following when Deny-3 is evaluated
> +    ; (allow type6 attr1 (class1 (perm1)))
> +    ; (allow type5 type5 (class1 (perm1)))
> +```
>   
>   allowx
>   ------

Re: [PATCH 0/9 v3] Add CIL Deny Rule

[Daniel Burgener]

On 4/13/2023 3:34 PM, James Carter wrote:
> This patch series depends on the "Add support for notself and other to
> CIL" patch series from April 12th.
> 
> These patches add a deny rule to CIL. Deny rules will be processed after
> everything except for neverallow rules. Unlike neverallow rules, they
> remove the permissions in the deny rule rather than reporting an error.
> 
> See the individual patches for an explanation of what they do.
> 
> Patches 2, 5, 6, and 7 are unchanged from v2. For the other patches, see
> the patch for a list of the changes from v2.
> 
> James Carter (9):
>    libsepol/cil: Parse and add deny rule to AST, but do not process
>    libsepol/cil: Add cil_list_is_empty macro
>    libsepol/cil: Add cil_tree_node_remove function
>    libsepol/cil: Process deny rules
>    libsepol/cil: Add cil_write_post_ast function
>    libsepol: Export the cil_write_post_ast function
>    secilc/secil2tree: Add option to write CIL AST after post processing
>    secilc/test: Add deny rule tests
>    secilc/docs: Add deny rule to CIL documentation
> 
>   libsepol/cil/include/cil/cil.h         |    1 +
>   libsepol/cil/src/cil.c                 |   68 ++
>   libsepol/cil/src/cil_build_ast.c       |   56 +
>   libsepol/cil/src/cil_build_ast.h       |    2 +
>   libsepol/cil/src/cil_copy_ast.c        |   19 +
>   libsepol/cil/src/cil_copy_ast.h        |    1 +
>   libsepol/cil/src/cil_deny.c            | 1413 ++++++++++++++++++++++++
>   libsepol/cil/src/cil_deny.h            |   36 +
>   libsepol/cil/src/cil_flavor.h          |    1 +
>   libsepol/cil/src/cil_internal.h        |   10 +
>   libsepol/cil/src/cil_list.h            |    3 +
>   libsepol/cil/src/cil_post.c            |    7 +
>   libsepol/cil/src/cil_reset_ast.c       |    8 +
>   libsepol/cil/src/cil_resolve_ast.c     |   48 +
>   libsepol/cil/src/cil_resolve_ast.h     |    1 +
>   libsepol/cil/src/cil_tree.c            |   35 +
>   libsepol/cil/src/cil_tree.h            |    1 +
>   libsepol/cil/src/cil_verify.c          |    9 +
>   libsepol/cil/src/cil_write_ast.c       |   10 +
>   libsepol/cil/src/cil_write_ast.h       |    1 +
>   libsepol/src/libsepol.map.in           |    5 +
>   secilc/docs/cil_access_vector_rules.md |   67 ++
>   secilc/secil2tree.c                    |    8 +-
>   secilc/test/deny_rule_test1.cil        |  580 ++++++++++
>   secilc/test/deny_rule_test2.cil        |  418 +++++++
>   25 files changed, 2807 insertions(+), 1 deletion(-)
>   create mode 100644 libsepol/cil/src/cil_deny.c
>   create mode 100644 libsepol/cil/src/cil_deny.h
>   create mode 100644 secilc/test/deny_rule_test1.cil
>   create mode 100644 secilc/test/deny_rule_test2.cil

For patches 1-8:

Reviewed-by: Daniel Burgener <dburgener@linux.microsoft.com>