The Library

A methodology for the generation of efficient error detection mechanisms

Tools

Leeke, Matthew, Arif, Saima, Jhumka, Arshad and Anand, Sarabjot Singh (2011) A methodology for the generation of efficient error detection mechanisms. In: IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN), Hong Kong, 27-30 June 2011 . Published in: Proceedings of the 41st International Conference on Dependable Systems and Networks pp. 25-36.

Preview

PDF
WRAP_Leeke_A_Methodology_for_the_Generation_of_Efficient_Error_Detection_Mechanisms.pdf - Draft Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (399Kb) | Preview

Official URL: http://dx.doi.org/10.1109/DSN.2011.5958204

Abstract

A dependable software system must contain error detection mechanisms and error recovery mechanisms. Software components for the detection of errors are typically designed based on a system specification or the experience of software engineers, with their efficiency typically being measured using fault injection and metrics such as coverage and latency. In this paper, we introduce a methodology for the design of highly efficient error detection mechanisms. The proposed methodology combines fault injection analysis and data mining techniques in order to generate predicates for efficient error detection mechanisms. The results presented demonstrate the viability of the methodology as an approach for the development of efficient error detection mechanisms, as the predicates generated yield a true positive rate of almost 100% and a false positive rate very close to 0% for the detection of failure-inducing states. The main advantage of the proposed methodology over current state-of-the-art approaches is that efficient detectors are obtained by design, rather than by using specification-based detector design or the experience of software engineers.

Item Type:

Conference Item (Paper)

Subjects:

Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software

Divisions:

Faculty of Science > Computer Science

Library of Congress Subject Headings (LCSH):

Debugging in computer science, Data mining

Journal or Publication Title:

Proceedings of the 41st International Conference on Dependable Systems and Networks

Publisher:

IEEE

ISBN:

9781424492329

ISSN:

1530-0889

Book Title:

2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN)

Official Date:

27 June 2011

Dates:

Date	Event
27 June 2011	Available

Page Range:

pp. 25-36

Identification Number:

10.1109/DSN.2011.5958204

Status:

Peer Reviewed

Publication Status:

Published

Access rights to Published version:

Restricted or Subscription Access

Conference Paper Type:

Paper

Title of Event:

IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN)

Type of Event:

Conference

Location of Event:

Hong Kong

Date(s) of Event:

27-30 June 2011

References:

