Van-Thiep Nguyen
email: van-thiep.nguyen@irisa.fr

Matthieu Gautier
email: matthieu.gautier@irisa.fr

Olivier Berder
email: olivier.berder@irisa.fr

FTA-MAC: Fast Traffic Adaptive energy efficient MAC protocol for Wireless Sensor Networks

Keywords: Energy-efficient MAC protocol, Traffic aware, Wireless sensor networks, Wake-up interval

This paper presents the FTA-MAC (Fast Traffic Adaptive MAC) protocol, a novel energy-efficient MAC protocol based on asynchronous duty cycling for Wireless Sensor Networks (WSNs). In FTA-MAC protocol, the communication between the sensor nodes is initiated by sending a wake-up beacon from the receiving node. The latter fast adapts its wake-up interval according to the traffic rate in order to reduce the idle listening of the transmitting nodes, which results in reducing the energy consumption. FTA-MAC protocol is implemented and evaluated in OMNeT++/Mixim network simulator. Simulation results show that FTA-MAC outperforms state-of-the-art protocols under fixed and variable traffic rates and also with multiple concurrent nodes. Thanks to this better wake-up schedule, the lifetime of a sensor node is increased 1.5 to 2 times.

Introduction

Wireless sensor networks (WSNs) received tremendous attention in recent years because of the evolution of sensor devices as well as wireless communication technologies. The sensor devices connected to the Internet of Things (IoT) [START_REF]Definition of the Internet of Things (IoT)[END_REF] can be used to enable remote health monitoring, emergency notification or other observation systems. A problem of such sensor devices is the limited lifetime because of the limitation of the battery capacity. To tackle this problem, one solution is to use an energy efficient protocol to control the behavior of each device in the network. Another challenge in these systems is to deal with variable traffic that can appear in applications such as remote health monitoring. In this type of systems, the sensor nodes are used to monitor the patient physiological parameters such as pulse rate, body temperature, etc., which are periodically transmitted to the center node (e.g. a smart phone). However when the observed patient changes its activity, the sensor nodes can also modify their data rate. Therefore, a new communication management mechanisms are required allowing these devices to adapt with respect to the variable traffic.

The Medium Access Control (MAC) layer allows a sensor node to efficiently share the wireless medium with others in the network. In this layer, the main causes of energy consumption are the idle listening, the overheads, the overhearing and the collisions [START_REF] Bachir | MAC Essentials for Wireless Sensor Networks[END_REF]. Thus, in order to reduce the energy, these factors need to be optimized but there are trade-offs between them. For example, reducing idle listening and collisions requires extra synchronization and overheads, whereas reducing the synchronization and overheads causes the waste of energy in collisions. In the context of energy-efficient MAC protocols, an important mechanism for reducing the energy consumption is duty cycling. In this technique, the radio is turned on periodically, switching between awake and sleeping states.

The recent duty cycling MAC protocols can be grouped into two types: synchronous and asynchronous. While synchronous duty cycling MAC protocols (such as SMAC [START_REF] Ye | An energy-efficient MAC protocol for wireless sensor networks[END_REF], TMAC [START_REF] Van Dam | An Adaptive Energy-efficient MAC Protocol for Wireless Sensor Networks[END_REF]) reduce the energy consumption by synchronizing the sleep and wake-up times of sensor nodes, asynchronous duty cycling protocols do not require any synchronization period and can be categorized into two groups: sender initiated (e.g. BMAC [START_REF] Polastre | Versatile Low Power Media Access for Wireless Sensor Networks[END_REF], XMAC [START_REF] Buettner | X-MAC: A Short Preamble MAC Protocol for Duty-cycled Wireless Sensor Networks[END_REF], WiseMAC [START_REF] El-Hoiydi | WiseMAC: An Ultra Low Power MAC Protocol for the Downlink of Infrastructure Wireless Sensor Networks[END_REF]) and receiver initiated (PW-MAC [START_REF] Tang | PW-MAC: An Energy-Efficient Predictive-Wakeup MAC Protocol for Wireless Sensor Networks[END_REF], RICER [START_REF] Lin | Power-efficient rendez-vous schemes for dense wireless sensor networks[END_REF], RI-MAC [START_REF] Sun | RI-MAC: A Receiver-initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks[END_REF], TAD-MAC [START_REF] Alam | TAD-MAC: Traffic-Aware Dynamic MAC Protocol for Wireless Body Area Sensor Networks[END_REF]). In asynchronous protocols, the receiver/sender sends a Wake-up Beacon (WB) to schedule a rendez-vous with other nodes for receiving/sending data frames.

While many of these protocols have been proposed to reduce energy consumption, few of them address the case of WSNs with variable traffics. Indeed, the traffic in WSNs can be variable depending on the requirements of the applications. The senders can change their traffic rate many times and without any preview.

In this paper, a new asynchronous duty cycling energy efficient MAC protocol, called Fast Traffic Adaptive MAC (FTA-MAC) protocol, is presented. Typically, in a duty cycling protocol, the optimal protocol has the schedule such that the sender and receiver wake up at same time, as it is the case for synchronous protocols but at the price of less flexibility and extra overheads, leading to energy waste. To approach this optimal schedule, FTA-MAC protocol adapts the wake-up interval of the receiver toward the transmission rate of the sender. To deal with variable traffic, FTA-MAC provides an adaptive mechanism at the receiver side to quickly reach a steady state value of wake-up interval according to the new traffic rate of sender.

The contributions of our work are:

-designing of a novel energy-efficient MAC (FTA-MAC) protocol for WSNs with variable traffics. FTA-MAC minimizes the energy consumption of the sensor nodes by reducing their idle listening time. -implementing FTA-MAC in OMNeT++/Mixim network simulator for a star network topology. The performance of FTA-MAC are compared with TAD-MAC and RICER under fixed and variable traffic rates.

The rest of this paper is organized as follows. Section 2 describes the related works on receiver-initiated and adaptive MAC protocols. The main contribution of the paper is presented in Sections 3 and 4, which describe the design of FTA-MAC protocol and its evaluation through network simulations, respectively. Finally, the paper ends with the conclusion in Section 5.

Related Works

One of the early MAC protocols based on duty cycling technique with initiation by the receiver is RICER proposed in [START_REF] Lin | Power-efficient rendez-vous schemes for dense wireless sensor networks[END_REF]. A receiving node wakes up with a constant period I W U and initiates the communication by transmitting a short WB (with a duration T b ) and by monitoring the channel for a fixed duration T l . If there is no response, this node goes back to sleep. A source node with data to transmit wakes up, stays awake and waits for the WB from the destination. Once receiving a WB, it sends its data frame. The communication ends with an acknowledgement (ACK) sends from the destination after correctly receiving the data frame. Two other versions of RICER were proposed in [START_REF] Lin | Receiver initiated rendezvous schemes for sensor networks[END_REF] to avoid data collisions.

