Shaukat Ali
Muhammad Zohaib Iqbal
ABSTRACT
The Object Constraint Language (OCL) is a standard language for specifying constraints on Unified Modeling Language (UML) models. The specified constraints can be used for various purposes including verification, and model-based testing (e.g., test data generation). Efficiently solving OCL constraints is one of the key requirements for the practical use of OCL. In this paper, we propose an improvement in existing heuristics to solve OCL constraints using search algorithms. We evaluate our improved heuristics using two empirical studies with three search algorithms: Alternating Variable Method (AVM), (1+1) Evolutionary Algorithm (EA), and a Genetic Algorithm (GA). We also used Random Search (RS) as a comparison baseline. The first empirical study was conducted using carefully designed artificial problems (constraints) to assess each individual heuristics. The second empirical study is based on an industrial case study provided by Cisco about model-based testing of Video Conferencing Systems. The results of both empirical evaluations reveal that the effectiveness of the search algorithms, measured in terms of time to solve the OCL constraints to generate data, is significantly improved when using the novel heuristics presented in this paper. In particular, our experiments show that (1+1) EA with the novel heuristics has the highest success rate among all the analyzed algorithms, as it requires the least number of iterations to solve constraints.
- OCL. (2011). Object Constraint Language Specification, Version 2.2. Available: http://www.omg.org/spec/OCL/2.2/Google Scholar
- R. V. Binder, Testing object-oriented systems: models, patterns, and tools: Addison-Wesley Longman Publishing Co., Inc., 1999. Google ScholarDigital Library
- S. Ali, M. Z. Iqbal, A. Arcuri, and L. Briand, "A Search-based OCL Constraint Solver for Model-based Test Data Generation," in Proceedings of the 11th International Conference On Quality Software (QSIC 2011), 2011, pp. 41--50. Google ScholarDigital Library
- S. Ali, M. Z. Iqbal, A. Arcuri, and L. Briand, "Generating Test Data from OCL Constraints with Search Techniques," IEEE Trans. Softw. Eng., vol. 39, pp. 1376--1402, 2013. Google ScholarDigital Library
- P. McMinn, "Search-based software test data generation: a survey: Research Articles," Softw. Test. Verif. Reliab., vol. 14, pp. 105--156, 2004. Google ScholarDigital Library
- S. Ali, M. Z. Iqbal, A. Arcuri, and L. Briand, "Generating Test Data from OCL Constraints with Search Techniques," Simula Reserach Laboratory, Technical Report (2010--16)2012.Google Scholar
- S. Ali, M. Z. Iqbal, and A. Arcuri, "Empirically Evaluating Improved Heuristics for Test Data Generation from OCL Constraints using Search Algorithms," Simula Research Laboratory2012.Google Scholar
- S. Ali, L. C. Briand, H. Hemmati, and R. K. Panesar-Walawege, "A Systematic Review of the Application and Empirical Investigation of Search-Based Test Case Generation," IEEE Transactions on Software Engineering, vol. 99, 2009. Google ScholarDigital Library
- A. Arcuri, "It really does matter how you normalize the branch distance in search-based software testing," Software Testing, Verification and Reliability, 2011.Google Scholar
- M. Z. Iqbal, A. Arcuri, and L. Briand, "Empirical Investigation of Search Algorithms for Environment Model-Based Testing of Real-Time Embedded Software " in International Symposium on Software Testing and Analysis (ISSTA), 2012. Google ScholarDigital Library
- A. Arcuri and G. Fraser, "On Parameter Tuning in Search Based Software Engineering," presented at the International Symposium on Search Based Software Engineering (SSBSE), 2011. Google ScholarDigital Library
- A. Arcuri and L. Briand., "A Practical Guide for Using Statistical Tests to Assess Randomized Algorithms in Software Engineering," presented at the International Conference on Software Engineering (ICSE), 2011. Google ScholarDigital Library
- D. J. Sheskin, Handbook of Parametric and Nonparametric Statistical Procedures: Chapman and Hall/CRC, 2007. Google ScholarDigital Library
- B. Bordbar and K. Anastasakis, "UML2Alloy: A tool for lightweight modelling of Discrete Event Systems," presented at the IADIS International Conference in Applied Computing, 2005.Google Scholar
- D. Distefano, J.-P. Katoen, and A. Rensink, "Towards model checking OCL," presented at the ECOOP-Workshop on Defining Precise Semantics for UML, 2000.Google Scholar
- M. Clavel and M. A. G. d. Dios, "Checking unsatisfiability for OCL constraints," presented at the In the proceedings of the 9th OCL 2009 Workshop at the UML/MoDELS Conferences, 2009.Google Scholar
- J. Winkelmann, G. Taentzer, K. Ehrig, and J. M. ster, "Translation of Restricted OCL Constraints into Graph Constraints for Generating Meta Model Instances by Graph Grammars," Electron. Notes Theor. Comput. Sci., vol. 211, pp. 159--170, 2008. Google ScholarDigital Library
- D. Jackson, I. Schechter, and H. Shlyahter, "Alcoa: the alloy constraint analyzer," presented at the Proceedings of the 22nd international conference on Software engineering, Limerick, Ireland, 2000. Google ScholarDigital Library
- M. Krieger and A. Knapp, "Executing Underspecified OCL Operation Contracts with a SAT Solver," presented at the 8th International Workshop on OCL Concepts and Tools., 2008.Google Scholar
- L. v. Aertryck and T. Jensen, "UML-Casting: Test synthesis from UML models using constraint resolution," presented at the Approches Formelles dans l'Assistance au Développement de Logiciels (AFADL'2003), 2003.Google Scholar
- J. Cabot, R. Claris, and D. Riera, "Verification of UML/OCL Class Diagrams using Constraint Programming," presented at the Proceedings of the 2008 IEEE International Conference on Software Testing Verification and Validation Workshop, 2008. Google ScholarDigital Library
- A. D. Brucker, M. P. Krieger, D. Longuet, and B. Wolff, "A Specification-Based Test Case Generation Method for UML/OCL," presented at the Worksshop on OCL and Textual Modelling, MoDELS, 2010. Google ScholarDigital Library
- L. Bao-Lin, L. Zhi-shu, L. Qing, and C. Y. Hong, "Test case automate generation from uml sequence diagram and ocl expression," presented at the International Conference on computational Intelligence and Security, 2007. Google ScholarDigital Library
Index Terms
- Improved heuristics for solving OCL constraints using search algorithms
Recommendations
Improving the performance of OCL constraint solving with novel heuristics for logical operations: a search-based approach
A common practice to specify constraints on the Unified Modeling Language (UML) models is using the Object Constraint Language (OCL). Such constraints serve various purposes, ranging from simply providing precise meaning to the models to supporting ...
A Search-Based OCL Constraint Solver for Model-Based Test Data Generation
QSIC '11: Proceedings of the 2011 11th International Conference on Quality SoftwareModel-based testing (MBT) aims at automated, scalable, and systematic testing solutions for complex industrial software systems. To increase chances of adoption in industrial contexts, software systems should be modeled using well-established standards ...
Generating Test Data from OCL Constraints with Search Techniques
Model-based testing (MBT) aims at automated, scalable, and systematic testing solutions for complex industrial software systems. To increase chances of adoption in industrial contexts, software systems can be modeled using well-established standards ...
Comments