bin/47374: Possible Integer Overflow in msort.c

[er.abhinav.upadhyay%gmail.com@localhost]

>Number:         47374
>Category:       bin
>Synopsis:       Possible Integer Overflow in msort.c
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    bin-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Sat Dec 29 14:45:00 +0000 2012
>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@localhost:/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)