Discovering properties about arrays in simple programs
Authors:
Open Access
- 30 May 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 43 (6) , 339-348
Abstract
Array bound checking and array dependency analysis (for parallelization) have been widely studied. However, there are much less results about analyzing properties of array contents . In this paper, we propose a way of using abstract interpretation for discovering properties about array contents in some restricted cases: one-dimensional arrays, traversed by simple "for" loops. The basic idea, borrowed from [GRS05], consists in partitioning arrays into symbolic intervals (e.g., [1, i -- 1], [ i , i ], [ i + 1, n ]), and in associating with each such interval I and each array A an abstract variable A I ; the new idea is to consider relational abstract properties ψ( A I , B I , ...) about these abstract variables, and to interpret such a property pointwise on the interval I : ∀ l ∈ I , ψ( A [ l ], B [ l ],...). The abstract semantics of our simple programs according to these abstract properties has been defined and implemented in a prototype tool. The method is able, for instance, to discover that the result of an insertion sort is a sorted array, or that, in an array traversal guarded by a "sentinel", the index stays within the bounds.Keywords
This publication has 15 references indexed in Scilit:
- Lifting abstract interpreters to quantified logical domains2008
- Path invariants2007
- FAST Extended Release2006
- Programs with Lists Are Counter AutomataLecture Notes in Computer Science, 2006
- What’s Decidable About Arrays?2005
- Numeric Domains with Summarized Dimensions2004
- Indexed Predicate Discovery for Unbounded System Verification2004
- Verification by Abstract Interpretation2003
- Model-Checking in Dense Real-TimeInformation and Computation, 1993
- Proof of a programCommunications of the ACM, 1971