Smoke Test Planning using Answer Set Programming.

Tobias Philipp; Valentin Roland; Lukas Schweizer

doi:10.9781/ijimai.2021.02.003

Authors

Tobias Philipp Division Defence & Space.
Valentin Roland Division Defence & Space.
Lukas Schweizer Technische Universität Dresden

DOI:

https://doi.org/10.9781/ijimai.2021.02.003

Keywords:

Planning, Answer Set Programming, Testing

Supporting Agencies

We are grateful for the valuable feedback and additional references from the anonymous reviewers, which helped greatly to improve this work.

Abstract

Smoke testing is an important method to increase stability and reliability of hardware- gramming, Testing depending systems. Due to concurrent access to the same physical resource and the impracticality of the use of virtualization, smoke testing requires some form of planning. In this paper, we propose to decompose test cases in terms of atomic actions consisting of preconditions and effects. We present a solution based on answer set programming with multi-shot solving that automatically generates short parallel test plans. Experiments suggest that the approach is feasible for non-inherently sequential test cases and scales up to thousands of test cases.

Downloads

Download data is not yet available.

References

[1] G. D. Everett, R. McLeod Jr, Software testing: testing across the entire software development life cycle. Piscataway, NJ, Hoboken, N.J: John Wiley & Sons, 2007.

[2] H. Palacios, H. Geffner, “Compiling uncertainty away in conformant planning problems with bounded width,” Journal of Artificial Intelligence Research, vol. 35, pp. 623–675, 2009, doi: 10.1613/jair.2708.

[3] D. E. Smith, “Choosing Objectives in Over-Subscription Planning,” in Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), June 3-7 2004, Whistler, British Columbia, Canada, 2004, pp. 393–401, AAAI.

[4] G. Brewka, T. Eiter, M. Truszczynski, “Answer set program-ming at a glance,” Communications of the ACM, vol. 54, no. 12, pp. 92–103, 2011, doi: 10.1145/2043174.2043195.

[5] I. Niemelä, “Logic programs with stable model semantics as a constraint programming paradigm,” Annals of Mathematics and Artificial Intelligence, vol. 25, no. 3-4, pp. 241–273, 1999, doi: 10.1023/A:1018930122475.

[6] M. Gelfond, V. Lifschitz, “Classical negation in logic programs and disjunctive databases,” New Generation Computing, vol. 9, no. 3/4, pp. 365–386, 1991, doi: 10.1007/BF03037169.

[7] T. Janhunen, I. Niemelä, “The answer set programming paradigm,” AI Magazine, vol. 37, no. 3, pp. 13–24, 2016.

[8] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, “Answer Set Solving in Practice,” Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 6, pp. 1–238, 2012, doi: 10.2200/S00457ED1V01Y201211AIM019.

[9] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, “Clingo = ASP + control: Preliminary report,” CoRR, vol. abs/1405.3694, 2014.

[10] J. Rintanen, K. Heljanko, I. Niemelä, “Planning as satisfia-bility: parallel plans and algorithms for plan search,” Artificial Intelligence, vol. 170, no. 12-13, pp. 1031–1080, 2006, doi: 10.1016/j.artint.2006.08.002.

[11] A. Cimatti, M. Roveri, P. Bertoli, “Conformant planning via symbolic model checking and heuristic search,” Artificial Intelligence, vol. 159, no. 1-2, pp. 127–206, 2004, doi: 10.1016/j.artint.2004.05.003.

[12] M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, S. Thiele, “Engineering an incremental ASP solver,” in Logic Programming, 24th International Conference, ICLP 2008, Udine, Italy, December 9-13 2008, Proceedings, vol. 5366 of Lecture Notes in Computer Science, 2008, pp. 190–205, Springer.

[13] T. C. Son, C. Baral, T. H. Nam, S. A. McIlraith, “Domain-dependent knowledge in answer set planning,” ACM Transactions on Computational Logic, vol. 7, no. 4, pp. 613–657, 2006, doi: 10.1145/1183278.1183279.

[14] T. Eiter, E. Erdem, H. Erdogan, M. Fink, “Finding similar/-diverse solutions in answer set programming,” Theory and Practice of Logic Programming, vol. 13, no. 3, pp. 303–359, 2013, doi: 10.1017/S1471068411000548.

