Buffer overflow in boost::container::vector (affects flat_set)

[mykmartin@…]

boost::container::flat_set's ranged insert with ordered_unique_range_t uses vector::priv_merge to perform the insertion. The implementation of vector::priv_merge contains a buffer overflow bug for some combinations of inputs.

(Note: trac won't let me submit this with links to the source on github, so for future reference the line numbers are referring to commit 1261ac33089cbc08108b4beaed97f307270892a8 of boost/container/vector.hpp)

Line 2260 in vector.hpp calculates whether there is enough spare space in the vector's storage buffer to hold index values used during the merge operation:

std::size_t index_capacity = (aligned_addr >= capaddr) ? 0u : (capaddr - addr)/sizeof(size_type);

• addr = start address of buffer + num of currently stored values (s) + num of new values to add (n)
• aligned_addr = addr rounded up to the memory alignment boundary for size_type (typically 8)
• capaddr = end address of buffer (start address + capacity)

When the byte size of the elements being stored is not a multiple of sizeof(size_type), the calculation of index_capacity can overestimate the available spare space. The attached test case uses a flat_set containing 4-byte integers and has the following layout for the ordered_unique_range insertion (numbers are element counts, not bytes):

  <-       capacity=623         ->
  +-------------+----------------+
  |    s=311    |    free=312    |
  +-------------+----------------+
                +---------+ :    :
                |  n=118  | :    :
                +---------+ :    ^ capaddr
                          : :
                     addr ^ ^ aligned_addr (= addr + 4 bytes)

The 8-byte index values are stored using an 8-byte aligned pointer (size_type *position in priv_insert_ordered_range). This is correctly initialised to aligned_addr but the index_capacity is incorrectly calculated using addr; it should use aligned_addr:

capaddr - addr         = 776 bytes / 8 = 97.0
capaddr - aligned_addr = 772 bytes / 8 = 96.5

The actual spare capacity is 96 index values of 8 bytes each, with a slack of 4 bytes. The code attempts to write 97 elements and overflows at line 2307. To detect the overflow, pass capaddr to priv_insert_ordered_range and add an assert before that line:

assert(boost::uintptr_t(position) + sizeof(size_type) < capaddr);
*position = static_cast<size_type>(pcur - pbeg);

The fix for this is to replace addr with aligned_addr in line 2260:

std::size_t index_capacity = (aligned_addr >= capaddr) ? 0u : (capaddr - aligned_addr)/sizeof(size_type);

[mykmartin@…]

Minor correction: the assert to show the problem should use <=:

assert(boost::uintptr_t(position) + sizeof(size_type) <= capaddr);

[fdegros@…]

Ping? Any progress on this ticket? The diagnosis and fix have been provided by the original reporter. Is the fix making its way into new releases of Boost Containers?

[karl.tarbe@…]

I might have also run into this. Why is this bug still new?

[Ion Gaztañaga]

vector's merge implementation was rewritten some releases ago. Provided overflow.cc correctly works under current develop branch with gcc with ASAN+UBSAN.

[karl.tarbe@…]

When run with valgrind: invalid write of size 8

[karl.tarbe@…]

Log of valgrind output

[karl.tarbe@…]

I have attached test.cpp and log of valgrind output on it.

I am using Arch linux with boost 1.67.0-4 and gcc 8.1.1+20180531-1

This might be a separate bug, but I am not sure.

[Ion Gaztañaga]

Thanks for the new test case, it's a separate bug, working on it.

[Ion Gaztañaga]

Looks like the following commit:

​https://github.com/boostorg/move/commit/ddeb2341271583d25a0a9974d339b519b8e18dc9

fixes the issue. Will be released in 1.68.

[karl.tarbe@…]

Thank you for quickly addressing the issue.

[karl.tarbe@…]

I have one follow-up question. Which Boost versions are affected by this (the one I provided the test case for) bug.

So I can use BOOST_VERSION to switch between workaround (insert one-by-one) and the faster method.

[Ion Gaztañaga]

There were other bugs related to this in Boost 1.67, so I would say soon to be released version 1.68 will be safe.

[Ion Gaztañaga]

Closing the bug.