How to: Create a new processor in Metasm

Fri 02 October 2009 by alex

Some guys from our lab took part to the last Defcon CTF in Vegas. While trying to sharpen our tools before the CTF, we had this brilliant idea (actually not so brilliant) "Hey, DDTEK guys proposed a challenge based on a virtual machine in the quals, they may re-use it during the CTF: we need to have a disassembler for the vm's cpu !". Well, I will not keep you hanging, there was no challenge using this processor in the CTF. However, we coded the tool and it is an interesting use case for Metasm, so let's document it and see in this post how to add support for a new cpu in Metasm.

The whole thing starts with the binary500 challenge from Defcon qualifications (Note you can find the game here, under the section "Binary L33tness" level 500): we were given a piece of asm and an interpreter.

Once you reversed the interpreter,you were able to code the assembler. The program given in assembly, once compiled, send itself to a remote server to be checked. Here is a piece of code from the assembly:

start:
    EOR   R29,R29,R29
    MOVLE R28, 1
    MOVLE R27, 2
    MOVLE R26, 5
    TRAP  R26, R27, R28, R29
    OR    R26, R26, R26
    BNS   label1
    HALT

Once compiled, all instructions are four bytes long. Let's look at the details for the EOR instruction. How to encode it:

bin_EOR = (reg(arg0) << 27) | (reg(arg1) << 22) | (reg(arg2) << 17) | 0x16

Register are encoded using five bits, offset and immediate values on 16 bits, and finally the opcode for EOR (0X16) is encoded on the low seven bits left. Here is the same piece of code, with its binary representation:

0xef7a0010 EOR ['R29', 'R29', 'R29']
0xe000008b MOVLE ['R28', '1']
0xd800010b MOVLE ['R27', '2']
0xd000028b MOVLE ['R26', '5']
0xd6f9d017 TRAP ['R26', 'R27', 'R28', 'R29']
0xd6b40000 OR ['R26', 'R26', 'R26']
0x000000a9 BNS [1]
0x00000015 HALT []

The cpu is simple and will make a perfect example for the post. To build our disassembler, we only need three file, first let's start with main.rb.

require 'metasm/main'

module Metasm
class Dc17 < CPU

        def initialize(endianness = :little)
                super()
                @endianness = endianness
                @size = 32
        end

        class Reg
                include Renderable

                def ==(o)
                        o.class == self.class and (not respond_to?(:i) or o.i == i)
                end
        end

        # general purpose reg
        class GPR < Reg
                attr_accessor :i
                def initialize(i)
                        @i = i
                end

                Sym = (0..31).map { |i| "r#{i}".to_sym }
                def symbolic ; Sym[@i] end
                def render ; [@i == 31 ? 'sp' : "r#@i"] end
        end


        def init_opcode_list
                init
        end

end
end

We will create our new processor class inside the Metasm module, to be able to reference misc Metasm objects (e.g. Expression) without having to prefix everything with "Metasm::".

Our class is a CPU, so it inherits from the CPU class. During initialization we simply define endianness and the register size: 32 bits.

Our new class GPR (for General Purpose Register) inherits from the Reg class: this is a general architecture that would allow the definition of other type of registers (e.g. debug, segments) ; in this exemple this is not really needed. For the GPR, well basically we say that there are 32 registers, we define a symbol for each of them to be used when backtracking (ex: register 26 => :r26). As a nice side touch, we define that r31 will be displayed as the "sp" register ("stack pointer").

Finally the last method we have to implement is init_opcode_list but its code will be located into another file. At this point we have described the general characteristics of our new processor, now let's focus on opcode descriptions.

Here is the opcode.rb file

require 'dc17/main'

