# Low-Level Computing Concepts

## Club Resources
* [Practice Problems](https://ctf.tjcsec.club)
* [Codespaces Desktop](https://github.com/dianalin2/desktop)
* [Shell Commands List](https://hackmd.io/@tjcsc/cmd)

While we know lots about higher-level abstractions in programming languages because we write Python, Java, and/or C, it is not very often that we look to how everything works "under the hood." For programmers, this often isn't necessary, but, for hackers, this is crucial! We need to know how everything works on a low, micro level in order to better reverse engineer and exploit programs.

## How Does a CPU Work?

The central processing unit (CPU) is the most important component of a computer. It is made of many smaller parts, including the arithmetic logic unit (ALU), which performs operations on numbers.


Since the CPU is made to quickly do instructions (i.e. operations), it is very useful to have a quick place for the CPU to store/access data during operations. **Registers** are places to hold data in a CPU. In code terms, you can think of these as simple "variables" that the user is able to change and manipulate via **instructions**, or simple commands.

Examples of general-purpose registers in x86-64 are `rax`, `rbx`, `rdx`, `rsi`, and `rdi`.

## Assembly

Instructions are given to the CPU as machine code, but it is very difficult for a human to read machine code because it consists of a series of bytes (numbers), which is not friendly to humans. Instead, people can write their code in **assembly**, which is (marginally) more human-readable. This assembly code is then converted in a 1-to-1 manner into machine code that the computer can easily read. That isn't to say that it is *easy* to read assembly, however. Here is a sample x86-64 program (written in NASM-style assembly) that simply loops from 0 to 100:

section .text
    global _start

_start:
    mov rax, 0

loop_start:
    cmp rax, 100
    jg loop_end

    ; loop body code goes here...

    inc rax
    jmp loop_start

loop_end: 
    mov rax, 60      ; syscall number for exit 
    xor rdi, rdi     ; exit code 0
    syscall          ; make syscall

This doesn't even do anything *inside* the loop. Programmers very rarely write in pure assembly nowadays because it is so difficult; however, it is very useful for reverse engineering! Let's walk through what this code does, noting that anything after `;` is a comment.

The `.text` segment includes the actual instructions that the computer runs during the program. In this program, `.text` segment includes every line in the program after line 4. `global _start` must be stated to define where the program should start. When the program starts, it will jump to the `_start` **label** (on line 7) and start executing the instructions under that label.

A label represents a "name" for a piece of data in the program. When this program is compiled, this label is converted into a raw memory address.

The first instruction that this program executes is `mov rax, 0`. The mov instruction "moves" a value (0) into a register (`rax`). All instructions are written in a similar manner: `opcode operand, operand, ..., operand`. For two-operand instructions, the first operand is often the *destination* operand and the second operand is often the *source* operand. The destination is where the results of the instruction are stored. Some examples of other arithmetic instructions are listed below:
* The `inc` instruction (shown on line 16) increments the specified register by one.
* The `xor` instruction (shown on line 22) runs the xor operation and stores the result in the first operand. In this case, xoring `rdi` with `rdi` zeroes out (or stores a zero in) the `rdi` register.
* The `add op1, op2` instruction (not shown in the example) adds `op2` to `op1`.
* The `sub op1, op2` instruction (not shown in the example) subtracts `op2` from `op1.`

### Branching

You may have noticed that I skipped over what `jmp`, `cmp`, and `jg` do. Using the `jmp` and `jg` instructions, we can "jump" to another place in memory to run instructions in a different location.

The `jmp` instruction is an unconditional jump that simply moves the code execution to another address (or label). On line 14, `jmp` is used to go back to the beginning of the loop procedure (which starts on line 7).

The `jg` instruction is a "conditional" jump that is usually associated with a comparison done by the `cmp` instruction. If the flags set by the comparison above are set to indicate that the first operand is greater than the second, the instruction moves execution to the specified address. More simply stated, lines 8 and 9 tell the program to jump to `loop_end` if `rax` is greater than 100.

There are many other conditional jumps, including `je` (jump if equal), `jl` (jump if less than or equal), `jle`, and `jge` (jump if greater than or equal).

### System Calls (syscalls)

Lines 34 to 36 perform a system call telling the computer to stop the current program's execution. This requests a service from the kernel, which means that it asks Linux to do something. There are many [syscall numbers](https://blog.rchapman.org/posts/Linux_System_Call_Table_for_x86_64/) associated with different kernel functions. To make a syscall, we have to do three things:
1. Store the syscall number in `rax`. This is done on line 17, setting the syscall number for `sys_exit` in `rax`.
2. Store the specified parameters (found in columns 3+ on the syscall table) in the registers to perform the syscall. For `sys_exit`, the only necessary parameter is the exit/error code, which is stored in `rdi`. By xoring `rdi` with itself, we set `rdi` to 0, making a 0 exit code.
3. Make the syscall, which is done with `syscall` on line 19.

## The Program Stack (Advanced)

The `push` and `pop` instructions interact with something called the "program stack", which is exactly like a [stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) in APCS. One can add a value to the stack by saying `push operand` and remove a value from the stack by saying `pop operand`. When a function is called, an address is pushed to the stack to ensure that we go back to the correct location when we return from the called function.

One difference from normal stacks that you might not expect from the program stack is that it grows down instead of up. This means that the top of the stack is at a lower memory address than the bottom of the stack.

The stack is accessed via the stack pointer register (`rsp`). `rsp` refers to the address at the top of the stack. When a value is pushed to the stack, 8 is subtracted from `rsp`. When a value is popped from the stack, 8 is added to `rsp`.

### Functions

I'm sure you are familiar with functions from other programming languages, but it turns out that functions are very high-level concepts, meaning they cannot be replicated with simple instructions. Instead, we should follow conventions set by people much smarter than me.[^1] For our purposes, we will be using the conventions laid out by the [System V ABI for x86-64](https://wiki.osdev.org/System_V_ABI). The System V ABI details info such as how functions are defined. It answers questions such as:
* Which registers must be preserved in function calls?
* How do function parameters get passed?
* How do values get returned from functions?

To call a function, we can use the `call` instruction. This is equivalent to `push address-of-instruction-to-return-to` and `jmp address-of-function`. To return from a function, we can use the `ret` instruction, which pops the address from the top of the stack and jumps to it.

Parameters are passed to functions through the following registers, in the following order:
* `rdi` (first argument)
* `rsi` (second argument)
* `rdx` (third argument)
* `rcx` (fourth argument)
* `r8` (fifth argument)
* `r9` (sixth argument)

If the function has more than 6 arguments, the rest of the arguments are pushed onto the stack and passed that way. At the beginning of the called function, the seventh argument would be stored at `rsp + 8`.

Values returned from functions are stored in `rax`.

#### Stack Frames

While we can do a lot by manipulating register values, there are a limited number of registers on the CPU. What if we need hundreds of variables for a function? In this case, we need **local variables**, but how do we do that? One way to do that is to make a stack frame. Stack frames are conventions used to make stack memory management easy. For each function that is called, a new stack frame is "constructed" on the stack for easy local variable initialization and cleanup.

To create a stack frame, we can execute:

push rbp
mov rbp, rsp
sub rsp, 0xXX

`rbp` is a general-purpose register that is generally used to establish stack frames. The above code will save the current value of `rbp` onto the stack and then store `rsp` on the stack. Recall that `rsp` is the location of the top of the stack. If we manually change the value of `rsp`, we have manually changed where the top of the stack lies. Since the stack grows downward, subtracting `rsp` from the stack will reserve `0xXX` bytes of space on the stack. We can use this reserved space for local variables.

In addition to reserving space for local variables, this also creates a simple way to refer to these local variables. Since we saved the value of `rsp` in `rbp` earlier, we can always refer to each local variable as an offset of `rbp`.

If we had three local long int (8-byte size) variables, we could create a stack frame like so:

push rbp
mov rbp, rsp
sub rsp, 0x18 ; 0x18 = 24

We could then access the local variables anywhere in the function like so:

mov DWORD PTR [rbp - 8], 1
mov DWORD PTR [rbp - 16], 2
mov DWORD PTR [rbp - 24], 3

`DWORD` gives the size of the memory location to operate `mov` on. `DWORD` means 32 bits, which is equivalent to 4 bytes.

We would also then be able to access function parameters through positive offsets of `rbp`. In a function, the stack should look something like this:

Position (offset from rbp)   Contents
...                          ...
24                           Argument 8
16                           Argument 7
8                            Return address
0                            Previous rbp value
-8                           Local variable 1
-16                          Local variable 2
...                          ...

A stack frame requires a bit of overhead when the function returns. We must delete the stack frame before the `ret` executes. To do so, we can use the `leave` instruction. This is equivalent to `mov rsp, rbp` and `pop rbp`. Assuming that we did not manipulate `rbp` during the function (excluding stack frame initialization), this would set `rsp` and `rbp` back to their original values before the function was called. This results in the stack looking identical to how it was before the function was called. Perfect!

## Conclusions

Low-level concepts like these are very confusing, and they can be different for different architectures (see i386 vs x86-64). Because of that, please ask questions if you're stuck on anything. As always, feel free to contact us by:
- Asking for help during a club block
- Creating a ticket on our [Discord server](https://tjcsec.club/discord)
- DMing an officer

Happy hacking!

[^1]: You do not need to follow these conventions to make local variables! They are just suggestions to make code that makes sense, but you can do you. The conventions here are widely used, however, so there are optimizations and special instructions to work efficiently with these conventions.