Extinction and End Games

Recently Jeff Moss gave an introduction to the opening of Black Hat DC 2009, in which he essentially asked "is there any problem in security that has been definitively crushed or completely eradicated? Is there a problem from 10 years ago that is no longer a concern?" Specific instances of problems have been eradicated but the families of problems that persist include computer viruses, buffer overflows, cross site scripting (XSS), SQL injection (SQLi), etc. Computer viruses have existed since 1971, buffer overflows were popularized in 1996, XSS has been around since about 1997, and SQLi has been present since 1998.

Managers and security professionals are often looking for that silver bullet for solving all of the information security issues that an organization may have. Vendors of security products are often willing to demonstrate that their single or integrated security solution will provide all of the protection that an enterprise needs against emerging threats, the next generation of attacks, etc.

As information security is engaged in a Red Queen race or an evolutionary arms race, there should be no expectation that a single or multiple strategies can always ensure the survival of an organization. The security controls that are put in place will act as selection pressures on their adversaries to ensure that only the successful exploitation strategies are passed on to the next generation of attacks. The security controls are going to ensure that attackers and malware authors continue to escalating their exploitation strategies against the implemented security solutions to ensure their survival. This escalatory relationship is akin to the evolutionary arms race between predator and prey.

There are multiple outcomes for predator and prey resulting from an evolutionary arms race (Evolutionary Biology, 3rd Edition, Futuyma);

• The first outcome is that neither side gains the advantage. In this situation, the evolutionary arms race continues with each side escalating their strategies (Richard Dawkins and J. R. Krebs, Arms Races between and within Species, 1979). Within an escalatory arms race, both the predator's weapons and the prey's defenses become more effective than previous generations, but neither has an advantage (G.J. Vermeij, Evolution and Escalation, 1999). More simply stated, as time passes a predator's weapons become more refined, and in response to the evolution of these better weapons a prey species evolves better defenses. The end result is neither side makes any progress, but a modern predator would be able to better exploit an ancestral prey than a predator from that period.
• The second outcome is that as the evolutionary costs for continuing the escalation increase, a set of strategies employed by both sides causes an equilibrium to be established. This equilibrium can form what is referred to as an Evolutionarily Stable System (ESS). In an ESS, a point is reached where the system is stable and resistant to invasion from outside strategies based on the costs associated for each strategy. ESSs are detailed in Evolution and the Theory of Games, by John Maynard Smith, 1982 and in the Selfish Gene by Richard Dawkins.
• The third outcome is that the system suffers from continual or periodic changes as a new strategy is employed and a counter-strategy is evolved and then deployed. This is similar to disease/parasite and host relationships, in which a disease or parasite invades a host. The population takes time to develop resistance or immunity to the invasive disease/parasite. For a period of time the population may be quite successful at repelling the disease/parasite, but eventually the disease/parasite can develop a strategy to overcome the factor that was keeping them out of the host. This is commonly seen as the over use of antibiotics has caused various strains of antibiotic immune diseases to develop; such as Methicillin-resistant Staphylococcus aureus (MRSA) or Extensively Drug-Resistant Tuberculosis (XDR-TB).
• Lastly the outcome of an evolutionary arms race can result in one or both of the species going extinct. One of the sides of the evolutionary arms race evolves an adaptation which allows it to fully exploit or evade exploitation from the other species in a way that it cannot adapt before becoming extinct. Conversely, if the predator was entirely focused on exploiting a single prey species, with the extinction of the prey, the predator species may also collapse.

Ideally, the goal of information security is to seek the last outcome of an evolutionary arms race, in which the opponent becomes extinct. Although this is the goal, currently within the malware and anti-malware Red Queen race, it appears that the reality of the situation is that the race is in the first outcome (continued escalation) or the third outcome (cyclic strategy and counter-strategy development). The race will continue to persist in one of these states for the foreseeable future. The cost of the evolutionary arms race is still asymmetric between defenders and attackers. The methods and strategies employed to evade Anti-Virus scanners with Free/Open Source Software (FOSS) tools such as the Metasploit Framework are still fairly effective, despite the strategies begin implemented prior to March 2008.

