|
Published Articles >> Table of Contents >> Abstract
August 2007 (Vol. 33, No. 8)
pp. 526-543
Discovering Documentation for Java Container Classes
Johannes Henkel
Christoph Reichenbach
Amer Diwan
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TSE.2007.70705
Send link to a friend
| Abstract |
|
Abstract—Modern programs make extensive use of reusable software libraries. For example, we found that 17% to 30% of the classes in a number of large Java applications use the container classes from the java.util package. Given this extensive code reuse in Java programs, it is important for the reusable interfaces to have clear and unambiguous documentation. Unfortunately, most documentation is expressed in English, and therefore does not always satisfy these requirements. Worse yet, there is no way of checking that the documentation is consistent with the associated code. Formal specifications present an alternative which does not suffer from these problems; however, formal specifications are notoriously hard to write. To alleviate this difficulty, we have implemented a tool which automatically derives documentation in the form of formal specifications. Our tool probes Java classes by invoking them on dynamically generated tests and captures the information observed during their execution as algebraic axioms. While the tool is not complete or correct from a formal perspective we demonstrate that it discovers many useful axioms when applied to container classes. These axioms then form an initial formal documentation of the class they describe.
|
 References
|
[1] J.V. Guttag and J.J. Horning, “The Algebraic Specification of Abstract Data Types,” Acta Informatica, vol. 10, pp.27-52, 1978.
[2] M.D. Ernst, J. Cockrell, W.G. Griswold, and D. Notkin, “Dynamically Discovering Likely Program Invariants to Support Program Evolution,” ACM Trans. Software Eng., vol. 27, no. 2, pp.1-25, Feb. 2001.
[3] G. Ammons, R. Bodik, and J.R. Larus, “Mining Specifications,” Proc. 29th ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, pp.4-16, 2002.
[4] S. Hangal and M.S. Lam, “Tracking Down Software Bugs Using Automatic Anomaly Detection,” Proc. Int'l Conf. Software Eng., pp.291-301, May 2002.
[5] J. Whaley, M.C. Martin, and M.S. Lam, “Automatic Extraction of Object-Oriented Component Interfaces,” Proc. Int'l Symp. Software Testing and Analysis, 2002.
[6] J. Henkel and A. Diwan, “Discovering Algebraic Specifications from Java Classes,” Proc. 17th European Conf. Object-Oriented Programming (ECOOP '03), L. Cardelli, ed., citeseer.nj.nec.com/henkel03discovering.html, July 2003.
[7] J. Henkel and A. Diwan, “A Tool for Writing and Debugging Algebraic Specifications,” Proc. Int'l Conf. Software Eng. (ICSE), pp.449-458, May 2004.
[8] J.A. Goguen, J.W. Thatcher, and E.G. Wagner, “An Initial Algebra Approach to the Specification, Correctness and Implementation of Abstract Data Types,” Current Trends in Programming Methodology, R.T. Yeh, ed., vol.4, pp.80-149, 1978.
[9] J.C. Mitchell, Foundations of Programming Languages. MIT Press, 1996.
[10] R. Doong and P.G. Frankl, “The ASTOOT Approach to Testing Object-Oriented Programs,” ACM Trans. Software Eng. and Methodology, vol. 3, no. 2, Apr. 1994.
[11] S. Kamin, “Final Data Types and Their Specification,” ACM Trans. Programming Languages and Systems., vol. 5, no. 1, pp.97-121, 1983.
[12] G.D. Plotkin, “Call-By-Name, Call-By-Value and the $\lambda$ -Calculus,” Theoretical Computer Science, vol. 1, no. 2, pp.125-159, http://dx.doi.org/10.1016/0304-3975(75)90017-1, Dec. 1975.
[13] J. Henkel and A. Diwan, “Case Study: Debugging a Discovered Specification for java.util.arraylist by Using Algebraic Interpretation,” Technical Report CU-CS-970-04, Univ. of Colorado at Boulder, 2004.
[14] I.V. Horebeek and J. Lewi, Algebraic Specifications in Software Engineering: An Introduction. Springer-Verlag, 1989.
[15] D. Sannella and A. Tarlecki, “Essential Concepts of Algebraic Specification and Program Development,” Formal Aspects of Computing, vol. 9, pp. 229-269, ftp://ftp.dcs.ed.ac.uk/pub/dts/concepts.ps, 1997.
[16] Algebraic Foundations of Systems Specification, E. Astesiano, H.-J.Kreowski and B. Krieg-Brückner, eds. Springer, 1999.
[17] S. Antoy, “Systematic Design of Algebraic Specifications,” Proc. Fifth Int'l Workshop Software Specification and Design, 1989.
[18] S. Rugaber, T. Shikano, and R.E.K. Stirewalt, “Adequate Reverse Eng.,” Proc. 16th Ann. Int'l Conf. Automated Software Eng., pp.232-24, 2001.
[19] W. Bartussek and D.L. Parnas, “Using Assertions about Traces to Write Abstract Specifications for Software Modules,” Proc. Second Conf. European Cooperation in Informatics: Information Systems Methodology, Oct. 1978.
[20] R. Janicki and E. Sekerinski, “Foundations of the Trace Assertion Method of Module Interface Specification,” IEEE Trans. Software Eng., vol. 27, no. 7, July 2001.
[21] R. Deline and M. Fahndrich, “Typestates for Objects,” citeseer.ist. psu.edu/deline04typestates.html, 2004.
[22] P. Lam, V. Kuncak, and M. Rinard, “Generalized Typestate Checking Using Set Interfaces and Pluggable Analyses,” SIGPLAN Notices, vol. 39, no. 3, pp. 46-55, 2004.
[23] M.D. Ernst, J.H. Perkins, P.J. Guo, S. McCamant, C. Pacheco, M.S. Tschantz, and C. Xiao, “The Daikon System for Dynamic Detection of Likely Invariants,” Science of Computer Programming, 2006.
[24] C.A.R. Hoare, “An Axiomatic Basis for Computer Programming,” Comm. ACM, vol. 12, no. 10, pp.576-580, 1969.
[25] D. Gries, The Science of Programming, Texts and Monographs in Computer Science. Springer-Verlag, 1981.
[26] M.D. Ernst, A. Czeisler, W.G. Griswold, and D. Notkin, “Quickly Detecting Relevant Program Invariants,” Proc. 22nd Int'l Conf. Software Eng., pp.449-458, June 2000.
[27] M.D. Ernst, W.G. Griswold, Y. Kataoka, and D. Notkin, “Dynamically Discovering Program Invariants Involving Collections,” Technical Report UW-CSE-99-11-02, revised version, Univ. of Washington, Mar. 2000.
[28] N. Dodoo, A. Donovan, L. Lin, and M.D. Ernst, “Selecting Predicates for Implications in Program Analysis,” http://pag.lcs. mit.edu/~mernst/pubs/invariants-implications.pdf., Mar. 2002.
[29] J.H. Perkins and M.D. Ernst, “Efficient Incremental Algorithms for Dynamic Detection of Likely Invariants,” Proc. ACM SIGSOFT 12th Symp. Foundations of Software Eng. (FSE '04), pp.23-32, Nov. 2004.
[30] S. Artzi, M.D. Ernst, A. Kieun, C. Pacheco, and J.H. Perkins, “Finding the Needles in the Haystack: Generating Legal Test Inputs for Object-Oriented Programs,” Proc. First Workshop Model-Based Testing and Object-Oriented Systems (M-TOOS), Oct. 2006.
[31] P.J. Guo, J.H. Perkins, S. McCamant, and M.D. Ernst, “Dynamic Inference of Abstract Types,” Proc. 2006 Int'l Symp. Software Testing and Analysis (ISSTA '06), pp.255-265, July 2006.
[32] Y. Kataoka, M.D. Ernst, W.G. Griswold, and D. Notkin, “Automated Support for Program Refactoring Using Invariants,” Proc. Int'l Conf. Software Maintenance, 2001.
[33] M. Harder and M.D. Ernst, “Specification Coverage as a Measure of Test Suite Quality,” MEng. thesis, Massachusetts Inst. of Tech nology, Sept. 2001.
[34] J.W. Nimmer and M.D. Ernst, “Automatic Generation of Program Specifications,” Proc. Int'l Symp. Software Testing and Analysis (ISSTA), July 2002.
[35] R. O'Callahan and D. Jackson, “Lackwit: A Program Understanding Tool Based on Type Inference,” Proc. Int'l Conf. Software Eng., pp.338-348, citeseer.nj.nec.com/329620.html, 1997.
[36] J. Henkel, C. Reichenbach, and A. Diwan, “Developing and Debugging Algebraic Specifications for Java Classes,” Technical Report CU-CS-984-04, Univ. of Colorado, 2004.
[37] A.W. Biermann, “On the Inference of Turing Machines from Sample Computations,” Artificial Intelligence, vol. 3, pp.181-198, 1972.
[38] A.W. Biermann and R. Krishnaswamy, “Constructing Programs from Example Computations,” IEEE Trans. Software Eng., vol. 2, no. 3, pp.141-153, Sept. 1976.
[39] A.W. Biermann, “The Inference of Regular Lisp Programs from Examples,” IEEE Trans. Systems, Man, and Cybernetics, vol. 8, pp.585-600, Aug. 1978.
[40] D. Angluin, “Inference of Reversible Languages,” J. ACM (JACM), vol. 29, no. 3, pp.741-765, 1982.
[41] S. Hardy, “Synthesis of Lisp Functions from Examples,” Proc. Fourth Int'l Joint Conf. Artificial Intelligence, pp.240-245, 1975.
[42] P.D. Summers, “A Methodology for Lisp Program Construction from Examples,” J. ACM, vol. 24, no. 1, pp.161-175, 1977.
[43] E.Y. Shapiro, Algorithmic Program Debugging, ACM Distinguished Dissertation 1982, MIT Press, 1982.
[44] M. Sagiv, T. Reps, and R. Wilhelm, “Parametric Shape Analysis via 3-Valued Logic,” ACM Trans. Programming Languages and Systems, vol. 24, no. 3, pp.217-298, May 2002.
[45] F. Logozzo, “Automatic Inference of Class Invariants,” citeseer. ist.psu.edu/logozzo04automatic.html, 2004.
[46] N. Tillmann, F. Chen, and W. Schulte, “Discovering Likely Method Specifications,” Proc. Int'l Conf. Formal Eng. Methods (ICFEM '07), pp.717-736, 2006.
[47] Z. Li and Y. Zhou, “PR-Miner: Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code,” Proc. 10th European Software Eng. Conf./13th ACM SIGSOFT Int'l Symp. Foundations of Software Eng. (ESEC/FSE 13), vol. 30, no. 5, pp.306-315, http://portal.acm.org/citation.cfm?id=1081755, Sept. 2005.
[48] M.G. Nanda, C. Grothoff, and S. Chandra, “Deriving Object Typestates in the Presence of Inter-Object References,” Proc. 20th Ann. ACM SIGPLAN Conf. Object Oriented Programming, Systems, Languages, and Applications (OOPSLA '05), pp.77-96, 2005.
[49] M.R. Woodward, “Errors in Algebraic Specifications and an Experimental Mutation Testing Tool,” Software Eng. J., vol. 8, no. 4, pp.237-245, July 1993.
[50] J. Gannon, P. McMullin, and R. Hamlet, “Data-Abstraction Implementation, Specification and Testing,” ACM Trans. Programming Languages and Systems, vol. 3, no. 3, pp.211-223, 1981.
[51] S. Sankar, “Run-Time Consistency Checking of Algebraic Specifications,” Proc. Symp. Testing, Analysis, and Verification, Sept. 1991.
[52] M. Hughes and D. Stotts, “Daistish: Systematic Algebraic Testing for OO Programs in the Presence of Side-Effects,” Proc. Int'l Symp. Software Testing and Verification, 1996.
[53] S. Antoy and D. Hamlet, “Automatically Checking an Implementation against Its Formal Specification,” IEEE Trans. Software Eng., vol. 26, no. 1, Jan. 2000.
[54] H.Y. Chen, T.H. Tse, F.T. Chan, and T.Y. Chen, “In Black and White: An Integrated Approach to Class-Level Testing of Object Oriented Programs,” ACM Trans. Software Eng. and Methodology, vol. 7, no. 3, July 1998.
[55] R. Helm, I.M. Holland, and D. Gangopadhyay, “Contracts: Specifying Behavioral Compositions in Object-Oriented Systems,” Proc. European Conf. Object-Oriented Programming Object-Oriented Programming Systems, Languages, and Applications, pp.169-180, 1990.
[56] U. Buy, A. Orso, and M. Pezze, “Automated Testing of Classes,” Proc. Int'l Symp. Software Testing and Analysis, 2000.
[57] V. Martena, A. Orso, and M. Pezze, “Interclass Testing of Object Oriented Software,” Proc. IEEE Int'l Conf. Eng. Complex Computer Systems, 2002.
[58] H. Zhu, P.A.V. Hall, and J.H.R. May, “Software Unit Test Coverage and Adequacy,” ACM Computing Surveys, vol. 29, no. 4, pp. 366-427, 1997.
[59] T.L. Graves, M.J. Harrold, J.-M. Kim, A. Porter, and G. Rothermel, “An Empirical Study of Regression Test Selection Techniques,” ACM Trans. Software Eng. and Methodology, vol. 10, no. 2, pp.184-208, 2001.
[60] C. Boyapati, S. Khurshid, and D. Marinov, “Korat: Automated Testing Based on Java Predicates,” Proc. Int'l Symp. Software Testing and Analysis, July 2002.
|
 Additional Information
|
Citation:
Johannes Henkel, Christoph Reichenbach, Amer Diwan,
"Discovering Documentation for Java Container Classes,"
IEEE Transactions on Software Engineering,
vol. 33,
no. 8,
pp. 526-543,
Aug.,
2007
|
|
RSS Feed