research-article

Scenario-based and value-based specification mining: better together

Authors:

Shahar MaozAuthors Info & Claims

ASE '10: Proceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering

Pages 387 - 396

https://doi.org/10.1145/1858996.1859081

Published: 20 September 2010 Publication History

Abstract

Specification mining takes execution traces as input and extracts likely program invariants, which can be used for comprehension, verification, and evolution related tasks. In this work we integrate scenario-based specification mining, which uses data-mining algorithms to suggest ordering constraints in the form of live sequence charts, an inter-object, visual, modal, scenario-based specification language, with mining of value-based invariants, which detects likely invariants holding at specific program points. The key to the integration is a technique we call scenario-based slicing, running on top of the mining algorithms to distinguish the scenario-specific invariants from the general ones. The resulting suggested specifications are rich, consisting of modal scenarios annotated with scenario-specific value-based invariants, referring to event parameters and participating object properties.

An evaluation of our work over a number of case studies shows promising results in extracting expressive specifications from real programs, which could not be extracted previously. The more expressive the mined specifications, the higher their potential to support program comprehension and testing.

References

[1]

}}CrossFTP Server. sourceforge.net/projects/crossftpserver/.

[2]

}}Eclipse Test and Performance Tools Platform. http://www.eclipse.org/tptp/.

[3]

}}Jeti. Version 0.7.6 (Oct. 2006). http://jeti.sourceforge.net/.

[4]

}}http://www.mysmu.edu/faculty/davidlo/inv/invariants.html.

[5]

}}M. Acharya, T. Xie, J. Pei, and J. Xu. Mining API patterns as partial orders from source code: From usage scenarios to specifications. In SIGSOFT FSE, 2007.

Digital Library

[6]

}}G. Ammons, R. Bodik, and J. R. Larus. Mining specification. In POPL, 2002.

Digital Library

[7]

}}M. Boshernitsan, R.-K. Doong, and A. Savoia. From Daikon to Agitator: Lessons and challenges in building a commercial tool for developer testing. In ISSTA, 2006.

Digital Library

[8]

}}V. Dallmeier, C. Lindig, A. Wasylkowski, and A. Zeller. Mining object behavior with ADABU. In WODA, 2006.

Digital Library

[9]

}}W. Damm and D. Harel. LSCs: Breathing life into Message Sequence Charts. J. on Formal Methods in System Design, 19(1):45--80, 2001.

Digital Library

[10]

}}T. Doan, D. Lo, S. Maoz, and S.-C. Khoo. LM: A tool for scenario-based specification mining. In ICSE, 2010.

Digital Library

[11]

}}M. B. Dwyer, G. S. Avrunin, and J. C. Corbett. Patterns in property specifications for finite-state verification. In ICSE, 1999.

Digital Library

[12]

}}M. El-Ramly, E. Stroulia, and P. Sorenson. Interaction-pattern mining: Extracting usage scenarios from run-time behavior traces. In KDD, 2002.

Digital Library

[13]

}}M. Ernst, J. Cockrell, W. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. TSE, 27(2):99--123, 2001.

Digital Library

[14]

}}J. Han and M. Kamber. Data Mining Concepts and Techniques. Morgan Kaufmann, 2006.

Digital Library

[15]

}}D. Harel. From play-in scenarios to code: An achievable dream. IEEE Computer, 34(1):53--60, 2001.

Digital Library

[16]

}}D. Harel and S. Maoz. Assert and negate revisited: Modal semantics for UML sequence diagrams. Software and Systems Modeling, 7(2):237--252, 2008.

[17]

}}D. Harel and R. Marelly. Come, Let's Play: Scenario-Based Programming Using LSCs and the Play-Engine. Springer, 2003.

Digital Library

[18]

}}D. F. Jerding, J. T. Stasko, and T. Ball. Visualizing interactions in program executions. In ICSE, 1997.

Digital Library

[19]

}}F. Klein and H. Giese. Joint structural and temporal property specification using timed story scenario diagrams. In FASE, 2007.

Digital Library

[20]

}}J. Klose, T. Toben, B. Westphal, and H. Wittke. Check it out: On the efficient formal verification of Live Sequence Charts. In CAV, 2006.

Digital Library

[21]

}}I. Krüger. Capturing overlapping, triggered, and preemptive collaborations using MSCs. In FASE, 2003.

Digital Library

