[PATCH] libsepol: avoid unsigned integer overflow

[PATCH] libsepol: avoid unsigned integer overflow

[Christian Göttsche]

Unsigned integer overflow is well-defined and not undefined behavior.
But it is still useful to enable undefined behavior sanitizer checks on
unsigned arithmetic to detect possible issues on counters or variables
with similar purpose.

Use a spaceship operator like comparison instead of subtraction.

Modern compilers will generate a single comparison instruction instead
of actually perform the subtraction.

    policydb.c:851:24: runtime error: unsigned integer overflow: 801 - 929 cannot be represented in type 'unsigned int'

This is similar to 1537ea84.

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 libsepol/src/policydb.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/libsepol/src/policydb.c b/libsepol/src/policydb.c
index ef2217c2..8865a2eb 100644
--- a/libsepol/src/policydb.c
+++ b/libsepol/src/policydb.c
@@ -843,15 +843,15 @@ static int rangetr_cmp(hashtab_t h __attribute__ ((unused)),
 	const struct range_trans *key2 = (const struct range_trans *)k2;
 	int v;
 
-	v = key1->source_type - key2->source_type;
+	v = (key1->source_type > key2->source_type) - (key1->source_type < key2->source_type);
 	if (v)
 		return v;
 
-	v = key1->target_type - key2->target_type;
+	v = (key1->target_type > key2->target_type) - (key1->target_type < key2->target_type);
 	if (v)
 		return v;
 
-	v = key1->target_class - key2->target_class;
+	v = (key1->target_class > key2->target_class) - (key1->target_class > key2->target_class);
 
 	return v;
 }
-- 
2.32.0

[PATCH v2] libsepol: avoid unsigned integer overflow

[Christian Göttsche]

Unsigned integer overflow is well-defined and not undefined behavior.
But it is still useful to enable undefined behavior sanitizer checks on
unsigned arithmetic to detect possible issues on counters or variables
with similar purpose.

Use a spaceship operator like comparison instead of subtraction.

Modern compilers will generate a single comparison instruction instead
of actually perform the subtraction.

    policydb.c:851:24: runtime error: unsigned integer overflow: 801 - 929 cannot be represented in type 'unsigned int'

This is similar to 1537ea84.

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 libsepol/src/policydb.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/libsepol/src/policydb.c b/libsepol/src/policydb.c
index ef2217c2..5ee78b4c 100644
--- a/libsepol/src/policydb.c
+++ b/libsepol/src/policydb.c
@@ -843,15 +843,15 @@ static int rangetr_cmp(hashtab_t h __attribute__ ((unused)),
 	const struct range_trans *key2 = (const struct range_trans *)k2;
 	int v;
 
-	v = key1->source_type - key2->source_type;
+	v = (key1->source_type > key2->source_type) - (key1->source_type < key2->source_type);
 	if (v)
 		return v;
 
-	v = key1->target_type - key2->target_type;
+	v = (key1->target_type > key2->target_type) - (key1->target_type < key2->target_type);
 	if (v)
 		return v;
 
-	v = key1->target_class - key2->target_class;
+	v = (key1->target_class > key2->target_class) - (key1->target_class < key2->target_class);
 
 	return v;
 }
-- 
2.32.0

Re: [PATCH v2] libsepol: avoid unsigned integer overflow

[Nicolas Iooss]

On Thu, Jul 1, 2021 at 8:38 PM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> Unsigned integer overflow is well-defined and not undefined behavior.
> But it is still useful to enable undefined behavior sanitizer checks on
> unsigned arithmetic to detect possible issues on counters or variables
> with similar purpose.
>
> Use a spaceship operator like comparison instead of subtraction.
>
> Modern compilers will generate a single comparison instruction instead
> of actually perform the subtraction.
>
>     policydb.c:851:24: runtime error: unsigned integer overflow: 801 - 929 cannot be represented in type 'unsigned int'
>
> This is similar to 1537ea84.

