Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Practical Constraint Solving for Generating System Test Data

Published: 29 April 2020 Publication History

Abstract

The ability to generate test data is often a necessary prerequisite for automated software testing. For the generated data to be fit for their intended purpose, the data usually have to satisfy various logical constraints. When testing is performed at a system level, these constraints tend to be complex and are typically captured in expressive formalisms based on first-order logic. Motivated by improving the feasibility and scalability of data generation for system testing, we present a novel approach, whereby we employ a combination of metaheuristic search and Satisfiability Modulo Theories (SMT) for constraint solving. Our approach delegates constraint solving tasks to metaheuristic search and SMT in such a way as to take advantage of the complementary strengths of the two techniques. We ground our work on test data models specified in UML, with OCL used as the constraint language. We present tool support and an evaluation of our approach over three industrial case studies. The results indicate that, for complex system test data generation problems, our approach presents substantial benefits over the state-of-the-art in terms of applicability and scalability.

References

[1]
Shaukat Ali, Lionel C. Briand, Hadi Hemmati, and Rajwinder Kaur Panesar-Walawege. 2010. A systematic review of the application and empirical investigation of search-based test case generation. IEEE Trans. Softw. Eng. 36, 6 (2010), 742--762.
[2]
Shaukat Ali, Muhammad Zohaib Z. Iqbal, Andrea Arcuri, and Lionel C. Briand. 2013. Generating test data from OCL with search techniques. IEEE Trans. Softw. Eng. 39, 10 (2013), 1376--1402.
[3]
Shaukat Ali, Muhammad Zohaib Z. Iqbal, Maham Khalid, and Andrea Arcuri. 2016. Improving the performance of OCL constraint solving with novel heuristics for logical operations: A search-based approach. Emp. Softw. Eng. 21, 6 (2016), 2459--2502.
[4]
Paul Ammann and Jeff Offutt. 2016. Introduction to Software Testing (2nd ed.). Cambridge University Press.
[5]
Kyriakos Anastasakis. 2009. UML2Alloy (Version 0.52). Retrieved from http://www.cs.bham.ac.uk/∼bxb/UML2Alloy/.
[6]
Kyriakos Anastasakis, Behzad Bordbar, Geri Georg, and Indrakshi Ray. 2007. UML2Alloy: A challenging model transformation. In Proceedings of the 10th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems (MoDELS’07). 436--450.
[7]
Apache Foundation. 2006. Apache OpenJPA. Retrieved from http://openjpa.apache.org/.
[8]
Clark W. Barrett, Christopher L. Conway, Morgan Deters, Liana Hadarean, Dejan Jovanović, Tim King, Andrew Reynolds, and Cesare Tinelli. 2011. CVC4. In Proceedings of the 23rd International Conference on Computer Aided Verification (CAV’11). 171--177.
[9]
Clark W. Barrett, Pascal Fontaine, and Cesare Tinelli. 2017. The SMT-LIB Standard: Version 2.6. Technical Report. The University of Lowa. Retrieved from http://smtlib.cs.uiowa.edu/language.shtml.
[10]
Clark W. Barrett and Cesare Tinelli. 2018. Satisfiability modulo theories. In Handbook of Model Checking. Springer, 305--343.
[11]
Daniel Le Berre and Anne Parrain. 2010. The SAT4J library, release 2.2. J. Satis. Boolean Model. Computat. 7, 2--3 (2010), 59--6.
[12]
Chandrasekhar Boyapati, Sarfraz Khurshid, and Darko Marinov. 2002. Korat: Automated testing based on Java predicates. In Proceedings of the 11th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’02). 123--133.
[13]
Pietro Braione, Giovanni Denaro, Andrea Mattavelli, and Mauro Pezzè. 2017. Combining symbolic execution and search-based testing for programs with complex heap inputs. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’17). 90--101.
[14]
Pietro Braione, Giovanni Denaro, Andrea Mattavelli, and Mauro Pezzè. 2018. SUSHI: A test generator for programs with complex structured inputs. In Proceedings of the 40th IEEE/ACM International Conference on Software Engineering: Companion Proceeedings (ICSE’18). 21--24.
[15]
Lilian Burdy, Yoonsik Cheon, David R. Cok, Michael D. Ernst, Joseph R. Kiniry, Gary T. Leavens, K. Rustan M. Leino, and Erik Poll. 2005. An overview of JML tools and applications. Int. J. Softw. Tools Technol. Trans. 7, 3 (2005), 212--232.
[16]
Jordi Cabot, Robert Clarisó, and Daniel Riera. 2007. UMLtoCSP: A tool for the formal verification of UML/OCL models using constraint programming. In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE’07). 547--548.
[17]
Jordi Cabot, Robert Clarisó, and Daniel Riera. 2009. Verifying UML/OCL operation contracts. In Proceedings of the 7th International Conference on Integrated Formal Methods (IFM’09). 40--55.
[18]
Jérôme Cantenot, Fabrice Ambert, and Fabrice Bouquet. 2014. Test generation with satisfiability modulo theories solvers in model-based testing. Softw. Test. Verif. Reliab. 24, 7 (2014), 499--531.
[19]
Felix Chang, Emina Torlak, Julie Pelaez, and Daniel Jackson. 2018. Alloy Analyzer (Version 5). Retrieved from http://alloytools.org/.
[20]
Robert Clarisó, Carlos A. González, and Jordi Cabot. 2009. UMLtoCSP. Retrieved from http://gres.uoc.edu/UMLtoCSP/.
[21]
Robert Clarisó, Carlos A. González, and Jordi Cabot. 2019. Smart bound selection for the verification of UML/OCL class diagrams. ACM Trans. Softw. Eng. 45, 4 (2019), 412--426.
[22]
Coninfer Ltd. 2006. The ECLiPSe Constraint Programming System (Version 5.0). Retrieved from http://eclipseclp.org/.
[23]
Carolina Dania and Manuel Clavel. 2016. OCL2MSFOL: A mapping to many-sorted first-order logic for efficiently checking the satisfiability of OCL constraints. In Proceedings of the 19th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems (MoDELS’16). 65--75.
[24]
Leonardo Mendonça de Moura and Nikolaj Bjørner. 2008. Z3: An efficient SMT solver. In Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’08). Springer, 337--340.
[25]
Leonardo Mendonça de Moura and Nikolaj Bjørner. 2011. Satisfiability modulo theories: Introduction and applications. Commun. ACM 54, 9 (2011), 69--77.
[26]
Leonardo Mendonça de Moura and Nikolaj Bjørner (Microsoft Research). 2012. Z3 Solver. Retrieved from https://github.com/Z3Prover/z3.
[27]
Rina Dechter and David Cohen. 2003. Constraint Processing. Morgan Kaufmann.
[28]
Daniel Di Nardo, Fabrizio Pastore, and Lionel C. Briand. 2017. Augmenting field data for testing systems subject to incremental requirements changes. ACM Trans. Softw. Eng. Methodol. 26, 1 (2017), 1--40.
[29]
Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276, 1--2 (2002), 51--81.
[30]
Eclipse Foundation. 2006. Acceleo—Transforming Models into Code. Retrieved from http://www.eclipse.org/acceleo/.
[31]
Eclipse Foundation. 2007. ATL—A model transformation technology. Retrieved from https://www.eclipse.org/atl/.
[32]
Eclipse Foundation. 2009. Xpand. Retrieved from https://www.eclipse.org/modeling/m2t/?project=xpand.
[33]
Eclipse Foundation. 2018. Eclipse OCL (Version 6.4.0). Retrieved from http://www.eclipse.org/ocl.
[34]
Niklas Eén and Niklas Sörensson. 2003. An extensible SAT-solver. In Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT’03). 502--518.
[35]
Carlos A. González and Jordi Cabot. 2014. Formal verification of static software models in MDE: A systematic review. Inf. Softw. Technol. 56, 8 (2014), 821--838.
[36]
Mark Harman, S. Afshin Mansouri, and Yuanyuan Zhang. 2012. Search-based software engineering: Trends, techniques, and applications. Comput. Surv. 45, 1 (2012), 11:1--11:61.
[37]
Mark Harman and Phil McMinn. 2010. A theoretical and empirical study of search-based testing: Local, global, and hybrid search. IEEE Trans. Softw. Eng. 36, 2 (2010), 226--247.
[38]
John Henry Holland et al. 1992. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. The MIT Press.
[39]
Patrick Hurley. 2014. A Concise Introduction to Logic. Nelson Education.
[40]
Kobi Inkumsah and Tao Xie. 2008. Improving structural testing of object-oriented programs via integrating evolutionary testing and symbolic execution. In Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE’08). 297--306.
[41]
Muhammad Zohaib Z. Iqbal, Andrea Arcuri, and Lionel C. Briand. 2012. Combining search-based and adaptive random testing strategies for environment model-based testing of real-time embedded systems. In Proceedings of the 4th International Symposium on Search-based Software Engineering (SSBSE’02). 136--151.
[42]
Muhammad Zohaib Z. Iqbal, Andrea Arcuri, and Lionel C. Briand. 2015. Environment modeling and simulation for automated testing of soft real-time embedded software. Softw. Syst. Model. 14, 1 (2015), 483--524.
[43]
Stefan J. Galler and Bernhard K. Aichernig. 2014. Survey on test data generation tools. Int. J. Softw. Tools Technol. Trans. 16 (2014), 727--751.
[44]
Daniel Jackson. 2012. Software Abstractions: Logic, Language, and Analysis. The MIT Press.
[45]
Guy Katz, Clark W. Barrett, Cesare Tinelli, Andrew Reynolds, and Liana Hadarean. 2016. Lazy proofs for DPLL(T)-based SMT solvers. In Proceedings of the International Conference on Formal Methods in Computer-aided Design (FMCAD’16). 93--100.
[46]
Joseph Kempka, Phil McMinn, and Dirk Sudholt. 2015. Design and analysis of different alternating variable searches for search-based software testing. Theoret. Comput. Sci. 605 (2015), 1--20.
[47]
Marouane Kessentini, Houari A. Sahraoui, and Mounir Boukadoum. 2011. Example-based model-transformation testing. Autom. Softw. Eng. 18, 2 (2011), 199--224.
[48]
Bogdan Korel. 1990. Automated software test data generation. IEEE Trans. Softw. Eng. 16, 8 (1990), 870--879.
[49]
Mirco Kuhlmann and Martin Gogolla. 2012. Strengthening SAT-based validation of UML/OCL models by representing collections as relations. In Proceedings of the 8th European Conference on Modelling Foundations and Applications (ECMFA’12). 32--48.
[50]
Bao-Lin Li, Zhi-Shu Li, Li Qing, and Yan-Hong Chen. 2007. Test case automate generation from UML sequence diagram and OCL expression. In Proceedings of the International Conference on Computational Intelligence and Security (CIS’07). 1048--1052.
[51]
Leonid Libkin. 2004. Elements of Finite Model Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer Verlag.
[52]
Phil McMinn. 2004. Search-based software test data generation: A survey. Softw. Test. Verif. Reliab. 14, 2 (2004), 105--156.
[53]
Phil McMinn and Gregory M. Kapfhammer. 2016. AVMf: An open-source framework and implementation of the alternating variable method. In Proceedings of the 8th International Symposium on Search-based Software Engineering (SSBSE’16). 259--266.
[54]
Glenford J. Myers, Corey Sandler, and Tom Badgett. 2011. The Art of Software Testing (3rd ed.). Wiley Publishing.
[55]
Object Management Group. 2004. Object Constraint Language 2.4 Specification. Retrieved from http://www.omg.org/spec/OCL/2.4/.
[56]
Object Management Group. 2015. OMG Unified Modeling Language (UML). Retrieved from http://www.omg.org/spec/UML/2.5.
[57]
Xavier Oriol and Ernest Teniente. 2017. OCL: Expressive UML/OCL conceptual schemas for finite reasoning. In Proceedings of the 36th International Conference on Conceptual Modeling (ER’17). 354--369.
[58]
Xavier Oriol and Ernest Teniente. 2017. Simplification of UML/OCL schemas for efficient reasoning. J. Syst. Softw. 128 (2017), 130--149.
[59]
Annibale Panichella, Fitsum Meshesha Kifetew, and Paolo Tonella. 2018. Automated test case generation as a many-objective optimisation problem with dynamic selection of the targets. IEEE Trans. Softw. Eng. 44, 2 (2018), 122--158.
[60]
Roy P. Pargas, Mary Jean Harrold, and Robert R. Peck. 1999. Test-data generation using genetic algorithms. Softw. Test. Verif. Reliab. 9, 4 (1999), 263--282.
[61]
Nils Przigoda, Mathias Soeken, Robert Wille, and Rolf Drechsler. 2016. Verifying the structure and behavior in UML/OCL models using satisfiability solvers. IET Cyber-Phys. Syst.: Theory Applic. 1, 1 (2016), 49--59.
[62]
Nils Przigoda, Robert Wille, and Rolf Drechsler. 2016. Ground setting properties for an efficient translation of OCL in SMT-based model finding. In Proceedings of the 19th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems (MoDELS’16). 261--271.
[63]
Anna Queralt, Alessandro Artale, Diego Calvanese, and Ernest Teniente. 2012. OCL-Lite: Finite reasoning on UML/OCL conceptual schemas. Data Knowl. Eng. 73 (2012), 1--22.
[64]
Red Hat. 2001. Hibernate. Everything data. Retrieved from http://hibernate.org/.
[65]
Alan Robinson and Andrei Voronkov. 2001. Handbook of Automated Reasoning. Elsevier.
[66]
Nicolás Rosner, Juan P. Galeotti, Carlos López Pombo, and Marcelo F. Frias. 2010. ParAlloy: Towards a framework for efficient parallel analysis of Alloy models. In Proceedings of the International Conference on 2nd Abstract State Machines, Alloy, B and Z (ABZ’10). 396--397.
[67]
Nicolás Rosner, Junaid Haroon Siddiqui, Nazareno Aguirre, Sarfraz Khurshid, and Marcelo F. Frias. 2013. Ranger: Parallel analysis of Alloy models by range partitioning. In Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering (ASE’13). 147--157.
[68]
Per Runeson and Claes Wohlin. 1995. Statistical usage testing for software reliability control. Informatica 19, 2 (1995), 195--207.
[69]
Stuart J. Russell and Peter Norvig. 1995. Artificial Intelligence: A Modern Approach. Prentice-Hall, Inc.
[70]
Hassan Sartaj, Muhammad Zohaib Iqbal, Atif Aftab Ahmed Jilani, and Muhammad Uzair Khan. 2019. A search-based approach to generate MC/DC test data for OCL constraints. In Proceedings of the 11th International Symposium on Search-based Software Engineering (SSBSE’19). 105--120.
[71]
Julia Seiter, Robert Wille, Mathias Soeken, and Rolf Drechsler. 2013. Determining relevant model elements for the verification of UML/OCL specifications. In Proceedings of the Design, Automation and Test in Europe Conference (DATE’13). 1189--1192.
[72]
Oszkár Semeráth, Andraás Szabolcs Nagy, and Dániel Varró. 2018. A graph solver for the automated generation of consistent domain-specific models. In Proceedings of the 40th IEEE/ACM International Conference on Software Engineering (ICSE’18). 969--980.
[73]
Sagar Sen, Benoit Baudry, and Jean-Marie Mottu. 2009. Automatic model generation strategies for model transformation testing. In Proceedings of the 2nd International Conference on Model Transformations (ICMT’09). 148--164.
[74]
Asadullah Shaikh, Robert Clarisó, Uffe Kock Wiil, and Nasrullah Memon. 2010. Verification-driven slicing of UML/OCL models. In Proceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering (ASE’10). 185--194.
[75]
Mathias Soeken, Robert Wille, and Rolf Drechsler. 2011. Encoding OCL data types for SAT-based verification of UML/OCL models. In Proceedings of the 5th International Conference on Tests and Proofs (TAP’11). 152--170.
[76]
Ghanem Soltana, Mehrdad Sabetzadeh, and Lionel C. Briand. 2017. Search-based Synthetic Data Generator. Retrieved from http://people.svv.lu/tools/SDG/.
[77]
Ghanem Soltana, Mehrdad Sabetzadeh, and Lionel C. Briand. 2017. Synthetic data generation for statistical testing. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE’17). 872--882.
[78]
Ting Su, Zhoulai Fu, Geguang Pu, Jifeng He, and Zhendong Su. 2015. Combining symbolic execution and model checking for data flow testing. In Proceedings of the 37th IEEE/ACM International Conference on Software Engineering (ICSE’15). 654--665.
[79]
Emina Torlak. 2012. Scalable test data generation from multidimensional models. In Proceedings of the 20th ACM SIGSOFT Symposium on Foundations of Software Engineering (FSE’12). 36.
[80]
Alexandre Torres, Renata Galante, Marcelo Soares Pimenta, and Alexandre Jonatan B. Martins. 2017. Twenty years of object-relational mapping: A survey on patterns, solutions, and their implications on application design. Inf. Softw. Technol. 82 (2017), 1--18.
[81]
Mark Utting and Bruno Legeard. 2010. Practical Model-based Testing: A Tools Approach. Elsevier.
[82]
Chunhui Wang, Fabrizio Pastore, Arda Goknil, Lionel C. Briand, and Muhammad Zohaib Z. Iqbal. 2015. Automatic generation of system test cases from use case specifications. In Proceedings of the 24th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’15). 385--396.
[83]
Jianghao Wang, Hamid Bagheri, and Myra B. Cohen. 2018. An evolutionary approach for analyzing Alloy specifications. In Proceedings of the 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE’18). 820--825.
[84]
Jos B. Warmer and Anneke G. Kleppe. 2003. The Object Constraint Language: Getting Your Models Ready for MDA. Addison-Wesley Professional.
[85]
W. Eric Wong. 2001. Mutation Testing for the New Century. Kluwer Academic Publishers, Norwell, MA.
[86]
Pingyu Zhang, Sebastian G. Elbaum, and Matthew B. Dwyer. 2011. Automatic generation of load tests. In Proceedings of the 26th IEEE/ACM International Conference on Automated Software Engineering (ASE’11). 43--52.

