This work presents a debugging methodology for MPSoC based on deterministic record-replay. We propose a general model of MPSoC and define a debugging cycle targeting errors by applying temporal and spatial selection criteria. The idea behind spatial and temporal selection is to consider not the entire execution of the whole application but replay a part of the application during a specific execution interval. The proposed mechanisms are connected to GDB and allow for a visual representation of the considered part of the trace. The approach is validated on two execution platforms and two multimedia applications.

I. INTRODUCTION

Recent years have witnessed a tremendous development of embedded systems. They find their place in numerous domains in our everyday life like transports, domotics and telecommunications. This omnipresence has called for new design methods targeting more complex applications, more efficiency and yet a shorter time to market.

Multi-Processor Systems on Chip (MPSoC) architectures have been proposed to meet these new requirements. They follow the "multi-core trend" and propose an increasing number of components allowing for bigger computational power at a lower energetic cost. The hardware design includes general purpose processors, specialized accelerators, shared, as well as distributed memory, numerous peripherals and Network-on-Chip (NoC) interconnections.

The increasing hardware complexity of MPSoC brings new challenges to the process of software development and validation. Indeed, parallel computations and concurrent data accesses makes software execution non deterministic. As a consequence, software validation is faced with the problem of detecting and rooting the causes of non deterministic errors which are hard to observe and reproduce. The problem is even more emphasized by the important number of components (threads, tasks, processes) taking part in an execution and their possible interactions.

In this paper we describe our approach to debugging non deterministic embedded software. We propose a record-replay mechanism in which non deterministic errors are first captured in execution traces and then tracked through debugging a deterministic replay of the recorded traces. The main contribution of this work is a debugging methodology reducing the error search space by applying spatial and temporal selection criteria. We describe our implementation, ReDSoC, and its trace collection, trace visualization, deterministic replay and partial replay support. ReDSoC has been validated on two different platforms with two multimedia applications.

The rest of the paper is organized as follows. After presenting the general methodology for debugging based on deterministic partial record-replay (Section II), we describe the general principles of our ReDSoC system and its implementation (Sections III and IV). We illustrate its application in the cases of a Tetris and a Video Mosaic application and discuss performance issues (Section V). Related work and future perspectives conclude the paper (Sections VI and VII).

II. RECORD-REPLAY DEBUGGING METHODOLOGY

We propose the following methodology (Figure 1).

Step 1: Recording a Reference Execu5on Trace

Step 2: Trace Analysis

Step 4: Search Space Reduc5on

Step 5: Determinis5c Replay and Recording Par5al Traces

Step 6: Determinis5c Par5al Replay and Debugging

Step 3: Error Detec5on

Step 7: Error Iden5fica5on

III. REDSOC OVERVIEW

To define the debugging selection criteria(Section III-B), we use an abstract MPSoC architecture model (Section III-A). We have studied existing algorithms and based our solution on the ones with minimal intrusion in terms of tracing overhead (Section III-C).

A. MPSoC Model

Our work is based on the generic hardware model showed in Figure 2.

MPSoC components include processors, memory blocs, peripherals and a communication network. Processors are computational units including general purpose processors, cores or accelerators. They are organized in a two-level hierarchy. Homogeneous processors form groups we call nodes. Thus there may be a node with audio processing units and another specialized in video decoding.

In a node, processors have access to and communicate through a shared memory bloc. Among nodes, memory is distributed and a processor from one node cannot access the memory of another node without passing through inter-node network connections.

Peripherals are the devices ensuring data exchange between the MPSoC and the external environment. Peripherals may include sensors, keyboards, screens, microphones, etc. The data they capture is communicated to the processors via the memory or the network.

The network connections organize components in a hierarchical way.

As for MPSoC software, our assumptions are the following. The software execution is composed of a set of execution flows which is statically partitioned and scheduled on the MPSoC nodes. The execution flows scheduled on the same node communicate using the shared memory bloc and via synchronization. The execution flows scheduled on different nodes communicate using message-passing through the network. Data from peripherals is acquired either by polling, or using interruptions.

B. Partial Replay

To partially replay MPSoC software execution, we apply two selection criteria concerning the software architecture (space) and the execution duration (time). With space reduction, the idea is to isolate a set of nodes on which the debugging can focus. The replay phase thus concerns only the execution flows running on the identified set of nodes. We call the set of nodes to be debugged, the suspected nodes. The non suspected nodes are called the correct nodes.

To isolate suspected nodes from the correct nodes, the tracing phase needs to differentiate the nodes and consider their message exchanges. Indeed, messages exchanged between correct nodes are not to be recorded as these nodes would not participate in the replay. Messages exchanged between suspected nodes do not need to be recorded either, as they will be executed during replay. In the case of a message sent from a suspected node to a correct one, as the receive operation has no relevance to the replay, the replay may skip the send operation. In the case of a message sent by a correct node to a suspected one, the order and the content of the message need to be traced. During replay, the trace is used to decide whether to execute a message exchange operation and also to provide message values coming from the external/correct nodes.

The reduction of the search space concerning time is based on the time sequence of events recorded in the trace. The developer needs to delimit the interval to consider during debugging. This is done by choosing the interval limits which are two traced events. The choice is typically facilitated by a visualization tools which represents the trace. During replay, events are compared to the chosen interval beginning. When this event is reached, a debugger is launched and a standard debugging process may start. When the interval end is reached, the debugging phase terminates.

C. Record-Replay Algorithms

We focus on replaying shared data accesses, network communications and I/O operations.

Given that recording all accesses to shared data implies a prohibitive execution overhead [START_REF] Ronsse | Execution Replay for TreadMarks[END_REF], our record-replay mechanisms focuses on accesses to synchronization structures. Nonsynchronized shared data accesses are considered to be errors, to be detected and corrected. We have chosen the algorithm proposed by Levrouw et al. in [START_REF] Levrouw | A New Trace and Replay System for Shared Memory Programs based on Lamport Clocks[END_REF]. The algorithm uses Lamport clocks to identify accesses to different synchronization structures by different execution flows.

Two network communication situations may be non deterministic. First, when multiple sources send messages to a single destination. The reception order may depend on numerous factors like network protocols, connection speed, routing, system load, etc. The second situation concerns non blocking reception operations. In this case, the reception operation relies on a verification of the data availability (probe) which is itself non deterministic.

To trace and deterministically replay network communications, we have used the solution proposed in [START_REF] Clemencon | An Implementation of Race Detection and Deterministic Replay with MPI[END_REF], [START_REF] Netzer | Optimal Tracing and Replay for Debugging Message-Passing Parallel Programs[END_REF]. For blocking network communications, the detection of race reception primitives is based on vector clocks. For non blocking reception operations, there is a need to record the number of executed probes, as well as their outcome (message available or not). This solution has minimal intrusion as it traces only race reception operations.

Output operations have no effect on replay techniques. Input operations, however, are important, as they influence the execution path of MPSoC software. Input operations are based either on interrupts, or on busy waiting (polling). Interrupts, however, are a challenge to embedded record-replay [START_REF] Gracioli | Tracing and Recording Interrupts in Embedded Software[END_REF].

We have decided to limit the intrusion of our mechanism by not recording interrupts and only consider polling requests. We suppose that the content of the input data is recorded by specific devices. We only record the input size in the reference execution trace (Step 1). During replay, the trace is read to decide that there is an input operation which is in turn acquired by executing a polling request to the specific recording device.

IV. REDSOC IMPLEMENTATION

The architecture of our prototype is given on Figure 4. We consider a standard configuration in which part of the debugging operations are deported on a host platform connected to the target MPSoC platform. This is necessary as in many cases MPSoCs have limited resources and do not provide keyboard and screen peripherals.

ReDSoC is deployed both on the host machine and the target MPSoC machine. It is composed of four tools, namely a trace visualization tool, a partial replay tool, a trace collection tool and a deterministic replay tool. The trace collection tool, as well as the temporal selection management of the partial replay tool are deployed on the host machine. The other tools are deployed on the MPSoC, each MPSoC node having its own ReDSoC instance. The deployment on a MPSoC node is guided using a configuration file, provided by the developer. The file indicates the node number, the debugging phase to consider (Steps 1, 5 or 6 on Figure 1), as well as the identifiers of the suspected nodes.

The host machine is supposed to run a Linux-based system and have GDB for debugging. The MPSoC runs a MPSoC kernel characterized by a MPSoC API. The MPSoC API is inspired by the the POSIX standard and includes basic functions for execution flow management, synchronization, network communications and I/O.

Our trace collection tool is deployed on each node of the MPSoC platform. As its purpose is to intercept the calls to the defined MPSoC API, it provides a simple interface including a trace function used for generating trace entries.

The tool for deterministic replay implements the algorithms presented in Section III using as basis the MPSoC API. Shared data accesses are managed through tracking the synchronization operations of the API. Network communications are targeted using our message-based communication. Finally, I/O are addresses by the MPSoC file-oriented I/O operations.

To apply the space reduction criterion based on isolating suspected nodes, our partial replay tool needs to monitor and record all communications between normal and suspected nodes. During replay, each communication operation is intercepted to decide whether a normal node takes part in it or not. If yes, the operation is replayed by directly reading the needed values from the recorded trace. If the communication is between suspected nodes, the operation is normally executed.

To apply the time reduction criterion, we have implemented an extension for GDB and introduced a new type of breakpoint. We use replay breakpoints corresponding to the limits of the time interval that has been selected for debugging. Each replay breakpoint corresponds to an event recorded in the trace and is identified by a triple containing a node identifier, a task identifier and a timestamp.

During replay, each call to the MPSoC API is intercepted and compared to to the limits of the selected time interval. If it does not correspond to any of them, the execution is pursued. If the call corresponds to the start of the time interval, the execution is suspended and the debugging starts. When the end of the time interval is reached, the debugging stops and the developer may choose a new time interval. If it is after the previous time interval, the execution continues. If not, it is launched from the beginning.

We have adapted the KPTrace Viewer of STMicroelectronics [START_REF]KPTrace[END_REF] to visualize our recorded traces. The viewer allows for representation of an event, characterized by a time, a timestamp, a process identifier and a number of arguments. We have provided for a tool formatting our traces according to the Pajé [START_REF] De Kergommeaux | Pajé, an interactive visualization tool for tuning multi-threaded parallel applications[END_REF] format and adapted the KPTrace viewer to take into account its visualization.

An example of visualization is shown on Figure 5. The x dimension gives the time progression. The y dimension represent containers, in this case tasks. The links, represented using arrows, show three successive accesses of the tasks T 0, T 2 and T 1 to a shared synchronization structure. The flags show peripheral operations, their color being specific for each peripheral device. We have validated our approach in two settings: the debugging of a real-time game application on an MPSoC platform (Section V-A) and the debugging of a video-decoding application on a NUMA platform (Section V-C).

A. Debugging a Tetris Application on an MPSoC Platform

For this use case, we have used a Stagecoach expansion board having two OveroFE COM nodes (computer-on-module) 1 . Each node has an ARM Cortex-A8 600MHz processor with 256MB of DDR RAM, 256MB of NAND flash memory and a microSD port. The two nodes occupy the first and the third slot of the board. They are connected through a 100Mb/s Ethernet link and have distinct IP addresses. The RJ45 slot of the board is used to connect to an external network card which gives IP access to both nodes. We have implemented our MPSoC API using the POSIX and the libc interfaces. We have installed the platform from scratch by creating a bootable microSD with the needed Linux distribution. The system image includes the 2.6 Linux kernel, libc6, a file system and the ssh service. To deploy the platform, we have used the cross-compiler provided in the Sourcery Codebench2 to create a x86 executable. The executable contains the MPSoC application, the ReDSoC tools, as well as a GDB server.

The debugged MPSoC application is the Tetris game for two players (cf. Figure 7). The application's size is about 0,7MB and contains about 15000 lines of code. It is executed by two tasks run respectively on the two MPSoC nodes. Both players see both Tetris boards. When a player succeeds in making disappear multiple lines, the other player's game becomes harder. The player whose board fills first, loses the game.

The Tetris pieces movements are controlled through the keyboard and also using the clock frequency. The keyboard is scanned for player commands, while the clock frequency is used to advance the pieces downwards.

In our use case, we needed to debug the application as, from time to time, one of the Tetris instances crashed and as a consequence the other player won. Following our debug cycle, we re-executed several times the Tetris application to obtain a reference trace containing the error (cf. Figure 8). As, in our case, the node to fail is node 1, we suspect this node and choose it as a target for the partial replay. To select the time interval for debugging, we focus and zoom the end of its trace (cf. Figure 9). We select the small end time interval containing three operations reading the system clock, four keyboard inputs and one message reception. As each event can be examined, we can see that the first event is a GetTimerOp operation, executed by task T 0 at time 19 ′ 244 ′ 641µs. The last event is a NetRecvOp executed by T 0 at time 19 ′ 244 ′ 728µs. These two events are defined as the two replay breakpoints for the debugging session. ReDSoC needs to first deterministically replay the whole application to gather additional traces about the communications of node 1 with node 2. Once these traces are generated, ReDSoC may start the deterministic replay of node 1 and debug it during the selected time interval. Indeed, when the replay reaches the first replay breakpoint, ReDSoC starts a standard debugging session (cf. Figure 10).

The figure contains a screen capture of the debugging session when the first replay breakpoint is reached. The first line's information states clearly the number of the entry in the trace (202459), the type of the entry (IO), the node identifier (Node1) and the task identifier (Task0).

The bt GDB command given on the fourth line gives the function call stack. We observe the interaction between the GDB server and our GDB extension implemented in the rdb_notify_event function. The additional parameter information for rdb_notify_syscall confirms that the replay considers an IO operation of the task with tid=0 on node node=1. Up the call stack, we see the replay function When the debugging session reaches the last message reception operation, it is possible to investigate the received value. It appears that it is not correct and contains zero. This value is used in a division operation and the division by zero makes the node 1 to crash. To understand why the value is incorrect, we choose to suspect the other node, node 0. When we focus on the end of its trace, we observe a non regular behavior. Partially replaying node 0 and debugging it during a time interval at the end of its execution, makes us discover that there are many keyboard input operations resulting form a continuous pressing of a keyboard key. The input data being saved in a memory buffer, an error in the buffer management makes it overflow and results in sending an incorrect value.

B. Debugging a Video Decoding Application on a NUMA Platform

To validate the scalability of our approach and given the unavailability of a large scale MPSoC platform at the time of the experience, we have developed the use case on a NUMA platform. The considered MPSoC software is the FFMPEG video decoder [START_REF] Tomar | Converting Video Formats with FFmpeg[END_REF], [START_REF]FFMPEG Website[END_REF].

The NUMA architecture used in our experiments has four nodes, each having eight dual core 2.2 GHz AMD Opteron processors and 32GB of main memory.

In the final experimental setup, one node is considered to be the master one, and as such can access the file system, as well as the peripherals. The master node is also responsible for communicating input peripheral data to the other nodes. It occupies four of the NUMA processors, the other four being reserved for GDB. The other three nodes are MPSoC slave nodes.

The implementation of our MPSoC API uses the Linux2.6 interface, as well as the libSDL 3 and libc libraries. The task management and synchronization functions are based on the POSIX interface and use the system call sched_setaffinity. The I/O functions encapsulate the accesses to the file system, the screen, the keyboard, the audio card and the system clock. The file system is accessed using the libc functions. The audio and video peripherals are accessed through libSDL calls. Finally, the system clock is accessed using a dedicated Linux register. The network communication primitives are based on the inter-process socket-based communication of Linux.

From the FFMPEG suite, we have used the FFPLAY [START_REF] Ahn | Flexible framework for dynamic management of multi-core systems[END_REF] and FFSERVER [START_REF] Pura | Design of a wireless adapter for multimedia projectors[END_REF] components. FFSERVER is a video server, receiving video flows through different protocols (e.g., RTP or RTSP) and creating multiple output flows having different formats (H.264, DIVX, MPEG-4, etc). FFPLAY is a video decoder, receiving and synchronizing audio and video frames. Using these components, we have created a video mosaic application (cf. Figure 12). We have re-engineered the code to redirect all Linux function calls to calls to our MPSoC API. The video mosaic application exhibited a non deterministic bug. During some executions, one or more videos were not visible. By tracing one of these executions, we captured the situation showed on Figure 13. The trace of Node0 (FFSERVER) shows the non blocking receptions of messages coming from FFPLAY components. The other three traces (FFPLAY components) show, in the beginning of their execution, receptions of messages from FFSERVER, followed by synchronization operations related to the work with memory buffers containing the audio/video data. We can clearly see that at one point, Task2 on Node2 blocks and causes the blocking of Task0 and Task1. Having selected this node as the suspected one, as well as the short time interval directly preceding the blocking, the debugging session proved rather straightforward. By tracking the accesses to synchronization structures, we observed that a condition variable is never signaled. During a second replay, we established the connection between this variable and the memory allocation for video frames. During a third replay, we discovered that the developer has forgotten to notify the frame memory allocation.

C. Performances

To evaluate the performances of our implementation, we have considered three criteria, namely the intrusion during normal execution, the trace volume and the execution speed during debugging. To evaluate the intrusion of ReDSoC during the recording phase, we have considered both the embedded and the NUMA platforms and have used the the native execution time and the reference execution time. The native execution time reflects the execution duration of the software without ReDSoC. The measure is obtained as a mean value of thirty executions.The reference execution time is the mean execution time of the same software with the same inputs but running under the control of ReDSoC. This execution is logically slower due to the interception of function calls and the tracing mechanism. Using the two previous measures, the overhead gives the execution slowdown as a percentage.

The considered applications include a simple MJPEG decoder, the Tetris application and the video mosaic application. The results are given in Table I.

In all use cases, the intrusion is very low (Overhead column, 4% for MJPEG and less than 1% in the other cases) and does not cause video glitch visible to the eye. In the case of the Tetris application, for example, this is explained by the fact that the time spent for moving the pieces is much smaller that the time between moves. As a consequence, tracing happens during this inactivity time and does not perturb the application. In the case of the video mosaic application, the tracing situation is similar: the application behavior is very regular and the tracing operations happen in between image decoding operations.

Obviously, this low intrusion cannot be generalized for all cases. However, this experiment confirms the utility to have a resource provisioning (here the management of time constraints) for the tracing operations. Indeed, in most MPSoC platforms, the architecture includes hardware tracing ports which do not perturb normal execution. It is interesting to apply this approach to tracing of the upper software layers.