While I agree with the change, I still see subtractions in gcc 11.1
and clang 12. What do you call "modern compilers"?

More precisely, I copied the function rangetr_cmp in Godbolt and
compiled it with "x86-64 gcc 11.1" and -O2,
https://godbolt.org/z/5c4jG7eeh . The generated assembly code
contains:

    mov eax, DWORD PTR [rsi]
    cmp DWORD PTR [rdi], eax
    seta al
    movzx eax, al
    sbb eax, 0
    test eax, eax
    jne .L1

This really computes a subtraction, with instruction SBB. For people
not familiar with x86_64 assembly language:

* the first two instructions compare two values,
* SETA sets the 8-bit register AL to 1 if the first value was above
the other one,
* MOVZX ensures that the 32-bit register EAX contains 0 or 1,
* SBB computes the subtraction between EAX and the carry flag, which
is one only if the first value was below the other one.
* TEST checks whether the result of the subtraction is zero.

For information, the previous code generated the following instructions:

    mov eax, DWORD PTR [rdi]
    sub eax, DWORD PTR [rsi]
    jne .L1

So the previous code generated simpler assembler instructions, but
which could trigger an undefined behavior in C.

TL;DR Anyway, as this change is not about performance but about
undefined behaviour in C, it looks good to me. Nevertheless the
sentence "Modern compilers will generate a single comparison
instruction instead of actually perform the subtraction." seems to be
wrong. Could you rephrase it (for example by giving examples of such
compilers), or remove it?

Thanks,
Nicolas

PS: about the integer overflow itself, I read
https://wiki.sei.cmu.edu/confluence/display/c/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap
too, which seems to be clear that subtracting two unsigned integers
and expecting the subtraction to wrap is something which should be
avoided.

> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> ---
>  libsepol/src/policydb.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
>
> diff --git a/libsepol/src/policydb.c b/libsepol/src/policydb.c
> index ef2217c2..5ee78b4c 100644
> --- a/libsepol/src/policydb.c
> +++ b/libsepol/src/policydb.c
> @@ -843,15 +843,15 @@ static int rangetr_cmp(hashtab_t h __attribute__ ((unused)),
>         const struct range_trans *key2 = (const struct range_trans *)k2;
>         int v;
>
> -       v = key1->source_type - key2->source_type;
> +       v = (key1->source_type > key2->source_type) - (key1->source_type < key2->source_type);
>         if (v)
>                 return v;
>
> -       v = key1->target_type - key2->target_type;
> +       v = (key1->target_type > key2->target_type) - (key1->target_type < key2->target_type);
>         if (v)
>                 return v;
>
> -       v = key1->target_class - key2->target_class;
> +       v = (key1->target_class > key2->target_class) - (key1->target_class < key2->target_class);
>
>         return v;
>  }
> --
> 2.32.0
>

Re: [PATCH v2] libsepol: avoid unsigned integer overflow

[Christian Göttsche]

On Fri, 2 Jul 2021 at 22:36, Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> On Thu, Jul 1, 2021 at 8:38 PM Christian Göttsche
> <cgzones@googlemail.com> wrote:
> >
> > Unsigned integer overflow is well-defined and not undefined behavior.
> > But it is still useful to enable undefined behavior sanitizer checks on
> > unsigned arithmetic to detect possible issues on counters or variables
> > with similar purpose.
> >
> > Use a spaceship operator like comparison instead of subtraction.
> >
> > Modern compilers will generate a single comparison instruction instead
> > of actually perform the subtraction.
> >
> >     policydb.c:851:24: runtime error: unsigned integer overflow: 801 - 929 cannot be represented in type 'unsigned int'
> >
> > This is similar to 1537ea84.
>
> While I agree with the change, I still see subtractions in gcc 11.1
> and clang 12. What do you call "modern compilers"?
>
> More precisely, I copied the function rangetr_cmp in Godbolt and
> compiled it with "x86-64 gcc 11.1" and -O2,
> https://godbolt.org/z/5c4jG7eeh . The generated assembly code
> contains:
>
>     mov eax, DWORD PTR [rsi]
>     cmp DWORD PTR [rdi], eax
>     seta al
>     movzx eax, al
>     sbb eax, 0
>     test eax, eax
>     jne .L1
>
> This really computes a subtraction, with instruction SBB. For people
> not familiar with x86_64 assembly language:
>
> * the first two instructions compare two values,
> * SETA sets the 8-bit register AL to 1 if the first value was above
> the other one,
> * MOVZX ensures that the 32-bit register EAX contains 0 or 1,
> * SBB computes the subtraction between EAX and the carry flag, which
> is one only if the first value was below the other one.
> * TEST checks whether the result of the subtraction is zero.
>

