| Revision as of 10:51, 26 November 2018 editZazpot (talk | contribs)Extended confirmed users, IP block exemptions, Rollbackers11,461 editsm Wikilink David A. Huffman← Previous edit | Revision as of 23:55, 13 December 2018 edit undoBloo Baroo (talk | contribs)4 editsm ←Replaced content with '{{DEFAULTSORT:Race condition}} Category:Anti-patterns Category:Computer security exploits Category:Concurrency (computer science) Category:Dist...'Tags: Replaced blanking Visual editNext edit → | ||
| Line 1: | Line 1: | ||
| {{Refimprove|date=July 2010}} | |||
| ]s of the logic elements. When the input value ''A'' changes from low to high, the circuit outputs a short spike of duration (∆''t''<sub>1</sub> + ∆''t''<sub>2</sub>) − ∆''t''<sub>2</sub> = ∆''t''<sub>1</sub>.]] | |||
| A '''race condition''' or '''race hazard''' is the behavior of an ], ], or other ] where the output is dependent on the sequence or timing of other uncontrollable events. It becomes a ] when events do not happen in the order the programmer intended. | |||
| The term '''race condition''' was already in use by 1954, for example in ]'s doctoral thesis "The synthesis of sequential switching circuits". <ref>Huffman, David A. "The synthesis of sequential switching circuits." (1954).</ref> | |||
| Race conditions can occur especially in ], ] or ] software programs. | |||
| ==Electronics== | |||
| A typical example of a race condition may occur when a ] combines signals that have traveled along different paths from the same source. The inputs to the gate can change at slightly different times in response to a change in the source signal. The output may, for a brief period, change to an unwanted state before settling back to the designed state. Certain systems can tolerate such ]es but if this output functions as a ] for further systems that contain memory, for example, the system can rapidly depart from its designed behaviour (in effect, the temporary glitch becomes a permanent glitch). | |||
| Consider, for example, a two-input ] fed with a logic signal A on one input and its negation, NOT A, on another input. In theory the output (A AND NOT A) should never be true. If, however, changes in the value of A take longer to propagate to the second input than the first when A changes from false to true then a brief period will ensue during which both inputs are true, and so the gate's output will also be true.<ref>{{cite journal |first=S.H. |last=Unger |title=Hazards, Critical Races, and Metastability |journal=IEEE Transactions on Computers |volume=44 |issue=6 |pages=754–768 |date=June 1995 |doi=10.1109/12.391185 |url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=391185}}</ref> | |||
| Design techniques such as ]s encourage designers to recognize and eliminate race conditions before they cause problems. Often ] can be added to eliminate some kinds of races. | |||
| As well as these problems, some logic elements can enter ], which create further problems for circuit designers. | |||
| ===Critical and non-critical forms=== | |||
| A ''critical race condition'' occurs when the order in which internal variables are changed determines the eventual state that the ] will end up in. | |||
| A ''non-critical race condition'' occurs when the order in which internal variables are changed does not determine the eventual state that the state machine will end up in. | |||
| ===Static, dynamic, and essential forms=== | |||
| A ''static race condition'' occurs when a signal and its complement are combined together. | |||
| A ''dynamic race condition'' occurs when it results in multiple transitions when only one is intended. They are due to interaction between gates. It can be eliminated by using no more than two levels of gating. | |||
| An ''essential race condition'' occurs when an input has two transitions in less than the total feedback propagation time. Sometimes they are cured using inductive ] elements to effectively increase the time duration of an input signal. | |||
| ==Software== | |||
| Race conditions arise in software when an application depends on the sequence or timing of ] or ] for it to operate properly. As with electronics, there are critical race conditions that result in invalid execution and ]. Critical race conditions often happen when the processes or threads depend on some shared state. Operations upon shared states are ]s that must be ]. Failure to obey this rule opens up the possibility of corrupting the shared state. | |||
| The ] defined in the ] and ] standards uses the term "data race" for a race condition caused by potentially concurrent operations on a shared memory location, of which at least one is a write. A C or C++ program containing a data race has ].<ref>{{cite web|url=http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=57853 |title=ISO/IEC 9899:2011 - Information technology - Programming languages - C |publisher=Iso.org |date= |accessdate=2018-01-30}}</ref><ref>{{cite web |authorlink= ISO |title= ISO/IEC 14882:2011 |publisher= ISO |date= 2 September 2011 |url= http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=50372 |accessdate= 3 September 2011}}</ref> | |||
| Race conditions have a reputation of being difficult to reproduce and debug, since the end result is ] and depends on the relative timing between interfering threads. Problems occurring in production systems can therefore disappear when running in debug mode, when additional logging is added, or when attaching a debugger, often referred to as a "]". It is therefore better to avoid race conditions by careful software design rather than attempting to fix them afterwards. | |||
| ===Example=== | |||
| As a simple example, let us assume that two threads want to increment the value of a global integer variable by one. Ideally, the following sequence of operations would take place: | |||
| {| class="wikitable" style="text-align: center;" | |||
| |- | |||
| ! Thread 1 !! Thread 2 !! !! Integer value | |||
| |- | |||
| | || || || 0 | |||
| |- | |||
| | read value || || ← || 0 | |||
| |- | |||
| | style="background: wheat;" | increase value || || || 0 | |||
| |- | |||
| | write back || || → || 1 | |||
| |- | |||
| | || read value || ← || 1 | |||
| |- | |||
| | || style="background: wheat;" | increase value || || 1 | |||
| |- | |||
| | || write back || → || 2 | |||
| |} | |||
| In the case shown above, the final value is 2, as expected. However, if the two threads run simultaneously without locking or synchronization, the outcome of the operation could be wrong. The alternative sequence of operations below demonstrates this scenario: | |||
| {| class="wikitable" style="text-align: center;" | |||
| |- | |||
| ! Thread 1 !! Thread 2 !! !! Integer value | |||
| |- | |||
| | || || || 0 | |||
| |- | |||
| | read value || || ← || 0 | |||
| |- | |||
| | || read value || ← || 0 | |||
| |- | |||
| | style="background: wheat;" | increase value || || || 0 | |||
| |- | |||
| | || style="background: wheat;" | increase value || || 0 | |||
| |- | |||
| | write back || || → || 1 | |||
| |- | |||
| | || write back || → || 1 | |||
| |} | |||
| In this case, the final value is 1 instead of the expected result of 2. This occurs because here the increment operations are not ]. Mutually exclusive operations are those that cannot be interrupted while accessing some resource such as a memory location. | |||
| ===Computer security=== | |||
| Many software race conditions have associated ] implications. A race condition allows an attacker with access to a shared resource to cause other actors that utilize that resource to malfunction, resulting in effects including ]<ref name="CVE-2015-8461">{{cite web|url=https://kb.isc.org/article/AA-01319/0/CVE-2015-8461%3A-A-race-condition-when-handling-socket-errors-can-lead-to-an-assertion-failure-in-resolver.c.html|title=CVE-2015-8461: A race condition when handling socket errors can lead to an assertion failure in resolver.c|accessdate=5 June 2017|publisher=]}}</ref> and ].<ref name="CVE-2017-6512" /><ref name="lighttpd-issue-2724">{{cite web|url=https://redmine.lighttpd.net/issues/2724|publisher=]|accessdate=5 June 2017|title=security: stat cache *very large* race condition if caching when follow_symlink disabled}}</ref> | |||
| A specific kind of race condition involves checking for a predicate (e.g. for ]), then acting on the predicate, while the state can change between the ''time of check'' and the ''time of use''. When this kind of ] exists in security-sensitive code, a ] called a ] (''TOCTTOU'') bug is created. | |||
| Race conditions are also intentionally used to create ]s and ]s.{{Citation needed|date=February 2018}} PUFs can be created by designing circuit topologies with identical paths to a node and relying on manufacturing variations to randomly determine which paths will complete first. By measuring each manufactured circuit's specific set of race condition outcomes, a profile can be collected for each circuit and kept secret in order to later verify a circuit's identity. | |||
| ===File systems=== | |||
| Two or more programs may collide in their attempts to modify or access a file system, which can result in data corruption or privilege escalation.<ref name="CVE-2017-6512">{{cite web|url=https://rt.cpan.org/Public/Bug/Display.html?id=121951|accessdate=5 June 2017|title=Vulnerability in rmtree() and remove_tree(): CVE-2017-6512|publisher=]}}</ref> ] provides a commonly used solution. A more cumbersome remedy involves organizing the system in such a way that one unique process (running a ] or the like) has exclusive access to the file, and all other processes that need to access the data in that file do so only via interprocess communication with that one process. This requires synchronization at the process level. | |||
| A different form of race condition exists in file systems where unrelated programs may affect each other by suddenly using up available resources such as disk space, memory space, or processor cycles. Software not carefully designed to anticipate and handle this race situation may then become unpredictable. Such a risk may be overlooked for a long time in a system that seems very reliable. But eventually enough data may accumulate or enough other software may be added to critically destabilize many parts of a system. An example of this occurred with the near loss of the ] not long after landing. A solution is for software to request and reserve all the resources it will need before beginning a task; if this request fails then the task is postponed, avoiding the many points where failure could have occurred. Alternatively, each of those points can be equipped with error handling, or the success of the entire task can be verified afterwards, before continuing. A more common approach is to simply verify that enough system resources are available before starting a task; however, this may not be adequate because in complex systems the actions of other running programs can be unpredictable. | |||
| ===Networking=== | |||
| In networking, consider a distributed chat network like ], where a user who starts a channel automatically acquires channel-operator privileges. If two users on different servers, on different ends of the same network, try to start the same-named channel at the same time, each user's respective server will grant channel-operator privileges to each user, since neither server will yet have received the other server's signal that it has allocated that channel. (This problem has been largely ] by various IRC server implementations.) | |||
| In this case of a race condition, the concept of the "]" covers the state of the network (what channels exist, as well as what users started them and therefore have what privileges), which each server can freely change as long as it signals the other servers on the network about the changes so that they can update their conception of the state of the network. However, the ] across the network makes possible the kind of race condition described. In this case, heading off race conditions by imposing a form of control over access to the shared resource—say, appointing one server to control who holds what privileges—would mean turning the distributed network into a centralized one (at least for that one part of the network operation). | |||
| Race conditions can also exist when a computer program is written with ], in which case the performance of the program can be dependent on the speed of the network link. | |||
| ===Life-critical systems=== | |||
| Software flaws in ]s can be disastrous. Race conditions were among the flaws in the ] ] machine, which led to the death of at least three patients and injuries to several more.<ref>{{cite web |url=http://courses.cs.vt.edu/~cs3604/lib/Therac_25/Therac_1.html |title=An Investigation of Therac-25 Accidents — I |publisher=Courses.cs.vt.edu |date= |accessdate=2011-09-19}}</ref> | |||
| Another example is the Energy Management System provided by ] and used by ]-based ] (among other power facilities). A race condition existed in the alarm subsystem; when three sagging power lines were tripped simultaneously, the condition prevented alerts from being raised to the monitoring technicians, delaying their awareness of the problem. This software flaw eventually led to the ].<ref>{{cite web |author=Kevin Poulsen |url=http://www.securityfocus.com/news/8412 |title=Tracking the blackout bug |publisher=Securityfocus.com |date=2004-04-07 |accessdate=2011-09-19}}</ref> GE Energy later developed a software patch to correct the previously undiscovered error. | |||
| ==Examples outside of computing== | |||
| ===Biology=== | |||
| {{Expand section|date=October 2016}} | |||
| Neuroscience is demonstrating that race conditions can occur in mammal (rat) brains as well.<ref>{{cite web |date=2013-08-03 |title=How Brains Race to Cancel Errant Movements |publisher=Discover Magazine blogs |url=https://blogs.discovermagazine.com/neuroskeptic/2013/08/03/the-race-to-stop-an-errant-movement/}}</ref><ref>{{cite journal |doi= 10.1038/nn.3456|title= Canceling actions involves a race between basal ganglia pathways|year= 2013|last1= Schmidt|first1= Robert|last2= Leventhal|first2= Daniel K|last3= Mallet|first3= Nicolas|last4= Chen|first4= Fujun|last5= Berke|first5= Joshua D|journal= Nature Neuroscience|volume= 16|issue= 8|pages= 1118–24|pmid= 23852117|pmc= 3733500}}</ref> | |||
| ==Tools== | |||
| Many software tools exist to help detect race conditions in software. They can be largely categorized into two groups: ] tools and ] tools. | |||
| Thread Safety Analysis is a static analysis tool for annotation-based intra-procedural static analysis, originally implemented as a branch of gcc, and now reimplemented in ], supporting PThreads.<ref>{{cite web |title=Thread Safety Analysis|url=http://clang.llvm.org/docs/ThreadSafetyAnalysis.html}}</ref>{{Primary source inline|date=December 2016}} | |||
| Dynamic analysis tools include: ], a memory and thread checking and debugging tool to increase the reliability, security, and accuracy of C/C++ and Fortran applications; ], a sampling based, SIMD vectorization optimization and shared memory threading assistance tool for C, C++, C#, and Fortran software developers and architects; ThreadSanitizer, which uses binary (]-based) or source, ]-based instrumentation, and supports PThreads);<ref>{{cite web |title=THREADSANITIZER|url=http://clang.llvm.org/docs/ThreadSanitizer.html}}</ref>{{Primary source inline|date=December 2016}} and Helgrind, a ] tool for detecting synchronisation errors in C, C++ and Fortran programs that use the POSIX pthreads threading primitives.<ref>{{cite web |title=Helgrind: a thread error detector|url=http://valgrind.org/docs/manual/hg-manual.html}}</ref>{{Primary source inline|date=December 2016}} | |||
| ==See also== | |||
| {{Portal|Software testing}} | |||
| * ] | |||
| * ] | |||
| * ] | |||
| * ] (near-duplicate article) | |||
| * ] | |||
| * ] | |||
| * ] | |||
| * ] | |||
| ==References== | |||
| {{Reflist}} | |||
| ==External links== | |||
| * {{cite journal |first1=G.M. |last1=Karam |first2=R.J.A. |last2=Buhr |title=Starvation and Critical Race Analyzers for Ada |journal=] |volume=16 |issue=8 |pages=829–843 |date=August 1990 |doi=10.1109/32.57622 |url=http://doi.ieeecomputersociety.org/10.1109/32.57622}} | |||
| * {{cite book |last1=Fuhrer |first1=R.M. |last2=Lin |first2=B. |last3=Nowick |first3=S.M. |author3-link=Steven M. Nowick |chapter=Algorithms for the optimal state assignment of asynchronous state machines |chapterurl=http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=515611 |title=Advanced Research in VLSI, 1995. Proceedings., 16th Conference on |date=March 1995 |isbn=0-8186-7047-9 |pages=59–75 |doi=10.1109/ARVLSI.1995.515611}} | |||
| * Paper "" by ], ], ], and ] | |||
| * {{cite web |first=David A. |last=Wheeler |title=Secure programmer: Prevent race conditions—Resource contention can be used against you |date=7 October 2004 |work=IBM developerWorks |url=http://www-128.ibm.com/developerworks/linux/library/l-sprace.html |archive-date= Nov 14, 2013 |archive-url= http://www.ida.liu.se/~TDDC90/literature/papers/SP-race-conditions.pdf |format= PDF}} | |||
| * Chapter "" (Secure Programming for Linux and Unix HOWTO) | |||
| * , with sample source code and comparison to C code, by Chiral Software | |||
| * {{cite web |first=Andrey |last=Karpov |title=Interview with Dmitriy Vyukov — the author of Relacy Race Detector (RRD) |date=11 April 2009 |work=Intel Software Library Articles |url=http://software.intel.com/en-us/articles/interview-with-dmitriy-vyukov-the-author-of-relacy-race-detector-rrd/}} | |||
| * | |||
| {{Concurrent computing}} | |||
| {{DEFAULTSORT:Race condition}} | {{DEFAULTSORT:Race condition}} | ||
| ] | ] | ||
| Line 154: | Line 8: | ||
| ] | ] | ||
| ] | ] | ||
| It makes you stupid. Example Race Grinder Born 2006 December 8th. He is very stupid and idiotic. | |||
Revision as of 23:55, 13 December 2018
It makes you stupid. Example Race Grinder Born 2006 December 8th. He is very stupid and idiotic.
Categories: