Automated Discovery of Emergent Misbehaviour

Lead Research Organisation: University of Sheffield
Department Name: Computer Science


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.


10 25 50
Description Agents have been used to model individual people in a crowd control simulation, cells in skin tissue, the main players in an economy; for example banks, countries, households and firms. During simulation, agents interact to produce complex macro-behaviours - emergent behaviours such as the self-organisation of blood vessel membranes in response to a tumour, uprising of terrorist activity or voting trends in election campaigns. Observations made from simulating the model can be understood and explained in terms of the individuals involved.

The aim of this project was to develop testing techniques for agent-based simulation models, using a combination of metaheuristic search, invariant detection and mutation analysis. The key findings were as follows:

1. Random search works better than metaheuristic search for detecting anomalous behaviour (as detected through the violation of invariants using the Daikon tool). This is because the input domain is huge, and random search is highly diversified compared to a search that involves a fitness function. This led to some developments in search-based testing:

a) The development of input domain reduction strategies and when and why they will work for different search algorithms (Evolutionary, Local and Random).

b) A theory backed up by empirical evaluation as to why different search algorithms (Evolutionary, Local and Random) perform better in generating test cases

2. Anomalous behaviour may also be detected by statistical monitoring and checking for outliers. This was implemented into a tool called MASTER.

3. Test effectiveness can be evaluated using Mutation Analysis, yet multi-agent systems are suitably complex and different enough from existing software paradigms to warrant a definition of a set of mutation operators.
Exploitation Route The research may be used to test agent-based models used in industry in order to gain confidence from the predictions made from them. The research has been used to build the MASTER prototype tool for agent testing. The tool may be further improved and the other research results may also form the basis of tools - or knowledge about how to improve them.
Sectors Digital/Communication/Information Technologies (including Software)

Title MASTER (Multi-Agent Simulation TestER 
Description A tool for monitoring and testing agent-based model simulations. 
Type Of Technology Software 
Year Produced 2012 
Impact The tool notifies the tester about outlying potential anomalous behaviours of an agent-based model.