As non deterministic behavior cannot be easily reproduced and captured, we also note that there is no general prediction about the number of executions a developer needs to run to obtain the reference trace.

Considering the trace volumes (Trace Data column), as we focus on a restrained type of events to record, in all cases the number of entries is rather small (Trace Entries column). In the MJPEG case, for example, due to the more intensive use of synchronization, the number of entries (45471) is more important, which explains the perceivable execution time overhead. The trace data volume is minimal, as we do not record the full data characterizing an event but only the information needed for deterministic replay.

To start the debugging session itself, the actual ReDSoC solution forces the developer to wait for the deterministic replay to happen and reach the selected time interval. In the worst cases, if the selected debugging region is at the end of the execution, the developer needs to wait for two replays, corresponding to the deterministic and partial trace recordings respectively. In the case of the Tetris application, for exemple, if the execution time of N ode0 is 61s, the waiting time for the developer to be able to debug N ode0 is about 161s. An interesting approach to accelerate the process would be to manage application snapshots allowing the deterministic replay to start in the middle of an application execution.

VI. RELATED WORK

There are numerous deterministic record-replay solutions that focus and limit themselves on different sources of non determinism. In a shared memory setting, projects reproduce scheduling decisions only [START_REF] Choi | Deterministic replay of java multithreaded applications[END_REF] or consider data races. The latter consider all shared data accesses [START_REF] Dunlap | Execution replay of multiprocessor virtual machines[END_REF], [START_REF] Laadan | Transparent, lightweight application execution replay on commodity multiprocessor operating systems[END_REF], [START_REF] Patil | PinPlay: a framework for deterministic replay and reproducible analysis of parallel programs[END_REF] or the accesses to synchronization structures [START_REF] Ronsse | Recplay: a fully integrated practical record/replay system[END_REF]. Alternative approaches relax the exact replay of data accesses and focus on application outputs [START_REF] Lee | Respec: efficient online multiprocessor replayvia speculation and external determinism[END_REF]. Others eliminate non determinism by using an adapted execution support [START_REF] Bergan | Deterministic process groups in dos[END_REF]. In a distributed setting, record-replay solutions focus on the data exchanges among nodes [START_REF] Konuru | Deterministic replay of distributed java applications[END_REF], [START_REF] Geels | Replay debugging for distributed applications[END_REF]. To apply to realistic embedded platforms, ReDSoC considers all sources of non determinism and combines record-replay techniques from both shared and distributed memory settings.

In the domain of embedded systems, record-replay mechanisms for multi-tasking embedded systems mainly focus on the reproduction of context switches [START_REF] Thane | Replay debugging of real-time systems using time machines[END_REF], [START_REF] Maeng | Rt-replayer: a recordreplay architecture for embedded real-time software debugging[END_REF], [START_REF] Gracioli | Tracing and Recording Interrupts in Embedded Software[END_REF]. The works investigate the unique identification of context switches, needed for a precise replay, as well as various algorithms for efficient computing of the system state fingerprint. This approach can be used in hard real-time embedded systems but does not apply to multi-core concurrent executions which are considered in ReDSoC.

Record-replay mechanisms strive for a trade-off between cost of implementation, precision and generality. Indeed, hardware-based mechanisms [START_REF] Devietti | Dmp: Deterministic shared memory multiprocessing[END_REF] impose minimal intrusion on the traced system but require costly non commodity hardware. Virtual machine mechanisms [START_REF] Dunlap | Revirt: enabling intrusion analysis through virtual-machine logging and replay[END_REF], [START_REF] Dunlap | Execution replay of multiprocessor virtual machines[END_REF] provide for a comparable level of detail but rarely consider multi-processor platforms. In addition, their cost is prohibitive for embedded systems. System mechanisms [START_REF] Laadan | Transparent, lightweight application execution replay on commodity multiprocessor operating systems[END_REF] provide for transparent record-replay which does not require application modification. They are, however, tightly coupled with the specific operating system they consider. ReDSoC is at the level of application and library mechanisms [START_REF] Geels | Replay debugging for distributed applications[END_REF], [START_REF] Saito | Jockey: A user-space library for record-replay debugging[END_REF] which require some modification (instrumentation, recompilation) of the target application but provide better portability.

Partial replay has been considered in parallel and distributed systems which exhibit too much components and interactions for a total record-replay. Recent works [START_REF] Xue | Mpiwiz: Subgroup reproducible replay of mpi applications[END_REF], [START_REF] Gioachin | Robust non-intrusive recordreplay with processor extraction[END_REF] on many-core High Performance Computing (HPC) architectures reproduce selected groups of processes. However, as their mechanisms are based on their programming models API, they cannot be applied to embedded system environments. As for distributed systems [START_REF] Saito | Jockey: A user-space library for record-replay debugging[END_REF], [START_REF] Hunt | Ddos: Taming nondeterminism in distributed systems[END_REF], existing partial replay solutions limit themselves to considering a single node.

VII. CONCLUSION

In this paper we argue that with the increasing scale and complexity of embedded systems, classic debugging techniques cannot be applied "as is". Non deterministic systems with numerous components need our debugging methodology which applies space and time reduction criteria to the error search space. For human comprehension, debugging should indeed be able to focus on a specific part of the target software and consider a limited time interval. We have shown the usefulness of this approach in our experiences with two multimedia applications on two different platforms. The debugging experiences have proven successful and our system has performed with minimal intrusion.

The selection of the suspected software parts and the time interval to debug is a delicate issue which for now relies on the developer experience. It would be highly beneficial and interesting to couple the proposed debugging methodology with techniques able to automatically delimit "problem zones".

Intrusion is a major issue in record-replay systems and the usual answer is to provide ad-hoc solutions for minimizing the execution overhead. However, modeling and formally estimating the cost of a given tracing/replaying technique will allow for cost predictions and will greatly facilitate the choice between different solutions. This would also be the basis for provisioning hardware resources for record/replay in embedded systems.

ReDSoC uses trace visualization which greatly facilitates the debugging task of the developer. Our belief is that a visual support, representing the execution history of a target system, with the possibility of going back and examining past events beyond the current call stack, becomes a necessary feature for future development environments.

Our proposal is independent from execution platforms as it is based on a general model for MPSoC and an MPSoC API. However, task-based programming models are not the only ones used in the embedded system domain. We think that the future of debugging techniques is to consider higher levels of the application stack and namely the used programming models. The developer needs to be able to work in a topdown approach, starting by the human-comprehensive application entities and interactions before going down to operating system details. Some works exist in the domain of interactive debugging [START_REF] Pouget | Interactive debugging of dynamic dataflow embedded applications[END_REF] but the approach should be also investigated for post-mortem analysis.

Fig. 1 .

 1 Fig. 1. Debugging Cycle

8 Fig. 2 .

 82 Fig. 2. MPSoC Hardware Architecture

Fig. 3 .

 3 Fig. 3. Search Space Reduction

Fig. 4 .

 4 Fig. 4. ReDSoC Architecture

Fig. 5 .

 5 Fig. 5. A fragment of trace visualization

Fig. 6 .

 6 Fig. 6. Stagecoach board with two Overo FE COM nodes

Fig. 7 .

 7 Fig. 7. Two Player Tetris.

Fig. 8 .

 8 Fig. 8. Visualization of the Tetris Reference Trace

Fig. 9 .

 9 Fig. 9. Time Interval Selection

Fig. 10 .

 10 Fig. 10. Partial Debugging of the MPSoC Tetris Application

Fig. 11 .

 11 Fig. 11. Considering a Different Node and a Different Time Interval

Fig. 12 .

 12 Fig. 12. Video Mosaic Application

Fig. 13 .

 13 Fig. 13. Visualization of Captured Traces.

  The step is performed by the developer who debugs the MPSoC software. Using different available tools but mainly his/her experience, the developer analyzes the reference traces in search of abnormal behavior.

	• Step 3: Error Detection
	At this step, the developer decides whether a problem
	has been recorded and should be investigated, in
	which case the cycle continues with Step 4. Otherwise,
	typically if a targeted non deterministic error has not
	yet been recorded, the cycle may restart with Step 1.
	• Step 4: Spatial and Temporal Reduction of the Search
	Space
	During this step, the developer decides to focus on a
	particular part of the software execution thus reducing
	the search space. To do so, the developer may apply
	a spatial and/or a temporal selection criteria. He/she
	selects a suspected part of the application to debug
	during a specific time interval. The definition of these
	criteria represents our second contribution.
	• Step 1: Recording a Reference Execution Trace
	During this step, the execution of the whole MPSoC
	software is recorded to produce reference execution
	traces. These reference traces target the non deter-
	ministic behavior to debug and are exploited in the
	next debugging steps. The data captured in these
	traces has been defined in close relation with the non
	deterministic phenomena we have decided to target,

as well as with the replay techniques we have chosen. Their volume is limited to minimize the tracing overhead during execution. Yet, the recorded data is sufficient for a deterministic replay. The choice of target non deterministic phenomena to debug and the identification of adapted replay algorithms represents our first contribution.

• Step 2: Trace Analysis

• Step 5: Deterministic Replay and Recording Partial

