Stupid Compiler

I’ve been working to disassemble and comment the source to a certain SNES cartridge. I’ve decided to write all the tools from the ground up — as a learning experience. I’m making good progress and, at the current rate, I should have something reasonable in 4 or 5 months. I’m happy with that. I just hope I can keep it going long enough to produce something worth posting. Today, I wanted to explain why I’ve had a harder time than I expected writing the disassembler and show a piece of particularly tricky (for someone, like myself, who has never worked with the 6502 or 65816) code.

Writing the disassembler has been tough. I’ve never written one before, but I believe the quirks of the 65816 make it a little more of a pain than usual. Disassembling a flat binary isn’t too bad if you have a few entry points (typically interrupt vector locations); you follow the control flow graph visiting every connected instruction and mark the rest as data. Of course there are a few stumbling blocks:

• Indirect or computed jumps are not so simple to deal with. For now, my method is the human method — taking a look and adding a map from indirect jump addresses to a list of possible destinations. My brain fantasizes that using abstract interpretation may give enough information to reason this out occasionally (especially with the use of a constraint solver like STP). Of course, I don’t have much confidence in the idea. I doubt I will try it, but I do continue to think about it.
• Not playing nice with CALL or JSR instructions. A call instruction pushes the return address on the stack. Some pieces of code (including the one I talk about below) will either modify this stack variable or remove it from the stack and use it to compute the next jump. This makes it very difficult to follow control flow and breaks the call/return semantics we usually assume.

Those are the usual problems encountered when writing a disassembler. The 65816 adds another layer of pain: a particular opcode can have a variable sized argument depending on a runtime flag state. Huh? Let me say that again, the interpretation of an instruction can vary over two dynamic execution. Example: The bytes A9 00 60 have two very different interpretations based on the value of the M flag in the P (Processor Status) register. If M is set (8-bit accumulator/memory access):

008000:    lda #$0x00
008002:    rts

If M is unset (16-bit accumulator/memory access):

008000:    lda #$0x6000

Can you see how this might make things difficult to debug statically? My solution is to associate a flag state with each address I encounter. The instruction isn’t decoded until the state of the M and X (the X and Y registers can also be dynamically sized) are known. I assume that once one path hits the instruction the value for the flags is valid. In other words, no two paths result in conflicting flag settings. This assumption could be invalid. Take the case of a path which is not valid due to the constraints placed on external data. If that path is evaluated first, the flag settings could be invalid and so my further processing would be invalid. In practice, I don’t think this would happen outside of intentional obfuscation. In other words, my method is a simple data flow analysis without the fix-point iteration. (In case you were wondering, this is why I didn’t just add the (human generated) indirect jump destination addresses to the set of entry points — they need to be associated with a source jump to have a flags value.)

I now have my disassembler chugging along and have been working from both a reset and a VSYNC interrupt. I’ve commented about 16 pages of assembly and have a feel for the main game loop. I’m just getting to the real logic — so far it has just been bookkeeping for the GFX hardware and sound co-processor. In my analysis of the main game loop, I’ve encountered some super awesome code I had to share with someone:

0cc135: jsr $00879c
00879c: sty $05
00879e: ply
00879f: sty $02
0087a1: rep #$30
0087a3: and #$00ff
0087a6: sta $03
0087a8: asl A
0087a9: adc $03
0087ab: tay
0087ac: pla
0087ad: sta $03
0087af: iny
0087b0: lda [$02],Y
0087b2: sta $00
0087b4: iny
0087b5: lda [$02],Y
0087b7: sta $01
0087b9: sep #$30
0087bb: ldy $05
0087bd: jmp [$0000]

Below the fold is the translated version of this gem.
Read the rest of this entry »

Recently, my friend Dave and I were talking about the Adobe PDF DRM mechanism for eBooks. He was one of many people I’ve talked to who have bought an Adobe eBook without realizing it included DRM sludge. You can’t move it around (easily) or copy excerpts or print any of it. The discussion got me thinking about how Adobe went about their DRM system. I work for a company that does the equivalent for satellite cable systems and these things interest me once in a while. I went to Google and researched Adobes system.

In the end I decided to just take a look at the eBooks I own to see how the DRM mechanism fits with the PDF format. I downloaded the latest free PDF specification and opened up the PDF in vim to follow along. It seems the eBook I was looking at was using a version of the EBX system. After digesting some of that specification, I found a nice (if somewhat old) presentation outlining some reversing done on the various eBook protections. The comments about the passwords protections seem bit out of date, so I’m not sure how accurate this still is. In the end, I got completely distracted by the huge number of features implemented by Adobe. A whole JS engine? embedded Postscript support too? I thought it must be hard to have any confidence in the security of such a sprawling system. Less than a week later, there was a security advisory (some vulns provided remote code execution).

Anyway, I realized (or strongly suspected) that I needed a tcpdump of the eBook buying experience to make any more progress and put the eBook DRM circumvention (for academics! honest) on hold. I decided to play with the PDF format instead. My first exercise was adding a wookie sound (which turned into R2D2 due to lack of good internet accessible wookie sounds) to my (OLD!)resume (obviously something all employers want when opening a PDF document). It will play when opened by Adobe Reader (does anyone know if it works on Preview for OS X?). Adding this was fairly easy; PDFs can be modified by simply appending the modifications to the end of the file. Let’s walk through the robotification of my PDF.

