Article

Free access

Inference rules for program annotation

Authors:

Nachum Dershowitz,

Zohar MannaAuthors Info & Claims

ICSE '78: Proceedings of the 3rd international conference on Software engineering

Pages 158 - 167

Published: 10 May 1978 Publication History

Abstract

Methods are presented whereby an Algol-like program, given together with its specifications, can be documented automatically. The program is incrementally annotated with invariant relationships that hold between program variables at intermediate points in the program and explain the actual workings of the program regardless of whether the program is correct. Thus this documentation can be used for proving the correctness of the program or may serve as an aid in the debugging of an incorrect program.

The annotation techniques are formulated as Hoare-like inference rules which derive invariants from the assignment statements, from the control structure of the program, or, heuristically, from suggested invariants. The application of these rules is demonstrated by an example, one of a number that have run on an experimental implementation.

References

[1]

Caplain, M. {Apr. 1975},Finding invariant assertions for proving programs, Proc. Intl. Conf. on Reliable Software, Los Angeles, CA, pp. 165-171.

Digital Library

[2]

Dershowitz, N. and Z. Manna {Nov. 1977},The evolution of programs: Automatic program modification, IEEE Software Engineering, vol. SE-3, no. 6, pp. 377-385.

[3]

Elspas, B. {July 1974},The semiautomatic generation of inductive assertions for proving program correctness, interim report, SRI International, Menlo Park, CA.

[4]

Gerhart, S.L. {July 1975},Verification operator systems and their application to logical analysis of programs, Colloques IRIA on Proving and Improving Programs, Arc-et-Senans, France, pp. 209-221.

[5]

German, S.M. {May 1974},A program verifier that generates inductive assertions, Undergraduate thesis, Memo TR 19-74, Harvard Univ., Cambridge, MA.

[6]

German, S.M. {Jan. 1978},Automating proofs of the absence of common runtime errors, Proc. 5th Symp. on Principles of Programming Languages, Tucson, AZ, pp. 105-118.

Digital Library

[7]

German, S.M., and B. Wegbreit {Mar. 1975},A synthesizer of inductive assertions, IEEE Software Engineering, vol. SE-1, no. 1, pp. 68-75.

[8]

Gibb, A. {July 1961}, Algorithm 61: Procedures for range arithmetic, CACM, vol. 4, no. 7, pp. 319-320.

Digital Library

[9]

Greif, I. and R.J. Waldinger {Apr. 1974},A more mechanical heuristic approach to program verification, Proc. Intl. Symp. On Programming, Paris, France, pp. 83-90.

Digital Library

[10]

Harrison, W.H. {May 1977},Compiler analysis of the value ranges for variables, IEEE Software Engineering, vol, SE-3, no. 3, pp. 243-250.

[11]

Hoare, C.A.R. {Oct. 1969},An axiomatic basis of computer programming, CACM, vol. 12, no. 10, pp. 576-580, 583.

Digital Library

[12]

Katz, S.M. {Sept. 1976},Invariants and the logical analysis of programs, Ph.D. thesis, Weizmann Institute of Science, Rehovot, Israel.

[13]

Katz, S.M. and Z. Manna {Aug. 1973},A heuristic approach to program verification, |Adv. Papers Third Intl. Conf. on Artificial intelligence,# Stanford, CA, pp. 500-512.

[14]

Katz, S.M. and Z. Manna {Apr. 1976},Logical analysis of programs, CACM, vol. 19, no. 4, pp. 188-206.

Digital Library

[15]

Luckham, D.C. and N. Suzuki {1977},Proof of termination within a weak logic of programs, Acta Informatica, vol. 8, no. 1, pp. 21-36.

Digital Library

[16]

Misra, J. {July 1975},Relations uniformly conserved by a loop, Colloques IRIA on Proving and Improving Programs, Arc-et-Senans, France, pp. 71-80.

[17]

Moriconi, M.S. {Oct. 1974},Towards the interactive synthesis of assertions, Memo ATP-20, Automatic Theorem Proving Project, Univ. of Texas, Austin, TX.

[18]

Morris, J.H. and B. Wegbreit {Apr. 1977},subgoal induction, CACM, vol. 20, no. 4, pp. 209-222.

Digital Library

[19]

Scherlis, W. {May 1974},On the weak interpretation method for extracting program properties, Undergraduate thesis, Harvard Univ., Cambridge, MA.

[20]

Sintzoff, M. {Jan. 1972},Calculating properties of programs by valuations on specific models, Proc. Conf. on Proving Assertions About Programs, Las Cruces, NM, SIGPLAN Notices, vol. 7, no. 1, pp. 203-207.

