Automated testing of refactoring engines

ABSTRACT

Refactorings are behavior-preserving program transformations that improve the design of a program. Refactoring engines are tools that automate the application of refactorings: first the user chooses a refactoring to apply, then the engine checks if the transformation is safe, and if so, transforms the program. Refactoring engines are a key component of modern IDEs, and programmers rely on them to perform refactorings. A bug in the refactoring engine can have severe consequences as it can erroneously change large bodies of source code.

We present a technique for automated testing of refactoring engines. Test inputs for refactoring engines are programs. The core of our technique is a framework for iterative generation of structurally complex test inputs. We instantiate the framework to generate abstract syntax trees that represent Java programs. We also create several kinds of oracles to automatically check that the refactoring engine transformed the generated program correctly. We have applied our technique to testing Eclipse and NetBeans, two popular open-source IDEs for Java, and we have exposed 21 new bugs in Eclipse and 24 new bugs in NetBeans.

REFERENCES

• 1: Don Batory , Sean O'Malley, The design and implementation of hierarchical software systems with reusable components, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.4, p.355-398, Oct. 1992 [doi>10.1145/136586.136587]
• 2: F. Bazzichi , I. Spadafora, An Automatic Generator for Compiler Testing, IEEE Transactions on Software Engineering, v.8 n.4, p.343-353, July 1982 [doi>10.1109/TSE.1982.235428]
• 3: Kent Beck, Smalltalk: best practice patterns, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 4: Kent Beck, Extreme programming explained: embrace change, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: Chandrasekhar Boyapati , Sarfraz Khurshid , Darko Marinov, Korat: automated testing based on Java predicates, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 6: A. Celentano, S. C. Reghizzi, P. D. Vigna, C. Ghezzi, G. Granata, and F. Savoretti. Compiler testing using a sentence generator. Software -- Practice and Experience, 10(11):897--918, 1980.
• 7: Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.268-279, September 2000
• 8: A. G. Duncan , J. S. Hutchison, Using attributed grammars to test designs and implementations, Proceedings of the 5th international conference on Software engineering, p.170-178, March 09-12, 1981, San Diego, California, United States
• 9: Refactoring: improving the design of existing code, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 10: E. Gamma and K. Beck. JUnit, 1997. http://www.junit.org.
• 11: Sarfraz Khurshid , Daniel Jackson, Generating structurally complex tests from declarative constraints, Massachusetts Institute of Technology, 2004
• 12: Sarfraz Khurshid , Darko Marinov, TestEra: Specification-Based Testing of Java Programs Using SAT, Automated Software Engineering, v.11 n.4, p.403-434, October 2004 [doi>10.1023/B:AUSE.0000038938.10589.b9]
• 13: R. Lämmel and W. Schulte. Controllable combinatorial coverage in grammar-based testing. In TestCom, pages 19--38, 2006.
• 14: B. A. Malloy and J. F. Power. An interpretation of Purdom's algorithm for automatic generation of test cases. 1st Annual International Conf. on Computer and Information Science, 2001.
• 15: John J. Marciniak, Encyclopedia of software engineering, Wiley-Interscience, New York, NY, 1994
• 16: Darko Marinov , Martin C. Rinard, Automatic testing of software with structurally complex inputs, Massachusetts Institute of Technology, Cambridge, MA, 2005
• 17: Peter M. Maurer, Generating Test Data with Enhanced Context-Free Grammars, IEEE Software, v.7 n.4, p.50-55, July 1990 [doi>10.1109/52.56422]
• 18: W. M. McKeeman. Differential testing for software. Digital Technical Journal, 10(1), 1998.
• 19: W. F. Opdyke and R. E. Johnson. Refactoring: an aid in designing application frameworks and evolving object-oriented systems. In Proc. Symposium on Object-Oriented Programming Emphasizing Practical Applications (SOOPPA), Sept 1990.
• 20: P. Purdom. A sentence generator for testing parsers. Behavior and Information Technology, 12(3):366--375, 1972.
• 21: Emin Gün Sirer , Brian N. Bershad, Using production grammars in software testing, Proceedings of the 2nd conference on Domain-specific languages, p.1-13, October 03-06, 1999, Austin, Texas, United States
• 22: Kevin Sullivan , Jinlin Yang , David Coppit , Sarfraz Khurshid , Daniel Jackson, Software assurance by bounded exhaustive testing, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Object-oriented programming

General Terms:
Verification

Keywords:
automated testing, bounded-exhaustive testing, imperative generators, refactoring engines, test data generation