In order to cause an extinction of predator strategies (or in the case of information security an attacker's or malware author's strategies), it is not necessary to wipe out an entire population in a single event. Within evolutionary biology, an estimate of effective population size is given by the following equation; Pi = P0 * exp([b-d]*t), where Pi is the population size in the future, P0 is the initial effective population size, t is the time, b is the birth rate, and d is the death rate. As long as the birth rate is higher than the death rate, the population size will grow exponentially. If the death rate is higher than the birth rate, the population is shrinking. The birth and death rates are typically associated with environmental factors such as competition for available resources and types of selection pressures. Essentially the environment only has to change faster than the opponent's strategies can adapt.

By inspecting the rate of growth for malware, it appears that the "birth" rate is higher than the "death" rate. The effective malware population (based on the number of unique samples) is growing exponentially. The costs for malware populations have not reached their carrying capacity on the environment. Within evolutionary biology and ecology, the carrying capacity is the population size that a given environment can support based on the available resources. If a population is increasing in size, then the carrying capacity has not been reached as more resource are available to support the growth. As the population approaches the carrying capacity, the population growth decreases as available resources are more difficult to access. If the population exceeds the carrying capacity, the population will reduce in size as selection works against the population and the entities which are not able to extract enough resources to survive.

Ideally, security professionals would like to see the current situation change from being a continually escalating arms race or a cyclic strategy/counter-strategy to that of the extinction of attacker/malware strategies. By changing the selection pressures that are applied against these invasive strategies, it could be argued that extinction can be triggered. A set of selection pressures could be implemented such that nothing could survive or the selection pressures of the environment change so quickly that the invasive strategy does not have time to evolve successful adaptations. Another solution could involve changing local environmental selection pressures independent of the global selection pressures such that only specific strategies can thrive in specific "regions." This strategy is similar to having an organization switch to a different operating system and/or browser, so the commonly employed exploit strategies fail on the organization.

One of the main problems with implementing a strategy to solve the issue drastically changing the environment is that the environment has to change quickly, more quickly than the invasive strategy can evolve adaptations. The current computing environment is not conducive to drastic changes implemented through out the entire infrastructure. Virtualization is often proposed as a security solution, but to implement this solution globally would take years to decades. Most users are not going to upgrade to a virtualized operating system, unless they are going to acquire a new computer. Typically computers are not replaced or even upgraded annually. This represents a significant period of time in which attackers and malware author's can update their strategies and adapt to the new environment. As previously discussed, attackers and malware have the advantage when the environment changes due to their smaller size.

Another method for improving the situation within the Red Queen race that is occurring within information security, would be the attempt to convert the situation into an ESS. In an ESS, there is an equilibrium reached that is resistant to invasion by outside strategies. If this occurred attackers and malware would achieve a balance with the security professionals in which new infections are cleaned at approximately the same rate as they are occurring.

Instead of focusing on the extinction of malware in the near term, another strategy would be to focus on the infectious nature of malware and reducing the associated virulence. In dealing with the interactions between diseases/parasites and their hosts, the virulence of the disease/host tends to be associated with how it is transmitted between the hosts. A disease or parasite that is transmitted from parent to offspring is said to be vertically transmitted though a population. Diseases and parasites that are vertically transmitted tend to have a lower virulence, or exhibit avirulent behavior. If the disease or parasite reduces the host's fitness too much, then they will not be able to propagate to its offspring after/during reproduction, since no offspring will be produced. Horizontally transmitted diseases/parasites jump from host to host in a population through a variety of different mechanisms; direct contact, the environment or a pathogen vector (such as a mosquito in the case of Malaria). As the virulence of the disease/parasite is not dependent on the survival of the host to reproduce, only the contact with other vulnerable hosts, it is capable of reaching a much higher virulence and significantly reducing the fitness of the host.

