The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Simple relational correctness proofs for static analyses and program transformations
Abstract
We show how some classical static analyses for imperative programs, and the optimizing transformations which they enable, may be expressed and proved correct using elementary logical and denotationaltechniques. The key ingredients are an interpretation of program properties as relations, rather than predicates, and a realization that although many program analyses are traditionally formulated in very intensional terms, the associated transformations are actually enabled by more liberal extensional properties.We illustrate our approach with formal systems for analysing and transforming while-programs. The first is a simple type system which tracks constancy and dependency information and can be used to perform dead-code elimination, constant propagation and program slicing as well as capturing a form of secure information flow. The second is a relational version of Hoare logic, which significantly generalizes our first type system and can also justify optimizations including hoisting loop invariants. Finally we show how a simple available expression analysis and redundancy elimination transformation may be justified by translation into relational Hoare logic.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Compilers: Principles, Techniques, and Tools
Aho, A. V., Sethi, R., & Ullman, J. D. (1986) · Cited by 8,453
An axiomatic basis for computer programming
Hoare, C. A. R. (1969) · Communications of the ACM · doi:10.1145/363235.363259 · Cited by 4,002
Weiser, M. (1984) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1984.5010248 · Cited by 3,204
A sound type system for secure flow analysis
Volpano, D., Irvine, C., & Smith, G. (1996) · Journal of Computer Security · doi:10.3233/jcs-1996-42-304 · Cited by 969
A unified approach to global program optimization
Kildall, G. A. (1973) · Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '73 · doi:10.1145/512927.512945 · Cited by 916
Flow Analysis of Computer Programs
Hecht, M. S. (1977) · Cited by 724
Translation validation for an optimizing compiler
Necula, G. C. (2000) · Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation · doi:10.1145/349299.349314 · Cited by 488
Abadi, M., Banerjee, A., Heintze, N., & Riecke, J. G. (1999) · Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/292540.292555 · Cited by 413
Secure information flow in a multi-threaded imperative language
Smith, G., & Volpano, D. (1998) · Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '98 · doi:10.1145/268946.268975 · Cited by 406
A Per Model of Secure Information Flow in Sequential Programs
Sabelfeld, A., & Sands, D. (2001) · Higher-Order and Symbolic Computation · doi:10.1023/a:1011553200337 · Cited by 172
Secure information flow and pointer con .nement in a java-like language
Banerjee, A., & Naumann, D. A. (2005) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csfw.2002.1021820 · Cited by 147
A sound type system for secure flow analysis
VolpanoDennis, IrvineCynthia, & SmithGeoffrey (1996) · Journal of Computer Security · doi:10.5555/353629.353648 · Cited by 146
Automatically proving the correctness of compiler optimizations
Lerner, S., Millstein, T. D., & Chambers, C. (2003) · ACM SIGPLAN Notices · doi:10.1145/780822.781156 · Cited by 114
Certification of Compiler Optimizations Using Kleene Algebra with Tests
Kozen, D. C., & Patron, M.-C. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44957-4_38 · Cited by 100
Proving correctness of compiler optimizations by temporal logic
Lacey, D., Jones, N. D., Wyk, E. V., & Frederiksen, C. C. (2002) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/503272.503299 · Cited by 98
Automatically proving the correctness of compiler optimizations
Lerner, S., Millstein, T. D., & Chambers, C. (2003) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/781131.781156 · Cited by 88
VOC: A methodology for the translation validation of optimizing compilers
Zuck, L. D., Pnueli, A., Fang, Y., & Goldberg, B. (2003) · Cited by 82
Lightweight closure conversion
Steckler, P. A., & Wand, M. (1997) · ACM Transactions on Programming Languages and Systems · doi:10.1145/239912.239915 · Cited by 70
Binding time analysis: a new PERspective
Hunt, S., & Sands, D. (1991) · ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM) · doi:10.1145/115865.115881 · Cited by 62
Cited by
Formal certification of code-based cryptographic proofs
Barthe, G., Grégoire, B., & Zanella Béguelin, S. (2009) · Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1480881.1480894 · Cited by 268
seL4: From General Purpose to a Proof of Information Flow Enforcement
Murray, T., Matichuk, D., Brassil, M., Gammie, P., Bourke, T., Seefried, S., Lewis, C., Gao, X., & Klein, G. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.35 · Cited by 205
Semantic program alignment for equivalence checking
Churchill, B., Padon, O., Sharma, R., & Aiken, A. (2019) · Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3314221.3314596 · Cited by 97
Smith, C., & Albarghouthi, A. (2016) · Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2908080.2908102 · Cited by 76
Wang, Y., Wang, X., & Dillig, I. (2018) · Proceedings of the ACM on Programming Languages · doi:10.1145/3276525 · Cited by 17
Metadata
- Authors
- Benton, N.
- Venue
- Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages
- Publisher
- ACM
- Published
- 2004-01
- Pages
- 14-25
- OpenAlex
- W2149996206
- Cited by
- 356
- References
- 19
- FWCI
- 7.37
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.