Skip to contentSkip to conversation

libsepol: reject invalid roles before inverting

PATCH In review Christian Göttsche 2 participants 4 messages Jan 17, 2022 – Jan 20, 2022 SELinux security module

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 libsepol: reject invalid roles before inverting

Since the role datums have not been validated yet, they might be invalid and set to an enormous high value. Inverting such an ebitmap will take excessive amount of memory and time.

Found by oss-fuzz (#43709)

---
 libsepol/src/expand.c | 4 ++++
 1 file changed, 4 insertions(+)
libsepol/src/expand.c +4 -0
index 898e6b87..3fc54af6 100644
@@ -2481,6 +2481,10 @@ int role_set_expand(role_set_t * x, ebitmap_t * r, policydb_t * out, policydb_t
 
 	/* if role is to be complimented, invert the entire bitmap here */
 	if (x->flags & ROLE_COMP) {
+		/* inverting an ebitmap with an invalid highbit will take aeons */
+		if (ebitmap_length(r) > p->p_roles.nprim)
+			return -1;
+
 		for (i = 0; i < ebitmap_length(r); i++) {
 			if (ebitmap_get_bit(r, i)) {
 				if (ebitmap_set_bit(r, i, 0))
Signature · 1 line
2.34.1
#1 lore raw
Quoted 26 lines · Christian Göttsche

Since the role datums have not been validated yet, they might be invalid and set to an enormous high value. Inverting such an ebitmap will take excessive amount of memory and time.

Found by oss-fuzz (#43709)

---
 libsepol/src/expand.c | 4 ++++
 1 file changed, 4 insertions(+)
libsepol/src/expand.c +4 -1
index 898e6b87..3fc54af6 100644
@@ -2481,6 +2481,10 @@ int role_set_expand(role_set_t * x, ebitmap_t * r, policydb_t * out, policydb_t
 
        /* if role is to be complimented, invert the entire bitmap here */
        if (x->flags & ROLE_COMP) {
+               /* inverting an ebitmap with an invalid highbit will take aeons */
+               if (ebitmap_length(r) > p->p_roles.nprim)
+                       return -1;
+
                for (i = 0; i < ebitmap_length(r); i++) {
                        if (ebitmap_get_bit(r, i)) {
                                if (ebitmap_set_bit(r, i, 0))
--
Quoted 2 lines

2.34.1

One would think that ebitmap_length() would be the right function, but actually it will return the highest position in the bitmap without regard to whether it is set or not. Since the ebitmap has 64 bit nodes, it will be a multiple of 64.

The function you want to use here is ebitmap_highest_set_bit().

Thanks,
Jim

#2 lore raw
Quoted 37 lines · James Carter
Quoted 26 lines · Christian Göttsche

Since the role datums have not been validated yet, they might be invalid and set to an enormous high value. Inverting such an ebitmap will take excessive amount of memory and time.

Found by oss-fuzz (#43709)

---
 libsepol/src/expand.c | 4 ++++
 1 file changed, 4 insertions(+)
libsepol/src/expand.c +4 -1
index 898e6b87..3fc54af6 100644
@@ -2481,6 +2481,10 @@ int role_set_expand(role_set_t * x, ebitmap_t * r, policydb_t * out, policydb_t
 
        /* if role is to be complimented, invert the entire bitmap here */
        if (x->flags & ROLE_COMP) {
+               /* inverting an ebitmap with an invalid highbit will take aeons */
+               if (ebitmap_length(r) > p->p_roles.nprim)
+                       return -1;
+
                for (i = 0; i < ebitmap_length(r); i++) {
                        if (ebitmap_get_bit(r, i)) {
                                if (ebitmap_set_bit(r, i, 0))
--
Quoted 2 lines

2.34.1

One would think that ebitmap_length() would be the right function, but actually it will return the highest position in the bitmap without regard to whether it is set or not. Since the ebitmap has 64 bit nodes, it will be a multiple of 64.

Quoted 1 line

The function you want to use here is ebitmap_highest_set_bit().

On a second thought: does this inverting even work?

Consider p->p_roles.nprim being 42, the highest bit in the current ebitmap being 32, and thus the length/highbit being 64. The highest bit 32 is less than 42 so that's fine.
But then the inversion inverts all bits up to ebitmap_length() (=64), so now the highest bit is 64, which is bigger than p->p_roles.nprim.
The ebitmap now has a role set that is not defined, some further operations might fail, and any subsequent validation will fail (e.g. in validate_ebitmap()).
git-blame[1] shows this code was introduced with the initial import from svn and also the flag ROLE_COMP is otherwise unused (with an exception in the test binary dismod).
checkpolicy(8) does not accept role complements, e.g. user sys_user roles ~sys_role; or allow role1 ~role2; are invalid.

Maybe the inversion would be safe if the upper bound was p->p_roles.nprim not ebitmap_length()?

[1]: https://github.com/SELinuxProject/selinux/blame/master/libsepol/src/expand.c

Quoted 3 lines

Thanks,
Jim

#3 lore raw
Quoted 58 lines · Christian Göttsche
Quoted 37 lines · James Carter
Quoted 26 lines · Christian Göttsche

Since the role datums have not been validated yet, they might be invalid and set to an enormous high value. Inverting such an ebitmap will take excessive amount of memory and time.

Found by oss-fuzz (#43709)

---
 libsepol/src/expand.c | 4 ++++
 1 file changed, 4 insertions(+)
libsepol/src/expand.c +4 -1
index 898e6b87..3fc54af6 100644
@@ -2481,6 +2481,10 @@ int role_set_expand(role_set_t * x, ebitmap_t * r, policydb_t * out, policydb_t
 
        /* if role is to be complimented, invert the entire bitmap here */
        if (x->flags & ROLE_COMP) {
+               /* inverting an ebitmap with an invalid highbit will take aeons */
+               if (ebitmap_length(r) > p->p_roles.nprim)
+                       return -1;
+
                for (i = 0; i < ebitmap_length(r); i++) {
                        if (ebitmap_get_bit(r, i)) {
                                if (ebitmap_set_bit(r, i, 0))
--
Quoted 2 lines

2.34.1

One would think that ebitmap_length() would be the right function, but actually it will return the highest position in the bitmap without regard to whether it is set or not. Since the ebitmap has 64 bit nodes, it will be a multiple of 64.

Quoted 1 line

The function you want to use here is ebitmap_highest_set_bit().

On a second thought: does this inverting even work?

Consider p->p_roles.nprim being 42, the highest bit in the current ebitmap being 32, and thus the length/highbit being 64. The highest bit 32 is less than 42 so that's fine.
But then the inversion inverts all bits up to ebitmap_length() (=64), so now the highest bit is 64, which is bigger than p->p_roles.nprim.
The ebitmap now has a role set that is not defined, some further operations might fail, and any subsequent validation will fail (e.g. in validate_ebitmap()).
git-blame[1] shows this code was introduced with the initial import from svn and also the flag ROLE_COMP is otherwise unused (with an exception in the test binary dismod).
checkpolicy(8) does not accept role complements, e.g. user sys_user roles ~sys_role; or allow role1 ~role2; are invalid.

Quoted 3 lines

Maybe the inversion would be safe if the upper bound was p->p_roles.nprim not ebitmap_length()?

Yes, it should be using p->p_roles.nprim and not ebitmap_length(). The function type_set_expand() uses p->p_types.nprim as it should.

Thanks,
Jim

Quoted 6 lines

[1]: https://github.com/SELinuxProject/selinux/blame/master/libsepol/src/expand.c

Quoted 3 lines

Thanks,
Jim