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.