Exploring the Paretto front of diverse program variants

Contact: Benoit Baudry (benoit.baudry@inria.fr)
Keywords: software diversity, program transformation, approximate computation, program synthesis


Software developers must constantly consider a wide variety of concerns in the code that goes into production and, to this extent, they must constantly take multi-criteria decisions. For example, they must often think about functionality, fault-tolerance (through exception handling) and performance (through ad-hoc optimization). Eventually, they deliver a program that implements one possible trade- off between all these concerns. Yet, there naturally exist other possible trade-offs that could provide satisfactory solutions with different code [5, 4].
We aim at automatically building and exploring the set of programs, in the neighbourhood of a given program, which provide similar functionalities but different trade-offs between quality criteria. In other words, we aim at synthesizing the Paretto front of functionally similar programs, through automatic code diversification [3].
This work will exploit our previous work on automatic diversification of Java programs [1]. We developed a set of program transformations to synthesize sosie programs, i.e., program variants that pass the same test suite as the original. We have observed that there regions of code that have very plastic, open specifications. These regions can be modified to change some quality factors, without sacrificing functionality. Examples of such regions include code that optimizes data structures, that limits computation time, that introduce redundant code, etc. [2]. Yet, these regions are not explicitly documented in the code, are not correlated to specific syntactic structures and are unequally present in a program. Consequently, the search space to explore the Paretto front of similar, diverse programs is very irregular.
This internship will consist of the following tasks: investigate meta heuristics to automatically gen- erate program sosies that are as different from the original as possible, setup a performance evaluation harness to position the sosies on the Paretto front, classify the code regions that are prone to the exploration of the front.
The applicant should have previous experience in software engineering and program analysis, as well as a taste for program transformation and experimental science.


[1] B. Baudry, S. Allier, and M. Monperrus. Tailored source code transformations to synthesize computationally diverse program variants. In Proc. of ISSTA, pages 149–159, CA, USA, 2014.
[2] B. Baudry, S. Allier, M. Rodriguez-Cancio, and M. Monperrus. Automatic Software Diversity in the Light of Test Suites. Technical Report 1509.00144, ArXiv e-prints, 2015.
[3] B. Baudry and M. Monperrus. The multiple facets of software diversity: Recent developments in year 2000 and beyond. ACM Computing Survey, 2015.
[4] M. Rinard. Obtaining and reasoning about good enough software. In Proc. of DAC, pages 930–935, 2012.
[5] E. Schulte, J. Dorn, S. Harding, S. Forrest, and W. Weimer. Post-compiler software optimization for reducing
. In ACM SIGARCH Computer Architecture News, volume 42, pages 639–652. ACM, 2014.