ESP

Manuvir Das, Sorin Lerner, Mark Seigle

ACM SIGPLAN Notices · 2002 · 55 citations · 19 references

Concepts

TL;DR

The paper focuses on verifying that a program satisfies a given temporal safety property. The authors propose a polynomial‑time, polynomial‑space algorithm for partial program verification. The algorithm, named ESP, models only branches where property‑relevant behavior differs, enabling efficient verification, and it was applied to a 140,000‑LOC GCC variant to check file‑I/O behavior. ESP verified all 646 .fprintf calls in GCC to print to valid, open files and demonstrated scalability to large programs.

Abstract

In this paper, we present a new algorithm for partial program verification that runs in polynomial time and space. We are interested in checking that a program satisfies a given temporal safety property. Our insight is that by accurately modeling only those branches in a program for which the property-related behavior differs along the arms of the branch, we can design an algorithm that is accurate enough to verify the program with respect to the given property, without paying the potentially exponential cost of full path-sensitive analysis.We have implemented this "property simulation" algorithm as part of a partial verification tool called ESP. We present the results of applying ESP to the problem of verifying the file I/O behavior of a version of the GNU C compiler (gcc, 140,000 LOC). We are able to prove that all of the 646 calls to .fprintf in the source code of gcc are guaranteed to print to valid, open files. Our results show that property simulation scales to large programs and is accurate enough to verify meaningful properties.

References

19