There are a number of different ways that an evolutionary arms race can play out; it can continue to escalate, it can continue to escalate until the costs associated with the escalation cause the system to stabilize into an ESS, it can develop in cyclic phases such as the case in the interactions between diseases/parasites and hosts with their immune responses, or one of the interacting entities can go extinct as it is no longer able to adapt to the environment. With the rate that the malware population is increasing, it does not appear that the evolutionary arms race has stabilized into an ESS or that malware will go extinct in the near future, so either the escalatory nature of the race will continue or the cyclic interplay between strategy and counter-strategy will continue for the foreseeable future. The strategies employed by attackers and malware authors rely on small easily adaptable applications, which in terms of evolutionary biology means that the can more readily adapt to environmental selection pressures. Instead of causing malware to go extinct, perhaps a way can be found to tie it to the host, and force it to adopt a more avirulent or beneficial behavior by being vertically transmitted through a computer population instead of horizontally transmitted.

Evolutionary Costs and the Life/Dinner Principle

As illustrated previously, the time it takes to evolve strategies and/or the ability to exploit existing environments (or a population) is important. An additional factor that should be considered when examining exploits are the associated costs. Within evolution these items are referred to as the evolutionary costs.

There are costs associated with utilizing a strategy, evolving a new strategy, and neglecting the use of an existing strategy.

• In utilizing a strategy, an entity must pay the costs of maintaining that strategy. It should be recognized that in employing or retaining the capability of a strategy consumes resources that could have been spent elsewhere.
• Evolving a new strategy also consumes resources, and those resources have to be taken from another source. They are going to come from resources that could have been spent to refine another strategy, develop a different strategy or continuing the usage of a existing strategy (i.e. allowing a current strategy to atrophy).
• Lastly neglecting the use of an existing strategy could have the cost of preventing an organism from surviving from the fact the organism may have misspent resources. Not using an existing strategy could adversely affect an entity in that the resources consumed during development a new strategy could have been used elsewhere to form a necessary new strategy (and are considered to have been wasted in this effort).

Evolution and development are two different concepts within evolutionary biology. In a simplistic form, evolving refers to the process of creating a strategy through natural selection. Development is the process of creating a strategy for an individual entity. To more clearly illustrate the difference; birds as a class have evolved wings but while they are individuals in the egg as embryos they develop wings.

When dealing with the costs of employing strategies for survival, it should be noted that the costs for all entities involved are not shared equally. This potential asymmetry is summed up in the life/dinner evolutionary principle (as popularized in both the Selfish Gene and the Extended Phenotype written by Richard Dawkins, but originated by M. Slatkin in Models of Coevolution). Slatkin uses the rabbit and fox from one of Aesop's fables to illustrate the basic idea of the asymmetrical costs in association with life/dinner principle.