Traces During this step, the reference trace is deterministically replayed to capture additional data reflecting the execution of the software part, selected in Step 4.

• Step 6: Deterministic Partial Replay and Debugging

During this step, only the selected software part is considered and the corresponding trace deterministically replayed. The replay mechanism is connected to a debugging tool, so the developer may debug the execution of the selected part and during the selected time interval in a standard way. • Step 7: Error Identification If the error source is not identified after Step 6, the developer goes back to Step 4. If the developer want to focus on a different software part, the cycle goes through Step 5. If the developer considers the same software part but during a different time interval, there is no need for additional trace collection and the cycle continues directly with Step 6.

TABLE I

 I

	.	INTRUSION MEASURES

https://store.gumstix.com/index.php/products/247/

http://www.mentor.com/embedded-software/sourcery-tools/sourcerycodebench/editions/lite-edition/

ACKNOWLEDGMENT

This work has been done in a collaboration with the IDTEC department of STMicroelectronics, Crolles, France.


Ivan Gazeau

Dale Miller

Catuscia Palamidessi

Preserving differential privacy under finite-precision semantics *

Keywords: Differential privacy, floating-point arithmetic, robustness to errors

The approximation introduced by finite-precision representation of continuous data can induce arbitrarily large information leaks even when the computation using exact semantics is secure. Such leakage can thus undermine design efforts aimed at protecting sensitive information. We focus here on differential privacy, an approach to privacy that emerged from the area of statistical databases and is now widely applied also in other domains. In this approach, privacy is protected by the addition of noise to a true (private) value. To date, this approach to privacy has been proved correct only in the ideal case in which computations are made using an idealized, infinite-precision semantics. In this paper, we analyze the situation at the implementation level, where the semantics is necessarily finiteprecision, i.e. the representation of real numbers and the operations on them, are rounded according to some level of precision. We show that in general there are violations of the differential privacy property, and we study the conditions under which we can still guarantee a limited (but, arguably, totally acceptable) variant of the property, under only a minor degradation of the privacy level. Finally, we illustrate our results on two cases of noise-generating distributions: the standard Laplacian mechanism commonly used in differential privacy, and a bivariate version of the Laplacian recently introduced in the setting of privacy-aware geolocation.

Introduction

It is well known that, due to the physical limitations of actual machines, in particular the finiteness of their memory, real numbers and their operations cannot be implemented with full precision. While for traditional computation getting an approximate result is not critical when a bound on the error is known, we argue that, in security applications, the approximation error can became a fingerprint potentially causing the disclosure of secrets.

Obviously, the standard techniques to measure the security breach do not apply, because an analysis of the system in the ideal (aka exact) semantics does not reveal the information leaks caused by the implementation. Consider, for instance, the following simple program if f (h) > 0 then ℓ = 0 else ℓ = 1 where h is a high (i.e., confidential) variable and ℓ is a low (i.e., public) variable. Assume that h can take two values, v 1 and v 2 , and that both f (v 1 ) and f (v 2 ) are strictly positive. Then, in the ideal semantics, the program is perfectly secure, i.e. it does not leak any information. However, in the implementation, it could be the case that the test succeeds in the case of v 1 but not in the case of v 2 because, for instance, the value of f (v 2 ) is below the smallest representable positive number. Hence, we would have a total disclosure of the secret value.

The example above is elementary but it should give an idea of the pervasive nature of the problem, which can have an impact in any confidentiality setting, and should therefore receive attention by those researchers interested in (quantitative) information flow. In this paper, we initiate this investigation with an in-depth study of the particular case of differential privacy.

Differential privacy [START_REF] Dwork | Differential privacy[END_REF][START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] is an approach to the protection of private information that originated in the field of statistical databases and is now investigated in many other domains, ranging from programming languages [START_REF] Barthe | Probabilistic relational reasoning for differential privacy[END_REF][START_REF] Gaboardi | Linear dependent types for differential privacy[END_REF] to social networks [START_REF] Narayanan | De-anonymizing social networks[END_REF] and geolocation [START_REF] Machanavajjhala | Privacy: Theory meets practice on the map[END_REF][START_REF] Ho | Differential privacy for location pattern mining[END_REF][START_REF] Andrés | Geoindistinguishability: Differential privacy for location-based systems[END_REF]. The key idea behind differential privacy is that whenever someone queries a dataset, the reported answer should not allow him to distinguish whether a certain individual record is in the dataset or not. More precisely, the presence or absence of the record should not change significantly the probability of obtaining a given answer. The standard way of achieving such a property is by using an oblivious mechanism 1 which consists in adding some noise to the true answer. Now the point is that, even if such a mechanism is proved to provide the desired property in the ideal semantics, its implementation may induce errors that alter the least significant digits of the reported answer and cause significant privacy breaches. Let us illustrate the problem with an example.

Example 1.1. Consider the simplest representation of reals: the fixed-point numbers. This representation is used on low-cost processors which do not have floating-point arithmetic module. Each value is stored in a memory cell of fixed length. In such cells, the last d digits represent the fractional part. Thus, if the value (interpreted as an integer) stored in the cell is z, its semantics (i.e., the true real number being represented) is z • 2 -d .

To grant differential-privacy, the standard technique consists of returning a random value with probability p(x) = 1 /2b • e -|x-r| /b where r is the true result and b is a scale parameter which depends on the degree of privacy to be obtained and on the sensitivity of the query. To get a random variable with any specific distribution, in general, we need to start with an initial random variable provided by a primitive of the machine with a given distribution. To simplify the example, we assume that the machine already provides a Laplacian random variable X with a scale parameter 1. The probability distribution of such an X is p X (x) = 1 /2e -|x| . Hence, if we want to generate the random variable bX with probability distribution p bX (x) = 1 /2b • e -|x| /b , we can just multiply by b the value x = z • 2 -d returned by the primitive.

Assume that we want to add noise with a scale parameter b = 2 n for some fixed integer n (b can be big when the sensitivity of the query and the required privacy degree are high). In this case, the multiplication by 2 n returns a number 2 n z • 2 -d that, in the fixed-point representation terminates with n zeroes. Hence, when we add this noise to the true result, we return a value whose representation has the same n last digits as the secret. For example, assume b = 2 2 = 4 and d = 6. Consider that the true answers are r 1 = 0 and r 2 = 1 + 2 -5 . In the fixed-point representation, the last two digits of r 1 are 00, and the last two digits of r 2 are 10. Hence, even after we add the noise, we can always tell whether the true value was r 1 or r 2 . Note that the same example holds for every b = 2 n and every pair of true values r 1 and r 2 which differ by (2 n k+h) /2 d where k is any integer and h is any integer between 1 and 2 n -1. Figure 1 illustrates the situation for b = 4, k = 3 and h = 2.

Another attack, based on the IEEE standard floating-point representation [START_REF]IEEE 754-2008, Standard for Floating-Point Arithmetic. IEEE[END_REF], was presented in [START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF]. In contrast to [START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF], we have chosen an example based on the fixed point representation because it allows x P(x) 0 Figure 1: The probability distribution of the reported answers after the addition of Laplacian noise for the true answer r 1 = 0 (black) and

r 2 = 3 • 2 -4 + 2 -5 (green).
to illustrate more distinctively a problem for privacy which rises from the finite precision2 and which is, therefore, pandemic. (This is not the case for the example in [START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF]: fixed-point and integer-valued algorithms are immune to that attack.)

In this paper, we propose a solution to fix the privacy breach induced by the finite-precision implementation of a differentially-private mechanism for any kind of implementation. Our main concern is to establish a bound on the degradation of privacy induced by both the finite representation and by the computational errors in the generation of the noise. In order to achieve this goal, we use the concept of closeness introduced by the authors in [START_REF] Gazeau | A non-local method for robustness analysis of floating point programs[END_REF], which allows us to reason about the approximation errors and their accumulation. We make as few assumptions as possible about the procedure for generating the noise. In particular, we do not assume that the noise has a linear Laplacian distribution: it can be any noise that provides differential privacy and whose implementation satisfies a few properties (normally granted by the implementation of real numbers) which ensure its closeness. We illustrate our method with two examples: the classic case of the univariate (i.e., linear) Laplacian, and the case of the bivariate Laplacian. The latter distribution is used, for instance, to generate noise in privacy-aware geolocation mechanisms [START_REF] Andrés | Geoindistinguishability: Differential privacy for location-based systems[END_REF].

Related work

As far as we know, the only other work that has considered the problem introduced by the finite precision in the implementation of differential privacy is [START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF]. As already mentioned, that paper showed an attack on the Laplacian-based implementation of differential privacy within the IEEE standard floating-point representation 3 . To thwart such an attack, the author of [START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF] proposed a method that avoids using the standard uniform random generator for floating point (because it does not draw all representable numbers but only multiple of 2 -53 ). Instead, his method generates two integers, one for the mantissa and one for the exponent in such a way that every representable number is drawn with its correct probability. Then it computes the linear Laplacian using a logarithm implementation (assumed to be full-precision), and finally it uses a snapping mechanism consisting in truncating large values and then rounding the final result.

