Published in Volume XXX, Issue 2, 2020, pages 105-166, doi: 10.7561/SACS.2020.2.105

Authors: J.A. Bergstra


The notion of an instruction sequence fault is considered as a theoretical concept, for which the justification of the  qualification of a fragment as faulty is mathematical instead of pragmatic, the latter approach being much more common. Starting from so-called Laski faults a range of patterns of faults and changes thereof for instruction sequences is developed.

Full Text (PDF)


[1] Z.A. Alzamil. Application of Redundant Computation in Program Debugging. The Journal of Systems and Software 81, 2024-2033, 2008. doi:10.1016/j.jss.2008.02.024.

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

[3] A. Avižienzis, J.C. Laprie, B. Randell. Fundamental Concepts of Dependability. In Workshop on Robot Dependability: Technological Challenge of Dependable Robots in Human Environments, Seoul, 2001.

[4] A. Avižienzis, J.C. Laprie, B. Randell, C. Landwehr. Basic Concepts and Taxonomy of Dependable and Secure Computing. IEEE Transactions on Dependable and Secure Computing 1 (1), 1–23, 2004. doi:10.1109/TDSC.2004.2.

[5] R. Balzer, N. Goldman. Principles of Good Software Specification and Their Implications for Specification Language. AFIPS’81, 393-400, 1981. doi:10.1145/1500412.1500468.

[6] J.A. Bergstra. Quantitative Expressiveness of Instruction Sequence Classes for Computation on Single Bit Registers.. Computer Science Journal of Moldova 27 (2), 131-161, 2019.

[7] J.A. Bergstra. Adams Conditioning and Likelihood Ratio Transfer Mediated Inference. Scientific Annals of Computer Science 29 (1), 1–58, 2019. doi:10.7561/sacs.2019.1.1.

[8] J.A. Bergstra, I. 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.

[9] J.A. Bergstra, M. Burgess. A Promise Theoretic Account of the Boeing 737 Max MCAS Algorithm Affair. 2019. arxiv:2001.01543v1.

[10] J.A. Bergstra, M. Burgess. Candidate Software Process Flaws for the Boeing 737 Max MCAS Algorithm and a Risk for a Proposed Upgrade. 2020. arxiv:2001.05690v1.

[11] J.A. Bergstra, 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.

[12] J.A. Bergstra, C.A. Middelburg. Thread Algebra for Strategic Interleaving. Formal Aspects of Computing 19 (4), 445–474, 2007. doi:10.1007/s00165-007-0024-9.

[13] J.A. Bergstra, C.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.

[14] J.A. Bergstra, C.A. Middelburg. Thread Extraction for Polyadic Instruction Sequences. Scientific Annals of Computer Science 21 (2), 283–310, 2011.

[15] J.A. Bergstra, C.A. Middelburg. Thread Algebra for Poly-Threading. Formal Aspects of Computing 23 (4), 567–583, 2011. doi:10.1007/s00165-011-0178-3.

[16] J.A. Bergstra, C.A. Middelburg. Instruction Sequence Processing Operators. Acta Informatica 49 (3), 139–172, 2012. doi:10.1007/s00236-012-0154-2.

[17] J.A. Bergstra, C.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.

[18] J.A. Bergstra, C.A. Middelburg. A Short Introduction to Program Algebra with Instructions for Boolean Registers. Computer Science Journal of Moldova 26 (3), 199–232, 2019.

[19] J.A. Bergstra, C.A. Middelburg. Program Algebra for Turing-Machine Programs. Scientific Annals of Computer Science 29 (2), 113–139, 2019. doi:10.7561/sacs.2019.2.113.

[20] J.A. Bergstra, A. Ponse. Execution Architectures for Program Algebra. Journal of Applied Logic 5 (1), 170–192, 2004. doi:10.1016/j.jal.2005.10.013.

[21] A. Bertolino. The (Im)Maturity Level of Software Testing. ACM SIGSOFT Software Engineering Notes 29 (5), 1–4, 2004. doi:10.1145/1022494.1022540.

[22] I.B. Bourdonov, A.S. Kossatschev, V.V. Kulianin. Formalization of Test Experiments. Programming and Computer Software 33 (5), 239-260, 2007. doi:10.1134/s0361768807050015.

[23] M. Christakis, M. Heizmann, M.N. Mansur, C. Schilling, V. Wüstholz. Semantic Fault Localization and Suspiciousness Ranking. In T. Vojnar, L. Zhang (Eds.), Tools and Algorithms for the Construction and Anal-
ysis of Systems (TACAS 2019), Lecture Notes in Computer Science 11427, 226–243, 2019. doi:10.1007/978-3-030-17462-0_13.

[24] T.R. Colburn. Program Verification, Defeasible Reasoning, and Two Views of Computer Science. Minds and machines 1, 97–116, 1991. doi:10.1007/978-94-011-1793-7_17.

[25] W. Ghardallou, A. Mili, N. Diallo. Relative Correctness: A Bridge Between Testing and Proving. In M. Ghazel, M. Jmaiel (Eds.), Proceedings of the 10th Workshop on Verification and Evaluation of Computer and Communication System (VECoS 2016), CEUR Workshop Proceedings 1689, 141-156, 2016.

[26] M. Dyer. A Formal Approach to Software Errors Removal. The Journal of Systems and Software 7, 109-114, 1987. doi:10.1016/0164-1212(87)90015-x.

[27] J.H. Feltzer. Philosophical Aspects of Program Verification. Minds and Machines 1, 197-216, 1991. doi:10.1007/978-94-011-1793-7_18.

[28] R.L. Glass. Persistent Software Errors. IEEE Transactions on Software Engineering 7 (2), 162–168, 1981. doi:10.1109/tse.1981.230831.

[29] R. Gopinah, C. Jensen, A. Groce. Mutations: How Close Are They to Real Faults? 25th International Symposium on Software Reliability Engineering, 2014. doi:10.1109/ISSRE.2014.40.

[30] M. Grottke, K.S. Tivedi. A Classification of Software Faults. 16th IEEE Symposium on Software Reliability Engineering, 19–20, 2005.

[31] L. Hatton. Programming Technology, Reliability, Safety and Measurement. Computing and Control Engineering Journal 9 (1), 23–27, 1998. doi:10.1049/cce:19980105.

[32] J.J. Horning. Program Specification: Issues and Observations. In J. Staunstrup (Ed.), Program Specification (ProgSpec 1981), Lecture Notes in Computer Science 134. 5–24, 2005. doi:10.1007/3-540-11490-4_2.

[33] K. Hewett, P. Kijsanayothin. On Modeling Software Defect Repair Time. Empirical Software Engineering 14 (2), 165–186, 2009. doi:10.1007/s10664-008-9064-x.

[34] B. R. Kidwell. MiSFIT: Mining Software Fault Information and Types. University of Kentucky, Theses and Dissertations–Computer Science. 33, 2015.

[35] E. van der Kouwe. Improving Software Fault Injection. Ph. D. Thesis, Vrije Universiteit Amsterdam, 2016.

[36] J.C. Laprie. Dependable Computing and Fault Tolerance: Concepts and Terminology. In Twenty-Fifth International Symposium on Fault-Tolerant Computing, Highlights from Twenty-Five Years, 2–11, 1995. doi:10.1109/FTCSH.1995.532603.

[37] J. Laski. Programming Faults and Errors: Towards a Theory of Software Incorrectness. Annals of Software Engineering 4, 79–114, 1997. doi:10.1023/A:1018966827888.

[38] C.A. Middelburg. Searching Publications on Software Testing. 2010. arxiv:1008.2647v1.

[39] A. Mili, M.F. Frias, A. Jaoua. On Faults and Faulty Programs. In: P. Höfner, P. Jipsen, W. Kahl, M.E. Müller (Eds.), Relational and Algebraic Methods in Computer Science (RAMICS 2014), Lecture Notes in Computer Science 8428, 191–207, 2014. doi:10.1007/978-3-319-06251-8_12.

[40] A. Mockus, D.M. Weiss. Predicting Risk of Software Changes. Bell Labs Technical Journal 5 (2), 169–180, 2000. doi:10.1002/bltj.2229.

[41] S. Mukherjee, J. Emer, S.R. Reinhardt. The Soft Error Problem: An Architectural perspective. 11th International Symposium on High-Performance Computer Architecture, 2005. doi:10.1109/HPCA.2005.37.

[42] J.C. Munson, A.P. Nikora, J.S. Sherif. Software Faults: A Quantifyable Definition. Advances in Engineering Software 37 (5), 327–333, 2005. doi:10.1016/j.advengsoft.2005.07.003.

[43] B. Nuseibeh. Ariane 5: Who Dunnit? IEEE Software 14 (3), 15–16, 1997. doi:10.1109/ms.1997.589224.

[44] A.J. Offut, J.H. Hayes. A Semantic Model of Program Faults. ACM SIGSOFT Software Engineering Notes 21 (3), 195–200, 1996. doi:10.1145/226295.226317.

[45] J. Ploski, M. Rohr, P. Schwenkenberg, W. Hasselbring. Research Issues in Software Fault Categorization. ACM Software Engineering Notes 32 (6), 1–8, 2007. doi:10.1145/1317471.1317478.

[46] Z. Qi, F. Long, S. Achour, M. Rinard. An Analysis of Patch Plausibility and Correctness for Generate-and-Validate Patch Generation Systems. Proceedings of the 2015 International Symposium on Software Test-
ing and Analysis (SSTA 2015), 24–36, 2015. doi:10.1145/2771783.2771791.

[47] S. Saha, R.K. Saha, M.K. Prasad. Harnessing Evolution for Multi-Hunk Program Repair. IEEE/ACM 41st International Conference on Software Engineering (ICSE), 2019. doi:10.1109/ICSE.2019.00020.

[48] J. Shimeall, N.G. Leveson. An Empirical Comparison of Software-Fault Tolerance Elimination and Software Fault Elimination. IEEE Transactions on Software Engineering 17 (2), 173–183, 1991. doi:10.1109/32.67598.

[49] The House Committee on Transportation and Infrastructure: Boeing 737 Max Aircraft: Costs, Consequences, and Lessons from Its Design, Development, and Certification : Preliminary Investigative Findings. (2020).

[50] J.A. Whittaker. What is Software Testing? And Why is it so Hard? IEEE Software 17 (1), 70–79, 2000. doi:10.1109/52.819971.

[51] J.M. Wing. Program Specification. Encyclopaedia of Computer Science 1454–1458, 2003.

[52] W. E. Wong, R. Gao, Y. Li, R. Abreu, F. Wotawa. A Survey on Software Fault Localization. IEEE Transactions on Software Engineering 42 (8), 707–740, 2016. doi:10.1109/tse.2016.2521368.

[53] L. Xiaojian, J. Ting, D. Xiaofeng. Formal Definition of Program Faults and Hierarchy of Program Fault-Tolerant Abilities. 4th International Conference on Information Science and Control Engineering (ICISCE), 2017. doi:10.1109/ICISCE.2017.78.

[54] X. Xie, T.Y. Chen, F.C. Kuo, B. Xu. A Theoretical Analysis of the Risk Evaluation Formulas for Spectrum-Based Fault Localization. ACM Transactions on Software Engineering and Methodology 22 (4), article no. 31, 2013. doi:10.1145/2522920.2522924.

[55] A. Zakari, S.P. Lee, C.Y. Chong. Simultaneous Localization of Software Faults Based on Complex Network Theory. IEEE Access 6, 23990–24002, 2018. doi:10.1109/access.2018.2829541.


  title={Instruction Sequence Faults with Formal Change Justification},
  author={J.A. Bergstra},
  journal={Scientific Annals of Computer Science},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},