TopoScope: a Topographical Approach to Software Testing

Modern software systems deal with complex inputs, which can be highly structured (e.g., Json documents; service requests), completely unstructured (e.g., images or text processed by a neural network), or a hybrid of the two. The dimensionality of the input space is often huge and correspondingly only a small fraction of all possible inputs can be used to exercise the system during software testing. Hence, the way inputs are sampled from such huge space represents a critical component of any software testing approach. Ideally, representative inputs should be sampled to ensure the intended behaviour in nominal conditions, but at the same time corner case inputs should be also sampled to verify the behaviour exhibited in extreme conditions.

Existing adequacy criteria used for test input selection or generation are mostly based on coverage: a test suite is deemed adequate if upon execution it exercises all code elements targeted by the specific coverage criterion (e.g., branch coverage; data-flow coverage). However, there are multiple ways to cover the same code elements, some involving nominal, others extreme, inputs. With traditional software, the relation between coverage and fault exposure has been shown empirically to be weak. With modern software (e.g., including deep learning components) that processes complex, highly unstructured inputs such a relation is expected to be even weaker. Indeed, recent attempts to extend the notion of coverage adequate test suites to deep learning components were also investigated empirically and found equally ineffective. A novel approach is needed to represent the input space of complex, unstructured inputs and to sample it in order to maximize the effectiveness of the resulting test suite.

In this project we investigate TOPOSCOPE, a novel topographical approach to test software components (e.g., neural networks) that handle highly complex inputs. TOPOSCOPE consists of an input topography construction phase, in which the elements of the input space are organized into an N-dimensional map that preserves the key features of the inputs. The topography of the input space is accompanied by a distance metric, which is used to guide automated test input generation. TOPOSCOPE provides both a diversity oriented and a focused test generator. The former aims at covering the regions of the input topographical map at large, so as to ensure the intended behaviour across the various feature combinations that may occur in nominal conditions. The latter aims at finding examples that belong to a narrow and potentially problematic region of the topographical map.

The project will study black box and white box techniques for the extraction of input features that can be used to create a software input topography. It will design alternative topography construction algorithms, based on different input embeddings, considering human interpretability as an important property of the resulting topographical map. It will evaluate the approach empirically on both traditional and deep learning based software systems. The tool TOPOSCOPE will be released as open source software under a permissive (e.g., MIT) open license.