The novelties of our paper, w.r.t. [START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF], consist in the fact that we deal with a general kind of noise, not necessarily the linear Laplacian, and with any kind of implementation of real numbers, not necessarily the IEEE floating point standard. Furthermore, our kind of analysis allows us to measure how safe an existing solution can be and what to do if the requirements needed for the safety of this solution are not met. Finally, we consider our correct implementation of the bivariate Laplacian also as a valuable contribution, given its practical usefulness for location-based applications.

The only other work we are aware of, considering both computational error and differential privacy, is [START_REF] Chaudhuri | Proving programs robust[END_REF]. However, that paper does not consider at all the problem of the loss of privacy due to implementation error: rather, they develop a technique to establish a bound on the error, and show that this technique can also be used to compute the sensitivity of a query, which is a parameter of the Laplacian noise.

Plan of the paper

This paper is organized as follow. In section 2, we recall some mathematical definitions and introduce some notation. In section 3, we describe the standard Laplacian-based mechanism that provides differential privacy in a theoretical setting. In section 4, we discuss the errors due to the implementation, and we consider a set of assumptions which, if granted, allows us to establish a bound on the irregularities of the noise caused by the finite-precision implementation. Furthermore we propose a correction to the mechanism based on rounding and truncating the result. Section 5 contains our main theorem, stating that with our correction the implementation of the mechanism still preserves differential privacy, and establishing the precise degradation of the privacy parameter. The next two sections propose some applications of our result: Section 6 illustrates the technique for the case of Laplacian noise in one dimension and section 7 shows how our theorem applies to the case of the Euclidean bivariate Laplacian. Section 8 concludes and discusses some future work.

Preliminaries and notation

In this section, we recall some basic mathematical definitions and we introduce some notation that will be useful in the rest of the paper. We will assume that the the queries give answers in R m . Examples of such queries are the tuples representing, for instance, the average height, weight, and age. Another example comes from geolocation, where the domain is R 2 .

Distances and geometrical notations

There are several natural definitions of distance on R m [START_REF] Rudin | Real and Complex Analysis[END_REF]. For m ∈ N and x = (x 1 , . . . , x m ) ∈ R m , the L p norm of x, which we will denote by x p , is defined as

x p = p m ∑ i=1 |x i | p
The corresponding distance function is

d p (x, y) = x -y p
We extend this norm and distance to p = ∞ in the usual way:

x ∞ = max i∈{1,...,m} |x i | and d ∞ (x, y) =
xy ∞ . The notion of L ∞ norm is extended to functions in the following way: given

f : A → R m , we define f ∞ = max x∈A f (x)
. When clear from the context, we will omit the parameter p and write simply x and d(x, y) for x p and d p (x, y), respectively. Let S ⊆ R m . We denote by S c the complement of S, i.e., S c = R m \ S. The diameter of S is defined as

(S) = max x,y∈S d(x, y).
For ε ∈ R + , the +ε-neighbor and the -ε-neighbor of S are defined as

S +ε = {x | ∃s ∈ S, d(x, s) ≤ ε} S -ε = {x | ∀s ∈ R m , d(x, s) ≤ ε =⇒ s / ∈ S} = ((S c ) +ε ) c
For x ∈ R m , the translations of S by x and -x are defined as

S + x = {y + x | y ∈ S} S -x = {y -x | y ∈ S}

Measure theory

We recall here some basic notions of measures theory that will be used in this paper.

Definition 2.1 (σ -algebra and measurable space). A σ -algebra T for a set M is a nonempty set of subsets of M that is closed under complementation (wrt to M) and (potentially empty) enumerable union.

The tuple (M, T ) is called a measurable space.

Definition 2.2 (Measure). A positive measure µ on a measurable space (M, T ) is a function T → R + ∪ {0} such that µ( / 0) = 0 and whenever (S i ) is a enumerable family of disjoint subset of M then ∑ µ(S i ) = µ( S i ).
A positive measure µ where µ(X) = 1 is called a probability measure.

A tuple (M, T , P) where (M, T ) is a measurable space and P a probability measure is called probability space.

In this paper we will make use of the Lebesgue measure λ on (R m , S ) where S is the Lebesgue σ -algebra. The Lebesgue measure is the standard way of assigning a measure to subsets of R m .

Definition 2.3 (Measurable function). Let (M, T ) and (V, Σ) be two measurable spaces. A function

f : M → V is measurable if f -1 (v) ∈ T for all v ∈ Σ. Definition 2.4 (Absolutely continuous). A measure ν is absolutely continuous according to a measure µ, if for all M ∈ S , µ(M) = 0 implies ν(M) = 0.
If a measure is absolutely continuous according to the Lebesgue measure then by the Radon-Nikodym theorem, we can express it as an integration of a density function f :

µ(M) = M f (x) dλ

Probability theory

Definition 2.5 (Random variable). Let (Ω, F , P) be a probability space and (E, E ) a measurable space. Then a random variable is a measurable function X : Ω → E. We shall use the expression P [X ∈ B] to denote P X -1 (B) .

Let f : R m → R m be a measurable function and let X : Ω → R m be a random variable. In this paper, we will use the notation f (X) to denote the random variable Y :

Ω → R m such that f (X)(ω) = f (X(ω)).
In particular, for m ∈ R m we denote by m + X the random variable Y : Ω → R m such that ω → X(ω) + m. Definition 2.6 (Density function). Let X : Ω → E be a random variable. If there exists a function f such that, for all S ∈ S , P[X ∈ S] = S f (u) du, then f is called the density function of X.

In this paper, we use the following general definition of the Laplace distribution (centered at zero).

[(X,Y ) ∈ (I, J)] = P[X ∈ I ∧ Y ∈ J].
Definition 2.9 (Marginals). Let X and Y : (Ω, F , P) → (R m , S ). The marginal probability of the random variable (X,Y ) for X is defined as:

P[X ∈ B] = R m P[(X,Y ) ∈ (B, dy)].

Differential privacy in the exact semantics

In this section we recall the definition of differential privacy and of the standard mechanisms to achieve it, and we discuss its correctness.

Differential privacy

We denote by D the set of databases and we assume that the domain of the answers of the query is R m for some n ≥ 1. We denote by D 1 ∼ D 2 the fact that D 1 and D 2 differ by at most one element. Namely, D 2 is obtained from D 1 by adding or removing one element.

Definition 3.1 (ε-differential privacy). A randomized mechanism

A : D → R m is ε-differentially private if for all databases D 1 and D 2 in D with D 1 ∼ D 2 ,
and all S ∈ S (the Lebegue σ -algebra), we have :

P[A (D 1 ) ∈ S] ≤ e ε P[A (D 2 ) ∈ S] Definition 3.2 (sensitivity). The sensitivity ∆ f of a function f : D → R m is ∆ f = sup D 1 ,D 2 ∈D,D 1 ∼D 2 d( f (D 1 ), f (D 2 )).

Standard technique to implement differential privacy

The standard technique to grant differential privacy is to add random noise to the true answer to the query. In the following, we denote the query by f : D → R m . This is usually a deterministic function.

We represent the noise as a random variable X : Ω → R m . The standard mechanism, which we will denote by A 0 , returns a probabilistic value which is the sum of the true result and of a random variable X, namely:

Mechanism 1. A 0 (D) = f (D) + X

Error due to the implementation of the query

The correctness of a mechanism A , if we do not take the implementation error into account, consists in A being ε-differentially private. However, we are interested in analyzing the correctness of the implemented mechanism. We start here by discussing the case in which, in mechanism 1, the noise X is exact but we take into account the approximation error in the implementation of f .

Notation Given a function g, we will indicate by g ′ its implementation, i.e. the function that, for any x, gives as result the value actually computed for g(x), with all the approximation and representation errors.

The first thing we observe is that the implementation of f can give a sensitivity ∆ f ′ greater than ∆ f and we need to take that into account. In fact, in the exact semantics the correctness of the mechanism relies on the fact that d( f (D 1 ), f (D 2 )) ≤ ∆ f . However, with rounding errors, we may have d( f ′ (D 1 ), f ′ (D 2 )) > ∆ f . Hence we need to require the following property, usually stronger than differential privacy.

Condition 1. Given a mechanism A (D) = f ′ (D) + X, we say that A satisfies Condition 1 with degree ε (the desired degree of differential privacy) if the random variable X has a probability distribution which is absolutely continuous according to the Lebesgue measure, and

∀S ∈ S , r 1 , r 2 ∈ R m , P[r 1 + X ∈ S] ≤ e ε d(r 1 ,r 2 ) ∆ f ′ P[r 2 + X ∈ S]
Remark 1. In general we expect that an analysis of the implementation of f will provide some bound on the difference between f and f ′ , and that will allow us to provide a bound on

∆ f ′ in terms of ∆ f . For instance, if f -f ′ ≤ δ f then we get ∆ f ′ ≤ ∆ f + 2δ f . Proposition 3.1. Condition 1 implies that the mechanism A (D) = f ′ (D) + X is ε-differentially private (w.r.t. f ′ ).
Proof Let D 1 and D 2 be two databases such that

D 1 ∼ D 2 . Let r 1 = f ′ (D 1 ) and r 2 = f ′ (D 2 ) be two answers. By definition of sensitivity, d(r 1 , r 2 ) ≤ ∆ f ′ so e ε d(r 1 ,r 2 ) ∆ f ′ ≤ e ε . Hence, P[A (D 1 ) ∈ S] ≤ e ε P[A (D 2 ) ∈ S]
The following theorem shows that Condition 1 is actually equivalent to differential privacy in the case of Laplacian noise.

Theorem 3.1. Let A (D) = f ′ (D) + X be a mechanism, and assume that X is Laplacian. If A is ε- differentially private (w.r.t. f ′ ), then Condition 1 holds. Proof First, we show that if A is ε-differentially private then b ≤ ε ∆ f ′ holds for the scale parameter b of X. Let D 1 ∼ D 2 with d( f ′ (D 1 ), f ′ (D 2 )) = ∆ f ′ .
By ε-differential privacy we have, for any S ∈ S :

P[ f ′ (D 1 ) + X ∈ S] ≤ e ε P[ f ′ (D 2 ) + X ∈ S]
From the density function of the Laplace noise (Definition 2.7), we derive:

K(n, d)dλ ≤ e ε K(n, d)e -b∆ f ′ dλ Hence, b ≤ ε ∆ f ′ . (1)
Now, by definition of the density function, we have

P[r 2 + X ∈ S] = x∈S K(n, d)e -bd(x,r 2 ) dλ
From the triangular inequality, we derive:

P[r 2 + X ∈ S] ≥ x∈S K(n, d)e -b(d(x,r 1 )+d(r 1 ,r 2 )) dλ
Hence,

P[r 2 + X ∈ S] ≥ e -bd(r 2 ,r 1 ) x∈S e -bd(r 1 ,x) dλ
From inequality (1), we derive:

P[r 2 + X ∈ S] ≥ e - εd(r 2 ,r 1 ) ∆ f ′ x∈S e -bd(r 1 ,x) dλ Finally, P[r 2 + X ∈ S] ≥ e - εd(r 2 ,r 1 ) ∆ f ′ P[r 1 + X ∈ S]
4 Error due to the implementation of the noise

In this section we consider the implementation error in the noise, trying to make as few assumptions as possible about the implementation of real numbers and of the noise function.

We start with example which shows that any finite implementation makes it impossible for a mechanism to achieve the degree of privacy predicted by the theory (i.e. the degree of privacy it has in the exact semantics). This example is more general than the one in the introduction in the sense that it does not rely on any particular implementation of the real numbers, just on the (obvious) assumption that in a physical machine the representation of numbers in memory is necessarily finite. On the other hand it is less "dramatic" than the one in the introduction, because it only shows that the theoretical degree of privacy degrades in the implementation, while the example in the introduction shows a case in which ε-differential privacy does not hold (in the implementation) for any ε.

Example 4.1. Consider the standard way to produce a random variable with a given probability law, such as the Laplace distribution. Randomness on most computers is generated with integers. When we call a function that returns a uniform random value on the representation of reals, the function generates a random integer z (with uniform law) between 0 and N (in practice N ≥ 2 32 ) and returns u = z /N. From this uniform random generator, we compute n( z /N) where n depends on the probability distribution we want to generate. For instance, to generate the Laplace distribution we have n(u) = -b sgn(u -1/2) ln(1 -2|u -1 /2|) which is the inverse of the cumulative function of the Laplace distribution. However the computation of n is performed in the finite precision semantics, i.e. n is a function F → F where F is the finite set of the representable numbers. In this setting, the probability of getting some value x for our noise depends on the number of integers z such that n( z /N) = x : if there are k values for z such x P(x)

0 x 0 Figure 2:
The probability distributions of Laplace noises generated from a discretized uniform generator that n( z /N) = x then the probability of getting x is k /N. This means, in particular, that, if the theoretical probability for a value x is 1.5/N, then the closest probability actually associated with the drawing of x is either 1 /N or 2 /N and in both cases the error is at least 33%. In figure 2, we illustrate how the error on the distribution breaks the differential-privacy ratio that holds for the theoretical distribution. The ratio between the two theoretical Laplacian distributions is 4 /3. However, since the actual distribution is issued from a discretization of the uniform generator, the resulting distribution is a step function. So when the theoretical probability is very low like in x 0 , the discretization creates an artificial ratio of 2 instead of 4 /3.

The initial uniform random generator

To generate a random variable, programing languages have only one primitive that generates a random value between 0 and 1 that aims to be uniform and independent across several calls.Hence, to get a random variable with a non uniform distribution, we generate it with a function that makes calls to this random generator. For instance, to draw a value from a random variable X on R distributed according to the cumulative function C : R →]0, 1], it is sufficient to pick a value u from the uniform generator in ]0, 1] and then return C -1 (u).

We identify three reasons why a uniform random generator may induce errors. The first has been explained in the introduction: finite precision allows generating only N different numbers such that when we apply a function on the value picked some values are missing and other are over represented. The second reason comes from the generator itself which can returns the N values with different probabilities even though we might assume that they are returned with probability 1/N: furthermore, some values may not even be returned at all. A third error is due to the dependence of returned results when we pick several random values. Indeed most of the generator implementations are indeed pseudo generators: when a value is picked the next one is generated as a hash function of the first one. This means that if we have N possibilities for one choice then we also have N possible pairs of successive random values.

To reason about implementation leakage, we have to take into account all of these sources of errors. We propose the following model. In the exact semantics, the uniform random variable U q is generated from a cross product of q uniform independent variables U (with q ≥ m). We denote by u 1 , . . . , u q ∈ [0, 1] q the values picked by our perfect random generator. Then we consider the random variable U q′ actually provided as generated from a function n 0 : R q → R q , (u ′ 1 , . . . , u ′ q ) = n 0 (u 1 , . . . , u q ). We assume that the Preserving differential privacy bias, i.e., the difference between n 0 and the identity, is bounded by some δ 0 ∈ R + :

n 0 -Id ∞ ≤ δ 0 . (2)

The function n for generating the noise

From the value u (resp. u ′ ) drawn according to the distribution U q in the exact semantics (resp. according to U q′ in the actual implementation), we generate another value by applying the functions n and n ′ respectively. Let X = n(U q ) be the random variable with the exact distribution and X ′ = n ′ (U q′ ) the random variable with the actual one.

Definition 4.1. We denote by µ and ν the probability measure of X and X ′ , respectively: for all S ∈ S ,

µ(S) = P[n(U q ) ∈ S] = λ (n -1 (S)) and ν(S) = P[n ′ (U q′ ) ∈ S] = λ (n -1 0 (n -1 (S))
). In order to establish a bound on the difference between the probability distribution of X and X ′ we need some condition on the implementation n ′ of n. For this purpose we use the notion of closeness that we defined in [START_REF] Gazeau | A non-local method for robustness analysis of floating point programs[END_REF]. Definition 4.2 ((k, δ )-close, [START_REF] Gazeau | A non-local method for robustness analysis of floating point programs[END_REF]). Let A and B be metric spaces with distance d A and d B , respectively. Let n and n ′ be two functions from A to B and let k, δ ∈ R + . We say that n

′ is (k, δ )-close to n if ∀u, v ∈ A, d B (n(u), n ′ (v)) ≤ k d A (u, v) + δ .
This condition is a combination of the k-Lipschitz property, that states a bound between the error on the output and the error on the input, see below, and the implementation errors of n:

Definition 4.3 (k-Lipschitz). Let (A, d A ) and (B, d B ) be two metrics spaces and k ∈ R: A function n : A → B is k-Lipschitz if: ∀u, v ∈ A, d B (n(u), n(v)) ≤ kd A (u, v)
In [START_REF] Gazeau | A non-local method for robustness analysis of floating point programs[END_REF], we have proven the following relation between the properties of being k-Lipschitz and of being (k, δ )-close. We strengthen now the relation by proving that (a sort of) the converse is also true. d(n(u),n(v)) ≤ kd(u, v) + 2δ . Hence, we obtain a contradiction. Now, we would like and n ′ to be (k, δ )-close on R m . However, this implies that A 0 (mechanism 1) cannot be ε-differentially-private. In fact, the latter would imply n([0, 1] q ) ∞ = ∞ otherwise certain answers could be reported (with non-null probability) only in correspondence with certain true answers and not with others. However, n([0, 1] q ) ∞ = ∞ and [0, 1] q bounded implies there exist u, v, such that d(n(u), n(v)) > kd(u, v) + 2δ : we derive from theorem 4.2 that n ′ cannot exist.

In order to keep computed results in a range where we are able to bound the computational errors, one possible solution consists of a truncation of the result. The traditional truncation works as follows: choose a subset M r ⊂ R m and, whenever the reported answer x is outside M r return the closest point to x in M r . However, while such a procedure is safe in the exact semantics because remapping does not alter differential privacy, problems might appears when n and n ′ are not close. Furthermore, while in the uni-dimensional case there are two disjoints set that are mapped one on the minimal value and the other on the maximal value, in higher dimensions we have a connected set that is mapped on several points, and on which the error is not bounded.

Therefore, to remain in a general framework where we do not have any additional knowledge about computational errors for large numbers, we decide here to return an exception value when the result is outside of some compact subset M r of R m . We denote by ∞ the value returned by the mechanism when f ′ (D) + X ′ / ∈ M r . Hence, the truncated mechanism A returns the randomized value or ∞:

Mechanism 2. A (D) = f ′ (D) + X ′ if f ′ (D) + X ′ ∈ M r ∞ otherwise
We truncate the result because we want to exclude non-robust computations from our mechanism. However, such a procedure is effective only if unsafe computations remain outside the safe domain.

