Tegawendé F Bissyandé
email: tegawende.bissyande@uni.lu

Laurent Réveillère
email: laurent.reveillere@labri.fr

Julia L Lawall

Gilles Muller
email: gilles.muller@lip6.fr

Ahead of Time Static Analysis for Automatic Generation of Debugging Interfaces to the Linux Kernel

Keywords: Diagnosys, Debugging, Wrappers, Linux, Device Drivers, Plugin, Reliability, Testing

The Linux kernel does not export a stable, well-defined kernel interface, complicating the development of kernel-level services, such as device drivers and file systems. While there does exist a set of functions that are exported to external modules, this set of functions frequently changes, and the functions have implicit, ill-documented preconditions. No specific debugging support is provided.

We present Diagnosys, an approach to automatically constructing a debugging interface for the Linux kernel. First, a designated kernel maintainer uses Diagnosys to identify constraints on the use of the exported functions. Based on this information, developers of kernel services can then use Diagnosys to generate a debugging interface specialized to their code. When a service including this interface is tested, it records information about potential problems. This information is preserved following a kernel crash or hang. Our experiments show that the generated debugging interface provides useful log information and incurs a low performance penalty.

Introduction

Debugging is difficult. And debugging an operating system kernel-level service, such as a device driver, file system, or network protocol, is particularly difficult. When a service crashes, the service developer is presented with a backtrace, containing the location of the instruction that caused the crash and the pending return pointers on the stack. This information may be unreliable or incomplete. And even when the backtrace information is present and correct, it does not capture context information such as the values of local variables and the effect of recent decisions that are often essential to identify the problem. Indeed, kernel service code contains many execution paths, taking conditions from the operating environment into account, and is difficult to test deterministically. Support is needed for providing more information at the time of a crash, without introducing a substantial performance penalty or imposing an additional burden on the developer.

As Linux is becoming more and more widely used, in platforms ranging from embedded systems to supercomputers, there is an increasing interest from third-party developers, having little expertise in Linux internals, in developing new Linux kernel services. Such services must integrate with the Linux kernel via the various kernel-level APIs. Developing code at this level is challenging. Indeed, the Linux kernel is designed around the assumption that the source code of all kernel-level services is available within the publicly available kernel source tree, and thus kernel APIs are, for efficiency, only as robust as required by their internal client services. Furthermore, kernel developers can freely adjust the kernel APIs, as long as they are willing to update all of the affected service code. The kernel implementation is thus, by design, maximally efficient and evolvable, enabling it to rapidly meet new performance requirements, address security issues, and accommodate new functionalities. But these assumptions complicate the task of the developers of new services who require more safety and help in debugging, and whose code is not yet integrated into the mainline kernel. Advances in bug-finding tools [START_REF] Ball | Thorough static analysis of device drivers[END_REF][START_REF] Lawall | WYSIWIB: A declarative approach to finding API 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], specialized testing techniques [START_REF] Kuznetsov | Testing closed-source binary device drivers with DDT[END_REF][START_REF] Marinescu | Efficient testing of recovery code using fault injection[END_REF], and code generation from specifications [START_REF] Ryzhyk | Dingo: Taming device drivers[END_REF] have eased but not yet fully solved these difficulties. Current approaches put substantial demands on the developer, both to learn how to use the approach and to effectively integrate it into his development process.

We concretize the difficulty confronting a Linux service developer in interacting with the Linux kernel as the notion of a safety hole. We define a safety hole as a fragment of code that introduces the potential for a fault to occur in the interaction between a kernel-level service and the rest of the kernel. For example, code in the definition of a kernel API function that dereferences a parameter without testing its value represents a safety hole, because a service could invoke the function with NULL as the corresponding argument. Likewise, code in the definition of a kernel API function that returns NULL as the result represents a safety hole, because a calling service could dereference this result without checking its value. We stress, however, that a safety hole is not a fault. It constitutes an implementation choice for a function that poses a risk to the safety of other functions that call that function. Unfortunately, such a risk is often undocumented.

To address the problem of safety holes in Linux kernel internal API functions, we propose an approach, named Diagnosys, that automatically generates a debugging interface to the Linux kernel tailored for a particular kernel-level service under development. The generation of the interface is automatic, based on a prior static analysis of the Linux kernel source code, that is performed only once, for each release. The generated debugging interface amounts to a wrapper on the kernel exported functions, that logs information about potentially dangerous uses of these functions. Localizing the interface in this way, at the boundary of the interaction between the service and the OS kernel, ensures that the feedback provided by the interface is in terms of the code that the developer has written, and is thus expected to be familiar with. Because the interface is only visible to the service, it has no impact on the performance of code within the kernel, even code that uses functions that contain safety holes. When the service executes, the interface generates log messages whenever service code invokes a kernel API function containing a safety hole in a potentially risky way. Such a debugging interface requires no manual intervention from the service developer until there is a crash or hang, and is thus well-suited to intensive service development, when the developer is modifying the code frequently, and bugs are likewise frequent. Because the debugging interface is generated automatically, it can be regenerated for each new version of the Linux kernel, as the properties of the kernel APIs change.

Diagnosys is composed of two tools: SHAna (Safety Hole Analyzer), which statically analyzes the kernel source code to identify safety holes in the definitions of the kernel exported functions, and DIGen (Debugging Interface Generator), which uses the information about the identified safety holes to construct a debugging interface tailored to a given service. Diagnosys also includes a runtime system, provided as a kernel patch. SHAna is run by a Linux kernel maintainer once for each Linux version, to take into account the current definitions of the Linux kernel API functions. The service developer does not interact with SHAna. DIGen is run by a service developer as part of the service compilation process, using a Diagnosys-specific variant of the standard make command. During the execution of the resulting service, the debugging interface uses the runtime system to log information about any unsafe uses of functions containing safety holes in a buffer that is preserved across reboots. On a kernel crash or hang, the service developer can consult the buffer after reboot to obtain the logged information.

The main contributions of this paper are as follows:

-We identify the interface of kernel exported functions as a sweet spot at which it is possible to interpose the generation of debugging information, in a way that improves debuggability but does not introduce an excessive runtime overhead. -We identify safety holes as a significant problem in the interface between a service and the kernel. Indeed, after carefully analysing all 703 commits of Linux 2.6 that explicitly refer, in their log message, to a function exported in Linux 2.6.32, we have found that 38% of these commits corrected faults that are related to one of our identified safety holes. -We propose an approach to allow a service developer to seamlessly generate, integrate, and exploit a kernel debugging interface specialized to the service code. This approach has a low learning curve, and in particular does not require any particular Linux kernel expertise. -Using fault-injection experiments on 10 Linux kernel services, we demonstrate the improvement in debuggability provided by our approach. We find that in 90% of the cases in which a crash occurs, the log contains information relevant to the origin of the defect, and in 95% of these cases, a message relevant to the crash is the last piece of logged information. We also find that in 93% of the cases in which a crash or hang occurs, the log information reduces the number of files that have to be consulted to find the cause of the bug. -We show that the generated debugging interface incurs only a minimal runtime overhead on service execution, allowing it to be used up through early deployment.

The rest of this paper is organized as follows. Section 2 illustrates problems in kernel development that have been related to safety holes and gives an overview of kinds of safety holes that we take into account. Section 3 discusses the challenges in kernel debugging, focusing on crashes and hangs derived from safety holes. Section 4 presents Diagnosys, including the process of collecting information about the occurrences of safety holes and the associated preconditions, and the process of generating a debugging interface. We also describe the runtime logging system and discuss how, in practice, Diagnosys supports debugging tasks. Section 5 evaluates our approach. Finally, Section 6 discusses related work, and Section 7 concludes.

Characterization of Safety Holes

In kernel programming, we consider a safety hole to be a fragment of kernel code that can cause the kernel to crash or hang if the code is executed in a context that does not respect some implicit preconditions. To understand the challenges posed by safety holes, we first consider some typical examples in Linux kernel internal API functions and the problems that these examples have caused, as reflected by Linux patches. Then, we present a methodology for identifying kinds of safety holes, and use this methodology to enumerate the kinds of safety holes considered in the rest of the paper.

Examples of safety holes

Because the Linux kernel does not define a precise internal API, we focus on the set of functions that are made available to dynamically loadable kernel modules using either EXPORT SYMBOL or EXPORT SYMBOL GPL. Dynamically loadable kernel modules provide a convenient means to develop new services, as they allow the service to be loaded into and removed from a running kernel for the testing of new service versions. We refer to kernel functions that are made available to such modules as kernel API functions.

Figure 1a shows an excerpt of the definition of the kernel API function skb put, which dereferences its first argument without first checking its value. Many kernel functions are written in this way, assuming that all arguments are valid. This code represents a safety hole, because the dereference is invalid if the corresponding argument is NULL. Since kernel code runs in a single protection domain, dereferencing an invalid pointer will crash the entire system. Such a fault occurred in Linux 2.6.18 in the file drivers/net/forcedepth.c. In the function nv loopback test, skb put is called with its skb argument being the result of calling dev alloc skb, which can be NULL. The fix, as implemented by the patch shown in Figure 1b, is to avoid calling skb put in this case. skb put remains unchanged. Figure 2a shows an excerpt of the definition of the kernel exported function open bdev exclusive, which returns a value constructed using the kernel function ERR PTR when an error is detected. Dereferencing such a value will crash the kernel. Thus, this return statement also represents a safety hole. Indeed, many allocation, initialization and copy functions may fail and return such a value, and leaving these values unchecked is a common fault. In Linux 2.6.32, in the file fs/btrfs/volumes.c, the function btrfs init new device called open bdev exclusive and compared the result to NULL before dereferencing the value. This test, however, does not prevent a kernel crash, because an ERR PTR value is different from NULL. Figure 2b shows the patch that was used to fix the fault. In the previous cases, the safety hole is apparent in the definition of a kernel exported function. A safety hole, however, may also be interprocedural, making the danger that it poses more difficult to spot. For example, as shown in Figure 3(a,b), the kernel exported function kmap, defined in arch/x86/mm/highmem 32.c, passes its argument to the function page zone via the macro PageHighMem, which in turn forwards the pointer, again without ensuring its validity, to the function page to nid. This function then dereferences it, unchecked. This safety hole resulted in a fault, which was fixed by the patch shown in Figure 3c.

Safety holes can also be found in the implementations of critical sections with locks. For example, between Linux 2.6.32 and 2.6.33, a bug was first introduced and then fixed in the nouveau drm driver for nVidia R cards, in which the ttm bo wait exported function was called by nouveau gem ioctl cpu prep without holding the bo lock. Since ttm bo wait attempts to release and then re-acquire that lock, as depicted in Figure 4(a), a subsequent call to another function, nouveau bo busy, which acquires the lock, hanged the machine. This bug was fixed by ensuring that the bo lock is held when invoking the ttm bo wait API function (cf. Figure 4(b)). The examples described above show (1) how safety holes lead to bugs that reach the mainline kernel, and (2) how safety holes involve various types of bugs. We now describe a methodology, based on our observations in these examples, for identifying types of safety holes systematically, by recasting a type of code fault as a collection of one or more types of safety holes. We then use this methodology to enumerate the types of safety holes considered in this paper.

Methodology

As illustrated by the bug fixes in Section 2.1, some fragments of code executed by kernel API functions, while themselves being correct, can provoke kernel crashes or hangs when the API function is used incorrectly. In the most obvious case, the service code passes to the API function some bad arguments or calls it from an inappropriate context (e.g., with a lock held or with interrupts disabled) causing an execution error in the core kernel: we refer to this kind of safety hole as an entry safety hole. In other cases, the kernel API function may return a value or return from a context that might not meet the expectations of the service code: we refer to this kind of safety hole as an exit safety hole. Such exit safety holes appear when, for example, the API function may return NULL rather than a pointer to a valid region of memory, or returns with a lock held or with interrupts turned off. In these cases the crash or hang may happen in the service code, with the API function that caused the problem no longer on the call stack. Figure 5 schematically represents the two families of entry and exit safety holes, by indicating where, in each case, the execution error occurs. In the figure, the box represents the definition of an API function, while the symbol ⊥ indicates the point of crash. In general, we observe that any bug type that involves multiple disjoint core fragments can lead to an entry or exit safety hole. An an example, consider Figure 6, based on the example of a bug involving a lock/unlock combination for defining a critical section. The middle of the figure represents correct code, with Lock followed by a corresponding Unlock. The left side of the figure represents the potential bug case. Within a known block of code, represented by the pair of right angles, a bug may occur if both elements of code are expected to be present, but one is missing, i.e., a Lock missing a subsequent Unlock, or an Unlock with no previous lock. On the right side of the figure, we consider how the relevant fragments of code can be intended to be split across an API function, represented by either of the shown right angles, and the service code that uses the API. The API function may end with a Lock, expecting the calling service to perform the corresponding Unlock, representing an exit safety hole, or it may begin with an Unlock, conversely representing an entry safety hole. Thus, a single possible bug type gives rise to as many kinds of entry and exit safety holes as there are ways to split the elements of code relevant to the bug type across the boundary between the API function and the service code.

Taxonomy

Safety hole kinds. Following our methodology, we can, in principle, derive entry and exit safety hole types from any fault type involving multiple fragments of code. As a first source of fault types, we consider those identified by Chou et al. in their 2001 empirical study of Linux code [START_REF] Chou | An empirical study of operating systems errors[END_REF]. We also refer to a more recent study by Palix et al. who revisited the study of Chou et al. in 2011 [41].

Table 1 details the different kinds of safety holes that were derived from these fault types, following the terminology of Palix et al. [START_REF] Palix | Faults in Linux: Ten years later[END_REF]. For each fault type, we split the possible fault code fragment into two parts and characterize the part that may be located inside the implementation of an API function f , thus identifying the possible entry and exit safety holes. We have enhanced some of the categories to take into account new kernel features. For example, in Linux kernel 2.6, ERR PTR, in addition to NULL, is widely used as an invalid pointer indicating errors. Thus, in the Null and INull categories, we have added ERR PTR as an invalid pointer.

For some categories of faults, however, we have not been able to derive interesting safety holes:

-NullRef (A pointer is dereferenced and then tested for being NULL.) seems meaningless as a safety hole. If the dereference fails, then the machine has crashed. If the dereference succeeds, this value will not cause the machine to crash. -Float (Do not use floating point in the kernel.) is a purely local property. Thus, it is not relevant to the interface between a service code and the kernel API functions. -Real (Do not leak memory by updating pointers with potentially NULL realloc return values.), in practice, only manifests itself as a direct assignment of the pre-existing pointer to the result of realloc, and thus it is also a purely local property. -Size (Allocate enough memory to hold the type for which you are allocating), in practice, is local to the definition of a function, as sizes are typically expressed in terms of sizeof, which is evaluated according to type information as defined in the current context. Thus, it is not Possible vs. certain safety holes. As a safety hole involves a fragment of code inside the definition of an API function, it belongs to one or more potential execution paths through that function.

Such an execution path may be possibly followed during a call to the API function, if the code involved in the safety hole is only executed on certain inputs or calling contexts, or it may be certainly followed, implying that the code involved in the safety hole is always reached when the function is called.

Figure 7 illustrates a combination of execution paths from an entry point (noted as ) of an API function to any of the different potential exit points (noted as ). The execution paths pass through different program points (noted as ) and split at some of these points (noted as ). This graph contains two safety-hole related potential crash points, indicated by colored boxes. The topmost one (orange/light grey) is labelled as possible, because only a portion of the execution paths through the function reach this code. The lower one (red/dark grey) is labelled as certain, because every execution of the function reaches this code. Of course, whether a crash occurs, depends on whether the implicit preconditions of the safety hole are satisfied. In the case of an exit safety hole, the potential crash depends on how the service uses the result of the API function. As this cannot be determined from analyzing the definition of the API function, we consider all exit safety holes to be possible. For more implementation details, we refer the reader to the thesis in [START_REF] Bissyandé | Contributions for improving debugging of kernel-level services in a monolithic operating system[END_REF]. To further understand the difficulties that can be caused by safety holes, we consider the problem of kernel debugging. Each of the examples presented in Section 2.1 could crash the kernel. When the kernel crashes, it generates an oops report, consisting of the reason for the crash, the values of some registers and a backtrace, listing the function calls pending on the stack. Using this information in debugging raises two issues: 1) the reliability of the provided information, and 2) the relevance of the provided information to the actual fault. Debugging kernel hangs raises further issues; if the hang is due to an infinite loop, the point at which an oops is finally generated may not be the same as the point that causes the loop not to terminate.

Reliability of kernel oops reports. Linux kernel backtraces suffer from the problem of stale pointers, either because the base pointer register is corrupted or because function return pointers appear on the stack, e.g., as function arguments or as meaningless data in the space allocated to uninitialized stack-allocated local variables. To illustrate this problem, we consider a crash occurring in the function btrfs init new device previously shown in Figure 2. The crash occurred because the kernel exported function open bdev exclusive returns an ERR PTR value in case of an error, while btrfs init new device expects that the value will be NULL. This caused a subsequent invalid pointer dereference.

To replay the crash, we installed a version of the btrfs module from just before the application of the patch. To cause open bdev exclusive to fail we first created and mounted a btrfs volume and then attempted to add to this volume a new device that was not yet created. This operation is handled by the btrfs ioctl add dev ioctl which calls btrfs init new device with the device path as an argument. This path value is then passed to open bdev exclusive which fails to locate the device and returns an ERR PTR value. Figure 8 shows an extract of the resulting oops report. Line 1 shows that the crash is due to an attempt to access an invalid memory address. Line 5 shows that the faulty operation occurred in the function btrfs initnew device, ostensibly during a call to btrfs ioctl add dev (line 8). Source files and line numbers can be obtained by applying the standard debugger gdb to the compiled module and to the compiled kernel.

This backtrace contains possibly stale pointers, as indicated by the ? symbol on lines 8 and 9. While btrfs ioctl add dev really does call btrfs init new device, so this seems likely to be a legitimate stack entry, this is not the case for memdup user. Since it cannot be known a priori whether a function annotated with ? is really stale, the service developer has to find and study the definitions of all of the functions starting from the top of the backtrace, until finding the reason for the crash, including the definitions of functions that may be completely unrelated to the problem. A goal of the kernel debugger kdb,1 which was merged into the mainline in Linux 2.6.35, was to improve the quality of backtraces. Nevertheless, some stale pointers remain. 2Relevance of kernel oops reports. A kernel oops backtrace only contains the instruction causing the crash and the sequence of function calls considered to be on the stack. The actual reason for a crash, however, may occur in previously executed code that is not represented. For the fault shown in Figure 2, the oops report mentions a dereference of the variable bdev in the function btrfs init new device, but the real source of the problem is at the initialization of bdev, to the result of calling open bdev exclusive. This call has returned and thus no longer appears on the stack. Such situations make debugging more difficult as the developer must thoroughly consult kernel and service source code to locate possibly relevant initialization code sites.

Kernel hangs. By default, the Linux kernel gives no feedback in the case of a kernel hang. It is possible, however, to configure the kernel such that it generates a panic when it detects no progress over a certain period of time. When the hang is due to an infinite loop, the backtrace resulting from the panic can occur anywhere within this loop, and thus the point of the panic may thus have no relation to the actual source of the problem.

Diagnosys

The goal of Diagnosys is to improve the quality of the information available when a crash or hang occurs as the result of a safety hole in a kernel internal API function. To this end, the Diagnosys approach involves three phases, as illustrated in Figure 9: 1. Identification of safety holes in kernel internal API functions and inference of the associated usage preconditions, using the static analysis tool SHAna. This phase is carried out only once by a kernel maintainer, for each new version of the mainline Linux kernel. 2. Automatic generation of a debugging interface using DIGen based on the inferred preconditions.

This phase is carried out by each service developer for each specific service under development.

It is transparently encapsulated in a script dmake that replaces the standard make command. 3. Testing service code with the support of the debugging interface and of the Diagnosys crash resilient logging system, CRELSys, that preserves runtime logs across boots. This phase is also carried out by the service developer. To get a benefit from Diagnosys, a small amount of investment is needed here from the developer, to learn how to interpret the log messages.

In this section we succinctly describe the design of SHAna, DIGen and CRELSys. Some implementation details are also provided. SHAna is a tool built on top of Coccinelle for identifying safety holes in kernel API functions and inferring their usage preconditions. Based on the safety hole descriptions, SHAna first searches the kernel code for occurrences of safety holes in the implementations of API functions and then computes the preconditions that must be satisfied for these safety holes to cause a kernel crash or hang. The analysis focuses on unsafe operations that occur in code that is in, or is reachable from, an API function. For each such occurrence, a backward analysis amounting to a simple version of Hoare logic [START_REF] Huth | Logic in Computer Science: Modelling and reasoning about systems[END_REF] produces the weakest liberal precondition to be satisfied such that the safety hole may cause a crash. This weakest precondition is computed for the entry point of the function, for entry safety holes, and for the exit points of the function, for exit safety holes.

Theory of precondition inference

Hoare logic [START_REF] Hoare | An axiomatic basis for computer programming[END_REF] is a formal system for reasoning about the correctness of computer programs. In particular this logic introduces the Hoare triple to describe how the execution of statements of an imperative program changes the state of the computation.

A Hoare triple (1) consists of two assertions, the precondition P and the postcondition Q, and a program S. Hoare logic states that: If the execution starts in a state where the precondition P is met, at the end of the program execution the postcondition is realized [START_REF] Frade | Verification conditions for source-level imperative programs[END_REF]. Consider the simple Hoare triple below (2) where the precondition x = y is true before the execution of the program. Once the program is executed, the post-condition is true; the value of y has not been changed, and is still equal to the initial value of x, but the value of x is 3 greater than it was previously.

{P }S{Q}

(1)

{x = y}x := x + 3{x = y + 3} (2)
This logic can be used to express function specifications, i.e., the contract between the implementation of a core API function and the client plug-in (the service code). In this case, the precondition represents the predicate that describes the condition on which the API function relies for correct operation. The postcondition on the other hand describes the condition that the API function establishes after correctly running. If some service code calls the API function after fulfilling the function's precondition, the function will execute to completion and when it terminates, the postcondition will be true.

Starting with a postcondition, the weakest precondition wp(S, Q) of S with respect to Q is defined by Equation 3, where the program S is allowed to be invoked in the most general condition P that would still lead to the realization of the postcondition Q.

P = wp(S, Q) ⇔ {P }S{Q} ∧ ∀P ′ , {P ′ }S{Q} ⇒ (P ′ ⇒ P ) (3)
Using a simplified version of this logic we infer the weakest preconditions of API functions that can trigger faults in the different kinds of safety holes. For ease of prototyping, we use the program matching tool Coccinelle [START_REF] Padioleau | Documenting and automating collateral evolutions in Linux device drivers[END_REF] to implement an interprocedural static analyzer3 that finds the safety holes and constructs the preconditions.

In our analysis, the postcondition is satisfied when the execution of the API function completes without leading to an execution error for entry safety holes and without returning invalid values or leaving a context that is unsafe for the execution of service code. As previously defined in Section 2.2, a precondition associated with an entry safety hole is classified as:

certain, if satisfaction of the precondition is guaranteed to result in a crash or hang within the execution of the kernel API function possible, if satisfaction of the precondition may cause a crash or hang on at least one possible execution path

The preconditions of exit safety holes are always classified as possible. The result of SHAna is a list mapping each kernel API function identified as containing safety holes to the associated preconditions.

Analysis process

The starting point of the analysis for identifying safety holes and inferring their preconditions is the definition of an API function. The analysis recognizes a kernel API function as one that is declared using EXPORT SYMBOL or EXPORT SYMBOL GPL. Table 2 provides a complete summary of the description of the safety holes for all categories of faults. The table also indicates for each category of safety hole, whether intraprocedural, interprocedural or no analysis is used.

In search scenarios that only require intraprocedural analysis, the analyzer scans the definition of the API function to identify code fragments that represent safety holes. For example, in searching for the various Lock and Intr entry safety holes, SHAna only looks for interrupt disabling operations in the kernel API function itself, because interrupt state flags should not be passed from one function to another [START_REF] Rubini | Linux Device Drivers[END_REF]. Performing only an intraprocedural analysis reduces the cost in cases where it is known in advance, due to specific properties of the code, that a more precise analysis will not give any further information.

In the case of interprocedural analysis, SHAna starts from the definition of an API function and iteratively analyzes all called functions. For example, in searching for Null entry safety holes, SHAna searches through both the kernel API function itself and all called functions that receive a parameter of the kernel API function as an argument to find unchecked dereferences.

In a few cases, we do not collect safety holes, because the condition seems too common and an error seems relatively unlikely. For example, according to Table 2, collecting Free entry safety holes would entail collecting every function that dereferences a pointer argument, as there is no way to check whether a value has been freed. This does not seem useful in practice, and thus SHAna does not collect safety holes in this case. In other cases, however, we augment the scope of the categories of safety holes by considering new fault kinds that may arise at the boundary of kernel API functions. For example, the fault types considered by Chou et al. [START_REF] Chou | An empirical study of operating systems errors[END_REF] and later by Palix et al. [START_REF] Palix | Faults in Linux: Ten years later[END_REF] only include double-locks and deadlocks in the Lock category. Nevertheless, we have seen in mainline bug fixes that attempting to unlock a lock that has not been acquired, or that has been released (double-unlock), is a damaging fault (cf. Figure 4). Thus, we also implement an analysis to search for this kind of safety hole. Finally, for the Null category of safety holes, SHAna furthermore includes unchecked dereferences of values that in some way depend on the value of an unchecked parameter, and for which the failure caused by the dereference may be hard to diagnose by the service developer. [START_REF] Chou | An empirical study of operating systems errors[END_REF][START_REF] Palix | Faults in Linux: Ten years later[END_REF]. f refers to the API function. The "analysis type" column indicates whether the analysis is interprocedural or intraprocedural

We now discuss the specific strategies that we have implemented for searching for occurrences of the various categories of safety holes. Table 3 summarizes examples of conditions that enable the safety holes to manifest themselves into faults. SHAna bases its analysis on such enabling conditions.

Block: To identify API functions that contain Block entry safety holes, SHAna performs an interprocedural analysis, searching for functions that may block. We focus on the common case of functions that are allowed to block during memory allocations. We recognize such functions as those that contain a function call having GFP KERNEL as an argument, as this argument allows the basic kernel memory functions to block, if needed, to wait for more memory to become available.

A Block exit safety hole amounts to taking a lock before exiting the API function. This condition is the same as the one indicating a Lock/Intr/LockIntr exit safety hole. The associated analysis is described in the Lock/Intr/LockIntr section below.

IsNull/Null: To identify API functions with IsNull/Null safety holes, SHAna performs an interprocedural analysis that detects unsafe dereferences of pointer-typed parameters. The search identifies dereferences that are performed prior to any validity check in one or all of the control-flow paths. We have also augmented this search strategy by detecting, in the implementation of API To collect API functions that exhibit an IsNull/Null exit safety hole, SHAna interprocedurally searches for functions that may return an invalid pointer. We recognize both NULL values and ERR PTR values as invalid pointers.

Var: To identify API functions that implement Var entry safety holes, SHAna performs an intraprocedural analysis for detecting array allocations with sizes depending on a parameter value, whether it is an integer parameter value or an integer derived from a parameter.

To collect API functions with a Var exit safety hole, SHAna searches for functions that return large constant values. We parameterize SHAna to report constant integer values larger than 128.

Range: To identify API functions that exhibit Range entry safety holes, SHAna performs an intraprocedural analysis that follows the use of API function parameters to identify places where one unchecked parameter is used to compute an array index.

To collect API functions with a Range exit safety hole, SHAna performs an interprocedural analysis for identifying functions that return a value obtained from user-level. The search strategy relies on a list of names of Linux kernel primitives, namely getuser, memcpy fromfs, and copy from user, that give access to user data.

Lock/Intr/LockIntr: To identify API functions that implement a Lock/Intr/LockIntr entry safety hole, SHAna performs an intraprocedural analysis, searching for functions that disable interrupts or acquire locks that are derived from parameters. The search strategy relies on a set of commonly used functions for locking and interrupt management. 5 We have furthermore augmented this category of safety holes by identifying API functions that attempt to release locks that they have not acquired themselves. This accounts for a type of real-world usage bug6 that was not considered by Chou et al. Indeed, while many Linux critical sections both begin and end within the body of a single function, some span function boundaries, implying that some functions expect to be called within a critical section. When the calling code fails to respect this condition, deadlock may ensue.

To collect API functions that expose a Lock/Intr/LockIntr exit safety hole, SHAna follows the same search strategy as for Lock/Intr/LockIntr entry safety hole, relying on the same locking and interrupt management functions, but inverting the roles of the locking and unlocking functions.

Free: To identify API functions that exhibit a Free entry safety hole, we consider that any pointer-valued argument to an API function may refer to a freed memory block, thus making any dereference of a pointer-typed parameter a risky operation. Nonetheless, because practically all API functions dereference their parameters, we do not perform precondition inference for this sub-category.

To collect API functions that implement the Free exit safety hole, SHAna performs an interprocedural analysis for identifying code places where an API function argument is passed to the kernel memory release function kfree.

Certification Process

As is standard in static analysis, SHAna makes some approximations [START_REF] Dillig | Reasoning about the unknown in static analysis[END_REF] to ensure termination and scalability. These approximations may result in false positives, i.e., reported safety holes that cannot actually lead to a crash or hang. Using such false positives in the inference of API function usage preconditions may cause two important issues:

1. Inferring unnecessary usage preconditions can lead to excessive checking at runtime in the Diagnosys approach, which, in turn, will degrade the performance.

2. False positives may also lead to the generation of useless runtime warnings, that will clutter the debug log with messages that are not relevant to any encountered crash or hang.

To address the problem of false positives, our approach requires that a kernel maintainer study the inferred safety holes to discard those that represent false positives. This step is referred to as certification and is performed by a kernel maintainer, who is expected to be knowledgeable about the internals of core kernel code. The certification process is only necessary once for each version of the kernel.

To reduce the workload, SHAna maintains in a database information about safety holes across OS versions, so that the kernel maintainer need only validate reported safety holes in those functions, including functions called by API functions, whose definitions have changed. To ease the management of this information, we have built a certification helper utility that, given data from a static analysis, automatically selects the analysis results related to functions whose definitions have changed, and thus need to be checked. When no certification has been performed the utility shows all results and records the result of manual checking. In a subsequent certification process, e.g., for a later release of the kernel, the certification utility first checks whether manually checked analysis results need to be revisited.

DIGen: Debugging Interface Generator

DIGen is a tool that builds on the results of SHAna to introduce runtime checks and monitoring into the execution of kernel-level services. The goal of DIGen is to create log messages that reflect the usage preconditions of kernel API functions, to keep track of any violation of these preconditions by service code.

Based on the results of SHAna, DIGen generates a debugging interface as a collection of wrapper functions that augment the definitions of kernel API functions with the necessary checks and calls to logging primitives, to detect and record violations of safety hole preconditions. Ideally, the kernel maintainer who runs SHAna could also generate a single debugging interface for the entire kernel that could be used by all service developers. Unfortunately, many kernel source files target specific hardware platforms, and thus have mutually incompatible header file dependencies, making it impossible to compile such a debugging interface. Accordingly, we put the interface generation process into the hands of the service developers, who generate an interface specific to their service. Because the functions invoked by a single service can necessarily be compiled together, this approach avoids all compilation difficulties, while producing a debugging interface that is sufficient for an individual service's needs. We now describe the generation of a debugging interface and how it is integrated into a service under development.

Generating a debugging interface

The first step in the generation of a debugging interface for a given kernel-level service (e.g., a device driver) is to determine the API functions that are actually called by the service code. A reliable way to identify such functions is to analyze the object code of the kernel-level service to look for references to functions whose implementation is not included in the object code. DIGen thus disassembles the object code, using the GNU user-level command objdump, and recovers information about the symbol table entries of the compiled loadable kernel module (.ko file). Figure 10(a) provides an example of a toy Linux kernel module that tests the latency of a primitive from the Ftrace library [START_REF] Rostedt | Debugging the kernel using ftrace[END_REF]. Figure 10(b) shows an excerpt of the symbol table entries obtained from the object code of the module.

In each row of the symbol table,7 the first field is a number representing the symbol value (i.e., an address). The next field is a set of characters and spaces indicating the flag bits that are set on the symbol (e.g., l represents local, g represents global, u represents global unique, etc.). Next, is the section with which the symbol is associated. When this section is not connected to any other section, i.e., is absolute, the field contains instead *ABS*. However, if the section is referenced in the object file but not defined there, the field contains *UND* (undefined). In our example, the symbols printk, mcount and trace bprintk, which are defined in the core kernel and used in the tested module, are marked as undefined (lines 11, 13-14.). Overall, the symbols listed by disassembling the object code not only include symbols that are apparent in the service code (e.g., printk), but also include symbols that are called from inside core kernel header files (e.g., cleanup module) or that were integrated by macro expansion (e.g., trace bprintk is in the expansion of trace printk). The list of undefined symbols is then checked against the list of kernel API functions. All "undefined" functions in the service code, that are known to be kernel API functions, are listed by DIGen for the next step in the generation of a debugging interface.

For each kernel API function that is used in the service and for which SHAna identified at least one safety hole, DIGen generates a wrapper function. The general structure of such a wrapper function is shown in Figure 11. Based on the argument values, the wrapper first checks each entry safety-hole precondition (line 4) and then, if the precondition is not satisfied, logs a message indicating the violation. This message includes the safety hole category, which specifies the kind of safety hole and an annotation expressing whether the violation is CERTAIN or POSSIBLE (line 5), as defined in Section 2.2. The wrapper then calls the original function. If the original function has a return value, this value is stored in a local variable, __ret, and then the preconditions on any exit safety holes are checked based on this information and on the context (lines 9-10). As exit safety holes are always possible, exit safety hole log messages are simply annotated with EXIT. Finally, the return value, if any, of the original function is returned as the result (line 12).

For performance reasons, Diagnosys does not log formatted strings in kernel memory. Instead, it logs integers representing unique information identifiers that are decoded and translated onthe-fly during log retrieval. Once formatted, a typical Diagnosys log line contains the timestamp of the log, the source file and line number where the unsafe call was performed, the name of the API function, the category of the safety hole, and possibly the name of a relevant argument or an unsafe return value.

Integrating a debugging interface into a service

For each generated wrapper function, DIGen also generates a #define macro (Figure 11, line 14) that, upon expansion, will replace in the service code all calls to the kernel API function with To facilitate the integration of a debugging interface into a kernel-level service under test, Diagnosys provides an automated script, dmake. This script manages the generation of the interface in four steps: dmake (1) compiles the original service code, (2) identifies the kernel API functions referenced by the resulting object files, (3) generates an interface dedicated to these functions, and (4) recompiles the service with the interface included. The resulting compiled kernel module object thus produced is ready for loading into a running kernel for execution tests.

CRELSys: Crash-Resilient & Efficient Logging System

To be able to use Diagnosys, the service developer must use a version of the Linux kernel that includes the Diagnosys runtime system, CRELSys. CRELSys is implemented as a kernel patch, that we have implemented for Linux 2.6.32, that extends the kernel with a crash resilient logging system. The patch additionally configures the kernel to send all crashes and hangs (Linux soft and hard lockups) to the kernel panic function, which the patch extends to reboot into a special crash kernel. Finally, Diagnosys provides a tool that can be run from user space to install a copy of the CRELSys patched kernel as a crash kernel, initialize the reserved log buffer, and retrieve and format the logs. We describe first how the logs are stored in the kernel memory and then how they are preserved upon a crash.

Storing logs in kernel memory

When using a Diagnosys-enabled kernel, the service developers test their code as usual. During service execution, if a wrapper function detects a safety hole for which the precondition is violated, the wrapper logs information about the safety hole in a reserved area of memory, annotated with a timestamp and including the memory address of the call site.

To reserve memory for Diagnosys runtime logs, we leverage the kernel memmap boot parameters, 8 which instruct the kernel to completely ignore an area of memory during its own allocations and use. Thus, CRELSys, which is aware of the location of this memory area, can use it without any risk of conflict with other parts of the kernel. CRELSys manages this reserved area of memory through a fixed-size ring buffer. When the ring buffer fills up, adding another log element overwrites the first one. The use of this reserved area of memory allows information to be maintained without involving the file system, which is slow and is not intended to be used by kernel-level code [START_REF] Kroah-Hartman | Driving me nuts -things you should never do in the kernel[END_REF]. The use of a ring buffer limits the amount of memory consumed, even if many log messages are generated. Indeed, our experience in using Diagnosys shows that debugging tasks usually only need to take into account recent events, so the information retained in the ring buffer is sufficient.

Preserving logs across a system reboot

On a kernel crash or hang, CRELSys redirects the execution into a panic state where, using a Kexec-based mechanism [START_REF] Nellitheertha | Reboot Linux faster using kexec[END_REF], the system is rebooted into a new instance of the Diagnosys-enabled kernel. Kexec is a mechanism of the Linux kernel that allows booting of a new kernel over the currently running one without resetting hardware (including RAM memory) and by skipping the bootloader phase to gain speed. The use of Kexec allows the new kernel to sit in the same place in memory as the currently running one. Because the reboot is performed without reinitializing memory, and the same memmap boot parameters are provided, the Kexec mechanism ensures that the accumulated Diagnosys log is still available. The service developer may then access the log messages after the reboot.

To allow the service developer to access the log messages from user space, we have implemented a character device driver that transfers data directly to and from a user process. The driver sets up a pseudo device to accept user commands (e.g., cat /dev/crelsys) and produce the log messages that were stored in kernel memory. The messages are made available in the order in which they were generated. When a crash occurs, the Diagnosys runtime system also inserts the kernel stack trace into the Diagnosys log before rebooting.

Assessment

In designing Diagnosys, we have chosen to focus on the interface between the service code and the kernel. We first study the effect of this choice qualitatively, by considering the process of debugging some of the real-life bug examples presented in Section 2.1. We then assess the number of safety holes in this interface and study their past impact on kernel robustness, as evidenced by commits to the Linux kernel. Then, we assess the coverage of Diagnosys with respect to the possible crashes and hangs that are triggered by misuse of the interface between the service code and the kernel, and show that the Diagnosys log messages allow the service developer to find the cause of a crash or hang more rapidly than when relying on a kernel backtrace alone. Then, we show that Diagnosys incurs a sufficiently low runtime overhead to be embedded in a service, up to the early deployment phase. Finally, we show that the certification of static analysis results is affordable.

Our experiments use code from Linux 2.6.32, which is used in the 10.04 Long Term Support version of Ubuntu R , in Red Hat Enterprise Linux 6, in Oracle Linux, etc. Our performance experiments are carried out on a Dell 2.40 GHz Intel R Core TM 2 Duo with 3.9 GB of RAM. Unless otherwise indicated, the OS is running a Linux 2.6.32 kernel that has been modified to support CRELSys. 1MB is reserved for CRELSys' crash-resilient log buffer.

Kernel Debugging with Diagnosys

We now describe some debugging experiments that we have performed to highlight the benefits of the Diagnosys approach. In particular, we investigate how Diagnosys solves the issues of unreliable backtraces and the questionable relevance of the information found in crash reports that make kernel debugging difficult. To this end, we replay a kernel crash from the btrfs file system, previously presented in Figure 2. To account for other common failures, we also replay a hang reported in the kernel commit logs, previously presented in Figure 4.

Replaying a kernel crash

Kernel crashes are the most common type of OS failures. When they occur, developers must identify the origin and the cause of the failure based on any generated oops reports that they manage to capture. As an example of a kernel crash, we again consider the btrfs example used for illustration in Section 2.1. Figure 12 shows the bug fix patch that was introduced in mainline code to fix the usage of the open bdev exclusive API function.

1 commit 7f59203abeaf18bf3497b308891f95a4489810ad 2 bdev = open bdev exclusive(. . .); 3 -if (!bdev) 4 - return -EIO; 5 + if (IS ERR(bdev)) 6 +
return PTR ERR(bdev);

Fig. 12: Excerpt of a bug fix patch in btrfs file system

For the purpose of this experiment, we have recovered and installed a version of the btrfs file system, from right before the relevant patch was applied. The goal of the experiment was then to execute the code so that a fault would manifest itself to reflect the need for this patch. To cause open bdev exclusive to fail, we first created and mounted a btrfs volume and then attempted to add to this volume a new device that was not yet created. As discussed in Section 2.1, the open bdev exclusive API function then returns ERR PTR, after failing to locate the device to open.

Figure 13 shows the crash report that we have collected from the kernel console at the end of the above experiment. Our previous study of this report, in Section 3, in the context of debugging, showed that the source of the problem was not readily available in the backtrace. Specifically, the backtrace contains only stale pointers, making it challenging to pinpoint the origin of the crash, and the backtrace does not contain information about the root cause of the crash.

We have replayed the same execution scenario when using Diagnosys. Figure 14 shows the last line added to the Diagnosys log before the crash, which is the line that the developer is likely to consult first. This line shows that the function open bdev exclusive activated an INull exit safety hole by returning ERR PTR. It also reports the runtime timestamp and the call site where the safety hole was violated. Combining this information with the information about the crash site in the oops report and the service source code shows that the problem is the inadequate error handling code after open bdev exclusive. Using Diagnosys, service developers can focus on their own code, and do not have to probe the kernel source or object code to obtain the needed information.

Replaying a kernel hang

Kernel hangs are notoriously hard to debug9 as they can simply freeze the computer leaving the developer without any information on the ongoing failure. Alternatively, the kernel can be configured to panic after a certain delay. Nevertheless, this panic may occur long after the actual fault, and thus may produce a backtrace that is hard to correlate to the actual source of the problem. In such situations, Diagnosys, which records information about previous potentially dangerous operations, can aid service developers. To illustrate the benefits of Diagnosys, we replay a bug in the the nouveau drm nVidia R graphics card driver that was discussed in Section 2.1.

Just before the release of Linux 2.6.33, the nouveau drm nVidia R graphics card driver contained a hang resulting from the use of the kernel API function ttm bo wait. This function exhibits a Lock entry safety hole and a Lock exit safety hole, as it first unlocks and then relocks a lock received via its first argument. The nouveau drm driver called this function without holding this lock, hanging the kernel. Fig. 13: Oops report following a btrfs ERR PTR crash in Linux 2.6.32

[4294934950]|@/var/diagnosys/tests/my btrfs/volumes.c:1441|open bdev exclusive|INULL(EXITED)|ERR PTR| Fig. 14: Last Diagnosys log line in the execution of btrfs When we do not use the Diagnosys debugging interface, the hang leaves the developer with little information. Using Diagnosys, when the hang is detected, it causes a kernel panic, which in turn causes a reboot with CRELSys that preserves the log messages. In Figure 15, the last line of the Diagnosys log shows that ttm bo wait has been called without the expected lock held. The log message indicates the type of safety hole, the place of the offending call to the API function and the lock that needs to acquired to avoid the failure. Correlating the information provided by the Diagnosys log message with the source code suggests taking the lock before the call and releasing it after the call, as shown in the Linux patch in Figure 16. This patch reflects the fix that was ultimately made in the mainline code.

Opportunities for Diagnosys

To understand the degree of opportunity for Diagnosys, we first investigate the properties of the stability of the Linux kernel-module interface, and then we consider the prevalence of safety holes in the API functions of this interface. Finally, we estimate the likely relevance of the APIs containing safety holes to potential kernel services.

We first study the evolution of the kernel API of exported functions to highlight how safety holes can be easily pass under the radar of service developers. Figure 17 presents the number of API functions exported by versions of the Linux kernel released over the course of three years (December 2008-January 2011). The graph distinguishes between the API functions already exported in the first considered version, Linux 2.6.28, and the API functions added or modified since then. The results show that the number of exported API functions has been steadily increasing. For example, Linux 2.6.37 exports 224 more API functions than Linux 2.6.36. The results also show that the set of exported API functions continuously changes [START_REF] Kroah-Hartman | The Linux kernel driver interface (all your questions answered and then some[END_REF]. Indeed, over 3,000 (25% of all) API functions present in 2.6.37 were not available in 2.6.28, while over 1,000 (10% of all) API functions present in 2.6.28 have disappeared. In addition, over 3,000 (33% of all) API functions present in 2.6.28 have been modified in 2.6.32. These changes make it difficult for service developers to keep up. Furthermore, we have found that only a small number (15%) of API functions exported by the Linux kernel are documented (Section 9 of the Linux "man" pages), and we have found that the amount of documentation of the API functions of a given release does not significantly improve over time. Fig. 17: Evolution in the number of Linux kernel exported API functions (baseline Linux 2.6.28)

We now investigate how widespread are the safety hole types presented in Section 2.2 (p. 5). Table 4 summarizes, for each kind of safety hole, the number of API functions exported in Linux 2.6.32 that SHAna identifies as containing at least one occurrence of that kind of safety hole. In all, SHAna reports 22,932 safety holes in 7,497 API functions. The most frequently occurring kinds are IsNull/Null , Lock/Intr/LockIntr and Block . Over 7,000 API functions process pointertyped parameters without checking their validity. More than 94% of these functions perform unsafe dereferences directly within the body of their definition, while 5% forward the parameter value to other functions that unsafely use the value with no prior check. In the Lock/Intr/LockIntr entry sub-category, 98% of the over 800 collected functions try to acquire a lock that has been transmitted to them via a parameter, without first making sure that they do not already hold it. The remaining 2% assume that the transmitted mutexes or spinlocks are already held in the calling context and unsafely attempt to release them. Table 4: Prevalence of safety holes in Linux 2.6.32

Finally, we estimate the utility of the kernel API functions to new services, by considering the number of calls to these functions within the kernel code itself. In the 147,403 call sites across the entire kernel source code where API functions are used, half invoke a function containing a known safety hole. We have grouped all functions by category of safety hole that they contain, and computed the median number of calls to functions in each category. Depending on the kind of safety hole, the median number of calls to functions containing an entry safety hole ranges from 3 to 9, while the median number of calls to functions containing an exit safety hole ranges from 8 to 20. This suggests that the kernel API functions containing safety holes are likely to be useful to new services.

Impact of safety holes on code quality

We next investigate whether API function safety holes are effectively dangerous in kernel programming, i.e., (1) if programmers write programs with bugs that are related to the presence of safety holes in API functions, and (2) if the percentage of those bugs is significant, as compared to the overall set of bugs related to the usage of API functions.

To assess the impact of the identified safety holes over the course of the development of Linux, we have searched through the commit logs of the history of Linux 2.610 to identify patches where the commit log mentions the kernel API functions exported in Linux 2.6.32, omitting those commits in which the function name is used as a common word (e.g., "sort", "panic", etc.), to limit the number of false positives during manual processing. We have then manually reviewed these patches to identify those that are actually related to the usage of API functions, and exclude, e.g., those that affect only an API function's definition. Finally, from these relevant patches, we identify those for which the bug fix was made to account for a usage precondition as defined by SHAna. As shown in Table 5, 267 out of 703, i.e., 38%, of the usage defects are related to our categories of safety holes.

Quantitative improvement in debuggability

To be useful, Diagnosys must cover a high percentage of the misuses of kernel API functions. We first evaluate this, by artificially creating and activating misuses of API functions in kernel services and measuring how many are trapped by Diagnosys. Additionally, Diagnosys must be able to produce log messages that ease the debugging process. We then evaluate the debugging Total number of commits in Linux 2.6 278,078

Commits in any way related to exported functions 11,294

Commits related to the usage of exported functions 703

Commits related to the categorized safety holes 267

Table 5: Linux kernel bug fix commits effort, in terms of the number of files and functions that have to be studied to identify the cause of a crash, with and without Diagnosys.

Our experiments involve a number of commonly used kinds of services: networking code, USB drivers, multimedia drivers, and file systems. Services of these kinds make up over a third of the Linux 2.6.32 source code. We have selected a range of services that run on our test hardware. Table 6 presents those services along with the number of API functions exhibiting safety holes that they use.

Coverage of Diagnosys

To determine the coverage of Diagnosys, we assess the number of false negatives of SHAna, i.e., the set of safety holes that can lead to faults in practice but are not identified by SHAna. For this, we first mutate existing services so as to artificially create bugs. Then, we inject faults at run-time to cause the mutation to trigger actual crashes across the execution of our test services.

Fault model. The largest percentage of our identified safety holes are related to NULL and ERR PTR dereferences, and so we focus on these safety holes in our fault injection study. To devise a fault model, we consider how it can happen that such values are manipulated by kernel code. One prominent source of NULL and ERR PTR values is to indicate the failure of some sort of allocation. Robust kernel code checks for these values and aborts the ongoing computation. Nevertheless, omission of these tests is common. For example, in Linux 2.6.32, for the standard kernel memory allocation functions kmalloc, kzalloc, and kcalloc, over 8% of the calls that may fail 11 do not test the result before dereferencing the returned value or passing the returned value to another function.

Based on these observations, our fault injection experiments focus on missing NULL and ERR PTR tests in the service code. Our mutations remove such tests from the service code, one by one, and use the failslab feature of the Linux fault injection infrastructure [START_REF] Corbet | Injecting faults into the kernel[END_REF] within the initialization of the tested value to inject failures into the execution of any call to a basic memory allocation function that this initialization involves. Because the initialization can invoke basic memory allocation functions multiple times, a single mutation experiment may involve multiple injected faults.

Results. Our fault-injection experiments have a number of possible results. One is that there is no observable effect. This can occur when the code initializing the tested variable does not involve a memory allocation, when the effect of the failure of the memory allocation is confined within the kernel code and does not affect the service, or when the safety hole is possible and is not encountered in the actual execution. Another possible result is that there is a crash, but there is no information relevant to the cause of the crash in the Diagnosys log. In this case, either the information has been overwritten in the ring buffer or SHAna has not detected the safety hole, representing a false negative. The final possible result is that there is a crash and information related to the crash is found in the Diagnosys log, representing a success for Diagnosys. In this latter case, we can further consider the position of the information relevant to the crash in the Diagnosys log. It is most helpful for the developer if this information is in the most recent entry before the crash occurred, as this position is easily identifiable.

Table 7 presents the fault injection results for 10 services implemented as kernel modules. Overall, we have performed 555 mutations. For each mutation, we have exercised the various execution paths of the affected module. 56% of the experiments have resulted in a service crash. After reboot, in 90% of the crash cases, the log contained information relevant to the origin of the defect. The table also distinguishes between cases where this information is at the last position in the log buffer and the cases where other information that is irrelevant to the crash was logged subsequently. As a metric of debuggability we use the ratio between the number of crashes for which the log contained information in the last position, and the total number of crashes. On average, Diagnosys has improved the debuggability of the service by 86%. In one case, the improvement is as low as 66%, but there are very few mutation sites in this code. Ease of debugging In a traditional Linux kernel debugging context, a developer, provided with an oops report containing a backtrace and debugging tools that can translate stack entries into file names and line numbers, typically starts from the point of the crash, visiting all files and caller functions until the origin of the crash is localized. When the reason for the crash is in the service, but the actual crash occurs deep within the kernel, the number of functions and files to visit can be large.

To study ease of debugging quantitatively, we have considered 199 of the mutations performed in our coverage tests that lead to crashes, from btusb, nfs, and isofs. We also consider 31 mutations in nfs code that add statements for arbitrarily acquiring and releasing locks in services in order to provoke kernel hangs, focusing on locks that are passed between functions, as they can trigger safety holes in core kernel code. This results in 230 oops reports.

We have compared the 230 oops reports with the corresponding Diagnosys logs. In 92% of these crashes, the Diagnosys log contains information on the origin of the fault. For those cases, debugging with the oops report alone required consulting 1 to 14 functions, including on average one possibly stale pointer, in up to 4 different files distributed across kernel and service code. In 73% of the cases for which the Diagnosys log contains relevant information, we find that using Diagnosys reduces by at least 50% the number of files and functions to consult. In 19% of the cases for which the Diagnosys log contains relevant information, the crash occurred in the same file as the mutation, but the Diagnosys log made it possible to more readily pinpoint the fault by providing line numbers that are closer to the mutation site.

Finally, we consider the impact of stale pointers on the debugging process. The considered backtraces contain an average of 5 entries that are marked as possibly stale, of which on average one appears between the entry indicating the point of crash and the entry of the function where the mutation was performed. We have furthermore assessed the improvement brought by kdb, and established that its backtraces contain fewer unreliable entries, but still include 2 on average.

Our assessment has also shown that kernel backtraces can miss functions, which can be attributed, in some cases, to tail call optimizations. Such corrupted stack traces can then adversely affect debugging.

Service execution overhead

The testing of preconditions and logging introduced by a Diagnosys wrapper incurs a performance overhead on the execution of a kernel-level service. This overhead must be sufficiently small to avoid interfering with the normal service execution. In this section, we evaluate the overheads introduced by the primitives used by Diagnosys to test preconditions, and investigate at a macroscopic level the impact of Diagnosys on service performance.

Penalties introduced by Diagnosys primitives

To measure the execution time of the Diagnosys precondition checking and logging operations, we have used the Klogger framework [START_REF] Etsion | Fine grained kernel logging with KLogger: experience and insights[END_REF], 12 a state-of-the-art tool for performing fine grained logging of kernel operations. We also compare the execution time of a call to an exported API function having an empty body to that of a call to an exported API function containing a single precondition test. Each experimental test is run 10 times, and we compute the median value and standard deviation. Table 8 summarizes the overhead for one instance of each of the types of validity tests performed by a Diagnosys debugging interface. The observed overhead varies between 1.35% and 11.04%. [START_REF] Rostedt | Debugging the kernel using ftrace[END_REF] optimizes the logging process by deferring formatting from tracing time to output time. In Diagnosys, string formatting is not needed as the log message is generated at compile-time and is encoded as a series of integers that uniquely identify an API function, a safety hole type, etc. Diagnosys' logging primitive is thus 1.3x faster than Ftrace's trace printk, and 5x faster than printk. In Diagnosys, the time-consuming processing tasks are performed in user space, after a reboot when the service developer attempts to display the log messages.

Impact of Diagnosys on service performance

To understand the global performance overhead induced by the Diagnosys approach, we tested various real-world kernel services with and without a generated debugging interface.

Network driver performance. Our first test scenario involves a Gigabit Ethernet device that requires both low latency and high throughput to guarantee high performance. We evaluated the impact of a Diagnosys debugging interface by exercising the e1000e Linux device driver using the TCP STREAM, UDP STREAM and UDP RR tests from the netperf benchmark [START_REF] Jones | Netperf: A network performance benchmark[END_REF]. For these experiments, the netperf utility was configured to report results accurate to 5% with 99% confidence. Table 10 summarizes the performance and CPU overhead for the e1000e driver when it is run without and with a debugging interface. The debugging interface only reduces the throughput by between 0.4% and 6.4%, and increases the CPU utilization by between 0.4% and 10%. Nevertheless, while small, the existence of this overhead suggests why kernel developers would not want to systematically implement API functions such that they always perform all of these checks. This shows the need for a pluggable debugging interface dedicated to a service under development, as provided by Diagnosys. File system performance. Our second test scenario involves the NFS file system, whose implementation uses about 200 exported functions exhibiting safety holes. The experiment consists of sequential read, sequential write/rewrite and random seek phases based on patterns generated by the Bonnie benchmark [START_REF] Bray | The Bonnie file system benchmark[END_REF]. For this experiment, the client and server run on the same machine, connected using a network loopback interface, to eliminate the network transmission time. During a run of this benchmark with a debugging interface integrated into the NFS file system, we have recorded over 48,000,000 calls to the interface wrapper functions to write and read 8G of data.

As shown in Table 11, for data transfers of only one character, amounting to 1 byte, the overhead can be significant, of up to 67%. For block reads and writes, however, the overhead is only up to 17%, and for random seeks and sequential rewrites it is under 3%. Although SHAna only needs to be run once per kernel release, the number of results that it returns still makes certification of its results potentially very expensive. Diagnosys includes several techniques to reduce the amount of certification needed.

Highlighting likely false positives. In practice, a major source of false positives is when multiple definitions are provided for a given function, selectable by different, incompatible configuration options. In this case, interprocedural analysis can detect a safety hole that involves the interaction between two definitions that cannot coexist in an actual kernel. When SHAna detects that this is a possibility, due to the existence of multiple definitions of a called function, it annotates the derived safety holes as potential false positives. SHAna also provides information about the file in which the function instance inducing the safety hole is defined. Of the 22,940 safety holes reported by SHAna for Linux 2.6.32, SHAna itself annotated 465 (2%) as potential false positives, because of the ambiguity of the identification of called functions during interprocedural analysis. Since the Linux kernel provides different definitions of some functions for different architectures, these different definitions may exhibit different safety holes, and therefore results with respect to such functions require thorough validation. At a rate of about 5 minutes per safety hole, we estimate that this certification requires about a week of work (38 hours). Of the 465 potential safety holes, we have found that 405 (87%) are actual false positives.

We have also manually reviewed all of the other safety holes reported by SHAna for Linux 2.6.32. Among the reported safety holes that were not annotated as potential false positives during the analysis, we have identified some cases for which misuse seems very unlikely. For example, some lock-related exported functions such as unlock rename clearly indicate their purpose in their name. Similarly, clk get rate may return a large integer, but it seems unlikely that a developer would use this integer to declare the size of an array. We have found 9 such false positives in Linux 2.6.32. Most of the associated functions are called fewer than 5 times, with the most frequently used, clk get rate, being called 144 times. Thus, given the small rate of these safety holes and the low usage of the associated functions, we consider that it is sufficient for the kernel maintainer to manually check only the safety holes that are actually annotated as potential false positives by SHAna.

Preserving certification information across kernel versions. To further reduce the certification overhead, SHAna maintains information about safety holes across OS versions, so that the kernel maintainer need only check reported safety holes in those functions whose definitions have changed. To demonstrate the potential benefit of this information, we have also checked the safety holes that SHAna has annotated as potential false positives in 5 versions that were released after Linux 2.6.32. As shown in Figure 18, the burden on the maintainer is significantly reduced when data from a previous certification are available. Between two certification processes, the workload can drop by 50 to 95%, often to around a day or less, depending on the amount of time elapsed since the release of the previously certified version.

It may be the case that the maintainer is not available to run SHAna and perform the certification for every release. The blue dashed line in Figure 18 shows that even performing a certification In assessing the certification overhead, we have only considered the costs of certifying the results from the mainline kernel. In practice, most users do not use the mainline kernel, but instead one prepared for a particular Linux distribution, such as Debian or Fedora. While such a kernel may diverge slightly from the mainline, the differences are unlikely to affect the kernel API. Furthermore, a service that should ultimately be integrated into the mainline kernel must be developed against the mainline kernel's API.

Related work

In the last decade, studies have shown that kernel-level services, in particular device drivers, are responsible for the majority of OS crashes. Ganapathi et al. have found that 65% of all Windows XP crashes are due to device drivers [START_REF] Ganapathi | Windows XP kernel crash analysis[END_REF]. Ten years ago, Chou et al. found that the fault rate in Linux drivers was 3-7 times higher than that of other parts of the kernel [START_REF] Chou | An empirical study of operating systems errors[END_REF]. Palix et al. have shown that while this error rate is decreasing, Linux drivers still contain many defects [START_REF] Palix | Tracking code patterns over multiple software versions with herodotos[END_REF]. They have also found that file systems have recently had a high fault rate, indeed even higher than that of drivers. More generally on software code, empirical studies show that software bugs are becoming pervasive, specially in large projects with large code base and large development teams [START_REF] Bissyandé | Got issues? who cares about it? a large scale investigation of issue trackers from github[END_REF], for all programming languages [START_REF] Bissyandé | Popularity, interoperability, and impact of programming languages in 100,000 open source projects[END_REF]. System robustness testing. Fault injection has been applied to the Linux kernel to evaluate the impact of various fault classes [START_REF]EAX: ffffffea EBX: fbc7cc0d ECX: f716ea80 EDX: fbc9cdc0[END_REF][START_REF] Cotroneo | Assessment and improvement of hang detection in the Linux operating system[END_REF]. Our work identifies the safety holes in kernel interfaces that explain their observations. Marinescu and Candea [START_REF] Marinescu | Efficient testing of recovery code using fault injection[END_REF] focus on the returns of error codes from userspace library functions. These are analogous to our Null exit safety holes. Their approach, however, is not applicable to other types of safety holes.

Static bug finding. Model checking, theorem proving, and program analysis have been used to analyze OS code to find thousands of bugs [START_REF] Ball | Thorough static analysis of device drivers[END_REF][START_REF] Engler | Bugs as deviant behavior: a general approach to inferring errors in systems code[END_REF][START_REF] Lawall | WYSIWIB: A declarative approach to finding API protocols and bugs in Linux code[END_REF][START_REF] Post | Integrated static analysis for Linux device driver verification[END_REF]. Nevertheless, these tools take time to run and the results require time and expertise to interpret. Thus, these tools are not well suited to the frequent modifications and tests that are typical of initial code development. Numerous approaches have proposed to statically infer so-called protocols, describing expected sequences of function calls [START_REF] Engler | Bugs as deviant behavior: a general approach to inferring errors in systems code[END_REF][START_REF] Lawall | WYSIWIB: A declarative approach to finding API 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] Ramanathan | Path-sensitive inference of function precedence protocols[END_REF]. These approaches have focused on sequences of function calls that are expected to appear within a single function, rather than the specific interaction between a service and the rest of the kernel. Some of our kinds of safety holes could be eliminated by the use of advanced type systems. For example, Bugrara and Aiken propose an analysis to differentiate between safe and unsafe userspace pointers in kernel code [START_REF] Bugrara | Verifying the safety of user pointer dereferences[END_REF]. They focus, however, on the entire kernel, and thus may inform service developers about faults in code other than their own.

Logging. Runtime logs are frequently insufficient for failure diagnosis especially in case of unexpected crashes [START_REF] Yuan | Sherlog: Error diagnosis by connecting clues from run-time logs[END_REF]. LogEnhancer [START_REF] Yuan | Improving software diagnosability via log enhancement[END_REF] enriches log messages with extra information, but does not create new messages. Diagnosys creates new log messages along the kernel-service boundary, where they can be most helpful to service developers.

Robust interfaces. LXFI [START_REF] Mao | Software fault isolation with API integrity and multi-principal modules[END_REF] isolates kernel modules and includes the concept of API integrity, which allows developers to define the usage contract of kernel interfaces by annotating the source code. LXFI, however, aims at limiting the security threat posed by the privileges granted to kernel modules, while Diagnosys focuses on various categories of common faults encountered in kernel code.

Healers automatically generates a robust interface to a user-level library without access to the source code [START_REF] Fetzer | Healers: a toolkit for enhancing the robustness and security of existing applications[END_REF]. It relies on fault injection to identify the set of assumptions that a library function makes about its arguments. Healers can obtain information about runtime values, such as array bounds, that may be difficult to detect using static analysis. However, Healers does not address safety hole kinds such as Lock that require calling-context information. Supporting Lock would require testing the state of all available locks, which would be expensive and are likely unknown.

Programming with contracts. A software contract represents the agreement between the developer of a component and its user on the component's functional behavior [START_REF] Flanagan | Extended static checking for Java[END_REF][START_REF] Hirschfeld | Dynamic contract layers[END_REF][START_REF] Meyer | Object-Oriented Software Construction[END_REF][START_REF] Mills | Using Design by Contract in C, 1st edn. OnLamp.com[END_REF]. Contracts include pre-and post-conditions, as well as invariants. A safety hole is essentially the dual of a contract, in that a contract describes properties that the context should have, while a safety hole describes properties that it should not have.

Contract inference is analogous to the execution of SHAna. Arnout and Meyer infer contracts based on exceptions found in .NET code [START_REF] Arnout | Uncovering hidden contracts: The .NET example[END_REF]. Daikon infers invariants dynamically by running the program with multiple inputs and generalizing the observations [START_REF] Ernst | The Daikon system for dynamic detection of likely invariants[END_REF]. Diagnosys targets situations that lead to unhandled exceptions, either in the kernel or the service code. Linux kernel execution is highly dependent on the particular architecture and devices involved, and thus service developers would have to actively use Daikon in their own environment. SHAna, in contrast, allows the collection of safety holes to be centralized. Finally, only one of the invariants in the Daikon invariant list, 13 NonZero, may correspond to one of our safety hole kinds, namely INull. Daikon does not handle common safety hole kinds such as Free, or kernel-specific safety hole kinds such as Param, for user/pointer bugs.

The Extended Static Checker for Java (ESC/Java) [START_REF] Flanagan | Extended static checking for Java[END_REF] relies on programmer annotations to check method contracts. Annotation assistants such as Houdini [START_REF] Flanagan | Houdini, an annotation assistant for ESC/Java[END_REF] automate the inference of annotations. Houdini supports various exceptions involving arguments, such as NullPointerException and IndexOutOfBoundsException, but does not provide tests for the validity of allocated memory.

Finally, Parnin and Orso have presented a user study involving actual developers to investigate whether automated debugging tools really help developers [START_REF] Parnin | Are automated debugging techniques actually helping programmers?[END_REF]. They found, for instance, that expert developers were faster when using the tool, although the tool did not help perform harder tasks. In our assessment, we sought to demonstrate that Diagnosys provides debugging information that is useful even for a novice programmer, and that it helps in pinpointing the root cause even in cases where the root cause is hidden in the stack trace of a crash.

Programming using DSLs Domain-Specific languages provide concise syntax and rich semantics for allowing domain experts, who may not be traditional programmers, to write programs for a given domain. There are claims in the literature that DSL programs are easy to use and maintain [START_REF] Strembeck | An approach for the systematic development of domain-specific languages[END_REF]. Our own experience in designing DSLs [START_REF] Bissyandé | Bridging the gap between legacy services and web services[END_REF] has led us to note that the maintainability issues are shifted in the implementation of the DSL compiler. We have then proposed to use transformation rules to implement embedded compilers so as to improve maintainability [START_REF] Bissyandé | Implementing an embedded compiler using program transformation rules[END_REF]. However, a more general study by Donahue found that easy maintainability is not an intrinsic property of DSLs [START_REF] Donahue | Debugging domain-specific languages[END_REF].

Conclusion

Defects in kernel-level services can cause the demise of the entire operating system, often leaving developers without any information about what went wrong. In the Linux kernel, for example, one significant difficulty in developing drivers is that the kernel does not export a debugging interface to its internal functionalities [START_REF] Kroah-Hartman | The Linux kernel driver interface (all your questions answered and then some[END_REF]. Many of the functions that are exported to external modules have implicit ill-documented preconditions, which, if not satisfied, can cause the entire system to crash or hang.

In this paper, we have presented a new approach for supporting kernel-level service developers in the early stages of service development. Diagnosys was designed and implemented as an approach to automatically constructing a debugging interface for the Linux kernel. The tool detects safety holes in Linux kernel-level API functions and supports the generation of a debugging interface, tailored for a particular service, according to this information. At runtime Diagnosys provides a crash-resilient logging system for recording information about risky uses of kernel functions containing safety holes.

Using fault injection tests on 10 Linux kernel-level services, we have shown that our interface alerts the developers to the critical defects in their code. Using a driver for a Gigabit Ethernet device and a NFS file system, we have shown that the performance impact of our approach is within the limits of what is acceptable when testing a kernel-level service in the initial stages of development, and can even be used up to the phase of initial deployment.

Availability: Materials for this paper, including more detailed information on the analysis specifications, the Diagnosys tool, and the certified versions of the kernel can be found on the project webpagehttp://diagnosys.labri.fr.

1

  Fig. 1: Bug fix of the usage of skb put

Fig. 2 :

 2 Fig. 2: Bug fix of error handling code

Fig. 4 :Fig. 5 :

 45 Fig. 4: Bug fix of critical section code

Fig. 6 :

 6 Fig. 6: Derivation of safety hole kinds from the elements of a Lock bug type

Fig. 7 :

 7 Fig. 7: Localization of possible and certain safety holes in the execution paths of an API function

Fig. 8 :

 8 Fig. 8: Oops report following a btrfs ERR PTR pointer dereference crash.

Fig. 9 :

 9 Fig. 9: The steps in using Diagnosys

Fig. 10 :

 10 Fig. 10: Identification of core kernel primitives in module object code with GNU objdump

Fig. 11 :

 11 Fig. 11: Structure of a wrapper for a non-void function

[Fig. 15 :

 15 Fig. 15: Last Diagnosys log line in the execution of nouveau drm

Fig. 16 :

 16 Fig. 16: Patch to avoid a fault involving a Lock safety hole in nouveau drm

  Tegawendé F. Bissyandé et al.

  BlockTo avoid deadlock, do not call blocking functions with interrupts disabled or a spinlock held.

		Entry safety hole	f possibly/certainly calls a blocking function
		Exit safety hole	f returns after disabling interrupts or while holding a lock
	Null/INull	Check potentially NULL pointers returned from routines.
		Do not make inconsistent assumptions about whether a pointer is NULL/ERR PTR.
		Entry safety hole	f possibly/certainly dereferences an argument without checking its validity
		Exit safety hole	f returns NULL/ERR PTR pointer
	Var	Do not allocate large stack variables (> 1K) on the fixed-size kernel stack.
		Entry safety hole	f possibly/certainly allocates an array whose size depends on a parameter
		Exit safety hole	f returns a large value
	Range	Always check bounds of array indices and loop bounds derived from user data.
		Entry safety hole	f possibly/certainly uses an unchecked parameter to compute an array index
		Exit safety hole	f returns value obtained from user level
	Lock	Release acquired locks; Do not double-acquire locks
	LockIntr	Entry safety hole	f possibly/certainly acquires a lock derived from a parameter
		Exit safety hole	f returns without releasing an acquired lock
	Intr	Restore disabled interrupts.
	LockIntr	Entry safety hole	f possibly/certainly calls a blocking function
		Exit safety hole	f returns with interrupts disabled
	Free	Do not use freed memory.
		Entry safety hole	f possibly/certainly dereferences a pointer-typed parameter value
		Exit safety hole	f frees memory derived from a parameter
	Param	Do not dereference user pointers.
		Entry safety hole	f possibly/certainly dereferences a pointer-typed parameter
		Exit safety hole	f returns a pointer-typed value obtained from user level
	Table 1: Recasting common faults in Linux into safety hole categories. f refers to an API function
	interprocedural between service code, where the call might be, and kernel code, where the fault
	might be activated.

  1 [847.353202] BUG: unable to handle kernel paging request at ffffffee 2 [847.353205] IP: [<fbc722d9>] btrfs init new device+0xcf/0x5c5 [btrfs] 3 [847.353229] *pdpt = 00000000007ee001 *pde = 00000000007ff067 4 [847.353233] Oops: 0000 [#1] . . . 5 [847.353291] EIP is at btrfs init new device+0xcf/0x5c5 [btrfs] . . . 6 [847.353298] Process btrfs-vol (pid: 3699, . . . 7 [847.353312] Call Trace: 8 [847.353327] [<fbc7b84e>] ? btrfs ioctl add dev+0x33/0x74 [btrfs] 9 [847.353334] [<c01c52a8>] ? memdup user+0x38/0x70 . . . 10 [847.353451] ---[ end trace 69edaf4b4d3762ce ]---

Table 2 :

 2 Categorization of common faults in Linux

Table 3 :

 3 Enabling conditions for triggering API function safety holes functions, unsafe dereferences of other pointer values, such as ERR PTR values,4 whose validity is directly or indirectly related to the validity of an API function's unchecked parameter.

Table 6 :

 6 Tested Linux 2.6.32 services

	Category	Service module	Description	# of used functions with safety holes
		e1000e	Ethernet adapter	57
	Networking	iwlagn	Intel WiFi Next Gen AGN	57
		btusb	Bluetooth generic driver	26
	USB drivers	usb-storage ftdi sio	Mass storage device driver USB to serial converter	51 31
	Multimedia	uvcvideo	Webcam device driver	28
	device drivers	snd-intel8x0	ALSA driver	35
		isofs	ISO 9660 file system	26
	File systems	nfs	Network file system	198
		fuse	File system in userspace	86

Table 7 :

 7 Results of fault injection campaigns

Table 8 :

 8 Checking overhead ± standard deviation Table 9 compares the execution time of Diagnosys' logging primitive with that of other logging mechanisms used in the kernel. printk is the most commonly used logging function. Ftrace

Table 9 :

 9 Performance of the Diagnosys logging primitive

Table 10 :

 10 Performance of the e1000e driver

Table 11 :

 11 Performance of the NFS file system 5.6 Certification overhead of analysis results

https://kgdb.wiki.kernel.org/

https://lkml.org/lkml/2012/2/10/129

The implementation of the analysis can be found at http://diagnosys.labri.fr

We refer to a value constructed with the function ERR PTR as just an ERR PTR value.

{mutex,spin,read,write} lock, {mutex,spin,read,write} trylock local irq disable, {read,write,spin} lock irq, {read,write,spin} lock irqsave, local irq save, save and cli.

Linux kernel commit: f0fbe3eb5f65fe5948219f4ceac68f8a665b1fc6

More information on the format used by GNU objdump can be found at http://www.gnu.org/software/ binutils/.

See an article at http://www.linuxjournal.com/article/5749

git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git -history back to 2.6.12.

Kernel allocation functions use flags to indicate whether the process can afford to have a failed allocation. Calls that are not allowed to fail have flag information containing GFP NOFAIL or GFP RETRY.

Acknowledgements: This work was supported in part by the ANR Blanc grant ABL.