[PATCH userspace 0/4] Remove redundant rules when building policydb

[PATCH userspace 0/4] Remove redundant rules when building policydb

[Ondrej Mosnacek]

This series implements an optional optimization step when building
a policydb via semodule or secilc, which identifies and removes rules
that are redundant -- i.e. they are already covered by a more general
rule based on attribute inheritance.

Since the performance penalty of this additional step is very small
(it adds about 1 s to the current running time of ~20-30 s [1]) and
it can have a big positive effect on the number of rules in policy
(it manages to remove ~40% AV rules from Fedora 29 policy), the
optimization is enabled by default and can be turned off using a
command-line option (--no-optimize) in secilc and semodule [2].

The optimization routine eliminates:
 * all allow/neverallow/dontaudit/auditallow rules (including xperm
   variants) that are covered by another more general rule,
 * all conditional versions of the above rules that are covered by a
   more general rule either in the unconditional table or in the same
   branch of the same conditional.

The optimization doesn't process other rules, since they currently
do not support attributes. There is some room left for more precise
optimization of conditional rules, but it would likely bring only
little additional benefit.

When the policy is mostly or fully expanded, the optimization should
be turned off. If it isn't, the policy build time will increase a lot
for no benefit. However, the complexity of optimization will be only
linear w.r.t. the number of rules and so the impact should not be
catastrophic. (When testing with secilc on a subset of Fedora policy
with -X 100000 the build time was 1.7 s with optimization vs. 1 s
without it.)

Tested live on my Fedora 29 devel machine under normal use. No unusual
AVCs were observed with optimized policy loaded.

Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427

NOTE: The xperm rule support wasn't tested -- I would welcome some
      peer review/testing of this part.

[1] As measured on my machine (Fedora 29 policy, x86_64).
[2] I have no problem with switching it to opt-in if that is preferred.

Ondrej Mosnacek (4):
  libsepol: add a function to optimize kernel policy
  secilc: optimize policy before writing
  libsemanage: optimize policy on rebuild
  semodule: add flag to disable policy optimization

 libsemanage/include/semanage/handle.h      |   4 +
 libsemanage/src/direct_api.c               |   7 +
 libsemanage/src/handle.c                   |  13 +
 libsemanage/src/handle.h                   |   1 +
 libsemanage/src/libsemanage.map            |   5 +
 libsepol/include/sepol/policydb.h          |   5 +
 libsepol/include/sepol/policydb/policydb.h |   2 +
 libsepol/src/libsepol.map.in               |   5 +
 libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
 libsepol/src/policydb_public.c             |   5 +
 policycoreutils/semodule/semodule.c        |  12 +-
 secilc/secilc.c                            |  16 +-
 12 files changed, 442 insertions(+), 3 deletions(-)
 create mode 100644 libsepol/src/optimize.c

-- 
2.20.1

[PATCH userspace 1/4] libsepol: add a function to optimize kernel policy

[Ondrej Mosnacek]

Add sepol_policydb_optimize(), which checks a kernel policy for
redundant rules (i.e. those that are covered by an existing more general
rule) and removes them.

Results on Fedora 29 policy:

WITHOUT OPTIMIZATION:
    # time semodule -B --no-optimize
    real    0m20,190s
    user    0m18,003s
    sys     0m2,075s

    $ wc -c /sys/fs/selinux/policy
    8689631 /sys/fs/selinux/policy

    $ seinfo (edited)
      Allow:            113152
      Dontaudit:         10294
      Total:            123146

WITH OPTIMIZATION ENABLED:
    # time semodule -B
    real    0m21,406s
    user    0m19,061s
    sys     0m2,227s

    $ wc -c /sys/fs/selinux/policy
    8089575 /sys/fs/selinux/policy

    $ seinfo (edited)
      Allow:             66328
      Dontaudit:          7138
      Total:             73466

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 libsepol/include/sepol/policydb.h          |   5 +
 libsepol/include/sepol/policydb/policydb.h |   2 +
 libsepol/src/libsepol.map.in               |   5 +
 libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
 libsepol/src/policydb_public.c             |   5 +
 5 files changed, 387 insertions(+)
 create mode 100644 libsepol/src/optimize.c

