Combining Genetic Algorithms & Simulation to

Search for Failure Scenarios in System Models

Kevin Mills, Chris Dabrowski, Jim Filliben and Sandy Ressler

NIST

Cloud Security Working Group

July 17, 2013
Outline

• Motivation & Context

• Method

• Case Study

– Koala IaaS Cloud Simulator

– Searching for Failure Scenarios

– Evaluating Method

• Conclusions & Future Work

July 17, 2013 NIST Cloud Security WG 2
July 17, 2013 NIST Cloud Security WG 3

GROWING GLOBAL DEPENDENCE ON COMPLEX INFO. SYSTEMS
July 17, 2013 NIST Cloud Security WG 4

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

PREDICT & CONTROL THEM?
July 17, 2013 NIST Cloud Security WG 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
July 17, 2013 NIST Cloud Security WG 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.

 Ongoing: 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

PRESENTATION

 Planned: 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
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

July 17, 2013 NIST Cloud Security WG 7
Case Study Topics

July 17, 2013 NIST Cloud Security WG 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
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

July 17, 2013 NIST Cloud Security WG 9

Topic 1: Koala Simulator

In our case study we defined anti-fitness as the proportion of arriving users not served
 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

July 17, 2013 NIST Cloud Security WG 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

July 17, 2013 NIST Cloud Security WG 11

Topic 2: Koala Parameters & GA Representation

 as Chromosomes (i.e., bit strings) 
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.

July 17, 2013 NIST Cloud Security WG 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)

July 17, 2013 NIST Cloud Security WG 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

July 17, 2013 NIST Cloud Security WG 14

Topic 3: Genetic Algorithm
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

July 17, 2013 NIST Cloud Security WG 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

July 17, 2013 NIST Cloud Security WG 16

Topic 4: Population of Koala Simulators
July 17, 2013 NIST Cloud Security WG 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
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

July 17, 2013 NIST Cloud Security WG 18

Topic 5: Dynamics of GA Search
July 17, 2013 NIST Cloud Security WG 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
July 17, 2013 NIST Cloud Security WG 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
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

July 17, 2013 NIST Cloud Security WG 21

Topic 6: Analysis Method
-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

July 17, 2013 NIST Cloud Security WG 22

Differential Probability Analysis

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

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  f

x > 0.70} and L = {x  C  fx < 0.15}

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

P(PVif > 0.70 =PVi  H∕H and P(PVif > 0.15) = PVi  L∕L

Then compute the estimated differential probability:

D = P(PVif > 0.70) – P(PVif < 0.15)

Plot D for each PV pair
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

July 17, 2013 NIST Cloud Security WG 23

Topic 7: Results from Four GA Searches
July 17, 2013 NIST Cloud Security WG 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.
July 17, 2013 NIST Cloud Security WG 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
-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

July 17, 2013 NIST Cloud Security WG 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.
July 17, 2013 NIST Cloud Security WG 27

Potential Issue Regarding Estimate of P(PVif > 0.15) = PVi  L∕L

In scenarios 1-3, H  104, while L  103

To Increase |L|:

• use GA to search for success scenarios

• combine those tuples with tuples collected when searching for failures

Conduct differential probability analysis on 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

Next slide, shows the differential probability analysis for the combined tuple collection
July 17, 2013 NIST Cloud Security WG 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.
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

July 17, 2013 NIST Cloud Security WG 29

Conclusions
• 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

July 17, 2013 NIST Cloud Security WG 30

Future Work
QUESTIONS?

July 17, 2013 NIST Cloud Security WG 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