Diversity Through N-Version Programming: Current State, Challenges and Recommendations

Full Text (PDF, 308KB), PP.56-64

Views: 0 Downloads: 0

Author(s)

Raphael Khoury 1,* Abdelwahab Hamou-Lhadj 2 Mario Couture 1 Robert Charpentier 1

1. Defence Research and Development Canada-Valcartier Research Center, Quebec, Canada

2. Department of Electrical & Computer Engineering, Concordia University, Montreal Canada

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2012.02.08

Received: 14 Feb. 2011 / Revised: 4 Jun. 2011 / Accepted: 22 Aug. 2011 / Published: 8 Mar. 2012

Index Terms

Software reliability, System design, N-version programming, fault-tolerance

Abstract

N-version programming is a software development paradigm that draws upon the concept of diversity to increase the reliability of software. The central idea is to independently produce multiple functionally equivalent versions of a program, and execute them in parallel. If the versions fail independently, then the probability of multiple versions producing a faulty output on any given input is very small; much lower than the failure probability of any single version. In this paper, we examine and contrast various experiments that have been performed to evaluate the benefits of this approach and draw some conclusions. We find that for diversity to be effective, it must be introduced in a targeted and informed manner and encompass several phases of the software’s development.

Cite This Paper

Raphaël Khoury, Abdelwahab Hamou-Lhadj, Mario Couture, Robert Charpentier, "Diversity Through N-Version Programming: Current State, Challenges and Recommendations", IJITCS, vol.4, no.2, pp.56-64, 2012. DOI:10.5815/ijitcs.2012.02.08

Reference

[1]A. Avizienis. The N-Version Approach to Fault-Tolerant Software. 1985, IEEE Transactions on Software Engineering 11 (12), pp. 1491--1501.

[2]D. E. Eckhardt, Jr. and L. D. Lee. A theoretical basis for the analysis of redundant software subject to coincident errors. NASA Technical Memorandum 86369, 1985.

[3]B. Littlewood, P. Popov and L. Strigini. Modelling software design diversity - a review. ACM Computing Surveys. ACM, June 2001, 33(2), pp. 177-208.

[4]D. Partridge and W. Krzanowski. Distinct Failure Diversity in Multiversion Software. University of Exeter, U.K., 1997.

[5]A. Avizienis. The N-Version Approach to Fault-Tolerant Software. 1985, IEEE Transactions on Software Engineering (TSE) 11(12), pp. 1491-1501.

[6]D. Gao, M. K. Reiter and D. Song. Behavioral Distance Measurement Using Hidden Markov Models. In Proceedings of the 9th International Symposium on Recent Advances in Intrusion Detection (RAID 2006), Hamburg, Germany, September 2006

[7]D. Gao, M. K. Reiter and D. Song. Behavioral Distance for Intrusion Detection. In Proceedings of the 8th International Symposium on Recent Advances in Intrusion Detection (RAID 2005), Seattle, WA, USA, September 2005

[8]I. Gashi, et al. An Experimental Study of Diversity with Off-the-Shelf AntiVirus Engines. In Proceedings of The Eighth IEEE International Symposium on Networking Computing and Applications (NCA). Cambridge, Massachusetts , USA. 2009. pp. 4-11.

[9]F. B. Schneider. Beyond traces and independence. Dependable and Historic Computing. Essays Dedicated to Brian Randell on the Occasion of His 75th Birthday, Lecture Notes in Computer Science, Vol. 6875 (Cliff Jones and John Lloyd, eds). Springer Verlag, 2011, 479--485.

[10]B. Littlewood and S. Lorenzo. Redundancy and Diversity in Security. In Proceedings of the 9th European Symposium on Research in Computer Security (ESORICS 2004), Sophia Antipolis, France, September, pp. 423-438, Springer-Verlag, Lecture Notes in Computer Science 3193, 2004.

[11]D. Williams et al. Security through Diversity: Leveraging Virtual Machine Technology. IEEE Security & Privacy. 2009,7 (1), pp. 26--33.

[12]ANSI/IEEE. Standard Glossary of Software Engineering Terminology. STD-729-1991, 1991.

[13]A. Avizienis and J. Kelly. Fault Tolerance by Design Diversity: Concepts and Experiments. 1984, Computer 17(8), pp. 67 - 80.

[14]D. E. Jr. Eckhardt et al. An experimental evaluation of software redundancy as a strategy for improving reliability. NASA, 1990.

[15]R. Campbell et al. Preliminary design of the redundant software experiment. NASA, 1985.

[16]T. Shimeall and N. Levenson. An Empirical Comparison of Software Fault Tolerance and Fault Elimination 1991, IEEE Trans. Software Eng. 17(2), pp. 173-182.

[17]J. Knight, and N. Leveson. An Experimental Evaluation of the Assumption of Independence in Multiversion Programming. 1986, IEEE Trans. Software Eng.

[18]S. Brillant, J. C. Knight, and N. Levenson. Analysis of Faults in an N-Version Software Experiment. 1990, IEEE Transactions on Software Engineering (TSE), 16(2), pp. 238-247.

[19]P. Ammann, and J. C. Knight. Data Diversity: An Approach to Software Fault Tolerance. 1988, IEEE Trans. Computers, pp. 418--425.

[20]M. R. Lyu and Y. He. Improving the N-Version Programming Process Through the Evolution of a Design Paradigm. IEEE Transactions on Reliability. 1993, Vol. 42, 2, pp. 179-189.

[21]L. Gmeiner, L. U. Voges Software diversity in reactor protection systems: an experiment. In Proceedings of the IFAC Workshop SAFECOMP 1979.

[22]A. Avizienis, M. R. Lyu and W. Schutz. In Search Of Effective Diversity: A Six-Language Study Of Fault-Tolerant Flight Control Software. Tokyo, Japan. Proceedings of the 18th International Symposium on Fault-Tolerant Computing (FTCS-18) 1998. pp. 15-22.

[23]M. R. Lyu, and A. Avizienis. Assuring Design Diversity in N-Version Software: A Design Paradigm for N-Version Programming. In Proceedings 2nd IEEE International Working Conference on Dependable Computing for Critical Applications, Tucson, Arizona, February 18-20 1991, pp. 89-98.

[24]J. M.Adams, and A. Taha. An experiment in software redundancy with diverse methodologies. In Proceedings of the Twenty-Fifth Hawaii International Conference on System Sciences. .Kauai, HI, USA pp. 83-90.

[25]A. Avizienis. Design diversity: an approach to fault tolerance of design. AFIPS Press, 1984. In Proceedings if the AFIPS National Computer Conference. Las Vegas, Nevada, California pp. 163-171.

[26]A. Avizienis and J. P. L. Kelly. A specification-oriented multi-version software experiment. In Proceedings of the Thirteenth International Symposium on Fault Tolerant Computing (FTCS 13) Milan , 1983.

[27]P. Bishop et al. PODS—A project on diverse software.. 1986, IEEE Trans. Softw. Eng.12(9), pp. 929--940.

[28]M. R. Lyu, J.-H. Chen, and A. Avizienis. Software Diversity Metrics and Measurements. In proceedings of the Sixteenth Annual International Computer Software and Applications Conference (COMPSAC '92), Chigaco,. IL USA. 1992. pp. 69-78.