Jia-Ju Bai

Julia Lawall
email: julia.lawall@lip6.fr

Wende Tan

Shi-Min 2019 Hu

DCNS: Automated Detection of Conservative Non-Sleep Defects in the Linux Kernel

Keywords: CCS Concepts, Software and its engineering → Software defect analysis, Operating systems, • Computer systems organization → Reliability, Linux kernel, atomic context, defect detection, function-pointer analysis

For waiting, the Linux kernel offers both sleep-able and nonsleep operations. However, only non-sleep operations can be used in atomic context. Detecting the possibility of execution in atomic context requires a complete inter-procedural flow analysis, often involving function pointers. Developers may thus conservatively use non-sleep operations even outside of atomic context, which may damage system performance, as such operations unproductively monopolize the CPU. Until now, no systematic approach has been proposed to detect such conservative non-sleep (CNS) defects.

In this paper, we propose a practical static approach, named DCNS, to automatically detect conservative non-sleep defects in the Linux kernel. DCNS uses a summary-based analysis to effectively identify the code in atomic context and a novel file-connection-based alias analysis to correctly identify the set of functions referenced by a function pointer. We evaluate DCNS on Linux 4.16, and in total find 1629 defects. We manually check 943 defects whose call paths are not so difficult to follow, and find that 890 are real. We have randomly selected 300 of the real defects and sent them to kernel developers, and 251 have been confirmed.

Introduction

The Linux kernel provides fundamental support, such as memory management and hardware access, for high-level applications. To limit the overhead on applications, kernel code should complete as quickly as possible. Nevertheless, in many cases, the Linux kernel must wait, e.g. until a resource is available or a response from a hardware device is received. For efficiency, the Linux kernel offers a range of waiting operations, tailored to the requirements of different execution contexts.

Waiting operations in the Linux kernel can be categorized as non-sleep and sleep-able. Non-sleep operations, such as the function mdelay, spin by monopolizing a CPU core until a specified amount of time has passed. These operations have quick reactivity when the waiting time expires, as the thread is already running on the CPU, but spinning can reduce the overall system throughput, because the monopolized CPU is not available to other more productive threads. In contrast, sleep-able operations, such as the function msleep, can make the thread yield the CPU to sleep (or block), until a timer expires or some other expected condition becomes true. These operations have slower reactivity, because a waking thread must wait further until the scheduler allows it to run on the CPU, but system throughput can be improved, because other threads can run on the CPU during the wait. A second nonsleep alternative is to abort the operation and return an error code, which is allowed by the non-sleep flag GFP_ATOMIC in the Linux kernel. This strategy eliminates the overhead incurred by sleeping, but increases the probability of failure of the operation. For example, resource allocation using GFP_ATOMIC is more likely to fail than resource allocation using the sleep-able flag GFP_KERNEL. It also imposes on the calling context the burden of handling the error case.

Given this range of waiting operations, the challenge for the kernel developer is to choose the best one for each execution context. A general "rule of thumb" is that spinning is fine for short durations, due to the improved reactivity, but sleeping should be used for longer waiting times, to avoid wasting CPU resources. 1 In the Linux kernel, however, in atomic context [START_REF] Corbet | Atomic context and kernel API design[END_REF], where a spinlock is held or within an interrupt handler, sleeping is not allowed, and non-sleep operations must be used. Unlike the rule about the expected waiting time, the property of being in atomic context is not a local property, i.e., it does not depend on the arguments of the call but rather on the possible code execution paths through the system that can reach the operation. Understanding the complete set of such possible execution paths can require tracing through many function calls across many different source files, which is challenging given the large size of the Linux kernel. The challenge is compounded when the execution path contains function pointers, which the Linux kernel uses often for modularity. Kernel developers who are unsure about whether their code is in atomic context may simply use non-sleep operations, to the detriment of the overall system performance. We call such unnecessary non-sleep operations conservative non-sleep (CNS) defects. There is a need for tool support to detect such issues.

In this paper, we propose a practical static analysis approach named DCNS, to automatically detect conservative non-sleep defects in the Linux kernel. Overall, DCNS first identifies non-sleep function calls in the Linux kernel code, then marks those occurring in atomic context, and finally reports the remaining ones as CNS defects. Specifically, DCNS consists of three phases. Firstly, DCNS analyzes the Linux kernel code to identify non-sleep function calls, and collects some useful code information, such as function definitions, function-pointer assignments, etc. Secondly, using the collected information, DCNS identifies source files that are connected by direct function calls. We call this connection a file connection, and it guides the function-pointer analysis in the next phase. Thirdly, DCNS performs a summary-based analysis to mark all non-sleep function calls that occur in atomic context. To cover all possible code execution paths in atomic context, this analysis is inter-procedural, and is started from each spinlock-acquire function call and the entry of each interrupt handler function. It maintains a lock stack to accurately identify atomic context, and uses function summaries to avoid repeated analysis. To handle function-pointer calls, DCNS performs a file-connection-based alias analysis, to correctly identify the set of functions referenced by the function pointer. After this phase, DCNS reports unmarked non-sleep function calls as CNS defects.

We have implemented DCNS using LLVM [START_REF] Llvm | LLVM compiler infrastructure[END_REF]. DCNS works automatically, given the Linux kernel source code. Moreover, DCNS can work in parallel to speed up the analysis. Overall, we make the following contributions:

• Using an experiment with a standard benchmark, we show that CNS defects can damage system performance. We also study the commits fixing CNS defects in the Linux kernel, and find that these CNS defects have all been manually detected, because no systematic approach has been proposed to detect such defects.

• We analyze the main challenges of detecting CNS defects in the Linux kernel, and then propose a practical static approach named DCNS to automatically detect CNS defects in the Linux kernel code. To our knowledge, DCNS is the first approach to automatically detect CNS defects. • In DCNS, we propose a file-connection-based alias analysis to correctly identify the set of functions referenced by a function pointer. • We evaluate DCNS on Linux 4.16, and in total find 1629 defects. We manually check 943 defects whose call paths are not so difficult to follow, and find that 890 are real, giving an accuracy rate of 94%. We have randomly selected 300 of the real defects and sent them to kernel developers, and 251 have been confirmed.

The remainder of this paper is organized as follows. Section 2 reviews the motivation. Section 3 shows the main challenges of detecting CNS defects. Section 4 introduces our key techniques. Section 5 introduces DCNS in detail. Section 6 presents our evaluation. Section 7 discusses the results. Section 8 gives related work, and Section 9 concludes.

Motivation

We first introduce sleeping and atomic context, then introduce conservative non-sleep (CNS) defects, and finally study the existing commits fixing CNS defects in the Linux kernel.

Sleeping and Atomic Context

Sleeping. To improve system performance and utilize multiple CPUs, the Linux kernel allows multiple threads to run concurrently. When there are more threads than CPUs, it is undesirable for a kernel thread to monopolize a CPU. Thus, when a kernel thread has nothing useful to do, it should yield the CPU for other threads to use. We refer to the action of yielding the CPU as sleeping. An operation that can sleep is a sleep-able operation. Atomic context. Sleeping is not allowed in a special kernel context known as atomic context [START_REF] Corbet | Atomic context and kernel API design[END_REF]. Typical examples of atomic context are holding a spinlock and executing an interrupt handler. Atomic context is used to protect data from concurrent access. In such a context, a thread monopolizes a CPU, and the progress of other threads that need to concurrently access the same data is delayed. Code in atomic context should thus complete as quickly as possible. Code in atomic context is furthermore not able to be rescheduled. As sleeping can block the CPU for a long time and requires the code to be rescheduled, sleeping in atomic context is forbidden. It may cause a system hang or crash at runtime.

Conservative Non-Sleep Defects

While waiting in atomic context must be implemented with non-sleep operations, the use of non-sleep operations outside of atomic context may damage system performance by wasting CPU resources and increasing the likelihood of failure of some operations. Thus, such use represents a form of defect, which we refer to as a conservative non-sleep (CNS) defect. Still, whether code is in atomic context often depends on inter-procedural properties, which are tricky to follow, especially in code with the size and complexity of the Linux kernel. Kernel developers may be unsure about whether their code may occur in atomic context, and may use non-sleep operations to be on the safe side. We now give an example of Linux kernel code containing CNS defects, and study the impact of these defects on performance. CNS defect example. Figure 1 shows part of a patch (commit 4e0d8f7d97f9) to the e1000 Ethernet controller driver in Linux 3.2 for fixing CNS defects. This patch was applied in 2011, at which point the CNS defects had been present since Linux 2.6.10, released nearly 7 years earlier. In Figure 1, the function e1000_polarity_reversal_workaround can be called when the Ethernet controller checks or changes the link. This function calls mdelay, which is a non-sleep function, to busily wait for some time before and after writing hardware registers. But this function is never called in atomic context, so mdelay is unnecessary, and it will monopolize a CPU to busily wait with no benefit. The patch thus replaces the calls to mdelay by calls to the sleep-able function msleep. CNS defect impact. To show the potential impact of CNS defects on system performance, we run the e1000 driver in Linux 3.2 with and without the patch in Figure 1, on a Lenovo PC with four CPUs and an Intel 82543 Ethernet controller (managed by the e1000 driver). To cause the code in Figure 1 to be executed, we can change the network link status when the driver is running. To measure the system performance, we select a standard benchmark sysbench [START_REF] Sysbench | Sysbench: a scriptable database and system performance benchmark[END_REF] and run its CPU tests with N (the number of enabled CPUs in the system) running threads, and measure the execution time. We run the experiment in four situations:

• S1: Without applying the patch, and keeping the network link status unchanged during the test. benchmark increases by 25%, 22%, 19% and 13%, respectively with 1-4 enabled CPUs. The impact decreases as the number of enabled CPUs increases, because more CPUs are available to run the benchmark, even when the e1000 driver monopolizes one CPU to run the non-sleep function mdelay. By comparing the results of S3 and S4, we find that after fixing the defects, the performance is essentially the same, whether the line status is kept the same (S3) or changed (S4). Thus, our experiment shows that CNS defects can damage system performance, so they should be detected and fixed. patches for coding style violations, it is not effective to find CNS defects. Indeed, checkpatch relies on regular expressions, and is thus not able to sufficiently analyze the context of a non-sleep operation to justify transforming it into a sleep-able operation. This analysis must still be performed manually. Some fixing commits explicitly mention the side effects of the CNS defects. For example, commit 55bf851b4ad7 mentions concern about a busy wait of upwards of 100ms, which is a long time for the kernel. Commit 0c87b672098b mentions that GFP_ATOMIC can cause an allocation failure that will cause an easily avoidable user-visible failure. Commit fa17806cde76 mentions that GFP_ATOMIC can cause dropping packets. From these commits, we find that CNS defects can cause serious system problems besides damaging system performance.

