Permchecker: a toolchain for debugging memory managers with typestate
Permchecker: a toolchain for debugging memory managers with typestate
复制标题
Permchecker：用于使用 typestate 调试内存管理器的工具链
DOI：
10.1145/3485526
复制
发表时间：
2021
影响因子：
--
通讯作者：
Guyer, Samuel Z.
中科院分区：
文献类型：
--
作者：
Cronburg, Karl;Guyer, Samuel Z.
动态内存管理器是几乎所有现代软件系统的关键组件。除了实现有效的分配和回收，内存管理器还提供了内存作为不同对象的基本抽象，这支持了内存安全和类型安全的属性。内存管理器中的bug虽然不常见，但非常难以诊断和修复。一个原因是它们的实现通常涉及棘手的指针计算、原始内存操作和复杂的内存状态不变量。虽然这些属性经常被记录下来，但它们并没有以任何精确的、可机器检查的形式被指定。第二个原因是内存管理器的bug可能会以奇怪的方式破坏客户端应用程序，而这些方式根本不会立即涉及内存管理器。第三个原因是，现有的工具，用于调试内存错误，如Memcheck，不能帮助，因为他们依赖于正确的分配和解除分配的信息working.In本文中，我们提出Permchecker，专门设计用于检测和诊断内存管理器中的错误的工具。Permchecker中的关键思想是通过将类型状态与每一段内存相关联来使堆的预期结构显式化。Typestate捕获两种类型的元素（例如，页、块或单元）和状态（例如，分配的、空闲的或转发的）。内存管理器开发人员用有关内存的预期类型状态以及堆操作如何更改这些类型状态的信息来注释其实现。在运行时，我们的系统跟踪的typestates，并确保每个内存访问是符合预期的typestates。这种技术可以在错误损坏应用程序或内存管理器之前快速检测到错误，并且通常可以提供有关错误原因的准确信息。Permchecker的实现使用了编译时注释和插装以及动态二进制插装（DBI）的组合。由于DBI的开销相当高，Permchecker适合于测试和调试设置，而不适合于部署。它适用于各种现有系统，包括显式的malloc/free内存管理器和垃圾收集器，例如JikesRVM和OpenJDK中的那些。由于这些系统中的错误并不多，我们开发了一种测试方法，在这种方法中，我们使用来自真实的错误的错误模式自动将错误注入到代码中。这种技术允许我们在数百或数千个代码的错误变体上测试Permchecker。我们发现Permchecker在绝大多数情况下都能有效地检测和定位错误;如果没有它，这些错误通常会在实际错误发生很久之后导致奇怪的、不正确的行为。
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 associatingtypestateswith 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.
DOI：
10.1145/3357765.3359519
发表时间：
2019-09
期刊：
Proceedings of the 18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences
影响因子：
--
作者：
Karl Cronburg;Samuel Z. Guyer
通讯作者：
Karl Cronburg;Samuel Z. Guyer
LoCal：一种用于操作序列化数据的程序的语言
DOI：
10.1145/3314221.3314631
发表时间：
2019
期刊：
40th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Vollmer, Michael;Koparkar, Chaitanya;Rainey, Mike;Sakka, Laith;Kulkarni, Milind;Newton, Ryan R.
通讯作者：
Newton, Ryan R.