Subject: bug#73474: closed (Re: bug#73474: Bug in factor utility of coreutils)

From: [email-masked] (GNU bug Tracking System)
Date: Wed, 25 Sep 2024 15:17:01 +0000

Your bug report

#73474: Bug in factor utility of coreutils

which was filed against the coreutils package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
73474: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=73474
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#73474: Bug in factor utility of coreutils
From: Pádraig Brady <[email-masked]>
To: Артем Насонов<[email-masked]>, [email-masked]
Cc: Виктория Егорова<[email-masked]>
Date: Wed, 25 Sep 2024 16:14:42 +0100
List-Id: <debbugs-submit.debbugs.gnu.org>

On 25/09/2024 11:26, Артем Насонов wrote:
> To whom it may concern,
> 
> I’m writing to let you know that I found an issue by fuzzing in
> coreutils in *factor* utility and want to report it. Here are some details:
> 
> 1. Host architecture: Host it Debian x86_64 architecture
> 2. factor version: factor (GNU coreutils) 9.5.94-5cecd
> 3. Affected code area: src/factor.c:425
> 4. Steps to reproduce:
>       Working on commit: 5cecd703e57b2e1301767d82cbe5bb01cae88472
> 
> |    export CC="clang-17"
>       export CXX="clang++-17"
>       export CFLAGS="-fsanitize=address,undefined -g"
>       export LDFLAGS="-fsanitize=address,undefined -g"
>       export
> UBSAN_OPTIONS=halt_on_error=1,abort_on_error=1,print_stacktrace=true,symbolize=true,print_stacktrace=1,report_error_type=1,symbolize=1
>       ./bootstrap
>       ./configure
>       make
>       ./src/factor 22222222222222222202111121111|
> 
> 5. Bug details: during fuzzing with Undefined-Behaviour sanitizer we've
> got the following report:
> 
> |//src/factor.c:425:3: runtime error: shift exponent 64 is too large for
> 64-bit type 'uintmax_t' (aka 'unsigned long')
>       #0 0x56332975f862 in mod2
> /home/artemiin/Work/crash_confirmation/coreutils/src/factor.c:425:3
>       #1 0x56332975ae54 in factor_using_pollard_rho2
> coreutils/src/factor.c:1665:12
>       #2 0x563329750ab5 in factor  coreutils/src/factor.c:2246:9
>       #3 0x56332974eed6 in print_factors_single coreutils/src/factor.c:2454:3
>       #4 0x56332974dd4c in print_factors coreutils/src/factor.c:2506:11
>       #5 0x56332974d20d in main  coreutils/src/factor.c:2647:15
>       #6 0x7fa1933eb249 in __libc_start_call_main
> csu/../sysdeps/nptl/libc_start_call_main.h:58:16
>       #7 0x7fa1933eb304 in __libc_start_main csu/../csu/libc-start.c:360:3
>       #8 0x563329673630 in _start ( coreutils/src/factor+0x59630)
> (BuildId: 28b6f8b912cd8e99b886145a922476ec873a438b)/
> /|
>       During analysis of this report, I found that there are some
> numbers, like 22222222222222222202111121111, which fall into the
> function mod2 and produce cnt=0.
>       I suppose that you expect lsh2(number, 0) == number (shift by zero
> should not change the number). But inside the realization of that macro,
> with cnt=0 we have an operation (d0) >> (64 - (cnt)) which stands for
> d0>>64. This is generally undefined behavior - on some systems, the
> number d0 remains unchanged (but is expected to be 0) and on other
> systems it can be zero.
>       So, generally, the result of this operation is undefined. Although
> the result is correct for the number 22222222222222222202111121111, it
> may not be true for other numbers or architectures.
> 
> 6. Patch suggestion: I suggest just not to call lsh2 when cnt=0 to avoid
> this bug. My patch is in the attachment.
> 
> Waiting for your reply,
> Best regards,
> Nasonov Artem

Nice one!
It seems better to move the checks within the macro to avoid any future issues.
I've also applied the same check to rsh2 in the attached.

I'll apply the attached later.

Marking this as done.

thanks!
Pádraig

diff --git a/src/factor.c b/src/factor.c
index 2649e9fc6..802c05e4f 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -318,16 +318,16 @@ static void factor (uintmax_t, uintmax_t, struct factors *);
 #endif
 
 #define rsh2(rh, rl, ah, al, cnt)                                       \
-  do {                                                                  \
+  if (cnt) {                                                            \
     (rl) = ((ah) << (W_TYPE_SIZE - (cnt))) | ((al) >> (cnt));           \
     (rh) = (ah) >> (cnt);                                               \
-  } while (0)
+  } else (void) 0
 
 #define lsh2(rh, rl, ah, al, cnt)                                       \
