Complexity of adaptive testing in scenarios defined extensionally

doi:10.1007/s11704-022-1673-9

Front. Comput. Sci.

2023, Vol. 17

Issue (3) : 173206 https://doi.org/10.1007/s11704-022-1673-9

RESEARCH ARTICLE

Complexity of adaptive testing in scenarios defined extensionally

Ismael RODRÍGUEZ^1,², David RUBIO³, Fernando RUBIO^1,²(

)

¹. Dpto. Sistemas Informáticos y Computación, Facultad de Informática, Universidad Complutense de Madrid,Madrid 28040, Spain
². Instituto de Tecnologías del Conocimiento, Universidad Complutense de Madrid, Madrid 28040, Spain
³. Instituto de Biomecánica de Valencia. Universitat Politècnica de València, València 46022, Spain

Download: PDF(2819 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

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.

Keywords formal testing adaptive testing computational complexity PSPACE-completeness approximation hardness

Corresponding Author(s): Fernando RUBIO

About author:

Tongcan Cui and Yizhe Hou contributed equally to this work.

Just Accepted Date: 22 April 2022 Issue Date: 20 October 2022

Cite this article:

Ismael RODRÍGUEZ,David RUBIO,Fernando RUBIO. Complexity of adaptive testing in scenarios defined extensionally[J]. Front. Comput. Sci., 2023, 17(3): 173206.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-1673-9
https://academic.hep.com.cn/fcs/EN/Y2023/V17/I3/173206

Fig.1 The possible definitions of the IUT. Definitions

f 1

−

f 3

are considered correct, whereas

f 4

−

f 13

are considered incorrect

Fig.2 Adaptive testing strategy applying at most two test cases in all situations

1	D, Lee M Yannakakis . Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE, 1996, 84( 8): 1090–1123
2	A Petrenko . Fault model-driven test derivation from finite state models: annotated bibliography. In: Proceedings of the 4th Summer School on Modeling and Verification of Parallel Processes. 2001, 196–205
3	R, Dorofeeva K, El-Fakih S, Maag A R, Cavalli N Yevtushenko . FSM-based conformance testing methods: a survey annotated with experimental evaluation. Information and Software Technology, 2010, 52( 12): 1286–1297
4	J Tretmans . Conformance testing with labelled transition systems: implementation relations and test generation. Computer Networks and ISDN Systems, 1996, 29( 1): 49–79
5	J Tretmans . Testing concurrent systems: a formal approach. In: Proceedings of the 10th International Conference on Concurrency Theory. 1999, 46–65
6	E, Brinksma J Tretmans . Testing transition systems: an annotated bibliography. In: Proceedings of the 4th Summer School on Modeling and Verification of Parallel Processes. 2001, 187–195
7	J, Springintveld F, Vaandrager P R D’Argenio . Testing timed automata. Theoretical Computer Science, 2001, 254( 1-2): 225–257
8	M, Krichen S Tripakis . Black-box conformance testing for real-time systems. In: Proceedings of the 11th International SPIN Workshop on Model Checking of Software. 2004, 109–126
9	I, Berrada R, Castanet P, Félix A Salah . Test case minimization for real-time systems using timed bound traces. In: Proceedings of the 18th IFIP TC 6/WG 6.1 International Conference on Testing of Communicating Systems. 2006, 289–305
10	M, Merayo M, Núñez I Rodríguez . Extending EFSMs to specify and test timed systems with action durations and time-outs. IEEE Transactions on Computers, 2008, 57( 6): 835–844
11	M, Stoelinga F Vaandrager . A testing scenario for probabilistic automata. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 2003, 464–477
12	N, López M, Núñez I Rodríguez . Specification, testing and implementation relations for symbolic-probabilistic systems. Theoretical Computer Science, 2006, 353( 1−3): 228–248
13	M, Efatmaneshnik S, Shoval K Joiner . System test architecture evaluation: a probabilistic modeling approach. IEEE Systems Journal, 2019, 13( 4): 3651–3662
14	L J Morell . A theory of fault-based testing. IEEE Transactions on Software Engineering, 1990, 16( 8): 844–857
15	R M Hierons . Comparing test sets and criteria in the presence of test hypotheses and fault domains. ACM Transactions on Software Engineering and Methodology, 2002, 11( 4): 427–448
16	R M Hierons . Verdict functions in testing with a fault domain or test hypotheses. ACM Transactions on Software Engineering and Methodology, 2009, 18( 4): 14
17	I, Rodríguez M G, Merayo M Núñez . HOTL: hypotheses and observations testing logic. The Journal of Logic and Algebraic Programming, 2008, 74( 2): 57–93
18	I, Rodríguez L, Llana P Rabanal . A general testability theory: classes, properties, complexity, and testing reductions. IEEE Transactions on Software Engineering, 2014, 40( 9): 862–894
19	I, Rodríguez F, Rosa-Velardo F Rubio . Introducing complexity to formal testing. Journal of Logical and Algebraic Methods in Programming, 2020, 111: 100502
20	N, Kushik N Yevtushenko . Adaptive homing is in P. In: Proceedings of the 10th Workshop on Model-Based Testing. 2015, 73–78
21	H, Yenigün N, Yevtushenko N Kushik . The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs. Information Processing Letters, 2017, 127: 49–53
22	N, Kushik N, Yevtushenko H Yenigun . Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. In: Proceedings of the 4th International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn. 2016, 83–90
23	A, Petrenko N Yevtushenko . Adaptive testing of deterministic implementations specified by nondeterministic FSMs. In: Proceedings of the 23rd IFIP WG 6.1 International Conference on Testing Software and Systems. 2011, 162–178
24	A, Petrenko N Yevtushenko . Adaptive testing of nondeterministic systems with FSM. In: Proceedings of the 15th IEEE International Symposium on High-Assurance Systems Engineering. 2014, 224–228
25	den Bos P, van F Vaandrager . State identification for labeled transition systems with inputs and outputs. In: Proceedings of the 16th International Conference on Formal Aspects of Component Software. 2019, 191–212
26	R, Bloem G, Fey F, Greif R, Könighofer I, Pill H, Riener F Röck . Synthesizing adaptive test strategies from temporal logic specifications. Formal Methods in System Design, 2019, 55( 2): 103–135
27	I Rodríguez . A general testability theory. In: Proceedings of the 20th International Conference on Concurrency Theory. 2009, 572–586
28	P Crescenzi . A short guide to approximation preserving reductions. In: Proceedings of the 12th Annual IEEE Conference on Computational Complexity. 1997, 262–273
29	U Feige . A threshold of ln n for approximating set cover. Journal of the ACM, 1998, 45( 4): 634–652
30	M Sipser . Introduction to the Theory of Computation. Boston: Cengage Learning, 2012
31	L Stockmeyer . Classifying the computational complexity of problems. The Journal of Symbolic Logic, 1987, 52( 1): 1–43

[1]

FCS-21673-OF-IR_suppl_1

Download

[1]	Yang WANG, Mingqiang WANG. On the hardness of NTRU problems[J]. Front. Comput. Sci., 2022, 16(6): 166822-.
[2]	Qingliang CHEN,Kaile SU,Abdul SATTAR,Xiangyu LUO,Aixiang CHEN. A first-order coalition logic for BDI-agents[J]. Front. Comput. Sci., 2016, 10(2): 233-245.
[3]	Silvano COLOMBO TOSATTO,Pierre KELSEN,Qin MA,Marwane el KHARBILI,Guido GOVERNATORI,Leendert van der TORRE. Algorithms for tractable compliance problems[J]. Front. Comput. Sci., 2015, 9(1): 55-74.

Viewed

Full text

Abstract

Cited

Shared

Discussed