DIMACS Working Group on Analogies Between Computer Viruses and Immune Systems and Biological Viruses and Immune Systems

June 10 - 14, 2002
DIMACS Center, CoRE Building, Rutgers University

Lora Billings, Montclair State University, billingsl@mail.montclair.edu
Stephanie Forrest, University of New Mexico, forrest@cs.unm.edu
Alun Lloyd, Institute for Advanced Study, alun@alunlloyd.com
Ira Schwartz, Naval Research Laboratory, schwartz@nlschaos.nrl.navy.mil
Presented under the auspices of the Special Focus on Computational and Mathematical Epidemiology

Co-sponsored by DIMACS and the Office of Naval Research (ONR).



The Benefits of a Notification Process in Addressing the Worsening
   Computer Virus Problem: Results of a Survey and a Simulation Model
(Joint work with M. O'Leary, R.A. Gove, S. Azadegan, and M.C. Schneider)

Joan Aron
Science Communication Studies and Johns Hopkins School of Public Health

Computer viruses present an increasing risk to the integrity of
information systems and the functions of a modern business
enterprise. Systematic study of this problem can yield better
indicators of the impact of computer viruses as well as a better
understanding of strategies to reduce that impact.

We conducted a Computer Virus Epidemiology Survey (CVES) on the World
Wide Web to examine indicators of the impact of computer viruses. A
major finding from the CVES is that multiple indicators of the impact
of computer viruses reveal a problem growing more severe that affects
large, as well as small, organizations. Another important finding is
that viruses not detected despite regular updating of antiviral
software caused only about 15% to 21% of virus problems reported in
workgroups using antiviral software. The possible reasons for failure
to detect include improper configuration of software and the inability
of all known anti-virus detectors to detect. A related implication is
that a substantial amount of damage due to viruses could probably have
been prevented by regular updating of antiviral software.

We also used the CVES in the development of a simulation model for the
spread of computer viruses in workgroups in order to analyze the
effect of a notification process on control. Our major finding is that
the process of notification, whether by human behaviour or by
technology, substantially reduces the impact of computer viruses in
workgroups. For example, if a workgroup has a period of vulnerability
when only 80% of its workstations are effectively using antiviral
software, then even a 50% probability of notification of a detected
virus substantially reduces the burden. An added benefit of
maintaining an environment with high effective antiviral software
usage and high levels of notification is that greater rates of
communication events that can potentially transmit computer viruses
within the workgroup actually reduce the impact of computer viruses in
the workgroup. Anecdotal observations also indicate that the process
of notification is significant in controlling the spread of new
viruses not yet detectable by software, although the process of
notification from law enforcement authorities to workgroups was not in
the simulation model.

More formally, the reduced impact of computer viruses in a workgroup
due to a greater rate of communication events that can potentially
transmit computer viruses corresponds to a situation when a computer
virus introduced into the workgroup produces, on average, less than
one copy in the workgroup. This threshold corresponds to the basic
reproduction ratio in epidemiology that describes the spread of
infectious disease.

2. Stochastic Modeling and Chaotic Epidemic Outbreaks Lora Billings Montclair State University Many diseases that occur in large populations tend to have oscillatory behavior, where the amplitudes of the number of cases appear to vary randomly. Examples are malaria, measles, influenza, and pertussis, just to name a few. These diseases are influenced by external environments, such as climate, as well as social factors, such as opening and closing of schools. In contrast, most deterministic population models predict regular, or periodic behavior. This talk will identify a global mechanism in a class of population models that induces chaos by stochastic perturbations, or population noise, where chaos does not naturally occur. Through a combination of computational and analytic techniques, this talk will present the generic setting of when this bifurcation is possible, identify the transport region that facilitates it, and, if time, suggest possible vaccination strategies to control and prevent future outbreaks.
3. Double Trouble: Attack of Two or More Separate Viral Species Erik Bollt Clarkson University Most popular models of disease infection, and all of the work that we have seen adapted for computer virus modeling, accounts for just one infection type. This is reasonable in the limit that the number of viral types is small relative to the life cycle of an infection. On the other hand, in an environment frought with many possible infections, health modeling of an individual must account for multiply staged infections and recovering. We discuss such life-cycles of an individual computer's health. Then we discuss that such individual components can be freely put into various network topology models, such as all-all, chains, scale-free, small-world, or stars. Control of information and infection flow will be discussed in this setting.
4. A Computational Model of RNA Virus Evolution Donald Burke Johns Hopkins School of Public Health RNA viruses (biological viruses in which the genome is composed of RNA, ribonucleic acid, rather than DNA, deoxyribonucleic acid) are important pathogens of man which as a group have high mutation rates and a proven propensity for rapid evolution, emergence, and pandemic spread. We developed a computational model of biological RNA virus evolution based on a genetic algorithm, an evolutionary computation method commonly used in artificial intelligence and machine learning. In a typical model run of our computational model, a population of code-strings evolves through iterative generations of modification, replication, and selection. Novel biologically-inspired features of our computational model include use of code-string genomes composed of nucleotides, triplet codons, open reading frames, and non-coding inter-genic regions; an artificial genetic code in which codons specify letters of the Roman alphabet rather than amino acids; genome modifications that are based on point mutations, random (non-homologous) recombination, and string-string homology-based recombination; variable length genomes; and phenotypes based on Roman letter sequences, with fitness defined by correct spelling of target English words (rather than protein conformations). We report that, just as in biological RNA virus evolution, the optimal mutation rate for the code-strings in our computational model is approximately 1/L (where L = string length). Interestingly, at sub-optimal high mutation rates (>1/L), mean code-strings are seen to lengthen as they accumulate multiple copies of pseudogenes. These preliminary results suggest a possible generalization: in evolving code-string systems (biological and computational), code-strings evolve to a length that is in large measure defined by the replication error rate.
5. Can Viruses Be Halted in a Scale-free Network? Zoltan Deszo University of Notre Dame The vanishing epidemic threshold for viruses spreading on scale-free networks indicate that traditional methods, aiming to decrease a virus' spreading rate cannot succeed in eradicating an epidemic. We demonstrate that policies that discriminate between the nodes, curing mostly the highly connected nodes, can restore a finite epidemic threshold and potentially eradicate a virus. We find that the more biased a policy is towards the hubs, the more chance it has to bring the epidemic threshold above the virus' spreading rate. Furthermore, such biased policies are more cost effective, requiring less cures to eradicate the virus.
6. A Vision of an Adaptive Artificial Immune System Stephanie Forrest University of New Mexico Natural immune systems are sophisticated information processors. They learn to recognize relevant patterns, they remember patterns that have been seen previously, they use combinatorics to construct pattern detectors efficiently, and they use diversity to promote robustness. Further, the individual cells and molecules that comprise the immune system are highly distributed, encoding and controlling the system in parallel with no central control mechanism. The talk will describe recent progress on several related projects which are incorporating principles and mechanisms from immunology into computer security. It will emphasize recent work on network-based intrusion detection in which normal behavior (self) is characterized using TCP/IP packets. Several immune-inspired mechanisms are employed to create a distributed and robust approach to network security.
7. Epidemiological Theory Alun Lloyd Institute for Advanced Study I shall give a brief overview of relevant epidemiological theory. Much attention has been given to threshold behavior in epidemic settings, leading to the key concept of the basic reproductive number (R_0). In simple situations, R_0 defines a threshold conditon which determines both invasion and persistence properties of diseases, together with corresponding critical vaccination proportions. Beyond the basic model, a great deal of work has focussed on the impact of heterogeneity in disease transmission, particularly with the setting of sexually transmitted diseases, such as HIV. I shall review some of these studies and highlight their links to recent discussion of the transmission dynamics of computer viruses and their prevention.
8. Computer Viruses and Techniques to Defend Against Them Rafail Ostrovsky Telcordia Technologies In this talk we will survey many cryptographic tools of dealing with computer viruses and malicious attacks.
9. Bull's Eye Prediction Theory for Controlling Large Epidemic Outbreaks Before They Occur Ira Schwartz Naval Research Laboratory Population models are dynamical systems which capture all ranges of behavior, from periodic to chaotic time series. The SEIR model is a commonly used base model that predicts epidemic outbreaks in many diseases. Our work identifies a global mechanism that induces chaos by stochastic perturbations, or population noise, where it does not naturally occur. To refine the possibility of epidemic control, we have analyzed the stochastic transport between large and small outbreaks. We have identified a precursor to large outbreaks and tested various vaccination strategies using that information to remove the large outbreaks before they occur. Both successes and failures will be presented with the hope that new ideas may be created in duscussion.
10. The Time-evolution of Small Populations H. G. Solari University of Buenos Aires A few hundred rabbits share a patch of land, less than a hundred share the same warren. They are not sane, the virus of the mixomatosis has taken part of the population. How will the population evolve? Will the illness become endemic? Which strain of virus will be the prevalent one? The problem has been posed for about 50 years, the standard (deterministic) models give clear answers to these questions, but Nature does not behaves according to them. What is wrong with our models? At a can-making factory the manager goes berserk! Once again the process is out of control and one complete roll of steel will have to be re-processed. Why our noisy-deterministic models cannot account for this situation? Why we have been unable to solve this problem so far? We will discuss these and related problems of small populations where stochasticity is not just a correction to the deterministic dynamics but a fundamental element of the dynamics.
11. Epidemic Outbreaks and Immunization in Complex Heterogeneous Networks Yamir Moreno Vega Abdus Salam International Centre for Theoretical Physics, Trieste Complex networks such as the sexual partnership web or the Internet show a high degree of redundancy and heterogeneity in their connectivity properties. This peculiar connectivity provides an ideal environment for the spreading of infective agents. Here, we present a detailed analytical and numerical analysis for the spreading of infections with and without acquired immunity in complex population networks. We show that the large connectivity fluctuations usually found in these networks strengthen considerably the incidence of epidemic outbreaks. In particular, we argue the lack of an epidemic threshold and the existence of a finite fraction of infected individuals in scale-free networks. Besides, we analyze several immunization strategies and show that the random uniform immunization of individuals does not lead to the eradication of infections in all complex networks. Successful immunization strategies can be developed only by targeted immunization schemes that sharply lower the network's vulnerability to epidemic attacks. The understanding of epidemic outbreaks in complex networks might deliver new insights in the spread of information and diseases in biological and technological networks that often appear to be characterized by complex heterogeneous architectures.
12. Computer Viruses: A View from the Trenches Matt Williamson HP Labs, Bristol (UK) This talk will provide some industrial context to the problem of computer viruses, looking at the overall cost and impact of them, and current techniques for stopping and cleaning up after them. I will also discuss a technique for fighting the Code Red and Nimda viruses that we have developed at HP. The approach exploits the same vulnerability that the virus uses for propagation to stop the offending program and prepare the computer for cleanup. By eliminating the requirement of physically locating the machine before it can be "treated", this technique greatly speeds up the process of both fighting and cleaning up after the virus.

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on June 4, 2002.