Michael D. Ernst
Adam Czeisler
William G. Griswold
David Notkin
ABSTRACT
Explicitly stated program invariants can help programmers by characterizing certain aspects of program execution and identifying program properties that must be preserved when modifying code. Unfortunately, these invariants are usually absent from code. Previous work showed how to dynamically detect invariants from program traces by looking for patterns in and relationships among variable values. A prototype implementation, Daikon, accurately recovered invariants from formally-specified programs, and the invariants it detected in other programs assisted programmers in a software evolution task. However, Daikon suffered from reporting too many invariants, many of which were not useful, and also failed to report some desired invariants.
This paper presents, and gives experimental evidence of the efficacy of, four approaches for increasing the relevance of invariants reported by a dynamic invariant detector. One of them — exploiting unused polymorphism — adds desired invariants to the output. The other three — suppressing implied invariants, limiting which variables are compared to one another, and ignoring unchanged values — eliminate undesired invariants from the output and also improve runtime by reducing the work done by the invariant detector.
- ECGN.Michael D. Ernst, Jake Cockrell, William G. Griswold, and David Notkin. Dynamically discovering likely program invariants to support program evolution. IEEE Transactions on Software Engineering. To appear. A previous version appeared in Proceedings of the 21st International Conference on Software Engineering, pages 213-224, May 19-21, 1999. Google Scholar
Digital Library
- EGKN99.Michael D. Ernst, William G. Griswold, Yoshio Kataoka, and David Notkin. Dynamically discovering pointerbased program invariants. Technical Report UW-CSE-99-11-02, University of Washington, Seattle, WA, November 16, 1999.Google Scholar
- Goe85.Amrit L. Goel. Software reliability models: Assumptions, limitations, and applicability. IEEE Transactions on Software Engineering, SE-11(12):1411-23, December 1985.Google ScholarDigital Library
- Gri81.David Gries. The Science of Programming. Springer- Verlag, New York, 1981. Google ScholarDigital Library
- HFGO94.Monica Hutchins, Herb Foster, Tarak Goradia, and Thomas Ostrand. Experiments on the effectiveness of dataflowand controlflow-based test adequacy criteria. In Proceedings of the 16th International Conference on Software Engineering, pages 191-200, May 1994. Google ScholarDigital Library
- OJ97.Robert O'Callahan and Daniel Jackson. Lackwit: A program understanding tool based on type inference. In Proceedings of the 19th International Conference on Software Engineering, pages 338-348, May 1997. Google ScholarDigital Library
- RH98.Gregg Rothermel and Mary Jean Harrold. Empirical studies of a safe regression test selection technique. IEEE Transactions on Software Engineering, 24(6):401-419, June 1998. Google ScholarDigital Library
- Sal68.Gerard Salton. Automatic Information Organization and Retrieval. McGraw-Hill, 1968. Google ScholarDigital Library
- Wei99.Mark Allen Weiss. Data Structures and Algorithm Analysis in Java. Addison Wesley Longman, 1999.Google ScholarDigital Library
Index Terms
- Quickly detecting relevant program invariants
Recommendations
Rotation and translation invariants of Gaussian-Hermite moments
Geometric moment invariants are widely used in many fields of image analysis and pattern recognition since their first introduction by Hu in 1962. A few years ago, Flusser has proved how to find the independent and complete set of geometric moment ...
Radial Zernike Moment Invariants
CIT '04: Proceedings of the The Fourth International Conference on Computer and Information TechnologyRadial Zernike moment invariants are special case from the complex Zernike moment invariants. The radial and angular dependence of Zernike moments is naturally separable which makes them very suitable features for achieving totational invarinces. The ...
Generic radial orthogonal moment invariants for invariant image recognition
As the variation of parameters in Jacobi polynomial, Jacobi-Fourier moments can form various types of orthogonal moments: Legendre-Fourier moments, Orthogonal Fourier-Mellin moments, Zernike moments, pseudo-Zernike moments, and so on. In this paper, we ...
Comments