A symbolic analysis framework for static analysis of imperative programming languages
Saved in:
| Title: | A symbolic analysis framework for static analysis of imperative programming languages |
|---|---|
| Authors: | Burgstaller, Bernd1 bburg@cs.yonsei.ac.kr, Scholz, Bernhard2 scholz@it.usyd.edu.au, Blieberger, Johann3 blieb@auto.tuwien.ac.at |
| Source: | Journal of Systems & Software. Jun2012, Vol. 85 Issue 6, p1418-1439. 22p. |
| Subjects: | Symbolic computation, Imperative programming, Programming languages, Computer software, Homomorphisms, Compactification (Mathematics) |
| Abstract: | Abstract: We present a generic symbolic analysis framework for imperative programming languages. Our framework is capable of computing all valid variable bindings of a program at given program points. This information is invaluable for domain-specific static program analyses such as memory leak detection, program parallelization, and the detection of superfluous bound checks, variable aliases and task deadlocks. We employ path expression algebra to model the control flow information of programs. A homomorphism maps path expressions into the symbolic domain. At the center of the symbolic domain is a compact algebraic structure called supercontext. A supercontext contains the complete control and data flow analysis information valid at a given program point. Our approach to compute supercontexts is based purely on algebra and is fully automated. This novel representation of program semantics closes the gap between program analysis and computer algebra systems, which makes supercontexts an ideal symbolic intermediate representation for all domain-specific static program analyses. Our approach is more general than existing methods because it can derive solutions for arbitrary (even intra-loop and nested loop) nodes of reducible and irreducible control flow graphs. We prove the correctness of our symbolic analysis method. Our experimental results show that the problem sizes arising from real-world applications such as the SPEC95 benchmark suite are tractable for our symbolic analysis framework. [Copyright &y& Elsevier] |
| Copyright of Journal of Systems & Software is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
