By the same authors

Metamorphic testing of constraint solvers

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

Author(s)

Department/unit(s)

Publication details

Title of host publicationPrinciples and Practice of Constraint Programming
DateAccepted/In press - 15 Jun 2018
DateE-pub ahead of print - 23 Aug 2018
DatePublished (current) - 23 Aug 2018
Pages727-736
Number of pages10
PublisherSpringer
Place of PublicationNetherlands
EditorsJohn Hooker
Original languageEnglish
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332

Publication series

NameLecture Notes in Computer Science
PublisherSpringer

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.

Bibliographical note

© Springer Nature Switzerland AG 2018. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Funding: EPSRC EP/P015638/1 and EP/P026842/1. Dr Jefferson holds a Royal Society University Research Fellowship.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations