| Message ID | 20190926171934.9786-1-jwcart2@tycho.nsa.gov (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | libsepol: Further improve binary policy optimization | expand |
On Thu, Sep 26, 2019 at 7:19 PM James Carter <jwcart2@tycho.nsa.gov> wrote: > 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> Nice improvement, thanks! Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > 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 > -- Ondrej Mosnacek <omosnace at redhat dot com> Software Engineer, Security Technologies Red Hat, Inc.
On 9/27/19 5:23 AM, Ondrej Mosnacek wrote: > On Thu, Sep 26, 2019 at 7:19 PM James Carter <jwcart2@tycho.nsa.gov> wrote: >> 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> > > Nice improvement, thanks! > > Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com> > Thanks for the review. This is now merged. Jim >> --- >> 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 >> > > -- > Ondrej Mosnacek <omosnace at redhat dot com> > Software Engineer, Security Technologies > Red Hat, Inc. >
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;
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(-)