SELinux Archive on lore.kernel.org
 help / color / Atom feed
* [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	[flat|nested] 3+ messages in thread

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

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.


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

* Re: [Non-DoD Source] Re: [PATCH] libsepol: Further improve binary policy optimization
  2019-09-27  9:23 ` Ondrej Mosnacek
@ 2019-09-30 19:19   ` " jwcart2
  0 siblings, 0 replies; 3+ messages in thread
From: jwcart2 @ 2019-09-30 19:19 UTC (permalink / raw)
  To: Ondrej Mosnacek; +Cc: SElinux list

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.
> 


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

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

end of thread, back to index

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-09-26 17:19 [PATCH] libsepol: Further improve binary policy optimization James Carter
2019-09-27  9:23 ` Ondrej Mosnacek
2019-09-30 19:19   ` [Non-DoD Source] " jwcart2

SELinux Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/selinux/0 selinux/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 selinux selinux/ https://lore.kernel.org/selinux \
		selinux@vger.kernel.org selinux@archiver.kernel.org
	public-inbox-index selinux

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.selinux


AGPL code for this site: git clone https://public-inbox.org/ public-inbox