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.

Analyzing Sorting Algorithms With Java

In this blog post we’ll be looking at two basic sorting algorithms implemented with Java. We’ll try to analyze the run-time efficiency of each algorithm by plotting the time taken for each sort iteration with a given random array. We’ll try to demystify some basic misconceptions on how each algorithm works by trying to implement them with Java.

We’ll cover the following algorithms:

  • Bubble Sort
  • Quick Sort
    • With choosing a random pivot
    • With choosing a basic pivot (media of three)

Bubble Sort


Above is a standard implementation of bubble sort with a little yet important tweak. Rather then iterating the array until its end, where each iteration we progress the rightPos index a step more towards the end of the array, we count how many swaps were made each iteration. If at the end of and iteration no swaps were made, the array is sorted and the algorithm should be stopped. In this case, if the passed array already ordered, the algorithm will run run in O(n) instead of O(n^2)

Quick Sort


Quick sort works as a “divide and conquer” algorithm. It splits a given array into 2 parts around a chosen “pivot” element. In our implementation, Quick Sort will move all of the elements that are smaller than the pivot to its left, and all the elements that are bigger than the pivot to its right. The algorithm stops dividing the array when it receives an array equal or smaller to the size of three elements.

For many Computer Sciences undergraduates, when first trying to implement the algorithm on their own they seem to get confused on the technicalities of properly choosing the pivot and arranging all elements around it. As you might already know, there are all sorts of ways to choose the pivot. Each way might be suitable for different requirements. The point of this post is to provide you with some boilerplate code for further testing.

Quick sort with a random pivot

First, we choose out random pivot by selecting it as the last element of the given array. Because we can’t assume anything on the elements of the array, choosing the last element has the same “random” effect as generating a number between 1 to the length of the array and than selecting the pivot at that location. Here, we gradually move inwards from the leftmost index and the rightmost index of the array in order to swap the desired numbers. Because we need to swap the pivot element with the last swapped element we’ll need to create a checkPos variable to hold the position of the last swapped index. All of the elements to the right of checkPos will be greater than the pivot. After swapping all the required elements, a final swap is required to position the pivot at its designated place. The function will return the index position of the pivot. This way, Quick Sort can be run again on the right and left sub arrays around the pivot (not including it, of course).

Quick Sort with a median of three pivot

Here we choose the median of three strategy to choosing a pivot more efficiently. We look at the first, middle, and last elements of the array. We sort them using a basic sorting algorithm. Because we do this for only 3 elements, fancy sorting algorithms are unnecessary. For the sake of our implementation, we’ll use Bubble Sort as implemented above. You can choose whatever algorithm you like. Then, we arrange them in place, and swap the median of them with the element to the left of the rightmost (the highest element in the array we just sorted) element. Effectively, this gives us a starting point of a chosen pivot and an element larger than him, in its designated place. The Sorting itself is done by the same QSRandomPartition function we presented above. The only difference is, the rightPos index should be the median’s position we swapped above, like so:

Plotting The Run-Time Results


Capture

(Figure 1)

As seen in figure 1, the Y axis is the amount taken for each plotted algorithm to sort the array, and the X axis represent the array’s length. Each array is generated randomly and passed to the plotted sorting algorithms. The green graph represents O(nlogn) just for comparison reasons. The red graph is the run-time for Quick Sort (median of three pivot)  and the blue graph is the run-time for Bubble Sort.

As we already should know, Bubble Sort has average performance of O(n^2) as clearly seen above. The blue graph has an asymptotic shape as expected, whereas the green graph is almost identical to O(nlogn), which is the average case performance of Quick Sort.

Capture1

(Figure 2)

As seen in figure 2, the axes represent the same metrics. However, in these graphs the generated arrays are already sorted. The green graph is as seen in figure 1, representing O(nlogn) for comparison reasons. The blue graph, which is barely visible, represents Bubble Sort. Thanks to the performance tweak we implemented, we can see that the graph is way below O(nlogn). It is safe to say that our addition to the algorithm made it linear for sorted arrays. The red graph represents Quick Sort (median of three pivot). Here, the graph looks something like O(n^2) which is its worst case performance.

Capture2

(Figure 3)

In figure 3, the axes yet again represent the same metrics as in figure 1 and 2. Here, as in Figure 1, the arrays are generated randomly. The green graph is O(nlogn). The red graph is Quick Sort with a random pivot, and the blue graph is Quick Sort with a median of three pivot. They are extremely similar to each other, as the media of three strategy has no real benefit in real-world case scenarios.

 

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

CSC CISO Conference talk on IoT hacking

Earlier today I took part in a conference arranged by Israeli’s pc.co.il (People & Computers) group. The main topic was IoT (Internet of Things) security concerns and what we as consumers can do about it.

My presentation talked about real case scenarios of IoT hacking, showing case studies from numerous researches and vulnerability disclosures. The presentation was uploaded to my personal GitHub account and can be found here: http://bit.ly/2tHAdmJ