To grant this property we need two more conditions. One requires the implementation to respect the monotonicity of the computed functions:

Condition 2. We say that a function g : R m → R k satisfies Condition 2 if, for all x, y ∈ R m , g(x) ≤ g(y) implies g ′ (x) ≤ g ′ (y) .
With this property, even if the implementation is not robust for large values, if we know some result is not in M r then the result for any greater value is not in M r either.

The other condition is about the closeness of the implementation of the noise and its exact semantics in a safe area. For any δ r ∈ R + , we consider the set U r ⊂ U q defined as ∀u ∈ U r n(u)

≤ (M r ) + δ r i.e. : U r = n -1 ({y | y ≤ (M r ) + δ r }).

Condition 3. We say that a noise n satisfies Condition 3 if n and n

′ are (k, δ n )-close on a set U r such that ∀u ∈ U c r f ′ (D) + n(u) / ∈ M +kδ 0 +δ n r
To find such a set U r , one possible way is by a fix point construction. We begin by finding the smallest k 0 and δ n0 such that n and n ′ are (k 0 , δ n0 )-close on M r . Then for the generic step m > 0, we compute the smallest k m+1 and δ nm+1 such that n and n ′ are (k m+1 , δ nm+1 )-close on M k m δ 0 +δ nm r . If Conditions 2 and 3 hold, then from (2) we derive

∀u ∈ U c r f ′ (D) + n ′ (n 0 (u)) / ∈ M r (3)
So whatever happens outside of U r , the result will be truncated. We can then consider that there is no implementation error outside U r . Finally, we have a bound δ t for the maximal shift between the exact and the actual semantics:

δ t = kδ 0 + δ n (4)

A distance between distributions

Given that we are in a probabilistic setting, the round-off errors cannot be measured in terms of numerical difference as they can be in the deterministic case, they should rather be measured in terms of distance between the theoretical distribution and the actual distribution. Hence, we need a notion of distance between distributions. We choose to use the ∞-Wassertein distance [START_REF] Champion | The ∞-wasserstein distance: Local solutions and existence of optimal transport maps[END_REF] which, as we will show, is the natural metric to measure our deviation.

In this way we grant that any measurable set has a minimal measure and we prevent the inequality from being violated when probabilities are small. The following value R represents the robustness of the rounding.

R = max S∈S ′ 0 ,S = / 0 λ (S δ t \ S -δ t ) λ (S -δ t ) (6)
5 Preserving differential privacy

In this section, we prove that if all conditions are met, then the implementation of the mechanism satisfies differential privacy.

Theorem 5.1. Any mechanism that respects Conditions 1-3 is ε ′ -differentially private, with:

∀S ∈ S , P[A ′ (D 1 ) ∈ S] ≤ e ε ′ P[A ′ (D 2 ) ∈ S ′ ]
where

ε ′ = ε + ln(1 + Re ε L+δ t ∆ f ′ ), δ t = kδ 0 + δ n and L = max S∈S ′ 0 S.
Proof Let S in S . We first consider the case S = ∞.

Define P 1 = P[A ′ (D 1 ) ∈ S] and P 2 = P[A ′ (D 2 ) ∈ S].
Since the result has been rounded (Definition 3), it is equivalent to consider the set S ′ ∈ S ′ with S ′ = r -1 (S) instead of S. Now we have

P i = P[ f ′ (D i ) + n ′ (X) ∈ S ′ ] = P[n ′ (X) ∈ S ′ -f ′ (D i )]
where i is 1 or 2. Since ν is the measure associated to n ′ , we have

P i = ν(S ′ -f ′ (D i ))
From ( 4) and Theorem 4.3, d(ν, µ) ≤ δ t . From Theorem 4.4 we derive

P 1 ≤ µ(S δ t -f ′ (D 1 )) and P 2 ≥ µ(S -δ t -f ′ (D 2 )).
The additivity property of measures grants us µ(S δ t ) = µ(S -δ t ) + µ(S δ t -S -δ t ). Condition 1 can be expressed in term of the measure as:

∀S ∈ S , r ∈ R m r , µ(S) ≤ e ε r ∆ f ′ µ(S -r)
From this inequality, we can derive, since r = ∆ f ′ :

µ(S ε ) ≤ e ε P 2 + µ(S δ t \ S -δ t )
Since the probability is absolutely continuous according to the Lebesgue measure (Condition 1), we can express the probability with a density function p:

∀S ∈ S , µ(S) = S p(x)dλ We derive: ∀S ∈ S , min x∈S p(x) ≤ µ(S) λ (S)
By applying this property on S -δ tf ′ (D 2 ), we get:

min x∈S -δ t -f ′ (D 2 ) p(x) ≤ µ(S -δ t -f ′ (D 2 )) λ (S -δ t -f ′ (D 2 ))
We derive:

∃x 0 ∈ S -f ′ (D 2 ), p(x 0 ) ≤ P 2 λ (S)
By the triangular inequality, we can bound the distance between x 0 and any point of S δ t by ∆ f ′ +L+δ t Hence, from Condition 1 we derive:

∀x ∈ S δ t -f ′ (D 1 ), p(x) ≤ e ε ∆ f ′ +L+δ t ∆ f ′ p(x 0 )
Then by integration:

µ(S δ t -f ′ (D 1 ) \ S -δ t ) ≤ e ε ∆ f ′ +L+δ t ∆ f ′ λ (S δ t \ S -δ t ) λ (S -δ t ) P 2
We apply the condition 6:

µ(S δ t -f ′ (D 1 ) \ S -δ t ) ≤ e ε ∆ f ′ +L+δ t ∆ f ′ RP 2
Finally we obtain :

P 1 ≤ (1 + Re ε L+δ t ∆ f ′ )e ε P 2 In case S is ∞, due to (3), P[A ′ (D) = ∞] is the same as P[ f ′ (D) + X ′ ∈ M c r ] where d(µ, ν) ≤ δ t . Moreover, M c
r can be decomposed in a enumerable disjoint union of element of S 0 . Therefore, the first part of the proof applies: ε ′ -differential privacy holds for all these elements. By the additivity of the measure of disjoint union we conclude.

Application to the Laplacian noise in one dimension

In this section we illustrate how to use our result in the case in which the domain of the answers is R. The noise added for the protocol, stated in the mechanism 1, is the Laplacian centered in 0 with scale parameter ∆ f ′ /ε. Theorem 3.1 implies that Condition 1 holds for ε. We truncate the result outside of some interval M r = [m, M].

Implementation of the n function

To generate a centered Laplacian distribution from a uniform random variable U in ]0, 1], a standard method consists in using the inverse of the cumulative function, i.e.

X = n(U) = -b sgn(U -1/2) ln(1 -2|U -1/2|
), where b is the intended scale parameter (

∆ f ′ ε in our case). Hence our exact function n is n(u) = ∆ f ′ ε sgn(u -1/2) ln(1 -2|u -1/2|). ( 7
)
Closeness of n and n ′ In order to apply our theorem, we need to prove that Condition 3 is satisfied. By theorem 4.1, it is sufficient to prove that, in the interval of interest, n(u) is k-Lipschitz and that |n(u)n ′ (u)| ≤ δ n . Note that the values of δ n and k in general depend on n and on its implementation (often the logarithm is implemented by the CORDIC algorithm).

The logarithm function used by n is not k-Lipschitz for any k. However, we are interested in the behavior of n when |n(u)| ≤ Mm. From the definition of n in [START_REF] Chaudhuri | Proving programs robust[END_REF], we have:

dn du (u) ≤ dn max = 2∆ f ′ ε e ε (Mr ) ∆ f ′ in U r = {u|n(u) ≤ M -m}.
So our function n is dn max -Lipschitz. Finally, our global error is

δ t = 2∆ f ′ ε e ε (Mr ) ∆ f ′ δ 0 + δ n
Rounding the result The rounding process generates a σ -algebra S ′ composed by small intervals of length L where L is the accuracy step of the rounding. In that case, the value defined in ( 6) is R = L+2δ t L-2δ t .

Differential privacy By Theorem 5.1, the implementation of our mechanism is ε ′ -differentially private with

ε ′ = ε + ln(1 + L + 2δ t L -2δ t e ε L+δ t ∆ f ′ ) Remark 2.
In case our answer is not in [m, M], we can return -∞ or +∞ instead of ∞. The reason is that even if the algorithm is not robust when |u -0.5| is small the sign is still correct. Then we can remap -∞ to m and +∞ to M to get the usual truncation procedure.

7 Application to the Laplacian noise in R 2

When the domain of the answers are the points of a map, like in the case of location-based applications, it is natural to formalize it as the space R 2 equipped with the Euclidean distance.

According to the protocol, we sanitize the results by adding a random variable X. In this case, we will use for X the bivariate Laplacian defined for the Euclidean metric [START_REF] Andrés | Geoindistinguishability: Differential privacy for location-based systems[END_REF] whose density function is:

p(x, y) = Ke b √ |x-x 0 | 2 +|y-y 0 | 2
where K is the normalization constant and b the scale parameter. Since we are using a Laplacian noise, by Theorem 3.1, Condition 1 holds.