The receiver-initiated mechanism has been also applied to asynchronous duty cycling in RI-MAC (Receiver-Initiated MAC) [START_REF] Sun | RI-MAC: A Receiver-initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks[END_REF]. In RI-MAC, the WB is used to initiate the communication.In some cases, the receiver is already active and sends WB before the sender wakes up so the latter misses it. An mechanism called beacon-on-request aims to avoid this bad situation. The sender sends a special WB which contains the receiver address to specify who is supposed to receive the following DATA frame. The receiver answers a beacon to enable the sender to send DATA immediately. RI-MAC works with dynamic traffic load by increasing or decreasing the number of nodes but does not work for the variable traffic.

Proposed in [START_REF] Tang | PW-MAC: An Energy-Efficient Predictive-Wakeup MAC Protocol for Wireless Sensor Networks[END_REF], PW-MAC (Predictive-Wakeup MAC) aims at optimizing the idle listening. PW-MAC schedules the rendez-vous for a receiving node and a transmitting node by using a pseudo-random number generator in each node. The receiver includes the parameters of its generator in the WB. Based on these values, the sender can predict the next wake-up of the receiver so that the sender can wake up shortly before the receiver. Although this mechanism reduces the idle listening and energy, it is not suitable for networks with variable traffic. If the sender needs to change its traffic rate, it must buffer the data frame and waits until the receiver wakes up. The traffic latency will increase and frames will be dropped if the buffer is full.

One protocol that includes a mechanism for variable traffic is TAD-MAC (Traffic-Aware Dynamic MAC) protocol, presented in [START_REF] Alam | TAD-MAC: Traffic-Aware Dynamic MAC Protocol for Wireless Body Area Sensor Networks[END_REF]. In TAD-MAC, the receiver periodically sends a WB and considers the variable traffic by adapting its wake-up interval to the traffic rate of each individual sender. In order to be reactive to the traffic change, the receiver wakes up twice more frequently than the sender. This leads to energy waste due to unnecessary wake-ups of the receiver. Unlike in RI-MAC, the WB of TAD-MAC contains a specific node address to identify the destination address. This mechanism allows the reduction of wireless collisions.

FTA-MAC and TAD-MAC protocols are both based on the Traffic Status Register (TSR) technique introduced in the next section. However, FTA-MAC proposes an algorithm which allows the receivers to estimate the data rate of senders and to wake up just in time to reduce the idle listening of senders.

Fast Traffic Adaptive MAC protocol 3.1 Traffic Status Register (TSR) based protocol

In a network under variable traffic, the traffic estimation is an important part. With their limited computation capacity, the sensor nodes require a light-weight mechanism to estimate the traffic. The TSR technique is first introduced in [START_REF] Alam | TAD-MAC: Traffic-Aware Dynamic MAC Protocol for Wireless Body Area Sensor Networks[END_REF] to store the status information of the traffic. When a receiver wakes up to send a WB, if it receives a data response, the TSR corresponding to the transmitted node is filled with a BIT 1, in contrast, the TSR is filled with a BIT 0. The new status (either BIT 1 or BIT 0) is inserted into the TSR at the first index by shifting left one bit. In a star network, the receiver contains a list of TSR to track the traffic status of all the potential senders, as described in Fig. 1. This is a blind way to keep the track of traffic load without any information about the data rate of the transmitter. This blind estimation is not a quantitative evaluation of the data rate but rather a relative measure of either the traffic is increasing (which is represented by multiple consecutive ones in the TSR) or decreasing (which is represented by multiple zeros in the TSR). In this context, the sequence [10101010. . . ] seems the best trade-off between the optimal sequence [11111111. . . ] (i.e. each wake-up of the node is followed with a successful data reception), and the too frequent wake-up [10001000...] due to several reasons:

-Sequence of [11111111. . . ] is an ideal sequence which means that each time the receiver wakes up, it receives data. Because of the blind estimation, it always has probability of missing data as soon as the traffic rate increases (at the transmitter side). The wake-up interval of the receiver will remain at lower traffic rate. -Sequence of [10001000. . . ] is another extreme as the receiver wakes up too often and wastes energy by sending unnecessary WB.

Thus, [10101010. . . ] sequence is selected as a steady state in TAD-MAC protocol. The sender periodically wakes up to send data. This period is called interval of transmission (I T x ) and the receiver adapts it wake-up interval (I W U ) according to the I T x of sender. With the sequence [10101010. . . ], the receiver wakes up twice more frequently than the sender. It means that I W U is equal to 0.5I T x . The sender wakes up and waits for WB from the receiver in a limited interval of time (t W Bmax ) and the t W Bmax is always less than I T x . Because of the blind estimation, a drawback of the TSR technique is that the receiver can converge to a wrong value even if the sequence is still the best trade-off sequence Fig. 2. Wrong convergence of TAD-MAC protocol (IW U converges to 3 2 IT x instead of 1 2 IT x).

[10101010. . . ] with the condition that t W Bmax is less than 0.5I T x . This problem is described more clearly in Fig. 2 where the receiver converges to a wrong value:

I W U is equal to 1.5I T x .
Moreover, the speed of convergence depends on the length of the TSR and the pair values of I W U0 (the initial value of I W U ) and I T x . In some worst case, the receiver takes a long time to reach the steady state and loses much energy. The blind estimation without any additional information from the sender nodes is a good idea but it still has many limitations. described in Fig. 3. The figure is divided into two phases: before and after the convergence. On the one hand, the receiver periodically sends a WB frame to notify its wake-up to the other nodes. On the other hand, the sender periodically wakes up with a period I T x which depends on its data rate. Before sending the data, it waits for the WB from the receiver. This period is called idle listening time (t idle ) which is the most energy consumption activity in receiver-initiated MAC protocols. Once receiving the WB, the sender sends the data after sensing the medium channel during an interval of time called t CCA (Clear Channel Assessment). The communication session ends with an acknowledgement (ACK) message from the receiver to the sender after successfully receiving the data frame.

FTA-MAC Protocol Design

To reduce t idle , the receiver attempts to wake up according to the I T x of each sender. The wake-up interval (I W U ) of the receiver is adapted itself to the data transmission rate of each transmitting node by collecting the statistics of its data traffic. To this aim, a TSR is used to store the recent history of data transmission, as for TAD-MAC protocol.

The second phase after convergence indicates that the receiver has adapted its I W U to the I T x of the senders in such a way that the idle listening time is reduced. This phase is described in Fig. 3b, where the t idle of the source node is reduced. The adaptive mechanism of I W U is explained in Fig. 4 and I W U is calculated by the following adaptive function:

