Hacker handle: `0xc3`

# Execution instructions
To generate `id_mars1`, simply run `run.sh`. This will first generate a dummy input (consisting of asterisks), then compile the pintool, run it, and parse its output to generate `id_mars1`.
Having a proper dummy input seemed to be important to try to recover all of the data in one run; filling the input with zero bytes caused a small amount of text to not be recovered.

# Notes

## Starting off
When starting off, the first question is "how big should this input file be?". Luckily, this question is easily answered by generating a reasonably large input (4KB), running the binary under `ltrace`, and seeing a 1600-byte read, giving us a logical input file size.

## Missing pieces
A few lines of code were left for us to fill in the implementation of taint propagation through moves. In `handle_mov_memtomem`, data is copied from `from` to `to`, so taint should also be copied from `shadowFrom` to `shadowTo`. In `handle_mov_regtomem`, data is copied from a register to memory, so taint should be copied from `g_regTags + reg` to `shadow`.

## Direct comparisons
The handling of the various forms of the `cmp` instruction is modelled loosely on the code for `mov`. Comparing a register to memory or memory to a register is equivalent for our purposes, so those are handled together. Some work was done to support multi-byte comparisons, but it is inconsistent and probably incomplete as it was not needed for this assignment. All comparisons with tainted values are logged to `stderr`, in a format that is easily parsed by tools (such as the `analyse_output.py` analysis script). To perform this logging, values in registers or memory or immediates are often required. This information can be passed quickly using `IARG_MEMORY(READ|WRITE)_EA`, `IARG_REG_VALUE`, or by passing `INS_OperandImmediate(ins, n)` as an `IARG_UINT64` in the calls to `INS_InsertCall`.

### Analysis
As mentioned above, information about the compare operations is logged. The output of the pintool is subsequently parsed and interpreted by a Python script, `analyse_output.py`, which uses the information about the comparisons to deduce the data that should be in `id_mars1`. For instance, when a tainted value is compared with an untainted value, the required value is inferred to be the untainted value (modulo backtracking of course).

### Clearing taint
Of course, before the implementation of arithmetic operations, taint is cleared in their destinations, using code cribbed from the handling of BSWAP.

## Library functions
When running the binary under `ltrace` and grepping for string and memory operations, a few functions that require taint propagation jump out: `memset`, `memcpy` and `str(n)cmp`. The framework already includes partial code for handling `memset`; this code is completed (by setting the taint in the destination of `memset` to the taint of `rsi`, the register which contains the fill byte parameter) and supplemented with code that handles `memcpy` and `str(n)cmp`.

## Arithmetic operations
If arithmetic operations are done using an immediate source, no taint propagation is required but the operations must be logged so that they can be reversed later. If the source operand is memory or a register, the operations are logged and additionally the taint of the destination is OR'ed with the taint of the source. This way, the destination is tainted if either the source or the destination was tainted before the operation occurred. In this assignment, no arithmetic operations using both a tainted source and a tainted destination are used, so we don't have to worry about storing a combination of both taints.

## Obfuscated comparisons
The basis for handling obfuscated comparisons was already created in the previous step; all arithmetic operations on tainted values are logged. Now all that is left to do is to reverse these operations in the Python analysis script. Luckily, the operations that are used are easily reversed; implementing reversal for non-overflowing ADD, SUB, SHR, SHL and XOR suffices.
