Program Analysis via Multiple Context Free Language Reachability

Explore a groundbreaking 18-minute conference talk from POPL 2025 that introduces Multiple Context Free Language (MCFL) reachability as a novel approach to static program analysis. Presented by researchers from Hong Kong University of Science and Technology and Aarhus University, this video addresses the limitations of traditional Context-Free Language (CFL) reachability while avoiding the undecidability issues of fully context-sensitive languages. Learn how MCFLs create a tunable hierarchy of mildly context-sensitive languages parameterized by dimension and rank, offering adjustable analysis precision. The presentation details algorithmic complexity findings, proving optimal time bounds for various configurations, and demonstrates practical application through a taint analysis for Android that achieves remarkable coverage. The research represents a significant advancement in approximating interleaved Dyck reachability problems with provable coverage guarantees, with supporting artifacts available and evaluated as reusable.