[Boost-bugs] [Boost C++ Libraries] #12915: Buffer overflow in boost::container::vector (affects flat_set)

Subject: [Boost-bugs] [Boost C++ Libraries] #12915: Buffer overflow in boost::container::vector (affects flat_set)
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-03-20 04:46:09

#12915: Buffer overflow in boost::container::vector (affects flat_set)
-------------------------------------+------------------------
 Reporter:  mykmartin@…              |      Owner:  igaztanaga
     Type:  Bugs                     |     Status:  new
Milestone:  To Be Determined         |  Component:  container
  Version:  Boost Development Trunk  |   Severity:  Problem
 Keywords:                           |
-------------------------------------+------------------------
 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);
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/12915>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.