An Effective Method to Control Interrupt Handler for Data
Race Detection
Makoto Higashi

Tetsuo Yamamoto

Graduate School ofInformation Science andTechnology, Osaka University

College of Information Scienceand Engineering, Ritsumeikan
University

m-higasi@ist.osakau.ac.jp

tetsuo@cs.ritsumei.ac.jp

Yasuhiro Hayase,Takashi Ishio,
Katsuro Inoue
Graduate School ofInformation Science andTechnology, Osaka University{y-hayase, ishio,
inoue}@ist.osaka-u.ac.jp

ABSTRACT

1.

Embedded software frequently uses interrupts for timer or
I/O processing. If a memory area is used by both an interrupt handler and other routines at the same time, theembedded system has the potential to fail because of unexpected data in the memory. To detect the race conditions ofmemory, this paper proposes a method of interrupt testing
on a CPU emulator. The method consists of two features:
one is interrupt generation at the instruction points thatpossibly causes race conditions; the other is replacing input
value from external device to control interrupt handlers. Aninterrupt is generated just after the program reads or writes
data on memory for the purpose of covering all possibilityof sharing memory between the interrupt handler and otherroutines. Sequence of input value from the external device
is prepared by hand before program execution. We have applied our method to testing for a race condition of uClinux.
The experience of detecting race conditions has shown themechanism causes interrupts at necessary and suﬃcient timing compared with random interrupt testing. Also, it is easy
to substitute values in memory to detect race conditions.

Embedded software frequently uses interrupts for timer
or I/O processing. However, interrupts should be used andtested carefully since wrong use of interrupts causes a race
condition [12], i.e. the failure caused by inadequately controlled multiple accesses to shared memory[15]. Assume thata certain variable is changed by an interrupt handler just after a condition check for the variable. In such case, the statements after the condition check should not work correctly
since the precondition for the statements may be violated.
To detect the race conditions, static detection methods,
which are based on model checking[5, 8, 14], and dynamic
detection methods, which intentionally generate an interrupt for testing [16], are proposed. In this paper, we focusedon dynamic testing since the dynamic methods generate lessfalse-positive than the static methods.
In [16], Regehr proposed a dynamic detection method that
randomly causes interrupts while a program is running. Thismethod depends on duration of the random interrupt schedule. If the schedule is too sparse, there are only a little
detections of race conditions. If the schedule is too dense,
there are always multiple pending interrupts, and then noninterrupt routine cannot make progress. Therefore, it is important to consider adequate interrupt schedule.
At ﬁrst, we consider the timing in which interrupts occur.
To test all race conditions, it needs that an interrupt occurs
on all instruction points which access shared memory.
Moreover, it is necessary that appropriate value in memory or variable within interrupt handler to cause a race condition. If there is no execution path to access shared memory, there is no race condition.
In this paper, we propose a method of interrupt testing
to detect race conditions. The method comprises two mechanisms. One is that a mechanism to cause an interrupt at
all possible timing to cause race conditions. Another is thata mechanism to substitute appropriate value for a value inmemory. The former one is to provide a function that aninterrupt automatically occurs just after instructions whichaccess shared memory. The latter one is to provide a function that automatically change the value speciﬁed by a user.
The user speciﬁes memory address and new value in thememory before a program runs.
These two mechanisms are implemented on a CPU emulator to test for race conditions in an early phase of thedevelopment of embedded systems. In development of em-

Categories and Subject Descriptors
C.3 [Special-purpose and application-basedsystems]:
Real-time and embedded systems; D.2.5 [Software Engineering]: Testing and debugging.Testing tools

General Terms
RELIABILITY

Keywords
race condition, embedded systems, fault injection, interruptdriven software

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
AST’10 , May 2-8 2010, Cape Town, South Africa
Copyright 2010 ACM 978-1-60558-970-1/10/05 ...$10.00.

INTRODUCTION

