从做题到出题再到做题三部曲-VM
前言
VM的题目相信对于CTF老鸟来说已经不陌生了，基本上每场比赛都会出现，通常会作为签到题或者简单题。
对于刚接触的小白来说，确实会感到十分棘手，不过一旦理解什么是VM，那么这种题就是体力活了（汗！）
为此我想从做题者和出题者的角度来理解VM，同时自己也做一个总结。
由于代码拿去出题了，不便公开，所以网上找了个简单的VM实现
基本介绍
参考自《加密与解密》
VMP：也就是虚拟机保护技术，它是将基于x86汇编系统的可执行代码转换为字节码指令系统的代码，以达到保护原有指令不被轻易逆向和篡改的目的。这种指令执行系统和Intel的x86指令系统不在同一个层次中。
字节码（Bytecode）：是由指令执行系统定义的一套指令和数据组成的一串数据流，由于每个系统设计的字节码都是供自己使用的，因此他们之间的字节码并不通用。
虚拟机执行时的情况：
VStartVM将真实环境压入栈后会生成一个VMDispather标签，当Handler执行完毕后会跳回这里，形成一个循环，所以VStratVM，也叫做dispather
网上有篇别人写的笔记可以参考，这里不再赘述
做题
护网杯的refinal我之前做过较为详细的分析，可以参考此文，因此这里就不在分析了。
分析VM题的一般套路：
- 提取出bytecode
- 根据op代入函数
- 转化成伪汇编代码
- 转化成高级语言代码(C/C++/Python)
- 逆向算法，写出解密脚本
出题
这里主要还是讲一下出题。
首先一条指令由操作符、操作地址和操作数组成。为简单起见，操作符可以如下定义：
typedef enum {
NOOP = 0,
IADD = 1, // int add
ISUB = 2,
IMUL = 3,
ILT = 4, // int less than
IEQ = 5, // int equal
BR = 6, // branch
BRT = 7, // branch if true
BRF = 8, // branch if false
ICONST = 9, // push constant integer
LOAD = 10, // load from local context
GLOAD = 11, // load from global memory
STORE = 12, // store in local context
GSTORE = 13, // store in global memory
PRINT = 14, // print stack top
POP = 15, // throw away top of stack
HALT = 16 //over
} VM_CODE;然后我们需要编写一个VStartVM,也就是VM的入口函数，将所有的寄存器压栈，设置VM的ip，sp，fp，定义出全局变量的大小，并为stack分配空间，初始化完成后，便进入了VMDispatcher循环，根据一些特殊的条件退出循环。
为了简单起见，我们一条指令只有两字节操作数+操作地址将操作数压入栈中，通过操作地址来获取。
定义一个常量的代码可以如下实现：
case ICONST:
stack[++sp] = code[ip++];//将操作符后的数据压入vm的stack中
break;将常量压入stack后，还需要将其存储到相对vm是固定位置的地方去，因此需要使用fp+offset的方法。
存储一个常量的代码可以如下实现：
case STORE:
offset = code[ip++];
stack[fp+offset] = stack[sp--];
break;因此定义一个常量并存储的伪指令可以如下：
ICONST,10,
STORE,0加减运算可以如下实现：
case IADD:
b = stack[sp--]; // 2nd opnd at top of stack
a = stack[sp--]; // 1st opnd 1 below top
stack[++sp] = a + b; // push result
break;由于此时的数据通常在fp+offset中，我们需要加载到当前的栈上进行运算，加载变量的实现可以如下：
case GLOAD: // load from global memory
addr = code[ip++];
stack[++sp] = globals[addr];
break;因此加法运算的伪指令可以如下：
加载需要进行运算的两个操作数
GLOAD,0, // 假设 0 为 I
ICONST,1, // 引入常量 1
IADD, // I+1
STORE,1 // I = I + 1接下来还需要实现判断以及跳转，其实这两者是联系在一起的，所以结合起来考虑，跳转指令只需要实现三种方式即可，其余均靠比较条件实现。
直接跳转
TRUE 跳转
FALSE 跳转首先是将判断的结果保留在栈顶。
相等和小于的判断可以如下实现：
case ILT:
b = stack[sp--];
a = stack[sp--];
stack[++sp] = (a < b) ? TRUE : FALSE;
break;
case IEQ:
b = stack[sp--];
a = stack[sp--];
stack[++sp] = (a == b) ? TRUE : FALSE;
break;跳转指令可以如下实现：
直接跳转：
case BR:
ip = code[ip];
break;
当前栈顶为TRUE则跳转：
case BRT:
addr = code[ip++];
if (stack[sp--] == TRUE) ip = addr;
break;
当前栈顶为FALSE则跳转：
case BRF:
addr = code[ip++];
if (stack[sp--] == FALSE) ip = addr;
break;因此一个简单的条件转移的伪指令可以如下：
GLOAD, 1, // 12
GLOAD, 0, // 14
ILT, // 16 A是否小于B
BRT, 35, //如果 A<B 则跳转到addr 35 处至此我们已经实现了一个VM的基本功能，从代码上来看，并不复杂，理解起来也十分的简单。
做题
结合着源代码一起逆向分析VM
分析
通常来说，正常的VM题，第一步需要找到VM的入口函数，在其入口处参数往往能暴露出很多信息。
loop2是如下的数据
这就是伪代码，也就是Bytecode,接下来就需要将Bytecode逐步的根据opcode转化为伪汇编代码，最后转换为高级语言，进而写出解密脚本。这是一般套路，不过在这里用不到。
VM的题一般不会去静态分析opcode的功能，通常采用动态调试的方法，搭好环境我们开始。
当进入while循环时，读取第一个opcode
程序根据opcode执行到对应的handler,此时我们不能继续关注当前的stack，而是应该关注VM的stack。
注意到此时的VMStack在esp+0x50的位置，并且将code[1]传递给了stack[sp]
_sp指向的便是VM的栈顶，由于事先预设了stack的大小为1000，因此程序的栈并不会将VM的栈覆盖，这一点在设计VM的时候需要注意。
每次运算完成后，将结果保存在栈顶，通常的VM会取用到栈顶元素，对其进行操作
所以09 03相当于是r1 = 03,为了便于观察，我们将stack固定住，使其反应出VM的stack，设置也很简单，将stack同步取消即可。
继续走，程序会逐个识别Bytecode，并执行相应的功能，通常我会这样来组织，并将中间过程如下记录。
bytecode.txt
bytecode
opcode 伪代码 addr 高级语言
0x09,0x03 r0 = 3 0 // init
0x0D,0x00 d0 = r1 =3 2 i = 0
0x09,0x00 r0 = 0 4 N = 3
0x0D,0x01 d1 = r0 = 0 6 sum = 0
0x09,0x00 r0 = 0 8
0x0D,0x02 d2 = r0 = 0 10
0x0B,0x01 r0 = d1 = 0 12 while(i<N)
0x0B,0x00 r1 = d0 = 3 14
0x04, JL 16
0x08,0x23 jmp code-offset 0x23(35) 17
0x0B,0x01, r0 = d1 = 0 19
0x09,0x01, r1 = 1 21
0x01, r0 = r0+r1 = 1 23 i = i + 1
0x0D,0x01, d1 = r0 = 1 24
0x0B,0x02, r0 = d2 = 0 26
0x0B,0x01, r1 = d1 = 1 28
0x01, r0 = r0 + r1 = 1 30 sum = sum + i
0x0D,0x02, d2 = r0 = 1 31
0x06,0x0C, jmp 0xc(12) 33
0x0B,0x02, r0 = d2 = ? 35 print sum
0x0E, print r0 37
0x10, exit 38当然如果觉得有必要为了简化手动分析的工作量，我们可以写一个interpreter来翻译伪指令，使其便于我们的分析。
以下代码仅仅作为参考，因为就像之前所说，VM是没有通用的interpreter的，因此第一步还是需要分析出各个handler的功能，然后进行后续的分析。通常只有在遇到代码量较大的bytecode时才会选择去编写一个针对性的interpreter。
#-*-coding:utf-8-*-
code=[0x09,0x03,0x0D,0x00,0x09,0x00,0x0D,0x01,0x09,0x00,0x0D,0x02,0x0B,0x01,0x0B,0x00,0x04,0x08,0x23,0x0B,0x01,0x09,0x01,0x01,0x0D,0x01,0x0B,0x02,0x0B,0x01,0x01,0x0D,0x02,0x06,0x0C,0x0B,0x02,0x0E,0x10]
def interpreter():
inst = {
0: "noop",
1: "iadd",
2: "isub",
3: "imul",
4: "ilt",
5: "ieq",
6: "br",
7: "brt",
8: "brf",
9: "iconst",
10: "load",
11: "gload",
12: "store",
13: "gstore",
14: "print",
15: "pop",
16: "halt",
}
index = 0
while 1:
op = code[index]
if inst[op] == "halt" :
print "%s: exit" % (inst[op])
break
if inst[op] == "iadd" :
print "%s: r0 = r0 + r1" % (inst[op])
index = index + 1
continue
if inst[op] == "print" :
print "%s: " % (inst[op])
index = index + 1
continue
if inst[op] == "gstore" :
d_index = code[index+1]
print "%s: d%d = r0" % (inst[op],d_index)
index = index + 2
continue
if inst[op] == "ilt" :
print "%s: JL" % (inst[op])
index = index + 1
continue
if inst[op] == "brf" :
d_index = code[index+1]
print "%s: jmp %d" % (inst[op],d_index)
index = index + 2
continue
if inst[op] == "br" :
d_index = code[index+1]
print "%s: jmp %d" % (inst[op],d_index)
index = index + 2
continue
if inst[op] == "gload" :
d_index = code[index+1]
print "%s: r0 = d%d " % (inst[op],d_index)
index = index + 2
continue
if inst[op] == "iconst" :
d_index = code[index+1]
print "%s: r0 = %d " % (inst[op],d_index)
index = index + 2
continue
index = index + 1
interpreter()
运行结果如下：
总结
如果理解了VM，那么完全可以自己开发一个VM，用自己写的VM来保护核心代码，这真的是棒极了！
题目代码
vm.h
#ifndef VM_H_
#define VM_H_
#ifdef __cplusplus
extern "C" {
#endif
typedef enum {
NOOP = 0,
IADD = 1, // int add
ISUB = 2,
IMUL = 3,
ILT = 4, // int less than
IEQ = 5, // int equal
BR = 6, // branch
BRT = 7, // branch if true
BRF = 8, // branch if false
ICONST = 9, // push constant integer
LOAD = 10, // load from local context
GLOAD = 11, // load from global memory
STORE = 12, // store in local context
GSTORE = 13, // store in global memory
PRINT = 14, // print stack top
POP = 15, // throw away top of stack
HALT = 16 //over
} VM_CODE;
void vm_exec(int *code, int count, int startip, int nglobals, int trace);
#ifdef __cplusplus
}
#endif
#endifvm.c
#include <stdio.h>
#include <stdlib.h>
#include "vm.h"
#define DEFAULT_STACK_SIZE 1000
#define FALSE 0
#define TRUE 1
typedef struct {
char name[8];
int nargs;
} VM_INSTRUCTION;
VM_INSTRUCTION vm_instructions[] = {
{ "noop", 0 },
{ "iadd", 0 },
{ "isub", 0 },
{ "imul", 0 },
{ "ilt", 0 },
{ "ieq", 0 },
{ "ret", 0 },
{ "br", 1 },
{ "brt", 1 },
{ "brf", 1 },
{ "iconst", 1 },
{ "load", 1 },
{ "gload", 1 },
{ "store", 1 },
{ "gstore", 1 },
{ "print", 0 },
{ "pop", 0 },
{ "halt", 0 }
};
static void vm_print_instr(int *code, int ip);
static void vm_print_stack(int *stack, int count);
static void vm_print_data(int *globals, int count);
void vm_exec(int *code, int count, int startip, int nglobals, int trace)
{
// registers
int ip = 0; // instruction pointer register
int sp = -1; // stack pointer register
int fp = -1; // frame pointer register
int opcode = code[ip];
int a = 0;
int b = 0;
int addr = 0;
int offset = 0;
// global variable space
int globals[nglobals];
// Operand stack, grows upwards
int stack[DEFAULT_STACK_SIZE];
while (opcode != HALT && ip < count) {
if (trace) vm_print_instr(code, ip);
ip++; //jump to next instruction or to operand
switch (opcode) {
case IADD:
b = stack[sp--]; // 2nd opnd at top of stack
a = stack[sp--]; // 1st opnd 1 below top
stack[++sp] = a + b; // push result
break;
case ISUB:
b = stack[sp--];
a = stack[sp--];
stack[++sp] = a - b;
break;
case IMUL:
b = stack[sp--];
a = stack[sp--];
stack[++sp] = a * b;
break;
case ILT:
b = stack[sp--];
a = stack[sp--];
stack[++sp] = (a < b) ? TRUE : FALSE;
break;
case IEQ:
b = stack[sp--];
a = stack[sp--];
stack[++sp] = (a == b) ? TRUE : FALSE;
break;
case BR:
ip = code[ip];
break;
case BRT:
addr = code[ip++];
if (stack[sp--] == TRUE) ip = addr;
break;
case BRF:
addr = code[ip++];
if (stack[sp--] == FALSE) ip = addr;
break;
case ICONST:
stack[++sp] = code[ip++]; // push operand
break;
case LOAD: // load local or arg; 1st local is fp+1, args are fp-3, fp-4, fp-5, ...
offset = code[ip++];
stack[++sp] = stack[fp+offset];
break;
case GLOAD: // load from global memory
addr = code[ip++];
stack[++sp] = globals[addr];
break;
case STORE:
offset = code[ip++];
stack[fp+offset] = stack[sp--];
break;
case GSTORE:
addr = code[ip++];
globals[addr] = stack[sp--];
break;
case PRINT:
printf("%x\n", stack[sp--]);
break;
case POP:
--sp;
break;
default:
printf("invalid opcode: %d at ip=%d\n", opcode, (ip - 1));
exit(1);
}
if (trace) vm_print_stack(stack, sp);
opcode = code[ip];
}
if (trace) vm_print_instr(code, ip);
if (trace) vm_print_stack(stack, sp);
if (trace) vm_print_data(globals, nglobals);
}
static void vm_print_instr(int *code, int ip)
{
int opcode = code[ip];
VM_INSTRUCTION *inst = &vm_instructions[opcode];
switch (inst->nargs) {
case 0:
printf("%04d: %-20s", ip, inst->name);
break;
case 1:
printf("%04d: %-10s%-10d", ip, inst->name, code[ip + 1]);
break;
}
}
static void vm_print_stack(int *stack, int count)
{
printf("stack=[");
for (int i = 0; i <= count; i++) {
printf(" %d", stack[i]);
}
printf(" ]\n");
}
static void vm_print_data(int *globals, int count)
{
printf("Data memory:\n");
for (int i = 0; i < count; i++) {
printf("%04d: %d\n", i, globals[i]);
}
}vmtest.c
#include <stdio.h>
#include <time.h>
#include "vm.h"
int loop2[] = {
// .GLOBALS 2; N, I
// N = 10 ADDRESS
ICONST, 3, // 0
GSTORE, 0, // 2
// I = 0
ICONST, 0, // 4
GSTORE, 1, // 6
// SUM = 0
ICONST,0, //8
GSTORE,2, //10
// WHILE I<N:
// START (8):
GLOAD, 1, // 12
GLOAD, 0, // 14
ILT, // 16
BRF, 35, // 17
// I = I + 1
GLOAD, 1, // 19
ICONST, 1, // 21
IADD, // 23
GSTORE, 1, // 24
//sum = sum +i
GLOAD,2, //26
GLOAD,1, //28
IADD, //30
GSTORE,2, //31
BR, 12, // 33
GLOAD,2, //35
PRINT, //37
// DONE (24):
// PRINT "LOOPED "+N+" TIMES."
HALT // 38
};
int main(int argc, char *argv[])
{
// vm_exec(hello, sizeof(hello), 0, 0, 1);
vm_exec(loop2, sizeof(loop2), 0, 2, 0);
return 0;
}