Study on the Commits of Fixing CNS Defects

The logs associated with these fixing commits furthermore show that CNS defects are often introduced in two ways. Firstly, due to complex control logic across multiple function calls and source files, the kernel developer may not realize that the code never occurs in atomic context (e.g., commits 55bf851b4ad7 and c01c77ce4b2). Secondly, with the evolution of the Linux kernel, code that originally occured in atomic context may be moved out of atomic context, without changing the original non-sleep operations (e.g., commits 882e1492c7ca and cc1674eeee60).

Detecting CNS defects requires checking the code across multiple function calls, which is time-consuming and errorprone. To our knowledge, no systematic approach has been proposed to detect CNS defects. Thus, our goal is to propose an automated and effective approach to detect CNS defects in the Linux kernel.

Challenges

Our basic strategy for detecting CNS defects is to first find non-sleep operations and then identify those that may be executed in atomic context. The remaining ones are then defects. Implementing this strategy involves three main challenges:

C1: Atomic Context Analysis

There are two aspects of this challenge: Identify the code in atomic context. Whether the code occurs in atomic context depends on whether the code can be reached by an execution path where a spinlock is held or that is part of the execution of an interrupt handler. Checking this condition is straightforward when e.g., a spinlock is acquired in the same function, but it can be much more difficult when multiple function calls have to be taken into account.

Ensure completeness. To accurately detect CNS defects, all code that may occur in atomic context needs to be completely identified. Otherwise, non-sleep operations that are actually executed in atomic context may be not marked, and they will be reported as CNS defects, leading to false positives. If the user fixes these false CNS defects by using sleep-able operations, serious sleep-in-atomic-context bugs may be introduced, which can cause system hangs and crashes.

Several previous approaches [START_REF] Bai | DSAC: effective static analysis of sleep-in-atomic-context bugs in kernel modules[END_REF][START_REF] Engler | Checking system rules using system-specific, programmer-written compiler extensions[END_REF][START_REF] Palix | Faults in Linux 2.6[END_REF] can detect sleep-inatomic-context (SAC) bugs, and they perform atomic context analysis. However, they focus on how to accurately find the existence of a path where the code occurs in atomic context. For these approaches, missing some code that may occur in atomic context (like the code in a function referenced by a function pointer) only introduces false negatives, but for detecting CNS defects, it introduces false positives. Thus, a new atomic context analysis is needed for the latter problem.

C2: Function-Pointer Analysis

The Linux kernel is essentially an object-oriented system, in which data structures containing function pointers play the role of objects containing methods. This design improves extensibility, but greatly complicates static analysis. Namely, many possible execution paths contain calls to function pointers, and static analysis needs to correctly determine the set of functions that may be referenced by these pointers. An accurate function-pointer analysis is thus very important when detecting CNS defects. Without function-pointer analysis, non-sleep operations in the referenced functions may not be marked as being in atomic context, and thus many false positives will be introduced. On the other hand, if incorrect functions are identified for function pointers, the amount of code that is considered to be in atomic context will increase, so many false negatives will occur. Some alias analysis approaches (e.g. [START_REF] Hardekopf | Flow-sensitive pointer analysis for millions of lines of code[END_REF][START_REF] Heintze | Ultra-fast aliasing analysis using CLA: a million lines of C code in a second[END_REF][START_REF] Lattner | Making context-sensitive points-to analysis with heap cloning practical for the real world[END_REF][START_REF] Milanova | Precise call graphs for C programs with function pointers[END_REF]) can handle function pointers, but they are reported to produce many incorrect results for function pointers in large, complex software [START_REF] Hardekopf | Flow-sensitive pointer analysis for millions of lines of code[END_REF][START_REF] Lattner | Making context-sensitive points-to analysis with heap cloning practical for the real world[END_REF].

C3: Analysis efficiency

The Linux kernel code base is very large, amounting to over 16.8M lines in our tested version Linux 4.16, and complex. Moreover, it contains many source files in multiple directories. For these reasons, performing static analysis of the Linux kernel code may be quite time-consuming.

Key Techniques

To solve the above challenges, we propose two key techniques. For C1 and C3, we propose a summary-based analysis to effectively identify the code that may be executed in atomic context. For C2, we propose a file-connectionbased alias analysis to correctly identify the set of functions referenced by a function pointer. We now introduce these techniques.

Summary-Based Analysis of Atomic Context

Atomic context analysis is the basis of detecting CNS defects. Our analysis extends that of DSAC, our previous approach for detecting sleep-in-atomic-context (SAC) bugs [START_REF] Bai | DSAC: effective static analysis of sleep-in-atomic-context bugs in kernel modules[END_REF]. DSAC provides a hybrid flow analysis to detect code in atomic context. This analysis is inter-procedural and context-sensitive, and it maintains a lock stack and an interrupt handling flag, to respectively record spinlock and interrupt handling states across function calls. To provide accuracy, this analysis is flow-sensitive if the analyzed function is in an interrupt handler or calls spin-lock and spin-unlock functions. Otherwise, to improve efficiency, the analysis is flow-insensitive.

While the analysis provided by DSAC was sufficient to find many SAC bugs, for detecting CNS defects, it has some limitations: (1) DSAC handles a single kernel module at a time and only unfolds function calls within the module. To detect CNS defects, we must extend this analysis to consider the whole kernel, to collect the complete calling context of each non-sleep operation. (2) DSAC considers one execution path at a time, and only aborts an analysis if the same function or basic block and context (lock stack and an interrupt handling flag) has been seen in the current execution path. To detect CNS defects, we introduce globally visible function summaries, to avoid repeatedly unfolding core kernel functions that may be called from many different drivers. (3) DSAC performs flow-sensitive analysis of the functions called from interrupt handlers, to detect and abort repeated analysis within the current path. In the case of interrupt handlers, code is already in atomic context, it is unnecessary to analyze each code path. Thus, to detect CNS defects, functions called from interrupt handlers are analyzed in a flow-insensitive way, to improve efficiency. (4) DSAC stops at function pointers, potentially missing some execution paths and thus some SAC bugs. This is not acceptable for CNS defects, where all execution paths must be considered. To detect CNS defects, we handle function pointers using a file-connection-based alias analysis that we will introduce in Section 4.2.

Our analysis has two steps. The first step identifies interrupt handler functions and calls to spin-lock functions, which initiate atomic context. Starting from these entry points, the second step uses AtomicAnalysis shown in Figure 2, to identify the code that may be executed in atomic context and mark the non-sleep function calls within this code. Like the analysis of DSAC [START_REF] Bai | DSAC: effective static analysis of sleep-in-atomic-context bugs in kernel modules[END_REF], AtomicAnalysis maintains a lock stack (lock_stack) to store the spinlock state, a path stack (path_stack) to store analyzed basic blocks, and a global flag (g_intr_flag) to indicate whether the code is executed in an interrupt handler. As shown in Figure 2, AtomicAnalysis uses HandleBlock to handle a basic block, HandleCall to handle a function call, and HandleFunc (new as compared to DSAC) to handle the definition of a called function. In the following, we introduce our summary-based analysis and how it extends the hybrid flow analysis of DSAC.

HandleBlock. It handles the instructions in the basic block myblock with the arguments path_stack and lock_stack. It first checks the path_stack to see if myblock has already been analyzed with respect to the current lock_stack and g_intr_flag, to prevent infinite loops. Then, it analyzes the definition of each called function in myblock except for locking functions and non-sleep functions. Finally, it handles each successive basic block. The only change as compared to DSAC is to mark calls to non-sleep functions that are detected to be in atomic context (lines 10-11).

HandleCall. It handles the function call mycall with the arguments path_stack and lock_stack. As compared to DSAC, the analysis is simplified to process all calls rather than checking for and stopping at module boundaries. HandleCall also uses the results of our alias analysis, described in Section 4.2, to collect all possibly referenced functions when the call involves a function pointer (lines 5-8).

HandleFunc. It handles the function myfunc with the arguments path_stack and lock_stack. HandleFunc implements the summary-based analysis. For a given function name, lock_stack and g_intr_flag, HandleFunc searches the function summaries stored in a global database to check whether myfunc has been already handled under the current execution context (lines 1-4). If so, it returns immediately. If not, it adds the function name and context information to the database. Finally, HandleFunc handles the definition of myfunc (lines 5-14). If g_intr_flag is TRUE or myfunc does not contains spin-lock or spin-unlock function calls, Han-dleFunc performs flow-insensitive analysis to handle each function call in myfunc, using HandleCall. Otherwise, Han-dleFunc performs flow-sensitive analysis from the entry basic block of myfunc, using HandleBlock, because whether the code is in atomic context is decided by the positions of the spinlock-related function calls in the path.

File-Connection-Based Function-Pointer

Analysis The main technical challenge in detecting CNS defects is to accurately identify the set of functions referenced by a given function pointer. To do this, we first collect all of the functions that may be assigned to this function pointer, and then select the relevant function(s) at a given call site from this collected set. The first step is done straightforwardly, by scanning the source code for assignments to function pointers. The second step, of how to identify the relevant function(s) at a particular call site, is more difficult.

To illustrate the issues involved, we consider the Linux kernel code shown in Figure 3. The function ixgbe_get_-ethtool_stats calls the function dev_get_stats (line 1211) that is defined in another source file. The function dev_-get_stats uses a function-pointer call through the ndo_-get_stats64 field of a net_device_ops data structure. This field is initialized in multiple drivers to various functions; Figure 4 pointer is called from the ixgbe driver, only ixgbe_get-_stats64 can actually be called at this call site. The functions rtl8139_get_stats64 and usbnet_get_stats64 cannot be called, as their source files are not related to the ixgbe driver. ixgbe_get_stats64, on the other hand, is stored in the ndo_get_stats64 field of a net_device_ops data structure in a source file of the ixgbe driver.

Based on this example, we observe that for a function to be invoked from a function-pointer call site, there needs to be some form of communication between the file in which the function is defined and the file containing the call site. Thus, a function can only be relevant at a function-pointer call site if such communication exists. The most basic form of communication, which does not require the prior establishment of any function pointers, is via a direct function call. If there are direct function calls between two files, we say that they have a file connection. Specifically, if there exists a direct function call between File A and File B (File A → File B or File B → File A), then File A and File B have a direct connection. Similarly, if there exists a direct function call from File A to File B (File A → File B) and from File B to File C (File B → File C), then File A and File C have an indirect connection. We thus filter possible functions at a function-pointer call using the transitive closure of file connections.

Consider again the example of Figure 3. There exists a direct function call ixgbe_update_stats from ixgbe_main.c to ixgbe_ethtool.c, and thus these two source files have a connection. But there does not exist any sequence of calls between 8139too.c or sr9700.c and ixgbe_ethtool.c, and thus these files do not have any connection.

Based on our observation, we propose a file-connectionbased alias analysis, to identify the set of functions referenced by the function pointer. For efficiency, our alias analysis is flow-insensitive. Moreover, in the Linux kernel, many function pointers are obtained from data structure fields [START_REF] Baliga | Detecting kernel-level rootkits using data structure invariants[END_REF], especially in device drivers, as illustrated in Figure 3. To handle such function pointers in large-scale code, our alias analysis performs a field-based analysis of data structure fields [START_REF] Heintze | Ultra-fast aliasing analysis using CLA: a million lines of C code in a second[END_REF]. Our alias analysis has two steps:

Step 1: Collect code information. This step is performed before the atomic context analysis in Section 4.1. It traverses the Linux kernel code to identify the assignments to function pointers, and collects the possible function values in each case. Specifically, for each function pointer represented by a data structure field, our alias analysis extracts the data structure type, field offset and function-pointer type to differentiate it from other function pointers. Moreover, our alias analysis also collects direct file connections, representing direct function calls. All of the above information is stored in a database, and will be used in the next step.

Step 2: Identify the set of functions. This step, defined in Figure 4, is performed when the atomic context analysis encounters a function-pointer call, to identify the set of functions referenced by the function pointer. The inputs of this step are the function-pointer call func_ptr_call and the name of the source file src_file where the atomic context analysis started. The output is a set of functions func_set that contains the functions referenced by the function pointer. This step first checks the form of the function-pointer expression. If it has the form of a data structure field reference, the analysis extracts the functions according to the type of this data structure, the offset of the field and the function-pointer type (line 4). Otherwise, the analysis extracts all functions stored in any function pointer of the given type (line 6). The analysis then returns the subset of these functions for which there is a direct or indirect file connection, as identified in Step 1, between the file containing the starting point of the atomic context analysis and the file defining the given function (lines 8-14).

The main advantage of our file-connection-based alias analysis is to reduce the amount of incorrect functions identified for function pointers. This reduction can benefit the detection of CNS defects in two aspects: (1) These incorrect functions are not analyzed during the atomic context analysis, which can improve the efficiency of defect detection.

(2) The non-sleep function calls in these incorrect functions are not marked in atomic context analysis, which can reduce the number of false negatives.

Approach

Based on the two techniques in Section 4, we propose a practical static analysis approach named DCNS, to automatically detect conservative non-sleep (CNS) defects in the Linux kernel. We implement DCNS using the Clang compiler [START_REF] Clang | Clang compiler[END_REF], and store the code information collected during analysis in a MySQL database [START_REF] Mysql | MySQL database[END_REF]. DCNS performs static analysis on the LLVM bytecode of the Linux kernel. Figure 5 shows the overall architecture of DCNS, which consists of four modules: • Clang compiler. This module compiles each source file of the Linux kernel into an LLVM bytecode file. • Information collector. This module traverses the Linux kernel code by analyzing each LLVM bytecode file, to record useful code information in the database. This code information is used in the remaining analyses. • Connection extractor. This module uses the collected code information to extract direct file connections, and records them in the database. • Atomic context analyzer. This module performs atomic context analysis to mark non-sleep function calls that may be executed in atomic context, and then reports the remaining ones as CNS defects.

DCNS Information Collector

Atomic Context Analyzer

CNS Defect Reports Connection Extractor

Direct File Connections

OS Kernel Source Files

Clang Compiler

LLVM Bytecode

Based on this architecture, DCNS has three phases. We introduce them below.

Code Information Collection

In this phase, the code compiler first compiles each source file into an LLVM bytecode file. Then, by analyzing each LLVM bytecode file, the code information collector extracts and records the name and position of each function definition, the callee and caller functions of each direct function call, the possible functions stored in function pointers and the position of each non-sleep function call.

Direct File Connection Extraction

In this phase, the connection extractor extracts direct file connections, using the collected code information. The extractor analyzes each function call to check whether the call and the definition of the called function are in different source files. If so, the two source files are regarded as having a direct file connection, and this connection is recorded in the database.

Code Analysis of Atomic Context

In this phase, the atomic context analyzer performs summarybased atomic context analysis on the LLVM bytecode files, using the collected code information. It marks non-sleep function calls that may be executed in atomic context. To handle function-pointer calls, the analyzer uses the file connection information to identify the set of functions referenced by the function pointer, and processes each function in the resulting set. Finally, the analyzer reports unmarked non-sleep function calls as CNS defects.

The first two phases of DCNS work on individual files independently, benefiting from the collected information. Thus, these phases can be parallelized straightforwardly. The atomic context analysis traces through function calls, which may cross file boundaries, when the called function is defined in another file and no function summary is available for the current context. In this case, we can also run the analysis in parallel, allowing the global database of function summaries to prevent repeated analysis of functions in the same context across different threads. 6 Evaluation

Experimental Setup

To validate the effectiveness of DCNS, we evaluate it on Linux kernel code. We run the evaluation on an x86-64 PC with four Intel i5-3470@3.20GHz processors and 8GB physical memory. We use the kernel configuration allyesconfig to enable all kernel code for the x86 architecture. We compile the kernel code using Clang 6.0 [START_REF] Clang | Clang compiler[END_REF]. Because DCNS can work in parallel, we configure it to run on 4 threads.

In the evaluation, we consider two common kinds of nonsleep operations in the Linux kernel, which have been involved in many previously reported CNS defects:

• Calls to mdelay with a waiting time ⩾ 20ms. The function mdelay is used to busily wait for a specified number of milliseconds. This function has a counterpart msleep, which can sleep to wait, when the waiting time is ⩾ 20ms.2 • Calls to a function with the argument GFP_ATOMIC.

Such a call is often used to allocate a resource. If the resource is not available, the call directly returns an error. GFP_ATOMIC has a corresponding sleep-able flag GFP_KERNEL, that allows the called function to sleep and wait for the resource to become available. 3Given this configuration information and the Linux kernel source code, DCNS works fully automatically, and produces readable CNS defect reports.

Detecting Known Defects

To check whether DCNS can find known CNS defects, we select the commits fixing CNS defects submitted from January 2016 to July 2017 that change mdelay to msleep and GFP_ATOMIC to GFP_KERNEL. In total, there are 15 commits (see Table 2), which fix 46 CNS defects. For each commit, we revert the kernel code to the status just before the commit, and run DCNS. Table 3 shows the results classified by the defect's root cause. DCNS finds 42 of the defects. It misses 4 defects, because the related source code is not enabled in the kernel configuration for the x86 architecture. These results indicate that DCNS can find known CNS defects.

Detecting New Defects

We next check whether DCNS can find new CNS defects. We evaluate DCNS on Linux kernel version 4.16 (released in April 2018). Table 4 summarizes the results, and we have the following findings:

(1) DCNS can scale to large code bases. It handles 12.1M source code lines from 16.6K source files in 79 minutes (elapsed time). The remaining 4.7M source code lines of the Linux kernel are not enabled for the x86 architecture, and thus DCNS does not handle them.

(2) DCNS is effective in handling function-pointer calls. Firstly, DCNS successfully identifies the referenced functions for 23,680 function pointer calls, accounting for more than 92% of all encountered function pointer calls. The remaining 8% fall into two cases. One case is when there is no initialization of the function pointer in the code selected by the compiler as being relevant to the x86 architecture, which causes 55% of the unhandled calls. In these cases, the code tests whether the pointer is null before making the call. The other case is when DCNS observes relevant assignments in the analyzed code, but the assignment is somehow too complex for DCNS to be able to identify the function(s) assigned to the function pointer, which causes 45% of the unhandled calls. Figure 6 shows an example of the latter case. hfi1_handle_cnp_tb is a global array of function pointers, and it is initialized on lines 426-429. The structure of the bytecode generated by LLVM for this code prevents DCNS from detecting the array initialization, so the function-pointer call on line 480 is not handled. (File: linux-4.16/drivers/infiniband/hw/hfi1/driver.c) Secondly, by using the file-connection-based alias analysis, DCNS identifies 245K functions referenced by handled function-pointer calls, and discards 1435K possible functions. Namely, 85% of the possible functions are discarded as they are likely to be incorrect in the calling context of the given function-pointer call. By discarding these incorrect possible functions, DCNS reduces unnecessary atomic context analysis, and also reduces false negatives in defect detection.

(3) DCNS is effective in detecting CNS defects. DCNS in total finds 1629 CNS defects, from 4589 non-sleep operations. We scan all the defects, and manually check 943 defects whose call paths are not so difficult to follow, and find that 890 are real, giving an accuracy rate of 94%. We randomly selected 300 of the real defects and sent them to kernel developers, and 251 have been confirmed. We do not manually check the remaining 686 defects, because their non-sleep function calls are touched by many code paths, and thus we are not confident in our manual analysis.

Among the 251 confirmed defects, 73 involve calls to mdelay with a waiting time ⩾ 100ms, and 6 of the 73 have a waiting time of 1000ms. These calls busily wait for a long time with no benefit and can damage the overall system performance. Besides, 110 of the confirmed defects involve GFP_ATOMIC, with many in driver initialization functions, and are thus likely cause a user-visible failure.

(4) DCNS is efficient. In total, it handles 16.6K source files in 79 minutes running on four threads.

False Positive Analysis

False results mainly occur in two cases:

(1) Some interrupt handler functions are not identified, so the non-sleep function calls in these functions may be not marked and will be reported as CNS defects. This case is mainly caused by the fact that DCNS only identifies as interrupt handler functions the functions in specific arguments of known interrupt handler register functions (such as request_irq and tasklet_init in the Linux kernel), and when the argument is an explicit function. If the argument is a function pointer that is assigned at other places, DCNS cannot identify the concrete interrupt handler function. Figure 7 shows an example of this case. The interrupt handler register function request_irq uses a function pointer as an argument on line 391. This function pointer is assigned as the function aac_sa_intr on line 344, but DCNS does not track this information.

(2) Some function-pointer calls are not handled, so the non-sleep function calls in the referenced function may be unmarked and will be reported as CNS defects. These reported CNS defects are false positives. As described in Section 6.3, this case mainly occurs when the function pointer is assigned in complex ways that DCNS cannot handle.

Besides, another possible source of false positives is in code that is reachable from functions exported to dynamically loadable kernel modules. Such functions are declared (File: linux-4.16/drivers/scsi/aacraid/sa.c) using EXPORT_SYMBOL or similar macros. The goal of the Linux kernel developer community is that loadable kernel modules should have their source code included with the Linux source code distribution, 4 but in practice, this may not always be the case. DCNS does not see the code of such external modules, and these modules may invoke the exported functions with a different lock stack or interrupt handler state than that exhibited within the kernel source tree. If a non-sleep operation is only reachable in atomic context in this way, DCNS will report a false positive. To estimate the impact of this issue, we rerun DCNS extended to consider that all exported functions enter atomic context. DCNS finds 1101 defects, all of which are also found in the original results. Among them, 524 defects have been manually checked, and 492 are real. Nevertheless, we expect that generally, exported functions will be used by external Linux kernel modules in the same way that they are used by code in the Linux kernel source tree. And all exported function should be used somewhere within the Linux kernel [START_REF] Corbet | Exported symbols and the internal API[END_REF], giving DCNS information about their expected use.

Defect Distribution

We classify the found CNS defects according to the directory of their source files. Figure 8 shows the distribution of all reported defects and the real defects identified by our manual check. Figure 8(a) shows the defect distribution in the whole kernel. We find that drivers have more than 75% of the defects. This is somewhat higher than the percentage of code represented by drivers (67% in Linux 4. [START_REF] Hallem | A system and language for building system-specific, static analyses[END_REF], and shows that drivers remain a significant source of system problems [START_REF] Michael | Improving the reliability of commodity operating systems[END_REF]. We then classify the driver defects by the driver class (Figure 8(b)). We find that network, staging, media and SCSI drivers are together the source of nearly 70% of the defects in drivers.

Sensitivity Analysis

DCNS uses two key techniques: a summary-based analysis to reduce repeated analysis of atomic context, and a fileconnection-based alias analysis to correctly identify the set of functions referenced by a function pointer. To better understand the value of these two techniques, we modify DCNS to remove each of them, and evaluate each modified tool on the Linux 4.16 kernel code. Summary-based analysis. We implement the modified tool without using function summaries, which allows a function to be repeatedly handled in the same execution context. The PathHasExisted check is retained in lines 1-3 of HandleBlock (Figure 2), to protect against infinite loops due to recursion. The resulting tool runs for 700 minutes and finally aborts due to insufficient memory, without completing the analysis. This experiment indicates that our summary-based analysis indeed improves the efficiency of atomic context analysis. File-connection-based analysis. We implement two modified tools. The first tool drops our file-connection-based analysis, and simply reports all functions that were collected as being possibly assigned to the function pointer. The other tool builds on our observation that only functions defined in related files are relevant. We implement the notion of a related file in a simpler way, by considering source files to be related when they are part of the same kernel module. Table 5 shows the results of the first tool (Tool 1) and the second tool (Tool 2).

For the first tool, there are three main differences between its results and those of DCNS. Firstly, the tool considers many functions as being referenced by each function pointer that are dropped by DCNS, and thus more functions pointers are considered to be handled than when using DCNS. But in fact, most of these functions are incorrect given the execution context of function-pointer calls. Secondly, the tool finds far fewer CNS defects than DCNS, and no additional ones. The modified tool marks more non-sleep function calls, which For the second tool, there are also three main differences between its results and those of DCNS. Firstly, the tool handles fewer function-pointer calls than DCNS. Indeed, many kernel modules are only meant to be loaded in conjunction with other kernel modules, and there may be direct interactions between them. But the tool cannot detect such a relationship from the link information, and thus drops many correct functions referenced by function pointer calls, hiding calls that initiate atomic context. Secondly, the tool reports many CNS defects that are not reported by DCNS. But in fact, most of these defects are false positives, because many function-pointer calls are not handled. Finally, the tool is faster than DCNS, because the tool analyzes fewer functions that are considered to be referenced by function pointers.

Overall, we find that DCNS has fewer false negatives than the first tool, and has fewer false positives than the second tool. Thus, our file-connection-based analysis indeed improves the accuracy of CNS defect detection.

Discussion

In this section, we discuss three interesting things about CNS defects and our approach: CNS defects are "similar" but "reverse" to SAC bugs. CNS defects are similar to SAC bugs in four ways: 1) They are both related to atomic context. 2) They are both introduced when the developer does not understand what code may be executed in atomic context. 3) They both only occur in kernel-mode code, because user-mode applications never have atomic context. 4) Detecting them both requires atomic context analysis to identify the code that may be executed in atomic context.

There are also four ways in which the defect types are the reverse of each other: 1) CNS defects are caused by the non-sleep operations that are never in atomic context, while SAC bugs are caused by the sleep-able operations that are in atomic context. 2) CNS defects are introduced because developers are too conservative in using sleep-able operations, while SAC bugs are introduced because developers are too aggressive in using sleep-able functions. 3) During atomic context analysis, missing code paths that are executed in atomic context may introduce false positives when detecting CNS detects, while they may introduce false negatives when detecting SAC bugs. 4) To fix CNS defects, related non-sleep operations should be changed to sleep-able operations, while to fix SAC bugs, related sleep-able operations can be changed to non-sleep operations in some cases. Our previous approach DSAC is related to DCNS, but it is different. DSAC [START_REF] Bai | DSAC: effective static analysis of sleep-in-atomic-context bugs in kernel modules[END_REF] is our previous approach of detecting sleep-in-atomic-context (SAC) bugs. DSAC and DCNS both check the Linux kernel and identify the code in atomic context. But they are quite different due to three main aspects. Firstly, DSAC targets SAC bugs, while DCNS targets DCNS defects. Secondly, DSAC uses a hybrid of flow-sensitive and -insensitive analysis to handle one kernel module at a time, and it only analyzes code paths within the module. DCNS uses a summary-based analysis to handle the whole kernel code involving multiple kernel modules, and it analyzes code paths across different kernel modules. Finally, DSAC does not consider function pointers, but still finds real bugs. However, without handling function pointers, DCNS produces many false positives, because it has only partial knowledge of the execution context of the faulty code and cannot cover complete code paths of non-sleep operations. Thus, DCNS uses a file-connection-based alias analysis to identify the set of functions referenced by a function pointer. Our file-connection-based alias analysis is applicable to other kernel problems. As shown in Section 6.3, 55% of unhandled function calls are caused by no initialization of a relevant function pointer. In these cases, if the code does not test whether the pointer is null before making the call, a null pointer dereference bug may occur. In fact, we did find several such bugs that have been confirmed by kernel developers, although this is not the main focus of this work and thus we do not provide further details. Moreover, our alias analysis can help to build a full call graph of the kernel code, from which it should be possible to detect hard-to-find kernel bugs, such as double free and double lock errors.

8 Related Work 8.1 Bug Finding in Systems Software Engler et al. [START_REF] Engler | Checking system rules using system-specific, programmer-written compiler extensions[END_REF] made the first static analysis that could scale up to complete real OS kernels, by accepting the possibility of some false negatives and false positives. Chou et al. [START_REF] Chou | An empirical study of operating system errors[END_REF] followed up on this work by using the proposed analysis to conduct an extensive survey of bugs across the history of the Linux kernel; this work was reprised a decade later by Palix et al. [START_REF] Palix | Faults in Linux 2.6[END_REF] for more recent kernel versions. Although some of the considered bug types, including sleeping in atomic context, can benefit from inter-procedural analysis, they all involve finding the existence of a faulty execution path, rather than requiring checking all possible execution paths, as needed for detecting CNS defects. A paper by Hallem et al. [START_REF] Hallem | A system and language for building system-specific, static analyses[END_REF] that presents the analyses behind the former works does not mention function pointers.

Inspired by the initial works, a number of bug finding approaches targeting systems code have been proposed. Engler et al. [START_REF] Engler | Bugs as deviant behavior: a general approach to inferring errors in systems code[END_REF] and Li et al. [START_REF] Li | PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code[END_REF] use statistics to mine and then check API usage rules. These approaches focus on common patterns occurring within a single function. Lawall et al. [START_REF] Lawall | WYSIWIB: a declarative approach to finding API protocols and bugs in Linux code[END_REF] propose patterns that can be instantiated to find various kinds of bug types, such as incorrect return values, but again do not consider function pointers. Saha et al. [START_REF] Saha | Hector: detecting resource-release omission faults in error-handling code for systems software[END_REF] find resource-release omission faults by comparison with other resource-release operations in the same function. This work includes inter-procedural analysis, but only across direct calls to other functions in the same file. Our previous approach DSAC [START_REF] Bai | DSAC: effective static analysis of sleep-in-atomic-context bugs in kernel modules[END_REF] detects sleep-in-atomic-context bugs in kernel modules, but it does not handle function pointers.

Several previous approaches do take into account function pointers. Gunawi et al. [START_REF] Haryadi | EIO: error handling is occasionally correct[END_REF] and Rubio-González et al. [START_REF] Rubio-González | Error propagation analysis for file systems[END_REF] study the propagation of errors in file system code. Like our approach, they focus on function pointers stored in data structure fields. They collect alias information based on static initializations and direct assignments, and use the collected information to transform function-pointer calls to switch statements considering all collected possibilities. We initially tried a similar approach, but found that it led to too many false positives. Indeed, these previous approaches analyze a single module at a time, and thus they do not need to handle function pointers across multiple modules. But finding CNS defects typically requires starting from the kernel core and tracing execution paths outward between the core and the individual kernel modules, which greatly increases the risk of confusion.