and the program may not work correctly if an interruption
handler asynchronously works and modiﬁes the variable.
In this paper, a race condition is deﬁned as the failurethat is caused by interruption handler that modiﬁes a certain
variable between a reference or modiﬁcation to the variable
and a later reference to the variable. Our method is designed
to detect this kind of race condition.

1: #define MAX 16
2: unsigned int index = 0;
3: int array[MAX];
4: void array_print(void);
5: {6:
if(index < MAX)
7:
printf(“%d¥n”, array[index]);
8: }9:
10: void interrupt_handler(DEVICE *dev){
11:
index+=get_int(dev);
12: }

3.

Figure 1: Sample source code that potentially causes
race condition
Call interrupt_handler(dev)Call array_printer(void)yes
index < MAX
Interruption

index+=int_getter(dev)Returnno
Print Array[index]

ReturnFigure 2: Flowchart of Figure 1 with an interrupt
just after the branchbedded systems, software is often executed and tested ona CPU emulator since hardware and software for the system are developed in parallel. The mechanisms on a CPU
emulator enable eﬃcient test for race conditions before thehardware is ﬁnished.
The rest of this paper is organized as follows: Section
2 clariﬁes a race condition that this paper targets. Section 3 describes details of our method, which test for race
conditions using the mechanism to cause interrupts and themechanism to substitute values in memory. Section 4 shows
implementation of our method on a CPU emulator. Section
5 evaluates our method through an experiment. Section 6 introduces related work on generating interrupts and changing
values. Concluding remark and future work are presented
in Section 7.

2. DEFINITION OF RACE CONDITIONIn this section, we provide a motivating example, explaining the deﬁnition of race conditions in this paper.
Figure 1 shows an example source code that may causes
a race condition. Procedure print_array checks that index
is less than MAX, then print index-th element of array.
It apparently seems that print_array has no buﬀer-overrun problem since the function checks the index before it
accesses to the array. However, as shown in Figure 2, if
an interrupt occurred and interrupt_handler is called justafter the check of index, index in line 7 may have MAX ormore value.
As mentioned above, a program that is made without attention for an interrupt sometimes has an implicit assumption that a variable stores the same value when the variable
is accessed previously. Unfortunately, the assumption breaks

METHOD

This section proposes a method to test for race conditionseﬀectively. The method has two mechanisms. One is themechanism to cause interrupts and another is to substitutevalues.
As described in section 2, a race condition occurs if following conditions are met.
1. An interrupt handler is executed when the programis running on the point after an access to a certain
variable and before a read access to the variable.
2. The interrupt handler modiﬁes the variable in the execution.
Therefore, we need to treat two tasks in order to detecta race condition; to cause an interrupt between the former
access to the variable and the latter reference to the variable,
and to control the interrupt handler to access the variable.
Then, the mechanism to cause interrupts treats the former task, and the mechanism to substitute values treats thelatter task. Each mechanism runs independently and treats
the diﬀerent task, but both these mechanisms contribute to
the solution of the same problem. It is eﬃcient interruption
to test for race conditions.

3.1 Mechanism to cause interrupts
This section describes the mechanism to cause interrupts
on all point that possibly causes a race condition, i.e. after any access to certain memory area. The mechanism isimplemented as a part of memory-accessing instruction in a
CPU emulator. The mechanism proceeds in following steps
after all memory-access instructions are executed.
1. Checks whether the instruction access memory.
2. If step 1 is true, checks whether the program has justreturned from any interrupt handler.
3. If step 2 is false, checks whether the current status of
the execution matches the conditions in the conﬁguration ﬁle.
4. If step 3 is true, causes an interrupt according to the
conﬁguration ﬁle.
The step 3 is designed to avoid inﬁnite loop. If interrupts occurs just after returning from interrupt handlers every time, only the interrupt handler runs inﬁnitely. For thisreason, the mechanism doesn’t cause interrupt in such case.
Figure 3 shows the steps to check whether an interrupt
should be caused. Inputs to this mechanism are program
counter of a CPU emulator and a conﬁguration ﬁle. The
conﬁguration ﬁle consists of the following items.
kind of interrupt A kind of interrupt which this mechanism causes. An example of this kind is I/O device
number linked with the interrupt handler to test for arace condition.

