Hacker handle: `0xc3`

## Execution instructions 
To run all parts of the assignment, use `./run_all.sh`; this simply runs the scripts below in sequence. To reset the assignment to a clean state, use `./clean.sh`.

All Ghidra scripts are stored in the subdirectory `ghidra_scripts`.

#### Execution instructions for individual parts
- To initialize the Ghidra project `challenge4`, run `./init.sh`.
- To perform dynamic analysis and patching, run `./task_1a.sh`.
  - This runs the dynamic analysis pintool and parses its output, storing the result in `dyn_results.json`, and runs the Ghidra scripts `patch_dyn_rets.py` and `patch_dyn_calls.py`. It also generates a patched binary, `mars_ssh.task1a`.
- To perform patching based on static analysis, run `./task_1b.sh`.
  - This runs the Ghidra scripts `patch_static_rets.py` and `patch_static_calls.py`. It also generates a patched binary, `mars_ssh.task1b`.
- To perform control flow graph-based classification of the taint washing functions and generate `id_mars2`, run `./task_2.sh`
  - This runs the Ghidra script `gen_cfgs.py`, which outputs control flow graph data in `cfgs.json`, runs the taint washing function classifier `classify_twf.py`, which outputs classification data in `taint_data.txt`, and runs the taint tool, outputting `id_mars2`.

## 1A. Dynamic analysis
The dynamic analysis pintool can be found in `dyntool.cpp`. Its working is described below.

### Determining indirect call targets and return addresses
#### Indirect call targets
This is simple; we instrument indirect calls and log their target address.

#### Return addresses
We only care about finding return addresses that do not match the address that we expect the function to return to when it is called. In order to keep track of this expected return address and see whether it is changed, we use a shadow stack.

We push a return address onto the shadow stack if:

1. A `call` instruction is executed.
2. The `call` instruction is not to an address in the PLT.

The non-PLT requirement stems from the fact that we don't instrument library functions and so don't want to keep track of them on the shadow stack. If the call is direct, we simply check whether the call target is in the PLT at instrumentation time, if not we use an `INS_InsertIfCall`/`INS_InsertThenCall` pair.

We pop a return address from the shadow stack when a `ret` instruction is executed. If the real return address doesn't match the expected address, we log the expected and real return addresses.

### Parsing the log
The pintool generates logs that have to be parsed. The log is parsed by `scripts/parse_dyn_log.py`, which generates a map of `call address ⇒ list of call targets` and a map of `call address ⇒ list of (expected return addr, real return addr)`. Of note is the fact that there are quite a number of indirect calls which do not have a single target.

There are some "false positive" results that we don't actually want to patch; for instance, the call to `__libc_start_main` does not return to the `HLT` instruction, but we don't want to `NOP` out the entire program. Similarly, we don't want to patch out that indirect call to `__libc_start_main`. These cases are also handled here, by skipping return addresses that are more than 32 bytes away from the expected address and by skipping targets that do not match "0x40XXXX".

### Patching the binary
Dynamic indirect call patching is done in `ghidra_scripts/patch_dyn_calls.py`.
Dynamic RA modification patching is done in `ghidra_scripts/patch_dyn_rets.py`.
All patches are marked with end-of-line comments indicating what type of patch was done. Dynamic patches are tagged with `[dyn]`.

#### Return addresses
This is fairly simple; we simply insert NOP instructions between the expected and the real return address.

#### Indirect ⇒ direct calls
Firstly, there are quite a number of indirect calls which have multiple targets, and we can therefore not just patch them to be direct calls. This information can still aid analysis, however; the patching script handles these by simply instructing Ghidra to disassemble at each of the call targets, and marking them.

When it comes to the single-target indirect calls, there are a number of different indirect call instructions that we need to handle.

##### `CALL RBX`
These call a single target that is computed at runtime using an iterative process described below. They are patched by removing the preceding `MOV EBX, EDX` instruction and then replacing the `ADD RBX, ...; CALL RBX` sequence with `MOV RBX, call_target; CALL call_target; NOP`.

