Saturday, June 20, 2009

Fun with erase()

Over the last few months I've been knee deep in C++, you can view this as good thing or a bad thing, I for one enjoy it. I personally like finding bugs in C++ applications, as they are usually more complex then plain old C and require a bit more thought:
  • Keeping track of what variables your destructor will take care of, and which it wont
  • Iterators, and what methods invalidate them
  • (insert your favorite C++ gotcha here)
While debugging a crash one day it occured to me that the security research community has paid very little attention to the STL and CPPism's in general. There are a few things out there like TAOSSA's delete vs delete[] and of course there is also Cert's secure coding standards. But there is very little written on exploring STL specific bugs. Maybe its all private and im just not cool enough to see it :/

I decided to document some ways STL specific bugs may be exploited. The first place I looked was containers, you know vectors/queues/lists etc... Any use of these containers probably means lots of interesting data is being stored, and considering they all have very easy-to-use methods even novice C++ developers were (ab)using them somewhere.
Most of these methods take in iterators (don't let the name fool you, they're just pointers), and tainted iterators have been a known bad thing for a long time (read certs secure coding standards). But where were the exploits? Where were the how-to's on owning an attacker influenced iterator? I decided to look into it myself.
I settled on using vectors as my first topic of interest, as they are widely used for their efficiency and ease of use. I further focused my efforts by looking at any method that added/moved/deleted multiple elements of data at a time from a container. The erase method seemed like a good candidate considering the amount of memory copies that take place under the hood.
The erase method either takes a single position within the container and removes it, or it takes a range supplied by two iterators and deletes the elements within that range. But I needed to see what it looked like under the hood. After navigating the tangled mess that is the GNU C++ templates (this is probably the real reason no one has done a lot of STL security research) I was able to isolate the relevant erase() code and find what I was looking for.
This is where you are probably getting bored, so I'll skip ahead and just tell you why you care about any of this.
Tainted iterators are a known C++ gotcha that every code auditor should know about, but in certain situations they can lead to very interesting conditions for an exploit writer. The Cert secure coding standard begins to touch on the subject of invalid iterator ranges, but labels their 'undefined behavior' as equivalent to a buffer overflow. This is true, however it can be more then that depending onthe STL implementation. When an attacker can control the range iterators passed to erase() he may be able to leak or directly overwrite memory contents or even better he can trick the STL into resizing the container to encapsulate adjacent heap memory (think 'other containers'). This opens up all kinds of doors for creative exploitation.

I would love to post those details here, but blogger mangled my write up pretty bad. So I've uploaded it here. If you spot any inaccurate technical information please let me know.


jf said...

a few years ago during an audit I ran across an case where a multi-threaded app was passing an instance of one of the containers around, and while they synchronized access while inserting into the container, they didnt synchronize access upon removal (or maybe it was the other way). Whatever the case was, everything I read was somewhat ambiguous as to whether this was safe or not, they implied it was but no one specifically said it.

I dug through the mess of g++ STL and it turned out to not be true at all and it resulted in a third point in the code where a call to end() to terminate a for loop was invalid and the loop then operated on an invalid iterator.

Arslan ibn Da'ud said...

Hello. As maintainer of the CERT C++ Secure Coding standards, I am pleased to see some other interest on the subject, especially on the STL. We are still adding STL-related vulnerabilities because there IS painfully little research in this area, as you cited.

The rule you cite:, does liken invalid iterator ranges to a buffer overflow, because ultimately a buffer overflow can enable an attacker to execute arbitrary code, which is the most serious level of vulnerability possible (in our view). Granted, we could give a lot more specific details on how it could be done (it would be tricky because vector data lives on the heap, not the stack).
Will follow up more soon.

Chris Rohlf said...

Arslan - Thanks for the comment. The CERT guideline for invalid iterators is definitely accurate but yah it could use some more details, but I'm not sure if you want to call out specific STL implementations or not. Let me know if I can be of any help in that area.

Chris Rohlf said...

@jf - those g++ templates are a nightmare at first. I bet theres tons of more 'features' like that lurking beneath. I'm on a mission to find them...