Published in Volume XXXII, Issue 1, 2022, pages 5-86, doi: 10.7561/SACS.2022.1.5

Authors: J. A. Bergstra

Abstract

Using the conceptual analysis of instruction sequence faults, failures, and defects as developed by the author in [10] and [12], a survey of  testing is developed as an extension of a theory of instruction sequences. An attempt is made to develop a consistent terminology regarding instruction sequence testing while taking into account the literature on software testing at large.

Full Text (PDF)

References

[1] Ahmet Ziya Aktas, Eray Yagdereli, and Doga Serdaroglu. An introduction to software testing methodologies. Gazi University Journal of Science Part A: Engineering and Innovation, 8:1-15, 2021. URL: https://dergipark.org.tr/en/pub/gujsa/issue/60638/517975.

[2] Paul Ammann and Jeff Offutt. Introduction to Software Testing. Cambridge University Press, 2008. doi:10.1017/CBO9780511809163.

[3] Algirdas Avizienis, Jean-Claude Laprie, and Brian Randell. Fundamental concepts of computer system dependability. In IARP/IEEE-RAS Workshop on Robot Dependability: Technological Challenge of Dependable Robots in Human Environments, 2001.

[4] Algirdas Avizienis, Jean-Claude Laprie, Brian Randell, and Carl E. Landwehr. Basic concepts and taxonomy of dependable and secure computing. IEEE Transactions on Dependable and Secure Computing, 1(1):11-33, 2004. doi:10.1109/TDSC.2004.2.

[5] Jos C. M. Baeten and Cornelis A. Middelburg. Process Algebra with Timing. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2002. doi:10.1007/978-3-662-04995-2.

[6] Adam Barr. The problem with software, why smart engineers write bad code. MIT Press, 2018.

[7] Boris Beizer. Software System Testing and Quality Assurance. Van Nostrand Reinhold, 2nd edition, 1990.

[8] D. Elliott Bell and Leonard J. LaPadula. Secure computer systems: mathematical foundations. Technical Report 2547, MITRE CORP BEDFORD MA, 1973.

[9] Jan A. Bergstra. Quantitative expressiveness of instruction sequence classes for computation on single bit registers. Computer Science Journal of Moldova, 27(2):131-161, 2019. URL: http://www.math.md/publications/csjm/issues/v27-n2/12969/.

[10] Jan A. Bergstra. Instruction sequence faults with formal change justification. Scientific Annals of Computer Science, 30(2):105-166, 2020. doi:10.7561/SACS.2020.2.105.

[11] Jan A. Bergstra. Promise theory as a tool for informaticians. Transmathematica, 2020. doi:10.36285/tm.35.

[12] Jan A. Bergstra. Qualifications of instruction sequence failures, faults and defects: Dormant, effective, detected, temporary, and permanent. Scientific Annals of Computer Science, 31(1):1-50, 2021.  doi:10.7561/SACS.2021.1.1.

[13] Jan A. Bergstra and Inge Bethke. On the contribution of backward jumps to instruction sequence expressiveness. Theory of Computing Systems, 50(4):706-720, 2012. doi:10.1007/s00224-011-9376-x.

[14] Jan A. Bergstra and Mark Burgess. Promise Theory: Principles and Applications. \chi_t Axis Press, 2014. 2nd edition, 2019.

[15] Jan A. Bergstra and Mark Burgess. Candidate software process flaws for the Boeing 737 Max MCAS algorithm and risks for a proposed upgrade. CoRR, abs/2001.05690, 2020. arXiv:2001.05690.

[16] Jan A. Bergstra and M. E. Loots. Program algebra for sequential code. Journal of Logic and Algebraic Programming, 51(2):125-156, 2002. doi:10.1016/S1567-8326(02)00018-8.

[17] Jan A. Bergstra and Cornelis A. Middelburg. Thread algebra for strategic interleaving. Formal Aspects of Computing, 19(4):445-474, 2007. doi:10.1007/s00165-007-0024-9.

[18] Jan A. Bergstra and Cornelis A. Middelburg. Distributed strategic interleaving with load balancing. Future Generation Computer Systems, 24(6):530-548, 2008. doi:10.1016/j.future.2007.08.001.

[19] Jan A. Bergstra and Cornelis A. Middelburg. Thread algebra for polythreading. Formal Aspects of Computing, 23(4):567-583, 2011. doi:10.1007/s00165-011-0178-3.

[20] Jan A. Bergstra and Cornelis A. Middelburg. Instruction sequence processing operators. Acta Informatica, 49(3):139-172, 2012. doi:10.1007/s00236-012-0154-2.

