[RFC PATCH] libsepol: Add support for checking standalone CIL neverallow rules

["Thiébaud Weksteen" <tweek@google.com>]

This commit refactors the CIL part of libsepol to support validating
standalone "neverallow" assertions provided in CIL format against an
existing binary policy.

Background
==========
Android has the requirement of validating various policies from partners
against the standard AOSP assertions. While this is done at build time,
we also enforce this requirement during certification via the
Compatibility Test Suite.

Until now, this validation was implemented by manually parsing the
neverallow assertions [1]. This approach is brittle and limited (we
currently do not support neverallowxperm assertions).

Design idea
===========
An idea is to reuse the existing parsing in libsepol/cil to parse the
assertions. However, the current API forces the policy to be complete
before being able to run the verification. That is, all the symbols
referred to in the assertions must already be defined.

To solve this issue, the implementation idea of this patch is to attach
an existing kernel policy to the incomplete cil_db_t. This existing
policy is considered a "fallback" policy. When compiling the cil_db_t if
any type, attribute, class or permission is unknown, it is pulled in
from the fallback policy.

An alternative option to this patch is to (1) use checkpolicy to
translate a binary policy into its CIL format; (2) append neverallow
assertions to the CIL policy and (3) rebuild the complete policy. While
this reuses the current tools and API, this requires a lot of
unnecessary translation.

Implementation changes
======================
- Lazy Symbol Import: Modified cil_resolve_ast.c to support a "fallback
  policy". If a symbol (type, attribute, class, or permission) is not
  found in the CIL database during resolution, it now searches a provided
  policydb_t. When found, it dynamically creates CIL datums and inserts
  them into the AST, allowing compilation to proceed without requiring
  the full source policy in CIL format.
- Lazy Attribute Resolution: Updated cil_binary.c to correctly handle
  imported attributes by utilizing their bitmask from the binary policy
  when they have no explicit members in CIL.
- New Public API: Introduced cil_compile_against and
  cil_check_neverallows_assertions. These functions allow a caller to
  set a fallback binary policy for compilation and then run neverallow
  validation against it.
- Validation Utility: Added a new utility cil_neverallow_check in
  libsepol/utils to facilitate testing and validation of this new API.

Feedback
========
This is an RFC and I am looking for feedback on the idea. If a similar
tool can be written without having to increase the API, please let me
know.

I don't know if these new functions (cil_compile_against and
cil_check_neverallows_assertions) are sufficient or how they could be
improved. Could they be made more generic to cover similar use cases?

If the approach seems sensible, more work is likely needed to support
users, roles and others objects. Please let me know what you think is
missing here.

[1] https://cs.android.com/android/platform/superproject/+/android-latest-release:system/sepolicy/tools/sepolicy-analyze/neverallow.c

Signed-off-by: Thiébaud Weksteen <tweek@google.com>
---
 libsepol/cil/include/cil/cil.h        |  16 ++++
 libsepol/cil/src/cil.c                |  68 +++++++++++++++++
 libsepol/cil/src/cil_binary.c         |  15 +++-
 libsepol/cil/src/cil_binary.h         |  24 ++++++
 libsepol/cil/src/cil_internal.h       |   1 +
 libsepol/cil/src/cil_resolve_ast.c    | 102 +++++++++++++++++++++++--
 libsepol/src/libsepol.map.in          |   4 +-
 libsepol/utils/Makefile               |   2 +-
 libsepol/utils/cil_neverallow_check.c | 103 ++++++++++++++++++++++++++
 9 files changed, 324 insertions(+), 11 deletions(-)
 create mode 100644 libsepol/utils/cil_neverallow_check.c

diff --git a/libsepol/cil/include/cil/cil.h b/libsepol/cil/include/cil/cil.h
index 88e47e79..51a999b9 100644
--- a/libsepol/cil/include/cil/cil.h
+++ b/libsepol/cil/include/cil/cil.h
@@ -81,6 +81,22 @@ extern void cil_log(enum cil_log_level lvl, const char *msg, ...);
 
 extern void cil_set_malloc_error_handler(void (*handler)(void));
 
+/*
+ * Compile a partial policy (db), importing types, attributes,
+ * classes and permissions from sepol_db if not found.
+ */
+extern int cil_compile_against(cil_db_t *db, sepol_policydb_t *sepol_db);
+
+/*
+ * Validate neverallow assertions in a policy.
+ *
+ * This step is usually performed implicitly within cil_build_policydb.
+ * However, there might be some interest in validating these assertions
+ * without a full build.
+ */
+extern int cil_check_neverallows_assertions(cil_db_t *db);
+
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c
index 9662cf45..b323f144 100644
--- a/libsepol/cil/src/cil.c
+++ b/libsepol/cil/src/cil.c
@@ -467,6 +467,7 @@ void cil_db_init(struct cil_db **db)
 	(*db)->qualified_names = CIL_FALSE;
 	(*db)->target_platform = SEPOL_TARGET_SELINUX;
 	(*db)->policy_version = POLICYDB_VERSION_MAX;
+	(*db)->fallback_pdb = NULL;
 }
 
 static void cil_declared_strings_list_destroy(struct cil_list **strings)
@@ -3001,3 +3002,70 @@ void cil_src_info_init(struct cil_src_info **info)
 	(*info)->hll_line = 0;
 	(*info)->path = NULL;
 }
+
+struct cil_check_neverallow_args {
+	const struct cil_db *db;
+	policydb_t *pdb;
+	int violation;
+};
+
+static int __cil_check_neverallow_helper(struct cil_tree_node *node, uint32_t *finished __attribute__((unused)), void *extra_args)
+{
+	struct cil_check_neverallow_args *args = extra_args;
+	int rc = SEPOL_OK;
+
+	if (node->flavor == CIL_AVRULE) {
+		struct cil_avrule *rule = node->data;
+		if (rule->rule_kind == CIL_AVRULE_NEVERALLOW) {
+			int violation = CIL_FALSE;
+			rc = cil_check_neverallow(args->db, args->pdb, node, &violation);
+			if (rc != SEPOL_OK) {
+				return rc;
+			}
+			if (violation == CIL_TRUE) {
+				args->violation = CIL_TRUE;
+			}
+		}
+	}
+	return SEPOL_OK;
+}
+
+int cil_compile_against(cil_db_t *db, sepol_policydb_t *sepol_db)
+{
+	int rc;
+
+	if (db == NULL || sepol_db == NULL) {
+		return SEPOL_ERR;
+	}
+
+	db->fallback_pdb = &sepol_db->p;
+
+	rc = cil_compile(db);
+
+	return rc;
+}
+
+int cil_check_neverallows_assertions(cil_db_t *db)
+{
+	int rc;
+	struct cil_check_neverallow_args extra_args;
+
+	if (db == NULL || db->fallback_pdb == NULL) {
+		return SEPOL_ERR;
+	}
+
+	extra_args.db = db;
+	extra_args.pdb = db->fallback_pdb;
+	extra_args.violation = CIL_FALSE;
+
+	rc = cil_tree_walk(db->ast->root, __cil_check_neverallow_helper, NULL, NULL, &extra_args);
+	if (rc != SEPOL_OK) {
+		return rc;
+	}
+
+	if (extra_args.violation == CIL_TRUE) {
+		return SEPOL_ERR;
+	}
+
+	return SEPOL_OK;
+}
diff --git a/libsepol/cil/src/cil_binary.c b/libsepol/cil/src/cil_binary.c
index 74ec3cd5..a1485560 100644
--- a/libsepol/cil/src/cil_binary.c
+++ b/libsepol/cil/src/cil_binary.c
@@ -4843,6 +4843,17 @@ static int __cil_add_sepol_type(policydb_t *pdb, const struct cil_db *db, struct
 		ebitmap_node_t *tnode;
 		unsigned int i;
 		struct cil_typeattribute *attr = (struct cil_typeattribute *)datum;
+
+		if (attr->types == NULL) {
+			rc = __cil_get_sepol_type_datum(pdb, datum, &sepol_datum);
+			if (rc != SEPOL_OK) goto exit;
+			if (sepol_datum->flavor != TYPE_ATTRIB) {
+				rc = SEPOL_ERR;
+				goto exit;
+			}
+			return ebitmap_union(map, &pdb->attr_type_map[sepol_datum->s.value - 1]);
+		}
+
 		ebitmap_for_each_positive_bit(attr->types, tnode, i) {
 			datum = DATUM(db->val_to_type[i]);
 			rc = __cil_get_sepol_type_datum(pdb, datum, &sepol_datum);
@@ -5032,7 +5043,7 @@ exit:
 	return rc;
 }
 
-static int cil_check_neverallow(const struct cil_db *db, policydb_t *pdb, struct cil_tree_node *node, int *violation)
+int cil_check_neverallow(const struct cil_db *db, policydb_t *pdb, struct cil_tree_node *node, int *violation)
 {
 	int rc = SEPOL_OK;
 	struct cil_avrule *cil_rule = node->data;
@@ -5127,7 +5138,7 @@ exit:
 	return rc;
 }
 
-static int cil_check_neverallows(const struct cil_db *db, policydb_t *pdb, struct cil_list *neverallows, int *violation)
+int cil_check_neverallows(const struct cil_db *db, policydb_t *pdb, struct cil_list *neverallows, int *violation)
 {
 	int rc = SEPOL_OK;
 	struct cil_list_item *item;
diff --git a/libsepol/cil/src/cil_binary.h b/libsepol/cil/src/cil_binary.h
index e6826221..8b20e45e 100644
--- a/libsepol/cil/src/cil_binary.h
+++ b/libsepol/cil/src/cil_binary.h
@@ -341,6 +341,30 @@ int cil_sepol_level_define(policydb_t *pdb, struct cil_sens *cil_sens);
  */
 int cil_rangetransition_to_policydb(policydb_t *pdb, const struct cil_db *db, struct cil_rangetransition *rangetrans);
 
+/**
+ * Check a neverallow rule against a policydb.
+ *
+ * @param[in] db The cil database.
+ * @param[in] pdb The policy database to check against.
+ * @param[in] node The AST node containing the neverallow rule.
+ * @param[out] violation Set to CIL_TRUE if a violation is found.
+ *
+ * @return SEPOL_OK upon success or an error otherwise.
+ */
+int cil_check_neverallow(const struct cil_db *db, policydb_t *pdb, struct cil_tree_node *node, int *violation);
+
+/**
+ * Check a list of neverallow rules against a policydb.
+ *
+ * @param[in] db The cil database.
+ * @param[in] pdb The policy database to check against.
+ * @param[in] neverallows The list of AST nodes containing neverallow rules.
+ * @param[out] violation Set to CIL_TRUE if any violation is found.
+ *
+ * @return SEPOL_OK upon success or an error otherwise.
+ */
+int cil_check_neverallows(const struct cil_db *db, policydb_t *pdb, struct cil_list *neverallows, int *violation);
+
 /**
  * Insert cil ibpkeycon structure into sepol policydb.
  * The function is given a structure containing the sorted ibpkeycons and
diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h
index ae3ab824..fcfa7b0d 100644
--- a/libsepol/cil/src/cil_internal.h
+++ b/libsepol/cil/src/cil_internal.h
@@ -336,6 +336,7 @@ struct cil_db {
 	int qualified_names;
 	int target_platform;
 	int policy_version;
+	policydb_t *fallback_pdb;
 };
 
 struct cil_root {
diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c
index bcac4026..75a790e7 100644
--- a/libsepol/cil/src/cil_resolve_ast.c
+++ b/libsepol/cil/src/cil_resolve_ast.c
@@ -68,17 +68,18 @@ struct cil_args_resolve {
 	struct cil_list *abstract_blocks;
 };
 
-static int __cil_resolve_perms(symtab_t *class_symtab, symtab_t *common_symtab, struct cil_list *perm_strs, struct cil_list **perm_datums, enum cil_flavor class_flavor)
+static int __cil_resolve_perms(struct cil_db *db, struct cil_class *class, symtab_t *common_symtab, struct cil_list *perm_strs, struct cil_list **perm_datums, enum cil_flavor class_flavor)
 {
 	int rc = SEPOL_ERR;
 	struct cil_list_item *curr;
+	symtab_t *class_symtab = &class->perms;
 
 	cil_list_init(perm_datums, perm_strs->flavor);
 
 	cil_list_for_each(curr, perm_strs) {
 		if (curr->flavor == CIL_LIST) {
 			struct cil_list *sub_list;
-			rc = __cil_resolve_perms(class_symtab, common_symtab, curr->data, &sub_list, class_flavor);
+			rc = __cil_resolve_perms(db, class, common_symtab, curr->data, &sub_list, class_flavor);
 			if (rc != SEPOL_OK) {
 				cil_log(CIL_ERR, "Failed to resolve permission list\n");
 				goto exit;
@@ -92,6 +93,37 @@ static int __cil_resolve_perms(symtab_t *class_symtab, symtab_t *common_symtab,
 					rc = cil_symtab_get_datum(common_symtab, curr->data, &perm_datum);
 				}
 			}
+
+			if (rc == SEPOL_ENOENT && db->fallback_pdb != NULL) {
+				/* Try fallback to policydb */
+				if (class != NULL && FLAVOR(class) == CIL_CLASS) {
+					class_datum_t *sepol_class = hashtab_search(db->fallback_pdb->p_classes.table, DATUM(class)->fqn);
+					if (sepol_class != NULL) {
+						perm_datum_t *sepol_perm = hashtab_search(sepol_class->permissions.table, curr->data);
+						if (sepol_perm == NULL && sepol_class->comdatum != NULL) {
+							sepol_perm = hashtab_search(sepol_class->comdatum->permissions.table, curr->data);
+						}
+
+						if (sepol_perm != NULL) {
+							struct cil_perm *cil_perm = NULL;
+							struct cil_tree_node *node = NULL;
+							cil_perm_init(&cil_perm);
+							cil_tree_node_init(&node);
+							node->data = cil_perm;
+							node->flavor = CIL_PERM;
+							node->parent = NODE(class);
+							rc = cil_symtab_insert(class_symtab, curr->data, (struct cil_symtab_datum *)cil_perm, node);
+							if (rc == SEPOL_OK) {
+								perm_datum = (struct cil_symtab_datum *)cil_perm;
+							} else {
+								cil_destroy_data(&node->data, node->flavor);
+								cil_tree_node_destroy(&node);
+							}
+						}
+					}
+				}
+			}
+
 			if (rc != SEPOL_OK) {
 				if (class_flavor == CIL_MAP_CLASS) {
 					cil_log(CIL_ERR, "Failed to resolve permission %s for map class\n", (char*)curr->data);
@@ -137,7 +169,7 @@ int cil_resolve_classperms(struct cil_tree_node *current, struct cil_classperms
 
 	cp->class = class;
 
-	rc = __cil_resolve_perms(&class->perms, common_symtab, cp->perm_strs, &cp->perms, FLAVOR(datum));
+	rc = __cil_resolve_perms(db, class, common_symtab, cp->perm_strs, &cp->perms, FLAVOR(datum));
 	if (rc != SEPOL_OK) {
 		goto exit;
 	}
@@ -4188,9 +4220,11 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current)
 		}
 	}
 
-	rc = __cil_verify_initsids(db->sidorder);
-	if (rc != SEPOL_OK) {
-		goto exit;
+	if (db->fallback_pdb == NULL) {
+		rc = __cil_verify_initsids(db->sidorder);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
 	}
 
 	rc = SEPOL_OK;
@@ -4211,8 +4245,62 @@ exit:
 static int __cil_resolve_name_with_root(struct cil_db *db, char *name, enum cil_sym_index sym_index, struct cil_symtab_datum **datum)
 {
 	symtab_t *symtab = &((struct cil_root *)db->ast->root->data)->symtab[sym_index];
+	int rc = cil_symtab_get_datum(symtab, name, datum);
+
+	if (rc != SEPOL_OK && db->fallback_pdb != NULL) {
+		void *sepol_datum = NULL;
+		struct cil_tree_node *node = NULL;
+		struct cil_symtab_datum *new_datum = NULL;
+
+		enum cil_flavor flavor = CIL_NONE;
+
+		switch (sym_index) {
+		case CIL_SYM_TYPES:
+			sepol_datum = hashtab_search(db->fallback_pdb->p_types.table, name);
+			if (sepol_datum != NULL) {
+				type_datum_t *type = sepol_datum;
+				if (type->flavor == TYPE_ATTRIB) {
+					struct cil_typeattribute *cil_attr = NULL;
+					cil_typeattribute_init(&cil_attr);
+					new_datum = (struct cil_symtab_datum *)cil_attr;
+					flavor = CIL_TYPEATTRIBUTE;
+				} else {
+					struct cil_type *cil_type = NULL;
+					cil_type_init(&cil_type);
+					new_datum = (struct cil_symtab_datum *)cil_type;
+					flavor = CIL_TYPE;
+				}
+			}
+			break;
+		case CIL_SYM_CLASSES:
+			sepol_datum = hashtab_search(db->fallback_pdb->p_classes.table, name);
+			if (sepol_datum != NULL) {
+				struct cil_class *cil_class = NULL;
+				cil_class_init(&cil_class);
+				new_datum = (struct cil_symtab_datum *)cil_class;
+				flavor = CIL_CLASS;
+			}
+			break;
+		default:
+			break;
+		}
 
-	return cil_symtab_get_datum(symtab, name, datum);
+		if (new_datum != NULL) {
+			cil_tree_node_init(&node);
+			node->data = new_datum;
+			node->flavor = flavor;
+			node->parent = db->ast->root;
+			rc = cil_symtab_insert(symtab, name, new_datum, node);
+			if (rc == SEPOL_OK) {
+				*datum = new_datum;
+			} else {
+				cil_destroy_data(&node->data, node->flavor);
+				cil_tree_node_destroy(&node);
+			}
+		}
+	}
+
+	return rc;
 }
 
 static int __cil_resolve_name_with_parents(struct cil_tree_node *node, char *name, enum cil_sym_index sym_index, struct cil_symtab_datum **datum)
diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
index e5e6608c..3440fe98 100644
--- a/libsepol/src/libsepol.map.in
+++ b/libsepol/src/libsepol.map.in
@@ -290,7 +290,9 @@ LIBSEPOL_3.4 {
 	sepol_validate_transition_reason_buffer;
 } LIBSEPOL_3.0;
 
-LIBSEPOL_3.6 {
+LIBSEPOL_3.11 {
   global:
 	cil_write_post_ast;
+	cil_compile_against;
+	cil_check_neverallows_assertions;
 } LIBSEPOL_3.4;
diff --git a/libsepol/utils/Makefile b/libsepol/utils/Makefile
index a8bedf2e..67eebd16 100644
--- a/libsepol/utils/Makefile
+++ b/libsepol/utils/Makefile
@@ -3,7 +3,7 @@ PREFIX ?= /usr
 BINDIR ?= $(PREFIX)/bin
 
 CFLAGS ?= -Wall -Werror
-override CFLAGS += -I../include
+override CFLAGS += -I../include -I../cil/include
 override LDFLAGS += -L../src
 override LDLIBS += -lsepol
 
diff --git a/libsepol/utils/cil_neverallow_check.c b/libsepol/utils/cil_neverallow_check.c
new file mode 100644
index 00000000..0dae047c
--- /dev/null
+++ b/libsepol/utils/cil_neverallow_check.c
@@ -0,0 +1,103 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include <sepol/policydb.h>
+#include <cil/cil.h>
+
+int main(int argc, char *argv[])
+{
+	if (argc < 3) {
+		fprintf(stderr, "Usage: %s <policy_file> <neverallow_cil_file>\n", argv[0]);
+		return -1;
+	}
+
+	const char *policy_file = argv[1];
+	const char *neverallow_file = argv[2];
+
+	sepol_policydb_t *pdb = NULL;
+	sepol_policy_file_t *pf = NULL;
+	FILE *fp;
+
+	fp = fopen(policy_file, "re");
+	if (!fp) {
+		perror("fopen policy_file");
+		return -1;
+	}
+
+	if (sepol_policy_file_create(&pf) != 0) {
+		fprintf(stderr, "sepol_policy_file_create failed\n");
+		fclose(fp);
+		return -1;
+	}
+	sepol_policy_file_set_fp(pf, fp);
+
+	if (sepol_policydb_create(&pdb) != 0) {
+		fprintf(stderr, "sepol_policydb_create failed\n");
+		sepol_policy_file_free(pf);
+		fclose(fp);
+		return -1;
+	}
+
+	if (sepol_policydb_read(pdb, pf) != 0) {
+		fprintf(stderr, "sepol_policydb_read failed\n");
+		sepol_policydb_free(pdb);
+		sepol_policy_file_free(pf);
+		fclose(fp);
+		return -1;
+	}
+	fclose(fp);
+	sepol_policy_file_free(pf);
+
+	struct cil_db *db;
+	cil_db_init(&db);
+
+	int fd = open(neverallow_file, O_RDONLY);
+	if (fd < 0) {
+		perror("open neverallow_file");
+		sepol_policydb_free(pdb);
+		cil_db_destroy(&db);
+		return -1;
+	}
+	struct stat sb;
+	if (fstat(fd, &sb) < 0) {
+		perror("fstat neverallow_file");
+		close(fd);
+		sepol_policydb_free(pdb);
+		cil_db_destroy(&db);
+		return -1;
+	}
+	char *text = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	close(fd);
+
+	if (cil_add_file(db, neverallow_file, text, sb.st_size)) {
+		fprintf(stderr, "cil_add_file failed\n");
+		munmap(text, sb.st_size);
+		sepol_policydb_free(pdb);
+		cil_db_destroy(&db);
+		return -1;
+	}
+
+	int rc = cil_compile_against(db, pdb);
+	if (rc != SEPOL_OK) {
+		fprintf(stderr, "cil_compile_against failed\n");
+	} else {
+		rc = cil_check_neverallows_assertions(db);
+		if (rc == SEPOL_OK) {
+			printf("Neverallow check passed (no violations)\n");
+		} else {
+			printf("Neverallow check failed (violation found or error)\n");
+		}
+	}
+
+	munmap(text, sb.st_size);
+	cil_db_destroy(&db);
+	sepol_policydb_free(pdb);
+
+	return (rc == SEPOL_OK) ? 0 : 1;
+}
-- 
2.53.0.1118.gaef5881109-goog