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:



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 !