Scenario-based and value-based specification mining: better together | Automated Software Engineering Skip to main content
Springer Nature Link
Log in

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

  • Published:
Automated Software Engineering Aims and scope Submit manuscript

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 a data-mining algorithm 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.

We have implemented the mining algorithm and the visual presentation of the mined scenarios within a standard development environment. 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The original notation is slightly modified for brevity.

  2. Please refer to the detailed description in Sect. 8.6.

  3. CrossFTP server is available from http://sourceforge.net/projects/crossftpserver/, Jeti is available from http://jeti.sourceforge.net/, Columba is available from http://sourceforge.net/projects/columba/, and Thingamablog is available from http://www.thingamablog.com/.

References

  • Accompanying Website & Technical Report: LSC mining with value-based invariants. Supplementary material (2011). http://www.mysmu.edu/faculty/davidlo/inv/invariants.html

  • Acharya, M., Xie, T., Xu, J.: Mining interface specifications for generating checkable robustness properties. In: Proc. of International Symposium on Software Reliability Engineering (ISSRE), pp. 311–320 (2006)

    Google Scholar 

  • Acharya, M., Xie, T., Pei, J., Xu, J.: Mining API patterns as partial orders from source code: from usage scenarios to specifications. In: Proc. of Joint Symposium on the Foundations of Software Engineering and European Software Engineering Conference (ESEC/SIGSOFT FSE), pp. 25–34 (2007)

    Chapter  Google Scholar 

  • Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: Proc. of International Conference on Very Large Data Bases (VLDB), pp. 487–499 (1994)

    Google Scholar 

  • Agrawal, R., Srikant, R.: Mining sequential patterns. In: Proc. of International Conference on Data Engineering (ICDE), pp. 3–14 (1995)

    Google Scholar 

  • Ammons, G., Bodík, R., Larus, J.R.: Mining specifications. In: Proc. of Symposium on Principles of Programming Languages (POPL), pp. 4–16 (2002)

    Google Scholar 

  • Boshernitsan, M., Doong, R.K., Savoia, A.: From Daikon to Agitator: Lessons and challenges in building a commercial tool for developer testing. In: Proc. of International Symposium on Software Testing and Analysis (ISSTA), pp. 169–180 (2006)

    Chapter  Google Scholar 

  • Dallmeier, V., Lindig, C., Wasylkowski, A., Zeller, A.: Mining object behavior with ADABU. In: Proc. of International Workshop on Dynamic Analysis (WODA), pp. 17–24 (2006)

    Chapter  Google Scholar 

  • Damm, W., Harel, D.: LSCs: breathing life into message sequence charts. Form. Methods Syst. Des. 19(1), 45–80 (2001)

    Article  MATH  Google Scholar 

  • Dwyer, M.B., Avrunin, G.S., Corbett, J.C.: Patterns in property specifications for finite-state verification. In: Proc. of International Conference on Software Engineering (ICSE), pp. 411–420 (1999)

    Chapter  Google Scholar 

  • EclipseTPTP: Eclipse test and performance tools platform (2011). http://www.eclipse.org/tptp/

  • El-Ramly, M., Stroulia, E., Sorenson, P.G.: From run-time behavior to usage scenarios: an interaction-pattern mining approach. In: Proc. of International Conference on Knowledge Discovery and Data Mining (KDD), pp. 315–324 (2002)

    Google Scholar 

  • Ernst, M., Cockrell, J., Griswold, W., Notkin, D.: Dynamically discovering likely program invariants to support program evolution. IEEE Trans. Softw. Eng. 27(2), 99–123 (2001)

    Article  Google Scholar 

  • Ernst, M.D., Perkins, J.H., Guo, P.J., McCamant, S., Pacheco, C., Tschantz, M.S., Xiao, C.: The Daikon system for dynamic detection of likely invariants. Sci. Comput. Program. 69(1–3), 35–45 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Gabel, M., Su, Z.: Symbolic mining of temporal specifications. In: Proc. of International Conference on Software Engineering (ICSE), pp. 51–60 (2008)

    Google Scholar 

  • Goues, C.L., Weimer, W.: Specification mining with few false positives. In: Proc. of International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 292–306 (2009)

    Chapter  Google Scholar 

  • Guo, P.J., Perkins, J.H., McCamant, S., Ernst, M.D.: Dynamic inference of abstract types. In: Proc. of International Symposium on Software Testing and Analysis (ISSTA), pp. 255–265 (2006)

    Chapter  Google Scholar 

  • Han, J., Kamber, M.: Data Mining Concepts and Techniques. Morgan Kaufmann, San Mateo (2006)

    MATH  Google Scholar 

  • Han, J., Pei, J.: Mining frequent patterns by pattern-growth: methodology and implications. ACM SIGKDD Explor. 2(2), 14–20 (2000)

    Article  Google Scholar 

  • Harel, D.: From play-in scenarios to code: an achievable dream. Computer 34(1), 53–60 (2001)

    Article  MathSciNet  Google Scholar 

  • Harel, D., Maoz, S.: Assert and negate revisited: modal semantics for UML sequence diagrams. Softw. Syst. Model. 7(2), 237–252 (2008)

    Article  Google Scholar 

  • Harel, D., Marelly, R.: Come, Let’s Play: Scenario-Based Programming Using LSCs and the Play-Engine. Springer, Berlin (2003)

    Google Scholar 

  • Harel, D., Kleinbort, A., Maoz, S.: S2A: A compiler for multi-modal UML sequence diagrams. In: Proc. of International Conference on Fundamental Approaches to Software Engineering (FASE), pp. 121–124 (2007)

    Chapter  Google Scholar 

  • Harel, D., Maoz, S., Szekely, S., Barkan, D.: PlayGo: towards a comprehensive tool for scenario based programming. In: Proc. of International Conference on Automated Software Engineering (ASE), pp. 359–360 (2010)

    Google Scholar 

  • Jerding, D.F., Stasko, J.T., Ball, T.: Visualizing interactions in program executions. In: Proc. of International Conference on Software Engineering (ICSE), pp. 360–370 (1997)

    Google Scholar 

  • Klein, F., Giese, H.: Joint structural and temporal property specification using timed story scenario diagrams. In: Proc. of International Conference on Fundamental Approaches to Software Engineering (FASE), pp. 185–199 (2007)

    Chapter  Google Scholar 

  • Klose, J., Toben, T., Westphal, B., Wittke, H.: Check it out: on the efficient formal verification of live sequence charts. In: Proc. of International Conference on Computer Aided Verification (CAV), pp. 219–233 (2006)

    Chapter  Google Scholar 

  • Krüger, I.: Capturing overlapping, triggered, and preemptive collaborations using MSCs. In: Proc. of International Conference on Fundamental Approaches to Software Engineering (FASE), pp. 387–402 (2003)

    Chapter  Google Scholar 

  • Kugler, H., Segall, I.: Compositional synthesis of reactive systems from live sequence chart specifications. In: Proc. of International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 77–91 (2009)

    Chapter  Google Scholar 

  • Kugler, H., Harel, D., Pnueli, A., Lu, Y., Bontemps, Y.: Temporal logic for scenario-based specifications. In: Proc. of International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 445–460 (2005)

    Chapter  Google Scholar 

  • Lettrari, M., Klose, J.: Scenario-based monitoring and testing of real-time UML models. In: Proc. of International Conference on the Unified Modeling Language (UML), pp. 317–328 (2001)

    Google Scholar 

  • Li, J., Li, H., Wong, L., Pei, J., Dong, G.: Minimum description length principle: generators are preferable to closed patterns. In: Proc. of Conference on Artificial Intelligence (AAAI) (2006)

    Google Scholar 

  • Li, Z., Zhou, Y.: PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code. In: Proc. of Joint Symposium on the Foundations of Software Engineering and European Software Engineering Conference (ESEC/SIGSOFT FSE), pp. 306–315 (2005)

    Google Scholar 

  • Livshits, V.B., Nori, A.V., Rajamani, S.K., Banerjee, A.: Merlin: specification inference for explicit information flow problems. In: Proc. of Conference on Programming Language Design and Implementation (PLDI), pp. 75–86 (2009)

    Chapter  Google Scholar 

  • Lo, D., Khoo, S.C.: SMArTIC: towards building an accurate, robust and scalable specification miner. In: Proc. of Symposium on the Foundations of Software Engineering (SIGSOFT FSE), pp. 265–275 (2006)

    Google Scholar 

  • Lo, D., Maoz, S.: Mining scenario-based triggers and effects. In: Proc. of International Conference on Automated Software Engineering (ASE), pp. 109–118 (2008a)

    Google Scholar 

  • Lo, D., Maoz, S.: Specification mining of symbolic scenario-based models. In: Proc. of Workshop on Program Analysis For Software Tools and Engineering (PASTE), pp. 29–35 (2008b)

    Google Scholar 

  • Lo, D., Maoz, S.: Mining hierarchical scenario-based specifications. In: Proc. of International Conference on Automated Software Engineering (ASE), pp. 359–370 (2009)

    Google Scholar 

  • Lo, D., Maoz, S.: Scenario-based and value-based specification mining: better together. In: Proc. of International Conference on Automated Software Engineering (ASE), pp. 387–396 (2010)

    Google Scholar 

  • Lo, D., Maoz, S.: Towards succinctness in mining scenario-based specifications. In: Proc. of International Conference on Engineering of Complex Computer Systems (ICECCS), pp. 231–240 (2011)

    Chapter  Google Scholar 

  • Lo, D., Maoz, S., Khoo, S.C.: Mining modal scenario-based specifications from execution traces of reactive systems. In: Proc. of International Conference on Automated Software Engineering (ASE), pp. 465–468 (2007)

    Google Scholar 

  • Lo, D., Khoo, S.C., Li, J.: Mining and ranking generators of sequential patterns. In: Proc. of SIAM International Conference on Data Mining (SDM), pp. 553–564 (2008)

    Google Scholar 

  • Lo, D., Ramalingam, G., Ranganath, V.P., Vaswani, K.: Mining quantified temporal rules: formalism, algorithms, and evaluation. In: Proc. of Working Conference on Reverse Engineering (WCRE), pp. 62–71 (2009)

    Google Scholar 

  • Lorenzoli, D., Mariani, L., Pezzè, M.: Automatic generation of software behavioral models. In: Proc. of International Conference on Software Engineering (ICSE), pp. 501–510 (2008)

    Google Scholar 

  • Maoz, S., Harel, D.: From multi-modal scenarios to code: compiling LSCs into AspectJ. In: Proc. of Symposium on the Foundations of Software Engineering (SIGSOFT FSE), pp. 219–230 (2006)

    Google Scholar 

  • Maoz, S., Harel, D.: On tracing reactive systems. Softw. Syst. Model. 10(4), 447–468 (2011)

    Article  Google Scholar 

  • Maoz, S., Metsä, J., Katara, M.: Model-based testing using LSCs and S2A. In: Proc. of International Conference on Model Driven Engineering Languages and Systems (MoDELS), pp. 301–306 (2009)

    Chapter  Google Scholar 

  • Maoz, S., Harel, D., Kleinbort, A.: A compiler for multimodal scenarios: transforming LSCs into AspectJ. ACM Trans. Softw. Eng. Methodol. 20(4), 18 (2011)

    Article  Google Scholar 

  • Mariani, L., Pezzè, M.: Behavior capture and test: automated analysis of component integration. In: Proc. of International Conference on Engineering of Complex Computer Systems (ICECCS), pp. 292–301 (2005)

    Google Scholar 

  • Mariani, L., Papagiannakis, S., Pezzè, M.: Compatibility and regression testing of COTS-component-based software. In: Proc. of International Conference on Software Engineering (ICSE), pp. 85–95 (2007)

    Chapter  Google Scholar 

  • Milea, N., Khoo, S.C., Lo, D., Pop, C.: Nort: Runtime anomaly-based monitoring of malicious behavior for windows. In: Proc. of International Conference on Runtime Verification (RV) (2011)

    Google Scholar 

  • Olender, K., Osterweil, L.: Cecil: a sequencing constraint language for automatic static analysis generation. IEEE Trans. Softw. Eng. 16, 268–280 (1990)

    Article  Google Scholar 

  • Pytlik, B., Renieris, M., Krishnamurthi, S., Reiss, S.P.: Automated fault localization using potential invariants. CoRR cs.SE/0310040 (2003)

  • Quante, J., Koschke, R.: Dynamic protocol recovery. In: Proc. of Working Conference on Reverse Engineering (WCRE), pp. 219–228 (2007)

    Google Scholar 

  • Ramanathan, M.K., Grama, A., Jagannathan, S.: Path-sensitive inference of function precedence protocols. In: Proc. of International Conference on Software Engineering (ICSE), pp. 240–250 (2007a)

    Chapter  Google Scholar 

  • Ramanathan, M.K., Grama, A., Jagannathan, S.: Static specification inference using predicate mining. In: Proc. of Conference on Programming Language Design and Implementation (PLDI), pp. 123–134 (2007b)

    Google Scholar 

  • Safyallah, H., Sartipi, K.: Dynamic analysis of software systems using execution pattern mining. In: Proc. of International Conference on Program Comprehension (ICPC), pp. 84–88 (2006)

    Chapter  Google Scholar 

  • Santelices, RA, Chittimalli, P.K., Apiwattanapong, T., Orso, A., Harrold, M.J.: Test-suite augmentation for evolving software. In: Proc. of International Conference on Automated Software Engineering (ASE), pp. 218–227 (2008)

    Google Scholar 

  • Shoham, S., Yahav, E., Fink, S., Pistoia, M.: Static specification mining using automata-based abstractions. In: Proc. of International Symposium on Software Testing and Analysis (ISSTA), pp. 174–184 (2007)

    Chapter  Google Scholar 

  • Sibay, G., Uchitel, S., Braberman, VA: Existential live sequence charts revisited. In: Proc. of International Conference on Software Engineering (ICSE), pp. 41–50 (2008)

    Google Scholar 

  • Sun, J., Dong, J.S.: Synthesis of distributed processes from scenario-based specifications. In: Proc. of International Symposium on Formal Methods (FM), pp. 415–431 (2005)

    Google Scholar 

  • Uchitel, S., Kramer, J., Magee, J.: Detecting implied scenarios in message sequence chart specifications. In: Proc. of Symposium on the Foundations of Software Engineering (SIGSOFT FSE), pp. 74–82 (2001)

    Google Scholar 

  • Wang, J., Han, J.: BIDE: efficient mining of frequent closed sequences. In: Proc. of International Conference on Data Engineering (ICDE), pp. 79–90 (2004)

    Chapter  Google Scholar 

  • Wang, J., Han, J., Pei, J.: Closet+: searching for the best strategies for mining frequent closed itemsets. In: Proc. of International Conference on Knowledge Discovery and Data Mining (KDD), pp. 236–245 (2003)

    Google Scholar 

  • Wasylkowski, A., Zeller, A.: Mining temporal specifications from object usage. In: Proc. of International Conference on Automated Software Engineering (ASE), pp. 295–306 (2009)

    Google Scholar 

  • Wasylkowski, A., Zeller, A.: Mining temporal specifications from object usage. Autom. Softw. Eng. 18(3–4), 263–292 (2011)

    Article  Google Scholar 

  • Weimer, W., Necula, G.C.: Mining temporal specifications for error detection. In: Proc. of International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 461–476 (2005)

    Chapter  Google Scholar 

  • Xie, T., Thummalapenta, S., Lo, D., Liu, C.: Data mining for software engineering. Computer 42(8), 35–42 (2009)

    Google Scholar 

  • Xu, Z., Cohen, M.B., Rothermel, G.: Factors affecting the use of genetic algorithms in test suite augmentation. In: Proc. of Annual Genetic and Evolutionary Computation Conference (GECCO), pp. 1365–1372 (2010)

    Chapter  Google Scholar 

  • Yang, J., Evans, D., Bhardwaj, D., Bhat, T., Das, M.: Perracotta: mining temporal API rules from imperfect traces. In: Proc. of International Conference on Software Engineering (ICSE), pp. 282–291 (2006)

    Google Scholar 

Download references

Acknowledgements

We would like to thank Smadar Szekely for her advice and assistance in using components from PlayGo for the profile definition and the presentation of the mined scenarios.

Author information

Authors and Affiliations

  1. School of Information Systems, Singapore Management University, Singapore, Singapore

    David Lo

  2. Dept. of Computer Science 3, Software Engineering, RWTH Aachen University, Aachen, Germany

    Shahar Maoz

Authors
  1. David Lo
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Shahar Maoz
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to David Lo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lo, D., Maoz, S. Scenario-based and value-based specification mining: better together. Autom Softw Eng 19, 423–458 (2012). https://doi.org/10.1007/s10515-012-0103-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10515-012-0103-x

Keywords