Revisiting program slicing with ownership-based information flow
Abstract/Contents
- Abstract
- Program slicing is the technique of automatically identifying the subset of a program that is relevant to a particular piece of code. In theory, slicing addresses one of the core challenges of modern-day programming: sorting through large quantities of information to find what is relevant to the task at hand. However, very little is known about how people would actually use a slicer while programming. This dearth of evidence is compounded by the fact that no practical program slicer exists for programmers to use today. This dissertation contributes to the theoretical and practical foundations of program slicing in three ways. First, I provide evidence for the cognitive basis of slicing. I report on a series of experiments that demonstrate how a person's working memory significantly limits their ability to remember information about a program while engaging in a variety of comprehension tasks. These experiments support the design of tools to reduce working memory load while programming, such as program slicing. Second, I describe the theory and implementation of a modular program slicer for the Rust programming language. This slicer is based on a novel information flow analysis, Flowistry, that leverages Rust's type system, namely ownership types, to approximate the behavior of unknown code solely from its static type. With these approximations, code can be analyzed more efficiently (no whole-program analysis) and robustly (no library source code needed). I show that this approximation is provably sound and reasonably precise in practice. Finally, I describe the design of a new program slicing interface, Focus Mode, that interactively visualizes slices as the user changes their focus in a program. I report on a user study of Rust developers debugging programs with Focus Mode. We find that slices do help programmers find relevant code by focusing their attention on code with unexpected side effects. However, slices may also exclude code which is cognitively relevant to understanding a bug, suggesting the need for further work on the design of program analyses and user interfaces for code relevance. Flowistry and Focus Mode are both free and open-source tools that have been downloaded by thousands of Rust developers. The tools are publicly available at https://github.com/willcrichton/flowistry.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Crichton, William Perry |
|---|---|
| Degree supervisor | Agrawala, Maneesh |
| Degree supervisor | Hanrahan, P. M. (Patrick Matthew) |
| Thesis advisor | Agrawala, Maneesh |
| Thesis advisor | Hanrahan, P. M. (Patrick Matthew) |
| Thesis advisor | Aiken, Alexander |
| Degree committee member | Aiken, Alexander |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Will Crichton. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/sw150vv9472 |
Access conditions
- Copyright
- © 2022 by William Perry Crichton
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...