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

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

[Ondrej Mosnacek]

Changes in v4:
 * fix deallocation in error path in build_type_map()
 * fix leaked cond nodes
 * also update the man pages
 * use UINT32_C for 0xFFFFFFFF constant
 * squash in the RFC patches & drop the semodule patch
v3: https://lore.kernel.org/selinux/20190529073759.20548-1-omosnace@redhat.com/T/

Changes in v3:
 * fix bad patch squashing
 * rename secilc --optimize-policy option to --optimize (to be simpler
   and consistent with checkpolicy and semodule)
v2: https://lore.kernel.org/selinux/20190528145912.13827-1-omosnace@redhat.com/T/

Changes in v2:
 * fix handling of dontaudit (AVTAB_DENY) rules
 * switch optimization from opt-out to opt-in everywhere
 * add a patch from jwcart2 that adds optimization support to
   checkpolicy as well
 * add two RFC modifications (see log messages for details):
   * one improves the optimization to detect also rules covered by the
     union of two or more other rules (on permission set level)
   * the other one drops libsemanage/semodule run-time enabling/
     disabling of optimization in favor of a global config option
v1: https://lore.kernel.org/selinux/20190523102449.9621-1-omosnace@redhat.com/T/

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 the type attribute hierarchy.

Since the optimization might not always be useful (e.g. when care is
taken to not have redundant rules or when the attributes are
aggressively expanded) and might even drastically increase policy build
times under some cicumstances (for example with the DSSP standard policy
[1]), the optimization is applied only when requested explictly.

The optimization routine eliminates:
 * all allow/dontaudit/auditallow(/neverallow) rules (including xperm
   variants) that are covered by another more general rule (or by a
   union of other rules),
 * 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.

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

Tested:
 * live on my Fedora 29 devel machine under normal use (no unusual AVCs
   observed with the optimized policy loaded)
 * using: https://gitlab.com/omos/selinux-misc/blob/master/opt_test.sh
   * tests also xperm rules
   * doesn't test conditionals

[1] https://github.com/DefenSec/dssp2-standard

James Carter (1):
  checkpolicy: add flag to enable policy optimization

Ondrej Mosnacek (3):
  libsepol: add a function to optimize kernel policy
  libsemanage: optionally optimize policy on rebuild
  secilc: add flag to enable policy optimization

 checkpolicy/checkpolicy.8                  |   3 +
 checkpolicy/checkpolicy.c                  |  16 +-
 libsemanage/man/man5/semanage.conf.5       |   5 +
 libsemanage/src/conf-parse.y               |  15 +-
 libsemanage/src/conf-scan.l                |   1 +
 libsemanage/src/direct_api.c               |   7 +
 libsemanage/src/semanage_conf.h            |   1 +
 libsepol/include/sepol/policydb.h          |   5 +
 libsepol/include/sepol/policydb/policydb.h |   2 +
 libsepol/src/libsepol.map.in               |   5 +
 libsepol/src/optimize.c                    | 378 +++++++++++++++++++++
 libsepol/src/policydb_public.c             |   5 +
 secilc/secilc.8.xml                        |   5 +
 secilc/secilc.c                            |  16 +-
 14 files changed, 460 insertions(+), 4 deletions(-)
 create mode 100644 libsepol/src/optimize.c

-- 
2.20.1

[PATCH userspace v4 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
    real    0m21,280s
    user    0m18,636s
    sys     0m2,525s

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

    $ seinfo (edited)
      Allow:            113159
      Dontaudit:         10297
      Total:            123156

WITH OPTIMIZATION ENABLED:
    # time semodule -B
    real    0m22,825s
    user    0m20,178s
    sys     0m2,520s

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

    $ seinfo (edited)
      Allow:             66334
      Dontaudit:          7480
      Total:             73814

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                    | 378 +++++++++++++++++++++
 libsepol/src/policydb_public.c             |   5 +
 5 files changed, 395 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..3780b68b
--- /dev/null
+++ b/libsepol/src/optimize.c
@@ -0,0 +1,378 @@
+/*
+ * 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[k]);
+	free(map);
+	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 process_xperms(uint32_t *p1, const uint32_t *p2)
+{
+	size_t i;
+	int ret = 1;
+
+	for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
+		p1[i] &= ~p2[i];
+		if (p1[i] != 0)
+			ret = 0;
+	}
+	return ret;
+}
+
+static int process_avtab_datum(uint16_t specified,
+			       avtab_datum_t *d1, const avtab_datum_t *d2)
+{
+	/* inverse logic needed for AUDITDENY rules */
+	if (specified & AVTAB_AUDITDENY)
+		return (d1->data |= ~d2->data) == UINT32_C(0xFFFFFFFF);
+
+	if (specified & AVTAB_AV)
+		return (d1->data &= ~d2->data) == 0;
+
+	if (specified & AVTAB_XPERMS) {
+		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 process_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 process_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 (process_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 (process_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);
+			free(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 v4 2/4] libsemanage: optionally optimize policy on rebuild

[Ondrej Mosnacek]

When building binary policy, optionally run it through
sepol_policydb_optimize() just before writing it out.

Add an optimize-policy variable to semanage.conf(5) that controls
whether optimization will be applied during libsemanage operations.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 libsemanage/man/man5/semanage.conf.5 |  5 +++++
 libsemanage/src/conf-parse.y         | 15 ++++++++++++++-
 libsemanage/src/conf-scan.l          |  1 +
 libsemanage/src/direct_api.c         |  7 +++++++
 libsemanage/src/semanage_conf.h      |  1 +
 5 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/libsemanage/man/man5/semanage.conf.5 b/libsemanage/man/man5/semanage.conf.5
index 8f8de55a..8efc7dd5 100644
--- a/libsemanage/man/man5/semanage.conf.5
+++ b/libsemanage/man/man5/semanage.conf.5
@@ -121,6 +121,11 @@ and by default it is set to "false".
 Please note that since this option deletes all HLL files, an updated HLL compiler will not be able to recompile the original HLL file into CIL.
 In order to compile the original HLL file into CIL, the same HLL file will need to be reinstalled.
 
+.TP
+.B optimize-policy
+When set to "true", the kernel policy will be optimized upon rebuilds.
+It can be set to either "true" or "false" and by default it is set to "false".
+
 .SH "SEE ALSO"
 .TP
 semanage(8)
diff --git a/libsemanage/src/conf-parse.y b/libsemanage/src/conf-parse.y
index b527e893..9bf9364a 100644
--- a/libsemanage/src/conf-parse.y
+++ b/libsemanage/src/conf-parse.y
@@ -59,7 +59,7 @@ static int parse_errors;
         char *s;
 }
 
-%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT
+%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT OPTIMIZE_POLICY
 %token LOAD_POLICY_START SETFILES_START SEFCONTEXT_COMPILE_START DISABLE_GENHOMEDIRCON HANDLE_UNKNOWN USEPASSWD IGNOREDIRS
 %token BZIP_BLOCKSIZE BZIP_SMALL REMOVE_HLL
 %token VERIFY_MOD_START VERIFY_LINKED_START VERIFY_KERNEL_START BLOCK_END
@@ -95,6 +95,7 @@ single_opt:     module_store
 	|	bzip_blocksize
 	|	bzip_small
 	|	remove_hll
+	|	optimize_policy
         ;
 
 module_store:   MODULE_STORE '=' ARG {
@@ -268,6 +269,17 @@ remove_hll:  REMOVE_HLL'=' ARG {
 	free($3);
 }
 
+optimize_policy:  OPTIMIZE_POLICY '=' ARG {
+	if (strcasecmp($3, "false") == 0) {
+		current_conf->optimize_policy = 0;
+	} else if (strcasecmp($3, "true") == 0) {
+		current_conf->optimize_policy = 1;
+	} else {
+		yyerror("optimize-policy can only be 'true' or 'false'");
+	}
+	free($3);
+}
+
 command_block: 
                 command_start external_opts BLOCK_END  {
                         if (new_external->path == NULL) {
@@ -352,6 +364,7 @@ static int semanage_conf_init(semanage_conf_t * conf)
 	conf->bzip_small = 0;
 	conf->ignore_module_cache = 0;
 	conf->remove_hll = 0;
+	conf->optimize_policy = 0;
 
 	conf->save_previous = 0;
 	conf->save_linked = 0;
diff --git a/libsemanage/src/conf-scan.l b/libsemanage/src/conf-scan.l
index 607bbf0b..b06a896c 100644
--- a/libsemanage/src/conf-scan.l
+++ b/libsemanage/src/conf-scan.l
@@ -54,6 +54,7 @@ handle-unknown    return HANDLE_UNKNOWN;
 bzip-blocksize	return BZIP_BLOCKSIZE;
 bzip-small	return BZIP_SMALL;
 remove-hll	return REMOVE_HLL;
+optimize-policy return OPTIMIZE_POLICY;
 "[load_policy]"   return LOAD_POLICY_START;
 "[setfiles]"      return SETFILES_START;
 "[sefcontext_compile]"      return SEFCONTEXT_COMPILE_START;
diff --git a/libsemanage/src/direct_api.c b/libsemanage/src/direct_api.c
index c58961be..0153091f 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->conf->optimize_policy) {
+			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/semanage_conf.h b/libsemanage/src/semanage_conf.h
index c99ac8c7..23c4b8b4 100644
--- a/libsemanage/src/semanage_conf.h
+++ b/libsemanage/src/semanage_conf.h
@@ -47,6 +47,7 @@ typedef struct semanage_conf {
 	int bzip_small;
 	int remove_hll;
 	int ignore_module_cache;
+	int optimize_policy;
 	char *ignoredirs;	/* ";" separated of list for genhomedircon to ignore */
 	struct external_prog *load_policy;
 	struct external_prog *setfiles;
-- 
2.20.1

[PATCH userspace v4 3/4] secilc: add flag to enable policy optimization

[Ondrej Mosnacek]

Add a command-line option -O/--optimize to optimize the final policydb
using sepol_policydb_optimize() before writing it out.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 secilc/secilc.8.xml |  5 +++++
 secilc/secilc.c     | 16 +++++++++++++++-
 2 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/secilc/secilc.8.xml b/secilc/secilc.8.xml
index e08a9624..2b734f09 100644
--- a/secilc/secilc.8.xml
+++ b/secilc/secilc.8.xml
@@ -95,6 +95,11 @@
             <listitem><para>Expand type attributes with fewer than <emphasis role="bold">&lt;SIZE></emphasis> members.</para></listitem>
          </varlistentry>
 
+         <varlistentry>
+            <term><option>-O, --optimize</option></term>
+            <listitem><para>Optimize final policy (remove redundant rules).</para></listitem>
+         </varlistentry>
+
          <varlistentry>
             <term><option>-v, --verbose</option></term>
             <listitem><para>Increment verbosity level.</para></listitem>
diff --git a/secilc/secilc.c b/secilc/secilc.c
index ad6862ba..186c5a73 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("  -O, --optimize                 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 = 0;
 	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'},
+		{"optimize", no_argument, 0, 'O'},
 		{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:PDmNOc:GX:n", long_opts, &opt_index);
 		if (opt_char == -1) {
 			break;
 		}
@@ -211,6 +214,9 @@ int main(int argc, char *argv[])
 				}
 				break;
 			}
+			case 'O':
+				optimize = 1;
+				break;
 			case 'h':
 				usage(argv[0]);
 			case '?':
@@ -294,6 +300,14 @@ int main(int argc, char *argv[])
 		goto exit;
 	}
 
+	if (optimize) {
+		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 v4 4/4] checkpolicy: add flag to enable policy optimization

[Ondrej Mosnacek]

From: James Carter <jwcart2@tycho.nsa.gov>

Add the command-line option 'O' to checkpolicy to cause kernel policies
to be optimized by calling policydb_optimize() before being written out.

This option can be used on conf files and binary kernel policies, but
not when converting a conf file to CIL.

Signed-off-by: James Carter <jwcart2@tycho.nsa.gov>
[omosnace: make commit desc more consistent with the other patches]
[omosnace: fix a typo in the commit message]
[omosnace: directly use policydb_optimize() as also the rest of code already uses
 other policydb_*() functions...]
[omosnace: update man page]
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 checkpolicy/checkpolicy.8 |  3 +++
 checkpolicy/checkpolicy.c | 16 ++++++++++++++--
 2 files changed, 17 insertions(+), 2 deletions(-)

diff --git a/checkpolicy/checkpolicy.8 b/checkpolicy/checkpolicy.8
index 8f7dad41..1552f497 100644
--- a/checkpolicy/checkpolicy.8
+++ b/checkpolicy/checkpolicy.8
@@ -48,6 +48,9 @@ Sort ocontexts before writing out the binary policy. This option makes output of
 .B \-t,\-\-target
 Specify the target platform (selinux or xen).
 .TP
+.B \-O,\-\-optimize
+Optimize the final kernel policy (remove redundant rules).
+.TP
 .B \-V,\-\-version
 Show version information.
 .TP
diff --git a/checkpolicy/checkpolicy.c b/checkpolicy/checkpolicy.c
index e0a00f7c..f928ec06 100644
--- a/checkpolicy/checkpolicy.c
+++ b/checkpolicy/checkpolicy.c
@@ -394,7 +394,7 @@ int main(int argc, char **argv)
 	size_t scontext_len, pathlen;
 	unsigned int i;
 	unsigned int protocol, port;
-	unsigned int binary = 0, debug = 0, sort = 0, cil = 0, conf = 0;
+	unsigned int binary = 0, debug = 0, sort = 0, cil = 0, conf = 0, optimize = 0;
 	struct val_to_name v;
 	int ret, ch, fd, target = SEPOL_TARGET_SELINUX;
 	unsigned int nel, uret;
@@ -419,11 +419,12 @@ int main(int argc, char **argv)
 		{"cil", no_argument, NULL, 'C'},
 		{"conf",no_argument, NULL, 'F'},
 		{"sort", no_argument, NULL, 'S'},
+		{"optimize", no_argument, NULL, 'O'},
 		{"help", no_argument, NULL, 'h'},
 		{NULL, 0, NULL, 0}
 	};
 
-	while ((ch = getopt_long(argc, argv, "o:t:dbU:MCFSVc:h", long_options, NULL)) != -1) {
+	while ((ch = getopt_long(argc, argv, "o:t:dbU:MCFSVc:Oh", long_options, NULL)) != -1) {
 		switch (ch) {
 		case 'o':
 			outfile = optarg;
@@ -466,6 +467,9 @@ int main(int argc, char **argv)
 		case 'S':
 			sort = 1;
 			break;
+		case 'O':
+			optimize = 1;
+			break;
 		case 'M':
 			mlspol = 1;
 			break;
@@ -625,6 +629,14 @@ int main(int argc, char **argv)
 	if (policydb_load_isids(&policydb, &sidtab))
 		exit(1);
 
+	if (optimize && policydbp->policy_type == POLICY_KERN) {
+		ret = policydb_optimize(policydbp);
+		if (ret) {
+			fprintf(stderr, "%s:  error optimizing policy\n", argv[0]);
+			exit(1);
+		}
+	}
+
 	if (outfile) {
 		outfp = fopen(outfile, "w");
 		if (!outfp) {
-- 
2.20.1

Re: [Non-DoD Source] [PATCH userspace v4 2/4] libsemanage: optionally optimize policy on rebuild

[jwcart2]

On 6/13/19 7:45 AM, Ondrej Mosnacek wrote:
> When building binary policy, optionally run it through
> sepol_policydb_optimize() just before writing it out.
> 
> Add an optimize-policy variable to semanage.conf(5) that controls

Sorry I didn't notice this in v3, but why not use "optimize" instead of 
"optimize-policy"?

Jim

> whether optimization will be applied during libsemanage operations.
> 
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
>   libsemanage/man/man5/semanage.conf.5 |  5 +++++
>   libsemanage/src/conf-parse.y         | 15 ++++++++++++++-
>   libsemanage/src/conf-scan.l          |  1 +
>   libsemanage/src/direct_api.c         |  7 +++++++
>   libsemanage/src/semanage_conf.h      |  1 +
>   5 files changed, 28 insertions(+), 1 deletion(-)
> 
> diff --git a/libsemanage/man/man5/semanage.conf.5 b/libsemanage/man/man5/semanage.conf.5
> index 8f8de55a..8efc7dd5 100644
> --- a/libsemanage/man/man5/semanage.conf.5
> +++ b/libsemanage/man/man5/semanage.conf.5
> @@ -121,6 +121,11 @@ and by default it is set to "false".
>   Please note that since this option deletes all HLL files, an updated HLL compiler will not be able to recompile the original HLL file into CIL.
>   In order to compile the original HLL file into CIL, the same HLL file will need to be reinstalled.
>   
> +.TP
> +.B optimize-policy
> +When set to "true", the kernel policy will be optimized upon rebuilds.
> +It can be set to either "true" or "false" and by default it is set to "false".
> +
>   .SH "SEE ALSO"
>   .TP
>   semanage(8)
> diff --git a/libsemanage/src/conf-parse.y b/libsemanage/src/conf-parse.y
> index b527e893..9bf9364a 100644
> --- a/libsemanage/src/conf-parse.y
> +++ b/libsemanage/src/conf-parse.y
> @@ -59,7 +59,7 @@ static int parse_errors;
>           char *s;
>   }
>   
> -%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT
> +%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT OPTIMIZE_POLICY
>   %token LOAD_POLICY_START SETFILES_START SEFCONTEXT_COMPILE_START DISABLE_GENHOMEDIRCON HANDLE_UNKNOWN USEPASSWD IGNOREDIRS
>   %token BZIP_BLOCKSIZE BZIP_SMALL REMOVE_HLL
>   %token VERIFY_MOD_START VERIFY_LINKED_START VERIFY_KERNEL_START BLOCK_END
> @@ -95,6 +95,7 @@ single_opt:     module_store
>   	|	bzip_blocksize
>   	|	bzip_small
>   	|	remove_hll
> +	|	optimize_policy
>           ;
>   
>   module_store:   MODULE_STORE '=' ARG {
> @@ -268,6 +269,17 @@ remove_hll:  REMOVE_HLL'=' ARG {
>   	free($3);
>   }
>   
> +optimize_policy:  OPTIMIZE_POLICY '=' ARG {
> +	if (strcasecmp($3, "false") == 0) {
> +		current_conf->optimize_policy = 0;
> +	} else if (strcasecmp($3, "true") == 0) {
> +		current_conf->optimize_policy = 1;
> +	} else {
> +		yyerror("optimize-policy can only be 'true' or 'false'");
> +	}
> +	free($3);
> +}
> +
>   command_block:
>                   command_start external_opts BLOCK_END  {
>                           if (new_external->path == NULL) {
> @@ -352,6 +364,7 @@ static int semanage_conf_init(semanage_conf_t * conf)
>   	conf->bzip_small = 0;
>   	conf->ignore_module_cache = 0;
>   	conf->remove_hll = 0;
> +	conf->optimize_policy = 0;
>   
>   	conf->save_previous = 0;
>   	conf->save_linked = 0;
> diff --git a/libsemanage/src/conf-scan.l b/libsemanage/src/conf-scan.l
> index 607bbf0b..b06a896c 100644
> --- a/libsemanage/src/conf-scan.l
> +++ b/libsemanage/src/conf-scan.l
> @@ -54,6 +54,7 @@ handle-unknown    return HANDLE_UNKNOWN;
>   bzip-blocksize	return BZIP_BLOCKSIZE;
>   bzip-small	return BZIP_SMALL;
>   remove-hll	return REMOVE_HLL;
> +optimize-policy return OPTIMIZE_POLICY;
>   "[load_policy]"   return LOAD_POLICY_START;
>   "[setfiles]"      return SETFILES_START;
>   "[sefcontext_compile]"      return SEFCONTEXT_COMPILE_START;
> diff --git a/libsemanage/src/direct_api.c b/libsemanage/src/direct_api.c
> index c58961be..0153091f 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->conf->optimize_policy) {
> +			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/semanage_conf.h b/libsemanage/src/semanage_conf.h
> index c99ac8c7..23c4b8b4 100644
> --- a/libsemanage/src/semanage_conf.h
> +++ b/libsemanage/src/semanage_conf.h
> @@ -47,6 +47,7 @@ typedef struct semanage_conf {
>   	int bzip_small;
>   	int remove_hll;
>   	int ignore_module_cache;
> +	int optimize_policy;
>   	char *ignoredirs;	/* ";" separated of list for genhomedircon to ignore */
>   	struct external_prog *load_policy;
>   	struct external_prog *setfiles;
> 


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

Re: [Non-DoD Source] [PATCH userspace v4 2/4] libsemanage: optionally optimize policy on rebuild

[Ondrej Mosnacek]

On Thu, Jun 13, 2019 at 9:51 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 6/13/19 7:45 AM, Ondrej Mosnacek wrote:
> > When building binary policy, optionally run it through
> > sepol_policydb_optimize() just before writing it out.
> >
> > Add an optimize-policy variable to semanage.conf(5) that controls
>
> Sorry I didn't notice this in v3, but why not use "optimize" instead of
> "optimize-policy"?

Since this is in a global libsemanage config file, I thought it would
be better if the name described also what is being optimized. In
secilc or checkpolicy it is more or less obvious; in the config file
it can't hurt to be more specific, IMHO.

>
> Jim
>
> > whether optimization will be applied during libsemanage operations.
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> > ---
> >   libsemanage/man/man5/semanage.conf.5 |  5 +++++
> >   libsemanage/src/conf-parse.y         | 15 ++++++++++++++-
> >   libsemanage/src/conf-scan.l          |  1 +
> >   libsemanage/src/direct_api.c         |  7 +++++++
> >   libsemanage/src/semanage_conf.h      |  1 +
> >   5 files changed, 28 insertions(+), 1 deletion(-)
> >
> > diff --git a/libsemanage/man/man5/semanage.conf.5 b/libsemanage/man/man5/semanage.conf.5
> > index 8f8de55a..8efc7dd5 100644
> > --- a/libsemanage/man/man5/semanage.conf.5
> > +++ b/libsemanage/man/man5/semanage.conf.5
> > @@ -121,6 +121,11 @@ and by default it is set to "false".
> >   Please note that since this option deletes all HLL files, an updated HLL compiler will not be able to recompile the original HLL file into CIL.
> >   In order to compile the original HLL file into CIL, the same HLL file will need to be reinstalled.
> >
> > +.TP
> > +.B optimize-policy
> > +When set to "true", the kernel policy will be optimized upon rebuilds.
> > +It can be set to either "true" or "false" and by default it is set to "false".
> > +
> >   .SH "SEE ALSO"
> >   .TP
> >   semanage(8)
> > diff --git a/libsemanage/src/conf-parse.y b/libsemanage/src/conf-parse.y
> > index b527e893..9bf9364a 100644
> > --- a/libsemanage/src/conf-parse.y
> > +++ b/libsemanage/src/conf-parse.y
> > @@ -59,7 +59,7 @@ static int parse_errors;
> >           char *s;
> >   }
> >
> > -%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT
> > +%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT OPTIMIZE_POLICY
> >   %token LOAD_POLICY_START SETFILES_START SEFCONTEXT_COMPILE_START DISABLE_GENHOMEDIRCON HANDLE_UNKNOWN USEPASSWD IGNOREDIRS
> >   %token BZIP_BLOCKSIZE BZIP_SMALL REMOVE_HLL
> >   %token VERIFY_MOD_START VERIFY_LINKED_START VERIFY_KERNEL_START BLOCK_END
> > @@ -95,6 +95,7 @@ single_opt:     module_store
> >       |       bzip_blocksize
> >       |       bzip_small
> >       |       remove_hll
> > +     |       optimize_policy
> >           ;
> >
> >   module_store:   MODULE_STORE '=' ARG {
> > @@ -268,6 +269,17 @@ remove_hll:  REMOVE_HLL'=' ARG {
> >       free($3);
> >   }
> >
> > +optimize_policy:  OPTIMIZE_POLICY '=' ARG {
> > +     if (strcasecmp($3, "false") == 0) {
> > +             current_conf->optimize_policy = 0;
> > +     } else if (strcasecmp($3, "true") == 0) {
> > +             current_conf->optimize_policy = 1;
> > +     } else {
> > +             yyerror("optimize-policy can only be 'true' or 'false'");
> > +     }
> > +     free($3);
> > +}
> > +
> >   command_block:
> >                   command_start external_opts BLOCK_END  {
> >                           if (new_external->path == NULL) {
> > @@ -352,6 +364,7 @@ static int semanage_conf_init(semanage_conf_t * conf)
> >       conf->bzip_small = 0;
> >       conf->ignore_module_cache = 0;
> >       conf->remove_hll = 0;
> > +     conf->optimize_policy = 0;
> >
> >       conf->save_previous = 0;
> >       conf->save_linked = 0;
> > diff --git a/libsemanage/src/conf-scan.l b/libsemanage/src/conf-scan.l
> > index 607bbf0b..b06a896c 100644
> > --- a/libsemanage/src/conf-scan.l
> > +++ b/libsemanage/src/conf-scan.l
> > @@ -54,6 +54,7 @@ handle-unknown    return HANDLE_UNKNOWN;
> >   bzip-blocksize      return BZIP_BLOCKSIZE;
> >   bzip-small  return BZIP_SMALL;
> >   remove-hll  return REMOVE_HLL;
> > +optimize-policy return OPTIMIZE_POLICY;
> >   "[load_policy]"   return LOAD_POLICY_START;
> >   "[setfiles]"      return SETFILES_START;
> >   "[sefcontext_compile]"      return SEFCONTEXT_COMPILE_START;
> > diff --git a/libsemanage/src/direct_api.c b/libsemanage/src/direct_api.c
> > index c58961be..0153091f 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->conf->optimize_policy) {
> > +                     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/semanage_conf.h b/libsemanage/src/semanage_conf.h
> > index c99ac8c7..23c4b8b4 100644
> > --- a/libsemanage/src/semanage_conf.h
> > +++ b/libsemanage/src/semanage_conf.h
> > @@ -47,6 +47,7 @@ typedef struct semanage_conf {
> >       int bzip_small;
> >       int remove_hll;
> >       int ignore_module_cache;
> > +     int optimize_policy;
> >       char *ignoredirs;       /* ";" separated of list for genhomedircon to ignore */
> >       struct external_prog *load_policy;
> >       struct external_prog *setfiles;
> >
>
>
> --
> 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 v4 2/4] libsemanage: optionally optimize policy on rebuild

[jwcart2]

On 6/14/19 6:18 AM, Ondrej Mosnacek wrote:
> On Thu, Jun 13, 2019 at 9:51 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
>> On 6/13/19 7:45 AM, Ondrej Mosnacek wrote:
>>> When building binary policy, optionally run it through
>>> sepol_policydb_optimize() just before writing it out.
>>>
>>> Add an optimize-policy variable to semanage.conf(5) that controls
>>
>> Sorry I didn't notice this in v3, but why not use "optimize" instead of
>> "optimize-policy"?
> 
> Since this is in a global libsemanage config file, I thought it would
> be better if the name described also what is being optimized. In
> secilc or checkpolicy it is more or less obvious; in the config file
> it can't hurt to be more specific, IMHO.
> 

Ok. I just wanted to make sure we had thought about it.

Jim

>>
>> Jim
>>
>>> whether optimization will be applied during libsemanage operations.
>>>
>>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>>> ---
>>>    libsemanage/man/man5/semanage.conf.5 |  5 +++++
>>>    libsemanage/src/conf-parse.y         | 15 ++++++++++++++-
>>>    libsemanage/src/conf-scan.l          |  1 +
>>>    libsemanage/src/direct_api.c         |  7 +++++++
>>>    libsemanage/src/semanage_conf.h      |  1 +
>>>    5 files changed, 28 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/libsemanage/man/man5/semanage.conf.5 b/libsemanage/man/man5/semanage.conf.5
>>> index 8f8de55a..8efc7dd5 100644
>>> --- a/libsemanage/man/man5/semanage.conf.5
>>> +++ b/libsemanage/man/man5/semanage.conf.5
>>> @@ -121,6 +121,11 @@ and by default it is set to "false".
>>>    Please note that since this option deletes all HLL files, an updated HLL compiler will not be able to recompile the original HLL file into CIL.
>>>    In order to compile the original HLL file into CIL, the same HLL file will need to be reinstalled.
>>>
>>> +.TP
>>> +.B optimize-policy
>>> +When set to "true", the kernel policy will be optimized upon rebuilds.
>>> +It can be set to either "true" or "false" and by default it is set to "false".
>>> +
>>>    .SH "SEE ALSO"
>>>    .TP
>>>    semanage(8)
>>> diff --git a/libsemanage/src/conf-parse.y b/libsemanage/src/conf-parse.y
>>> index b527e893..9bf9364a 100644
>>> --- a/libsemanage/src/conf-parse.y
>>> +++ b/libsemanage/src/conf-parse.y
>>> @@ -59,7 +59,7 @@ static int parse_errors;
>>>            char *s;
>>>    }
>>>
>>> -%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT
>>> +%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT OPTIMIZE_POLICY
>>>    %token LOAD_POLICY_START SETFILES_START SEFCONTEXT_COMPILE_START DISABLE_GENHOMEDIRCON HANDLE_UNKNOWN USEPASSWD IGNOREDIRS
>>>    %token BZIP_BLOCKSIZE BZIP_SMALL REMOVE_HLL
>>>    %token VERIFY_MOD_START VERIFY_LINKED_START VERIFY_KERNEL_START BLOCK_END
>>> @@ -95,6 +95,7 @@ single_opt:     module_store
>>>        |       bzip_blocksize
>>>        |       bzip_small
>>>        |       remove_hll
>>> +     |       optimize_policy
>>>            ;
>>>
>>>    module_store:   MODULE_STORE '=' ARG {
>>> @@ -268,6 +269,17 @@ remove_hll:  REMOVE_HLL'=' ARG {
>>>        free($3);
>>>    }
>>>
>>> +optimize_policy:  OPTIMIZE_POLICY '=' ARG {
>>> +     if (strcasecmp($3, "false") == 0) {
>>> +             current_conf->optimize_policy = 0;
>>> +     } else if (strcasecmp($3, "true") == 0) {
>>> +             current_conf->optimize_policy = 1;
>>> +     } else {
>>> +             yyerror("optimize-policy can only be 'true' or 'false'");
>>> +     }
>>> +     free($3);
>>> +}
>>> +
>>>    command_block:
>>>                    command_start external_opts BLOCK_END  {
>>>                            if (new_external->path == NULL) {
>>> @@ -352,6 +364,7 @@ static int semanage_conf_init(semanage_conf_t * conf)
>>>        conf->bzip_small = 0;
>>>        conf->ignore_module_cache = 0;
>>>        conf->remove_hll = 0;
>>> +     conf->optimize_policy = 0;
>>>
>>>        conf->save_previous = 0;
>>>        conf->save_linked = 0;
>>> diff --git a/libsemanage/src/conf-scan.l b/libsemanage/src/conf-scan.l
>>> index 607bbf0b..b06a896c 100644
>>> --- a/libsemanage/src/conf-scan.l
>>> +++ b/libsemanage/src/conf-scan.l
>>> @@ -54,6 +54,7 @@ handle-unknown    return HANDLE_UNKNOWN;
>>>    bzip-blocksize      return BZIP_BLOCKSIZE;
>>>    bzip-small  return BZIP_SMALL;
>>>    remove-hll  return REMOVE_HLL;
>>> +optimize-policy return OPTIMIZE_POLICY;
>>>    "[load_policy]"   return LOAD_POLICY_START;
>>>    "[setfiles]"      return SETFILES_START;
>>>    "[sefcontext_compile]"      return SEFCONTEXT_COMPILE_START;
>>> diff --git a/libsemanage/src/direct_api.c b/libsemanage/src/direct_api.c
>>> index c58961be..0153091f 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->conf->optimize_policy) {
>>> +                     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/semanage_conf.h b/libsemanage/src/semanage_conf.h
>>> index c99ac8c7..23c4b8b4 100644
>>> --- a/libsemanage/src/semanage_conf.h
>>> +++ b/libsemanage/src/semanage_conf.h
>>> @@ -47,6 +47,7 @@ typedef struct semanage_conf {
>>>        int bzip_small;
>>>        int remove_hll;
>>>        int ignore_module_cache;
>>> +     int optimize_policy;
>>>        char *ignoredirs;       /* ";" separated of list for genhomedircon to ignore */
>>>        struct external_prog *load_policy;
>>>        struct external_prog *setfiles;
>>>
>>
>>
>> --
>> 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

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

[jwcart2]

On 6/13/19 7:45 AM, Ondrej Mosnacek wrote:
> Changes in v4:
>   * fix deallocation in error path in build_type_map()
>   * fix leaked cond nodes
>   * also update the man pages
>   * use UINT32_C for 0xFFFFFFFF constant
>   * squash in the RFC patches & drop the semodule patch
> v3: https://lore.kernel.org/selinux/20190529073759.20548-1-omosnace@redhat.com/T/
> 
> Changes in v3:
>   * fix bad patch squashing
>   * rename secilc --optimize-policy option to --optimize (to be simpler
>     and consistent with checkpolicy and semodule)
> v2: https://lore.kernel.org/selinux/20190528145912.13827-1-omosnace@redhat.com/T/
> 
> Changes in v2:
>   * fix handling of dontaudit (AVTAB_DENY) rules
>   * switch optimization from opt-out to opt-in everywhere
>   * add a patch from jwcart2 that adds optimization support to
>     checkpolicy as well
>   * add two RFC modifications (see log messages for details):
>     * one improves the optimization to detect also rules covered by the
>       union of two or more other rules (on permission set level)
>     * the other one drops libsemanage/semodule run-time enabling/
>       disabling of optimization in favor of a global config option
> v1: https://lore.kernel.org/selinux/20190523102449.9621-1-omosnace@redhat.com/T/
> 
> 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 the type attribute hierarchy.
> 
> Since the optimization might not always be useful (e.g. when care is
> taken to not have redundant rules or when the attributes are
> aggressively expanded) and might even drastically increase policy build
> times under some cicumstances (for example with the DSSP standard policy
> [1]), the optimization is applied only when requested explictly.
> 
> The optimization routine eliminates:
>   * all allow/dontaudit/auditallow(/neverallow) rules (including xperm
>     variants) that are covered by another more general rule (or by a
>     union of other rules),
>   * 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.
> 
> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/545184071
> 
> Tested:
>   * live on my Fedora 29 devel machine under normal use (no unusual AVCs
>     observed with the optimized policy loaded)
>   * using: https://gitlab.com/omos/selinux-misc/blob/master/opt_test.sh
>     * tests also xperm rules
>     * doesn't test conditionals
> 
> [1] https://github.com/DefenSec/dssp2-standard
> 
> James Carter (1):
>    checkpolicy: add flag to enable policy optimization
> 
> Ondrej Mosnacek (3):
>    libsepol: add a function to optimize kernel policy
>    libsemanage: optionally optimize policy on rebuild
>    secilc: add flag to enable policy optimization
> 
>   checkpolicy/checkpolicy.8                  |   3 +
>   checkpolicy/checkpolicy.c                  |  16 +-
>   libsemanage/man/man5/semanage.conf.5       |   5 +
>   libsemanage/src/conf-parse.y               |  15 +-
>   libsemanage/src/conf-scan.l                |   1 +
>   libsemanage/src/direct_api.c               |   7 +
>   libsemanage/src/semanage_conf.h            |   1 +
>   libsepol/include/sepol/policydb.h          |   5 +
>   libsepol/include/sepol/policydb/policydb.h |   2 +
>   libsepol/src/libsepol.map.in               |   5 +
>   libsepol/src/optimize.c                    | 378 +++++++++++++++++++++
>   libsepol/src/policydb_public.c             |   5 +
>   secilc/secilc.8.xml                        |   5 +
>   secilc/secilc.c                            |  16 +-
>   14 files changed, 460 insertions(+), 4 deletions(-)
>   create mode 100644 libsepol/src/optimize.c
> 

Acked-by: James Carter <jwcart2@tycho.nsa.gov>

staged: https://github.com/SELinuxProject/selinux/pull/168

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

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

[jwcart2]

On 6/21/19 10:11 AM, jwcart2 wrote:
> On 6/13/19 7:45 AM, Ondrej Mosnacek wrote:
>> Changes in v4:
>>   * fix deallocation in error path in build_type_map()
>>   * fix leaked cond nodes
>>   * also update the man pages
>>   * use UINT32_C for 0xFFFFFFFF constant
>>   * squash in the RFC patches & drop the semodule patch
>> v3: https://lore.kernel.org/selinux/20190529073759.20548-1-omosnace@redhat.com/T/
>>
>> Changes in v3:
>>   * fix bad patch squashing
>>   * rename secilc --optimize-policy option to --optimize (to be simpler
>>     and consistent with checkpolicy and semodule)
>> v2: https://lore.kernel.org/selinux/20190528145912.13827-1-omosnace@redhat.com/T/
>>
>> Changes in v2:
>>   * fix handling of dontaudit (AVTAB_DENY) rules
>>   * switch optimization from opt-out to opt-in everywhere
>>   * add a patch from jwcart2 that adds optimization support to
>>     checkpolicy as well
>>   * add two RFC modifications (see log messages for details):
>>     * one improves the optimization to detect also rules covered by the
>>       union of two or more other rules (on permission set level)
>>     * the other one drops libsemanage/semodule run-time enabling/
>>       disabling of optimization in favor of a global config option
>> v1: https://lore.kernel.org/selinux/20190523102449.9621-1-omosnace@redhat.com/T/
>>
>> 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 the type attribute hierarchy.
>>
>> Since the optimization might not always be useful (e.g. when care is
>> taken to not have redundant rules or when the attributes are
>> aggressively expanded) and might even drastically increase policy build
>> times under some cicumstances (for example with the DSSP standard policy
>> [1]), the optimization is applied only when requested explictly.
>>
>> The optimization routine eliminates:
>>   * all allow/dontaudit/auditallow(/neverallow) rules (including xperm
>>     variants) that are covered by another more general rule (or by a
>>     union of other rules),
>>   * 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.
>>
>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/545184071
>>
>> Tested:
>>   * live on my Fedora 29 devel machine under normal use (no unusual AVCs
>>     observed with the optimized policy loaded)
>>   * using: https://gitlab.com/omos/selinux-misc/blob/master/opt_test.sh
>>     * tests also xperm rules
>>     * doesn't test conditionals
>>
>> [1] https://github.com/DefenSec/dssp2-standard
>>
>> James Carter (1):
>>    checkpolicy: add flag to enable policy optimization
>>
>> Ondrej Mosnacek (3):
>>    libsepol: add a function to optimize kernel policy
>>    libsemanage: optionally optimize policy on rebuild
>>    secilc: add flag to enable policy optimization
>>
>>   checkpolicy/checkpolicy.8                  |   3 +
>>   checkpolicy/checkpolicy.c                  |  16 +-
>>   libsemanage/man/man5/semanage.conf.5       |   5 +
>>   libsemanage/src/conf-parse.y               |  15 +-
>>   libsemanage/src/conf-scan.l                |   1 +
>>   libsemanage/src/direct_api.c               |   7 +
>>   libsemanage/src/semanage_conf.h            |   1 +
>>   libsepol/include/sepol/policydb.h          |   5 +
>>   libsepol/include/sepol/policydb/policydb.h |   2 +
>>   libsepol/src/libsepol.map.in               |   5 +
>>   libsepol/src/optimize.c                    | 378 +++++++++++++++++++++
>>   libsepol/src/policydb_public.c             |   5 +
>>   secilc/secilc.8.xml                        |   5 +
>>   secilc/secilc.c                            |  16 +-
>>   14 files changed, 460 insertions(+), 4 deletions(-)
>>   create mode 100644 libsepol/src/optimize.c
>>
> 
> Acked-by: James Carter <jwcart2@tycho.nsa.gov>
> 
> staged: https://github.com/SELinuxProject/selinux/pull/168
> 
Merged.


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