I W U (i + 1) = I W U (i) + n 0 (i).t ref if TSR(i) = 0 i j=k I W U (j)+t idle k -t idle i N W W +1 if TSR(i) = 1 , (1)
where n 0 (i) is the number of bits 0 in the TSR, t ref is the system clock factor, i and k indexes stand for the two last moments when the receiving node received data from the sender, t idle k and t idlei are the sender idle listening time for the two last times it received a WB and N W W is the number of wake-ups without receiving WB. The three values t idle k , t idlei and N W W are calculated at the sender side and sent to the receiver in the data frame, whose structure is described in the next section. The variable N W W stores the statistic of the received WB in order to deal with the TSR wrong convergence problem described in Fig. 2. Each time the sender wakes up without receiving the WB, the variable N W W is increased. This information is sent to the receiver at the next data frame and then is reset to 0.

In FTA-MAC, the algorithm is designed to converge toward a steady state value of I W U , where the TSR contains a sequence [11111111. . . ]. This sequence is the best sequence of the TSR, i.e. each time the receiver wakes up, it receives the data from the sender. This sequence also specifies that the I W U has converged. As discussed in Sec. 3.1, the sequence [111111111. . . ] has the latent problem that the receiver can not detect the increase of traffic rate. But in FTA-MAC protocol, the adaptive function is provided the essential information (t idle , N W W ) of the sender so the receiver can detect as soon as the traffic rate changes (either increases or decreases) and the receiver does not need to wake up more frequently than the sender.

Frame structure

The frame structure proposed for FTA-MAC is described in Fig. 5. The first byte is used for the frame information in which the 3 first bits specify the type of frame. In FTA-MAC, there are 3 types of frame: WB (000), DATA (001) and ACK (010). The next 5 bits are reserved for further utilization. Based on the type of frame, the 4 or 8 next bytes are used for address information. The WB frame is broadcast so the destination address does not need to be defined. In this case, the frame size of WB is 7 bytes and 11 bytes for ACK because these frames have not data.

As discussed in Sec. 3.2 above, the sender will include the 2 variables t idle and N W W in the data frame. The 2 first bytes in the payload part are reserved for these variables so the size of the DATA frame is greater than 13 bytes. For the simulations of the next section, the size of DATA frame is set to 16 bytes.

Performance Evaluation

In this section, the evaluation of performance of FTA-MAC protocol is presented. This protocol is implemented in the OMNeT++ network simulator using the framework MiXiM for WSNs. For comparison purpose, TAD-MAC and RICER protocols have also been implemented. This section addresses first point-to-point communications, then the same simulation framework is used to validate the protocol for multi-sender communications.

Simulation topology

OMNeT++ is an object-oriented modular event network simulator and it provides the infrastructure for writing simulations with the component architecture. MiXiM is a modeling framework for wireless network (WSNs, body area network, ad-hoc network, vehicular network, etc). Each sensor node is simulated with a single omni-directional antenna and using the simple path loss model of radio propagation. Table 1 summarizes the key parameters which are used to simulate the radio. Most of these parameters are from the data sheet of CC2420 radio chip [START_REF]CC2420 Single-Chip 2.4GHz[END_REF], which is used in popular WSN testbed systems such as MICAz [START_REF]MEMSIC, Inc -WSN Nodes -MPR2400CB[END_REF], TelosB [START_REF]MEMSIC, Inc -WSN Nodes -TPR2420[END_REF] and PowWow [START_REF]Power Optimized Hardware and Software FrameWork for Wireless Motes[END_REF]. These parameters are used to calculate the energy consumption in the Physical layer of MiXiM.

Convergence speed

In a network with variable traffics, the convergence speed is an important factor to evaluate the performance of a MAC protocol. The convergence speed corresponds to the number of wake-ups of the receiver needed to converge toward the good TSR register, i.e. [1111. . . ] for FTA-MAC and [1010. . . ] for TAD-MAC. When the receiver reaches the steady state, the t idle of the sender is minimized such that the faster the receiver converges toward the steady state, the less energy the sender consumes. In order to evaluate the convergence speed of FTA-MAC and TAD-MAC, the first simulation scenario is configured with a fixed traffic rate of 2 frames per second for a point-to-point communication. Table 2 summarizes the MAC protocol parameters which are used in the simulations. These parameters are the values used for TAD-MAC protocol in [START_REF] Alam | TAD-MAC: Traffic-Aware Dynamic MAC Protocol for Wireless Body Area Sensor Networks[END_REF]. The variable I W U0 is tuned from 0.1s to 2s to study the impact of the initial wake-up interval on the convergence speed of these protocols.

The simulation results in Fig. 6 show that FTA-MAC protocol reaches the steady state value faster than TAD-MAC and the convergence speed is nearly independent of the variable I W U0 . The convergence speed is constant when the value of I W U0 is greater or equal than the traffic rate (I T x =0.5s for a data rate of 2 frames/s). On the contrary, the convergence speed of TAD-MAC depends on the value of I W U0 . Even with the best value of I W U0 (0.3s) for TAD-MAC, the latter converges slower than FTA-MAC.

Energy Evaluation for Variable Traffics

One of the advantages of FTA-MAC compared with TAD-MAC is the fast convergence speed toward a steady state value of I W U . This advantage can be traduced in significant energy gain for sending and receiving a frame in a network with variable traffics. The traffic rate changes by increasing or decreasing the I T x of the traffic generator of the sender. In this simulation, a change corresponds to a new random value for I T x uniformly distributed between 100ms and 1000ms. The number of changes is varied from 0 to 30 for a simulation time of 2000s. All of these parameters are specified in Table 3. The results for variable traffic are shown in Fig. 7 and8, where each average value is calculated from the results of 100 random simulations. FTA protocol is compared with TAD-MAC and also with the commonly used RICER protocol. RICER has no adaptation mechanism and is tuned by its wake-up interval I W U . Fig. 7 shows the average energy consumption for sending and receiving a frame which is calculated at both sender and receiver sides for a successful transmission. The energy consumption of TAD-MAC is 1.6 to 2 times more than the one of FTA-MAC and this gain increases with the number of changes of I T x . The FTA-MAC protocol saves more energy than TAD-MAC because of the fast convergence speed. For each change of the traffic rate, the receiver needs to adapt its I W U according to the new steady state value of I T x . The fast convergence speed reduces not only the energy consumption of the receiver but also of the sender by reducing the energy wasted during the idle listening period. The adaptation of the receiver toward the data rate of the sender allows FTA-MAC to outperform also RICER protocol not only under the variable traffic but also with fixed traffic. Indeed, Fig. 7 shows that FTA-MAC uses nearly 7 times less energy consumption than RICER (I W U = 100ms) and 9 times less than RICER (I W U = 50ms).

The other factor used to evaluate the performance of the MAC protocols is the frame latency. The results are shown in Fig. 8. Although the RICER sensor node wakes up more frequently, FTA-MAC protocol has a lower latency. To gain 0.002s less latency than FTA-MAC at 30 changes of traffic rate, RICER sensor node with a I W U = 50ms needs to wake up 10 times more frequently and thus consumes much more energy (about 9 times more).

