Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
N-version programming
open-in-new
<h2 id="nvp-approach">NVP approach</h2> <p>The general steps of <i>N</i>-version programming are: </p> <ol><li>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.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a></li> <li>From the specifications, two or more versions of the program are independently developed, each by a group that does not interact with the others.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> The implementations of these functionally equivalent programs use different algorithms and programming languages.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> At various points of the program, special mechanisms are built into the software which allow the program to be governed by the <i>N</i>-version execution environment (NVX).<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> These special mechanisms include: comparison vectors (c-vectors, a data structure representing the program's state), comparison status indicators (cs-indicators), and synchronization mechanisms.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> The resulting programs are called <i>N</i>-version software (NVS).<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li>Some <i>N</i>-version execution environment (NVX) is developed which runs the <i>N</i>-version software and makes final decisions of the <i>N</i>-version programs as a whole given the output of each individual <i>N</i>-version program.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> 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.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li></ol> <h2 id="criticisms">Criticisms</h2> <ul><li>Researchers have argued that different programming teams can make similar mistakes.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> In 1986, Knight & <a href="/facts/Nancy_Leveson/kPPvN46W">Leveson</a> conducted an experiment to evaluate the assumption of independence in NVP, they found that the assumption of independence of failures in <i>N</i>-version programs failed statistically.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a><a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a><a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a></li> <li>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 <i>N</i>-version program.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> In theory, output from multiple independent versions is more likely to be correct than output from a single version.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> However, there is debate whether or not the improvements of <i>N</i>-version development is enough to warrant the time, additional requirements, and costs of using the NVP method.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> In particular, under certain models of reliability and design effort, it has been shown that improvements due to using NVP are less than if all of the effort was concentrated on improving the reliability of a single version.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a></li></ul> <ul><li>“There has been considerable debate as to realizing the full potential from n-version programming as it makes the assumption that the independence will lead to statistically independent mistakes. Evidence has shown that this premise may be faulty [12].” <a href="http://www.faa.gov/aircraft/air_cert/design_approvals/air_software/media/AR-01-26_COTS.pdf">[1]</a></li></ul> <h2 id="applications">Applications</h2> <p><i>N</i>-version programming has been applied to software in switching trains, performing flight control computations on modern airliners, <a href="/facts/Electronic_voting/jsI9Ngwr">electronic voting</a> (the SAVE System), and the detection of <a href="/facts/Zero-day_exploit/B1jJkD0C">zero-day exploits</a>, among other uses.<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a><a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a><a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Redundancy_(engineering)/odqzTmIo">Redundancy (engineering)</a></li> <li><a href="/facts/Triple_modular_redundancy/QzscWD2F">Triple modular redundancy</a></li> <li><a href="/facts/Data_redundancy/k8SCyw0J">Data redundancy</a></li> <li><a href="/facts/Fault_tolerant_design/rasrYlJk">Fault tolerant design</a></li> <li><a href="/facts/Reliability_engineering/cd6AS5w3">Reliability engineering</a></li> <li><a href="/facts/Safety_engineering/ywUBoqda">Safety engineering</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://web.archive.org/web/20080828060019/http://www.rkbexplorer.com/explorer/#display=mechanism%2D{http://resex.rkbexplorer.com/id/resilience-mechanism-e679bd05}">N-version programming in the RKBExplorer</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation, Liming Chen; Avizienis, A., Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'., Twenty-Fifth International Symposium on, Vol., Iss., 27-30 Jun 1995, Pages:113- <a href="https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621" target="_blank">https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation, Liming Chen; Avizienis, A., Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'., Twenty-Fifth International Symposium on, Vol., Iss., 27-30 Jun 1995, Pages:113- <a href="https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621" target="_blank">https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>A.A. Avizienis, “The Methodology of N-version Programming” Archived 2005-11-03 at the Wayback Machine, Software Fault Tolerance, edited by M. Lyu, John Wiley & Sons, 1995. <a href="http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146" target="_blank">http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation, Liming Chen; Avizienis, A., Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'., Twenty-Fifth International Symposium on, Vol., Iss., 27-30 Jun 1995, Pages:113- <a href="https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621" target="_blank">https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation, Liming Chen; Avizienis, A., Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'., Twenty-Fifth International Symposium on, Vol., Iss., 27-30 Jun 1995, Pages:113- <a href="https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621" target="_blank">https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>A.A. Avizienis, “The Methodology of N-version Programming” Archived 2005-11-03 at the Wayback Machine, Software Fault Tolerance, edited by M. Lyu, John Wiley & Sons, 1995. <a href="http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146" target="_blank">http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation, Liming Chen; Avizienis, A., Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'., Twenty-Fifth International Symposium on, Vol., Iss., 27-30 Jun 1995, Pages:113- <a href="https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621" target="_blank">https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation, Liming Chen; Avizienis, A., Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'., Twenty-Fifth International Symposium on, Vol., Iss., 27-30 Jun 1995, Pages:113- <a href="https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621" target="_blank">https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>A.A. Avizienis, “The Methodology of N-version Programming” Archived 2005-11-03 at the Wayback Machine, Software Fault Tolerance, edited by M. Lyu, John Wiley & Sons, 1995. <a href="http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146" target="_blank">http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation, Liming Chen; Avizienis, A., Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'., Twenty-Fifth International Symposium on, Vol., Iss., 27-30 Jun 1995, Pages:113- <a href="https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621" target="_blank">https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=532621</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>A.A. Avizienis, “The Methodology of N-version Programming” Archived 2005-11-03 at the Wayback Machine, Software Fault Tolerance, edited by M. Lyu, John Wiley & Sons, 1995. <a href="http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146" target="_blank">http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>A.A. Avizienis, “The Methodology of N-version Programming” Archived 2005-11-03 at the Wayback Machine, Software Fault Tolerance, edited by M. Lyu, John Wiley & Sons, 1995. <a href="http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146" target="_blank">http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Liburd, Soyini. An N-version electronic voting system (Thesis). Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science, 2004. <a href="http://hdl.handle.net/1721.1/28441" target="_blank">http://hdl.handle.net/1721.1/28441</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Lajos Nagy, Richard Ford, and William Allen. N-Version Programming for the Detection of Zero-day Exploits. The 2006 IEEE Topical Conference on Cybersecurity, Daytona Beach, Florida, April 2006. <a href="https://cs.fit.edu/Projects/tech_reports/cs-2006-04.pdf" target="_blank">https://cs.fit.edu/Projects/tech_reports/cs-2006-04.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Lajos Nagy, Richard Ford, and William Allen. N-Version Programming for the Detection of Zero-day Exploits. The 2006 IEEE Topical Conference on Cybersecurity, Daytona Beach, Florida, April 2006. <a href="https://cs.fit.edu/Projects/tech_reports/cs-2006-04.pdf" target="_blank">https://cs.fit.edu/Projects/tech_reports/cs-2006-04.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Knight, J. C. and Leveson, N. G. 1986. An experimental evaluation of the assumption of independence in multiversion programming. IEEE Trans. Softw. Eng. 12, 1 (Jan. 1986), 96-109. <a href="http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=10688#" target="_blank">http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=10688#</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Knight, J. C. and Leveson, N. G. 1990. A reply to the criticisms of the Knight & Leveson experiment. SIGSOFT Softw. Eng. Notes 15, 1 (Jan. 1990), 24-35. <a href="http://doi.acm.org/10.1145/382294.382710" target="_blank">http://doi.acm.org/10.1145/382294.382710</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Liburd, Soyini. An N-version electronic voting system (Thesis). Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science, 2004. <a href="http://hdl.handle.net/1721.1/28441" target="_blank">http://hdl.handle.net/1721.1/28441</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Liburd, Soyini. An N-version electronic voting system (Thesis). Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science, 2004. <a href="http://hdl.handle.net/1721.1/28441" target="_blank">http://hdl.handle.net/1721.1/28441</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Liburd, Soyini. An N-version electronic voting system (Thesis). Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science, 2004. <a href="http://hdl.handle.net/1721.1/28441" target="_blank">http://hdl.handle.net/1721.1/28441</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Sha, L. (July 2001). "Using simplicity to control complexity". IEEE Software. 18 (4): 20–28. doi:10.1109/MS.2001.936213. ISSN 1937-4194. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>A.A. Avizienis, “The Methodology of N-version Programming” Archived 2005-11-03 at the Wayback Machine, Software Fault Tolerance, edited by M. Lyu, John Wiley & Sons, 1995. <a href="http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146" target="_blank">http://se2c.uni.lu/tiki/se2c-bib_download.php?id=1146</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Liburd, Soyini. An N-version electronic voting system (Thesis). Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science, 2004. <a href="http://hdl.handle.net/1721.1/28441" target="_blank">http://hdl.handle.net/1721.1/28441</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Lajos Nagy, Richard Ford, and William Allen. N-Version Programming for the Detection of Zero-day Exploits. The 2006 IEEE Topical Conference on Cybersecurity, Daytona Beach, Florida, April 2006. <a href="https://cs.fit.edu/Projects/tech_reports/cs-2006-04.pdf" target="_blank">https://cs.fit.edu/Projects/tech_reports/cs-2006-04.pdf</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> </ol>