Smatch [START_REF] Smatch | Smatch: a static bug-finding tool for the Linux kernel[END_REF] is an open-source static analysis tool that mainly targets finding bugs in the Linux kernel. It collects function pointers that are stored in a given structure field or array element, passed into a particular function parameter, or returned from a particular function. The set of pointers considered at a given call site is refined by function arity. The precision is thus comparable to that of Gunawi et al. and Rubio-González et al., as discussed above. Smatch does not provide a checker for CNS defects.

Alias Analysis

Many approaches have been proposed to analyze pointers in C/C++ programs. Most of these approaches are based on either Andersen's algorithm [START_REF] Ole | Program analysis and specialization for the C programming language[END_REF] (e.g. [START_REF] Hardekopf | Flow-sensitive pointer analysis for millions of lines of code[END_REF][START_REF] Sui | Making contextsensitive inclusion-based pointer analysis practical for compilers using parameterised summarisation[END_REF][START_REF] Whaley | An efficient inclusion-based points-to analysis for strictly-typed languages[END_REF][START_REF] Yu | Level by level: making flow-and context-sensitive pointer analysis scalable for millions of lines of code[END_REF]) or Steensgaard's algorithm [START_REF] Steensgaard | Points-to analysis in almost linear time[END_REF] (e.g. [START_REF] Das | Unification-based pointer analysis with directional assignments[END_REF][START_REF] Fähndrich | Scalable context-sensitive flow analysis using instantiation constraints[END_REF][START_REF] Livshits | Tracking pointers with path and context sensitivity for bug detection in C programs[END_REF][START_REF] Ye | Region-based selective flowsensitive pointer analysis[END_REF]). Some approaches focus on handling pointers in data structure fields, and provide field-sensitive (e.g. [START_REF] Avots | Improving software security with a C pointer analysis[END_REF][START_REF] Emami | Context-sensitive interprocedural points-to analysis in the presence of function pointers[END_REF][START_REF] Lattner | Making context-sensitive points-to analysis with heap cloning practical for the real world[END_REF][START_REF] David J Pearce | Efficient fieldsensitive pointer analysis of C[END_REF]), or field-based (e.g. [START_REF] Heintze | Ultra-fast aliasing analysis using CLA: a million lines of C code in a second[END_REF][START_REF] Lhoták | Scaling Java points-to analysis using Spark[END_REF][START_REF] Sridharan | Demand-driven points-to analysis for Java[END_REF]) analysis. Field-sensitive analysis uses a separate variable to model the field information for each instance, while field-based analysis uses one variable to model all instances of a particular data structure field. For example, Lattner et al. [START_REF] Lattner | Making context-sensitive points-to analysis with heap cloning practical for the real world[END_REF] propose a field-sensitive and flow-insensitive pointer analysis algorithm named DSA. DSA is Steensgaardstyle, and uses some optimizations to speed up the analysis. Heintze and Tardieu [START_REF] Heintze | Ultra-fast aliasing analysis using CLA: a million lines of C code in a second[END_REF] propose a field-based and flowinsensitive pointer analysis approach. It is Andersen-style, and uses the data structure type and field name to maintain field sensitivity. Some of the above approaches (e.g. [START_REF] Hardekopf | Flow-sensitive pointer analysis for millions of lines of code[END_REF][START_REF] Heintze | Ultra-fast aliasing analysis using CLA: a million lines of C code in a second[END_REF][START_REF] Lattner | Making context-sensitive points-to analysis with heap cloning practical for the real world[END_REF][START_REF] Milanova | Precise call graphs for C programs with function pointers[END_REF]) can handle function pointers, but they are reported to produce many false results on such data in large and complex software. Indeed, they do not consider the calling context of a functionpointer call, and just produce all the functions possibly referenced by the called function pointer according to type and field information. Thus, many reported functions may be false for a given function-pointer call. In this paper, building on the field-based analysis of Heintze and Tardieu, we add file connection guidance to improve the analysis accuracy of function-pointer calls.

Conclusion

In this paper, we have proposed a practical static approach named DCNS, to automatically detect conservative non-sleep defects in the Linux kernel. DCNS uses two key techniques: 1) a summary-based analysis to effectively identify the code in atomic context; 2) a file-connection-based alias analysis to correctly identify the set of functions referenced by a function pointer. We evaluated DCNS on Linux 4.16, and in total found 1629 CNS defects. We manually checked 943 defects whose call paths are not so difficult to follow, and found that 890 are real. We randomly selected 300 of the real defects and sent them to kernel developers, and 251 have been confirmed.

As future work, DCNS can be improved in several ways. Firstly, the current implementation of DCNS can be improved to reduce false positives. For example, DCNS fails to handle some function-pointer calls, typically when the function pointer is initialized in complex ways (like function-pointer arrays). Secondly, we have only evaluated DCNS for the Linux kernel. In fact, sleep-in-atomic-context defects have been also found in FreeBSD and NetBSD kernel code [START_REF] Bai | DSAC: effective static analysis of sleep-in-atomic-context bugs in kernel modules[END_REF], and thus these kernels may exhibit CNS defects as well. Finally, our file-connection-based alias analysis is applicable to other kernel problems.

Figure 2 .

 2 Figure 2. Atomic context analysis.

Figure 3 .

 3 Figure 3. Example of identifying functions referenced by the function pointer.

Figure 4 .

 4 Figure 4. Procedure of file-connection-based alias analysis.

Figure 5 .

 5 Figure 5. Overall architecture of DCNS.

Figure 6 .

 6 Figure 6. Example of unhandled function-pointer call. (File: linux-4.16/drivers/infiniband/hw/hfi1/driver.c)

Figure 7 .

 7 Figure 7. Example of unhandled interrupt handler function. (File: linux-4.16/drivers/scsi/aacraid/sa.c)

  (a) Defects in the kernel. (b) Defects in drivers.

Figure 8 .

 8 Figure 8. Defect distribution in the Linux kernel.

---a / drivers / net / ethernet / intel / e1000 / e1000_hw .c + ++ b / drivers / net / ethernet / intel / e1000 / e1000_hw .c @ @ -5716 ,85 +5716 ,85 @@ static s32 e1000_polarity_reversal_workaround (...) { ... /* Recommended delay time after link has been lost */ - mdelay (1000); + msleep (1000); ret_val = e1000_write_phy_reg (...); if ( ret_val ) return ret_val ; - mdelay (50); + msleep (50); ret_val = e1000_write_phy_reg (...); if ( ret_val ) return ret_val ; - mdelay (50); + msleep (50); ret_val = e1000_write_phy_reg (...); if ( ret_val ) return ret_val ; - mdelay (50); + msleep (50); ... }

	Figure 1. Part of a patch for fixing CNS defects in the e1000
	driver of Linux 3.2.
	• S2: Without applying the patch, and changing the net-
	work link status once during the test.
	• S3: Applying the patch, and keeping the network link
	status unchanged during the test.
	• S4: Applying the patch, and changing the network link
	status once during the test.
	Table 1 shows the results. By comparing the results of S1
	and S2, we find that without fixing the CNS defects, when
	the network link status is changed, the execution time of the

Table 1 .

 1 Running time of the benchmark.

	N (CPU)	S1	S2	S3	S4
	1	16.7s 20.9s 16.7s 16.8s
	2	8.3s	10.1s	8.3s	8.3s
	3	5.7s	6.8s	5.7s	5.8s
	4	4.5s	5.1s	4.5s	4.5s

Table 2

 2

	shows the total number of commits between Linux
	4.0 (released in April 2015) and Linux 4.12 (released in July
	2017) that fix CNS defects by changing mdelay (non-sleep)
	to msleep (sleep-able) or usleep_range (sleep-able), and
	by changing GFP_ATOMIC (non-sleep) to GFP_KERNEL (sleep-
	able). During this period, the Linux kernel received almost
	160K non-merge commits, amounting to almost 6000 per
	month, of which only around 1 commit per month fixes such
	a CNS defect. Furthermore, only one of the CNS-defect fixing
	commits mentions the use of a tool, checkpatch [5]. While
	checkpatch is well known to kernel developers for checking

Table 2 .

 2 Commits of fixing CNS defects in Linux 4.0 to 4.12.

	Time	Total Per month Wait GFP Flag	Tools
	2015 (Apr-Dec)	13	1.44	6	7	none
	2016 (Jan-Dec)	11	0.92	4	7	none
	2017 (Jan-Jun)	4	0.67	3	1	checkpatch (1 commit)

HandleCall(mycall, path_stack, lock_stack)

	AtomicAnalysis: Identify the code in atomic context
	1: InitializeFunctionSummary();	1: if lock_stack == ø and g_intr_flag == FALSE then
	2: g_cur_file := GetCurrentSourceFileName();	2:	return;
	3: foreach func_call in spinlock_func_set do	3: end if
	4:	myblock := GetBasicBlock(func_call);	4: func_set := ø;
	5:	lock_stack := ø; path_stack := ø; g_intr_flag := FALSE;	5 if mycall is a call to a function pointer then
	6:	HandleBlock(block, path_stack, lock_stack);	6	/* File-connection-based alias analysis to
	7: end foreach	7	* get the set of referenced functions */
	8: foreach func in intr_handler_func_set do	8:	func_set := FileConnAliasAnalysis(mycall, g_cur_file);
	9:	lock_stack := ø; path_stack := ø; g_intr_flag := TRUE;	9: else
	10:	entry_block := GetEntryBlock(func);	10:	myfunc := GetCalledFunction(mycall);
	11:	HandleBlock(entry_block, path_stack, lock_stack);	11:	Push myfunc into func_set;
	12: end foreach	12: end if
			13: foreach func in func_set do
	HandleBlock(myblock, path_stack, lock_stack)	14:	HandleFunc(func, path_stack, lock_stack);
	1: if PathHasExisted(myblock, path_stack, lock_stack) == TRUE then	15: end foreach
	2: 3: end if return; /* prevent infinite handling on loops and recursive calls */	HandleFunc(myfunc, path_stack, lock_stack)
	4: AddPathStack(myblock, path_stack);	1: if FindFuncSummary(myfunc, lock_stack, g_intr_flag) == TRUE then
	5: foreach func_call in FunctionCallList(myblock) do	2:	return;
	6:	if func_call is a call to a spin-lock function then	3: end if
	7	Push func_call onto lock_stack;	4: AddFuncSummary(myfunc, lock_stack, g_intr_flag);
	8:	else if func_call is a call to a spin-unlock function then	5: if g_intr_flag == TRUE or HaveSpinFuncCall(myfunc) == FALSE then
	9:	Pop an item from lock_stack;	6:	/* Flow-insensitive analysis */
	10:	else if func_call is a call to a non-sleep function then	7:	foreach call in FunctionCallList(myfunc) do
	11:	MarkNonSleepFunction(func_call);	8:	HandleCall(call, path_stack, lock_stack);
	12:	else	9:	end foreach
	13:	HandleCall(func_call, path_stack, lock_stack);	10: else
	14:	end if	11:	/* Flow-sensitive analysis */
	15: end foreach	12:	entry_block := GetEntryBlock(myfunc);
	16: if lock_stack == ø and g_intr_flag == FALSE then	13:	HandleBlock(entry_block, path_stack, lock_stack);
	17:	return;	14: end if
	18: end if
	19: foreach block in SuccessorBlocks(myblock) do
	20:	HandleBlock(block, path_stack, lock_stack);
	21: end foreach

(b) shows three examples. Because this function 1

Table 3 .

 3 Detection of known defects.

	Root Cause	Defects DCNS Example Commit IDs
	mdelay	16	16	8c15d66e429a, 3e0f86b33709
	GFP_ATOMIC	30	26	9ec6f6b89a13, 55bf851b4ad7
	Total	46	42	9631739f8196 (not found by DCNS)

Table 4 .

 4 Detection results on Linux 4.16.

		Description	DCNS
	Code handling	Source files (.c) Source code lines	16.6K 12.1M
	Atomic context analysis	Handled interrupt handler functions Handled functions Function summaries	1408 181K 323K
	Function-pointer analysis	Handled function-pointer calls Unhandled function-pointer calls Identified referenced functions Discarded referenced functions	23,680 1996 245K 1435K
	Defect detection	Non-sleep operations Final CNS defects	4589 1629
		P1: Code information collection	13m
	Time usage	P2: Direct file connection extraction P3: Code analysis of atomic context	10m 56m
		Total	79m

Table 5 .

 5 Sensitivity results of file-connection-based analysis. But in fact, most of these calls are indeed real CNS defects, and thus false negatives. Referring to our manually checked results in DCNS, we find that the first tool finds 244 defects that have been manually checked, and 224 are real defects. Finally, the tool requires much more time than DCNS, as it analyzes more functions that are considered to be referenced by function pointers than DCNS does.

		Description	Tool 1	Tool 2
	Function-pointer analysis	Handled function-pointer calls Unhandled function-pointer calls Identified referenced functions Discarded referenced functions	30583 2491 2723K 0	830 8975 1586 142K
	Defect detection	Final CNS defects Manually checked defects Real defects	627 244 224	2954 943 890
		P1: Code information collection	13m	13m
	Time usage	P2: Direct file connection extraction P3: Code analysis of atomic context	0m 351m	10m 31m
		Total	364m	54m
	are in the functions newly identified as being referenced by
	functions pointers.

Indeed, spinlocks are designed according to this principle, where they spin for a short time in case the lock becomes available quickly, and then sleep if it is necessary to wait for a longer time.

The Linux kernel documentation for sleep and delay: https://www.kernel.org/doc/Documentation/timers/timers-howto.txt

The Linux kernel documentation for memory allocation: https://www.kernel.org/doc/htmldocs/kernel-api/API-kmalloc.html

The Linux kernel driver interface: https://www.kernel.org/doc/Documentation/process/stable-apinonsense.rst

Acknowledgments

We would like to thank the Linux kernel developers who gave helpful feedback on our defect reports and patches. Shi-Min Hu is the corresponding author.


Fuster Beatrice

Deborah Houssin-Agbomson

Gilles Bernard-Michel

Guy Dang-Nhu

Simon Jallais

Elena Vyazmina

Mike Kuznetsov

Vladimir Molkov

Boris Chernyavskiy

Volodymyr Shentsov

Guidelines and recommendations for indoor use of fuel cells and hydrogen systems

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Pauline Maurice

Vincent Padois

Yvan Measson

Philippe Bidaud

Digital Human Modeling for Collaborative Robotics

Keywords: digital human model, collaborative robotics, dynamic simulation, human-robot physical interaction, ergonomics, robot design, human motion simulation. Figure Left: HookAssist (Kinea Design) for beef boning. Center: Lightweight robot

Work-related musculoskeletal disorders in industry represent a major health problem in many developed countries. Collaborative robotics, which allows the joint manipulation of objects by both a robot and a person, is a possible solution. But efficiently designing such assistive robots requires to assess the ergonomic benefit they offer. Similarly to other domains such as automotive or workstation design, the use of a digital human simulation (DHS) can cut down the development cost and time by replacing the physical mock-up with a virtual one easier to modify. However, simulating human-robot collaborative tasks poses specific challenges because the human and the robot form a highly coupled dynamic system in which the motion of each partner depends on the forces exchanged. Therefore a dynamic simulation is required to obtain reliable measurements for ergonomic assessments. The first part of this chapter details the challenges of DHS for collaborative robotics. State-of-the-art work on DHS with collaborative robots is reviewed to identify which questions currently remain open. An optimization-based controller is then proposed to animate a digital human model (DHM) in the context of human-robot collaboration. The second part of this chapter presents an application of the DHM controller. A human-robot collaborative task is successfully simulated and allows to quantify the effect of kinematic, dynamic and control parameters of the robot on the DHM posture and effort.

Introduction

Work-related musculoskeletal disorders (WMSDs) are the first cause of occupational diseases in developed countries [START_REF] Schneider | OSH [Occupational Safety and Health] in Figures: Workrelated Musculoskeletal Disorders in the EU-Facts and Figures[END_REF][START_REF] Parent-Thirion | Fifth European working conditions survey, European foundation for the improvement of living and working conditions[END_REF]; US Department of Labor, 2016). They represent a major health issue and a significant cost for companies. WMSDs develop when biomechanical demands at work repeatedly exceed workers' physical capacity [START_REF] Punnett | Work-related musculoskeletal disorders: the epidemiologic evidence and the debate[END_REF]. Despite growing automation, numerous strenuous tasks cannot be fully automatized, at all or at a reasonable cost. With the increase of product variants built at the same assembly line associated to small order sizes, human flexibility and cognitive skills remain needed. In such situations, collaborative robotics has the potential to reduce workers exposure to WMSDs risk factors, while keeping them in control of the task execution [START_REF] Krüger | Cooperation of human and machines in assembly lines[END_REF][START_REF] Schmidtler | Human Centered Assistance Applications for the working environment of the future[END_REF]. Collaborative robotics takes multiple forms, from shared workspace, where a human and a robot work sideby-side without physical separation, to direct physical interaction where a human and a robot cooperatively work on a common task (co-manipulation, Fig. 1). Specifically, co-manipulation robots can provide a variety of benefits, such as strength enhancement, weight compensation or movement guidance [START_REF] Colgate | Intelligent assist devices in industrial applications: a review[END_REF].

Alleviating workers' physical load is among the primary goals of the deployment of collaborative robots in workplaces. Yet, the efficacy of a collaborative robot regarding the reduction of WMSDs risks is highly taskdependent. Faber et al. list ergonomic requirements and standards for human-robot physical cooperation [START_REF] Faber | Human-robot cooperation in future production systems: analysis of requirements for designing an ergonomic work system[END_REF]. However standards provide non task-specific thresholds: they serve to guarantee safety and integrity, not to optimize the benefit provided by a robot. Therefore, when designing either a dedicated robot or a workstation including a collaborative robot, an ergonomic assessment of the robot-worker system should be performed throughout the design process. Such an assessment is however hardly ever carried out, because of the lack of appropriate tools.

Ergonomic assessments traditionally rely on pen-and-paper worksheets filled by experts observing operators at work (e.g. Rapid Upper-Limb Assessment RULA, European Assembly Worksheet EAWS) [START_REF] Li | Current techniques for assessing physical exposure to work-related musculoskeletal risks, with emphasis on posture-based methods[END_REF][START_REF] David | Ergonomic methods for assessing exposure to risk factors for work-related musculoskeletal disorders[END_REF][START_REF] Mcatamney | RULA: a survey method for the investigation of work-related upper limb disorders[END_REF][START_REF] Schaub | The European assembly worksheet[END_REF]. However digital evaluations now tend to replace physical evaluations in domains such as vehicle and workstation design [START_REF] Chaffin | Human motion simulation for vehicle and workplace design[END_REF]. Digital evaluations rely on a digital human model (DHM) to simulate the human operator within a CAD model on the environment, and thereby offer several advantages over their physical counterparts. Digital human simulation (DHS) allows testing various human morphologies without having to recruit a wide variety of participants. Furthermore, within an iterative design process, modifications of the prototype are easier and cheaper to implement on a virtual mock-up compared to a physical one. Thus, despite an initial additional cost due to the animation development time, DHS reduces final design costs [START_REF] Chaffin | Human motion simulation for vehicle and workplace design[END_REF]. These advantages make DHS a promising tool for designing collaborative robots or collaborative workstations. DHS of a human-robot system would allow a company to test several existing robots in order to identify the best-suited for a specific application, without having to buy all these robots. When designing a new robot from scratch, DHS would leave engineers more freedom to explore innovative designs by removing the constraint of building a new physical prototype every time a parameter of the mechanical structure is updated.

Requirements of DHS for collaborative robotics

DHS is now commonly used to design and evaluate workstations and vehicles. Many commercially available DHS software embed ergonomic modules (e.g. Jack [START_REF] Raschke | The Jack human simulation tool. Working postures and movements: tools for evaluation and engineering[END_REF], Delmia (ref missing), EMA [START_REF] Fritzsche | Introducing ema (Editor for Manual Work Activities)-A New Tool for Enhancing Accuracy and Efficiency of Human Simulations in Digital Production Planning[END_REF], RAMSIS [START_REF] Seidl | The RAMSIS and ANTHROPOS Human Simulation Tools. Working postures and movements: tools for evaluation and engineering[END_REF], IMMA [START_REF] Högberg | Creating and shaping the DHM tool IMMA for ergonomic product and production design[END_REF]). Yet, a DHS for assessing the ergonomic benefit provided by a robot physically interacting with a human must implement some specific features.

Simulation of robot motion

The CAD model of the robot needs to be included in the simulation framework and animated. Many DHS software enable the simulation of moving elements, thereby allowing reachability, collision and operating time analysis of human-robot collaborative workstations. Ruiz Castro et al. present an ergonomic assessment of a human-robot welding task with IMMA [START_REF] Ruiz Castro | IPS IMMA for designing human-robot collaboration workstations[END_REF]. Busch et al. address the question of planning a robot trajectory that minimizes physical stress on the worker [START_REF] Busch | Application of a character animation SDK to design ergonomic human-robot-collaboration[END_REF]. However both studies only address shared workspace: none of the task involves direct physical interaction between the human and the robot, so robot trajectories are entirely preplanned.

Conversely co-manipulation robots involve force exchange between the human and the robot, either directly or through a co-manipulated object. The motion of the robot is rarely fully preplanned, but instead depends on the force the human applies on it. The simulation should therefore allow such interactive force-dependent behaviors. Ore et al. use IMMA to compare productivity and ergonomics of an assembly task performed by a worker alone, by an industrial robot alone, and jointly by a worker and a robot [START_REF] Ore | Human industrial robot collaboration-development and application of simulation software[END_REF]. In the collaborative scenario, the robot motion is controlled by the worker through force sensors in the robot joints. However, the force-dependent behavior is limited to the robot since the generation of the DHM movement in IMMA is based on kinematics [START_REF] Högberg | Creating and shaping the DHM tool IMMA for ergonomic product and production design[END_REF].

Simulation of human motion

In co-manipulation, the human-robot force exchange also affects the human motion, whether because moving the robot requires additional effort, or because the robot alleviates the physical load on the worker (e.g. robots providing strength enhancement or weight compensation). Currently, most DHM animation techniques rely on kinematics only, thus ignoring the inertial properties of the human body and the effect of an external load. In addition, many DHM software provide a library of predefined behaviors such as walk, grasp, reach. However those movements become unrealistic when loading conditions change, which is common in human-robot co-manipulation (the force exchanged is not constant). The DHM software Jack also provides a module for posture optimization which takes external force into account. However only static forces are considered while dynamic forces are ignored. Yet, co-manipulation robots can be powerful thus heavy; due to the high inertia, moving/stopping such a robot may require additional effort from the human (dedicated control laws are designed to compensate these phenomena, but the compensation is never perfect and the robot is not fully backdrivable). Therefore considering dynamic forces is needed to generate a realistic DHM movement in a human-robot co-manipulation scenario.

Alternatively, many DHS software enable importing motion capture data to animate the DHM. However the movement is realistic only if the human participant and the avatar experience a similar environment, especially in terms of interaction force. The participant must therefore be placed in a virtual reality set-up and provided with force feedback. Dombrowski et al. use such a set-up with Delmia to simulate a humanrobot collaborative task on an automotive assembly line [START_REF] Dombrowski | Interactive Simulation of Human-robot Collaboration Using a Force Feedback Device[END_REF]. However motion capture based animation requires heavy instrumentation of the participants and is therefore highly time and resource consuming.

Concurrently to DHS software for workstation design, biomechanical software such as OpenSim [START_REF] Delp | OpenSim: open-source software to create and analyze dynamic simulations of movement[END_REF] or AnyBody [START_REF] Damsgaard | Analysis of musculoskeletal systems in the AnyBody Modeling System[END_REF] provide detailed musculoskeletal models of the human body. These software can generate DHM movements based on optimization of muscle activation and forward dynamics. The resulting movement is more realistic than with kinematic techniques, but the computation time is much longer. Furthermore, interactive control laws of collaborative robots cannot be simulated in these software.

Thus, despite the diversity of software that exist for simulating human activity, none of them is suitable to analyze a task involving a human and a collaborative robot working together. The main limitation of existing software is that they do not provide dynamic simulation, which is necessary to obtain realistic movements of the robot and of the DHM.

DHM controller for human-robot dynamic simulation

In order to circumvent the aforementioned limitations of existing DHM animation techniques, we propose to apply a control technique traditionally used in humanoid robotics. The motion of the DHM is computed by solving an optimization problem to find the actuation variables (joint torques and contact forces) which enable to follow some objectives at best (e.g. hand or foot trajectory, hand force), while respecting physical and biomechanical constraints. Unlike analytical control techniques [START_REF] Sentis | A whole-body control framework for humanoids operating in human environments[END_REF], optimization techniques explicitly guarantee that both equality and inequality constraints are respected [START_REF] Abe | Multiobjective control with frictional contacts[END_REF][START_REF] Kanoun | Prioritizing linear equality and inequality systems: application to local motion planning for redundant robots[END_REF][START_REF] Salini | Synthesis of complex humanoid whole-body behavior: a focus on sequencing and tasks transitions[END_REF][START_REF] Escande | Hierarchical quadratic programming: Fast online humanoid-robot motion generation[END_REF]. De Magistris et al. already proposed an optimization-based controller for DHM animation [START_REF] De Magistris | Dynamic control of DHM for ergonomic assessments[END_REF]. However it is based on a Jacobian-transpose method which does not guarantee the optimality of the solution, because joint torques limits cannot be explicitly included in the optimization.

LQP Controller

In this work, we use a linear quadratic programming (LQP) controller framework developed by Salini et al. [START_REF] Salini | Synthesis of complex humanoid whole-body behavior: a focus on sequencing and tasks transitions[END_REF]. Linear quadratic programming handles the optimization of a quadratic objective that depends on several variables, subjected to linear equality and inequality constraints. The control problem is formulated as follows: where τ is the vector of joint torques, wcj the contact wrench of the j-th contact point (ground reaction force and human-robot interaction force), q the generalized coordinates of the system (joint angles), ν the generalized velocity concatenating the free-floating base twist and the joint velocities q̇, and 𝕏 =(τ T , wc T ,𝝂̇𝑇) T . The equality constraint corresponds to the equation of motion. Including it in the list of constraints guarantees the dynamic consistency of the resulting movement. M is the inertia matrix of the system, C the vector of centrifugal and Coriolis forces, g the vector of gravity forces, S the actuation selection matrix due to the free-floating base, and Jcj the Jacobian of contacts. The inequality constraint includes the bounds on the joint positions, velocities, and torques, and the contact existence conditions for each contact point according to the Coulomb friction model:

𝐶 𝑐𝑗 w cj ≤ 0 ∀𝑗 𝐽 𝑐𝑗 (𝒒) 𝝂̇+ 𝐽 ̇𝑐𝑗 (𝝂, 𝒒)𝝂 = 0 ∀𝑗
where Ccj is the linearized friction cone of the j-th contact point. Including the contact existence condition in the constraints ensures that the balance of the DHM follows the laws of physics.

Tasks definition

The objective function is a weighted sum of tasks Ti (weights ωi) representing the squared error between a desired acceleration or wrench and the system acceleration/wrench. Since the human body is kinematically redundant, a same Cartesian motion (e.g. hand trajectory) can be achieved by different combinations of joint motions. Human-beings use this redundancy to perform several tasks simultaneously, e.g. manipulation and postural tasks. The weighted sum strategy handles several potentially conflicting tasks, by making a compromise between the different tasks, based on their relative importance. The following tasks are defined:

 Operational space acceleration ‖𝐽 𝑖 𝝂̇ + 𝐽 ̇𝑖𝝂 -𝑿 ̈𝒊 * ‖ 2  Joint space acceleration ‖𝒒̈-𝒒̈ * ‖ 2  Operational space wrench ‖𝒘 𝒊 -𝒘 𝒊 * ‖ 2  Joint torque ‖𝝉 -𝝉 * ‖ 2
where Ẍi is the Cartesian acceleration of body i, and wi the wrench associated with body i. The superscript * refers to the desired acceleration/force. The desired acceleration is defined by a proportional derivative control: 𝒛̈ * = 𝒛̈𝑔 𝑜𝑎𝑙 + 𝐾 𝑣 (𝒛̇𝑔 𝑜𝑎𝑙 -𝒛̇) + 𝐾 𝑝 (𝒛 𝑔𝑜𝑎𝑙 -𝒛)

where z stands for X or q, and Kp and Kv are the proportional and derivative gains. The superscript goal indicates the position, velocity and acceleration wanted for the body or joint (reference trajectory).

The tasks Ti which compose the objective function vary depending on the specific activity that is simulated. Yet some generic tasks can be defined. Balance is the main priority. It is managed with a high weight center of mass acceleration task, which reference is computed using a Zero Moment Point preview control [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF]. Hands operational acceleration and/or force tasks are given the second highest weight because they determine whether the job is correctly performed (as well as feet tasks if walking is involved). The reference trajectory of the hand tasks results from an interpolation between the start and end points specified by the user. If the simulated activity requires exerting a given force (e.g. pushing an object, drilling a hole), the objective force must also be specified by the user. The head is controlled with an orientation task, so that the DHM looks at what it is doing. Finally, low weight joint acceleration tasks (postural task) and joint torque tasks are used respectively to define a natural reference posture which is adopted if no other objective is defined (standing, arms along the body), and to prevent useless effort.

In order to ensure the physical consistency of the motion and forces measured in the simulation, the DHS must be run in dynamic simulation framework based on a physics engine. In this work we use the simulation framework XDE developed by CEA-LIST [START_REF] Merlhiot | The xde mechanical kernel: Efficient and robust simulation of multibody dynamics with intermittent nonsmooth contacts[END_REF]. However, the DHM controller described above can be used in any simulation environment based on a physics engine (e.g. Gazebo with Bullet, ODE, Dart...).

Application

The current section presents a proof of concept of a human-robot simulation using the DHM controller described in the previous section. A co-manipulation activity is simulated, and kinematic, dynamic, and control parameters of the robot are varied. The influence of these parameters on biomechanical quantities measured on the DHM is analyzed to evaluate the reliability and usefulness of the simulation.

Method

Task description: A manual task consisting of two different phases, free space and contact, is simulated. The DHM moves the end-effector of the robot back and forth between two points P1 and P2 along a straight line and stays 4s on each point (Fig. 2). P2 is located on the surface of a fixed rigid body, while P1 is 20cm backwards in free space. The displacement from one point to another takes 2s (free space phase). While on P2, a normal force of 80N must be exerted on the rigid body (contact phase). One work cycle lasts 12s and consists in: starting in P1, going to P2, exerting the required force, going back to P1, waiting for the next cycle. The task is simulated with and without the assistance of a collaborative robot. The condition without the robot represents the reference situation. Robot description: The collaborative robot studied in this application is a simplified version of the strength enhancement robot Cobot 7A.15 designed by RB3D and CEA-LIST (Fig. 1). The kinematic structure is a serial chain with 6 revolute joints. We compare two structures (A and B), which differ by the location and axes of two of the joints (Fig. 3). In order to test the effect of a dynamic parameter on the DHM movement, the mass of the robot is varied.

