Subject: bug#75606: closed (Re: bug#75606: undefined behaviour in sort.c)

From: [email-masked] (GNU bug Tracking System)
Date: Thu, 16 Jan 2025 17:25:02 +0000

Your bug report

#75606: undefined behaviour in sort.c

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].

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

Subject: Re: bug#75606: undefined behaviour in sort.c
From: Paul Eggert <[email-masked]>
To: Bruno Haible <[email-masked]>
Cc: [email-masked]
Date: Thu, 16 Jan 2025 09:24:29 -0800
List-Id: <debbugs-submit.debbugs.gnu.org>

Thanks for reporting that. I installed the attached to fix it.

From e07161d4af89dbf82311ca396ac0916aa90b7301 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Thu, 16 Jan 2025 09:20:45 -0800
Subject: [PATCH] sort: fix --debug buffer overrun

* src/sort.c (debug_key): Fix undefined behavior when a key ends
before it starts.  Problem reported by Bruno Haible
<https://bugs.gnu.org/75606>.
---
 src/sort.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/src/sort.c b/src/sort.c
index 997566240..0928fd57c 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -2373,7 +2373,11 @@ debug_key (struct line const *line, struct keyfield const *key)
       if (key->sword != SIZE_MAX)
         beg = begfield (line, key);
       if (key->eword != SIZE_MAX)
-        lim = limfield (line, key);
+        {
+          lim = limfield (line, key);
+          /* Treat field ends before field starts as empty fields.  */
+          lim = MAX (beg, lim);
+        }
 
       if ((key->skipsblanks && key->sword == SIZE_MAX)
           || key->month || key_numeric (key))
-- 
2.45.2

Subject: undefined behaviour in sort.c
From: Bruno Haible <[email-masked]>
To: [email-masked]
Date: Thu, 16 Jan 2025 17:18:53 +0100
List-Id: <debbugs-submit.debbugs.gnu.org>

Testing the current coreutils with the current gnulib, there is an
undefined behaviour in sort.c, in or around the functions
  debug_line
  debug_key
  debug_width

 ------------------------------------------------------------------------------

Found by building on Ubuntu 24.04, with clang 19,

CC="clang -fsanitize=address,undefined,signed-integer-overflow,shift,integer-divide-by-zero -fno-sanitize-recover=undefined"

and running the test suite. The log shows this:

+ printf 'A\tchr10\nB\tchr1\n'
+ sort -s -k2.4b,2.3n --debug
sort: text ordering performed using simple byte comparison
sort: leading blanks are significant in key 1; consider also specifying 'b'
sort: note numbers use '.' as a decimal point in this locale
../lib/mbswidth.c:60:26: runtime error: addition of unsigned offset to 0x76f80b601805 overflowed to 0x76f80b601804
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../lib/mbswidth.c:60:26 
../tests/sort/sort-debug-keys.sh: line 292: 345166 Done                    printf 'A\tchr10\nB\tchr1\n'
     345167 Aborted                 | sort -s -k2.4b,2.3n --debug

 ------------------------------------------------------------------------------

How to reproduce without clang and UBSAN:

$ printf 'A\tchr10\nB\tchr1\n' > in
$ gdb src/sort
(gdb) break mbsnwidth
(gdb) run -s -k2.4b,2.3n --debug < in

The first time the mbsnwidth function is invoked:
Breakpoint 1, mbsnwidth (string=0x51d000000a80 "A\tchr10", nbytes=5, flags=0) at ../lib/mbswidth.c:59

The second time the mbsnwidth function is invoked:
Breakpoint 1, mbsnwidth (string=0x51d000000a85 "10", nbytes=18446744073709551615, flags=0) at ../lib/mbswidth.c:59

The nbytes value is obviously bogus. The documentation of mbsnwidth() says:
  /* Returns the number of screen columns needed for the NBYTES bytes
     starting at BUF.  */
  extern int mbsnwidth (const char *buf, size_t nbytes, int flags);

Stack trace at the second invocation:

(gdb) where
#0  mbsnwidth (string=0x51d000000a85 "10", nbytes=18446744073709551615, flags=0) at ../lib/mbswidth.c:59
#1  0x00005555556bff9e in debug_width (text=0x51d000000a85 "10", lim=0x51d000000a84 "r10") at ../src/sort.c:2326
#2  0x00005555556bfee6 in debug_key (line=0x51d000001280, key=0x5070000001e0) at ../src/sort.c:2415
#3  0x00005555556beabc in debug_line (line=0x51d000001280) at ../src/sort.c:2427
#4  0x00005555556b487f in write_line (line=0x51d000001280, fp=0x7ffff78045c0 <_IO_2_1_stdout_>, output_file=0x0) at ../src/sort.c:2942
#5  0x00005555556cc3be in write_unique (line=0x51d000001280, tfp=0x7ffff78045c0 <_IO_2_1_stdout_>, temp_output=0x0) at ../src/sort.c:3577
#6  0x00005555556d15c8 in mergelines_node (node=0x51d000001500, total_lines=2, tfp=0x7ffff78045c0 <_IO_2_1_stdout_>, temp_output=0x0)
    at ../src/sort.c:3624
#7  0x00005555556cf27f in merge_loop (queue=0x7ffff59096c0, total_lines=2, tfp=0x7ffff78045c0 <_IO_2_1_stdout_>, temp_output=0x0)
    at ../src/sort.c:3708
#8  0x00005555556cbff7 in sortlines (lines=0x51d0000012a0, nthreads=8, total_lines=2, node=0x51d000001500, queue=0x7ffff59096c0, 
    tfp=0x7ffff78045c0 <_IO_2_1_stdout_>, temp_output=0x0) at ../src/sort.c:3825
#9  0x00005555556ae58f in sort (files=0x502000000418, nfiles=0, output_file=0x0, nthreads=8) at ../src/sort.c:4124
#10 0x00005555556a2d20 in main (argc=4, argv=0x7fffffffd0c8) at ../src/sort.c:4900

Bruno