Program Analysis via Multiple Context Free Language Reachability

on YouTube ↗18m

" summary

Introduces MCFL reachability as a tunable, decidable underapproximation for interleaved Dyck (context-sensitive) reachability, implements an algorithm with running time O(n^{2d+1}) when r=1 and O(n^{d(r+1)}) when r>1, proves matching lower bounds (membership n^{2d}, reachability n^3 for d=1), and evaluates on an Android taint benchmark: the tool finds all taints on 8 of 11 benchmarks and confirms 94.3% of overapproximation pairs on the rest, with runtimes comparable to existing methods.

AI-written summary · about

" chapters (14)

1. 0:00Program analysis via MCFL reachability
2. 0:24Language reachability as static analysis
3. 3:13Function calls with parenthesis handling
4. 4:17Language reachability framework
5. 5:41Limitations of context-free reachability
6. 7:07Multiple context-free languages
7. 8:28Defining MCFL grammars
8. 10:55Under-approximating interdic languages
9. 12:45Tunable grammar and context switching
10. 13:28MCFL reachability algorithm
11. 14:10Taint analysis benchmarks
12. 15:54Runtime results summary
13. 16:16Conclusion and future applications
14. 17:02Q&A