PDF documents are specified by a list of PDF objects, followed by a lookup table giving the byte offsets for each object. These objects are one of: number, array, dictionary, boolean, null, string, stream, name, or indirect reference. You can see the PDF spec for full details, but most are exactly what you imagine. An array is written as “[ obj1 obj2 obj3 ... objn ]“. Names are written “/name” and act as identifiers. A dictionary is written “<< name1 obj1 name2 obj2 ... namen objn >>” and maps names to objects. A stream is written “dict stream EOL bytes EOL endstream” and is a chunk of data which is not limited (as strings are) to a smaller length. An indirect reference is like a pointer to an identifiable object (an indirect object, which is given a unique pair of id numbers). To modify an existing PDF, you can add another list of objects (which, if the same identifier is used, override previous definitions of objects) and corresponding lookup table.

The PDF format also includes a dictionary after the lookup table. This dictionary includes a reference to the root object of the object tree. The root object is a dictionary containing the key Type of value Catalog. The Catalog object must also contain a entry for the Pages object (usually an indirect reference), but it has many other optional keys. We want to add an event that takes place when the document opens; the Catalog provides a key (OpenAction) we can define for this event. That is the first step.

We will lookup the current Catalog object:

53 0 obj <<
/Type /Catalog
/Pages 25 0 R
>> endobj


So, starting at the end of the “victim” PDF, we append the new Catalog entry:

53 0 obj <<
/Type /Catalog
/Pages 25 0 R
/OpenAction 55 0 R
>> endobj


I chose to add the event as an indirect reference to object 55 (of generation 0). The number was chosen by looking at the trailer dictionary at the end of the PDF. The Size entry contains the highest unused object number — which was 55 for my document.

Now we must define our action. For this example, I decided to play a sound, but looking at the PDF spec, section 12.6.4 lists a bunch of action types. An action is a dictionary with the Type set to Action. It must contain an S entry giving the action type. For us, that is Sound. A Sound Action also requires a Sound entry giving a Sound object. Let’s add the Sound Action first:


55 0 obj <<
/Type /Action
/S /Sound
/Sound 56 0 R
>> endobj


The last object we must add is the actual Sound object. The Sound object is a stream. The stream dictionary (in addition to the usual stream dictionary entries such as Filter and Length) has the Type set to Sound. It is also required to set the Rate (R) — given in samples per second. Optionally, if the sound is not a 8-bit mono sample, bits per sample (B) and channels (C) can be set. Also, the encoding (E) can be set — see the specification for details (you can also just embed a whole WAV or AIFF file). The R2D2 sample was given as:


56 0 obj <<
/Type /Sound
/B 16
/R 11025
/C 1
/E /Signed
/Filter /ASCIIHexDecode
/Length 60772
>>
stream
...
endstream
endobj


I left out the 60k hexdump of raw samples. I had a really simple python script to convert from WAV to this, but I can’t find it now, sorry.

Now that all the new objects have been appended, we can write the crossref table and the trailer:

xref
0 1
0000000000 65535 f
53 1
0000069494 00000 n
55 2
0000069564 00000 n
0000069624 00000 n
trailer
<< /Size 57
/Root 53 0 0 R
/Prev 68237
>>
startxref
130519
%%EOF


The xref table is a fixed format to allow quick and easy access for the PDF viewer. It contains a list of entries. Each entry begins with a line specifying the object to start at and the number of objects given. This is followed by a line for each object. The line contains two numbers: the byte offset of the start of that object and the generation of the object. Generations come into play when updates to a PDF delete an object. For us, all our objects are of generation 0. Also, object 0 is always of generation 65535 and is used when keeping the list of deleted object numbers available for reuse. The line must be of a strict format: the ten digit zero padded decimal number specifying the byte offset for the current object, a single space, the 5 digit zero padded decimal generation, a single space, a single character (‘n’ for regular object or ‘f’ for a freed object), and a 2 char end of line sequence (space + carriage return, space + line feed, or CR + LF).

After the xref table, the trailer dictionary is written. The trailer dictionary contains the Root reference, the new Size entry (our highest object was 56, so the Size is 57), and the byte offset to the last xref table (prior to this one — it will be given in the startxref near the end of the original file).

Finally, the startxref is given. startxref on a line by itself, then the byte offset of the new xref table in decimal on a line by itself.

Really finally, the ‘%%EOF’ comment ends the file.

Note: I did this with vim and while it wasn’t too bad, manually adding the byte offsets required by the PDF format was a bit error prone. I ended up writing a Python script to build PDFs to do some further experiments, but I didn’t add any parsing to do modification of existing PDFs. I know these things exist, but it was worth it to work it out myself.

After the first experiment, I wanted to bounce a ball around the PDF. Adobe provides Javascript! My bouncing ball worked great in older version of Adobe Reader, but a new security policy put the kibosh on my enthusiasm — I didn’t want to buy the full version of Adobe. I can’t find a way to enable modification of a document without having Adobe sign the PDF with their key. I may be reading the spec wrong, but it appears the default is to restrict modification by default and not allow any 3rd parties from generating annotatable documents. If anyone can show me how to do so, I’d love to know.

I was going to talk about breaking PathWords on Facebook to give a friend 6200 points. That will have to be next time. The length got away from me.

Other things: I’m reading “Ynot: Reasoning with the Awkward Squad” and I like the writing style. It is surprising to grok this stuff without too much trouble. I’d like to chalk that up to having more experience, but I think it’s just the clarity of the writing. I spent some time on the 0×41414141 reversing challenge. It was fun — I hope they add more. I encourage anyone looking for a job to take a crack at it.

TODO: Clean up the rest of this site (markup and finish the SHA notes). Write up the PathWords experience. Write up my experiences reversing the SNES version of “Zelda: A Link to the Past”.