POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Programs often interface with file systems for a variety of tasks, from retrieving and storing computation data to configuring the operating system. These interactions are mediated by paths, and the complex interplay between programs, paths, and hierarchical file system state can lead to unexpected behaviors ranging from silent failures to irreversible data loss and security vulnerabilities. Yet, this domain remains underserved by formal reasoning. This paper addresses that gap by developing foundations for automated formal analysis of file-system-interacting programs. Grounding our study in a survey of APIs across several widely used standard libraries, we distill core file system behaviors into a representative object language, WhileFS . We then develop a theory of tree-walking word equations (TWE) and show that it is adequate to reason about file system interactions via sound and complete symbolic semantics for WhileFS . We demonstrate that the satisfiability question for TWE is as hard as the longstanding open problem of word equations with length constraints. Nonetheless, we also show that two useful fragments remain decidable in PSPACE by reduction to standard word equation theories. Together, these results demonstrate that TWE and WhileFS constitute a rich foundation for formal reasoning about programs that interact with file systems.