The original mass of each segment of the robot is scaled by the same parameter β. We compare 3 values for β: 0.6, 1.0 and 1.4.

The robot is controlled to provide strength enhancement: the robot joint torques are computed so that the force the robot exerts on the environment is an amplified image of the force applied by the worker onto the robot. A user handle, located on the robot end-effector, is therefore equipped with a force sensor to measure the human-robot interaction force. In addition, the robot control law compensates the robot weight and the viscous friction effects. The inertial effects are not compensated. The full control law is:

𝝉 𝒓 = 𝛼 𝐽 𝑒𝑒,𝑟 𝑇 𝑭 𝒉 + 𝒈 𝒓 (𝒒 𝒓 ) + 𝐵 𝑟 𝒒̇𝒓
where τr is the vector of robot joint torques, qr the vector of robot joint angles and q̇r the vector of joint velocities, gr the vector of gravity forces, Br the matrix of viscous friction coefficients, Jee,r the Jacobian matrix of the robot end effector, Fh the force applied by the DHM onto the robot end-effector, and α the amplification coefficient. Strength enhancement is provided only during the contact phase, i.e. on point P2.

During the free space phase, strength enhancement is not active (α = 0). We compare 4 values for α: 0, 1, 2 and 3. The theoretical value of the force the DHM needs to apply on the rigid body while in P2 is then: 80N (α=0), 40N (α=1), 26.7N (α=2) and 20N (α=3).

DHM:

The DHM used in this work is a rigid-body model consisting of 21 segments linked together by 20 joints, with a total of 45 degrees of freedom (DoFs). Each DoF is a revolute joint controlled by a single actuator (actuation variable: joint torque). Given a body size and mass, the model can be scaled according to average anthropometric coefficients to represent different morphologies.

The DHM motions are generated using the LQP controller presented in the previous section. A right hand acceleration task is created to follow the desired trajectory between P1 and P2 (straight line with a bell-shape velocity profile). A right hand force task is activated while in P2 to exert the desired contact force. The feet are immobile, i.e. there is no stepping or walking.

Data analysis: Two kinds of biomechanical quantities are measured on the DHM to evaluate the effects of the robot: joint angles and joint torques. With the DHS, angles and torques can be measured for each DoF at each timestep of the simulation. In this study, however, only the joints of the right arm are analyzed since the robot is manipulated with the right hand. A position indicator and a torque indicator are defined to represent the stress on the whole arm during the whole simulation with a single value. The position indicator Iq is:

𝐼 𝑞 = 1 𝑁 ∑ ∫ ( 𝑞 𝑖 (𝑡) -𝑞 𝑖 𝑛 𝑞 𝑖 𝑚𝑎𝑥 -𝑞 𝑖 𝑛 ) 2 𝑑𝑡 𝑇 0 𝑁 𝑖=1
and the torque indicator Iτ is:

𝐼 𝜏 = 1 𝑁 ∑ ∫ ( 𝜏 𝑖 (𝑡) 𝜏 𝑖 𝑚𝑎𝑥 (𝑡) ) 2 𝑑𝑡 𝑇 0 𝑁 𝑖=1
where N is the number of joints in the right arm (N=7), T is the duration of the simulation, qi(t) is the angle of joint i at time t, and τi(t) is the torque of joint i at time t. qi n , qi max and τi max are respectively the neutral position, joint limit and maximal torque capacity of joint i (neutral posture: standing arms along the body). In order to take fatigue into account, the torque capacity changes with time according to the model by Ma et al. [START_REF] Ma | Multi-objective optimisation method for posture prediction and analysis with consideration of fatigue effect and its application case[END_REF]:

𝜏 𝑖 𝑚𝑎𝑥 (𝑡) = 𝜏 𝑖 𝑚𝑎𝑥 (0) 𝑒 -𝑘 ∫ 𝜏 𝑖 (𝑢) 𝜏 𝑖 𝑚𝑎𝑥 (0) 𝑑𝑢 𝑡 0
where k is a fatigue rate assigned to 1min -1 , and τi max (0) is the nominal torque capacity of joint i.

Given the definition of both indicators, a higher value corresponds to higher stress. A detailed definition of the indicators is available in [START_REF] Maurice | Experimental assessment of the quality of ergonomic indicators for dynamic systems computed using a digital human model[END_REF].

Results

Tables 1, 2 and 3 present the effects of respectively the robot structure, mass and amplification coefficient on the position and torque indicators. The values presented in the tables are the percentages of increase or decrease compared to the condition without robot. Free space and contact phases are presented separately since prevailing physical phenomena and robot assistance differ in both phases. The reference is the situation without robot. The robot mass is equal for both structures and is not varied (β = 1.0). In free space, no amplification is provided, while the amplification coefficient is set to α=3 for both robots during the contact phase.

Free space (α=0) Whole cycle (α=1) Table 3: Percentage of increase/decrease in the position and torque indicators for different amplification coefficients of robot A. The reference is the situation without robot. The robot mass is not varied (β = 1.0). Results of the free space phase are not displayed since the strength enhancement is not active in free space. Therefore the value α of has no influence.

β = 0.6 β = 1.0 β = 1.4 β = 0.6 β = 1.0 β =
Effect of the robot on effort: In free space, both robot A and robot B degrade the torque indicator (Table 1).

The additional effort required in free space when working with the robot is likely due to the robot inertia which is not compensated by the control law. Indeed, the torque demand in free space increases with the robot mass (Table 2). The increase in torque is much larger with robot B, because of the orientation of the joint axes with respect to the direction of the task. With robot A, joint 1 and 2 are not useful to move the endeffector from P1 to P2 (Fig. 3). Conversely, with robot B a motion of joint 2 is needed. One more segment needs to be displaced, hence a higher inertia.

During the contact phase, both robots are equivalent regarding torque demand (Table 1). As expected, the torque indicator decreases when the robot provides more assistance (i.e. when α increases, Table 3). Nevertheless, the relation between the torque indicator and α is not inversely proportional, because fatigue is taken into account in the indicator calculation and modifies the joint torque capacity. Despite the additional effort required to move the robot in free space, the effect of the robot on torque demand across the whole work cycle is beneficial; the positive effect of strength enhancement overtakes the negative effect of additional inertia. With α=1, the torque indicator is reduced by more than 50% (Table 2).

Effect of the robot on posture: Both robot A and robot B degrade the position indicator, in free space and during the contact phase (Table 1). However the robot mass (Table 2) and amplification coefficient (Table 3) have no effect on the position indicator. Both these parameters affect the effort the DHM needs to produce (see values of the torque indicator). Therefore the change in posture is not due to a change in effort. Instead, the posture modification induced by the robot is likely due to collisions with the robot, which disrupt the DHM posture.

Discussion and Conclusion

The case-study presented above demonstrates that an LQP controller can be successfully used to animate a DHM interacting physically with a collaborative robot. Thanks to the dynamic simulation, the human-robot interaction is realistic: the robot control and the human posture both interactively adapt to the human-robot interaction force. The proposed animation technique therefore enables to quantity the biomechanical effects of kinematic, dynamic and control parameters of the robot on the human. If some phenomena could be anticipated in this simple case-study, quantifying their relative importance is not straightforward. Being able to quantify the relative ergonomic effects of different parameters is of great interest for the design of collaborative robots which often requires compromises.

Nevertheless, the reliability of the biomechanical quantities measured with the DHM depends on the realism of the DHM posture and motion. The dynamics-based animation technique generates movements that are more realistic than with purely kinematic techniques. Nevertheless, the DHM currently lacks autonomy regarding feet placement. Though the controller handles stepping and walking, the feet placement are entirely defined by the user and therefore not necessarily well-adapted to the task. Solutions for automatic online feet adaptation [START_REF] Ibanez | Emergence of humanoid walking behaviors from mixed-integer model predictive control[END_REF] and for optimal contact placement when significant external forces are at play [START_REF] Liu | Task-driven posture optimization for virtual characters[END_REF] exist. However they are purely reactive whereas a human-being usually anticipates such movements. Anticipated optimal placement of contacts requires complex planning methods [START_REF] Bouyarmane | Multi-contact stances planning for multiple agents[END_REF], which for now are computationally very expensive. More generally, simulating realistic human motions requires to understand the psychophysical principles that voluntary movements obey. The human motor control research community has established mathematical formulae for some of these principles, especially for reaching motions (Fitts's law, minimum jerk principle,...). De Magistris et al. have successfully implemented some of them in their DHM controller [START_REF] De Magistris | Dynamic control of DHM for ergonomic assessments[END_REF]. However, these improvements are currently limited because the driving principles are not yet known for all kinds of motions Despite these limitations, human-robot DHS is a promising tool for collaborative robot design. An example of application is presented in [START_REF] Maurice | Human-oriented design of collaborative robots[END_REF], where we use the DHM controller described here to automatically optimize the design of a collaborative robot for a drilling task.

  𝑇 𝑖 (𝕏) 𝑖 𝑠. 𝑡. { 𝑀(𝒒)𝝂̇+ 𝑪(𝒒, 𝝂) + 𝒈(𝒒) = 𝑆𝝉 -∑ 𝐽 𝑐𝑗 𝑇 (𝒒)𝒘 𝒄𝒋 𝑗 𝐺𝕏 ≤ 𝐡

Figure 2 :

 2 Figure 2: Simulation of the DHM performing the task assisted by the collaborative robot.

Figure 3 :

 3 Figure 3: Kinematic structure of robot A (left) and robot B (right).

Table 1 :

 1 Percentage of increase/decrease in the position and torque indicators with robot A and robot B.

		Contact (α=3)	Free space (α=0)
		Robot A	Robot B	Robot A	Robot B
	Position indicator	+16	+35	+38	+45
	Torque indicator	-79	-76	+26	+74

Table 2 :

 2 Percentage of increase/decrease in the position and torque indicators for different masses of robot A. The reference is the situation without robot. During the contact phase, the amplification coefficient is set to α=1. Results of the contact phase are not displayed because the weight of the robot is fully compensated and there is no movement, so no inertial effects, during the contact phase. Therefore dynamic parameters of the robot have no influence.

	1.4