Title
Program Analysis through the Algorithmic Lens

Abstract
Is my program correct? Does it respect its specification? Does it utilize resources efficiently? The complexity of software renders each of these questions algorithmically unattainable, yet they remain of paramount importance for safe and secure software systems. Program analyses take charge of this task, by answering pragmatic approximations to these questions. Their success lies on a delicate balance between the development of models that are sufficiently close to the target program, yet amenable to efficient automated analysis.

In this talk I will present some of my recent research in this direction, mostly in the context of testing concurrent programs. A central theme is their algorithmic treatment, which tries to provably render the boundary between tractable and intractable approximations. While there is little to do for the intractable, our tractability results have driven the development of testing tools.