## Combinatorial Explosion in Fault Injection

By nbguzman on Thursday 1 October 2015, 00:00 - cdot - Permalink

As mentioned in the previous post, I will be going into more detail regarding the problem of generating cases when building a series of test cases to be used in our fault injection framework.

The problem is that we are generating way too many cases--which is kind of what we want because we want to go through every single possible combination of fault cases. Below are simple examples of how we generate cases.

**Simple case: 2 nodes, 1 plugin:**

Nodes: n1, n2 Plugins: p1 Combinations of Relationships: n1 - n2 Combinations of Plugins that can apply to a single node at a time: none, p1 Combinations of plugins applied to combinations of nodes: n1:n2 -------- none:none p1:none none:p1 p1:p1 Total: 4 cases (3 if excluding none:none)

**Simple case: 2 nodes, 2 plugins:**

Nodes: n1, n2 Plugins: p1, p2 Combinations of Relationships: n1 - n2 Combinations of Plugins that can apply to a single node at a time: none, p1, p2, (p1 & p2) Combinations of plugins applied to combinations of nodes: n1:n2 -------- none:none p1:none p2:none (p1 & p2):none none:p1 p1:p1 p2:p1 (p1 & p2):p1 none:p2 p1:p2 p2:p2 (p1 & p2):p2 none:(p1 & p2) p1:(p1 & p2) p2:(p1 & p2) (p1 & p2):(p1 & p2) Total: 16 cases (15 if excluding none:none)

As you can see, the total number of cases increases exponentially the more plugins you add in from just simple cases. It gets even larger when increasing the nodes. For example, having 3 nodes that are connected to each other generates a combination of: (n1-n2, n1-n3, n2-n3). This is an example of Combinatorial Explosion. This is when the number of combinations grow exponentially.

Our total number of cases is equal to *C^N*, where *C* is the
combination of plugins and *N* is the number of nodes. This only takes
into consideration of node-to-node relationships, if each node has the same
plugins available to them, and if the plugins only apply to 1 node.

To decrease the number of generated cases, we thought of Fault Collapsing. Because some cases are necessary (duplicates) or have obvious results (having all nodes being tested shut down), we would be able to decrease the total number of cases that should actually be run. So our next course of action would be to start implementing these rules to rule out the illegal combination of plugins and nodes.