Dxbx symbol detection
Some people have asked me to write a little about the new symbol detection engine I’ve been working on during this last release;
First a bit of background :
The Xbox always runs just one process, which comes from an executable that’s always loaded at address 0x0001000. This executable (.xbe file) does not load any other code, so there’s no DLL’s to worry about. Microsoft realised this by linking all needed support code into the Xbe. This code comes from libraries, that where distributed to game-developers. All in all there have been 34 versions of this Xbox1 SDK (XDK for short). The oldest versions where a bit of a mess (the version numbers of the various library files where not consistent). Later on (around version 4242 if I remember correctly) the XDK’s used 1 version for all the library files. Game developers also stopped mix-and-matching the XDK’s, so most games released since early 2003 and later have a consistent library version numbering.
Over to Dxbx :
Since Dxbx needs to patch various functions coming from these libraries, we had to write a piece of code that’s able to detect the location of these functions. Since we started as a translation of the Cxbx sources to Delphi, we encountered the Cxbx-solution to that problem and stopped right there with our translation. As it turns out, Cxbx uses a manually constructed data structure, called OOPVA. In itself it’s ingenious, it is huge, and I couldn’t believe that we would have to translate and maintain that piece of code!
So I set out to do it differently; I firmly believe that we have to automate this as much as possible, so I started to collect so-called ‘pattern files’. Pattern files are deviates (not actual copies) of the library files, containing just enough information about the functions to look them up with in an Xbe. In the beginning, I used the IDA Pro flirt-package to generate these pattern files (I requested & got quite a few contributions around that time) so my collection of pattern files has now grown to cover 9 XDK versions.
[ As a side note : we’re still very much interested in other versions, so if you have access to an XDK : Please help us out! ]
Anyway, those patterns became quite big (143 MB right now) and where not easily searchable. So I came up with a super-compact datastructure, that can hold all relevant data (like the first 32 bytes of a function, it’s length, it’s name, a CRC and all of it’s references to other functions) and is very fast to navigate in.
The detection data-structure is a Trie (for those that want to know – look it up on Wikipedia to learn more). with a depth of 32 levels. Those 32 levels correspond with the 32 bytes that each function-pattern starts with, and in the leaves I put all the functions that ended up there (just the rest of the data I have in the patterns).
Because I store strings only once, and because those paths through the first 32 levels are shared by many functions, the size of the data-structure stayed quite low : Right now I fit everything in a file of just 3,7 Mb!
However, when I wrote up the first generation of my symbol-detection engine, there where two problems : 1: The code that was searching for symbols found way too many potential locations, and 2: it was still missing detail. So I added all sorts of checks, intermediate cleanups, etc etc, but in the end it still came to an incorrect end-result. I’ve been tinkering with that code way too long until I realised that that approach just didn’t work.
I didn’t want to ditch the datastructure, but I had to do it better somehow. So just to get some inspiration, I looked at the method that Cxbx used once more, and realised that it actually did rather well because of two very important aspects : It checked a few big (and therefor reasonably unique) functions first, and it marked the first location where it was found as ‘final’, but that was done for the references too!
Once I realised that, I felt quite stupid, as that method removes the need to keep all potential locations around (which had been very cumbersome to work with in my previous detection code). And as an added bonus it promised for some nice speed optimizations!
Also, as I was saying, I was missing some detail in our patterns; As it turns out, the IDA Pro flirt package only registers a reference to another symbol once! And also, there’s no mention if the reference is either an absolute or an immediate reference. In order to add this information, I wrote a tool that parses the output of libdump.exe (a tool that can dump the contents of a library). Using the information gained using this parser, I wrote my own pattern-files, and extended them to mention both the type of reference and all references (including te duplicate ones).
With this extra infrmation, I started out on the new detection method, which works like this :
First, I scan over all code-sections in the Xbe, and do nothing more than register all locations that have a match to one of the paths I have in the detection data-structure. This scan takes a fraction of a second, and results in about 500 (in some bigger Xbe’s maybe 1500) locations.
The next thing I do, is to take all the leaves that where hit, and create symbols (just a record I put in a hashtable) for those symbols that fit the version of the libraries linked to the current Xbe.
Given these symbols, I sort them big to small and work that list downwards. For each symbol, I visit the locations on which it’s leaf had hit, and check a few more things : Does the CRC match? Is the memory range not claimed by something else already? Are all the references valid too? Once I find a location for which all these check hold, I declare it a hit and register the location of that symbol and everything it references. The fact that other functions also have references to the symbols I just pin-pointed, makes it almost impossible to make a mistake in the further detection code. (The memory map I build up is quite helpful too in that regards).
There are a few pitfalls to, though : For some XDK versions I have no exact version-matching patterns, so I have no choice but to use the closest two versions I DO have. (Again: Please contribute!) Those close versions are however slightly different to the actual version, so I have to approach this with a more relaxed validation check. This causes incorrect results, which are hard to fix.
Another problem is, that not all library code is present as-is. We knew that already from the link-time optimized libraries (which we just don’t support), but it also applies to code being compiled in (like macro’s and other inlined pieces of code). These slight differences occur mainly in sections with user-code, so they are recognisable, but cause problems nonetheless.
Now, in order to tackle the problem of missing patterns, I’ve been working on XbeExplorer and extended it with a feature that enables the user (that’s YOU!) to extract patterns manually. Just run a titles with Dxbx and let it detect the symbols. This will probably fail, but in XbeExplorer I read those symbols back in, and present them in the disassembly pane. Now try to find some function, choose “Generate pattern” from the popup, and presto : A new pattern is put in your clipboard, ready to be pasted in a manually build pattern file!
After building a pattern file, put it in the resources\patterns folder and run PatternTrieBuilder in order to get a new Trie – in the next run of Dxbx, this updated Trie will be used (if you clear or bypass the symbol cache) and our symbol-detection should find your function without any trouble!
So I hope that some of you will actually collect enough patterns for the missing XDK versions, so that we can start seeing better detection results in the titles that use those XDK versions, and thus might run them better!
Okay, that’s enough for now, there’s a whole lot more going on, but that’s for another day.