In this paper,we consider a testing setting where the set of possible definitions of the Implementation Under Test(IUT),as well as the behavior of each of these definitions in all possible interactions,are extensional...In this paper,we consider a testing setting where the set of possible definitions of the Implementation Under Test(IUT),as well as the behavior of each of these definitions in all possible interactions,are extensionally defined,i.e.,on an element-by-element and case-by-case basis.Under this setting,the problem of finding the minimum testing strategy such that collected observations will necessarily let us decide whether the IUT is correct or not(i.e.,whether it necessarily belongs to the set of possible correct definitions or not)is studied in four possible problem variants:with or without non-determinism;and with or without more than one possible definition in the sets of possible correct and incorrect definitions.The computational complexity of these variants is studied,and properties such as PSPACE-completeness and Log-APX-hardness are identified.展开更多
Software systems are present all around us and playing their vital roles in our daily life.The correct functioning of these systems is of prime concern.In addition to classical testing techniques,formal techniques lik...Software systems are present all around us and playing their vital roles in our daily life.The correct functioning of these systems is of prime concern.In addition to classical testing techniques,formal techniques like model checking are used to reinforce the quality and reliability of software systems.However,obtaining of behavior model,which is essential for model-based techniques,of unknown software systems is a challenging task.To mitigate this problem,an emerging black-box analysis technique,called Model Learning,can be applied.It complements existing model-based testing and verification approaches by providing behavior models of blackbox systems fully automatically.This paper surveys the model learning technique,which recently has attracted much attention from researchers,especially from the domains of testing and verification.First,we review the background and foundations of model learning,which form the basis of subsequent sections.Second,we present some well-known model learning tools and provide their merits and shortcomings in the form of a comparison table.Third,we describe the successful applications of model learning in multidisciplinary fields,current challenges along with possible future works,and concluding remarks.展开更多
基金This work has been partially supported by project PID2019-108528RB-C22by Comunidad de Madrid as part of the program S2018/TCS-4339(BLOQUES-CM)co-funded by EIE Funds of the European Union.
文摘In this paper,we consider a testing setting where the set of possible definitions of the Implementation Under Test(IUT),as well as the behavior of each of these definitions in all possible interactions,are extensionally defined,i.e.,on an element-by-element and case-by-case basis.Under this setting,the problem of finding the minimum testing strategy such that collected observations will necessarily let us decide whether the IUT is correct or not(i.e.,whether it necessarily belongs to the set of possible correct definitions or not)is studied in four possible problem variants:with or without non-determinism;and with or without more than one possible definition in the sets of possible correct and incorrect definitions.The computational complexity of these variants is studied,and properties such as PSPACE-completeness and Log-APX-hardness are identified.
基金the National Natural Science Foundation of China(NSFC)(Grant Nos.61872016,61932007 and 61972013).
文摘Software systems are present all around us and playing their vital roles in our daily life.The correct functioning of these systems is of prime concern.In addition to classical testing techniques,formal techniques like model checking are used to reinforce the quality and reliability of software systems.However,obtaining of behavior model,which is essential for model-based techniques,of unknown software systems is a challenging task.To mitigate this problem,an emerging black-box analysis technique,called Model Learning,can be applied.It complements existing model-based testing and verification approaches by providing behavior models of blackbox systems fully automatically.This paper surveys the model learning technique,which recently has attracted much attention from researchers,especially from the domains of testing and verification.First,we review the background and foundations of model learning,which form the basis of subsequent sections.Second,we present some well-known model learning tools and provide their merits and shortcomings in the form of a comparison table.Third,we describe the successful applications of model learning in multidisciplinary fields,current challenges along with possible future works,and concluding remarks.