Digital Library

[21]

Suzuki N. and K. Ishihata {Jan. 1977},Implementation of an array bound checker, Proc. Fourth Symp. on Principles of Programming Languages, Los Angeles, CA, pp. 132-143.

Digital Library

[22]

Tamir, M. {Aug 1976},ADI - Automatic derivation of invariants, Master's thesis, Welzmann Institute of Science, Rehovot, Israel.

[23]

Wegbreit, B. {Feb. 1974},The synthesis of loop predicates, CACM, vol. 17, no. 2, pp. 102-112.

Digital Library

[24]

Wegbreit, B. {Sept. 1975},Property extraction in well-founded property sets, IEEE Software Engineering, vol. SE-1, no. 3, pp. 270-285.

[25]

Wilber, B.M. {Mar. 1976},A QLISP reference manual, Tech. note 118, Artificial intelligence Center, SRI International, Menlo Park, CA.

Cited By

Nguyen TKapur DWeimer WForrest S(2014)DIGACM Transactions on Software Engineering and Methodology (TOSEM)10.1145/255678223:4(1-30)Online publication date: 5-Sep-2014
https://dl.acm.org/doi/10.1145/2556782
Nguyen TKapur DWeimer WForrest SGlinz MMurphy GPezzè M(2012)Using dynamic analysis to discover polynomial and array invariantsProceedings of the 34th International Conference on Software Engineering10.5555/2337223.2337304(683-693)Online publication date: 2-Jun-2012
https://dl.acm.org/doi/10.5555/2337223.2337304
Shen LWu MYang ZZeng ZSasaki TShirayanagi KKotsireas I(2009)Finding positively invariant sets of a class of nonlinear loops via curve fittingProceedings of the 2009 conference on Symbolic numeric computation10.1145/1577190.1577218(185-190)Online publication date: 3-Aug-2009
https://dl.acm.org/doi/10.1145/1577190.1577218
Show More Cited By

Index Terms

Inference rules for program annotation
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Control structures
      2. Language types
  2. Software organization and properties
    1. Software functional properties
      1. Correctness
2. Theory of computation
  1. Logic
    1. Proof theory
  2. Semantics and reasoning
    1. Program reasoning
      1. Invariants

Recommendations

Inference Rules for Program Annotation

Methods are presented whereby an Algol-like program given together with its specifications can be documented automatically. The program is incrementaly annotated with invariant relations that hold between program variables at intermediate points in the ...
Inference rules for program annotation
Weakest precondition based modelling and verification of a class of concurrent systems

A weakest precondition based modelling and verification technique for a class of concurrent systems is proposed. A system in this class is defined by a set of non-terminating interactive sequential processes. The constituent processes are allowed to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '78: Proceedings of the 3rd international conference on Software engineering

May 1978

348 pages

Sponsors

NBS: National Bureau of Standards
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS: Computer Society

Publisher

IEEE Press

Publication History

Published: 10 May 1978

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
312
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)8

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nguyen TKapur DWeimer WForrest S(2014)DIGACM Transactions on Software Engineering and Methodology (TOSEM)10.1145/255678223:4(1-30)Online publication date: 5-Sep-2014
https://dl.acm.org/doi/10.1145/2556782
Nguyen TKapur DWeimer WForrest SGlinz MMurphy GPezzè M(2012)Using dynamic analysis to discover polynomial and array invariantsProceedings of the 34th International Conference on Software Engineering10.5555/2337223.2337304(683-693)Online publication date: 2-Jun-2012
https://dl.acm.org/doi/10.5555/2337223.2337304
Shen LWu MYang ZZeng ZSasaki TShirayanagi KKotsireas I(2009)Finding positively invariant sets of a class of nonlinear loops via curve fittingProceedings of the 2009 conference on Symbolic numeric computation10.1145/1577190.1577218(185-190)Online publication date: 3-Aug-2009
https://dl.acm.org/doi/10.1145/1577190.1577218
Denney EFischer BSmaragdakis YSiek J(2008)Generating customized verifiers for automatically generated codeProceedings of the 7th international conference on Generative programming and component engineering10.1145/1449913.1449926(77-88)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449913.1449926
Denney EFischer BJarzabek SSchmidt DVeldhuizen T(2006)A generic annotation inference algorithm for the safety certification of automatically generated codeProceedings of the 5th international conference on Generative programming and component engineering10.1145/1173706.1173725(121-130)Online publication date: 22-Oct-2006
https://dl.acm.org/doi/10.1145/1173706.1173725

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents