search

embeddedartistry / libc

libc targeted for embedded systems usage. Reduced set of functionality (due to embedded nature). Chosen for portability and quick bringup.
MIT License
504 stars 67 forks source link

heapsort and heapsort_r: Undefined behavior due to out of bounds pointer arithmetic #181

Open smcpeak opened 2 years ago

smcpeak commented 2 years ago

The heapsort and heapsort_r functions both contain this code:

/*
 * Items are numbered from 1 to nmemb, so offset from size bytes
 * below the starting address.
 */
base = (char*)vbase - size;

Here, vbase is a pointer to the start of the array to sort and size is the element size. The purpose of the arithmetic is to allow base to be treated as a 1-indexed array rather than 0-indexed. But this conflicts with C11 6.5.6/8:

When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. [...] If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

Here, the result does not point to the array object (nor one past the end) because it would point to a location size bytes before the first element, hence the behavior is undefined. (For completeness: a caller could fix this by allocating extra space at the start of the array. But, for example, the tests in test/stdlib/heapsort.c do not do so.)

I am not aware of any practical adverse consequence of this. I found it because I'm building a tool to enforce some of the C pointer rules, and am applying it to this C library. The tool has a mechanism to work around specific instances, so this isn't a problem for that effort. I'm just filing this to notify you of the issue and for my own record-keeping. I won't be offended if you close it as irrelevant, although I am not advising that (or any) course of action.

phillipjohnston commented 2 years ago

I'm happy to hear about any and all such instances. Part of my goal back-in-the-day when I started this library was cleaning up long-used libc code that was worrying.