Tue 25 Jun 2019 14:00 - 14:20 at 229AB - Static Analysis Chair(s): Martin C. Rinard

Analyzing the behavior of a program running on a processor that supports speculative execution is crucial for applications such as execution time estimation and side channel detection. Unfortunately, existing static analysis techniques based on abstract interpretation do not model speculative execution since they focus on functional properties of a program while speculative execution does not change the functionality. To fill the gap, we propose a method to make abstract interpretation sound under speculative execution. There are two contributions. First, we introduce the notion of virtual control flow to augment instructions that may be speculatively executed and thus affect subsequent instructions. Second, to make the analysis efficient, we propose optimizations to handle merges and loops and to safely bound the speculative execution depth. We have implemented and evaluated the proposed method in a static cache analysis for execution time estimation and side channel detection. Our experiments show that the new method, while guaranteed to be sound under speculative execution, outperforms state-of-the-art abstract interpretation techniques that may be unsound.

Conference Day
Tue 25 Jun

Displayed time zone: Tijuana, Baja California change

14:00 - 15:30
Static AnalysisPLDI Research Papers at 229AB
Chair(s): Martin C. RinardMassachusetts Institute of Technology
14:00
20m
Talk
Abstract Interpretation under Speculative Execution
PLDI Research Papers
Meng WuVirginia Tech, Chao WangUSC
Media Attached
14:20
20m
Talk
A Fast Analytical Model of Fully Associative Caches
PLDI Research Papers
Tobias GysiETH Zurich, Switzerland, Tobias GrosserETH Zurich, Laurin BrandnerETH Zurich, Switzerland, Torsten HoeflerETH Zurich
Media Attached
14:40
20m
Talk
Sound, Fine-Grained Traversal Fusion for Heterogeneous Trees
PLDI Research Papers
Laith SakkaPurdue University, Kirshanthan SundararajahPurdue University, Ryan R. NewtonIndiana University, Milind KulkarniPurdue University
Media Attached
15:00
20m
Talk
Size-Change Termination as a Contract
PLDI Research Papers
Phúc C. NguyễnUniversity of Maryland, Thomas GilrayUniversity of Maryland, Sam Tobin-HochstadtIndiana University, David Van HornUniversity of Maryland, USA
Media Attached