Graduate mentor's supervisor: Prof. Chengnian Sun
When a compiler crashes, the program that triggered it is often thousands of lines long, yet almost none of them matter to the failure. "Program reduction" tools automatically shrink such inputs to a tiny reproducing example by repeatedly deleting pieces and re-testing. The major algorithms (Delta Debugging, Hierarchical Delta Debugging, Perses, ProbDD) are closely related and even reuse one another, but each is its own separate program, so they are hard to compare head-to-head or mix and match. This project builds a clean open-source framework where the candidate-generation strategy and the inner reduction algorithm are each a swappable plug-in. With every algorithm running on one shared engine, they can be compared on equal footing and recombined in new ways.
Students implement the framework against a plug-in interface we provide, so the team of 3-4 splits cleanly:
Short-term (within the term):
- Core engine: one or two members build the shared loop that proposes deletions, queries the oracle, and keeps successful reductions.
- Algorithm plug-ins: the others each implement an algorithm against the common interface, starting with Delta Debugging and HDD. Validation: cross-check plug-ins by differential testing against the reference tools.
Longer-term (if continuing): add further algorithms (e.g., ProbDD), then run a reproducible comparison that could contribute to a publication.
Reference: https://dl.acm.org/doi/10.1145/3180155.3180236
This project is best suited for second- or third-year students, and first-years already familiar withparsing and syntax trees are definitely welcome.
- Required: comfort programming in Python or Rust.
- A plus: a data structures course (trees) and a compilers course (parsers, syntax trees).