Blogs (9) >>
Sun 30 October - Fri 4 November 2016 Amsterdam, Netherlands
Wed 2 Nov 2016 16:05 - 16:30 at Matterhorn 1 - Static Analysis Chair(s): Sam Guyer

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

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%.

Wed 2 Nov

15:40 - 17:20: OOPSLA - Static Analysis at Matterhorn 1
Chair(s): Sam GuyerTufts University
splash-2016-oopsla15:40 - 16:05
Sulekha KulkarniGeorgia Tech, Ravi MangalGeorgia Institute of Technology, Xin ZhangGeorgia Tech, Mayur NaikGeorgia Tech
splash-2016-oopsla16:05 - 16:30
Venkatesh SrinivasanUniversity of Wisconsin - Madison, Thomas RepsUniversity of Wisconsin - Madison and Grammatech Inc.
DOI Pre-print
splash-2016-oopsla16:30 - 16:55
Dmytro PetrashkoEPFL, Vlad UrecheEPFL, Switzerland, Ondřej LhotákUniversity of Waterloo, Martin OderskyEPFL, Switzerland
splash-2016-oopsla16:55 - 17:20
Satish ChandraSamsung Research America, Colin GordonDrexel University, Jean-Baptiste JeanninCarnegie Mellon University , Cole SchlesingerSamsung Research America, Manu SridharanSamsung Research America, Frank TipSamsung Research America, Young-il ChoiSamsung Electronics
DOI Pre-print