Archgrove - Implicit Definition

We’re on the home stretch now – anyone who’s survived this far is a brave soul indeed and those who make it through today shall be hailed as kings among men (by me anyway). If you’re just joining us, please read the previous articles before you start. Finally, before we begin, make sure you’ve got this archive extracted, and make a copy of the “helloWorld.exe” file called “worldHello.exe”. We’ll be rewriting the program today and we wouldn’t don’t want to break the original in our experiments!

As promised, we’ll start with the actual x86 assembly “big list” of the program, slightly trimmed to show only the information we’re need (If you want the entire assembly listing, here it is). Again, don’t be scared – it’s actually quite easy to understand. You might want to print it out before reading on.

Let’s make some sense of this. Just like in your hex editor, the first column is the address that the line being shown corresponds to in the file. “But”, I hear your ask, “00401000 is way bigger than the size of the file!”. Exceptional observation indeed, if that was you I heard - The number is actually the “base address”, which is pretty much where the program will end up in memory. Don’t worry about this, as today I’ll translate each of these numbers into the file offset for us.

The second part shows the actual representation of the instructions. This is a chunk of the data from the file at the given address. Let’s check this – load “worldHello.exe” in your hex editor, and scroll down until you find the closest row to 0400 (which corresponds to 00401000). As we read along the line we should start seeing the data shown within our assembly listing – and yes indeed, after a long run of “00” up pops “55 8b ec…”, just as expected. Fantastic!

The final 2 columns are exactly like the “program” we ran yesterday - First comes the assembly instruction, then the associated parameters. This is the bit we’re most interested in, as it gives the human readable portion of the assembly (something we can actually understand). Both of these last two columns were created from the data in the second column by the tool used to “disassemble” the “helloWorld.exe” program into the big list.

Now we’ve got our big list, and have some idea about how to read it, let’s start the process of changing it! First, we need to roughly work out what’s going on, based on our new understanding of assembly, so let’s “run” this program in our heads just like yesterday, starting from the top.

1. push ebp – Well, we’re not sure what an ebp is, but it must refer to some memory somewhere, as it’s getting pushed onto the stack. Let’s ignore it for now, and hope it doesn’t matter too much.
2. mov ebp, esp – “mov”? We’ve not seen that before, but all it does is move some memory from one block to another, without it going onto the stack. We can ignore this as well.
3. call 00401020 - Aha, a call! We know what this does. It’s going to go run the instructions located at 00401020
4. call 00401040 - Hmm, another call straight afterwards, going to a function that’s near the first one.

Woah, let’s stop for a second now and think about what we’ve found. We know we’ve got a program that prints “Hello” and “World” to the screen. We know we want to change that to print “World” and “Hello” instead. What if the printing functions for each word were separate? In this case, we’d expect them to be called straight after one another – which is exactly the behaviour we’ve just noticed in our assembly. If we can see that both the called functions are similar, it’s likely that we’ve found our printing functions.

So, off to the assembly again, and let’s look at the function under address 00401020.

push ebp
mov ebp,esp
push 402030h
call 00401085
add esp, 4
pop ebp
ret

Well, that looks interesting – it’s moving memory around just like the beginning of our big list, but then it’s pushing something right before it’s calling something. Looking over the function at 00401040, it’s virtually identical – the only difference is the memory it’s pushing before it makes the call! Our hypothesis is looking stronger and stronger. What if the function at 00401085 being used in these functions actually does the printing? If so, we’d expect the memory pushed onto the stack to be the data the function needs to do it’s job – i.e. something to print (this is just like yesterday, when the “add” function needed the numbers to add on the stack). The first of our functions is pushing data at 402030 onto the stack, so everyone eagerly go look at address 0830 in the file (0830 corresponds the 402030 address).

[Sound of people tabbing to and from hex editor]

Yes! Amazing! At offset 0830, our file does indeed say “Hello”! We’ve almost certainly found the 2 functions we want, and we’ve seen where they’re used. Going back to the big list, to the site of the 2 calls (00401003), we need to find some method of achieving our goal. As we want to make the program say “World Hello”, and we think we’ve found the two functions that print “Hello” and “World”, the easiest thing to do will be to just swap the two calls around.

