Coverage Based Failure Injection Toward Efficient Chaos Engineering
Hiroki Ikeuchi, Akio Watanabe, Yousuke Takahashi · 2023
We discuss the problem of designing efficient chaos engineering (CE) experiments in network systems on the basis of coverage. CE is an operational methodology to verify whether unexpected events occur by injecting failures while satisfying conditions called invariant in order to continue service provision in a commercial environment. Since the number of possible failures is enormous, random or manual design of CE is inefficient, and redundant experiments may unnecessarily burden the system. Therefore, a systematic design of CE experiments is needed. We formulate this as a mathematical optimization problem that aims to maximize coverage or minimize the number of experimental iterations. When connectivity is used as an invariant, we propose a polynomial algorithm to obtain an exact optimal solution by attributing it to a matroid intersection problem. When the invariant is general, we propose algorithms that give approximate and exact optimal solutions for problems of realistic size by constructing a binary decision diagram (BDD) representing the invariant. Numerical evaluation on open datasets demonstrates the effectiveness of the proposed methods.