* [PATCH] libsepol: avoid unsigned integer overflow @ 2021-07-01 18:34 Christian Göttsche 2021-07-01 18:38 ` [PATCH v2] " Christian Göttsche 2021-07-06 17:36 ` [PATCH v3] " Christian Göttsche 0 siblings, 2 replies; 7+ messages in thread From: Christian Göttsche @ 2021-07-01 18:34 UTC (permalink / raw) To: selinux 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 ^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH v2] libsepol: avoid unsigned integer overflow 2021-07-01 18:34 [PATCH] libsepol: avoid unsigned integer overflow Christian Göttsche @ 2021-07-01 18:38 ` Christian Göttsche 2021-07-02 20:36 ` Nicolas Iooss 2021-07-06 17:36 ` [PATCH v3] " Christian Göttsche 1 sibling, 1 reply; 7+ messages in thread From: Christian Göttsche @ 2021-07-01 18:38 UTC (permalink / raw) To: selinux 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 ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH v2] libsepol: avoid unsigned integer overflow 2021-07-01 18:38 ` [PATCH v2] " Christian Göttsche @ 2021-07-02 20:36 ` Nicolas Iooss 2021-07-06 17:24 ` Christian Göttsche 0 siblings, 1 reply; 7+ messages in thread From: Nicolas Iooss @ 2021-07-02 20:36 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list 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 > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v2] libsepol: avoid unsigned integer overflow 2021-07-02 20:36 ` Nicolas Iooss @ 2021-07-06 17:24 ` Christian Göttsche 0 siblings, 0 replies; 7+ messages in thread From: Christian Göttsche @ 2021-07-06 17:24 UTC (permalink / raw) To: Nicolas Iooss; +Cc: SElinux list 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. ^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v3] libsepol: avoid unsigned integer overflow 2021-07-01 18:34 [PATCH] libsepol: avoid unsigned integer overflow Christian Göttsche 2021-07-01 18:38 ` [PATCH v2] " Christian Göttsche @ 2021-07-06 17:36 ` Christian Göttsche 2021-07-12 7:33 ` Nicolas Iooss 1 sibling, 1 reply; 7+ messages in thread From: Christian Göttsche @ 2021-07-06 17:36 UTC (permalink / raw) To: selinux 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 ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH v3] libsepol: avoid unsigned integer overflow 2021-07-06 17:36 ` [PATCH v3] " Christian Göttsche @ 2021-07-12 7:33 ` Nicolas Iooss 2021-07-13 20:00 ` Nicolas Iooss 0 siblings, 1 reply; 7+ messages in thread From: Nicolas Iooss @ 2021-07-12 7:33 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list 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 > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v3] libsepol: avoid unsigned integer overflow 2021-07-12 7:33 ` Nicolas Iooss @ 2021-07-13 20:00 ` Nicolas Iooss 0 siblings, 0 replies; 7+ messages in thread From: Nicolas Iooss @ 2021-07-13 20:00 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list 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 > > ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-07-13 20:00 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-07-01 18:34 [PATCH] libsepol: avoid unsigned integer overflow Christian Göttsche 2021-07-01 18:38 ` [PATCH v2] " Christian Göttsche 2021-07-02 20:36 ` Nicolas Iooss 2021-07-06 17:24 ` Christian Göttsche 2021-07-06 17:36 ` [PATCH v3] " Christian Göttsche 2021-07-12 7:33 ` Nicolas Iooss 2021-07-13 20:00 ` Nicolas Iooss
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).