Contact: Benoit Baudry (baudry@kth.se)
Keywords: approximate computation, program synthesis, code analysis, software diversification
Description
Continuity analysis aims at determining the effects that small changes on the input of function have on the output of this function [1,2]. Meanwhile, approximate computing is a novel form of program analysis and runtime transformation, which trades slight losses in the accuracy of a function’s output, in exchange of savings in energy or speed [3].
Approximate computing exploits the existence of forgiving regions in code, i.e. regions that can tolerate slight degradations in their behavior and still compute an acceptable output. The intuition here is that continuous functions represent excellent candidates for forgiving regions.
The goal of this project is to exploit the sound techniques of continuity analysis, in order to build analyzers that can automatically locate forgiving regions in large programs. More specifically, the student is expected to:
- experiment with existing tools
- study the feasability of continuous analysis for Java methods
- evaluate static analysis to detect forgiving regions in Java code
References
[1] S. Chaudhuri, S. Gulwani, and R. Lublinerman. Continuity analysis of programs. In ACM Sigplan Notices, volume 45, pages 57–70. ACM, 2010.
[2] S. Chaudhuri, S. Gulwani, and R. Lublinerman. Continuity and robustness of programs. Communications of the ACM, 55(8):107–115, 2012.
[3] Z. A. Zhu, S. Misailovic, J. A. Kelner, and M. Rinard. Randomized accuracy-aware program transformations for efficient approximate computations. In
ACM SIGPLAN Notices, volume 47, pages 441–454. ACM, 2012.
[4] Goubault, Eric, and Sylvie Putot. “Robustness Analysis of Finite Precision Implementations.” APLAS. 2013.
[5] Misailovic, S., Roy, D. M., & Rinard, M. C. (2011, September). Probabilistically accurate program transformations. In International Static Analysis Symposium (pp. 316-333). Springer, Berlin, Heidelberg.
[6] Kirsch, C. M., & Payer, H. (2012, June). Incorrect systems: it’s not the problem, it’s the solution. In Proceedings of the 49th Annual Design Automation Conference (pp. 913-917). ACM.
[7] B. Danglot, P. Preux, B. Baudry, M. Monperrus. Correctness Attraction: A Study of Stability of Software Behavior Under Runtime Perturbation. Empirical Software Engineering, 2017. To appear.