[Bug libstdc++/71945] New: Integer overflow in use counter of shared pointers

["gcc-bugzilla at chwress dot at" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71945

            Bug ID: 71945
           Summary: Integer overflow in use counter of shared pointers
           Product: gcc
           Version: 5.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gcc-bugzilla at chwress dot at
  Target Milestone: ---

Created attachment 38942
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=38942&action=edit
A small program demonstrating the issue

We (Fabian Yamaguchi, Christian Wressnegger, and Alwin Maier) would like
to report an integer overflow of the use counter in the `share_pointer`
object of the Standard C++ Libraries version 5.4, 6.1 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:

(1) 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.

(2) The attacker is capable of triggering the creation of a multitude of
shared objects.

(3) 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
$ ./shared_ptr_overflow

--- /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 Standard C++ Library shared pointer
(class shared_ptr : public __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 (bits/shared_ptr.h) ---

 class shared_ptr : public __shared_ptr<_Tp>)

--- /snip ---


--- snip (bits/shared_ptr_base.h) ---

template<typename _Tp, _Lock_policy _Lp>
class __shared_ptr
{
  // ...

private:

  _Tp*                 _M_ptr;         // Contained pointer.
  __shared_count<_Lp>  _M_refcount;    // Reference counter.         (!)
};


// ...

template<_Lock_policy _Lp = __default_lock_policy>
class _Sp_counted_base
: public _Mutex_base<_Lp>
{
private:  
  _Sp_counted_base(_Sp_counted_base const&) = delete;
  _Sp_counted_base& operator=(_Sp_counted_base const&) = delete;

  _Atomic_word  _M_use_count;     // #shared                         (A)
  _Atomic_word  _M_weak_count;    // #weak + (#shared != 0)

public:  
  _Sp_counted_base() noexcept
  : _M_use_count(1), _M_weak_count(1) { }

  virtual
  ~_Sp_counted_base() noexcept
  { }

  // Called when _M_use_count drops to zero, to release the resources
  // managed by *this.
  virtual void
  _M_dispose() noexcept = 0;

  // Called when _M_weak_count drops to zero.
  virtual void
  _M_destroy() noexcept
  { delete this; }

  virtual void*
  _M_get_deleter(const std::type_info&) noexcept = 0;

  void
  _M_add_ref_copy()
  { __gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1); }            (B)

  void
  _M_add_ref_lock();

  bool
  _M_add_ref_lock_nothrow();

  void
  _M_release() noexcept
  {
    // Be race-detector-friendly.  For more info see bits/c++config.
    _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
    if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
    {
      _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
      _M_dispose();                                                  (C)
      // ...
    }
  }
};

--- /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 -- _Atomic_word
is defined as `int` on amd64, for instance) 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.