##### `CALL R15`
Occurs once, at `0x404c9c`. `R15` is the first argument of the function (`RDI` is moved into it at the start). Currently this one remains unpatched, because it could be a multi-target call (the function argument could vary outside of what we've seen during dynamic analysis).

##### `CALL qword ptr [0x410280 + R12*0x8]` and `CALL qword ptr [0x410240 + R12*0x8]`
Both of these call an index in an array of function pointers; the array is simply a bunch of pointers to `strcmp` or `strncmp`. These instructions are long (8 bytes), and can simply be overwritten with a direct call + padding NOPs.

##### `CALL qword ptr [R15 + RBX*0x8]`
Used once, when looping over the array of initializers. Unpatched because it is probably not relevant.

## 1B. Static analysis
Static indirect call patching is done in `ghidra_scripts/patch_static_calls.py`.
Static RA modification patching is done in `ghidra_scripts/patch_static_rets.py`.

As in the dynamic case, patches are marked with end-of-line comments indicating what type of patch was done. Static patches are tagged with `[static]`.

### Indirect call patches

#### How call targets are computed
Call targets seem to be computed in an iterative process that looks kind of like a Feistel network.

Let `A_0`, `B_0`, `C` be 32-bit integers. All operations are computed modulo 2**32. Then,

`A_{n+1} = B_n - A_n` and `B_{n+1} = A_n`.

A call target is computed as `A_x + C`, where `x` is the lowest `n` for which `A_{x+1} = 0`.

In practice, two specific values of `A_0` and `B_0` are used, namely `0xbfb9c9a5` and `0x2b495d78`. This allows us to precompute `A_x`, which is `0x8048819`, and compute call targets simply by figuring out what `C` is and adding it to `A_x`.

#### Indirect register calls
The `CALL Rxx`-type indirect calls are preceded with a sequence of instructions that loads the arguments to the callee out of an array at RAX, i.e.:

```asm
MOV Rxx, Ryy
MOV R8,  QWORD PTR [RAX + 0x20]
MOV RCX, QWORD PTR [RAX + 0x18]
MOV RDX, QWORD PTR [RAX + 0x10]
MOV RSI, QWORD PTR [RAX + 0x8]
MOV RDI, QWORD PTR [RAX]
ADD Rxx, C
CALL Rxx
```

While the register that is called through varies, the argument registers seem to always be the standard ones, and a pointer to the argument array always seems to be in `RAX`. Therefore, we use `findBytes` with the encoding of the loading step to find patchable indirect calls.

The basic idea is to move the loading instructions up (overwriting the `MOV Rxx, Ryy`), making room for a simple `MOV Rxx, 0xTARGET; CALL 0xTARGET` (possibly with some NOPs after it).

#### Indirect calls into arrays
The indirect calls which end up calling `str(n)cmp` are easily found by looking for the byte pattern `\x42\xff\x14....\x00` and easily patched out by assembling a direct call + three NOPs.

### Return address modification patches
Return address modification seems to be done according to one pattern:
```asm
MOV RAX, [RBP + 0x8]
ADD RAX, 0xX
MOV [RBP + 0x8], RAX
```
where `0xX` is obviously the number of bytes added to the return address.

Doing this patching statically is not as simple as just looking for this pattern and then patching it out, however; we need to do patching at the callsite. The approach I used works as follows:

   1. Look at all close direct calls (byte patterns matching `\xe8..[\xff\x00]{2}`). 
   2. Check whether the call target is valid and in `.text`, if not continue. 
   3. Try to disassemble at the target and mark it as a function, keeping a mapping from call to target.
   4. Allow Ghidra to analyse all of these new functions by calling `analyzeChanges`.
   5. Iterate over the call-target mapping, and if the target function contains accesses to the return address (as determined by Ghidra's analysis), look for the pattern above at the accessing instructions.
   6. If the pattern is found, extract the return address delta and NOP out the misleading instructions at the callsite.

## 2. Taint-washing function detection and message recovery
Looking at the indirect calls with many targets, an array of functions at `0x414540` jumps out; this is most likely the array with taint-washing functions.

### CFG construction
The Ghidra script `gen_cfgs.py` generates control flow graph information and stores it in `cfgs.json`. It works as follows:

  1. For each address in the function array at `0x414540`, create a function and decompile it
  2. Use the decompilation result to get the basic blocks and create a mapping from each block to the possible next block.
  3. Store the result in a mapping of function name ⇒ CFG.    
  4. Output this mapping in `cfgs.json`.

### Classifying CFGs
CFG classification is done by `scripts/classify_twf.py`. It takes `cfgs.json` and outputs `taint_data.txt`.

The metrics I found to classify the CFGs seem fairly arbitrary to me, but yield good results. Of course, easy metrics to start with are the number of basic blocks and the number of links between them. Those alone doesn't quite get you far enough, but another thing I noticed when looking through CFGs I rendered using `dot` was the presence of loops, and specifically loops from a block to itself. Taking the metric of (number of links, number of self-loops) splits the CFGs into one large class of 128 functions that I classified as taint-washing, and a number of smaller classes that I classified as non-taint-washing.

When I was playing around with different metrics on graphs I discovered using a graph's average shortest path length splits the CFGs into exactly the same classes; the implementation of this uses NetworkX so is not enabled by default.

### Message recovery
If we have "real" and "fake" taint-washing functions, it seemed logical to me to want to clear taint on entry of a fake taint-washing function, and to want to propagate it through real taint-washing functions. My approach is fairly simple; the CFG classification script outputs a data file which contains the entry and exit point of each taint-washing function along with its classification as real or fake. This data is used in the pintool (`tainttool.cpp`) to modify instrumentation as follows:

- When a fake taint-washing function is entered (marked by a TEST instruction at the entry point), clear taint on `RDI` (the first argument).
- When a real taint-washing function is entered (marked similarly), save `RDI`s taint and clear it.
- When a real taint-washing function is exited (marked by a RET at the exit point), copy the saved taint into `RAX`s taint.

As in assignment 3, the pintool outputs logs that are analysed to generate `id_mars2`. The analysis script is in `scripts/analyse_taint_output.py`, and has minimal changes from the assignment 3 version (some asserts are changed to `if not x: continue`, the size of the output is changed according to the changed read).
