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.
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
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
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
Search-based software engineering: Trends, techniques and applications
Harman, M., Mansouri, S. A., & Zhang, Y. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379787 · Cited by 777
Hovemeyer, D., & Pugh, W. (2004) · Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications · doi:10.1145/1028664.1028717 · Cited by 760
Bugs as deviant behavior: a general approach to inferring errors in systems code
Engler, D., Chen, D. Y., Hallem, S., Chou, A., & Chelf, B. (2001) · Proceedings of the eighteenth ACM symposium on Operating systems principles · doi:10.1145/502034.502041 · Cited by 737
Scalable statistical bug isolation
Liblit, B., Naik, M., Zheng, A. X., Aiken, A., & Jordan, M. I. (2005) · ACM SIGPLAN Notices · doi:10.1145/1064978.1065014 · Cited by 729
An overview of JML tools and applications
Burdy, L., Cheon, Y., Cok, D. R., Ernst, M. D., Kiniry, J. R., Leavens, G. T., Leino, K. R. M., & Poll, E. (2005) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-004-0167-4 · Cited by 714
Self-citationAmmons, G., Bodík, R., & Larus, J. R. (2002) · Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/503272.503275 · Cited by 665
Intrusion detection via static analysis
Wagner, D., & Dean, R. (2002) · Proceedings 2001 IEEE Symposium on Security and Privacy. S&P 2001 · doi:10.1109/secpri.2001.924296 · Cited by 647
Tracking down software bugs using automatic anomaly detection
Hangal, S., & Lam, M. S. (2002) · Proceedings/Proceedings - International Conference on Software Engineering · doi:10.1145/581339.581377 · Cited by 602
Locating causes of program failures
Cleve, H., & Zeller, A. (2005) · Proceedings of the 27th international conference on Software engineering - ICSE '05 · doi:10.1145/1062455.1062522 · Cited by 550
Isolating cause-effect chains from computer programs
Zeller, A. (2002) · Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering · doi:10.1145/587051.587053 · Cited by 530
Bug isolation via remote program sampling
Liblit, B., Aiken, A., Zheng, A. X., & Jordan, M. I. (2003) · ACM SIGPLAN Notices · doi:10.1145/780822.781148 · Cited by 504
Scalable statistical bug isolation
Liblit, B., Naik, M., Zheng, A. X., Aiken, A., & Jordan, M. I. (2005) · Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation · doi:10.1145/1065010.1065014 · Cited by 472
Li, Z., & Zhou, Y. (2005) · Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering · doi:10.1145/1081706.1081755 · Cited by 428
Automatic generation of software behavioral models
Lorenzoli, D., Mariani, L., & Pezzè, M. (2008) · Proceedings of the 13th international conference on Software engineering - ICSE '08 · doi:10.1145/1368088.1368157 · Cited by 416
Automatically patching errors in deployed software
Perkins, J. H., Kim, S., Larsen, S., Amarasinghe, S., Bachrach, J., Carbin, M., Pacheco, C., Sherwood, F., Sidiroglou, S., Sullivan, G., et al. (2009) · Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles · doi:10.1145/1629575.1629585 · Cited by 409
Self-citationEvolutionary testing of classes
Tonella, P. (2004) · Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis · doi:10.1145/1007512.1007528 · Cited by 410
Perracotta: mining temporal API rules from imperfect traces
Yang, J., Evans, D., Bhardwaj, D., Bhat, T., & Das, M. (2006) · Proceedings of the 28th international conference on Software engineering · doi:10.1145/1134285.1134325 · Cited by 406
Hovemeyer, D., & Pugh, W. (2004) · ACM SIGPLAN Notices · doi:10.1145/1052883.1052895 · Cited by 397
SOBER: statistical model-based bug localization
Liu, C., Yan, X., Fei, L., Han, J., & Midkiff, S. P. (2005) · Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering · doi:10.1145/1081706.1081753 · Cited by 357
DynaMine: finding common error patterns by mining software revision histories
Livshits, B., & Zimmermann, T. (2005) · Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering · doi:10.1145/1081706.1081754 · Cited by 330
Automatic Software Repair: A Survey
Gazzola, L., Micucci, D., & Mariani, L. (2019) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2017.2755013 · Cited by 327
Detection of False-Data Injection Attacks in Cyber-Physical DC Microgrids
Beg, O. A., Johnson, T. T., & Davoudi, A. (2017) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2017.2656905 · Cited by 297
Regression testing minimization, selection and prioritization: a survey
Yoo, S., & Harman, M. (2012) · Software Testing, Verification and Reliability · doi:10.1002/stvr.430 · Cited by 297
A Survey on Automated Log Analysis for Reliability Engineering
He, S., He, P., Chen, Z., Yang, T., Su, Y., & Lyu, M. R. (2022) · ACM Computing Surveys · doi:10.1145/3460345 · Cited by 334
From symptom to cause: localizing errors in counterexample traces
Ball, T., Naik, M., & Rajamani, S. K. (2003) · Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/604131.604140 · Cited by 294
Have things changed now?: an empirical study of bug characteristics in modern open source software
Li, Z., Tan, L., Wang, X., Lu, S., Zhou, Y., & Zhai, C. (2006) · Proceedings of the 1st workshop on Architectural and system support for improving software dependability · doi:10.1145/1181309.1181314 · Cited by 291
Statistical Debugging: A Hypothesis Testing-Based Approach
Liu, C., Fei, L., Yan, X., Han, J., & Midkiff, S. P. (2006) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2006.105 · Cited by 288
An Empirical Study of Fault Localization Families and Their Combinations
Zou, D., Liang, J., Xiong, Y., Ernst, M. D., & Zhang, L. (2021) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2019.2892102 · Cited by 270
Self-citationReverse Engineering Mobile Application User Interfaces with REMAUI (T)
Nguyen, T. A., & Csallner, C. (2015) · 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2015.32 · Cited by 200
Identifying patch correctness in test-based program repair
Xiong, Y., Liu, X., Zeng, M., Zhang, L., & Huang, G. (2018) · Proceedings of the 40th International Conference on Software Engineering · doi:10.1145/3180155.3180182 · Cited by 162
Inferring extended finite state machine models from software executions
Walkinshaw, N., Taylor, R., & Derrick, J. (2016) · Empirical Software Engineering · doi:10.1007/s10664-015-9367-7 · Cited by 127
Automatically Generating Test Cases for Specification Mining
Dallmeier, V., Knopp, N., Mallon, C., Fraser, G., Hack, S., & Zeller, A. (2012) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2011.105 · Cited by 67
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.