Biological Systems For Intrusion Detection

Biological Programming Models for IntrusionTolerant Systems Workshop on Statistical and Machine Learning Techniques in Computer Intrusion Detection George Mason University 24 September 2003

David Evans University of Virginia, Department of Computer Science

Learning from Biology • Process – Genetic algorithms

• Product – Immune systems – Programs

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

2

(Really) Brief History of Computing 1950

1960

1970

1980

1990 2000-

Monolithic Computers in guarded, airconditioned rooms

Fixed Networks of PCs

Billions of small, cheap unreliable devices

No interactions

Data interactions with other computers, but most computing done locally

Computing organized through local interactions

Narrow interface to operator (punch cards, teletype), no interface to environment

Rich interface to user, limited interface to environment

Fundamentally integrated into physical environment

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

3

Challenges and Opportunities • Embedded in physical environment – Challenges: unpredictable, energy-limited – Opportunities: physical laws, continuous

• Scale – Challenges: billions of independent components – Opportunities: redundant to failures

• Demands new programming approaches and reasoning techniques ID03 - 24 Sept 2003

swarm.cs.virginia.edu

4

Swarm Computing: Long-Range Goal

Cement 10 TFlop

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

5

Existing Systems • Trillions of unreliable, inexpensive components • No significant performance degradation when billions fail • Small programs produce complex behavior ID03 - 24 Sept 2003

• ~70 Trillion Cells in adult human • ~ 3 Billion of your cells have died since I started talking • Program (3B nucleotides) is shorter than Windows XP, difference between 2 humans on 1 floppy

swarm.cs.virginia.edu

6

Swarm Programming Behavioral Description Environment Model Device Model

Behavior and primitives defined over groups

Swarm Program Generator

Device Units

Device Programs

Programmed Device Units

Primitives Library ID03 - 24 Sept 2003

swarm.cs.virginia.edu

7

Observations About Nature’s Programs • Responsive – Aware of state of self and surroundings

• Localized – Communication through chemical diffusion

• Redundant – Millions of cells can die without compromising function

• Diverse – Species survive because of diversity of individuals

• Remarkably Expressive • Human genome ~250MB ID03 - 24 Sept 2003

swarm.cs.virginia.edu

8

Foundations

Current Research

• Amorphous Computing [Abelson, Nagpal, Sussman] Cellular Automata • Paintable Computing von Neumann [1940s] [Butera] Conway’s Game of Life [1970] • Embryonics [Mange, Wolfram [2002] Sipper] Reaction-Diffusion Turing [1952] • Ant Colony Optimization, Swarm Intelligence ID03 - 24 Sept 2003

swarm.cs.virginia.edu

9

Simplified Cell Model • Awareness of Environment – Sense chemicals on cell walls – Sense chemicals in environment

• Cell Actions – Cell Division (asymmetric) – State Change – Communicate: emit (directional, neighboring walls), diffuse (omnidirectional)

• Simple physical forces – Two cells cannot overlap in space ID03 - 24 Sept 2003

swarm.cs.virginia.edu

10

Biological Complexity

Molecular map of colon cancer cell from http://www.gnsbiotech.com/applications.shtml ID03 - 24 Sept 2003

swarm.cs.virginia.edu

11

Simple Sphere Program center alive < 1

state center { color 1 0 0 emits (alive, 1) diffuses (radius, 10) transitions alive from dir < 1 -> (center, body) in dir; }

state body { color 0 0 1 emits (alive, 1) transitions alive from dir < 1 & radius > 0 alive < 1 & radius > 0 -> (body, body) in dir; }

body

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

12

state center { color 1 0 0 emits (alive, 1) diffuses (radius, 10) transitions alive from dir < 1 -> (center, body) in dir; } state body { color 0 0 1 emits (alive, 1) transitions alive from dir < 1 & radius > 0 -> (body, body) in dir; }

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

13

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

14

Robustness of Sphere Program

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

15

Intrusion Tolerance? • Robust to random failures – As long as source cell survives, the sphere will re-generate – Sphere has > 10000 cells

• Not robust to attacks – Destroy the center cell, sphere will not regrow

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

16

state center { color 1 0 0 emits (alive, 1) diffuses (radius, 10) transitions (alive from dir < 1) -> (center, core) in dir; }

Example

state core { color 0 1 0 emits (alive, 1) transitions (alive from dir < 1) & (radius > 2) -> (core, body) in dir; (radius < 2) & (alive from dir < 1) -> (core, center) in dir; } state body { color 1 1 0 emits (alive, 1) transitions (alive from dir < 1) & (radius > 1) -> (body, body) in dir; } ID03 - 24 Sept 2003

swarm.cs.virginia.edu

17

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

18

state corner { color red emits (length, 8), (alive, 1) transitions (alive < 1) from dir -> (corner, segment) in dir; -> (corner); }

Network Mesh

state segment { color cyan emits (alive, 1) forwards (length - 1) transitions (length > 1.5) from dir & (alive < 0.5) from opposite (dir) -> (segment, segment) in opposite (dir); (length > 0.1) -> (corner); (length < 0.1) -> die; } ID03 - 24 Sept 2003

swarm.cs.virginia.edu

19

Composing Primitives • Cells can follow multiple programs simultaneously (vector of independent states) • Cells can combine primitives through shared chemicals – Chemicals secreted by one primitive can induce changes in other primitives

• Goals: – Predict properties of composition based on properties of primitives – Diversity of primitive implementations provides protection from directed attacks ID03 - 24 Sept 2003

swarm.cs.virginia.edu

20

Mickey Mouse Program • 20 states • 50 transition rules • Starts from one cell, combines lines, spheres Real Mouse Program • 3B base pairs • 98% same as human DNA • Starts from one cell, combines complex proteins

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

21

Towards Real Systems • Cells – Sensor Devices, MEMS, Internet Nodes

• Division – Processes – Find new hosts

• Communication – Point-to-point emissions – Wireless multicast (can be multi-hop) diffusions

• Example: distributed file system running on simulated wireless nodes ID03 - 24 Sept 2003

swarm.cs.virginia.edu

22

Distributed Wireless File Service File Distribution and Update

Publishe r

inhibit

publish

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

23

Distributed Wireless File Service File Distribution and Update

replicate ID03 - 24 Sept 2003

swarm.cs.virginia.edu

24

Robustness to Node Failures

80% of requests satisfied ID03 - 24 Sept 2003

swarm.cs.virginia.edu

25

Summary • Trillions of creatures have died to evolve the extremely robust programs that survive today • Robustness and scalability require: – Decentralization – Awareness of surroundings – Diversity

• Swarm Programming – Develop high level behaviors from local interactions – Use communication through environment to coordinate locally – Produce complex behaviors by combining primitives defined over groups ID03 - 24 Sept 2003

swarm.cs.virginia.edu

26

Acknowledgements Sponsor: National Science Foundation Contributors: Lance Davidson (UVa Biology) Selvin George Salvatore Guarnieri Steven Marchette Qi Wang Brian Zhang

http://swarm.cs.virginia.edu ID03 - 24 Sept 2003

swarm.cs.virginia.edu

27

Biological Programming Models for IntrusionTolerant Systems Workshop on Statistical and Machine Learning Techniques in Computer Intrusion Detection George Mason University 24ID03September 2003 - 24 Sept 2003

David Evans University of Virginia, Department of Computer Science

swarm.cs.virginia.edu

1

Learning from Biology • Process – Genetic algorithms

• Product – Immune systems – Programs

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

2

(Really) Brief History of Computing 1950

1960

1970

1980

1990 2000-

Monolithic Computers in guarded, airconditioned rooms

Fixed Networks of PCs

Billions of small, cheap unreliable devices

No interactions

Data interactions with other computers, but most computing done locally

Computing organized through local interactions

Narrow interface to operator (punch cards, teletype), no interface to environment

Rich interface to user, limited interface to environment

Fundamentally integrated into physical environment

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

3

Challenges and Opportunities • Embedded in physical environment – Challenges: unpredictable, energy-limited – Opportunities: physical laws, continuous

• Scale – Challenges: billions of independent components – Opportunities: redundant to failures

• Demands new programming approaches and reasoning techniques ID03 - 24 Sept 2003

swarm.cs.virginia.edu

4

Swarm Computing: Long-Range Goal

Cement 10 TFlop

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

5

Existing Systems • Trillions of unreliable, inexpensive components • No significant performance degradation when billions fail • Small programs produce complex behavior ID03 - 24 Sept 2003

• ~70 Trillion Cells in adult human • ~ 3 Billion of your cells have died since I started talking • Program (3B nucleotides) is shorter than Windows XP, difference between 2 humans on 1 floppy

swarm.cs.virginia.edu

6

Swarm Programming Behavioral Description Environment Model Device Model

Behavior and primitives defined over groups

Swarm Program Generator

Device Units

Device Programs

Programmed Device Units

Primitives Library ID03 - 24 Sept 2003

swarm.cs.virginia.edu

7

Observations About Nature’s Programs • Responsive – Aware of state of self and surroundings

• Localized – Communication through chemical diffusion

• Redundant – Millions of cells can die without compromising function

• Diverse – Species survive because of diversity of individuals

• Remarkably Expressive • Human genome ~250MB ID03 - 24 Sept 2003

swarm.cs.virginia.edu

8

Foundations

Current Research

• Amorphous Computing [Abelson, Nagpal, Sussman] Cellular Automata • Paintable Computing von Neumann [1940s] [Butera] Conway’s Game of Life [1970] • Embryonics [Mange, Wolfram [2002] Sipper] Reaction-Diffusion Turing [1952] • Ant Colony Optimization, Swarm Intelligence ID03 - 24 Sept 2003

swarm.cs.virginia.edu

9

Simplified Cell Model • Awareness of Environment – Sense chemicals on cell walls – Sense chemicals in environment

• Cell Actions – Cell Division (asymmetric) – State Change – Communicate: emit (directional, neighboring walls), diffuse (omnidirectional)

• Simple physical forces – Two cells cannot overlap in space ID03 - 24 Sept 2003

swarm.cs.virginia.edu

10

Biological Complexity

Molecular map of colon cancer cell from http://www.gnsbiotech.com/applications.shtml ID03 - 24 Sept 2003

swarm.cs.virginia.edu

11

Simple Sphere Program center alive < 1

state center { color 1 0 0 emits (alive, 1) diffuses (radius, 10) transitions alive from dir < 1 -> (center, body) in dir; }

state body { color 0 0 1 emits (alive, 1) transitions alive from dir < 1 & radius > 0 alive < 1 & radius > 0 -> (body, body) in dir; }

body

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

12

state center { color 1 0 0 emits (alive, 1) diffuses (radius, 10) transitions alive from dir < 1 -> (center, body) in dir; } state body { color 0 0 1 emits (alive, 1) transitions alive from dir < 1 & radius > 0 -> (body, body) in dir; }

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

13

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

14

Robustness of Sphere Program

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

15

Intrusion Tolerance? • Robust to random failures – As long as source cell survives, the sphere will re-generate – Sphere has > 10000 cells

• Not robust to attacks – Destroy the center cell, sphere will not regrow

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

16

state center { color 1 0 0 emits (alive, 1) diffuses (radius, 10) transitions (alive from dir < 1) -> (center, core) in dir; }

Example

state core { color 0 1 0 emits (alive, 1) transitions (alive from dir < 1) & (radius > 2) -> (core, body) in dir; (radius < 2) & (alive from dir < 1) -> (core, center) in dir; } state body { color 1 1 0 emits (alive, 1) transitions (alive from dir < 1) & (radius > 1) -> (body, body) in dir; } ID03 - 24 Sept 2003

swarm.cs.virginia.edu

17

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

18

state corner { color red emits (length, 8), (alive, 1) transitions (alive < 1) from dir -> (corner, segment) in dir; -> (corner); }

Network Mesh

state segment { color cyan emits (alive, 1) forwards (length - 1) transitions (length > 1.5) from dir & (alive < 0.5) from opposite (dir) -> (segment, segment) in opposite (dir); (length > 0.1) -> (corner); (length < 0.1) -> die; } ID03 - 24 Sept 2003

swarm.cs.virginia.edu

19

Composing Primitives • Cells can follow multiple programs simultaneously (vector of independent states) • Cells can combine primitives through shared chemicals – Chemicals secreted by one primitive can induce changes in other primitives

• Goals: – Predict properties of composition based on properties of primitives – Diversity of primitive implementations provides protection from directed attacks ID03 - 24 Sept 2003

swarm.cs.virginia.edu

20

Mickey Mouse Program • 20 states • 50 transition rules • Starts from one cell, combines lines, spheres Real Mouse Program • 3B base pairs • 98% same as human DNA • Starts from one cell, combines complex proteins

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

21

Towards Real Systems • Cells – Sensor Devices, MEMS, Internet Nodes

• Division – Processes – Find new hosts

• Communication – Point-to-point emissions – Wireless multicast (can be multi-hop) diffusions

• Example: distributed file system running on simulated wireless nodes ID03 - 24 Sept 2003

swarm.cs.virginia.edu

22

Distributed Wireless File Service File Distribution and Update

Publishe r

inhibit

publish

ID03 - 24 Sept 2003

swarm.cs.virginia.edu

23

Distributed Wireless File Service File Distribution and Update

replicate ID03 - 24 Sept 2003

swarm.cs.virginia.edu

24

Robustness to Node Failures

80% of requests satisfied ID03 - 24 Sept 2003

swarm.cs.virginia.edu

25

Summary • Trillions of creatures have died to evolve the extremely robust programs that survive today • Robustness and scalability require: – Decentralization – Awareness of surroundings – Diversity

• Swarm Programming – Develop high level behaviors from local interactions – Use communication through environment to coordinate locally – Produce complex behaviors by combining primitives defined over groups ID03 - 24 Sept 2003

swarm.cs.virginia.edu

26

Acknowledgements Sponsor: National Science Foundation Contributors: Lance Davidson (UVa Biology) Selvin George Salvatore Guarnieri Steven Marchette Qi Wang Brian Zhang

http://swarm.cs.virginia.edu ID03 - 24 Sept 2003

swarm.cs.virginia.edu

27