Rudroid - Writing the World's worst Android Emulator in Rust 🦀

Introduction

Rudroid - this might arguably be one of the worst Android emulators possible. In this blog, we'll write an emulator that can run a 'Hello World' Android ELF binary. While doing this, we will learn how to go about writing our own emulators.

Writing an emulator is an awesome way to study and probably master the low-level details of the system we are trying to emulate. I assume you have some working knowledge of Rust, a Linux machine with Rust installed or a Docker engine, and a lot of patience to go through the documentation of system calls, file formats, and more.

 

Topics we need to understand while writing Rudroid: - Basic Android Operating System Architecture - What are system calls - How system calls are handled in AArch64 - How memory mapping works - How the operating system loads an ELF into memory and runs it - How we can emulate the behavior of Operating system to load an ELF into memory and run

Let's start by reading the definition of Android:

Android is an open-source, Linux-based software stack created for a wide array of devices and form factors. The following diagram shows the major components of the Android platform.  

Kernel Architecture

The basic architecture of Linux kernel:

Core functionalities of a kernel are: - Process management - Device management - Memory management - Interrupt handling - Block I/O communication - File System Management

For writing an emulator that just runs an Android ELF binary, the most interesting kernel components are Memory Management, File System Management, Process Management and Interrupt handling, and System Call Interface via which ELF communicates with Kernel.

 

Signals: The kernel uses signals to call into a process. For example, signals are used to notify a process of certain faults, such as division by zero.

Processes and Scheduler: Creates, schedules, and manages processes.

Virtual Memory: Allocates and manages virtual memory for processes.

File Systems: Implements the file and filesystem-related interfaces for user-space to communicate with the underlying disks.

Traps and faults: Handles traps and faults generated by the processor, such as a memory fault.

Physical memory: Manages the pool of page frames in real memory and allocates pages for virtual memory.

Interrupts: Handles all the interrupts from peripheral devices.

System calls: The system call is the means by which a process requests a specific kernel service for example read from a file, write to file, execute a program. There are several hundred system calls, which can be roughly grouped into six categories:

* file system


* process


* scheduling


* interprocess communication (ipc)


* socket (networking)


* miscellaneous.

How do Emulators do what they do?

An emulator usually has an MMU to manage guest's memory requests, an instruction interpreter (decode -> translate -> execute), signal handlers, interrupt handlers.

These are the steps an emulator usually does: * load the target binary to memory * figure out the ISA of target binary * if emulator supports the ISA, initialize CPU * initialize signal handlers * initialize interrupt handlers * initialize syscall handlers * start CPU loop

What happens inside a CPU Loop: * fetch opcode to execute at Program Counter * increment Program Counter * decode opcode * translate opcode from emulated ISA to host ISA * execute the translated opcode * handle any raised signals/interrupts * continue the loop

Rudroid's Architecture

So, our Rudroid is just going to be a binary that implements an ELF loader, memory management, system call interface, filesystem. The final Rudroid's binary should take the ELF that prints 'Hello World' to stdout as command-line argument and execute it on the host. The command should look something like this:

# ./Rudroid hello_world.elf
hello world

We are going to run our Rudroid on a Linux machine. This is how our Rudroid's architecture is going to look like:

ELF loading process

We'll try not to dwell too much into the details of the ELF file format. Take a look at this comprehensive ELF standard here.

Executable (ELFs) and shared object files (libraries) statically represent programs. When you decide to run a binary, the operating system starts by setting up a new process for the program to run.

ELFs are composed of three major components: - an executable header (Ehdr) - Sections (section header are represented as Shdr) - Segments (also known as Program Headers are represented as Phdr)

Ehdr as defined in /usr/include/elf.h

