GNU bug report logs - #73474
Bug in factor utility of coreutils

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 73474 in the body.
You can then email your comments to 73474 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Артем Насонов <anasonov <at> astralinux.ru>
To: bug-coreutils <at> gnu.org
Cc: Виктория Егорова
 <vegorova <at> astralinux.ru>
Subject: Bug in factor utility of coreutils
Date: Wed, 25 Sep 2024 13:26:55 +0300

[Message part 1 (text/plain, inline)]

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 уважением,
Артём Насонов
Специалист по анализу безопасности
Департамент анализа безопасности
Отдел динамического анализа

Эл. почта: 	anasonov <at> astralinux.ru

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

Группа Астра

[Message part 2 (text/html, inline)]

[factor.c.patch (text/x-patch, attachment)]

Message #10 received at 73474-done <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Артем Насонов
 <anasonov <at> astralinux.ru>, 73474-done <at> debbugs.gnu.org
Cc: Виктория Егорова
 <vegorova <at> astralinux.ru>
Subject: Re: bug#73474: Bug in factor utility of coreutils
Date: Wed, 25 Sep 2024 16:14:42 +0100

[Message part 1 (text/plain, inline)]

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

[factor-undefined-shifts.diff (text/x-patch, attachment)]

Message #13 received at 73474 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: 73474 <at> debbugs.gnu.org, P <at> draigBrady.com, anasonov <at> astralinux.ru
Subject: Re: bug#73474: Bug in factor utility of coreutils
Date: Wed, 25 Sep 2024 12:55:44 -0700

On 2024-09-25 08:14, Pádraig Brady wrote:
> 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.

That patch doesn't suffice (nor does Artem's) because the count can be 
negative. I'll take a further look at this.

Message #16 received at 73474 <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Paul Eggert <eggert <at> cs.ucla.edu>, 73474 <at> debbugs.gnu.org,
 anasonov <at> astralinux.ru
Subject: Re: bug#73474: Bug in factor utility of coreutils
Date: Wed, 25 Sep 2024 21:48:50 +0100

On 25/09/2024 20:55, Paul Eggert wrote:
> On 2024-09-25 08:14, Pádraig Brady wrote:
>> 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.
> 
> That patch doesn't suffice (nor does Artem's) because the count can be
> negative. I'll take a further look at this.

Indeed. I had already added asserts just in case, and hit:

  $ src/factor 79228162514264337593543941441  factor: src/factor.c:427: mod2: Assertion `0 < cnt' failed.
  Aborted (core dumped)

Note factor does give the correct result on amd64 at least
without the asserts:

  $ factor 79228162514264337593543941441 | sed 's/.*: //; s/ /*/g' | bc
  79228162514264337593543941441

cheers,
Pádraig

Message #19 received at 73474-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Pádraig Brady <P <at> draigBrady.com>, anasonov <at> astralinux.ru
Cc: 73474-done <at> debbugs.gnu.org
Subject: Re: bug#73474: Bug in factor utility of coreutils
Date: Fri, 27 Sep 2024 17:50:51 -0700

[Message part 1 (text/plain, inline)]

On 2024-09-25 13:48, Pádraig Brady wrote:
> 
> Note factor does give the correct result on amd64 at least
> without the asserts:

Yes, as far as I know the existing code works correctly on all practical 
platforms. It's only pedantic/checking platforms, where shifts by 
negative or by too-large result in crashes or diagnostics, where the 
existing code fails.

The bug is easy to fix and the fixdoesn't hurt performance 
significantly, so I installed the attached. Closing the bug report.

While looking into this I got seduced by the prospect of making 'factor' 
a bit better (e.g., eliminate some recursion and fix some buffering 
issues) and installed a bunch of followup patches for 'factor'. Yeah, 
yeah, I should know better....

[0001-factor-port-to-platforms.patch (text/x-patch, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.