Abstract
For Finite State Machine (FSM) based testing, it has been shown that the use of shorter Adaptive Distinguishing Sequences (ads) yields shorter test sequences. It is also known, on the other hand, that constructing a minimum cost ADS is an NP-hard problem and it is NP-hard to approximate. In this paper, we introduce a lookahead-based greedy algorithm to construct reduced ADSs for FSMs. The greedy algorithm inspects a search space to make a decision. The size of the search space is adjustable, allowing a trade-off between the quality and the computation time. We analyse the performance of the approach on randomly generated FSMs by comparing the ADSs constructed by our algorithm with the ADSs that are computed by the existing algorithms.
Chapter PDF
Similar content being viewed by others
References
Aho, A.V., Dahbura, A.T., Lee, D., Uyar, M.U.: An optimization technique for protocol conformance test generation based on UIO sequences and rural chinese postman tours. In: Protocol Specification, Testing, and Verification VIII, Atlantic City, pp. 75–86. Elsevier, North-Holland (1988)
Alur, R., Cerny, P., Madhusudan, P., Nam, W.: Synthesis of interface specifications for java classes. In: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, pp. 98–109. ACM (2005)
Betin-Can, A., Bultan, T.: Verifiable concurrent programming using concurrency controllers. In: Proceedings of the 19th IEEE International Conference on Automated Software Engineering, pp. 248–257. IEEE Computer Society (2004)
Chow, T.S.: Testing software design modelled by finite state machines. IEEE Transactions on Software Engineering 4, 178–187 (1978)
Pomeranz, I., Reddy, S.M.: Test generation for multiple state-table faults in finite-state machines. IEEE Transactions on Computers 46(7), 783–794 (1997)
Whaley, J., Martin, M.C., Lam, M.S.: Automatic extraction of object-oriented component interfaces. SIGSOFT Softw. Eng. Notes 27, 218–228 (2002)
Sabnani, K., Dahbura, A.: A protocol test generation procedure. Computer Networks 15(4), 285–297 (1988)
Hennie, F.C.: Fault-detecting experiments for sequential circuits. In: Proceedings of Fifth Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, New Jersey, pp. 95–110 (November 1964)
Gonenc, G.: A method for the design of fault detection experiments. IEEE Transactions on Computers 19, 551–558 (1970)
Vasilevskii, M.P.: Failure diagnosis of automata. Cybernetics and Systems Analysis 9, 653–665 (1973), 10.1007/BF01068590
Vuong, S.T., Chan, W.W.L., Ito, M.R.: The UIOv-method for protocol test sequence generation. In: The 2nd International Workshop on Protocol Test Systems, Berlin (1989)
Fujiwara, S., Bochmann, G.V., Khendek, F., Amalou, M., Ghedamsi, A.: Test selection based on finite state models. IEEE Transactions on Software Engineering 17(6), 591–603 (1991)
Ural, H., Zhu, K.: Optimal length test sequence generation using distinguishing sequences. IEEE/ACM Transactions on Networking 1(3), 358–371 (1993)
Petrenko, A., Yevtushenko, N.: Testing from partial deterministic FSM specifications. IEEE Transactions on Computers 54(9), 1154–1165 (2005)
Hierons, R.M., Jourdan, G.V., Ural, H., Yenigun, H.: Checking sequence construction using adaptive and preset distinguishing sequences. In: Proceedings of 7th IEEE International Conference on Software Engineering and Formal Methods (SEFM 2009), pp. 157–166. IEEE Computer Society (2009)
Hierons, R.M., Ural, H.: Optimizing the length of checking sequences. IEEE Transactions on Computers 55, 618–629 (2006)
Hierons, R.M., Ural, H.: Reduced length checking sequences. IEEE Transactions on Computers 51(9), 1111–1117 (2002)
Hierons, R.M.: Minimizing the number of resets when testing from a finite state machine. Information Processing Letters 90(6), 287–292 (2004)
Ural, H., Wu, X., Zhang, F.: On minimizing the lengths of checking sequences. IEEE Transactions on Computers 46(1), 93–99 (1997)
Kohavi, Z.: Switching and Finite State Automata Theory. McGraw-Hill, New York (1978)
Boute, R.T.: Distinguishing sets for optimal state identification in checking experiments. IEEE Trans. Comput. 23, 874–877 (1974)
Jourdan, G.V., Ural, H., Yenigun, H., Zhang, J.: Lower bounds on lengths of checking sequences. Formal Aspects of Computing 22(6), 667–679 (2010)
Lee, D., Yannakakis, M.: Testing finite-state machines: State identification and verification. IEEE Transactions on Computers 43(3), 306–320 (1994)
Sokolovskii, M.N.: Diagnostic experiments with automata. Cybernetics and Systems Analysis 7, 988–994 (1971)
Kushik, N., El-Fakih, K., Yevtushenko, N.: Adaptive homing and distinguishing experiments for nondeterministic finite state machines. In: Yenigün, H., Yilmaz, C., Ulrich, A. (eds.) ICTSS 2013. LNCS, vol. 8254, pp. 33–48. Springer, Heidelberg (2013)
Gill, A.: Introduction to The Theory of Finite State Machines. McGraw-Hill, New York (1962)
Türker, U.C., Yenigun, H.: Hardness and inapproximability of minimizing adaptive distinguishing sequences. Formal Methods in System Design 44(3), 264–294 (2014)
Hennie, F.C.: Finite-state models for logical machines. Wiley (1968)
Gunicen, C., Türker, U.C., Ural, H., Yenigün, H.: Generating preset distinguishing sequences using SAT. In: Gelenbe, E., Lent, R., Sakellari, G. (eds.) Computer and Information Sciences II, pp. 487–493. Springer, London (2012), 10.1007/978-1-4471-2155-8_62.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 IFIP International Federation for Information Processing
About this paper
Cite this paper
Türker, U.C., Ünlüyurt, T., Yenigün, H. (2014). Lookahead-Based Approaches for Minimizing Adaptive Distinguishing Sequences. In: Merayo, M.G., de Oca, E.M. (eds) Testing Software and Systems. ICTSS 2014. Lecture Notes in Computer Science, vol 8763. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44857-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-662-44857-1_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44856-4
Online ISBN: 978-3-662-44857-1
eBook Packages: Computer ScienceComputer Science (R0)