Analyzing array manipulating programs by program transformation

J. Robert M. Cornish, Graeme Gange, Jorge A. Navas, Peter Schachte, Harald Søndergaard, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

Abstract

We explore a transformational approach to the problem of verifying simple array-manipulating programs. Traditionally, verification of such programs requires intricate analysis machinery to reason with universally quantified statements about symbolic array segments, such as “every data item stored in the segment A[i] to A[j] is equal to the corresponding item stored in the segment B[i] to B[j].”We define a simple abstract machine which allows for set-valued variables and we show how to translate programs with array operations to array-free code for this machine. For the purpose of program analysis, the translated program remains faithful to the semantics of array manipulation. Based on our implementation in LLVM, we evaluate the approach with respect to its ability to extract useful invariants and the cost in terms of code size.

Original languageEnglish
Title of host publicationLogic-Based Program Synthesis and Transformation
Subtitle of host publication24th International Symposium, LOPSTR 2014 Canterbury, UK, September 9–11, 2014 Revised Selected Papers
EditorsMaurizio Proietti, Hirohisa Seki
Place of PublicationCham Switzerland
PublisherSpringer
Pages3-20
Number of pages18
ISBN (Electronic)9783319178226
ISBN (Print)9783319178219
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventInternational Symposium on Logic-Based Program Synthesis and Transformation 2014 - Canterbury, United Kingdom
Duration: 9 Sep 201411 Sep 2014
Conference number: 24th
http://www.iasi.cnr.it/events/lopstr14/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8981
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Symposium on Logic-Based Program Synthesis and Transformation 2014
Abbreviated titleLOPSTR 2014
CountryUnited Kingdom
CityCanterbury
Period9/09/1411/09/14
Internet address

Cite this

Cornish, J. R. M., Gange, G., Navas, J. A., Schachte, P., Søndergaard, H., & Stuckey, P. J. (2015). Analyzing array manipulating programs by program transformation. In M. Proietti, & H. Seki (Eds.), Logic-Based Program Synthesis and Transformation: 24th International Symposium, LOPSTR 2014 Canterbury, UK, September 9–11, 2014 Revised Selected Papers (pp. 3-20). (Lecture Notes in Computer Science ; Vol. 8981). Springer. https://doi.org/10.1007/978-3-319-17822-6_1