Metamorphic testing of constraint solvers

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)
3 Downloads (Pure)

Abstract

Constraint solvers are complex pieces of software and are notoriously difficult to debug. In large part this is due to the difficulty of pinpointing the source of an error in the vast searches these solvers perform, since the effect of an error may only come to light long after the error is made. In addition, an error does not necessarily lead to the wrong result, further complicating the debugging process. A major source of errors in a constraint solver is the complex constraint propagation algorithms that provide the inference that controls and directs the search. In this paper we show that metamorphic testing is a principled way to test constraint solvers by comparing two different implementations of the same constraint. Specifically, specialised propagators for the constraint are tested against the general purpose table constraint propagator. We report on metamorphic testing of the constraint solver Minion. We demonstrate that the metamorphic testing method is very effective for finding artificial bugs introduced by random code mutation.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings
EditorsJohn Hooker
PublisherSpringer
Pages727-736
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332
DOIs
Publication statusPublished - 2018
Event24th International Conference on Principles and Practice of Constraint Programming (CP 2018) - Euratechnologies, Lille, France
Duration: 27 Aug 201831 Aug 2018
Conference number: 24
http://cp2018.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11008
ISSN (Print)0302-9743

Conference

Conference24th International Conference on Principles and Practice of Constraint Programming (CP 2018)
Abbreviated titleCP 2018
Country/TerritoryFrance
CityLille
Period27/08/1831/08/18
Internet address

Fingerprint

Dive into the research topics of 'Metamorphic testing of constraint solvers'. Together they form a unique fingerprint.

Cite this