Spatial and Temporal Decomposition for Faster Translation Validation
Translation validation is a critical tool in program analysis: when a program $P$ is transformed into a new program $P'$, translation validation asks whether $P$ and $P'$ have the same semantics. It serves as a middle ground between compiler testing and formal verification, capable of proving that a particular run of a compiler produced correct results. However, one bottleneck holds back wider adoption of translation validation: performance. State-of-the-art tools frequently time out or require extensive manual engineering to adapt to specific use cases. In this paper, we propose a new approach to improving the scalability of translation validation by decomposing the problem along two axes. Our primary contribution is a method for harnessing compiler information to extract subprograms whose equivalence result implies equivalence of the overall transformation (the spatial axis). We augment this method by utilizing compiler information to dynamically group transformation passes for validation (the temporal axis). Our evaluation demonstrates that this approach validates 10% of translations that existing approaches fail to validate, and speeds up validation by up to $2.4\times$.
Mon 5 OctDisplayed time zone: Pacific Time (US & Canada) change
15:30 - 17:00 | |||
15:30 18mTalk | Spatial and Temporal Decomposition for Faster Translation Validation OOPSLA Benjamin Mikek Georgia Institute of Technology, Chathur Bommineni Georgia Institute of Technology, Qirun Zhang Georgia Institute of Technology, Thomas Reps University of Wisconsin-Madison DOI | ||
15:48 18mTalk | Efficient Extraction for Effectful E-graphs OOPSLA Oliver Flatt University of Washington, Anjali Pal University of Washington, Yihong Zhang University of Washington, Ryan Tjoa Jane Street, Kirsten Graham University of Washington, Alex Fischman University of Washington, Chandrakana Nandi Certora; University of Washington, Eli Rosenthal Google, Zachary Tatlock University of Washington, Haobin Ni University of Washington DOI | ||
16:06 18mTalk | Phaedrus: Predicting Dynamic Application Behavior with Lightweight Generative Models and LLMs OOPSLA Bodhisatwa Chatterjee NVIDIA, Georgia Institute of Technology, Neeraj Jadhav Georgia Institute of Technology, Santosh Pande Georgia Institute of Technology DOI | ||
16:24 18mTalk | Taming the Hydra: Targeted Control-Flow Transformations for Dynamic Symbolic Execution OOPSLA Charitha Saumya Intel, Muhammad Hassan Virginia Tech, Rohan Gangaraju University of Texas at Austin, Milind Kulkarni Purdue University, Kirshanthan Sundararajah Virginia Tech DOI Authorizer link Pre-print | ||