The big list shows us that the data for the first call is “E8 18 00 00 00” and the second is “E8 33 00 00 00” – scroll into your file (offset 0403) and find these two blocks of data, one after the other. If you click on the “18”, you’ll be able to type in a new number – enter “33″. Change the “33” in the second block to “18” in a similar vein. Fantastic – we’ve effectively swaped over the two blocks of data, so we should have reversed the calls! Save the file, and let’s give our new program a trial run!

Oh dear, that was impressively destructive. I hope you didn’t opt to send an error report, because we’re going to fix this ourselves!

We’ve two options for finding out what went wrong. We could attach a debugger (a special program that watches the CPU as it executes each instruction, and tells us what the state of the system) – this would certainly help us track down the problem, and if you start doing this on your own you can expect to spend a lot of time inside one. The other option is for me to tell you what happened. Yes, I suppose I could have rigged this so that we choose the right option straight away, but everyone loves an explosion and it serves to show you what happens when you get things wrong!

To expedite things, I’ll explain what mistake we made. We know the “call” instructions that got modified take a parameter of the address they want to call to - We can see that in the assembly listing. The problem arises in that the assembly listing is too smart for it’s own good - it turns out there are lots of different “call” instructions, all behaving slightly differently but doing the same basic job. A single word is not expressive enough to display this data for us; hence the big list shows all “call” instructions as equal. The only way we’ll ferret out exactly what’s happening is to look at that intimidating data in the 2nd column, and understand what it means.

In our case, the call instruction corresponds to the “E8” on the far left of the hex in the second column. This is the instruction number – the actual data your CPU will use to decide where to send the instruction. Intel has kindly provided us with a big manual of all these numbers, and what they mean, which tells us that “E8″ actually refers to “Call near, displacement relative to next instruction”. So, the parameter to our call isn’t actually an address, it’s how far away from us the call should go. It seems we can’t always trust the assembly given to us by tools – it’s being “helpful” and calculating where the call is going for us, rather than showing us what’s strictly happening.

This means we need to work out the “relative offsets” – how far away from each call instruction the function we want to call is. This isn’t too hard because we’re swapping one call instruction 5 bytes forward (the number of bytes of data for the instruction, if you add them up), and one it going 5 bytes backwards. So, what’s was 33 becomes 38 (5 bytes “further away” to the call) and what was 18 because 13 (5 bytes “closer”). So, let’s make this change. The new data for the first call becomes “e8 38” - change the byte just as we did before. The second changes to “e8 13”, make the change in the same way. Save the result, cross fingers and toes and run the program.

Being English, this is the point where I quietly nod my head, shake a hand or two and ponder the meaning of life. Other cultures might want to apply different celebratory techniques, because we’ve achieved our goal! We battled through a remarkably complex set of concepts, and emerged victorious and educated – I feel like I should make certificates. I hope everything was reasonably easy to understand, but these are hard ideas to wrap your head around. If you’re stuck anywhere, leave a comment and I’ll see what I can do to help. Remember: there’s never any shame in asking for help, as long as you ask politely and have tried to understand things from the given material.

So, that about wraps up this 4 part series introducing the “memlocs” process. What’s done for Decal is pretty similar to this, albeit much more involved. We don’t “change” the client to test the functionality we want, but we do inject entirely new functions that will call the functions we find when AC is running. If you enjoyed doing this small exercise, then it’s quite possible you’ll be able (with work and research) to find “memlocs” yourself – I’ll post something later about where you can carry on learning this topic in more detail. Even if you hated every moment of it, at least you’ve got a better idea of the general process. My next article will be a less detailed, more accessible view of another part of the Decal update process, so everyone I alienated with this with can come back and join us.

Oh, wait a second - I can’t forget the promised super bonus questions! There are no guaranteed riches or fame, but I can give you mostly anything you like from my L60 character on Thistledown (if AC is your thing) or my L60 Human Mage on Argent Dawn EU (if you’re a Warcraft player). Hold onto your hats, and give these a try!

Bonus question 1: What changes would you make to print “Hello Hello”?

