[PATCH 1/4] libsepol/cil: Allow lists in constraint expressions

[PATCH 1/4] libsepol/cil: Allow lists in constraint expressions

[James Carter]

The expectation in CIL was to use user, role, or type attributes in
constraint expressions. The problem is that neither user nor role
attributes are part of the kernel binary policy, so when converting
from a kernel policy to CIL, that would require the creation of a
role or user attribute. The better solution is to just allow a list
to be used. In fact, the only thing preventing a list to be used
is a check in cil_verify_constraint_leaf_expr_syntax().

Remove the check and allow lists in constraint expressions.

The following is now allowed:
  (constrain (CLASS1 (PERM1)) (eq r1 (ROLE1 ROLE2 ROLE_ATTR3)))

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_verify.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c
index 6706e219..09e3daf9 100644
--- a/libsepol/cil/src/cil_verify.c
+++ b/libsepol/cil/src/cil_verify.c
@@ -225,9 +225,6 @@ int cil_verify_constraint_leaf_expr_syntax(enum cil_flavor l_flavor, enum cil_fl
 				cil_log(CIL_ERR, "u3, r3, and t3 can only be used with (mls)validatetrans rules\n");
 				goto exit;
 			}
-		} else if (r_flavor == CIL_LIST) {
-			cil_log(CIL_ERR, "t1, t2, r1, r2, u1, u2 cannot be used on the left side with a list on the right side\n");
-			goto exit;
 		}
 	} else {
 		if (r_flavor == CIL_CONS_U2) {
-- 
2.26.2

[PATCH 2/4] secilc/docs: Lists are now allowed in constraint expressions

[James Carter]

Update the CIL documentation to show that lists are allowed in
constraint expressions.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 secilc/docs/cil_constraint_statements.md | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/secilc/docs/cil_constraint_statements.md b/secilc/docs/cil_constraint_statements.md
index 2dd6e6f0..358927d6 100644
--- a/secilc/docs/cil_constraint_statements.md
+++ b/secilc/docs/cil_constraint_statements.md
@@ -34,12 +34,12 @@ Enable constraints to be placed on the specified permissions of the object class
 <p><code>    (op u1 u2)</code></p>
 <p><code>    (role_op r1 r2)</code></p>
 <p><code>    (op t1 t2)</code></p>
-<p><code>    (op u1 user_id)</code></p>
-<p><code>    (op u2 user_id)</code></p>
-<p><code>    (op r1 role_id)</code></p>
-<p><code>    (op r2 role_id)</code></p>
-<p><code>    (op t1 type_id)</code></p>
-<p><code>    (op t2 type_id)</code></p>
+<p><code>    (op u1 user_id | (user_id ...))</code></p>
+<p><code>    (op u2 user_id | (user_id ...))</code></p>
+<p><code>    (op r1 role_id | (role_id ...))</code></p>
+<p><code>    (op r2 role_id | (role_id ...))</code></p>
+<p><code>    (op t1 type_id | (type_id ...))</code></p>
+<p><code>    (op t2 type_id | (type_id ...))</code></p>
 <p>where:</p>
 <p><code>  u1, r1, t1 = Source context: user, role or type</code></p>
 <p><code>  u2, r2, t2 = Target context: user, role or type</code></p>
-- 
2.26.2

[PATCH 3/4] libsepol: Enclose identifier lists in CIL constraint expressions

[James Carter]

When writing CIL policy from a kernel policy or module, if there are
multiple users, roles, or types, then the list needs to be enclosed
by "(" and ")".

When writing a constraint expression, check to see if there are
multiple identifiers in the names string and enclose the list with
"(" and ")" if there are.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/src/kernel_to_cil.c | 6 +++++-
 libsepol/src/module_to_cil.c | 9 ++++++++-
 2 files changed, 13 insertions(+), 2 deletions(-)

diff --git a/libsepol/src/kernel_to_cil.c b/libsepol/src/kernel_to_cil.c
index a146ac51..96e0f5d3 100644
--- a/libsepol/src/kernel_to_cil.c
+++ b/libsepol/src/kernel_to_cil.c
@@ -191,7 +191,11 @@ static char *constraint_expr_to_str(struct policydb *pdb, struct constraint_expr
 				if (!names) {
 					goto exit;
 				}
-				new_val = create_str("(%s %s %s)", 3, op, attr1, names);
+				if (strchr(names, ' ')) {
+					new_val = create_str("(%s %s (%s))", 3, op, attr1, names);
+				} else {
+					new_val = create_str("(%s %s %s)", 3, op, attr1, names);
+				}
 				free(names);
 			}
 		} else {
diff --git a/libsepol/src/module_to_cil.c b/libsepol/src/module_to_cil.c
index a87bc15e..3cc75b42 100644
--- a/libsepol/src/module_to_cil.c
+++ b/libsepol/src/module_to_cil.c
@@ -1800,13 +1800,20 @@ static int constraint_expr_to_string(struct policydb *pdb, struct constraint_exp
 
 				// length of values/oper + 2 spaces + 2 parens + null terminator
 				len = strlen(op) + strlen(attr1) +  strlen(names) + 2 + 2 + 1;
+				if (num_names > 1) {
+					len += 2; // 2 more parens
+				}
 				new_val = malloc(len);
 				if (new_val == NULL) {
 					log_err("Out of memory");
 					rc = -1;
 					goto exit;
 				}
-				rlen = snprintf(new_val, len, "(%s %s %s)", op, attr1, names);
+				if (num_names > 1) {
+					rlen = snprintf(new_val, len, "(%s %s (%s))", op, attr1, names);
+				} else {
+					rlen = snprintf(new_val, len, "(%s %s %s)", op, attr1, names);
+				}
 				if (rlen < 0 || rlen >= len) {
 					log_err("Failed to generate constraint expression");
 					rc = -1;
-- 
2.26.2

[PATCH 4/4] libsepol: Write "NO_IDENTIFIER" for empty CIL constraint expression

[James Carter]

If a role or user attribute with nothing associated with it is used
in a constraint expression, then the bitmap will be empty. This is
not a problem for the kernel, but does cause problems when converting
a kernel policy or module to CIL.

When creating a CIL policy from a kernel policy or module, if an
empty bitmap is encountered, use the string "NO_IDENTIFIER". An
error will occur if an attempt is made to compile the resulting
policy, but a valid policy was not being produced before anyway.
Treat types the same way even though empty bitmaps are not expected.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/src/kernel_to_cil.c |  2 +-
 libsepol/src/module_to_cil.c | 10 +++++++---
 2 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/libsepol/src/kernel_to_cil.c b/libsepol/src/kernel_to_cil.c
index 96e0f5d3..c6dd2e12 100644
--- a/libsepol/src/kernel_to_cil.c
+++ b/libsepol/src/kernel_to_cil.c
@@ -189,7 +189,7 @@ static char *constraint_expr_to_str(struct policydb *pdb, struct constraint_expr
 					names = ebitmap_to_str(&curr->names, pdb->p_role_val_to_name, 1);
 				}
 				if (!names) {
-					goto exit;
+					names = strdup("NO_IDENTIFIER");
 				}
 				if (strchr(names, ' ')) {
 					new_val = create_str("(%s %s (%s))", 3, op, attr1, names);
diff --git a/libsepol/src/module_to_cil.c b/libsepol/src/module_to_cil.c
index 3cc75b42..2a794f57 100644
--- a/libsepol/src/module_to_cil.c
+++ b/libsepol/src/module_to_cil.c
@@ -1793,9 +1793,13 @@ static int constraint_expr_to_string(struct policydb *pdb, struct constraint_exp
 						goto exit;
 					}
 				}
-				rc = name_list_to_string(name_list, num_names, &names);
-				if (rc != 0) {
-					goto exit;
+				if (num_names == 0) {
+					names = strdup("NO_IDENTIFIER");
+				} else {
+					rc = name_list_to_string(name_list, num_names, &names);
+					if (rc != 0) {
+						goto exit;
+					}
 				}
 
 				// length of values/oper + 2 spaces + 2 parens + null terminator
-- 
2.26.2

Re: [PATCH 4/4] libsepol: Write "NO_IDENTIFIER" for empty CIL constraint expression

[Nicolas Iooss]

On Tue, Mar 16, 2021 at 9:49 PM James Carter <jwcart2@gmail.com> wrote:
>
> If a role or user attribute with nothing associated with it is used
> in a constraint expression, then the bitmap will be empty. This is
> not a problem for the kernel, but does cause problems when converting
> a kernel policy or module to CIL.
>
> When creating a CIL policy from a kernel policy or module, if an
> empty bitmap is encountered, use the string "NO_IDENTIFIER". An
> error will occur if an attempt is made to compile the resulting
> policy, but a valid policy was not being produced before anyway.
> Treat types the same way even though empty bitmaps are not expected.
>
> Signed-off-by: James Carter <jwcart2@gmail.com>
> ---
>  libsepol/src/kernel_to_cil.c |  2 +-
>  libsepol/src/module_to_cil.c | 10 +++++++---
>  2 files changed, 8 insertions(+), 4 deletions(-)
>
> diff --git a/libsepol/src/kernel_to_cil.c b/libsepol/src/kernel_to_cil.c
> index 96e0f5d3..c6dd2e12 100644
> --- a/libsepol/src/kernel_to_cil.c
> +++ b/libsepol/src/kernel_to_cil.c
> @@ -189,7 +189,7 @@ static char *constraint_expr_to_str(struct policydb *pdb, struct constraint_expr
>                                         names = ebitmap_to_str(&curr->names, pdb->p_role_val_to_name, 1);
>                                 }
>                                 if (!names) {
> -                                       goto exit;
> +                                       names = strdup("NO_IDENTIFIER");
>                                 }
>                                 if (strchr(names, ' ')) {
>                                         new_val = create_str("(%s %s (%s))", 3, op, attr1, names);
> diff --git a/libsepol/src/module_to_cil.c b/libsepol/src/module_to_cil.c
> index 3cc75b42..2a794f57 100644
> --- a/libsepol/src/module_to_cil.c
> +++ b/libsepol/src/module_to_cil.c
> @@ -1793,9 +1793,13 @@ static int constraint_expr_to_string(struct policydb *pdb, struct constraint_exp
>                                                 goto exit;
>                                         }
>                                 }
> -                               rc = name_list_to_string(name_list, num_names, &names);
> -                               if (rc != 0) {
> -                                       goto exit;
> +                               if (num_names == 0) {
> +                                       names = strdup("NO_IDENTIFIER");
> +                               } else {
> +                                       rc = name_list_to_string(name_list, num_names, &names);
> +                                       if (rc != 0) {
> +                                               goto exit;
> +                                       }
>                                 }
>
>                                 // length of values/oper + 2 spaces + 2 parens + null terminator

Hello,
This change somehow made gcc unhappy:

$ gcc -O2 -c module_to_cil.c
In function ‘name_list_to_string’,
    inlined from ‘constraint_expr_to_string’ at module_to_cil.c:1799:11:
module_to_cil.c:1156:8: warning: argument 1 range
[18446744071562067968, 18446744073709551615] exceeds maximum object
size 9223372036854775807 [-Walloc-size-larger-than=]
 1156 |  str = malloc(len);
      |        ^~~~~~~~~~~
In file included from module_to_cil.c:39:
module_to_cil.c: In function ‘constraint_expr_to_string’:
/usr/include/stdlib.h:539:14: note: in a call to allocation function
‘malloc’ declared here
  539 | extern void *malloc (size_t __size) __THROW __attribute_malloc__
      |              ^~~~~~

(With gcc 10.2.0 on Arch Linux and gcc 9.3.0-17ubuntu1 on Ubuntu 20.04
which is used by GitHub Actions,
https://github.com/fishilico/selinux/runs/2125501324?check_suite_focus=true#step:9:107
; building for x86_64)

The main cause of this error is the fact that num_names is considered
as a signed integer in name_list_to_string(). This patch fixes the
issue:

diff --git a/libsepol/src/module_to_cil.c b/libsepol/src/module_to_cil.c
index 2a794f577841..6185c7e4ccb7 100644
--- a/libsepol/src/module_to_cil.c
+++ b/libsepol/src/module_to_cil.c
@@ -1124,7 +1124,7 @@ exit:
 }


-static int name_list_to_string(char **names, int num_names, char **string)
+static int name_list_to_string(char **names, unsigned int num_names,
char **string)
 {
        // create a space separated string of the names
        int rc = -1;

... but it would be even better if the type of num_names was
consistent. Right now, ebitmap_to_names() initializes a local variable
"uint32_t num;" and then does "*num_names = num;" with "int
*num_names". I believe the code would be more correct if the parameter
of ebitmap_to_names() was "uint32_t *num_names" or "unsigned int
*num_names" (why is uint32_t used?), and if all its callers used an
unsigned type to store this value. What do you think?

Moreover, I stumbled upon this code pattern in function name_list_to_string:

len += strlen(names[i]);
if (len < strlen(names[i])) {
    log_err("Overflow");
    return -1;
}

Nowadays, both gcc and clang provide checked arithmetic builtins and I
think the intent of this code would be clearer if it used them:

if (__builtin_add_overflow(len, strlen(names[i]), &len)) {
    log_err("Overflow");
    return -1;
}

Does anyone have an opinion about using checked arithmetic builtins?
(I have not used them much, and if someone knows of some compatibility
issues, this would be important to know)

Cheers,
Nicolas

Re: [PATCH 4/4] libsepol: Write "NO_IDENTIFIER" for empty CIL constraint expression

[James Carter]

On Tue, Mar 16, 2021 at 5:45 PM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> On Tue, Mar 16, 2021 at 9:49 PM James Carter <jwcart2@gmail.com> wrote:
> >
> > If a role or user attribute with nothing associated with it is used
> > in a constraint expression, then the bitmap will be empty. This is
> > not a problem for the kernel, but does cause problems when converting
> > a kernel policy or module to CIL.
> >
> > When creating a CIL policy from a kernel policy or module, if an
> > empty bitmap is encountered, use the string "NO_IDENTIFIER". An
> > error will occur if an attempt is made to compile the resulting
> > policy, but a valid policy was not being produced before anyway.
> > Treat types the same way even though empty bitmaps are not expected.
> >
> > Signed-off-by: James Carter <jwcart2@gmail.com>
> > ---
> >  libsepol/src/kernel_to_cil.c |  2 +-
> >  libsepol/src/module_to_cil.c | 10 +++++++---
> >  2 files changed, 8 insertions(+), 4 deletions(-)
> >
> > diff --git a/libsepol/src/kernel_to_cil.c b/libsepol/src/kernel_to_cil.c
> > index 96e0f5d3..c6dd2e12 100644
> > --- a/libsepol/src/kernel_to_cil.c
> > +++ b/libsepol/src/kernel_to_cil.c
> > @@ -189,7 +189,7 @@ static char *constraint_expr_to_str(struct policydb *pdb, struct constraint_expr
> >                                         names = ebitmap_to_str(&curr->names, pdb->p_role_val_to_name, 1);
> >                                 }
> >                                 if (!names) {
> > -                                       goto exit;
> > +                                       names = strdup("NO_IDENTIFIER");
> >                                 }
> >                                 if (strchr(names, ' ')) {
> >                                         new_val = create_str("(%s %s (%s))", 3, op, attr1, names);
> > diff --git a/libsepol/src/module_to_cil.c b/libsepol/src/module_to_cil.c
> > index 3cc75b42..2a794f57 100644
> > --- a/libsepol/src/module_to_cil.c
> > +++ b/libsepol/src/module_to_cil.c
> > @@ -1793,9 +1793,13 @@ static int constraint_expr_to_string(struct policydb *pdb, struct constraint_exp
> >                                                 goto exit;
> >                                         }
> >                                 }
> > -                               rc = name_list_to_string(name_list, num_names, &names);
> > -                               if (rc != 0) {
> > -                                       goto exit;
> > +                               if (num_names == 0) {
> > +                                       names = strdup("NO_IDENTIFIER");
> > +                               } else {
> > +                                       rc = name_list_to_string(name_list, num_names, &names);
> > +                                       if (rc != 0) {
> > +                                               goto exit;
> > +                                       }
> >                                 }
> >
> >                                 // length of values/oper + 2 spaces + 2 parens + null terminator
>
> Hello,
> This change somehow made gcc unhappy:
>
> $ gcc -O2 -c module_to_cil.c
> In function ‘name_list_to_string’,
>     inlined from ‘constraint_expr_to_string’ at module_to_cil.c:1799:11:
> module_to_cil.c:1156:8: warning: argument 1 range
> [18446744071562067968, 18446744073709551615] exceeds maximum object
> size 9223372036854775807 [-Walloc-size-larger-than=]
>  1156 |  str = malloc(len);
>       |        ^~~~~~~~~~~
> In file included from module_to_cil.c:39:
> module_to_cil.c: In function ‘constraint_expr_to_string’:
> /usr/include/stdlib.h:539:14: note: in a call to allocation function
> ‘malloc’ declared here
>   539 | extern void *malloc (size_t __size) __THROW __attribute_malloc__
>       |              ^~~~~~
>
> (With gcc 10.2.0 on Arch Linux and gcc 9.3.0-17ubuntu1 on Ubuntu 20.04
> which is used by GitHub Actions,
> https://github.com/fishilico/selinux/runs/2125501324?check_suite_focus=true#step:9:107
> ; building for x86_64)
>
> The main cause of this error is the fact that num_names is considered
> as a signed integer in name_list_to_string(). This patch fixes the
> issue:
>
> diff --git a/libsepol/src/module_to_cil.c b/libsepol/src/module_to_cil.c
> index 2a794f577841..6185c7e4ccb7 100644
> --- a/libsepol/src/module_to_cil.c
> +++ b/libsepol/src/module_to_cil.c
> @@ -1124,7 +1124,7 @@ exit:
>  }
>
>
> -static int name_list_to_string(char **names, int num_names, char **string)
> +static int name_list_to_string(char **names, unsigned int num_names,
> char **string)
>  {
>         // create a space separated string of the names
>         int rc = -1;
>

This looks good to me.

> ... but it would be even better if the type of num_names was
> consistent. Right now, ebitmap_to_names() initializes a local variable
> "uint32_t num;" and then does "*num_names = num;" with "int
> *num_names". I believe the code would be more correct if the parameter
> of ebitmap_to_names() was "uint32_t *num_names" or "unsigned int
> *num_names" (why is uint32_t used?), and if all its callers used an
> unsigned type to store this value. What do you think?
>

uint32_t is probably used because both startbit in an ebitmap_node_t
and highbit in an ebitmap_t are uint32_t. Although the ebitmap
functions take unsigned int for bit position and return unsigned int
for bit position as well.

I do agree that it would be better to make the type consistent, but,
since num_names has type int in many places, I would rather change it
everywhere to unsigned int. I'll send out a patch.

> Moreover, I stumbled upon this code pattern in function name_list_to_string:
>
> len += strlen(names[i]);
> if (len < strlen(names[i])) {
>     log_err("Overflow");
>     return -1;
> }
>
> Nowadays, both gcc and clang provide checked arithmetic builtins and I
> think the intent of this code would be clearer if it used them:
>
> if (__builtin_add_overflow(len, strlen(names[i]), &len)) {
>     log_err("Overflow");
>     return -1;
> }
>
> Does anyone have an opinion about using checked arithmetic builtins?
> (I have not used them much, and if someone knows of some compatibility
> issues, this would be important to know)
>

I don't know about compatibility issues, but I would prefer to use the
builtins as long as they won't cause problems.

Jim


> Cheers,
> Nicolas
>

Re: [PATCH 1/4] libsepol/cil: Allow lists in constraint expressions

[Nicolas Iooss]

On Tue, Mar 16, 2021 at 9:49 PM James Carter <jwcart2@gmail.com> wrote:
>
> The expectation in CIL was to use user, role, or type attributes in
> constraint expressions. The problem is that neither user nor role
> attributes are part of the kernel binary policy, so when converting
> from a kernel policy to CIL, that would require the creation of a
> role or user attribute. The better solution is to just allow a list
> to be used. In fact, the only thing preventing a list to be used
> is a check in cil_verify_constraint_leaf_expr_syntax().
>
> Remove the check and allow lists in constraint expressions.
>
> The following is now allowed:
>   (constrain (CLASS1 (PERM1)) (eq r1 (ROLE1 ROLE2 ROLE_ATTR3)))
>
> Signed-off-by: James Carter <jwcart2@gmail.com>

For these 4 patches:
Acked-by: Nicolas Iooss <nicolas.iooss@m4x.org>

Before merging, the patch that I sent to fix an issue with some gcc
optimizations (https://lore.kernel.org/selinux/20210316222313.19793-1-nicolas.iooss@m4x.org/)
should be reviewed and applied.

Nicolas

> ---
>  libsepol/cil/src/cil_verify.c | 3 ---
>  1 file changed, 3 deletions(-)
>
> diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c
> index 6706e219..09e3daf9 100644
> --- a/libsepol/cil/src/cil_verify.c
> +++ b/libsepol/cil/src/cil_verify.c
> @@ -225,9 +225,6 @@ int cil_verify_constraint_leaf_expr_syntax(enum cil_flavor l_flavor, enum cil_fl
>                                 cil_log(CIL_ERR, "u3, r3, and t3 can only be used with (mls)validatetrans rules\n");
>                                 goto exit;
>                         }
> -               } else if (r_flavor == CIL_LIST) {
> -                       cil_log(CIL_ERR, "t1, t2, r1, r2, u1, u2 cannot be used on the left side with a list on the right side\n");
> -                       goto exit;
>                 }
>         } else {
>                 if (r_flavor == CIL_CONS_U2) {
> --
> 2.26.2
>

Re: [PATCH 1/4] libsepol/cil: Allow lists in constraint expressions

[James Carter]

On Wed, Mar 17, 2021 at 5:31 AM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> On Tue, Mar 16, 2021 at 9:49 PM James Carter <jwcart2@gmail.com> wrote:
> >
> > The expectation in CIL was to use user, role, or type attributes in
> > constraint expressions. The problem is that neither user nor role
> > attributes are part of the kernel binary policy, so when converting
> > from a kernel policy to CIL, that would require the creation of a
> > role or user attribute. The better solution is to just allow a list
> > to be used. In fact, the only thing preventing a list to be used
> > is a check in cil_verify_constraint_leaf_expr_syntax().
> >
> > Remove the check and allow lists in constraint expressions.
> >
> > The following is now allowed:
> >   (constrain (CLASS1 (PERM1)) (eq r1 (ROLE1 ROLE2 ROLE_ATTR3)))
> >
> > Signed-off-by: James Carter <jwcart2@gmail.com>
>
> For these 4 patches:
> Acked-by: Nicolas Iooss <nicolas.iooss@m4x.org>
>

These four patches have been merged (the patch below was merged as well).
Thanks,
Jim

> Before merging, the patch that I sent to fix an issue with some gcc
> optimizations (https://lore.kernel.org/selinux/20210316222313.19793-1-nicolas.iooss@m4x.org/)
> should be reviewed and applied.
>
> Nicolas
>
> > ---
> >  libsepol/cil/src/cil_verify.c | 3 ---
> >  1 file changed, 3 deletions(-)
> >
> > diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c
> > index 6706e219..09e3daf9 100644
> > --- a/libsepol/cil/src/cil_verify.c
> > +++ b/libsepol/cil/src/cil_verify.c
> > @@ -225,9 +225,6 @@ int cil_verify_constraint_leaf_expr_syntax(enum cil_flavor l_flavor, enum cil_fl
> >                                 cil_log(CIL_ERR, "u3, r3, and t3 can only be used with (mls)validatetrans rules\n");
> >                                 goto exit;
> >                         }
> > -               } else if (r_flavor == CIL_LIST) {
> > -                       cil_log(CIL_ERR, "t1, t2, r1, r2, u1, u2 cannot be used on the left side with a list on the right side\n");
> > -                       goto exit;
> >                 }
> >         } else {
> >                 if (r_flavor == CIL_CONS_U2) {
> > --
> > 2.26.2
> >
>