NetBSD Problem Report #47374

From www@NetBSD.org  Sat Dec 29 14:40:31 2012
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [149.20.53.66])
	by www.NetBSD.org (Postfix) with ESMTP id 6270F63EB00
	for <gnats-bugs@gnats.NetBSD.org>; Sat, 29 Dec 2012 14:40:31 +0000 (UTC)
Message-Id: <20121229144030.35D1C63EB00@www.NetBSD.org>
Date: Sat, 29 Dec 2012 14:40:30 +0000 (UTC)
From: er.abhinav.upadhyay@gmail.com
Reply-To: er.abhinav.upadhyay@gmail.com
To: gnats-bugs@NetBSD.org
Subject: Possible Integer Overflow in msort.c
X-Send-Pr-Version: www-1.0

>Number:         47374
>Category:       bin
>Synopsis:       Possible Integer Overflow in msort.c
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    bin-bug-people
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Sat Dec 29 14:45:00 +0000 2012
>Closed-Date:    Tue May 31 07:22:14 +0000 2016
>Last-Modified:  Tue May 31 07:22:14 +0000 2016
>Originator:     Abhinav Upadhyay
>Release:        CURRENT
>Organization:
>Environment:
NetBSD  6.99.15 NetBSD 6.99.15 (GENERIC) #0: Fri Nov 30 23:27:05 UTC 2012  builds@b6.netbsd.org:/home/builds/ab/HEAD/i386/201211301540Z-obj/home/builds/ab/HEAD/src/sys/arch/i386/compile/GENERIC i386
>Description:
This came up during a discussion with Dhruv Matani (@dhruvbird) over Twitter. There seems to be a chance of an integer overflow in the implementation of merge sort in src/usr.bin/sort. 

The for loop in the insert function in msort.c has the potential of an integer overflow (during the calculation of mid).

static int
insert(struct mfile **flist, struct mfile *rec, int ttop, int delete)
{
    int mid, top = ttop, bot = 0, cmpv = 1;

    for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
>How-To-Repeat:

>Fix:
Index: msort.c
===================================================================
RCS file: /cvsroot/src/usr.bin/sort/msort.c,v
retrieving revision 1.30
diff -u -r1.30 msort.c
--- msort.c    5 Feb 2010 21:58:42 -0000    1.30
+++ msort.c    26 Dec 2012 17:52:28 -0000
@@ -307,7 +307,7 @@
 {
     int mid, top = ttop, bot = 0, cmpv = 1;

-    for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
+    for (mid = top / 2; bot + 1 != top; mid = bot + (top - bot) / 2) {
         cmpv = cmp(rec->rec, flist[mid]->rec);
         if (cmpv == 0 ) {
             if (UNIQUE)

>Release-Note:

>Audit-Trail:
From: David Laight <david@l8s.co.uk>
To: gnats-bugs@NetBSD.org
Cc: gnats-admin@netbsd.org, netbsd-bugs@netbsd.org
Subject: Re: bin/47374: Possible Integer Overflow in msort.c
Date: Sat, 29 Dec 2012 20:27:00 +0000

 On Sat, Dec 29, 2012 at 02:45:01PM +0000, er.abhinav.upadhyay@gmail.com wrote:
 > >Number:         47374
 > >Category:       bin
 > >Synopsis:       Possible Integer Overflow in msort.c
 ...
 > >Description:
 > This came up during a discussion with Dhruv Matani (@dhruvbird) over Twitter. There seems to be a chance of an integer overflow in the implementation of merge sort in src/usr.bin/sort. 
 > 
 > The for loop in the insert function in msort.c has the potential of an integer overflow (during the calculation of mid).
 > 
 > static int
 > insert(struct mfile **flist, struct mfile *rec, int ttop, int delete)
 > {
 >     int mid, top = ttop, bot = 0, cmpv = 1;
 > 
 >     for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {

 No it doesn't.
 The calculated number is an index into an in-memory array of records.
 There is no way that the array is going to have more than MAXINT/2
 entries.

 I can't remember off-hand what actually limits the array (it might
 be the number of files in the merge), but it can't be anywhere
 near MAXINT/2.

 	David

 -- 
 David Laight: david@l8s.co.uk

State-Changed-From-To: open->closed
State-Changed-By: pgoyette@NetBSD.org
State-Changed-When: Tue, 31 May 2016 07:22:14 +0000
State-Changed-Why:
Determined not to be a problem.


>Unformatted:

Home	PR Database Search