Heap overflow is a prevalent memory corruption vulnerability, playing an important role in recent attacks. Find- ing such vulnerabilities in applications is thus critical for security. Many state-of-art solutions focus on runtime detection, requiring abundant inputs to explore program paths in order to reach a high code coverage and luckily trigger security violations. It is likely that the inputs being tested could exercise vulnerable program paths, but fail to trigger (and thus miss) vulnerabilities in these paths. Moreover, these solutions may also miss heap vulnerabilities due to incomplete vulnerability models.
In this paper, we propose a new solution HOTracer to discover potential heap vulnerabilities. We model heap overflows as spatial inconsistencies between heap allocation and heap access operations, and perform an in- depth offline analysis on representative program execution traces to identify heap overflows. Combining with several optimizations, it could efficiently find heap over- flows that are hard to trigger in binary programs. We implemented a prototype of HOTracer, evaluated it on 17 real world applications, and found 47 previously unknown heap vulnerabilities, showing its effectiveness.