  To reduce the source of potential exploits, binary debloating or
specialization tools are used to remove unnecessary code from binaries. This
paper presents a new binary debloating and specialization tool, LeanBin, that
harnesses lifting and recompilation, based on observed execution traces. The
dynamically recorded execution traces capture the required subset of
instructions and control flow of the application binary for a given set of
inputs. This initial control flow is subsequently augmented using
heuristic-free static analysis to avoid overrestricting the input space; and
the further structuring of the control flow and translation of binary
instructions into a subset of C, enables a lightweight generation of the code
that can be recompiled, obtaining LLVM IR and a new debloated binary. Unlike
most debloating approaches, LeanBin enables both binary debloating of the
application and shared libraries, while reusing the existing compiler
infrastructure. Additionally, unlike existing binary lifters, it does not rely
on potentially unsound heuristics, used by static lifters, nor suffers from
long execution times, a limitation of existing dynamic lifters. Instead LeanBin
combines both heuristic-free static and dynamic analysis. The run time during
lifting and debloating SPEC CPU2006 INT benchmarks is on average 1.78$\times$,
normalized to the native execution, and the debloated binary runs with an
average overhead of 1.21$\times$. The percentage of gadgets, compared to the
original binary, has a geomean between 24.10% and 30.22%, depending on the
debloating strategy; the code size can be as low as 53.59%. For the SQLite
use-case, LeanBin debloats a binary together with its shared library, and
generates a debloated binary that runs up to 1.24$\times$ faster with 3.65%
gadgets.