Evaluation for multi sender networks

When the communication is extended to multiple concurrent senders, data collisions can occur and decrease the performance of a protocol. Thus this kind of networks is also addressed to evaluate the performance of FTA-MAC. A star topology with a number of senders increasing from 1 to 9 is used and a traffic rate of 2 frames per second is set for all senders. When increasing the number of nodes, wake-up collisions will appear more frequently. Simulation results are given in Fig. 9 and Fig. 10, showing the average latency and the energy consumption of FTA-MAC, TAD-MAC and RICER3 (a version of RICER with a mechanism to avoid data collision). The latency and the energy consumption of FTA-MAC slightly increase while these factors for TAD-MAC and RICER3 sharply increase with the number of senders. In RICER3, the number of slots are set according to the number of senders to avoid data collision. Thus, when many senders concurrently send data to the receiver, some nodes will take a long time to wait their WB (i.e. the t idle is increased). For TAD-MAC protocol, the data collision increases the time to converge toward the steady state. This issue increases the latency and the energy consumption in TAD-MAC.

Conclusion

In this research, a novel adaptive energy efficient MAC protocol is introduced. The FTA-MAC protocol presents an algorithm that allows the receiver to adapt its I W U according to the transmission rates of the sender. With the fast convergence speed, the receiver is well scheduled to wake up closely to the sender so reducing its idle listening. Thus the energy consumption in a sensor node is decreased 2 times compared to TAD-MAC protocol and 9 times compared to RICER protocol. This improvement is even more interesting for communications with variable traffics and also for a star network topology with concurrent multi-senders. The further work will extend FTA protocol to multi-hop networks, where the impact of idle listening on the energy consumption increases with the number of hops.

Fig. 1 .

 1 Fig. 1. Traffic Register Status (TSR) structure.

  FTA-MAC is a novel protocol based on the duty cycling technique. The communications between the sensor nodes are initiated by the receiving node and the principle is (a) Before convergence phase. (b) After convergence phase.

Fig. 3 .

 3 Fig. 3. Behaviour of FTA-MAC protocol.

Fig. 4 .

 4 Fig. 4. Adaptive function to calculate IW U .

Fig. 5 .

 5 Fig. 5. New frame structure of FTA-MAC.

Fig. 7 .

 7 Fig. 7. Energy consumption per frame under variable traffic.

Fig. 8 .

 8 Fig. 8. Average latency of frame under variable traffic.

Fig. 9 .

 9 Fig. 9. Average latency of frame with multiple concurrent senders.

Fig. 10 .

 10 Fig. 10. Energy consumption per frame with multiple concurrent senders.

Table 1 .

 1 Configuration of radio parameters.

	Bitrate 250 kbit/s
	RX current 18.8 mA
	TX current 17.4 mA
	Sleep current 0.03 mA
	PT x 1mW

Table 2 .

 2 Configuration of MAC protocol parameters. IW U convergence speed as a function of IW U 0 .

	TSR length 4
	tW Bmax 500 ms
	tCCA 0.5 ms
	IW U 0 0.1s -2s

Table 3 .

 3 Simulation parameters for variable traffic.

	Simulation time 2000 s
	Traffic rate 1 frame/s -10 frames/s
	IW U 0 (FTA & TAD) 0.3 s
	IW U (RICER) 0.05s / 0.1s
	Number of changes from 0 to 30
	Number of random simulations 100


Suman Saha

Jean-Pierre Lozi

EHCtor: Detecting Resource-Release Omission Faults in Error-Handling Code for Systems Software

Adequate error-handling code is essential to the reliability of any system. On an error, such code is responsible for releasing acquired resources to restore the system to a viable state. Missing resource-release operations can lead to system crashes, memory leaks and deadlocks. A number of approaches have been proposed to detect such problems, but they mainly target frequently occurring resource-release operations. In this paper, we propose a novel approach to finding resource-release omission faults, focusing on error-handling code. Our approach achieves precision and scalability by exploiting information available within each function definition itself. Using a tool, EHCtor, that we have developed based on this approach, we have found over 370 faults in six different C infrastructure software projects, with a false positive rate well below the 30% that has been reported to be acceptable to developers. Some of these faults are exploitable by an unprivileged malicious user, making it possible to crash the entire system.

Introduction

Any computing system may encounter errors, such as inappropriate requests from supported applications, or unexpected behavior from malfunctioning or misconfigured hardware. If the system's software does not recover from these errors correctly, they may lead to more serious failures such as a crash or a vulnerability to an attack by a malicious user. Therefore, correct error recovery is essential when a system supports long-running or critical services. Indeed, the ability to recover from errors has long been viewed as a cornerstone of system reliability [START_REF] Randell | Software reliability: The role of programmed exception handling[END_REF], and much of systems code is concerned with error detection and handling. Despite its importance to systems software, error recovery has received insufficient attention in the systems community. Previous work has focused on error detection and propagation [START_REF] Gunawi | EIO: Error handling is occasionally correct[END_REF][START_REF] Kadav | Tolerating hardware device failures in software[END_REF][START_REF] Rubio-González | Error propagation analysis for file systems[END_REF], i.e., the correctness of tests and return values, and on fault-injection prioritization with the goal of exercising error recovery code [START_REF] Banabic | Fast black-box testing of system recovery code[END_REF]. Error detection and propagation, however, are not enough; a function detecting an error must also undo any previous operations that could leave system resources in an inconsistent state. Omission of a resource-release operation in such errorhandling code can lead to crashes, deadlocks, and resource leaks. To our knowledge, detecting these omission faults in error-handling code has not previously been specifically targeted. Detecting resource-release omission faults is challenging because it requires knowing the set of operations that are required to restore the system to a viable state. Typical systems software relies on a wide range of resources, each associated with many different dedicated operations, making it difficult for any given developer to be familiar with all of them. Approaches have been proposed to automatically identify these operations by some form of specification mining [START_REF] Ammons | Mining specifications[END_REF][START_REF] Engler | Bugs as deviant behavior: A general approach to inferring errors in systems code[END_REF][START_REF] Gabel | Javert: Fully automatic mining of general temporal properties from dynamic traces[END_REF][START_REF] Lawall | WYSIWIB: A declarative approach to finding protocols and bugs in Linux code[END_REF][START_REF] Li | PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code[END_REF][START_REF] Lo | Mining temporal rules for software maintenance[END_REF][START_REF] Nguyen | Graph-based mining of multiple object usage patterns[END_REF][START_REF] Wasylkowski | Detecting object usage anomalies[END_REF][START_REF] Weimer | Mining temporal specifications for error detection[END_REF][START_REF] Yang | Perracotta: Mining temporal API rules from imperfect traces[END_REF], in order to find arbitrary faults in function usage. Nevertheless, to reduce the number of false positives, these approaches mostly focus on frequently occurring functions. In practice, however, operations on specific types of resources may appear in the code only rarely. Existing specification mining-based approaches are thus insufficient for finding many of the faults in error-handling code. In this paper, we propose a resource-release omission fault finding tool, EHCtor, that targets and exploits the properties of error-handling code (EHC) in C programs. EHCtor finds resource-release omission faults irrespective of the number of times the associated acquisition and release functions are used together across the code base, and focuses on the resources themselves, rather than the particular functions that manipulate them. To provide both scalability and precision, EHCtor primarily exploits information available within a single function, specifically the information that can be derived from the function's own error-handling code. Our key observation is that when one block of error-handling code needs a given resource release operation, nearby error-handling code typically needs the same operation. Thus, the existing error-handling code within a function can be used as an exemplar for the operations that should be performed by other error-handling code in the same function. By exploiting this observation, EHCtor does not require any fixed or user-provided list of resource-release functions and does not depend on the most frequent results obtained by a global scan, like previous approaches. EHCtor can be applied to real-sized systems software. We have applied EHCtor to Linux 2.6.341 drivers (including sound drivers), networking code, and filesystems, as well as to five widely used open-source systems software projects: PostgreSQL, Apache, Wine, Python, and PHP. We have submitted patches based on many of our results to the developers of the concerned software, and these patches have been accepted or are awaiting evaluation. EHCtor finds 371 faults, with an overall false positive rate of 23%, which is below the threshold of 30% that has been found to be acceptable to developers [START_REF] Bessey | A few billion lines of code later: using static analysis to find bugs in the real world[END_REF]. We find omission faults involving 150 different pairs of resource acquisition and release functions. 52% of these pairs of resource acquisition and release functions are used together in the code fewer than 15 times, making the associated faults unlikely to be detected by previous specification-mining based approaches. The rest of this paper is organized as follows. Section 2 presents some examples that motivate our work. Section 3 presents the fault-finding algorithm on which EHCtor is based. Section 4 evaluates the results obtained by applying EHCtor to large systems software projects. Finally, Section 5 presents related work and Section 6 concludes.

