Jack Dongarra
email: dongarra|herault@eecs.utk.edu

Thomas Herault

Yves Robert
email: yves.robert@ens-lyon.fr

Revisiting the double checkpointing algorithm

Fast checkpointing algorithms require distributed access to stable storage. This paper revisits the approach base upon double checkpointing, and compares the blocking algorithm of Zheng, Shi and Kalé [1], with the non-blocking algorithm of Ni, Meneses and Kalé [2] in terms of both performance and risk. We also extend the model proposed in [1], [2] to assess the impact of the overhead associated to non-blocking communications. We then provide a new peer-topeer checkpointing algorithm, called the triple checkpointing algorithm, that can work at constant memory, and achieves both higher efficiency and better risk handling than the double checkpointing algorithm. We provide performance and risk models for all the evaluated protocols, and compare them through comprehensive simulations.

I. INTRODUCTION

Parallel computing environments follow an exponential trend in doubling their size on a regular basis. The Top 500 ranking 1 features a typical illustration of this trend in the High Performance Computing world: the measured performance doubled every 18 months for the last 15 years. Since the multicore revolution, motivated by the impediment of frequency increase, this growth is sustained by the multiplication of cores and sockets in parallel machines. The International Exascale Software Project (IESP) [START_REF] Dongarra | The international exascale software project: a call to cooperative action by the global high-performance community[END_REF], [START_REF] Cappello | Toward Exascale Resilience[END_REF] forecasts the Exaflop mark to be reached by high performance supercomputers by 2019-2022. In their study, which proposes an outline of the characteristics of an Exascale machine based on foreseeable limits of the hardware and maintenance costs, a machine in this performance range is expected to be built from GHz processing cores, with thousands of cores per computing node (up to 10 12 flop/s/node), thus requiring millions of computing nodes to reach the goal.

A major concern in the IESP report is reliability. If we consider that failures of computing nodes are independent, the reliability probability of the whole system (i.e. the probability that all components will be up and running during the next time unit) is the product of the reliability probability of each of the components. A very conservative assumption of a fifty years MTBF (Mean Time Between Failures) translates into a probability of 0.999998 that a node will still be running in the next hour. However, if the system consists of a million of nodes, the probability that at least one unit will be subject to a failure during the next hour jumps to 1 -0.999998 10 6 > 0.86. This probability is significantly high, especially since the machine was used for only one hour. One can conclude that many computing nodes will inevitably fail during the execution of a long-running Exascale application.

A traditional approach to tolerate failures in parallel computing relies on rollback/recovery: processes can take a checkpoint of their state, together (in coordinated checkpointing protocols), or independently (in uncoordinated checkpointing protocols with message logging). In case of failures, they are rolled back from these saved states, to allow further progress of the computation. A critical point of such an approach is to store the checkpoint images efficiently and reliably. One of the reasons why uncoordinated checkpointing can provide a better efficiency than coordinated checkpointing, despite the higher overheads it imposes on a failure free execution, is because it reduces the amount of data transferred at rollback [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF].

Zheng, Shi and Kalé [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF] consider the issue of where to store the checkpoint images in order to reduce the demand on I/O during checkpoint phases. They proposed a "buddy" algorithm, that we call the double checkpointing algorithm in the rest of this paper, because it creates a copy of the process checkpoint in a remote process. In this algorithm, processes are coupled: checkpoints are kept in the storage space (local drive or memory) of the buddy, and reciprocally. Each process also keeps a local copy (local drive or memory) of its last checkpoint image. In case of failure, all living processes rollback from the local image, while the processes replacing a process victim of a failure load the corresponding checkpoints from the designated buddies. This approach allows to use the high-speed network to transfer the checkpoint, and to distribute the load of checkpoint storage (which happens in a single wave in coordinated checkpointing protocols) between all the peers of the system. The double checkpointing algorithm comes in two versions: after the blocking version of [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF], a non-blocking version has been introduced by Ni, Meneses and Kalé [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF], which exhibits better performance, because checkpointing can then be (at least partially) overlapped with computations. However, the increased performance comes with a higher risk of fatal failure, which is not addressed in [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF].

In this paper, we revisit both versions of the double checkpointing algorithm, and we introduce a unified and Figure 1: Non-blocking checkpoint algorithm (see [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF]).

extended model to assess both the performance and risk of the different strategies. Our first major contribution is to provide a quantitative assessment of the impact of nonblocking checkpointing on both performance and risk. Our second major contribution is the design of a new peer-topeer checkpointing algorithm, called the triple checkpointing algorithm, that can work at constant memory, and achieves both a higher efficiency and a better risk handling than the double checkpointing algorithm. We provide performance and risk models for all the evaluated protocols, and compare them through comprehensive simulations.

The rest of this paper is organized as follows: in Sec. II, we present the double checkpointing algorithm, together with our model extension to assess the impact of nonblocking protocols. We show how to compute the optimal checkpoint period in Sec. III. Next, we introduce the triple checkpointing algorithm in Sec. IV, and we conduct its analysis in Sec. V. Then, having a performance model for all the algorithms, we instantiate these models using a comprehensive set of parameters, and compare their efficiency and risk in Sec. VI. We discuss related work in Sec. VII. Finally, we provide concluding remarks.

II. THE DOUBLE CHECKPOINTING ALGORITHM

In this section, we review and extend the double checkpointing algorithm that has been proposed in the literature, first with a blocking version by Zheng, Shi and Kalé [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF], and then with a non-blocking version by Ni, Meneses and Kalé [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF]. In both versions, the main idea is to avoid using a centralized stable storage by storing checkpoints in local memory. To avoid the possibility for a single failure to crash the whole application, local checkpoints must be replicated. Thus platform nodes are partitioned into pairs, and each node in a pair exchanges its checkpoint with its buddy. As a consequence, each node saves two checkpoints, one locally (storing its own data) and one remotely (receiving and storing its buddy's data), hence the name double checkpointing.

The double checkpointing algorithm is a coordinated protocol where nodes operate synchronously. In what follows, we reuse the notations of [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF] whenever possible. Also, without loss of generality, it is assumed that the application progresses at unit speed when it is not slow-downed by checkpoint-related activities, so that time-units and workunits can be used indifferently. The non-blocking algorithm is illustrated in Figure 1 and is summarized below:

• Checkpoints are taken periodically, with a period P = δ + θ + σ • In the first part of the period, of length δ, each node checkpoints locally, in blocking mode. No application work is performed in parallel. • In the second part of the period, of length θ, each node checkpoints remotely, i.e. it exchanges its checkpoint file with its buddy. Some application work is performed in parallel, but not at full speed, due to the overhead induced by the concurrent communications for exchanging files. This overhead is expressed as φ work units. • In the third part of the period, of length σ, the application progresses at full speed. Altogether, in the absence of failures, the work executed during each period of length P is

W = (θ -φ) + σ = P -δ -φ
Note that in the original paper [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF], the period is decomposed is only two parts, with τ = θ + σ being the time after the local checkpoint, letting P = δ + τ and W = τ -φ. Decomposing the period into three parts is equivalent but makes thing clearer when failures strike (see Sec. III).

A key-feature of the non-blocking algorithm is to overlap computations and checkpoint file exchanges during the second part of the period of length θ, at the price of some overhead φ. Intuitively, the larger θ, the more flexibility to hide the cost of the file exchange, hence the smaller the overhead due to checkpointing in the absence of failures. However, in [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF], the overhead φ is fixed independently of the value of θ. We propose to extend the model as follows:

• When θ = θ min , the communication has the smallest possible duration. In this case it is fully blocking, and no computation can take place concurrently. The overhead is 100%, i.e., φ = θ min . • When θ = θ max , the communication is made long enough so that it can fully be overlapped with computation. In that case, the overhead is φ = 0. • We use a linear interpolation between these extremes.

The overhead is φ when the communication time is

θ(φ) = θ min + α(θ min -φ)
We derive that φ = 0 for θ = θ max = (1 + α)θ min . This last equation gives an intuitive explanation for the parameter α, which measures the rate at which the overhead decreases when the communication length increases. In a failure-free environment, both θ and σ should be made as large as possible, in order to minimize the overhead due to local and remote checkpointing. This is equivalent to letting the ratio W P tend to 1. But the advent of failures calls for smaller period lengths. Indeed, let M denote the Mean Time Between Failures (MTBF) of the platform. When a failure hits a node, which happens every M time-units in average, the work executed since the last checkpoint is lost, and must be re-executed, which induces an overhead proportional to the loss. The optimal period length P is the result of the trade-off between minimizing the waste due to checkpointing (large periods) and re-executing only a small amount of work when a failure strikes (small periods).

When a failure hits a node, there is a downtime period of length D for that node, that represent the overhead to detect the failure and allocate a new replacement node for the computation. Then we can start the recovery from the buddy node. There are two checkpoint files that have been lost due to the failure, and which the buddy node must re-send to the faulty processor: (i) the checkpoint file of the faulty node, which is needed for recovery; and (ii) the checkpoint file of the buddy node, which has been lost after the failure and which will be needed if the buddy node would fail later on.

Obviously, the first file (checkpoint of the faulty node) should be sent as fast as possible, i.e. in time θ min , because all processors are stopped until the faulty one has recovered from the failure. Using the notations of [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF], the recovery time R is thus equal to θ min . As for the second file (checkpoint of the buddy), there are two possibilities:

• The file is sent at the same speed as in regular (failurefree) mode, in time θ(φ). Some overlap is possible, and the overhead is φ. This scenario, which we call DOUBLENBL ((NBL for Non-Blocking), is the one chosen in [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF]. • The file is sent as fast as possible, in time θ min = R.

This scenario, which we call DOUBLEBOF (BOF for Blocking on Failure), does not allow for any overlap during the communication. The application is at risk as long as the faulty processor has not stored a copy of its buddy's checkpoint file. In other words, until complete reception of both messages, it is impossible to recover from a second failure that would hit the buddy. One can say that the DOUBLEBOF favors risk reduction, at the price of a higher overhead, while DOUBLENBL favors performance, at the price of a higher risk. In Sec. III, we provide a detailed analysis of the performance and risk of both strategies.

III. ANALYSIS OF THE DOUBLE CHECKPOINTING

ALGORITHM

In this section, we compute the overhead induced by the double checkpointing algorithm, and we analytically determine the optimal checkpointing period.

A. Computing the waste

Let T base be the base time of the application without any overhead due to resilience techniques. First, assume a faultfree execution of the application: every period of length P, only W = P -δ -φ units of work are executed, hence the time T ff for a fault-free execution is

T ff = P W T base (1)
Now, let T denote the expectation of the execution time with the double checkpointing algorithm (any version). T can refer to a single application or to the platform life if many jobs are running concurrently. In average, failures occur every M time-units, and for each of them we lose F time-units, so there are T M failures during the execution. Hence we derive the equation:

T = T ff + T M F (2)
which we rewrite as

1 - F M 1 - δ + φ P T = T base (3)
Defining the waste as

WASTE = 1 -1 - F M 1 - δ + φ P (4)
we can express Equation (3) as 1 -WASTE T = T base .

The waste is the fraction of time where nodes do not perform useful computations. In Equation ( 4), we identify the two sources of overhead: (i) the term WASTE ff = δ+φ P , which is the waste due to checkpointing in a fault-free execution, by construction of the algorithm; and (ii) the term WASTE fail = F M , which is the waste due to failures striking during execution. With these notations, Equation (4) writes: 1-WASTE = 1-WASTE fail 1-WASTE ff , and we derive WASTE = WASTE fail + WASTE ff -WASTE fail WASTE ff [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF] There remains to determine the (expected) value of F in each strategy, denoted as F nbl for DOUBLENBL and F bof for DOUBLEBOF. Then we will be able to determine the value of P that minimizes T in Equation ( 3), or, equivalently, that minimizes WASTE in Equation [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF].

DOUBLENBL strategy: Here we aim at determining the expected value of F nbl for the DOUBLENBL strategy, where the fault node starts by receiving its own checkpoint file in time R before the buddy's checkpoint file in time θ(φ). The faulty node undergoes a downtime and recovery, of length D + R. Then it starts re-executing the work that has been lost. The amount of work to re-execute depends upon the part of the period where the failure strikes, hence there are three cases. Now, failures strikes uniformly across the period, regardless of the distribution law of the failures: this is because the instants at which periods begin and at which faults strike are independent. Hence we can compute

F nbl = D + R + δ P RE 1 + θ P RE 2 + σ P RE 3 (6)
where RE i is the expected re-execution time when the failure strikes during the i-th part of the period. We start with the case when the failure causes the least damage i.e. when it strikes during the third part of the period, after both checkpoints have been taken. See Figure 2 for an illustration. We compute RE 3 as follows:

• The faulty processor cannot execute any work during D + R time-units. • Then it starts re-executing the work that has been lost, namely W lost = (θ -φ) + t lost . The first term corresponds to the work executed during the second part of the period, taking into account the overhead associated to this part. The second term comes from the third part of the period, where work executes at full speed. • During the first θ time-units of re-execution, there is an overhead φ due to receiving the buddy's checkpoint.

After that, the re-execution of the remaining work

W lost -(θ -φ) progresses at full speed. Altogether, the re-execution time is θ + W lost -(θ -φ) = θ + t lost . The expected value of t lost is σ
2 , because failures strike uniformly during the third part of the period. This leads to RE 3 = θ + σ 2 When a failure hits the first part of the period, during local checkpointing, it causes more damage: the work W during the whole previous period has to be re-executed, and we get W lost = W + t lost . Just as before, the re-execution time is θ + W lost -(θ -φ). Here the expected value of t lost is δ 2 . We derive:

RE 1 = θ + σ + δ 2
When a failure hits the second part of the period, during remote checkpointing, it causes the same damage as during the first part: the work W during the whole previous period has to be re-executed, and we get W lost = W +t lost . Again, the re-execution time is θ +W lost -(θ -φ), but the expected value of t lost is even higher than when the failure hits the first part of the period:

t lost = δ + θ 2 .
We derive:

RE 2 = θ + σ + δ + θ 2
We are ready to compute the value of F nbl using Equation [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]. After some simplifications, we obtain

F nbl = D + R + θ + P 2 (7)
This is almost in accordance with the value reported in [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF]: they derive the value F nbl -φ instead of F nbl , because they forgot the overhead due to receiving the second checkpoint file while re-executing.

DOUBLEBOF strategy: Here we aim at determining the expected value of F bof for the DOUBLEBOF strategy, where both checkpoint files are received in minimum time θ min = R. As before, there are three cases, depending upon the part of the period where the failure strikes, and the computation goes in a similar way as for the DOUBLENBL strategy. Indeed, for each part of the period, the amount of work to re-execute W lost is the same, but it is entirely executed at full speed instead of being slowed-down during the first θ time-units (since all communications are already completed). In other words, we add R to the recovery time to account for the second blocking message, and we suppress φ from the time needed to re-execute, which leads to:

F bof = F nbl + R -φ = D + 2R + θ -φ + P 2 (8)

B. Waste minimization

We use a computer algebra system (Maple2 ) to compute the optimal period that minimizes the total waste. We obtain the following formulas:

T O nbl = 2(δ + φ)(M -R -D -θ) (9)
T O bof = 2(δ + φ)(M -2R -D -θ + φ) (10)
There is a similarity with the formulas of Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF], namely T = √ 2M δ + δ, and of Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF], namely T = 2(M + (D + R))δ + δ. However, in both these formulas, δ represents the time needed to checkpoint the whole application onto stable storage, while with the (distributed) double checkpointing algorithm, δ is the time needed to checkpoint a single node locally. The value of the optimal period is therefore much larger for the double checkpointing algorithm than for a centralized scheme based on global remote storage. The value of the optimal waste, whose dominant term is 2δ M for all reasonably large values of M , is reduced accordingly.

