# On-the-Fly Repairing of Atomicity Violations in ARINC 653 Software
## 3 Related Work
### Avionics  
There are reports and research studies of concurrency errors occurred in airborne software. According to the report in the DoD JSSSEH [23], a race condition, which is one of the concurrency errors, occurred in the first shuttle flight and the 44 th flight of NASA's Advanced Fighter Technology Integration (AFTI) F16. All airborne software must comply with ARINC 653, the standard for airborne software. To prevent airborne software from crashing, ARINC 653 introduces health management systems (HMSs) for IMA (integrated modular avionics). The job of HMSs is to detect and repair faults in software. Regardless of this preventive structure, there are reports and research studies documenting concurrency errors in airborne software. However, it is not surprising, because all multi-threaded programs are inherent with concurrency errors. There are research studies focusing on repairing atomicity violations raised in ARINC 653-based airborne software [6; 16]. [PERSON] et al. [16] and [PERSON] et al. [6] experimentally proved that the atomicity-violation issue exists in ARINC 653-based software. The approach these works used to treat the faults are similar. They store the shared variable access information of each thread in a data structure called access history[5]. The atomicity violation is diagnosed by examining the access history to check if the shared variables of each thread can be parallelly executed and whether they are protected by a lock [4; 28]. To treat atomicity violations, [PERSON] et al. 's method [16] inserts a lock around a shared variable that is not protected by a lock. On the other hand, [PERSON] et al. 's method [6] delays the thread initiating an access to the shared variable. The access history used to check the parallelism is a set of data structures generally called label. The label stores parallelism and order relationship information for each access. The label can be expressed as \([\alpha,\ \beta]\). \(\alpha\) and \(\beta\) are any integers defined by the programmer to denote the start and the end of a thread, respectively. \(\alpha\) must always be less than \(\beta\) (\(\alpha<\beta\)). Here, we give an example to better understand how labeling works to identify concurrent access to shared variables. Let us assume that there are two threads, \(T_{i}\) and \(T_{j}\), branching from the main thread. The label of the main thread at the program startup time is [1, 100]. When the program creates two threads on the main thread, the label is split in half. Then, the label of \(thread1\) is set to [1, 50] and the label of \(thread2\) is set to [51, 100]. Next, we compare \([\alpha_{i},\beta_{i}]\) of \(T_{i}\) and \([\alpha_{j},\beta_{j}]\) of \(T_{j}\) to check if the two regions collide. The following rules identify the concurrent relationship between threads:  
* The two threads \(T_{i}\) and \(T_{j}\) are in a concurrent relationship if the regions are \(\alpha_{i}<\beta_{j}\) and \(\alpha_{j}>\beta_{i}\). * Otherwise, \(T_{i}\) and \(T_{j}\) are in a sequential relationship. The atomicity violation detection protocol guarantees to find at least one error if there are concurrency violations in a code. Every access event [label, Locks] pair is logged in the history and categorizes the access event. There are four types of access events, Read, Write, Critical Section (CS)-Read and CS-Write. Based on the diagnosis, we take actionsbased on a policy. When the read operation is detected, it checks for the write and CS-write operations in the history and whether they collide. We search for the Read, CS-read and CS-write operations to identify the atomicity violations of write operations. The labeling scheme needs to log every access event in the history. The time and space overheads of existing atomicity violation diagnosing schemes depend on the maximum parallelism \(T\) and the time and space complexity are \(O(T)\). Recent real-world programs are known to have millions of threads running at the same time [39, 40, 41] and navigation software of an aircraft has about a billion lines of code [42].