Motivation and Background

We first present two examples of faults in error-handling code found by EHCtor. These examples reveal that faults in error-handling code can have an impact that goes beyond just the loss of a few bytes due to an unreleased resource. We then give an overview of error-handling in system software.

Linux resource-release omission faults

We motivate our work using the examples of crashes and memory leaks derived from faults in Linux error-handling code. One of these faults were previously found by users; in these cases, the Linux commit logs contain no evidence that the faults were found using other tools. The other fault was previously unreported; we have reported it to the appropriate maintainers and provided patches. 2 The unreported fault involves rarely used acquisition and release functions that would be unlikely to be taken into account by a specification-mining based approach. Crash in handling a resource conflict: In January 2009, a user of the Fedora Rawhide (development) kernel found that installing the w83627ehf driver crashed his machine. 3 Fig. 1(a) shows an extract of the code containing the fault. This extract performs a series of operations, on lines 1, 4, 6, 10, and 13, that may encounter an error. If an error is detected, the function branches to the error-handling code (boxed) on lines 3, 5, 8, 12 and 15, respectively. In the first three cases, the error-handling code correctly jumps to labels at the end of the function that execute an increasing sequence of device unregister operations, according to the resource acquisitions that have been performed so far. The error-handling code provided with the ACPI resource conflict check on line 10, however, is faulty, as it jumps to the last label in the function, which just returns the error code. The device remains registered even though it does not exist, and subsequent operations by the kernel on the non-existent device are reported to cause the system to crash.

Memory leak in the handling of invalid user inputs: Using EHCtor, we found a previously unreported memory-release omission fault in the autofs4 IOCTL function. Using a 9-line program, we were able to repeatedly invoke the IOCTL function with an invalid command argument, and use up almost all of the 2GB of memory on our test machine in less than one minute. This fault is exploitable by an unprivileged user who has obtained the CAP MKNOD capability.

We have verified that an unprivileged user can obtain this capability using a previously reported NFS security vulnerability. 4 Using this vulnerability, an attacker, having usurped the IP address of an NFS client, is able to create an autofs4 device file accessible to non-privileged users on the NFS server. Then, the attacker, connected as a non-priviliged user on each NFS client machine, can exploit the autofs4 fault to exhaust all the memory of each client machine by issuing invalid IOCTL calls, preventing other programs from allocating memory and causing them to fail in unpredictable ways. Reclaiming the lost memory requires rebooting each affected machine.

Systems error-handling code

The interest of our approach depends on the importance of error handling code in system software. To assess the importance of such in systems software, we consider the amount of code that is found within functions that contain error-handling code and the kinds of errors that are detected. Our study focuses on the main subdirectories of the Linux 2.6.34 kernel as well as a selection of other widely used systems software, as summarized in Table 1.

Amount of code containing error-handling code:

We define a block of error-handling code as the code executed from when a test for an error is found to be true up to the point of returning from the containing function. The block may include gotos. Fig. 2(a) shows the percentage of code found within functions that contain zero, one, or more blocks of error-handling code. Depending on the project, 28%-69% of the code is within functions that contain at least one block of error-handling code and 16%-43% of the code is within functions that contain more than one block of error-handling code (shown below the horizontal dashed lines). The latter functions are of particular interest, because in such functions, it is possible to identify resourcerelease omission faults by comparing the various blocks of error-handling code to each other and determining whether they are consistent.

Kinds of errors encountered:

The impact of faults in error-handling code is determined in part by how often the handled errors occur. It is difficult to automatically determine the source of all the possible errors that may be encountered. Nevertheless, 48% of the error-handling code in the Linux drivers, sound, net, and fs directories, returns integer error codes, understood by the user-level standard library function perror, to indicate the error cause. We rely on these error codes to obtain an overview of the reasons for the errors encountered in Linux. Fig. 2(b) shows the percentage of the considered blocks of error-handling code that involve the various constants used in each of the Linux drivers, sound, net, and fs directories, focusing on the top 10 such constants used in each case. The errors associated with these values differ in their source and likelihood. EINVAL is the most common value throughout and indicates that the function has received invalid arguments. These arguments may ultimately depend on values received from applications or hardware, allowing invalid values from the user level or from hardware malfunctions to trigger a fault. ENOMEM, indicating insufficient memory, is the next most common value for most of the subsystems. Running out of kernel memory is unlikely, except in the case of low-memory embedded systems or unless the system is already under a memory-leak based attack. For drivers, the second most common constant is ENODEV, which is also common in sound. This constant indicates the unavailability of a device, as may be triggered by defective hardware. Another common constant is EFAULT, indicating a bad address. This constant is commonly used by functions copying data to or from user space, where an address comes from user level. A malicious application can easily construct an invalid address, making the correctness of the associated error-handling code critical.

