Machine-code slicing is an important primitive for building binary
analysis and rewriting tools, such as taint trackers, fault
localizers, and partial evaluators.
However, it is not easy to create a machine-code slicer that exhibits
a high level of precision.
Moreover, the problem of creating such a tool is compounded by the
fact that a small amount of local imprecision can be amplified via cascade
effects.

Most instructions in instruction sets such as Intel's IA-32 and ARM
are multi-assignments: they have several inputs and several outputs
(registers, flags, and memory locations).
This aspect of the instruction set introduces a granularity issue
during slicing:
there are often instructions at which we would like the slice to
include only a subset of the instruction's semantics,
whereas the slice is forced to include the entire instruction.
Consequently, the slice computed by state-of-the-art tools is very
imprecise, often including essentially the entire program.

This paper presents an algorithm to slice machine code more accurately.
To counter the granularity issue, our algorithm performs
slicing at the microcode level, instead of the instruction level,
and obtains a more precise microcode slice.
To reconstitute a machine-code program from a microcode slice,
our algorithm uses machine-code synthesis.
Our experiments on IA-32 binaries of FreeBSD utilities show that, in
comparison to slices computed by a state-of-the-art tool, our
algorithm reduces the size of backward slices by
33%, and forward slices by 70%.