ROP setRegisters

[zachriggle]

The current issue with setRegisters is that it requires basic gadgets a la pop rdi; ret.

If we need to set rdi and rsi and we have the following gadget, it will fail:

pop rsi; pop rdi; ret

We can solve this in two ways.

Dirty matching

Just use whatever matches we can get away with. This will bloat our ROP stack.

Set cover problem

This is ultimately the Set Cover Problem. Given a set of registers R which we wish to modify, and a collection S of m sets each containing some of the registers, we want to optimize for total stack space used.

This is slightly different from the Set Cover Problem, because our desired set R is not all possible values in the union of all sets in S, but it is a subset. Separately, we want to optimize not for the cardinality of the selected sets, but the total stack space used (since all gadgets add a ret and some gadgets even have add esp).

[zachriggle]

We should also cache the results of this operation, since it may be expensive.