Fidelity Is Not Effectiveness: Limits of the Mutation Score in LLM-Inferred Mealy Machines
Resumo
Model-based testing (MBT) derives test cases from behavioral models, whose construction may require manual effort and specialized knowledge. Large language models (LLMs) offer an alternative by inferring such models directly from natural-language requirements, but the resulting test suites are trustworthy only if the inferred model faithfully represents the expected behavior. We investigate whether the mutation effectiveness of input sequences generated from an inferred Mealy machine provides sufficient evidence of behavioral fidelity. In a retrospective analysis of 30 pipeline runs, all final modelswere valid and minimal, but twowere behaviorally non-equivalent to the reference even though their test suites achieved the same mutation score as a suite generated from the reference model. We prospectively replicated the experiment with 50 runs under a predefined protocol and a fixed LLM version. Seven runs again produced non-equivalent models whose suites achieved the same score as the reference-derived suite across three classical FSM test-generation methods. The result persists after excluding mutants that make the machines partial and does not arise because the two test suites are identical. A contrasting case shows that mutation score can reveal a loss of test effectiveness when model errors alter the selected input sequences. Therefore, mutation effectiveness is useful as a complementary measure, but equality with the reference-derived score does not certify behavioral fidelity. Formal validity, behavioral equivalence, and test-suite effectiveness should be evaluated separately.
Referências
James H. Andrews, Lionel C. Briand, and Yvan Labiche. 2005. Is Mutation an Appropriate Tool for Testing Experiments?. In Proceedings of the 27th International Conference on Software Engineering (ICSE). Association for Computing Machinery, New York, NY, USA, 402–411. DOI: 10.1145/1062455.1062530
Dana Angluin. 1987. Learning Regular Sets from Queries and Counterexamples. Information and Computation 75, 2 (1987), 87–106. DOI: 10.1016/0890-5401(87)90052-6
Earl T. Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. 2015. The Oracle Problem in Software Testing: A Survey. IEEE Transactions on Software Engineering 41, 5 (2015), 507–525. DOI: 10.1109/TSE.2014.2372785
Lawrence D. Brown, T. Tony Cai, and Anirban DasGupta. 2001. Interval Estimation for a Binomial Proportion. Statist. Sci. 16, 2 (2001), 101–133. DOI: 10.1214/ss/1009213286
Tsun S. Chow. 1978. Testing Software Design Modeled by Finite-State Machines. IEEE Transactions on Software Engineering SE-4, 3 (1978), 178–187. DOI: 10.1109/TSE.1978.231496
Rita Dorofeeva, Khaled El-Fakih, Stéphane Maag, Ana R. Cavalli, and Nina Yevtushenko. 2010. FSM-based Conformance Testing Methods: A Survey Annotated with Experimental Evaluation. Information and Software Technology 52, 12 (2010), 1286–1297. DOI: 10.1016/j.infsof.2010.07.001
Sandra C. P. F. Fabbri, Márcio Eduardo Delamaro, José Carlos Maldonado, and Paulo César Masiero. 1994. Mutation Analysis Testing for Finite State Machines. In Proceedings of the 5th International Symposium on Software Reliability Engineering (ISSRE). IEEE Computer Society Press, Los Alamitos, CA, USA, 220–229. DOI: 10.1109/ISSRE.1994.341378
Christopher Foster, Abhishek Gulati, Mark Harman, Inna Harper, Ke Mao, Jillian Ritchey, Hervé Robert, and Shubho Sengupta. 2025. Mutation-Guided LLMBased Test Generation at Meta. In Companion Proceedings of the 33rd ACM International Conference on the Foundations of Software Engineering (FSE Companion). Association for Computing Machinery, New York, NY, USA, 180–191. DOI: 10.1145/3696630.3728544
Susumu Fujiwara, Gregor von Bochmann, Ferhat Khendek, Mokhtar Amalou, and Abderrazak Ghedamsi. 1991. Test Selection Based on Finite State Models. IEEE Transactions on Software Engineering 17, 6 (1991), 591–603. DOI: 10.1109/32.87284
René Just, Darioush Jalali, Laura Inozemtseva, Michael D. Ernst, Reid Holmes, and Gordon Fraser. 2014. Are Mutants a Valid Substitute for Real Faults in Software Testing?. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE). ACM, New York, NY, USA, 654–665. DOI: 10.1145/2635868.2635929
David Lee and Mihalis Yannakakis. 1996. Principles and Methods of Testing Finite State Machines—A Survey. Proc. IEEE 84, 8 (1996), 1090–1123. DOI: 10.1109/5.533956
Gang Luo, Alexandre Petrenko, and Gregor von Bochmann. 1995. Selecting Test Sequences for Partially-Specified Nondeterministic Finite State Machines. In Protocol Test Systems VII. Springer, Boston, MA, USA, 95–110. DOI: 10.1007/978-0-387-34883-4_6
Arghavan Moradi Dakhel, Amin Nikanjam, Vahid Majdinasab, Foutse Khomh, and Michel C. Desmarais. 2024. Effective Test Generation Using Pre-Trained Large Language Models and Mutation Testing. Information and Software Technology 171 (2024), 107468. DOI: 10.1016/j.infsof.2024.107468
Omer Nguena Timo, Paul-Alexis Rodriguez, and Florent Avellaneda. 2026. Designing FSMs Specifications from Requirements with GPT 4.0. arXiv:2603.29140 [cs.SE] DOI: 10.48550/arXiv.2603.29140
Mark Utting, Alexander Pretschner, and Bruno Legeard. 2012. A Taxonomy of Model-Based Testing Approaches. Software Testing, Verification and Reliability 22, 5 (2012), 297–312. DOI: 10.1002/stvr.456
Frits Vaandrager. 2017. Model Learning. Commun. ACM 60, 2 (2017), 86–95. DOI: 10.1145/2967606
Frits Vaandrager and Ivo Melse. 2025. New Fault Domains for Conformance Testing of Finite State Machines. In 36th International Conference on Concurrency Theory (CONCUR 2025) (LIPIcs, Vol. 348). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 34:1–34:22. DOI: 10.4230/LIPIcs.CONCUR.2025.34
M. P. Vasilevskii. 1973. Failure Diagnosis of Automata. Cybernetics 9, 4 (1973), 653–665. DOI: 10.1007/BF01068590
Junjie Wang, Yuchao Huang, Chunyang Chen, Zhe Liu, Song Wang, and Qing Wang. 2024. Software Testing With Large Language Models: Survey, Landscape, and Vision. IEEE Transactions on Software Engineering 50, 4 (2024), 911–936. DOI: 10.1109/TSE.2024.3368208
Edwin B. Wilson. 1927. Probable Inference, the Law of Succession, and Statistical Inference. J. Amer. Statist. Assoc. 22, 158 (1927), 209–212. DOI: 10.1080/01621459.1927.10502953
Yuheng Wu, Berk Gokmen, Zhouhua Xie, Peijing Li, Caroline Trippel, Priyanka Raina, and Thierry Tambe. 2026. LLM-FSM: Scaling Large Language Models for Finite-State Reasoning in RTL Code Generation. arXiv:2602.07032 [cs.AR] DOI: 10.48550/arXiv.2602.07032
Cheng Xu, Shuhao Guan, Derek Greene, and M-Tahar Kechadi. 2024. Benchmark Data Contamination of Large Language Models: A Survey. arXiv:2406.04244 [cs.CL] DOI: 10.48550/arXiv.2406.04244