[22]

}}H. Kugler, D. Harel, A. Pnueli, Y. Lu, and Y. Bontemps. Temporal logic for scenario-based specifications. In TACAS, 2005.

Digital Library

[23]

}}H. Kugler and I. Segall. Compositional synthesis of reactive systems from live sequence chart specifications. In TACAS, 2009.

Digital Library

[24]

}}M. Lettrari and J. Klose. Scenario-based monitoring and testing of real-time UML models. In UML, 2001.

Digital Library

[25]

}}D. Lo and S.-C. Khoo. SMArTIC: Towards building an accurate, robust and scalable specification miner. In SIGSOFT FSE, 2006.

Digital Library

[26]

}}D. Lo and S. Maoz. Mining scenario-based triggers and effects. In ASE, 2008.

Digital Library

[27]

}}D. Lo and S. Maoz. Mining symbolic scenario-based specifications. In PASTE, 2008.

Digital Library

[28]

}}D. Lo and S. Maoz. Mining hierarchical scenario-based specifications. In ASE, 2009.

Digital Library

[29]

}}D. Lo, S. Maoz, and S.-C. Khoo. Mining modal scenario-based specifications from execution traces of reactive systems. In ASE, 2007.

Digital Library

[30]

}}D. Lo, G. Ramalingam, V. Ranganath, and K. Vaswani. Mining Quantified Temporal Rules: Formalisms, Algorithms, and Evaluation. In WCRE, 2009.

Digital Library

[31]

}}D. Lorenzoli, L. Mariani, and M. Pezzè. Automatic generation of software behavioral models. In ICSE, 2008.

Digital Library

[32]

}}S. Maoz and D. Harel. From multi-modal scenarios to code: Compiling LSCs into AspectJ. In SIGSOFT FSE, 2006.

Digital Library

[33]

}}L. Mariani, S. Papagiannakis, and M. Pezzè. Compatibility and regression testing of COTS-component-based software. In ICSE, 2007.

Digital Library

[34]

}}L. Mariani and M. Pezzè. Behavior capture and test: Automated analysis for component integration. In Proc. IEEE Int. Conf. on Eng. of Complex Computer Systems, 2005.

Digital Library

[35]

}}K. Olender and L. Osterweil. Cecil: A sequencing constraint language for automatic static analysis generation. IEEE TSE, 16:268--280, 1990.

Digital Library

[36]

}}B. Pytlik, M. Renieris, S. Krishnamurthi, and S. P. Reiss. Automated fault localization using potential invariants. CoRR, cs.SE/0310040, 2003.

[37]

}}H. Safyallah and K. Sartipi. Dynamic analysis of software systems using execution pattern mining. In ICPC, 2006.

Digital Library

[38]

}}G. Sibay, S. Uchitel, and V. A. Braberman. Existential live sequence charts revisited. In ICSE, 2008.

Digital Library

[39]

}}J. Sun and J. S. Dong. Synthesis of distributed processes from scenario-based specifications. In FM, 2005.

Digital Library

[40]

}}T. Xie, S. Thummalapenta, D. Lo, and C. Liu. Data mining for software engineering. IEEE Computer, 42(8):35--42, 2009.

Digital Library

[41]

}}J. Yang, D. Evans, D. Bhardwaj, T. Bhat, and M.Das. Perracotta: Mining temporal API rules from imperfect traces. In ICSE, 2006.

Digital Library

Cited By

Nguyen HPhan HKhairunnesa SNguyen SYadavally AWang SRajan HNguyen T(2022)A Hybrid Approach for Inference between Behavioral Exception API Documentation and Implementations, and Its ApplicationsProceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering10.1145/3551349.3560434(1-13)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3551349.3560434
Afzal AMotwani MStolee KBrun YLe Goues C(2021)SOSRepair: Expressive Semantic Search for Real-World Program RepairIEEE Transactions on Software Engineering10.1109/TSE.2019.294491447:10(2162-2181)Online publication date: 1-Oct-2021
https://doi.org/10.1109/TSE.2019.2944914
Yang NCuijpers PSchiffelers RLukkien JSerebrenik AEldh SFalessi D(2021)An interview study of how developers use execution logs in embedded software engineeringProceedings of the 43rd International Conference on Software Engineering: Software Engineering in Practice10.1109/ICSE-SEIP52600.2021.00015(61-70)Online publication date: 25-May-2021
https://dl.acm.org/doi/10.1109/ICSE-SEIP52600.2021.00015
Show More Cited By

Index Terms

Scenario-based and value-based specification mining: better together
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
    2. Software post-development issues
      1. Software reverse engineering

Recommendations

Mining scenario-based specifications with value-based invariants
OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference companion on Object oriented programming systems languages and applications

There have been a number of studies on mining candidate specifications from execution traces. Some extract specifications corresponding to value-based invariants, while others work on inferring ordering constraints. In this work, we merge our previous ...
Mining Hierarchical Scenario-Based Specifications
ASE '09: Proceedings of the 24th IEEE/ACM International Conference on Automated Software Engineering

Scalability over long traces, as well as comprehensibility and expressivity of results, are major challenges for dynamic analysis approaches to specification mining. In this work we present a novel use of object hierarchies over traces of inter-object ...
Mining modal scenario-based specifications from execution traces of reactive systems
ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering

Specification mining is a dynamic analysis process aimed at automatically inferring suggested specifications of a program from its execution traces. We describe a novel method, framework, and tool, for mining inter-object scenario-based specifications ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '10: Proceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering

September 2010

534 pages

ISBN:9781450301169

DOI:10.1145/1858996

General Chair:
Charles Pecheur
Université catholique de Louvain, Belgium
,
Program Chairs:
Jamie Andrews
University of Western Ontario, Canada
,
Elisabetta Di Nitto
Politecnico di Milano, Italy

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 September 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASE10

Sponsor:

ASE10: IEEE/ACM International Conference on Automated Software Engineering

September 20 - 24, 2010

Antwerp, Belgium

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
744
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nguyen HPhan HKhairunnesa SNguyen SYadavally AWang SRajan HNguyen T(2022)A Hybrid Approach for Inference between Behavioral Exception API Documentation and Implementations, and Its ApplicationsProceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering10.1145/3551349.3560434(1-13)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3551349.3560434
Afzal AMotwani MStolee KBrun YLe Goues C(2021)SOSRepair: Expressive Semantic Search for Real-World Program RepairIEEE Transactions on Software Engineering10.1109/TSE.2019.294491447:10(2162-2181)Online publication date: 1-Oct-2021
https://doi.org/10.1109/TSE.2019.2944914
Yang NCuijpers PSchiffelers RLukkien JSerebrenik AEldh SFalessi D(2021)An interview study of how developers use execution logs in embedded software engineeringProceedings of the 43rd International Conference on Software Engineering: Software Engineering in Practice10.1109/ICSE-SEIP52600.2021.00015(61-70)Online publication date: 25-May-2021
https://dl.acm.org/doi/10.1109/ICSE-SEIP52600.2021.00015
Bichhawat AFredrikson MYang J(2021)Automating Audit with Policy Inference2021 IEEE 34th Computer Security Foundations Symposium (CSF)10.1109/CSF51468.2021.00001(1-16)Online publication date: Jun-2021
https://doi.org/10.1109/CSF51468.2021.00001
Beschastnikh ILiu PXing AWang PBrun YErnst M(2020)Visualizing Distributed System ExecutionsACM Transactions on Software Engineering and Methodology10.1145/337563329:2(1-38)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1145/3375633
Zhou YWang CYan XChen TPanichella SGall H(2020)Automatic Detection and Repair Recommendation of Directive Defects in Java API DocumentationIEEE Transactions on Software Engineering10.1109/TSE.2018.287297146:9(1004-1023)Online publication date: 1-Sep-2020
https://doi.org/10.1109/TSE.2018.2872971
Zhong HMei H(2019)An Empirical Study on API UsagesIEEE Transactions on Software Engineering10.1109/TSE.2017.278228045:4(319-334)Online publication date: 1-Apr-2019
https://doi.org/10.1109/TSE.2017.2782280
Sun PBrown CBeschastnikh IStolee K(2019)Mining Specifications from Documentation using a Crowd2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER.2019.8668025(275-286)Online publication date: Feb-2019
https://doi.org/10.1109/SANER.2019.8668025
Motwani MBrun YAtlee JBultan TWhittle J(2019)Automatically generating precise Oracles from structured natural language specificationsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00035(188-199)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00035
Amar HBao LBusany NLo DMaoz SLeavens GGarcia APăsăreanu C(2018)Using finite-state models for log differencingProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3236069(49-59)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3236069
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten