详细实验地址：https://justinmeiners.github.io/lc3-vm/index.html#1:12

本质上是在用C语言描述16位机器的操作过程，因此可以以此为一个架接运行一个16位程序，因此成为虚拟机（Virtual Machine）；

前置要求：C语言（写出虚拟机的语言），位运算，汇编代码的运行模式（虚拟机的工作方式，不懂汇编代码的意思也没关系），丁点API知识（键盘传输和屏幕显示，以及内存收取等），LC-3指令集（模拟指令OP）；

指令集地址：https://justinmeiners.github.io/lc3-vm/supplies/lc3-isa.pdf

思路：

1. 读取文件

既然要读取其他程序和文件，那需要构造一个内存池容纳16位的程序，总大小也就是二的十六次方；

代码1-1：

1
2
/* 65536 locations */
uint16_t memory[UINT16_MAX];	//Memory Storage

文件读入主要代码1-2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (argc < 2)
{
    /* show usage string */
    printf("usage: %s [image-file1] ...\n", argv[0]);
    exit(2);
}

for (int j = 1; j < argc; ++j)
{
    if (!read_image(argv[j]))
    {
        printf("failed to load image: %s\n", argv[j]);
        exit(1);
    }
}

补充说明：argc 和 argv 是 main 函数参数，第一个代表main参数个数，第二个代表为地址的参数；

作用：如果没有输入main函数的参数，第一个判断就会提示用法为： ./main [image-file1] ；如果输入[image-file1]这个参数，那么就会将其读入for循环中，用 read_image() 函数计算参数并判断，若返回值是0，就会说：装载映像失败；

这里显示出一个函数叫 read_image() ，下面说说它的作用：

代码1-3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void read_image_file(FILE* file)
{
    /* the origin tells us where in memory to place the image */
    uint16_t origin;
    fread(&origin, sizeof(origin), 1, file);
    origin = swap16(origin);

    /* we know the maximum file size so we only need one fread */
    uint16_t max_read = UINT16_MAX - origin;
    uint16_t* p = memory + origin;
    size_t read = fread(p, sizeof(uint16_t), max_read, file);

    /* swap to little endian */
    while (read-- > 0)
    {
        *p = swap16(*p);
        ++p;
    }
}

int read_image(const char* image_path)
{
    FILE* file = fopen(image_path, "rb");
    if (!file) { return 0; };
    read_image_file(file);
    fclose(file);
    return 1;
}

这段代码中有两个函数，最后一个就是1-2中提到的，他的作用就是判断输入的参数地址是否为正确文件地址；如果不是就返回1，进而让1-2的判断输出错误并中断程序；如果是就执行 read_image_file() 函数；

read_image_file() 函数的作用便是将读取的程序内存装入之前设定好的memory数组中；首先计算的起始地址：origin，使用fread() C原装函数，读取起始地址；之后计算最大可容纳地址，并用p指针标记，最后使用循环不断缩小范围；

至于为什么要使用swap16()函数呢？因为LC-3程序是大端序排列，一般电脑用的都是小端序，所以要交换高低8位；

代码1-4：

1
2
3
4
uint16_t swap16(uint16_t x)
{
    return (x << 8) | (x >> 8);
}

2. 内存访问

某些特殊寄存器无法从普通寄存器表中访问。相反，在内存中为它们保留一个特殊地址。要读取和写入这些寄存器，只需读取和写入它们的内存位置即可。这些称为内存映射寄存器。它们通常用于与特殊硬件设备进行交互（如键盘）；

LC-3 具有两个需要实现的内存映射寄存器。它们是键盘状态寄存器 （） 和键盘数据寄存器 （）。指示是否已按下某个键，并标识按下了哪个键；

代码2-1：

1
2
3
4
5
enum	//Memory Mapped Registers
{
    MR_KBSR = 0xFE00, /* keyboard status */
    MR_KBDR = 0xFE02  /* keyboard data */
};

上面是模拟LC-3 的两个内存寄存器；第一个为状态管理，第二个是数据管理；

代码2-2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
uint16_t check_key()
{
    return WaitForSingleObject(hStdin, 1000) == WAIT_OBJECT_0 && _kbhit();
}

void mem_write(uint16_t address, uint16_t val)
{
    memory[address] = val;
}

uint16_t mem_read(uint16_t address)
{
    if (address == MR_KBSR)
    {
        if (check_key())
        {
            memory[MR_KBSR] = (1 << 15);
            memory[MR_KBDR] = getchar();
        }
        else
        {
            memory[MR_KBSR] = 0;
        }
    }
    return memory[address];
}

