A Deterministic Memory Allocator for Dynamic Symbolic Execution

1@inproceedings{schemmelDeterministicMemoryAllocator2022,
2  author = {Schemmel, Daniel and Büning, Julian and Busse, Frank and Nowack, Martin and Cadar, Cristian},
3  title = {A {{Deterministic}} {{Memory}} {{Allocator}} for {{Dynamic}} {{Symbolic}} {{Execution}}},
4  booktitle = {36th {{European}} {{Conference}} on {{Object-Oriented}} {{Programming}} {{(ECOOP}} 2022)},
5  location = {Berlin, Germany},
6  pages = {9:1--9:26},
7  year = {2022},
8  month = {jun},
9  doi = {10.4230/LIPIcs.ECOOP.2022.9},
10}

Dynamic symbolic execution (DSE) has established itself as an effective testing and analysis technique. While the memory model in DSE has attracted significant attention, the memory allocator has been largely ignored, despite its significant influence on DSE.

In this paper, we discuss the different ways in which the memory allocator can influence DSE and the main design principles that a memory allocator for DSE needs to follow: support for external calls, cross-run and cross-path determinism, spatially and temporally distanced allocations, and stability. We then present KDAlloc, a deterministic allocator for DSE that is guided by these six design principles.

We implement KDAlloc in KLEE, a popular DSE engine, and first show that it is competitive with KLEE's default allocator in terms of performance and memory overhead, and in fact significantly improves performance in several cases. We then highlight its benefits for use-after-free error detection and two distinct DSE-based techniques: MoKlee, a system for saving DSE runs to disk and later (partially) restoring them, and SymLive, a system for finding infinite-loop bugs.