Cited By

View all
  • (2024)Requirement-Driven Generation of Distributed Ledger ArchitecturesProceedings of the ACM/IEEE 27th International Conference on Model Driven Engineering Languages and Systems10.1145/3640310.3674097(268-279)Online publication date: 22-Sep-2024
  • (2024)Concretization of Abstract Traffic Scene Specifications Using Metaheuristic SearchIEEE Transactions on Software Engineering10.1109/TSE.2023.333125450:1(48-68)Online publication date: Jan-2024
  • (2024)Exploring Dependencies Among Inconsistencies to Enhance the Consistency Maintenance of Models2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00023(147-158)Online publication date: 12-Mar-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology
ACM Transactions on Software Engineering and Methodology  Volume 29, Issue 2
April 2020
200 pages
ISSN:1049-331X
EISSN:1557-7392
DOI:10.1145/3386453
  • Editor:
  • Mauro Pezzè
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 April 2020
Accepted: 01 January 2020
Revised: 01 January 2020
Received: 01 January 2019
Published in TOSEM Volume 29, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. OCL
  2. SMT
  3. System testing
  4. UML
  5. metaheuristic search
  6. model-driven engineering
  7. test data generation

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • European Union's Horizon 2020 Research and Innovation Program

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)68
  • Downloads (Last 6 weeks)8