这里给出三个函数；第一个是设置windows终端输入的代码（调用API）；第二个是写入内存的代码；第三个是读入内存的代码；

3. 模拟寄存器

既然要模拟汇编代码的运行模式，那就少不掉寄存器；在汇编代码中，寄存器就相当于C的变量，保存数据用；

LC-3中，一共只有10个寄存器，8个通用，1个指向即将执行的代码的寄存器(PC)，1个条件控制寄存器；

代码3-1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enum	//Registers
{
    R_R0 = 0,
    R_R1,
    R_R2,
    R_R3,
    R_R4,
    R_R5,
    R_R6,
    R_R7,
    R_PC, /* program counter */
    R_COND,
    R_COUNT
};

这里多设置了一个，R_COUNT不是寄存器，只是计数用的，因为是从0开始数的；

之后用这个来控制寄存器：

代码3-2：

1
uint16_t reg[R_COUNT];	//Register Storage

而控制寄存器需要特别加一个枚举：

代码3-3：

1
2
3
4
5
6
enum	//condition flags
{
    FL_POS = 1 << 0, /* P */
    FL_ZRO = 1 << 1, /* Z */
    FL_NEG = 1 << 2, /* N */
};

结果为正数则是P，为0则是Z，为负数则是N；它们的计算结果分别是：1，2，4；用到它们的时候，这些数字就代表它们的意义；而实际上是用移位来模拟这些条件位在寄存器中的形式；

4. 模拟指令

这里就是LC-3需要用到的指令，于是模拟出所有会用到的：

代码4-1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
enum
{
    OP_BR = 0, /* branch */
    OP_ADD,    /* add  */
    OP_LD,     /* load */
    OP_ST,     /* store */
    OP_JSR,    /* jump register */
    OP_AND,    /* bitwise and */
    OP_LDR,    /* load register */
    OP_STR,    /* store register */
    OP_RTI,    /* unused */
    OP_NOT,    /* bitwise not */
    OP_LDI,    /* load indirect */
    OP_STI,    /* store indirect */
    OP_JMP,    /* jump */
    OP_RES,    /* reserved (unused) */
    OP_LEA,    /* load effective address */
    OP_TRAP    /* execute trap */
};

它们实现机器所需要的运算；

而LC-3的运算中，因为是16位，所以这些指令会放在最高的4位判断，剩下的位数就会放参数一类的东西，每个运算的参数需求位都不同，详细请看LC-3指令集；指令集中会要求使用的参数需要扩展为16位运算；所以需要接下来的函数：

代码4-2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
uint16_t sign_extend(uint16_t x, int bit_count)
{
    if ((x >> (bit_count - 1)) & 1) {
        x |= (0xFFFF << bit_count);
    }
    return x;
}


void update_flags(uint16_t r)
{
    if (reg[r] == 0)
    {
        reg[R_COND] = FL_ZRO;
    }
    else if (reg[r] >> 15) /* a 1 in the left-most bit indicates negative */
    {
        reg[R_COND] = FL_NEG;
    }
    else
    {
        reg[R_COND] = FL_POS;
    }
}

第一个函数的作用便是 带符号扩展 位数；第二个函数的作用便是每次运算结束后，调整条件控制寄存器中的三个值；

5. 模拟执行过程

这是逆向题中的核心思想，便是C语言如何执行虚拟机模式的，如何找到flag的指令生成顺序；

以下是我们需要编写的过程：

  1. 从寄存器地址处的内存中加载一条指令。PC
  2. 递增寄存器。PC
  3. 查看操作码以确定它应该执行哪种类型的指令。
  4. 使用指令中的参数执行指令。
  5. 返回步骤 1。

这样一来，就能模拟出虚拟机的内核了；

代码5：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
int main(int argc, const char* argv[])
{
    {代码1-2}
    {代码7-3}

    /* since exactly one condition flag should be set at any given time, set the Z flag */
    reg[R_COND] = FL_ZRO;

    /* set the PC to starting position */
    /* 0x3000 is the default */
    enum { PC_START = 0x3000 };
    reg[R_PC] = PC_START;

    int running = 1;
    while (running)
    {
        /* FETCH */
        uint16_t instr = mem_read(reg[R_PC]++);
        uint16_t op = instr >> 12;

        switch (op)
        {
            case OP_ADD:
                {代码6-1}
                break;
            case OP_AND:
                {代码6-2}
                break;
            case OP_NOT:
                {代码6-3}
                break;
            case OP_BR:
                {代码6-4}
                break;
            case OP_JMP:
                {代码6-5}
                break;
            case OP_JSR:
                {代码6-6}
                break;
            case OP_LD:
                {代码6-7}
                break;
            case OP_LDI:
                {代码6-8}
                break;
            case OP_LDR:
                {代码6-9}
                break;
            case OP_LEA:
                {代码6-10}
                break;
            case OP_ST:
                {代码6-11}
                break;
            case OP_STI:
                {代码6-12}
                break;
            case OP_STR:
                {代码6-13}
                break;
            case OP_TRAP:
                {代码6-15}
                break;
            case OP_RES:
            case OP_RTI:
            default:
                abort();
                break;
        }
    }
    {代码7-4}
}

