An Analytical Investigation of Software Mutation for Increased Information Survivability

AFRL

Funded by: Department of Defense, Air Force Research Lab
Administered by: Rome Laboratories

Abstract

Survivability in the natural world is based on diversity and evolution. Species only survive when sufficiently many individuals in the population are able to thwart disease and other adversities.

By contrast, software has a lack of diversity that often makes it vulnerable to malicious attacks. Our desire for standards and interoperability has overshadowed our desire for diversity. A series of attacks, all employing the same technique, can quickly undermine many programs in a distributed system by exploiting their shared vulnerabilities. Software viruses automate such attack methods, and their success shows how serious the consequences of non-diversity can be. Because of this, it has been suggested that the paradigm of survival through diversity might apply to software systems as well as biological systems.

If information systems can benefit from the same diversity that makes biological populations robust, then (1) the extent of these benefits must be quantified, and (2) practical methods need to be found for boosting survivability by increasing diversity. Our research is pursuing these two goals.

Personnel

Projects

Generic Mutation Tool (MARV)

The generic mutation tool is a hierarchical rewrite system that can be applied to parse trees. Rewrite rules define software mutations that change the incidental behavior of a program without changing the intended behavior, thus creating what are known as equivalent mutants.

Analysis of Multi-version System Survivability

The issues raised by using diversity to boost software survivability are similar to those raised in multi-version programming, where diversity is used to boost reliability. Because the effectiveness of multi-version programming has been called into question, we are developing formal models to characterize software diversity and its effect on survivability.

Canonical Representation of Software Idioms

One of the main concerns of software mutation testing is to avoid generating equivalent mutants. In this project, equivalent mutants are desirable, so we use the technology normally used to detect equivalent mutants to generate them instead. We do this by reducing portions of the program to a canonical symbolic form, which can then be re-expanded to source code in different ways.

Suite of Malicious Linux Attacks

We will test our techniques empirically by performing attacks on a (possibly weakened) system running under Linux. Our suite of attacks will be used to quantify effectiveness of diversity in thwarting malicious attacks. This attack suite will also help us understand when automatic diversification is (or is not) a feasible way to slow down a malicious attack.

Contact

Dr. Christoph Michael, Principal Investigator