Thursday, December 22, 2011

Simple Virtual Machine

Sample code for this article may be found here.


In computing, Virtual Machine (VM) is a software implementation of either existing or a fictional hardware platform.  VM's are generally divided into two classes - system VM (VM which is capable of running an operating system) and process VM (the one that only can run one executable, roughly saying). Anyway, if you are just interested in the definition of the term, you better go here

There are tones of articles dedicated to this matter on the Internet, hundreds of tutorials and explanations. I see no reason to just add another "trivial" article or tutorial to the row. Instead, I think it may be more interesting to see it in action, to have an example of real application. One may say that we are surrounded by those examples - Java, .NET, etc. It is correct, however, I would like to touch a slightly different application of this technology - protect your software/data from being hacked.

Data Protection
Millions of dollars are being spent by software (or content) vendors in an attempt to protect their products from being stolen or used in any other illegal way. There are numerous protection tools and utilities, starting with simple packers/scramblers and ending with complex packages that implement multilevel encryption and virtual machines as well. However, you may disagree, but you wont convince me, an out-of-the-box solution is good until it gains popularity. There is enough evidence for this statement. In my opinion, no one can protect your software better than you. It only depends on how much protected you want it to be.

Although, there are numerous protection methods and techniques, we are going to concentrate on a virtual machine for data coding/decoding. Nothing special, just a trivial XOR method, but, in my opinion, enough to demonstrate the fundamentals.

Design Your VM
While in real life, hardware design precedes its software counterpart, we may let ourselves to do it in reverse order (it is our own VM, after all). Therefore, we will begin with the pseudo executable file format which will be supported by our VM. 


Pseudo Executable File Format
Well, it is a good idea to put a header in the beginning of the file. In order to do so, we have to think what our file is going to contain. The file may be a raw code (remember DOS com files?), but this would not be interesting enough. So, let our file be divided into three sections:
  • code section - this section would contain code written in our pseudo assembly language (we'll cover it a bit later);
  • data section - this section would contain all the data needed by our pseudo executable (PE :-) );
  • export section - this section would contain references to all the elements that we want to make visible to the core program.
Let us define the header as a C structure:

typedef struct _VM_HEADER
{
   unsigned int  version; /* Version of our VM. Will be 0x101 for now */
   unsigned int  codeOffset; /* File offset of the code section */
   unsigned int  codeSize; /* Size of the code section in bytes */
   unsigned int  dataOffset; /* File offset of the data section */
   unsigned int  dataSize; /* Size of the data section in bytes */
   unsigned int  exportOffset; /* File offset of the export section */
   unsigned int  exportSize; /* Size of the export section in bytes */
   unsigned int  requestedStack; /* Required size of stack in 4 bytes blocks */
   unsigned int  fileSize; /* Size of the whole file in bytes */
}VM_HEADER;

Well, one more thing. Actually the most important one. We need a compiler for our pseudo assembly that would be able to output files of this format. Fortunately, we do not have to write one (although, this may be an interesting task). Tomasz Grysztar has done a wonderful work with his Flat Assembler. Despite the fact, that this compiler is intended to compile Intel assembly code, thanks to the wonderful macro instruction support, we can adopt it to our needs. The skeleton source for our file would look like this:

include 'defs.asm' ;Definitions of our pseudo assembly instructions

org 0
; Header =======================
   h_version   dd 0x101
   h_code      dd _code
   h_code_size dd _code_size
   h_data      dd _data
   h_data_size dd _data_size
   h_exp       dd _export
   h_exp_size  dd _export_size
   h_stack     dd 0x40
   h_size      dd size

; Code =========================
_code:
   _function:
      ;some pseudo code here
_code_size = $ - _code

; Data =========================
_data:

   ;some data here

_data_size = $ - _data

; Export =======================
_export:
   
   ;export table structures here

_export_size = $ - _export
size = $ - h_version

as simple as that.

Export section deserves special attention. I tried to make it as easy to use as possible. It is divided into two parts:

  1. Array of file offsets of export entries terminated by 0;
  2. Export entries:
    1. File offset of the exported function/variable (4 bytes);
    2. Public name of the exported object (NULL terminated ASCII string);
