AUTHORS: Sebastien Salva, William Durand

Download as PDF

ABSTRACT: In the industry, testing production systems, i.e., systems transforming raw materials into products, is usually performed manually and is a long and error-prone task. The automation of the testing process could be initiated with the use of models. But, for this kind of system that has a long life span, models, when they exist, are seldom up-to-date. In this paper, we do not presume the availability of any model and we propose a method to automatically test the CIM2 level of production systems i.e., the software controlling them, by combining two approaches: model inference and passive testing. Using a set of events collected from a production system, our approach combines the notions of expert system, formal models and machine learning to infer symbolic models while preventing over-generalisation (i.e., the models should not capture more behaviours than those possible in the real system). These models are then used as specifications to passively test the conformance of other production systems. We define conformance with two complementary implementation relations. The first relation is based upon the classical trace-preorder relation. The second one is a weaker relation, less strict on the parameter values found in the traces of the system under test. With the collaboration of the manufacturer Michelin, we evaluated our approach on a real production system and show that it can be used in practice to quickly generate models and to test new production systems.

KEYWORDS: Software engineering, Maintenance, Model generation , Passive testing , Industrial systems

REFERENCES:

[1] G. Ammons, R. Bod´ık, and J. R. Larus. Mining specifications. SIGPLAN Not., 37(1):4–16, Jan. 2002.

[2] C. Andres, M. G. Merayo, and M. Nu ` nez. For- ˜ mal passive testing of timed systems: Theory and tools. Softw. Test. Verif. Reliab., 22(6):365– 405, Sept. 2012.

[3] D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87 – 106, 1987.

[4] J. Antunes, N. Neves, and P. Verissimo. Reverse engineering of protocols from network traces. In Reverse Engineering (WCRE), 2011 18th Working Conference on, pages 169–178, Oct 2011.

[5] J. A. Arnedo, A. Cavalli, and M. Nu´nez. ˜ Fast Testing of Critical Properties through Passive Testing, pages 295–310. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.

[6] E. Bayse, A. Cavalli, M. Nunez, and F. Zaidi. A passive testing approach based on invariants: application to the {WAP}. Computer Networks, 48(2):247 – 266, 2005.

[7] A. Biermann and J. Feldman. On the synthesis of finite-state machines from samples of their behavior. Computers, IEEE Transactions on, C- 21(6):592–597, June 1972.

[8] E. Brinksma and J. Tretmans. Modeling and verification of parallel processes. chapter Testing Transition Systems: An Annotated Bibliography, pages 187–195. Springer-Verlag New York, Inc., New York, NY, USA, 2001.

[9] S. R. Buss. An introduction to proof theory.

[10] A. Cavalli, C. Gervy, and S. Prokopenko. New approaches for passive testing using an extended finite state machine specification. Information and Software Technology, 45(12):837 – 852, 2003. Testing and Validation of Communication Software.

[11] A. Cavalli, S. Maag, and E. M. de Oca. A passive conformance testing approach for a manet routing protocol. In Proceedings of the 2009 ACM symposium on Applied Computing, SAC ’09, pages 207–211, New York, NY, USA, 2009. ACM.

[12] N. Chen and C. Viho. Passive Interoperability Testing for Request-Response Protocols: Method, Tool and Application on CoAP Protocol, pages 87–102. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.

[13] K. T. Cheng and A. S. Krishnakumar. Automatic functional test generation using the extended fi- nite state machine model. In Proceedings of the 30th International Design Automation Conference, DAC ’93, pages 86–91, New York, NY, USA, 1993. ACM.

[14] R. de Nicola and M. C. B. Hennessy. Automata, Languages and Programming: 10th Colloquium Barcelona, Spain, July 18–22, 1983, chapter Testing equivalences for processes, pages 548– 560. Springer Berlin Heidelberg, Berlin, Heidelberg, 1983.

[15] P. Dupont. Incremental regular inference. In Proceedings of the Third ICGI-96, pages 222– 237. Springer, 1996.

[16] W. Durand and S. Salva. Passive testing of production systems based on model inference. In 13. ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2015, Austin, TX, USA, September 21- 23, 2015, pages 138–147. IEEE, 2015.

[17] M. D. Ernst, J. Cockrell, W. G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. In Proceedings of the 21st International Conference on Software Engineering, ICSE ’99, pages 213–224, New York, NY, USA, 1999. ACM.

[18] Y. Falcone, J.-C. Fernandez, and L. Mounier. Runtime Verification of Safety-Progress Properties, pages 40–59. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

[19] L. Frantzen, J. Tretmans, and T. Willemse. Test Generation Based on Symbolic Specifications. In J. Grabowski and B. Nielsen, editors, FATES 2004, number 3395 in Lecture Notes in Computer Science, pages 1–15. Springer, 2005.

[20] E. M. Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302 – 320, 1978.

[21] V. J. Hodge and J. Austin. A Survey of Outlier Detection Methodologies. Artificial Intelligence Review, 22:85–126, 2004.

[22] I. Krka, Y. Brun, D. Popescu, J. Garcia, and N. Medvidovic. Using dynamic execution traces and program invariants to enhance behavioral model inference. In Proceedings of the 32Nd ACM/IEEE International Conference on Software Engineering - Volume 2, ICSE ’10, pages 179–182, New York, NY, USA, 2010. ACM.

[23] J. Lang, P. Liberatore, and P. Marquis. Propositional independence - formula-variable independence and forgetting. Journal of Artificial Intelligence Research, 18:391–443, 2003.

[24] D. Lee, D. Chen, R. Hao, R. E. Miller, J. Wu, and X. Yin. Network protocol system monitoring: a formal approach with passive testing. IEEE/ACM Trans. Netw., 14:424–437, April 2006.

[25] D. Lee and M. Yannakakis. Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE, 84(8):1090–1123, Aug 1996.

[26] M. Leucker and C. Schallhart. A brief account of runtime verification. The Journal of Logic and Algebraic Programming, 78(5):293 – 303, 2009. The 1st Workshop on Formal Languages and Analysis of Contract-Oriented Software (FLACOS07).

[27] D. Lo, L. Mariani, and M. Santoro. Learning extended fsa from software: An empirical assessment. Journal of Systems and Software, 85(9):2063 – 2076, 2012. Selected papers from the 2011 Joint Working IEEE/IFIP Conference on Software Architecture (WICSA 2011).

[28] D. Lorenzoli, L. Mariani, and M. Pezze. Auto- ` matic generation of software behavioral models. In Proceedings of the 30th International Conference on Software Engineering, ICSE ’08, pages 501–510, New York, NY, USA, 2008. ACM.

[29] L. Mariani and M. Pezze. Dynamic detection of cots component incompatibility. IEEE Software, 24(5):76–85, 2007.

[30] P. Mouttappa, S. Maag, and A. Cavalli. Using passive testing based on symbolic execution and slicing techniques. Comput. Netw., 57(15):2992–3008, Oct. 2013.

[31] M. Pradel and T. R. Gross. Automatic generation of object usage specifications from large method traces. In Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering, ASE ’09, pages 371–382, Washington, DC, USA, 2009. IEEE Computer Society.

[32] M. Salah, T. Denton, S. Mancoridis, and A. Shokouf. Scenariographer: A tool for reverse engineering class usage scenarios from method invocation sequences. In In ICSM, pages 155– 164. IEEE Computer Society, 2005.

[33] S. Salva and W. Durand. Autofunk, a fast and scalable framework for building formal models from production systems. In Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems, DEBS ’15, Oslo, Norway, June 29 - July 3, 2015, pages 193–204, 2015.

[34] S. Salva and W. Durand. Combining model generation and passive testing in the same framework to test industrial systems. Technical report, LIMOS, http://sebastien.salva.free.fr/RR- 17-03.pdf, 2017. LIMOS Research report RR- 17-03.

[35] P. Tonella, C. D. Nguyen, A. Marchetto, K. Lakhotia, and M. Harman. Automated generation of state abstraction functions using data invariant inference. In 8th International Workshop on Automation of Software Test, AST 2013, San Francisco, CA, USA, May 18-19, 2013, pages 75–81, 2013.

[36] G. Tretmans. Test generation with inputs, outputs and repetitive quiescence. Software— Concepts and Tools, 3(TR-CTI), 1996.

[37] H. Ural and Z. Xu. An efsm-based passive fault detection approach. In Proceedings of the 19th IFIP TC6/WG6.1 International Conference, and 7th International Conference on Testing of Software and Communicating Systems, TestCom’07/FATES’07, pages 335–350, Berlin, Heidelberg, 2007. Springer-Verlag.

[38] N. Walkinshaw, K. Bogdanov, M. Holcombe, and S. Salahuddin. Reverse engineering state machines by interactive grammar inference. In In Proceedings of the 14th Working Conference on Reverse Engineering (WCRE’07. IEEE, 2007.

[39] C. Wernhard. Literal Projection for First-Order Logic, pages 389–402. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.

[40] C. Wu, F. YuShun, and X. Deyun. Computer Integrated Manufacturing, pages 484–529. John Wiley & Sons, Inc., 2007.

[41] X. Wu, V. Kumar, J. Ross Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, P. S. Yu, Z.-H. Zhou, M. Steinbach, D. J. Hand, and D. Steinberg. Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1):1–37, 2008.

[42] J. Yang, D. Evans, D. Bhardwaj, T. Bhat, and M. Das. Perracotta: Mining temporal api rules from imperfect traces. In Proceedings of the 28th International Conference on Software Engineering, ICSE ’06, pages 282–291, New York, NY, USA, 2006. ACM.

[43] H. Zhong, L. Zhang, T. Xie, and H. Mei. Inferring specifications for resources from natural language api documentation. Autom. Softw. Eng., 18(3-4):227–261, 2011.

WSEAS Transactions on Business and Economics, ISSN / E-ISSN: 1109-9526 / 2224-2899, Volume 14, 2017, Art. #35, pp. 330-353


Copyright © 2017 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0