https://svn.boost.org/trac10/ticket/12915 <p> 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. </p> <p> (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) </p> <p> 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: </p> <div class="wiki-code"><div class="code"><pre><span class="n">std</span><span class="o">::</span><span class="kt">size_t</span> <span class="n">index_capacity</span> <span class="o">=</span> <span class="p">(</span><span class="n">aligned_addr</span> <span class="o">&gt;=</span> <span class="n">capaddr</span><span class="p">)</span> <span class="o">?</span> <span class="mi">0u</span> <span class="o">:</span> <span class="p">(</span><span class="n">capaddr</span> <span class="o">-</span> <span class="n">addr</span><span class="p">)</span><span class="o">/</span><span class="k">sizeof</span><span class="p">(</span><span class="n">size_type</span><span class="p">);</span> </pre></div></div><ul><li>addr = start address of buffer + num of currently stored values (s) + num of new values to add (n) </li><li>aligned_addr = addr rounded up to the memory alignment boundary for size_type (typically 8) </li><li>capaddr = end address of buffer (start address + capacity) </li></ul><p> 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): </p> <pre class="wiki"> &lt;- capacity=623 -&gt; +-------------+----------------+ | s=311 | free=312 | +-------------+----------------+ +---------+ : : | n=118 | : : +---------+ : ^ capaddr : : addr ^ ^ aligned_addr (= addr + 4 bytes) </pre><p> 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: </p> <pre class="wiki">capaddr - addr = 776 bytes / 8 = 97.0 capaddr - aligned_addr = 772 bytes / 8 = 96.5 </pre><p> 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: </p> <div class="wiki-code"><div class="code"><pre><span class="n">assert</span><span class="p">(</span><span class="n">boost</span><span class="o">::</span><span class="kt">uintptr_t</span><span class="p">(</span><span class="n">position</span><span class="p">)</span> <span class="o">+</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">size_type</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">capaddr</span><span class="p">);</span> <span class="o">*</span><span class="n">position</span> <span class="o">=</span> <span class="k">static_cast</span><span class="o">&lt;</span><span class="n">size_type</span><span class="o">&gt;</span><span class="p">(</span><span class="n">pcur</span> <span class="o">-</span> <span class="n">pbeg</span><span class="p">);</span> </pre></div></div><p> The fix for this is to replace addr with aligned_addr in line 2260: </p> <div class="wiki-code"><div class="code"><pre><span class="n">std</span><span class="o">::</span><span class="kt">size_t</span> <span class="n">index_capacity</span> <span class="o">=</span> <span class="p">(</span><span class="n">aligned_addr</span> <span class="o">&gt;=</span> <span class="n">capaddr</span><span class="p">)</span> <span class="o">?</span> <span class="mi">0u</span> <span class="o">:</span> <span class="p">(</span><span class="n">capaddr</span> <span class="o">-</span> <span class="n">aligned_addr</span><span class="p">)</span><span class="o">/</span><span class="k">sizeof</span><span class="p">(</span><span class="n">size_type</span><span class="p">);</span> </pre></div></div> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/12915 Trac 1.4.3 mykmartin@… Mon, 20 Mar 2017 04:48:01 GMT https://svn.boost.org/trac10/ticket/12915 https://svn.boost.org/trac10/ticket/12915 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">overflow.cc</span> </li> </ul> Ticket mykmartin@… Sun, 26 Mar 2017 22:57:46 GMT https://svn.boost.org/trac10/ticket/12915#comment:3 https://svn.boost.org/trac10/ticket/12915#comment:3 <ul> <li><strong>cc</strong> <span class="trac-author">fdegros@…</span> added </li> </ul> Ticket karl.tarbe@… Wed, 20 Jun 2018 09:09:44 GMT https://svn.boost.org/trac10/ticket/12915 https://svn.boost.org/trac10/ticket/12915 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">test.cpp</span> </li> </ul> <p> When run with valgrind: invalid write of size 8 </p> Ticket karl.tarbe@… Tue, 26 Jun 2018 23:07:05 GMT https://svn.boost.org/trac10/ticket/12915 https://svn.boost.org/trac10/ticket/12915 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">log</span> </li> </ul> <p> Log of valgrind output </p> Ticket karl.tarbe@… Tue, 26 Jun 2018 23:10:15 GMT https://svn.boost.org/trac10/ticket/12915#comment:12 https://svn.boost.org/trac10/ticket/12915#comment:12 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> Closing the bug. </p> Ticket