Fault Detection and Ranking with EHCtor

The concept behind EHCtor is that resource-release operations that are needed in one block of errorhandling code are likely to be needed in other nearby blocks of error-handling code in the same function.

To create an algorithm based on this intuition, we first need a strategy for identifying errorhandling code and resources. The C language does not provide any specific abstractions for these entities, and thus our algorithm begins with a preprocessing phase that identifies them using heuristics. Next, we observe that not every resource-release omission is a fault. It may be that the release is not yet needed, or has already taken place. The algorithm thus includes an analysis that identifies and discards cases where an omitted resource-release operation is indeed not needed. The result of the algorithm is a set of reports consisting of those omissions that represent likely faults. To guide the user in identifying the real faults in the code, we propose a strategy for ranking these reports.

Detecting faults

Preprocessing phase: This phase recognizes a block of error-handling code as a conditional that ends, possibly after one or more gotos, by returning an error value. Error values are specific to each software project, but typically include NULL and various constants, or error-value constructing function calls. For example, in Linux, common error values include negative constants, as illustrated in line 12 of Fig. 1(b), and calls to the functions ERR PTR and PTR ERR, as illustrated in line 3 of Fig. 1(b). Information about these error values must be provided by the user in a configuration file. Because error values are used for communicating between different parts of the software, they typically change rarely and are well known. A block of error-handling code may also return no value, or return a variable whose value is not statically apparent, as illustrated in line 22 of Figure 1(a). In this case, the conditional is considered to be a block of error-handling code if the test expression checks for an error value. A conditional that directly returns the result of a function that it calls, other than one of the error functions mentioned above, is never considered to be a block of error handling code, as in this case, the called function must handle any errors.

A resource is typically represented by a collection of information, and is thus implemented by a pointer to a structure or buffer. Resource acquisition and release are typically complex operations, and are thus implemented by function calls. The algorithm recognizes an acquisition as a function call that returns a pointer-typed value, either directly or via a reference argument (&x). It recognizes a release as the last operation on a resource in a given execution path. A release operation should have only one acquired resource among its arguments, which is assumed to be the released resource. We furthermore require that a release operation have no string argument, as string arguments are typically used in debugging code. To improve accuracy, within the file containing the analyzed function, we identify resource-release operations interprocedurally. A function call that has an acquired resource as an argument and whose definition contains a release operation for that resource is also considered to be a release operation. Some kinds of resources, notably locks, are not acquired and released according to the above patterns, but instead using a function that takes the resource as an argument, or even takes no arguments when the resource is encapsulated in the function itself. To account for these cases, we also consider a function call having at most one argument where the argument has pointer type and is not involved in an earlier resource acquisition as being a resource acquisition. The corresponding release is similar, but must occur in a block of error-handling code. Not every pointer-typed value is a resource, not every function that returns a pointer-typed value represents an acquisition, and it is not always the case that the last operation on a pointertyped value in a given function releases that value. To reduce the number of false positives, i.e., values that represent resources that must be released but are not, our algorithm requires all of these properties: a resource is a pointer-typed value that is acquired somewhere within the function and is released in some subsequent block of error-handling code.

Analysis phase: Omission of a resource-release may represent a fault, or it may be legitimate, e.g., because the resource is not yet acquired, has already been released, or has been passed to another function that has the side-effect of releasing the resource on success, on failure, or both. The analysis phase distinguishes between these cases. In presenting the analysis phase, we refer to a block of error-handling code that releases a given resource as an exemplar for the release of that resource and a block of error-handling code that does not release that resource as a candidate fault. This phase then uses the exemplars to determine whether each candidate fault is a real fault. The analysis phase considers that a resource-release may not yet be required if a dataflow analysis shows that a possible value of the resource reaching the candidate fault is different from any possible value reaching any exemplar. Consider the block of error-handling code starting on line 5 in Fig. 1(a), which is missing the release of pdev. Exemplars for the release of pdev are found in the block of error-handling code starting on line 8 and the block of error-handling code starting on line 15. The exemplars and the candidate fault are all reachable from the definition of pdev in line 4. For the exemplars, however, pdev is known to be non-NULL, based on the conditional test enclosing the initialization, while in the case of the candidate fault, it is known to be NULL. Since these possible values are incompatible, the algorithm determines that it has no information about whether releasing pdev is necessary at the point of the candidate fault, i.e., the release is not yet known to be acquired, and no fault is reported. It is indeed not a fault. The analysis phase considers that the resource may already be released when the candidate fault is preceded by a function call that satisfies the constraints for being a release of the resource and that does not appear in any execution path leading to an exemplar. In Fig. 3(a), the block of error-handling code (starting on line 7) releases attr while the second block of error-handling code (starting on line 15) does not. In both cases, the only reaching definition of attr is the one on line 1. However, preceding the execution of the error-handling code starting on line 15, there is a call to kfree on attr in line 12. This call has the form of a resource-release operation, in that the resource is the only pointer-typed argument and there is no reference to attr in the execution path to the error-handling code after this call. Furthermore, this call does not appear in the execution path to the exemplar, implying that there is no information that a resource-release operation is necessary after this call. Note that these considerations are independent of the fact that kfree is a well-known resource-release function, and that it is the resource-release function used by the exemplar. The algorithm thus determines that it has no information about whether a resource release is still necessary, i.e., the resource may already be released, and does not report the fault. The omission is indeed not a fault. Finally, we consider the case where the resource is released as a side-effect of some other operation. In Fig. 3(b), the resource namelist is allocated on line 1, and stored within a field of the resource kctl on line 10. The resource namelist is freed in the error-handling code starting on line 6, but is not freed in the error-handling code on line 13. The analysis phase observes, however, that kctl, from which namelist is reachable, is not used on either success or failure after the call to the non-local function add control to empty on line 12. It thus assumes that add control to empty has freed both kctl and namelist, and thus does not report a fault. add control to empty does indeed free both kctl and namelist, and thus this omission is not a fault. As this example illustrates, our analysis does take into account aliases such as kctl that are constructed within a control-flow path, and assumes that if a resource is released then all resources that are reachable from it are released as well.

Ranking the fault reports

To help the user of a fault-finding tool focus on the reports that are the most likely to represent real faults, a standard approach is to rank the reports in some way. We propose a novel ranking strategy that reflects the properties of error-handling code. The ranking strategy gives a fault report a high rank when the block of error-handling code containing the fault is both preceded in the Control flow graph (CFG) by a block of errorhanding code that releases the resource and followed in the CFG by a release of the resource, whether or not in error-handling code. In this case, we know that a release has been necessary, and that the resource has not yet been released. The ranking strategy gives a report that is only somewhere followed in the CFG by a block of error-handling code releasing the resource a low-initial rank, as it is possible that in this case a resource-release is not yet needed. Finally, the ranking strategy gives a low-final rank to a report that is somewhere preceded in the CFG by a block of error-handling code that releases the resource but is not followed in the CFG by any release of the resource, as in this case we know that the resource has previously reached a state in which it should be released, but may be released already. For example, in Fig. 1(a), the faulty of error-handling code starting on line 12 does not release pdev, while the preceding and following blocks of error-handling code, starting on lines 8 and 15 respectively, do release this resource. The fault is thus ranked high.