Since I also checked the assembly results with Godbolt, it seems I had
misinterpreted the results regarding the subtract instruction.

> For information, the previous code generated the following instructions:
>
>     mov eax, DWORD PTR [rdi]
>     sub eax, DWORD PTR [rsi]
>     jne .L1
>
> So the previous code generated simpler assembler instructions, but
> which could trigger an undefined behavior in C.
>

It is not undefined behaviour, unsigned integer overflow is well defined
to be wrapped. And there are legitimate use cases, like for hashing or
pseudo number generation. But outside of those unsigned integer over-
and underflow can point to logic errors (when reducing a counter below zero)
or missed overflow checks on user input.

> TL;DR Anyway, as this change is not about performance but about
> undefined behaviour in C, it looks good to me. Nevertheless the
> sentence "Modern compilers will generate a single comparison
> instruction instead of actually perform the subtraction." seems to be
> wrong. Could you rephrase it (for example by giving examples of such
> compilers), or remove it?
>

I'll send a new version with an updated description and also using a comparison
macro, to minimize the chance for typos like in the first version.

[PATCH v3] libsepol: avoid unsigned integer overflow

[Christian Göttsche]

Unsigned integer overflow is well-defined and not undefined behavior.
It is commonly used for hashing or pseudo random number generation.
But it is still useful to enable undefined behavior sanitizer checks on
unsigned arithmetic to detect possible issues on counters or variables
with similar purpose or missed overflow checks on user input.

Use a spaceship operator like comparison instead of subtraction.

    policydb.c:851:24: runtime error: unsigned integer overflow: 801 - 929 cannot be represented in type 'unsigned int'

Follow-up of: 1537ea8412e4 ("libsepol: avoid unsigned integer overflow")

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 libsepol/src/policydb.c | 10 +++++-----
 libsepol/src/private.h  |  2 ++
 2 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/libsepol/src/policydb.c b/libsepol/src/policydb.c