typedef struct {
    unsigned char e_ident[16]; /* Magic number and other info */
    uint16_t e_type; /* Object file type */
    uint16_t e_machine; /* Architecture */
    uint32_t e_version; /* Object file version */
    uint64_t e_entry; /* Entry point virtual address */
    uint64_t e_phoff; /* Program header table file offset */
    uint64_t e_shoff; /* Section header table file offset */
    uint32_t e_flags; /* Processor-specific flags */
    uint16_t e_ehsize; /* ELF header size in bytes */
    uint16_t e_phentsize; /* Program header table entry size */
    uint16_t e_phnum; /* Program header table entry count */
    uint16_t e_shentsize; /* Section header table entry size */
    uint16_t e_shnum; /* Section header table entry count */
    uint16_t e_shstrndx; /* Section header string table index*/
} Elf64_Ehdr;

 

Phdr as defined in /usr/include/elf.h

typedef struct elf64_phdr {
  Elf64_Word p_type;
  Elf64_Word p_flags;
  Elf64_Off p_offset;       /* Segment file offset */
  Elf64_Addr p_vaddr;       /* Segment virtual address */
  Elf64_Addr p_paddr;       /* Segment physical address */
  Elf64_Xword p_filesz;     /* Segment size in file */
  Elf64_Xword p_memsz;      /* Segment size in memory */
  Elf64_Xword p_align;      /* Segment alignment, file & memory */
} Elf64_Phdr;

 

Shdr as defined in /usr/include/elf.h

typedef struct elf64_shdr {
  Elf64_Word sh_name;       /* Section name, index in string tbl */
  Elf64_Word sh_type;       /* Type of section */
  Elf64_Xword sh_flags;     /* Miscellaneous section attributes */
  Elf64_Addr sh_addr;       /* Section virtual addr at execution */
  Elf64_Off sh_offset;      /* Section file offset */
  Elf64_Xword sh_size;      /* Size of section in bytes */
  Elf64_Word sh_link;       /* Index of another section */
  Elf64_Word sh_info;       /* Additional section information */
  Elf64_Xword sh_addralign; /* Section alignment */
  Elf64_Xword sh_entsize;   /* Entry size if section holds table */
} Elf64_Shdr;

The kernel only really cares about Ehdr and Phdrs and only three types of program header entries: - PT_LOAD : Loadable Segment - PT_INTERP : Segment holding .interp section - PT_GNU_STACK : flag to set program's stack to executable

The ELF loader in the kernel starts loading ELF by first examining the ELF header to check the validity of ELF. After this, the loader now loops over the program header entries, looking for PT_LOAD and PT_INTERP. For every PT_LOAD entry, the loader maps memory at load_address + phdr_header.p_vaddr of size phdr_header.mem_size and copies the contents of the segment into allocated memory. If PT_INTERP is found, the loader again parses this as an ELF file and maps it into memory, and keeps track of the entrypoints of the main ELF file and interpreter's ELF file.

Once this is done, the loader starts setting up and populating the stack with auxiliary vector (ELF tables), environment variables, and command-line arguments passed to the ELF. An ELF auxiliary vector is an (id, value) pair that describes useful information about the program being run and the environment it is running in.

For this, we need an ELF parser in rust. We can either write our own ELF parser or use an already existing xmas-elf crate.

Before we could start writing an ELF loader, we also need a memory manager as we have to map the ELF into memory, manage stack, etc. Let's look at how a memory manager works.

Memory Management (MMU)

Linux memory management subsystem is responsible, as the name implies, for managing the memory in the system. This includes implementation of virtual memory and demand paging, memory allocation both for kernel internal structures and userspace programs, mapping of files into processes address space, and many other cool things.  

It provides functionality to map and unmap memory allocations. We have to implement these functionalities: - map memory at a given location or of a given size - unmap memory at a given location or of a given size - read from memory - write to memory - manage permissions of the memory  

Mapping ranges from an address to address + size_of_the_mapping. We can look at mmap reference from the manual here.  

void *mmap(void *addr, size_t length, int prot, int flags,
                  int fd, off_t offset);
````

mmap() creates a new mapping in the virtual address space of the calling process. The starting address for the new mapping is specified in addr. The length argument specifies the length of the mapping (which must be greater than 0).

Memory protections:

```c
PROT_EXEC
    Pages may be executed.

PROT_READ
    Pages may be read.

PROT_WRITE
    Pages may be written.

PROT_NONE
    Pages may not be accessed.

Unicorn Engine offers this functionality:

    /// Map a memory region in the emulator at the specified address.
    ///
    /// `address` must be aligned to 4kb or this will return `Error::ARG`.
    /// `size` must be a multiple of 4kb or this will return `Error::ARG`.
    pub fn mem_map(&mut self, 
            address: u64, 
            size: libc::size_t, 
            perms: Protection
    ) -> Result<(), uc_error>;


    /// Unmap a memory region.
    ///
    /// `address` must be aligned to 4kb or this will return `Error::ARG`.
    /// `size` must be a multiple of 4kb or this will return `Error::ARG`.
    pub fn mem_unmap(&mut self, 
            address: u64, 
            size: libc::size_t
    ) -> Result<(), uc_error>;


    /// Set the memory permissions for an existing memory region.
    ///
    /// `address` must be aligned to 4kb or this will return `Error::ARG`.
    /// `size` must be a multiple of 4kb or this will return `Error::ARG`.
    pub fn mem_protect(&mut self, 
            address: u64, 
            size: libc::size_t, 
            perms: Protection
    ) -> Result<(), uc_error> {
        let err = unsafe { ffi::uc_mem_protect(self.uc, address, size, perms.bits()) };
        if err == uc_error::OK {
            Ok(())
        } else {
            Err(err)
        }
    }

 

We can define protections and mapping as structs in rust:

bitflags! {
#[repr(C)]
pub struct Protection : u32 {
        const NONE = 0;
        const READ = 1;
        const WRITE = 2;
        const EXEC = 4;
        const ALL = 7;
    }
}

pub struct MapInfo {
    pub memory_start    : u64,
    pub memory_end      : u64,
    pub memory_perms    : Protection,
    pub description     : String,
}

Using these mem_map, mem_unmap functions from Unicorn, We can implement our MMU as a hashmap of starting address and MapInfo struct.

We'll also look at how system calls work and then start writing our Emulator.

System Calls

A system call is a routine that allows a user application to request actions that require special privileges or functionalities. Adding system calls is one of several ways to extend the functions provided by the kernel.  

In AArch64, there are special instructions for making such system calls. These instructions cause an exception, which allows controlled entry into a more privileged Exception level.

• SVC - Supervisor call: Causes an exception targeting EL1. Used by an application to call the OS.
• HVC - Hypervisor call: Causes an exception targeting EL2. Used by an OS to call the hypervisor, not available at EL0.
• SMC - Secure monitor call: Causes an exception targeting EL3. Used by an OS or hypervisor to call the EL3 firmware, not available at EL0.

 

InAArch64, the system call number is passed in X8 register and the return value in X0 register. We will use Unicorn's hooks to hook onto these SVC calls and execute the corresponding system call and return the results.

AArch64 Instruction Emulation

Since writing emulating all the AArch64 instructions is a tedious job, we will make use of Unicorn Engine for emulating the instructions. We will still see how it works.

impl rudroid

Finally, we'll start writing the code for our Rudroid. Let's see how easy or complex it will be.

I'm going to use a Linux Docker container on my Apple M1 as the host for running Rudroid.

Rudroid's Dockerfile:

Dockerfile

```dockerfile FROM rust:latest

RUN apt update -y RUN apt install -y nano cmake

WORKDIR /setup RUN git clone https://github.com/unicorn-engine/unicorn/ WORKDIR /setup/unicorn/ RUN ./make.sh RUN ./make.sh install

WORKDIR /setup/ RUN git clone https://github.com/keystone-engine/keystone/ RUN mkdir build WORKDIR /setup/keystone/build RUN ../make-share.sh RUN make install

RUN cp /usr/local/lib/libkeystone.so* /usr/lib/

RUN apt-get ins