Bug#732042: Buffer overflow in std::nth_element()

[Max Kellermann <max@duempel.org>]

Package: libstdc++-4.8-dev
Version: 4.8.2-1
Severity: important

Demo exploit:

 #include <algorithm>
 int main(int argc, char **argv) {
     static int data[] = {3,5,4,1,0,2};
     std::nth_element(data + 0, data + 3, data + 6, std::less<int>());
 }

Crashes:

 g++ -std=c++11 test.cxx && ./a.out
 Segmentation fault

Full backtrace:

 #0  0x0000000000400b14 in std::less<int>::operator() (this=0x7fffffffe500, __x=@0x602000: <error reading variable>, __y=@0x601aa8: 5) at /usr/include/c++/4.8/bits/stl_function.h:235
 No locals.
 #1  0x0000000000400d33 in std::__unguarded_partition<int*, int, std::less<int> > (__first=0x602000, __last=0x601ab8 <completed.6392>, __pivot=@0x601aa8: 5, __comp=...) at /usr/include/c++/4.8/bits/stl_algo.h:2263
 No locals.
 #2  0x0000000000400978 in std::__unguarded_partition_pivot<int*, std::less<int> > (__first=0x601aa8 <main::data+8>, __last=0x601ab8 <completed.6392>, __comp=...) at /usr/include/c++/4.8/bits/stl_algo.h:2296
         __mid = 0x601ab0 <main::data+16>
 #3  0x00000000004007f8 in std::__introselect<int*, long, std::less<int> > (__first=0x601aa8 <main::data+8>, __nth=0x601aac <main::data+12>, __last=0x601ab8 <completed.6392>, __depth_limit=2, __comp=...) at /usr/include/c++/4.8/bits/stl_algo.h:2394
         __cut = 0x601aa8 <main::data+8>
 #4  0x000000000040077b in std::nth_element<int*, std::less<int> > (__first=0x601aa0 <main::data>, __nth=0x601aac <main::data+12>, __last=0x601ab8 <completed.6392>, __comp=...) at /usr/include/c++/4.8/bits/stl_algo.h:5417
 No locals.
 #5  0x00000000004006e3 in main (argc=1, argv=0x7fffffffe718) at test.cxx:4
         data = {1, 0, 5, 3, 4, 2}

Valgrind output:

 ==31432== Invalid read of size 4
 ==31432==    at 0x400B14: std::less<int>::operator()(int const&, int const&) const (stl_function.h:235)
 ==31432==    by 0x400D32: int* std::__unguarded_partition<int*, int, std::less<int> >(int*, int*, int const&, std::less<int>) (stl_algo.h:2263)
 ==31432==    by 0x400977: int* std::__unguarded_partition_pivot<int*, std::less<int> >(int*, int*, std::less<int>) (stl_algo.h:2296)
 ==31432==    by 0x4007F7: void std::__introselect<int*, long, std::less<int> >(int*, int*, int*, long, std::less<int>) (stl_algo.h:2394)
 ==31432==    by 0x40077A: void std::nth_element<int*, std::less<int> >(int*, int*, int*, std::less<int>) (stl_algo.h:5417)
 ==31432==    by 0x4006E2: main (test.cxx:4)
 ==31432==  Address 0x602000 is not stack'd, malloc'd or (recently) free'd

Same problem with clang 2.2 using libstdc++ 4.8.2 (library bug, not
compiler bug):

 clang++ -std=c++11 test.cxx && ./a.out
 Segmentation fault

No crash with clang++-libc++, because this uses libc++ instead of
libstdc++.

This appears like an important bug to me, because it is possible to
craft a "malicious" file and inject it in a vulnerable binary that was
compiled with this library; since this overwrites data outside a
buffer, it may be used to inject code remotely.  This affects one
project I maintain, and compiling with this library crashes my program
all the time.  Upgrading just the library package does not help, all
programs need to be recompiled, because this bug is in inlined
template code.