index ef2217c2..0398ceed 100644
--- a/libsepol/src/policydb.c
+++ b/libsepol/src/policydb.c
@@ -817,11 +817,11 @@ static int filenametr_cmp(hashtab_t h __attribute__ ((unused)),
 	const filename_trans_key_t *ft2 = (const filename_trans_key_t *)k2;
 	int v;
 
-	v = (ft1->ttype > ft2->ttype) - (ft1->ttype < ft2->ttype);
+	v = spaceship_cmp(ft1->ttype, ft2->ttype);
 	if (v)
 		return v;
 
-	v = (ft1->tclass > ft2->tclass) - (ft1->tclass < ft2->tclass);
+	v = spaceship_cmp(ft1->tclass, ft2->tclass);
 	if (v)
 		return v;
 
@@ -843,15 +843,15 @@ static int rangetr_cmp(hashtab_t h __attribute__ ((unused)),
 	const struct range_trans *key2 = (const struct range_trans *)k2;
 	int v;
 
-	v = key1->source_type - key2->source_type;
+	v = spaceship_cmp(key1->source_type, key2->source_type);
 	if (v)
 		return v;
 
-	v = key1->target_type - key2->target_type;
+	v = spaceship_cmp(key1->target_type, key2->target_type);
 	if (v)
 		return v;
 
-	v = key1->target_class - key2->target_class;
+	v = spaceship_cmp(key1->target_class, key2->target_class);
 
 	return v;
 }
diff --git a/libsepol/src/private.h b/libsepol/src/private.h
index 72f21262..c63238ab 100644
--- a/libsepol/src/private.h
+++ b/libsepol/src/private.h
@@ -47,6 +47,8 @@
 #define is_saturated(x) (x == (typeof(x))-1)
 #define zero_or_saturated(x) ((x == 0) || is_saturated(x))
 
+#define spaceship_cmp(a, b) (((a) > (b)) - ((a) < (b)))
+
 /* Policy compatibility information. */
 struct policydb_compat_info {
 	unsigned int type;
-- 
2.32.0

Re: [PATCH v3] libsepol: avoid unsigned integer overflow

[Nicolas Iooss]

On Tue, Jul 6, 2021 at 7:36 PM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> Unsigned integer overflow is well-defined and not undefined behavior.
> It is commonly used for hashing or pseudo random number generation.
> But it is still useful to enable undefined behavior sanitizer checks on
> unsigned arithmetic to detect possible issues on counters or variables
> with similar purpose or missed overflow checks on user input.
>
> Use a spaceship operator like comparison instead of subtraction.
>
>     policydb.c:851:24: runtime error: unsigned integer overflow: 801 - 929 cannot be represented in type 'unsigned int'
>
> Follow-up of: 1537ea8412e4 ("libsepol: avoid unsigned integer overflow")
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Acked-by: Nicolas Iooss <nicolas.iooss@m4x.org>

Thanks!
Nicolas

> ---
>  libsepol/src/policydb.c | 10 +++++-----
>  libsepol/src/private.h  |  2 ++
>  2 files changed, 7 insertions(+), 5 deletions(-)
>
> diff --git a/libsepol/src/policydb.c b/libsepol/src/policydb.c
> index ef2217c2..0398ceed 100644
> --- a/libsepol/src/policydb.c
> +++ b/libsepol/src/policydb.c
> @@ -817,11 +817,11 @@ static int filenametr_cmp(hashtab_t h __attribute__ ((unused)),
>         const filename_trans_key_t *ft2 = (const filename_trans_key_t *)k2;
>         int v;
>
> -       v = (ft1->ttype > ft2->ttype) - (ft1->ttype < ft2->ttype);
> +       v = spaceship_cmp(ft1->ttype, ft2->ttype);
>         if (v)
>                 return v;
>
> -       v = (ft1->tclass > ft2->tclass) - (ft1->tclass < ft2->tclass);
> +       v = spaceship_cmp(ft1->tclass, ft2->tclass);
>         if (v)
>                 return v;
>
> @@ -843,15 +843,15 @@ static int rangetr_cmp(hashtab_t h __attribute__ ((unused)),
>         const struct range_trans *key2 = (const struct range_trans *)k2;
>         int v;
>
> -       v = key1->source_type - key2->source_type;
> +       v = spaceship_cmp(key1->source_type, key2->source_type);
>         if (v)
>                 return v;
>
> -       v = key1->target_type - key2->target_type;
> +       v = spaceship_cmp(key1->target_type, key2->target_type);
>         if (v)
>                 return v;
>
> -       v = key1->target_class - key2->target_class;
> +       v = spaceship_cmp(key1->target_class, key2->target_class);
>
>         return v;
>  }
> diff --git a/libsepol/src/private.h b/libsepol/src/private.h
> index 72f21262..c63238ab 100644
> --- a/libsepol/src/private.h
> +++ b/libsepol/src/private.h
> @@ -47,6 +47,8 @@
>  #define is_saturated(x) (x == (typeof(x))-1)
>  #define zero_or_saturated(x) ((x == 0) || is_saturated(x))
>
> +#define spaceship_cmp(a, b) (((a) > (b)) - ((a) < (b)))
> +
>  /* Policy compatibility information. */
>  struct policydb_compat_info {
>         unsigned int type;
> --
> 2.32.0
>

Re: [PATCH v3] libsepol: avoid unsigned integer overflow

[Nicolas Iooss]

On Mon, Jul 12, 2021 at 9:33 AM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> On Tue, Jul 6, 2021 at 7:36 PM Christian Göttsche
> <cgzones@googlemail.com> wrote:
> >
> > Unsigned integer overflow is well-defined and not undefined behavior.
> > It is commonly used for hashing or pseudo random number generation.
> > But it is still useful to enable undefined behavior sanitizer checks on
> > unsigned arithmetic to detect possible issues on counters or variables
> > with similar purpose or missed overflow checks on user input.
> >
> > Use a spaceship operator like comparison instead of subtraction.
> >
> >     policydb.c:851:24: runtime error: unsigned integer overflow: 801 - 929 cannot be represented in type 'unsigned int'
> >
> > Follow-up of: 1537ea8412e4 ("libsepol: avoid unsigned integer overflow")
> >
> > Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
>
> Acked-by: Nicolas Iooss <nicolas.iooss@m4x.org>
>
> Thanks!
> Nicolas

Merged.
Thanks!
Nicolas

> > ---
> >  libsepol/src/policydb.c | 10 +++++-----
> >  libsepol/src/private.h  |  2 ++
> >  2 files changed, 7 insertions(+), 5 deletions(-)
> >
> > diff --git a/libsepol/src/policydb.c b/libsepol/src/policydb.c
> > index ef2217c2..0398ceed 100644
> > --- a/libsepol/src/policydb.c
> > +++ b/libsepol/src/policydb.c
> > @@ -817,11 +817,11 @@ static int filenametr_cmp(hashtab_t h __attribute__ ((unused)),
> >         const filename_trans_key_t *ft2 = (const filename_trans_key_t *)k2;
> >         int v;
> >
> > -       v = (ft1->ttype > ft2->ttype) - (ft1->ttype < ft2->ttype);
> > +       v = spaceship_cmp(ft1->ttype, ft2->ttype);
> >         if (v)
> >                 return v;
> >
> > -       v = (ft1->tclass > ft2->tclass) - (ft1->tclass < ft2->tclass);
> > +       v = spaceship_cmp(ft1->tclass, ft2->tclass);
> >         if (v)
> >                 return v;
> >
> > @@ -843,15 +843,15 @@ static int rangetr_cmp(hashtab_t h __attribute__ ((unused)),
> >         const struct range_trans *key2 = (const struct range_trans *)k2;
> >         int v;
> >
> > -       v = key1->source_type - key2->source_type;
> > +       v = spaceship_cmp(key1->source_type, key2->source_type);
> >         if (v)
> >                 return v;
> >
> > -       v = key1->target_type - key2->target_type;
> > +       v = spaceship_cmp(key1->target_type, key2->target_type);
> >         if (v)
> >                 return v;
> >
> > -       v = key1->target_class - key2->target_class;
> > +       v = spaceship_cmp(key1->target_class, key2->target_class);
> >
> >         return v;
> >  }
> > diff --git a/libsepol/src/private.h b/libsepol/src/private.h
> > index 72f21262..c63238ab 100644
> > --- a/libsepol/src/private.h
> > +++ b/libsepol/src/private.h
> > @@ -47,6 +47,8 @@
> >  #define is_saturated(x) (x == (typeof(x))-1)
> >  #define zero_or_saturated(x) ((x == 0) || is_saturated(x))
> >
> > +#define spaceship_cmp(a, b) (((a) > (b)) - ((a) < (b)))
> > +
> >  /* Policy compatibility information. */
> >  struct policydb_compat_info {
> >         unsigned int type;
> > --
> > 2.32.0
> >