Bonus question 2: What changes would you make to print “Hello Decal”?

Bonus question 3: We know the printing functions were generated from an object in our source C++. Which of the 3 blocks in the given assembly do you think belonged to that object originally?

Bonus question 4: There’s another instruction that your processor understands: “nop”, or “No operation”. It takes no parameters, has instruction number “90” and does absolutely nothing (the CPU skips right over it). Use this instruction to stop the program from waiting for enter before exiting, and explain what you did.

Bonus question 5 (Advanced Extra Credit): The C++ source code consisted of a single object, “HelloWorldPrinter” which had 3 functions “printHello”, “printWorld” and “waitForReturn”. When compiling, I turned off standard library linking, and used libctiny to reduce the size of the result. All compiler optimisations were off, and no debug symbols were generated. Use this and anything else you can glean, produce a single CPP file that will compile to the given program. Ignoring formatting, the closest to my source code wins!

Answers in the comments please and yes, this does mean could in theory copy someone else but as I’ll only take the first “correct” answer for each question, this shouldn’t be a big deal. Results of the quiz (if I get any replies) will appear in a couple of days, along with the project source.

Now we know how the program exists on your computer, we’ll learn a little bit about how your CPU actually runs the instructions once they’re loaded. As usual, please make sure you’re up to date on the previous articles; It will be very hard to understand if you don’t. Also, if there’s something that’s not clear or you spot a mistake, please leave a comment – I don’t knowingly leave errors in, and would like everyone who’s playing along to get the most out of this series. Finally, note that will be the last “pure theory” article, so we can get back to the interesting Decal specific stuff. Let’s get to it!

Here’s a secret that will make our lives a lot easier. The big instruction list is actually subdivided! Inside the big list is actually lots of little lists, groups of instructions that are stored together. We call these groups “functions”, as they do just one thing. Rather than include each group everywhere it’s used, the compiler will only include the group once. After that, when it needs the “functionality” that the “function” provides, it will tell the CPU to stop executing the big list, and to start executing one of these groups. When the CPU is finished, it will go back to where it was in the list.

This is very useful to us, as the compiler will have created these functions for out of our original objects. We know our program prints “Hello” and “World”, so the odds are good that there are functions specifically for printing “Hello” and “World” inside the list. In fact, there is almost certainly a function for “Printing something”, and then our two functions which use the “Print something” function themselves.

Enough waffle – let’s role-play! Today, we’re going to be CPUs! Let’s set ourselves up with some memory, and then we’ll try and execute an instruction list.

I’ve put 3 things inside our memory. Coming first, we guess that “Add” is a function – it’s a list of instructions that can add two numbers together. Remember, as a function, we don’t have to copy “add” into the big list, we can just tell ourselves to execute it and watch what happens! We’ve also got 2 boxes of data – the number “2” and the number “5”. Above each box is the “memory address” of that box. This tells us where in memory that box is stored, and we’ll use it to uniquely identify the box in our instructions.

The scary tower on the right is the “Stack”. This is a sort of temporary memory that we’ll use when we’re executing our program. We can “push” data onto the stack, and it will go into the topmost free slot. We can also “pop” the stack, and the topmost item will come back into our memory.

So, without further ado, let’s run the following assembly “big list”, specially designed for our “Weblog Reader” processor.

OK, jot that down on a piece of paper and put your finger on the first line. Your finger is the “execution cursor”. Every time we finish an instruction, move it down a line. Notice how each instruction is very simple, consisting of just one operation and that they take extra information in the form of “parameters” - basically additional information for the instruction to do it’s work. Let’s begin, and it should all become clear!

1. push 02 – We need to take the box labelled 02, and push it onto the stack. Simple enough, and let’s see what we now look like.

   

2. push 03 – Basically the same again, except from a different address. Notice how the stack “builds up” as we push things onto it; it’s like a giant pile of plates!

   

3. call 01 – Hmm. We need to “call” the add function. It’s going to take all the data on the stack, add it together, and put the result on the stack for us. Great - We don’t need to do any work ourselves, our function is doing it for us.

   

4. pop 02 – Aha! We can now take the result we received from the stack, and put it back into box 02!

   

Superb. In just 4 instructions, we’ve successfully executed our program, and worked out that 2 + 5 = 7. Our memory now reflects the result, our user is happy, and we’ve shown that Intel and AMD have nothing on us!

Back on earth, we’ve just played the part of a “Stack machine processor”. Using this technique, we can run basically every program we can think of! The slight dampener is that your CPU is not strictly the same, but don’t panic – what we’re dealing with will be close enough to finish our task in part 4, where we’ll make “Hello World” into “World Hello”!

So next time we’ll start by disassembling the helloWorld.exe file into a list of instructions similar to those we just executed. We’ll work out roughly what the instructions in the list do, find the functions and then determine what we need to edit in order to change the output. Then, with one fell swoop, we’ll modify Hello world to do our bidding! Mmmmm, we’re so close, one can almost taste it.

Oh, and because the last “advanced” bonus question was answered by Enolive with almost precognisant alacrity, here’s another: Can you tell me what alternative to stack based processing an x86 CPU uses, and name 2 virtual machines with widespread deployment that are purely stack based (before their code is JITed)?

Welcome back! Last time, we defined what a “memloc” was and why we might want one, so anyone new to this series, please read up on the previous articles from this list. Also, for the rest of these articles, you’ll need a so-called “hex editor” – basically a glorified text editor that can edit anything, not just text. I’ll recommend frHED to you, as it’s solid and free (though you can use whatever you like). Download it and install it, but don’t be scared by it. All will become clear.

Before we can find a “memloc” of our own, we’ll need something to dissect. As the AC client is far too complex for an introductory exercise, the best approach will be to make a sample program to work on. Lets use the canonical “Hello world” example, whereby the words “Hello” and “World” are printed to the screen and the program waits for us to press enter.

I’ll write our “Hello world” program for us all in the same language Turbine use (C++) and I’ll use the same compiler that they do (MS Visual Studio 7.1). For those disappointed about not seeing the C++, well, that would rather spoil the exercise. We want to work in conditions that mirror what we go through with Decal, just with some of the extra complications removed. Also I have “Super Bonus Question” regarding this, so just hold it together for a while longer!

[Sound of keyboard and compilation]

Done! Here’s one “Hello World” client, ready for us to download. Grab it, extract it and run it to get the idea. I hope that at least some of you will trust that I’m not trying to break your machine, but if you’re worried then please just wait a few days and I’ll post the original source.

Right, we’ve now got everything we need to begin! However, being the conscientious developers that we are, before we gleefully jump in and start dismantling programs we need to make sure we understand what we’re dealing with. Hence the rest of this session will deal with how the big instruction list that makes up your program is stored on your machine. Don’t worry, that tasty little example program will still be waiting for us.

Let’s start with a program. What is a program? The answer you’ve probably come up with is “An exe file”, and that’s a damn good start. As far as our users are concerned, programs are exe files (exe for “Executable”). Inside an exe file is the big instruction list that makes up the program and the extra data it will need to run. The pressing question becomes “how is our instruction list stored”?

You know that you can store your images on your computer in lots of different file types. You’ve no doubt used bitmap files (.BMP), JPEG files (.JPG) and many others. These are the file formats and, like images, programs have file formats as well - Indeed, the “.EXE” file format is called “Portable Executable” and it defines where in the file we’ll find our instruction list and where we’ll find our data. Using a special tool, we can find out that PE format says that, for our program, the instruction list will be at the start of the program, and the data will follow straight after it.

Advanced bonus question: Given that Windows programs are only designed to run on Windows, what does the “Portable” in “Portable Executable” refer to?

What we expect to find in the instruction list for helloWorld.exe would seem to be obvious – it’ll just be a list of instructions telling our machine to print “Hello world”! But, don’t forget, in the translation from the C++ into the instruction list the compiler will have added some more instructions, things that whilst not directly printing “Hello world” are necessary for the computer to finish the job.

What our “data” is might be less obvious. In general, the data is everything the instructions need to complete their task and as in this case our task is writing to the screen, the instructions will deal solely with that. What they actually print is up to us, and as such “Hello world” is our data.

We now know what the compiler put into our executable file. We’ve got a list of instructions at the beginning that will tell the computer to print something to the screen, as well as some extra instructions to help it along. This will be followed by what will actually be printed, in our data section (which might also contain some other useful data added by the compiler). Let’s check that the reality matches what we’ve learned, so open frHED and load into it the executable file “helloWorld.exe”. What it shows you might look scary, but don’t be put off – it’s actually really simple.

The left hand column shows you the position the line being shown takes in the file. The middle column is the actual data in the file. Both these columns are displayed in hexadecimal, but don’t worry if you don’t know it - we’re only interested in the right hand column, which interprets the data for us as normal text. If we’re correct, somewhere near the bottom of this column will be the data section containing (at least) the words “Hello” and “World”, so scroll down and…yes! There they are! Our new knowledge matches the theory, and the universe makes sense. Fantastic!

In summary, we’ve built our sample program, learned a little bit about how it’s stored and then checked this knowledge against the real world. This is an important cycle in scientific and semi-scientific disciplines. Learn, hypothesise, validate. Whenever learning something new, follow it often and you’ll find the subject seems far more alive than just reading a textbook.

Next time, I’ll talk a little bit about how your CPU actually executes the instruction list. Finally, part 4 will actually have us in there, hands dirty, hacking away changing what helloWorld.exe does without ever having seen the source code! I hope you can contain your excitement, because I’m having trouble!

Adam Wright (as Asriel).

PS – Yes, I know I said this would be a two part article, but the amount of back story needed to make sure everyone has a chance of playing along would have made this part way to long to digest. Sorry for my misestimate, and I hope no-ones too bothered. After this set of articles is done, I do have at least one more stand alone planned targeting a specific problem we’ve had in updating Decal.

My apologies for not getting part 5 of “Reapplying the Decal” up today, but I do have a (pathetic) excuse. I was in London for the majority of the my time, and in what I had left for writing, I decided that one more part wouldn’t cut it for the “memlocs” section. Expect to see part 2 of a total 3 or 4 tomorrow!

To at least write something, I’ll answer a few of the comment questions. Anyone not interested in what the comments have said, feel free to tune out now and return for the article on Friday.

First of all, a myriad of thanks to those who’ve left supporting comments, and I’ll even spare a couple for those who’ve don’t think this was particularly useful. Criticism is always useful; as long as one can extract the barbs it often comes with. I didn’t expect a lot of interest when I started writing these, but I’m glad that people found them interesting.

Regarding personal questions, I don’t normally like to talk about myself as I prefer to let my work speak for me. Nonetheless, for Kyle, no – I’m not a teacher nor have I ever formally taught. At the moment, I’m a mature student (over 21) majoring in Mathematics with a minor in Computer Science.

As for those wondering about a donations link, don’t expect to see one on my site anytime soon (I cannot and do not speak for the rest of the developers). I’m fortunate to be blessed with a comfortable life, and I do this purely because I find it interesting. On the remote chance that something here really provokes the need for a fiscal contribution, there are many good charities and groups that I’d much rather see the money go to. I’ll value anything given to them (or other good causes) much the more than any money you could ever give me. Oh, and if you do donate because of something I’ve done, please send me an e-mail that we might share the warm fuzzy feeling.

Now, the meaty technical questions and advice regarding memlocs. I should first say that I’m not overly involved in finding the function and object addresses at the moment – Hazridi has shouldered the bulk of this work, and he’s had a much harder job than I have by an order of magnitude.

To Joseph Bruno, we have used a pattern matching technique in the past to help locate functions changed by only address additions (and other minor alterations). At one point, someone (alas, I can’t remember who) wrote a tool that would find all the functions for us. But, as you say, this sort of device is vulnerable to failure when significant changes are made, or when the compiler is updated. The best of my memory says we’ve lived through two compiler updates so far - VC6 to VC7, and VC7 to VC7.1 We might have also suffered an optimisation flag change (which is just as damaging), I’m sure one of the other developers will remember far better than I. The idea is certainly sound, and I’m Decal will use it again when the client is stable.