[21] Jan A. Bergstra and Cornelis A. Middelburg. On instruction sets for Boolean registers in program algebra. Scientific Annals of Computer Science, 26(1):1-26, 2016. doi:10.7561/SACS.2016.1.1.

[22] Jan A. Bergstra and Cornelis A. Middelburg. Instruction sequences expressing multiplication algorithms. Scientific Annals of Computer Science, 28(1):39-66, 2018. doi:10.7561/SACS.2018.1.39.

[23] Jan A. Bergstra and Cornelis A. Middelburg. A short introduction to program algebra with instructions for boolean registers. Computer Science Journal of Moldova, 26(3):199-232, 2018. URL: http://www.math.md/publications/csjm/issues/v26-n3/12735/.

[24] Jan A. Bergstra and Alban Ponse. Execution architectures for program algebra. Journal of Applied Logic, 5(1):170-192, 2007. doi:10.1016/j.jal.2005.10.013.

[25] Gustavo Betarte, Juan Diego Campo, Carlos Luna, and Agustin Romano. Formal analysis of android’s permission-based security model. Scientific Annals of Computer Science, 26(1):27-68, 2016. doi:10.7561/SACS.2016.1.27.

[26] Harsh Bhasin, Esha Khanna, and Sudha Sudha. Black box testing based on requirement analysis and design specifications. International Journal of Computer Applications, 87(18):36-40, 2014. doi:10.5120/15311-4024.

[27] Ken J. Biba. Integrity considerations for secure computer systems. Technical Report 3154, MITRE CORP BEDFORD MA, 1977.

[28] Manuel Blum and Sampath Kannan. Designing programs that check their work. Journal of the ACM, 42(1):269-291, 1995. doi:10.1145/200836.200880.

[29] Marcel Bohme, Cristian Cadar, and Abhik Roychoudhury. Fuzzing: Challenges and reflections. IEEE Software, 38(3):79-86, 2021. doi:10.1109/MS.2020.3016773.

[30] Adilson Luiz Bonifacio and Arnaldo Vieira Moura. Test suite completeness and black box testing. Software Testing, Verification and Reliability, 27(1-2), 2017. doi:10.1002/stvr.1626.

[31] Luc Bouge. A contribution to the theory of program testing. Theoretical Computer Science, 37:151-181, 1985. doi:10.1016/0304-3975(85)90090-8.

[32] Houssem Ben Braiek and Foutse Khomh. On testing machine learning programs. Journal of Systems and Software, 164:110542, 2020. doi:10.1016/j.jss.2020.110542.

[33] Robert Cartwright. Formal program testing. In John White, Richard J. Lipton, and Patricia C. Goldberg, editors, Conference Record of the Eighth Annual ACM Symposium on Principles of Programming Languages, POPL 1981, pages 125-132. ACM Press, 1981. doi:10.1145/567532.567546.

[34] Christophe Chareton, Sebastien Bardin, Dongho Lee, Benoit Valiron, Renaud Vilmart, and Zhaowei Xu. Formal methods for quantum programs: A survey. CoRR, abs/2109.06493, 2021. arXiv:2109.06493.

[35] Tse-Hsun Chen, Meiyappan Nagappan, Emad Shihab, and Ahmed E. Hassan. An empirical study of dormant bugs. In Premkumar T. Devanbu, Sung Kim, and Martin Pinzger, editors, 11th Working Conference on Mining Software Repositories, MSR 2014, pages 82-91. ACM, 2014. doi:10.1145/2597073.2597108.

[36] Tsong Yueh Chen, S. C. Cheung, and Siu-Ming Yiu. Metamorphic testing: A new approach for generating next test cases. Technical Report HKUST-CS98-01, Deptartment of Computer Science, The Hong Kong University of Science and Technology, 1988. arXiv:2002.12543.

[37] Mohammad Torabi Dashti and David A. Basin. A theory of black-box tests. CoRR, abs/2006.10387, 2020. arXiv:2006.10387.

[38] Richard A. DeMillo, Richard J. Lipton, and Frederick G. Sayward. Hints on test data selection: Help for the practicing programmer. Computer, 11(4):34-41, 1978. doi:10.1109/C-M.1978.218136.

[39] Gencer Erdogan, Yan Li, Ragnhild Kobro Runde, Fredrik Seehusen, and Ketil Stolen. Approaches for the combined use of risk analysis and testing: a systematic literature review. International Journal on Software Tools for Technology Transfer, 16(5):627-642, 2014. doi:10.1007/s10009-014-0330-5.