Experimenting with EHCtor

The goals of our experiments with EHCtor are 1) to determine its success in finding faults, 2) to compare the results obtained using our algorithm with those of related approaches, 3) to understand the reason for any false positives. EHCtor consists of around 3500 lines of OCaml code, excluding the code for the parser and abstract syntax, which we have borrowed from the open-source transformation tool Coccinelle. 5 We evaluate EHCtor on the large, widely used open-source software projects described in Table 1. For this, we have analyzed 10.5 million lines of C code, in total. Our tests have been carried out on one core of a 8-core 3GHz machine with 16GB memory. Analyzing e.g., Linux drivers (4.6 MLOC) takes around 3 hours.

Found faults

As shown in Table 2, EHCtor generates a total of 484 reports for all projects. We manually investigated all reports and found that 371 of them, from 247 different functions, represent actual faults. These faults occur in the use of 150 pairs of resource acquisition and release operations. There are 113 false positives. We examine the reasons for these false positives in Section 4.2.

Support

Pairs having support >= 15 and confidence >= 90% Other protocols

Figure 4: Support and confidence associated with the functions found in the faults reported by our algorithm. The dotted lines mark support 15 and confidence 90%.

Comparison to specification mining

Specification mining approaches detect sets or sequences of functions that are commonly used together and that represent the required protocol for carrying out a particular task. Such approaches typically suffer from a high rate of false positives [START_REF] Goues | Specification mining with few false positives[END_REF], and thus use some form of pruning and ranking to make the most likely specifications the most apparent to the user. Common metrics used in pruning and ranking include support and confidence, or variants thereof [START_REF] Engler | Bugs as deviant behavior: A general approach to inferring errors in systems code[END_REF][START_REF] Lo | Mining temporal rules for software maintenance[END_REF][START_REF] Nguyen | Graph-based mining of multiple object usage patterns[END_REF][START_REF] Wasylkowski | Detecting object usage anomalies[END_REF][START_REF] Weimer | Mining temporal specifications for error detection[END_REF][START_REF] Yang | Perracotta: Mining temporal API rules from imperfect traces[END_REF]. Support is the number of times the protocol is followed across the code base, while confidence is the percentage of occurrences of a portion of the protocol that satisfy the complete protocol. The tool PR-Miner, for example, which has been applied to Linux code [START_REF] Li | PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code[END_REF], has been evaluated with thresholds causing it to prune fault reports where the associated protocol does not have support of at least 15 and confidence of at least 90% Fig. 4 shows the support and confidence for the protocols involved in our identified faults. The ×s and circles represent the 150 pairs of resource acquisition and release operations associated with the 371 faults identified by EHCtor, and the y-axis indicates support, while the x-axis indicates confidence. Protocols associated with 52% of the faults found by EHCtor have support less than 15, and protocols associated with 86% of the faults found by EHCtor have confidence less than 90%. Indeed, only 7 pairs, marked as ×, have support greater than or equal to 15 and confidence greater than or equal to 90%. These 7 pairs are associated with only 23 (6%) of the 371 faults found by EHCtor, implying that 94% of the faults found by EHCtor would be overlooked when using these thresholds. Indeed, the well-known Linux protocol kmalloc/kfree, for which we find 28 faults, only has confidence of 59%, as many of the functions that call kmalloc have no reason to also call kfree. On the other hand, reducing the support or confidence thresholds used by data-mining-based approaches could drastically increase their number of false positives. EHCtor finds faults independent of the support and confidence of the protocol.

False positives

Figure 5(a) shows the number of false positives among the reports generated by EHCtor and the reasons why these reports are considered to be false positives. The overall false positive rate is 23%, which is below the threshold of 30% that has has been found to be the limit of what is acceptable to developers [START_REF] Bessey | A few billion lines of code later: using static analysis to find bugs in the real world[END_REF]. The reasons for the false positives vary, including failure of the heuristics for distinguishing error-handling code from successful completion of a function (Not EHC, 4%), failure of the heuristics for identifying newly acquired resources (Not alloc, 26%), or for recognizing existing resource releases, whether via an alias (Via alias, 29%) or via a non-local call (Non-local call frees, 12%), or releases performed in the caller of the considered function rather than within the function itself (Caller frees, 13%). The Linux sound, net, and fs directories all have false positive rates higher than 30%. All of the sound false positives come from the use of a single function that creates an alias via which the resource is released. The affected functions all show the same pattern, making these false positives easy to spot. For net, four of the six false positives are due to error-handling code Figure 5: (a) False Positives (b) Report ranking related to timeouts, in which case it is not necessary to release all of the resources. Again, the affected functions have a similar structure. Finally, the fs faults are more varied, and thus more difficult to identify. Still, there are fewer than 50 fs reports in all, making the identification of false positives tractable by a filesystem expert.