module Metasm
class Dc17
        def addop(name, bin, *args)
                o = Opcode.new(name)

                o.bin = bin
                o.args.concat(args & @fields_mask.keys)
                (args & @valid_props).each { |p| o.props[p] = true }

                (args & @fields_mask.keys).each { |f|
                        o.fields[f] = [@fields_mask[f], @fields_shift[f]]
                }

                @opcode_list << o
        end

        def init
                @opcode_list = []

                @fields_mask = {
                        :op => 0x7f,
                        :offset => 0xffff, :i16 => 0xffff, :i8 => 0xff, :i5 => 0x1f,
                        :reg1 => 0x1F, :reg2 => 0x1F,   :reg3 => 0x1F,
                        :reg4 => 0x1F,  :reg5 => 0x1F,  :reg6 => 0x1F,
                }

                @fields_shift = {
                        :op => 0x0,
                        :offset => 0x7, :i16 => 0x7, :i8 => 0x7, :i5 => 0x1b,
                        :reg1 => 0x1b, :reg2 => 0x16,   :reg3 => 0x1b,
                        :reg4 => 0x11, :reg5 => 0xC, :reg6 => 0x7,
                }

                @props_allowed = {:setip => true, :saveip => true, :stopexec => true }

                addop 'dec', 27, :reg1
                addop 'eor', 16, :reg1, :reg2, :reg3
                addop 'bns', 41, :offset, :setip
                addop 'halt', 21, :stopexec
                # all others opcode come here
        end
end
end

Describing the instruction set is actually quite easy. The first part of the file holds helper function, mostly copy/pasted from an existing CPU, and the description of the various fields that may be found in the the binary representation: mask and shift, resp. in the @fields_mask and @fields_shift hashes.

Then the addop method inserts the individual opcodes into the opcode list. Operands/fields are described using symbols, to be used in the method decode_instr_op from decode.rb. It will use the symbolic opcode description to decode real binary instructions.

A useful feature is the ability to add properties to each opcode: the list of allowed properties is defined in the @props_allowed hash. For example, that the HALT instruction has the :stopexec property, which indicates to the disassembler that this instruction stops the execution flow. These properties are needed by the Metasm disassembling engine to provide an accurate disassembly, and follow the code flow.

The decode.rb file is a bit more important, but most of the code can be re-used from other processor. Here is the decode_instr_op method for our new cpu (responsible for decoding a single instruction):

def decode_instr_op(edata, di)
        before_ptr = edata.ptr
        op = di.opcode
        di.instruction.opname = op.name
        val = edata.decode_imm(:u32, @endianness)    # read a 32bit instruction into an int

        field_val = lambda{ |f|
                r = (val >> @fields_shift[f]) & @fields_mask[f]
                case f
                when :offset; Expression.make_signed(r, 16) # interpret the high bit as sign
                else r
                end
        }

        op.args.each { |a|
                di.instruction.args << case a
                when :reg1, :reg2, :reg3, :reg4, :reg5; GPR.new field_val[a]
                when :offset; Expression[di.address + 4 + 4*field_val[a]]
                when :i16, :i8, :i5; Expression[field_val[a]]
                else raise SyntaxError, "Internal error: invalid argument #{a} in #{op.name}"
                end
        }

        di.bin_length += edata.ptr - before_ptr
        di
end

And that's all: we are now able to disassemble code. Nonetheless, we still miss a special feature: bactracking. Within our decode.rb file, we must implement the following methods, so that the disassembler knows the semantics of the opcodes:

def backtrace_binding
        @backtrace_binding ||= init_backtrace_binding
end

def init_backtrace_binding
        @backtrace_binding ||= {}
        opcode_list.map { |op| op.name }.uniq.each { |op|
                binding = case op
                when 'or' ; lambda { |di, a0, a1, a2| { a0 => Expression[a1, :|, a2] } }
                when 'eor' ; lambda { |di, a0, a1, a2| { a0 => Expression[a1, :^, a2] } }
                when 'add' ; lambda { |di, a0, a1, a2| { a0 => Expression[a1, :+, a2] } }
                when 'dec' ; lambda { |di, a0, a1, a2| { a0 => Expression[a0, :-, Expression[1]] } }
                when 'movl' ; lambda { |di, a0, a1| {a0 => Expression[[a0, :&, 0xffff], :&, a1]}}
                when 'trap' ; lambda { |di, a0, a1, a2, a3|  {a0 => :unknown} }
                # define other bindings here.
                else {}
                end

                @backtrace_binding[op] ||= binding if binding
        }

        @backtrace_binding