[40] Michael Felderer, Matthias Buchler, Martin Johns, Achim D. Brucker, Ruth Breu, and Alexander Pretschner. Security testing: A survey. Advances in Computers, 101:1-51, 2016. doi:10.1016/bs.adcom.2015.11.003.

[41] Michael Felderer and Vahid Garousi. Together we are stronger: Evidence-based reflections on industry-academia collaboration in software testing. In Dietmar Winkler, Stefan Bi, Daniel Mendez, and Johannes Bergsmann, editors, 12th International Conference on Software Quality: Quality Intelligence in Software and Systems Engineering, SWQD 2020, volume 371 of Lecture Notes in Business Information Processing, pages 3-12. Springer, 2020. doi:10.1007/978-3-030-35510-4\_1.

[42] Gordon Fraser and Jose Miguel Rojas. Software testing. In Sungdeok Cha, Richard N. Taylor, and Kyo Chul Kang, editors, Handbook of Software Engineering, pages 123-192. Springer, 2019. doi:10.1007/978-3-030-00262-6\_4.

[43] Vahid Garousi, Michael Felderer, and Feyza Nur Kilicaslan. A survey on software testability. Information and Software Technology, 108:35-64, 2019. doi:10.1016/j.infsof.2018.12.003.

[44] Marie-Claude Gaudel. Testing can be formal, too. In Peter D. Mosses, Mogens Nielsen, and Michael I. Schwartzbach, editors, TAPSOFT’95: Theory and Practice of Software Development, 6th International Joint Conference CAAP/FASE, volume 915 of Lecture Notes in Computer Science, pages 82-96. Springer, 1995. doi:10.1007/3-540-59293-8\_188.

[45] Yulia Gavrilova. Machine learning testing: a step to perfection. Serokell Site, November 11 2020 [Online]. URL: https://serokell.io/blog/machine-learning-testing.

[46] David Gelperin and Bill Hetzel. The growth of software testing. Communications of the ACM, 31(6):687-695, 1988. doi:10.1145/62959.62965.

[47] Joseph A. Goguen and Jose Meseguer. Security policies and security models. In 1982 IEEE Symposium on Security and Privacy, pages 11-20. IEEE Computer Society, 1982. doi:10.1109/SP.1982.10014.

[48] John B. Goodenough and Susan L. Gerhart. Toward a theory of test data selection. IEEE Transactions on Software Engineering, 1(2):156-173, 1975. doi:10.1109/TSE.1975.6312836.

[49] John S. Gourlay. A mathematical framework for the investigation of testing. IEEE Transactions on Software Engineering, 9(6):686-709, 1983. doi:10.1109/TSE.1983.235433.

[50] Jens Grabowski, Anthony Wiles, Colin Willcock, and Dieter Hogrefe. On the design of the new testing language TTCN-3. In Hasan Ural, Robert L. Probert, and Gregor von Bochmann, editors, Testing of Communicating Systems: Tools and Techniques, IFIP TC6/WG6.1 13th International Conference on Testing Communicating Systems (TestCom 2000), volume 176 of IFIP Conference Proceedings, pages 161-176. Kluwer, 2000.

[51] Philip J. Guo, Thomas Zimmermann, Nachiappan Nagappan, and Brendan Murphy. “Not my bug!” and other reasons for software bug report reassignments. In Pamela J. Hinds, John C. Tang, Jian Wang, Jakob E. Bardram, and Nicolas Ducheneaut, editors, Proceedings of the 2011 ACM Conference on Computer Supported Cooperative Work, CSCW 2011, pages 395-404. ACM, 2011. doi:10.1145/1958824.1958887.

[52] Brent Hailpern and Padmanabhan Santhanam. Software debugging, testing, and verification. IBM Systems Journal, 41(1):4-12, 2002. doi:10.1147/sj.411.0004.

[53] Dick Hamlet. Predicting dependability by testing. ACM SIGSOFT Software Engineering Notes, 21(3):84-91, 1996. doi:10.1145/226295.226305.

[54] Richard G. Hamlet. Foundations of software testing: Dependability theory. In David S. Wile, editor, Proceedings of the Second ACM SIGSOFT Symposium on Foundations of Software Engineering, SIGSOFT 1994, pages 128-139. ACM, 1994. doi:10.1145/193173.195400.

[55] Shahin Honarvar, Mohammad Reza Mousavi, and Rajagopal Nagarajan. Property-based testing of quantum programs in q#. In ICSE ’20: 42nd International Conference on Software Engineering, pages 430-435. ACM, 2020. doi:10.1145/3387940.3391459.

[56] Cem Kaner. Software negligence and testing coverage. In STAR 96: Fifth International Conference on Software Testing, Analysis, and Review, pages 313-327, 1996.

[57] Robert Konighofer, Georg Ho erek, and Roderick Bloem. Debugging formal specifications using simple counterstrategies. In Proceedings of 9th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2009, pages 152-159. IEEE, 2009. doi:10.1109/FMCAD.2009.5351127.

[58] Christine M. Kreiser. Computer bug. American History, 45(6):19, 2011.

[59] Butler W. Lampson. A note on the confinement problem. Communications of the ACM, 16(10):613-615, 1973. doi:10.1145/362375.362389.

[60] Carl E. Landwehr, Alan R. Bull, John P. McDermott, and William S. Choi. A taxonomy of computer program security flaws. ACM Computing Surveys, 26(3):211-254, 1994. doi:10.1145/185403.185412.

[61] Janusz W. Laski. Programming faults and errors: Towards a theory of software incorrectness. Annals of Software Engineering, 4:79-114, 1997. doi:10.1023/A:1018966827888.

[62] Jun Li, Bodong Zhao, and Chao Zhang. Fuzzing: a survey. Cybersecurity, 1(1):6, 2018. doi:10.1186/s42400-018-0002-y.

[63] Richard J. Lipton. New directions in testing. In Joan Feigenbaum and Michael Merritt, editors, Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 191-202. DIMACS/AMS, 1989. doi:10.1090/dimacs/002/13.

[64] Pan Liu, Yihao Li, and Huaikou Miao. Transition algebra for software testing. IEEE Transactions on Reliability, 70(4):1438-1454, 2021. doi:10.1109/TR.2021.3116054.

[65] Lu Luo. Software testing techniques: Technology maturation and research strategies. Technical Report 17-939A, Institute for Software Research International, Carnegie Mellon University, 2001.

[66] Annabelle McIver and Carroll Morgan. Correctness by construction for probabilistic programs. In Tiziana Margaria and Bernhard Ste en, editors, 9th International Symposium on Leveraging Applications of Formal Methods: Verification Principles, ISoLA 2020, volume 12476 of Lecture Notes in Computer Science, pages 216-239. Springer, 2020. doi:10.1007/978-3-030-61362-4\_12.

[67] Cornelis A. Middelburg. Searching publications on software testing. CoRR, abs/1008.2647, 2010. arXiv:1008.2647.

[68] Cornelis A. Middelburg. Program algebra for random access machine programs. CoRR, abs/2007.09946, 2020. arXiv:2007.09946.

[69] Ali Mili, Marcelo F. Frias, and Ali Jaoua. On faults and faulty programs. In Peter Hofner, Peter Jipsen, Wolfram Kahl, and Martin Eric Muller, editors, 14th International Conference on Relational and Algebraic Methods in Computer Science, volume 8428 of Lecture Notes in Computer Science, pages 191-207. Springer, 2014. doi:10.1007/978-3-319-06251-8\_12.

[70] Roy Miller and Christopher Collins. Acceptance testing. In Proceedings XPUniverse 2001, page 238, 2001.

[71] Andriy V. Miranskyy, Lei Zhang, and Javad Doliskani. Is your quantum program bug-free? In Gregg Rothermel and Doo-Hwan Bae, editors, ICSE-NIER 2020: 42nd International Conference on Software Engineering, New Ideas and Emerging Results, pages 29-32. ACM, 2020. doi:10.1145/3377816.3381731.

[72] Joshua Moerman. Nominal Techniques and Black Box Testing for Automata Learning. PhD thesis, Radboud University Nijmegen, 2019. URL: http://hdl.handle.net/2066/204194.

[73] Edward F. Moore. Gedanken-Experiments on Sequential Machines, pages 129-154. Princeton University Press, 1956. doi:10.1515/9781400882618-006.

[74] Srinivas Nidhra and Jagruthi Dondeti. Black box and white box testing techniques-a literature review. International Journal of Embedded Systems and Applications (IJESA), 2(2):29-50, 2012. doi:10.5121/ijesa.2012.2204.

[75] Adrian Nistor. Understanding, detecting, and repairing performance bugs. PhD thesis, University of Illinois at Urbana-Champaign, 2014. URL: https://mir.cs.illinois.edu/marinov/publications/Nistor14PhD.pdf.

[76] Tom Ridge, David Sheets, Thomas Tuerk, Andrea Giugliano, Anil Madhavapeddy, and Peter Sewell. Sibylfs: formal specification and oracle-based testing for POSIX and real-world file systems. In Ethan L. Miller and Steven Hand, editors, Proceedings of the 25th Symposium on Operating Systems Principles, SOSP 2015, pages 38-53. ACM, 2015. doi:10.1145/2815400.2815411.

[77] Sergio Segura, Dave Towey, Zhi Quan Zhou, and Tsong Yueh Chen. Metamorphic testing: Testing the untestable. IEEE Software, 37(3):46-53, 2020. doi:10.1109/MS.2018.2875968.

[78] Fred R. Shapiro. Etymology of the computer bug: History and folklore. American Speech, 62(4):376-378, 1987. URL: http://www.jstor.org/stable/455415.

[79] Emad Shihab, Audris Mockus, Yasutaka Kamei, Bram Adams, and Ahmed E. Hassan. High-impact defects: a study of breakage and surprise defects. In Tibor Gyimothy and Andreas Zeller, editors, SIGSOFT/FSE’11 19th ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE-19) and ESEC’11: 13th European Software Engineering Conference (ESEC-13), pages 300-310. ACM, 2011. doi:10.1145/2025113.2025155.

[80] Yogesh Singh. Software Testing. Cambridge University Press, 2011. doi:10.1017/CBO9781139196185.

[81] Eric Steegmans, Pieter Bekaert, Frank Devos, Geert Delanote, Nele Smeets, Marko van Dooren, and Jeroen Boydens. Black & white testing: Bridging black box testing and white box testing. pages 1-12. Sterck, P, 2004. URL: https://lirias.kuleuven.be/retrieve/6947.

[82] Jan Tretmans. Testing concurrent systems: A formal approach. In Jos C. M. Baeten and Sjouke Mauw, editors, CONCUR ’99: 10th International Conference on Concurrency Theory, volume 1664 of Lecture Notes in Computer Science, pages 46-65. Springer, 1999. doi:10.1007/3-540-48320-9\_6.

[83] Jeffrey M. Voas and Keith W. Miller. Software testability: The new verification. IEEE Software, 12(3):17-28, 1995. doi:10.1109/52.382180.

[84] Thuy Duong Vu. Thread algebra for noninterference. RAIRO – Theoretical Informatics and Applications, 43(2):249-268, 2009. doi:10.1051/ita:2008026.

[85] John Watkins. Agile Testing: How to Succeed in an Extreme Testing Environment. Cambridge University Press, 2009.

[86] Yi Wei, Bertrand Meyer, and Manuel Oriol. Is branch coverage a good measure of testing effectiveness? In Bertrand Meyer and Martin Nordio, editors, International Summer Schools on Empirical Software Engineering and Verification, LASER 2008-2010, Revised Tutorial Lectures, volume 7007 of Lecture Notes in Computer Science, pages 194-212. Springer, 2010. doi:10.1007/978-3-642-25231-0\_5.

[87] Elaine J. Weyuker. On testing non-testable programs. The Computer Journal, 25(4):465-470, 1982. doi:10.1093/comjnl/25.4.465.

[88] Elaine J. Weyuker. Evaluating software complexity measures. IEEE Transactions on Software Engineering, 14(9):1357-1365, 1988. doi:10.1109/32.6178.

[89] Elaine J.Weyuker and Thomas J. Ostrand. Theories of program testing and the application of revealing subdomains. IEEE Transactions on Software Engineering, 6(3):236-246, 1980. doi:10.1109/TSE.1980.234485.

[90] Linmin Yang, Zhe Dang, and Thomas R. Fischer. Information gain of black-box testing. Formal Aspects of Computing, 23(4):513-539, 2011. doi:10.1007/s00165-011-0175-6.

[91] Peng Yang, Zixi Liu, Jin Xu, Yong Huang, and Ya Pan. An empirical study on the ability relationships between programming and testing. IEEE Access, 8:161438-161448, 2020. doi:10.1109/ACCESS.2020.3018718.

[92] Abubakar Zakari, Sai Peck Lee, and Chun Yong Chong. Simultaneous localization of software faults based on complex network theory. IEEE Access, 6:23990-24002, 2018. doi:10.1109/ACCESS.2018.2829541.

[93] Jie M. Zhang, Mark Harman, Lei Ma, and Yang Liu. Machine learning testing: Survey, landscapes and horizons. IEEE Transactions on Software Engineering, 48(2):1-36, 2022. doi:10.1109/TSE.2019.2962027.

Bibtex

@article{sacscuza:bergstra22astaist,
  title={A Survey of Testing for Admit Instruction Sequence Theory},
  author={J.A. Bergstra},
  journal={Scientific Annals of Computer Science},
  volume={32},
  number={1},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2022},
  pages={5-86},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2022.1.5}
}