Walkinshaw, Neil
[University of Leicester, Leicester, UK]
Lambeau, Bernard
[UCL]
Damas, Christophe
[UCL]
Bogdanov, Kirill
[University of Sheiffeld, UK]
Dupont, Pierre
[UCL]
Models play a crucial role in the development and maintenance of software systems, but are often neglected during the development process due to the considerable manual effort required to produce them. In response to this problem, numerous techniques have been developed that seek to automate the model generation task with the aid of increasingly accurate algorithms from the domain of Machine Learning. From an empirical perspective, these are extremely challenging to compare; there are many factors that are difficult to control (e.g. the richness of the input and the complexity of subject systems), and numerous practical issues that are just as troublesome (e.g. tool availability). This paper describes the StaMinA (State Machine Inference Approaches) competiton, that was designed to address these problems. The competition attracted numerous submissions, many of which were improved or adapted versions of techniques that had not been subjected to extensive empirical evaluations, and had not been evaluated with respect to their ability to infer models of software systems. This paper shows how many of these techniques substantially improve on the state of the art, providing insights into some of the factors that could underpin the success of the best techniques. In a more general sense it demonstrates the potential for competitions to act as a useful basis for empirical software engineering by (a) spurring the development of new techniques and (b) facilitating their comparative evaluation to an extent that would usually be prohibitively challenging without the active participation of the developers.
- Adriaans P, Jacobs C (2006) Using MDL for grammar induction. In: International colloquium on grammatical inference: algorithms and applications (ICGI). Lecture notes in artificial intelligence, vol 4201, pp 293–306
- Ammons G, Bodík R, Larus J (2002) Mining Specifications. In: Principles of programming languages (POPL). Portland, Oregon, pp 4–16
- Angluin Dana, On the complexity of minimum inference of regular sets, 10.1016/s0019-9958(78)90683-6
- Biermann A. W., Feldman J. A., On the Synthesis of Finite-State Machines from Samples of Their Behavior, 10.1109/tc.1972.5009015
- Biermann A.W., Krishnaswamy R., Constructing Programs from Example Computations, 10.1109/tse.1976.233812
- Combe David, de la Higuera Colin, Janodet Jean-Christophe, Zulu: An Interactive Learning Competition, Lecture Notes in Computer Science (2010) ISBN:9783642146831 p.139-146, 10.1007/978-3-642-14684-8_15
- Cook Jonathan E., Wolf Alexander L., Discovering models of software processes from event-based data, 10.1145/287000.287001
- Coste F, Nicolas J (1997) Regular inference as a graph coloring problem. In: Workshop on grammatical inference, automata induction, and language acquisition (ICML’97), pp 9–7
- Damas C., Lambeau B., Dupont P., van Lamsweerde A., Generating annotated behavior models from end-user scenarios, 10.1109/tse.2005.138
- Dupont Pierre, Lambeau Bernard, Damas Christophe, Lamsweerde Axel van, THE QSM ALGORITHM AND ITS APPLICATION TO SOFTWARE BEHAVIOR MODEL INDUCTION, 10.1080/08839510701853200
- Dupont P, Miclet L, Vidal E (1994) What is the search space of the regular inference? In: Proceedings of the international colloqium on grammatical inference and applications (ICGI’94). LNAI, vol 862. Springer Verlag, pp 25–37
- García P, de Parga M, López D, Ruiz J (2010) Learning automata teams. In: International colloquium on grammatical inference: algorithms and applications (ICGI). Springer, pp 52–65
- Gold E Mark, Complexity of automaton identification from given data, 10.1016/s0019-9958(78)90562-4
- Heule M, Verwer S (2010) Exact DFA identification using SAT solvers. In: International colloquium on grammatical inference: algorithms and applications (ICGI), vol 6339. Springer, pp 66–79
- Heule Marijn J. H., Verwer Sicco, Software model synthesis using satisfiability solvers, 10.1007/s10664-012-9222-z
- Hopcroft J, Motwani R, Ullman J (2007) Introduction to automata theory, languages, and computation, 3rd edn. Addison-Wesley
- Keller Robert M., Formal verification of parallel programs, 10.1145/360248.360251
- Kleinberg Jon M., Authoritative sources in a hyperlinked environment, 10.1145/324133.324140
- Lambeau B, Damas C, Dupont P (2008) State-merging DFA induction algorithms with mandatory merge constraints. In: International colloquium on grammatical inference: algorithms and applications (ICGI). Springer, pp 139–153
- van Lamsweerde A (2009) Requirements engineering: from system goals to UML models to software specifications. Wiley
- Lang K (1992) Random DFA’s can be approximately learned from sparse uniform examples. In: Proceedings of the international conference on learning theory (COLT’92), pp 45–52
- Lang K, Pearlmutter B, Price R (1998) Results of the abbadingo One DFA learning competition and a new evidence-driven state merging algorithm. In: International colloquium on grammatical inference and applications(ICGI). LNAI, vol 1433, pp 1–12
- Lee D., Yannakakis M., Principles and methods of testing finite state machines-a survey, 10.1109/5.533956
- Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data (or TKDD) 1(1)
- Lo D, Cheng H, Han J, Khoo S, Sun C (2009) Classification of software behaviors for failure detection: a discriminative pattern mining approach. In: International conference on knowledge discovery and data mining (KDD2009). ACM, pp 557–566
- Lo D, Khoo S (2006) SMArTIC: towards building an accurate, robust and scalable specification miner. In: Foundations of software engineering (FSE), pp 265–275
- Lorenzoli D, Mariani L, Pezzè M (2008) Automatic generation of software behavioral models. In: ICSE ’08: Proceedings of the 30th international conference on software engineering, pp 501–510
- Magee J, Kramer J (1999) Concurrency: state models and java programs. Wiley
- Mulder W, Jacobs C, van Someren M (2009) Collaborative DFA learning applied to grid administration. In: Benelearn, annual Belgian-Dutch conference on machine learning. Tilburg, the Netherlands, pp 38–46
- Van Nieuwpoort Rob V., Wrzesińska Gosia, Jacobs Ceriel J. H., Bal Henri E., Satin : A high-level and efficient grid programming model, 10.1145/1709093.1709096
- Oncina J., García P., INFERRING REGULAR LANGUAGES IN POLYNOMIAL UPDATED TIME, Series in Machine Perception and Artificial Intelligence (1992) ISBN:9789810208813 p.49-61, 10.1142/9789812797902_0004
- Raffelt Harald, Steffen Bernhard, Berg Therese, Margaria Tiziana, LearnLib: a framework for extrapolating behavioral models, 10.1007/s10009-009-0111-8
- Reiss S, Renieris M (2001) Encoding program executions. In: International conference on software engineering(ICSE), pp 221–230
- Rissanen Jorma, A Universal Prior for Integers and Estimation by Minimum Description Length, 10.1214/aos/1176346150
- Rousseeuw P, Ruts I, Tukey J (1999) The bagplot: a bivariate boxplot. Am Stat 53(4)
- Shahbaz M, Groz R (2009) Inferring mealy machines. In: FM 2009: formal methods, second world congress, Proceedings. Lecture notes in computer science, vol 5850. Springer, Eindhoven, The Netherlands, pp 207–222, 2–6 November 2009
- Sim S, Easterbrook S, Holt R (2003) Using benchmarking to advance research: a challenge to software engineering. In: International conference on software engineering (ICSE), pp 74–83
- Tukey J (1975) Mathematics and the picturing of data. In: Proceedings of the international congress of mathematicians, vol 2, pp 523–531
- Walkinshaw N, Bogdanov K (2008) Inferring finite-state models with temporal constraints. In: International conference on automated software engineering (ASE)
- Walkinshaw Neil, Bogdanov Kirill, Holcombe Mike, Salahuddin Sarah, Reverse Engineering State Machines by Interactive Grammar Inference, 10.1109/wcre.2007.45
- Walkinshaw Neil, Bogdanov Kirill, Holcombe Mike, Salahuddin Sarah, Improving dynamic software analysis by applying grammar inference principles, 10.1002/smr.373
- Walkinshaw N, Bogdanov K, Johnson K (2008) Evaluation and comparison of inferred regular grammars. In: International colloquium on grammatical inference: algorithms and applications (ICGI). Lecture notes in computer science, vol 5278. Springer, pp 252–265
Bibliographic reference |
Walkinshaw, Neil ; Lambeau, Bernard ; Damas, Christophe ; Bogdanov, Kirill ; Dupont, Pierre. STAMINA: A Competition to Encourage the Development and Assessment of Software Model Inference Techniques. In: Empirical Software Engineering : an international journal, Vol. 18, no.4, p. 791-824 (2013) |
Permanent URL |
http://hdl.handle.net/2078.1/141236 |