[PATCH 0/2 v2] libsepol and checkpolicy: Add ability to expand some attributes in binary policy

[PATCH 0/2 v2] libsepol and checkpolicy: Add ability to expand some attributes in binary policy

[James Carter]

The number of type attributes included in the binary policy is becomming a performance issue in some cases.

This patch set more aggressives removes attributes and gives the options to expand and remove all auto-generated attributes and all attributes with fewer than a given amount of attributes assigned.

Comparison of the number of attributes remaining in the binary policy
     mls   normal  android
org  310     286     255
old  268     251     130 
max   71      20      17
min  226     173     119
def  223     170      80
gen  220     170      46
u5   164     112      59 

Org - Number of attributes in the CIL policy 
Old - Results without this patch set
Max - Remove the maximum number of attributes: "-G -X 9999"
Min - Remove the minimum number of attributes: "-X 0"
Def - The new defaults for CIL
Gen - Just removing auto-generated attributes: "-G"
U5  - Remove attributes with less than five members: "-X 5"

v2:
- Use "--expand-generated" and "--expand-size" as options for consistency.
- Fixed bug in cil_post.c:__cil_post_db_attr_helper() where cil_typeattribute_used() would not be called if the attribute type bitmap was already created.

James Carter (2):
  libsepol/cil: Add ability to expand some attributes in binary policy
  secilc: Add options to control the expansion of attributes

 libsepol/cil/include/cil/cil.h     |   2 +
 libsepol/cil/src/cil.c             |  12 ++
 libsepol/cil/src/cil_binary.c      | 253 +++++++++++++++++++++++++++----------
 libsepol/cil/src/cil_internal.h    |   7 +-
 libsepol/cil/src/cil_post.c        |  32 +++--
 libsepol/cil/src/cil_resolve_ast.c |  25 ++--
 libsepol/src/libsepol.map.in       |   2 +
 secilc/secil2conf.c                |   2 +
 secilc/secilc.8.xml                |  10 ++
 secilc/secilc.c                    |  31 ++++-
 10 files changed, 275 insertions(+), 101 deletions(-)

-- 
2.7.4

[PATCH 1/2 v2] libsepol/cil: Add ability to expand some attributes in binary policy

[James Carter]

Originally, all type attributes were expanded when building a binary
policy. As the policy grew, binary policy sizes became too large, so
changes were made to keep attributes in the binary policy to minimize
policy size.

Keeping attributes works well as long as each type does not have too
many attributes. If an access check fails for types t1 and t2, then
additional checks must be made for every attribute that t1 is a member
of against t2 and all the attributes that t2 is a member of. This is
O(n*m) behavior and there are cases now where this is becoming a
performance issue.

Attributes are more aggressively removed than before. An attribute
will now be removed if it only appears in rules where attributes are
always expanded (typetransition, typechange, typemember, roletransition,
rangetransition, roletype, and AV Rules with self).

Attributes that are used in constraints are always kept because the
attribute name is stored for debugging purposes in the binary policy.

Attributes that are used in neverallow rules, but not in other AV rules,
will be kept unless the attribute is auto-generated.

Attributes that are only used in AV rules other than neverallow rules
are kept unless the number of types assigned to them is less than the
value of attrs_expand_size in the CIL db. The default is 1, which means
that any attribute that has no types assigned to it will be expanded (and
the rule removed from the policy), which is CIL's current behavior. The
value can be set using the function cil_set_attrs_expand_size().

Auto-generated attributes that are used only in neverallow rules are
always expanded. The rest are kept by default, but if the value of
attrs_expand_generated in the CIL db is set to true, they will be
expanded. The function cil_set_attrs_expand_generated() can be used
to set the value.

When creating the binary policy, CIL will expand all attributes that
are being removed and it will expand all attributes with less members
than the value specified by attrs_expand_size. So even if an attribute
is used in a constraint or neverallow and the attribute itself will be
included in the binary policy, it will be expanded when writing AV
rules if it has less members than attrs_expand_size.

Signed-off-by: James Carter <jwcart2@tycho.nsa.gov>
---
 libsepol/cil/include/cil/cil.h     |   2 +
 libsepol/cil/src/cil.c             |  12 ++
 libsepol/cil/src/cil_binary.c      | 253 +++++++++++++++++++++++++++----------
 libsepol/cil/src/cil_internal.h    |   7 +-
 libsepol/cil/src/cil_post.c        |  32 +++--
 libsepol/cil/src/cil_resolve_ast.c |  25 ++--
 libsepol/src/libsepol.map.in       |   2 +
 7 files changed, 233 insertions(+), 100 deletions(-)

diff --git a/libsepol/cil/include/cil/cil.h b/libsepol/cil/include/cil/cil.h
index c4a6fb9..4507892 100644
--- a/libsepol/cil/include/cil/cil.h
+++ b/libsepol/cil/include/cil/cil.h
@@ -50,6 +50,8 @@ extern void cil_set_disable_neverallow(cil_db_t *db, int disable_neverallow);
 extern void cil_set_preserve_tunables(cil_db_t *db, int preserve_tunables);
 extern int cil_set_handle_unknown(cil_db_t *db, int handle_unknown);
 extern void cil_set_mls(cil_db_t *db, int mls);
+extern void cil_set_attrs_expand_generated(struct cil_db *db, int attrs_expand_generated);
+extern void cil_set_attrs_expand_size(struct cil_db *db, unsigned attrs_expand_size);
 extern void cil_set_target_platform(cil_db_t *db, int target_platform);
 extern void cil_set_policy_version(cil_db_t *db, int policy_version);
 extern void cil_write_policy_conf(FILE *out, struct cil_db *db);
diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c
index 7c40ad0..a64c528 100644
--- a/libsepol/cil/src/cil.c
+++ b/libsepol/cil/src/cil.c
@@ -282,6 +282,8 @@ void cil_db_init(struct cil_db **db)
 
 	(*db)->disable_dontaudit = CIL_FALSE;
 	(*db)->disable_neverallow = CIL_FALSE;
+	(*db)->attrs_expand_generated = CIL_FALSE;
+	(*db)->attrs_expand_size = 1;
 	(*db)->preserve_tunables = CIL_FALSE;
 	(*db)->handle_unknown = -1;
 	(*db)->mls = -1;
@@ -1629,6 +1631,16 @@ void cil_set_disable_neverallow(struct cil_db *db, int disable_neverallow)
 	db->disable_neverallow = disable_neverallow;
 }
 