To Miss Stepahnie, it’s an intriguing idea, but I’ve yet to find any decompiler that will produce anything useful from compiled C++. We have no debug symbols and compiler optimisations are used aggressively in the client, both contributing to a soup of code that, whilst in theory is reversible, would produce C that wouldn’t be much more better than assembly itself. The one to many instruction mapping you get with 3g to 1g alone would be a big issue (we’d have to go back to the assembly to know exactly where, and in what state we want to perform the call). However, I love being proven wrong so if you know of one, I’m sure we’ll gladly look at it!

Well, people have asked for a post about how the “memlocs” used within Decal are found, and who am I to argue? This one will be a bit more hands on, for those that are willing. Bonus kudos (and maybe something from my Thistledown swag bag) for the first person to solve the puzzle at the end of this article pair!

Before we write a line of code, or even turn on our computers (wait! Don’t turn off your computer!), we have to again stop think about our problem. What’s a “memloc”? Why would we want a memloc? Where’s my glass of Pinot noir gone?

First, the spelling. “memloc” is a contraction of “memory location”. For this to make any sense, we’ll have to dig into how computers work a bit. We already know that computers are stupid – all they can do is follow instructions. Your computer has a specific device for doing this – the CPU. The CPU looks at memory, finds an instruction to execute, and runs it. Then it finds another one, and runs that. It keeps doing this from the moment you turn it on until it’s turned off.

We also know that common way of programming is to use “object orientation”. We write our programs in a special language the humans can more easily understand, and then we translate it into instructions computers can understand. In the case of AC, the language Turbine use is called “C++”. Almost certainly, the only language your CPU understands is called “x86 assembly”. The translator turns objects written into C++ into this much more verbose and complex assembly language, so that your computer can execute them.

Why do we care? Because in the AC client that Turbine wrote, there are lots of fun groups of instructions that were the original Turbine objects. If we could get hold of these objects, we can extend the client with Decal much more easily. Rather than making Decal “type for you” to interact, we can just use the same objects that Turbine uses to interact with it.

Unfortunately, lots of information is lost in this translation phase (called “compilation”). Because humans don’t need to understand the instructions anymore the “compiler” can make lots of changes to make it easier for the computer to execute them. This is unfortunate for us as we don’t get to see the C++ that Turbine wrote – all we have is the big assembly instruction list! This is now hard to read and hard to understand, but if we want to use these objects, we’re going to have to try and make some sense of it.

We’ll have to “undo the translation” far enough that we can see roughly how the original objects work, and what places in the assembly code correspond to each object. These are called the “instruction addresses”, but as your computer loads the instructions into memory so it can execute them, we can just as easily call them “memory locations” - “memlocs”!

Right, we all now understand why we want “memlocs”, what they are, and where they come from. So, how hard can it be? We’ll read through these instructions until we find what we’re looking for, note them down, and go home early! But, as always, something’s there to trip us up. The first problem, the one you as users see most often is that every time Turbine translates their C++ into assembly (every patch, basically), the compiler has different work to do. The translation ends up being slightly different every time, and this is why we have to find the “memlocs” again every month. Sometimes, Turbine don’t make many changes, the translation is similar, and the job is easy. Sometimes, the C++ changes a lot and so the assembly changes a lot – just like when the expansion was released. In this case, everything is moved a lot, some objects are deleted entirely, and new objects take their place, resulting in a totally new set of instructions.

But, we can deal with this – we just plod along every month and find them again. This being far too kind, the world throws another problem at our feet – There are approximately 1,380,000 instructions in the client executable! Even with some of the helper tools used, this is a lot of things to read and piece together. The size of the client is a prime factor in how long it takes to find the addresses we’re after.

So how is it done? Well, the easiest way to demonstrate this is to show you. We’ll make a sample program of our own, compile it, and then work out a “memloc” from the compiled result. So, tune in for part 2 and see code created, ripped apart, and stuck back together in a grotesque mockery of education!

Adam Wright (as Asriel)

Disclaimer: This explanation is actually a simplification of what goes on, but it’s close enough to be useful.

Edit: To once again prove that whilst spell checkers can fix the spelling of your words, they can’t fix the meaning.