end

def get_backtrace_binding(di)
        a = di.instruction.args.map { |arg|
                case arg
                when GPR: arg.symbolic
                else arg
                end
        }

        if binding = backtrace_binding[di.opcode.basename]
                bd = binding[di, *a]
        else
                puts "unhandled instruction to backtrace: #{di}" if $VERBOSE
                # assume nothing except the 1st arg is modified
                case a[0]
                when Indirection, Symbol; { a[0] => Expression::Unknown }
                when Expression; (x = a[0].externals.first) ? { x => Expression::Unknown } : {}
                else {}
                end.update(:incomplete_binding => Expression[1])
        end
end

def get_xrefs_x(dasm, di)
        return [] if not di.opcode.props[:setip]

        arg = case di.instruction.opname
              when 'br', 'bz', 'bns'';
                Expression[di.instruction.args.last].reduce
              else di.instruction.args.last
              end

        [Expression[
        case arg
        when Reg; arg.symbolic
        else arg
        end]]
end

That is the real voodoo of Metasm, El Pollo Diablo spirit. We now have a complete support for the processor of the virtual machine, given these few lines of code we get a disassembler interface for the binary code. In the script, one a can also find a nice callback we have used to dynamically resolve syscall, whose number is passed through the appropriate register.

require 'metasm'
require 'dc17'
include Metasm

bin = 'dc17.bin'
ep = [0]  # entrypoints offsets
bsd_syscall = {
        0 => 'SYS_exit',
        1 => 'SYS_open',
        2 => 'SYS_close',
        3 => 'SYS_read',
        4 => 'SYS_write',
        5 => 'SYS_socket',
        6 => 'SYS_recvfrom',
        7 => 'SYS_sendto',
        8 => 'SYS_accept',
        9 => 'SYS_bind',
        10 => 'SYS_listen',
        11 => 'SYS_connect'
}

cpu = Metasm::Dc17.new
sc = Metasm::Shellcode.load_file('dc17.bin', cpu)
d = sc.disassembler
d.callback_newinstr = proc { |di|
        next di if di.instruction.opname != 'trap'
        next di if not ddi = di.block.list[-2]
        syscall = nil

        if bt = d.backtrace(di.instruction.args.first.symbolic, di.address) and not bt.empty?
                n_wrapper_syscall = bt.first.reduce
        end

        if syscall = bsd_syscall[n_wrapper_syscall]
                di.add_comment syscall
        end

        di
}

sc.disassemble([ep])

w = Metasm::GtkGui::MainWindow.new("metasm disassembler").display(sc.disassembler, ep)
w.focus_addr ep.first if not ep.empty?
w.signal_connect('destroy') { Gtk.main_quit }
Gtk.main

You are now in position to proudly enjoy the nice graphical interface of the disassembler:

dc17.png

So as a conclusion to this post, Defcon CTF was a great experience even though there was no new challenge reusing the processor. In this post we've seen another use case of Metasm: one can easily add support for a new processor and then enjoy the powerful functionalities from the disassembly and backtracking engine. The whole source code can be downloaded from here. Adding support to parse and encode binary code would only require writing a few other functions, leveraging the opcode list and the framework infrastructure.

Yoann and I will present some of our recent and not so recent works based on Metasm at the HITB conference in Kuala Lumpur next week (06/10/09).

Remember that until this date, if you buy one copy of Metasm (0.00 eur, VAT excl.), you will be eligible to receive one extra copy FOR FREE !