[1] J.-C. Laprie, Dependability: Basic Concepts and Terminology. Springer-Verlag, December 1992.
[2] A. Arora and S. S. Kulkarni, “Detectors and correctors: A theory of fault-tolerance components,” in Proceedings of the 18th IEEE International Conference on Distributed Computing Systems, May 1998, pp. 436–443.
[3] A. Jhumka, F. Freiling, C. Fetzer, and N. Suri, “An approach to synthesise safe systems,” International Journal of Security and Networks, vol. 1, no. 1, pp. 62–74, September 2006.
[4] M. Hsueh, T. K. Tsai, and R. K. Iyer, “Fault injection
techniques and tools,” IEEE Computer, vol. 30, no. 4, pp.
75–82, April 1997.
[5] D. Powell, E. Martins, J. Arlat, and Y. Crouzet, “Estimators for fault tolerance coverage evaluation,” IEEE Transactions on Computers, vol. 44, no. 2, pp. 261–274, June 1995.
[6] M. Hiller, “Executable assertions for detecting data errors in embedded control systems,” in Proceedings of the 30th IEEE/IFIP International Conference on Dependable Systems and Networks, June 2000, pp. 24–33.
[7] J. Vinter, J. Aidemark, P. Folkesson, and J. Karlsson, “Reducing critical failures for control algorithms using executable assertions and best effort recovery,” in Proceedings of the 37th IEEE/IFIP International Conference on Dependable Systems and Networks, July 2001, pp. 347–356.
[8] N. G. Leveson, S. S. Cha, J. C. Knight, and T. J. Shimeall, “The use of self checks and voting in software error detection: An empirical study,” IEEE Transactions on Software Engineering, vol. 16, no. 4, pp. 432–443, April 1990.
[9] A. Jhumka and M. Leeke, “Issues on the design of efficient fail-safe fault tolerance,” in Proceedings International Symposium on Software Reliability Engineering, November 2009, pp. 155–164.
[10] S. S. Kulkarni and A. Arora, “Automating the addition
of fault-tolerance,” in Proceedings of the 6th International
Symposium on Formal Techniques in Real-Time and Fault-
Tolerant Systems, September 2000, pp. 82–93.
[11] S. S. Kulkarni and A. Ebnenasir, “Complexity of adding failsafe fault-tolerance,” in Proceedings of the 22nd IEEE International Conference on Distributed Computing Systems, July 2002, pp. 337–344.
[12] M. Hiller, A. Jhumka, and N. Suri, “Propane: An environment for examining the propagation of errors in software,” in Proceedings of the 11th ACM SIGSOFT International Symposium on Software Testing and Analysis, July 2002, pp. 81–85.
[13] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten, “The weka data mining software: An update,” SIGKDD Explorations, vol. 11, no. 1, pp. 10–18, June 2009.
[14] M. Hiller, A. Jhumka, and N. Suri, “An approach for
analysing the propagation of data errors in software,” in
Proceedings of the 31st IEEE/IFIP International Conference on Dependable Systems and Networks, July 2001, pp. 161–172.
[15] A. Jhumka, M. Hiller, and N. Suri, “An approach for designing and assessing detectors for dependable component-based systems,” in Proceedings of the 8th IEEE International Symposium on High Assurance Systems Engineering, March 2004, pp. 69–78.
[16] G. Pinter, H. Madeira, M. Vieira, A. Pataricza, and I. Majzik, “A data mining approach to identify key factors in dependability experiments in dependable computing,” in Proceedings of the 5th European Dependable Computing Conference, March 2005, pp. 263–280.
[17] C.-T. Lu, A. P. Boedihardjo, and P. Manalwar, “Exploiting efficient data mining techniques to enhance intrusion detection systems,” in Proceedings of the 2005 IEEE International Conference on Information Reuse and Integration, September 2005, pp. 512–517.
[18] S. J. Wenke Lee Stolfo and K. W. Mok, “A data mining framework for building intrusion detection models,” in Proceedings of the 20th IEEE Symposium on Security and Privacy, May 1999, pp. 120–132.
[19] E. Clarke, O. Grumberg, and D. Peled, Model Checking. MIT Press, January 2000.
[20] D. A. Schmidt, “Data flow analysis is model checking of abstract interpretations,” in Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 1998, pp. 38–48.
[21] P. Cousot and R. Cousot, “Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints,” in Proceedings 6th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 1977, pp. 238–252.
[22] M. D. Ernst, J. Cockrell, W. G. Griswold, and D. Notkin,
“Dynamically discovering likely program invariants to support program evolution,” IEEE Transactions on Software Engineering, vol. 27, no. 2, pp. 99–123, February 2001.
[23] B. Demsky, M. D. Ernst, P. J. Guo, S. McCamant, J. H.
Perkins, and M. Rinard, “Inference and enforcement of data structure consistency specifications,” in Proceedings of the International Symposium on Software Testing and Analysis, May 2006, pp. 233–244.
[24] S. K. Sahoo, M. Li, P. Ramachandran, S. V. Adve, V. S.
Adve, and Y. Zhou, “Using likely program invariants to detect hardware errors,” in Proceedings of the 38th IEEE/IFIP International Conference on Dependable Systems and Networks, June 2008, pp. 70–79.
[25] D. Powell, “Failure model assumptions and assumption coverage,” in Proceedings of the 22nd International Symposium on Fault-Tolerant Computing, July 1992, pp. 386–395.
[26] M. Kubat, R. C. Holte, and S. Matwin, “Machine learning for the detection of oil spills in satellite radar images,” Machine Learning, vol. 30, no. 2-3, pp. 195–215, 1998.
[27] T. Fawcett, “An introduction to roc analysis,” Pattern Recognition Letters, vol. 27, no. 8, pp. 861–874, June 2006.
[28] N. Japkowicz, “The class imbalance problem: Significance and strategies,” in Proceedings of the 2000 International Conference on Artificial Intelligence (ICAI, June 2000, pp. 111–117.
[29] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone, Classification and Regression Trees. Chapman and Hall/CRC, January 1984.
[30] M. Pazzani, C. Merz, P. Murphy, K. Ali, T. Hume, and
C. Brunk, “Reducing misclassification costs,” in Proceedings of the 11th International Conference on Machine Learning, July 1994, pp. 217–225.
[31] K. M. Ting, “An instance-weighting method to induce costsensitive trees,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 3, pp. 659–665, May 2002.
[32] P. Domingos, “A general method for making classifiers costsensitive,” in Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 1999, pp. 155–164.
[33] W. Fan, S. J. Stolfo, J. Zhang, and P. K. Chan, “Misclassification cost-sensitive boosting,” in Proceedings of the 16th International Conference on Machine Learning, June 1999, pp. 97–105.
[34] J. Quinlan, C4.5: Programs for Machine Learning. Morgan Kaufmann, October 1992.
[35] M. Kubat and S. Matwin, “Addressing the curse of imbalanced training sets: One-sided selection,” in Proceedings of the 14th International Conference on Machine Learning, January 1997, pp. 179–186.
[36] D. D. Lewis and J. Catlett, “Heterogeneous uncertainty sampling for supervised learning,” in Proceedings of the 11th International Conference on Machine Learning, June 1994, pp. 148–156.
[37] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P.
Kegelmeyer, “Smote: Synthetic minority over-sampling technique,” Journal of Artificial Intelligence Research, vol. 16, no. 1, pp. 321–357, May 2002.
[38] B. Zadrozny, J. Langford, and N. Abe, “Cost-sensitive learning by cost-proportionate example weighting,” in Proceedings of the 3rd IEEE International Conference on Data Mining, July, 2003, pp. 435–442.
[39] N. V. Chawla, D. A. Cieslak, L. O. Hall, and A. Joshi, “Automatically countering imbalance and its empirical relationship to cost,” Journal of Data Minining and Knowledge Discovery, vol. 17, no. 2, pp. 225–252, February 2008.
[40] 7-Zip, “http://www.7-zip.org/,” 2010.
[41] FlightGear, “http://www.flightgear.org/,” April 2009.
[42] Mp3Gain, “http://mp3gain.sourceforge.net/,” 2010.