Combining Genetic Algorithms & Simula

Search for Failure Scenarios in System M

Kevin Mills*, Chris Dabrowski, Jim Filliben and Sandy 

(work done at NIST prior to US Government Shutd

Cyber Security Technical Center Distinguished Speak

October 16, 2013

*Today speaking speaking in his capacity capacity as a private private citizen citizen
Outline

• Motivation & Context• Method• Case Study

– Koala IaaS Cloud Simulator– Searching for Failure Failure Scenarios Scenarios– Evaluating Method

• Conclusions & Future Work

Oct 16, 2013 Mitre Distinguished Lecture 
GROWING GLOBAL DEPENDENCE ON COMPLEX INFO. S

Oct 16, 2013 Mitre Distinguished Lecture 
WE CAN BUILD & DEPLOY SUCH SYSTEMS, BUT CAN WE U

PREDICT & CONTROL THEM?

Oct 16, 2013 Mitre Distinguished Lecture 
PAST NIST RESEARCH FROM 2006‐2011

How can we understand understand the influence influence of distributed distributed 

algorithms on global system behavior and user expe

 Mills, Filliben, Cho, Schwartz and Genin, Study of Proposed

What 

Mills, Filliben, Cho, Schwartz and Genin, Study of ProposedInternet Congestion Control Mechanisms, NIST SP 500‐282 (2010).

 Mills and Filliben, "Comparison of Two Dimension‐Reduction

Methods for Network Simulation Models", Journal of NIST

Research Research 116‐5, 771‐783 (2011). (2011).

 Mills, Schwartz and Yuan, "How to Model a TCP/IP Network using

only 20 Parameters", Proceedings of the Winter Simulation

Conference (2010).

 Mills, Filliben, Cho and Schwartz, "Predicting Macroscopic

Under w

Mills, Filliben, Cho and Schwartz, Predicting Macroscopic

Dynamics in Large Distributed Systems", Proceedings of ASME

(2011).

 Mills, Filliben and Dabrowski, "An Efficient Sensitivity Analysis

Method for Large Cloud Simulations", Proceedings of the 4 Method th for Large Cloud Simulations , Proceedings of the 4International Cloud Computing Conference, IEEE (2011).

 Mills, Filliben and Dabrowski, "Comparing VM‐Placement

Algorithms for On‐Demand Clouds", Proceedings of IEEE

CloudCom, 91‐98 (2011).CloudCom, 91 98 (2011).

For more see: http://www.nist.gov/itl/antd/emergent_behavior.cfm http://www.nist.gov/i

At an 

Oct 16, 2013 Mitre Distinguished Lecture
How can we increase the reliability of complex informati

ONGOING NIST RESEARCH FROM 2012‐PRESEN

3⁄4 Research Goals: (1) develop and evaluate design‐time method

system engineers can use to detect existence and causes of co

regimes prior to system deployment and (2) develop and evalu

y p 

regimes prior to system deployment and (2) develop and evalutime methods that system managers can use to detect onset o

failure regimes in deployed systems, prior to collapse.

3⁄4 Recent R h esearch: i ii nvestigating d i es gn‐time meth do s –

a. Markov Chain Modeling + Cut‐Set Analysis + Perturbation

Analysis (e.g., Dabrowski, Hunt and Morrison, “Improving

the Efficiency of Markov Chain Analysis of Complex

Distributed Systems”, NIST IR 7744, 2010).

b. Anti‐Optimization (AO) + Genetic Algorithm (GA) – TODAY’S

PRESENTATION

3⁄4 O i ( ll hi t t th t ti ) i ti t 

http://www.nist.

3⁄4 Ongoing (well, on hiatus at the present time): investigate run

methods based on approaches that may provide early warning 

critical transitions in large systems (e.g., Scheffer et al., “Early‐warnin

critical transitions” NATURE 461 53‐59 2009)critical transitions , NATURE, 461, 53 59, 2009).

Oct 16, 2013 Mitre Distinguished Lecture
Method: Genetic Algorithm (GA) steers a populat

simulators to search for parameter comb

that lead to system failure

Principal Components Analysis,

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Selection based on

Anti Fitness

Recombination& Mutation

GENETIC ALGORITHM

Principal Components Analysis,Clustering, ...

& Mutation Anti-Fitness

Anti-Fitness Reports

MODEL SIMULATORS

List of parameters

and for each

parameter a MIN,MAX andprecision.

Model Parameter 

Specifications Parallel Executio

Model Simulator

Population of Model Parameterizations

Oct 16, 2013 Mitre Distinguished Lecture 
Case Study Topics

1. Koala Simulator2. Koala Parameters & Representation as Chromo

3. Genetic Algorithm

4. Population of Koala Simulators5. Dynamics of GA Search6. Analysis Method7. Results from Four GA Searches

Oct 16, 2013 Mitre Distinguished Lecture 
Topic 1: Koala Simulator

GENETIC ALGORITHM

Principal Components Analysis,Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Selection based on

Anti-Fitness

Recombination& Mutation

GENETIC ALGORITHM

Anti-Fitness Reports

MODEL SIMULATORS

List of parameters

and for each

parameter a MIN,

Model Parameter 

Specifications Parallel Execution 

Model Simulators Population of Model Parameterizations

p ,MAX andprecision.

Parameterizations

In our case study we defined anti‐fitness as the proportion of arriving use

Oct 16, 2013 Mitre Distinguished Lecture
Schematic of Koala IaaS Cloud Simu

Demand and supply layers modeled after Amazon EC2

DEMAND LAYER

User 

#1

User 

#2

User 

#3

User 

#4

User 

#5

User 

#6

User 

#n-3

User 

#n-2

User 

#n-1

(1)

Demand and supply layers modeled after Amazon EC2

Internal structure modeled after Eucalyptus v1.6

 INTERNET (4)

RESOURCE 

ALLOCATION

CLOUD CONTROLLER

Cluster TTCluster 

Cluster 

(4) (3) (4) 

LAYER Cluster Controller #1 Cluster Controller #c

NODE CONTROLLER #kNODE RESOURCES NODE CONTROLLER #k-1

NODE CONTROLLER #pNODE RESOURCES NODE CONTROLLER #p-1

NODE CONTROLLER #qNODE RESOURCES NODE CONTROLLER #q-1

INTRANET

INTRANET

Controller #c- 

m

(2)

SUPPLY 

LAYER

VM 

BEHAVIOR

NODE RESOURCES NODE CONTROLLER #k-2

NODE RESOURCES

NODE CONTROLLER #3NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

NODE RESOURCES NODE CONTROLLER #p-2

NODE RESOURCES

NODE CONTROLLER #3NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

NODE RESOURCES NODE CONTROLLER #q-2

NODE RESOURCES

NODE CONTROLLER #3NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

II

VM1 VMs VM1 VMs VM1 VMs (5)BEHAVIOR

 LAYER

VMs

Shown forOne Node Only

Shown forOne Node Only

VMs

ShoOne 

VM1VM1VM1VM1 VM1 VM1VM1VM1VM1 VM1 VM1VM1VM1VM1 VM1 ( )

Oct 16, 2013 Mitre Distinguished Lecture 
Topic 2: Koala Parameters & GA Represe

as Chromosomes (i.e., bit strings

Principal Components Analysis,Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

as Chromosomes (i.e., bit strings

Selection based on

Anti-Fitness

Recombination& Mutation

GENETIC ALGORITHM

Anti-Fitness Reports

MODEL SIMULATORS

List of parametersand for each

Model Parameter 

Specifications Parallel Executio

Population of Model

and for eachparameter a MIN,MAX andprecision.

Specifications Parallel Executio

Model Simulator

Population of Model Parameterizations

Oct 16, 2013 Mitre Distinguished Lecture 
Summary of Koala Parameters to Sea

Parameter Category

Test Case – Can GA find VM Leakage due to message loss and lack of orph

Failure scenario found manually by accident and described in C. Dabrowski and K. Mills, "VM Leakage and O

Open‐Source Clouds", Proceedings of IEEE CloudCom 2011, Nov. 29‐Dec. 1, Athens, Greece, pp. 554‐559.

ModelElement

Parameter Category

Behavior Structure Asymmetry Failure 

User 28 2 4 0 

Cloud Controller 21 4 5 0 Cluster Controllers 11 5 3 0 

Nodes 6 0 0 14 

Intra‐Net/Inter‐Net 4 11 2 9 Totals 70 22 14 23 

Average # values per parameter is about 6, so search space is ≈ 6 Average 

# values per parameter is about 6, so search space is 6

i.e.,  ≈ 10100 scenarios are possible

 adapted 125‐parameter Koala IaaS simulator to be GA controlla

 added 4 Koala parameters to turn on/off logic to control ( ) a cre

(b) termination orphans, (c) relocation orphans and (d) administ

Oct 16, 2013 Mitre Distinguished Lecture 
Sample Chromosome Specificati

Genetic Algorithm ComChromosome Map (Si

Koala ParameterSpace (Size = 10100)

PARAMETER MIN MAX PRECISION #VALUES LOW_BIT HIGH_BIT P_CreateOrphanControlOn 0 1 1 2 36 36 P_TerminationOrphanControlOn 0 1 1 2 58 58 P_RelocationOrphanControlOn 0 1 1 2 11 11 P_AdministratorActive 0 1 1 2 330 330 

Space (Size 10 ) Chromosome Map (Si

P_clusterAllocationAlgorithm 0 5 1 6 31 33 P_describeResourcesInterval 600 3600 600 6 81 83 P_nodeResponseTimeout 30 90 30 3 210 211 P_TerminatedInstancesBackOffThreshold 3 6 1 4 56 57 P_TerminationBackOffInterval 180 360 60 4 88 89 P TerminationRetryPeriod P_TerminationRetryPeriod 600 1200 300 3 316 317 P_StaleShadowAllocationPurgeInterval 600 3600 600 6 242 244 P_cloudAllocationCriteria 0 3 1 4 321 322 P_clusterShadowPurgeLimit 1 21 5 5 290 292 P_instancePurgeDelay 180 600 60 8 98 100 P_clusterEvaluationResponseTimeout 60 120 30 3 14 15 P_MaxPendingRequests 1 10 1 10 72 75 P_CloudTerminatedInstancesBackOffThreshold 3 6 1 4 169 170 P_CloudTerminationBackOffInterval 180 360 60 4 40 41 P_CloudTerminationRetryPeriod 3600 10800 1800 5 297 299 P_ClusterShutdownGracePeriod 86400 2.59E+05 43200 5 147 149 P_RequestEvaluatorTimeoutWaitProportion 0.1 0.4 0.1 4 145 146 P_RequestEvaluatorClusterMinimumResponse 0.6 0.9 0.1 3 269 270 P_MaxRelocationDuratonProportion 0.65 0.95 0.1 4 90 91 P_MaximumRelocateDescribeRetries 4 16 2 7 254 256 P_AverageCloudAdministratorAttentionLatency 28800 86400 14400 5 308 310 P_AverageCloudAdministratorShutdownDelay 300 900 300 3 45 46 P_avgTimeToClusterCommunicationCut 2.88E+06 2.88E+07 2.88E+06 10 217 220 

Oct 16, 2013 Mitre Distinguished Lecture 
Topic 3: Genetic Algorithm

Principal Components Analysis,Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Selection based on

Anti-Fitness

Recombination& Mutation

GENETIC ALGORITHM

Anti-Fitness Reports

MODEL SIMULATORS

List of parametersand for each

Model Parameter 

Specifications Parallel Executio

Population of Model

and for eachparameter a MIN,MAX andprecision.

Specifications Parallel Executio

Model Simulator

Population of Model Parameterizations

Oct 16, 2013 Mitre Distinguished Lecture 
Genetic Algorithm Flow Chart

REBOOT?

2

3

EVALUATE DONE?

1

4

MUTATE 

SEEDPOPULATION

7

RECOMBIN

Oct 16, 2013 Mitre Distinguished Lecture 
Topic 4: Population of Koala Simul

Principal Components Analysis,Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Selection based on

Anti-Fitness

Recombination& Mutation

GENETIC ALGORITHM

Anti-Fitness Reports

MODEL SIMULATORS

List of parameters

and for each

Model Parameter 

Specifications Parallel Execution 

S Population of Model

parameter a MIN,MAX andprecision.

p Model Simulators p Parameterizations

Oct 16, 2013 Mitre Distinguished Lecture 
Population of Koala Simulators Deployed o

Performance Computing Cluster

Oct 16, 2013 Mitre Distinguished Lecture 
Topic 5: Dynamics of GA Search

Principal Components Analysis,Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Selection based on

Anti-Fitness

Recombination& Mutation

GENETIC ALGORITHM

Anti-Fitness Reports

MODEL SIMULATORS

List of parameters

and for each

Model Parameter 

Specifications Parallel Execution 

S Population of Model

parameter a MIN,MAX andprecision.

p Model Simulators p Parameterizations

Oct 16, 2013 Mitre Distinguished Lecture 
One GA Search over 500 Genera

Generations 500Population Size 200 Individuals

GENETIC ALGORITHM CONTROL PARAMETERS

0.60.70.80.9 (a)Average Anti‐Fitn

Elite Per Generation 16 Individuals

Reboot After 200 Generations

Selection Method Stochastic Uniform Sampling

0.10.20.30.40.5

# Crossover Points 3Mutation Rate 0.001 < Adaptive < 0.01

0

0.1

0 100 200 300 

Generation

( ) M i A ti Fit Di d

0.2

0.25

0.3

(b) Standard Deviation i

0.78

0.8

0.820.84

(c) Maximum Anti‐Fitness Discovered

0

0.05

0.1

0.15

0.7

0.720.740.76

0 100 200 300 400 500

0 100 200 300 

Generation

Generation

Oct 16, 2013 Mitre Distinguished Lecture
Assessment of Search Conducted by 

(based on 105 scenarios i e 200 individuals x 500 generation

0.2

Frequency Distribution of Anti‐Fitness

(based on 10 scenarios, i.e., 200 individuals x 500 generation

0 1

0.150.05

0.1

0

5

10

15

20

25

30

35

40

45

50

55

60

65

70

75

80

85

90

95

100

Anti‐Fitness

• 84% of scenarios exhibit anti‐fitness ≥ 0.50

• Only 8% of scenarios are duplicate (equals elite‐selection percenta

• For Koala simulator, failure scenarios appear within first 100‐200 g

, pp

Oct 16, 2013 Mitre Distinguished Lecture
Topic 6: Analysis Method

Principal Components Analysis,Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Selection based on

Anti-Fitness

Recombination& Mutation

GENETIC ALGORITHM

Anti-Fitness Reports

MODEL SIMULATORS

List of parameters

and for each

Model Parameter 

Specifications Parallel Execution 

S Population of Model

parameter a MIN,MAX andprecision.

p Model Simulators p Parameterizations

Oct 16, 2013 Mitre Distinguished Lecture 
Differential Probability Analysi

Let C be the set of collected collected tuples, each containing containing a vector of param

param

value (PV) pairs and a corresponding anti‐fitness value, f

Segment C into high‐pass (H) and low‐pass (L) subsets, where:

H = {x c C x f > 0 70} and L = {x c C x f < 0 15} x > 0.70} and L = {x c C x fx < 0.15}

For each PV estimate the probability of occurrence in H and L:

P(PVixf > 0.70 =xPVi c Hx⁄xHx and P(PVixf > 0.15) = xPVi c 

Then compute the estimated differential probability:

D = P(PVixf > 0.70) – P(PVixf < 0.15)

Plot D for each PV pair

0.20.40.6

i = 684 Parameter‐Value Pairs

OutliersP(PVcontributing i|f>0.70)to ‐failure P(PVscenarios i|f<0.15)

PVs exerting little influence on success or failure

‐0.4‐0.2

0

0 100 200 300 400 500 600 700

D

PVi

PVs exerting little influence on success or failure

‐0.6 Outliers contributing to success scenarios

Oct 16, 2013 Mitre Distinguished Lecture 
Topic 7: Results from Four GA Sear

Principal Components Analysis,Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Selection based on

Anti-Fitness

Recombination& Mutation

GENETIC ALGORITHM

Anti-Fitness Reports

MODEL SIMULATORS

List of parameters

and for each

Model Parameter 

Specifications Parallel Execution 

S Population of Model

parameter a MIN,MAX andprecision.

p Model Simulators p Parameterizations

Oct 16, 2013 Mitre Distinguished Lecture 
Analysis of Results from GA Search 1 – 500 Gen

Seeking Known Failure Scenario – search duration 30 da

0.40.6 CreateOrphanControlOn = FALSE

AvgUserRequestTimeout = 30

AvgThinkTime = 900

0.2

NodesPerCluster = 200

UserRestPeriodMultiplier = 32

NodesPerCluster = 400

0

0 100 200 300 400 500 600 700

‐0.2‐0.4

CreateOrphanControlOn = TRUE

‐0.6 CreateOrphanControlOn TRUE

D (y‐axis) for 684 PV pairs (x‐axis) for first GA search–outlier PV pairs lab

Oct 16, 2013 Mitre Distinguished Lecture
Analysis of Results from GA Search 2 – 205 Gen

Seeking Previously Unknown Failure Scenarios – search duratio

0.40.5

AvgUserRequestTimeout = 30

AvgThinkTime = 900

0 20.3

UserRestPeriodMultiplier = 32 NumberofSitesReservedForCloud = 2

NodesPerCluster = 200

MilesPerRouterHop = 500

MaxPerHopDelay = 0.9

StdUserRequestTimeout = 30

0.10.2 StdUserRequestTimeout = 30 NodesPerCluster = 400

‐0.1

0

0 100 200 300 400 500 600 70

MilesPerRouterHop = 1500

‐0.3‐0.2

AvgUserRequestTimeout = 120

NumberofSitesReservedForCloud = 1

AvgThinkTime = 1500

MilesPerRouterHop 1500

D (y‐axis) for 677 PV pairs (x‐axis) for first GA search–outlier PV pairs lab

Oct 16, 2013 Mitre Distinguished Lecture
Analysis of Results from GA Search 3 – 209 Gen

Nudging up Some Parameter Ranges and Seeking Additional Failur

h d i 16 d

0.50.6 NodesPerCluster = 600 UserTypeArraySelector = 4

AvgThinkTime = 1200 AvgUserRequestTimeout = 90

SiteDistanceMultiplier = 7

Mi Sit C di t 0 U R P i dM l i li 32

search duration 16 days

0 30.40.5 MinSiteCoordinate = 0 UserRestPeriodMultiplier = 32

StdUserRequestTimeout = 30

MinReservationRetries = 2

AvgInterUserStartDelay = 30

MinIntrasiteDelay = 2x10‐8

MinClusters = 9

MaxSiteCoordinate = 16000 MaxIntrasiteDelay = 1.5x10‐5

0.20.3 MaxPerHopDelay = 0.9 y CloudSizeChangeFraction = 0.3 ClusterResponseTimeout = 12

MaxIntersiteLossRate = 10‐7

PlatformTypeArraySelector = 4 ProbabilityImageNotFound = 

0

0.1

0 100 200 300 400 500 600 700

‐0.2‐0.1

RandomizeMinMaxVMsRequested = TRUE

MinRestPeriods = 2

NodeResponseTimeout = 30

‐0.3 ChoosePlatformTypesRandomly = FALSE

RandomizeMinMaxVMsRequested = TRUE

D (y‐axis) for 680 PV pairs (x‐axis) for first GA search–outlier PV pairs lab

Oct 16, 2013 Mitre Distinguished Lecture
Potential Issue Regarding Estimate of P(PVixf > 0.15) = x

In scenarios 1‐3, xHx π 104, while xLx π 103To Increase |L|:

• use GA to search for success success scenarios scenarios• combine those tuples with tuples collected when searching fo

Conduct differential probability analysis on the combined tuple colleAs an example, we augmented GA search 3 with a 4th GA search looksuccess success scenarios scenarios, and combined combined the tuple collections collections from searches searches 

to yield |L| = 42253 scenarios and |H| = 14601

Next slide, shows the differential differential probability probability analysis analysis for the combined combined tuOct 16, 2013 Mitre Distinguished Lecture 
Analysis of Results from GA Search 4 – 209+205 G

Including additional PV pairs in L discovered by GA searching for suc

‐ search d i urat on 14 days

0.8 AvgUserRequestTimeout = 90 AvgThinkTime = 1200

SiteDistanceMultiplier = 7 UserRestPeriodMultiplier = 32 NodesPerCluster = 600 UserTypeArraySelector = 4

MinSiteCoordinate = 0 StdUserRequestTimeout = 30

0.40.6 MinSiteCoordinate 0 StdUserRequestTimeout 30 MaxSiteCoordinate = 16000 AvgInterUserStartDelay = 30

MinIntrasiteDelay = 2x10‐8 MinReservationRetries = 2

MinClusters = 9 RandomizeMinMaxVMsRequested = FA

AvgAdminDelay = 900 CloudSizeChangeFraction = 0.3

ClusterResponseTimeout = 120

0.2

‐0.2

0

0 100 200 300 400 500 600 

‐0.4

RandomizeMinMaxVMsRequested TRUE

NodeResponseTimeout = 30 MinRestPeriods = 2

ChoosePlatformTypesRandomly = FALSEMaxSiteCoordinate = 12000 AvgAdminDelay = 300

‐0.6

RandomizeMinMaxVMsRequested = TRUE

D (y‐axis) for 683 PV pairs (x‐axis) for first GA search–outlier PV pairs lab

Oct 16, 2013 Mitre Distinguished Lecture
Conclusions

SUMMARY:

• Defined a design‐time method, combing GA search with s

to seek failure failure scenarios scenarios in system models

• Applied the method in a case study, seeking (and finding) 

failure scenario in an existing cloud simulator

• Iterated Iterated search to reveal previously previously unknown unknown failure failure scen

scen

FINDINGS:

• GA searches explored predominantly non‐duplicative sce

high anti‐fitness

• Uncovered evidence that GA search can reveal insights ab

optimal parameters settings, while simultaneously search

failure scenarios

• GA search should be pursued only for systems with suffic

schedule time, and where failure scenarios have high cos

Oct 16, 2013 Mitre Distinguished Lecture 
Future Work (I hope :‐)

• Additional analysis methods need to be explored:

– Use statistical and information‐theoretic techniques to extract 

from collected tuples

– Apply clustering algorithms to suggest specific classes of failur

• Continue to explore our case study:

– Uncover parameter subspaces where no failure scenarios can – Search under alternate definitions of anti‐fitness

• Apply method to models of other complex systems:

– Communication networks– Electrical grids– Epidemic networks– Network attack models

• Investigate run‐time methods to provide early warning of 

failures

Oct 16, 2013 Mitre Distinguished Lecture 
QUESTIONS?

Project Web Page: http://www.nist.gov/itl/antd/emergent_behaviorProject Team:Kevin Mills, computer scientist – kmills@nist.govChris Dabrowski, computer scientist – cdabrowski@nist.govJim Filliben, statistician – jfilliben@nist.govSandy Ressler, Ressler, information information visualization visualization specialist specialist – sressler@nist.gov sressler@nist.gov

Oct 16, 2013 Mitre Distinguished Lecture