Published in Volume XXXI, Issue 1, 2021, pages 1-50, doi: 10.7561/SACS.2021.1.1

Authors: J.A. Bergstra


Starting out from the survey of instruction sequence faults from [6] program faults are classified according to the conventional criteria of being dormant, effective, detected, temporary, and permanent. Being retrospectively approved is introduced as an additional qualification. For this theoretical investigation the context is simplified by contemplating instruction sequences as a theoretical model for programs, and by assuming that instruction sequences are supposed to compute total transformations on finite bit sequences of a fixed length only.

The main conclusion which can be drawn from this work concerns the notion of dormancy. First of all it is noticed that the unconventional notion of a dormant failure is both plausible and amenable to a straightforward and convincing definition. The conventional notion of a dormant fault, however, is much harder to grasp and the definition of a dormant fault which is provided in the paper may be disputed.

The notion of a dormant fault seems to admit no convincing intuition. All faults are defects but not the other way around. The idea of a fault exclusively depends on an instruction sequence and a specification of which it is considered to be a candidate implementation. In the presence of a design, however, in addition to faults, the notion of a deviation from design (DFD) defect arises, which constitutes a class of defects many of which are not faults. For DFD defects the notion of dormancy admits a straightforward and convincing definition.

Full Text (PDF)


[1] H. Mushtaq, Z. Al-Ars, K. Bertels. Survey of Fault Tolerance Techniques for Shared Memory Multicore/Multiprocessor Systems. 6th IEEE International Design and Test Workshop (IDT 2011), 12-17, (2011). doi:10.1109/IDT.2011.6123094

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

[3] A. Avizienzis, 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

[4] 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.

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

[6] J.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

[7] J.A. Bergstra. Sumterms, summands, sumtuples, and sums and the meta-arithmetic of summation. Scientific Annals of Computer Science 30 (2), 167{203 (2020). doi:10.7561/SACS.2020.2.167

[8] 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

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

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

[11] 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

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

[13] J.A. Bergstra, C.A. Middelburg. On Algorithmic Equivalence of Instruction Sequences for Computing Bit String Functions. Fundamenta Informaticae 138 (4), 411-434, 2014. doi:10.3233/FI-2015-1219

[14] 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

[15] J.A. Bergstra, C.A. Middelburg. Instruction Sequence Size Complexity of Parity. Fundamenta Informaticae 149 (3), 411-434, 2014. doi:10.3233/FI-2016-1450

[16] 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.

[17] N. Diallo, W. Ghardallou, A. Mili. Relative Correctness: A Bridge Between Testing and Proving. 10th Workshop on Veri cation and Evaluation of Computer and Communication System (VECoS 2016), 141-156, 2016. CEUR-WS:Vol-1689/paper11

[18] E.W. Dijkstra. Notes on Structure Programming. Technological University Eindhoven, Department of Mathematics and Computing Science. Vol. 70-WSK-03, 1970. TUE-TR:EWD249

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

[20] 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

[21] 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

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

[23] A. Mili, M.F. Frias, A. Jaoua. On Faults and Faulty Programs. In: P. Hofner, P. Jipsen, W. Kahl, M.E. Muller (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

[24] A. Ponse. Program Algebra with Unit Instruction Operators. Journal of Logic and Algebraic Programming 51 (2), 157-174, 2002. doi:10.1016/S1567-8326(02)00019-X

[25] 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

[26] 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

[27] 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

[28] 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={Qualifications of Instruction Sequence Failures, Faults and Defects: Dormant, Effective, Detected, Temporary, and Permanent},
  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},