+void cil_set_attrs_expand_generated(struct cil_db *db, int attrs_expand_generated)
+{
+	db->attrs_expand_generated = attrs_expand_generated;
+}
+
+void cil_set_attrs_expand_size(struct cil_db *db, unsigned attrs_expand_size)
+{
+	db->attrs_expand_size = attrs_expand_size;
+}
+
 void cil_set_preserve_tunables(struct cil_db *db, int preserve_tunables)
 {
 	db->preserve_tunables = preserve_tunables;
diff --git a/libsepol/cil/src/cil_binary.c b/libsepol/cil/src/cil_binary.c
index ac18c4e..e1481a4 100644
--- a/libsepol/cil/src/cil_binary.c
+++ b/libsepol/cil/src/cil_binary.c
@@ -567,7 +567,7 @@ int cil_typeattribute_to_policydb(policydb_t *pdb, struct cil_typeattribute *cil
 	char *key = NULL;
 	type_datum_t *sepol_attr = NULL;
 
-	if (cil_attr->used == CIL_FALSE) {
+	if (!cil_attr->used) {
 		return SEPOL_OK;		
 	}
 
@@ -632,7 +632,7 @@ int cil_typeattribute_to_bitmap(policydb_t *pdb, const struct cil_db *db, struct
 	ebitmap_node_t *tnode;
 	unsigned int i;
 
-	if (cil_attr->used == CIL_FALSE) {
+	if (!cil_attr->used) {
 		return SEPOL_OK;
 	}
 
@@ -1429,46 +1429,20 @@ exit:
 	return rc;
 }
 
-static int __cil_type_datum_is_unused_attrib(struct cil_symtab_datum *src)
+static int __cil_should_expand_attribute( const struct cil_db *db, struct cil_symtab_datum *datum)
 {
-	struct cil_tree_node *node = NULL;
-	struct cil_typeattribute *attrib = NULL;
+	struct cil_tree_node *node;
+	struct cil_typeattribute *attr;
 
-	if (src->fqn == CIL_KEY_SELF) {
-		return CIL_FALSE;
-	}
-
-	node = NODE(src);
+	node = NODE(datum);
 
 	if (node->flavor != CIL_TYPEATTRIBUTE) {
 		return CIL_FALSE;
 	}
 
-	attrib = (struct cil_typeattribute *) src;
-	return ebitmap_cardinality(attrib->types) == 0;
-}
-
-static int __cil_avrule_can_remove(struct cil_avrule *cil_avrule)
-{
-	struct cil_symtab_datum *src = cil_avrule->src;
-	struct cil_symtab_datum *tgt = cil_avrule->tgt;
-
-	// Don't remove neverallow rules so they are written to
-	// the resulting policy and can be checked by tools in
-	// AOSP.
-	if (cil_avrule->rule_kind == CIL_AVRULE_NEVERALLOW) {
-		return CIL_FALSE;
-	}
-
-	if (__cil_type_datum_is_unused_attrib(src)) {
-		return CIL_TRUE;
-	}
-
-	if (__cil_type_datum_is_unused_attrib(tgt)) {
-		return CIL_TRUE;
-	}
+	attr = (struct cil_typeattribute *)datum;
 
-	return CIL_FALSE;
+	return !attr->used || (ebitmap_cardinality(attr->types) < db->attrs_expand_size);
 }
 
 int __cil_avrule_to_avtab(policydb_t *pdb, const struct cil_db *db, struct cil_avrule *cil_avrule, cond_node_t *cond_node, enum cil_flavor cond_flavor)
@@ -1478,6 +1452,9 @@ int __cil_avrule_to_avtab(policydb_t *pdb, const struct cil_db *db, struct cil_a
 	struct cil_symtab_datum *src = NULL;
 	struct cil_symtab_datum *tgt = NULL;
 	struct cil_list *classperms = cil_avrule->perms.classperms;
+	ebitmap_t src_bitmap, tgt_bitmap;
+	ebitmap_node_t *snode, *tnode;
+	unsigned int s,t;
 
 	if (cil_avrule->rule_kind == CIL_AVRULE_DONTAUDIT && db->disable_dontaudit == CIL_TRUE) {
 		// Do not add dontaudit rules to binary
@@ -1485,36 +1462,98 @@ int __cil_avrule_to_avtab(policydb_t *pdb, const struct cil_db *db, struct cil_a
 		goto exit;
 	}
 
-	if (__cil_avrule_can_remove(cil_avrule)) {
-		rc = SEPOL_OK;
-		goto exit;
-	}
-
 	src = cil_avrule->src;
 	tgt = cil_avrule->tgt;
 
 	if (tgt->fqn == CIL_KEY_SELF) {
-		ebitmap_t type_bitmap;
-		ebitmap_node_t *tnode;
-		unsigned int i;
-
-		rc = __cil_expand_type(src, &type_bitmap);
-		if (rc != SEPOL_OK) goto exit;
+		rc = __cil_expand_type(src, &src_bitmap);
+		if (rc != SEPOL_OK) {
+			goto exit;
+		}
 
-		ebitmap_for_each_bit(&type_bitmap, tnode, i) {
-			if (!ebitmap_get_bit(&type_bitmap, i)) continue;
+		ebitmap_for_each_bit(&src_bitmap, snode, s) {
+			if (!ebitmap_get_bit(&src_bitmap, s)) continue;
 
-			src = DATUM(db->val_to_type[i]);
+			src = DATUM(db->val_to_type[s]);
 			rc = __cil_avrule_expand(pdb, kind, src, src, classperms, cond_node, cond_flavor);
 			if (rc != SEPOL_OK) {
-				ebitmap_destroy(&type_bitmap);
+				ebitmap_destroy(&src_bitmap);
 				goto exit;
 			}
 		}
-		ebitmap_destroy(&type_bitmap);
+		ebitmap_destroy(&src_bitmap);
 	} else {
-		rc = __cil_avrule_expand(pdb, kind, src, tgt, classperms, cond_node, cond_flavor);
-		if (rc != SEPOL_OK) goto exit;
+		int expand_src = __cil_should_expand_attribute(db, src);
+		int expand_tgt = __cil_should_expand_attribute(db, tgt);
+		if (!expand_src && !expand_tgt) {
+			rc = __cil_avrule_expand(pdb, kind, src, tgt, classperms, cond_node, cond_flavor);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+		} else if (expand_src && expand_tgt) {
+			rc = __cil_expand_type(src, &src_bitmap);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+
+			rc = __cil_expand_type(tgt, &tgt_bitmap);
+			if (rc != SEPOL_OK) {
+				ebitmap_destroy(&src_bitmap);
+				goto exit;
+			}
+
+			ebitmap_for_each_bit(&src_bitmap, snode, s) {
+				if (!ebitmap_get_bit(&src_bitmap, s)) continue;
+				src = DATUM(db->val_to_type[s]);
+				ebitmap_for_each_bit(&tgt_bitmap, tnode, t) {
+					if (!ebitmap_get_bit(&tgt_bitmap, t)) continue;
+					tgt = DATUM(db->val_to_type[t]);
+
+					rc = __cil_avrule_expand(pdb, kind, src, tgt, classperms, cond_node, cond_flavor);
+					if (rc != SEPOL_OK) {
+						ebitmap_destroy(&src_bitmap);
+						ebitmap_destroy(&tgt_bitmap);
+						goto exit;
+					}
+				}
+			}
+			ebitmap_destroy(&src_bitmap);
+			ebitmap_destroy(&tgt_bitmap);
+		} else if (expand_src) {
+			rc = __cil_expand_type(src, &src_bitmap);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+
+			ebitmap_for_each_bit(&src_bitmap, snode, s) {
+				if (!ebitmap_get_bit(&src_bitmap, s)) continue;
+				src = DATUM(db->val_to_type[s]);
+
+				rc = __cil_avrule_expand(pdb, kind, src, tgt, classperms, cond_node, cond_flavor);
+				if (rc != SEPOL_OK) {
+					ebitmap_destroy(&src_bitmap);
+					goto exit;
+				}
+			}
+			ebitmap_destroy(&src_bitmap);
+		} else { /* expand_tgt */
+			rc = __cil_expand_type(tgt, &tgt_bitmap);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+
+			ebitmap_for_each_bit(&tgt_bitmap, tnode, t) {
+				if (!ebitmap_get_bit(&tgt_bitmap, t)) continue;
+				tgt = DATUM(db->val_to_type[t]);
+
+				rc = __cil_avrule_expand(pdb, kind, src, tgt, classperms, cond_node, cond_flavor);
+				if (rc != SEPOL_OK) {
+					ebitmap_destroy(&tgt_bitmap);
+					goto exit;
+				}
+			}
+			ebitmap_destroy(&tgt_bitmap);
+		}
 	}
 
 	return SEPOL_OK;
@@ -1789,11 +1828,9 @@ int cil_avrulex_to_hashtable(policydb_t *pdb, const struct cil_db *db, struct ci
 	uint16_t kind;
 	struct cil_symtab_datum *src = NULL;
 	struct cil_symtab_datum *tgt = NULL;
-	ebitmap_t type_bitmap;
-	ebitmap_node_t *tnode;
-	unsigned int i;
-
-	ebitmap_init(&type_bitmap);
+	ebitmap_t src_bitmap, tgt_bitmap;
+	ebitmap_node_t *snode, *tnode;
+	unsigned int s,t;
 
 	if (cil_avrulex->rule_kind == CIL_AVRULE_DONTAUDIT && db->disable_dontaudit == CIL_TRUE) {
 		// Do not add dontaudit rules to binary
@@ -1806,28 +1843,97 @@ int cil_avrulex_to_hashtable(policydb_t *pdb, const struct cil_db *db, struct ci
 	tgt = cil_avrulex->tgt;
 
 	if (tgt->fqn == CIL_KEY_SELF) {
-		rc = __cil_expand_type(src, &type_bitmap);
+		rc = __cil_expand_type(src, &src_bitmap);
 		if (rc != SEPOL_OK) goto exit;
 
-		ebitmap_for_each_bit(&type_bitmap, tnode, i) {
-			if (!ebitmap_get_bit(&type_bitmap, i)) continue;
+		ebitmap_for_each_bit(&src_bitmap, snode, s) {
+			if (!ebitmap_get_bit(&src_bitmap, s)) continue;
 
-			src = DATUM(db->val_to_type[i]);
+			src = DATUM(db->val_to_type[s]);
 			rc = __cil_avrulex_to_hashtable_helper(pdb, kind, src, src, cil_avrulex->perms.x.permx, args);
 			if (rc != SEPOL_OK) {
 				goto exit;
 			}
 		}
+		ebitmap_destroy(&src_bitmap);
 	} else {
-		rc = __cil_avrulex_to_hashtable_helper(pdb, kind, src, tgt, cil_avrulex->perms.x.permx, args);
-		if (rc != SEPOL_OK) goto exit;
+		int expand_src = __cil_should_expand_attribute(db, src);
+		int expand_tgt = __cil_should_expand_attribute(db, tgt);
+
+		if (!expand_src && !expand_tgt) {
+			rc = __cil_avrulex_to_hashtable_helper(pdb, kind, src, tgt, cil_avrulex->perms.x.permx, args);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+		} else if (expand_src && expand_tgt) {
+			rc = __cil_expand_type(src, &src_bitmap);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+
+			rc = __cil_expand_type(tgt, &tgt_bitmap);
+			if (rc != SEPOL_OK) {
+				ebitmap_destroy(&src_bitmap);
+				goto exit;
+			}
+
+			ebitmap_for_each_bit(&src_bitmap, snode, s) {
+				if (!ebitmap_get_bit(&src_bitmap, s)) continue;
+				src = DATUM(db->val_to_type[s]);
+				ebitmap_for_each_bit(&tgt_bitmap, tnode, t) {
+					if (!ebitmap_get_bit(&tgt_bitmap, t)) continue;
+					tgt = DATUM(db->val_to_type[t]);
+
+					rc = __cil_avrulex_to_hashtable_helper(pdb, kind, src, tgt, cil_avrulex->perms.x.permx, args);
+					if (rc != SEPOL_OK) {
+						ebitmap_destroy(&src_bitmap);
+						ebitmap_destroy(&tgt_bitmap);
+						goto exit;
+					}
+				}
+			}
+			ebitmap_destroy(&src_bitmap);
+			ebitmap_destroy(&tgt_bitmap);
+		} else if (expand_src) {
+			rc = __cil_expand_type(src, &src_bitmap);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+
+			ebitmap_for_each_bit(&src_bitmap, snode, s) {
+				if (!ebitmap_get_bit(&src_bitmap, s)) continue;
+				src = DATUM(db->val_to_type[s]);
+
+				rc = __cil_avrulex_to_hashtable_helper(pdb, kind, src, tgt, cil_avrulex->perms.x.permx, args);
+				if (rc != SEPOL_OK) {
+					ebitmap_destroy(&src_bitmap);
+					goto exit;
+				}
+			}
+			ebitmap_destroy(&src_bitmap);
+		} else { /* expand_tgt */
+			rc = __cil_expand_type(tgt, &tgt_bitmap);
+			if (rc != SEPOL_OK) {
+				goto exit;
+			}
+
+			ebitmap_for_each_bit(&tgt_bitmap, tnode, t) {
+				if (!ebitmap_get_bit(&tgt_bitmap, t)) continue;
+				tgt = DATUM(db->val_to_type[t]);
+
+				rc = __cil_avrulex_to_hashtable_helper(pdb, kind, src, tgt, cil_avrulex->perms.x.permx, args);
+				if (rc != SEPOL_OK) {
+					ebitmap_destroy(&tgt_bitmap);
+					goto exit;
+				}
+			}
+			ebitmap_destroy(&tgt_bitmap);
+		}
 	}
 
-	rc = SEPOL_OK;
+	return SEPOL_OK;
 
 exit:
-	ebitmap_destroy(&type_bitmap);
-
 	return rc;
 }
 
@@ -2417,12 +2523,19 @@ int __cil_constrain_expr_datum_to_sepol_expr(policydb_t *pdb, const struct cil_d
 		if (pdb->policyvers >= POLICYDB_VERSION_CONSTRAINT_NAMES) {
 			rc = __cil_get_sepol_type_datum(pdb, item->data, &sepol_type);
 			if (rc != SEPOL_OK) {
-				ebitmap_destroy(&type_bitmap);
-				goto exit;
+				if (FLAVOR(item->data) == CIL_TYPEATTRIBUTE) {
+					struct cil_typeattribute *attr = item->data;
+					if (!attr->used) {
+						rc = 0;
+					}
+				}
 			}
 
-			if (ebitmap_set_bit(&expr->type_names->types, sepol_type->s.value - 1, 1)) {
-				ebitmap_destroy(&type_bitmap);
+			if (sepol_type) {
+				rc = ebitmap_set_bit(&expr->type_names->types, sepol_type->s.value - 1, 1);
+			}
+
+			if (rc != SEPOL_OK) {
 				goto exit;
 			}
 		}
diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h
index 03672bb..efa2cd6 100644
--- a/libsepol/cil/src/cil_internal.h
+++ b/libsepol/cil/src/cil_internal.h
@@ -306,6 +306,8 @@ struct cil_db {
 	struct cil_user **val_to_user;
 	int disable_dontaudit;
 	int disable_neverallow;
+	int attrs_expand_generated;
+	unsigned attrs_expand_size;
 	int preserve_tunables;
 	int handle_unknown;
 	int mls;
@@ -513,11 +515,14 @@ struct cil_type	{
 	int value;
 };
 
+#define CIL_ATTR_AVRULE     0x01
+#define CIL_ATTR_NEVERALLOW 0x02
+#define CIL_ATTR_CONSTRAINT 0x04
 struct cil_typeattribute {
 	struct cil_symtab_datum datum;
 	struct cil_list *expr_list;
 	ebitmap_t *types;
-	int used;	// whether or not this typeattribute was used and should be added to the binary
+	int used;	// whether or not this attribute was used in a binary policy rule
 };
 
 struct cil_typeattributeset {
diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c
index 089c02f..e32a8fc 100644
--- a/libsepol/cil/src/cil_post.c
+++ b/libsepol/cil/src/cil_post.c
@@ -1188,22 +1188,32 @@ exit:
 	return SEPOL_ERR;
 }
 
-static int cil_typeattribute_used(struct cil_typeattribute *cil_attr)
+static int cil_typeattribute_used(struct cil_typeattribute *attr, struct cil_db *db)
 {
-	if (cil_attr->used) {
-		return CIL_TRUE;
+	if (!attr->used) {
+		return CIL_FALSE;
 	}
 
-	if (strcmp(DATUM(cil_attr)->name, GEN_REQUIRE_ATTR) == 0) {
-		return CIL_FALSE;
+	if (attr->used & CIL_ATTR_CONSTRAINT) {
+		return CIL_TRUE;
 	}
 
-	if (strstr(DATUM(cil_attr)->name,TYPEATTR_INFIX) != NULL) {
-		return CIL_FALSE;
+	if (db->attrs_expand_generated || attr->used == CIL_ATTR_NEVERALLOW) {
+		if (strcmp(DATUM(attr)->name, GEN_REQUIRE_ATTR) == 0) {
+			return CIL_FALSE;
+		} else if (strstr(DATUM(attr)->name, TYPEATTR_INFIX) != NULL) {
+			return CIL_FALSE;
+		}
+
+		if (attr->used == CIL_ATTR_NEVERALLOW) {
+			return CIL_TRUE;
+		}
 	}
 
-	if (ebitmap_cardinality(cil_attr->types) == 0) {
-		return CIL_FALSE;
+	if (attr->used == CIL_ATTR_AVRULE) {
+		if (ebitmap_cardinality(attr->types) < db->attrs_expand_size) {
+			return CIL_FALSE;
+		}
 	}
 
 	return CIL_TRUE;
@@ -1231,10 +1241,8 @@ static int __cil_post_db_attr_helper(struct cil_tree_node *node, uint32_t *finis
 		if (attr->types == NULL) {
 			rc = __evaluate_type_expression(attr, db);
 			if (rc != SEPOL_OK) goto exit;
-			if (cil_typeattribute_used(attr)) {
-				attr->used = CIL_TRUE;
-			}
 		}
+		attr->used = cil_typeattribute_used(attr, db);
 		break;
 	}
 	case CIL_ROLEATTRIBUTE: {
diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c
index 1870501..6da44ba 100644
--- a/libsepol/cil/src/cil_resolve_ast.c
+++ b/libsepol/cil/src/cil_resolve_ast.c
@@ -269,13 +269,13 @@ exit:
 	return rc;
 }
 
-int cil_type_used(struct cil_symtab_datum *datum)
+int cil_type_used(struct cil_symtab_datum *datum, int used)
 {
 	struct cil_typeattribute *attr = NULL;
 
 	if (FLAVOR(datum) == CIL_TYPEATTRIBUTE) {
 		attr = (struct cil_typeattribute*)datum;
-		attr->used = CIL_TRUE;
+		attr->used |= used;
 	}
 
 	return 0;
@@ -307,6 +307,7 @@ int cil_resolve_avrule(struct cil_tree_node *current, void *extra_args)
 	struct cil_symtab_datum *src_datum = NULL;
 	struct cil_symtab_datum *tgt_datum = NULL;
 	struct cil_symtab_datum *permx_datum = NULL;
+	int used;
 	int rc = SEPOL_ERR;
 
 	if (args != NULL) {
@@ -318,9 +319,6 @@ int cil_resolve_avrule(struct cil_tree_node *current, void *extra_args)
 		goto exit;
 	}
 	rule->src = src_datum;
-	if (rule->rule_kind != CIL_AVRULE_NEVERALLOW) {
-		cil_type_used(src_datum);
-	}
 		
 	if (rule->tgt_str == CIL_KEY_SELF) {
 		rule->tgt = db->selftype;
@@ -330,9 +328,10 @@ int cil_resolve_avrule(struct cil_tree_node *current, void *extra_args)
 			goto exit;
 		}
 		rule->tgt = tgt_datum;
-		if (rule->rule_kind != CIL_AVRULE_NEVERALLOW) {
-			cil_type_used(tgt_datum);
-		}
+		used = (rule->rule_kind == CIL_AVRULE_NEVERALLOW) ?
+			CIL_ATTR_NEVERALLOW : CIL_ATTR_AVRULE;
+		cil_type_used(src_datum, used); /* src not used if tgt is self */
+		cil_type_used(tgt_datum, used);
 	}
 
 	if (!rule->is_extended) {
@@ -376,14 +375,12 @@ int cil_resolve_type_rule(struct cil_tree_node *current, void *extra_args)
 		goto exit;
 	}
 	rule->src = src_datum;
-	cil_type_used(src_datum);
 
 	rc = cil_resolve_name(current, rule->tgt_str, CIL_SYM_TYPES, extra_args, &tgt_datum);
 	if (rc != SEPOL_OK) {
 		goto exit;
 	}
 	rule->tgt = tgt_datum;
-	cil_type_used(tgt_datum);
 
 	rc = cil_resolve_name(current, rule->obj_str, CIL_SYM_CLASSES, extra_args, &obj_datum);
 	if (rc != SEPOL_OK) {
@@ -589,14 +586,12 @@ int cil_resolve_nametypetransition(struct cil_tree_node *current, void *extra_ar
 		goto exit;
 	}
 	nametypetrans->src = src_datum;
-	cil_type_used(src_datum);
 
 	rc = cil_resolve_name(current, nametypetrans->tgt_str, CIL_SYM_TYPES, extra_args, &tgt_datum);
 	if (rc != SEPOL_OK) {
 		goto exit;
 	}
 	nametypetrans->tgt = tgt_datum;
-	cil_type_used(tgt_datum);
 
 	rc = cil_resolve_name(current, nametypetrans->obj_str, CIL_SYM_CLASSES, extra_args, &obj_datum);
 	if (rc != SEPOL_OK) {
@@ -647,14 +642,12 @@ int cil_resolve_rangetransition(struct cil_tree_node *current, void *extra_args)
 		goto exit;
 	}
 	rangetrans->src = src_datum;
-	cil_type_used(src_datum);
 
 	rc = cil_resolve_name(current, rangetrans->exec_str, CIL_SYM_TYPES, extra_args, &exec_datum);
 	if (rc != SEPOL_OK) {
 		goto exit;
 	}
 	rangetrans->exec = exec_datum;
-	cil_type_used(exec_datum);
 
 	rc = cil_resolve_name(current, rangetrans->obj_str, CIL_SYM_CLASSES, extra_args, &obj_datum);
 	if (rc != SEPOL_OK) {
@@ -1006,7 +999,6 @@ int cil_resolve_roletype(struct cil_tree_node *current, void *extra_args)
 		goto exit;
 	}
 	roletype->type = (struct cil_type*)type_datum;
-	cil_type_used(type_datum);
 
 	return SEPOL_OK;
 
@@ -1035,7 +1027,6 @@ int cil_resolve_roletransition(struct cil_tree_node *current, void *extra_args)
 		goto exit;
 	}
 	roletrans->tgt = tgt_datum;
-	cil_type_used(tgt_datum);
 
 	rc = cil_resolve_name(current, roletrans->obj_str, CIL_SYM_CLASSES, extra_args, &obj_datum);
 	if (rc != SEPOL_OK) {
@@ -3108,7 +3099,7 @@ int cil_resolve_expr(enum cil_flavor expr_type, struct cil_list *str_expr, struc
 			}
 
 			if (sym_index == CIL_SYM_TYPES && (expr_type == CIL_CONSTRAIN || expr_type == CIL_VALIDATETRANS)) {
-				cil_type_used(res_datum);
+				cil_type_used(res_datum, CIL_ATTR_CONSTRAINT);
 			}
 
 			cil_list_append(*datum_expr, CIL_DATUM, res_datum);
diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
index 5e68fcb..4042640 100644
--- a/libsepol/src/libsepol.map.in
+++ b/libsepol/src/libsepol.map.in
@@ -45,6 +45,8 @@ LIBSEPOL_1.1 {
 	cil_set_target_platform;
 	cil_set_policy_version;
 	cil_set_mls;
+	cil_set_attrs_expand_generated;
+	cil_set_attrs_expand_size;
 	cil_write_policy_conf;
 	sepol_ppfile_to_module_package;
 	sepol_module_package_to_cil;
-- 
2.7.4

[PATCH 2/2 v2] secilc: Add options to control the expansion of attributes

[James Carter]

Added "-G, --expand_generated" option to specify that all automatically
generated attributes should be expanded and removed.

Added "-X, --expand_size <SIZE>" option to specify which attributes
are expanded when building a kernel policy. All attributes that have
less types assigned to it than SIZE will be expanded when writing AV
rules.

Signed-off-by: James Carter <jwcart2@tycho.nsa.gov>
---
 secilc/secil2conf.c |  2 ++
 secilc/secilc.8.xml | 10 ++++++++++
 secilc/secilc.c     | 31 ++++++++++++++++++++++++++++++-
 3 files changed, 42 insertions(+), 1 deletion(-)

diff --git a/secilc/secil2conf.c b/secilc/secil2conf.c
index 5d8fe87..4e97dd6 100644
--- a/secilc/secil2conf.c
+++ b/secilc/secil2conf.c
@@ -124,6 +124,8 @@ int main(int argc, char *argv[])
 	cil_db_init(&db);
 	cil_set_preserve_tunables(db, preserve_tunables);
 	cil_set_mls(db, mls);
+	cil_set_attrs_expand_generated(db, 0);
+	cil_set_attrs_expand_size(db, 0);
 
 	for (i = optind; i < argc; i++) {
 		file = fopen(argv[i], "r");
diff --git a/secilc/secilc.8.xml b/secilc/secilc.8.xml
index 9e2670b..4c779b6 100644
--- a/secilc/secilc.8.xml
+++ b/secilc/secilc.8.xml
@@ -81,6 +81,16 @@
          </varlistentry>
 
          <varlistentry>
+            <term><option>-G, --expand-generated</option></term>
+            <listitem><para>Expand and remove auto-generated attributes</para></listitem>
+         </varlistentry>
+
+         <varlistentry>
+            <term><option>-X, --attrs-size &lt;size></option></term>
+            <listitem><para>Expand type attributes with fewer than <emphasis role="bold">&lt;SIZE></emphasis> members.</para></listitem>
+         </varlistentry>
+
+         <varlistentry>
             <term><option>-v, --verbose</option></term>
             <listitem><para>Increment verbosity level.</para></listitem>
          </varlistentry>
diff --git a/secilc/secilc.c b/secilc/secilc.c
index f4ecbee..f2232e7 100644
--- a/secilc/secilc.c
+++ b/secilc/secilc.c
@@ -64,6 +64,9 @@ static __attribute__((__noreturn__)) void usage(const char *prog)
 	printf("  -D, --disable-dontaudit        do not add dontaudit rules to the binary policy\n");
 	printf("  -P, --preserve-tunables        treat tunables as booleans\n");
 	printf("  -N, --disable-neverallow       do not check neverallow rules\n");
+	printf("  -G, --expand-generated         Expand and remove auto-generated attributes\n");
+	printf("  -X, --expand-size <SIZE>       Expand type attributes with fewer than <SIZE>\n");
+	printf("                                 members.\n");
 	printf("  -v, --verbose                  increment verbosity level\n");
 	printf("  -h, --help                     display usage information\n");
 	exit(1);
@@ -90,6 +93,8 @@ int main(int argc, char *argv[])
 	int preserve_tunables = 0;
 	int handle_unknown = -1;
 	int policyvers = POLICYDB_VERSION_MAX;
+	int attrs_expand_generated = 0;
+	int attrs_expand_size = -1;
 	int opt_char;
 	int opt_index = 0;
 	char *fc_buf = NULL;
@@ -107,12 +112,14 @@ int main(int argc, char *argv[])
 		{"preserve-tunables", no_argument, 0, 'P'},
 		{"output", required_argument, 0, 'o'},
 		{"filecontexts", required_argument, 0, 'f'},
+		{"expand-generated", no_argument, 0, 'G'},
+		{"expand-size", required_argument, 0, 'X'},
 		{0, 0, 0, 0}
 	};
 	int i;
 
 	while (1) {
-		opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDNc:", long_opts, &opt_index);
+		opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDNc:GX:", long_opts, &opt_index);
 		if (opt_char == -1) {
 			break;
 		}
@@ -180,6 +187,24 @@ int main(int argc, char *argv[])
 			case 'f':
 				filecontexts = strdup(optarg);
 				break;
+			case 'G':
+				attrs_expand_generated = 1;
+				break;
+			case 'X': {
+				char *endptr = NULL;
+				errno = 0;
+				attrs_expand_size = strtol(optarg, &endptr, 10);
+				if (errno != 0 || endptr == optarg || *endptr != '\0') {
+					fprintf(stderr, "Bad attribute expand size: %s\n", optarg);
+					usage(argv[0]);
+				}
+
+				if (attrs_expand_size < 0) {
+					fprintf(stderr, "Attribute expand size must be > 0\n");
+					usage(argv[0]);
+				}
+				break;
+			}
 			case 'h':
 				usage(argv[0]);
 			case '?':
@@ -210,6 +235,10 @@ int main(int argc, char *argv[])
 	cil_set_mls(db, mls);
 	cil_set_target_platform(db, target);
 	cil_set_policy_version(db, policyvers);
+	cil_set_attrs_expand_generated(db, attrs_expand_generated);
+	if (attrs_expand_size >= 0) {
+		cil_set_attrs_expand_size(db, (unsigned)attrs_expand_size);
+	}
 
 	for (i = optind; i < argc; i++) {
 		file = fopen(argv[i], "r");
-- 
2.7.4

Re: [PATCH 0/2 v2] libsepol and checkpolicy: Add ability to expand some attributes in binary policy

[James Carter]

On 04/12/2017 02:26 PM, James Carter wrote:
> The number of type attributes included in the binary policy is becomming a performance issue in some cases.
>
> This patch set more aggressives removes attributes and gives the options to expand and remove all auto-generated attributes and all attributes with fewer than a given amount of attributes assigned.
>
> Comparison of the number of attributes remaining in the binary policy
>      mls   normal  android
> org  310     286     255
> old  268     251     130
> max   71      20      17
> min  226     173     119
> def  223     170      80
> gen  220     170      46
> u5   164     112      59
>
> Org - Number of attributes in the CIL policy
> Old - Results without this patch set
> Max - Remove the maximum number of attributes: "-G -X 9999"
> Min - Remove the minimum number of attributes: "-X 0"
> Def - The new defaults for CIL
> Gen - Just removing auto-generated attributes: "-G"
> U5  - Remove attributes with less than five members: "-X 5"
>
> v2:
> - Use "--expand-generated" and "--expand-size" as options for consistency.
> - Fixed bug in cil_post.c:__cil_post_db_attr_helper() where cil_typeattribute_used() would not be called if the attribute type bitmap was already created.
>
> James Carter (2):
>   libsepol/cil: Add ability to expand some attributes in binary policy
>   secilc: Add options to control the expansion of attributes
>
>  libsepol/cil/include/cil/cil.h     |   2 +
>  libsepol/cil/src/cil.c             |  12 ++
>  libsepol/cil/src/cil_binary.c      | 253 +++++++++++++++++++++++++++----------
>  libsepol/cil/src/cil_internal.h    |   7 +-
>  libsepol/cil/src/cil_post.c        |  32 +++--
>  libsepol/cil/src/cil_resolve_ast.c |  25 ++--
>  libsepol/src/libsepol.map.in       |   2 +
>  secilc/secil2conf.c                |   2 +
>  secilc/secilc.8.xml                |  10 ++
>  secilc/secilc.c                    |  31 ++++-
>  10 files changed, 275 insertions(+), 101 deletions(-)
>

These three patches have been merged.


-- 
James Carter <jwcart2@tycho.nsa.gov>
National Security Agency