Validation of array accesses: integration of flow analysis and program verification techniques

✍ Scribed by Raymond W. Lo; Karl N. Levitt; Ronald A. Olsson

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 165 KB
• Volume: 7
• Category: Article
• ISSN: 0960-0833
• DOI: 10.1002/(sici)1099-1689(199712)7:4<201::aid-stvr145>3.0.co;2-b

✦ Synopsis

A program that accesses an out-of-bound array element can cause unexpected behaviour that is unacceptable to safety-critical or security-critical systems. Two traditional compile-time approaches to array bound checking are flow analysis and program verification. This paper presents a new approach, IFV, that integrates flow analysis and program verification techniques. IFV is generally about as effective as program verification yet runs in about the same time as flow analysis. Its typical runtime is proportional to the product of the program size and the number of declared variables. IFV matches loops to templates, which represent commonly occurring loop patterns, to discover loop invariants automatically, which it then uses to strengthen flow analysis. With only seven templates, it handles many common array-access patterns. Patterns not verified by flow analysis are processed with verification techniques entirely automatically. This paper also describes a prototype IFV system that performs compiletime array bound checking for programs in a subset of C.