What the hell are pointers? Explained through gameplay

c_meme.png

I’ve always been a fan of introducing new ideas through already perceived metaphors and logical equivalences. I find it easier relating to something one already knows, instead of forcing a yet unknown terminology onto the listener. So I am going to practice what I preach. I am going to try and convince you that pointers in low level computer languages aren’t as bad as they seem.

When students encounter the word “pointer” along with some pictures of stack implementation and lots of arrows, loaded with hex codes, it might intimidate more than it is supposed to. The concept in and of itself is quite simple, but it sometimes takes a while to get used to. We’ll try demystify what confused me, as a novice programmer and some other CS students that I’ve talked with.

So let’s play a game. If you’ve ever watched an episode of “Doctor Who”, you might be familiar with the “TARDIS”. It looks like a police phone booth from the outside. But when you open its door and step inside, the small cabin turns into a huge room full of engines and stuff. So, lets imagine something like the “TARDIS”. But instead of a phone booth we shall imagine a small box. A box no larger than a shoe box. Even better, a lot of small boxes. When you open the box and reach in, you might pull something much bigger than what the actual volume of the box might hold.

For example – I give you, the reader, a box with a small note on it which says “AIRPLANE!”. When you try to reach in and pull something out, BAM – you pull out an entire airplane! A full size Boeing 787!

Pointers-Airplane-1

Now, lets make a simple dictionary. Suppose you want to insert some object into a box. But the game is made for lazy people. Instead of writing the object’s description on the box, you should actually write a unique ID assigned to it. So, the dictionary is actually the set of IDs, matched with different object descriptions.

To make things clearer, let’s continue with the example provided above. So you received a box with a note. Instead of the note having "AIRPLANE!" written on it, it will have "0x1" written on it. And, the accompanying dictionary will have the following entry: "0x1" is actually "AIRPLANE!".

Pointers-Airplane-2

Good. Now we’ve explained the rules of the game to the fullest. What is the objective you might ask? Pass other players objects as efficiently as possible. For instance, if you need to pass another player a single pen – it might be more efficient to pass the pen itself instead of putting it in a box and then passing it. This is because the pen is a lot smaller than the box you have and it makes no sense to use more space than necessary. But, if you have to pass another player a full size car, it might be more efficient to put it inside that magic box to save some space.

We shall write some basic C-like code to associate our game to something more concrete. Suppose we have a dedicated type for our object we want to pass. Let’s just call them – “Objects” (how convenient and original?). So, to declare what box you are going to use, and what the box is going to contain you might write something like the following:

Briefly explained – Object* says that we initialized a new box (pointer – to be exact), containing an object of some sort. If you want to be more specific, you might even replace it with Airplane*. Why the asterisk? That is just so you’d know that airplane is not a real airplane, but rather a box containing one. The value of airplane however, is that same unique ID we’ve talked about earlier.

To access what’s inside the box you might want to use *airplane in context to our example above. This is the same as “opening the box and reaching in” as described earlier. However, to replace the object inside the box with another, you write something like seen in line 1 of the code snippet above.

Nevertheless, if you try and assign something to airplane (mind the small asterisk is missing), you actually replace what is written on the box – which is the ID of the object behind it. But by doing so, you replace the content of the box with that assigned to the unique ID you’re replacing it with, according to the dictionary. You see, replacing the unique ID of the box doesn’t just change the ID. It also changes what you get when trying to “reach in and pull out” the object from the box.

So, in our little example in line 2 of the code above, we changed the ID of airplane to be 0x152. Suppose that we had an entry in our dictionary that said: "0x152 is actually "A GOAT!". What we’ve done is make the box itself point (you see the analogy now?) to another object, which is in our case – a goat.

Pointers-Airplane-3

(The box now points to another object, according to the assigned ID)

So now, when trying to access *airplane what we actually get is not a huge real-life airplane, but a smaller rather cuter goat. It might seem confusing that *airplane is now something else that isn’t an airplane. It is indeed, something you need to take into consideration when changing the pointer of the box.

In technical terms, our box is actually called a “pointer” and what is written on the box is called the “address” of the pointer. When accessing the object behind the pointer, this is called “dereferencing” the pointer. Furthermore, pointers provide no compression services whatsoever. It might seem intuitive through the analogies used above that somehow the pointer “shrinks” the data being passed. This is not the case with pointers, and one might claim that this is where the described analogy fails. They just point to something else, as the name suggests – so keep that in mind.

Consequently, if you want to pass an object to someone else, or pass an object to some function, it should be clear by now that it is much more efficient to do so by using a pointer. The larger the object, the more efficient the usage. There are other reasons to pass pointers to functions instead of copies of the objects themselves – however these reasons are outside the scope of this article.

If you want to elaborate some more on this topic – ask yourself what would happen if a pointer points to another pointer. Better yet, what a pointer pointing to another data structure containing multiple pointers will look like?

To summarize, I hope these examples clear a bit of the initial confusion of trying to grasp pointers and how to use them in C. If you encounter any confusions, have a question or have any suggestions please contact me via email or twitter.

Unmarshalling JSON structs containing interfaces in Go

As far as developing goes, Go is the most fun programming language I’ve used until now. If you are not familiar with Go, you should really check it out. However, all languages have their own barriers and obstacles. This blog post describes the most recent one I’ve had to tackle: Unmarshalling JSON structs that contain interfaces as their attributes.

What’s the problem you may ask? Well, if you have an interface (we won’t be talking about empty interfaces this time) encoding/json doesn’t handle decoding those for you. You need to be very specific on which types you pass to the decoder. But we want to be able to do so, so how do we manage to do that?

Lets build a simple TV guide. The guide consists of some technical information about the guide itself like company’s name, legal notices, ID and so forth. The guide also contains the library itself, which is conceptually everything you can hit play on: movies, series, music, radio etc. We’ll start with defining what is actually a Playable is:

That will be our interface for playing various types of items inside the library. Like we said, we want the library to contain everything we can hit the play button on. Next we will need a TVGuide struct to hold all of our data inside:

As you can see, we already lay the groundwork for JSON decoding. Also, we used type aliasing and define a slice of Playable as Playables. We do that because, turns out that functions declared in Go don’t go well with interface types as receivers. Now we need something to implement that interface. Hence, the Movie struct:

We create the Movie struct and instantly implement the Playable interface. Here too, we define our struct attributes as JSON decoding compatible.

Just one more thing and we are done. We need to implement UnmarshalJSON for Playables in order to manually decide, depending on the type which JSON field to parse, into what implementation of a Playable should we decode to. The following code does exactly that:

We start with unmarshalling the passed data into a map of strings as keys and pointers to json.RawMessage as value.  This way we ensure we can iterate over all the fields received under the library JSON field and check for what Playable implementation they should decode to. Because we support only Movie implementations for now, we will parse only movies.

We iterate through all the library fields and enter into the movies JSON. Because we want to decode multiple movies, that value is a list of one or more JSONs. Every one of those matches exactly to what we defined in Movies struct. This describes exactly the JSON we require:

The way we receive those types of JSON string is entirely up to you, Whether it is by a web-service, directly from files, receiving from a raw socket and so forth. We will skip that part because it is entirely out of scope for this post. But there is a common way to handle all of those. This pseudo code completes this blog post by unmarshalling the above JSON string and printing it for us to be joyful it all works.

Running this will result in the required output:

{0rkaTV NO RUNNING WITH SCISSORS 0x1337H4X0R [0xc0420505e0 0xc042050640]}

The complete code is available on gist and also on Go’s playground.

Dalvik’s smali static code analysis with Python, Part II

If you still haven’t read the first blog post of this series, I highly recommend you do. You can grab it here: Dalvik’s smali static code analysis with Python.

Without further ado, lets dive straight into business. Continuing the topic of static data extraction from smali files such as classes info, method deceleration and invocation. Why only extract these types of data and not something like other glorious types of opcodes? Well, It would take a really long time and I needed a quick solution for my main question – “What could have called the function I’m currently reading?”

