Metamorphic Testing for “Non-Testable” Systems2018-03-19T13:44:35+00:00

Verification Futures 2018

Conference:Verification Futures 2018 (click here to see full programme)
Speaker:Alastair Donaldson, Director (GraphicsFuzz) and Reader (Imperial College London)
Presentation Title:Metamorphic Testing for “Non-Testable” Systems

Software testing, and testing of systems more generally, usually depends on the availability of a “test oracle” that specifies the expected behaviour for a given test input. Unfortunately for many systems a rich test oracle is not readily available. For example, a compiler should never crash (a very basic property), but more importantly should produce a binary that respects the semantics of the input program (a much richer property).

Obtaining a “crash oracle” for a compiler is simple, but obtaining a trustworthy oracle for deciding when the code generated by a compiler is valid is extremely difficult: if the programming language of interest is complex (think C++) then building an oracle is as hard as building a compiler for the language. Programs and systems for which there does not exist an oracle in theory, or for which an oracle is infeasible to obtain in practice, were termed “untestable” by Weyuker in her seminal 1982 paper.

In this talk I will discuss “metamorphic testing”, a mechanism for circumventing the oracle problem proposed by Chen et al. The basic idea behind metamorphic testing is to exploit known properties of a problem domain to derive “metamorphic relations” between inputs, such that while the expected behaviour of a single input is not known, the relationship between behaviours for a pair of metamorphically-related inputs is. I will illustrate this concretely by showing how we have used metamorphic testing to find a large number of bugs in graphics shader compilers for the OpenGL programming model, and will talk briefly about GraphicsFuzz, a spinout company from Imperial College London based on this work.

  • The oracle problem in software testing is hard
  • Metamorphic testing provides a solution
  • The GraphicsFuzz spinout is based on applying this solution in the domain of graphics drivers
Speaker Bio:Alastair Donaldson is a Reader and EPSRC Early Career Fellow in the Department of Computing, Imperial College London, where he leads the Multicore Programming Group, and is director of GraphicsFuzz, a spin-out company specialising in automated testing for graphics drivers. He is the recipient of the 2017 BCS Roger Needham Award for his research into many-core programming. He has published more than 70 peer-reviewed papers on programming languages, formal verification, software testing and parallel programming, and leads the GPUVerify project on automatic verification of GPU kernels – a collaboration with Microsoft Research – and the GLFuzz project on automated testing for graphics shader compilers. Alastair coordinated the FP7 project CARP: Correct and Efficient Accelerator Programming, which completed successfully in 2015. Before joining Imperial, Alastair was a Visiting Researcher at Microsoft Research Redmond, an EPSRC Postdoctoral Research Fellow at the University of Oxford and a Research Engineer at Codeplay Software Ltd. He holds a PhD from the University of Glasgow.