Red teaming is the process of studying a problem by anticipating adversary behaviors. When done in simulations, the behavior space is divided into two groups; one controlled by the red team which represents the set of adversary behaviors or bad guys, while the other is controlled by the blue team which represents the set of defenders or good guys. Through red teaming, analysts can learn about the future by forward prediction of scenarios. More recently, defense has been looking at evolutionary computation methods in red teaming. The fitness function in these systems is highly stochastic, where a single configuration can result in multiple different outcomes. Operational, tactical and strategic decisions can be made based on the findings of the evolutionary method in use. Therefore, there is an urgent need for understanding the nature of these problems and the role of the stochastic fitness to gain insight into the possible performance of different methods. This paper presents a first attempt at characterizing the search space difficulties in red teaming to shed light on the expected performance of the evolutionary method in stochastic environments.