# CPEN 212 Computing Systems II X86汇编
# Lab 1: Rapid Unplanned Disassembly
Copyright By PowCoder代写 加微信 powcoder
In this lab, you will learn to examine programs at low-level using a debugger, and practice what you know about assembly coding and calling conventions.
## Contents
* [Logistics](#logistics)
* [Task 1: Learning to debug low\-level code](#task-1-learning-to-debug-low-level-code)
* [Task 2: Binary search](#task-2-binary-search)
* [Task 3: Reverse engineering](#task-3-reverse-engineering)
* [BONUS](#bonus)
* [Marks breakdown](#marks-breakdown)
## Logistics
### Server access
To complete this lab, you will need access to a 64-bit Linux machine running on x86-64 hardware. You can access a suitable machine by running
ssh ssh.ece.ubc.ca
and doing the lab there (you will need an ECE account for this).
You can use your own machine or a VM, but **make sure** your code also works on `ssh.ece.ubc.ca`. Execution on that machine will be what we mark.
### Reading
You might want to review parts of [_x86-64 Assembly Language Programming with Ubuntu_](http://www.egr.unlv.edu/~ed/x86.html). In particular, Section 12.8 describes the x86-64 System V calling convention. Section 8 might also be useful; it describes the many addressing modes that x86-64 has (i.e., how memory addresses can be computed). Section 2.3.1 reviews the registers available in x86-64. Section 22 lists some common x86-64 instructions.
There are several good x86-64 instruction set references online; [here](https://www.felixcloutier.com/x86/) is one. These are good for looking up instructions you don’t know.
We will also use the `gdb` debugger. You might want to have a command reference handy; google something like “gdb cheatsheet” or “gdb quick reference” and pick one that you like. (You can of course also read the GDB manual if you’re particularly bored.)
### Task completion order
The three tasks do not depend on one another, so you may do them in any order. Task 1 is essentially a tutorial, though, so we recommend doing that first.
## Task 1: Learning to debug low-level code
### Introduction
First, we will remind ourselves how the x86-64 calling convention works, and review the pieces of a program written in assembly. Then, we will learn how to effectively use the `gdb` debugger to understand what programs are doing at instruction level.
Let’s examine a small program `hello` that prints a greeting for each of the command-line arguments passed to it. That is, if you run `hello` on these three arguments like this:
hello foo bar quux
it will output this to the console:
hello, foo!
hello, bar!
hello, quux!
### Understanding the program
You can find the code in `hello.asm` in the `task1` folder. To run it, execute the following commands:
nasm -felf64 hello.asm
ld -o hello hello.o
The first one produces an object file `hello.o` and the second links it to produce the actual executable `hello`. (We will talk about object files and linking later in the course.)
In addition to the `_start` entry point, the program uses two functions:
– `len` computes the length of a zero-terminated string at the address passed in the first argument.
– `print` writes to the console the zero-terminated string at the address passed in the first argument.
The `print` function first calls `len` and then invokes the `write` system call (which needs the length).
Make sure you understand how the program works and what is on the stack at any given point. Here are some pointers:
– `equ` defines a convenient name for something, somewhat like `#define` in C; it does not emit any code.
– `len` uses a 64-bit variable stored on the stack to keep track of how many non-zero bytes it has seen.
– `len` uses the frame pointer, stored in `rbp`. Because `rbp` is a callee-saved register, its previous value must be saved before `len` returns.
– `print` has no local variables stored on the stack, and does not modify the frame pointer.
– When you run `hello` and `_start` is first called, the top of the stack has the number of arguments you passed to the program plus one; let’s say this value is _n_. The next _n_ stack entries are the program name (e.g., `./hello`) followed by the _n–1_ arguments you passed to the program (e.g., `foo`, `bar`, and `glurph` in the example above), all as addresses of zero-terminated strings.
– `db` puts some bytes directly in the assembled code. 10 is the ASCII linefeed character (`\n`).
You might wonder why `len` uses a frame pointer and `print` doesn’t. Often, optimized code generated by a compiler omits the frame pointer, and calculates the addresses of any local variables that live on the stack from the stack pointer `rsp`. While this would be trivial for our `len`, in a more complicated function the same stack variable might be in `[rsp+8]` at one point but in `[rsp+24]` later after two more 64-bit values have been pushed on the stack; this is easy for the compiler to keep track of, but pretty annoying for humans. The cases where something like a frame pointer is absolutely necessary are very rare in practice (what are they?).
So does `len` actually need a frame pointer? Not really. In fact, it doesn’t even need to use a stack variable to store the count; we would have been fine with a register. We wrote it this way to help you learn how the frame pointer is used. (Actually, `len` can be written much more efficiently; try it.)
Compile the program and run it with different numbers of arguments.
### Examining the executable file
Let’s examine the `hello` executable. We can do this by using a program called `objdump` like this:
objdump -dzw -Mintel hello
(it might be convenient to pipe it through `less` or redirect the output to a file; see the Data Wrangling lecture in _The Missing Semester_ course linked from Piazza if you don’t know how to do this).
The `-d` flag asks `objdump` to disassemble what it finds, `-z` tells it to display zeros (which are otherwise skipped), and `-w` tells it to use wide lines rather than split instructions over multiple lines. `-Mintel` asks `objdump` to use the Intel assembly syntax for x86-64 (this is the same as what `nasm` uses except `nasm` doesn’t need `ptr` and `offset`).
You should see three columns: a hexadecimal address, a sequence of bytes at this address, and an instruction decoded from the bytes. You can immediately see that x86-64 instructions are encoded as a variable number of bytes, in contrast to many other architectures where all instructions have the same size. You can also see that `objdump` doesn’t know which bytes are code and which are data, so it tries its very best to disassemble everything; this is why we get nonsense instructions at `pre` and `post`.
You can also see that sometimes addresses appear in the dissassembled code, but are clearly not directly encoded in the instruction. For example, the instruction
40104d: 74 26 je 401075
is encoded is only two bytes, but the address 401075 needs at least three bytes. This is because the `je` instruction uses addressing _relative_ to the address of the next instruction: you can verify that 0x40104d + 0x26 + 2 equals 0x401075 (2 because the `je` takes two bytes).
Some instructions encode the _absolute_ address, for example
40107f: 48 bf a5 10 40 00 00 00 00 00 movabs rdi,0x4010a5
loads the address of the usage message `msg` in `rdi`. You can also see that x86-64 is little-endian: that is, addresses are encoded with the least-significant byte at the lowest address, so the 64-bit address `00000000004010a5` is encoded as the byte sequence `a5 10 40 00 00 00 00 00`.
Most of the time, you don’t need to pay attention to how the instructions are encoded as bytes. Sometimes, though, this is very useful, for example if you’re trying to exploit certain security vulnerabilities to hack into something.
Although we started with the source code for `hello.asm`, `objdump` only read the binary file — meaning that you can use `objdump` to examine the instructions of any program, even if you don’t have the source code. The key limitation is that `objdump` can’t necessarily distinguish data from instructions, and might try to disassemble everything in sight (as we just saw).
### Running in the debugger
Rather than using `objdump` and reading the code, it would be much nicer to just watch what the code is doing as it is running. In this section, we will use the `gdb` debugger to do this.
To configure `gdb` for this course, first create a file `.gdbinit` in your home directory on `ssh.ece.ubc.ca` with the following two lines:
set disassembly-flavor intel
set disassemble-next-line on
You can also type them in whenever you start `gdb`, but this gets old pretty quickly. The first line is not strictly necessary, but by default `gdb` uses the AT&T assembler syntax, and you will find it annoying to constantly switch between this and the Intel syntax we use. Similarly, you can type in the `disassemble` command every time instead of using the second setting, but I bet you won’t last long before you set it to happen automatically.
To start debugging, run
Now, inside `gdb`, we can run the program with some arguments like this:
run foo bar
Unfortunately, this runs the program to completion, not one instruction at a time like we want to. So we have to tell it to set a breakpoint somewhere. Let’s set it at `_start`, which is the entry point to the program:
and then repeat the `run` command. (You can use an address instead, e.g., `b *0x401044`).
Now the program is running but it stopped just before executing the first instruction in `_start`. To see the rest of the code, you can use `disass`; by itself, it will show the code until next label, but you can also tell `disass` a range of addresses, such as
disass $rip,+30
which will disassemble the next 30 bytes (recall that `rip` is the instruction pointer, that is the address of the next instruction to be executed).
We can use the `p` command to display register values, e.g.,
will display the instruction point (`/x` means use hexadecimal format)
We can also use the `x` command to look at memory contents. For example,
will display eight quadwords starting at `rsp` in hex format (the `/8x` means 8 elements in hex format). If you recall, the top of the stack at the entry point to `_start` has the command-line argument count, so if you ran `run foo bar` you should see 3 there. The addresses after that are the command-line arguments; you can examine them with `x/s` followed by the address (`s` means string). What do you think are the addresses after the last argument? Try to look at them with `x/s`.
To avoid typing this all the time, we can instruct `gdb` to display some registers and the very top of the stack every time the execution stops; for example:
display/x {$rax, $rbx, $rdx, $rdi, $rsi, $rbp, $rsp}
display/4xg $rsp
(`/4xg` means 4 hex quadwords). If you end up with too many `display` outputs, you can use `undisplay` followed by the relevant number.
Let’s run through some instructions. The
command will execute instructions one at a time, and follow any `call` instructions. You can press ENTER to repeat the last command, so it’s convenient to type `si` once and keep going with ENTER.
Single-step through all instructions of `hello` and check that you correctly understood the `hello.asm` source code earlier.
### Deliverables
In the `task1` folder, you will find a file called `ANSWERS.txt`. Modify this file to fill in the correct answers below each question heading, and push the modified file to GitHub.
## Task 2: Binary search
Now, let’s get more comfortable writing assembly code. In this task, you will implement a recursive binary search directly in x86-64 assembly. Your routine will receive an array of unsigned 64-bit integers and a search key, and will have to find where the key is in the array.
### Binary search
Binary search is a sublinear-time algorithm for finding something in a sorted sequence.
The idea is simple. You start in the middle of the sequence and compare the element you find there to the key you are looking for. If it’s the same, you’re done. If not, you recurse on the left or right half of the array, depending on whether the key is larger or smaller than the midpoint element.
For example, suppose you have a sorted sequence of numbers:
[2, 4, 5, 6, 9, 13, 17]
and suppose our search key is 5.
We will start looking in the middle of the array:
[2, 4, 5, 6, 9, 13, 17]
Our search key is smaller than the midpoint value, so we can ignore the right half of the array (because we know it’s sorted). Instead, we need to recurse left — that is, call binary search on `[2, 4, 5]`. We again look at the midpoint:
This time, the key is larger than the midpoint, so we recurse right on `[5]`:
When we’re down to one element, only two possibilities remain: either the key is in the list and we have found it, or the key is not in the list.
Here is the entire process:
[2, 4, 5, 6, 9, 13, 17]
With an array, it’s silly to allocate a new subarray every time we recurse, so instead one keeps track of the high and low bounds of the range of interest, and adjusts them for every recursion.
### Specification
**Algorithm:**
Recursive binary search. If you implement another algorithm (e.g., linear search), you will receive **no credit**.
**Arguments:**
1. _lo_: 64-bit address of the first element in the array
2. _hi_: 64-bit address of the last element in the array
3. search key: 64-bit unsigned integer
**Input invariants:**
– _hi_ ≥ _lo_ > 0
**Return value:**
– if search key found: 64-bit address of an element in the array equal to the search key
– if search key not found: address 0 (aka null pointer)
For example, if the only occurrence of the key is at the very beginning of the array, your function will return _lo_.
**Output invariants:**
– the contents of the array have not been modified
Your code must conform to the x86-64 System V calling convention. (This is what is used on Linux, and explained in the assembly programming book on Piazza.)
### Usage example
We have provided an empty `binsearch.asm` that returns an undefined value, as well as a `smoketest.asm` that illustrates how the `binsearch` function is called. There is also a `Makefile` that will assemble both files and link them into an executable program `smoketest`. You can build and run this with
make smoketest
./smoketest
Because the example `binsearch` does nothing, the smoketest will report failure. With a correct implementation of `binsearch`, it will say that the smoketest passed.
### Deliverables
In the `task2` folder, you will find a file called `binsearch.asm`. Modify this file to implement the `binsearch` function as specified above, and push the modified file to GitHub.
– Addresses can span the full 64-bit range even if your computer does not have that much physical memory. Be careful how you compute the midpoint to avoid overflow. (There was a bug in the Java JDK implementation of `java.util.Arrays.binarySearch()` _for almost a decade_ that got this wrong.)
– 64-bit numbers are 8 bytes long, but memory is byte-addressable. Make sure you don’t generate addresses that point in the middle of some number.
– Be careful about the termination conditions. Carefully test the edge cases of array lengths, found / not found, location in array, etc.
– The numbers in the input array are unsigned. x86-64 provides signed and unsigned conditional branches; make sure you use the right ones.
– You probably don’t need the division instruction. (No harm in using it, but there are simpler options.)
– You might find it convenient to first prototype the function in a high-level language to understand the algorithm, figure out the corner cases, and plan how you will test your code.
– However, you must all submitted code must be written **from scratch** in x86-64 assembly. Writing the code in a higher-level language and submitting the (possibly modified) output of the compiler **will be considered cheating**. That is, you may use a higher-level language implementation to help you develop the algorithm, but not to compile, modify, and submit.
– The smoketest barely tests anything, it’s just an example of how we will call your code.
– If you didn’t test your code extensively, it probably doesn’t work for some cases. Which would not be good because your marks will be based on what works.
## Task 3: Reverse engineering
Now that you have some practice with writing code in assembly, let’s use the tools we learned to reverse-engineer some binary code.
### Instructions
In the `task3` folder, you will find ten binaries `hackme0` through `hackme9`. Each binary takes a password as its only command-line argument; a correct password will unlock the binary and output `YOU WIN!` while an incorrect password will output `**BOOM**`.
Your task is to analyze all of the functions included in the binary using `gdb`, and find at least one correct password.
Your target is the binary that corresponds to the **last digit of your student number**; you will receive **no credit** if you analyze a different binary.
### Deliverables
In the `task3` folder, you will find a file called `ANSWERS.txt`. Modify this file to fill in the correct answers below each question heading, and push the modified file to GitHub.
– Use `gdb` rather than `objdump -d` to disassemble the code. `gdb` knows exactly which code you are running, while `objdump` has to guess (and can be wrong).
– Start by finding where all the functions are. You can tell by finding the `call` instructions and seeing where they go.
– Make sure you know how to print registers and memory.
– In `gdb`, you can set breakpoints on addresses, not just labels. `c` will continue execution until the next label.
– You can also change the contents of registers and memory if you wish to examine how some code will run with different inputs. It might be useful to find out how to do that if you get stuck.
To receive some bonus credit, optimize `binsearch` to produce an implementation with the _shortest possible code length in bytes_. Since x86-64 instruction encoding is variable-length, this does not _necessarily_ mean fewest instructions.
Our first working implementation of `binsearch` was 38 bytes long. If your code is shorter than this and satisfies all of the functional requirements, you will receive 1 bonus mark. If your code is very close to this length and functionally correct, we may consider some partial bonus depending on what optimization tricks you used.
The bonus task will be marked separately from the rest of the problem set, so it may take longer to notify you.
### Deliverables
In the `bonus` folder you will find `binsearch-bonus.asm`. Modify and push as in task 2.
## Marks breakdown
– Task 1: 1 mark
– Task 2: 4 marks
– Task 3: 5 marks
– Bonus: 1 mark