diff --git a/libsepol/include/sepol/policydb.h b/libsepol/include/sepol/policydb.h
index 6769b913..792913dd 100644
--- a/libsepol/include/sepol/policydb.h
+++ b/libsepol/include/sepol/policydb.h
@@ -100,6 +100,11 @@ extern int sepol_policydb_set_handle_unknown(sepol_policydb_t * p,
 extern int sepol_policydb_set_target_platform(sepol_policydb_t * p,
 					     int target_platform);
 
+/*
+ * Optimize the policy by removing redundant rules.
+ */
+extern int sepol_policydb_optimize(sepol_policydb_t * p);
+
 /* 
  * Read a policydb from a policy file.
  * This automatically sets the type and version based on the 
diff --git a/libsepol/include/sepol/policydb/policydb.h b/libsepol/include/sepol/policydb/policydb.h
index 591ce6e0..a279382e 100644
--- a/libsepol/include/sepol/policydb/policydb.h
+++ b/libsepol/include/sepol/policydb/policydb.h
@@ -636,6 +636,8 @@ extern int policydb_user_cache(hashtab_key_t key,
 
 extern int policydb_reindex_users(policydb_t * p);
 
+extern int policydb_optimize(policydb_t * p);
+
 extern void policydb_destroy(policydb_t * p);
 
 extern int policydb_load_isids(policydb_t * p, sidtab_t * s);
diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
index d879016c..6358e51f 100644
--- a/libsepol/src/libsepol.map.in
+++ b/libsepol/src/libsepol.map.in
@@ -59,3 +59,8 @@ LIBSEPOL_1.1 {
 	sepol_polcap_getnum;
 	sepol_polcap_getname;
 } LIBSEPOL_1.0;
+
+LIBSEPOL_1.2 {
+  global:
+	sepol_optimize_policy;
+} LIBSEPOL_1.1;
diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
new file mode 100644
index 00000000..1fa1495c
--- /dev/null
+++ b/libsepol/src/optimize.c
@@ -0,0 +1,370 @@
+/*
+ * Author: Ondrej Mosnacek <omosnacek@gmail.com>
+ *
+ * Copyright (C) 2019 Red Hat Inc.
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2.1 of the License, or (at your option) any later version.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Lesser General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Lesser General Public
+ *  License along with this library; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+
+/*
+ * Binary policy optimization.
+ *
+ * Defines the policydb_optimize() function, which finds and removes
+ * redundant rules from the binary policy to reduce its size and potentially
+ * improve rule matching times. Only rules that are already covered by a
+ * more general rule are removed. The resulting policy is functionally
+ * equivalent to the original one.
+ */
+
+#include <sepol/policydb/policydb.h>
+#include <sepol/policydb/conditional.h>
+
+/* builds map: type/attribute -> {all attributes that are a superset of it} */
+static ebitmap_t *build_type_map(const policydb_t *p)
+{
+	unsigned int i, k;
+	ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
+	if (!map)
+		return NULL;
+
+	for (i = 0; i < p->p_types.nprim; i++) {
+		if (p->type_val_to_struct[i] &&
+		    p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
+			if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
+				goto err;
+		} else {
+			ebitmap_t *types_i = &p->attr_type_map[i];
+
+			ebitmap_init(&map[i]);
+			for (k = 0; k < p->p_types.nprim; k++) {
+				ebitmap_t *types_k = &p->attr_type_map[k];
+
+				if (ebitmap_contains(types_k, types_i)) {
+					if (ebitmap_set_bit(&map[i], k, 1))
+						goto err;
+				}
+			}
+		}
+	}
+	return map;
+err:
+	for (k = 0; k < i; k++)
+		ebitmap_destroy(&map[i]);
+	return NULL;
+}
+
+static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
+{
+	unsigned int i;
+	for (i = 0; i < p->p_types.nprim; i++)
+		ebitmap_destroy(&type_map[i]);
+	free(type_map);
+}
+
+static int match_xperms(const uint32_t *p1, const uint32_t *p2)
+{
+	size_t i;
+
+	for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
+		if ((p2[i] & p1[i]) != p1[i])
+			return 0;
+	}
+	return 1;
+}
+
+static int match_avtab_datum(uint16_t specified,
+			     const avtab_datum_t *d1, const avtab_datum_t *d2)
+{
+	if (specified & AVTAB_AV)
+		return (d2->data & d1->data) == d1->data;
+
+	if (specified & AVTAB_XPERMS) {
+		const avtab_extended_perms_t *x1 = d1->xperms;
+		const avtab_extended_perms_t *x2 = d2->xperms;
+
+		if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
+			if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
+				if (x1->driver != x2->driver)
+					return 0;
+				return match_xperms(x1->perms, x2->perms);
+			}
+			if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
+				return xperm_test(x1->driver, x2->perms);
+		} else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
+			if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
+				return 0;
+
+			if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
+				return match_xperms(x1->perms, x2->perms);
+		}
+		return 0;
+	}
+	return 0;
+}
+
+/* checks if avtab contains a rule that covers the given rule */
+static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
+			       const ebitmap_t *type_map)
+{
+	unsigned int i, k, s_idx, t_idx;
+	ebitmap_node_t *snode, *tnode;
+	avtab_datum_t *d1, *d2;
+	avtab_key_t key;
+
+	/* we only care about AV rules */
+	if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
+		return 0;
+
+	s_idx = entry->key.source_type - 1;
+	t_idx = entry->key.target_type - 1;
+
+	key.target_class = entry->key.target_class;
+	key.specified    = entry->key.specified;
+
+	d1 = &entry->datum;
+
+	ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
+		key.source_type = i + 1;
+
+		ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
+			if (s_idx == i && t_idx == k)
+				continue;
+
+			key.target_type = k + 1;
+
+			d2 = avtab_search(tab, &key);
+			if (!d2)
+				continue;
+
+			if (match_avtab_datum(key.specified, d1, d2))
+				return 1;
+		}
+	}
+	return 0;
+}
+
+static int is_type_attr(policydb_t *p, unsigned int id)
+{
+	return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
+}
+
+static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
+{
+	unsigned int s_idx = entry->key.source_type - 1;
+	unsigned int t_idx = entry->key.target_type - 1;
+
+	return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
+}
+
+/* checks if conditional list contains a rule that covers the given rule */
+static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
+				  const ebitmap_t *type_map)
+{
+	unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
+
+	/* we only care about AV rules */
+	if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
+		return 0;
+
+	s1 = e1->key.source_type - 1;
+	t1 = e1->key.target_type - 1;
+	c1 = e1->key.target_class;
+	k1 = e1->key.specified;
+
+	for (; list; list = list->next) {
+		avtab_ptr_t e2 = list->node;
+
+		s2 = e2->key.source_type - 1;
+		t2 = e2->key.target_type - 1;
+		c2 = e2->key.target_class;
+		k2 = e2->key.specified;
+
+		if (k1 != k2 || c1 != c2)
+			continue;
+
+		if (s1 == s2 && t1 == t2)
+			continue;
+		if (!ebitmap_get_bit(&type_map[s1], s2))
+			continue;
+		if (!ebitmap_get_bit(&type_map[t1], t2))
+			continue;
+
+		if (match_avtab_datum(k1, &e1->datum, &e2->datum))
+			return 1;
+	}
+	return 0;
+}
+
+static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
+{
+	avtab_t *tab = &p->te_avtab;
+	unsigned int i;
+	avtab_ptr_t *cur;
+
+	for (i = 0; i < tab->nslot; i++) {
+		cur = &tab->htable[i];
+		while (*cur) {
+			if (is_avrule_redundant(*cur, tab, type_map)) {
+				/* redundant rule -> remove it */
+				avtab_ptr_t tmp = *cur;
+
+				*cur = tmp->next;
+				if (tmp->key.specified & AVTAB_XPERMS)
+					free(tmp->datum.xperms);
+				free(tmp);
+
+				tab->nel--;
+			} else {
+				/* rule not redundant -> move to next rule */
+				cur = &(*cur)->next;
+			}
+		}
+	}
+}
+
+/* find redundant rules in (*cond) and put them into (*del) */
+static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
+				  policydb_t *p, const ebitmap_t *type_map)
+{
+	cond_av_list_t **listp = cond;
+	cond_av_list_t *pcov = NULL;
+	cond_av_list_t **pcov_cur = &pcov;
+
+	/*
+	 * Separate out all "potentially covering" rules (src or tgt is an attr)
+	 * and move them to the end of the list. This is needed to avoid
+	 * polynomial complexity when almost all rules are expanded.
+	 */
+	while (*cond) {
+		if (is_avrule_with_attr((*cond)->node, p)) {
+			cond_av_list_t *tmp = *cond;
+
+			*cond = tmp->next;
+			tmp->next = pcov;
+			pcov = tmp;
+		} else {
+			cond = &(*cond)->next;
+		}
+	}
+	/* link the "potentially covering" rules to the end of the list */
+	*cond = pcov;
+
+	/* now go through the list and find the redundant rules */
+	cond = listp;
+	pcov_cur = &pcov;
+	while (*cond) {
+		/* needed because pcov itself may get deleted */
+		if (*cond == pcov)
+			pcov_cur = cond;
+		/*
+		 * First check if covered by an unconditional rule, then also
+		 * check if covered by another rule in the same list.
+		 */
+		if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map) ||
+		    is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
+			cond_av_list_t *tmp = *cond;
+
+			*cond = tmp->next;
+			tmp->next = *del;
+			*del = tmp;
+		} else {
+			cond = &(*cond)->next;
+		}
+	}
+}
+
+static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
+{
+	avtab_t *tab = &p->te_cond_avtab;
+	unsigned int i;
+	avtab_ptr_t *cur;
+	cond_node_t **cond;
+	cond_av_list_t **avcond, *del = NULL;
+
+	/* First go through all conditionals and collect redundant rules. */
+	cond = &p->cond_list;
+	while (*cond) {
+		optimize_cond_av_list(&(*cond)->true_list,  &del, p, type_map);
+		optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
+		/* TODO: maybe also check for rules present in both lists */
+
+		/* nothing left in both lists -> remove the whole conditional */
+		if (!(*cond)->true_list && !(*cond)->false_list) {
+			cond_node_t *cond_tmp = *cond;
+
+			*cond = cond_tmp->next;
+			cond_node_destroy(cond_tmp);
+		} else {
+			cond = &(*cond)->next;
+		}
+	}
+
+	if (!del)
+		return;
+
+	/*
+	 * Now go through the whole cond_avtab and remove all rules that are
+	 * found in the 'del' list.
+	 */
+	for (i = 0; i < tab->nslot; i++) {
+		cur = &tab->htable[i];
+		while (*cur) {
+			int redundant = 0;
+			avcond = &del;
+			while (*avcond) {
+				if ((*avcond)->node == *cur) {
+					cond_av_list_t *cond_tmp = *avcond;
+
+					*avcond = cond_tmp->next;
+					free(cond_tmp);
+					redundant = 1;
+					break;
+				} else {
+					avcond = &(*avcond)->next;
+				}
+			}
+			if (redundant) {
+				avtab_ptr_t tmp = *cur;
+
+				*cur = tmp->next;
+				if (tmp->key.specified & AVTAB_XPERMS)
+					free(tmp->datum.xperms);
+				free(tmp);
+
+				tab->nel--;
+			} else {
+				cur = &(*cur)->next;
+			}
+		}
+	}
+}
+
+int policydb_optimize(policydb_t *p)
+{
+	ebitmap_t *type_map;
+
+	if (p->policy_type != POLICY_KERN)
+		return -1;
+
+	type_map = build_type_map(p);
+	if (!type_map)
+		return -1;
+
+	optimize_avtab(p, type_map);
+	optimize_cond_avtab(p, type_map);
+
+	destroy_type_map(p, type_map);
+	return 0;
+}
diff --git a/libsepol/src/policydb_public.c b/libsepol/src/policydb_public.c
index e7218423..747a43ff 100644
--- a/libsepol/src/policydb_public.c
+++ b/libsepol/src/policydb_public.c
@@ -169,6 +169,11 @@ int sepol_policydb_set_target_platform(sepol_policydb_t * sp,
 	return 0;
 }
 
+int sepol_policydb_optimize(sepol_policydb_t * p)
+{
+	return policydb_optimize(&p->p);
+}
+
 int sepol_policydb_read(sepol_policydb_t * p, sepol_policy_file_t * pf)
 {
 	return policydb_read(&p->p, &pf->pf, 0);
-- 
2.20.1

[PATCH userspace 2/4] secilc: optimize policy before writing

[Ondrej Mosnacek]

Call sepol_policydb_optimize() on the final policydb before writing it
out. Also add a command-line flag to optionally skip this step.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 secilc/secilc.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/secilc/secilc.c b/secilc/secilc.c
index ad6862ba..26996ef9 100644
--- a/secilc/secilc.c
+++ b/secilc/secilc.c
@@ -68,6 +68,7 @@ static __attribute__((__noreturn__)) void usage(const char *prog)
 	printf("  -G, --expand-generated         Expand and remove auto-generated attributes\n");
 	printf("  -X, --expand-size <SIZE>       Expand type attributes with fewer than <SIZE>\n");
 	printf("                                 members.\n");
+	printf("  -n, --no-optimize              do not optimize final policy\n");
 	printf("  -v, --verbose                  increment verbosity level\n");
 	printf("  -h, --help                     display usage information\n");
 	exit(1);
@@ -97,6 +98,7 @@ int main(int argc, char *argv[])
 	int policyvers = POLICYDB_VERSION_MAX;
 	int attrs_expand_generated = 0;
 	int attrs_expand_size = -1;
+	int optimize_policy = 1;
 	int opt_char;
 	int opt_index = 0;
 	char *fc_buf = NULL;
@@ -117,12 +119,13 @@ int main(int argc, char *argv[])
 		{"filecontexts", required_argument, 0, 'f'},
 		{"expand-generated", no_argument, 0, 'G'},
 		{"expand-size", required_argument, 0, 'X'},
+		{"no-optimize", no_argument, 0, 'n'},
 		{0, 0, 0, 0}
 	};
 	int i;
 
 	while (1) {
-		opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:", long_opts, &opt_index);
+		opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:n", long_opts, &opt_index);
 		if (opt_char == -1) {
 			break;
 		}
@@ -211,6 +214,9 @@ int main(int argc, char *argv[])
 				}
 				break;
 			}
+			case 'n':
+				optimize_policy = 0;
+				break;
 			case 'h':
 				usage(argv[0]);
 			case '?':
@@ -294,6 +300,14 @@ int main(int argc, char *argv[])
 		goto exit;
 	}
 
+	if (optimize_policy) {
+		rc = sepol_policydb_optimize(pdb);
+		if (rc != SEPOL_OK) {
+			fprintf(stderr, "Failed to optimize policydb\n");
+			goto exit;
+		}
+	}
+
 	if (output == NULL) {
 		int size = snprintf(NULL, 0, "policy.%d", policyvers);
 		output = malloc((size + 1) * sizeof(char));
-- 
2.20.1

[PATCH userspace 3/4] libsemanage: optimize policy on rebuild

[Ondrej Mosnacek]

When building binary policy, run it through sepol_policydb_optimize()
just before writing the final policy to disk.

Also add a semanage_set_optimize() function to allow skipping the
optimization step.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 libsemanage/include/semanage/handle.h |  4 ++++
 libsemanage/src/direct_api.c          |  7 +++++++
 libsemanage/src/handle.c              | 13 +++++++++++++
 libsemanage/src/handle.h              |  1 +
 libsemanage/src/libsemanage.map       |  5 +++++
 5 files changed, 30 insertions(+)

diff --git a/libsemanage/include/semanage/handle.h b/libsemanage/include/semanage/handle.h
index c8165900..418c2c72 100644
--- a/libsemanage/include/semanage/handle.h
+++ b/libsemanage/include/semanage/handle.h
@@ -66,6 +66,10 @@ void semanage_set_reload(semanage_handle_t * handle, int do_reload);
  * 1 for yes, 0 for no (default) */
 void semanage_set_rebuild(semanage_handle_t * handle, int do_rebuild);
 
+/* set whether to optimize the policy (remove redundancies) when built.
+ * 1 for yes (default), 0 for no */
+void semanage_set_optimize(semanage_handle_t * handle, int do_optimize);
+
 /* Fills *compiler_path with the location of the hll compiler sh->conf->compiler_directory_path
  * corresponding to lang_ext.
  * Upon success returns 0, -1 on error. */
diff --git a/libsemanage/src/direct_api.c b/libsemanage/src/direct_api.c
index c58961be..95cbee81 100644
--- a/libsemanage/src/direct_api.c
+++ b/libsemanage/src/direct_api.c
@@ -1461,6 +1461,13 @@ rebuild:
 
 		cil_db_destroy(&cildb);
 
+		/* Remove redundancies in binary policy if requested. */
+		if (sh->do_optimize) {
+			retval = sepol_policydb_optimize(out);
+			if (retval < 0)
+				goto cleanup;
+		}
+
 		/* Write the linked policy before merging local changes. */
 		retval = semanage_write_policydb(sh, out,
 						 SEMANAGE_LINKED);
diff --git a/libsemanage/src/handle.c b/libsemanage/src/handle.c
index e5109aef..0160ba18 100644
--- a/libsemanage/src/handle.c
+++ b/libsemanage/src/handle.c
@@ -88,6 +88,10 @@ semanage_handle_t *semanage_handle_create(void)
 	 * If any changes are made, this flag is ignored */
 	sh->do_rebuild = 0;
 
+	/* Optimize policy by default. If the policy is not
+	 * being rebuilt, this flag is ignored. */
+	sh->do_optimize = 1;
+
 	sh->commit_err = 0;
 
 	/* By default always reload policy after commit if SELinux is enabled. */
@@ -125,6 +129,15 @@ void semanage_set_rebuild(semanage_handle_t * sh, int do_rebuild)
 	return;
 }
 
