Combining Genetic Algorithms & Simulation to

Search for Failure Scenarios in System Models

Kevin Mills

National Institute of Standards & Technology (NIST)

Joint work with NIST colleagues: Chris Dabrowski

 Jim Filliben

 Sandy Ressler

George Mason University Computer Science Seminar

February 19, 2014
Outline

• Motivation & Context

• Method

• Case Study

– Koala IaaS Cloud Simulator

– Searching for Failure Scenarios

– Evaluating Method

• Conclusions & Future Work

February 19, 2014 GMU CS Interdisciplinary Seminar 2
3

GROWING GLOBAL DEPENDENCE ON COMPLEX INFO. SYSTEMS

February 19, 2014 GMU CS Interdisciplinary Seminar
4

WE CAN BUILD & DEPLOY SUCH SYSTEMS, BUT CAN WE UNDERSTAND,

PREDICT & CONTROL THEM?

February 19, 2014 GMU CS Interdisciplinary Seminar
5

PAST NIST RESEARCH FROM 2006-2011

How can we understand the influence of distributed control 

algorithms on global system behavior and user experience?

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

Internet 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 116-5, 771-783 (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 

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 4th

International Cloud Computing Conference, IEEE (2011).

 Mills, Filliben and Dabrowski, "Comparing VM-Placement 

Algorithms for On-Demand Clouds", Proceedings of IEEE 

CloudCom, 91-98 (2011).

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

What to measure

Under what conditions

http://www.nist.gov/itl/antd/Congestion_Control_Study.cfm

At an affordable cost

Internet

Cloud

February 19, 2014 GMU CS Interdisciplinary Seminar
6

 Research Goals: (1) develop and evaluate design-time methods that 

system engineers can use to detect existence and causes of costly failure 

regimes prior to system deployment and (2) develop and evaluate runtime methods that system managers can use to detect onset of costly 

failure regimes in deployed systems, prior to collapse.

 Recent: investigating design-time methods –

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

SEMINAR

 Ongoing: investigate run-time methods based on approaches that may 

provide early warning signals for critical transitions in large systems (e.g., 

Scheffer et al., “Early-warning signals for critical transitions”, NATURE, 461, 53-59, 2009).

http://www.nist.gov/itl/antd/upload/NISTIR7744.pdf

How can we increase the reliability of complex information systems?

ONGOING NIST RESEARCH FROM 2012-PRESENT

February 19, 2014 GMU CS Interdisciplinary Seminar
Method: Genetic Algorithm (GA) steers a population of 

 simulators to search for parameter combinations 

 that lead to system failure

Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

February 19, 2014 GMU CS Interdisciplinary Seminar 7
Case Study Topics

8

1. Koala Simulator

2. Koala Parameters & Representation as Chromosomes

3. Genetic Algorithm

4. Population of Koala Simulators

5. Dynamics of GA Search

6. Analysis Method

7. Results from Four GA Searches

February 19, 2014 GMU CS Interdisciplinary Seminar
Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

9

Topic 1: Koala Simulator

In our case study we defined anti-fitness as the proportion of arriving users not served

February 19, 2014 GMU CS Interdisciplinary Seminar
 INTERNET

DEMAND LAYER

SUPPLY 

LAYER

VM 

BEHAVIOR

 LAYER

RESOURCE 

ALLOCATION

 LAYER

User 

#1

User 

#2

User 

#n

User 

#3

User 

#4

User 

#5

User 

#6

User 

#n-3

User 

#n-2

User 

#n-1

CLOUD CONTROLLER

Cluster 

Controller #1

Cluster 

Controller #c

NODE CONTROLLER #k

NODE RESOURCES NODE CONTROLLER #k-1

NODE RESOURCES NODE CONTROLLER #k-2

NODE RESOURCES

NODE CONTROLLER #3

NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

NODE CONTROLLER #p

NODE RESOURCES NODE CONTROLLER #p-1

NODE RESOURCES NODE CONTROLLER #p-2

NODE RESOURCES

NODE CONTROLLER #3

NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

NODE CONTROLLER #q

NODE RESOURCES NODE CONTROLLER #q-1

NODE RESOURCES NODE CONTROLLER #q-2

NODE RESOURCES

NODE CONTROLLER #3

NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

INTRANETINTRANETINTRANET

VMs 

Shown for

One Node Only

VMs 

Shown for

One Node Only

VMs 

Shown for

One Node Only

VM1VM1VM1VM1 VM1VM1VM1VM1VM1 VM1VM1VM1VM1VM1 VM1

Cluster 

Controller #cm

(1)

(4)

(4) (3)

(2)

(4) (4)

(5)

Schematic of Koala IaaS Cloud Simulator

Demand and supply layers modeled after Amazon EC2 

Internal structure modeled after Eucalyptus v1.6

February 19, 2014 GMU CS Interdisciplinary Seminar 10
Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

11

Topic 2: Koala Parameters & GA Representation

 as Chromosomes (i.e., bit strings) 

February 19, 2014 GMU CS Interdisciplinary Seminar
Model

Element

Parameter Category

Behavior Structure Asymmetry Failure Total

User 28 2 4 0 34

Cloud Controller 21 4 5 0 30

Cluster Controllers 11 5 3 0 19

Nodes 6 0 0 14 20

Intra-Net/Inter-Net 4 11 2 9 26

Totals 70 22 14 23 129

Summary of Koala Parameters to Search Over

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

i.e., ≈ 10100 scenarios are possible

 adapted 125-parameter Koala IaaS simulator to be GA controllable 

 added 4 Koala parameters to turn on/off logic to control (a) creation orphans, 

 (b) termination orphans, (c) relocation orphans and (d) administrator actions

Test Case – Can GA find VM Leakage due to message loss and lack of orphan control? 

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

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

February 19, 2014 GMU CS Interdisciplinary Seminar 12
Sample Chromosome Specification

PARAMETER MIN MAX PRECISION #VALUES LOW_BIT HIGH_BIT #BITS

P_CreateOrphanControlOn 0 1 1 2 3 6 3 6 1

P_TerminationOrphanControlOn 0 1 1 2 5 8 5 8 1

P_RelocationOrphanControlOn 0 1 1 2 1 1 1 1 1

P_AdministratorActive 0 1 1 2 330 330 1

P_clusterAllocationAlgorithm 0 5 1 6 3 1 3 3 3

P_describeResourcesInterval 600 3600 600 6 8 1 8 3 3

P_nodeResponseTimeout 3 0 9 0 3 0 3 210 211 2

P_TerminatedInstancesBackOffThreshold 3 6 1 4 5 6 5 7 2

P_TerminationBackOffInterval 180 360 6 0 4 8 8 8 9 2

P_TerminationRetryPeriod 600 1200 300 3 316 317 2

P_StaleShadowAllocationPurgeInterval 600 3600 600 6 242 244 3

P_cloudAllocationCriteria 0 3 1 4 321 322 2

P_clusterShadowPurgeLimit 1 2 1 5 5 290 292 3

P_instancePurgeDelay 180 600 6 0 8 9 8 100 3

P_clusterEvaluationResponseTimeout 6 0 120 3 0 3 1 4 1 5 2

P_MaxPendingRequests 1 1 0 1 1 0 7 2 7 5 4

P_CloudTerminatedInstancesBackOffThreshold 3 6 1 4 169 170 2

P_CloudTerminationBackOffInterval 180 360 6 0 4 4 0 4 1 2

P_CloudTerminationRetryPeriod 3600 10800 1800 5 297 299 3

P_ClusterShutdownGracePeriod 86400 2.59E+05 43200 5 147 149 3

P_RequestEvaluatorTimeoutWaitProportion 0.1 0.4 0.1 4 145 146 2

P_RequestEvaluatorClusterMinimumResponse 0.6 0.9 0.1 3 269 270 2

P_MaxRelocationDuratonProportion 0.65 0.95 0.1 4 9 0 9 1 2

P_MaximumRelocateDescribeRetries 4 1 6 2 7 254 256 3

P_AverageCloudAdministratorAttentionLatency 28800 86400 14400 5 308 310 3

P_AverageCloudAdministratorShutdownDelay 300 900 300 3 4 5 4 6 2

P_avgTimeToClusterCommunicationCut 2.88E+06 2.88E+07 2.88E+06 1 0 217 220 4

Genetic Algorithm Computed

Chromosome Map (Size = 2334)

Koala Parameter 

Space (Size = 10100)

February 19, 2014 GMU CS Interdisciplinary Seminar 13
Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

14

Topic 3: Genetic Algorithm

February 19, 2014 GMU CS Interdisciplinary Seminar
Genetic Algorithm Flow Chart

Generate Needed Random Population of Individuals

Terminate? Evaluate Fitness Stop

Elite Individuals? Population of Individuals

YES

YES COPY TO NEXT GENERATION Select Candidate Individuals NO or YES

Reboot? Elite Individuals?

YES COPY TO NEXT GENERATION

NO or YES YES NO

Candidate Individuals

Choose Pair From Candidate Individuals Crossover? Choose Crossover Points & Swap Chromosomes Population of Recombined Individuals

Mutate Individual? Iterate Over Individuals Flip Chromosomes as Required

Start

YES NO

YES NO

INSERT PAIR INTO RECOMBINED POPULATION

INSERT INSERT IN NEXT POPULATION

INSERT PAIR

NO

SELECT

RECOMBINE

MUTATE

REBOOT?

EVALUATE

SEED

POPULATION

DONE?

1

2

3

4

5

6

7

February 19, 2014 GMU CS Interdisciplinary Seminar 15
Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

16

Topic 4: Population of Koala Simulators

February 19, 2014 GMU CS Interdisciplinary Seminar
17

Head Node 1

Head Node 2

Shared File

Store

Compute Node 1 Compute Node 2 Compute Node 12

Compute Node 13 Compute Node 14 Compute Node 24

Enterprise Network

Cluster Network

License Server 8 Koala Processes

8 Koala Processes

12 Koala Processes

12 Koala Processes 12 Koala Processes

200 Koala Working Directories GA Checkpoint Database

Node Manager Job Manager

GA Controller GA Management Processes

CLUSTER GA Results Tuples

Population of Koala Simulators Deployed on a High 

Performance Computing Cluster

February 19, 2014 GMU CS Interdisciplinary Seminar
Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

18

Topic 5: Dynamics of GA Search

February 19, 2014 GMU CS Interdisciplinary Seminar
19

Generations 500

Population Size 200 Individuals

Elite Per Generation 16 Individuals

Reboot After 200 Generations

Selection Method Stochastic Uniform Sampling

# Crossover Points 3

Mutation Rate 0.001 < Adaptive < 0.01

GENETIC ALGORITHM CONTROL PARAMETERS

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 100 200 300 400 500

Generation

(a) Average Anti-Fitness

0

0.05

0.1

0.15

0.2

0.25

0.3

0 100 200 300 400 500

Generation

(b) Standard Deviation in Anti-Fitness

0.7

0.72

0.74

0.76

0.78

0.8

0.82

0.84

0 100 200 300 400 500

Generation

(c) Maximum Anti-Fitness Discovered

One GA Search over 500 Generations

February 19, 2014 GMU CS Interdisciplinary Seminar
20

0

0.05

0.1

0.15

0.2

5

101520253035404550556065707580859095

100

Anti-Fitness

Frequency Distribution of Anti-Fitness

Assessment of Search Conducted by GA

(based on 105scenarios, i.e., 200 individuals x 500 generations) 

• 84% of scenarios exhibit anti-fitness ≥ 0.50

• Only 8% of scenarios are duplicate (equals elite-selection percentage)

• For Koala simulator, failure scenarios appear within first 100-200 generations

February 19, 2014 GMU CS Interdisciplinary Seminar
Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

21

Topic 6: Analysis Method

February 19, 2014 GMU CS Interdisciplinary Seminar
-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0 100 200 300 400 500 600 700

i = 684 Parameter-Value Pairs

P(PVi|f>0.70) - P(PVi|f<0.15) 

D

PVi 

Outliers contributing to failure scenarios

Outliers contributing to success scenarios

PVs exerting little influence on success or failure

22

Differential Probability Analysis

February 19, 2014 GMU CS Interdisciplinary Seminar
Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

23

Topic 7: Results from Four GA Searches

February 19, 2014 GMU CS Interdisciplinary Seminar
24

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0 100 200 300 400 500 600 700

CreateOrphanControlOn = FALSE

AvgUserRequestTimeout = 30

AvgThinkTime = 900

CreateOrphanControlOn = TRUE

NodesPerCluster = 200

UserRestPeriodMultiplier = 32

NodesPerCluster = 400

Analysis of Results from GA Search 1 – 500 Generations

Seeking Known Failure Scenario – search duration 30 days

D (y-axis) for 684 PV pairs (x-axis) for first GA search–outlier PV pairs labeled.

February 19, 2014 GMU CS Interdisciplinary Seminar
25

Analysis of Results from GA Search 2 – 205 Generations

Seeking Previously Unknown Failure Scenarios – search duration 14 days

D (y-axis) for 677 PV pairs (x-axis) for first GA search–outlier PV pairs labeled.

-0.3

-0.2

-0.1

0

0.1

0.2

0.3

0.4

0.5

0 100 200 300 400 500 600 700

AvgUserRequestTimeout = 30

AvgThinkTime = 900

UserRestPeriodMultiplier = 32

NumberofSitesReservedForCloud = 2

NodesPerCluster = 200

MilesPerRouterHop = 500

MaxPerHopDelay = 0.9

StdUserRequestTimeout = 30

NodesPerCluster = 400

AvgUserRequestTimeout = 120

NumberofSitesReservedForCloud = 1

AvgThinkTime = 1500

MilesPerRouterHop = 1500

February 19, 2014 GMU CS Interdisciplinary Seminar
-0.3

-0.2

-0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0 100 200 300 400 500 600 700

NodesPerCluster = 600 UserTypeArraySelector = 4

AvgThinkTime = 1200 AvgUserRequestTimeout = 90

SiteDistanceMultiplier = 7

MinSiteCoordinate = 0 UserRestPeriodMultiplier = 32

StdUserRequestTimeout = 30

MinReservationRetries = 2

AvgInterUserStartDelay = 30

MinIntrasiteDelay = 2x10-8

MinClusters = 9

MaxSiteCoordinate = 16000

MaxPerHopDelay = 0.9

MaxIntrasiteDelay = 1.5x10-5

CloudSizeChangeFraction = 0.3

ClusterResponseTimeout = 120

MaxIntersiteLossRate = 10-7

PlatformTypeArraySelector = 4 ProbabilityImageNotFound = 10-6

ChoosePlatformTypesRandomly = FALSE

RandomizeMinMaxVMsRequested = TRUE

MinRestPeriods = 2

NodeResponseTimeout = 30

26

Analysis of Results from GA Search 3 – 209 Generations

Nudging up Some Parameter Ranges and Seeking Additional Failure Scenarios -

search duration 16 days

D (y-axis) for 680 PV pairs (x-axis) for first GA search–outlier PV pairs labeled.

February 19, 2014 GMU CS Interdisciplinary Seminar
27

Next slide, shows the differential probability analysis for the combined tuple collection

As an example, we augmented GA search 3 with a 4th GA search looking for 

success scenarios, and combined the tuple collections from searches 3 and 4 

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

February 19, 2014 GMU CS Interdisciplinary Seminar
28

Analysis of Results from GA Search 4 – 209+205 Generations

Including additional PV pairs in L discovered by GA searching for success scenarios

- search duration 14 days

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

0 100 200 300 400 500 600 700

AvgUserRequestTimeout = 90 AvgThinkTime = 1200

SiteDistanceMultiplier = 7 UserRestPeriodMultiplier = 32

NodesPerCluster = 600 UserTypeArraySelector = 4

MinSiteCoordinate = 0 StdUserRequestTimeout = 30

MaxSiteCoordinate = 16000 AvgInterUserStartDelay = 30

MinIntrasiteDelay = 2x10-8 MinReservationRetries = 2

MinClusters = 9 RandomizeMinMaxVMsRequested = FALSE

AvgAdminDelay = 900 CloudSizeChangeFraction = 0.3

ClusterResponseTimeout = 120

RandomizeMinMaxVMsRequested = TRUE

NodeResponseTimeout = 30

MinRestPeriods = 2

ChoosePlatformTypesRandomly = FALSE

MaxSiteCoordinate = 12000

AvgAdminDelay = 300

D (y-axis) for 683 PV pairs (x-axis) for first GA search–outlier PV pairs labeled.

February 19, 2014 GMU CS Interdisciplinary Seminar
SUMMARY:

• Defined a design-time method, combing GA search with simulation, 

to seek failure scenarios in system models

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

failure scenario in an existing cloud simulator

• Iterated search to reveal previously unknown failure scenarios

FINDINGS:

• GA searches explored predominantly non-duplicative scenarios with 

high anti-fitness

• Uncovered evidence that GA search can reveal insights about 

optimal parameters settings, while simultaneously searching for 

failure scenarios

• GA search should be pursued only for systems with sufficient 

schedule time, and where failure scenarios have high cost

29

Conclusions

February 19, 2014 GMU CS Interdisciplinary Seminar
• Additional analysis methods need to be explored:

– Use statistical and information-theoretic techniques to extract features 

from collected tuples

– Apply clustering algorithms to suggest specific classes of failure scenarios

• Continue to explore our case study:

– Uncover parameter subspaces where no failure scenarios can be found

– 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 incipient 

failures

30

Future Work

February 19, 2014 GMU CS Interdisciplinary Seminar
 RELATED INFORMATION

31

Project Web Page: http://www.nist.gov/itl/antd/emergent_behavior.cfm

Project Team:

Kevin Mills, computer scientist – kmills@nist.gov

Chris Dabrowski, computer scientist – cdabrowski@nist.gov

Jim Filliben, statistician – jfilliben@nist.gov

Sandy Ressler, information visualization specialist – sressler@nist.gov

Paper: K. Mills, C. Dabrowski, J. Filliben and S. Ressler, 

 "Combining Genetic Algorithms and Simulation to 

 Search for Failure Scenarios in System Models", 

 Proceedings of the 5th International Conference on 

 Advances in Simulation, Venice, Italy, October 2013.

February 19, 2014 GMU CS Interdisciplinary Seminar