When dealing with regular code and utilizing some advanced IDE’s you might as well click on the “call hierarchy” button, if you have one, and check out all the method invocations done all the way until the method you are standing on. But with obfuscated code, it is much harder for the IDE’s to track these calls and tell you what’s the call hierarchy.

Personally I found that when dealing with a large and obfuscated code base, all of the major IDE’s cant cope with displaying call hierarchies. When dumping all of our extracted data into a database, you could by theory track method calls and make queries in order to recursively print call hierarchies. So that’s exactly what we’ll do.

We will start with creating the database and all the relevant schemes for our call tracking. We will use python’s sqlite3 library because we don’t need crazy amount of processing power, at least for this stage. The following present the scheme layout:

This gives us a nice start for inserting all of the extracted data to be later selected by our recursive matcher function. The id field is simply the full representation of a smali class+method. For example: ibe/a->c when ibe is the parent class, a is the child class and c is the method declared and defined inside a class. The data column contains all of the method’s smali code. It is much simpler containing this inside the database and not extracting this straight out of the smali files each time we want to access some method’s data. calling_to column is for listing all of the method invocation done inside a single method definition.

Lets try to give an example. Imagine you have the following class definition and a method definition like so:


Let’s try to deconstruct this code ourselves. What come after .class is the type of the class and the full path that the class is contained in. The .super is the super class, or the base class from which the class should derive. The .source is simply for stating in which file Java file the code should reside. The .method directive is what we are really after, and it states what method is being declared, what it’s type is, it’s parameter types, it’s return type and all of the method is defined up until the closest .end method. Also, all of the invoke- directives are for method calling. This is exactly where we extract what methods are being called.

I’ll skip the part where we scan for all smali files inside a directory and load all of the extracted data into the database. This could be done as seen in parse_smali_file method.

After understanding the most basic directives, and ignoring some for the sake of simplicity, we can start building our method matcher. Let’s assume we stumble upon a method, and we would like to know who across all the application’s code could have invoked it. After populating all of the defined methods inside the application’s smali code files, we could select from the database all of the rows containing the relevant method ID inside their calling_to column. This is achieved by:

For each method received by this select statement, apply the same statement recursively. This will result in something like this:

downloadThe full image can be downloaded from here.

To summarize it all, by applying all of the above we could achieve greater accomplishments which we would talk about extensively later on the series. The matcher function and the graph populating function can be grabbed from here.

Dalvik’s smali static code analysis with Python

A while ago I played around with android applications, trying to figure out new ways I could make my life easier as a vulnerability researcher. I stumbled upon Caleb Fenton’s amazing Simplify. This neat framework executes application’s code, trying to make it more human-approachable. This allows researchers like me understand obfuscated code better. Going through Simplify’s code was a bit shocker, as I wasn’t a big fan of java frameworks, not to talk about code analysis done in java.

So being the stubborn fella I am, I tried to implement my own version of smali code analysis with Python. Dalvik, which is Android’s Java Virtual Machine implementation uses smali code as it’s assembly-level opcodes.

The following regular expressions take care of extracting data from any relevant opcodes for my needs.

For class deceleration extraction:

This results in a result group containing only one member – the name of the class.

For method deceleration extraction:

Quite a fancy regex, but this extracts into a single result group: methods’ name, methods’ parameters, methods’ return value, and all of the methods’ data declared inside a single class.

For method invocation extraction:

When applying this regex on the captured method’s data as seen above, you get all of the called methods’ parameters values, methods’ object type, methods’ name, methods’ parameter object types and the methods’ return object type.

For method return deceleration extraction:

The move-result opcode moves the result of the last invoked method inside a register. This allows us to track the returned values from various method invocations inside a single smali class.

The whole python package and it’s features will be discussed in a future blog post, but for now, the complete code extracting all of the data above from a set of smali files can be found here: https://github.com/0rka/smalidroid/blob/master/parser.py