The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Dynamically discovering likely program invariants to support program evolution
Abstract
Explicitly stated program invariants can help programmers by identifying program properties that must be preserved when modifying code. In practice, however, these invariants are usually implicit. An alternative to expecting programmers to fully annotate code with invariants is to automatically infer likely invariants from the program itself. This research focuses on dynamic techniques for discovering invariants from execution traces. This article reports three results. First, it describes techniques for dynamically discovering invariants, along with an implementation, named Daikon, that embodies these techniques. Second, it reports on the application of Daikon to two sets of target programs. In programs from Gries's work (1981) on program derivation, the system rediscovered predefined invariants. In a C program lacking explicit invariants, the system discovered invariants that assisted a software evolution task. These experiments demonstrate that, at least for small programs, invariant inference is both accurate and useful. Third, it analyzes scalability issues, such as invariant detection runtime and accuracy, as functions of test suites and program points instrumented.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Dijkstra, E. W. (1976) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,733
An axiomatic basis for computer programming
Hoare, C. A. R. (1969) · Communications of the ACM · doi:10.1145/363235.363259 · Cited by 4,002
Representation of Events in Nerve Nets and Finite Automata
Kleene, S. C. (1956) · Automata Studies. (AM-34) · doi:10.1515/9781400882618-002 · Cited by 1,655
Learning Logical Definitions from Relations
Quinlan, J. R. (1990) · Machine Learning · doi:10.1023/a:1022699322624 · Cited by 1,644
Partial evaluation and automatic program generation
Jones, N. D., Gomard, C. K., & Sestoft, P. (1993) · Medical Entomology and Zoology · Cited by 1,440
Gries, D. (1981) · Springer eBooks · doi:10.1007/978-1-4612-5983-1 · Cited by 1,433
Formal Methods: State of the Art and Future Directions
Clarke, E., Wing, J. M., & Jones, C. B. (1996) · doi:10.25405/ncl.34123050 · Cited by 1,122
Discovering models of software processes from event-based data
Cook, J. E., & Wolf, A. L. (1998) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/287000.287001 · Cited by 870
Experiments on the effectiveness of dataflow- and control-flow-based test adequacy criteria
Hutchins, M., Foster, H. D., Goradia, T., & Ostrand, T. J. (1994) · doi:10.5555/257734.257766 · Cited by 774
Formal methods: state of the art and future directions
Clarke, E. M., & Wing, J. M. (1996) · ACM Computing Surveys · doi:10.1145/242223.242257 · Cited by 763
Dependent types in practical programming
Xi, H., & Pfenning, F. (1999) · Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/292540.292560 · Cited by 575
Abstraction and Specification in Program Development
Liskov, B. H., & Guttag, J. V. (1986) · CERN Document Server (European Organization for Nuclear Research) · Cited by 545
Efficient context-sensitive pointer analysis for C programs
Wilson, R. P., & Lam, M. S. (1995) · Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation · doi:10.1145/207110.207111 · Cited by 458
Leino, K. R. M. (1998) · Programming Concepts and Methods PROCOMET ’98 · doi:10.1007/978-0-387-35358-6_1 · Cited by 393
Experiments on the effectiveness of dataflow- and control-flow-based test adequacy criteria
Hutchins, M., Foster, H., Goradia, T., & Ostrand, T. (2002) · Proceedings of 16th International Conference on Software Engineering · doi:10.1109/icse.1994.296778 · Cited by 375
The design and implementation of a certifying compiler
Necula, G. C., & Lee, P. (1998) · Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation · doi:10.1145/277650.277752 · Cited by 358
Dynamically discovering likely program invariants to support program evolution
Ernst, M. D., Cockrell, J., Griswold, W. G., & Notkin, D. S. (1999) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/302405.302467 · Cited by 357
Self-citationA practical approach to programming with assertions
Rosenblum, D. S. (1995) · IEEE Transactions on Software Engineering · doi:10.1109/32.341844 · Cited by 334
Analysis of pointers and structures
Chase, D. R., Wegman, M., & Zadeck, F. K. (1990) · Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation - PLDI '90 · doi:10.1145/93542.93585 · Cited by 303
Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C
Ghiya, R., & Hendren, L. J. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237724 · Cited by 287
Eliminating array bound checking through dependent types
Xi, H., & Pfenning, F. (1998) · Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation · doi:10.1145/277650.277732 · Cited by 284
Software reliability via run-time result-checking
Wasserman, H., & Blum, M. (1997) · Journal of the ACM · doi:10.1145/268999.269003 · Cited by 192
An empirical investigation of program spectra
Harrold, M. J., Rothermel, G., Wu, R., & Yi, L. (1998) · Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering · doi:10.1145/277631.277647 · Cited by 164
Liao, S.-W., Ζ, A. D., Bosch, R. P., Ghuloum, A. M., & Lam, M. S. (1999) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/301104.301108 · Cited by 151
Machine Learning: A Guide to Current Research
Mitchell, T. M., Carbonell, J. G., & Michalski, R. S. (1986) · Kluwer international series in engineering and computer science · doi:10.1007/978-1-4613-2279-5 · Cited by 143
Katz, S. M., & Manna, Z. (1976) · Communications of the ACM · doi:10.1145/360032.360048 · Cited by 137
When only random testing will do
Hamlet, D. (2006) · doi:10.1145/1145735.1145737 · Cited by 106
Automatic synthesis of optimal invariant assertions: Mathematical foundations
Cousot, P. M., & Cousot, R. (1977) · Symposium on Artificial Intelligence and Programming Languages · doi:10.1145/800228.806926 · Cited by 106
Testing using log file analysis: tools, methods, and issues
Andrews, J. H. (2002) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.1998.732614 · Cited by 93
Cohen, W. W. (1994) · Artificial Intelligence · doi:10.1016/0004-3702(94)90070-1 · Cited by 85
A fresh look at optimizing array bound checking
Gupta, R. (1990) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/93542.93581 · Cited by 77
The use of program profiling for software maintenance with applications to the year 2000 problem
Reps, T., Ball, T., Das, M., & Larus, J. R. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63531-9_29 · Cited by 57
The Maintainer's Assistant (software tool)
Ward, W., Calliss, F. W., & Munro, M. (2003) · IEEE International Conference on Software Maintenance (ICSM) · doi:10.1109/icsm.1989.65225 · Cited by 56
Inductive Learning Applied to Program Construction and Verification
Bratko, I., & Grobelnik, M. (1992) · Cited by 36
Cited by
Regression testing minimization, selection and prioritization: a survey
Yoo, S., & Harman, M. (2012) · Software Testing, Verification and Reliability · doi:10.1002/stv.430 · Cited by 1,322
A Survey on Software Fault Localization
Wong, W. E., Gao, R., Li, Y., Abreu, R., & Wotawa, F. (2016) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2016.2521368 · Cited by 1,110
The oracle problem in software testing: A survey
Barr, E. T., Harman, M., McMinn, P., Shahbaz, M., & Yoo, S. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2014.2372785 · Cited by 1,104
The Daikon system for dynamic detection of likely invariants
Ernst, M. D., Perkins, J. H., Guo, P. J., McCamant, S., Pacheco, C., Tschantz, M. S., & Xiao, C. (2007) · Science of Computer Programming · doi:10.1016/j.scico.2007.01.015 · Cited by 1,080
Self-citationPreliminary design of JML: a behavioral interface specification language for java
Leavens, G. T., Baker, A. L., & Ruby, C. (2006) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/1127878.1127884 · Cited by 790
Metadata
- Authors
- Ernst, M. D., Cockrell, J., Griswold, W. G., & Notkin, D.
- Venue
- IEEE Transactions on Software Engineering
- Published
- 2001-02
- Volume
- 27
- Issue
- 2
- Pages
- 99-123
- ISSN
- 0098-5589 (ISSN-L)
- 1939-3520
- 2326-3881
- OpenAlex
- W3106729728
- Cited by
- 1,050
- References
- 34
- FWCI
- 141.75
- Type
- journal article
- 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.