+void semanage_set_optimize(semanage_handle_t * sh, int do_optimize)
+{
+
+	assert(sh != NULL);
+
+	sh->do_optimize = do_optimize;
+	return;
+}
+
 void semanage_set_reload(semanage_handle_t * sh, int do_reload)
 {
 
diff --git a/libsemanage/src/handle.h b/libsemanage/src/handle.h
index a91907b0..b8fbf120 100644
--- a/libsemanage/src/handle.h
+++ b/libsemanage/src/handle.h
@@ -62,6 +62,7 @@ struct semanage_handle {
 	int is_in_transaction;
 	int do_reload;		/* whether to reload policy after commit */
 	int do_rebuild;		/* whether to rebuild policy if there were no changes */
+	int do_optimize;	/* whether to optimize the built policy */
 	int commit_err;		/* set by semanage_direct_commit() if there are
 				 * any errors when building or committing the
 				 * sandbox to kernel policy at /etc/selinux
diff --git a/libsemanage/src/libsemanage.map b/libsemanage/src/libsemanage.map
index 02036696..535bd9b5 100644
--- a/libsemanage/src/libsemanage.map
+++ b/libsemanage/src/libsemanage.map
@@ -63,3 +63,8 @@ LIBSEMANAGE_1.1 {
 	  semanage_module_remove_key;
 	  semanage_set_store_root;
 } LIBSEMANAGE_1.0;
+
+LIBSEMANAGE_1.2 {
+  global:
+	  semanage_set_optimize;
+} LIBSEMANAGE_1.1;
-- 
2.20.1

[PATCH userspace 4/4] semodule: add flag to disable policy optimization

[Ondrej Mosnacek]

Skip binary policy optimization on rebuild when the --no-optimize
command-line flag is given.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 policycoreutils/semodule/semodule.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/policycoreutils/semodule/semodule.c b/policycoreutils/semodule/semodule.c
index a76797f5..f490ca2e 100644
--- a/policycoreutils/semodule/semodule.c
+++ b/policycoreutils/semodule/semodule.c
@@ -46,6 +46,7 @@ static int verbose;
 static int reload;
 static int no_reload;
 static int build;
+static int no_optimize;
 static int disable_dontaudit;
 static int preserve_tunables;
 static int ignore_module_cache;
@@ -123,8 +124,9 @@ static void usage(char *progname)
 	printf("usage:  %s [option]... MODE...\n", progname);
 	printf("Manage SELinux policy modules.\n");
 	printf("MODES:\n");
-	printf("  -R, --reload		    reload policy\n");
-	printf("  -B, --build		    build and reload policy\n");
+	printf("  -R,--reload		    reload policy\n");
+	printf("  -B,--build		    build and reload policy\n");
+	printf("     --no-optimize	    do not optimize built policy\n");
 	printf("  -D,--disable_dontaudit    Remove dontaudits from policy\n");
 	printf("  -i,--install=MODULE_PKG   install a new module\n");
 	printf("  -r,--remove=MODULE_NAME   remove existing module at desired priority\n");
@@ -191,6 +193,7 @@ static void parse_command_line(int argc, char **argv)
 		{"reload", 0, NULL, 'R'},
 		{"noreload", 0, NULL, 'n'},
 		{"build", 0, NULL, 'B'},
+		{"no-optimize", 0, NULL, 'O'},
 		{"disable_dontaudit", 0, NULL, 'D'},
 		{"preserve_tunables", 0, NULL, 'P'},
 		{"ignore-module-cache", 0, NULL, 'C'},
@@ -268,6 +271,9 @@ static void parse_command_line(int argc, char **argv)
 		case 'B':
 			build = 1;
 			break;
+		case 'O':
+			no_optimize = 1;
+			break;
 		case 'D':
 			disable_dontaudit = 1;
 			break;
@@ -738,6 +744,8 @@ cleanup_disable:
 			semanage_set_reload(sh, 0);
 		if (build)
 			semanage_set_rebuild(sh, 1);
+		if (no_optimize)
+			semanage_set_optimize(sh, 0);
 		if (disable_dontaudit)
 			semanage_set_disable_dontaudit(sh, 1);
 		else if (build)
-- 
2.20.1

Re: [PATCH userspace 0/4] Remove redundant rules when building policydb

[Dominick Grift]

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

On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> This series implements an optional optimization step when building
> a policydb via semodule or secilc, which identifies and removes rules
> that are redundant -- i.e. they are already covered by a more general
> rule based on attribute inheritance.

Some stats with dssp2-standard:

[kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt

real    0m9.278s
user    0m7.036s
sys     0m2.017s
[kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt

real    0m19.343s
user    0m16.939s
sys     0m2.027s
[kcinimod@myguest dssp2-standard]$ ls -lh policy.*
-rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
-rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt

Was unable to see the actual diff as sediff got oom-killed on me

> 
> Since the performance penalty of this additional step is very small
> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> it can have a big positive effect on the number of rules in policy
> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> optimization is enabled by default and can be turned off using a
> command-line option (--no-optimize) in secilc and semodule [2].
> 
> The optimization routine eliminates:
>  * all allow/neverallow/dontaudit/auditallow rules (including xperm
>    variants) that are covered by another more general rule,
>  * all conditional versions of the above rules that are covered by a
>    more general rule either in the unconditional table or in the same
>    branch of the same conditional.
> 
> The optimization doesn't process other rules, since they currently
> do not support attributes. There is some room left for more precise
> optimization of conditional rules, but it would likely bring only
> little additional benefit.
> 
> When the policy is mostly or fully expanded, the optimization should
> be turned off. If it isn't, the policy build time will increase a lot
> for no benefit. However, the complexity of optimization will be only
> linear w.r.t. the number of rules and so the impact should not be
> catastrophic. (When testing with secilc on a subset of Fedora policy
> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> without it.)
> 
> Tested live on my Fedora 29 devel machine under normal use. No unusual
> AVCs were observed with optimized policy loaded.
> 
> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> 
> NOTE: The xperm rule support wasn't tested -- I would welcome some
>       peer review/testing of this part.
> 
> [1] As measured on my machine (Fedora 29 policy, x86_64).
> [2] I have no problem with switching it to opt-in if that is preferred.
> 
> Ondrej Mosnacek (4):
>   libsepol: add a function to optimize kernel policy
>   secilc: optimize policy before writing
>   libsemanage: optimize policy on rebuild
>   semodule: add flag to disable policy optimization
> 
>  libsemanage/include/semanage/handle.h      |   4 +
>  libsemanage/src/direct_api.c               |   7 +
>  libsemanage/src/handle.c                   |  13 +
>  libsemanage/src/handle.h                   |   1 +
>  libsemanage/src/libsemanage.map            |   5 +
>  libsepol/include/sepol/policydb.h          |   5 +
>  libsepol/include/sepol/policydb/policydb.h |   2 +
>  libsepol/src/libsepol.map.in               |   5 +
>  libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
>  libsepol/src/policydb_public.c             |   5 +
>  policycoreutils/semodule/semodule.c        |  12 +-
>  secilc/secilc.c                            |  16 +-
>  12 files changed, 442 insertions(+), 3 deletions(-)
>  create mode 100644 libsepol/src/optimize.c
> 
> -- 
> 2.20.1
> 

-- 
Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
Dominick Grift

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 659 bytes --]

Re: [PATCH userspace 0/4] Remove redundant rules when building policydb

[Dominick Grift]

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

On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
> On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> > This series implements an optional optimization step when building
> > a policydb via semodule or secilc, which identifies and removes rules
> > that are redundant -- i.e. they are already covered by a more general
> > rule based on attribute inheritance.
> 
> Some stats with dssp2-standard:
> 
> [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
> 
> real    0m9.278s
> user    0m7.036s
> sys     0m2.017s
> [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
> 
> real    0m19.343s
> user    0m16.939s
> sys     0m2.027s
> [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
> -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
> -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
> 
> Was unable to see the actual diff as sediff got oom-killed on me

According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
Looks like dssp2-standard is pretty efficient as it is.

> 
> > 
> > Since the performance penalty of this additional step is very small
> > (it adds about 1 s to the current running time of ~20-30 s [1]) and
> > it can have a big positive effect on the number of rules in policy
> > (it manages to remove ~40% AV rules from Fedora 29 policy), the
> > optimization is enabled by default and can be turned off using a
> > command-line option (--no-optimize) in secilc and semodule [2].
> > 
> > The optimization routine eliminates:
> >  * all allow/neverallow/dontaudit/auditallow rules (including xperm
> >    variants) that are covered by another more general rule,
> >  * all conditional versions of the above rules that are covered by a
> >    more general rule either in the unconditional table or in the same
> >    branch of the same conditional.
> > 
> > The optimization doesn't process other rules, since they currently
> > do not support attributes. There is some room left for more precise
> > optimization of conditional rules, but it would likely bring only
> > little additional benefit.
> > 
> > When the policy is mostly or fully expanded, the optimization should
> > be turned off. If it isn't, the policy build time will increase a lot
> > for no benefit. However, the complexity of optimization will be only
> > linear w.r.t. the number of rules and so the impact should not be
> > catastrophic. (When testing with secilc on a subset of Fedora policy
> > with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> > without it.)
> > 
> > Tested live on my Fedora 29 devel machine under normal use. No unusual
> > AVCs were observed with optimized policy loaded.
> > 
> > Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> > 
> > NOTE: The xperm rule support wasn't tested -- I would welcome some
> >       peer review/testing of this part.
> > 
> > [1] As measured on my machine (Fedora 29 policy, x86_64).
> > [2] I have no problem with switching it to opt-in if that is preferred.
> > 
> > Ondrej Mosnacek (4):
> >   libsepol: add a function to optimize kernel policy
> >   secilc: optimize policy before writing
> >   libsemanage: optimize policy on rebuild
> >   semodule: add flag to disable policy optimization
> > 
> >  libsemanage/include/semanage/handle.h      |   4 +
> >  libsemanage/src/direct_api.c               |   7 +
> >  libsemanage/src/handle.c                   |  13 +
> >  libsemanage/src/handle.h                   |   1 +
> >  libsemanage/src/libsemanage.map            |   5 +
> >  libsepol/include/sepol/policydb.h          |   5 +
> >  libsepol/include/sepol/policydb/policydb.h |   2 +
> >  libsepol/src/libsepol.map.in               |   5 +
> >  libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
> >  libsepol/src/policydb_public.c             |   5 +
> >  policycoreutils/semodule/semodule.c        |  12 +-
> >  secilc/secilc.c                            |  16 +-
> >  12 files changed, 442 insertions(+), 3 deletions(-)
> >  create mode 100644 libsepol/src/optimize.c
> > 
> > -- 
> > 2.20.1
> > 
> 
> -- 
> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
> Dominick Grift



-- 
Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
Dominick Grift

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 659 bytes --]

Re: [PATCH userspace 0/4] Remove redundant rules when building policydb

[Ondrej Mosnacek]

On Thu, May 23, 2019 at 3:40 PM Dominick Grift <dac.override@gmail.com> wrote:
> On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
> > On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> > > This series implements an optional optimization step when building
> > > a policydb via semodule or secilc, which identifies and removes rules
> > > that are redundant -- i.e. they are already covered by a more general
> > > rule based on attribute inheritance.
> >
> > Some stats with dssp2-standard:
> >
> > [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
> >
> > real    0m9.278s
> > user    0m7.036s
> > sys     0m2.017s
> > [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
> >
> > real    0m19.343s
> > user    0m16.939s
> > sys     0m2.027s
> > [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
> > -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
> > -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
> >
> > Was unable to see the actual diff as sediff got oom-killed on me
>
> According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
> Looks like dssp2-standard is pretty efficient as it is.

Hmm, yeah, looks like I'll have to make it opt-in after all... or add
some heuristic to decide if running the optimization is really worth
it.

>
> >
> > >
> > > Since the performance penalty of this additional step is very small
> > > (it adds about 1 s to the current running time of ~20-30 s [1]) and
> > > it can have a big positive effect on the number of rules in policy
> > > (it manages to remove ~40% AV rules from Fedora 29 policy), the
> > > optimization is enabled by default and can be turned off using a
> > > command-line option (--no-optimize) in secilc and semodule [2].
> > >
> > > The optimization routine eliminates:
> > >  * all allow/neverallow/dontaudit/auditallow rules (including xperm
> > >    variants) that are covered by another more general rule,
> > >  * all conditional versions of the above rules that are covered by a
> > >    more general rule either in the unconditional table or in the same
> > >    branch of the same conditional.
> > >
> > > The optimization doesn't process other rules, since they currently
> > > do not support attributes. There is some room left for more precise
> > > optimization of conditional rules, but it would likely bring only
> > > little additional benefit.
> > >
> > > When the policy is mostly or fully expanded, the optimization should
> > > be turned off. If it isn't, the policy build time will increase a lot
> > > for no benefit. However, the complexity of optimization will be only
> > > linear w.r.t. the number of rules and so the impact should not be
> > > catastrophic. (When testing with secilc on a subset of Fedora policy
> > > with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> > > without it.)
> > >
> > > Tested live on my Fedora 29 devel machine under normal use. No unusual
> > > AVCs were observed with optimized policy loaded.
> > >
> > > Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> > >
> > > NOTE: The xperm rule support wasn't tested -- I would welcome some
> > >       peer review/testing of this part.
> > >
> > > [1] As measured on my machine (Fedora 29 policy, x86_64).
> > > [2] I have no problem with switching it to opt-in if that is preferred.
> > >
> > > Ondrej Mosnacek (4):
> > >   libsepol: add a function to optimize kernel policy
> > >   secilc: optimize policy before writing
> > >   libsemanage: optimize policy on rebuild
> > >   semodule: add flag to disable policy optimization
> > >
> > >  libsemanage/include/semanage/handle.h      |   4 +
> > >  libsemanage/src/direct_api.c               |   7 +
> > >  libsemanage/src/handle.c                   |  13 +
> > >  libsemanage/src/handle.h                   |   1 +
> > >  libsemanage/src/libsemanage.map            |   5 +
> > >  libsepol/include/sepol/policydb.h          |   5 +
> > >  libsepol/include/sepol/policydb/policydb.h |   2 +
> > >  libsepol/src/libsepol.map.in               |   5 +
> > >  libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
> > >  libsepol/src/policydb_public.c             |   5 +
> > >  policycoreutils/semodule/semodule.c        |  12 +-
> > >  secilc/secilc.c                            |  16 +-
> > >  12 files changed, 442 insertions(+), 3 deletions(-)
> > >  create mode 100644 libsepol/src/optimize.c
> > >
> > > --
> > > 2.20.1
> > >
> >
> > --
> > Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
> > https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
> > Dominick Grift
>
>
>
> --
> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
> Dominick Grift



-- 
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb

[jwcart2]

On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
> This series implements an optional optimization step when building
> a policydb via semodule or secilc, which identifies and removes rules
> that are redundant -- i.e. they are already covered by a more general
> rule based on attribute inheritance.
> 
> Since the performance penalty of this additional step is very small
> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> it can have a big positive effect on the number of rules in policy
> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> optimization is enabled by default and can be turned off using a
> command-line option (--no-optimize) in secilc and semodule [2].
> 
> The optimization routine eliminates:
>   * all allow/neverallow/dontaudit/auditallow rules (including xperm
>     variants) that are covered by another more general rule,
>   * all conditional versions of the above rules that are covered by a
>     more general rule either in the unconditional table or in the same
>     branch of the same conditional.
> 
> The optimization doesn't process other rules, since they currently
> do not support attributes. There is some room left for more precise
> optimization of conditional rules, but it would likely bring only
> little additional benefit.
> 
> When the policy is mostly or fully expanded, the optimization should
> be turned off. If it isn't, the policy build time will increase a lot
> for no benefit. However, the complexity of optimization will be only
> linear w.r.t. the number of rules and so the impact should not be
> catastrophic. (When testing with secilc on a subset of Fedora policy
> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> without it.)
> 
> Tested live on my Fedora 29 devel machine under normal use. No unusual
> AVCs were observed with optimized policy loaded.
> 
> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> 
> NOTE: The xperm rule support wasn't tested -- I would welcome some
>        peer review/testing of this part.
> 
> [1] As measured on my machine (Fedora 29 policy, x86_64).
> [2] I have no problem with switching it to opt-in if that is preferred.
> 
> Ondrej Mosnacek (4):
>    libsepol: add a function to optimize kernel policy
>    secilc: optimize policy before writing
>    libsemanage: optimize policy on rebuild
>    semodule: add flag to disable policy optimization
> 
>   libsemanage/include/semanage/handle.h      |   4 +
>   libsemanage/src/direct_api.c               |   7 +
>   libsemanage/src/handle.c                   |  13 +
>   libsemanage/src/handle.h                   |   1 +
>   libsemanage/src/libsemanage.map            |   5 +
>   libsepol/include/sepol/policydb.h          |   5 +
>   libsepol/include/sepol/policydb/policydb.h |   2 +
>   libsepol/src/libsepol.map.in               |   5 +
>   libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
>   libsepol/src/policydb_public.c             |   5 +
>   policycoreutils/semodule/semodule.c        |  12 +-
>   secilc/secilc.c                            |  16 +-
>   12 files changed, 442 insertions(+), 3 deletions(-)
>   create mode 100644 libsepol/src/optimize.c
> 

It would be nice to have checkpolicy support this as well. It shouldn't be too 
hard to do that.

I need to do some more testing, but I think something is not working correctly.

I am starting from conf files here because I have both Fedora and Android ones 
that I have used for testing and it is easier to run them through checkpolicy to 
convert to CIL.

With these rules:

# Redundant 1
allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
allow tp02 tpr1:cl01 { p01a p11a };
allow at02 tpr1:cl01 { p01a p11a p01b };

# Redundant 2
dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr2:cl01 { p01a p11a };
dontaudit at02 tpr2:cl01 { p01a p11a p01b };

# Redundant 3
allow at02 tpr3:cl01 { p01a p11a p01b };
if (b01) {
   allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
   allow tp02 tpr3:cl01 { p01a p11a };
}

# Redundant 4
dontaudit at02 tpr4:cl01 { p01a p11a p01b };
if (b01) {
   dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
   dontaudit tp02 tpr4:cl01 { p01a p11a };
}


I see the following from sediff:

Allow Rules (0 Added, 1 Removed, 0 Modified)
    Removed Allow Rules: 1
       - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True

Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
    Removed Dontaudit Rules: 1
       - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
    Modified Dontaudit Rules: 1
       * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };

So it handles Redundant 1 just fine, but has problems with Redundant 2 which 
should be the same.

I don't remember what to expect from sediff for boolean rules. I had played 
around with removing rules with some of my earlier lua tools and I thought that 
sediff handled removing redundant rules from booleans, but I could be wrong.

I will look at this more maybe tomorrow, but most likely after the Memorial day 
weekend.

Jim

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

Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb

[Ondrej Mosnacek]

On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
> > This series implements an optional optimization step when building
> > a policydb via semodule or secilc, which identifies and removes rules
> > that are redundant -- i.e. they are already covered by a more general
> > rule based on attribute inheritance.
> >
> > Since the performance penalty of this additional step is very small
> > (it adds about 1 s to the current running time of ~20-30 s [1]) and
> > it can have a big positive effect on the number of rules in policy
> > (it manages to remove ~40% AV rules from Fedora 29 policy), the
> > optimization is enabled by default and can be turned off using a
> > command-line option (--no-optimize) in secilc and semodule [2].
> >
> > The optimization routine eliminates:
> >   * all allow/neverallow/dontaudit/auditallow rules (including xperm
> >     variants) that are covered by another more general rule,
> >   * all conditional versions of the above rules that are covered by a
> >     more general rule either in the unconditional table or in the same
> >     branch of the same conditional.
> >
> > The optimization doesn't process other rules, since they currently
> > do not support attributes. There is some room left for more precise
> > optimization of conditional rules, but it would likely bring only
> > little additional benefit.
> >
> > When the policy is mostly or fully expanded, the optimization should
> > be turned off. If it isn't, the policy build time will increase a lot
> > for no benefit. However, the complexity of optimization will be only
> > linear w.r.t. the number of rules and so the impact should not be
> > catastrophic. (When testing with secilc on a subset of Fedora policy
> > with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> > without it.)
> >
> > Tested live on my Fedora 29 devel machine under normal use. No unusual
> > AVCs were observed with optimized policy loaded.
> >
> > Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> >
> > NOTE: The xperm rule support wasn't tested -- I would welcome some
> >        peer review/testing of this part.
> >
> > [1] As measured on my machine (Fedora 29 policy, x86_64).
> > [2] I have no problem with switching it to opt-in if that is preferred.
> >
> > Ondrej Mosnacek (4):
> >    libsepol: add a function to optimize kernel policy
> >    secilc: optimize policy before writing
> >    libsemanage: optimize policy on rebuild
> >    semodule: add flag to disable policy optimization
> >
> >   libsemanage/include/semanage/handle.h      |   4 +
> >   libsemanage/src/direct_api.c               |   7 +
> >   libsemanage/src/handle.c                   |  13 +
> >   libsemanage/src/handle.h                   |   1 +
> >   libsemanage/src/libsemanage.map            |   5 +
> >   libsepol/include/sepol/policydb.h          |   5 +
> >   libsepol/include/sepol/policydb/policydb.h |   2 +
> >   libsepol/src/libsepol.map.in               |   5 +
> >   libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
> >   libsepol/src/policydb_public.c             |   5 +
> >   policycoreutils/semodule/semodule.c        |  12 +-
> >   secilc/secilc.c                            |  16 +-
> >   12 files changed, 442 insertions(+), 3 deletions(-)
> >   create mode 100644 libsepol/src/optimize.c
> >
>
> It would be nice to have checkpolicy support this as well. It shouldn't be too
> hard to do that.

Looking at checkpolicy.c, it looks like it only generates POLICY_BASE
or POLICY_MODULE policy types. I currently limit the optimization only
to POLICY_KERN type, because from comments in policydb.h I got the
impression that other policy types have different structure and I'm
not sure if they need some special handling. I don't have that much
knowledge about SELinux userspace code yet... if you can give me some
hints about the difference between the various POLICY_* types, then I
will be happy to make some adjustments if they make sense.

>
> I need to do some more testing, but I think something is not working correctly.
>
> I am starting from conf files here because I have both Fedora and Android ones
> that I have used for testing and it is easier to run them through checkpolicy to
> convert to CIL.
>
> With these rules:
>
> # Redundant 1
> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
> allow tp02 tpr1:cl01 { p01a p11a };
> allow at02 tpr1:cl01 { p01a p11a p01b };
>
> # Redundant 2
> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
> dontaudit tp02 tpr2:cl01 { p01a p11a };
> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
>
> # Redundant 3
> allow at02 tpr3:cl01 { p01a p11a p01b };
> if (b01) {
>    allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
>    allow tp02 tpr3:cl01 { p01a p11a };
> }
>
> # Redundant 4
> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
> if (b01) {
>    dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
>    dontaudit tp02 tpr4:cl01 { p01a p11a };
> }
>
>
> I see the following from sediff:
>
> Allow Rules (0 Added, 1 Removed, 0 Modified)
>     Removed Allow Rules: 1
>        - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
>
> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
>     Removed Dontaudit Rules: 1
>        - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
>     Modified Dontaudit Rules: 1
>        * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
>
> So it handles Redundant 1 just fine, but has problems with Redundant 2 which
> should be the same.

Yes, I think I'm handling the dontaudit rules incorrectly... For some
(historical?) reason they actually specify the permissions that *are*
audited, although the semantic of combining multiple rules is still
that a permission is dontaudited if there is at least one dontaudit
rule for it, so the logic of handling the raw perms data has to be
inverted for AVTAB_AUDITDENY entries. I had noticed earlier that
AVTAB_AUDITDENY rules are handled differently but somehow I concluded
that the perms values should still bitwise-or together...

Can you please try it with adding:

if (specified & AVTAB_AUDITDENY)
    return (d1->data & d2->data) == d2->data;

to the beginning of match_avtab_datum() in optimize.c? (patch form
here: https://github.com/WOnder93/selinux/commit/17c77e4bb8857ebfff9b32e2e0bc800e206aba1e.patch)

>
> I don't remember what to expect from sediff for boolean rules. I had played
> around with removing rules with some of my earlier lua tools and I thought that
> sediff handled removing redundant rules from booleans, but I could be wrong.
>
> I will look at this more maybe tomorrow, but most likely after the Memorial day
> weekend.
>
> Jim
>
> --
> James Carter <jwcart2@tycho.nsa.gov>
> National Security Agency
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb

[jwcart2]

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

On 5/24/19 4:54 AM, Ondrej Mosnacek wrote:
> On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
>> On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
>>> This series implements an optional optimization step when building
>>> a policydb via semodule or secilc, which identifies and removes rules
>>> that are redundant -- i.e. they are already covered by a more general
>>> rule based on attribute inheritance.
>>>
>>> Since the performance penalty of this additional step is very small
>>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
>>> it can have a big positive effect on the number of rules in policy
>>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
>>> optimization is enabled by default and can be turned off using a
>>> command-line option (--no-optimize) in secilc and semodule [2].
>>>
>>> The optimization routine eliminates:
>>>    * all allow/neverallow/dontaudit/auditallow rules (including xperm
>>>      variants) that are covered by another more general rule,
>>>    * all conditional versions of the above rules that are covered by a
>>>      more general rule either in the unconditional table or in the same
>>>      branch of the same conditional.
>>>
>>> The optimization doesn't process other rules, since they currently
>>> do not support attributes. There is some room left for more precise
>>> optimization of conditional rules, but it would likely bring only
>>> little additional benefit.
>>>
>>> When the policy is mostly or fully expanded, the optimization should
>>> be turned off. If it isn't, the policy build time will increase a lot
>>> for no benefit. However, the complexity of optimization will be only
>>> linear w.r.t. the number of rules and so the impact should not be
>>> catastrophic. (When testing with secilc on a subset of Fedora policy
>>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
>>> without it.)
>>>
>>> Tested live on my Fedora 29 devel machine under normal use. No unusual
>>> AVCs were observed with optimized policy loaded.
>>>
>>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
>>>
>>> NOTE: The xperm rule support wasn't tested -- I would welcome some
>>>         peer review/testing of this part.
>>>
>>> [1] As measured on my machine (Fedora 29 policy, x86_64).
>>> [2] I have no problem with switching it to opt-in if that is preferred.
>>>
>>> Ondrej Mosnacek (4):
>>>     libsepol: add a function to optimize kernel policy
>>>     secilc: optimize policy before writing
>>>     libsemanage: optimize policy on rebuild
>>>     semodule: add flag to disable policy optimization
>>>
>>>    libsemanage/include/semanage/handle.h      |   4 +
>>>    libsemanage/src/direct_api.c               |   7 +
>>>    libsemanage/src/handle.c                   |  13 +
>>>    libsemanage/src/handle.h                   |   1 +
>>>    libsemanage/src/libsemanage.map            |   5 +
>>>    libsepol/include/sepol/policydb.h          |   5 +
>>>    libsepol/include/sepol/policydb/policydb.h |   2 +
>>>    libsepol/src/libsepol.map.in               |   5 +
>>>    libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
>>>    libsepol/src/policydb_public.c             |   5 +
>>>    policycoreutils/semodule/semodule.c        |  12 +-
>>>    secilc/secilc.c                            |  16 +-
>>>    12 files changed, 442 insertions(+), 3 deletions(-)
>>>    create mode 100644 libsepol/src/optimize.c
>>>
>>
>> It would be nice to have checkpolicy support this as well. It shouldn't be too
>> hard to do that.
> 
> Looking at checkpolicy.c, it looks like it only generates POLICY_BASE
> or POLICY_MODULE policy types. I currently limit the optimization only
> to POLICY_KERN type, because from comments in policydb.h I got the
> impression that other policy types have different structure and I'm
> not sure if they need some special handling. I don't have that much
> knowledge about SELinux userspace code yet... if you can give me some
> hints about the difference between the various POLICY_* types, then I
> will be happy to make some adjustments if they make sense.
> 

It is kind of confusing. I sent a patch to the list. You can incorporate that 
into your patch series or I can just do it after.

I've attached the test policy that I used and a test script. I haven't had a 
chance to dig more into what may be going on.

Jim


>>
>> I need to do some more testing, but I think something is not working correctly.
>>
>> I am starting from conf files here because I have both Fedora and Android ones
>> that I have used for testing and it is easier to run them through checkpolicy to
>> convert to CIL.
>>
>> With these rules:
>>
>> # Redundant 1
>> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
>> allow tp02 tpr1:cl01 { p01a p11a };
>> allow at02 tpr1:cl01 { p01a p11a p01b };
>>
>> # Redundant 2
>> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
>> dontaudit tp02 tpr2:cl01 { p01a p11a };
>> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
>>
>> # Redundant 3
>> allow at02 tpr3:cl01 { p01a p11a p01b };
>> if (b01) {
>>     allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
>>     allow tp02 tpr3:cl01 { p01a p11a };
>> }
>>
>> # Redundant 4
>> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
>> if (b01) {
>>     dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
>>     dontaudit tp02 tpr4:cl01 { p01a p11a };
>> }
>>
>>
>> I see the following from sediff:
>>
>> Allow Rules (0 Added, 1 Removed, 0 Modified)
>>      Removed Allow Rules: 1
>>         - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
>>
>> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
>>      Removed Dontaudit Rules: 1
>>         - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
>>      Modified Dontaudit Rules: 1
>>         * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
>>
>> So it handles Redundant 1 just fine, but has problems with Redundant 2 which
>> should be the same.
> 
> Yes, I think I'm handling the dontaudit rules incorrectly... For some
> (historical?) reason they actually specify the permissions that *are*
> audited, although the semantic of combining multiple rules is still
> that a permission is dontaudited if there is at least one dontaudit
> rule for it, so the logic of handling the raw perms data has to be
> inverted for AVTAB_AUDITDENY entries. I had noticed earlier that
> AVTAB_AUDITDENY rules are handled differently but somehow I concluded
> that the perms values should still bitwise-or together...
> 
> Can you please try it with adding:
> 
> if (specified & AVTAB_AUDITDENY)
>      return (d1->data & d2->data) == d2->data;
> 
> to the beginning of match_avtab_datum() in optimize.c? (patch form
> here: https://github.com/WOnder93/selinux/commit/17c77e4bb8857ebfff9b32e2e0bc800e206aba1e.patch)
> 
>>
>> I don't remember what to expect from sediff for boolean rules. I had played
>> around with removing rules with some of my earlier lua tools and I thought that
>> sediff handled removing redundant rules from booleans, but I could be wrong.
>>
>> I will look at this more maybe tomorrow, but most likely after the Memorial day
>> weekend.
>>
>> Jim
>>
>> --
>> James Carter <jwcart2@tycho.nsa.gov>
>> National Security Agency
> --
> Ondrej Mosnacek <omosnace at redhat dot com>
> Software Engineer, Security Technologies
> Red Hat, Inc.
> 


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

[-- Attachment #2: test_01.conf --]
[-- Type: text/plain, Size: 4295 bytes --]

# All policy.conf rules
# Called test_02.conf in expected_pass/conf
# Added redundantallow rules that are covered by attribute

class cl01
class cl02
class cl03
class cl04
class clx

sid kernel
sid security
sid unlabeled

common cm01 { p11a p11b }
common cm02 { p22a p22b }

class cl01 inherits cm01 { p01a p01b }
class cl02 inherits cm02
class cl03 { p03a p03b }
class cl04 { p04a p04b }
class clx { ioctl }

default_user { cl01 cl02 cl03 } source;
default_role { cl01 } source;
default_type { cl02 } target;
default_range { cl03 } target low-high;

sensitivity s01 alias syslow;
sensitivity s02;
sensitivity s03 alias { syshigh maxsens };

dominance { s01 s02 s03 }

category c01 alias cat01;
category c02 alias { cat02a cat02b };
category c03;

level s01;
level s02:c01,c03;
level s03:c01.c03;

mlsconstrain cl01 { p01a } ((h1 dom h2) and (l1 domby h1));
mlsvalidatetrans cl02 ((l1 eq l2) or (l1 incomp l2));
mlsvalidatetrans cl02 ((l1 eq l2) or (t3 eq tpo));

policycap network_peer_controls;
policycap open_perms;

attribute at01;
attribute at02;

attribute_role ar01;
attribute_role ar02;

bool b01 false;
bool b02 true;

type tpo;
type tpx;
type tp01;
type tp02;
type tp03p;
type tp03c;
type tp04;
type tpr1;
type tpr2;
type tpr3;
type tpr4;
type tpr5;

typealias tp01 alias { ta01a ta01b };
typealias tp02 alias ta02;

typebounds tp03p tp03c;

typeattribute tp01 at01, at02;
typeattribute tp02 at02;

permissive tp01;

allow tp01 self:cl01 { p01a p11a };
allow tp01 ta01a:cl01 p01b;
allow tp01 at01:cl01 p11b;
allow tp01 tpo:cl02 p22a;
allow at02 tpo:cl02 p22b;
allow tp03p tpo:cl03 { p03a p03b };
allow tp03c tpo:cl03 p03a;
allow tp04 tpx:clx ioctl;
auditallow tp01 tpo:cl01 p01a;
dontaudit tp01 tpo:cl01 p01b;
neverallow tp01 tpo:cl01 p11a;

# Redundant 1
allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
allow tp02 tpr1:cl01 { p01a p11a };
allow at02 tpr1:cl01 { p01a p11a p01b };

# Redundant 2
dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr2:cl01 { p01a p11a };
dontaudit at02 tpr2:cl01 { p01a p11a p01b };

# Redundant 3
allow at02 tpr3:cl01 { p01a p11a p01b };
if (b01) {
  allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
  allow tp02 tpr3:cl01 { p01a p11a };
}

# Redundant 4
dontaudit at02 tpr4:cl01 { p01a p11a p01b };
if (b01) {
  dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
  dontaudit tp02 tpr4:cl01 { p01a p11a };
}

# Redundant 5

if (b01) {
  allow tp01 tpr5:cl01 { p01a p11a p01b p11b };
  allow tp02 tpr5:cl01 { p01a p11a };
} else {
  allow at02 tpr5:cl01 { p01a p11a p01b };
}

allowxperm tp04 tpx:clx ioctl 0x1234;
auditallowxperm tp04 tpx:clx ioctl 0x9911;
dontauditxperm tp04 tpx:clx ioctl 0x9922;
neverallowxperm tp04 tpx:clx ioctl 0x9933;

type_transition tp01 tpo:cl01 tp02;
type_member tp01 tpo:cl02 tp02;
type_change tp01 tpo:cl03 tp02;
type_transition tp01 tpo:cl04 tp02 "file01";

range_transition tp01 tpo:cl01 s02;  
range_transition tp01 tpo:cl02 s02 - s03:c01,cat02a;  

role rl01;
role rl02;
role rl03p;
role rl03c;

role rl01 types { tp01 tp02 };
role rl02 types { tp02 };
role rl03p types tp03p;
role rl03c types tp03c;

roleattribute rl01 ar01, ar02;
roleattribute rl02 ar02;

allow rl01 rl02;

role_transition rl01 tpo:cl01 rl02;

user us01 roles rl01 level s01 range s01 - s03:c01.c03;

constrain cl01 { p01b } not ((t1 == tpo) and (u1 != u2));
validatetrans cl02 ((u1 == u2) or (r1 == r2));
validatetrans cl02 ((u1 == u2) or (t3 == tpo));

sid kernel us01:rl01:tp01:syslow - syshigh:c01,cat02b,c03
sid security us01:rl01:tp01:s01 - s02
sid unlabeled us01:rl01:tp01:s02:c01,c03 - maxsens:cat01,c03

fs_use_xattr fs01 us01:rl01:tp01:s01;
fs_use_task fs02 us01:rl01:tp01:s01;
fs_use_trans fs03 us01:rl01:tp01:s01;
genfscon fs04 / us01:rl01:tp01:s01
portcon udp 1000 us01:rl01:tp01:s01
portcon udp 1001-1009 us01:rl01:tp01:s01
portcon tcp 2000 us01:rl01:tp01:s01
portcon tcp 2001-2009 us01:rl01:tp01:s01
portcon dccp 3000 us01:rl01:tp01:s01
portcon dccp 3001-3009 us01:rl01:tp01:s01
netifcon if01 us01:rl01:tp01:s01 us01:rl01:tp02:s01
nodecon 10.0.0.1 255.255.255.0 us01:rl01:tp01:s01
nodecon fc00::1 fc00::ffff us01:rl01:tp01:s01

# XEN
#pirqcon 65535 us01:rl01:tp01:s01
#iomemcon 0-99999 us01:rl01:tp01:s01
#ioportcon 0-99999 us01:rl01:tp01:s01
#pcidevicecon 99999 us01:rl01:tp01:s01
#devicetreecon "/PATH" us01:rl01:tp01:s01

[-- Attachment #3: test.sh --]
[-- Type: application/x-shellscript, Size: 990 bytes --]

Re: [Non-DoD Source] Re: [PATCH userspace 0/4] Remove redundant rules when building policydb

[jwcart2]

On 5/23/19 10:08 AM, Ondrej Mosnacek wrote:
> On Thu, May 23, 2019 at 3:40 PM Dominick Grift <dac.override@gmail.com> wrote:
>> On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
>>> On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
>>>> This series implements an optional optimization step when building
>>>> a policydb via semodule or secilc, which identifies and removes rules
>>>> that are redundant -- i.e. they are already covered by a more general
>>>> rule based on attribute inheritance.
>>>
>>> Some stats with dssp2-standard:
>>>
>>> [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
>>>
>>> real    0m9.278s
>>> user    0m7.036s
>>> sys     0m2.017s
>>> [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
>>>
>>> real    0m19.343s
>>> user    0m16.939s
>>> sys     0m2.027s
>>> [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
>>> -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
>>> -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
>>>
>>> Was unable to see the actual diff as sediff got oom-killed on me
>>
>> According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
>> Looks like dssp2-standard is pretty efficient as it is.
> 
> Hmm, yeah, looks like I'll have to make it opt-in after all... or add
> some heuristic to decide if running the optimization is really worth
> it.
> 

Opt-in makes sense. How about just using 'O' for the option?

Jim

>>
>>>
>>>>
>>>> Since the performance penalty of this additional step is very small
>>>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
>>>> it can have a big positive effect on the number of rules in policy
>>>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
>>>> optimization is enabled by default and can be turned off using a
>>>> command-line option (--no-optimize) in secilc and semodule [2].
>>>>
>>>> The optimization routine eliminates:
>>>>   * all allow/neverallow/dontaudit/auditallow rules (including xperm
>>>>     variants) that are covered by another more general rule,
>>>>   * all conditional versions of the above rules that are covered by a
>>>>     more general rule either in the unconditional table or in the same
>>>>     branch of the same conditional.
>>>>
>>>> The optimization doesn't process other rules, since they currently
>>>> do not support attributes. There is some room left for more precise
>>>> optimization of conditional rules, but it would likely bring only
>>>> little additional benefit.
>>>>
>>>> When the policy is mostly or fully expanded, the optimization should
>>>> be turned off. If it isn't, the policy build time will increase a lot
>>>> for no benefit. However, the complexity of optimization will be only
>>>> linear w.r.t. the number of rules and so the impact should not be
>>>> catastrophic. (When testing with secilc on a subset of Fedora policy
>>>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
>>>> without it.)
>>>>
>>>> Tested live on my Fedora 29 devel machine under normal use. No unusual
>>>> AVCs were observed with optimized policy loaded.
>>>>
>>>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
>>>>
>>>> NOTE: The xperm rule support wasn't tested -- I would welcome some
>>>>        peer review/testing of this part.
>>>>
>>>> [1] As measured on my machine (Fedora 29 policy, x86_64).
>>>> [2] I have no problem with switching it to opt-in if that is preferred.
>>>>
>>>> Ondrej Mosnacek (4):
>>>>    libsepol: add a function to optimize kernel policy
>>>>    secilc: optimize policy before writing
>>>>    libsemanage: optimize policy on rebuild
>>>>    semodule: add flag to disable policy optimization
>>>>
>>>>   libsemanage/include/semanage/handle.h      |   4 +
>>>>   libsemanage/src/direct_api.c               |   7 +
>>>>   libsemanage/src/handle.c                   |  13 +
>>>>   libsemanage/src/handle.h                   |   1 +
>>>>   libsemanage/src/libsemanage.map            |   5 +
>>>>   libsepol/include/sepol/policydb.h          |   5 +
>>>>   libsepol/include/sepol/policydb/policydb.h |   2 +
>>>>   libsepol/src/libsepol.map.in               |   5 +
>>>>   libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
>>>>   libsepol/src/policydb_public.c             |   5 +
>>>>   policycoreutils/semodule/semodule.c        |  12 +-
>>>>   secilc/secilc.c                            |  16 +-
>>>>   12 files changed, 442 insertions(+), 3 deletions(-)
>>>>   create mode 100644 libsepol/src/optimize.c
>>>>
>>>> --
>>>> 2.20.1
>>>>
>>>
>>> --
>>> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
>>> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
>>> Dominick Grift
>>
>>
>>
>> --
>> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
>> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
>> Dominick Grift
> 
> 
> 


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

Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb

[Ondrej Mosnacek]

On Fri, May 24, 2019 at 6:01 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 5/24/19 4:54 AM, Ondrej Mosnacek wrote:
> > On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> >> On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
> >>> This series implements an optional optimization step when building
> >>> a policydb via semodule or secilc, which identifies and removes rules
> >>> that are redundant -- i.e. they are already covered by a more general
> >>> rule based on attribute inheritance.
> >>>
> >>> Since the performance penalty of this additional step is very small
> >>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> >>> it can have a big positive effect on the number of rules in policy
> >>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> >>> optimization is enabled by default and can be turned off using a
> >>> command-line option (--no-optimize) in secilc and semodule [2].
> >>>
> >>> The optimization routine eliminates:
> >>>    * all allow/neverallow/dontaudit/auditallow rules (including xperm
> >>>      variants) that are covered by another more general rule,
> >>>    * all conditional versions of the above rules that are covered by a
> >>>      more general rule either in the unconditional table or in the same
> >>>      branch of the same conditional.
> >>>
> >>> The optimization doesn't process other rules, since they currently
> >>> do not support attributes. There is some room left for more precise
> >>> optimization of conditional rules, but it would likely bring only
> >>> little additional benefit.
> >>>
> >>> When the policy is mostly or fully expanded, the optimization should
> >>> be turned off. If it isn't, the policy build time will increase a lot
> >>> for no benefit. However, the complexity of optimization will be only
> >>> linear w.r.t. the number of rules and so the impact should not be
> >>> catastrophic. (When testing with secilc on a subset of Fedora policy
> >>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> >>> without it.)
> >>>
> >>> Tested live on my Fedora 29 devel machine under normal use. No unusual
> >>> AVCs were observed with optimized policy loaded.
> >>>
> >>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> >>>
> >>> NOTE: The xperm rule support wasn't tested -- I would welcome some
> >>>         peer review/testing of this part.
> >>>
> >>> [1] As measured on my machine (Fedora 29 policy, x86_64).
> >>> [2] I have no problem with switching it to opt-in if that is preferred.
> >>>
> >>> Ondrej Mosnacek (4):
> >>>     libsepol: add a function to optimize kernel policy
> >>>     secilc: optimize policy before writing
> >>>     libsemanage: optimize policy on rebuild
> >>>     semodule: add flag to disable policy optimization
> >>>
> >>>    libsemanage/include/semanage/handle.h      |   4 +
> >>>    libsemanage/src/direct_api.c               |   7 +
> >>>    libsemanage/src/handle.c                   |  13 +
> >>>    libsemanage/src/handle.h                   |   1 +
> >>>    libsemanage/src/libsemanage.map            |   5 +
> >>>    libsepol/include/sepol/policydb.h          |   5 +
> >>>    libsepol/include/sepol/policydb/policydb.h |   2 +
> >>>    libsepol/src/libsepol.map.in               |   5 +
> >>>    libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
> >>>    libsepol/src/policydb_public.c             |   5 +
> >>>    policycoreutils/semodule/semodule.c        |  12 +-
> >>>    secilc/secilc.c                            |  16 +-
> >>>    12 files changed, 442 insertions(+), 3 deletions(-)
> >>>    create mode 100644 libsepol/src/optimize.c
> >>>
> >>
> >> It would be nice to have checkpolicy support this as well. It shouldn't be too
> >> hard to do that.
> >
> > Looking at checkpolicy.c, it looks like it only generates POLICY_BASE
> > or POLICY_MODULE policy types. I currently limit the optimization only
> > to POLICY_KERN type, because from comments in policydb.h I got the
> > impression that other policy types have different structure and I'm
> > not sure if they need some special handling. I don't have that much
> > knowledge about SELinux userspace code yet... if you can give me some
> > hints about the difference between the various POLICY_* types, then I
> > will be happy to make some adjustments if they make sense.
> >
>
> It is kind of confusing. I sent a patch to the list. You can incorporate that
> into your patch series or I can just do it after.

Thanks, I'll have a look at it and probably just include in v2.

>
> I've attached the test policy that I used and a test script. I haven't had a
> chance to dig more into what may be going on.

Cool, this test policy will also help me test the xperms support,
thanks! I will play with it tomorrow or on Monday.

I'm ~95% sure that my incremental patch will fix the dontaudit issue -
if I manage to verify it, then I'll squash it in and include in v2.

>
> Jim
>
>
> >>
> >> I need to do some more testing, but I think something is not working correctly.
> >>
> >> I am starting from conf files here because I have both Fedora and Android ones
> >> that I have used for testing and it is easier to run them through checkpolicy to
> >> convert to CIL.
> >>
> >> With these rules:
> >>
> >> # Redundant 1
> >> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
> >> allow tp02 tpr1:cl01 { p01a p11a };
> >> allow at02 tpr1:cl01 { p01a p11a p01b };
> >>
> >> # Redundant 2
> >> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
> >> dontaudit tp02 tpr2:cl01 { p01a p11a };
> >> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
> >>
> >> # Redundant 3
> >> allow at02 tpr3:cl01 { p01a p11a p01b };
> >> if (b01) {
> >>     allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
> >>     allow tp02 tpr3:cl01 { p01a p11a };
> >> }
> >>
> >> # Redundant 4
> >> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
> >> if (b01) {
> >>     dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
> >>     dontaudit tp02 tpr4:cl01 { p01a p11a };
> >> }
> >>
> >>
> >> I see the following from sediff:
> >>
> >> Allow Rules (0 Added, 1 Removed, 0 Modified)
> >>      Removed Allow Rules: 1
> >>         - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
> >>
> >> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
> >>      Removed Dontaudit Rules: 1
> >>         - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
> >>      Modified Dontaudit Rules: 1
> >>         * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
> >>
> >> So it handles Redundant 1 just fine, but has problems with Redundant 2 which
> >> should be the same.
> >
> > Yes, I think I'm handling the dontaudit rules incorrectly... For some
> > (historical?) reason they actually specify the permissions that *are*
> > audited, although the semantic of combining multiple rules is still
> > that a permission is dontaudited if there is at least one dontaudit
> > rule for it, so the logic of handling the raw perms data has to be
> > inverted for AVTAB_AUDITDENY entries. I had noticed earlier that
> > AVTAB_AUDITDENY rules are handled differently but somehow I concluded
> > that the perms values should still bitwise-or together...
> >
> > Can you please try it with adding:
> >
> > if (specified & AVTAB_AUDITDENY)
> >      return (d1->data & d2->data) == d2->data;
> >
> > to the beginning of match_avtab_datum() in optimize.c? (patch form
> > here: https://github.com/WOnder93/selinux/commit/17c77e4bb8857ebfff9b32e2e0bc800e206aba1e.patch)
> >
> >>
> >> I don't remember what to expect from sediff for boolean rules. I had played
> >> around with removing rules with some of my earlier lua tools and I thought that
> >> sediff handled removing redundant rules from booleans, but I could be wrong.
> >>
> >> I will look at this more maybe tomorrow, but most likely after the Memorial day
> >> weekend.
> >>
> >> Jim
> >>
> >> --
> >> James Carter <jwcart2@tycho.nsa.gov>
> >> National Security Agency
> > --
> > Ondrej Mosnacek <omosnace at redhat dot com>
> > Software Engineer, Security Technologies
> > Red Hat, Inc.
> >
>
>
> --
> James Carter <jwcart2@tycho.nsa.gov>
> National Security Agency

-- 
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [Non-DoD Source] Re: [PATCH userspace 0/4] Remove redundant rules when building policydb

[Ondrej Mosnacek]

On Fri, May 24, 2019 at 6:02 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 5/23/19 10:08 AM, Ondrej Mosnacek wrote:
> > On Thu, May 23, 2019 at 3:40 PM Dominick Grift <dac.override@gmail.com> wrote:
> >> On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
> >>> On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> >>>> This series implements an optional optimization step when building
> >>>> a policydb via semodule or secilc, which identifies and removes rules
> >>>> that are redundant -- i.e. they are already covered by a more general
> >>>> rule based on attribute inheritance.
> >>>
> >>> Some stats with dssp2-standard:
> >>>
> >>> [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
> >>>
> >>> real    0m9.278s
> >>> user    0m7.036s
> >>> sys     0m2.017s
> >>> [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
> >>>
> >>> real    0m19.343s
> >>> user    0m16.939s
> >>> sys     0m2.027s
> >>> [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
> >>> -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
> >>> -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
> >>>
> >>> Was unable to see the actual diff as sediff got oom-killed on me
> >>
> >> According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
> >> Looks like dssp2-standard is pretty efficient as it is.
> >
> > Hmm, yeah, looks like I'll have to make it opt-in after all... or add
> > some heuristic to decide if running the optimization is really worth
> > it.
> >
>
> Opt-in makes sense. How about just using 'O' for the option?

Sure, I already have patches to convert to opt-in ready in my devel
branch [1]. Expect them to be incorporated in v2 respin.

[1] https://github.com/WOnder93/selinux/compare/master...optimize-policy-v2

>
> Jim
>
> >>
> >>>
> >>>>
> >>>> Since the performance penalty of this additional step is very small
> >>>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> >>>> it can have a big positive effect on the number of rules in policy
> >>>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> >>>> optimization is enabled by default and can be turned off using a
> >>>> command-line option (--no-optimize) in secilc and semodule [2].
> >>>>
> >>>> The optimization routine eliminates:
> >>>>   * all allow/neverallow/dontaudit/auditallow rules (including xperm
> >>>>     variants) that are covered by another more general rule,
> >>>>   * all conditional versions of the above rules that are covered by a
> >>>>     more general rule either in the unconditional table or in the same
> >>>>     branch of the same conditional.
> >>>>
> >>>> The optimization doesn't process other rules, since they currently
> >>>> do not support attributes. There is some room left for more precise
> >>>> optimization of conditional rules, but it would likely bring only
> >>>> little additional benefit.
> >>>>
> >>>> When the policy is mostly or fully expanded, the optimization should
> >>>> be turned off. If it isn't, the policy build time will increase a lot
> >>>> for no benefit. However, the complexity of optimization will be only
> >>>> linear w.r.t. the number of rules and so the impact should not be
> >>>> catastrophic. (When testing with secilc on a subset of Fedora policy
> >>>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> >>>> without it.)
> >>>>
> >>>> Tested live on my Fedora 29 devel machine under normal use. No unusual
> >>>> AVCs were observed with optimized policy loaded.
> >>>>
> >>>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> >>>>
> >>>> NOTE: The xperm rule support wasn't tested -- I would welcome some
> >>>>        peer review/testing of this part.
> >>>>
> >>>> [1] As measured on my machine (Fedora 29 policy, x86_64).
> >>>> [2] I have no problem with switching it to opt-in if that is preferred.
> >>>>
> >>>> Ondrej Mosnacek (4):
> >>>>    libsepol: add a function to optimize kernel policy
> >>>>    secilc: optimize policy before writing
> >>>>    libsemanage: optimize policy on rebuild
> >>>>    semodule: add flag to disable policy optimization
> >>>>
> >>>>   libsemanage/include/semanage/handle.h      |   4 +
> >>>>   libsemanage/src/direct_api.c               |   7 +
> >>>>   libsemanage/src/handle.c                   |  13 +
> >>>>   libsemanage/src/handle.h                   |   1 +
> >>>>   libsemanage/src/libsemanage.map            |   5 +
> >>>>   libsepol/include/sepol/policydb.h          |   5 +
> >>>>   libsepol/include/sepol/policydb/policydb.h |   2 +
> >>>>   libsepol/src/libsepol.map.in               |   5 +
> >>>>   libsepol/src/optimize.c                    | 370 +++++++++++++++++++++
> >>>>   libsepol/src/policydb_public.c             |   5 +
> >>>>   policycoreutils/semodule/semodule.c        |  12 +-
> >>>>   secilc/secilc.c                            |  16 +-
> >>>>   12 files changed, 442 insertions(+), 3 deletions(-)
> >>>>   create mode 100644 libsepol/src/optimize.c
> >>>>
> >>>> --
> >>>> 2.20.1
> >>>>
> >>>
> >>> --
> >>> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
> >>> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
> >>> Dominick Grift
> >>
> >>
> >>
> >> --
> >> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
> >> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
> >> Dominick Grift
> >
> >
> >
>
>
> --
> James Carter <jwcart2@tycho.nsa.gov>
> National Security Agency



-- 
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb

[Chris PeBenito]

On 5/23/19 4:39 PM, jwcart2 wrote:
> With these rules:
> 
> # Redundant 1
> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
> allow tp02 tpr1:cl01 { p01a p11a };
> allow at02 tpr1:cl01 { p01a p11a p01b };
> 
> # Redundant 2
> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
> dontaudit tp02 tpr2:cl01 { p01a p11a };
> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
> 
> # Redundant 3
> allow at02 tpr3:cl01 { p01a p11a p01b };
> if (b01) {
>    allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
>    allow tp02 tpr3:cl01 { p01a p11a };
> }
> 
> # Redundant 4
> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
> if (b01) {
>    dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
>    dontaudit tp02 tpr4:cl01 { p01a p11a };
> }
> 
> 
> I see the following from sediff:
> 
> Allow Rules (0 Added, 1 Removed, 0 Modified)
>     Removed Allow Rules: 1
>        - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
> 
> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
>     Removed Dontaudit Rules: 1
>        - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
>     Modified Dontaudit Rules: 1
>        * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
> 
> So it handles Redundant 1 just fine, but has problems with Redundant 2 
> which should be the same.
> 
> I don't remember what to expect from sediff for boolean rules. I had 
> played around with removing rules with some of my earlier lua tools and 
> I thought that sediff handled removing redundant rules from booleans, 
> but I could be wrong.

Sediff doesn't do this optimization at this time. Rules inside a 
conditional block won't be considered redundant to unconditional rules.


-- 
Chris PeBenito