N-version programming
Encyclopedia
N-version programming also known as multiversion programming, is a method or process in software engineering
where multiple functionally equivalent programs are independently generated from the same initial specifications. The concept of N-version programming was introduced in 1977 by Liming Chen and Algirdas Avizienis with the central conjecture that the "independence of programming efforts will greatly reduce the probability of identical software faults occurring in two or more versions of the program". The aim of NVP is to improve the reliability of software operation by building in fault tolerance or redundancy
.
(the SAVE System), and the detection of zero-day exploits, among other uses.
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
where multiple functionally equivalent programs are independently generated from the same initial specifications. The concept of N-version programming was introduced in 1977 by Liming Chen and Algirdas Avizienis with the central conjecture that the "independence of programming efforts will greatly reduce the probability of identical software faults occurring in two or more versions of the program". The aim of NVP is to improve the reliability of software operation by building in fault tolerance or redundancy
Redundancy (engineering)
In engineering, redundancy is the duplication of critical components or functions of a system with the intention of increasing reliability of the system, usually in the case of a backup or fail-safe....
.
NVP approach
The general steps of N-version programming are:- An initial specification of the intended functionality of the software is developed. The specification should unambiguously define: functions, data formats (which include comparison vectors, c-vectors, and comparison status indicators, cs-indicators), cross-check points (cc-points), comparison algorithm, and responses to the comparison algorithm.
- From the specifications, two or more versions of the program are independently developed, each by a group that does not interact with the others. The implementations of these functionally equivalent programs use different algorithms and programming languages. At various points of the program, special mechanisms are built into the software which allow the program to be governed by the N-version execution environment (NVX). These special mechanisms include: comparison vectors (c-vectors, a data structure representing the program's state), comparison status indicators (cs-indicators), and synchronization mechanisms. The resulting programs are called N-version software (NVS).
- Some N-version execution environment (NVX) is developed which runs the N-version software and makes final decisions of the N-version programs as a whole given the output of each individual N-version program. The implementation of the decision algorithms can vary ranging from simple as accepting the most frequently occurring output (for instance, if a majority of versions agree on some output, then it is likely to be correct) to some more complex algorithm.
Criticisms
- Researchers have argued that different programming teams can make similar mistakes. In 1986, Knight & Leveson conducted an experiment to evaluate the assumption of independence in NVP, they found that the assumption of independence of failures in N-version programs failed statistically.
- The weakness of an NVP program lies in the decision algorithm. The question of correctness of an NVP program depends partially on the algorithm the NVX uses to determine what output is "correct" given the multitude of outputs by each individual N-version program. In theory, output from multiple independent versions is more likely to be correct than output from a single version. However, there is debate whether or not the improvements of N-version development is enough to warrant the time, additional requirements, and costs of using the NVP method.
Applications
N-version programming has been applied to software in switching trains, performing flight control computations on modern airliners, electronic votingElectronic voting
Electronic voting is a term encompassing several different types of voting, embracing both electronic means of casting a vote and electronic means of counting votes....
(the SAVE System), and the detection of zero-day exploits, among other uses.
See also
- Redundancy (engineering)Redundancy (engineering)In engineering, redundancy is the duplication of critical components or functions of a system with the intention of increasing reliability of the system, usually in the case of a backup or fail-safe....
- Triple modular redundancyTriple modular redundancyIn computing, triple modular redundancy is a fault tolerant form of N-modular redundancy, in which three systems perform a process and that result is processed by a voting system to produce a single output. If any one of the three systems fails, the other two systems can correct and mask the...
- Data redundancyData redundancyData redundancy occurs in database systems which have a field that is repeated in two or more tables. For instance, in case when customer data is duplicated and attached with each product bought then redundancy of data is a known source of inconsistency, since customer might appear with different...
- Fault tolerant design
- Reliability engineeringReliability engineeringReliability engineering is an engineering field, that deals with the study, evaluation, and life-cycle management of reliability: the ability of a system or component to perform its required functions under stated conditions for a specified period of time. It is often measured as a probability of...
- Safety engineeringSafety engineeringSafety engineering is an applied science strongly related to systems engineering / industrial engineering and the subset System Safety Engineering...