id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
12915,Buffer overflow in boost::container::vector (affects flat_set),mykmartin@…,Ion Gaztañaga,"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:

{{{#!c++
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:

{{{#!c++
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:

{{{#!c++
std::size_t index_capacity = (aligned_addr >= capaddr) ? 0u : (capaddr - aligned_addr)/sizeof(size_type);
}}}
",Bugs,closed,To Be Determined,container,Boost Development Trunk,Problem,fixed,,fdegros@…