C. Risk

When a failure strikes a node, the application is at risk until the faulty node has recovered and received the copy of its buddy's checkpoint. We let Risk denote the length of the risk period, which is Risk = D + 2R for DOUBLEBOF and Risk = D + R + θ for DOUBLENBL.

In this section, we compute the success probability of the application (no fatal failure throughout execution) for both strategies. Let n be the number of processors in the whole platform. Assume as in [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF] that failures strike with uniform distribution over time, and let λ = 1 nM denote the instantaneous failure rate of each processor. The inverse of λ is the individual processor MTBF and is estimated to range from a few years to one century in the literature.

Recall that T denotes the expectation of the execution time of the application with the double checkpointing algorithm (any version). Consider a pair made of one processor and its buddy. The probability of having the first processor fail during execution is λT , and the probability of having the pair failing during execution is 1 -(1 -λT ) 2 ≈ 2λT . Now, given that one processor fails, the probability of having the second one fail right after, within the risk period, is λRisk. Hence the probability that the pair experiences a fatal failure during execution is 2λT λRisk. Since the application succeeds if and only if all pairs succeed, the probability that the application will fail is 1 -(1 -2λ 2 T Risk) n/2 , or equivalently, the success probability is

P double = (1 -2λ 2 T Risk) n/2 (11)
This equation was originally given in [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF], except that they forgot the factor 2 to account for the failure probability of both processors in the pair. They also compare the value of P double with the probability P base that the application will succeed in the absence of checkpointing. In that case, the execution time is T base , and we derive that

P base = (1 -λT base ) n (12)
Equation ( 11) assesses the impact of the risk period length Risk on the resilience of the application. We can now quantitatively compare the DOUBLENBL and DOUBLEBOF strategies in terms of both performance and reliability. We provide such an evaluation in Sec. VI.

IV. THE TRIPLE CHECKPOINTING ALGORITHM

In this section, we introduce a new algorithm based on processor triples rather than on processor pairs. We show that this new algorithm is both more efficient and reliable than the double checkpointing algorithm, while equally memorydemanding. In fact, the main motivation to design a novel in-memory checkpointing algorithm is to provide a better answer to the following question: given a fixed amount of memory available for checkpointing, what is the best strategy for performance and reliability?

The double checkpointing algorithm of [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF], [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF] requires that sets of two checkpoint files can be stored in the memory of each processor. As with all coordinated checkpointing protocols, the collection, for all processes in the system, of a set of checkpoints, represents the (global) snapshot of the parallel application. Such sets must be updated atomically. This is implemented by keeping two sets at all time: the last set of checkpoints that was successful (by definition the first set of checkpoints is represented by the starting configuration of the application and is always successful), and the current set of checkpoints, that might be unfinished at the time when a failure hits the system. So, in double checkpointing algorithms, a local set contains two images: the image of the current process and the image of the buddy process. Given this memory constraint, can we do better than pairing each processor with a buddy? In fact, when a failure strikes a processor, the local checkpoint is lost, and must be recovered from the buddy. This calls for replacing the local checkpoint by that of a secondary buddy. Let us consider how checkpoint images are created: a process can create its checkpoint image using the fork system call that creates a copy in memory of the current state of the process. Modern operating systems do not create an explicit copy of all the pages of the parent process at the time of the call, but instead mark all pages of the parent process as copy-on-write, allowing to share most, if not all, the process pages. The parent process can continue its work, while the child process uploads its checkpoint image to the buddy file system, releasing its private copy of the pages as soon as they are successfully uploaded. This incurs a minimum overhead to the checkpointing process, and allows a significant overlap of application process and checkpoint transfer. If the rate of transmission is high enough, only a small number of pages will need to be actually duplicated before the child process releases them.

Buddy processes can then store the checkpoint images in their memory or in local storage, as they were doing in the double checkpointing algorithm. The system must decide for a trade-off between taking more time to upload the checkpoint image to the buddy processes in order to reduce the pressure on the network, and taking less time to upload the checkpoint image to the buddy processes in order to reduce the amount of pages that must be created with the copy-on-write mechanism. This trade-off is simplified by ordering the data that is uploaded to the buddy processes from the most likely to be modified to the least likely to be modified by the ongoing computation.

This idea leads us to the triple checkpointing algorithm, which is illustrated in Figure 3. Processors are organized in triples. Within a triple, each processor p has a preferred buddy p ′ and a secondary buddy p ′′ . We organize a rotation of buddies, so that p ′ has p ′′ for preferred buddy and p for secondary buddy, and p ′′ has p for preferred buddy and p ′ for secondary buddy.

From Figure 3, we see that the algorithm operates in a similar way as the double checkpointing algorithm. The period is still divided into three parts, but the first part is different: the local checkpoint is replaced by sending the checkpoint image to the preferred buddy (and receiving the checkpoint of the secondary buddy). The duration of the first part becomes θ(φ) instead of δ. The second part of the period is for an exchange of checkpoint files (sending to the secondary buddy and receiving from the preferred one), and its duration is θ(φ), just as before. During the third part of the period, computations proceed at full speed during σ seconds, just as before again.

The main advantage of the new scheme is to dramatically reduce the overhead induced by checkpointing (WASTE ff , the waste due to checkpointing in a fault-free execution, tends to zero) while maintaining a smaller risk, even for large values of θ that might be needed to achieve a fully nonblocking, hence overhead-free, checkpoint. Indeed, there must be three successive failures within a processor triple for the application to experience a fatal failure, instead of two failures striking a processor and its buddy in the double checkpointing algorithm.

One can envision two versions for the triple checkpointing algorithm. After a failure, the preferred buddy always sends the checkpoint file of the faulty node as fast as possible, in blocking mode, and in time θ min = R. But there is a choice for the next two communications, that correspond to the checkpoint images of the two buddies. Either these communications are executed in blocking mode and in minimum time, or they are executed in overlapped mode, in time θ(φ). The first version further reduces the risk, while the second version minimizes the overhead. Because the risk is already very low in both versions, we only deal with the second, non-blocking version, which we denote as TRIPLE.

