[PATCH] stdlib-bsearch: middle element calculation may overflow

[Zack Weinberg]

On Tue, Mar 28, 2017 at 6:19 AM, Ondřej Bílka <neleai@seznam.cz> wrote:
> On Thu, Mar 16, 2017 at 04:54:40PM -0400, Mike Frysinger wrote:
>> if you see a comment by Ulrich that looks to be unrelated/off, then you
>> can probably safely assume it is.  if the bug is open still, then we
>> usually consider it *now* to be something worth fixing.
>
> No, this is wrong fix as I probably write before. It isn't visible bug
> unless programmer is idiot who tries to sort gigabyte long array of
> single bytes and use binary search on it. Just keeping 256 byte table of positions
> would be more effective than sorting.

There's another possibility: a program might be tricked into calling
bsearch with the wrong arguments for the array it actually wants to
search.  If I understand the problem correctly, under the right
conditions bsearch could return a pointer outside the bounds of the
true (quite small) array.

Because of that, I think this qualifies as a must-fix bug and as a
potential security vulnerability.

> For any bigger size there isn't overflow as difference between that
> pointers is bounded.

It's unfortunate that there is no good way of making that apparent to
the compiler.  The relationship among base, nmemb, size, and the
address space as a whole is just too complicated.  Maybe if we were
actually doing pointer arithmetic on a nonce type - but that has its
own problems.

> This fix takes extra instruction which would harm performance for basically everybody for nonexistent problem.

As a meta concern: it is possible to disagree with people without
being this hostile.  You could have said "I don't think this is worth
doing, because it makes all uses of bsearch slower to handle a corner
case that will essentially never occur in practice" - same message,
avoids elevating your personal opinon to the status of a fact, and
avoids blowing off someone who cared enough to write a patch.

Please strive to do better in the future.

zw