Searching for invariants using genetic programming and mutation testing

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

Abstract

Invariants are concise and useful descriptions of a program's behaviour. As most programs are not annotated with invariants, previous research has attempted to automatically generate them from source code. In this paper, we propose a new approach to invariant generation using search. We reuse the trace generation front-end of existing tool Daikon and integrate it with genetic programming and a mutation testing tool. We demonstrate that our system can find the same invariants through search that Daikon produces via template instantiation, and we also find useful invariants that Daikon does not. We then present a method of ranking invariants such that we can identify those that are most interesting, through a novel application of program mutation.
Original languageEnglish
Title of host publicationGECCO 2011
Subtitle of host publicationProceedings of 13th Annual Conference on Genetic and Evolutionary Computation
EditorsNatalio Krasnogor, Pier Luca Lanzi
PublisherACM
Pages1907-1914
Number of pages8
ISBN (Print)978-1-4503-0557-0
DOIs
Publication statusPublished - 2011
EventGECCO '11 - Dublin, Ireland
Duration: 12 Jul 201116 Jul 2011

Conference

ConferenceGECCO '11
Country/TerritoryIreland
CityDublin
Period12/07/1116/07/11

Bibliographical note

Winner of the Best Search Based Software Engtineering (SBSE) Paper Prize

Cite this