V. ANALYSIS OF THE TRIPLE CHECKPOINTING

ALGORITHM

In this section we compute the waste and the risk of the triple checkpointing algorithm TRIPLE. We use the same notations as in Sec. III. Since the derivation is similar, we omit details and only provide final formulas.

A. Computing the waste

As before (see Equation ( 5)), there are two sources of overhead: WASTE ff , the waste due to checkpointing in a fault-free execution, and WASTE fail = Ftri M , the waste due to failures striking during execution. It is easy to derive that WASTE ff = 2φ P . As for the value of F tri , we use a modified version of Equation ( 6) to account for the different lengths of the three parts of the period:

F tri = D + R + θ P RE 1 + θ P RE 2 + σ P RE 3 (13)
We proceed to determine the (expected) value of F:

• RE 1 = 2θ + σ + θ 2 • RE 2 = 3θ 2 • RE 3 = 2θ + σ 2
which leads to

F tri = D + R + θ + P 2 (14)
We observe that the value of F is the same for DOU-BLENBL and TRIPLE (F nbl = F tri ). Hence the value of WASTE fail is the same too. However, the final waste is different, because we now have WASTE ff = 2φ P instead of WASTE ff = δ+φ P .

B. Waste minimization

As before, we use the computer algebra system to compute the optimal period that minimizes the total waste. We obtain the following formula, which is similar to the value obtained for DOUBLENBL (Equation ( 9)):

T O tri = 2 φ(M -D -R -θ) (15)

C. Risk

When a failure strikes a node, the application is at risk until the faulty node has recovered and received the copy of its two buddy checkpoints. We let Risk denote the length of the risk period, which is Risk = D + R + 2θ (note that it would be reduced to Risk = D + 3R if we used a blockingon-failure version of the algorithm).

We compute the probability of a fatal failure using the same line of reasoning as before. Let T denote the expectation of the execution time of the application with the triple checkpointing algorithm (any version). Consider a triple made of one processor and its two buddies. The probability of having one of the three processors fail during execution is 3λT , up to second order terms. Given that one processor fails, the probability of having the pair of remaining processors fail right after, within the risk period, is 2λRisk, up to second order terms. And given that situation, the probability that the last processor also fails during the risk period is λRisk. Finally, the probability that the triple experiences a fatal failure during execution is 6λ 3 T Risk 2 . Since the application succeeds if and only if all triples succeed, the probability that the application will succeed is

P triple = (1 -6λ 3 T Risk 2 ) n/3 (16)
Sec. VI provides a quantitative comparison of the success probability of the double and triple checkpointing algorithms.

VI. EXPERIMENTS

In this section, we consider the efficiency and risk of DOUBLENBL, DOUBLEBOF and TRIPLE, under different realistic conditions. Table I summarizes the two different scenarios that we consider, namely Base taken from [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF] and Exa which models future exscale platforms. Table I: Parameters for the different scenarios: D is the down time; δ the time to take the local checkpoint; φ, the amount of overhead; R the base time to load a remote checkpoint in blocking mode; α the overlap speedup factor, which defines θ the time to upload a remote checkpoint; n is the number of platform nodes (used for the risk assessment).

A. Base scenario

The Base scenario takes the same values as [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF]: for checkpointing a memory of 512MB, the time to produce a local checkpoint at the speed of SSDs is about 2s; for uploading the same amount of data to a remote neighbor, at the considered network speed, the time to upload (without any work in parallel) will be about 4s. Since [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF] does not consider the time to allocate a new node on the machine, we let D = 0. They consider only two cases for φ and α: when the checkpoint operation cannot overlap with any application progress (φ = R), or when checkpointing does not imply any overhead on the progress (φ = 0, and α > 0).

Figure 4 presents the waste, with the model-computed optimal checkpoint time, of each algorithm, as a function of φ (between 0 and R; the ratio φ/R is presented in the figure for normalization) and of M (from 15s, where no progress happens for any protocol, up to 1 day, where the waste is almost 0 for all), the latter shown on a logarithmic scale. By varying φ, we consider the waste when the amount of work that can be done during the checkpoint phase varies from 0 to no overhead at all. Moreover, since α = 10, checkpoint communication is completely hidden between application communications if the optimal checkpointing period allows a duration of at least (α + 1)R = 11R. We point out that this is a conservative assumption on the communication-tocomputation ratio.

Comparing the three subfigures together, one can see that TRIPLE behaves slightly differently than DOUBLENBL and DOUBLEBOF: indeed, TRIPLE takes a higher benefit of a low value of φ, because it does not suffer from the period δ during which no progress is done in the double checkpointing protocols. In a realistic setup, φ will not go down completely to 0 in the triple checkpointing protocol, because during the checkpoint transfer, some pages may need to be copied by the copy on write mechanism of fork; still, a very small ratio φ/R can be achieved for large enough values of θ, the file exchange phase. Similarly, using the same approach, the value of δ could be reduced significantly in the double checkpointing protocols, allowing for a better benefit of the φ parameter. All three kinds of protocols, however, clearly reduce their waste in a similar fashion when the MTBF increases. The differences between the three protocols is better illustrated with Figure 5 which compares the waste of the three algorithms, with a fixed value for M = 7h, relatively to the efficiency of DOUBLENBL. The benefit of a nonblocking approach is small, but noticeable: DOUBLEBOF has always a higher waste than DOUBLENBL, until the ratio of work that can be done during the checkpoint makes waiting for the checkpoint transfer transparent.

Up to φ/R ≤ 0.5, TRIPLE has a much smaller waste than any of the double checkpointing protocols. Because the number of faults is low, the dominating part of the waste comes from the failure-free case. TRIPLE does not suffer from a blocking checkpoint time, as DOUBLENBL and DOUBLEBOF do, and thus proves more efficient whenever a large amount of work can be done in parallel with the checkpoint. Once more time is spent communicating checkpoint data than computing, however, TRIPLE suffers from its double amount of data to communicate (compared to the double checkpointing approaches, TRIPLE needs to exchange twice the data on the network). The overhead, however, is limited to 15% more waste in the worst case. Furthermore, DOUBLEBOF and TRIPLE are expected to provide a better risk preservation than DOUBLENBL. This is the property that we quantify next. Figure 6a represents the relative risk between DOUBLEBOF and DOUBLENBL. A lower value means that DOUBLEBOF provides a better risk tolerance. As illustrated by the figure, this is measurable for long period of times (above 10 days), and for very low MTBF (M ≤ 60s); otherwise all protocols have a success probability almost equal to 1. On this setup, the benefit of blocking during the checkpoint is not significant, even if it induces a waste lower than 2%. Figure 6b presents the same comparison, but with TRIPLE compared to DOUBLENBL, the most secure version of double checkpointing. Again, a lower value means that TRIPLE provides a better risk tolerance than DOUBLENBL. This time, in the same range as where DOUBLEBOF was providing a small risk improvement, the gain is quite significant, providing risk mitigation by orders of magnitude. More importantly, even when the MTBF increases, and the application duration decreases, TRIPLE is able to tolerate twice more runs without incurring a fatal failure than DOUBLENBL. It is striking to point out that these numbers are achieved with θ = (α + 1)R, which corresponds to the largest possible risk duration for TRIPLE.

B. Exa scenario

We now consider a future exascale machine, as can be envisioned by the IESP work force in [START_REF] Dongarra | The international exascale software project: a call to cooperative action by the global high-performance community[END_REF], [START_REF] Cappello | Toward Exascale Resilience[END_REF]. Such a machine is summarized in Table I under the name Exa: based on the assumption of a 1-GHz limit for each core, it will hold 10 9 1-GHz cores. Taking the "slim" exascale assumption, these cores would be distributed among 10 6 nodes, with 1, 000 cores per nodes. Memory previsions plan around 64GB of memory per core, and we took the assumption of a 1TB/s/node network capacity, and 500Gb/s/node of bus limitation for the local storage capacity.

We then conducted the same set of evaluations as with the Base scenario. Results are presented in Figures 7 to 9b. First, we observe the same general behavior. TRIPLE remains more robust than double checkpointing protocols for very high failure frequency and long applications. DOUBLENBL and DOUBLEBOF have a similar waste, also, as expressed by Figure 8, but the gain of TRIPLE increases up to 25% of that of DOUBLENBL when φ/R = 1/10 while being more reliable (see Figure 9b). The model also forecasts that on such machines, the waste will be important when failures hit the system more than once a day. Last, for such an environment, Figure 9a shows that DOUBLEBOF can provide a higher reliability than DOUBLENBL, to a higher extent than on the Base scenario, for long-running applications. As expected, TRIPLE provides an even higher robustness with this respect (see Figure 9b), even with the largest possible risk period (θ = (α + 1)R).

VII. RELATED WORK

Coordinated checkpointing has been studied since many years. The major appeal of the coordinated approach is its simplicity, because a parallel job using n processors of individual MTBF M ind can be viewed as a single processor job with MTBF M = M ind n . Given the value of M , an approximation of the optimal checkpointing period can be computed as a function of the key parameters (downtime D, checkpoint time C and recovery time R). The first estimate had been given by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] and later refined by Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF].

Both use a first-order approximation for Exponential failure distributions; their derivation is similar to the approach in Equations (1) to [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF]. More accurate formulas for Weibull failure distributions are provided in [START_REF] Ling | A variational calculus approach to optimal checkpoint placement[END_REF], [START_REF] Ozaki | Distributionfree checkpoint placement algorithms based on min-max principle[END_REF], [START_REF] Bouguerra | A flexible checkpoint/restart model in distributed systems[END_REF]. The optimal checkpointing period is known only for Exponential failure distributions [START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF]. Dynamic programming heuristics for arbitrary distributions are proposed in [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF], [START_REF] Bouguerra | Complexity analysis of checkpoint scheduling with variable costs[END_REF], [START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF].