To help the user navigate among the reports, we have proposed a ranking strategy (Section 3.2). The ranking strategy is motivated by the common cases of false positives, where a candidate fault occurs before a release is actually needed (low-initial rank, corresponding to the Not alloc cases in Figure 5(a) and where a candidate fault occurs after the resource has already been released (low-final rank, corresponding to the Via alias and Non-local call free cases in Figure 5(a)). Figure 5(b) shows the total number of high, low-initial and low-final ranked reports. Few false positives are high. The user may thus study the high ranked reports first, to get an overall understanding of the use of resources in the software, and then consider the low ranked reports, taking into account the acquired intuitions.

Related Work

While EHCtor targets specifically omission faults in error-handling code software, several approaches have been proposed to detect omission faults more generally in infrastructure software [START_REF] Engler | Bugs as deviant behavior: A general approach to inferring errors in systems code[END_REF][START_REF] Gabel | Javert: Fully automatic mining of general temporal properties from dynamic traces[END_REF][START_REF] Lawall | WYSIWIB: A declarative approach to finding protocols and bugs in Linux code[END_REF][START_REF] Li | PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code[END_REF][START_REF] Nguyen | Graph-based mining of multiple object usage patterns[END_REF][START_REF] Wasylkowski | Detecting object usage anomalies[END_REF][START_REF] Weimer | Mining temporal specifications for error detection[END_REF][START_REF] Yang | Perracotta: Mining temporal API rules from imperfect traces[END_REF]. One heavily explored technique is to use data mining to extract implicit programming rules from source code and then to use static analysis to detect faults based on those programing rules. We first present a few of the proposed variants. Engler et al. use static analysis to automatically extract programming rules from source code, based on user-defined templates [START_REF] Engler | Bugs as deviant behavior: A general approach to inferring errors in systems code[END_REF]. Ranking calculated in terms of support and confidence is used to highlight the most probable rules. PR-Miner uses frequent itemset mining to extract programming rules, without using templates [START_REF] Li | PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code[END_REF]. Results are pruned and ranked according to support and confidence. Kremenek et al. use factor graphs in automatically inferring specifications directly from programs [START_REF] Kremenek | From uncertainty to belief: Inferring the specification within[END_REF]. Ramanathan et al. integrate mining within a path-sensitive dataflow framework to identify potential preconditions for invocation of a function [START_REF] Ramanathan | Path-sensitive inference of function precedence protocols[END_REF]. In each of these cases, the identified specifications can be used to find faults in code. EHCtor does not rely on a separate specification mining phase. Instead, it finds faults based on inconsistent local information, rather than a global analysis of the software. Weimer and Necula observed that faults in error-handling code are common in Java, and pro-posed a static analysis, to identify resource-release omission faults [START_REF] Weimer | Finding and preventing run-time error handling mistakes[END_REF]. Subsequently, they proposed a specification mining approach that gives more weight to specifications derived from error-handling code [START_REF] Weimer | Mining temporal specifications for error detection[END_REF]. While they found many faults, the specification-mining process has a high rate of false positives. To reduce the rate of false positives, Le Goues and Weimer integrated extra information such as author expertise [START_REF] Goues | Specification mining with few false positives[END_REF]. This approach, however, also reduced the number of found faults. Furthermore, statistics are still used, so rarely used resource-release functions may be overlooked. Sundararaman et al. also focus on faults in error-handling code, by trying to avoid the execution of error-handling code in the first place, through the definition of an alternate memory allocator [START_REF] Sundararaman | Making the common case the only case with anticipatory memory allocation[END_REF]. Gunawi et al. [START_REF] Gunawi | EIO: Error handling is occasionally correct[END_REF] and Rubio-González et al. [START_REF] Rubio-González | Error propagation analysis for file systems[END_REF] have studied faults in the detection and propagation of error values. Our work is complementary, in that we focus on the contents of blocks of error-handling code, while they focus only on the return values. In previous work [START_REF] Saha | Finding resource-release omission faults in Linux[END_REF], we considered the use of local information to find omitted errorhandling code, but the approach was evaluated only on Linux drivers, and found substantially fewer faults than found by EHCtor. Banabic and Candea propose a strategy for fault-injection prioritisation to perform run-time checking of error-handling code [START_REF] Banabic | Fast black-box testing of system recovery code[END_REF]. The reported faults involve omitted tests and duplicated releases, while EHCtor focuses on release omissions. Another approach to detect faults is to monitor program execution. A dynamic analysis tool such as Valgrind [START_REF] Nethercote | Valgrind: a framework for heavyweight dynamic binary instrumentation[END_REF] only reports on faults in code that is actually executed. Forcing the execution of all error-handling code would require developing an elaborate testing framework, potentially involving multiple kinds of hardware, depending on the application. Symbolic execution [START_REF] Bucur | Parallel symbolic execution for automated real-world software testing[END_REF] coupled with fault injection [START_REF] Marinescu | Lfi: A practical and general library-level fault injector[END_REF], attempts to address these problems by making it possible to activate all execution paths. However, such techniques remain time-consuming, and no form of specification inference is provided.

Conclusion

In this paper, we have shown that error-handling code is a significant source of faults in systems code, and that such code can have a significant impact on system reliability. We have presented a novel approach to finding faults in error-handling code of systems software that uses a function's existing error-handling code as an exemplar of the operations that are required. By focusing on one function at a time, while taking into account a small amount of interprocedural information from other functions defined in the same file, we obtain a faultfinding algorithm that is precise and scalable. We have implemented our approach as the tool EHCtor, and applied it to find 371 faults in Linux and five other systems software projects. A limitation of our approach is the need for at least one exemplar of a given resource-release operation in the given function. In future work, we will consider whether it is possible to relax this requirement, e.g., to find exemplars in other functions in the same file, or in functions that appear to play the same role in the implementations of related services.

Figure 1 :

 1 Figure 1: a)Omission fault in w83627ehf driver. b) Omission fault in Autofs4

Figure 2 :

 2 Figure 2: a) Percentage of code found within functions that have 0 or more blocks of errorhandling code. b) Distribution of integer error-code return values

Figure 3 :

 3 Figure 3: a) Extract of ib create fmr pool b) Extract of parse audio selector unit.

Table 1 :

 1 Considered software

	Project	(Lines of code)	Version	Description
	Linux drivers	(4.6MLoC)	2.6.34	Linux device drivers
	Linux sound	(0.4MLoC)	2.6.34	Linux sound drivers
	Linux net	(0.4MLoC)	2.6.34	Linux networking
	Linux fs	(0.7MLoC)	2.6.34	Linux file systems
	Wine	(2.1MLoC)	1.5.0	Windows emulator
	PostgreSQL	(0.6MLoC)	9.1.3	Database
	Apache httpd	(0.1MLoC)	2.4.1	HTTP server
	Python	(0.4MLoC)	2.7.3	Python runtime
	Python	(0.3MLoC)	3.2.3	Python runtime
	PHP	(0.6MLoC)	5.4.0	PHP runtime
	Both considered versions of Python are in current use.

Table 2 :

 2 Faults and containing functions (Fns)

		Reports	Faults	Faults	Impact
		(Fns)	(Fns) per EHC Resource leak Dead lock Debug
	Linux drivers 293 (180) 237 (152)	0.0026	217	7	13
	Linux sound	32 (19)	19 (13)	0.0018	16	0	3
	Linux net	13 (13)	7 (7)	0.0005	7	0	0
	Linux fs	47 (34)	22 (17)	0.0012	17	2	3
	Python (2.7)	17 (13)	13 (11)	0.0007	13	0	0
	Python (3.2.3)	22 (13)	20 (12)	0.0023	20	0	0
	Apache httpd	5 (5)	3 (3)	0.0012	3	0	0
	Wine	31 (19)	30 (18)	0.0009	30	0	0
	PHP	16 (13)	13 (10)	0.0053	13	0	0
	PostgreSQL	8 (5)	7 (4)	0.0010	7	0	0
	Total	484 (314) 371 (247)	0.0018	343	9	19

Linux

2.6.34 was released in May 2010. We have taken a somewhat older version to prevent our previous contributions to the Linux kernel from interfering with our results. 2 http://lkml.org/lkml/2012/4/14/41

https://bugzilla.redhat.com/show bug.cgi?id=483208

http://lwn.net/Articles/328594/

http://coccinelle.lip6.fr/