Allopatric software diversification

by Martin Monperrus, Benoit Baudry, Carlos Melian

In ecology, allopatric diversification is when the same population is split in two different locations and diversification happens after the split. In this post, we present the concept of “allopatric software diversification”, directly inspired from the ecological concept.

The key insight is to find the equivalent of “geographical location” for software. We propose to equate “geographical location” with “region of the input space.”

Let us consider this program:

p(int x) {

 ...

}

The input space is one single integer, it can be split for instance in thre regions x<0, 0<=x<1 and 1<x.

Now what would that mean to separate this program in different locations before diversification?

It would mean to transform the program as follows:

p(int x) {

  if (x<0) {

    p1(x);

  } else if (x<1) {

    p2(x);

  } else {

    p(x); // original implementation

  }

}

Then you can start to diversify p1 and p2 with any software diversification technique (eg neutral mutations) []. Both p1 and p2 remain valid on their respective input domain with respect to the expected behavior of p.

However, after several steps of diversification, it may happen that p1 is no longer valid on the input domain x>=0, or that p2 is no longer valid on x<0. In this case, we have obtained allopatric software speciation. The cool thing thing is that p(x), composed of p1 and p2 is still valid on the whole input domain.

The idea of allopatric software diversification and allopatric software speciation seems to be generalizable to any arbitrary input domain, much more complex than simple numerical values.

Feedback welcome

–Martin, Carlos and Benoit

Dublin October 2015

Tagged as: