Abstract
This paper presents a systematic method of building a more precise static analysis from a given one. The key idea is to lift an abstract domain to the finite sets of its labeled abstract properties. The labels are designed to gather information about the history of control flow and to obtain a finite partitioning of the program execution traces. The abstract operations of the lifted domain are derived from those of the original one. This is a particular instance of the reduced cardinal power introduced by P. and R. Cousot, where the base is the set of labels approximating the control history and the exponent is an abstract domain. The method is applied to the domain of convex polyhedra and to the domain of linear congruences.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Bourdoncle. Abstract interpretation by dynamic partitioning. Journal of Functional Programming, 2(4) (1992) 407–435.
P. Cousot. Semantic Foundations of Program Analysis. In Muchnick and Jones Eds. Program Flow Analysis, Theory and Applications, pp. 303–343, Prentice-Hall, 1981.
P. Cousot and R. Cousot. Static determination of dynamic properties of programs, In Proceedings of the 2nd Int. Symposium on Programming, pp. 106–130, 1976.
P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM Symposium on Principles of Programming Languages, pp. 238–252, 1977.
P. Cousot, and R. Cousot, Systematic Design of Program Analysis frameworks. In Proceedings of the 6th ACM Symposium on Principles of Programming Languages, pp. 269–282, 1979.
P. Cousot, and R. Cousot, Abstract Interpretation and Application to Logic Programs. In Journal of Logic Programming, pp. 103–179, 1992.
P. Cousot and N. Halbwachs. Automatic discovery of linear restraints among variables of a program. In Proceedings of the 5th Annual ACM Symposium on Principles of Programming Languages, pp. 84–97, 1978.
G. Filé and F. Ranzato, Improving abstract interpretations by systematic lifting to the powerset. In Proceedings of the International Logic Programming Symposium, Ithaca, NY, pages 655–669. The MIT Press, 1994.
P. Granger, Static analysis of linear congruence equalities among variables of a program, In Proceedings of the International Joint Conference on Theory and Practice of Software Development, pp. 169–192, number 493 in LNCS, 1991.
N. Halbwachs and Y.-E. Proy and P. Raymond, Verification of linear hybrid systems by means of convex approximations, In Proceedings of the International Static Analysis Symposium, pp. 223–237, number 864 in LNCS, 1994.
F. Masdupuy. Array operations abstractions using semantics analysis of trapezoid congruences. In Proceedings of the International Conference on Supercomputing, Washington, 1992.
A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Handjieva, M., Tzolovski, S. (1998). Refining Static Analyses by Trace-Based Partitioning Using Control Flow. In: Levi, G. (eds) Static Analysis. SAS 1998. Lecture Notes in Computer Science, vol 1503. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49727-7_12
Download citation
DOI: https://doi.org/10.1007/3-540-49727-7_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65014-0
Online ISBN: 978-3-540-49727-1
eBook Packages: Springer Book Archive