Truncation Since most of the time the domain studied is bound (for instance the public transportation of a city is inside the limit of the city), we can do a truncation. However, we recall that our truncation is made for robustness purpose and not just for utility reasons. Hence, if our domain of interest is a circle, we will not choose M r to be the same circle because the probability the truncation would return an exception would be too high (more than one half if the true result is on the circumference).

Implementation of the n function

C (ε, (M r )) the function C -1 ε is k-Lipschitz in [0, (M r )].
Since C is differential, this question is equivalent to find the inverse of the minimal value taken by its derivative function on the interval C -1 ε ([0, (M r )]). By computing this minimum value, we get:

K C (ε, (M r )) = e ε (M r ) 2ε + rε 2
On the other hand, the computation of θ is just a multiplication by 2π of the uniform generator hence k θ = 2π. Then, with the conversion (r, θ ) → (r cos(θ ), r sin(θ )) from polar coordinates to Cartesian coordinates we obtain the global k factor:

k = K C (ε, (M r )) 2 + 2π (M r )
Let δ n be the distance between n and n ′ , and δ 0 be the error of the uniform generator. From (4) we get:

δ t = K C (ε, (M r )) 2 + 2π (M r )δ 0 + δ n .
Rounding the answer We now compute the parameter R in ( 6). The rounding is made in the Cartesian coordinates, hence the inverse image of any returned value is a square S of length L. Note that S δ t is included in the square of length L + 2δ t and S -δ t is a square of length L -2δ t . Hence the ratio value is smaller than R = (

Conclusion and future work

In this paper we have shown that, in any implementation of mechanisms for differential privacy, the finite precision representation of numbers in any machine induces approximation errors that cause the loss of the privacy property. To solve this problem, we have proposed a method based on rounding the answer and raising an exception when the result is outside some values. The main result of our paper is that the above method is sound in the sense that it preserves differential privacy at the price of a degradation of the privacy degree. To prove this result, we needed to pay special attention at expressing the problem in terms of probability theory and at defining the link between computational error and distance between probability distributions. Finally, we have shown how to apply our method to the case of the linear Laplacian and to that of bivariate Laplacian.

As future developments of this work, we envisage two main lines of research:

• Deepening the study of the implementation error in differential privacy: there are several directions that seem interesting to pursue, including:

-Improving the mechanisms for generating basic random variables. For instance, when generating a one-dimensional random variable, it may have some advantage to pick more values from the uniform random generator, instead than just one (we recall that the standard method is to draw one uniformly distributed value in ]0, 1] and then apply the inverse of the cumulative function). For instance, u 1 + u 2 has a density function with a triangular shape and cost only one addition. The other advantage is due to the finite representation: if the uniform random generator can pick N different values then two calls of it generate N 2 possibilities, which enlarge considerably the number of possibilities, and therefore reduce the "holes" in the distribution.

-Considering more relaxed versions of differential privacy, for instance the (ε, δ )-differential privacy allows for a (small) additive shift δ between the two likelihoods in Definition 3.1 and it is therefore more tolerant to the implementation error. It would be worth investigating for what values of δ (if any) the standard implementation of differential privacy is safe.

• Enlarging the scope of this study to the more general area of quantitative information flow. There are various notions of information leakage that have been considered in the computer security literature; the one considered in differential privacy is just one particular case. Without the pretense of being exhaustive, we mention the information-theoretic approaches based on Shannon entropy [START_REF] Clark | Quantified interference for a while language[END_REF][START_REF] Malacaria | Assessing security threats of looping constructs[END_REF][START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] and those based on Rényi min-entropy [START_REF] Smith | On the foundations of quantitative information flow[END_REF][START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] and the more recent approach based on decision theory [START_REF] Mário | Measuring information leakage using generalized gain functions[END_REF]. The main difference between differential privacy and these other notions of leakage is that in the former any violation of the bound in the likelihood ratio is considered catastrophic, while the latter focuses on the average amount of leakage, and it is therefore less sensitive to the individual violations. However, even though the problem of the implementation error may be attenuated in general by the averaging, we expect that there are cases in which it may still represent a serious problem.

Definition 2 . 7 (

 27 Laplace distribution). The density function F of a Laplace distribution with scale parameter b is F b (x) = K(b)e -b x where K(b) is a normalization factor which is determined by imposing S F b (x) dx = 1. Definition 2.8 (Joint probability). Let (X,Y ) be a pair of random variable on R m . The joint probability on (X,Y ) is defined for all I, J ∈ S as: P

Theorem 4 . 1 (

 41 [START_REF] Gazeau | A non-local method for robustness analysis of floating point programs[END_REF]). If n is k-Lipschitz and nn ′ ∞ ≤ δ then n and n ′ are (k, δ )-close.

Theorem 4 . 2 .

 42 If there exist u, v, d(n(u), n(v)) > kd(u, v) + 2δ then there exist no function n ′ such that n and n ′ are (k, δ )-close.Proof Let u, v such that d(n(u), n(v)) > kd(u, v) + 2δ .Let n ′ such that n and n ′ are (k, δ )-close. From the definition of closeness, we get d(n(u), n ′ (u)) ≤ δ and d(n ′ (u), n(v)) ≤ kd(u, v) + δ . From a triangular inequality, we derive

Following [ 2 ]

 2 , we compute the random variable by drawing an angle and a distance independently. The angle θ is uniformly distributed in [-π, π[. The radius r has a probability density D ε,R (r) = ε 2 re -εr and cumulative function C ε (r) = 1 -(1 + εr)e -εr . The radius can therefore be drawn by setting r = C -1 ε (u) where u is generated uniformly in ]0, 1].Robustness of n As in the previous section, we do not analyze an actual implementation but we care about the k factor used for Condition 3. First, we analyze for which k

  L+2δ t L-2δ t ) 2 .Differential privacy By Theorem 5.1 we get that (the implementation of) our mechanism is ε ′ -differentially private with

	ε ′ = ε + ln(1 + (	L + 2δ t L -2δ t	) 2 e

ε L+δ t ∆ f ′ )

The name "oblivious" comes from the fact that the final answer depends only on the answer to the query and not on the dataset.

More precisely, the problem is caused by scaling a finite set of randomly generated numbers. It is easy to prove that the problem raises for any implementation of numbers, although it may not raise for every point like in the case of the fixed-point representation.

We discovered our attack independently, but[START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF] was published first.

* This work has been partially supported by the projects ANR-09-BLAN-0345-02 CPP and ANR-12-IS02-001 PACE, by the INRIA Action d'Envergure CAPPRIS, and by the European Union Seventh Framework Programme under grant agreement no. 295261 (MEALS).

Preserving differential privacy Definition 4.4 (∞-Wassertein distance). Let µ, ν two probability measures on (R m , S ) such that there exist a compact Ω, µ(Ω) = ν(Ω) = 1, the ∞-Wassertein distance between µ and ν is defined as follows:

Where Γ(µ, ν) denotes the collection of all measure on M × M with marginals µ and ν respectively.

If we denote by Supp(x, y), the support where γ(x, y) is non zero, we have an equivalent definition [START_REF] Champion | The ∞-wasserstein distance: Local solutions and existence of optimal transport maps[END_REF] for the ∞-Wassertein distance:

We extend this definition to any pair of measures that differ only on a compact (M r in our case) by considering the subset of Γ(µ, ν) containing only measure γ(x, y) with γ(x, y) = 0 if x = y and either x ∈ M c r or y ∈ M c r . We have introduced this measure because it has a direct link with the computational error as expressed by the following theorem.

Theorem 4.3. Let X and X ′ be two random variables with distribution µ and ν respectively. We have that X -

The marginals of γ are µ and ν. Moreover, the support of γ is δ since P(X ∈ A ∧ X ′ ∈ B) = 0 when A and B are distant by more than δ . Since we have such a γ the minimum on all the γ ∈ Γ(µ, ν) is less than δ .

In our case, according to (4), we have d(µ, ν) ≤ δ t . The following theorem allow us to bound the µ measure of some set with the measure ν.

Proof The property of marginals is ν(S) = R m ×S dγ(x, y). Since γ(x, y) = 0 if d(x, y) > ε, we derive ν(S) = S ε ×S dγ(x, y). Then we get ν(S) ≤ S ε ×R m dγ(x, y). The last expression is the marginal of γ in S ε , hence by definition of marginal: ν(S) ≤ µ(S ε ). The other inequality is obtain by considering the complement set of S (R m \ S).

Rounding the answer

Once the computation of A (D) is achieved, we cannot yet return the answer, because it could still leak some information. Indeed, the distribution of X and X ′ are globally the same, but, on a very small scale, the distributions could differ a lot. We prevent this problem by rounding the result:

Mechanism 3. The mechanism rounds the result by returning the value closest to f (D) + n ′ in some discrete subset S ′ . So K (D) = r(A (D)) where r is the rounding function.

From the above rounding function we define the set S ′ 0 of all sets that have the same image under r. Then we define the σ -algebra S ′ generated by S ′ 0 : it is the closure under union of all these sets. Observe now that it is not possible for the user to measure the probability that the answer belongs to a set which is not in S ′ . Hence our differential privacy property becomes: ∀S ∈ S ′ , P[A (D 1 ) ∈ S] ≤ e ε P[A (D 2 ) ∈ S]

(5)