Measuring Program Complexity
Automatically Measuring Program Complexity
This project tackles the problem of knowing what programs will do. A challenging problem (uncomputable, in fact!). On top of that, we also want to know HOW MANY ways a program can do its thing.
Counting the ways that a program can do something requires analyzing the source code (this is called static analysis), analyzing the running program (this is called dynamic analysis) and performing combinatorial computations (via logic and a field called "model counting") about the results. Doing so allows us to answer questions like "how safe is my code?", "how many test inputs do I need in order to discover some interesting program behavior?", or "how complicated is my code?".
Who should apply?
Excitement about programming languages, program analysis, and combinatorics is a real win. With this project you'll emerge with even more of that excitement! Join in!! Interest in automated theorem proving is a plus, but background in it is certainly not necessary--we'll learn together as we go.
Relevant reading
Links to relevant papers:
- Automatically Playing Games Using Program Analysis
- Computing Program Complexity
- Synthesizing Exploits
- Counting for Programs that Use Strings