[15] F. Wotawa, J. Bozic, “Plan it! automated security testing based on planning,” in Proceedings of Testing Software and Systems - International Conference, ICTSS 2014, Madrid, Spain, September 23-25, 2014., vol. 8763 of Lecture Notes in Computer Science, 2014, pp. 48–62, Springer.

[16] A. E. Howe, A. von Mayrhauser, R. T. Mraz, “Test case generation as an AI planning problem,” Automated Software Engineering, vol. 4, no. 1, pp. 77–106, 1997, doi: 10.1023/A:1008607721339.

[17] D. Shmaryahu, G. Shani, J. Hoffmann, M. Steinmetz, “Simulated penetration testing as contingent planning,” in Proceedings of the TwentyEighth International Conference on Automated Planning and Scheduling, ICAPS 2018, Delft, The Netherlands, June 24-29, 2018, 2018, pp. 241–249, AAAI Press.

[18] J. Bozic, O. A. Tazl, F. Wotawa, “Chatbot testing using AI planning,” in Proceedings of International Conference On Artificial Intelligence Testing IEEE, AITest 2019, Newark, CA, USA, April 4-9, 2019, 2019, pp. 37–44, IEEE.

[19] R. T. Mraz, A. E. Howe, A. von Mayrhauser, L. Li, “System testing with an AI planner,” in Proceedings of Sixth International Symposium on Software Reliability Engineering, ISSRE 1995, Toulouse, France, October 24-27, 1995, 1995, pp. 96–105, IEEE Computer Society.

[20] A. M. Memon, M. E. Pollack, M. L. Soffa, “Hierarchical GUI test case generation using automated planning,” IEEE Trans-actions of Software Engineering, vol. 27, no. 2, pp. 144–155, 2001, doi: 10.1109/32.908959.

[21] M. Diepenbeck, U. Kühne, M. Soeken, R. Drechsler, “Be-haviour driven development for tests and verification,” in Proceedings of Tests and Proofs - 8th International Conference, TAP@STAF 2014, York, UK, July 24-25, 2014, vol. 8570 of Lecture Notes in Computer Science, 2014, pp. 61–77, Springer.

[22] SmartBear Software, “Cucumber,” 2019. [Online]. Available: https://cucumber.io/, Accessed: 2020-01-11.

[23] H. A. Kautz, B. Selman, “Planning as satisfiability,” in 10th European Conference on Artificial Intelligence, ECAI 92, Vienna, Austria, August 3-7, 1992. Proceedings, 1992, pp. 359–363, John Wiley and Sons.

[24] M. Gebser, R. Kaufmann, T. Schaub, “Gearing up for effective ASP planning,” in Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, vol. 7265 of Lecture Notes in Computer Science, 2012, pp. 296–310, Springer.

[25] S. Zhang, M. Sridharan, F. S. Bao, “ASP+POMDP: integrating nonmonotonic logic programming and probabilistic planning on robots,” in Proceedings of IEEE International Conference on Development and Learning and Epigenetic Robotics, ICDL-EPIROB 2012, San Diego, CA, USA, November 7-9, 2012, 2012, pp. 1–7, IEEE.

[26] J. J. Portillo, C. L. García-Mata, P. R. Márquez-Gutiérrez, R. B a r a y - Arana, “Robot platform motion planning using answer set programming,” in Proceedings of the Seventh Latin American Workshop on Non-Monotonic Reasoning, LANMR 2011, Toluca, Estado de México, México, November 7-8, 2011, vol. 804 of CEUR Workshop Proceedings, 2011, pp. 35–44, CEUR-WS. org.

[27] Y. Jiang, S. Zhang, P. Khandelwal, P. Stone, “Task planning in robotics: an empirical comparison of PDDL- and asp-based systems,” Frontiers of Information Technology & Electronic Engineering, vol. 20, no. 3, pp. 363– 373, 2019, doi: 10.1631/FITEE.1800514.

[28] L. Vila, “A survey on temporal reasoning in artificial intelligence,” AI Communications, vol. 7, no. 1, pp. 4–28, 1994, doi: 10.3233/AIC-1994-7102.