| Message ID | 20220117150200.24953-1-cgzones@googlemail.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Headers | show |
| Series | libsepol: reject invalid roles before inverting | expand |
On Mon, Jan 17, 2022 at 9:34 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > 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(+) > > diff --git a/libsepol/src/expand.c b/libsepol/src/expand.c > index 898e6b87..3fc54af6 100644 > --- a/libsepol/src/expand.c > +++ b/libsepol/src/expand.c > @@ -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)) > -- > 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
On Wed, 19 Jan 2022 at 20:18, James Carter <jwcart2@gmail.com> wrote: > > On Mon, Jan 17, 2022 at 9:34 PM Christian Göttsche > <cgzones@googlemail.com> wrote: > > > > 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(+) > > > > diff --git a/libsepol/src/expand.c b/libsepol/src/expand.c > > index 898e6b87..3fc54af6 100644 > > --- a/libsepol/src/expand.c > > +++ b/libsepol/src/expand.c > > @@ -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)) > > -- > > 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(). 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 > > Thanks, > Jim
On Thu, Jan 20, 2022 at 11:15 AM Christian Göttsche <cgzones@googlemail.com> wrote: > > On Wed, 19 Jan 2022 at 20:18, James Carter <jwcart2@gmail.com> wrote: > > > > On Mon, Jan 17, 2022 at 9:34 PM Christian Göttsche > > <cgzones@googlemail.com> wrote: > > > > > > 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(+) > > > > > > diff --git a/libsepol/src/expand.c b/libsepol/src/expand.c > > > index 898e6b87..3fc54af6 100644 > > > --- a/libsepol/src/expand.c > > > +++ b/libsepol/src/expand.c > > > @@ -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)) > > > -- > > > 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(). > > 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()`? > 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 > > [1]: https://github.com/SELinuxProject/selinux/blame/master/libsepol/src/expand.c > > > > > Thanks, > > Jim
diff --git a/libsepol/src/expand.c b/libsepol/src/expand.c index 898e6b87..3fc54af6 100644 --- a/libsepol/src/expand.c +++ b/libsepol/src/expand.c @@ -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))