Automated Discovery of Emergent Misbehaviour

Computational models are essentially computer programs intended to simulate a natural system, such as an ant colony, the formation of skin tissue or the global economy. Scientists and industrialists use computational models to help develop their understanding of the natural system being modelled, to make forecasts, and to predict the impact of some change to the system. A topical example of an application of a computer model might be to predict the impact of nationalising the Northern Rock bank on the UK economy.Agent-based models are computational models which have been developed from the point of view of the main actors in the system, e.g. a terrorist in a model of civil uprising, or a voter in an election. Observations made from simulating the model can be understood and explained in terms of the individuals involved, answering questions such as 'why is there civil disturbance in this area of the country?', 'why is this political party popular here?' or 'why has a tumour developed here?'. Such inferences are arguably difficult to make from 'top-down' approaches to modelling, which are composed of a set of mathematical equations.As predictions and scientific discoveries are reliant on the models being implemented correctly, the consequences of not properly testing a model can be extremely serious, and have cost companies several millions of pounds in the past. However, traditional software testing strategies, which take a 'divide and conquer' approach, are difficult to apply to agent-based models. The interaction of agents in a simulation, often at random, produces complex patterns and behaviours. Thus, it is difficult to predict which causes will lead directly to which effects. The proposed research here intends to test agent-based models using intelligent search techniques, with the specific intention of 'homing in' on behaviours of the model that have not been exposed in previous simulation runs. In this way, the search process will encourage testing of the model in unlikely or ill-conceived situations, where the model's behaviour may diverge from that intended. In order to do this, the search process will build up an abstract picture of what the model is doing in simulation through extension of a technique known as invariant detection. Invariants are statements that are always found to be true. The search will essentially aim to falsify generated invariants generated from past simulations in order to demonstrate new behaviours of the model. These are likely to be rare or unexpected behaviours that may not have been previously tested, and thus possible instances where software errors may be lurking.