  Heap layout randomization renders a good portion of heap vulnerabilities
unexploitable. However, some remnants of the vulnerabilities are still
exploitable even under the randomized layout. According to our analysis, such
heap exploits often abuse pointer-width allocation granularity to spray crafted
pointers. To address this problem, we explore the efficacy of byte-granularity
(the most fine-grained) heap randomization. Heap randomization, in general, has
been a well-trodden area; however, the efficacy of byte-granularity
randomization has never been fully explored as \emph{misalignment} raises
various concerns. This paper unravels the pros and cons of byte-granularity
heap randomization by conducting comprehensive analysis in three folds: (i)
security effectiveness, (ii) performance impact, and (iii) compatibility
analysis to measure deployment cost. Security discussion based on 20 CVE case
studies suggests that byte-granularity heap randomization raises the bar
against heap exploits more than we initially expected; as pointer spraying
approach is becoming prevalent in modern heap exploits. Afterward, to demystify
the skeptical concerns regarding misalignment, we conduct cycle-level
microbenchmarks and report that the performance cost is highly concentrated to
edge cases depending on L1-cache line. Based on such observations, we design
and implement an allocator suited to optimize the performance cost of
byte-granularity heap randomization; then evaluate the performance with the
memory-intensive benchmark (SPEC2006). Finally, we discuss compatibility issues
using Coreutils, Nginx, and ChakraCore.
