SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Wed 20 Oct 2021 11:05 - 11:20 at Zurich B - Testing Chair(s): Iulian Neamtiu
Wed 20 Oct 2021 19:05 - 19:20 at Zurich B - Testing - Mirror Chair(s): Steve Blackburn

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.

Wed 20 Oct

Displayed time zone: Central Time (US & Canada) change

10:50 - 12:10
TestingOOPSLA at Zurich B +8h
Chair(s): Iulian Neamtiu New Jersey Institute of Technology
10:50
15m
Talk
Fully Automated Functional Fuzzing of Android Apps for Detecting Non-crashing Logic BugsVirtual
OOPSLA
Ting Su East China Normal University, Yichen Yan East China Normal University, Jue Wang Nanjing University, Jingling Sun East China Normal University, Yiheng Xiong East China Normal University, Geguang Pu East China Normal University, Ke Wang Visa Research, Zhendong Su ETH Zurich
DOI
11:05
15m
Talk
Permchecker: A Toolchain for Debugging Memory Managers with TypestateVirtual
OOPSLA
Karl Cronburg Tufts University, Sam Guyer Tufts University
DOI Pre-print
11:20
15m
Talk
Generative Type-Aware Mutation for Testing SMT SolversVirtual
OOPSLA
Jiwon Park École Polytechnique, Dominik Winterer ETH Zurich, Chengyu Zhang East China Normal University, Zhendong Su ETH Zurich
DOI
11:35
15m
Talk
Programming and Execution Models for Parallel Bounded Exhaustive TestingIn-Person
OOPSLA
Nader Al Awar University of Texas at Austin, Kush Jain University of Texas at Austin, Chris Rossbach University of Texas at Austin; Katana Graph, Milos Gligoric University of Texas at Austin
DOI
11:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA

18:50 - 20:10
Testing - MirrorOOPSLA at Zurich B
Chair(s): Steve Blackburn Australian National University
18:50
15m
Talk
Fully Automated Functional Fuzzing of Android Apps for Detecting Non-crashing Logic BugsVirtual
OOPSLA
Ting Su East China Normal University, Yichen Yan East China Normal University, Jue Wang Nanjing University, Jingling Sun East China Normal University, Yiheng Xiong East China Normal University, Geguang Pu East China Normal University, Ke Wang Visa Research, Zhendong Su ETH Zurich
DOI
19:05
15m
Talk
Permchecker: A Toolchain for Debugging Memory Managers with TypestateVirtual
OOPSLA
Karl Cronburg Tufts University, Sam Guyer Tufts University
DOI Pre-print
19:20
15m
Talk
Generative Type-Aware Mutation for Testing SMT SolversVirtual
OOPSLA
Jiwon Park École Polytechnique, Dominik Winterer ETH Zurich, Chengyu Zhang East China Normal University, Zhendong Su ETH Zurich
DOI
19:35
15m
Talk
Programming and Execution Models for Parallel Bounded Exhaustive TestingIn-Person
OOPSLA
Nader Al Awar University of Texas at Austin, Kush Jain University of Texas at Austin, Chris Rossbach University of Texas at Austin; Katana Graph, Milos Gligoric University of Texas at Austin
DOI
19:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA