Dynamic memory managers are a crucial component of almost every modern software
system. In addition to implementing efficient allocation and reclamation, memory
managers provide the essential abstraction of memory as distinct objects, which
underpins the properties of memory safety and type safety. Bugs in memory
managers, while not common, are extremely hard to diagnose and fix. One reason
is that their implementations often involve tricky pointer calculations, raw
memory manipulation, and complex memory state invariants. While these properties
are often documented, they are not specified in any precise, machine-checkable
form. A second reason is that memory manager bugs can break the client
application in bizarre ways that do not immediately implicate the memory manager
at all. A third reason is that existing tools for debugging memory errors, such
as Memcheck, cannot help because they rely on correct allocation and
deallocation information to work.

In this paper we present Permchecker, a tool designed specifically to detect and
diagnose bugs in memory managers. The key idea in Permchecker is to make the
expected structure of the heap explicit by associating \emph{typestates} with
each piece of memory. Typestate captures elements of both type (e.g., page,
block, or cell) and state (e.g., allocated, free, or forwarded). Memory manager
developers annotate their implementation with information about the expected
typestates of memory and how heap operations change those typestates. At
runtime, our system tracks the typestates and ensures that each memory access is
consistent with the expected typestates. This technique detects errors quickly,
before they corrupt the application or the memory manager itself, and it often
provides accurate information about the reason for the error.

The implementation of Permchecker uses a combination of compile-time annotation
and instrumentation, and dynamic binary instrumentation (DBI). Because the
overhead of DBI is fairly high, Permchecker is suitable for a testing and
debugging setting and not for deployment. It works on a wide variety of
existing systems, including explicit malloc/free memory managers and garbage
collectors, such as those found in JikesRVM and OpenJDK. Since bugs in these
systems are not numerous, we developed a testing methodology in which we
automatically inject bugs into the code using bug patterns derived from real
bugs. This technique allows us to test Permchecker on hundreds or thousands of
buggy variants of the code. We find that Permchecker effectively detects and
localizes errors in the vast majority of cases; without it, these bugs result
in strange, incorrect behaviors usually long after the actual error occurs.