  The predictability of program execution provides attackers a rich source of
knowledge who can exploit it to spy or remotely control the program. Moving
target defense addresses this issue by constantly switching between many
diverse variants of a program, which reduces the certainty that an attacker can
have about the program execution. The effectiveness of this approach relies on
the availability of a large number of software variants that exhibit different
executions. However, current approaches rely on the natural diversity provided
by off-the-shelf components, which is very limited. In this paper, we explore
the automatic synthesis of large sets of program variants, called sosies.
Sosies provide the same expected functionality as the original program, while
exhibiting different executions. They are said to be computationally diverse.
This work addresses two objectives: comparing different transformations for
increasing the likelihood of sosie synthesis (densifying the search space for
sosies); demonstrating computation diversity in synthesized sosies. We
synthesized 30184 sosies in total, for 9 large, real-world, open source
applications. For all these programs we identified one type of program analysis
that systematically increases the density of sosies; we measured computation
diversity for sosies of 3 programs and found diversity in method calls or data
in more than 40% of sosies. This is a step towards controlled massive
unpredictability of software.
