[RFC][PATCH 0/3] Reduce number of avtab nodes

[RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

The following patch set reduces the number of avtab nodes by preserving
attributes in TE allow/dontaudit/auditallow rules when possible rather
than expanding them during policy compilation, and having the kernel use
a type->attribute reverse map to perform the access vector computation,
per the earlier discussions on the list.  This slows down security
server computations, but these only occur on AVC cache misses, so the
expected performance impact is negligible.  I have not yet attempted to
measure the performance impact.  If it proves to be measurable at all,
we can likely optimize it in the same manner that I used for the
assertion checking code (see below).

Unlike the first patchset, where you could just patch the kernel and see
the memory savings from the reduction in the per-node size even with a
policy.19 file, this patch set requires you to patch your kernel,
libsepol, and checkpolicy and build a policy.20 policy in order to see
the reduction in nodes, as that is handled during compilation.

This patchset is relative to the prior patch set.  I've also made the
two patch sets available under http://www.cs.utah.edu/~sds/avtab1 and
http://www.cs.utah.edu/~sds/avtab2 respectively, along with prepatched
tarballs of libsepol and checkpolicy for convenience.  These include the
bug fixes for the first patch set and a re-base to the latest cvs.

Some notes:
- Expansion of attributes is only suppressed in type sets in
allow/dontaudit/auditallow rules, and only if the type set does not
include a negative set (e.g. file_type - shadow_t), wildcard (*), or
complement (~) and only if the rule is not a self rule.   I didn't
originally catch the latter (self rules), which had an interesting
effect (allow x self:process p; was being mis-interpreted as allow x
x:process p; for every t in x by the kernel).

- I didn't increment the policy version again for this patch set,
so it is still version 20, as with the prior patch set.  If we
were to upstream these patches separately, I'd split them into separate
versions, but if we roll them up for a single upstream change, there is
no reason to separate them.

- Compatibility code for writing older policy versions from the patched
checkpolicy is not written yet, unlike with the prior patchset.  Looks
rather painful (and I thought it was already painful with the last
patchset), as I'd have to expand the avtab and we've already discarded
the attribute->type mappings at this point (the type->attribute reverse
mappings aren't quite as helpful for such expansion).

- Assertion checking is significantly slower.  I added some new inline
ebitmap operations to help speed it up, but it is still a lot slower
than previously.

- A possible solution to both of the above problems would be to build a
fully expanded avtab during module expansion in addition to the
non-expanded one and saving it in the policydb for later use in
assertion checking and writing older policy versions.  But that will
obviously slow down module expansion and consume a lot more memory when
constructing policies.  Thoughts?  Patches?

Some data on the file size, number of slab objects (avtab nodes) and
slab object size (avtab node size) is below for the unpatched code
(version 19), the first patchset (reduce avtab node size, split multiple
data entries), and this second patchset (reduce number of nodes).  As I
didn't create separate policy versions for each patchset, 20.1 refers to
the first patchset and 20.2 refers to the second patchset.  Since the
first patchset reduces the node size, it has essentially the same impact
on targeted and strict policies, i.e. roughly halving the memory size.
In contrast, since the second patchset only reduces the number of nodes
and only when attributes are used in rules, it has a markedly different
impact on targeted vs. strict policy, although it reduces the memory
size for both.  In general, as policies move toward greater least
privilege, this patch set will provide less of an improvement, although
it is unlikely that we will ever get away completely from having some
rules that use attributes.

Targeted Policy
Vers | File | #Objs  | ObjSize
------------------------------
19   | 8.0M | 347387 |  32
20.1 | 4.1M | 350813 |  16
20.2 | 391K | 23751  |  16

Strict Policy
Vers | File | #Objs | ObjSize
------------------------------
19   | 16M  | 664756 | 32
20.1 | 8.0M | 689183 | 16
20.2 | 2.9M | 229295 | 16

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[RFC][PATCH 1/3] Reduce number of avtab nodes

[Stephen Smalley]

This patch, relative to the kernel patch to reduce avtab node size,
modifies the SELinux module to create a type->attribute reverse mapping,
with the type always included in its own mapping as a degenerate case,
and to use this mapping when computing access vectors.  This occurs even
if the binary policy lacks the mapping (i.e. older binary policy
version), in which case only the type itself is set in the bitmap and
used for computations.  This patch also happens to include a fix for a
longstanding memory leak in policydb_destroy for role_allow, role_trans,
and range_trans rules that was discovered in the corresponding libsepol
code by Ivan.  We can split that out separately for upstream if
necessary.

---

 security/selinux/ss/policydb.c |   40 ++++++++++++++++++++++++++++++++++++++
 security/selinux/ss/policydb.h |    3 ++
 security/selinux/ss/services.c |   43 +++++++++++++++++++++++++++--------------
 3 files changed, 72 insertions(+), 14 deletions(-)

diff -X /home/sds/dontdiff -rup linux-2.6.13-rc3-mm1-avtab1/security/selinux/ss/policydb.c linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/policydb.c
--- linux-2.6.13-rc3-mm1-avtab1/security/selinux/ss/policydb.c	2005-07-29 09:20:05.000000000 -0400
+++ linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/policydb.c	2005-07-29 09:21:01.000000000 -0400
@@ -589,6 +589,9 @@ void policydb_destroy(struct policydb *p
 	struct ocontext *c, *ctmp;
 	struct genfs *g, *gtmp;
 	int i;
+	struct role_allow *ra, *lra = NULL;
+	struct role_trans *tr, *ltr = NULL;
+	struct range_trans *rt, *lrt = NULL;
 
 	for (i = 0; i < SYM_NUM; i++) {
 		hashtab_map(p->symtab[i].table, destroy_f[i], NULL);
@@ -629,6 +632,28 @@ void policydb_destroy(struct policydb *p
 
 	cond_policydb_destroy(p);
 
+	for (tr = p->role_tr; tr; tr = tr->next) {
+		if (ltr) kfree(ltr);
+		ltr = tr;
+	}
+	if (ltr) kfree(ltr);
+
+	for (ra = p->role_allow; ra; ra = ra -> next) {
+		if (lra) kfree(lra);
+		lra = ra;
+	}
+	if (lra) kfree(lra);
+
+	for (rt = p->range_tr; rt; rt = rt -> next) {
+		if (lrt) kfree(lrt);
+		lrt = rt;
+	}
+	if (lrt) kfree(lrt);
+
+	for (i = 0; i < p->p_types.nprim; i++)
+		ebitmap_destroy(&p->type_attr_map[i]);
+	kfree(p->type_attr_map);
+
 	return;
 }
 
@@ -1830,6 +1855,21 @@ int policydb_read(struct policydb *p, vo
 		}
 	}
 
+	p->type_attr_map = kmalloc(p->p_types.nprim*sizeof(struct ebitmap), GFP_KERNEL);
+	if (!p->type_attr_map)
+		goto bad;
+
+	for (i = 0; i < p->p_types.nprim; i++) {
+		ebitmap_init(&p->type_attr_map[i]);
+		if (p->policyvers >= POLICYDB_VERSION_AVTAB) {
+			if (ebitmap_read(&p->type_attr_map[i], fp))
+				goto bad;
+		}
+		/* add the type itself as the degenerate case */
+		if (ebitmap_set_bit(&p->type_attr_map[i], i, 1))
+				goto bad;
+	}
+
 	rc = 0;
 out:
 	return rc;
diff -X /home/sds/dontdiff -rup linux-2.6.13-rc3-mm1-avtab1/security/selinux/ss/policydb.h linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/policydb.h
--- linux-2.6.13-rc3-mm1-avtab1/security/selinux/ss/policydb.h	2005-06-17 15:48:29.000000000 -0400
+++ linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/policydb.h	2005-07-29 09:21:01.000000000 -0400
@@ -237,6 +237,9 @@ struct policydb {
 	/* range transitions */
 	struct range_trans *range_tr;
 
+	/* type -> attribute reverse mapping */
+	struct ebitmap *type_attr_map;
+
 	unsigned int policyvers;
 };
 
diff -X /home/sds/dontdiff -rup linux-2.6.13-rc3-mm1-avtab1/security/selinux/ss/services.c linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/services.c
--- linux-2.6.13-rc3-mm1-avtab1/security/selinux/ss/services.c	2005-07-29 09:20:05.000000000 -0400
+++ linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/services.c	2005-07-29 09:21:01.000000000 -0400
@@ -268,6 +268,8 @@ static int context_struct_compute_av(str
 	struct avtab_key avkey;
 	struct avtab_node *node;
 	struct class_datum *tclass_datum;
+	struct ebitmap *sattr, *tattr;
+	unsigned int i, j;
 
 	/*
 	 * Remap extended Netlink classes for old policy versions.
@@ -300,23 +302,36 @@ static int context_struct_compute_av(str
 	 * If a specific type enforcement rule was defined for
 	 * this permission check, then use it.
 	 */
-	avkey.source_type = scontext->type;
-	avkey.target_type = tcontext->type;
 	avkey.target_class = tclass;
 	avkey.specified = AVTAB_AV;
-	for (node = avtab_search_node(&policydb.te_avtab, &avkey);
-	     node != NULL;
-	     node = avtab_search_node_next(node, avkey.specified)) {
-		if (node->key.specified == AVTAB_ALLOWED)
-			avd->allowed = node->datum.data;
-		else if (node->key.specified == AVTAB_AUDITALLOW)
-			avd->auditallow = node->datum.data;
-		else if (node->key.specified == AVTAB_AUDITDENY)
-			avd->auditdeny = node->datum.data;
-	}
+	sattr = &policydb.type_attr_map[scontext->type - 1];
+	tattr = &policydb.type_attr_map[tcontext->type - 1];
+	for (i = ebitmap_startbit(sattr); 
+	     i < ebitmap_length(sattr); i++) {
+		if (!ebitmap_get_bit(sattr, i))
+		    continue;
+		for (j = ebitmap_startbit(tattr); 
+		     j < ebitmap_length(tattr); j++) {
+			if (!ebitmap_get_bit(tattr, j))
+				continue;
+			avkey.source_type = i + 1;
+			avkey.target_type = j + 1;
+			for (node = avtab_search_node(&policydb.te_avtab, &avkey);
+			     node != NULL;
+			     node = avtab_search_node_next(node, avkey.specified)) {
+				if (node->key.specified == AVTAB_ALLOWED)
+					avd->allowed |= node->datum.data;
+				else if (node->key.specified == AVTAB_AUDITALLOW)
+					avd->auditallow |= node->datum.data;
+				else if (node->key.specified == AVTAB_AUDITDENY)
+					avd->auditdeny &= node->datum.data;
+			}
+
+			/* Check conditional av table for additional permissions */
+			cond_compute_av(&policydb.te_cond_avtab, &avkey, avd);
 
-	/* Check conditional av table for additional permissions */
-	cond_compute_av(&policydb.te_cond_avtab, &avkey, avd);
+		}
+	}
 
 	/*
 	 * Remove any permissions prohibited by a constraint (this includes


-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[RFC][PATCH 2/3] Reduce number of avtab nodes

[Stephen Smalley]

This patch, relative to the libsepol patch to reduce avtab node size,
modifies libsepol to preserve attributes in TE
allow/dontaudit/auditallow rules when possible rather than expanding
them and to create the type->attribute reverse mapping.  It does _not_
presently include code for writing older policy versions.  Some new
inline ebitmap operations are introduced to speed up assertion checking,
which is nonetheless still quite a bit slower than previously due to the
non-expanded avtab.

---

 include/sepol/ebitmap.h  |   23 ++++++
 include/sepol/expand.h   |    4 -
 include/sepol/policydb.h |    4 -
 src/assertion.c          |   67 +++++++++++++------
 src/constraint.c         |    2 
 src/expand.c             |  159 ++++++++++++++++++++++++++++++++++++-----------
 src/policydb.c           |   22 +++++-
 src/services.c           |   43 ++++++++----
 src/write.c              |   10 ++
 9 files changed, 259 insertions(+), 75 deletions(-)

diff -X /home/sds/dontdiff -rup libsepol-avtab1/include/sepol/ebitmap.h libsepol/include/sepol/ebitmap.h
--- libsepol-avtab1/include/sepol/ebitmap.h	2005-07-13 15:26:17.000000000 -0400
+++ libsepol/include/sepol/ebitmap.h	2005-07-28 14:48:44.000000000 -0400
@@ -39,12 +39,35 @@ typedef struct ebitmap {
 
 #define ebitmap_length(e) ((e)->highbit)
 #define ebitmap_startbit(e) ((e)->node ? (e)->node->startbit : 0)
+#define ebitmap_startnode(e) ((e)->node)
 
 static inline void ebitmap_init(ebitmap_t * e)
 {
 	memset(e, 0, sizeof(*e));
 }
 
+static inline unsigned int ebitmap_nextbit(ebitmap_t *e, 
+					   ebitmap_node_t **n,
+					   unsigned int bit)
+{
+	if ((bit == ((*n)->startbit + MAPSIZE - 1)) &&
+	    (*n)->next) {
+		*n = (*n)->next;
+		return (*n)->startbit;
+	}
+
+	return (bit+1);
+}
+
+static inline int ebitmap_node_get_bit(ebitmap_t *e, 
+				       ebitmap_node_t * n, 
+				       unsigned int bit)
+{
+	if (n->map & (MAPBIT << (bit - n->startbit)))
+		return 1;
+	return 0;
+}
+
 extern int ebitmap_cmp(ebitmap_t * e1, ebitmap_t * e2);
 extern int ebitmap_or(ebitmap_t * dst, ebitmap_t * e1, ebitmap_t * e2);
 extern int ebitmap_union(ebitmap_t *dst, ebitmap_t *e1);
diff -X /home/sds/dontdiff -rup libsepol-avtab1/include/sepol/expand.h libsepol/include/sepol/expand.h
--- libsepol-avtab1/include/sepol/expand.h	2005-07-13 15:26:17.000000000 -0400
+++ libsepol/include/sepol/expand.h	2005-07-28 14:48:44.000000000 -0400
@@ -29,8 +29,8 @@
 
 extern int expand_module(policydb_t *base, policydb_t *out,
                         int verbose, char *error_buf, size_t error_buf_size);
-extern int expand_convert_type_set(policydb_t *p, uint32_t *typemap, type_set_t *set, ebitmap_t *types);
-extern int type_set_expand(type_set_t *set, ebitmap_t *t, policydb_t *p);
+extern int expand_convert_type_set(policydb_t *p, uint32_t *typemap, type_set_t *set, ebitmap_t *types, unsigned char alwaysexpand);
+extern int type_set_expand(type_set_t *set, ebitmap_t *t, policydb_t *p, unsigned char alwaysexpand);
 extern int role_set_expand(role_set_t *x, ebitmap_t *r, policydb_t *p);
 extern int expand_rule(policydb_t *source_pol,
                 avrule_t *source_rule, avtab_t *dest_avtab,
diff -X /home/sds/dontdiff -rup libsepol-avtab1/include/sepol/policydb.h libsepol/include/sepol/policydb.h
--- libsepol-avtab1/include/sepol/policydb.h	2005-07-28 14:44:43.000000000 -0400
+++ libsepol/include/sepol/policydb.h	2005-07-28 14:48:44.000000000 -0400
@@ -431,6 +431,8 @@ typedef struct policydb {
 	/* range transitions */
 	range_trans_t *range_tr;
 
+	ebitmap_t *type_attr_map;
+
 	unsigned policyvers;
 } policydb_t;
 
@@ -485,7 +487,7 @@ extern void type_datum_destroy(type_datu
 extern void user_datum_init(user_datum_t *x);
 extern void user_datum_destroy(user_datum_t *x);
 
-extern int check_assertions(policydb_t *p, avrule_t *avrules, avtab_t *avtab);
+extern int check_assertions(policydb_t *p, avrule_t *avrules);
 extern int symtab_insert(policydb_t *x, uint32_t sym,
                   hashtab_key_t key, hashtab_datum_t datum,
                   uint32_t scope, uint32_t avrule_decl_id,
diff -X /home/sds/dontdiff -rup libsepol-avtab1/src/assertion.c libsepol/src/assertion.c
--- libsepol-avtab1/src/assertion.c	2005-07-28 14:44:43.000000000 -0400
+++ libsepol/src/assertion.c	2005-07-28 14:48:44.000000000 -0400
@@ -83,35 +83,62 @@ static char *av_to_string(policydb_t *po
 /* These should probably return the error to the caller but it may get very long
    when there are lots of assertion violations, may try to fix this later */
 static int check_assertion_helper(policydb_t *p, unsigned int stype, unsigned int ttype,
-        class_perm_node_t *perm, avtab_t *avtab, unsigned long line)
+        class_perm_node_t *perm, unsigned long line)
 {
         avtab_key_t avkey;
-        avtab_datum_t *avdatump;
         class_perm_node_t *curperm;
-
-        curperm = perm;
+	avtab_ptr_t node;
+	ebitmap_t *sattr, *tattr;
+	ebitmap_node_t *snode, *tnode;
+	unsigned int i, j;
 
 	for (curperm = perm; curperm != NULL; curperm = curperm->next) { 
-                avkey.source_type = stype + 1;
-                avkey.target_type = ttype + 1;
                 avkey.target_class = curperm->class;
 		avkey.specified = AVTAB_ALLOWED;
-                avdatump = avtab_search(avtab, &avkey);
-                if (!avdatump)
-			continue;
-                if (avdatump->data & curperm->data) {
-                        fprintf(stderr, "assertion on line %lu violated by allow %s %s:%s {%s };\n",
-                                line, p->p_type_val_to_name[stype], p->p_type_val_to_name[ttype],
-                                p->p_class_val_to_name[curperm->class - 1],
-				av_to_string(p, curperm->class+1, avdatump->data & curperm->data));
-                        return -1;
-                }
+		sattr = &p->type_attr_map[stype];
+		tattr = &p->type_attr_map[ttype];
+		for (i = ebitmap_startbit(sattr), 
+			     snode = ebitmap_startnode(sattr);
+		     i < ebitmap_length(sattr); 
+		     i = ebitmap_nextbit(sattr, &snode, i)) {
+			if (!ebitmap_node_get_bit(sattr, snode, i))
+				continue;
+			for (j = ebitmap_startbit(tattr), 
+				     tnode = ebitmap_startnode(tattr); 
+			     j < ebitmap_length(tattr); 
+			     j = ebitmap_nextbit(tattr, &tnode, j)) {
+				if (!ebitmap_node_get_bit(tattr, tnode, j))
+					continue;
+				avkey.source_type = i + 1;
+				avkey.target_type = j + 1;
+				for (node = avtab_search_node(&p->te_avtab, &avkey);
+				     node != NULL;
+				     node = avtab_search_node_next(node, avkey.specified)) {
+					if (node->datum.data & curperm->data)
+						goto err;
+				}
+
+				for (node = avtab_search_node(&p->te_cond_avtab, &avkey);
+				     node != NULL;
+				     node = avtab_search_node_next(node, avkey.specified)) {
+					if (node->datum.data & curperm->data)
+						goto err;
+				}
+			}
+		}
+	}
 
-        }
         return 0;
+
+err:
+	fprintf(stderr, "assertion on line %lu violated by allow %s %s:%s {%s };\n",
+		line, p->p_type_val_to_name[stype], p->p_type_val_to_name[ttype],
+		p->p_class_val_to_name[curperm->class - 1],
+		av_to_string(p, curperm->class, node->datum.data & curperm->data));
+	return -1;
 }
 
-int check_assertions(policydb_t *p, avrule_t *avrules, avtab_t *avtab)
+int check_assertions(policydb_t *p, avrule_t *avrules)
 {
         avrule_t *a;
         unsigned int i, j;
@@ -128,13 +155,13 @@ int check_assertions(policydb_t *p, avru
                         if (!ebitmap_get_bit(&a->stypes.types, i))
                                 continue;
                         if (a->flags & RULE_SELF) {
-                                if (check_assertion_helper(p, i, i, a->perms, avtab, a->line))
+                                if (check_assertion_helper(p, i, i, a->perms, a->line))
                                         errors++;
                         }
                         for (j = ebitmap_startbit(&a->ttypes.types); j < ebitmap_length(&a->ttypes.types); j++) {
                                 if (!ebitmap_get_bit(&a->ttypes.types, j))
                                         continue;
-                                if (check_assertion_helper(p, i, j, a->perms, avtab, a->line))
+                                if (check_assertion_helper(p, i, j, a->perms, a->line))
                                     errors++;
                         }
                 }
diff -X /home/sds/dontdiff -rup libsepol-avtab1/src/constraint.c libsepol/src/constraint.c
--- libsepol-avtab1/src/constraint.c	2005-07-26 11:45:32.000000000 -0400
+++ libsepol/src/constraint.c	2005-07-28 14:48:44.000000000 -0400
@@ -54,7 +54,7 @@ int expand_constraint(constraint_expr_t 
                       uint32_t *typemap, policydb_t *pol) {
          ebitmap_t e;
          int i, j;
-         if (type_set_expand(expr->type_names, &e, pol)) {
+         if (type_set_expand(expr->type_names, &e, pol, 1)) {
                  ebitmap_destroy(&e);
                  return -1;
          }
diff -X /home/sds/dontdiff -rup libsepol-avtab1/src/expand.c libsepol/src/expand.c
--- libsepol-avtab1/src/expand.c	2005-07-28 14:44:43.000000000 -0400
+++ libsepol/src/expand.c	2005-07-28 14:48:47.000000000 -0400
@@ -92,16 +92,10 @@ static int type_copy_callback(hashtab_ke
         memset(new_type, 0, sizeof(type_datum_t));
 
         new_type->isattr = type->isattr;
+	new_type->value = ++state->out->p_types.nprim;
         if (!type->isattr) {
-                new_type->value = ++state->out->p_types.nprim;
                 new_type->primary = 1;
         }
-        else {
-                /* lookups of attributes should never occur, so
-                 * explicitly set it to a blatantly illegal value
-                 * here */
-                new_type->value = -1;
-        }
         state->typemap[type->value - 1] = new_type->value;
 
         ret = hashtab_insert(state->out->p_types.table,
@@ -116,6 +110,49 @@ static int type_copy_callback(hashtab_ke
         return 0;
 }
 
+static int attr_convert_callback(hashtab_key_t key, hashtab_datum_t datum, void *data)
+{
+	int i;
+        char *id;
+        type_datum_t *type, *new_type;
+       	expand_state_t *state;
+
+        id = (char *)key;
+        type = (type_datum_t *)datum;
+        state = (expand_state_t*)data;
+
+        if (!type->isattr)
+                return 0;
+
+        if (!is_id_enabled(id, state->base, SYM_TYPES)) {
+                /* identifier's scope is not enabled */
+                return 0;
+        }
+
+        if (state->verbose)
+                printf("converting attribute %s\n", id);
+
+	new_type = hashtab_search(state->out->p_types.table, id);
+	if (!new_type) {
+		write_error (state, "attribute %s vanished!", id);
+                return -1;
+	}
+	ebitmap_init(&new_type->types);
+
+	for (i = ebitmap_startbit(&type->types); 
+	     i < ebitmap_length(&type->types); i++) {
+		if (ebitmap_get_bit(&type->types, i)) {
+			if (ebitmap_set_bit(&new_type->types,
+					    state->typemap[i]-1, 1)) {
+				write_error (state, "out of memory", id);
+				return -1;
+			}
+		}
+	}
+
+        return 0;
+}
+
 static int perm_copy_callback(hashtab_key_t key, hashtab_datum_t datum, void *data)
 {
         int ret;
@@ -249,7 +286,7 @@ static int constraint_node_clone(constra
                                 if (expand_convert_type_set(state->base,
                                                             state->typemap,
                                                             expr->type_names,
-                                                            &new_expr->names)) {
+                                                            &new_expr->names, 1)) {
                                         goto out_of_mem;
         			}
         		}
@@ -462,7 +499,7 @@ static int role_copy_callback(hashtab_ke
                 return -1;
         }
 
-        if (expand_convert_type_set(state->base, state->typemap, &role->types, &new_role->types.types)) {
+        if (expand_convert_type_set(state->base, state->typemap, &role->types, &new_role->types.types, 1)) {
                 write_error (state, "Out of memory!");
                 return -1;
         }
@@ -749,7 +786,7 @@ static int copy_role_trans(expand_state_
                         write_error (state, "Out of memory!");
 			return -1;
                 }
-		if (expand_convert_type_set(state->base, state->typemap, &cur->types, &types)) {
+		if (expand_convert_type_set(state->base, state->typemap, &cur->types, &types, 1)) {
                         write_error (state, "Out of memory!");
 			return -1;
                 }			
@@ -1100,6 +1137,7 @@ static int convert_and_expand_rule(polic
                                    int enabled, char **error_msg) {
         int retval;
         ebitmap_t stypes, ttypes;
+	unsigned char alwaysexpand;
 
         if (source_rule->specified & AVRULE_NEVERALLOW)
                 return 1;
@@ -1107,9 +1145,13 @@ static int convert_and_expand_rule(polic
         ebitmap_init(&stypes);
         ebitmap_init(&ttypes);
 
-        if (expand_convert_type_set(source_pol, typemap, &source_rule->stypes, &stypes))
+	/* Force expansion for type rules and for self rules. */
+	alwaysexpand = ((source_rule->specified & AVRULE_TYPE) ||
+			(source_rule->flags & RULE_SELF));
+
+        if (expand_convert_type_set(source_pol, typemap, &source_rule->stypes, &stypes, alwaysexpand))
                 return -1;
-        if (expand_convert_type_set(source_pol, typemap, &source_rule->ttypes, &ttypes))
+        if (expand_convert_type_set(source_pol, typemap, &source_rule->ttypes, &ttypes, alwaysexpand))
                 return -1;
 
         retval = expand_rule_helper(dest_pol, typemap,
@@ -1356,6 +1398,26 @@ static int range_trans_clone(expand_stat
         return -1;
 }
 
+static int type_attr_map(hashtab_key_t key, hashtab_datum_t datum, void *ptr)
+{
+  	type_datum_t *type;
+	expand_state_t *state = ptr;
+	policydb_t *p = state->out;
+	int i;
+
+	type = (type_datum_t *) datum;
+	if (type->isattr) {
+		for (i = ebitmap_startbit(&type->types); 
+		     i < ebitmap_length(&type->types); i++) 
+			if (ebitmap_get_bit(&type->types, i)) {
+				if (ebitmap_set_bit(&p->type_attr_map[i],
+						    type->value - 1, 1))
+					return -1;
+			}
+	}
+	return 0;
+}
+
 static int type_attr_remove(hashtab_key_t key __attribute__ ((unused)), hashtab_datum_t datum, void *p __attribute__ ((unused)))
 {
 	type_datum_t *typdatum;
@@ -1366,8 +1428,7 @@ static int type_attr_remove(hashtab_key_
 	return 0;
 }
 
-
-int expand_convert_type_set(policydb_t *p, uint32_t *typemap, type_set_t *set, ebitmap_t *types)
+int expand_convert_type_set(policydb_t *p, uint32_t *typemap, type_set_t *set, ebitmap_t *types, unsigned char alwaysexpand)
 {
         int i;
         ebitmap_t tmp;
@@ -1375,7 +1436,7 @@ int expand_convert_type_set(policydb_t *
         ebitmap_init(types);
         ebitmap_init(&tmp);
         
-        if (type_set_expand(set, &tmp, p))
+        if (type_set_expand(set, &tmp, p, alwaysexpand))
                 return -1;
                 
         for (i = ebitmap_startbit(&tmp); i < ebitmap_length(&tmp); i++) {
@@ -1409,9 +1470,9 @@ int expand_rule(policydb_t *source_pol,
         ebitmap_init(&stypes);
         ebitmap_init(&ttypes);
 
-        if (type_set_expand(&source_rule->stypes, &stypes, source_pol))
+        if (type_set_expand(&source_rule->stypes, &stypes, source_pol, 1))
                 return -1;
-        if (type_set_expand(&source_rule->ttypes, &ttypes, source_pol))
+        if (type_set_expand(&source_rule->ttypes, &ttypes, source_pol, 1))
                 return -1;
         retval = expand_rule_helper(source_pol, NULL,
                                     source_rule, dest_avtab,
@@ -1459,8 +1520,13 @@ int role_set_expand(role_set_t *x, ebitm
 
 /* Expand a type set into an ebitmap containing the types. This
  * handles the negset, attributes, and flags.
+ * Attribute expansion depends on several factors:
+ * - if alwaysexpand is 1, then they will be expanded,
+ * - if the type set has a negset or flags, then they will be expanded,
+ * - otherwise, they will not be expanded.
  */
-int type_set_expand(type_set_t *set, ebitmap_t *t, policydb_t *p)
+int type_set_expand(type_set_t *set, ebitmap_t *t, policydb_t *p,
+	             unsigned char alwaysexpand)
 {
         int i;
         ebitmap_t types, neg_types;
@@ -1468,20 +1534,26 @@ int type_set_expand(type_set_t *set, ebi
         ebitmap_init(&types);
         ebitmap_init(t);
 
-        /* First go through the types and OR all the attributes to types */
-        for (i = ebitmap_startbit(&set->types); i < ebitmap_length(&set->types); i++) {
-                if (ebitmap_get_bit(&set->types, i)) {
-                        if (p->type_val_to_struct[i]->isattr) {
-                                if (ebitmap_union(&types, &p->type_val_to_struct[i]->types)) {
-                                        return -1;
-                                }
-                        } else {
-                                if (ebitmap_set_bit(&types, i, 1)) {
-                                        return -1;
-                                }
-                        }
-                }
-        }
+	if (alwaysexpand || ebitmap_length(&set->negset) || set->flags) {
+		/* First go through the types and OR all the attributes to types */
+		for (i = ebitmap_startbit(&set->types); i < ebitmap_length(&set->types); i++) {
+			if (ebitmap_get_bit(&set->types, i)) {
+				if (p->type_val_to_struct[i]->isattr) {
+					if (ebitmap_union(&types, &p->type_val_to_struct[i]->types)) {
+						return -1;
+					}
+				} else {
+					if (ebitmap_set_bit(&types, i, 1)) {
+						return -1;
+					}
+				}
+			}
+		}
+	} else {
+		/* No expansion of attributes, just copy the set as is. */
+		if (ebitmap_cpy(&types, &set->types))
+			return -1;
+	}
 
         /* Now do the same thing for negset */
         ebitmap_init(&neg_types);
@@ -1552,9 +1624,9 @@ static int copy_neverallow (policydb_t *
 	ebitmap_init(&stypes);
 	ebitmap_init(&ttypes);
 
-        if (expand_convert_type_set(source_pol, typemap, &source_rule->stypes, &stypes))
+        if (expand_convert_type_set(source_pol, typemap, &source_rule->stypes, &stypes, 1))
                 return -1;
-        if (expand_convert_type_set(source_pol, typemap, &source_rule->ttypes, &ttypes))
+        if (expand_convert_type_set(source_pol, typemap, &source_rule->ttypes, &ttypes, 1))
                 return -1;
 
         avrule = (avrule_t*)malloc(sizeof(avrule_t));
@@ -1613,7 +1685,7 @@ static int copy_neverallow (policydb_t *
 int expand_module(policydb_t *base, policydb_t *out,
                         int verbose, char *error_buf, size_t error_buf_size)
 {
-        int retval = -1;
+        int retval = -1, i;
 	expand_state_t state;
         avrule_block_t *curblock;
 	char *error_msg = NULL;
@@ -1652,6 +1724,11 @@ int expand_module(policydb_t *base, poli
         if (hashtab_map(state.base->p_types.table, type_copy_callback, &state)) {
                 goto cleanup;
         }
+
+	/* convert attribute type sets */
+        if (hashtab_map(state.base->p_types.table, attr_convert_callback, &state)) {
+                goto cleanup;
+        }
                 
         /* copy commons */
         if (hashtab_map(state.base->p_commons.table, common_copy_callback, &state)) {
@@ -1768,6 +1845,18 @@ int expand_module(policydb_t *base, poli
                 goto cleanup;
         }
 
+	/* Build the type->attribute reverse map and remove attributes. */
+	state.out->type_attr_map = malloc(state.out->p_types.nprim*
+					  sizeof(ebitmap_t));
+	for (i = 0; i < state.out->p_types.nprim; i++) {
+		ebitmap_init(&state.out->type_attr_map[i]);
+		/* add the type itself as the degenerate case */
+		if (ebitmap_set_bit(&state.out->type_attr_map[i], i, 1))
+				goto cleanup;
+	}
+	if (hashtab_map(state.out->p_types.table, type_attr_map, 
+			&state))
+		goto cleanup;
 	hashtab_map_remove_on_error(state.out->p_types.table, 
                                     type_attr_remove, 0, 0);
 	
diff -X /home/sds/dontdiff -rup libsepol-avtab1/src/policydb.c libsepol/src/policydb.c
--- libsepol-avtab1/src/policydb.c	2005-07-28 14:44:43.000000000 -0400
+++ libsepol/src/policydb.c	2005-07-28 14:48:44.000000000 -0400
@@ -427,7 +427,7 @@ int policydb_role_cache(hashtab_key_t ke
 	role = (role_datum_t *)datum;
 	p = (policydb_t *)arg;
 
-	if (type_set_expand(&role->types, &role->cache, p)) {
+	if (type_set_expand(&role->types, &role->cache, p, 1)) {
 		return -1;
 	}
 
@@ -936,6 +936,10 @@ void policydb_destroy(policydb_t * p)
 	}
 	if (lrt) free(lrt);
 
+	for (i = 0; i < p->p_types.nprim; i++)
+		ebitmap_destroy(&p->type_attr_map[i]);
+	free(p->type_attr_map);
+
 	return;
 }
 
@@ -2576,10 +2580,24 @@ int policydb_read(policydb_t * p, struct
 
 	if (r_policyvers >= POLICYDB_VERSION_MLS) {
                 if (range_read(p, fp)) {
-                        return -1;
+			goto bad;
                 }
 	}
 
+	p->type_attr_map = malloc(p->p_types.nprim*sizeof(ebitmap_t));
+	if (!p->type_attr_map)
+		goto bad;
+	for (i = 0; i < p->p_types.nprim; i++) {
+		ebitmap_init(&p->type_attr_map[i]);
+		if (r_policyvers >= POLICYDB_VERSION_AVTAB) {
+			if (ebitmap_read(&p->type_attr_map[i], fp))
+				goto bad;
+		}
+		/* add the type itself as the degenerate case */
+		if (ebitmap_set_bit(&p->type_attr_map[i], i, 1))
+				goto bad;
+	}
+
 	return 0;
 bad:
 	policydb_destroy(p);
diff -X /home/sds/dontdiff -rup libsepol-avtab1/src/services.c libsepol/src/services.c
--- libsepol-avtab1/src/services.c	2005-07-28 14:44:43.000000000 -0400
+++ libsepol/src/services.c	2005-07-28 14:48:44.000000000 -0400
@@ -306,6 +306,8 @@ static int context_struct_compute_av(con
 	avtab_key_t avkey;
 	class_datum_t *tclass_datum;
 	avtab_ptr_t node;
+	ebitmap_t *sattr, *tattr;
+	unsigned int i, j;
 
 	if (!tclass || tclass > policydb->p_classes.nprim) {
 		DEBUG(__FUNCTION__, "unrecognized class %d\n", tclass);
@@ -327,23 +329,36 @@ static int context_struct_compute_av(con
 	 * If a specific type enforcement rule was defined for
 	 * this permission check, then use it.
 	 */
-	avkey.source_type = scontext->type;
-	avkey.target_type = tcontext->type;
 	avkey.target_class = tclass;
 	avkey.specified = AVTAB_AV;
-	for (node = avtab_search_node(&policydb->te_avtab, &avkey);
-	     node != NULL;
-	     node = avtab_search_node_next(node, avkey.specified)) {
-		if (node->key.specified == AVTAB_ALLOWED)
-			avd->allowed = node->datum.data;
-		else if (node->key.specified == AVTAB_AUDITALLOW)
-			avd->auditallow = node->datum.data;
-		else if (node->key.specified == AVTAB_AUDITDENY)
-			avd->auditdeny = node->datum.data;
-	}
+	sattr = &policydb->type_attr_map[scontext->type - 1];
+	tattr = &policydb->type_attr_map[tcontext->type - 1];
+	for (i = ebitmap_startbit(sattr); 
+	     i < ebitmap_length(sattr); i++) {
+		if (!ebitmap_get_bit(sattr, i))
+		    continue;
+		for (j = ebitmap_startbit(tattr); 
+		     j < ebitmap_length(tattr); j++) {
+			if (!ebitmap_get_bit(tattr, j))
+				continue;
+			avkey.source_type = i + 1;
+			avkey.target_type = j + 1;
+			for (node = avtab_search_node(&policydb->te_avtab, &avkey);
+			     node != NULL;
+			     node = avtab_search_node_next(node, avkey.specified)) {
+				if (node->key.specified == AVTAB_ALLOWED)
+					avd->allowed |= node->datum.data;
+				else if (node->key.specified == AVTAB_AUDITALLOW)
+					avd->auditallow |= node->datum.data;
+				else if (node->key.specified == AVTAB_AUDITDENY)
+					avd->auditdeny &= node->datum.data;
+			}
+
+			/* Check conditional av table for additional permissions */
+			cond_compute_av(&policydb->te_cond_avtab, &avkey, avd);
 
-	/* Check conditional av table for additional permissions */
-	cond_compute_av(&policydb->te_cond_avtab, &avkey, avd);
+		}
+	}
 
 	if (requested & ~avd->allowed) {
 		*reason |= SEPOL_COMPUTEAV_TE;
diff -X /home/sds/dontdiff -rup libsepol-avtab1/src/write.c libsepol/src/write.c
--- libsepol-avtab1/src/write.c	2005-07-28 14:52:08.000000000 -0400
+++ libsepol/src/write.c	2005-07-29 10:36:33.000000000 -0400
@@ -288,6 +288,10 @@ static int avtab_write(avtab_t * a, stru
 		   track merged ones and compute the final nel. */
 		avtab_reset_merged(a);
 		nel = a->nel;
+		/* XXX:  Need to expand the avtab to write out older policies. */ 
+		DEBUG(__FUNCTION__, "missing compatibility support for policy "
+			"version %d\n", policyvers);
+		return -1;
 	} else {
 		/* New avtab format.  nel is good to go. */
 		nel = cpu_to_le32(a->nel);
@@ -1495,5 +1499,11 @@ int policydb_write(policydb_t * p, struc
                         return -1;
                 }
         }
+
+	if (policyvers >= POLICYDB_VERSION_AVTAB) {
+		for (i = 0; i < p->p_types.nprim; i++)
+			ebitmap_write(&p->type_attr_map[i], fp);
+	}
+
 	return 0;
 }


-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[RFC][PATCH 3/3] Reduce number of avtab nodes

[Stephen Smalley]

This patch, relative to the checkpolicy patch to reduce avtab node size,
updates checkpolicy for the changes to libsepol.

---

 checkpolicy.c  |    7 ++-----
 policy_parse.y |    6 +++---
 2 files changed, 5 insertions(+), 8 deletions(-)

diff -X /home/sds/dontdiff -rup checkpolicy-avtab1/checkpolicy.c checkpolicy/checkpolicy.c
--- checkpolicy-avtab1/checkpolicy.c	2005-07-28 14:47:49.000000000 -0400
+++ checkpolicy/checkpolicy.c	2005-07-28 14:49:06.000000000 -0400
@@ -584,14 +584,11 @@ int main(int argc, char **argv)
 		}
 
 		if (check_assertions(policydbp,
-                                     policydbp->global->branch_list->avrules,
-                                     &policydbp->te_avtab) ||
-		    check_assertions(policydbp,
-                                     policydbp->global->branch_list->avrules,
-                                     &policydbp->te_cond_avtab)) {
+                                     policydbp->global->branch_list->avrules)) {
                         fprintf(stderr, "Check assertions failed.\n");
 			return -1;
                 }
+
 		fclose(yyin);
 	}
 
diff -X /home/sds/dontdiff -rup checkpolicy-avtab1/policy_parse.y checkpolicy/policy_parse.y
--- checkpolicy-avtab1/policy_parse.y	2005-07-06 13:28:08.000000000 -0400
+++ checkpolicy/policy_parse.y	2005-07-28 14:49:06.000000000 -0400
@@ -2483,7 +2483,7 @@ static int dominate_role_recheck(hashtab
 	/* If a dominating role found */
 	if (ebitmap_get_bit(&(rdatum->dominates), rdp->value - 1))
 	{
-		if (type_set_expand(&rdp->types, types, policydbp)) 
+		if (type_set_expand(&rdp->types, types, policydbp, 1)) 
 			return -1;
 		/* raise types and dominates from dominated role */
 		for (i = ebitmap_startbit(&rdp->dominates); 
@@ -2564,7 +2564,7 @@ static role_datum_t *
 			if (ebitmap_get_bit(&r->dominates, i))
 				ebitmap_set_bit(&role->dominates, i, TRUE);
 		}
-		if (type_set_expand(&r->types, types, policydbp)) 
+		if (type_set_expand(&r->types, types, policydbp, 1)) 
 			return NULL;
 		for (i = ebitmap_startbit(types); i < ebitmap_length(types); i++)	{
 			if (ebitmap_get_bit(types, i))
@@ -2683,7 +2683,7 @@ static int define_role_trans(void)
 	if (role_set_expand(&roles, &e_roles, policydbp))
 		goto bad;
 		
-	if (type_set_expand(&types, &e_types, policydbp))
+	if (type_set_expand(&types, &e_types, policydbp, 1))
 		goto bad;
 
 	for (i = ebitmap_startbit(&e_roles); i < ebitmap_length(&e_roles); i++) {

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Fri, 2005-07-29 at 12:49 -0400, Stephen Smalley wrote:
> The following patch set reduces the number of avtab nodes by preserving
> attributes in TE allow/dontaudit/auditallow rules when possible rather
> than expanding them during policy compilation, and having the kernel use
> a type->attribute reverse map to perform the access vector computation,
> per the earlier discussions on the list.  This slows down security
> server computations, but these only occur on AVC cache misses, so the
> expected performance impact is negligible.  I have not yet attempted to
> measure the performance impact.  If it proves to be measurable at all,
> we can likely optimize it in the same manner that I used for the
> assertion checking code (see below).
> 
> Unlike the first patchset, where you could just patch the kernel and see
> the memory savings from the reduction in the per-node size even with a
> policy.19 file, this patch set requires you to patch your kernel,
> libsepol, and checkpolicy and build a policy.20 policy in order to see
> the reduction in nodes, as that is handled during compilation.

I forgot to mention:  when I tried recompiling the FC/devel strict
policy with the updated checkpolicy, it failed an assertion check
(neverallow statement) on one of the conditional rules.  Older
checkpolicy wasn't checking assertions on the conditional avtab, only on
the base avtab; this was fixed by Tresys as part of the module support
patches.  The assertion failure turned up to be that rpcd.te has a
create_dir_file(kernel_t, {file_type - shadow_t }) conditional rule if
nfs_export_all_rw is enabled, which means that kernel_t needs the
etc_writer attribute.  kernel.te only gives kernel_t the etc_writer
attribute _if_ the nfs_export_all_rw tunable is defined, but it is no
longer a tunable and has been converted to a boolean (and attribute
assignment isn't conditional).  Hence, I had to add that attribute
(without the ifdef) to compile the policy.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[James Morris]

On Fri, 29 Jul 2005, Stephen Smalley wrote:

> - I didn't increment the policy version again for this patch set,
> so it is still version 20, as with the prior patch set.  If we
> were to upstream these patches separately, I'd split them into separate
> versions, but if we roll them up for a single upstream change, there is
> no reason to separate them.

I would suggest rolling them into one policy version change.


- James
-- 
James Morris
<jmorris@redhat.com>


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[James Morris]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 562 bytes --]

The checkpolicy stuff doesn't compile for me:

$ make
cc -g -Wall -O2 -pipe -fno-strict-aliasing -I. -I/usr/include -o 
checkpolicy.o -c checkpolicy.c
checkpolicy.c: In function ‘cond_check_type_rules_list’:
checkpolicy.c:288: error: ‘avtab_key_t’ has no member named 
‘specified’
checkpolicy.c:289: error: too few arguments to function ‘avtab_search’
checkpolicy.c: In function ‘main’:
checkpolicy.c:587: error: too few arguments to function 
‘check_assertions’
make: *** [checkpolicy.o] Error 1



-- 
James Morris
<jmorris@redhat.com>

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Joshua Brindle]

James Morris wrote:

>The checkpolicy stuff doesn't compile for me:
>
>$ make
>cc -g -Wall -O2 -pipe -fno-strict-aliasing -I. -I/usr/include -o 
>checkpolicy.o -c checkpolicy.c
>checkpolicy.c: In function ‘cond_check_type_rules_list’:
>checkpolicy.c:288: error: ‘avtab_key_t’ has no member named 
>‘specified’
>checkpolicy.c:289: error: too few arguments to function ‘avtab_search’
>checkpolicy.c: In function ‘main’:
>checkpolicy.c:587: error: too few arguments to function 
>‘check_assertions’
>make: *** [checkpolicy.o] Error 1
>  
>
It looks like you are building against your system headers, building the 
entire selinux-usr repository with DESTDIR should work correctly

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[James Morris]

With these patches, on a 64-bit system, after boot:

  
            #objs  objsize   kernmem
Targeted:
  Before:  237888       40     9.1MB
  After:    19968       24     468KB

Strict:
  Before:  571680       40   21.81MB
  After:   221052       24    5.06MB

-- 
James Morris
<jmorris@redhat.com>


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Sun, 2005-07-31 at 11:59 -0400, James Morris wrote:
> With these patches, on a 64-bit system, after boot:
> 
>   
>             #objs  objsize   kernmem
> Targeted:
>   Before:  237888       40     9.1MB
>   After:    19968       24     468KB
> 
> Strict:
>   Before:  571680       40   21.81MB
>   After:   221052       24    5.06MB

Ok, this along with the data I posted for 32-bit is certainly
encouraging as far as memory savings are concerned.  Things that we need
to resolve before committing/upstreaming these changes include:

- We need to measure the performance impact of the changes on the
kernel, if any, and possibly optimize the compute_av code if it is
measurable.

- We need to write compatibility code for writing out older binary
policy versions from libsepol/checkpolicy for the latest change.  This
is necessary even just to support loading version 19 policies,
since /sbin/init and load_policy regenerate the binary policy image
in-memory when adjusting them for local boolean and user definitions and
thus need that support in policydb_write.

- We need to improve assertion checking time (neverallow rules), as it
is significantly slowed by the lack of an expanded avtab.

- We need to be sure that we are comfortable with collapsing the type
value space and class value space to 16 bits.  That was done by the
first patchset as part of reducing the avtab node size.  The avtab_read
code checks for value truncation when reading older binary policies; we
should also add checks to checkpolicy to ensure that we don't overflow
during policy compilation.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Luke Kenneth Casson Leighton]

On Mon, Aug 01, 2005 at 09:41:05AM -0400, Stephen Smalley wrote:
> On Sun, 2005-07-31 at 11:59 -0400, James Morris wrote:
> > With these patches, on a 64-bit system, after boot:
> > 
> >   
> >             #objs  objsize   kernmem
> > Targeted:
> >   Before:  237888       40     9.1MB
> >   After:    19968       24     468KB
> > 
> > Strict:
> >   Before:  571680       40   21.81MB
> >   After:   221052       24    5.06MB
> 
> Ok, this along with the data I posted for 32-bit is certainly
> encouraging as far as memory savings are concerned.  Things that we need
> to resolve before committing/upstreaming these changes include:
> 
> - We need to measure the performance impact of the changes on the
> kernel, if any, and possibly optimize the compute_av code if it is
> measurable.

 little story for you that is comp-sci related [which if
 you're aware of these sorts of things i humbly apologise for
 mentioning - grandmas, eggs, suck, sorry :) ]

 andrew tridgell wrote an upper-case / lower-case unicode
 converter for samba.  it wasn't a 16-bit lookup table,
 because 65536 * 2 equals 128kbytes which is _way_ more memory
 than can fit into a first level cache of some processors.
 consequently, performance of a lookup table would be crap.
 what he wrote instead was a small algorithm with lookup ranges.
 it was heaps faster.
 
 anyway, what you're doing is reminiscent of that and so
 i thought i should mention it and i invite you to consider
 performing some tests on hardware ranging from ARM 2-400mhz
 with the usual shit-for-brains caches through PIIIs and
 AMD K7s to P4s, picking the most likely candidates where
 it's going to matter or even possibly consider offering /
 enabling / disabling different optimisations depending on
 the processor target (CONFIG_xxx).

 again though i respectfully ask you to totally ignore me
 should you have considered these things already - comp-sci
 being what it is.

 l.


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Joshua Brindle]

Stephen Smalley wrote:

> <snip>
>
>- We need to be sure that we are comfortable with collapsing the type
>value space and class value space to 16 bits.  That was done by the
>first patchset as part of reducing the avtab node size.  The avtab_read
>code checks for value truncation when reading older binary policies; we
>should also add checks to checkpolicy to ensure that we don't overflow
>
>during policy compilation.
>
I know it won't affect the size but why not make all symbol value spaces 16 bits, just for consistency?

Also, here is a trivial patch to let audit2why compile with -Werror (which the Makefile in cvs does by default)

diff -purN nsa-patched/selinux-usr/libsepol/include/sepol/ebitmap.h nsa-new/selinux-usr/libsepol/include/sepol/ebitmap.h

--- nsa-patched/selinux-usr/libsepol/include/sepol/ebitmap.h    2005-08-01 10:53:54.503439624 -0400

+++ nsa-new/selinux-usr/libsepol/include/sepol/ebitmap.h        2005-08-01 10:51:25.564081848 -0400

@@ -46,7 +46,7 @@ static inline void ebitmap_init(ebitmap_

        memset(e, 0, sizeof(*e));

 }

-static inline unsigned int ebitmap_nextbit(ebitmap_t *e,

+static inline unsigned int ebitmap_nextbit(ebitmap_t *e __attribute__ ((__unused__)),

                                           ebitmap_node_t **n,

                                           unsigned int bit)

 {

@@ -59,7 +59,7 @@ static inline unsigned int ebitmap_nextb

        return (bit+1);

 }

-static inline int ebitmap_node_get_bit(ebitmap_t *e,

+static inline int ebitmap_node_get_bit(ebitmap_t *e __attribute__ ((__unused__)),

                                       ebitmap_node_t * n,

                                       unsigned int bit)

 {



--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Mon, 2005-08-01 at 10:58 -0400, Joshua Brindle wrote:
> I know it won't affect the size but why not make all symbol value
> spaces 16 bits, just for consistency?

Hmm..well, I didn't actually change the datum types, as you may have
noticed, even for types (e.g. struct type_datum).   I only shrank the
avtab types.  We could certainly shrink them all, but the compatibility
code begins to get increasingly ugly...

> Also, here is a trivial patch to let audit2why compile with -Werror
> (which the Makefile in cvs does by default)

Ah, thanks - hadn't tried rebuilding that after the latest changes.
libsepol itself needs to be changed to be built with stricter warning
flags, and the resulting warnings need to be cleaned up.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Mon, 2005-08-01 at 10:58 -0400, Joshua Brindle wrote:
> Stephen Smalley wrote:
> 
> > <snip>
> >
> >- We need to be sure that we are comfortable with collapsing the type
> >value space and class value space to 16 bits.  That was done by the
> >first patchset as part of reducing the avtab node size.  The avtab_read
> >code checks for value truncation when reading older binary policies; we
> >should also add checks to checkpolicy to ensure that we don't overflow
> >
> >during policy compilation.
> >
> I know it won't affect the size but why not make all symbol value
> spaces 16 bits, just for consistency?

Also, my real question here is whether we are sure that 16 bit value
space is going to be enough forever for types.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Joshua Brindle]

Stephen Smalley wrote:

>On Mon, 2005-08-01 at 10:58 -0400, Joshua Brindle wrote:
>  
>
>>Stephen Smalley wrote:
>>
>>    
>>
>>><snip>
>>>
>>>- We need to be sure that we are comfortable with collapsing the type
>>>value space and class value space to 16 bits.  That was done by the
>>>first patchset as part of reducing the avtab node size.  The avtab_read
>>>code checks for value truncation when reading older binary policies; we
>>>should also add checks to checkpolicy to ensure that we don't overflow
>>>
>>>during policy compilation.
>>>
>>>      
>>>
>>I know it won't affect the size but why not make all symbol value
>>spaces 16 bits, just for consistency?
>>    
>>
>
>Also, my real question here is whether we are sure that 16 bit value
>space is going to be enough forever for types.
>  
>
Right, which I didn't answer although I do think the answer is yes.

To reach the 16 bit limit the policy would have to grow ~50 times and by 
then the avtab size would be very large, even after the attribute patch 
would result in a ~250 meg avtab (assuming the type to rule growth is 
the same)

Trying to contrive an example where the 16 bit space would not be 
sufficient... A shell or webserver with 10's of thousands of customers 
where the security goal is to keep customers seperate via domains, but I 
don't really think this is a realistic example, at least not real enough 
to penalize all SELinux users in order to facilitate it.

But just incase.. how hard do you think it'd be to toggle the size via 
kernel config and checkpolicy flag? I know the compatibility is already 
ugly and this wouldn't help at all but if there is a genuine need for a 
larger value space in very specialized systems, it would be nice to 
allow that without optimizing the system for corner cases.

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Russell Coker]

On Tuesday 02 August 2005 01:09, Stephen Smalley <sds@tycho.nsa.gov> wrote:
> Also, my real question here is whether we are sure that 16 bit value
> space is going to be enough forever for types.

I don't think so.

One thing that was idly discussed was a public build server that would use one 
domain and several types for every package that was to be compiled.  When you 
look at distributions such as Debian with ~10,000 packages the number 64K 
doesn't seem so large.

But maybe the MCS policy will reduce the need for types.  How well would a 
system with 10,000 categories work?

-- 
http://www.coker.com.au/selinux/   My NSA Security Enhanced Linux packages
http://www.coker.com.au/bonnie++/  Bonnie++ hard drive benchmark
http://www.coker.com.au/postal/    Postal SMTP/POP benchmark
http://www.coker.com.au/~russell/  My home page

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 689 bytes --]

On Thu, 04 Aug 2005 17:57:50 +1000, Russell Coker said:

> One thing that was idly discussed was a public build server that would use one 
> domain and several types for every package that was to be compiled.  When you 
> look at distributions such as Debian with ~10,000 packages the number 64K 
> doesn't seem so large.

10K?? I only count 1,806 in Fedora Core 4....

What percent of these packages need any special handling other than
"run as the invoking user"? FC4 has about 180 .te files in domains/programs,
so just about 10% there.  I have *no* idea if "the next 8K packages" will
sustain that 10%, or if it will be significantly lower.

In any case, yes, that could run over 64K.

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Thu, 2005-08-04 at 10:35 -0400, Valdis.Kletnieks@vt.edu wrote:
> On Thu, 04 Aug 2005 17:57:50 +1000, Russell Coker said:
> 
> > One thing that was idly discussed was a public build server that would use one 
> > domain and several types for every package that was to be compiled.  When you 
> > look at distributions such as Debian with ~10,000 packages the number 64K 
> > doesn't seem so large.
> 
> 10K?? I only count 1,806 in Fedora Core 4....
> 
> What percent of these packages need any special handling other than
> "run as the invoking user"? FC4 has about 180 .te files in domains/programs,
> so just about 10% there.  I have *no* idea if "the next 8K packages" will
> sustain that 10%, or if it will be significantly lower.
> 
> In any case, yes, that could run over 64K.

But if you have >64K types, then your avtab is likely going to be so
large as to make the policy unuseable anyway, as noted by Joshua
earlier.

With regard to categories, since the relationships are implicit and
governed by the constraints, you don't get the kind of policy growth
from adding more categories that you would from adding more types.  So
if your goal is simply strict isolation between the different packages
during their builds (not the same as isolating the resulting programs
running on an end system), then categories may indeed be more suitable.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Joshua Brindle]

Stephen Smalley wrote:

>On Thu, 2005-08-04 at 10:35 -0400, Valdis.Kletnieks@vt.edu wrote:
>  
>
>>On Thu, 04 Aug 2005 17:57:50 +1000, Russell Coker said:
>>
>>    
>>
>>>One thing that was idly discussed was a public build server that would use one 
>>>domain and several types for every package that was to be compiled.  When you 
>>>look at distributions such as Debian with ~10,000 packages the number 64K 
>>>doesn't seem so large.
>>>      
>>>
>>10K?? I only count 1,806 in Fedora Core 4....
>>
>>What percent of these packages need any special handling other than
>>"run as the invoking user"? FC4 has about 180 .te files in domains/programs,
>>so just about 10% there.  I have *no* idea if "the next 8K packages" will
>>sustain that 10%, or if it will be significantly lower.
>>
>>    
>>
exactly, I suspect that most apps that need their own types and policy 
(mostly daemons) are already covered. The remaining stuff for users is 
really about constraining networked user applications. Even assuming 
that there are a couple hundred of these that require special treatment 
we won't even close to approach 64k types. Further, just because apps 
need to be confined doesn't mean they need their own types, it's 
concievable that all 'unprivileged' user apps could run in the same 
domain (unless they process sensitive information)

>>In any case, yes, that could run over 64K.
>>    
>>
>
>But if you have >64K types, then your avtab is likely going to be so
>large as to make the policy unuseable anyway, as noted by Joshua
>earlier.
>
>With regard to categories, since the relationships are implicit and
>governed by the constraints, you don't get the kind of policy growth
>from adding more categories that you would from adding more types.  So
>if your goal is simply strict isolation between the different packages
>during their builds (not the same as isolating the resulting programs
>running on an end system), then categories may indeed be more suitable.
>  
>
Making a category for each type of application? It would work but it 
seems kind of awkward

This is interesting though. If your security model is to isolate all 
applications there are more possibilities than just using types. Roles, 
users and level can all be used. The bad thing about users and roles is 
that object access would be harder to isolate but mls levels can 
certainly address this.

But just incase (also mentioned in a previous email), would it be 
possible to use a macro in the kernel to switch between 16 and 32 bit 
avtab keys in the kernel and then make checkpolicy write a "fat" policy 
if the types exceed 16 bits? This would allow the possibility of having 
a huge number of types without penalizing all users.

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Thu, 2005-08-04 at 11:38 -0400, Joshua Brindle wrote:
> But just incase (also mentioned in a previous email), would it be 
> possible to use a macro in the kernel to switch between 16 and 32 bit 
> avtab keys in the kernel and then make checkpolicy write a "fat" policy 
> if the types exceed 16 bits? This would allow the possibility of having 
> a huge number of types without penalizing all users.

I don't think we want a kernel config option altering the expected
binary policy format.  That would also mean that /selinux/policyvers ==
n could have two meanings depending on how the kernel was configured,
leaving userspace rather confused about what to provide it.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Joshua Brindle]

Stephen Smalley wrote:

>On Thu, 2005-08-04 at 11:38 -0400, Joshua Brindle wrote:
>  
>
>>But just incase (also mentioned in a previous email), would it be 
>>possible to use a macro in the kernel to switch between 16 and 32 bit 
>>avtab keys in the kernel and then make checkpolicy write a "fat" policy 
>>if the types exceed 16 bits? This would allow the possibility of having 
>>a huge number of types without penalizing all users.
>>    
>>
>
>I don't think we want a kernel config option altering the expected
>binary policy format.  That would also mean that /selinux/policyvers ==
>n could have two meanings depending on how the kernel was configured,
>leaving userspace rather confused about what to provide it.
>  
>
This is exactly what the old MLS system did right? I suppose that was 
removed and for the better...

So, why not add a value size table to the header of the policy? I know 
this makes reads (and writes) a real pain but some cleaver unions could 
make that easier :)

Anyway, it's just a suggestion, I honestly don't know if it will ever be 
needed but I believe that it's much better to keep the smaller fields 
since the vast majority of the cases will benefit from it and only 
radical corner cases would be affected.

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Russell Coker]

On Friday 05 August 2005 00:38, Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On Thu, 2005-08-04 at 10:35 -0400, Valdis.Kletnieks@vt.edu wrote:
> > On Thu, 04 Aug 2005 17:57:50 +1000, Russell Coker said:
> > > One thing that was idly discussed was a public build server that would
> > > use one domain and several types for every package that was to be
> > > compiled.  When you look at distributions such as Debian with ~10,000
> > > packages the number 64K doesn't seem so large.
> >
> > 10K?? I only count 1,806 in Fedora Core 4....

In terms of 10K packages I was referring to Debian.  If Fedora Extras meets my 
personal criteria for success then it will bring the size of Fedora to the 
same approximate size as Debian.  Also we want to support all the operations 
on all distributions.

> > What percent of these packages need any special handling other than
> > "run as the invoking user"? FC4 has about 180 .te files in
> > domains/programs, so just about 10% there.  I have *no* idea if "the next
> > 8K packages" will sustain that 10%, or if it will be significantly lower.

The idea is that when the build system compiles a package the compilation 
scripts should not be able to interfere with other compilations (apart from 
running out of memory or other system resources).  One issue is that of 
hostile build scripts, having a hostile package do bad things when the 
package in question is installed has a lot of potential for damage.  Allowing 
the build scripts to trash the build system or corrupt other packages such 
that it can't easily be determined which package started the damage would be 
a worse situation.

> > In any case, yes, that could run over 64K.
>
> But if you have >64K types, then your avtab is likely going to be so
> large as to make the policy unuseable anyway, as noted by Joshua
> earlier.

OK.

> With regard to categories, since the relationships are implicit and
> governed by the constraints, you don't get the kind of policy growth
> from adding more categories that you would from adding more types.  So
> if your goal is simply strict isolation between the different packages
> during their builds (not the same as isolating the resulting programs
> running on an end system), then categories may indeed be more suitable.

So there is no inherent problem with 10,000 categories?

-- 
http://www.coker.com.au/selinux/   My NSA Security Enhanced Linux packages
http://www.coker.com.au/bonnie++/  Bonnie++ hard drive benchmark
http://www.coker.com.au/postal/    Postal SMTP/POP benchmark
http://www.coker.com.au/~russell/  My home page

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Mon, 2005-08-01 at 09:41 -0400, Stephen Smalley wrote:
> - We need to write compatibility code for writing out older binary
> policy versions from libsepol/checkpolicy for the latest change.  This
> is necessary even just to support loading version 19 policies,
> since /sbin/init and load_policy regenerate the binary policy image
> in-memory when adjusting them for local boolean and user definitions and
> thus need that support in policydb_write.

This patch, relative to the prior ones, adds this compatibility code.
It implements it by creating an in-memory attr->type map and then using
this map to expand the avtab and cond av lists when writing out an older
binary policy version.  The attr->type map has to be created by both the
expand_module code (where it is trivial to do so before we discard
attribute information) and by the policydb_read code, so that the
compatibility code works regardless of whether we are compiling an older
binary policy version (e.g. checkpolicy -c 19) or simply mutating an
in-memory policydb originally created from a kernel binary policy file
for local settings (e.g. /sbin/init and load_policy's use of
sepol_genusers/genbools).  This lets me boot an unpatched kernel with a
policy.19 and the new libsepol installed, without /sbin/init choking on
sepol_genusers/genbools.

It occurred to me that the simple checks of policyvers <
POLICYDB_VERSION_AVTAB might be breaking the module support, so I
started qualifying them with an additional policy_type == POLICY_KERN
test as well, but it looks like the same issue exists for other
policyvers checks, e.g. for MLS, VALIDATETRANS, etc.  Shouldn't all such
policy version checks be qualified with the policy_type as well on both
the read-side and write-side in libsepol?

It would also be good for someone to sanity check that these patches are
sane with respect to conditional policy, although they seem to be
correct.

diff -X /home/sds/dontdiff -rup libsepol.a/include/sepol/conditional.h libsepol/include/sepol/conditional.h
--- libsepol.a/include/sepol/conditional.h	2005-07-13 15:26:17.000000000 -0400
+++ libsepol/include/sepol/conditional.h	2005-08-01 16:31:40.000000000 -0400
@@ -107,6 +107,8 @@ extern int evaluate_conds(policydb_t *p)
 extern avtab_datum_t *cond_av_list_search(
 	avtab_key_t *key, cond_av_list_t *cond_list);
 
+extern void cond_av_list_destroy(cond_av_list_t *list);
+
 extern void cond_optimize_lists(cond_list_t *cl);
 
 extern int cond_policydb_init(policydb_t* p);
diff -X /home/sds/dontdiff -rup libsepol.a/include/sepol/expand.h libsepol/include/sepol/expand.h
--- libsepol.a/include/sepol/expand.h	2005-07-28 14:48:44.000000000 -0400
+++ libsepol/include/sepol/expand.h	2005-08-02 11:00:36.000000000 -0400
@@ -37,4 +37,9 @@ extern int expand_rule(policydb_t *sourc
                 cond_av_list_t **cond, cond_av_list_t **other,
                 int enabled, char **error_msg);
 
+extern int expand_avtab(policydb_t *p, avtab_t *a, avtab_t *expa);
+
+extern int expand_cond_av_list(policydb_t *p, cond_av_list_t *l,
+			       cond_av_list_t **newl, avtab_t *expa);
+
 #endif
diff -X /home/sds/dontdiff -rup libsepol.a/include/sepol/policydb.h libsepol/include/sepol/policydb.h
--- libsepol.a/include/sepol/policydb.h	2005-07-28 14:48:44.000000000 -0400
+++ libsepol/include/sepol/policydb.h	2005-08-01 13:15:30.000000000 -0400
@@ -433,6 +433,8 @@ typedef struct policydb {
 
 	ebitmap_t *type_attr_map;
 
+	ebitmap_t *attr_type_map; /* not saved in the binary policy */
+
 	unsigned policyvers;
 } policydb_t;
 
diff -X /home/sds/dontdiff -rup libsepol.a/src/conditional.c libsepol/src/conditional.c
--- libsepol.a/src/conditional.c	2005-07-28 14:44:43.000000000 -0400
+++ libsepol/src/conditional.c	2005-08-01 16:31:08.000000000 -0400
@@ -419,7 +419,7 @@ int cond_policydb_init(policydb_t *p)
 	return 0;
 }
 
-static void cond_av_list_destroy(cond_av_list_t *list)
+void cond_av_list_destroy(cond_av_list_t *list)
 {
 	cond_av_list_t *cur, *next;
 	for (cur = list; cur != NULL; cur = next) {
diff -X /home/sds/dontdiff -rup libsepol.a/src/expand.c libsepol/src/expand.c
--- libsepol.a/src/expand.c	2005-07-28 14:48:47.000000000 -0400
+++ libsepol/src/expand.c	2005-08-02 11:46:31.000000000 -0400
@@ -33,6 +33,8 @@
 #include <string.h>
 #include <assert.h>
 
+#include "debug.h"
+
 typedef struct expand_state {
 	int verbose;
 	uint32_t *typemap;
@@ -1407,12 +1409,19 @@ static int type_attr_map(hashtab_key_t k
 
 	type = (type_datum_t *) datum;
 	if (type->isattr) {
+		if (ebitmap_cpy(&p->attr_type_map[type->value-1],
+				&type->types)) {
+			write_error(state, "Out of memory!");
+			return -1;
+		}
 		for (i = ebitmap_startbit(&type->types); 
 		     i < ebitmap_length(&type->types); i++) 
 			if (ebitmap_get_bit(&type->types, i)) {
 				if (ebitmap_set_bit(&p->type_attr_map[i],
-						    type->value - 1, 1))
+						    type->value - 1, 1)) {
+					write_error(state, "Out of memory!");
 					return -1;
+				}
 			}
 	}
 	return 0;
@@ -1845,20 +1854,29 @@ int expand_module(policydb_t *base, poli
                 goto cleanup;
         }
 
-	/* Build the type->attribute reverse map and remove attributes. */
+	/* Build the type<->attribute maps and remove attributes. */
+	state.out->attr_type_map = malloc(state.out->p_types.nprim*
+					  sizeof(ebitmap_t));
 	state.out->type_attr_map = malloc(state.out->p_types.nprim*
 					  sizeof(ebitmap_t));
+	if (!state.out->attr_type_map || !state.out->type_attr_map) {
+		write_error(&state, "Out of memory!");
+		goto cleanup;
+	}
 	for (i = 0; i < state.out->p_types.nprim; i++) {
 		ebitmap_init(&state.out->type_attr_map[i]);
+		ebitmap_init(&state.out->attr_type_map[i]);
 		/* add the type itself as the degenerate case */
-		if (ebitmap_set_bit(&state.out->type_attr_map[i], i, 1))
-				goto cleanup;
+		if (ebitmap_set_bit(&state.out->type_attr_map[i], i, 1)) {
+			write_error(&state, "Out of memory!");
+			goto cleanup;
+		}
 	}
 	if (hashtab_map(state.out->p_types.table, type_attr_map, 
 			&state))
 		goto cleanup;
 	hashtab_map_remove_on_error(state.out->p_types.table, 
-                                    type_attr_remove, 0, 0);
+				    type_attr_remove, 0, 0);
 	
         retval = 0;
 
@@ -1866,3 +1884,273 @@ int expand_module(policydb_t *base, poli
         free (state.typemap);
         return retval;
 }
+
+static int expand_avtab_insert(avtab_t *a, avtab_key_t *k, avtab_datum_t *d)
+{
+	avtab_datum_t *avd;
+	int rc;
+
+	avd = avtab_search(a, k);
+	if (!avd) {
+		rc = avtab_insert(a, k, d);
+		if (rc)
+			DEBUG(__FUNCTION__, "Out of memory!\n");
+		return rc;
+	}
+	
+	switch (k->specified & ~AVTAB_ENABLED) {
+	case AVTAB_ALLOWED:
+	case AVTAB_AUDITALLOW:
+		avd->data |= d->data;
+		break;
+	case AVTAB_AUDITDENY:
+		avd->data &= d->data;
+		break;
+	default:
+		DEBUG(__FUNCTION__, "Type conflict!\n");
+		return -1;
+	}
+
+	return 0;
+}
+
+struct expand_avtab_data {
+	avtab_t *expa;
+	policydb_t *p;
+  
+};
+
+static int expand_avtab_node(avtab_key_t *k, avtab_datum_t *d, void *args) 
+{
+	struct expand_avtab_data *ptr = args;
+	avtab_t *expa = ptr->expa;
+	policydb_t *p = ptr->p;
+	type_datum_t *stype = p->type_val_to_struct[k->source_type-1];
+	type_datum_t *ttype = p->type_val_to_struct[k->target_type-1];
+	ebitmap_t *sattr = &p->attr_type_map[k->source_type-1];
+	ebitmap_t *tattr = &p->attr_type_map[k->target_type-1];
+	ebitmap_node_t *snode, *tnode;
+	unsigned int i, j;
+	avtab_key_t newkey;
+	int rc;
+
+	newkey.target_class = k->target_class;
+	newkey.specified = k->specified;
+
+	if (stype && ttype) {
+		/* Both are individual types, no expansion required. */
+		return expand_avtab_insert(expa, k, d);
+	}
+
+	if (stype) {
+		/* Source is an individual type, target is an attribute. */
+		newkey.source_type = k->source_type;
+		for (j = ebitmap_startbit(tattr), 
+			     tnode = ebitmap_startnode(tattr); 
+		     j < ebitmap_length(tattr); 
+		     j = ebitmap_nextbit(tattr, &tnode, j)) {
+			if (!ebitmap_node_get_bit(tattr, tnode, j))
+				continue;
+			newkey.target_type = j + 1;
+			rc = expand_avtab_insert(expa, &newkey, d);
+			if (rc)
+				return -1;
+		}
+		return 0;
+	}
+
+	if (ttype) {
+		/* Target is an individual type, source is an attribute. */
+		newkey.target_type = k->target_type;
+		for (i = ebitmap_startbit(sattr), 
+			     snode = ebitmap_startnode(sattr);
+		     i < ebitmap_length(sattr); 
+		     i = ebitmap_nextbit(sattr, &snode, i)) {
+			if (!ebitmap_node_get_bit(sattr, snode, i))
+				continue;
+			newkey.source_type = i + 1;
+			rc = expand_avtab_insert(expa, &newkey, d);
+			if (rc)
+				return -1;
+		}
+		return 0;
+	}
+
+	/* Both source and target type are attributes. */
+	for (i = ebitmap_startbit(sattr), 
+		     snode = ebitmap_startnode(sattr);
+	     i < ebitmap_length(sattr); 
+	     i = ebitmap_nextbit(sattr, &snode, i)) {
+		if (!ebitmap_node_get_bit(sattr, snode, i))
+			continue;
+		for (j = ebitmap_startbit(tattr), 
+			     tnode = ebitmap_startnode(tattr); 
+		     j < ebitmap_length(tattr); 
+		     j = ebitmap_nextbit(tattr, &tnode, j)) {
+			if (!ebitmap_node_get_bit(tattr, tnode, j))
+				continue;
+			newkey.source_type = i + 1;
+			newkey.target_type = j + 1;
+			rc = expand_avtab_insert(expa, &newkey, d);
+			if (rc)
+				return -1;
+		}
+	}
+
+	return 0;
+}
+
+int expand_avtab(policydb_t *p, avtab_t *a, avtab_t *expa)
+{
+	struct expand_avtab_data data;
+
+	data.expa = expa;
+	data.p = p;
+	return avtab_map(a, expand_avtab_node, &data);
+}
+
+static int expand_cond_insert(cond_av_list_t **l, 
+			      avtab_t *expa,
+			      avtab_key_t *k, avtab_datum_t *d)
+{
+	avtab_ptr_t node;
+	avtab_datum_t *avd;
+	cond_av_list_t *nl;
+
+	node = avtab_search_node(expa, k);
+	if (!node) {
+		node = avtab_insert_nonunique(expa, k, d);
+		if (!node) {
+			DEBUG(__FUNCTION__, "Out of memory!\n");
+			return -1;
+		}
+		node->parse_context = (void*)1;
+		nl = (cond_av_list_t *) malloc(sizeof(*nl));
+		if (!nl) {
+			DEBUG(__FUNCTION__, "Out of memory!\n");
+			return -1;
+		}
+		memset(nl, 0, sizeof(*nl));
+		nl->node = node;
+		nl->next = *l;
+		*l = nl;
+		return 0;
+	}
+
+	avd = &node->datum;
+	switch (k->specified & ~AVTAB_ENABLED) {
+	case AVTAB_ALLOWED:
+	case AVTAB_AUDITALLOW:
+		avd->data |= d->data;
+		break;
+	case AVTAB_AUDITDENY:
+		avd->data &= d->data;
+		break;
+	default:
+		DEBUG(__FUNCTION__, "Type conflict!\n");
+		return -1;
+	}
+
+	return 0;
+}
+
+
+int expand_cond_av_node(policydb_t *p, 
+			avtab_ptr_t node,
+			cond_av_list_t **newl,
+			avtab_t *expa)
+{
+	avtab_key_t *k = &node->key;
+	avtab_datum_t *d = &node->datum;
+	type_datum_t *stype = p->type_val_to_struct[k->source_type-1];
+	type_datum_t *ttype = p->type_val_to_struct[k->target_type-1];
+	ebitmap_t *sattr = &p->attr_type_map[k->source_type-1];
+	ebitmap_t *tattr = &p->attr_type_map[k->target_type-1];
+	ebitmap_node_t *snode, *tnode;
+	unsigned int i, j;
+	avtab_key_t newkey;
+	int rc;
+
+	newkey.target_class = k->target_class;
+	newkey.specified = k->specified;
+
+	if (stype && ttype) {
+		/* Both are individual types, no expansion required. */
+		return expand_cond_insert(newl, expa, k, d);
+	}
+
+	if (stype) {
+		/* Source is an individual type, target is an attribute. */
+		newkey.source_type = k->source_type;
+		for (j = ebitmap_startbit(tattr), 
+			     tnode = ebitmap_startnode(tattr); 
+		     j < ebitmap_length(tattr); 
+		     j = ebitmap_nextbit(tattr, &tnode, j)) {
+			if (!ebitmap_node_get_bit(tattr, tnode, j))
+				continue;
+			newkey.target_type = j + 1;
+			rc = expand_cond_insert(newl, expa, &newkey, d);
+			if (rc)
+				return -1;
+		}
+		return 0;
+	}
+
+	if (ttype) {
+		/* Target is an individual type, source is an attribute. */
+		newkey.target_type = k->target_type;
+		for (i = ebitmap_startbit(sattr), 
+			     snode = ebitmap_startnode(sattr);
+		     i < ebitmap_length(sattr); 
+		     i = ebitmap_nextbit(sattr, &snode, i)) {
+			if (!ebitmap_node_get_bit(sattr, snode, i))
+				continue;
+			newkey.source_type = i + 1;
+			rc = expand_cond_insert(newl, expa, &newkey, d);
+			if (rc)
+				return -1;
+		}
+		return 0;
+	}
+
+	/* Both source and target type are attributes. */
+	for (i = ebitmap_startbit(sattr), 
+		     snode = ebitmap_startnode(sattr);
+	     i < ebitmap_length(sattr); 
+	     i = ebitmap_nextbit(sattr, &snode, i)) {
+		if (!ebitmap_node_get_bit(sattr, snode, i))
+			continue;
+		for (j = ebitmap_startbit(tattr), 
+			     tnode = ebitmap_startnode(tattr); 
+		     j < ebitmap_length(tattr); 
+		     j = ebitmap_nextbit(tattr, &tnode, j)) {
+			if (!ebitmap_node_get_bit(tattr, tnode, j))
+				continue;
+			newkey.source_type = i + 1;
+			newkey.target_type = j + 1;
+			rc = expand_cond_insert(newl, expa, &newkey, d);
+			if (rc)
+				return -1;
+		}
+	}
+
+	return 0;
+}
+
+int expand_cond_av_list(policydb_t *p, cond_av_list_t *l,
+			cond_av_list_t **newl, avtab_t *expa)
+{
+	cond_av_list_t *cur;
+	avtab_ptr_t node;
+	int rc;
+
+	*newl = NULL;
+	for (cur = l; cur; cur = cur->next) {
+		node = cur->node;
+		rc = expand_cond_av_node(p, node, newl, expa);
+		if (rc)
+			return rc;
+	}
+
+	return 0;
+}
diff -X /home/sds/dontdiff -rup libsepol.a/src/policydb.c libsepol/src/policydb.c
--- libsepol.a/src/policydb.c	2005-07-28 14:48:44.000000000 -0400
+++ libsepol/src/policydb.c	2005-08-02 09:45:55.000000000 -0400
@@ -936,9 +936,12 @@ void policydb_destroy(policydb_t * p)
 	}
 	if (lrt) free(lrt);
 
-	for (i = 0; i < p->p_types.nprim; i++)
+	for (i = 0; i < p->p_types.nprim; i++) {
 		ebitmap_destroy(&p->type_attr_map[i]);
+		ebitmap_destroy(&p->attr_type_map[i]);
+	}
 	free(p->type_attr_map);
+	free(p->attr_type_map);
 
 	return;
 }
@@ -2585,13 +2588,24 @@ int policydb_read(policydb_t * p, struct
 	}
 
 	p->type_attr_map = malloc(p->p_types.nprim*sizeof(ebitmap_t));
-	if (!p->type_attr_map)
+	p->attr_type_map = malloc(p->p_types.nprim*sizeof(ebitmap_t));
+	if (!p->type_attr_map || !p->attr_type_map)
 		goto bad;
 	for (i = 0; i < p->p_types.nprim; i++) {
 		ebitmap_init(&p->type_attr_map[i]);
+		ebitmap_init(&p->attr_type_map[i]);
+	}
+	for (i = 0; i < p->p_types.nprim; i++) {
 		if (r_policyvers >= POLICYDB_VERSION_AVTAB) {
 			if (ebitmap_read(&p->type_attr_map[i], fp))
 				goto bad;
+			for (j = ebitmap_startbit(&p->type_attr_map[i]);
+			     j < ebitmap_length(&p->type_attr_map[i]); j++) {
+				if (!ebitmap_get_bit(&p->type_attr_map[i], j)) 
+					continue;
+				if (ebitmap_set_bit(&p->attr_type_map[j], i, 1))
+					goto bad;
+			}
 		}
 		/* add the type itself as the degenerate case */
 		if (ebitmap_set_bit(&p->type_attr_map[i], i, 1))
diff -X /home/sds/dontdiff -rup libsepol.a/src/write.c libsepol/src/write.c
--- libsepol.a/src/write.c	2005-07-29 10:36:33.000000000 -0400
+++ libsepol/src/write.c	2005-08-02 11:47:00.000000000 -0400
@@ -39,6 +39,7 @@
 #include <sepol/mls.h>
 #include <sepol/policydb.h>
 #include <sepol/conditional.h>
+#include <sepol/expand.h>
 
 #include "debug.h"
 #include "private.h"
@@ -148,9 +149,10 @@ static int avtab_write_item(avtab_ptr_t 
 	uint32_t buf32[10], lookup, val;
 	size_t items, items2;
 	unsigned set;
+	unsigned int oldvers = (policy_type == POLICY_KERN && policyvers < POLICYDB_VERSION_AVTAB);
 	int i;
 
-	if (policyvers < POLICYDB_VERSION_AVTAB) {
+	if (oldvers) {
 		/* Generate the old avtab format.
 		   Requires merging similar entries if uncond avtab. */
 		if (merge) {
@@ -273,25 +275,31 @@ static inline void avtab_reset_merged(av
 	}
 }
 
-static int avtab_write(avtab_t * a, struct policy_file * fp)
+static int avtab_write(struct policydb *p, 
+		       avtab_t * a, struct policy_file * fp)
 {
-	int i;
+	int i, rc;
+	avtab_t expa;
 	avtab_ptr_t cur;
 	uint32_t nel;
 	size_t items;
-	unsigned int oldvers = policyvers < POLICYDB_VERSION_AVTAB;
+	unsigned int oldvers = (policy_type == POLICY_KERN && policyvers < POLICYDB_VERSION_AVTAB);
 
 
 	if (oldvers) {
 		/* Old avtab format.
-		   Requires merging similar entries, so need to
-		   track merged ones and compute the final nel. */
+		   First, we need to expand attributes.  Then, we need to
+		   merge similar entries, so we need to track merged nodes 
+		   and compute the final nel. */
+		if (avtab_init(&expa))
+			return -1;
+		if (expand_avtab(p, a, &expa)) {
+			rc = -1;
+			goto out;
+		}
+		a = &expa;
 		avtab_reset_merged(a);
 		nel = a->nel;
-		/* XXX:  Need to expand the avtab to write out older policies. */ 
-		DEBUG(__FUNCTION__, "missing compatibility support for policy "
-			"version %d\n", policyvers);
-		return -1;
 	} else {
 		/* New avtab format.  nel is good to go. */
 		nel = cpu_to_le32(a->nel);
@@ -304,8 +312,10 @@ static int avtab_write(avtab_t * a, stru
 		for (cur = a->htable[i]; cur; cur = cur->next) {
 			/* If old format, compute final nel.
 			   If new format, write out the items. */
-			if (avtab_write_item(cur, fp, 1, !oldvers, &nel))
-			    return -1;
+			if (avtab_write_item(cur, fp, 1, !oldvers, &nel)) {
+				rc = -1;
+				goto out;
+			}
 		}	
 	}
 
@@ -314,18 +324,26 @@ static int avtab_write(avtab_t * a, stru
 		   Write the computed nel value, then write the items. */
 		nel = cpu_to_le32(nel);
 		items = put_entry(&nel, sizeof(uint32_t), 1, fp);
-		if (items != 1)
-			return -1;
+		if (items != 1) {
+			rc = -1;
+			goto out;
+		}
 		avtab_reset_merged(a);
 		for (i = 0; i < AVTAB_SIZE; i++) {
 			for (cur = a->htable[i]; cur; cur = cur->next) {
-				if (avtab_write_item(cur, fp, 1, 1, NULL))
-					return -1;
+				if (avtab_write_item(cur, fp, 1, 1, NULL)) {
+					rc = -1;
+					goto out;
+				}
 			}	
 		}
 	}
 
-	return 0;
+	rc = 0;
+out:
+	if (oldvers)
+		avtab_destroy(&expa);
+	return rc;
 }
 
 /*
@@ -549,11 +567,23 @@ static int cond_write_bool(hashtab_key_t
  * the conditional. This means that the avtab with the conditional
  * rules will not be saved but will be rebuilt on policy load.
  */
-static int cond_write_av_list(cond_av_list_t *list, struct policy_file *fp)
+static int cond_write_av_list(policydb_t *p,
+			      cond_av_list_t *list, struct policy_file *fp)
 {
 	uint32_t buf[4];
-	cond_av_list_t *cur_list;
+	cond_av_list_t *cur_list, *new_list = NULL;
+	avtab_t expa;
 	uint32_t len, items;
+	unsigned int oldvers = (policy_type == POLICY_KERN && policyvers < POLICYDB_VERSION_AVTAB);
+	int rc = -1;
+
+	if (oldvers) {
+		if (avtab_init(&expa))
+			return -1;
+		if (expand_cond_av_list(p, list, &new_list, &expa))
+			goto out;
+		list = new_list;
+	}
 
 	len = 0;
 	for (cur_list = list; cur_list != NULL; cur_list = cur_list->next) {
@@ -564,19 +594,30 @@ static int cond_write_av_list(cond_av_li
 	buf[0] = cpu_to_le32(len);
 	items = put_entry(buf, sizeof(uint32_t), 1, fp);
 	if (items != 1)
-		return -1;
-	if (items == 0)
-		return 0;
+		goto out;
+	if (items == 0) {
+		rc = 0;
+		goto out;
+	}
 
 	for (cur_list = list; cur_list != NULL; cur_list = cur_list->next) {
 		if (cur_list->node->parse_context)
 			if (avtab_write_item(cur_list->node, fp, 0, 1, NULL))
-				return -1;
+				goto out;
 	}
-	return 0;
+
+	rc = 0;
+out:
+	if (oldvers) {
+		cond_av_list_destroy(new_list);
+		avtab_destroy(&expa);
+	}
+
+	return rc;
 }
 
-static int cond_write_node(cond_node_t *node, struct policy_file *fp)
+static int cond_write_node(policydb_t *p, 
+			   cond_node_t *node, struct policy_file *fp)
 {
 	cond_expr_t *cur_expr;
 	uint32_t buf[2];
@@ -607,9 +648,9 @@ static int cond_write_node(cond_node_t *
 	}
 
         if (policy_type == POLICY_KERN) {
-		if (cond_write_av_list(node->true_list, fp) != 0)
+		if (cond_write_av_list(p, node->true_list, fp) != 0)
 			return -1;
-		if (cond_write_av_list(node->false_list, fp) != 0)
+		if (cond_write_av_list(p, node->false_list, fp) != 0)
 			return -1;
 	} else {
 		if (avrule_write_list(node->avtrue_list, fp))
@@ -621,9 +662,8 @@ static int cond_write_node(cond_node_t *
 	return 0;
 }
 
-static int cond_write_list(cond_list_t *list, struct policy_file *p)
+static int cond_write_list(policydb_t *p, cond_list_t *list, struct policy_file *fp)
 {
-	struct policy_file *fp = p;
 	cond_node_t *cur;
 	uint32_t len, items;
 	uint32_t buf[1];
@@ -637,7 +677,7 @@ static int cond_write_list(cond_list_t *
 		return -1;
 
 	for (cur = list; cur != NULL; cur = cur->next) {
-		if (cond_write_node(cur, p) != 0)
+		if (cond_write_node(p, cur, fp) != 0)
 			return -1;
 	}
 	return 0;
@@ -1275,7 +1315,7 @@ static int avrule_decl_write(avrule_decl
         if (put_entry(buf, sizeof(uint32_t), 2, fp) != 2) {
                 return -1;
         }
-        if (cond_write_list(decl->cond_list, fp) == -1 ||
+        if (cond_write_list(NULL, decl->cond_list, fp) == -1 ||
             avrule_write_list(decl->avrules, fp) == -1 ||
             role_trans_rule_write(decl->role_tr_rules, fp) == -1 ||
             role_allow_rule_write(decl->role_allow_rules, fp) == -1) {
@@ -1458,7 +1498,7 @@ int policydb_write(policydb_t * p, struc
 	}
 
 	if (p->policy_type == POLICY_KERN) {
-		if (avtab_write(&p->te_avtab, fp))
+		if (avtab_write(p, &p->te_avtab, fp))
 			return -1;
                 if (policyvers < POLICYDB_VERSION_BOOL) {
                         if (p->p_bools.nprim)
@@ -1466,7 +1506,7 @@ int policydb_write(policydb_t * p, struc
 					"booleans and conditional rules\n");
                 }
                 else {
-                        if (cond_write_list(p->cond_list, fp))
+                        if (cond_write_list(p, p->cond_list, fp))
                                 return -1;
                 }
                 if (role_trans_write(p->role_tr, fp))



  
-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Tue, 2005-08-02 at 12:43 -0400, Stephen Smalley wrote:
> On Mon, 2005-08-01 at 09:41 -0400, Stephen Smalley wrote:
> > - We need to write compatibility code for writing out older binary
> > policy versions from libsepol/checkpolicy for the latest change.  This
> > is necessary even just to support loading version 19 policies,
> > since /sbin/init and load_policy regenerate the binary policy image
> > in-memory when adjusting them for local boolean and user definitions and
> > thus need that support in policydb_write.
> 
> This patch, relative to the prior ones, adds this compatibility code.
> It implements it by creating an in-memory attr->type map and then using
> this map to expand the avtab and cond av lists when writing out an older
> binary policy version.  The attr->type map has to be created by both the
> expand_module code (where it is trivial to do so before we discard
> attribute information) and by the policydb_read code, so that the
> compatibility code works regardless of whether we are compiling an older
> binary policy version (e.g. checkpolicy -c 19) or simply mutating an
> in-memory policydb originally created from a kernel binary policy file
> for local settings (e.g. /sbin/init and load_policy's use of
> sepol_genusers/genbools).  This lets me boot an unpatched kernel with a
> policy.19 and the new libsepol installed, without /sbin/init choking on
> sepol_genusers/genbools.

I've made this patch available at
http://www.cs.utah.edu/~sds/libsepol-avtab3.patch as well.  

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Mon, 2005-08-01 at 09:41 -0400, Stephen Smalley wrote:
> - We need to improve assertion checking time (neverallow rules), as it
> is significantly slowed by the lack of an expanded avtab.

This patch modifies the assertion checking code to expand the avtabs
prior to checking the assertions, leveraging the expand_avtab function
that was added by the prior patch to provide compatibility support for
writing older binary policy versions.  This appears to eliminate the
performance penalty introduced by the earlier patches for assertion
checking.

--- libsepol.a/src/assertion.c	2005-07-28 14:48:44.000000000 -0400
+++ libsepol/src/assertion.c	2005-08-04 07:47:31.000000000 -0400
@@ -82,49 +82,31 @@ static char *av_to_string(policydb_t *po
 
 /* These should probably return the error to the caller but it may get very long
    when there are lots of assertion violations, may try to fix this later */
-static int check_assertion_helper(policydb_t *p, unsigned int stype, unsigned int ttype,
-        class_perm_node_t *perm, unsigned long line)
+static int check_assertion_helper(policydb_t *p, 
+				  avtab_t *te_avtab, avtab_t *te_cond_avtab,
+				  unsigned int stype, unsigned int ttype,
+				  class_perm_node_t *perm, unsigned long line)
 {
         avtab_key_t avkey;
-        class_perm_node_t *curperm;
 	avtab_ptr_t node;
-	ebitmap_t *sattr, *tattr;
-	ebitmap_node_t *snode, *tnode;
-	unsigned int i, j;
+        class_perm_node_t *curperm;
 
 	for (curperm = perm; curperm != NULL; curperm = curperm->next) { 
+		avkey.source_type = stype + 1;
+		avkey.target_type = ttype + 1;
                 avkey.target_class = curperm->class;
 		avkey.specified = AVTAB_ALLOWED;
-		sattr = &p->type_attr_map[stype];
-		tattr = &p->type_attr_map[ttype];
-		for (i = ebitmap_startbit(sattr), 
-			     snode = ebitmap_startnode(sattr);
-		     i < ebitmap_length(sattr); 
-		     i = ebitmap_nextbit(sattr, &snode, i)) {
-			if (!ebitmap_node_get_bit(sattr, snode, i))
-				continue;
-			for (j = ebitmap_startbit(tattr), 
-				     tnode = ebitmap_startnode(tattr); 
-			     j < ebitmap_length(tattr); 
-			     j = ebitmap_nextbit(tattr, &tnode, j)) {
-				if (!ebitmap_node_get_bit(tattr, tnode, j))
-					continue;
-				avkey.source_type = i + 1;
-				avkey.target_type = j + 1;
-				for (node = avtab_search_node(&p->te_avtab, &avkey);
-				     node != NULL;
-				     node = avtab_search_node_next(node, avkey.specified)) {
-					if (node->datum.data & curperm->data)
-						goto err;
-				}
-
-				for (node = avtab_search_node(&p->te_cond_avtab, &avkey);
-				     node != NULL;
-				     node = avtab_search_node_next(node, avkey.specified)) {
-					if (node->datum.data & curperm->data)
-						goto err;
-				}
-			}
+		for (node = avtab_search_node(te_avtab, &avkey);
+		     node != NULL;
+		     node = avtab_search_node_next(node, avkey.specified)) {
+			if (node->datum.data & curperm->data)
+				goto err;
+		}
+		for (node = avtab_search_node(te_cond_avtab, &avkey);
+		     node != NULL;
+		     node = avtab_search_node_next(node, avkey.specified)) {
+			if (node->datum.data & curperm->data)
+				goto err;
 		}
 	}
 
@@ -141,9 +123,25 @@ err:
 int check_assertions(policydb_t *p, avrule_t *avrules)
 {
         avrule_t *a;
+	avtab_t te_avtab, te_cond_avtab;
         unsigned int i, j;
 	int errors = 0;
 
+	if (avrules) {
+		if (avtab_init(&te_avtab))
+			goto oom;
+		if (avtab_init(&te_cond_avtab)) {
+			avtab_destroy(&te_avtab);
+			goto oom;
+		}
+		if (expand_avtab(p, &p->te_avtab, &te_avtab) ||
+		    expand_avtab(p, &p->te_cond_avtab, &te_cond_avtab)) {
+			avtab_destroy(&te_avtab);
+			avtab_destroy(&te_cond_avtab);
+			goto oom;
+		}
+	}
+
 	for (a = avrules; a != NULL; a = a->next) {
                 if (!(a->specified & AVRULE_NEVERALLOW))
        			continue; 
@@ -155,13 +153,13 @@ int check_assertions(policydb_t *p, avru
                         if (!ebitmap_get_bit(&a->stypes.types, i))
                                 continue;
                         if (a->flags & RULE_SELF) {
-                                if (check_assertion_helper(p, i, i, a->perms, a->line))
+				if (check_assertion_helper(p, &te_avtab, &te_cond_avtab, i, i, a->perms, a->line))
                                         errors++;
                         }
                         for (j = ebitmap_startbit(&a->ttypes.types); j < ebitmap_length(&a->ttypes.types); j++) {
                                 if (!ebitmap_get_bit(&a->ttypes.types, j))
                                         continue;
-                                if (check_assertion_helper(p, i, j, a->perms, a->line))
+                                if (check_assertion_helper(p, &te_avtab, &te_cond_avtab, i, j, a->perms, a->line))
                                     errors++;
                         }
                 }
@@ -173,4 +171,8 @@ int check_assertions(policydb_t *p, avru
 	}
 
         return 0;
+
+oom:
+    fprintf(stderr, "Out of memory - unable to check assertions\n");	
+    return -1;
 }

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Thu, 2005-08-04 at 08:52 -0400, Stephen Smalley wrote:
> This patch modifies the assertion checking code to expand the avtabs
> prior to checking the assertions, leveraging the expand_avtab function
> that was added by the prior patch to provide compatibility support for
> writing older binary policy versions.  This appears to eliminate the
> performance penalty introduced by the earlier patches for assertion
> checking.

The above patch is also available from
http://www.cs.utah.edu/~sds/libsepol-assert.patch

I've also now converted over most users of ebitmaps in libsepol and
checkpolicy to using the new inline operators, and added a
ebitmap_for_each_bit macro to simplify the code.  Those patches are
available from http://www.cs.utah.edu/~sds/libsepol-ebitmap.patch and
http://www.cs.utah.edu/~sds/checkpolicy-ebitmap.patch.

Next step is to similarly convert the users of ebitmaps in the kernel.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Thu, 2005-08-04 at 12:14 -0400, Stephen Smalley wrote:
> On Thu, 2005-08-04 at 08:52 -0400, Stephen Smalley wrote:
> > This patch modifies the assertion checking code to expand the avtabs
> > prior to checking the assertions, leveraging the expand_avtab function
> > that was added by the prior patch to provide compatibility support for
> > writing older binary policy versions.  This appears to eliminate the
> > performance penalty introduced by the earlier patches for assertion
> > checking.
> 
> The above patch is also available from
> http://www.cs.utah.edu/~sds/libsepol-assert.patch
> 
> I've also now converted over most users of ebitmaps in libsepol and
> checkpolicy to using the new inline operators, and added a
> ebitmap_for_each_bit macro to simplify the code.  Those patches are
> available from http://www.cs.utah.edu/~sds/libsepol-ebitmap.patch and
> http://www.cs.utah.edu/~sds/checkpolicy-ebitmap.patch.
> 
> Next step is to similarly convert the users of ebitmaps in the kernel.

The kernel patch for converting ebitmap users to the new inline
operators is below, and also available from http://www.cs.utah.edu/~sds.
This patch is relative to the two avtab memory optimization patches
(reduce node size, reduce number of nodes) previously posted and also
available from that URL.  I chose to kill the unused arguments from the
ebitmap operators for the kernel patch, and went back and removed them
from libsepol/checkpolicy as well.  Patches for that are also available
from the above URL, along with fully patched tarballs of
libsepol/checkpolicy for convenience, as the number of individual
patches is becoming unwieldy for them.  

diff -X /home/sds/dontdiff -rup linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/ebitmap.h linux-2.6.13-rc3-mm1-avtab3/security/selinux/ss/ebitmap.h
--- linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/ebitmap.h	2005-06-17 15:48:29.000000000 -0400
+++ linux-2.6.13-rc3-mm1-avtab3/security/selinux/ss/ebitmap.h	2005-08-04 12:27:07.000000000 -0400
@@ -32,11 +32,41 @@ struct ebitmap {
 #define ebitmap_length(e) ((e)->highbit)
 #define ebitmap_startbit(e) ((e)->node ? (e)->node->startbit : 0)
 
+static inline unsigned int ebitmap_start(struct ebitmap *e, 
+					 struct ebitmap_node **n) 
+{
+	*n = e->node;
+	return ebitmap_startbit(e);
+}
+
 static inline void ebitmap_init(struct ebitmap *e)
 {
 	memset(e, 0, sizeof(*e));
 }
 
+static inline unsigned int ebitmap_next(struct ebitmap_node **n,
+					unsigned int bit)
+{
+	if ((bit == ((*n)->startbit + MAPSIZE - 1)) &&
+	    (*n)->next) {
+		*n = (*n)->next;
+		return (*n)->startbit;
+	}
+
+	return (bit+1);
+}
+
+static inline int ebitmap_node_get_bit(struct ebitmap_node * n, 
+				       unsigned int bit)
+{
+	if (n->map & (MAPBIT << (bit - n->startbit)))
+		return 1;
+	return 0;
+}
+
+#define ebitmap_for_each_bit(e, n, bit) \
+	for (bit = ebitmap_start(e, &n); bit < ebitmap_length(e); bit = ebitmap_next(&n, bit)) \
+
 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);
 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2);
diff -X /home/sds/dontdiff -rup linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/mls.c linux-2.6.13-rc3-mm1-avtab3/security/selinux/ss/mls.c
--- linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/mls.c	2005-06-17 15:48:29.000000000 -0400
+++ linux-2.6.13-rc3-mm1-avtab3/security/selinux/ss/mls.c	2005-08-04 12:27:50.000000000 -0400
@@ -26,6 +26,7 @@
 int mls_compute_context_len(struct context * context)
 {
 	int i, l, len, range;
+	struct ebitmap_node *node;
 
 	if (!selinux_mls_enabled)
 		return 0;
@@ -35,24 +36,24 @@ int mls_compute_context_len(struct conte
 		range = 0;
 		len += strlen(policydb.p_sens_val_to_name[context->range.level[l].sens - 1]);
 
-		for (i = 1; i <= ebitmap_length(&context->range.level[l].cat); i++) {
-			if (ebitmap_get_bit(&context->range.level[l].cat, i - 1)) {
+		ebitmap_for_each_bit(&context->range.level[l].cat, node, i) {
+			if (ebitmap_node_get_bit(node, i)) {
 				if (range) {
 					range++;
 					continue;
 				}
 
-				len += strlen(policydb.p_cat_val_to_name[i - 1]) + 1;
+				len += strlen(policydb.p_cat_val_to_name[i]) + 1;
 				range++;
 			} else {
 				if (range > 1)
-					len += strlen(policydb.p_cat_val_to_name[i - 2]) + 1;
+					len += strlen(policydb.p_cat_val_to_name[i - 1]) + 1;
 				range = 0;
 			}
 		}
 		/* Handle case where last category is the end of range */
 		if (range > 1)
-			len += strlen(policydb.p_cat_val_to_name[i - 2]) + 1;
+			len += strlen(policydb.p_cat_val_to_name[i - 1]) + 1;
 
 		if (l == 0) {
 			if (mls_level_eq(&context->range.level[0],
@@ -76,6 +77,7 @@ void mls_sid_to_context(struct context *
 {
 	char *scontextp;
 	int i, l, range, wrote_sep;
+	struct ebitmap_node *node;
 
 	if (!selinux_mls_enabled)
 		return;
@@ -93,8 +95,8 @@ void mls_sid_to_context(struct context *
 		scontextp += strlen(policydb.p_sens_val_to_name[context->range.level[l].sens - 1]);
 
 		/* categories */
-		for (i = 1; i <= ebitmap_length(&context->range.level[l].cat); i++) {
-			if (ebitmap_get_bit(&context->range.level[l].cat, i - 1)) {
+		ebitmap_for_each_bit(&context->range.level[l].cat, node, i) {
+			if (ebitmap_node_get_bit(node, i)) {
 				if (range) {
 					range++;
 					continue;
@@ -105,8 +107,8 @@ void mls_sid_to_context(struct context *
 					wrote_sep = 1;
 				} else
 					*scontextp++ = ',';
-				strcpy(scontextp, policydb.p_cat_val_to_name[i - 1]);
-				scontextp += strlen(policydb.p_cat_val_to_name[i - 1]);
+				strcpy(scontextp, policydb.p_cat_val_to_name[i]);
+				scontextp += strlen(policydb.p_cat_val_to_name[i]);
 				range++;
 			} else {
 				if (range > 1) {
@@ -115,8 +117,8 @@ void mls_sid_to_context(struct context *
 					else
 						*scontextp++ = ',';
 
-					strcpy(scontextp, policydb.p_cat_val_to_name[i - 2]);
-					scontextp += strlen(policydb.p_cat_val_to_name[i - 2]);
+					strcpy(scontextp, policydb.p_cat_val_to_name[i - 1]);
+					scontextp += strlen(policydb.p_cat_val_to_name[i - 1]);
 				}
 				range = 0;
 			}
@@ -129,8 +131,8 @@ void mls_sid_to_context(struct context *
 			else
 				*scontextp++ = ',';
 
-			strcpy(scontextp, policydb.p_cat_val_to_name[i - 2]);
-			scontextp += strlen(policydb.p_cat_val_to_name[i - 2]);
+			strcpy(scontextp, policydb.p_cat_val_to_name[i - 1]);
+			scontextp += strlen(policydb.p_cat_val_to_name[i - 1]);
 		}
 
 		if (l == 0) {
@@ -156,6 +158,7 @@ int mls_context_isvalid(struct policydb 
 {
 	struct level_datum *levdatum;
 	struct user_datum *usrdatum;
+	struct ebitmap_node *node;
 	int i, l;
 
 	if (!selinux_mls_enabled)
@@ -178,11 +181,11 @@ int mls_context_isvalid(struct policydb 
 		if (!levdatum)
 			return 0;
 
-		for (i = 1; i <= ebitmap_length(&c->range.level[l].cat); i++) {
-			if (ebitmap_get_bit(&c->range.level[l].cat, i - 1)) {
+		ebitmap_for_each_bit(&c->range.level[l].cat, node, i) {
+			if (ebitmap_node_get_bit(node, i)) {
 				if (i > p->p_cats.nprim)
 					return 0;
-				if (!ebitmap_get_bit(&levdatum->level->cat, i - 1))
+				if (!ebitmap_get_bit(&levdatum->level->cat, i))
 					/*
 					 * Category may not be associated with
 					 * sensitivity in low level.
@@ -443,6 +446,7 @@ int mls_convert_context(struct policydb 
 	struct level_datum *levdatum;
 	struct cat_datum *catdatum;
 	struct ebitmap bitmap;
+	struct ebitmap_node *node;
 	int l, i;
 
 	if (!selinux_mls_enabled)
@@ -457,12 +461,12 @@ int mls_convert_context(struct policydb 
 		c->range.level[l].sens = levdatum->level->sens;
 
 		ebitmap_init(&bitmap);
-		for (i = 1; i <= ebitmap_length(&c->range.level[l].cat); i++) {
-			if (ebitmap_get_bit(&c->range.level[l].cat, i - 1)) {
+		ebitmap_for_each_bit(&c->range.level[l].cat, node, i) {
+			if (ebitmap_node_get_bit(node, i)) {
 				int rc;
 
 				catdatum = hashtab_search(newp->p_cats.table,
-				         	oldp->p_cat_val_to_name[i - 1]);
+				         	oldp->p_cat_val_to_name[i]);
 				if (!catdatum)
 					return -EINVAL;
 				rc = ebitmap_set_bit(&bitmap, catdatum->value - 1, 1);
diff -X /home/sds/dontdiff -rup linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/services.c linux-2.6.13-rc3-mm1-avtab3/security/selinux/ss/services.c
--- linux-2.6.13-rc3-mm1-avtab2/security/selinux/ss/services.c	2005-07-29 09:21:01.000000000 -0400
+++ linux-2.6.13-rc3-mm1-avtab3/security/selinux/ss/services.c	2005-08-04 12:19:02.000000000 -0400
@@ -269,6 +269,7 @@ static int context_struct_compute_av(str
 	struct avtab_node *node;
 	struct class_datum *tclass_datum;
 	struct ebitmap *sattr, *tattr;
+	struct ebitmap_node *snode, *tnode;
 	unsigned int i, j;
 
 	/*
@@ -306,13 +307,11 @@ static int context_struct_compute_av(str
 	avkey.specified = AVTAB_AV;
 	sattr = &policydb.type_attr_map[scontext->type - 1];
 	tattr = &policydb.type_attr_map[tcontext->type - 1];
-	for (i = ebitmap_startbit(sattr); 
-	     i < ebitmap_length(sattr); i++) {
-		if (!ebitmap_get_bit(sattr, i))
-		    continue;
-		for (j = ebitmap_startbit(tattr); 
-		     j < ebitmap_length(tattr); j++) {
-			if (!ebitmap_get_bit(tattr, j))
+	ebitmap_for_each_bit(sattr, snode, i) {
+		if (!ebitmap_node_get_bit(snode, i))
+			continue;
+		ebitmap_for_each_bit(tattr, tnode, j) {
+			if (!ebitmap_node_get_bit(tnode, j))
 				continue;
 			avkey.source_type = i + 1;
 			avkey.target_type = j + 1;
@@ -1479,6 +1478,7 @@ int security_get_user_sids(u32 fromsid,
 	struct user_datum *user;
 	struct role_datum *role;
 	struct av_decision avd;
+	struct ebitmap_node *rnode, *tnode;
 	int rc = 0, i, j;
 
 	if (!ss_initialized) {
@@ -1509,13 +1509,13 @@ int security_get_user_sids(u32 fromsid,
 	}
 	memset(mysids, 0, maxnel*sizeof(*mysids));
 
-	for (i = ebitmap_startbit(&user->roles); i < ebitmap_length(&user->roles); i++) {
-		if (!ebitmap_get_bit(&user->roles, i))
+	ebitmap_for_each_bit(&user->roles, rnode, i) {
+		if (!ebitmap_node_get_bit(rnode, i))
 			continue;
 		role = policydb.role_val_to_struct[i];
 		usercon.role = i+1;
-		for (j = ebitmap_startbit(&role->types); j < ebitmap_length(&role->types); j++) {
-			if (!ebitmap_get_bit(&role->types, j))
+		ebitmap_for_each_bit(&role->types, tnode, j) {
+			if (!ebitmap_node_get_bit(tnode, j))
 				continue;
 			usercon.type = j+1;
 


-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Russell Coker]

On Saturday 30 July 2005 02:49, Stephen Smalley <sds@tycho.nsa.gov> wrote:
> - Assertion checking is significantly slower.  I added some new inline
> ebitmap operations to help speed it up, but it is still a lot slower
> than previously.

Currently the speed penalty of assertions is a great disincentive for adding 
new assertions.  One of my slower machines has a checkpolicy time of 6.9s 
without assertions and 18.9s with them (and the policy that is being compiled 
is considerably simpler and smaller than the default policy).

I had considered adding some assertions to the daemon_domain macro and 
friends.  This might increase the computational work involved in checking 
assertions by a factor of 10 or more.

Maybe we should have a checkpolicy option to not check assertions?  Then when 
doing policy development work of the form "add access to a directory, compile 
and load policy, add access to a file in the directory, compile and load 
policy, etc" we could turn off assertions and then just check assertions 
before distributing policy.

Steve, I expect that you will take an extreme dislike to this idea and I admit 
that it has some significant possibilities for getting things wrong.  However 
given the number of people who currently comment out lines in assert.te 
because they don't know what they are doing I don't think it will make things 
any worse than they are now.

-- 
http://www.coker.com.au/selinux/   My NSA Security Enhanced Linux packages
http://www.coker.com.au/bonnie++/  Bonnie++ hard drive benchmark
http://www.coker.com.au/postal/    Postal SMTP/POP benchmark
http://www.coker.com.au/~russell/  My home page


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC][PATCH 0/3] Reduce number of avtab nodes

[Stephen Smalley]

On Thu, 2005-08-04 at 17:42 +1000, Russell Coker wrote:
> Currently the speed penalty of assertions is a great disincentive for adding 
> new assertions.  One of my slower machines has a checkpolicy time of 6.9s 
> without assertions and 18.9s with them (and the policy that is being compiled 
> is considerably simpler and smaller than the default policy).
> 
> I had considered adding some assertions to the daemon_domain macro and 
> friends.  This might increase the computational work involved in checking 
> assertions by a factor of 10 or more.
> 
> Maybe we should have a checkpolicy option to not check assertions?  Then when 
> doing policy development work of the form "add access to a directory, compile 
> and load policy, add access to a file in the directory, compile and load 
> policy, etc" we could turn off assertions and then just check assertions 
> before distributing policy.
> 
> Steve, I expect that you will take an extreme dislike to this idea and I admit 
> that it has some significant possibilities for getting things wrong.  However 
> given the number of people who currently comment out lines in assert.te 
> because they don't know what they are doing I don't think it will make things 
> any worse than they are now.

I'm not sure what this would ultimately mean in the future, where policy
changes will have to go through the policy daemon being developed by
Tresys and it will be applying assertion checks to the linked and
expanded policy prior to loading it.  Naturally, you don't want the
client to be able to tell the daemon to skip assertion checks ;)

As far as the current situation goes, I'm not fundamentally opposed to a
simple option to checkpolicy to disable assertion checking, as long as
the default behavior (in the absence of an explicit option) remains to
check them.  Although on the other hand that might reduce incentives for
people to optimize the assertion checking logic.

For the purposes of this thread/patchset, I just wanted to ensure that
the new logic didn't make assertion checking significantly slower, and
that seems to have been addressed by my latest patch.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.