The literature proposes different works [START_REF] Plank | Processor allocation and checkpoint interval selection in cluster computing systems[END_REF], [START_REF] Jin | Optimizing HPC fault-folerant environment: an analytical approach[END_REF], [START_REF] Wang | Modeling Coordinated Checkpointing for Large-Scale Supercomputers[END_REF], [START_REF] Oldfield | Modeling the impact of checkpoints on next-generation systems[END_REF], [START_REF] Zheng | Reliability-aware scalability models for high performance computing[END_REF] on the modeling of coordinated checkpointing protocols. In particular, [START_REF] Jin | Optimizing HPC fault-folerant environment: an analytical approach[END_REF] and [START_REF] Plank | Processor allocation and checkpoint interval selection in cluster computing systems[END_REF] focus on the usage of available resources: some may be kept as backup in order to replace the down ones, and others may be even shutdown in order to decrease the failure risk or to prevent storage consumption by saving less checkpoint snapshots. The major drawback of coordinated checkpointing protocols is their lack of scalability at extreme-scale. These protocols will lead to I/O congestion when too many processes are checkpointing at the same time. Even worse, transferring the whole memory footprint of an HPC application onto stable storage may well take so much time that a failure is likely to take place during the transfer! A few papers [START_REF] Zheng | Reliability-aware scalability models for high performance computing[END_REF], [START_REF] Cappello | Preventive migration vs. preventive checkpointing for extreme scale supercomputers[END_REF] propose a scalability study to assess the impact of a small MTBF (i.e., of a large number of processors). The mere conclusion is that checkpoint time should be dramatically reduced for platform waste to become acceptable. This very conclusion is the major motivation for the development of distributed checkpoint mechanisms. A first idea is to use a multi-level approach, with local disks for a high-rate checkpointing period and global stable storage for a smaller-rate checkpointing period. Another possibility is the in-memory blocking approach (with a buddy) suggested by Zheng, Shi and Kalé [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF]. This in-memory checkpointing technique was later extended to a non-blocking version by Ni, Meneses and Kalé [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF]. As already mentioned, these two papers constitute the main motivation for this work. While [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF] discusses the advantages of the non-blocking version over the blocking version in terms of performance, it fails to mention the augmented risk. This is why we have presented a two-criteria assessment of both versions. In addition, this paper is the first attempt at providing a unified model for quantifying the impact and overhead of checkpointing in parallel with application progress.

VIII. CONCLUSION

Checkpoint transfer and storage are the most critical issues of rollback/recovery protocols for the next few years. The overhead of transferring the checkpoint images to a stable storage dominates the cost related to this approach, and algorithms that allow to distribute this load among the whole system provide a much better scalability in the number of processors. However, since checkpoint storage is not reliable anymore, these algorithms introduce a risk of nonrecoverable failures.

In this work, we have reconsidered the double checkpointing algorithms proposed by Zheng, Shi and Kalé [START_REF] Zheng | FTC-Charm++: an inmemory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF] and by Ni, Meneses and Kalé in [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF], and we have introduced a new version, the DOUBLEBOF algorithm, that takes the same approach as [START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF], but tries to reduce the duration of the risk period by focusing all resources to restore a safe state, at the cost of increasing the overhead of each failure. More importantly, we have provided a unified and extended model that allows a performance/risk bi-criteria assessment of existing and future double-checkpointing algorithms. The model incorporates a new parameter α that dictates how fast a checkpoint can be transferred to overlap entirely the transfer cost with application computation.

We have also designed a new triple checkpointing algorithm that builds on modern operating system features to save the checkpoint on two remote processes instead of one, without much more memory or storage requirements. The new algorithm has excellent success probability and almost no failure-free overhead when full overlap of checkpoint transfers can be enabled. We have derived the performance and risk factors of the new algorithm using our unified model, and we have compared these factors to those of both double checkpointing versions. We have instantiated our model with realistic scenarios, which all conclude to the superiority of the triple-checkpointing algorithm.

Future work will proceed along two main directions. First, we took conservatively high values for the new model parameter α in this study, thereby reducing the potential benefit of the triple checkpointing algorithm. We plan to extend this work by studying real-life applications and propose refined values for α for a set of widely-used benchmarks. Second, the perspective of very small MTBF values on future exascale platforms calls for combining distributed inmemory strategies such as those discussed in this paper, with uncoordinated or hierarchical checkpointing protocols with message logging, in order to further reduce the waste due to failure recovery.

Figure 2 :

 2 Figure 2: DOUBLENBL strategy, failure during third part of the period

1 fFigure 3 :

 13 Figure 3: The triple checkpointing algorithm

Figure 4 :

 4 Figure 4: Waste for Scenario Base, function of φ/R and M

Figure 5 :

 5 Figure 5: Waste for Scenario Base, (M = 7h).

Figure 6 :

 6 Figure 6: Relative success probability for Scenario Base, function of M and platform life T . θ = (α + 1)R.

Figure 8 :

 8 Figure 8: Waste for Scenario Exa, (M = 7h).

Figure 9 :

 9 Figure 9: Relative success probability for Scenario Exa, function of M and platform life T . θ = (α + 1)R.

http://www.top500.org

http://www.maplesoft.com/products/Maple/

Acknowledgments. Y. Robert is with the Institut Universitaire de France. This work was supported in part by the ANR RESCUE project.


Guillaume Bonfante

Jean-Yves Marion

Fabrice Sabatier

Aurélien Thierry

Analysis and Diversion of Duqu's Driver

The propagation techniques and the payload of Duqu have been closely studied over the past year and it has been said that Duqu shared functionalities with Stuxnet. We focused on the driver used by Duqu during the infection, our contribution consists in reverseengineering the driver: we rebuilt its source code and analyzed the mechanisms it uses to execute the payload while avoiding detection. Then we diverted the driver into a defensive version capable of detecting injections in Windows binaries, thus preventing further attacks. We specifically show how Duqu's modified driver would have detected Duqu.

Introduction

When it was first discovered in September 2011 by CrySys [START_REF] Crysys | Duqu: A Stuxnet-like malware found in the wild[END_REF], it was said that Duqu was close to Stuxnet in that they shared infection and propagation mechanisms. Duqu is an offensive tool used to steal information: Symantec [START_REF] Symantec | Duqu: The Precursor to the Next Stuxnet[END_REF] identified, amongst other payloads, keyloggers, screen recorders, network monitors and service discovery tools. It is kept up to date by Command & Control servers and bundled with an autodestruction feature typically triggered 36 days after the infection.

The attacks seem to have been successful since the malware was not detected during the operations (some of them lasted a few month) but only post-mortem. Besides, according to Kasperky [START_REF] Kaspersky | The mystery of Duqu: Part Ten[END_REF], the latest version of Duqu was found in February 2012, long after the malware was first discovered and documented. Thus Duqu is a stealthy spyware and the attacks were carefully adapted to each target.

At the High Sec Lab, we develop a malware detector based on morphological analysis [START_REF] Bonfante | Architecture of a Morphological Malware Detector[END_REF], which is a technique based on control flow graph comparison. As soon as we put our hands on Stuxnet and Duqu samples, we wanted to know if our approach, knowing Stuxnet, could lead to the detection of Duqu. In fact the answer is yes but: we recognize Duqu's main DLL as related to Stuxnet but only if it is decrypted. The aim of this paper is to present an automatic extraction procedure to bypass stealth techniques such as those used by Duqu. The irony of this work is that Duqu itself served for this purpose. Let us describe in broad terms our contribution.

Infection timeline. The infection detected by

