Can you crack it part 2

Posted on 18.04.2013

Following on from part 1 of the challenge ""can you crack it"" which I decided to have a pop at. Part two consists of a virtual machine object written in Javascript, with a cpu sub object and memory storage. The challenge is to complete exec() such that the VM runs. The encoding instructions are given:

// virtual machine architecture
// ++++++++++++++++++++++++++++
//
// segmented memory model with 16-byte segment size (notation seg:offset)
//
// 4 general-purpose registers (r0-r3)
// 2 segment registers (cs, ds equiv. to r4, r5)
// 1 flags register (fl)
//
// instruction encoding
// ++++++++++++++++++++
//
//           byte 1               byte 2 (optional)
// bits      [ 7 6 5 4 3 2 1 0 ]  [ 7 6 5 4 3 2 1 0 ]
// opcode      - - -
// mod               -
// operand1            - - - -
// operand2                         - - - - - - - -
//
// operand1 is always a register index
// operand2 is optional, depending upon the instruction set specified below
// the value of mod alters the meaning of any operand2
//   0: operand2 = reg ix
//   1: operand2 = fixed immediate value or target segment (depending on instruction)
//
// instruction set
// +++++++++++++++
//
// Notes:
//   * r1, r2 => operand 1 is register 1, operand 2 is register 2
//   * movr r1, r2 => move contents of register r2 into register r1
//
// opcode | instruction | operands (mod 0) | operands (mod 1)
// -------+-------------+------------------+-----------------
// 0x00   | jmp         | r1               | r2:r1
// 0x01   | movr        | r1, r2           | rx,   imm
// 0x02   | movm        | r1, [ds:r2]      | [ds:r1], r2
// 0x03   | add         | r1, r2           | r1,   imm
// 0x04   | xor         | r1, r2           | r1,   imm
// 0x05   | cmp         | r1, r2           | r1,   imm
// 0x06   | jmpe        | r1               | r2:r1
// 0x07   | hlt         | N/A              | N/A
//
// flags
// +++++
//
// cmp r1, r2 instruction results in:
//   r1 == r2 => fl = 0
//   r1 < r2  => fl = 0xff
//   r1 > r2  => fl = 1
//
// jmpe r1
//   => if (fl == 0) jmp r1
//      else nop


It is fair to say this particular challenge is one of implementation, rather than anything beyond that.

So, rather than describe step by step how I wrote my VM, I'll instead explain some key concepts and gotchas.

• In the segmented memory model that all x86 processors use (yes, they do use it, but protected mode 32-bit operating systems tend to define the segments to cover the entire address space with segment base of 0 and 64-bit operating systems pretty much have to do this, see the AMD manuals) there are two types of jump: those that specify a code segment, and those that do not.

If a code segment is specified (on x86, this would be a segment selector and the CPU would go and look up the base) then we jump to segment base + offset. If not, we jump to cs+offset, since cs contains the segment base. Remember, if you switch segments via a jump, you must set the segment selector.

• To calculate the offset inside VM.mem, use (16*cs)+offset or (16*ds)+offset respectively.
• I strongly encourage you to check the register is valid.
• Likewise, imagine this was a real processor and wrap memory access. Memory goes out of bounds, then throw/signal an error somehow. This will make debugging your VM solution much quicker.
• That's about it for tips, really. Once you understand the memory model, you simply need to either deduce the correct register from the opcode, or use the intermediate. I would add I ensured my add operand would overflow by performing it mod 256. This did not impact the resultant code.

Once you're done, dump the memory somewhere and run strings on it.

I'll be honest, the biggest time cost from this challenge was a misplaced variable in my code. I calculated the actual linear offset when jmp rx was called, but then used the value from rx to jump to, meaning the code was stuck in an infinite loop. Once I realised what I was doing, easy.