Consider the case when a rabbit is being chased by the fox. The rabbit is running for its life, while the fox is only running for its dinner. The cost of failing is different for those involved. For the rabbit, if it fails it looses its life, while for the fox; if it fails it only looses its dinner. So the rabbit is going to be willing to spend more to ensure its survival in a given race, because if it is unsuccessful there will not be another generation of rabbits produced (at least from this rabbit's germ line). The fox can afford to lose this specific race; as if it fails it will have an opportunity to pursue another rabbit in the future.

It could be argued that if after several of these races and the fox remains unable to catch a rabbit, then it could very well be facing its final race too. This is true, but if you compare the costs associated with a single race, the rabbit is still going to face the more severe cost of failure.

Within this co-evolutionary race, the rabbit/fox race can pursue a number of different strategies to ensure their survival. The simplest way to continue the race would be that the fox can attempt to run faster as well as the rabbit can attempt to run faster. It is important to consider that this is not the only strategy that the rabbit can pursue; it could also develop better camouflage, better sensory systems to learn of the foxes presence before he comes too close, or even become more maneuverable so that if the fox does pursue him he can out maneuver the fox and escape, or the rabbit can just produce so many rabbits that in general the likelihood of a single individual becoming dinner is small. In general which ever method becomes more prominent in the rabbit population, the fox will have to escalate his attacks to deal with these new strategies.

Although the co-evolution is occurring in the rabbit/fox competition, there are costs and trade offs associated with each of these potential advancements. Obviously as we do not see rabbits that can run arbitrarily fast (out side of cartoons and comics). In order to evolve a strategy, there are costs associated with this development. The development takes resources that could have been devoted to creating or even just maintaining something. In the security field there are trade offs which must be considered, and the penalties for not maintaining the proper balance of strategies can be just as severe for an information system as it is for a rabbit.

The penalty asymmetry is commonly seen in the development of an information system. When a system is designed, it has to address all of the threats that will be present in its environment, but an attacker only needs to find one successful strategy to compromise the system. An attacker also has additional advantages;

• They do not have the expectation that they are not going to compromise every system they encounter. If they were unsuccessful in exploiting the initial target, they can move on to another system. It is built into their strategy, that they will not compromise every system they encounter only just enough to find dinner.
  
• They have time to attempt multiple strategies against the system and continue using different combinations of strategies until they find one that works.
• They do not have to play by the rules. Even more than that they have no expectation that they are going to stay within the design requirements of the system.

Unlike the general case in evolutionary biology in which if any animal's strategy fails, it pays for the costs of that failure directly. While within information security those who fail do not necessarily pay the costs for the failure. For example, spear phishing (e.g. targeted phishing) and whaling targets an individual within an organization to gain access to its resources and information. When an individual opens an email that contains a targeted attack, although they are the cause of the failure, it is the organization which pays the cost of the failure. Another cost to consider in information security is who pays the cost of failure.

Although there are response lags to develop or deploy new strategies and it takes time to exploit other resources. There are costs for developing, maintaining and even using evolutionary strategies. These evolutionary costs are also not necessarily paid evenly by all involved in the red queen race.

Red Queen Races

The Red Queen race has been used as a model for understanding some of the various evolutionary arms races in evolution such; as parasite/host relationships and the response of pathogens to resistance (See Ridley's Red Queen or Ridley's Evolution 3rd Edition). In information security, as part of the malware red queen race, malware has co-evolved with malware detection and analysis to not only maintain its fitness but become the dominant threat to systems.

Within information security there are a number of red queen races in effect;

• Attack strategies against applications/networks and the associated defensive strategies
• Malware attack strategies and the resulting malware detection strategies.
  
• Malware defensive strategies to prevent its analysis.

It could also be argued that cryptography is a red queen race between keeping things secret and attempting to reveal them. Cryptographic algorithms are constantly being developed to counter flaws discovered in existing algorithms and advances in technology which allows existing flaws to be exploited faster.

The strategies of attackers have changed dramatically since the early period of networking where attackers used manual methods (or custom scripts) that required a high degree of skill and/or knowledge to attack a single target. Now as tools have developed, attacks can be conducted by individuals with a low skill level and/or little knowledge about how the underlying attack works but using automated tools against any system that is accessible on the network (an overview of the development can be found in Computer Security by Bishop). In response to the development of attack tools, intrusion detection systems and log analysis tools were developed. In order to evade detection, attackers found ways to obfuscate their attacks to ensure that the attacks were reaching the end systems without alerting those monitoring networks (See libwhisker's IDS evasion techniques). More modern IDSs have responded by performing packet reassembly at the IDS to conduct packet inspection, but this consumes resources which could be allocated elsewhere. Tools such as the Metasploit Framework are making their attacks more difficult to detect by including various payload encoding techniques. Some tools are beginning to include encryption as their encoding methods are proving to be insufficient.

An overview of the history of malware can be found on VirusList.com's History of Malicious Programs. Malwarefinds its evolutionary beginnings in basic viruses which simply replicated to other hosts and deleted files or attempted to consume system resources. Early programs to detect malware were simply focused on signature matching techniques, and now malware detection has a variant of different techniques to detect malware.

• Signature detection in which streams of bytes are analyzed for virus signatures.
• Program emulation in which the functions of programs are emulated and executed. A program is determined to be malicious based on the events that occur.
• Virtualized execution in which the byte streams are executed in a sandbox. The execution and results are watched to see when effect on the system it could potentially have.
• System monitoring in which all programs are executed normally and the system's reaction is monitored for signs of malicious behavior.
• Anomaly detection in which a system's baseline behavior is determined and as the system operates deviations are monitored to determine if a malicious program is operating.
  

Modern malware has evolved a variety of different techniques to evade detection and prevent analysis. The following items represent some of the strategies that are employed by malware to evade detection and remain in operation even after detection.

• Metamorphic and polymorphic viruses - counter strategy to signature based detection.
• Multiple layers of encoding - counter strategy to prevent detection and analysis. Some malware makes the decoding dynamic so that it can only jump to the correct instructions in a non-virtualized environment.
• Memory only operations - counter strategy to performing offline analysis of malware. If it only exists in memory then taking the system offline will destroy the malware.
  
• Modification of Service ACLs - uses the systems access controls against it to prevent removal by removing all access to the service's registry keys (except for the SYSTEM account).
• DLL injection - Counter strategy against detection and removal. By being resident in another process it is more difficult to detect and makes it harder to remove the malware. This strategy has even been adopted by anti-malware vendors to ensure that malware cannot disable their detection engines.
  
• In Memory Patching - counter strategy against other infections. If the vulnerability that was exploited to gain access to the system is still open, other malware can infect the system and compete for system resources. Some malware installs permanent patches, but these can easily be detected as they modify the system's baseline and if the system is rebooted a reinfection cannot occur if the malware was only memory resident.
  
• Virtualization detection - counter strategy to analysis in virtualized environments. The Storm BotNet had VMware and VirtualPC detection methods, and if it detected that it was operating in a virtual environment it rebooted the system to clean the system and prevent further analysis. The Conficker/Downadup used SLDT/LDT results to determine if it is operating in a virtualized environment.
• Disable running anti-malware services during install - simple counter strategy against malware prevention and removal is to simply disable the malware detection services. In addition to simply disabling these services, some malware will make it difficult to access websites of anti-malware vendors.
• Remove system restore points - counter strategy to prevent system user's from just rolling their system state back to a previous clean point.
• Use of anti-malware products as pre-screening - Some malware when it is designed is tested against existing malware products to ensure that there is a poor detection rate. There is no advantage in using a product that is already commonly detected.

The methods of locating remote hosts have also evolved. They began with small routines to simply scan remote addresses randomly and as fast as possible to spread as fast as possible. Some of these algorithms were flawed and prevented a maximal infection. Now there are prescan activities in which a scan of available targets that are vulnerable to an attack is performed prior to releasing malware. Malware will often scan for hosts on adjacent network spaces before seeking out other networks randomly (hosts on the same network will often be configured and managed the same way so they will likely have the same exploitable vulnerabilities).

Not only are the specific survival strategies of malware evolving in response to threats but the general concept of malware has changed. Malware has changed from seeing remote systems merely as targets to viewing them as valuable resources. Since systems are seen as resources, it is no longer advantageous to spread as fast as possible and take down as many systems as possible, these resources need to stay active in order to be of any use. Lastly malware is also moving in the direction of targeting specific individuals and/or organizations. The more customized the malware is to a specific organization or individual, the more likely it is to succeed in infecting a target host. The general software quality of malware has changed; it is no longer just written and released. It has acquired the properties of being professionally written to be more flexible and modular, and includes error handling and proper resource deallocation/cleanup.

Enter the Red Queen

The Matrix is well known through out the information security profession and has become ingrained within the hacker culture. The iconic scene when Neo makes the ultimate choice is a pivotal point to the mythos. But when one examines the situation, a different path appears and perhaps the one Neo should have taken. Morpheus offers Neo the choice: "You take the blue pill; the story ends, you wake up in your bed and believe whatever you want to believe. You take the red pill; you stay in Wonderland and I show you how deep the rabbit-hole goes." Neo wants to learn the truth, so he accepts the Red pill and is brought into an adjacent room to be born into the real world. There sitting besides Neo is a Looking Glass. While Morpheus' crew is attempting to locate Neo, the Looking Glass changes and responds to Neo's touch. Maybe he should have accepted neither pill, and went through the Looking Glass instead. There instead of finding the Architect in white, who created and oversees the Matrix, Neo would have found the Red Queen, who determines the strategies that the entities within the Matrix use to respond to their reality.

Charles Darwin's 1st Edition of On the Origin of Species will be 150 on the 24th of November 2009. Given the complexity of Information Security and the rate at which the security landscape changes it might be appropriate to see if the concepts of Evolutionary Biology can be applied to Security.

In Evolutionary biology there is the concept referred to as the Red Queen hypothesis. Van Valen defined the Red Queen hypothesis as follows; "For an evolutionary system, continuing development is needed in order to maintain its fitness relative to the systems it is co-evolving with." The name of the hypothesis is based upon Lewis Carroll's Through the Looking Glass in which the Red Queen tells Alice, "It takes all the running you can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that!"

Security appears to fit will within the conditions of the Red Queen hypothesis. It is an evolving system composed of co-evolving entities. For example, an enterprise creates an information system in an effort to assist in accomplishing a business goal. In order for the information system to be successful, it must contain a set of strategies that will allow it to accomplish the business goal in a way that does not compromise the goal in the process. These strategies are implemented in order to deal with existing threats (crackers, insiders, malware, etc), and in order for these threats to continue to survive, they must either modify their existing strategies or evolve entirely new strategies. The system must then deal with these new strategies and respond. On the other hand it could choose to ignore these evolved strategies, but then the business goals would become compromised. So each side must continue to evolve in order to survive, and so the race continues.

When attempting to draw parallels between evolutionary biology and information security, it is helpful to think of things with a slightly different terminology. Instead of thinking about attacker using exploits and defenders using signatures, these can be thought of as entities employing various strategies in competing for resources. In the case of evolutionary biology, this would be organisms using what ever characteristics or tools they have to exploit resources in the environment that allows for their survival, while in information security, it would be the various programs competing for processor cycles and system resources. Although there is a selection process for determining what survives in information security, it is not natural selection. Natural selection requires four conditions to operate (based upon those found within Evolution, 3rd Edition by Mark Ridley);

1. Reproduction - Entities must reproduce to form a new generation.
2. Heredity - Entities produced via reproduction must tend to possess the characteristics (e.g. traits) from the previous generation.
3. Individual Variation - The population of entities is not identical.
4. Characteristic Fitness - Individual characteristics have varying degrees of fitness which allows them to propagate their traits to subsequent generations.

The selection process which operates on the entities within information security does not follow any of these conditions. Some programs reproduce by installation or infection, but they do not have any individual variation which natural selection can use for determining what survives to the next generation. Stated another way, there is no flow of selected characteristics between subsequent generations of programs via reproduction. Program heredity is passed on by design, and not by reproduction. In general, programs are identical when installed, although there exists some polymorphic and metamorphic malware.

The idea of applying evolutionary biology to information security was the result of recently completing the Selfish Gene (Dawkins), the Red Queen (Ridley), and the Extended Phenotype (Dawkins).