Replicators and Selection


+5 rating, 5 votes
Loading...

Replicators and Selection
Science
A lesson in navigating logical space
Share

Introduction

This post is about (biological) replicators and (natural) selection, but let us start with some thoughts on network security (bear with us, we’ll explain later). Most people don’t want just anybody to use their wireless network and this is why they protect it with a password. Suppose someone has heard that strong passwords are important and therefore uses an 8 digit password containing upper and lower case characters, symbols, and digits:

DHSj-SSd

One way of figuring out a password is by using the brute force method: an attacker blindly tries out every possible combination and tests whether the router accepts it. How feasible is this method for a password of this strength? If you try 3’100 combinations per second (this is the maximum with WPA keys) you’ll need almost 12’000 years to try all combinations. Granted, finding the right key might take less time than that, but the network is still fairly safe from brute force attacks.

But now imagine we could somehow find out whether the first four digits of the incorrect keys we are testing match the password. Suppose we try the key

DHSjjT-Q

and the response you get from the router would somehow tell us that, although the key is wrong, the first four digits are correct. We could then stop varying the first four digits and instead hold these fixed while varying the last four digits until the router accepts the password. How long would this whole procedure take? Slightly more than paltry 6 hours! (The bad news is that something very much like this is indeed possible with many wireless networks.)

What exactly is responsible for this massive difference in time required to crack the password? In the first case we rely completely on randomness. We systematically go through all possibilities, but each guess is a shot in the dark and as such it is completely random whether it is correct. The only “selection” happens once we send a password combination and the router tells us either “yes” or “no”. But this is not how things work with the second method: there we have a two-stage selection. We randomly choose the first four digits until we get a positive response from the router. This is the first selection. Then we create variations of that “proto-password” and only modify the last four digits. This “second generation” of passwords resembles the first password in its first four digits, only the last four digits differ. This means that dump randomness now has less work to do, it only has to get four digits right, then we can manually pick this “proto-password” and let randomness get the next four digits right. Once we got them the router will again tell us by accepting the complete password.

Self-Replication and Selection: Navigating Logical Space to Beat the Odds

The phenomenon, of which the password case is an instance, is a general one. It can be described in terms of three key concepts: that of logical space, replicators, and selection.

There is a space of logical possibilities or logical space – it is the space of all the individuals which could exist. This can be an 8 dimensional space in the case of our password, where each dimension corresponds to one digit and can have either an upper/lower character, a digit, or a symbol as a value. But it can also be something like a genetic space, where each coordinate in this high-dimensional space corresponds to one complete gene configuration. Usually the space of logical possibilities is vast. Even for our passwords the space contains 768 possibilities. The chances of landing with one try at any given coordinate in this space are therefore tiny. The chance of guessing the right password with one try is 1/768.

Additionally we need a replicator. A replicator is any entity spawning copies of itself or creating “second generation” entities. But not any kind of copy or second generation will do, it is important that the copies resemble the original, that they inherit most, but not all, of its characteristics. Such replicators are sometimes called informational replicators (Szathmàry 2000). An example of a sort of replicator which does not satisfy this criterion is a fire. A fire spawns other fires in the right environment, but the characteristica of the second generation fires are not determined by their parent fire, they are solely determined by the environment (Smith 1986). In our examples the replicators are the passwords. Usually brute force tools go systematically through all possibilities. They may start for example with 10000000 and then go all the way to =0000000 before they change the second to last digit. This means that each new password generation inherits much of its last generation.

The space of logical possibilities is vast and replicators will move unguided through it. Some replicators, for example passwords in a brute-force attack, move systemically in the sense that their copies exhibit systematic variation, but other replicators move less predictably through logical space. Where replicators go in logical space is in no way influenced by their environment, they simply follow the rules of their copying process. Due to this the probability that they will reach any specific coordinate in logical space within a certain timespan is usually astronomically low. In the case of the password the process of landing at the coordinate of the correct key takes up to 12’000 years. But now we add selection to the mix. Suppose there is a mechanism which only picks copies of replicators which satisfy certain criteria and destroys the others, or prevents them in some other way from replicating further. The criteria could be anything. In the password case it was having its first four digits match that of the password – once we have a replicator copy which has the first four digits right (the proto-password) the replication process continues from this key. The others are “destroyed”, or at least ignored. The resources, in the password case the 3’100 keys per second, are used solely on the replicators which have been selected. As we have seen, this element of selection increases the probability that the path of the replicators will reach the coordinate of the right password massively, it now takes merely 6 hours to get there.

This means that selection helps the replicators navigate logical space and increases the probability of reaching a certain coordinate in logical space within a certain timespan massively. Which coordinate will experience such a probability boost depends on both the variation which happens during the replication process and the criteria for which replicators are selected. This is the most general description we can give of the phenomenon we have observed in the password case.

Note that this process does not need to involve any teleology – the variation between replicators is not geared towards reaching a certain coordinate in logical space. In the password case this is simply because we do not know which coordinate the correct password has. And even the selection process may be a purely causal process. In the password case there is some teleology involved, an attacker consciously selects for passwords which match the first four digits of the right key, but this is not a necessary feature of selection as we will see in the next section.

Genetic Space, Biological Replicators, and Natural Selection

We are the result of the perhaps most impressive instance of this phenomenon we have ever observed: biological evolution. Our genes are the replicators. They create copies of themselves which sometimes contain small mistakes which we call mutations. The genes we know from species around us represent only a vanishingly small fraction of all possible genes. Genetic space is vast beyond imagination. Daniel Dennett calls this genetic space the Library of Mendel (Dennett 1995, p. 111). For genes to accidentally go all the way from the simple form of our earliest ancestors to the complex structure of our own genes is astronomically improbable. But the purely causal mechanism of natural selection, working like the attack tool picking only passwords which got the first four digit right, (blindly!) guides the genes through genetic space towards the genetic material we observe around us today. Only the genes which are better adapted to their environment than their competitors get to replicate, the others fall apart and cannot spawn copies of themselves. It turns out that the selection criterion of fitness tends to pick more and more complex genes – although this is by no means a general rule.

(To prevent a possible misunderstanding: natural selection does not work on the genes directly, it works on the plant or animal bodies they produce, their phenotype.)

It can seem incredible that the complex life forms around us should have come into existence “by accident”. But, as we have seen in the password case, this is not the whole story. If we add the right kind of selection to the mix, the odds of reaching a certain point in logical space within a certain timespan are boosted massively. A reduction from 12’000 years to 6 hours could turn out to be a relatively small reduction compared to how much natural selection has reduced the time necessary to create complex species compared to a purely random approach.

References

Dawkins, R. (1996). The blind watchmaker: Why the evidence of evolution reveals a universe without design. WW Norton & Company.

Dennett, D. C. (1995). Darwin’s dangerous idea. The Sciences, 35(3), 34-40.

Maynard Smith, J. (1986). The problems of biology (Vol. 144). Oxford: Oxford University Press.

Szathmáry, E. (2000). The evolution of replicators. Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences, 355(1403), 1669-1676.