初始化条件控制寄存器后，从0x3000的地址出发，并进入运行状态（ while(1) ），instr便是每次会执行的PC所指的指令内容；OP即为操作指令，因为总共16位的寄存器最高4位都是操作指令，所以只需要将instr右移12位就能得到OP；

之后根据switch选择OP，执行相应的指令；每执行完一条便循环回去，于是PC+1，开始执行下一条；

6. C语言模拟指令清单

核心内容，需要结合指令集理解怎么实现的；

代码6-1：和的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
{
    /* destination register (DR) */
    uint16_t r0 = (instr >> 9) & 0x7;
    /* first operand (SR1) */
    uint16_t r1 = (instr >> 6) & 0x7;
    /* whether we are in immediate mode */
    uint16_t imm_flag = (instr >> 5) & 0x1;

    if (imm_flag)
    {
        uint16_t imm5 = sign_extend(instr & 0x1F, 5);
        reg[r0] = reg[r1] + imm5;
    }
    else
    {
        uint16_t r2 = instr & 0x7;
        reg[r0] = reg[r1] + reg[r2];
    }

    update_flags(r0);
}

代码6-2：按位和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t imm_flag = (instr >> 5) & 0x1;

    if (imm_flag)
    {
        uint16_t imm5 = sign_extend(instr & 0x1F, 5);
        reg[r0] = reg[r1] & imm5;
    }
    else
    {
        uint16_t r2 = instr & 0x7;
        reg[r0] = reg[r1] & reg[r2];
    }
    update_flags(r0);
}

代码6-3：按位非

1
2
3
4
5
6
7
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;

    reg[r0] = ~reg[r1];
    update_flags(r0);
}

代码6-4：分支

1
2
3
4
5
6
7
8
{
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    uint16_t cond_flag = (instr >> 9) & 0x7;
    if (cond_flag & reg[R_COND])
    {
        reg[R_PC] += pc_offset;
    }
}

代码6-5：跳转

1
2
3
4
5
{
    /* Also handles RET */
    uint16_t r1 = (instr >> 6) & 0x7;
    reg[R_PC] = reg[r1];
}

代码6-6：寄存器跳转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
    uint16_t long_flag = (instr >> 11) & 1;
    reg[R_R7] = reg[R_PC];
    if (long_flag)
    {
        uint16_t long_pc_offset = sign_extend(instr & 0x7FF, 11);
        reg[R_PC] += long_pc_offset;  /* JSR */
    }
    else
    {
        uint16_t r1 = (instr >> 6) & 0x7;
        reg[R_PC] = reg[r1]; /* JSRR */
    }
    break;
}

代码6-7：加载

1
2
3
4
5
6
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    reg[r0] = mem_read(reg[R_PC] + pc_offset);
    update_flags(r0);
}

代码6-8：简介加载的实现

1
2
3
4
5
6
7
8
9
{
    /* destination register (DR) */
    uint16_t r0 = (instr >> 9) & 0x7;
    /* PCoffset 9*/
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    /* add pc_offset to the current PC, look at that memory location to get the final address */
    reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset));
    update_flags(r0);
}

代码6-9：加载寄存器

1
2
3
4
5
6
7
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t offset = sign_extend(instr & 0x3F, 6);
    reg[r0] = mem_read(reg[r1] + offset);
    update_flags(r0);
}

代码6-10：加载有效地址

1
2
3
4
5
6
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    reg[r0] = reg[R_PC] + pc_offset;
    update_flags(r0);
}

代码6-11：存储

1
2
3
4
5
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    mem_write(reg[R_PC] + pc_offset, reg[r0]);
}

代码6-12：间接存储

1
2
3
4
5
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    mem_write(mem_read(reg[R_PC] + pc_offset), reg[r0]);
}

代码6-13：寄存器存储

1
2
3
4
5
6
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t offset = sign_extend(instr & 0x3F, 6);
    mem_write(reg[r1] + offset, reg[r0]);
}

