Loren Roosendaal
Leiden University, Postbus 9500, 2300 RA Leiden
Media Technology MSc Program
This paper describes a novel combination of techniques used to evolve strategies targeted at defeating unknown opposition. In order to achieve this goal we use the available predecessors of our opposition and through the use of evolutionary algorithms evolve a new individual with high chances of defeating the current opposition. Experimental results using a game called “CoreWar” show that our approach is superior to techniques that were used previously.
In '84 CoreWar was born, inspired by programs such as “Darwin”, this brainchild of A. K. Dewdney presented an interesting challenge [1], which appealed to Computer Scientists all over the world. This challenge was that of creating an assembly program, written in a language called “RedCode”, with the sole intention of crashing all other programs running in the “Core”; a small area of cyclic virtual memory. These programs are commonly referred to as “Warriors”. This environment proved to be great for conducting research on genetic algorithms.
As early as 1991, John Perry an avid CoreWar player showed how simple CoreWar Warriors could be evolved in only a few generations. After Perry made his exploits known to the community more CoreWar evolvers started to make their appearance. Popular evolvers included Newton's “RedMaker”, Ankerl's Yace (Yet Another Corewar Evolver) and Hillis's RedRace.
In 2005, Corno, Sanchez and Squillero published their paper on evolution in games (such as CoreWar) and how it might help microprocessor validation. [2] In this paper they also mentioned the result of their work, the first evolved warrior to take the lead on several Hills which contained some of the best man made warriors.
This paper continues this interesting line of research and shows its potential in other directions. It presents a novel combination of techniques targeted at evolving strategies to beat an unknown enemy by exploiting knowledge about its predecessors, using our CoreWar based implementation as an example. The goal of this paper is twofold. We seek to explain our approach to solving this problem and to show the similarity of our example implementation to another interesting challenge in the software domain. Through this last goal we hope to demonstrate the usefulness of this approach to a very different activity; that of testing software for network vulnerabilities.
CoreWar competition usually takes place online. “Hills” were formed for this purpose. A hill maintains a list of 50 programs which are ranked according to their performance versus every other program on this list. New programs are usually submitted by e-mail and are tested against the top 50. If they perform better then at least one of the members of the hill they are added to it and the program with the lowest score is removed from the hill. The popular hills tend to see hundreds of successful challenges like these every month. The best programs will often stay on a hill for a very long time, some surviving thousands of challenges.
The best warriors that were on the hill in the past, but have now been defeated, can usually be found on a special “hall of fame” hill, called the “Koenigstuhl”. This hill was vital to our research as it contained many predecessors of the warriors that dominate the hill today.
We made it our goal to defeat the current hill. Unfortunately this goal couldn't be attained by evolving warriors that used the current hill as a fitness function, since the source of the warriors currently on the hill wasn't available. Instead we assumed the following:
Based on this assumption we gathered the warriors from the Koenigstuhl and implemented a compiler and interpreter that could test these programs against each other quickly. We analyzed the RedCode language and mapped it to a genotype representation which allowed us to define highly efficient crossover and mutation operators. Both by ensuring a one to one mapping from phenotype to genotype and vice versa and by using this mapping to calculate a special genotype probability distribution which was used during mutation. This distribution was calculated based on the genotype distribution of the Koenigstuhl warriors.
We created an evolver compatible with this representation and used the performance versus the warriors gathered from the Koenigstuhl as its fitness function. At the same time we also seeded the first population with these Koenigstuhl warriors.
After 3 hours of evolution our best individual was submitted to the hill at the University of Alberta, where it immediately took first place, even beating some individuals that where evolved using a massive clustered network.
After this success we took our best individuals and used them to replace the Koenigstuhl warriors that were used as the fitness function. Our theory in doing so was that if the warriors on the hill were built to defeat these same Koenigstuhl warriors and our first set of warriors was evolved to do the same, then the best scoring warrior that could be developed for the hill right now might well be one which aimed to defeat warriors that where built to defeat the Koenigstuhl. After a few more hours of evolution the best individuals were selected, these individuals performed slightly worse against the Koenigstuhl warriors, but where better at beating those that performed well against the Koenigstuhl. We submitted a total of 4 warriors to the hill which managed to take places 1 through 4, proving our theory and showing the similarity between a game of CoreWar and an arms race. This effect is seen in the constant fluctuation of the strategies that dominate the hill, just like in modern warfare, where the rise of one strategy (armor) is followed by that of a counter strategy (armor piercing weapons), which is in turn countered by a change of strategy on the other side (faster, light vehicles).
In the connected world of today network security is rapidly turning out to be one of the most vital requirements of our software. An arms race is taking place between developers and (blackhat) hackers. The goal of this race is simply to find the next hole in software security before the other party does. The results of this race can be found in the form of both exploit code and security patches. We propose a new method that uses all this data which is available to the developers of network software in combination with their home advantage, the advantage of having the source code to their software, to beat hackers to the punch. Since the amount and diversity of instructions executed to handle a network packet is an excellent indication of test coverage and the stability of the system is an excellent indication of a successful solution (such as a buffer overflow exploit). We propose using these metrics as a fitness function while at the same time using all the previously found exploits and quite possibly all the documented “legal” packets as the first population of a genetic algorithm. This way exploits could be rapidly located and fixed by attacking your own code, quite possibly before the software is even released. On top of this the nature of this approach also ensures that sufficient variations on previously found exploits are tested to ensure the bug fix has indeed been adequate.
In this paper we described a novel evolutionary approach to defeating new and unknown or even undeveloped future strategies based on old strategies believed to be related to those that will show up in the future. We showed how using this approach in the game called CoreWar yielded amazing results within a minimal amount of time and how we were able to create even more powerful warriors by using our algorithms to create a fitness function that closely resembled our expected opposition. Finally we proposed the use of our approach as a tool for testing network software. We believe the use of the described methods would lead to a significant increase in network software security. We will continue to develop this approach to evolving algorithms both by improving the methods of evolution and by experimenting with new types of problems and data.
[1] A. K. Dewdney, “Computer recreations: In the game called Corewar hostile programs engage in a battle of bits”, Scientific American, 250(5), pp. 14-22, 1984
[2] F. Corno, E. Sanchez, G. Squillero, “Evolving Assembly Programs: How games help microprocessor validation”, IEEE Transactions on Evolutionary Computation (9-6), pp. 695- 706, 2005