Reflects downloads up to 09 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Requirement-Driven Generation of Distributed Ledger ArchitecturesProceedings of the ACM/IEEE 27th International Conference on Model Driven Engineering Languages and Systems10.1145/3640310.3674097(268-279)Online publication date: 22-Sep-2024
  • (2024)Concretization of Abstract Traffic Scene Specifications Using Metaheuristic SearchIEEE Transactions on Software Engineering10.1109/TSE.2023.333125450:1(48-68)Online publication date: Jan-2024
  • (2024)Exploring Dependencies Among Inconsistencies to Enhance the Consistency Maintenance of Models2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00023(147-158)Online publication date: 12-Mar-2024
  • (2024)Generalized Formal Model-Verifier: A Formal Approach for Verifying Static ModelsSN Computer Science10.1007/s42979-024-02808-25:5Online publication date: 2-May-2024
  • (2024)Can Language Models Pretend Solvers? Logic Code Simulation with LLMsDependable Software Engineering. Theories, Tools, and Applications10.1007/978-981-96-0602-3_6(102-121)Online publication date: 26-Nov-2024
  • (2024)Generating and Evolving Real-Life Like Synthetic Data for e-Government Services Without Using Real-World Raw DataProduct-Focused Software Process Improvement. Industry-, Workshop-, and Doctoral Symposium Papers10.1007/978-3-031-78392-0_12(173-178)Online publication date: 2-Dec-2024
  • (2024)Evolutionary Analysis of Alloy Specifications with an Adaptive Fitness FunctionSearch-Based Software Engineering10.1007/978-3-031-64573-0_1(1-17)Online publication date: 2-Jul-2024
  • (2024)Search‐Based MC/DC Test Data Generation With OCL ConstraintsSoftware Testing, Verification and Reliability10.1002/stvr.190635:1Online publication date: 8-Nov-2024
  • (2023)Generating Structurally Realistic Models With Deep Autoregressive NetworksIEEE Transactions on Software Engineering10.1109/TSE.2022.322863049:4(2661-2676)Online publication date: 1-Apr-2023
  • (2023)OCL Rebuilt, From the Ground Up2023 ACM/IEEE 26th International Conference on Model Driven Engineering Languages and Systems (MODELS)10.1109/MODELS58315.2023.00010(194-205)Online publication date: 1-Oct-2023
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media