AVA: automated interpretation of dynamically detected anomalies

ABSTRACT

Dynamic analysis techniques have been extensively adopted to discover causes of observed failures. In particular, anomaly detection techniques can infer behavioral models from observed legal executions and compare failing executions with the inferred models to automatically identify the likely anomalous events that caused observed failures.

Unfortunately the output of these techniques is limited to a set of independent suspicious anomalous events that does not capture the structure and the rationale of the differences between the correct and the failing executions. Thus, testers spend a relevant amount of time and effort to investigate executions and interpret these differences, reducing effectiveness of anomaly detection techniques.

In this paper, we present Automata Violations Analyzer (AVA), a technique to automatically produce candidate interpretations of detected failures from anomalies identified by anomaly detection techniques. Interpretations capture the rationale of the differences between legal and failing executions with user understandable patterns that simplify identification of failure causes. The empirical validation with synthetic cases and third-party systems shows that AVA produces useful interpretations.

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: Apache Software Foundation. Tomcat JSP/Servlet server. http://tomcat.apache.org/, visited in 2009.
• 3: A. Biermann and J. Feldman. On the synthesis of finite state machines from samples of their behavior. IEEE Transactions on Computer, 21:592--597, June 1972.
• 4: Lionel C. Briand , Yvan Labiche , Xuetao Liu, Using Machine Learning to Support Debugging with Tarantula, Proceedings of the The 18th IEEE International Symposium on Software Reliability, p.137-146, November 05-09, 2007 [doi>10.1109/ISSRE.2007.36]
• 5: Mike Y. Chen , Emre Kiciman , Eugene Fratkin , Armando Fox , Eric Brewer, Pinpoint: Problem Determination in Large, Dynamic Internet Services, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.595-604, June 23-26, 2002
• 6: William Dickinson , David Leon , Andy Podgurski, Finding failures by cluster analysis of execution profiles, Proceedings of the 23rd International Conference on Software Engineering, p.339-348, May 12-19, 2001, Toronto, Ontario, Canada
• 7: Glassfish application server. Glassfish. https://glassfish.dev.java.net/, visited in 2009.
• 8: Glassfish bug database. Glassfish issue 4255. https://glassfish.dev.java.net/issues/showbug.cgi?id=4255, visited in 2009.
• 9: Glassfish user forum. Glassfish configuration issue. http://forums.java.net/jive/thread.jspa?messageID=252898, visited in 2009.
• 10: Glassfish user forum. Glassfish configuration issue. http://forum.java.sun.com/thread.jspa?threadID=5249570, visited in 2009.
• 11: 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]
• 12: James A. Jones , Mary Jean Harrold , John Stasko, Visualization of test information to assist fault localization, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581397]
• 13: Leonardo Mariani , Fabrizio Pastore, Automated Identification of Failure Causes in System Logs, Proceedings of the 2008 19th International Symposium on Software Reliability Engineering, p.117-126, November 10-14, 2008 [doi>10.1109/ISSRE.2008.48]
• 14: Leonardo Mariani , Mauro Pezzè, Dynamic Detection of COTS Component Incompatibility, IEEE Software, v.24 n.5, p.76-85, September 2007 [doi>10.1109/MS.2007.138]
• 15: Wes Masri , Andy Podgurski , David Leon, An Empirical Study of Test Case Filtering Techniques Based on Exercising Information Flows, IEEE Transactions on Software Engineering, v.33 n.7, p.454-477, July 2007 [doi>10.1109/TSE.2007.1020]
• 16: Alexander V. Mirgorodskiy , Naoya Maruyama , Barton P. Miller, Problem diagnosis in large-scale computing environments, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188548]
• 17: S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443--453, March 1970.
• 18: T. J. Ostrand , M. J. Balcer, The category-partition method for specifying and generating fuctional tests, Communications of the ACM, v.31 n.6, p.676-686, June 1988 [doi>10.1145/62959.62964]
• 19: Orna Raz , Philip Koopman , Mary Shaw, Semantic anomaly detection in online data sources, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581378]
• 20: 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
• 21: M. Renieris and S. Reiss. Fault localization with nearest neighbor queries. In proceedings of the Internation Conference on Automated Software Engineering, 2003.
• 22: Tomcat bug database. Tomcat fault 40820. https://issues.apache.org/bugzilla/showbug.cgi?id=40820, visited in 2009.
• 23: Tomcat bug database. Tomcat configuration issue. http://www.blogjava.net/haix/archive/2008/01/16/175592.html, visited in 2009.
• 24: Andrzej Wasylkowski , Andreas Zeller , Christian Lindig, Detecting object usage anomalies, 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 [doi>10.1145/1287624.1287632]
• 25: 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 [doi>10.1145/1173706.1173734]
• 26: John Whaley , Michael C. Martin , Monica S. Lam, Automatic extraction of object-oriented component interfaces, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 27: Cemal Yilmaz , Amit Paradkar , Clay Williams, Time will tell: fault localization using time spectra, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368100]
• 28: Chun Yuan , Ni Lao , Ji-Rong Wen , Jiwei Li , Zheng Zhang , Yi-Min Wang , Wei-Ying Ma, Automated known problem diagnosis with event traces, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 29: Andreas Zeller, Isolating cause-effect chains from computer programs, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002 [doi>10.1145/605466.605468]
• 30: Andreas Zeller, Why Programs Fail: A Guide to Systematic Debugging, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation
      D.2.5 Testing and Debugging
          Subjects: Monitors; Tracing

General Terms:
Verification

Keywords:
anomaly detection, dynamic analysis