-  do {                                                                  \
+  if (cnt) {                                                            \
     (rh) = ((ah) << cnt) | ((al) >> (W_TYPE_SIZE - (cnt)));             \
     (rl) = (al) << (cnt);                                               \
-  } while (0)
+  } else (void) 0
 
 #define ge2(ah, al, bh, bl)                                             \
   ((ah) > (bh) || ((ah) == (bh) && (al) >= (bl)))

Subject: Bug in factor utility of coreutils
From: Артем Насонов <[email-masked]>
To: [email-masked]
Cc: Виктория Егорова<[email-masked]>
Date: Wed, 25 Sep 2024 13:26:55 +0300
List-Id: <debbugs-submit.debbugs.gnu.org>

To whom it may concern,

I’m writing to let you know that I found an issue by fuzzing in 
coreutils in *factor* utility and want to report it. Here are some details:

1. Host architecture: Host it Debian x86_64 architecture
2. factor version: factor (GNU coreutils) 9.5.94-5cecd
3. Affected code area: src/factor.c:425
4. Steps to reproduce:
     Working on commit: 5cecd703e57b2e1301767d82cbe5bb01cae88472

|    export CC="clang-17"
     export CXX="clang++-17"
     export CFLAGS="-fsanitize=address,undefined -g"
     export LDFLAGS="-fsanitize=address,undefined -g"
     export 
UBSAN_OPTIONS=halt_on_error=1,abort_on_error=1,print_stacktrace=true,symbolize=true,print_stacktrace=1,report_error_type=1,symbolize=1
     ./bootstrap
     ./configure
     make
     ./src/factor 22222222222222222202111121111|

5. Bug details: during fuzzing with Undefined-Behaviour sanitizer we've 
got the following report:

|//src/factor.c:425:3: runtime error: shift exponent 64 is too large for 
64-bit type 'uintmax_t' (aka 'unsigned long')
     #0 0x56332975f862 in mod2 
/home/artemiin/Work/crash_confirmation/coreutils/src/factor.c:425:3
     #1 0x56332975ae54 in factor_using_pollard_rho2 
coreutils/src/factor.c:1665:12
     #2 0x563329750ab5 in factor  coreutils/src/factor.c:2246:9
     #3 0x56332974eed6 in print_factors_single coreutils/src/factor.c:2454:3
     #4 0x56332974dd4c in print_factors coreutils/src/factor.c:2506:11
     #5 0x56332974d20d in main  coreutils/src/factor.c:2647:15
     #6 0x7fa1933eb249 in __libc_start_call_main 
csu/../sysdeps/nptl/libc_start_call_main.h:58:16
     #7 0x7fa1933eb304 in __libc_start_main csu/../csu/libc-start.c:360:3
     #8 0x563329673630 in _start ( coreutils/src/factor+0x59630) 
(BuildId: 28b6f8b912cd8e99b886145a922476ec873a438b)/
/|
     During analysis of this report, I found that there are some 
numbers, like 22222222222222222202111121111, which fall into the 
function mod2 and produce cnt=0.
     I suppose that you expect lsh2(number, 0) == number (shift by zero 
should not change the number). But inside the realization of that macro, 
with cnt=0 we have an operation (d0) >> (64 - (cnt)) which stands for 
d0>>64. This is generally undefined behavior - on some systems, the 
number d0 remains unchanged (but is expected to be 0) and on other 
systems it can be zero.
     So, generally, the result of this operation is undefined. Although 
the result is correct for the number 22222222222222222202111121111, it 
may not be true for other numbers or architectures.

6. Patch suggestion: I suggest just not to call lsh2 when cnt=0 to avoid 
this bug. My patch is in the attachment.

Waiting for your reply,
Best regards,
Nasonov Artem
-- 

C уважением,
Артём Насонов
Специалист по анализу безопасности
Департамент анализа безопасности
Отдел динамического анализа

Эл. почта: 	[email-masked]

------------------------------------------------------------------------
Группа Астра
Сайт: astragroup.ru <https://astragroup.ru>

Группа Астра

From 014531da21b9c56a4bca5962ddd074ccb799c8df Mon Sep 17 00:00:00 2001
From: Artem Nasonov <[email-masked]>
Date: Wed, 25 Sep 2024 13:06:48 +0300
Subject: [PATCH] factor: fix undefined behaviour inside mod2 function

* src/factor.c: Avoid calling lsh2 macro with cnt=0, because of undefined-behaviour operation inside this macro. With cnt=0 d0 is shifted 64 bits to the right, which is UB.
---
 src/factor.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/factor.c b/src/factor.c
index 2649e9fc6..3cff47507 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -422,7 +422,8 @@ mod2 (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t d1, uintmax_t d0)
   count_leading_zeros (cntd, d1);
   count_leading_zeros (cnta, a1);
   int cnt = cntd - cnta;
-  lsh2 (d1, d0, d1, d0, cnt);
+  if(cnt) 
+    lsh2 (d1, d0, d1, d0, cnt);
   for (int i = 0; i < cnt; i++)
     {
       if (ge2 (a1, a0, d1, d0))
-- 
2.39.2