Wednesday, July 29, 2009

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.

Tuesday, July 7, 2009

Reducing the Time for Adaptation

Periodically security professionals and security vendors tout the idea that reducing the reaction time between an event and employing a counter strategy can potentially resolve the evolutionary arms races within information security. This idea is similar to an Observe, Orient, Decide and Act (OODA) loop.

In strategy, there is Boyd's OODA loop which emphasizes the idea that reducing the time required for planning and reacting faster than an opponent will provide an advantage and subsequently enhances the likelihood of the opponent making a mistake. By deceasing the time that is required to react appropriately to a situation, the initiative is maintained and consequently an opponent is always responding to the situation. The more time an opponent spends reacting, the less time they have to observe and plan; increasing the likelihood that a mistake will be made. This concept has been raised recently on the panel discussions at the CATCH 2009 conference. References to this particular type of strategy, arise periodically from malware vendors in that if the time between the release of malware and the release of generally available anti-malware signatures can be reduced, it could help to solve or alleviate the malware threat.

Applying the OODA loop or simply reducing the reaction time could potentially go a long way towards helping to alleviate the malware threat. But, it should be considered that malware will always be able to evolve more quickly than an operating system, a web application, a database or even the anti-malware tool as it has the initiative and malware is typically smaller in size and less complex. Looking at this strategy from an evolutionary biology perspective, it is similar to the Red Queen hypothesis that occurs between diseases/parasites and their hosts. It is also similar to the evolutionary arms race between malware and the rest of the information security community (anti-virus,browsers, office automation applications, operating systems, application services, etc). Viruses have genomes on the order of 10^4 base pairs, bacteria have genomes on the order of 2x10^6 base pairs, and humans have genomes on the order of 6.6x10^9 base pairs (Evolution 3rd Edition, Ridley). Modern operating systems have about 40 - 55 million lines of code (equating to 2.5 - 4 GB installed), while most malware is a few orders of magnitude smaller, approximately 119 - 134 KB in the case of Conficker.

As is the case with viruses and other more complex organisms within the real world, smaller organisms are capable of evolving at a much faster rate than large complex organisms. Consider the case of RNA viruses which have a mutation rate of about 1 mutation/generation. While bacteria have about 10^-3 mutations/generation, and humans have about 200 mutations/generation (Evolution 3rd Edition, Ridley and Evolutionary Biology 3rd Edition, Futuyma). Some diseases mutate frequently enough that every replication event experiences the likelihood that the disease will have changed. Although humans have a much higher mutation rate than diseases (such as viruses and bacteria), the generation span of a human is much longer than that of most diseases. The generation lifespan on a human is on the order of 15 - 30 years, while diseases typically have generation lifespans on the order of seconds to minutes. Per unit time diseases (e.g. viruses and bacteria) can evolve much more rapidly, and yet large complex organisms are able to survive as they have strategies which allow them to combat these adaptations. Despite the rate at which diseases are capable of evolving, they do not always win. Influenzavirus has the potential of being fatal but in most cases it is not considered life threatening.

Large complex organisms have multiple methods for allowing them to survive in an environment where diseases can rapidly evolve. Entities with smaller genomes have effectively less space in which to maintain a set of strategies which they can use to exploit their environment, while larger more complex organisms have more space in which they can record their survival strategies. Some bacteria use enzymes to protect against viral infections. Eukaryotes employ even more defenses against infection, while entities like vertebrates have evolved immune systems which are capable of responding to infection by disease. One segment of the Human genome, the Major Histocompatibility Complex (MHC) contains approximately 3.6 million base pairs or 140 genes which control a portion of the human immunological system. As of October 2004, the Immunogenetic Related Information Source (IRIS) database estimates the percentage of the human genome that controls the human immune system is approximately 7%, or 1562 genes. Although the percentage of the human genome related to the human immune system seems small, it is important to consider that a significant portion of the human genome is inactive. It is estimated that 25% of the genome is attributed to diseases which have inserted their genetic code into our genome and are now inactive, while other sections contain pseudogenes which are no inactive version of ancient genes. The percentage of the human active genome which relates to the immune system could be substantially higher than currently theorized. The cost of surviving in an evolutionary arms race can be high, as significant resources are required to defend an organism from infection by diseases and parasites.

Recently researchers, such as Banerjee in An Immune System Inspired Approach to Automated Program Verification, have looked at applying some of the methods that the immune system uses for protecting itself from disease by investigating an Automated Immune System (AIS) which can be implemented in information systems.

Implementing an immune system to handle rapidly evolving threats does not eradicate the threat. Immune systems will act as a selection pressure that will cause only those diseases which are capable of adapting to survive. Some adaptations can include methods for remaining undetected by the immune system, while others can include methods for exploiting the immune system and subverting it for its own use. In essence, these systems represent another vector in which disease can exploit a host. Human Immunodeficiency Virus (HIV) actively exploits the immune system; even at the cost of its own reproductive fitness to remain active in the host to survive when anti-HIV drugs are administered. Similarly with anti-malware products, flaws in these systems have allowed malware to exist and even spread in the form of computer worms. Malicious code routinely attempts to disable anti-virus before downloading and installing malicious components. In order to remain undetected, some malware will re-enable the anti-virus products to prevent the user from noticing anything conspicuous. Anti-virus software is complex enough that it has its own vulnerabilities which may be exploited by malware. In 2006, Symantec Anti-virus had a vulnerability (CVE-2006-2630) which allowed for a privilege escalation that was exploited by the W32.Rinbot.L worm.

Simply reducing the response time will not eradicate the threat. It will provide an advantage but it will not solve the problem. In order to respond to diseases which are able to quickly adapt to host evolutionary responses, large complex organisms have had to evolve complex responses that do not rely on a single strategy to ensure their survival. The cost of ensuring survival in an evolutionary arms race can be high, as numerous strategies need to be available to counter act the threat of disease and parasites.