[PATCH] libsepol: Further improve binary policy optimization

* [PATCH] libsepol: Further improve binary policy optimization
@ 2019-09-26 17:19 James Carter
  2019-09-27  9:23 ` Ondrej Mosnacek
  0 siblings, 1 reply; 3+ messages in thread
From: James Carter @ 2019-09-26 17:19 UTC (permalink / raw)
  To: selinux

This improves commit b8213acf (libsepol: add a function to optimize
kernel policy) by Ondrej Mosnacek <omosnace@redhat.com> by always
removing redundant conditional rules which have an identical rule
in the unconditional policy.

Add a flag called not_cond to is_avrule_redundant(). When checking
unconditional rules against the avtab (which stores the unconditional
rules) we need to skip the actual rule that we are checking (otherwise
a rule would be determined to be redundant with itself and bad things
would happen), but when checking a conditional rule against the avtab
we do not want to skip an identical rule (which is what currently
happens), we want to remove the redundant permissions in the conditional
rule.

A couple of examples to illustrate when redundant condtional rules
are not removed.

Example 1
  allow t1 t2:class1 perm1;
  if (bool1) {
    allow t1 t2:class1 perm1;
  }
The conditional rule is clearly redundant, but without this change it
will not be removed, because of the check for an identical rule.

Example 2
  typeattribute t1 a1;
  allow t1 t2:class1 perm1;
  allow a1 t2:class1 perm1;
  if (bool1) {
    allow t1 t2:class1 perm1;
  }
The conditional rule is again clearly redundant, but now the order of
processing during the optimization will determine whether or not the
rule is removed. Because a1 contains only t1, a1 and t1 are considered
to be supersets of each other. If the rule with the attribute is
processed first, then it will be determined to be redundant and
removed, so the conditional rule will not be removed. But if the rule
with the type is processed first, then it will be removed and the
conditional rule will be determined to be redundant with the rule with
the attribute and removed as well.

The change reduces the size of policy a bit more than the original
optimization. Looking at the change in number of allow rules, there is
about a 10% improvement over the old optimization.
           orig    old    new
Refpolicy 113284  82467  78053
Fedora    106410  64015  60008

Signed-off-by: James Carter <jwcart2@tycho.nsa.gov>
---
 libsepol/src/optimize.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
index 10399a43..1e5e97e8 100644
--- a/libsepol/src/optimize.c
+++ b/libsepol/src/optimize.c
@@ -123,7 +123,7 @@ static int process_avtab_datum(uint16_t specified,
 
 /* 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)
+			       const ebitmap_t *type_map, unsigned char not_cond)
 {
 	unsigned int i, k, s_idx, t_idx;
 	ebitmap_node_t *snode, *tnode;
@@ -146,7 +146,7 @@ static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
 		key.source_type = i + 1;
 
 		ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
-			if (s_idx == i && t_idx == k)
+			if (not_cond && s_idx == i && t_idx == k)
 				continue;
 
 			key.target_type = k + 1;
@@ -223,7 +223,7 @@ static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
 	for (i = 0; i < tab->nslot; i++) {
 		cur = &tab->htable[i];
 		while (*cur) {
-			if (is_avrule_redundant(*cur, tab, type_map)) {
+			if (is_avrule_redundant(*cur, tab, type_map, 1)) {
 				/* redundant rule -> remove it */
 				avtab_ptr_t tmp = *cur;
 
@@ -279,7 +279,7 @@ static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
 		 * 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) ||
+		if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map, 0) ||
 		    is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
 			cond_av_list_t *tmp = *cond;
 
-- 
2.21.0


^ permalink raw reply related	[flat|nested] 3+ messages in thread