CrySys used a malicious Microsoft Word document embedding Duqu. Firstly it exploits a 0-day kernel vulnerability (on TrueType fonts [1]), it installs three components: a driver (nfrd965.sys), an encrypted DLL (Duqu's main DLL, NETP191.PNF) and an encrypted configuration file (netp192.PNF).

The second step takes place at the next reboot. The driver monitors processes loaded by the OS and injects Duqu's DLL into a process specified by the configuration file, typically services.exe.

During the third and final step, the payload, which is included in the DLL, is activated. Detecting this malware is challenging because only the driver is unencrypted on the hard drive. The DLL is encrypted, packed with UPX, and is injected immediately after decryption so it is only stored decrypted in RAM. Thus detection could take place when the injection is done, which is right after the decryption of the DLL and before it is activated.

Once installed on a first target, Duqu receives orders for further attacks and propagation from Command & Control servers. Each new controlled machine can be configured to connect back to the attacker through some routing tunnel, providing access to restricted areas.

Defensive version.

The defense scenario will be the following. We modify Duqu's driver so it monitors loaded processes, stores hashes of their code and detects when an alteration is done.

We began by rebuilding a consistent source code for the driver from the binary, then performed an in-depth analysis of the infection method. Finally we modified the code to build a defensive version capable of monitoring loaded processes and detecting an infection.

Rebuilding the driver's source code

We knew Duqu shared code with Stuxnet since we showed equivalent parts in the drivers' main DLLs [START_REF] Thierry | Recognition of binary patterns by Morphological analysis[END_REF] and Symantec revealed similarities in the injection technique and some resources. The decompilation of Stuxnet's driver had already be done by Amr Thabet [START_REF] Thabet | Reversing Stuxnet's Rootkit (MRxNet) Into C++[END_REF] but we decided to decompile Duqu's driver into C code to expose how it operates and the difference between the drivers of Duqu and Stuxnet. And actually we found singular techniques for injection and anti-detection mechanisms.

IDA's decompiler

We used IDA's plugin "Hex-Rays Decompiler" [START_REF]Hex-Rays Decompiler[END_REF]. It generates C pseudocode from a binary being analyzed in IDA and authorizes modifications of the C code from within the plugin's GUI. Unfortunately the code generated by IDA was, in our case, not directly usable: an example of the first lines of a function decompiled by IDA is given on Figure 1. Firstly the code cannot be recompiled because some variable types, function arguments and calling conventions were not recognized by the decompiler. Secondly the generated code is hardly readable, partly because some structures and librairies were not identified. Let us detail how to circumvent these issues.

In order to rebuild a consistent source code we followed an incremental protocol based on the decompiler's output. We began with commenting the whole decompiled code except for the entrypoint of the driver. We fixed compilation errors and identified missing structures. Once the entrypoint was readable and could be compiled, we added some more code that was previously commented, fixed it, and so on.

Structures and types identification

Figure 1 depicts the first lines of the decompiler's output for one of the driver's function. A lot of information is missing, for instance most types are described as int so the kind of processing done is un-signed i n t __cdecl sub_12F36 ( i n t a1 , i n t a2 , i n t a3 ) { i n t v4 ; // eax@3 unsigned __int16 v5 ; // cx@4 i n t v6 ; // ecx@7 v4 = a2 + * (_DWORD * ) ( a2 + 6 0 ) ; i f ( * (_DWORD * ) v4 ^0 xF750F284 != 0xF750B7D4 ) return 1 ; known. We will give more details on this example to illustrate what has been done to fix the code generated by the decompiler. Some of the constants are going to be of great help: for instance we can combine both of them 0xF750F284 XOR 0xF750B7D4 = 0x00004550 = 'PE\0\0', the text searched is 'PE\0\0' which is obfuscated with a XOR operation.

At this point we have strong suspicion that this function is used to parse PE files. A quick dive in Microsoft's Visual C++ documentation reveals the structure PIMAGE_NT_HEADERS which first field is Signature, whose value is 'PE\0\0' for Windows binaries. Thus the variable v4, which is tested against 'PE\0\0', might be of type PIMAGE_NT_HEADERS. So we force this structure and others into IDA's decompiler in place of default int type, IDA then finds fields based on their offsets and updates them in the code. In some cases the structure is specific to the analyzed binary (user defined), it is possible to define them manually in the decompiler plugin.

The beginning of the fixed code is presented on Figure 2, it is readable by a C developer: one sees that the function checks whether a file is a PE binary. The following part of the code will parse it and fill a user defined structure with some information (entrypoint, sections...). Besides the compiled binary of this version is very similar to the original binary. Doing this kind of analysis on the whole driver lead us to build an understandable and consistent version of the driver's source code.

Functional analysis from the source code

Now that the source code has been rebuilt, let us detail how it operates. There are two main phases, the first one consists in setting up the driver: it asks the operating system for notifications when a binary is loaded, and initializes stealth mechanisms. The second one is triggered when it receives notifications: the driver infects the target binary by injecting Duqu's DLL into services.exe, then activates the payload.

Initialisation of the driver during boot

Recall that on Windows, the startup order of drivers is determined by their Group key in the registry. Duqu's nfrd965.sys, belonging to the "network" group, is activated before the hardware abstraction layer (HAL) is loaded into memory.

Once started, nfrd965.sys allocates 512 bytes for storing a array of functions shared by various callback routines. Then it decrypts some internal parameters, revealing the name and path of the registry key used for configuring the injection.

If the decryption succeeded, the driver checks its execution mode. If it is in debug or fail-safe mode, the driver halts, otherwise it creates a device named {624409B3-4CEF-41c0-8B81-7634279A41E5} and defines a list of control commands that the device can process.

That being done, it registers two callback functions within the kernel's event handler. The first is required by the operating system: it is used to create an access point (\Device\Gpd0) and a link (\DosDevices\GpdDev) to the driver, and attaches the device to a memory stack. The second function will be called when the driver is initialized or reinitialized, it is inserted in a waiting list of events.

This second function waits until the Windows kernel is totally loaded: it checks if the DLL hal.dll is loaded, if not, the function is once again inserted into the events waiting list (for at most 200 times). When the system is ready, an access point \Device\Gpd1 is created and linked to a request processing function. At that point librairies are available for Duqu's injection.

Stealth techniques

The driver acts like a rootkit because it avoids directly using suspicious system calls. Indeed those system calls might be monitored by an antivirus. Typically the function ZwAllocateVirtualMemory can be used to allocate memory space into any process, for instance to inject code into any target process. Besides, in order to hook the entrypoint of a system binary, Duqu also needs the function ZwProtectVirtualMemory that is deliberately not exported by the kernel. This function modifies the permissions of a memory block and can be used to make a code section writable or execute code in a data section. Duqu was built to find ZwProtectVirtualMemory's memory address without using imports.

The two functions are implemented in the Windows kernel (in Ntoskrnl.exe or ntkrnlpa.exe, depending on the version). The driver inspects every module (DLLs and EXE files) loaded by the OS during boot until it finds one of the two target kernel files.

Once the file is found, the driver uses the function ParsePE to examine it closely. It searches, in that kernel file, a call to ZwAllocateVirtualMemory (whose address is known from the export table) followed by the opcode push 104h and another (near) call to an unknown function. If this pattern, shown in Figure 3, is found, the target address of this last call is considered to be ZwProtectVirtualMemory. At this point the memory addresses of both functions are known.

Avoiding hooks. It is firstly checked that the two functions are located inside the kernel's memory addresses and not in user space which would indicate an obvious hook to a monitored function. Secondly an integrity mask applying a logical AND is applied on the first 32 bytes of both functions. The mask is the same for the two functions and is shown on Figure 4. If the functions pass both tests, their addresses are considered valid and are kept for a future stealthy use.

Initialization of shared memory

A shared memory space is allocated and used as a link between the driver's callback functions and the kernel. It is to be filled with, amongst others, infection parameters decrypted from the registry and an import table giving access to kernel32.dll and kernel functions. Values filled in gray are those checked.

This import table will be used by both the executable code that Duqu is going to inject and the payload.

The initialization phase ends by setting up a notification triggered each time a module is loaded into memory (through the system call PsSetLoadImageNotifyRoutine).

Code injection

Processing the first notification

Before the injection. The driver is notified each time a module (DLL or EXE file) is loaded into memory. Each time, the driver checks if the Windows version is supported, then it tries to locate the mapped module. To do so it uses the process id given as a parameter by the OS. It reads the file's base address from the PEB (Process Environment Block) structure and compares it to the address passed by the operating system. It checks that the configuration file is decrypted in the shared memory and reads the target file field. As explained by CrySys' document [START_REF] Crysys | Duqu: A Stuxnet-like malware found in the wild[END_REF], the target file in that case is services.exe so from now on we will focus on that process and the injection into it.

Payload injection. Duqu's driver is now going to inject malicious code into services.exe. Thus the payload will be executed by services.exe before services.exe's legitimate code.

Once services.exe is loaded, the driver determines its entrypoint and allocates memory (with ZwAllocateVirtualMemory) in the .data segment. It injects two PE files with altered headers. Then it restores the missing constants ('MZ', 'IMAGE_NT_SIGNATURE', 'IMAGE_PE_i386_MACHINE, and 'IMAGE_PE32_MAGIC') of the first injected code. Finally it proceeds with the addresses relocation and modifies the permissions of services.exe's entrypoint from RX (PAGE_EXECUTE_READ) to RWX (PAGE_EXECUTE_WRITECOPY) using ZwProtectVirtualMemory.

Duqu's nfrd965.sys allocates memory in the services.exe process, its size is 57 bytes plus the size of the decrypted DLL. The payload (the DLL NETP191.PNF) is decrypted and copied there. Next a handler is opened on the kernel driver (nfrd965.sys), saved in a shared structure in order to be gathered by the injected code.

Processing the second notification

The driver is not only notified when the main module (process services.exe) is loaded, but also when DLLs linked to that module are loaded. In particular, when kernel32.dll is loaded, the driver looks for the addresses of 10 functions exported by kernel32.dll that will be used by the payload. Trying to be stealthy, the search consists in comparing the hashed names of 10 functions. This processing ends with saving the first 12 bytes of the entrypoint assembly code of services.exe and their replacement by a jump on the first injected (and restored) code. The first instructions of the entrypoint are changed into mov eax,@adresseInjection followed by call eax.

The process services.exe has been altered and is now ready to launch the payload.

Launching the payload

The operating system finishes the initialization of the services.exe process and proceeds with its execution by passing control to the code at the entrypoint. Actually the system starts the first injected code.

Its first task consists in determining its own absolute memory address (with the instruction sequence callpop) because further processing (read, write, jump) depend on it. During execution the addresses are relocated with respect to the absolute address of the entrypoint.

It then restores the headers of the second injected code so it is a valid PE and fills, within a shared structure, an import table from the 10 functions found in kernel32.dll. Then it creates a handler on ntdll.dll which is stored in a shared structure. It then jumps to the entrypoint of the second injected code.

This additional module adds data from its own PE header (address of the module, number of sections, ad- dress of the export table) to the shared structure. Finally these informations are used to map the PE into memory manually: it allocates memory space, copies the PE header, maps sections, loads DLLs, creates the import table, relocates the addresses and finally determines the entrypoint. Then the function relocates Duqu's main decrypted DLL, NETP191.PNF, as a DLL linked to the PE just mapped and calls its entrypoint. Figure 5 sums up the injections done by Duqu into services.exe and the system memory. The payload contained in the DLL is now in place and executed.

Once it is done it sends a request to the driver through the access point \Device\{624409B3-4CEF-41c0-8B81-7634279A41E5} so it restores the 12 first bytes located at the entrypoint of services.exe. A second request is finally sent to restore the access permission of services.exe's entrypoint.

The injection is now done, control is then passed back to the restored services.exe.

Turning the driver

In the previous paragraph we described how the Duqu's DLL is injected in services.exe. Some of these mechanisms, for instance the notifications once a module is loaded, can be used for defensive purposes.

In a nutshell the modified driver will calculate signatures (checksums) on binaries upon notification that they are loaded into memory. On reception of further notifications, if the checksum has changed, an alert is risen and further actions might be taken. Let's now go into some details of the initialization, memorization and detection phase of the defensive driver. We'll end this paper by a demonstration of the defense granted by the modified driver against an attack by Duqu.

Initialization phase

The initialization phase of our driver has been greatly simplified.

We kept the creation of the access points, removed the search for the ZwProtectVirtualMemory function.

We kept the handling of notifications when modules are loaded and also asked for notifications when the system finishes creating a process (function PsSetCreateProcessNotifyRoutine).

Memorization phase

We saw that the alteration is not done when the first notification is triggered. Thus, if a checksum had been done at that point, the modification of the entrypoint could be detected when the second notification is triggered.

We reused Duqu's checksum function which was originally called for obfuscating function names.

A first notification is received when a process is created. Unfortunately Windows passes only the process id, its parent and whether it was created or destroyed. However we can retrieve the PEB (Process Enviroment Block) structure associated to that process. We used that information to find the memory address of the loaded file.

In order to detect Duqu, we focused on services.exe, we compare the process name to the string "services.exe". If it is the target process, we look for its entrypoint, we calculate its hashed value and store it as an initial signature. The defensive driver is now ready to detect the hook made by Duqu.

Detection phase

When a module is loaded, the operating system passes control to the defensive driver which looks for the entrypoint of the module. If the loaded module is a DLL, the entrypoint is searched in the PE file of the executable file it is linked to. We reused what was done in Duqu and added the verification of the hash.

The hash of the PE file has been determined and is to be compared to the original signature previously stored. If both checksums are different, we infer that The defensive driver stores its id (0x914), its entrypoint (0x01012475) and its hash (0x49af1bf2).

Duqu hooked services.exe between the two notifications. Since the entrypoint has been altered, the process services.exe is flagged as suspicious and submitted to further analysis.

Proof of concept

Aiming to debug and test the original driver and the defensive one, we followed the steps described by Sergei Shevchenko [START_REF] Shevchenko | Actually, my name is Duqu -Stuxnet is my middle name[END_REF] who proposes to rename the Windows calculator calc.exe as services.exe and launch it to watch how the drivers react.

For this example we used two virtual machines using Windows XPSP3 connected by a serial link. The first machine runs Microsoft's WinDBG for kernel debug. The other machine is launched in "kernel debug" mode which allows the debug machine to communicate on a kernel level and debug drivers.

While doing tests we uncovered that Duqu's nfrd965.sys checks if the system is in debug or failsafe mode so we had to patch that out for test purposes, thus allowing debug. We also configured both drivers so they can be launched on demand, it was needed to modify registry keys (the Start parameter has to be set to 3). This configuration provides us with the possibility to choose the launch order of both drivers and services.exe.

We first launched the defensive driver, then Duqu's driver and finally services.exe. In the debugger console, shown on Figure 6, we see when services.exe is launched. The system notifies the defensive driver which outputs information about the loaded module then stores its id, the address of its entrypoint and its initial signature (checksum of the first bytes at the entrypoint).

When the notification for kernel32.dll is triggered to the defensive driver, no modification has been made since Duqu's driver will receive the notification afterwards (due to the launch order of drivers). So the checksum succeeds. However there are further notifications, for instance when the linked DLL shell32.dll is loaded, the defensive driver checks once again the entrypoint's hash and it has been altered. It is shown on Figure 7. Thus the alteration of services.exe is detected and the defensive driver takes further steps to protect the system: it terminates services.exe, ending Duqu's attempt to compromise the machine.

Conclusion

Similarities between Duqu and Stuxnet lead us to look for a detection method of Duqu when the attack is going on. We described by and large the infection technique of Duqu and how its driver operates, stealthy injecting code into services.exe using kernel functions. Thus we rebuilt a source code for Duqu's driver and created a defensive version from this source code. Our modified driver is able to detect the injection made by Duqu and protects the system by terminating the infected process services.exe.

Duqu was considered at its times as one of the most sophisticated malware. And the above shows that, indeed, the malware was built with great care. At the same time, it is known that complex systems may be fragile. Usually, it is on the defender side that we make the observation: complex infrastructures offer a lot of entry points to malware. Here, the argument is opposite: it's the malware which was fragile and we exploited this feature to turn it for our own purposes.

Figure 1 .

 1 Figure 1. First 10 lines of the ParsePE function as decompiled by IDA

Figure 2 .

 2 Figure 2. First 10 lines of the fixed ParsePE function

4 )Figure 3 .

 43 Figure 3. Function calling ZwProtectVirtualMemory.

Figure 4

 4 Figure 4. Integrity mask applied on ZwAllocateVirtualMemory and ZwProtectVirtualMemory.Values filled in gray are those checked.

Figure 5 .

 5 Figure 5. Memory space injected by Duqu into services.exe once the injection is done.

- 5 EntrypointChecksum=0 x 4 9 a f 1 b f 2 Figure 6 .

 526 Figure 6. From WinDbg:The process services.exe is loaded.The defensive driver stores its id (0x914), its entrypoint (0x01012475) and its hash (0x49af1bf2).

*Figure 7 .

 7 Figure 7. Detection of the altered entrypoint (0x01012475) of services.exe.


Christophe Chesneau
email: christophe.chesneau@unicaen.fr

A note on wavelet estimation of the derivatives of a regression function in a random design setting

Keywords: AMS 2000 subject classifications: 62G07, 62G20 Nonparametric regression, Derivatives function estimation, Wavelets, Besov balls, Hard thresholding

We investigate the estimation of the derivatives of a regression function in the nonparametric regression model with random design. New wavelet estimators are developed. Their performances are evaluated via the mean integrated squared error. Fast rates of convergence are obtained for a wide class of unknown functions.

Introduction

We consider the nonparametric regression model with random design described as follows. Let (Y 1 , X 1 ), . . . , (Y n , X n ) be n random variables defined on a probability space (Ω, A, P), where

Y i = f (X i ) + ξ i , i = 1, . . . , n, (1.1)
wavelet estimators for f (m) from (1.1) but defined with a deterministic equidistant design, i.e., X i = i/n. The consideration of a random design complicates significantly the problem and no wavelet estimators exist in this case. This motivates our study.

In a first part, assuming that g is known, we propose two wavelet estimators: the first one is linear nonadaptive and the second one, nonlinear adaptive. Both use the approach of Prakasa [START_REF] Rao | Nonparametric estimation of the derivatives of a density by the method of wavelets[END_REF] initially developed in the context of the density estimation problem. Then we determine their rates of convergence by considering the mean integrated squared error (MISE) and assuming that f (m) belongs to Besov balls. In a second part, we develop a linear wavelet estimator in the case where g is unknown. It is derived from the one introduced by [START_REF] Pensky | On non-equally spaced wavelet regression[END_REF] considering the estimation of f (0) = f from (1.1). We evaluate its rate of convergence again under the MISE over Besov balls. The obtained rates of convergence are similar those attained by wavelet estimators for the derivatives of a density (see, e.g., Prakasa [START_REF] Rao | Nonparametric estimation of the derivatives of a density by the method of wavelets[END_REF], [START_REF] Chaubey | Wavelet based estimation of the derivatives of a density with associated variables[END_REF][START_REF] Chaubey | Wavelet based estimation of the derivatives of a density for a negatively associated process[END_REF]).

The organization of this note is as follows. The next section describes some basics on wavelets and Besov balls. Our estimators and their rates of convergence are presented in Section 3. The proofs are carried out in Section 4.

Preliminaries

This section is devoted to the presentation of the considered wavelet basis and the Besov balls.

Wavelet basis

We set

L 2 ([0, 1]) = h : [0, 1] → R; ||h|| 2 = 1 0 (h(x)) 2 dx 1/2 < ∞ .
We consider the wavelet basis on [0, 1] introduced by [START_REF] Cohen | Wavelets on the interval and fast wavelet transforms[END_REF]. Let φ and ψ be the initial wavelet functions of the Daubechies wavelets family db2N with N ≥ 1 (see, e.g., [START_REF] Daubechies | Ten lectures on wavelets[END_REF]). These functions have the distinction of being compactly supported and belong to the class C a for N > 5a. For any j ≥ 0, we set Λ j = {0, . . . , 2 j -1} and, for k ∈ Λ j ,

φ j,k (x) = 2 j/2 φ(2 j x -k), ψ j,k (x) = 2 j/2 ψ(2 j x -k).
With appropriated treatments at the boundaries, there exists an integer τ such that, for any integer ℓ ≥ τ ,

B = {φ ℓ,k , k ∈ Λ ℓ ; ψ j,k ; j ∈ N -{0, . . . , ℓ -1}, k ∈ Λ j }
imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014 forms an orthonormal basis of L 2 ([0, 1]). For any integer ℓ ≥ τ and h ∈ L 2 ([0, 1]), we have the following wavelet expansion:

h(x) = k∈Λ ℓ c ℓ,k φ ℓ,k (x) + ∞ j=ℓ k∈Λj d j,k ψ j,k (x), x ∈ [0, 1],
where

c j,k = 1 0 h(x)φ j,k (x)dx, d j,k = 1 0 h(x)ψ j,k (x)dx. (2.1)
These quantities are called the wavelet coefficients of h. See, e.g., [START_REF] Cohen | Wavelets on the interval and fast wavelet transforms[END_REF] and [START_REF] Mallat | A wavelet tour of signal processing[END_REF].

Besov balls

We consider the following wavelet sequential definition of the Besov balls. We say that h ∈ B s p,r (M ) with s > 0, p ≥ 1, r ≥ 1 and M > 0 if there exists a constant C > 0 such that c j,k and d j,k (2.1) satisfy

2 τ (1/2-1/p) k∈Λτ |c τ,k | p 1/p +    ∞ j=τ   2 j(s+1/2-1/p)   k∈Λj |d j,k | p   1/p    r    1/r ≤ C, with the usual modifications if p = ∞ or r = ∞.
The interest of Besov balls is to contain various kinds of homogeneous and inhomogeneous functions h. For particular choices of s, p and r, B s p,r (M ) correspond to standard balls of function spaces, as the Hölder and Sobolev balls (see, e.g., [START_REF] Meyer | Wavelets and Operators[END_REF] and [START_REF] Härdle | Wavelet, Approximation and Statistical Applications[END_REF]).

Results

In this section, we set the assumptions on the model, present our wavelet estimators and determine their rates of convergence under the MISE over Besov balls.

Assumptions

We formulate the following assumptions:

(K1) We have f (q) (0) = f (q) (1) = 0 for any q ∈ {0, . . . , m}. (K2) There exists a constant

C 1 > 0 such that sup x∈[0,1] |f (m) (x)| ≤ C 1 .
imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014 (K3) There exists a constant c 2 > 0 such that

c 2 ≤ inf x∈[0,1] g(x). (K4) There exists a constant C 3 > 0 such that sup x∈[0,1] g(x) ≤ C 3 .

Wavelet estimators: when g is known

We consider the wavelet basis B with N > 5m to ensure that φ and ψ belongs to C m .

Linear wavelet estimator. We define the linear wavelet estimator

f (m) 1 by f (m) 1 (x) = k∈Λj 0 ĉ(m) j0,k φ j0,k (x), x ∈ [0, 1], (3.1) where ĉ(m) j,k = (-1) m n n i=1 Y i g(X i ) (φ j,k ) (m) (X i ) (3.2)
and j 0 is an integer chosen a posteriori. The definition of ĉ(m) j,k is motivated by the following unbiased property: using the independence between X 1 and ξ 1 , E(ξ 1 ) = 0, and m integrations by parts with (K1), we obtain

E(ĉ (m) j,k ) = E (-1) m Y 1 g(X 1 ) (φ j,k ) (m) (X 1 ) = E (-1) m f (X 1 ) g(X 1 ) (φ j,k ) (m) (X 1 ) + E(ξ 1 )E (-1) m 1 g(X 1 ) (φ j,k ) (m) (X 1 ) = (-1) m E f (X 1 ) g(X 1 ) (φ j,k ) (m) (X 1 ) = (-1) m 1 0 f (x) g(x) (φ j,k ) (m) (x)g(x)dx = (-1) m 1 0 f (x)(φ j,k ) (m) (x)dx = 1 0 f (m) (x)φ j,k (x)dx = c (m) j,k , (3.3)
which is the wavelet coefficient of f (m) associated to φ j,k . This approach was initially introduced by Prakasa [START_REF] Rao | Nonparametric estimation of the derivatives of a density by the method of wavelets[END_REF] for the estimation of the derivatives of a density. Its adaptation to (1.1) gives a suitable alternative to the wavelet methods developed by [START_REF] Cai | On adaptive wavelet estimation of a derivative and other related linear inverse problems[END_REF] and [START_REF] Petsa | On the estimation of the function and its derivatives in nonparametric regression: a Bayesian estimation approach[END_REF] in the case X i = i/n, specially in the treatment of the random design.

Note that, for the standard case m = 0, this estimator has been considered and studied in [START_REF] Chesneau | Regression with random design: a minimax study[END_REF].

Theorem 3.1 below investigates the rate of convergence attained by f (m) 1 under the MISE assuming that f (m) belongs to Besov balls.

imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014

Theorem 3.1. Suppose that (K1), ( K2) and (K3) are satisfied and that

f (m) ∈ B s p,r (M ) with M > 0, p ≥ 1, r ≥ 1 and s ∈ (max(1/p -1/2, 0), N ). Let f (m)
1 be defined by (3.1) with j 0 such that

2 j0 = [n 1/(2s * +2m+1) ],
(3.4)

s * = s + min(1/2 -1/p, 0
) and [a] denotes the integer part of a.

Then there exists a constant C > 0 such that

E f (m) 1 -f (m) 2 2 ≤ Cn -2s * /(2s * +2m+1) .
The rate of convergence n -2s * /(2s * +2m+1) corresponds to the one obtained in the derivatives density estimation framework. See, e.g., Prakasa [START_REF] Rao | Nonparametric estimation of the derivatives of a density by the method of wavelets[END_REF], [START_REF] Chaubey | Wavelet based estimation of the derivatives of a density with associated variables[END_REF][START_REF] Chaubey | Wavelet based estimation of the derivatives of a density for a negatively associated process[END_REF]. For m = 0, Theorem 3.1 becomes (Chesneau, 2007, Theorem 3.1, p = 2).

Hard thresholding wavelet estimator. We define the hard thresholding wavelet estimator

f (m) 2 by f (m) 2 (x) = k∈Λτ ĉ(m) τ,k φ τ,k (x) + j1 j=τ k∈Λj d(m) j,k 1 | d(m) j,k |≥κλj ψ j,k (x), (3.5) x ∈ [0, 1], where ĉ(m) j,k is defined by (3.2), d(m) j,k = (-1) m n n i=1 Y i g(X i ) (ψ j,k ) (m) (X i )1 Y i g(X i ) (ψ j,k ) (m) (Xi) ≤ςj , (3.6)
1 is the indicator function, κ > 0 is a large enough constant, j 1 is the integer satisfying

2 j1 = n 1/(2m+1) , ς j = θ ψ 2 mj n ln n , λ j = θ ψ 2 mj ln n n and θ ψ = (2/c 2 )(C 2 1 + E(ξ 2 1 ))||ψ (m) || 2 2 . The construction of f (m)
2 is an adaptation of the hard thresholding wavelet estimator introduced by [START_REF] Delyon | On minimax wavelet estimators[END_REF] to the estimation of f (m) from (1.1). It used the modern version developed by [START_REF] Chaubey | Adaptive wavelet estimation of a density from mixtures under multiplicative censoring[END_REF]. The advantage of

f (m) 2 over f (m) 1 (3.1) is that f (m) 2
is adaptive ; thanks to the thresholding in (3.6), its performance does not depend on the knowledge of the smoothness of f (m) . The second thresholding in (3.6) enables us to relax some assumptions on the model, and, in particular, to only suppose E(ξ 2 1 ) < ∞ on ξ 1 (its density can be unknown). Basics and important results on hard thresholding wavelet estimators can be found in, e.g., Donoho andJohnstone (1994, 1995), Donoho et al. (1995[START_REF] Donoho | Density estimation by wavelet thresholding[END_REF] and [START_REF] Delyon | On minimax wavelet estimators[END_REF].

Theorem 3.2 below determines the rate of convergence attained by f (m) 2 under the MISE assuming that f (m) belongs to Besov balls.

imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014 Theorem 3.2. Suppose that (K1), (K2) and (K3) are satisfied and that

f (m) ∈ B s p,r (M ) with M > 0, r ≥ 1, {p ≥ 2 and s ∈ (0, N )} or {p ∈ [1, 2) and s ∈ ((2m + 1)/p, N )}. Let f (m)
2 be defined by (3.5). Then there exists a constant C > 0 such that

E f (m) 2 -f (m) 2 2 ≤ C ln n n 2s/(2s+2m+1)
.

The proof is based on a general result proved by (Chaubey et al., 2013, Theorem 6.1). Let us observe that, for the case p ≥ 2, (ln n/n) 2s/(2s+2m+1) is equal to the rate of convergence attained by f (m) 1 up to a logarithmic factor (see Theorem 3.1). However, for the case p ∈ [1, 2), it is significantly better in terms of power.

Wavelet estimators: when g is unknown

In the case where g is unknown, we propose the linear wavelet estimator f (m) 3 defined by

f (m) 3 (x) = k∈Λj 2 c(m) j2,k φ j2,k (x), x ∈ [0, 1], (3.7) where c(m) j,k = (-1) m a n an i=1 Y i ĝ(X i ) 1 {|ĝ(Xi)|≥c2/2} (φ j,k ) (m) (X i ), (3.8)
a n = [n/2], j 2 is an integer chosen a posteriori, c 2 refers to (K3) and ĝ is an estimator of g constructed from the random variables U n = (X an+1 , . . . , X n ).

For instance, we can consider the linear wavelet estimator ĝ by

ĝ(x) = k∈Λj 3 cj3,k φ j3,k (x), x ∈ [0, 1], (3.9) where cj,k = 1 n -a n n-an i=1 φ j,k (X an+i ),
and j 3 is an integer chosen a posteriori.

The estimator f (m) 3 is close to the "NES linear wavelet estimator" proposed by [START_REF] Pensky | On non-equally spaced wavelet regression[END_REF] for m = 0. However, there are notable differences in the thresholding in (3.8), the partitioning of the variables and the definition of ĝ, making the study of its performance under the MISE more simpler (see the proofs of Theorem 3.3 below).

Theorem 3.3 below determines an upper bound of the MISE of f (m)

Theorem 3.3. Suppose that (K1), (K2) and (K3) are satisfied and that

f (m) ∈ B s1 p1,r1 (M 1 ) with M 1 > 0, p 1 ≥ 1, r 1 ≥ 1 and s 1 ∈ (max(1/p 1 - 1/2, 0), N ). Let f (m)
3 be defined by (3.7). Then there exists a constant C > 0 such that

E f (m) 3 -f (m) 2 2 ≤ C 2 (2m+1)j2 max E ĝ -g 2 2 , 1 n + 2 -2j2s * , with s * = s 1 + min(1/2 -1/p 1 , 0). In addition, suppose that (K4) is satisfied, g ∈ B s2 p2,r2 (M 2 ) with M 2 > 0, p 2 ≥ 1, r 2 ≥ 1 and s 2 ∈ (max(1/p 2 -1/2, 0), N ), consider f (m) 3
with the estimator ĝ defined by (3.9) with j 3 such that

2 j3 = [(n -a n ) 1/(2so+1) ],
(3.10)

s o = s 2 + min(1/2 -1/p 2 , 0) and j 2 such that 2 j2 = [n 2so/((2so+1)(2s * +2m+1)) ]. (3.11)
Then there exists a constant C > 0 such that

E f (m) 3 -f (m) 2 2 ≤ Cn -4s * so/((2so+1)(2s * +2m+1)) .
The first point of Theorem 3.3 is proved for any estimator ĝ of g depending on U n . Taking ĝ = g, it corresponds to the upper bound of the MISE for f (m) 1 established in the proof of Theorem 3.1. Note that the rate of convergence described in the second point is slower to the one attained by f (m) 1

(see Theorem 3.1). The fact that the smoothness of g influences the performance of ĝ and, a fortiori, f (m) 3

, seems natural. This phenomenon also appears in [START_REF] Pensky | On non-equally spaced wavelet regression[END_REF], Theorem 2.1) for m = 0.

Remark 3.1. If c 2 exists but is unknown, we can defined f (m) 3 as (3.7) with 1/ ln n instead of c 2 in the threshold of (3.8). The impact of this modification is a logarithmic term in Theorem 3.3, i.e.,

E f (m) 3 -f (m) 2 2 ≤ C 2 (2m+1)j2 max (ln n)E ĝ -g 2 2 , 1 n + 2 -2j2s * .
Moreover, choosing j 2 such that

2 j2 = [n 2so/((2so+1)(2s * +2m+1)) (ln n) -1/(2s * +2m+1) ],
there exists a constant C > 0 such that

E f (m) 3 -f (m) 2 2 ≤ Cn -4s * so/((2so+1)(2s * +2m+1)) (ln n) 2s * /(2s * +2m+1) .
Remark 3.2. Note that the assumption (K4) has been only used in the second point of Theorem 3.3.

imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014

Conclusion and perspective. We explore the estimation of f (m) from (1.1). Distinguishing the cases where g is known or not, we propose wavelet methods and prove that they attain fast rates of convergence under the MISE assuming that f (m) ∈ B s p,r (M ). A perspective of this work will be to develop an adaptive wavelet estimator, as the hard thresholding one, for the estimation of f (m) in the case where g is unknown. The extension of f (m) 3 in this sense is not trivial and new theoretical problems raised. Another perspective is the consideration of dependent (Y 1 , X 1 ), . . . , (Y n , X n ). These two aspects need further investigations that we leave for a future work.

Proofs

In this section, C denotes any constant that does not depend on j, k and n. Its value may change from one term to another and may depend on φ or ψ.

Proof of Theorem 3.1. First of all, we expand the function f (m) on B at the level j 0 given by (3.4) : Using (φ j0,k ) (m) (x) = 2 (j0/2)(2m+1) φ (m) (2 j0 x -k), the change of variables y = 2 j0 x -k and the fact that φ is compactly supported, we obtain

f (m) (x) = k∈Λj 0 c (m) j0,k φ j0,k (x) + ∞ j=j0 k∈Λj d (m) j,k ψ j,k (x), where c (m) j0,k = 1 0 f (m) (x)φ j0,k (x)dx and d (m) j,k = 1 0 f (m) (x)ψ j,k (x)dx. Since B forms an orthonormal basis of L 2 ([0, 1]), we get E f (m) 1 -f (m) 2 2 = k∈Λj 0 E ĉ(m) j0,k -c (m) j0,k 2 + ∞ j=j0 k∈Λj (d (
E ĉ(m) j0,k -c (m) j0,k 2 = V ĉ(m) j0,k = 1 n V Y 1 g(X 1 ) (φ j0,k ) (m) (X 1 ) ≤ 1 n E Y 1 g(X 1 ) (φ j0,k ) (m) (X 1 ) 2 ≤ 1 n 2E (f (X 1 )) 2 + ξ 2 1 (g(X 1 )) 2 ((φ j0,k ) (m) (X 1 )) 2 ≤ 1 n 2 c 2 C 2 1 + E(ξ 2 1 ) E 1 g(X 1 ) ((φ j0,k ) (m) (X 1 )) 2 . ( 4
E 1 g(X 1 ) ((φ j0,k ) (m) (X 1 )) 2 = 1 0 1 g(x) ((φ j0,k ) (m) (x)) 2 g(x)dx = 2 2mj0 1 0 2 j0 (φ (m) (2 j0 x -k)) 2 dx ≤ 2 2mj0 ||φ (m) || 2 2 . (4.3) Therefore E ĉ(m) j0,k -c (m) j0,k 2 ≤ C2 2mj0 1 n
and, for j 0 satisfying (3.4), it holds

k∈Λj 0 E ĉ(m) j0,k -c (m) j0,k 2 ≤ C2 (2m+1)j0 1 n ≤ Cn -2s * /(2s * +2m+1) . (4.4)
On the other hand, we have

f (m) ∈ B s p,r (M ) ⊆ B s * 2,∞ (M ) [see Härdle et al. (1998), Corollary 9.2], which implies ∞ j=j0 k∈Λj (d (m) j,k ) 2 ≤ C2 -2j0s * ≤ Cn -2s * /(2s * +2m+1) . (4.5)
It follows from (4.1), (4.4) and (4.5) that

E f (m) 1 -f (m) 2 2 ≤ Cn -2s * /(2s * +2m+1) .
Theorem 3.1 is proved.

Proof of Theorem 3.2. Observe that, for γ ∈ {φ, ψ}, any integer j ≥ τ and any k ∈ Λ j ,

• using arguments similar to (3.3), we obtain

E (-1) m n n i=1 Y i g(X i ) (γ j,k ) (m) (X i ) = 1 0 f (m) (x)γ j,k (x)dx.
• using arguments similar to (4.2) and (4.3), we have

n i=1 E (-1) m Y i g(X i ) (γ j,k ) (m) (X i ) 2 = nE Y 1 g(X 1 ) (γ j,k ) (m) (X 1 ) 2 ≤ C 2 * n2 2mj , with C 2 * = (2/c 2 )(C 2 1 + E(ξ 2 1 ))||γ (m) || 2 2 .
imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014

Applying (Chaubey et al., 2013, Theorem 6.1) (presented in Appendix) with

µ n = υ n = n, δ = m, θ γ = C * , W i = (Y i , X i ), q i (γ, (y, x)) = (-1) m y g(x) γ (m) (x)
and f (m) ∈ B s p,r (M ) with M > 0, r ≥ 1, either {p ≥ 2 and s ∈ (0, N )} or {p ∈ [1, 2) and s ∈ (1/p, N )}, we prove the existence of a constant C > 0 such that

E f (m) 2 -f (m) 2 2 ≤ C ln n n 2s/(2s+2m+1)
.

Theorem 3.2 proved.

Proof of Theorem 3.3. As in the proof of Theorem 3.1, we first expand the function f (m) on B at the level j 2 given by (3.11) :

f (m) (x) = k∈Λj 2 c (m) j2,k φ j2,k (x) + ∞ j=j2 k∈Λj d (m) j,k ψ j,k (x).
Since B forms an orthonormal basis of L 2 ([0, 1]), we get

E f (m) 3 -f (m) 2 2 = k∈Λj 2 E c(m) j2,k -c (m) j2,k 2 + ∞ j=j2 k∈Λj (d (m) j,k ) 2 . (4.6) Using f (m) ∈ B s p,r (M ) ⊆ B s * 2,∞ (
(a + b) 2 ≤ 2(a 2 + b 2 ), (a, b) ∈ R 2 , yields k∈Λj 2 E c(m) j2,k -c (m) j2,k 2 ≤ 2(T 1 + T 2 ), (4.8)
where

T 1 = k∈Λj 2 E c(m) j2,k - ĉ(m) j2,k 2 , T 2 = k∈Λj 2 E ĉ(m) j2,k -c (m) j2,k 2 .
Proceeding as in (4.4), we get

T 2 ≤ C2 (2m+1)j2 1 a n ≤ C2 (2m+1)j2 1 n . (4.9)
Let us now investigate the upper bound for T 1 .

imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014

The triangular inequality gives

c(m) j2,k - ĉ(m) j2,k = (-1) m a n an i=1 Y i (φ j,k ) (m) (X i ) 1 ĝ(X i ) 1 {|ĝ(Xi)|≥c2/2} - 1 g(X i ) ≤ 1 a n an i=1 |Y i ||(φ j,k ) (m) (X i )| 1 ĝ(X i ) 1 {|ĝ(Xi)|≥c2/2} - 1 g(X i )
.

Moreover, we have

1 ĝ(X i ) 1 {|ĝ(Xi)|≥c2/2} - 1 g(X i ) = 1 g(X i ) g(X i ) -ĝ(X i ) ĝ(X i ) 1 {|ĝ(Xi)|≥c2/2} -1 {|ĝ(Xi)|<c2/2} .
It follows from the triangular inequality, the indicator function, (K3), {|ĝ

(X i )| < c 2 /2} ⊆ {|ĝ(X i ) -g(X i )| > c 2 /2} and the Markov inequality that 1 ĝ(X i ) 1 {|ĝ(Xi)|≥c2/2} - 1 g(X i ) ≤ 1 g(X i ) 2 c 2 |ĝ(X i ) -g(X i )| + 1 {|ĝ(Xi)-g(Xi)|>c2/2} ≤ 4 c 2 |ĝ(X i ) -g(X i )| g(X i ) . Hence c(m) j2,k - ĉ(m) j2,k ≤ CA j2,k,n ,
where

A j,k,n = 1 a n an i=1 |Y i ||(φ j,k ) (m) (X i )| |ĝ(X i ) -g(X i )| g(X i
) .

Let us now consider U n = (X an+1 , . . . , X n ). For any random variable D, we have the equality:

E(D 2 ) = E(E(D 2 |U n )) = E(V(D|U n )) + E((E(D|U n )) 2 ),
where E(D|U n ) denotes the expectation of D conditionally to U n and V(D|U n ), the variance of D conditionally to U n . Therefore

T 1 ≤ C k∈Λj 2 E(A 2 j2,k,n ) = C(W j2,n + Z j2,n ), (4.10)
where

W j2,n = k∈Λj 2 E (V (A j2,k,n |U n )) , Z j2,n = k∈Λj 2 E (E (A j2,k,n |U n )) 2 .
imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014

Let us now observe that, owing to the independence of (Y 1 , X 1 ), . . . , (Y n , X n ), the random variables

|Y 1 ||(φ j,k ) (m) (X 1 )| |ĝ(X 1 ) -g(X 1 )| /g(X 1 ), . . . , |Y an ||(φ j,k ) (m) (X an )| |ĝ(X an ) -g(X an )| /g(X an
) conditionally to U n are independent. This remark combines with the inequalities: V(D|U n ) ≤ E(D 2 |U n ) for any random variable D and (a + b) 2 ≤ 2(a 2 + b 2 ), (a, b) ∈ R 2 , the independence between X 1 and ξ 1 , (K2) and (K3), yields

V (A j2,k,n |U n ) = 1 a n V |Y 1 ||(φ j2,k ) (m) (X 1 )| |ĝ(X 1 ) -g(X 1 )| g(X 1 ) U n ≤ 1 a n E Y 2 1 (φ j2,k ) (m) (X 1 ) 2 ĝ(X 1 ) -g(X 1 ) g(X 1 ) 2 U n ≤ 1 a n 2 c 2 (C 2 1 + E(ξ 2 1 ))E (φ j2,k ) (m) (X 1 ) 2 (ĝ(X 1 ) -g(X 1 )) 2 g(X 1 ) U n = 2 c 2 (C 2 1 + E(ξ 2 1 )) 1 a n 1 0 (φ j2,k ) (m) (x) 2 (ĝ(x) -g(x)) 2 g(x) g(x)dx ≤ C 1 n 1 0 (φ j2,k ) (m) (x) 2 (ĝ(x) -g(x)) 2 dx.
Thanks to the support compact of φ (m) , we have k∈Λj 2 φ (m) (2 j2 x -k) 2 ≤ C.

Therefore, using (φ j2,k ) (m) (x) = 2 (j2/2)(2m+1) φ (m) (2 j2 x -k),

W j2,n ≤ C 1 n E   1 0 (ĝ(x) -g(x)) 2 k∈Λj 2 (φ j2,k ) (m) (x) 2 dx   ≤ C2 (2m+1)j2 1 n E ĝ -g 2 2 .
(4.11)

On the other hand, by the Hölder inequality for conditional expectations, arguments similar to (4.2) and (4.3), we get

E (A j2,k,n |U n ) = E |Y 1 ||(φ j2,k ) (m) (X 1 )| |ĝ(X 1 ) -g(X 1 )| g(X 1 ) U n ≤ E Y 2 1 g(X 1 ) (φ j2,k ) (m) (X 1 ) 2 U n 1/2 E (ĝ(X 1 ) -g(X 1 )) 2 g(X 1 ) U n 1/2 = E Y 2 1 g(X 1 ) (φ j2,k ) (m) (X 1 ) 2 1/2 1 0 (ĝ(x) -g(x)) 2 g(x) g(x)dx 1/2 ≤ C2 mj2 ĝ -g 2 .
Hence Z j2,n ≤ C2 (2m+1)j2 E ĝ -g 2 2 .

(4.12)

E f (m) 3 -f (m) 2 2 ≤ C 2 (2m+1)j2 max E ĝ -g 2 2 ,
1 n + 2 -2j2s * . (4.15)

A slight adaptation of (Donoho et al., 1996, Proposition 1) gives the following result. Suppose that (K4) is satisfied and g ∈ B s2 p2,r2 (M 2 ) with M 2 > 0, p 2 ≥ 1, r 2 ≥ 1 and s 2 ∈ (max(1/p 2 -1/2, 0), N ). Let ĝ be defined by (3.9) with j 3 as (3.10). Then there exists a constant C > 0 such that E ĝ -g 2 2 ≤ C(n -a n ) -2so/(2so+1) ≤ Cn -2so/(2so+1) .

Therefore, chosing j 2 as (3.11) and using (4.15), we have

E f (m) 3 -f (m) 2 2
≤ C 2 (2m+1)j2 n -2so/(2so+1) + 2 -2j2s * ≤ Cn -4s * so/((2so+1)(2s * +2m+1)) .

Theorem 3.3 is proved.

  (see (3.3)), (Y 1 , X 1 ), . . . , (Y n , X n ) are i.i.d., the inequalities : V(D) ≤ E(D 2 ) for any random variable D and (a + b) 2 ≤ 2(a 2 + b 2 ), (a, b) ∈ R 2 , (K2) and (K3), we have

  M ) [see[START_REF] Härdle | Wavelet, Approximation and Statistical Applications[END_REF], Corollary 9.2be (3.2) with n = a n and j = j 2 (3.11). The elementary inequality:

  imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014It follows from (4.10), (4.11) and (4.12) thatT 1 ≤ C2 (2m+1)j2 E ĝ -g 2 2 .

								(4.13)
	Putting (4.8), (4.9) and (4.13) together, we get
	k∈Λj 2	E	c(m) j2,k -c	(m) j2,k	2	≤ C2 (2m+1)j2 max E ĝ -g 2 2 ,	1 n	. (4.14)
	Combining (4.6), (4.7) and (4.14), we obtain

, then exhibits its rate of convergence when f (m) belongs to Besov balls.imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014

imsart-generic ver. 2009/12/15 file: deriv-reg.tex date: January 8, 2014

Appendix

Let us now present in details (Chaubey et al., 2013, Theorem 6.1) used in the proof of Theorem 3.2.

We consider a general form of the hard thresholding wavelet estimator denoted by fH for estimating an unknown function f ∈ L 2 ([0, 1]) from n independent random variables W 1 , . . . , W n :

where

κ ≥ 2 + 8/3 + 2 4 + 16/9 and j 1 is the integer satisfying

Here, we suppose that there exist

• n functions q 1 , . . . , q n with q i : L

(A2) there exist two constants, θ γ > 0 and δ ≥ 0, such that, for any integer j ≥ τ and any k ∈ Λ j ,

Let fH be (4.16) under ( A1) and (A2). Suppose that f ∈ B s p,r (M ) with r ≥ 1, {p ≥ 2 and s ∈ (0, N )} or {p ∈ [1, 2) and s ∈ ((2δ + 1)/p, N )}. Then there exists a constant C > 0 such that

.