Security Through Obscurityhttps://alschwalm.com/blog/static/2017-03-07T00:00:00-06:00On reverse engineering, programming, and maybe some other stuff.Exploring Dynamic Dispatch in Rust2017-03-07T00:00:00-06:002017-03-07T00:00:00-06:00Adam Schwalmtag:alschwalm.com,2017-03-07:/blog/static/2017/03/07/exploring-dynamic-dispatch-in-rust/<p>Let me preface this by saying that I am a novice in the world of rust (though I'm liking things so far!), so if I make technical mistakes please let me know and I will try to correct them. With that out of the way, lets get started.</p>
<p>My real …</p><p>Let me preface this by saying that I am a novice in the world of rust (though I'm liking things so far!), so if I make technical mistakes please let me know and I will try to correct them. With that out of the way, lets get started.</p>
<p>My real motivation for taking a closer look at dynamic dispatch can be seen in the following code snippet. Suppose I want to create a struct <code>CloningLab</code> that contains a vector of trait objects (in this case, <code>Mammal</code>):</p>
<script src="https://gist.github.com/ALSchwalm/b43986e11db2d864ee9adf090dedfa45.js"></script>
<p>This works fine. You can iterate over the vector of subjects and call <code>run</code> or <code>walk</code> as you would expect. However, things break down when you try to add an additional trait to the trait object bounds like:</p>
<script src="https://gist.github.com/ALSchwalm/d56ccd574a3b517ad20a7c6e5dc3f3f8.js"></script>
<p>This fails with the the following error:</p>
<div class="highlight"><pre><span></span><code><span class="n">error</span><span class="o">[</span><span class="n">E0225</span><span class="o">]</span><span class="err">:</span><span class="w"> </span><span class="k">only</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">builtin</span><span class="w"> </span><span class="n">traits</span><span class="w"> </span><span class="n">can</span><span class="w"> </span><span class="n">be</span><span class="w"> </span><span class="n">used</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="n">closure</span><span class="w"> </span><span class="ow">or</span><span class="w"> </span><span class="k">object</span><span class="w"> </span><span class="n">bounds</span><span class="w"></span>
<span class="w"> </span><span class="o">--></span><span class="w"> </span><span class="n">test1</span><span class="p">.</span><span class="nl">rs</span><span class="p">:</span><span class="mi">3</span><span class="err">:</span><span class="mi">32</span><span class="w"></span>
<span class="w"> </span><span class="o">|</span><span class="w"></span>
<span class="mi">3</span><span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="nl">subjects</span><span class="p">:</span><span class="w"> </span><span class="n">Vec</span><span class="o"><</span><span class="n">Box</span><span class="o"><</span><span class="n">Mammal</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">Clone</span><span class="o">>></span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="o">^^^^^</span><span class="w"> </span><span class="n">non</span><span class="o">-</span><span class="n">builtin</span><span class="w"> </span><span class="n">trait</span><span class="w"> </span><span class="n">used</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="n">bounds</span><span class="w"></span>
</code></pre></div>
<p>And I found this surprising. In my mind, a trait object with multiple bounds would be analogous to multiple inheritance in C++. I would expect the object to have multiple vpointers for each 'base', and do dispatch through the appropriate one. Given that rust is still a somewhat young language, I could appreciate why the developers might not want to introduce that complexity immediately (being stuck with a poor design forever would be a high cost for little reward), but I wanted to work out exactly how such a system might work (or not work).</p>
<h5>Vtables in Rust</h5>
<p>Like C++, dynamic dispatch is achieved in Rust though a table of function pointers (described <a href="https://doc.rust-lang.org/1.30.0/book/first-edition/trait-objects.html#representation">here</a> in the rust docs). According to that documentation, the memory layout of a <code>Mammal</code> trait object made from a <code>Cat</code> will consist of two pointers arranged like:</p>
<p><img alt="" src="/blog/static/images/2017/03/cat_layout-2.png"></p>
<p>I was surprised to see that the data members of the object had an additional layer of indirection. This is unlike the (typical) C++ representation which would look this:</p>
<p><img alt="" src="/blog/static/images/2017/03/cat_layout_cpp.png"></p>
<p>With the vtable pointer first and the data members immediately following. The rust approach is interesting. It incurs a cost when 'constructing' a trait object, unlike the C++ approach in which a cast to a base pointer is free (or just some addition for multiple inheritance). But this cost is very minor. The rust approach has the benefit that an object does not have to store the vtable pointer if it is never used in a polymorphic context. I think it is fair to say that rust encourages the use of monomorphism, so this is probably a good trade-off.</p>
<h5>Trait Objects with Multiple Bounds</h5>
<p>Returning to the original problem, lets consider how it is resolved in C++. If we have multiple traits (purely abstract classes) that we implement for some structure, then an instance of that structure will have the following layout (e.x., Mammal and Clone):</p>
<p><img alt="" src="/blog/static/images/2017/03/cat_and_clone_cpp-1.png"></p>
<p>Notice that we now have multiple vtable pointers, one for each base class <code>Cat</code> inherits from (that contains virtual functions). To convert a <code>Cat*</code> to a <code>Mammal*</code>, we don't need to do anything, but to convert a <code>Cat*</code> to a <code>Clone*</code>, the compiler will add 8 bytes (assuming <code>sizeof(void*) == 8</code>) to the <code>this</code> pointer.</p>
<p>It is easy to imagine a similar thing for rust:</p>
<p><img alt="" src="/blog/static/images/2017/03/cat_clone_rust_candidate_1-1.png"></p>
<p>So there are now two vtable pointers in the trait object. If the compiler needs to perform dynamic dispatch on a <code>Mammal + Clone</code> trait object, it can access the appropriate entry in the appropriate vtable and perform the call. Because rust does not (yet) support struct inheritance, the problem of determining the correct subobject to pass as <code>self</code>, does not exist. <code>self</code> will always be whatever is pointed at by the <code>data</code> pointer.</p>
<p>This seems like it would work well, but this approach also has some redundancy. We have multiple copies of the type's size, alignment, and <code>drop</code> pointer. We can eliminate this redundancy by combining the vtables. This is essentially what happens when you perform trait inheritance like:</p>
<script src="https://gist.github.com/ALSchwalm/b86e7753e26b57776bb00ef46aac6784.js"></script>
<p>Using trait inheritance in this way is a commonly suggested trick to get around the normal limitation of trait objects. The use of trait inheritance produces a single vtable without any redundancy. So the memory layout looks like:</p>
<p><img alt="" src="/blog/static/images/2017/03/clone_mammal_rust-1.png"></p>
<p>Much simpler! And you can currently do this! Perhaps what we really want is for the compiler to generate a trait like this for us when we try to make a trait object with multiple bounds. But hold on, there are some significant limitations. Namely, you cannot convert a trait object of <code>CloneMammal</code> in to a trait object of <code>Clone</code>. This seems like very strange behavior, but it is not hard to see why such a conversion won't work.</p>
<p>Suppose you attempt to write something like:</p>
<script src="https://gist.github.com/ALSchwalm/a1acc010590aac091a4d0c968f6024a2.js"></script>
<p>Line 10 must fail to compile because the compiler cannot possibly find the appropriate vtable to put in the trait object. It only knows that the object being referenced implements <code>CloneMammal</code>, but it doesn't know which one. Of course, we can tell that it must be a <code>Cat</code>, but what if the code was something like:</p>
<script src="https://gist.github.com/ALSchwalm/fc532dbdae257a03c070d02f7e2b9be1.js"></script>
<p>The problem is more clear here. How can the compiler know what vtable to put in the trait object being constructed on line 17? If <code>clone_mammal</code> refers to a <code>Cat</code>, then it should be the <code>Cat</code> vtable for <code>Clone</code>. If it refers to a <code>Dog</code> then it should be the <code>Dog</code> vtable for <code>Clone</code>.</p>
<p>So the trait-inheritance approach has this limitation. You cannot convert a trait object in to any other kind of trait object, even when the trait object you want is <em>more specific</em> than the one you already have.</p>
<p>The multiple vtable pointer approach seems like a good way forward to allowing trait objects with multiple bounds. It is trivial to convert to a less-bounded trait object with that setup. The vtable the compiler should use is simply whatever is already <code>Clone</code> vtable pointer slot (the second pointer in diagram 4).</p>
<h5>Conclusions</h5>
<p>I hope going through this was a useful exercise to some readers. It certainly helped me organize how I was thinking about trait objects. In practice, I think this is not really a pressing issue, the restriction was just surprising to me.</p>Reversing C++ Virtual Functions: Part 22017-01-24T00:00:00-06:002017-01-24T00:00:00-06:00Adam Schwalmtag:alschwalm.com,2017-01-24:/blog/static/2017/01/24/reversing-c-virtual-functions-part-2-2/<p>In the <a href="https://alschwalm.com/blog/static/2016/12/17/reversing-c-virtual-functions/">previous part</a> I described one approach to 'devirtualize' function calls in a small C++ program. Naturally there were several limitations to that approach, namely that it is very manual. If the target binary contains thousands of vtables, it is not practical to manually locate the tables and create …</p><p>In the <a href="https://alschwalm.com/blog/static/2016/12/17/reversing-c-virtual-functions/">previous part</a> I described one approach to 'devirtualize' function calls in a small C++ program. Naturally there were several limitations to that approach, namely that it is very manual. If the target binary contains thousands of vtables, it is not practical to manually locate the tables and create these structures and relationships.</p>
<p>So, in this part I will go through a more precise description of the layout of vtables and how we can find them programmatically. I will also show how we can sometimes recover relationships between these vtables (and therefore, between the types they are associated with).</p>
<p>But first I need to describe the set of binaries this is applicable to. In the first part I mentioned that most things related to vtable layout were not specified in the standard, and so tended to vary from compiler to compiler. This is because the C++ standard needs to be applicable regardless of the underlying architecture. It would be unfortunate if the spec required some specific vtable layout that was inefficient on some architecture. The compiler developers for that architecture would be required to choose between performance and compliance (more than they already are).</p>
<p>However, because programs produced by different compilers frequently need to interact (most notable, for dynamic linking), compiler developers agreed to a kind of supplemental specification for things like vtable layout, exception implementation and others. The most common of these is the <a href="https://mentorembedded.github.io/cxx-abi/abi.html">Itanium C++ ABI</a>. This standard is implemented by GCC, clang, ICC, and many other compilers (but notably, not Visual Studio). The descriptions I give will be applicable these compilers.</p>
<p>The Itanium ABI is also still ambiguous in some areas. For example, it does not state what segments should be used to store vtables. So I will further specify that I'm describing GCC's particular brand of Itanium. So in essence, I am describing the highlighted section:</p>
<p><img alt="" src="/blog/static/images/2017/01/GCC_location-1.png"></p>
<p>Additionally, the following assumptions are made:</p>
<ol>
<li>RTTI is disabled (if it were on, this would be much easier)</li>
<li>The program does not contain occurrences of virtual inheritance. <em>Unfortunately, discussing this would dramatically increase the complexity of this topic, and because virtual inheritance is somewhat uncommon I didn't think it was worth it.</em></li>
<li>These are 32bit binaries</li>
</ol>
<h4>More about vtable layout</h4>
<p>Before we move forward, recall that in part 1, we described a vtable as a contiguous collection of function pointers in a data segment of the binary. We can also say that the array should only be referenced by its first element, because the other elements will be accessed as offsets in to this array.</p>
<div class="highlight"><pre><span></span><code><span class="nl">.rodata:</span><span class="err">08048</span><span class="nf">D48</span><span class="w"> </span><span class="no">off_8048D48</span><span class="w"> </span><span class="no">dd</span><span class="w"> </span><span class="no">offset</span><span class="w"> </span><span class="no">sub_8048B6E</span><span class="w"></span>
<span class="nl">.rodata:</span><span class="err">08048</span><span class="nf">D4C</span><span class="w"> </span><span class="no">dd</span><span class="w"> </span><span class="no">offset</span><span class="w"> </span><span class="no">sub_8048BC2</span><span class="w"></span>
<span class="nl">.rodata:</span><span class="err">08048</span><span class="nf">D50</span><span class="w"> </span><span class="no">dd</span><span class="w"> </span><span class="no">offset</span><span class="w"> </span><span class="no">sub_8048BE0</span><span class="w"></span>
</code></pre></div>
<p>This is a section from a binary that seems to fit that definition. It is an array of 3 function pointers in the '.rodata' segment, and only the pointer at <code>0x08048D48</code> is referenced. It turns out that this <em>is</em> a vtable, so maybe this heuristic is good enough? If we were to compile the following code:</p>
<script src="https://gist.github.com/ALSchwalm/5a8cd4928eb8e3c1d2993a7acc0099d1.js"></script>
<p>We would expect there to be 5 vtables, one for <code>Mammal</code>, <code>Cat</code>, <code>Dog</code>, <code>Bird</code>, and <code>Bat</code>. But as you might have guessed, things aren't that simple. In fact there are 6 regions in the binary that meet the above criteria. It becomes clear why this happens when you consider the layout of an object with multiple inheritance.</p>
<p><img alt="" src="/blog/static/images/2017/01/Bat-Layout--1-.png"></p>
<p>Notice that <code>Bat</code> includes a complete instance (called subobjects) of <code>Bird</code> and <code>Mammal</code> as well as a <code>vptr</code> for each. These pointers point to different tables. So a type with multiple parents has a vtable in the binary for each one. The Itanium ABI refers to these as a "virtual table group".</p>
<h4>Virtual Table Groups</h4>
<p>A virtual table group consists of a <em>primary table</em> for the first parent type, and an arbitrary number of <em>secondary tables</em>, one for each parent type after the first. These tables will be adjacent in the binary, in the order the parent types were declared in the source. With this in mind, we would expect the vtable group for <code>Bat</code> to be something like:</p>
<table>
<thead>
<tr>
<th>Offset</th>
<th>Description</th>
<th>Bat's vtable for</th>
</tr>
</thead>
<tr>
<td>0</td>
<td>Address of Destructor 1</td>
<td>Bird</td>
</tr>
<tr>
<td>4</td>
<td>Address of Destructor 2</td>
<td>Bird</td>
</tr>
<tr>
<td>8</td>
<td>Address of Bat::Fly</td>
<td>Bird</td>
</tr>
<tr>
<td>12</td>
<td>Address of Destructor 1</td>
<td>Mammal</td>
</tr>
<tr>
<td>16</td>
<td>Address of Destructor 2</td>
<td>Mammal</td>
</tr>
<tr>
<td>20</td>
<td>Address of Mammal::walk</td>
<td>Mammal</td>
</tr>
</table>
<p>With each vtable taking 12 bytes. Recall from part 1 that there will be two destructors, and because <code>Bat</code> does not override <code>walk</code>, we would expect the <code>walk</code> from <code>Mammal</code> to appear in <code>Bat</code>'s table. However, if we examine the binary we don't see any place with 6 consecutive function pointers in the <code>.rodata</code> segment.</p>
<p>If we look more closely at the Itanium specification, we can see why. A virtual table does not consist of just function pointers. In fact a vtable looks more like this:</p>
<p><img alt="" src="/blog/static/images/2017/01/full_vtable--2-.png"></p>
<figcaption>Itanium vtable layout (without virtual inheritance)</figcaption>
<p>The <code>RTTI pointer</code> will typically point to an RTTI struct (that is also described by the Itanium spec). However, because we are assuming RTTI is disabled, it will always be 0. The offset to top has a value equal to the number of bytes that must be added to the <code>this</code> pointer to get the start of the object from some subobject. This is probably a little confusing, so to clarify, image the following code:</p>
<script src="https://gist.github.com/ALSchwalm/4d31be0344b8d1ff61ebbea1a94b0f3b.js"></script>
<p>These assignments to <code>b</code> and <code>m</code> are both valid. The first does not require any instructions. A <code>Bat</code> is a <code>Bird</code>, and because <code>Bird</code> is its first parent, the <code>Bird</code> subobject is at the very beginning of any <code>Bat</code> object. Thus, a pointer to a <code>Bat</code> is also a pointer to a <code>Bird</code>. This is just like normal, single inheritance.</p>
<p>However, the assignment to <code>m</code> does require work. The <code>Mammal</code> subobject inside a <code>Bat</code> is not at the beginning, so the compiler must insert some instructions to add to <code>bat</code> to make it point to its <code>Mammal</code> subobject. The value added will be the size of <code>Bird</code> (and alignment). The negative of this value will be stored in the Offset to Top field.</p>
<p>This Offset to Top component of the vtable allows us to easily identify vtable groups. <em>A group will consist of those consecutive vtables that have decreasing values in the Offset to Top</em>. Consider the following:</p>
<p><img alt="" src="/blog/static/images/2017/01/2017-01-23-182702_576x703_scrot.png"></p>
<p>These are the 6 vtables found in the binary built from the above source. Notice that table 2 has a value of -4 (0xFFFFFFFC as a signed int) for its Offset to Top, and all other tables have a value of 0. Also, each RTTI pointer is 0, as we expected. The -4 tells us two things:</p>
<ol>
<li>Table 2 is a secondary table in a vtable group (because offset to top is not 0)</li>
<li>The size of the type associated with table 1 is 4. Keep in mind that because tables 1 and 2 form a table group, the size of the type associated with <em>just</em> table 1 is actually the size of <em>part</em> of the object (i.e a subobject).</li>
</ol>
<h4>Finding Vtables Programmatically</h4>
<p>From the above, we can devise the following simple procedures to find vtable (groups) from a binary:</p>
<script src="https://gist.github.com/ALSchwalm/2c8a16576d713bacdbc3f9df36c0e843.js"></script>
<p>After running the above in the IDA python interpreter, you can execute <code>find_tablegroups()</code> to get a list of vtable group addresses. This could be combined with additional code to construct structures from each vtable, for example.</p>
<p>However, just knowing where tablegroups are is not very useful. We need some information about the relationships between the types associated with the tables. Then, we will be able to generate a list of 'candidate' function calls for a virtual call-site, so long as we know the 'family' the type is associated with.</p>
<h4>Recovering Type Relationships</h4>
<p>The simplest approach to recovering these relationships is to recognize that two vtables sharing a function pointer are necessarily related. We cannot recover the nature of that relationship, but it is enough to determine that they are in the same family.</p>
<p>But we can go further by considering the behavior of constructors and destructors in C++. An constructor performs the following steps:</p>
<ol>
<li>Invoke the parent class's constructors</li>
<li>Initialize the <code>vptr</code>(s) to point to this type's vtable(s)</li>
<li>Initialize the members of the object</li>
<li>Run whatever other code is in the constructor</li>
</ol>
<p>The destructor performs essentially the opposite steps:</p>
<ol>
<li>Set the <code>vptr</code>(s) to point to this type's vtable(s)</li>
<li>Run whatever other code is in the destructor</li>
<li>Destroy the members of the object</li>
<li>Invoke the parent class's destructor</li>
</ol>
<p>Notice that the <code>vptr</code> is again set to point to the vtable. This seems odd until you consider that virtual function calls should still work during destruction.</p>
<p>Suppose we modified the <code>Bird</code> destructor so it called <code>fly</code>. If you were to destruct a <code>Bat</code> object (which in turn called the <code>Bird</code> destructor when the <code>Bat</code> one was finished), it should call <code>Bird::fly</code> not <code>Bat::fly</code>, because the object is no longer a <code>Bat</code>. For this to work, the <code>Bird</code> destructor must update the <code>vptr</code>.</p>
<p>So, we know that each destructor will call the parent type's destructor, and we know that these destructors will reference the vtable (to assign it to the vptr). We can therefore reconstruct the inheritance hierarchy for a type by "following the destructors". Similar logic can be used for Constructors as well.</p>
<p>Consider the first entry in the first vtable (which we would expect to be a destructor):</p>
<p><img alt="" src="/blog/static/images/2017/01/2017-01-23-184412_418x135_scrot.png"></p>
<p>Notice that there are two assignments, and these are both address points of vtables. This is step 1 in the list above. These object does not seem to have any members, because it proceeds directly to step 4 and calls the two other destructors. We can confirm that these other functions are destructors because of their location in a vtable (at the start of table 6 and table 3). Doing this for the remaining tables this tells us that the inheritance hierarchy was laid out like:</p>
<p><img alt="" src="/blog/static/images/2017/01/inheritance--1-.png"></p>
<p>This matches the actual hierarchy from the source. There are two base classes and one class that has two parents.</p>
<h4>Identifying Constructors</h4>
<p>By similar reasoning, we can find the constructors associated with a vtable by noting that the constructors will be <em>those functions that assign their vptr to a vtable address that are not destructors</em>. By applying this rule to the target, we discover that there are 5 such functions, one for each type:</p>
<table>
<thead>
<tr>
<th>Constructor</th>
<th>Table</th>
</tr>
</thead>
<tr>
<td>sub_8048AEC</td>
<td>Table 1/2</td>
</tr>
<tr>
<td>sub_8048A64</td>
<td>Table 3</td>
</tr>
<tr>
<td>sub_80489A8</td>
<td>Table 4</td>
</tr>
<tr>
<td>sub_80488EC</td>
<td>Table 5</td>
</tr>
<tr>
<td>sub_8048864</td>
<td>Table 6</td>
</tr>
</table>
<h4>Devirtualize</h4>
<p>With this, we can look at the decompiled body of <code>main</code>:</p>
<p><img alt="" src="/blog/static/images/2017/01/2017-01-23-185429_638x534_scrot.png"></p>
<p>The virtual functions are clearly visible on lines 28 and 29. However, we can also identify constructors on lines 13, 16, 22, and 25 from the tables above. Using this knowledge, we can follow the process from part 1 to see the devirtualization:</p>
<p><img alt="" src="/blog/static/images/2017/01/2017-01-23-195432_518x533_scrot.png"></p>
<p>In the above screenshot, I have set <code>v0</code> to have type <code>type_8048D40*</code>. This is the type associated with table 1/2 and also with the constructor on line 13. Similarly, the constructor on line 16 is associated with table 5, which I have created a type for named <code>type_8048D98</code> (the are the addresses at which the tables start. I could just as easily have called them <code>table_5</code> or some such). The same thing could be done with <code>v2</code> and <code>v3</code> to see the alternate possibilities for lines 28 and 29.</p>
<p>So, while the original source contained strings that would make identifying types and methods easy, we did not need any of them to perform our "devirtualization".</p>
<h4>Conclusions</h4>
<p>This is still a very manual process, but we have come a bit further. We are now able to (approximately) automatically detect vtables. It is not hard to see how we will be able to automate the construction of the associated structures, and then perhaps the location of constructor calls. We could also imagine reconstructing type trees. In the next part, we will delve in to this a bit more.</p>Reversing C++ Virtual Functions: Part 12016-12-17T00:00:00-06:002016-12-17T00:00:00-06:00Adam Schwalmtag:alschwalm.com,2016-12-17:/blog/static/2016/12/17/reversing-c-virtual-functions/<p>There are a few posts in various parts of the internet discussing reverse engineering C++, and these often address virtual functions to a large or small extent. However, I wanted to take some time to write about dealing with virtual functions in large, ‘enterprisy’ code-bases. These can often include thousands …</p><p>There are a few posts in various parts of the internet discussing reverse engineering C++, and these often address virtual functions to a large or small extent. However, I wanted to take some time to write about dealing with virtual functions in large, ‘enterprisy’ code-bases. These can often include thousands of classes and massive type hierarchies, so I think it is worth describing some techniques for reversing them. But before that I’m going to go through some more simple cases. If you are already familiar with virtual function reversing, then you my want to proceed directly to <a href="https://alschwalm.com/blog/static/2017/01/24/reversing-c-virtual-functions-part-2-2/">part 2</a>.</p>
<p>It’s also worth noting the following:</p>
<ul>
<li>The code was compiled without RTTI (RTTI will be discussed later) and without exceptions</li>
<li>I’m using 32bit x86 as the example platform</li>
<li>The binaries have been stripped</li>
<li>Most virtual function implementation details are not standardized and can vary from compiler to compiler. For this reason, we’re going to focus on the behavior of GCC.</li>
</ul>
<p>So in general, the binaries we’re looking at have been compiled with <code>g++ -m32 -fno-rtti -fnoexceptions -O1 file.cpp</code> and then stripped with <code>strip</code>.</p>
<h4>The Goal</h4>
<p>In most cases, we cannot hope to “devirtualize” a virtual function call. The information needed to do that is just not present until runtime. Instead, the goal of this exercise will be to determine which function might be being called at a particular point. In later parts we will focus on narrowing down the possibilities.</p>
<h4>The Basics</h4>
<p>I’m assuming that you are familiar with writing C++ but maybe not with its implementation. So, let’s start by looking at how the compiler implements virtual functions. Suppose we have the following classes:</p>
<script src="https://gist.github.com/ALSchwalm/648158e4ed019cdd40632fc9335b4994.js"></script>
<p>And we have some code that uses them:</p>
<script src="https://gist.github.com/ALSchwalm/d978a2deb7cd47d467323762eede8f98.js"></script>
<p>Of course whether <code>m</code> is a <em>Cat</em> or <em>Dog</em> depends on the output of <code>rand</code>. The compiler cannot know this ahead of time, so how does it call the right function? The answer is that for each type having a virtual function, the compiler inserts a table of function pointers called a <em>vtable</em> into the resulting binary. Each instance of such a type is given an additional member called a <em>vptr</em> that points to the correct <em>vtable</em> for that object. Code to initialize this pointer with the right value will be added to the constructor.</p>
<p>Then, when the compiler needs to call a virtual function, it can just access the correct entry in the <em>vtable</em> for the object and call that. This means that the entries in the table must be in the same order for each related type (each class’s <code>run</code> could be at index 1, every <code>walk</code> at index 2, etc).</p>
<p>So we would expect to find three tables in the binary for <em>Mammal</em>, <em>Cat</em> and <em>Dog</em>. We can locate them quickly by looking through <code>.rodata</code> for adjacent function offsets:</p>
<p><img alt="IDA is not always great at detecting function addresses in rodata. You may need to play around a little to see the first table." src="/blog/static/images/2016/12/2016-12-14-194724_796x759_scrot.png"></p>
<p>What about the main function? It decompiles to:</p>
<p><img alt="" src="/blog/static/images/2016/12/2016-12-14-175006_728x438_scrot.png"></p>
<p>We can see that 4 bytes are being allocated in either branch. This makes sense, as the only data in the structure is the <em>vptr</em> added by the compiler. We can also see the virtual function calls on lines 15 and 17. In the first, the compiler is dereferencing (to get the <em>vptr</em>) and adding 12 to access the 4th entry in the <em>vtable</em>. Line 17 gets the 2nd entry in the table. The program then calls the function pointer it retrieved from the table.</p>
<p><img alt="" src="/blog/static/images/2016/12/2016-12-14-214141_825x115_scrot.png">
<img alt="" src="/blog/static/images/2016/12/2016-12-14-214210_828x118_scrot.png"></p>
<p>Looking back at the tables, the 4th entries are <code>sub_80487AA</code>, <code>sub_804877E</code>, and <code>___cxa_pure_virtual</code>. If we look at the bodies of the two “sub_” functions we see that they are the definitions of <code>walk</code> for <em>Dog</em> and <em>Cat</em> (shown in the pictures). By elimination, the <code>___cxa_pure_virtual</code> function must belong to the vtable for <em>Mammal</em>. This makes sense, as <em>Mammal</em> has no definition of <code>walk</code>, and these “pure_virtual” entries are inserted by GCC when a function is (unsurprisingly) purely virtual. So, table 1 must be for <em>Mammal</em> objects, 2 is for <em>Cats</em> and table 3 is for <em>Dogs</em>.</p>
<p>But it is seems strange that there are 5 entries in each vtable when there are only 4 virtual functions in play:</p>
<ul>
<li><code>run</code></li>
<li><code>walk</code></li>
<li><code>move</code></li>
<li>the destructors</li>
</ul>
<p>The additional entry is an ‘extra’ destructor. This is here because GCC will insert multiple destructors that are used in different circumstances. The first of these will simply destroy the members of the object. The second will also delete the memory that was allocated for the object (this is the version called in the example in line 17). In some cases there may be a 3rd version that is used in certain virtual-inheritance circumstances.</p>
<p>By looking back at the contents of the ‘sub_’ functions, we find the layout of the vtables are as follows:</p>
<div class="highlight"><pre><span></span><code>| Offset | Pointer to |
|--------+-------------|
| 0 | Destructor1 |
| 4 | Destructor2 |
| 8 | run |
| 12 | walk |
| 16 | move |
</code></pre></div>
<p>However, notice that the first two entries in the <em>Mammal</em> table are zero. This is an eccentricity of newer versions of GCC. The compiler will replace the destructor entries with NULL pointers in classes that have a pure-virtual method (i.e., classes that are abstract).</p>
<p>With all this in mind, let’s do some renaming. Afterwards we’re left with:</p>
<p><img alt="" src="/blog/static/images/2016/12/2016-12-15-192953_796x691_scrot.png"></p>
<p>Notice that because neither <em>Cat</em> nor <em>Dog</em> implemented <code>move</code>, they both inherited the definition from <em>Mammal</em> and so the move entries in their vtables are the same.</p>
<h4>Structures</h4>
<p>At this point is useful to start defining some structures. We’ve already seen that the only member of the <em>Mammal</em>, <em>Cat</em>, and <em>Dog</em> structures will be their vptrs. So we can define these quickly:</p>
<p><img alt="" src="/blog/static/images/2016/12/2016-12-16-164359_616x303_scrot.png"></p>
<p>The next step is a bit more complicated. We’re going to create a structure for each <em>vtable</em>. The objective here is to get the decompiler output to show us what function would actually be called if <code>m</code> had a particular type. We can then cycle through these possibilities and examine all of the options.</p>
<p>To achieve this, the members of this structure will have the name of the corresponding function it will point to, like so:</p>
<p><img alt="" src="/blog/static/images/2016/12/2016-12-16-164830_600x788_scrot.png"></p>
<p>You will need to set the type of the <em>vptr</em> for each structure to be the corresponding <code>Vtable</code> type. For example, the type of the <em>vptr</em> for <code>Cat</code> should be <code>CatVtable*</code>. Additionally, I have set the type of each vtable entry to be a function pointer. This will help IDA show things correctly. So the type of the <code>Dog__run</code> element should be <code>void (*) (Dog*)</code> (because that is the signature of <code>Dog__run</code>).</p>
<p>If we go back to the decompiled code for main, we can now rename the local variable to <code>m</code>, and set its type to be <code>Cat*</code> or <code>Dog*</code>. Afterwards we see:</p>
<p><img alt="" src="/blog/static/images/2016/12/2016-12-16-185921_437x338_scrot2.png"></p>
<p>Now we can easily see the possible functions being called at the call-sites. If <code>m</code> is a <code>Cat</code> then line 15 will call <code>Cat__walk</code>, if it is a <code>Dog</code> then it will call <code>Dog__walk</code>. Obviously this was a simple example, but this is the general idea.</p>
<p>We could also set the type of <code>m</code> to be <code>Mammal*</code>, but we will see some problems if we do that:</p>
<p><img alt="" src="/blog/static/images/2016/12/2016-12-16-190425_594x341_scrot.png"></p>
<p>Notice that if the real type of <code>m</code> was <code>Mammal</code> then the call at line 15 would be to a pure-virtual function. This should never happen. There's also a call to a null pointer at line 17 which would obviously cause issues. So we can conclude that <code>m</code> must not be a <code>Mammal</code>.</p>
<p>This may seem strange, because <code>m</code> is in fact declared as a <code>Mammal*</code>. However, that type is the compile-time type (a.k.a., the <em>static type</em>). We are interested in the <em>dynamic</em> type (or runtime-type) of <code>m</code>, because this is what determines which function is called in a virtual function call. In fact, the dynamic type of an object can <em>never</em> be an abstract type. So if a given <em>vtable</em> contains one of the <code>___cxa_pure_virtual</code> functions, then it is not a candidate and you can ignore it. We could have not created a <em>vtable</em> structure for <em>Mammal</em> because it will never be used (but I hope seeing why was useful).</p>
<p>So the dynamic type will be <em>Cat</em> or <em>Dog</em>, and we know which functions will be called in either case by looking at their vtable entries. This is the basics of virtual function reverse engineering. In the next part we will go in to how to deal with larger code bases and more complex scenarios.</p>