Home Dashboard Directory Help
Search

Check inside std::vector::_Reserve() triggers integer underflow and fails to detect invalid parameter passed to std::vector::resize() by Dmitry Me


Status: 

Closed
 as Fixed Help for as Fixed


1
0
Sign in
to vote
Type: Bug
ID: 694663
Opened: 10/13/2011 12:45:29 AM
Access Restriction: Public
Moderator Decision: Sent to Engineering Team for consideration
0
Workaround(s)
view
0
User(s) can reproduce this bug

Description

As of version 10.0.40219.1 SP1Rel std::vector::_Reserve() contains the following code:

size_type _Size = size();
if (max_size() - _Count < _Size)
_Xlen();

which has potential for arithmetic undeflow. For example, in this code:

int _tmain(int /*argc*/, _TCHAR* /*argv*/[])
{
    std::vector<int> vec;
    vec.resize( vec.max_size() + 1 );
}

restriction "_Size + _Count <= max_size()" is clearly violated, yet _Xlen() is not called from that code - instead code proceeds to "else if", then to the "else", then reserve() is called and _Xlen() is called from inside reserve().

The reason is the following. The intention was to compute (_Size+_Count) is such way that it doesn't overflow. There were two options to do that - either check that "max_size()-_Size<_Count" or check that "max_size()-_Count < Size".

The difference is that when checking "max_size()-_Size<_Count" there's a guarantee that "max_size()>= _Size" and therefore there's no risk of underflow. Meanwhile when checking "max_size()-_Count < Size" there's no such guarantee - _Count can have whatever value and that value can exceed "max_size()" and cause an underflow during subtraction.

Because of that the check doesn't work in certain cases, including one in the code snippet above. This check should be rewrtitten.
Details
Sign in to post a comment.
Posted by Dmitry Me on 11/6/2011 at 9:51 PM
Thanks a lot for fixing this and other items in std::vector source code.
Posted by Microsoft on 11/4/2011 at 9:05 PM
Hi,

Thanks for reporting this bug. We've fixed it, and the fix will be available in VC11.

If you're curious, here's my new implementation of _Reserve():

size_type _Unused_capacity() const _NOEXCEPT
    {    // micro-optimization for capacity() - size()
    return (this->_Myend - this->_Mylast);
    }

void _Reserve(size_type _Count)
    {    // ensure room for _Count new elements, grow exponentially
    if (_Unused_capacity() < _Count)
        {
        if (max_size() - size() < _Count)
            _Xlen();
        _Reallocate(_Grow_to(size() + _Count));
        }
    }

If you have any further questions, feel free to E-mail me at stl@microsoft.com .

Stephan T. Lavavej
Visual C++ Libraries Developer
Posted by MS-Moderator10 [Feedback Moderator] on 10/13/2011 at 1:56 AM
Thank you for submitting feedback on Visual Studio 2010 and .NET Framework. Your issue has been routed to the appropriate VS development team for investigation. We will contact you if we require any additional information.
Posted by MS-Moderator01 on 10/13/2011 at 1:45 AM
Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(http://support.microsoft.com)
Sign in to post a workaround.