Calculating Sensitivity by Parametricity
Abstract:
The work of Fuzz has pioneered the use of functional programming languages where types allow reasoning about the sensitivity of programs. Fuzz and subsequent work (e.g., DFuzz and Duet) use advanced technical devices like linear types, modal types, and partial evaluation. These features usually require the design of a new programming language from scratch - a major task on its own! While these features are part of the classical toolbox of programming languages, they might result unfamiliar to non-programming language experts. In this work, we propose to take a different direction. We present the novel idea of applying parametricity, i.e., a well-known abstract uniformity property enjoyed by polymorphic functions, to compute the sensitivity of functions. A direct consequence of our result is that calculating the sensitivity of functions can be reduced to simply type-checking in a programming language with support for polymorphism. We formalize our main result in a calculus, prove its soundness, and implement a software library in the programming language Haskell - where we reason about the sensitivity of classical examples. We also show that thanks to type-inference, our approach supports a limited form of sensitivity inference - something that, to the best of our knowledge, has not been explored before. Our library is implemented in 365 lines of code.
Biodata:
Alejandro Russo is a professor at Chalmers University of Technology / Göteborg University working on the intersection of functional languages, security, privacy, and systems. His research ranges from foundational aspects of security to practical ones. Prof. Russo worked on prestigious research institutions like Stanford University, where he was appointed visiting associate professor back in 2013-2015.