Specification mining of symbolic scenario-based models

ABSTRACT

Many dynamic analysis approaches to specification mining, which extract behavioral models from execution traces, do not consider object identities. This limits their power when used to analyze traces of general object oriented programs. In this work we present a novel specification mining approach that considers object identities, and, moreover, generalizes from specifications involving concrete objects to their symbolic class-level abstractions. Our approach uses data mining methods to extract significant scenario-based specifications in the form of Damm and Harel's live sequence charts (LSC), a formal and expressive extension of classic sequence diagrams. We guarantee that all mined symbolic LSCs are significant (statistically sound) and all significant symbolic LSCs are mined (statistically complete). The technique can potentially be applied to general object oriented programs to reveal expressive and useful reverse-engineered candidate specifications.

REFERENCES

• 1: Eclipse Test and Performance Tools Platform. http://www.eclipse.org/tptp/.
• 2: 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 [doi>10.1145/1287624.1287630]
• 3: 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
• 4: Lionel C. Briand , Yvan Labiche , Johanne Leduc, Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software, IEEE Transactions on Software Engineering, v.32 n.9, p.642-663, September 2006 [doi>10.1109/TSE.2006.96]
• 5: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 6: Werner Damm , David Harel, LSCs: Breathing Life into Message Sequence Charts, Formal Methods in System Design, v.19 n.1, p.45-80, July 2001 [doi>10.1023/A:1011227529550]
• 7: Dawson Engler , David Yu Chen , Seth Hallem , Andy Chou , Benjamin Chelf, Bugs as deviant behavior: a general approach to inferring errors in systems code, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 8: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 9: 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 [doi>10.1145/1453101.1453150]
• 10: Mark Gabel , Zhendong Su, Symbolic mining of temporal specifications, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368096]
• 11: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 12: David Harel, From Play-In Scenarios to Code: An Achievable Dream, Computer, v.34 n.1, p.53-60, January 2001
• 13: D. Harel and S. Maoz. Assert and Negate Revisited: Modal Semantics for UML Sequence Diagrams. Software and Systems Modeling, 7(2):237--252, 2008.
• 14: David Harel , Rami Marelly, Come, Let's Play: Scenario-Based Programming Using LSC's and the Play-Engine, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 15: Ø. Haugen, K. E. Husa, R. K. Runde, and K. Stølen. STAIRS towards Formal Design with Sequence Diagrams. Software and Systems Modeling (SoSyM), 4(4):355--367, 2005.
• 16: J. Klose, T. Toben, B. Westphal, and H. Wittke. Check it out: On the efficient formal verification of Live Sequence Charts. In CAV, 2006.
• 17: H. Kugler, D. Harel, A. Pnueli, Y. Lu, and Y. Bontemps. Temporal Logic for Scenario-Based Specifications. In TACAS, 2005.
• 18: Marc Lettrari , Jochen Klose, Scenario-Based Monitoring and Testing of Real-Time UML Models, Proceedings of the 4th International Conference on The Unified Modeling Language, Modeling Languages, Concepts, and Tools, p.317-328, October 01-05, 2001
• 19: David Lo , Siau-Cheng Khoo, QUARK: Empirical Assessment of Automaton-based Specification Miners, Proceedings of the 13th Working Conference on Reverse Engineering, p.51-60, October 23-27, 2006 [doi>10.1109/WCRE.2006.47]
• 20: 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 [doi>10.1145/1181775.1181808]
• 21: David Lo , Siau-Cheng Khoo , Chao Liu, Efficient mining of iterative patterns for software specification discovery, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281243]
• 22: D. Lo, S.-C. Khoo, and C. Liu. Efficient mining of recurrent rules from a sequence database. In Proc. of Int. Conf. on Database Systems for Advanced Applications, 2008.
• 23: D. Lo and S. Maoz. Mining Scenario-Based Triggers and Effects. In ASE, 2008.
• 24: D. Lo and S. Maoz. Specification mining of symbolic scenario-based models (tech. report. version). Technical Report at www.comp.nus.edu.sg/~dlo/symbolicmining.pdf, 2008.
• 25: David Lo , Shahar Maoz , Siau-Cheng Khoo, Mining modal scenario-based specifications from execution traces of reactive systems, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321710]
• 26: Davide Lorenzoli , Leonardo Mariani , Mauro Pezzè, Automatic generation of software behavioral models, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368157]
• 27: Shahar Maoz , David Harel, From multi-modal scenarios to code: compiling LSCs into aspectJ, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181802]
• 28: Rami Marelly , David Harel , Hillel Kugler, Multiple instances and symbolic variables in executable sequence charts, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 29: Behavior Capture and Test: Automated Analysis of Component Integration, Proceedings of the 10th IEEE International Conference on Engineering of Complex Computer Systems, p.292-301, June 16-20, 2005 [doi>10.1109/ICECCS.2005.25]
• 30: Mike McGavin , Tim Wright , Stuart Marshall, Visualisations of execution traces (VET): an interactive plugin-based visualisation tool, Proceedings of the 7th Australasian User interface conference, p.153-160, January 16-19, 2006, Hobart, Australia
• 31: Atanas Rountev , Beth Harkness Connell, Object naming analysis for reverse-engineered sequence diagrams, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062510]
• 32: Hossein Safyallah , Kamran Sartipi, Dynamic Analysis of Software Systems using Execution Pattern Mining, Proceedings of the 14th IEEE International Conference on Program Comprehension, p.84-88, June 14-16, 2006 [doi>10.1109/ICPC.2006.19]
• 33: Neil Walkinshaw , Kirill Bogdanov , Mike Holcombe , Sarah Salahuddin, Reverse Engineering State Machines by Interactive Grammar Inference, Proceedings of the 14th Working Conference on Reverse Engineering, p.209-218, October 28-31, 2007 [doi>10.1109/WCRE.2007.45]
• 34: Jianyong Wang , Jiawei Han, BIDE: Efficient Mining of Frequent Closed Sequences, Proceedings of the 20th International Conference on Data Engineering, p.79, March 30-April 02, 2004
• 35: W. Weimer and G. Necula. Mining temporal specifications for error detection. In TACAS, 2005.
• 36: X. Yan, J. Han, and R. Afhar. CloSpan: Mining closed sequential patterns in large datasets. In Proc. of SIAM Int. Conf. on Data Mining, 2003.
• 37: Jinlin Yang , David Evans , Deepali Bhardwaj , Thirumalesh Bhat , Manuvir Das, Perracotta: mining temporal API rules from imperfect traces, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134325]