access tomemory area
programLDR ADDR
ADD
MOV
・
・
・
・
・
・

CPU emulator

current
mechanism to cause interrupts
programcomparecountercurrent program counter
with the saved counter
result ofcomparison

interrupt

If the saved counter isdifferent fromthe current program counter,
cause an interrupt andsave program countersaved
countersaved counter

instruction whichreads memory
programaccess memory
with address

LDR ADDR
ADD
MOV

current
programcounter

・
・
・
・
・
・

specify causing
interrupts

send user
specified value

configuration file•kind of interrput•permission of nested interrupts

access memory
with address

mechanism to substitute inputs
check if the memory address which
the instruction reads
is mapped to external device
If memory address
the instruction reads
is mapped to external device,change the value

specify
substituting
inputsFigure 3: How to cause interrupts.

1. Checks whether the instruction is reading memory.
2. If step 1 is true, compares the program state to conditions in the conﬁguration ﬁle.
3. If step 2 matches, changes the value in the memory
according to the conﬁguration ﬁle.
Figure 4 shows the steps to substitute a value in a memoryarea.
Inputs of this mechanism are the memory address the instruction reads and a conﬁguration ﬁle. The conﬁgurationﬁle consists of the following items.
• memory address: An address which is mapped to external device.

4 5 6
7 8 9
* 0 #

configuration file・・・The program counter is used for determining whether the
program state is just return from an interrupt handler. Program counter is saved just before an interrupt is caused.
Then, the saved counter is compared with the current program counter when the mechanism checks to cause interrupt
or not. If the two counters are same, the mechanism determines that the program state is just return from the handler.

This mechanism is used for controlling execution path of
an interrupt handler by substituting an input value fromexternal device to user speciﬁed value. Since embedded
software uses memory-mapped I/O in interrupt handlers forcommunicating with external devices in most case, substituting input value is same as substituting values in a certain
memory area.
This mechanism functions on the place where instructions
read memory. This is the reason that we assume embedded
software on a processor using the memory-mapped I/O. On
the processor, a program gets input values from devices byreading memory.
The mechanism proceeds in following steps after all instructions are executed.

send aninput value

1 2 3

memory address A: 0x10000000
formula A: 0x2000
memory address B: 0x20000000
formula B: current input + 1
memory address C: 0x40000000
formula C: temp

permission of nested interrupt An option to select whether this mechanism causes an interrupt while the interrupt handler is executed.

3.2 Mechanism to substitute values

external device oran emulator of it

Figure 4: How to substitute a value.
• formula: An expression to calculate new value fromexisting value.
You can specify not only constant value, but also an expression using the current value and any other global variables in the expression. This expression makes variety of
execution path of interrupt handler possible.

4.

IMPLEMENTATION

To automate our method, we implemented a prototype
system of our approach on ARM subsystem of SkyEye[3]CPU emulator.

4.1 Mechanism to cause interrupts
We implemented functions to cause interrupts as follows.
• Function to cause interrupts: this is implemented in
C language. The function is called by six C functions
which deal with load instructions and by six C functions which deal with store instructions.
• Function to detect the return from interrupt handler:when an interrupt occurs, the function saves the valueof program counter. To compare current value of program counter with the saved value, we detect the state
just after the return from interrupt handler.
• Function to analyze the conﬁguration ﬁle: we implemented the function to parse the conﬁguration ﬁle byusing yacc and lex.In this conﬁguration ﬁle, the kindof interrupt consists of I/O device number linked with
the interrupt handler to test and whether an interrupt
is IRQ or FIQ in ARM architecture.

4.2 Mechanism to Substitute Values
We implemented functions to input new values as follows.
• Function to inject the new value: When load instructions read the value of devices from memory-mapped
I/O, we implemented the function which substituteuser speciﬁed value for the value of devices.
• Function to analyze the conﬁguration ﬁle: we implemented the function to parse the conﬁguration ﬁle byusing yacc and lex.
• Function to get the value of variables: we implemented
the function to get information of global variables byusing dwarf2[1] before running the program.

・・・

389: static _INLINE_ void transmit_chars(struct m68k_serial *info)
390: {
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:

if((info->xmit_cnt <= 0) || info->tty->stopped) {/* That's peculiar... TX ints off */uart->ustcnt &= ~USTCNT_TX_INTR_MASK;
goto clear_and_return;}/* Send char */uart->utx.b.txdata = info->xmit_buf[info->xmit_tail++];info->xmit_tail = info->xmit_tail & (SERIAL_XMIT_SIZE-1);
info->xmit_cnt--;・・・

423: }
・・・

428: void rs_interrupt(int irq, void *dev_id, struct pt_regs * regs)
429: {
・・・445: tx = uart->utx.w;
・・・

448: if (tx & UTX_TX_AVAIL)

transmit_chars(info);・・・

5. EXPERIMENT

453: }

This section describes a case study in applying our proposed method to test for race conditions for an open-source
software. The aim of this study is examine how much reduction of the cost to test for race conditions when a developer
doubts the possibility of a race condition. We test for a race
condition as a practical matter, and report the process todetect the race condition.

757: static void rs_flush_chars(struct tty_struct *tty)
758: {

5.1 Target of detection
We select a fault in uClinux version 2.4 as the detection
target of our method. The fault was ﬁxed in the revision
1.12 of /drivers/char/68328serial.c in the software. 1
Figure 5 shows an excerpt of the source code which has thefault. Function rs_flush_chars is a non-interrupt routine
and function rs_interrupt is an interrupt handler. These
functions are used by the driver of UART port to transmit characters through the port. Both of these functions
send one character obtain from the character queue, info>xmit_buf, when the following conditions are fulﬁlled.
In line 445–448 and 782, UART port is available for transmission, i.e. logical multiply of utx.w and UTX_TX_AVAIL is true.
In line 400 and 768, The queue stores one or more characters, i.e. info->xmit_cnt is greater than 0.
A race condition is exposed if the queue stores only one
character and the interrupt handler modiﬁes the queue justafter the conditional statement in line 768 branches to else
side. Especially, the condition in which the race condition occurs is that the conditional expression in line 768
is false and info->xmit_cnt is equal to 1, and utx.w &UTX_TX_AVAIL is true. Then last one character is removed
from the queue. However, the statements in line 786-789
read a character from the empty queue. Therefore, the program fails and a random character is transmitted.
In this experiment, we modiﬁed uClinux to run these functions on the emulator.
• uClinux is modiﬁed to call these functions on ARM architecture, since originally the functions are only calledon m68k architecture. The source code of the functions
is not modiﬁed.
1

http://cvs.uclinux.org/cgi-bin/cvsweb.cgi/
uClinux-2.4.x/drivers/char/68328serial.c.diff?
r2=1.12&r1=1.11&f=h

・
・
・

・
・
・

768: if (info->xmit_cnt <= 0 || tty->stopped || tty->hw_stopped ||769:!info->xmit_buf)
770:
return;・・・782: if (uart->utx.w & UTX_TX_AVAIL) {
・
・
・

786:
787:
788:
789:
790: }/* Send char */uart->utx.b.txdata = info->xmit_buf[info->xmit_tail++];info->xmit_tail = info->xmit_tail & (SERIAL_XMIT_SIZE-1);
info->xmit_cnt--;・・・

Figure 5:
Excerpt of the failure in uClinux2.4.x/drivers/char/68328serial.c rev 1.11
• uClinux is modiﬁed not to call function __delay, since
this function wastes much execution time. It is not related with both function rs_flush_chars and function
rs_interrupt, and the evaluation of this experimentdoes not need an exact execution time.
Also, in this experiment, we did not select the option explained in section 3.1 that chooses to cause interrupts while
the interrupt handler to test is being executed. This is because a race condition can be caused without multiple interrupts, and a large amount of multiple interrupts prevent a
non-interrupt routine from making progress.

5.2

Testing process

We report the process to detect the race condition we
described in the above. It must be noted that a developer
who tests for the race condition has following knowledge. He
or She:• Doubts the possibility to cause a race condition withinfunction rs_flush_chars.
• Assumes function rs_interrupt as the interrupt handler to cause the race condition in cooperation withfunction rs_flush_chars• Assumes variable info->xmit_cnt as a variable to cause the race condition.

He or she must proceed following procedures to test eﬀectively.
• Examines adequate number of data in info->xmit_buf
queue before calling function rs_flush_chars. The
number depends on the number of interrupts are caused by our method just before calling function rs_flush_chars and from 757 through 767 in Figure 5. Because the number of info->xmit_buf must be at least
one in the state the program executes line 768 in Figure 5 to cause the race condition. Also, the developerconsiders that an interrupt occurs just before calling
function rs_flush_chars and from line 757 through767. Therefore, the number of info->xmit_buf must
be calculated to use above information.
• Describes the number in the conﬁguration ﬁle.
Also, he or she must ﬁnd out following information thatis required in the conﬁguration ﬁle.
• Memory address of utx.w member in structure uartthat represents UART port: This address is required
to decide the value of uart->utx.w. There are two
ways to investigate the address. One is to check the
speciﬁcation of UART port. Another is to ﬁnd out theoperand of load instruction which reads the value ofuart->utx.w to use a debugger. In the latter way, themethod to ﬁnd out the load instruction is to search theaddress of all lines in source code by using dwarf2[1].
• A value of uart->utx.w to cause the race condition:
The value is decided to investigate the value of UTX_TX_AVAIL of line 445–448 and 782 in Figure 5.
• A kind of interrupt and interrupt number to call function rs_interrupt: These are decided to ﬁnd out theline of function rs_interrupt call instruction in theinterrupt vector of source code.

5.3 Result
We show the cost of testing for race conditions by theprocess we explained in section 5.2
It is needed to test more than six data about the valueof info->xmit_buf to detect the race condition. The reason is to cause the race condition before calling function
rs_flush_chars only when the number of info->xmit_buf
is from 6 through 10.
If the number is less than 6, our mechanism causes interrupts 5 times before executing line 768 in Figure 5. In suchcase, info->xmit_buf is empty at the execution of line 768.
As a result, lines 787–789 are not executed. On the contrary, if the number is more than 10, the number of info>xmit_buf is more than 1 at the execution of line 787–789.
As a result, there is no race condition.
A developer required writing 7 lines in the conﬁgurationﬁle to test for a race condition in this case. The amount of
the ﬁle is small. However, to get information to describe theﬁle, it took about 10 minutes to search variables in source
ﬁles of uClinux-2.4.x and dynamically ﬁnd out addresses ofvariables in uClinux-2.4.x executing on the CPU emulator.
Next, we measured CPU cycles from the start of the CPU
emulator through detecting the race condition. It took 72417488 cycles to execute uClinux-2.4.x on the CPU emulator
in applying our method. On the other hand, it took 4836078

cycles to normally execute uClinux-2.4.x on the CPU emulator. It requires time about 15 times to apply our method.
Other information is as follows.
• The number of interrupts: 1409375• The number of calling the interrupt handler: 390722• The total number of cycles took in the interrupt handler:69952632 (96% of all cycles)

5.4 Discussion
We argue the following points about the experience andthe results of it.
• diﬀerence from random interrupt testing• how to prepare values of variables• knowledge about target program

Difference from random interrupt testing.
The aim of our method is to improve random interrupt
testing(Regehr’s method) [16] as we explained in section 1.
There are two points to improve it, a timing of an interrupt
and behavior of an interrupt handler.
First, we argue the timing of an interrupt. In our method,
an interrupt occurs just after an instruction accesses memory. On the contrary, interrupts randomly occurs in Regehr’s
method. The timing of an interrupt between these methods
does not correspond. However, a user can set up the schedule of interrupts in Regehr’s method. If the schedule is too
dense, the timing of interrupts by Regehr’s method includes
the timing of interrupts by our method. However, we think
it is diﬃcult that our method and Regehr’s method correspond.
The reason is that Regehr’s method cannot detect nested
interrupt handler call. In our method, a user can select apermission of nested interrupts as we described in section
3.1. This option prevent over interrupt. On the other hand,
Regehr’s method cannot prevent multiple interrupts.
Next, we argue the behavior of an interrupt handler. Regehr’s method can only trigger interrupts. Our method can
not only trigger interrupts but also substitute the value ofvariables within the interrupt handler. Using this mechanism, a user can control execution path of the interrupt
handler. As a result, it is possible to try to test more caseto cause race conditions.
Given this mechanism, our method Regehr’s method are
diﬀerent kinds of testing. In our method a user have tounderstand the behavior of the program. On the other hand,a user does not have to understand it in Regehr’s method.
We consider the diﬀerence between our method and Regehr’s
method as the relation between white-box testing and blackbox testing.
It is useful to be able to change execution path of theinterrupt handler to detect race conditions. An interrupt
from external device occurs and reading and/or writing values from the device are a close relationship. Therefore, tochange the value from the device has an impact to the behavior of the interrupt handler.
However, a user needs to know information of the device
and values of it in advance. If there is no information, auser cannot specify the value. The diﬀerence between our1: unsigned int len = 0;
2: void str_cpy(char *buf, char *str);
3: {4:
len = strlen(str);5:
if((0 < len) && (len <= strlen(str)))6:
memcpy(buf,str,len+1);
7: }8:
9: void interrupt_handler(void){
10:
len++;
11: }method and Regehr’s method is small in such case. A future
work is to test by using as little information that a user needs
to describe as possible.
On the other hand, users of our approach have to determine which combinations of an interrupt handler and a noninterrupt routine should be tested. The following steps for
all interrupt handlers enumerate all the combinations that
potentially cause race condition.
1. Detect all variables to which an interrupt handler writes.
2. For each one of the variable, ﬁnd all routines that access the variable at least twice.

How to prepare values of variables.
Information of not only interrupts and input values fromdevices, but also values of variables in the program may berequired to detect race conditions as we described in section
5.3. We discuss how to prepare the information.
In section 5.3, we substituted values of variables by modifying the source code of uClinux to inject the information.
Then, we wasted much compile time because uClinux-2.4.x
is a large scale of software, As the result, the testing for race
conditions was ineﬃcient.
It is realized to use the mechanism to substitute values inmemory to easily inject the information. The aim of themechanism is to substitute appropriate value for a value
from extern device. You specify memory-mapped I/O address of the device to use the mechanism. If you specify
the address of the variable, you can change the value of avariable in source code.
It is generally diﬃcult to investigate the address of variables. However, it is easy to know the name of the variable.
We have to extend the format of a conﬁguration ﬁle to beable to write the name instead of the address.

Knowledge about target program.
In section 5.2, we assumed a user knows non-interrupt
routine, interrupt handler and shared memory of target program that test for race conditions in advance. We argue theknowledge of a user to test for race conditions.
First, we assume that a user has little knowledge about
target program, but enough about external device. A user
can test only when race conditions occur whenever an interrupt occurs. Because only knowledge of a kind of device is
suﬃcient information to cause interrupts exhaustively.
Next, we assume that the user has knowledge about values
from an external device. The user may be able to select thevalue to execute an instruction that causes race conditions.
Executing the path needs to examine source code in a precise
sense. However, it is possible to detect race conditions only
to create values according to the speciﬁcation of the external
device.
To detect all race conditions is needed to create adequate
test cases. It is important that combination non-interrupt
routine with interrupt handler to cause a race condition.
Therefore, to cause all race conditions requires checking all
execution paths of not only interrupt handlers but also noninterrupt routines. Also, there is a particular kind of caseas section 5.3. To detect a race condition is to make only 6
sets of test cases in such case.
However, it is impossible to detect race conditions in the

Figure 6: Sample source code that causes race condition when interrupt occurs only once
following conditions. As a future work, we are trying todetect these race conditions.
• A race condition that depends on the number of interrupts or a combination of interrupts: For example,
when an interrupt is not caused just after ﬁrst load instruction and is caused just after next load instruction,a race condition occurs. Our method cannot detect therace condition. For example, in Figure 6, race condition occurs when an interrupt does not occur in line 4
and occurs in line 5.
• A race condition that depends on a combination ofmultiple kinds of interrupts: For example, when atﬁrst a timer interrupt is caused, next, UART interrupt
is caused, a race condition occurs. Our method deals
with only one kind of interrupt at a time.
If a user needs to test multiple interrupt handlers, the userneeds to apply our method with respect to each interrupt.
In such case, the number of execution of the program totest is multiplying the number of interrupt handlers by the
number of test case. Test case means a value from external
device to cause a race condition.

6.

RELATED WORK

Testing embedded software with hardware interrupt suchas device drivers is challenging because developers must investigate possible race conditions on a large number of control-ﬂow paths caused by interrupt.
Regehr proposed a method to test interrupt-driven embedded software by causing interrupts at random [16]. Our
approach uses a CPU emulator to exhaustively cause interrupts to cover possible control-ﬂow paths.
Although our research focuses on interrupt-driven embedded software, detecting a race condition is also an important
issue for developing multi-threaded programs. Entropy Injection[4] inserts artiﬁcial delays between data access operations to provoke race conditions in multi-threaded programs.
This approach increases the probability of race conditions
during an automated test session. Our approach controls theinterrupt mechanism of a CPU emulator to directly cause
race conditions; our approach allows developers to test anddebug a particular execution scenario of a program undertest.
Joshi et al. [11] proposes a method extracting a cyclic
lock dependence chain from an execution trace of a multithreaded program; their customized thread scheduler suspends threads that acquire locks in the cycle to create adeadlock with high probability. Our tool controls schedule ofinterrupts instead of threads to create data race conditions.
A diﬀerence between interrupt-driven embedded softwareand multi-threaded program is that an interrupt handler
often reads and writes shared variables and most of them
do not cause any problem. Data race conditions of interest
to us are caused by statements executed under assumptions
on values stored in variables that might be updated by aninterrupt handler.
There are also several dynamic analysis methods [9, 13];
however, these methods cannot be applied to interrupt-driven software. Regehr and Cooprider have proposed an interesting approach that translates source code of an interruptdriven program into a multi-threaded program that emulates
the original behavior [17]. We did not take this approach because we would like to test an interrupt-driven program on a
CPU emulator to analyze the actual behavior of the program
when a race condition occurs.
Our approach monitors a program execution, artiﬁciallycauses interrupts and generates input data from external
devices when the program accesses a particular memory address. To implement our method, we have employed a fault
injection mechanism. Although the main goal of fault injection research is to decide input values that likely cause failures of systems to test and evaluate a program [10], a fault
injection approach that dynamically substitutes a modiﬁed
data for an actual data with a modiﬁed data is well suited
for us to generate input data to analyze a race condition.
Xception[6] is a tool to emulate hardware transient faults
in functional units of a processor. For example, Xception can
corrupt an operand loaded from a speciﬁed address with several bit level operations: stuck-at-zero, stuck-at-one, bit ﬂip,
and bridging. Our method implements a similar mechanism
but substitutes an arbitrary value for an input value speciﬁed by a developer so that developers can test a particular
execution scenario.
Qinject[7] is a CPU emulator with another fault injection
approach. Qinject generates input values when a speciﬁed
instruction is executed in order to emulate a defective code,
while our method generates input values when instructions
access a speciﬁed memory location in order to emulate amemory mapped I/O.
To test and debug a program, gdb, the GNU Project Debugger [2], also can substitute a test input for an actual
input when an instruction loaded the input from a speciﬁed
memory address. However, gdb cannot directly control interrupt. We have implemented our tool on a CPU emulator
instead of a combination of a regular CPU emulator and gdb
because of the ease of implementation.

7. CONCLUSIONSIn this paper, we have implemented two mechanisms toa CPU emulator, which can cause interrupts after memory
accesses and substitute input values from external devices
that interrupt handler uses to test for race conditions inembedded software. We have applied our method to testing
for a race condition of uClinux. The experience of detecting
race conditions has showed the mechanism causes interrupts
at necessary and suﬃcient timing compared with random
interrupt testing. Also, it is easy to substitute values inmemory to detect race conditions.
Future works will focus on substituting value of variables
in source code, causing more appropriate timing of inter-rupts and dealing with multiple kinds of interrupts.

8.

ACKNOWLEDGMENTS

This research was supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientiﬁc Research (A)(No.21240002). This research was also supported by Ministry of Education, Science, Sports and Culture, Grant-inAid for Young Scientists (B) (No.21700031).

9.

REFERENCES[1] Dwarf home. http://dwarfstd.org/.
[2] Gdb: The GNU project debugger.
http://www.gnu.org/software/gdb/.
[3] SkyEye - open source simulator.
http://www.skyeye.org/.
[4] L. Albertsson. Entropy injection. SICS Technical
Report, T2007(2), February 2007.
[5] T. Ball, E. Bounimova, B. Cook, V. Levin,
J. Lichtenberg, C. McGarvey, B. Ondrusek, S. K.
Rajamani, and A. Ustuner. Thorough static analysis
of device drivers. ACM SIGOPS Operating Systems
Review, 44(4):73–85, October 2006.
[6] J. Carreira, H. Madeira, and J. G. Silva. Xception: A
technique for the experimental evaluation of
dependability in modern computers. IEEE
Transactions on Software Engineering, 24(2):125–136,
February 1998.
[7] F. M. David, E. M. Chan, J. C. Carlyle, and R. H.
Campbell. Qinject: A virtual machine based fault
injection framework. International Conference on
Architectural Support for Programming Languages
and Operating Systems (Poster Presentation), March
2008.
[8] D. Engler and K. Ashcraft. Racerx: Eﬀective, static
detection of race conditions and deadlocks. ACM
SIGOPS Operating Systems Review, 37(5):237–252,
December 2003.
[9] C. Flanagan and S. N. Freund. Fasttrack: eﬃcient andprecise dynamic race detection. In Proceedings of the2009 ACM SIGPLAN Conference on Programming
Language Design and Implementation, pages 121–133,
June 2009.
[10] M.-C. Hsueh, T. K. Tsai, and R. K. Iyer. Fault
injection techniques and tools. IEEE Computer,30(4):75–82, April 1997.
[11] P. Joshi, C.-S. Park, K. Sen, and M. Naik. A
randomized dynamic program analysis technique fordetecting real deadlocks. In Proceedings of the 2009
ACM SIGPLAN Conference on Programming
Language Design and Implementation, pages 110–120,
June 2009.
[12] N. G. Leveson. An investigation of the therac-25
accidents. IEEE Computer, 26(7):18–41, July 1993.
[13] D. Marino, M. Musuvathi, and S. Narayanasamy.
Literace: eﬀective sampling for lightweight data-race
detection. In Proceedings of the 2009 ACM SIGPLAN
Conference on Programming Language Design and
Implementation, pages 134–143, June 2009.
[14] E. G. Mercer and M. D. Jones. Model checking
machine code with the GNU debugger. In 12th
International SPIN Workshop, pages 251–265, August2005.

[15] R. H. B. Netzer and B. P. Miller. What are race
conditions?: Some issues and formalizations. ACM
Letters on Programming Languages and Systems,
1(1):74–88, March 1992.
[16] J. Regehr. Random testing of interrupt-driven
software. In EMSOFT ’05: Proceedings of the 5th
ACM international conference on Embedded software,pages 290–298, September 2005.
[17] J. Regehr and N. Cooprider. Interrupt veriﬁcation via
thread veriﬁcation. Electronic Notes in TheoreticalComputer Science, 174(9):139–150, June 2007.