Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Undecidability of static analysis

Undecidability of static analysis Static analysis of programs is indispensable to any software tool, environment, or system that requires compile-time information about the semantics of programs. With the emergence of languages like C and LISP, static analysis of programs with dynamic storage and recursive data structures has become a field of active research. Such analysis is difficult, and the static-analysis community has recognized the need for simplifying assumptions and approximate solutions. However, even under the common simplifying assumptions, such analyses are harder than previously recognized. Two fundamental static-analysis problems are may alias and must alias . The former is not recursive (is undecidable), and the latter is not recursively enumerable (is uncomputable), even when all paths are executable in the program being analyzed for languages with if statements, loops, dynamic storage, and recursive data structures. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Letters on Programming Languages and Systems (LOPLAS) Association for Computing Machinery

Loading next page...
 
/lp/association-for-computing-machinery/undecidability-of-static-analysis-Dn3YTXUz95
Publisher
Association for Computing Machinery
Copyright
Copyright © 1992 by ACM Inc.
ISSN
1057-4514
DOI
10.1145/161494.161501
Publisher site
See Article on Publisher Site

Abstract

Static analysis of programs is indispensable to any software tool, environment, or system that requires compile-time information about the semantics of programs. With the emergence of languages like C and LISP, static analysis of programs with dynamic storage and recursive data structures has become a field of active research. Such analysis is difficult, and the static-analysis community has recognized the need for simplifying assumptions and approximate solutions. However, even under the common simplifying assumptions, such analyses are harder than previously recognized. Two fundamental static-analysis problems are may alias and must alias . The former is not recursive (is undecidable), and the latter is not recursively enumerable (is uncomputable), even when all paths are executable in the program being analyzed for languages with if statements, loops, dynamic storage, and recursive data structures.

Journal

ACM Letters on Programming Languages and Systems (LOPLAS)Association for Computing Machinery

Published: Dec 1, 1992

There are no references for this article.