Dynamically discovering likely program invariants to support program evolution

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamically discovering likely program invariants to support program evolution

Full text

Pdf (1.59 MB)

Source

International Conference on Software Engineering archive
Proceedings of the 21st international conference on Software engineering table of contents

Los Angeles, California, United States

Pages: 213 - 224

Year of Publication: 1999

ISBN:1-58113-074-0

Authors

Michael D. Ernst	Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA
Jake Cockrell	Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA
William G. Griswold	Dept. of Computer Science & Engineering, University of California San Diego, 0114, La Jolla, CA
David Notkin	Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA

Sponsors

IEEE-CS : Computer Society
IEEE-CS\TCSE : TC on Software Engineering
SIGADA: ACM Special Interest Group on Ada Programming Language
SIGSOFT: ACM Special Interest Group on Software Engineering
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 107, Citation Count: 43

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/302405.302467 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	And98	J. Andrews, Testing using Log File Analysis: Tools, Methods, and Issues, Proceedings of the 13th IEEE international conference on Automated software engineering, p.157, October 13-16, 1998
	BBM97	Nikolaj Bjørner , Anca Browne , Zohar Manna, Automatic generation of invariants and intermediate assertions, Theoretical Computer Science, v.173 n.1, p.49-87, Feb. 1997 [doi>10.1016/S0304-3975(96)00191-0]
	BG93	Ivan Bratko , Marko Grobelnik, Inductive Learning Applied to Program Construction and Verification, Extended Papers from the IFIP TC12 Workshop on Artificial Intelligence from the Information Processing Perspective: Knowledge Oriented Software Design, p.169-182, September 14-15, 1992
	BG97	Bernard Boigelot , Patrice Godefroid, Automatic Synthesis of Specifications from the Dynamic Observation of Reactive Programs, Proceedings of the Third International Workshop on Tools and Algorithms for Construction and Analysis of Systems, p.321-333, April 02-04, 1997
	BLS96	Saddek Bensalem , Yassine Lakhnech , Hassen Saïdi, Powerful Techniques for the Automatic Generation of Invariants, Proceedings of the 8th International Conference on Computer Aided Verification, p.323-335, August 03, 1996
	CC77	Patrick Cousot , Radhia Cousot, Automatic synthesis of optimal invariant assertions: Mathematical foundations, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.1-12, August 15-17, 1977
	Coh94	William W. Cohen, Grammatically biased learning: learning logic programs using an explicit antecedent description language, Artificial Intelligence, v.68 n.2, p.303-366, Aug. 1994 [doi>10.1016/0004-3702(94)90070-1]
	CW98a	Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
	CW98b	Jonathan E. Cook , Alexander L. Wolf, Event-based detection of concurrency, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.35-45, November 01-05, 1998, Lake Buena Vista, Florida, United States
	DB84	Douglas D. Dunlop , Victor R. Basili, A heuristic for deriving loop functions, IEEE Transactions on Software Engineering, v.10 n.3, p.275-285, May 1984 [doi>10.1109/TSE.1984.5010236]
	DC94	Matthew B. Dwyer , Lori A. Clarke, Data flow analysis for verifying properties of concurrent programs, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.62-75, December 06-09, 1994, New Orleans, Louisiana, United States
	Det96	David L. Detlefs. An overview of the Extended Static Checking system. In First Workshop on Formal Methods in Software Practice, pages 1-9, January 1996.
	EDG95	Edison Design Group. C++ Front End Xnternal Documentalion, version 2.28 edition, March 1995. http://www.edg.com.
	EGHT94	David Evans , John Guttag , James Horning , Yang Meng Tan, LCLint: a tool for using specifications to check code, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.87-96, December 06-09, 1994, New Orleans, Louisiana, United States
	Eva96	David Evans, Static detection of dynamic memory errors, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.44-53, May 21-24, 1996, Philadelphia, Pennsylvania, United States
	GC96	Gerald C. GannodandBetty H.C. Cheng. Strongest postcondition semantics as the formal basis for reverse engineering. Journal of Automated Software Engineering, 3(1/2):139-164, June 1996.
	GH96	Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
	Giv96	Robert Givan, Inferring Program Specifications in Polynomial-Time, Proceedings of the Third International Symposium on Static Analysis, p.205-219, September 24-26, 1996
	Gri81	David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	Gup90	Rajiv Gupta, A fresh look at optimizing array bound checking, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.272-282, June 1990, White Plains, New York, United States
	GW75	Steven M. German and Ben Wegbreit. A synthesizer of inductiveassertions. IEEE Transactions on Software Engineering, 1(1):68-75, March 1975.
	HFGO94	Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
	HHN92	Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.249-260, June 15-19, 1992, San Francisco, California, United States
	HRWY98	Mary Jean Harrold , Gregg Rothermel , Rui Wu , Liu Yi, An empirical investigation of program spectra, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.83-90, June 16-16, 1998, Montreal, Quebec, Canada
	HWF90	Robert R. Henry , Kenneth M. Whaley , Bruce Forstall, The University of Washington illustrating compiler, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.223-233, June 1990, White Plains, New York, United States
	JGS93	Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	JH98	Ralph Jeffords , Constance Heitmeyer, Automatic generation of state invariants from requirements specifications, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.56-69, November 01-05, 1998, Lake Buena Vista, Florida, United States
	JvH+98	Bart Jacobs , Joachim van den Berg , Marieke Huisman , Martijn van Berkum , U. Hensel , H. Tews, Reasoning about Java classes: preliminary report, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.329-340, October 18-22, 1998, Vancouver, British Columbia, Canada
	KM76	Shmuel Katz , Zohar Manna, Logical analysis of programs, Communications of the ACM, v.19 n.4, p.188-206, April 1976 [doi>10.1145/360032.360048]
	KW95	Priyadarshan Kolte , Michael Wolfe, Elimination of redundant array subscript range checks, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.270-278, June 18-21, 1995, La Jolla, California, United States
	LN98	K. Rustan M. Leino , Greg Nelson, An Extended Static Checker for Modular-3, Proceedings of the 7th International Conference on Compiler Construction, p.302-305, March 28-April 04, 1998
	Mit97	Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
	NCOD97	Gleb Naumovich , Lori A. Clarke , Leon J. Osterweil , Matthew B. Dwyer, Verification of concurrent software with FLAVERS, Proceedings of the 19th international conference on Software engineering, p.594-595, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253489]
	NL98	George C. Necula , Peter Lee, The design and implementation of a certifying compiler, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.333-344, June 17-19, 1998, Montreal, Quebec, Canada
	OJ97	Robert O'Callahan , Daniel Jackson, Lackwit: a program understanding tool based on type inference, Proceedings of the 19th international conference on Software engineering, p.338-348, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253351]
	Pfe92	Frank Pfeting. Dependent types in logic programming. In Types in Logic Programming, chapter 10, pages 285-311. MIT Press, Cambridge, MA, 1992.
	Qui90	Pat Langley, Editorial: Advice to Machine Learning Authors, Machine Learning, v.5 n.3, p.233-237, Aug. 1990 [doi>10.1023/A:1022647305786]
	RBDL97	Thomas Reps , Thomas Ball , Manuvir Das , James Larus, The use of program profiling for software maintenance with applications to the year 2000 problem, Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.432-449, September 22-25, 1997, Zurich, Switzerland
	RH98	Gregg Rothermel , Mary Jean Harrold, Empirical Studies of a Safe Regression Test Selection Technique, IEEE Transactions on Software Engineering, v.24 n.6, p.401-419, June 1998 [doi>10.1109/32.689399]
	SI77	Norihisa Suzuki , Kiyoshi Ishihata, Implementation of an array bound checker, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.132-143, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512963]
	van97	Guido van Rossum. Python Reference Manual, release 1.5 edition, December 1997.
	War96	Martin P. Ward. Program analysis by formal transformation. The Compuler Journal, 39(7):598-618,1996.
	Weg74	Ben Wegbreit, The synthesis of loop predicates, Communications of the ACM, v.17 n.2, p.102-113, Feb. 1974 [doi>10.1145/360827.360850]
	XP98	Hongwei Xi , Frank Pfenning, Eliminating array bound checking through dependent types, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.249-257, June 17-19, 1998, Montreal, Quebec, Canada

CITED BY 43

	Michael Ernst, Research summary for dynamic detection of program invariants, Proceedings of the 21st international conference on Software engineering, p.718-719, May 16-22, 1999, Los Angeles, California, United States
	Harold Ossher , William Harrison , Peri Tarr, Software engineering tools and environments: a roadmap, Proceedings of the Conference on The Future of Software Engineering, p.261-277, June 04-11, 2000, Limerick, Ireland
	Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-Mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, ACM SIGPLAN Notices, v.35 n.11, p.222-233, Nov. 2000
	Thoms Bell, The concept of dynamic analysis, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.216-234, Nov. 1999
	Mary Jean Harrold, Testing: a roadmap, Proceedings of the Conference on The Future of Software Engineering, p.61-72, June 04-11, 2000, Limerick, Ireland
	Amir Michail, Data mining library reuse patterns using generalized association rules, Proceedings of the 22nd international conference on Software engineering, p.167-176, June 04-11, 2000, Limerick, Ireland
	Axel van Lamsweerde, Formal specification: a roadmap, Proceedings of the Conference on The Future of Software Engineering, p.147-159, June 04-11, 2000, Limerick, Ireland
	Steven P. Reiss , Manos Renieris, Encoding program executions, Proceedings of the 23rd International Conference on Software Engineering, p.221-230, May 12-19, 2001, Toronto, Ontario, Canada
	John Whaley , Michael C. Martin , Monica S. Lam, Automatic extraction of object-oriented component interfaces, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
	Michael Harder , Jeff Mellen , Michael D. Ernst, Improving test suites via operational abstraction, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
	Jeremy W. Nimmer , Michael D. Ernst, Invariant inference for static checking:, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
	Jeremy W. Nimmer , Michael D. Ernst, Invariant inference for static checking: an empirical evaluation, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002
	David Evans , David Larochelle, Improving Security Using Extensible Lightweight Static Analysis, IEEE Software, v.19 n.1, p.42-51, January 2002
	Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001
	Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, ACM SIGOPS Operating Systems Review, v.34 n.5, p.222-233, Dec. 2000
	Adrian Birka , Michael D. Ernst, A practical type system and language for reference immutability, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Cormac Flanagan , K. Rustan M. Leino , Mark Lillibridge , Greg Nelson , James B. Saxe , Raymie Stata, Extended static checking for Java, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Christoph Csallner , Yannis Smaragdakis, Check 'n' crash: combining static checking and testing, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA
	Valentin Dallmeier , Christian Lindig , Andreas Zeller, Lightweight bug localization with AMPLE, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.99-104, September 19-21, 2005, Monterey, California, USA
	Margaret Burnett , Curtis Cook , Omkar Pendse , Gregg Rothermel , Jay Summet , Chris Wallace, End-user software engineering with assertions in the spreadsheet paradigm, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
	Stephen McCamant , Michael D. Ernst, Predicting problems caused by component upgrades, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003
	Brian Demsky , Michael D. Ernst , Philip J. Guo , Stephen McCamant , Jeff H. Perkins , Martin Rinard, Inference and enforcement of data structure consistency specifications, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	Jennifer B. Sartor , Martin Hirzel , Kathryn S. McKinley, No bit left behind: the limits of heap data compression, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Rui Abreu , Alberto González , Peter Zoeteweij , Arjan J. C. van Gemund, Automatic software fault localization using generic program invariants, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Pin Zhou , Wei Liu , Long Fei , Shan Lu , Feng Qin , Yuanyuan Zhou , Samuel Midkiff , Josep Torrellas, AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-Based Invariants, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.269-280, December 04-08, 2004, Portland, Oregon
	Christoph Csallner , Nikolai Tillmann , Yannis Smaragdakis, DySy: dynamic symbolic execution for invariant inference, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany
	Satish Chandra , Jackie de Vries , John Field , Howard Hess , Manivannan Kalidasan , Komondoor V. Raghavan , Frans Nieuwerth , Ganesan Ramalingam , Justin Xue, Using logical data models for understanding and transforming legacy business applications, IBM Systems Journal, v.45 n.3, p.647-655, July 2006
	Marat Boshernitsan , Roongko Doong , Alberto Savoia, From daikon to agitator: lessons and challenges in building a commercial tool for developer testing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	Sebastian Elbaum , Kalyan-Ram Chilakamarri , Marc Fisher, II , Gregg Rothermel, Web application characterization through directed requests, Proceedings of the 2006 international workshop on Dynamic systems analysis, May 23-23, 2006, Shanghai, China
	Piramanayagam Arumuga Nainar , Ting Chen , Jake Rosin , Ben Liblit, Statistical debugging using compound boolean predicates, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom
	Giuliano Antoniol , Yann-Gael Gueheneuc, Feature Identification: An Epidemiological Metaphor, IEEE Transactions on Software Engineering, v.32 n.9, p.627-641, September 2006
	Asuman Sünbül , Herbert Weber , Julia Padberg, Evolutionary Development Of Business Process Centered Architectures Using Component Technologies, Journal of Integrated Design & Process Science, v.5 n.3, p.13-24, August 2001
	F. Clauss , I. Yu. Chupaeva, Application of Symbolic Approach to the Bernstein Expansion for Program Analysis and Optimization, Programming and Computing Software, v.30 n.3, p.164-172, May-June 2004
	Orna Raz , Mary Shaw, An Approach to Preserving Sufficient Correctness in Open Resource Coalitions, Proceedings of the 10th International Workshop on Software Specification and Design, p.159, November 05-07, 2000
	Barthélémy Dagenais , Silvia Breu , Frédéric Weigand Warr , Martin P. Robillard, Inferring structural patterns for concern traceability in evolving software, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA
	Rylan Cottrell , Joseph J. C. Chang , Robert J. Walker , Jörg Denzinger, Determining detailed structural correspondence for generalization tasks, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia
	Sagar Chaki , Ofer Strichman, Three optimizations for Assume---Guarantee reasoning with L*, Formal Methods in System Design, v.32 n.3, p.267-284, June 2008
	Alexey Loginov , Eran Yahav , Satish Chandra , Stephen Fink , Noam Rinetzky , Mangala Nanda, Verifying dereference safety via expanding-scope analysis, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	Alex Groce , Rajeev Joshi, Random testing and model checking: building a common framework for nondeterministic exploration, Proceedings of the 2008 international workshop on dynamic analysis: held in conjunction with the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2008), July 21-21, 2008, Seattle, Washington
	Christian Murphy, Using runtime testing to detect defects in applications without test oracles, Proceedings of the 2008 Foundations of Software Engineering Doctoral Symposium, p.21-24, November 10-10, 2008, Atlanta, Georgia
	Shay Artzi , Adam Kieżun , Jaime Quinonez , Michael D. Ernst, Parameter reference immutability: formal definition, inference tool, and comparison, Automated Software Engineering, v.16 n.1, p.145-192, March 2009
	Nicolas Baskiotis , Michèle Sebag , Marie-Claude Gaudel , Sandrine Gouraud, A machine learning approach for statistical software testing, Proceedings of the 20th international joint conference on Artifical intelligence, p.2274-2279, January 06-12, 2007, Hyderabad, India
	Christian Murphy , Kuang Shen , Gail Kaiser, Automatic system testing of programs without test oracles, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA