Automatic extraction of object-oriented component interfaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Automatic extraction of object-oriented component interfaces

Full text

Pdf (248 KB)

Source

International Symposium on Software Testing and Analysis archive
Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis table of contents

Roma, Italy

SESSION: Dynamic analysis table of contents

Pages: 218 - 228

Year of Publication: 2002

ISBN ~ ISSN:0163-5948 , 1-58113-562-9

Also published in ...

Authors

John Whaley	Stanford University
Michael C. Martin	Stanford University
Monica S. Lam	Stanford University

Sponsor

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 100, Citation Count: 50

Additional Information:

abstract references cited by collaborative colleagues

Tools and Actions:	Request Permissions 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/566172.566212 What is a DOI?

ABSTRACT

Component-based software design is a popular and effective approach to designing large systems. While components typically have well-defined interfaces, sequencing information---which calls must come in which order---is often not formally specified.This paper proposes using multiple finite statemachine (FSM) submodels to model the interface of a class. A submodel includes a subset of methods that, for example, implement a Java interface, or access some particular field. Each state-modifying method is represented as a state in the FSM, and transitions of the FSMs represent allow able pairs of consecutive methods. In addition, state-preserving methods are constrained to execute only under certain states.We have designed and implemented a system that includes static analyses to deduce illegal call sequences in a program, dynamic instrumentation techniques to extract models from execution runs, and a dynamic model checker that ensures that the code conforms to the model. Extracted models can serve as documentation; they can serve as constraints to be enforced by a static checker; they can be studied directly by developers to determine if the program is exhibiting unexpected behavior; or they can be used to determine the completeness of a test suite.Our system has been run on several large code bases, including the joeq virtual machine, the basic Java libraries, and the Java 2 Enterprise Edition library code. Our experience suggests that this approach yields useful information.

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.

	1	Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
	2	Thomas Ball , Sriram K. Rajamani, Automatically validating temporal safety properties of interfaces, Proceedings of the 8th international SPIN workshop on Model checking of software, p.103-122, May 2001, Toronto, Ontario, Canada
	3	William R. Bush , Jonathan D. Pincus , David J. Sielaff, A static analyzer for finding dynamic programming errors, Software—Practice & Experience, v.30 n.7, p.775-802, June 2000 [doi>10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H]
	4	A. N. Habermann R. H. Campbell. The specification of process synchronization by path expressions. Lecture Notes on Computer Science, 16, 1974.
	5	Andy Chou , Benjamin Chelf , Dawson Engler , Mark Heinrich, Using meta-level compilation to check FLASH protocol code, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.59-70, November 2000, Cambridge, Massachusetts, United States
	6	M. Dahm. Byte code engineering library. http://bcel.sourceforge.net, 2000.
	7	Robert DeLine , Manuel Fähndrich, Enforcing high-level protocols in low-level software, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.59-69, June 2001, Snowbird, Utah, United States
	8	D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the Symposium on Operating Systems Design and Implementation, pages 1-16, 2000.
	9	Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically discovering likely program invariants to support program evolution, Proceedings of the 21st international conference on Software engineering, p.213-224, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302467]
	10	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	11	Jean-Yves Girard, Linear logic, Theoretical Computer Science, v.50 n.1, p.1-102, Jan. 30, 1987 [doi>10.1016/0304-3975(87)90045-4]
	12	Georg Gottlob , Michael Schrefl , Brigitte Röck, Extending object-oriented systems with roles, ACM Transactions on Information Systems (TOIS), v.14 n.3, p.268-296, July 1996 [doi>10.1145/230538.230540]
	13	Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
	14	M. Van Hilst and D. Notkin. Using C++ templates to implement role-based designs. Technical Report TR 95-07-02, Department of Computer Science and Engineering, University of Washington, 1996.
	15	Viktor Kuncak , Patrick Lam , Martin Rinard, Role analysis, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.17-32, January 16-18, 2002, Portland, Oregon
	16	David Lie , Andy Chou , Dawson Engler , David L. Dill, A simple method for extracting models for protocol code, Proceedings of the 28th annual international symposium on Computer architecture, p.192-203, June 30-July 04, 2001, Göteborg, Sweden
	17	J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73564]
	18	Sun Microsystems. Java 2 platform, enterprise edition. http://java.sun.com/j2ee/, 2001.
	19	Sun Microsystems. Petstore application for the java 2 platform, enterprise edition. http://java.sun.com/features/2001/05/petstore.html, 2001.
	20	J. Nimmer and M. Ernst. Static verification of dynamically detected program invariants: Integrating Daikon and ESC/Java. In Electronic Notes in Theoretical Computer Science, volume 55, 2001.
	21	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
	22	R. E. Strom , D. M. Yellin, Extending Typestate Checking Using Conditional Liveness Analysis, IEEE Transactions on Software Engineering, v.19 n.5, p.478-485, May 1993 [doi>10.1109/32.232013]
	23	R E Strom , S Yemini, Typestate: A programming language concept for enhancing software reliability, IEEE Transactions on Software Engineering, v.12 n.1, p.157-171, Jan. 1986
	24	P. Wadler. Linear types can change the world. In M. Broy and C. B. Jones, editors, IFIP TC 2 Working Conference on Programming Concepts and Methods, pages 561-581, 1990.
	25	J. Whaley. The joeq virtual machine. http://sourceforge.net/projects/joeq, 2001.
	26	R. Wiebicke. Linkverify. http://rw7.de/ralf/htmltools/index.en.html, 1998.
	27	Zhichen Xu , Thomas W. Reps , Barton P. Miller, Typestate Checking of Machine Code, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.335-351, April 02-06, 2001

CITED BY 50

	John Whaley, Joeq: a virtual machine and compiler infrastructure, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.58-66, June 12-12, 2003, San Diego, California
	Jeff H. Perkins , Michael D. Ernst, Efficient incremental algorithms for dynamic detection of likely invariants, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	Jinlin Yang , David Evans, Dynamically inferring temporal properties, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA
	Rajeev Alur , Pavol Černý , P. Madhusudan , Wonhong Nam, Synthesis of interface specifications for Java classes, ACM SIGPLAN Notices, v.40 n.1, p.98-109, January 2005
	Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar, Permissive interfaces, ACM SIGSOFT Software Engineering Notes, v.30 n.5, September 2005
	Patrice Godefroid , Nils Klarlund , Koushik Sen, DART: directed automated random testing, ACM SIGPLAN Notices, v.40 n.6, June 2005
	Antonia Bertolino , Andrea Polini, A framework for component deployment testing, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
	Mangala Gowri Nanda , Christian Grothoff , Satish Chandra, Deriving object typestates in the presence of inter-object references, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Michael Martin , Benjamin Livshits , Monica S. Lam, Finding application errors and security flaws using PQL: a program query language, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Benjamin Livshits , Thomas Zimmermann, DynaMine: finding common error patterns by mining software revision histories, ACM SIGSOFT Software Engineering Notes, v.30 n.5, September 2005
	Thomas Eisenbarth , Rainer Koschke , Gunther Vogel, Static object trace extraction for programs with pointers, Journal of Systems and Software, v.77 n.3, p.263-284, September 2005
	Hai Yuan , Tao Xie, Substra: a framework for automatic generation of integration tests, Proceedings of the 2006 international workshop on Automation of software test, May 23-23, 2006, Shanghai, China
	Jinlin Yang , David Evans , Deepali Bhardwaj , Thirumalesh Bhat , Manuvir Das, Perracotta: mining temporal API rules from imperfect traces, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Oksana Tkachuk , Sreeranga P. Rajan, Application of automated environment generation to commercial software, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	Valentin Dallmeier , Christian Lindig , Andrzej Wasylkowski , Andreas Zeller, Mining object behavior with ADABU, Proceedings of the 2006 international workshop on Dynamic systems analysis, May 23-23, 2006, Shanghai, China
	Graham Hughes , Tevfik Bultan , Muath Alkhalaf, Client and server verification for web services using interface grammars, Proceedings of the 2008 workshop on Testing, analysis, and verification of web services and applications, p.40-46, July 21-21, 2008, Seattle, Washington
	Stephen J. Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.17 n.2, p.1-34, April 2008
	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
	Evan Martin , Tao Xie, Understanding software application interfaces via string analysis, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Stephen Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	Westley Weimer, Patches as better bug reports, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA
	Inbal Ronen , Nurit Dor , Sara Porat , Yael Dubinsky, Combined static and dynamic analysis for inferring program dependencies using a pattern language, Proceedings of the 2006 conference of the Center for Advanced Studies on Collaborative research, October 16-19, 2006, Toronto, Ontario, Canada
	John Whaley, Joeq: a virtual machine and compiler infrastructure, Science of Computer Programming, v.57 n.3, p.339-356, September 2005
	Chang Liu , En Ye , Debra J. Richardson, LtRules: an automated software library usage rule extraction tool, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Tao Xie , Evan Martin , Hai Yuan, Automatic extraction of abstract-object-state machines from unit-test executions, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	David Lo , Siau-Cheng Khoo, SMArTIC: towards building an accurate, robust and scalable specification miner, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA
	Ted Kremenek , Paul Twohey , Godmar Back , Andrew Ng , Dawson Engler, From uncertainty to belief: inferring the specification within, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
	Sharon Shoham , Eran Yahav , Stephen Fink , Marco Pistoia, Static specification mining using automata-based abstractions, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom
	Sriram Sankaranarayanan , Swarat Chaudhuri , Franjo Ivančić , Aarti Gupta, Dynamic inference of likely data preconditions over predicates by tree learning, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	Yamini Kannan , Koushik Sen, Universal symbolic execution and its application to likely data structure invariant generation, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	Murali Krishna Ramanathan , Ananth Grama , Suresh Jagannathan, Static specification inference using predicate mining, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Graham Hughes , Tevfik Bultan, Interface grammars for modular software model checking, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom
	M. Pistoia , S. Chandra , S. J. Fink , E. Yahav, A survey of static analysis methods for identifying security vulnerabilities in software systems, IBM Systems Journal, v.46 n.2, p.265-288, April 2007
	Murali Krishna Ramanathan , Ananth Grama , Suresh Jagannathan, Path-Sensitive Inference of Function Precedence Protocols, Proceedings of the 29th International Conference on Software Engineering, p.240-250, May 20-26, 2007
	Huzefa Kagdi , Michael L. Collard , Jonathan I. Maletic, Comparing Approaches to Mining Source Code for Call-Usage Patterns, Proceedings of the Fourth International Workshop on Mining Software Repositories, p.20, May 20-26, 2007
	Jochen Quante , Rainer Koschke, Dynamic object process graphs, Journal of Systems and Software, v.81 n.4, p.481-501, April, 2008
	Anton Babenko , Leonardo Mariani , Fabrizio Pastore, AVA: automated interpretation of dynamically detected anomalies, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA
	Mark Gabel , Zhendong Su, Symbolic mining of temporal specifications, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany
	Shan Lu , Soyeon Park , Chongfeng Hu , Xiao Ma , Weihang Jiang , Zhenmin Li , Raluca A. Popa , Yuanyuan Zhou, MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Sriram Sankaranarayanan , Franjo Ivanči , Aarti Gupta, Mining library specifications using inductive logic programming, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany
	Christoph Csallner , Yannis Smaragdakis , Tao Xie, DSD-Crasher: A hybrid analysis tool for bug finding, ACM Transactions on Software Engineering and Methodology (TOSEM), v.17 n.2, p.1-37, April 2008
	Graham Hughes , Tevfik Bultan, Extended interface grammars for automated stub generation, Proceedings of the second workshop on Automated formal methods, p.41-50, November 06-06, 2007, Atlanta, Georgia
	Mithun Acharya , Tao Xie , Jian Pei , Jun Xu, Mining API patterns as partial orders from source code: from usage scenarios to specifications, 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
	Michael D. Ernst , Jeff H. Perkins , Philip J. Guo , Stephen McCamant , Carlos Pacheco , Matthew S. Tschantz , Chen Xiao, The Daikon system for dynamic detection of likely invariants, Science of Computer Programming, v.69 n.1-3, p.35-45, December, 2007
	Mark Gabel , Zhendong Su, Javert: fully automatic mining of general temporal properties from dynamic traces, Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, November 09-14, 2008, Atlanta, Georgia
	Benjamin Livshits , Aditya V. Nori , Sriram K. Rajamani , Anindya Banerjee, Merlin: specification inference for explicit information flow problems, ACM SIGPLAN Notices, v.44 n.6, June 2009
	Sudheendra Hangal , Monica S. Lam, Automatic dimension inference and checking for object-oriented programs, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.155-165, May 16-24, 2009
	David Lo , Leonardo Mariani , Mauro Pezzè, Automatic steering of behavioral model inference, Proceedings of the the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, August 24-28, 2009, Amsterdam, The Netherlands
	Michael Pradel, Dynamically inferring, refining, and checking API usage protocols, Proceeding of the 24th ACM SIGPLAN conference companion on Object oriented programming systems languages and applications, October 25-29, 2009, Orlando, Florida, USA
	Fan Long , Xi Wang , Yang Cai, Api hyperlinking via structural overlap, Proceedings of the the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, August 24-28, 2009, Amsterdam, The Netherlands

Collaborative Colleagues:

John Whaley: colleagues

Michael C. Martin: colleagues

Monica S. Lam: colleagues

This Article has also been published in:

ACM SIGSOFT Software Engineering Notes
Volume 27 , Issue 4 July 2002

Adobe Acrobat

QuickTime

Windows Media Player

Real Player