Global buffer overflow in ``qsort`` and ``select``

[shijiameng]

Overview

Benchmark qsort and select use array length as index, causing global buffer overflow.

Bug Description

qsort

Buggy code: src/qsort/libqsort.c#107

float arr[20] = {
  5, 4, 10.3, 1.1, 5.7, 100, 231, 111, 49.5, 99,
  10, 150, 222.22, 101, 77, 44, 35, 20.54, 99.99, 88.88
};
...
void sort(unsigned long n)
{
	unsigned long i,ir=n,j,k,l=1;  // NOTE: ir is initialized as the length of arr (i.e., 20)
	int jstack=0;
	float a,temp;

	for (;;) {
		if (ir-l < M) {
			...
		} else {
			k=(l+ir) >> 1;
			SWAP(arr[k],arr[l+1])
                        if (arr[l] > arr[ir]) { // Line 107: arr[ir] causes global buffer overflow
				SWAP(arr[l],arr[ir])
			}
			...
		}
	}
}

select

Buggy code: src/select/libselect.c#63

float arr[20] = {
  5, 4, 10.3, 1.1, 5.7, 100, 231, 111, 49.5, 99,
  10, 150, 222.22, 101, 77, 44, 35, 20.54, 99.99, 888.88
};
...
float select(unsigned long k, unsigned long n)
{
	unsigned long i,ir,j,l,mid;
	float a,temp;
	int flag, flag2;

	l=1;
	ir=n;   // NOTE: ir is initialized as the length of arr (i.e., 20)
	flag = flag2 = 0;
	while (!flag) {
		if (ir <= l+1) {
			...
		} else if (!flag) {
			mid=(l+ir) >> 1;
			SWAP(arr[mid],arr[l+1])
			if (arr[l+1] > arr[ir]) {  // Line 63: arr[ir] causes global buffer overflow 
				SWAP(arr[l+1],arr[ir])
			}
			...
		}

	}
	return arr[k];
}