Re: New GNU C Library (glibc) security flaw reported on 30 Jan 2024

[Paul Eggert <eggert@cs.ucla.edu>]

[-- Attachment #1: Type: text/plain, Size: 1299 bytes --]

On 2/6/24 07:00, Zack Weinberg wrote:

> This sentence only makes sense to me because of what you said in the
> cover letter, about the array not being required to be totally
> ordered.  I’d like to suggest instead

Good point about saying explicitly that the array need not be sorted. We 
can add "Although the @var{array} need not be completely sorted,". Done 
in the attached revised patch.

However, the paraphrase you sent was too generous, as it allowed the 
array to be in completely random order if it had no matching element. 
Although I think glibc bsearch works in that case, we're likely better 
off sticking with POSIXish wording.


> Not related to what you wrote, but: A later paragraph says “the object
> addresses passed to the comparison function lie within the array,”
> and C2011 7.22.5p2 actually makes this a hard requirement: “The
> implementation shall ensure that both arguments [of the comparison
> function called by qsort] are pointers to elements of the array.”
> It looks to me like there are situations where our implementation
> doesn’t do this:

I don't see that in the glibc source. Are you sure about that?

If glibc qsort passes addresses outside the array to the comparison 
function, then it's busted and should get fixed.

[-- Attachment #2: 0001-Fix-bsearch-qsort-etc.-doc-to-match-POSIX-better.patch --]
[-- Type: text/x-patch, Size: 4455 bytes --]

From 22837cc7c7f2ab98b823e620c1fa122cd9ad2afa Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 4 Feb 2024 16:53:22 -0800
Subject: [PATCH v2] Fix bsearch, qsort etc. doc to match POSIX better
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* manual/search.texi (Array Search Function):
Correct the statement about lfind’s mean runtime:
it is proportional to a number (not that number),
and this is true only if random elements are searched for.
Relax the constraint on bsearch’s array argument:
POSIX says it need not be sorted, only partially sorted.
Say that the first arg passed to bsearch’s comparison function
is the key, and the second arg is an array element, as
POSIX requires.  For bsearch and qsort, say that the
comparison function should not alter the array, as POSIX
requires.  For qsort, say that the comparison function
must define a total order, as POSIX requires.
---
 manual/search.texi | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

diff --git a/manual/search.texi b/manual/search.texi
index db577a5332..f3de84401d 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -84,8 +84,9 @@ The return value is a pointer to the matching element in the array
 starting at @var{base} if it is found.  If no matching element is
 available @code{NULL} is returned.
 
-The mean runtime of this function is @code{*@var{nmemb}}/2.  This
-function should only be used if elements often get added to or deleted from
+The mean runtime of this function is proportional to @code{*@var{nmemb}/2},
+assuming random elements of the array are searched for.  This
+function should be used only if elements often get added to or deleted from
 the array in which case it might not be useful to sort the array before
 searching.
 @end deftypefun
@@ -122,24 +123,27 @@ bytes.  If one is sure the element is in the array it is better to use
 calling @code{lsearch}.
 @end deftypefun
 
-To search a sorted array for an element matching the key, use the
-@code{bsearch} function.  The prototype for this function is in
+To search a sorted or partially sorted array for an element matching the key,
+use the @code{bsearch} function.  The prototype for this function is in
 the header file @file{stdlib.h}.
 @pindex stdlib.h
 
 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
 @standards{ISO, stdlib.h}
 @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
-The @code{bsearch} function searches the sorted array @var{array} for an object
+The @code{bsearch} function searches @var{array} for an object
 that is equivalent to @var{key}.  The array contains @var{count} elements,
 each of which is of size @var{size} bytes.
 
 The @var{compare} function is used to perform the comparison.  This
-function is called with two pointer arguments and should return an
+function is called with arguments that point to the key and to an
+array element, in that order, and should return an
 integer less than, equal to, or greater than zero corresponding to
-whether its first argument is considered less than, equal to, or greater
-than its second argument.  The elements of the @var{array} must already
-be sorted in ascending order according to this comparison function.
+whether the key is considered less than, equal to, or greater than
+the array element.  The function should not alter the array's contents.
+Although the @var{array} need not be completely sorted,
+it must consist of all elements that compare less than,
+equal to, and greater than @var{key}, in that order.
 
 The return value is a pointer to the matching array element, or a null
 pointer if no match is found.  If the array contains more than one element
@@ -170,7 +174,9 @@ The @var{compare} function is used to perform the comparison on the
 array elements.  This function is called with two pointer arguments and
 should return an integer less than, equal to, or greater than zero
 corresponding to whether its first argument is considered less than,
-equal to, or greater than its second argument.
+equal to, or greater than its second argument.  The function should
+be consistent with a total ordering on the array elements' values,
+and should not alter the array's contents.
 
 @cindex stable sorting
 @strong{Warning:} If two objects compare as equal, their order after
-- 
2.43.0