LC-3 提供了一些预定义的例程，用于执行常见任务和与 I/O 设备交互。例如，有一些例程用于从键盘获取输入以及用于向控制台显示字符串。这些称为trap routines，您可以将其视为LC-3的操作系统或API。每个trap routines都分配有一个trap code来标识它（类似于操作码）。要执行一个，请使用所需routine的code调用该指令；

枚举所有trap代码6-14：

1
2
3
4
5
6
7
8
9
enum
{
    TRAP_GETC = 0x20,  /* get character from keyboard, not echoed onto the terminal */
    TRAP_OUT = 0x21,   /* output a character */
    TRAP_PUTS = 0x22,  /* output a word string */
    TRAP_IN = 0x23,    /* get character from keyboard, echoed onto the terminal */
    TRAP_PUTSP = 0x24, /* output a byte string */
    TRAP_HALT = 0x25   /* halt the program */
};

为每个trap选择代码6-15：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
switch (instr & 0xFF)
{
    case TRAP_GETC:
        {代码6-16}
        break;
    case TRAP_OUT:
        {代码6-17}
        break;
    case TRAP_PUTS:
        {代码6-18}
        break;
    case TRAP_IN:
        {代码6-19}
        break;
    case TRAP_PUTSP:
        {代码6-20}
        break;
    case TRAP_HALT:
        {代码6-21}
        break;
}

trap指令清单：

代码6-16：输入字符

1
2
3
4
5
{
    /* read a single ASCII char */
	reg[R_R0] = (uint16_t)getchar();
	update_flags(R_R0);
}

代码6-17：输出字符

1
2
3
4
{
    putc((char)reg[R_R0], stdout);
	fflush(stdout);
}

代码6-18：输出字符

1
2
3
4
5
6
7
8
9
10
{
    /* one char per word */
    uint16_t* c = memory + reg[R_R0];
    while (*c)
    {
        putc((char)*c, stdout);
        ++c;
    }
    fflush(stdout);
}

代码6-19：准备输入字符

1
2
3
4
5
6
7
8
{
    printf("Enter a character: ");
    char c = getchar();
    putc(c, stdout);
    fflush(stdout);
    reg[R_R0] = (uint16_t)c;
    update_flags(R_R0);
}

代码6-20：输出字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
    /* one char per byte (two bytes per word)
       here we need to swap back to
       big endian format */
    uint16_t* c = memory + reg[R_R0];
    while (*c)
    {
        char char1 = (*c) & 0xFF;
        putc(char1, stdout);
        char char2 = (*c) >> 8;
        if (char2) putc(char2, stdout);
        ++c;
    }
    fflush(stdout);
}

代码6-21：终止程序

1
2
3
4
5
{
    puts("HALT");
	fflush(stdout);
	running = 0;
}

7. 头部添加以及windows加入API

加入的头部：

代码7-1：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdint.h> // uint16_t
#include <stdio.h>  // FILE
#include <signal.h> // SIGINT
/* windows only */
#include <Windows.h>
#include <conio.h>  // _kbhit

HANDLE hStdin = INVALID_HANDLE_VALUE;

#define UINT16_MAX 65536

加入API：

代码7-2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
DWORD fdwMode, fdwOldMode;

void disable_input_buffering()
{
    hStdin = GetStdHandle(STD_INPUT_HANDLE);
    GetConsoleMode(hStdin, &fdwOldMode); /* save old mode */
    fdwMode = fdwOldMode
            ^ ENABLE_ECHO_INPUT  /* no input echo */
            ^ ENABLE_LINE_INPUT; /* return when one or
                                    more characters are available */
    SetConsoleMode(hStdin, fdwMode); /* set new mode */
    FlushConsoleInputBuffer(hStdin); /* clear buffer */
}

void restore_input_buffering()
{
    SetConsoleMode(hStdin, fdwOldMode);
}

void handle_interrupt(int signal)
{
    restore_input_buffering();
    printf("\n");
    exit(-2);
}

代码7-3：初始化

1
2
signal(SIGINT, handle_interrupt);
disable_input_buffering();

代码7-4：释放

1
restore_input_buffering();

之后按顺序组装：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7-1
3-1
4-1
3-3
2-1
6-14
1-1
3-2
4-2
1-4
1-3
2-2
7-2
    
5

之后就可以得到一台16位的虚拟机；

总结

过了一遍VM实验过后对虚拟机有了一定理解，并且对之前所见的VM逆向题有了解题的思路，以及了解了LC-3指令集，和些许API函数的作用，由此更加理解一个源代码如何与其他文件产生共鸣；可以类比shell与程序之间的关系，更好地理解shell的作用和本质；

genshin