In the above example, the export section would look like this:

; Array of file offsets
      dd  _f1  ; Offset of '_f1' export entry
      dd  0    ; Terminating 0
; List of export entries
  _f1 dd  _function                  ; File offset
      db  'exported_function_name',0 ; Public name

Save the file as 'something.asm' or whatever name you prefer. Compile it with Fasm.

Pseudo Assembly Language
Now, when we are done with the file format, we have to define our pseudo assembly language. This includes both definition of commands and instruction encoding. As this VM is designed to only code/decode short text message, there is no need to develop full scale set of commands. All we need is MOV, XOR, ADD, LOOP and RET

Before you start writing macros that would represent these commands, we have to think about instruction encoding. This is not going to be difficult - we are not Intel. For simplicity, all our instructions will be two bytes long followed by one or more immediate arguments if there are any. This allows us to encode all the needed information, such as opcode, type of arguments, size of arguments and operation direction:
typedef struct _INSTRUCTION
{
   unsigned short opCode:5;    /* Opcode value */
   unsigned short opType1:2;   /* Type of the first operand if present */
   unsigned short opType2:2;   /* Type of the second operand if present */
   unsigned short opSize:2;    /* Size of the operand(s) */
   unsigned short reg1:2;      /* Index of the register used as first operand */
   unsigned short reg2:2;      /* Index of the register used as second operand */
   unsigned short direction:1; /* Direction of the operation */

}INSTRUCTION;


Define the following constants:

/* Operand types */

#define OP_REG 0 /* Register operand */
#define OP_IMM 1 /* Immediate operand */
#define OP_MEM 2 /* Memory reference */
#define OP_NONE 3 /* No operand (optional) */

/* Operand sizes */
#define _BYTE 0
#define _WORD 1
#define _DWORD 2

/* Operation direction */
#define DIR_LEFT  0
#define DIR_RIGHT 1

/* Instructions (OpCodes) */
#define MOV     1
#define MOVI 7
#define ADD     2
#define SUB 3
#define XOR     4
#define LOOP 5
#define RET 6


It seems to me that there is no reason to put all the macros defining our pseudo assembly opcodes here, as it would be a waste of space. I will just put one here as an example. This will be the definition of MOV instruction:

Constants to be used with our pseudo assembly language



























Macro defining the MOV instruction































As you can see in the code above, I've been lazy again and decided, that it would be easier to implicitly specify the size of the arguments, rather then writing some extra code to identify their size automatically. In addition, the name of the instruction tells what that specific instruction is intended to do. For example, mov_rm - moves value from memory to register and letters 'r' and 'm' tell what types of arguments are in use (register, memory). In this case, moving a WORD from memory to a register would look like this:

   mov_rm REG_A, address, _WORD

and the whole code section (currently contains only one function)  is represented by the image below:

loads address of the message as immediate value into B register; loads length of the message from address described by message_len into C register; iterates message_len times and applies XOR to every byte of the message. "mov_rmi" performs the same operation as "mov_rm" but the address is in the register specified as second parameter.







This is what the output looks like in IDA Pro:

Header













Code


















Data and Export sections































Virtual Machine
Alright, now, when we have some sort of a "compiler", we may start working on the VM itself. First of all, let us define a structure, that would represent our virtual CPU:

typedef struct _VCPU
{
   unsigned int  registers[4]; /* Four registers */
   unsigned int  *stackBase;   /* Pointer to the allocated stack */
   unsigned int  *stackPtr;    /* Pointer to the current position in stack */
   unsigned int  ip;           /* Instruction pointer */
   unsigned char *base;        /* Pointer to the buffer where our pseudo 
                                  executable is loaded to */
}VCPU

registers - general purpose registers. There is no need for any additional register in this VM's CPU;
stackBase - pointer to the beginning of the allocated region which we use as stack for our VM;
stackPtr - this is our stack pointer;
ip - instruction pointer. Points to the next instruction to be executed. It cannot point outside the buffer containing our pseudo executable;
base - pointer to the buffer which contains our executable. You may say that this is the memory of our VM.

In addition, you should implement at least some functions for the following:
  1. allocate/free virtual CPU
  2. load pseudo executable into VM's memory and setup stack
  3. a function to retrieve either a file offset or normal pointer to an object exported by the pseudo executable
  4. a function to set instruction pointer (although, this may be done by directly accessing the ip field of the virtual CPU
  5. a function that would run our pseudo code.
In my case, the final source looks like this:




































I decided not to cite the VM's code here as you should be able to write it yourself if the subject is interesting enough for you. Although, the code in this article does not contain any checks for correct return values, you should take care of them.

Summary
Although, this article describes a trivial virtual machine which is only able to encode/decode a fixed length buffer, the concept itself may serve you well in software/data protection as hacking into VM is several times harder then cracking native code.

One more thing to add. Our design allows us to call procedures provided by the pseudo executable, but there are several ways to allow the pseudo executable to "talk to us". The simplest (as it seems to me) is to implement interrupts.

I hope, I've covered it. Would appreciate comments and/or suggestions.

P.S. The encoded result would be "V{rrq2>Iqlrz?".

See you at the next post!


21 comments:

  1. keep sharing, you have some great posts, thx :))

    ReplyDelete
  2. thanks! will do my best not to disappoint ;)

    ReplyDelete
  3. Cool article! But fyi, underscore-capital identifiers, like _VM, are reserved for the compiler in C and C++.

    ReplyDelete
  4. Actually, as long as they are not made public (e.g. exported), I do not see any problem with that. In addition, we may simply remove all identifiers following the struct keyword, as we are defining types here.

    ReplyDelete
  5. Hi
    Nice article
    Can you contact me (Dr Mike James)
    editor@i-programmer.info
    Thanks

    ReplyDelete
  6. Thank you for good words, Dr James. I have sent you an email as you requested.

    ReplyDelete
  7. Maybe I have to go over it again once more, specially with all the assembly codes. It went way above my head. But thanks for sharing.

    ReplyDelete
    Replies
    1. Thanks for the comment!
      Let me know if you need any explanation or clarification.

      Delete
  8. Maybe I'm late, but looks like
    unsigned int *stackBase;
    is not quite correctly, bcoz pointer in 64 bit arch is 64 bit and in my mind you should write
    unsigned long *stackBase;

    ReplyDelete
    Replies
    1. Pointers are 64 bit on 64 bit platforms, but this does not affect the size of the values they point at. stackBase points at an allocated array of 32 bit values, therefore, it is unsigned int *stackBase

      Delete
    2. =) maybe I think a little ahead, to map a region of memory from host to VM =) but in this case, you are right

      Delete
    3. I am afraid I missed the point. Do you mean to let the VM access "real" memory? If so, then there's no difference as you still have to parse the instruction and access the memory from your code, not from VM's

      Delete
  9. Hi Alexey,

    nice job, nice article, good points..... please, keep posting good and relevant material.

    Regards,
    Carlos Pratti

    ReplyDelete
    Replies
    1. Thanks Carlos :)

      Working on another article from VM series

      Delete
  10. This comment has been removed by a blog administrator.

    ReplyDelete
  11. Oh my GOD it's Wonderful Please keep sharing

    ReplyDelete
  12. I suppose I'm late commenting, but in case the author is still active, I would like to ask for an insight of the bin file. It's the only thing I don't fully understand how it works!

    ReplyDelete
    Replies
    1. Not as active as I would like to be, but still here. Go on shoot your question

      Delete
    2. If I understand it properly, vcpu_load opens the bin file and reads it, then uses it to fully initialise the values of a VM_HEADER struct (vmh). I have tried opening and reading the bin file to see how the values for each field of the header are decided, to no success. How is this step done?

      Thank you very much for the answer!

      Delete
    3. Well, values are stored in the file, in its header, meaning sizeof(VM_HEADER) first bytes. These bytes are read into the vmh variable. That's it.

      However, if your question is how those fields are populated, then take a look at the asm source. It is quite self explanatory.

      Delete

Note: Only a member of this blog may post a comment.