Thomas Trouchkine
email: thomas.trouchkine@ssi.gouv.fr

Kevin K Sébanjila

Mathieu Bukasa

Ronan Escouteloup

Guillaume Lashermes

Bouffard

• Sébanjila

Kevin Bukasa

Mathieu Escouteloup

Ronan Lashermes

Guillaume Bouffard
email: guillaume.bouffard@ens.fr

S K Bukasa

Electromagnetic fault injection

Keywords: Physical attacks, Fault models, Electromagnetic Fault Injection (EMFI), System-on-Chip (SoC)

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Sensitive operations are usually performed on secureoriented devices such as smartcards. These kinds of devices are hardened microcontroller units (MCUs) designed to be tamper resistant against hardware and software attacks. They are evaluated under a scheme, e.g. Common Criteria, to ensure a high security level. Smartcards are the most studied secure-oriented devices.

Recently, sensitive operations are increasingly performed on more powerful and complex devices: the systemon-chips (SoCs). These SoCs are powered by central processing units (CPUs) with a complex micro-architecture including memory virtualization, several cache levels, speculative or out-of-order execution.

To behave correctly, components have to fulfill physical constraints. These constraints are directly linked to their design and, if they are respected in their nominal operation point, it is possible to break these constraints conditions by inducing stimuli in the component as presented in Figure 1.

When a stimuli perturbs the component, it is pushed to its operation limit. Therefore, faults can be induced. Among all the fault injection methods, electromagnetic fault injection (EMFI) has been demonstrated to be effective on the complex CPUs with a minimal effort on target preparation [START_REF] Cui | BADFET: Defeating Modern Secure Boot Using Second-Order Pulsed Electromagnetic Fault Injection[END_REF] and without chip alteration.

Complex CPUs are tuned for the best performance/energy consumption trade-off and are focused on software hardening. However, hardware security is not the main Fig. 1: Stimuli able to perturb a component concern and past works [START_REF] Cui | BADFET: Defeating Modern Secure Boot Using Second-Order Pulsed Electromagnetic Fault Injection[END_REF][START_REF] Kocher | Spectre attacks: Exploiting speculative execution[END_REF][START_REF] Lipp | Meltdown: Reading kernel memory from user space[END_REF][START_REF] Tang | CLKSCREW: exposing the perils of securityoblivious energy management[END_REF][START_REF] Timmers | Escalating privileges in linux using voltage fault injection[END_REF][START_REF] Timmers | Controlling PC on ARM using fault injection[END_REF][START_REF] Vasselle | Laser-induced fault injection on smartphone bypassing the secure boot[END_REF] have shown that physical attacks are effective against them.

These articles demonstrate the need for hardening complex CPUs against fault attacks. To achieve that goal, we first need to understand the effects of such faults on the micro-architecture.

To model the fault effects, literature [START_REF] Balasch | An in-depth and black-box characterization of the effects of clock glitches on 8-bit mcus. In 2011 Workshop on Fault Diagnosis and Tolerance in Cryptography[END_REF][START_REF] Bar-El | The sorcerer's apprentice guide to fault attacks[END_REF][START_REF] Dureuil | From code review to fault injection attacks: Filling the gap using fault model inference[END_REF][START_REF] Moro | Electromagnetic fault injection: Towards a fault model on a 32-bit microcontroller[END_REF][START_REF] Rivière | High precision fault injections on the instruction cache of armv7-m architectures[END_REF][START_REF] Verbauwhede | The fault attack jungle -A classification model to guide you[END_REF][START_REF] Yuce | Fault attacks on secure embedded software: Threats, design, and evaluation[END_REF] covers mostly a simple component: the MCU. The MCU is cheaper and smaller than a complex CPU without advanced micro-architectural components. Their works improve the hardware security of MCU and a lot of introduced countermeasures are embedded in smartcards. However, the obtained fault model cannot be scaled up on complex CPUs embedded in SoCs due to the latter's hardware complexity.

Some recent papers [START_REF] Proy | A first isa-level characterization of em pulse effects on superscalar microarchitectures -a secure software perspective[END_REF][START_REF] Trouchkine | Fault Injection Characterization on modern CPUs -From the ISA to the Micro-Architecture[END_REF] have proposed fault characterizations on complex CPUs. However, since they use a device running a complex operating system (OS), their analysis cannot precisely infer the impact on microarchitectural elements.

In this work, we propose instead to run our opensource characterization software 1 as a bare-metal application for the Raspberry Pi 3 B (RPi3)'s CPU embedded in the BCM2837 SoC. This implementation allows us to have control of software/hardware interactions. Therefore, we can realize a finer grained characterization on several micro-architectural components. To fault the BCM2837 CPU, we first make EMFI and we next use a forensic process based on JTAG debug port to understand fault effects.

In this article, we highlight several new fault effects at the micro-architectural level, in particular in the memory hierarchy. This article is organized as follows. The BCM2837 is described in section 2. On its complex CPU, we run a nested for loop and we vary the injection delay. The experimentation modus operandi is explained in section 3.

Regarding this experimentation, we observed faults on different micro-architecture blocks:

on the L1 instruction cache where we achieve a persistent fault in the L1 instruction cache as described in section 4, -on the memory management unit (MMU); we confuse the virtual-to physical memory mapping. This fault is introduced in section 5, -on the L2 cache; we also achieve a persistent fault in the L2 cache demonstrated in section 6.

A fault exploitation demonstration is given in section 7 with a persistent fault in the L1 data cache, where an AES cryptographic key is recovered with one fault injection and 2 24 hypotheses.

We finish with propositions to protect complex CPUs against these attacks in section 8. Section 9 puts our work in the state of the art and we conclude in section 10.

BCM2837 description

The RPi3 is a low-cost single-board computer. It features a complete system able to run a complex OS such as Linux or Windows and their applications. The SoC powering this board is the BCM2837 from Broadcom, a 28 nm quad-core Cortex-A53 CPU running at 1.2 GHz with the help of a dual-core VideoCore IV GPU at 400 MHz. This SoC also features 512 kB of cache memory and various wireless or contact connections such as HDMI, Wi-Fi, ethernet, USB, etc.

Our experiments are performed with our own software stack, with only one core active. Indeed, even if we tested EMFI with several cores enabled, it is hard to pinpoint the exact effect on the micro-architecture in this configuration since we cannot easily link a fault in unified memory with a particular core. Therefore, to increase our confidence in our characterization, we enable only one core.

To control the chip's behavior, we have implemented the minimum to run our applications: initialization of JTAG, UART, GPIO, CPU caches and MMU. We want to stress out that no complex OS is running during our experiments in sections 4, 5, 6 and 7, to avoid interference that could hinder our ability to infer more precise fault models. In particular, we try to avoid the context switching effects due to preemptive scheduling by the OS, the error recovery mechanisms (if an error occurs, we want to know it) and the cache maintenance performed by the OS.

In order to later explain the causes of the failures observed, we describe in more details two important micro-architecture blocks of this complex CPU: the cache hierarchy and the MMU.

Cache hierarchy

In modern systems, memory accesses are a lot slower than the arithmetic logic unit (ALU). To avoid losing too much performance to this latency difference, small and fast memories called caches are used to mirror a part of the memory space.

First, in the targeted CPU, each core has two L1 caches (the smallest and fastest kind), one dedicated to instructions (L1I), one to data (L1D). These caches are 16 kB in size with 64 B line width.

Second, the second layer of cache memory, the L2 cache, is common to all cores and thus provides a unified view of the memory space. Its size is 512 kB with 64 B line width.

The cache organization is displayed in Figure 2. The bus sizes between memory elements are given in Table 1 Fig. 2: BCM2837 memory hierarchy. The MMU is a central component for all multi-application systems. It aims to virtualize the physical memory of the system into a virtual one to segregate each app in their own address space. Therefore, the CPU only works with virtual addresses, and during a memory access to one of them, the MMU translates it into the corresponding physical address, which is transmitted to the memory controller. The information required for the translation of an address is called a page table entry (PTE), and it is stored in the physical memory and cached in the translation lookaside buffer (TLB). There is a PTE for all allocated pages in the physical memory. Our bare-metal implementation allocates the whole address space with an identity mapping (virtual and physical addresses are the same) with 64 kB pages.

In modern systems, the translation phase does not only compute the physical address but also realizes different checks. These checks are monitoring if the page can be written or not, which kind of process (user or supervisor) can access it or should the page be stored in cache or not.

Among all its roles, the MMU is also a security mechanism. Ensuring that a read-only page cannot be written to and ensuring that only authorized processes can access their corresponding pages. This last security mechanism is the memory partitioning. On multiapplication systems, it avoids a process to spy or corrupt the memory area used by another one.

In complex OSs, the MMU and the PTEs are critical assets set up by the kernel.

Experimental process methodology

In this section, we introduce our benchmark to characterize the fault model and which micro-architecture blocks are faulted.

Electromagnetic fault injection bench

Some apparatus are required in order to inject faults into the BCM2837. Our experimental setup has been designed to be highly configurable and to operate at higher frequencies than most setups targeting microcontrollers. First, we use a Keysight 33509B (waveform generator) to control the delay between a trigger issued by the RPi3 board before the instructions of interest. Second, a Keysight 81160A generates the signal shape for the EM injection: one sinus period. A sinus is used instead of the usual pulse since it gives fewer harmonics at the output of the signal generation chain. Third, this signal is amplified with a Milmega 80RF1000-175 (80 MHz -1 GHz bandwidth). Finally, the high-power signal is connected to a Langer RF U 5-2 near-field probe, in contact with the packaged chip. A part of this electromagnetic energy is, therefore, transmitted in the chip's metal lines, which can lead to a fault.

The minimum latency between the initial trigger and the faulting signal reaching the target is high: around 700 ns. As a consequence, the targeted application must run enough time to be reachable by our fault injection bench.

Bench parameters

To properly inject a fault, the experimenter must tune several parameters, namely the 1) injection signal, 2) the probe spatial location, and 3) temporal synchronization.

Fault effects are reproducible with a low ratio; meaning that if a fault has been achieved, it will be achieved again with the same parameters but only for a small ratio of the fault injections. In other cases, no failure occurs, or another effect is observed (mostly due to jitter). Unfortunately, we are not able to measure the fault ratio. Indeed a manual forensic analysis must be performed in order to establish the cause for a fault. Since this step is not automated, it is too time consuming to measure a fault ratio.

Injection signal. The signal parameters (shape, frequency, number of periods) have an optimal value with respect to our requirements:

-The shape is a sinus to reduce the presence of harmonics in the amplification chain. -The frequency (275 MHz) maximizes the probe gain as measured in the probe characterization phase. As a consequence the sinus period is 3.6 ns, or ≈ 4.3 clock periods. -The amplitude (-14 dBm) has been manually tuned during the fault injection until the desired effect is achieved: if too low, no faults are observed; if too high, the chip crashes and must be rebooted.

Probe spatial location. A sensitivity map has been made to find the sensitive places on the chip. By setting a high signal amplitude, we repeatedly try to inject a fault in every possible place on the chip. Next, we observe where the faults (the tested application, Listing 1, returns an incorrect result or no result at all) are obtained. The result, shown in Figure 3, clearly indicates an area of interest. For all experiments below, the probe is placed at the most sensitive location (X = 4 mm, Y = 4.5 mm on Figure 3).

Temporal synchronization. The main difficulty for fault injection is the temporal synchronization: when to inject a fault on the targeted and vulnerable instructions.

We first need a temporal reference, given here by a GPIO: a rising electrical edge is sent to a board pin by our application just before the area of interest. This signal is used by our apparatus to trigger the fault injection.

Our setup is using the evaluator approach: the attacker can instrument the system to ease the experiments. In the case of a real attack, the adversary would have to generate this trigger signal: it can be done by monitoring communications, IOs, or EM radiation to detect patterns of interest. In all cases, it is a tricky business, highly application dependent.

The trigger signal is just part of the problem: from that moment on, we must wait the correct duration to inject the fault. In other words, we want to control the injection time relatively to the trigger signal, in order to inject a fault when processing the targeted instruction. Propagation times are not negligible. On a complex CPU, the issue is more difficult due to the memory hierarchy. Since cache misses are highly unpredictable, they imply a corresponding jitter. It is difficult to predict the duration of memory access accurately and therefore, the waiting time to inject the fault.

Synchronization is a problem, but not an obstacle at this point. Indeed, the attacker only has to inject faults until the correct effect is achieved. Because of the jitter, for the same delay (time expected between the trigger and fault injection), different timings are tested with respect to the running program. For the same bench timing parameters, we will inject a fault during a different instruction at each execution, but a different one among a small set of instructions, depending on the jitter. If a fault with an interesting effect is possible, it is eventually achieved.

Additionally, as we will see in the next sections, memory transfers are particularly vulnerable to EMFI. They are also slower than the core pipeline, allowing for a bigger fault injection timing window.

Forensic methodology

Contrary to the state-of-the-art fault model characterization on complex CPUs, we target a bare-metal system, meaning that no complex OS, to characterize the effect of a fault in the micro-architecture. Removing the complex OS aims at improving the fault effect characterization with a better granularity by accessing to low-level micro-architecture blocks and instrumenting them.

As the targeted component is closed, we do not have any insider information and no way to analyse the hardware layout. Therefore, we can only characterize a fault from the instruction set architecture (ISA). Moreover, we have also limited means to explore what is happening in the system, mainly the JTAG. With it, we are able to halt the chip execution to read or write the register values and to read and write memory as seen by a particular core (with a data viewpoint).

Therefore, to pinpoint the particular effects of a fault injection, we force the system state such that an observable change gives us information on the fault mechanism. In particular, we have put several cache invalidation instructions in memory. During our forensic process, we can therefore call them by modifying the program counter (PC) by writing directly to it with the JTAG.

A technique used to detect the fault location is to execute the suspected instructions step-by-step (with the JTAG), and the verify the side effects after each instruction (by reading memory and registers).

Our software footprint has to be minimal to maintain controllability on the system state. As such, we will not describe how to breach a particular system with our faults since any exploit is highly applicationdependent, and our setup is not representative of a standard application environment. Instead, we will suggest exploit strategies: how a malicious attacker could use such faults?

A demonstration of a fault exploitation, given in section 7, is done on our own AES encryption implementation. However, those results cannot be extrapolated to any real-world application.

Characterization modus operandi

The application targeted during this experiment is two nested loops shown on Listing 1. This program is built without compiler optimizations. We set the compiler optimization level at -O0 to have better debuggable code and correspondence between C-code and generated assembly. Moreover, -O0 increases the number of memory accesses. This behavior helps us to analyse them against fault attacks. Before running the nested for loop, we invalidate the CPU caches (line 3) to detect modifications. Our bench has a latency of 700 ns, so we can still hit this memory transfer. To be able to observe the effect of a fault on the full-timing range, a 1 µs (line 2) wait has been inserted between the trigger and the cache invalidation. Moreover, a MMU is enabled to be closer to market deployed applications.

A fault occurs when the cnt variable value at the end of the program is not equal to 2500 or if the program crash. When a fault is detected, we use the JTAG to re-execute our for loop, in the Listing 1, by directly setting the PC value at the start of the loops. Executing instruction by instruction, we monitor the expected side effects. This execution is done without fault injection.

Based on this code, we vary the injection delay. Varying the injection delay confuses different microarchitecture blocks: L1 and L2 caches and the MMU. The L1 and L2 caches are confused at 3134 ns and the MMU is targeted at 25 400 ns.

With this setup, we disclose different fault models with EM fault injection on L1I cache, on MMU and on L2 cache.

Fault on the instruction cache

In this experiment, we achieve a fault in the L1 instruction cache (L1I).

On the impossibility to fault the instruction execution flow

Before reporting our positive results, we must report a negative one. Contrary to previous works on microcontrollers (where, e.g. instructions are replaced with a NOP instruction), we are not able to prevent or modify the execution of an instruction directly. Even if we cannot be sure that no set of experimental parameters would achieve such a fault, we thoroughly explored the parameters without success.

Instead, we get faults during cache transfers, which is probably because the buses involved in these transfers are easily coupled with our EM probe. In the case of a minimal application that can fit in the cache, the memories are filled only once at the first execution. As a consequence, to repeatedly observe our fault, we invalidate the cache memory of interest (L1I) just before launching our application, artificially triggering a memory transfer.

Forensic

As the instruction cache is invalidated before the loop of the Listing 1 is executed, the following instructions must be (re)loaded into the cache before execution. Moreover, it is this memory transfer that we target with our fault injection. By executing the same application with and without the cache invalidation and measuring the duration of the high state of the trigger, we deduce that loading instructions in the cache has an overhead of 2 µs.

To analyze the fault, we debug, without fault and step by step, the for loop through the JTAG interface. Each instruction was correctly executed except for the add instruction, in red, at address 0x48a08 on Listing 2. By monitoring the x0 register before and after the cnt incrementing instruction, in red in the Listing 2, we observe that the value is kept unchanged: the increment is not executed. Since the fault is still present after the EM injection, we can conclude that a wrong instruction value is stored in L1I. We confirm this fault model by executing an L1I cache invalidation instruction ic iallu 2 . By re-executing our application, the fault has disappeared.

We can infer that the injected fault has affected a part of the L1I cache. However, it is impossible to access (read) the new instruction value. Since the fault happens during the cache filling, we can suppose that the memory transfer had been altered.

Moreover, this fault model matches the observation made by Trouchkine et al. in [START_REF] Trouchkine | Fault Injection Characterization on modern CPUs -From the ISA to the Micro-Architecture[END_REF]. In this work, the authors characterize a fault model while perturbing a BCM2837 using EMFI. The model they observe is the corruption of the executed instruction second operand, which is forced to 0. This ISA fault model matches the one we observe in the cache as the corruption of the instruction add x0, x0, #0x1 by forcing the second operand to 0 gives the instruction add x0, x0, #0x0 which explains why the increment is not executed as we add 0 to the register. They identify that their faults happen during the instruction fetch. However, as they work with an OS, they cannot reliably test if the fault they observe is persistent in the cache, while we can with our bare-metal setup.

Exploits

This fault is one of the easiest to exploit since it induces an instruction replacement fault model, where an instruction is replaced by another. It can often be reduced to the classical instruction skip model, if the new instruction has no side effects on the application. Therefore, most exploits based on this classical model apply here. Since the faulted value is still present in the cache, it will stay faulted until the cache is invalidated: we can call this model "sticky instruction skip". Bukasa et al. [START_REF] Bukasa | Let's shock our iot's heart: Armv7-m under (fault) attacks[END_REF] demonstrated applications of this fault model: hijacking the control flow and initiating a return-oriented programing (ROP) attack, among others.

Targeting the memory management unit

The MMU is a critical component of the complex CPUs. It is in charge of the virtual memory mechanism and ensure memory partitioning between applications. In this section, the fault corrupts the virtual-to-physical memory mapping albeit in an uncontrolled manner. The targeted application is the same as in section 4, shown in Listing 1; only the fault injection timing has changed. We inject the fault at 25 400 ns after the trigger instead of 3144 ns when the L1I is confused. The faults, analyzed in this section, always crash the program in Listing 1.

We show in this section that this delay enables to perturb the MMU micro-architectural block. Regarding the results from the other characterization works in this paper, the cache hierarchy is the most sensitive CPU micro-architectural block.

Configuration of a working MMU

To understand the fault effect on the MMU, we begin to explore the state of an application without any fault. This state is a legitimate one.

Page tables

The page tables are used to memorize the mapping between virtual and physical memory. In our configuration, we have 3-page table directory (PTD) (mapping 512 MB chunks), and for each of them, we have 8 192 PTE pages of 64 kB.

In the page tables, the most and least significant bits are used for the page metadata (access rights, caches configuration, etc.).

Translation lookaside buffer

TLBs (plural since there are several of them) are small buffers used to speed up virtual-to-physical memory translation. As in a cache memory, the last mappings are saved from being reused later without a full-page walk by the MMU. In the targeted CPU, TLB hierarchy mirrors cache hierarchy: the TLB designates the unified Level2 buffer while micro-TLBs are dedicated to instructions or data in each core.

Operating system

In our bare-metal application, all the pages are initialized in the page tables with an identity mapping (virtual and physical addresses are identical). In a system with an OS, pages are allocated on-the-fly. On the one hand, this simplifies the forensic analysis since we are sure that page tables are correct prior to the fault. On the other hand, interesting faults may be missed if the OS page allocation is disrupted.

Forensic

To reconstruct the memory mapping, we use a pair of instructions computing the physical address (and the corresponding metadata) for a given virtual one. A script has been designed to extract the memory mapping. By using the JTAG, first, the two instructions at s1e3r, x0 and mrs x0, PAREL1 are written at a given address, then the x0 register is set to one virtual address, the two instructions are executed, and finally, the x0 register contains the corresponding physical address.

With this method, we compare the memory mappings with (Table 3) and without (Table 2) a fault.

Virtual Address Physical Address

Virtual Address Physical Address 0x0 0x0 0x80000 0x80000 0x10000 0x10000 0x90000 0x90000 0x20000 0x20000 0xa0000 0xa0000 0x30000 0x30000 0xb0000 0xb0000 0x40000 0x40000 0xc0000 0xc0000 0x50000 0x50000 0xd0000 0xd0000 0x60000 0x60000 0xe0000 0xe0000 0x70000 0x70000 0xf0000 0xf0000 Virtual Address Physical Address 0x0 0x0 0x80000 0x0 0x10000 0x10000 0x90000 0x0 0x20000 0x20000 0xa0000 0x0 0x30000 0x30000 0xb0000 0x0 0x40000 0x40000 0xc0000 0x80000 0x50000 0x50000 0xd0000 0x90000 0x60000 0x60000 0xe0000 0xa0000 0x70000 0x70000 0xf0000 0xb0000

Table 3: Mapping after fault Three different effects can be observed depending on the page:

1. Pages are correct with an identity mapping up to 0x70000. Remarkably, these are all the pages used to map our application in memory. Therefore, a hypothesis is that the corresponding translations are present in caches and are not impacted by the fault (in green in Table 3).

2. Pages are incorrectly mapped to 0x0. For instance, a read at 0x80000 reads, with success, physical memory at 0x0 (in blue in Table 3). 3. Pages are shifted. For example, a read at 0xc0000

gives the physical memory value at 0x80000 (in red in Table 3).

If we invalidate the TLB after a fault, nothing changes: the mapping is still modified. We conclude that the fault does not affect the cache mechanism to address translation (at least what can be invalidated by software) but directly the MMU configuration.

The fault on the MMU shifts the page tables in memory and inserts errors on it. The tables are still present, with small modifications, but at another base address.

Since the memory translation is still valid after the fault (translations are considered valid by the CPU), and do not correspond to the shifted page tables (we can reconstruct the virtual to physical mapping from the new page tables), this shift is not the only source of incorrect translation. Finally, we do not have enough control over the CPU to observe the failure cause with precision.

Exploit

This fault shows that the cornerstone of the key security feature in any CPU, namely memory isolation, does not withstand fault injection. In [START_REF] Van Der Veen | Drammer: Deterministic rowhammer attacks on mobile platforms[END_REF], the authors use the Rowhammer attack to fault a PTE. The faulted PTE accesses the kernel memory, which allows the attacker to obtain a privilege escalation: by overwriting a userland PTE for accessing all the memory, by changing the user ID to root or by changing the entry point of an executable.

Additionally, this fault model is a threat to pointer authentication countermeasures, as proposed in the recent ARMv8.3 ISA. This pointer protection mechanism works by storing authentication metadata in the most significant bits (usually useless) of a pointer value. The chip first validates the authentication metadata in order to use a pointer. In our case, the attacker does not need to alter the pointer value; it can alter where it physically points to, at a coarse (page) granularity.

Shifting data chunks in L2

We showed that the attacker could inject faults in the L1I cache and the MMU. In this section, we will demonstrate that another cache memory can be targeted: the L2 cache.

Another interesting behavior when faulting a modified version of the loop target, c.f. Listing 3, was investigated with JTAG.

The initial goal was to try to modify register values to see if we could confirm the fault model as in [START_REF] Trouchkine | Fault Injection Characterization on modern CPUs -From the ISA to the Micro-Architecture[END_REF]. Instead, we observed an original behavior described in this section. Inside each loop iteration, we call a function, register_transfer, that self copies all registers (e.g., mov x1, x1). init_registers fills registers x0 to x7 with constants (9 instructions with the ret).

Listing 3: Assembly for the modified loop target, the framed instructions have been added with respect to Listing 2. We also show the instructions just before in our function. The pulse parameters are strictly identical to the ones used for injecting a fault on L1I (in particular, we have the same delay of 3144 ns). But the different observed behaviors may be explained by the modification of the program under test (framed instructions in Listing 3). This modification has, in our opinion, no effect on the fault due to the functionality, but instead because it modifies the cache timings.

We show in this section that data are shifted in the L2 cache as if addresses had been slightly modified in the transfer from RAM to L2.

Forensic

Cache coherency methodology

The difficulty to identify the presence of a fault in the cache L2 is that we cannot observe it. Instead, we will locate the fault indirectly by testing the coherency of the L1I, L1D and L2 caches with the methods illustrated in Figures 4, 5 and6.

First, to check the coherency of L1D and L1I, we use the JTAG as illustrated on Figure 4. We compare the instructions read from L1D with the JTAG with the ones executed (fetched from L1I) by checking on their side effects, one instruction at a time. Fetch on 2 nd read Fig. 5: Method for testing cache coherency between L1D and L2 using JTAG Finally, it is also possible to force a new fetch from L2 after invalidating L1I (cf. Figure 6). We compare the executions before and after this new fetch by executing instructions step-by-step.

Incoherent cache fault

With the same injection parameters as in section 5, we can achieve a new reproducible faulted behavior where the chip is trapped in an infinite loop, as seen with a step-by-step execution. However, when we repeat A JTAG memory dump (from L1D point of view) at the instruction memory location for CoherentState shows modified instructions as seen on Listing 4a, to be compared to the unfaulted dump on Listing 4b.

The dump for IncoherentState shows different values in L1D memory with respect to CoherentState (for the first two instructions), as seen on the Listing 5.

Listing 5: Memory dump showing the instructions in the infinite loop as seen by the JTAG (L1D point of view) for IncoherentState.

0x000489f8: 940087c1 b94017a0 11000400 b90017a0 0x00048a08: b9401ba0 11000400 b9001ba0 b9401ba0 0x00048a18: 7100c41f 54fffeed b9401fa0 11000400 0x00048a28: b9001fa0 b9401fa0 7100c41f 54fffded

The step-by-step execution is coherent with the instructions shown by the JTAG dump for CoherentState (registers are loaded, stored and incremented as specified in this dump), which means that L1I and L1D are identically faulted. Therefore, we can suppose that the fault is present in the L2 cache (the first unified cache). The reconstructed instructions can be seen in Listing 6.

Listing 6: Assembly reconstruction of the faulted instructions from the Listing 4a. Listing 4: Comparison of the memory dumps with and without fault.

It is impossible to observe the L2 cache content, we must therefore confirm our hypothesis with additional indirect evidence, using our methodology introduced in section 6.1.1.

L1 fault. The L1I is modified by the fault since the behavior of the application is modified. However, the execution is coherent with the JTAG dump (showing the L1D cache) for CoherentState, hinting that L2 is impacted too.

In this case, if we invalidate the whole L1I cache (with ic iallu instruction), as illustrated on Figure 6, nothing changes (either in the execution trace or in the JTAG dump).

For IncoherentState, 940087c1 (first brown instruction in Listing 5) encodes a direct unconditional jump (bl) instruction that is not followed in the stepby-step execution. Therefore, in this case the JTAG dump (corresponding to data in L1D) does not reflect the values in the L1I cache. However, if we invalidate a cache line of L1D at address 0x489f8 (with dc ivac instruction), as illustrated on Figure 5, then L1D is modified, as seen with JTAG, and becomes the same as for CoherentState. Therefore, the L1D data seen in CoherentState is present in L2.

However, to the best of our knowledge, it is not possible to directly invalidate the L2 cache to directly confirm our hypothesis. memory management unit. A possibility that would explain coherent faults in L1D and L1I but not L2 is a modification of the memory mapping if the fault impacted the MMU.

After verification as in section 5, we observe that the MMU mapping is indeed modified but not for the memory region of interest. In particular, memory addresses from 0x0 to 0x7FFFF are still correctly mapping identically virtual and physical addresses. The fault on the MMU cannot, therefore, explain our observations.

Hypotheses. The effect of these faults seems to manifest itself in the L2 cache. We can observe that it consists in shifting groups of 4 instructions (128 bits or 16 B, under the cache line size of 64 B) at a nearby memory location. 128-bit is the size of the external memory bus connected to L2. The fault model could be that the address corresponding to a cache transfer toward L2 has been modified by a few bits.

Our model has some limits: with one fault, values in L2 and in L1D are modified simultaneously in an incoherent way for IncoherentState. Is it due to the EM probe coupling with several buses or to a microarchitectural mechanism?

Exploits

A fault in the L2 cache can impact either the instructions or the data giving more power to the attacker. Nevertheless, she does not control in what way the memory will be modified. Why have these particular 16byte blocks been shifted? Nevertheless, just corrupting data or instruction randomly is often enough to achieve the desired effect (as in the NOP fault model).

When persistent fault analysis meets L1D cache

To demonstrate the applicability of a cache memory fault model, a persistent fault analysis (PFA) [START_REF] Zhang | Persistent fault analysis on block ciphers[END_REF] is performed on a bare-metal AES implementation. In this section, we show how to reduce the AES key to 2 24 possibilities instead of 2 128 , with one persistent fault in L1D.

Setup

With the same experimental setup as before, we now target an AES encryption. Our AES implementation is a naive one without countermeasures. The sboxes are implemented with a lookup table. Before the actual encryption, we pre-warm the cipher: in order to limit timing leakages due to caches, we first invalidate L1I and L1D. Then we perform a dummy AES encryption to fill the caches with data and instructions of interest. This is the step where we inject the fault.

In a second step, we encrypt 10 000 random plaintexts, without any new fault injection, and try to deduce the key from the observed (faulty) ciphertexts.

Persistent fault analysis: the theory

We target the sbox lookup table: by modifying at least one bit in the table, the operation is now biased. For example, for the input x, the output is now

y * = SB * (x), (1)
instead of y = SB(x). Since a sbox is a bijection, now y cannot be outputted by SB * , the faulted sbox. We say that y is forbidden. At the last round of the AES encryption, for each byte index i ∈ [[0, 15]], we have

SB * (x i ) ⊕ K10 i = C * i , (2)
where x is an intermediate state, K10 the last round key and C * the faulty ciphertext. We consider, as an approximation, that the distribution of x i is uniform for all i.

Since y is a forbidden value, y ⊕ K10 i cannot be observed as a result for any C * i and this for all byte index i ∈ [[0, [START_REF] Rivière | High precision fault injections on the instruction cache of armv7-m architectures[END_REF]]. We note C 0 i the forbidden value for the corresponding ciphertext at byte index i. The attacker can easily observe C 0 i , it is enough to count the occurrences of the byte values and find the specific one that never occurs.

While we try to guess for the forbidden value y (2 8 possibilities), we can compute:

∀i, K10 i = C 0 i ⊕ y. (3)
From there, the master key is trivially recovered from K10, and a known pair with a plaintext and the corresponding correct ciphertext allows the attacker to validate the correct guess.

Results

In order to detect the forbidden values, we simply count the number of occurrences for all bytes values in the ciphertext, for the first byte, then the second byte, etc.

On Figure 7, we can observe that 2-byte values are forbidden. Therefore, in our case, two bytes have been faulted in the sbox lookup table. The analysis has to be adapted to the two faults case. For each byte index from 0 to 15, we get the two ciphertext forbidden values, as shown in Table 4 7.

Since we have 2 forbidden values y 1 and y 2 , we need to create 2 24 hypotheses to recover the key. First, we have 2 8 guesses for y 1 then, for each guess, we need to choose one value out of two possibilities for each of the byte index (2 16 possible choices). The possible key bytes for a correctly guessed forbidden value y 1 = 30 are displayed in Table 5. In other words, Table 5 is Table 4 xored with y 1 . Finding the key then consists in choosing the correct value (shown in red on Table 5) out of the two, for each byte index.

In total, we have 2 24 key hypotheses, with a pair of plaintext and corresponding ciphertext to validate the correct key, recovering the AES key can be done on a desktop computer in a few minutes. It takes 145 s on an Intel E5-1620 v3 CPU to find y 1 = 30, so it would take by extrapolation 757 s, or less than fifteen minutes, to test all keys.

Forensic

The fault exploited here is actually in L1D and can be directly observed with the JTAG. We show on Listings 7 and 8 the correct and faulty lookup tables as seen by the JTAG.

0x0006b510: 7b777c63 c56f6bf2 2b670130 76abd7fe 0x0006b520: 7dc982ca f04759fa afa2d4ad c072a49c

Listing 7: Part of the correct sbox lookup table.

0x0006b510: 7b777c63 c56f6bf2 2b670136 76abd7fe 0x0006b520: 7dc982ca f04759fa afa2d4ad c072a498

Listing 8: Part of the faulty sbox lookup table. The two faults are displayed in red.

We can notice that the sbox output 30 has been replaced by 36. 30 is, therefore, a forbidden value at sbox output, at the origin of the correct guess y 1 = 30.

The two faulted values are more than 128 bits apart, but on the same cache line (if we suppose that they are aligned in memory). The only memory bus (cf. Table 1) with a size greater than 128 bits is the one that write L2 from L1D values. Since we are reading sbox values, not writing them, it is highly improbable that such a bus transfer was hit. Instead, we should consider that the fault impacted several memory transfers, which has been shown possible in section 6 by the incoherence between the L2 and L1D caches in the IncoherentState case.

Defense mechanisms

In this paper, we have shown that you cannot rely on hardware for critical functionality. Our forensic analyses show that the memory hierarchy and the MMU can easily be corrupted. However, other micro-architectural elements might also be confused by the injected fault.

We can conjecture that the subsystems ensuring data coherence, speculative execution, etc. will one day be the victims of fault attacks.

As such, protecting a CPU against fault attacks requires to ensure the integrity of their micro-architectural blocks. If this problem is well known for secure components such as smartcards, hardening blocks which compose a modern and complex CPU is an open problem.

In this section, we discuss how to protect complex CPUs to fault injection attacks inside the CPU or out of it through the SoC organization.

Inside the CPU

Instead of solving the integrity problem for all microarchitectural blocks, which is a complex research program in itself, we focus on the cache memories.

Ensuring integrity and authenticity in cache memories

Two strategies can be deployed to detect memory faults. On the one hand, a common solution to quickly verify data integrity in memory hierarchy is the error correcting codes (ECCs). They are efficient to detect a a limited number random faults : this solution is relatively low-cost but assumes that the attacker has no control over the fault value and cannot inject a lot of faults. In the other case, the attacker would be able to inject random faults until one passes the ECC scheme.

If we only consider the attacks introduced in this paper, this mechanism is enough due to the lack of control on the fault injection and the low automation of the forensic process; the fault rate is low if we need to check the fault effects. However, face a more powerful attacker, it can only slightly slow the attack down.

On the other hand, the use of cryptography in the form of one message authentication code (MAC) can detect memory faults. A generic solution is KECCAK message authentication code (KMAC) with a small output length since the lifetime of the integrity and authenticity protection is limited and to reduce the memory overhead. With an output length of 64 bits (we store 8 B of MAC for each 64 B cache line), the protection increases by 12.5% the memory footprint than the unprotected version (without taking into account tags and flags).

Key generation.

The key k is a true random value that the system should generate at boot time. It must be kept secret so that the attacker cannot know the correct MAC value for a given cache line.

Signing. For each cache line modification, total or partial, the KMAC must be computed again. For a cache line tag t, data block d and flags f let h = KM AC(k, t|d|f ) be the MAC value stored along the cache line. Instead of the tuple (t, d, f ), we now store (t, d, f, h).

Verifying. When a cache line is read, the MAC must be verified. For a read in the cache line constituted by the tuple (t, d, f, h), we compute h verif = KM AC(k, t|d|f ). Finally, we compare h and h verif . If they are equal, the read value is correct. Otherwise, we trigger the alarm: an exception is raised to allow custom software management.

Speculative memory accesses

To ensure data integrity, a MAC is necessary against powerful attackers. However, computing a KMAC requires multiple cycles which drastically decrease the performances of the whole system, especially in the memory hierarchy which already constitutes a bottleneck.

To tackle this problem, we introduce a speculative mechanism for integrity verification. By default, all data coming from memory are considered as usable but not verified : we speculate that they are correct. Therefore, load instructions must be dealt with similarly to speculative branches: the core can continue its execution, but without committing the load until the integrity verification. If the chip is under attack, the verification would fail and the chip can be restored to its initial state, before the incriminated load. Fig. 8: Integrity speculation in a pipelined core. A green instruction means that no speculation is involved, a yellow one that speculation is pending. The red instruction denotes a speculative load that is dismissed. Figure 8 illustrates with an example how integrity speculation can be managed in a pipelined core.

With this speculation strategy, verification and normal computation can be performed simultaneously. It allows increasing the latency margin to perform the verification, enabling the use of MACs. Obviously, this kind of mechanism would be made simpler and less critical by low latency cryptographic hashes, which have yet to be invented.

The path to secure cores

Complex cores today are mainly split into two classes, the high-performance ones and the low energy consumption ones. The security problems are addressed through software modification (e.g. retpoline [START_REF] Turner | Retpoline: a software construct for preventing branch-target-injection[END_REF] against the Spectre attack [START_REF] Kocher | Spectre attacks: Exploiting speculative execution[END_REF]) or minimal hardware modification (e.g. TrustZone to protect against rich OS vulnerabilities). Security is considered as an implementation issue, where attacks happen only if a designer made a mistake.

However, this work shows that a modern complex core is not a reliable substrate for secure computations. Generic secure cores must be designed to handle all the security needs. These secure cores will have to be designed from the ground up, to guarantee security properties across all micro-architectural blocks. We envision a future where the SoCs will be composed of 3 kinds of cores: a core can either grant high performance, low energy consumption or high security.

Through the SoC organization

It is worth mentioning a natural countermeasure that may complicate fault attacks on SoCs, 3D packaging. This technique consists in stacking the dies (CPU, memory, baseband, etc.) in the same package. Experimentally, the attacker may find it difficult to target dies that are not on the surface of the package. Yet it has been demonstrated possible: for example, Vasselle et al. [START_REF] Vasselle | Laser-induced fault injection on smartphone bypassing the secure boot[END_REF] show a laser fault injection attack on a SoC where the external RAM is stacked on it.

Related works

In the literature, fault attacks are a hot topic where studies are focused on effects, targetting both MCUs and complex CPUs. Despite the works made on MCUs, recent complex CPUs are still vulnerable to fault attacks mainly because the manufacturers prefer performance or low consumption than security [START_REF] Kocher | Spectre attacks: Exploiting speculative execution[END_REF][START_REF] Lipp | Meltdown: Reading kernel memory from user space[END_REF]. In this section, we made an overview of state-of-the-art fault attacks.

Fault attacks on hardware components have been studied starting from the seminal work of Skorobogatov et al. [START_REF] Skorobogatov | Optical fault induction attacks[END_REF] in 2002. Significant works which focus on MCUs have been devoted to demonstrating how fault attacks can break security mechanisms where both cryptography [START_REF] Schmidt | A practical fault attack on square and multiply[END_REF][START_REF] Van Woudenberg | Practical optical fault injection on secure microcontrollers[END_REF][START_REF] Yuce | Software fault resistance is futile: Effective single-glitch attacks[END_REF] and critical applications [START_REF] Barbu | Attacks on java card 3.0 combining fault and logical attacks[END_REF][START_REF] Bouffard | Combined software and hardware attacks on the java card control flow[END_REF] are targeted.

Until recently, MCUs were the favourite targets since they are cheaper and simpler (no memory virtualization, simple cache levels if any, no speculative nor outof-order execution) than the complex CPUs. Therefore, it was a good target to evaluate the fault effects. Mainly within a black box approach, several works [START_REF] Balasch | An in-depth and black-box characterization of the effects of clock glitches on 8-bit mcus. In 2011 Workshop on Fault Diagnosis and Tolerance in Cryptography[END_REF][START_REF] Bar-El | The sorcerer's apprentice guide to fault attacks[END_REF][START_REF] Dureuil | From code review to fault injection attacks: Filling the gap using fault model inference[END_REF][START_REF] Moro | Electromagnetic fault injection: Towards a fault model on a 32-bit microcontroller[END_REF][START_REF] Rivière | High precision fault injections on the instruction cache of armv7-m architectures[END_REF][START_REF] Verbauwhede | The fault attack jungle -A classification model to guide you[END_REF] focus on characterizing fault effects from the ISA level. Characterizing ISA faults is an interesting approach when you have no access to the hardware IP. Another approach [START_REF] Beringuier-Boher | Body biasing injection attacks in practice[END_REF][START_REF] Dumont | Electromagnetic fault injection : How faults occur[END_REF] is to focus on characterizing faults at the level of transistors and logic gates.

Recently, inspired by the works made on MCUs, fault attacks targeting complex CPUs have emerged. They target the secure boot [START_REF] Cui | BADFET: Defeating Modern Secure Boot Using Second-Order Pulsed Electromagnetic Fault Injection[END_REF][START_REF] Timmers | Controlling PC on ARM using fault injection[END_REF][START_REF] Vasselle | Laser-induced fault injection on smartphone bypassing the secure boot[END_REF], the trusted execution environment (TEE) [START_REF] Tang | CLKSCREW: exposing the perils of securityoblivious energy management[END_REF], the memory partitioning [START_REF] Van Der Veen | Drammer: Deterministic rowhammer attacks on mobile platforms[END_REF] or some OS security mechanisms [START_REF] Timmers | Escalating privileges in linux using voltage fault injection[END_REF]. However, due to the complexity of both hardware and software on these targets, characterizing the fault effects are more difficult than on MCUs.

Characterizing fault effects on complex CPUs is a hot topic to improve their hardware security; for instance, to prevent attacks by implementing efficient countermeasures. Few works [START_REF] Proy | A first isa-level characterization of em pulse effects on superscalar microarchitectures -a secure software perspective[END_REF][START_REF] Trouchkine | Fault Injection Characterization on modern CPUs -From the ISA to the Micro-Architecture[END_REF] focus on this research area.

In [START_REF] Proy | A first isa-level characterization of em pulse effects on superscalar microarchitectures -a secure software perspective[END_REF], the authors develop a fault model at the ISA level. In other words, they identify how the data and the instructions of a program are affected by the fault. It is essential to understand the impact on a program and to propose software-based countermeasures, but some works have shown that software-based countermeasures are not sufficient [START_REF] Yuce | Software fault resistance is futile: Effective single-glitch attacks[END_REF] and hardware ones are needed. However, for building hardware countermeasures, the fault model must be characterized at the micro-architectural level, not the ISA level.

To complete this approach, Trouchkine et al. [START_REF] Trouchkine | Fault Injection Characterization on modern CPUs -From the ISA to the Micro-Architecture[END_REF] propose a model for complex CPUs and a method to obtain micro-architectural information on the fault from observations at the ISA level. By using this method, the authors are able to identify the defects that appear in the registers, pipeline or cache of an x86 CPU and an ARM CPU. Although this method is able to identify the affected CPU micro-architectural components, due to the complex OS presence and from an ISA perspective, they are not able to accurately determine the micro-architectural fault model.

In our article, we focus on a target without a complex OS. Therefore, we relax hypotheses about the effect of a complex software on the fault effect characterization. Within this approach, we disclose new fault effects on the memory hierarchy.

Conclusion

In this paper, we have demonstrated that complex CPUs are vulnerable to fault injection attacks. In particular, the memory hierarchy and the MMU can be changed, which creates a mismatch between hardware behavior and software expectations. Nowadays, the security of computing systems is focused on the software side; there are no efficient countermeasures against hardware perturbations in complex CPUs. Pointer authentication, as proposed by the ARMv8.3 ISA, for example, does not resist the introduced fault model.

Exploitation heavily depends on the interaction between the hardware (the specific device) and the software (including applications and OS). Therefore the cautious developer cannot predict where vulnerabilities will occur and, as a consequence, cannot efficiently protect its application. Today, such attacks using EMFI are still quite hard to realize: they require expensive apparatus, human resources to do the experiments, etc. However, they are within reach of small organizations, and we can expect that the difficulty and cost of these attacks will be lower in the future.

Actions must be taken to ensure that computing systems handle sensitive information securely. The performances/energy consumption trade-off has been settled by implementing the two kinds of cores in the same SoC. In the same way, we need secure cores as well that compromise both on performances and energy consumption but can offer much stronger security guarantees.

Fig. 3 :

 3 Fig. 3: EMFI BCM2837 sensitivity map (Dot size is not correlated with probe size.)

Listing 1 : 1 trigger_up

 11 Loop target application

Listing 2 :

 2 Assembly version of the for loop (Listing 1) without optimisation. ... 0x48a04: b94017a0 ldr x0, [x29,#20] 0x48a08: 11000400 add x0, x0, #0x1 0x48a0c: b90017a0 str x0, [x29,#20] 0x48a10: b9401ba0 ldr x0, [x29,#24] 0x48a14: 11000400 add x0, x0, #0x1 0x48a18: b9001ba0 str x0, [x29,#24] 0x48a1c: b9401ba0 ldr x0, [x29,#24] 0x48a20: 7100c41f cmp x0, #0x31 0x48a24: 54ffff0d b.le 48a04 <loop+0x48> ...

Fig. 4 :

 4 Fig.4: Method for testing cache coherency between L1D and L1I using JTAG

Fig. 7 :

 7 Fig.7: For the first ciphertext byte, a number of occurrences for each value; for a total of 10000 occurrences.

Table 2 :

 2 Correct identity mapping

	Virtual Address	Physical
		Address

  .

	Index	0	1	2	3	4	5	6	7
	Forbidden	23	21	2d	4f	7f	08	7a	27
	values	8f	8d	81	e3	d3	a4	d6	8b
	Index	8	9	10 11 12 13 14 15
	Forbidden	6f	37	3b	17	7d	1b	00	59
	values	c3	9b	97	bb	d1	b7	ac	f5

Table 4 :

 4 Ciphertext forbidden values. For each byte index, we have 2 forbidden values. The first two forbidden values are the ones that we can observe in Figure

Table 5 :

 5 Possible key bytes for the correct guess y 1 =

	30. The correct K10 key is 13 11 1d 7f e3 94 4a 17
	f3 07 a7 8b 4d 2b 30 c5.

We set the PC value to the ic iallu instruction address in memory.


Anthony Brunel

Amine Bourki
email: amine.bourki@gmail.com

Cédric Demonceaux

Olivier Strauss
email: olivier.strauss@lirmm.fr

Keywords: Efficient Autonomous Exploration via Permutohedral Frontier Filtering Aerial Systems: Perception and Autonomy, Vision-Based Navigation, Motion and Path Planning

published or not. The documents may come   L'archive ouverte pluridisciplinaire

SplatPlanner: Efficient Autonomous Exploration via Permutohedral Frontier Filtering

Anthony Brunel 1,2 , Amine Bourki 2 , Cédric Demonceaux 3 and Olivier Strauss 1

(b) (a) (c) (d)
Fig. 1: We introduce SplatPlanner, a fast algorithm for jointly mapping and planning a collision-free exploration of an unknown scene, using an MAV. Here, our method runs online and on-board in real-flight (a) to gradually enrich a volumetric 3D map of the scene at different iterations, at t = 54s (b), t = 169s (c) and t = 347s (d), near completion. Mapped voxels are colored based on their height, while frontier voxels that bound the known area are in gray, and trajectories in dark blue.

I. INTRODUCTION

The safe exploration of unknown environments by unmanned vehicles is a key requirement to transition into the long-awaited era of autonomous flying robots. Micro Aerial Vehicles (MAVs) in particular are often favored thanks to their agility, form-factor and affordability. However, despite their perpetually improving hardware capabilities, MAVs still run on limited resources in terms of on-board computation and battery-life. This has motivated two orthogonal research trends to integrate these constraints through collaborative excedric.demonceaux(@)u-bourgogne.fr ploration [START_REF] Yamauchi | Frontier-based exploration using multiple robots[END_REF], [START_REF] Dong | Multi-robot collaborative dense scene reconstruction[END_REF], and efficiency-oriented mono-agent methods [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF], [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF], which falls within our scope.

In this work, we devise a hybrid strategy relying on the two leading frameworks in autonomous exploration planning, frontier reasoning [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF] and Rapidly-exploring Random Trees (RRT*s) [START_REF] Lavalle | Rapidly-exploring random trees: A new tool for planning[END_REF], [START_REF] Kuffner | Rrt-connect: An efficient approach to single-query path planning[END_REF], [START_REF] Karaman | Sampling-based algorithms for optimal motion planning[END_REF], and advance the current state-of-theart in terms of speed and efficiency by a substantial margin. Our work makes the following main contributions:

• We introduce SplatPlanner, an end-to-end system for autonomous exploration that simultaneously maps the environment and plans collision-free trajectories therein. • The method uses a novel Permutohedral Frontier Filtering to extract and score promising frontier voxels in terms of their spatial density using highly efficient bilateral filtering operations on permutohedral lattices [START_REF] Adams | Fast high-dimensional filtering using the permutohedral lattice[END_REF]. • Our proposed system advances the state-of-theart w.r.t standard criteria of exploration speed and efficiency, as shown through quantitative and qualitative experiments in controlled simulated environments. • The practical robustness of our approach is tested in a challenging real-flight scenario, also showing superior performance w.r.t state-of-the-art planners in this regard.

II. RELATED WORK

The task of autonomous exploration planning is a longstanding problem and was studied for over two decades [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF], [START_REF] Lavalle | Rapidly-exploring random trees: A new tool for planning[END_REF], [START_REF] Holz | Evaluating the efficiency of frontier-based exploration strategies[END_REF], [START_REF] Juliá | A comparison of path planning strategies for autonomous exploration and mapping of unknown environments[END_REF]. The adopted methods can be categorized into frontier-based, sampling-based and hybrid strategies.

The first trend builds on the concept of frontiers, which are interstitial voxels between free-and unknown spaces (Fig. 1). It requires to re-detect such entities before each path-planning step. In their seminal work, Yamauchi et al. [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF] target the nearest available frontier to guide the exploration, eventually leading to a termination when all reachable frontiers are visited. In the same vain, Cieslewski et al. [START_REF] Cieslewski | Rapid exploration with multi-rotors: A frontier selection method for high speed flight[END_REF] prioritize frontiers that maintain the velocity of the MAV, hence limiting visits to positions in opposing directions. Dornhege et al. [START_REF] Dornhege | A frontier-void-based approach for autonomous exploration in 3d[END_REF] adhere to the broader Next-Best-View (NBV) paradigm [START_REF] Connolly | The determination of next best views[END_REF], i.e., selecting views that maximize a specific utility function, considering the popular unmapped volume within the current view frustum while also explicitly grouping frontiers into cohesive entities. Even though these two processes have become staple ingredients in frontierbased techniques [START_REF] Holz | Evaluating the efficiency of frontier-based exploration strategies[END_REF], they respectively rely on ray-casting and spatial clustering operations that are computationally expensive. Other common utility functions include the information gain [START_REF] Heng | Efficient visual exploration and coverage with a micro aerial vehicle in unknown environments[END_REF], Shannon entropy [START_REF] Palazzolo | Information-driven autonomous exploration for a vision-based mav[END_REF], [START_REF]Effective exploration for mavs based on the expected information gain[END_REF], supervised learning [START_REF] Hepp | Learn-to-score: Efficient 3d scene exploration by predicting view utility[END_REF], and many other efficient alternatives [START_REF] Bissmarck | Efficient algorithms for next best view evaluation[END_REF].

Sampling-based strategies on the other hand, randomly sample seed positions in space then maintain a data structure that can further be queried to produce a collision-free path connecting them. Most of the recent competitive methods rely on Rapidly-exploring Random Trees (RRTs) [START_REF] Lavalle | Rapidly-exploring random trees: A new tool for planning[END_REF], [START_REF] Kuffner | Rrt-connect: An efficient approach to single-query path planning[END_REF]. The framework uses a tree-structure over the sampled seeds but can produce jagged trajectories. RRTs* [START_REF] Karaman | Sampling-based algorithms for optimal motion planning[END_REF] extend RRTs by biasing the random seed sampling to plan simpler, more efficient trajectories. RH-NBVP [START_REF] Bircher | Receding horizon" next-best-view" planner for 3d exploration[END_REF] expands RRTs on viewpoints that are sampled by means of NBV where the first node of the utility-maximizing branch is executed. While the method performs very well in local exploration, it is prone to local minima leading to a poor global scene coverage. Witting et al. [START_REF] Witting | History-aware autonomous exploration in confined environments using mavs[END_REF] tackle this by maintaining a history of previously considered viewpoints to the expense of an additional cost in computation and storage. Alternatively, AEP [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF] successfully combines RH-NBVP with conventional frontier reasoning to balance out the poor performance in global exploration. Although RRTs* are effective for collision-free planning, they cannot recover from earlier mistakes. They are also notoriously inefficient as they repeatedly discard-thenrebuild most of the information from one iteration to another. To improve efficiency, ESM [START_REF] Schmid | An efficient sampling-based method for online informative path planning in unknown environments[END_REF] continuously grows one single tree and only sporadically queries feasible paths.

More related to our hybrid strategy, FFI [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF] uniformly samples frontiers per octant in an octree structure [START_REF] Hornung | Octomap: An efficient probabilistic 3d mapping framework based on octrees[END_REF], then targets views that maximize the map entropy. Despite achieving a very fast exploration, the strategy can suffer from quantization effects and induces a trade-off between timeand memory efficiency.

III. PROBLEM STATEMENT

Given V ⊂ R 3 a voxel-grid occupancy map of the scene, the goal of our considered MAV is to map every voxel x ∈ V initially labeled as 'unknown', with a final volumetric occupancy among {'free', 'occupied'} states, while computing collision-free flight-paths online and on-board. We denote the pose of the MAV by µ = [p, ψ], where p = [x, y, z] ⊤ ∈ R 3 is a 3D position and ψ ∈ [0, 2π[ a corresponding yaw angle. We also assume a maximum linear velocity v max and linear acceleration a max , as well as a maximum yaw rate ω max .

Our framework exploits the notion of frontiers [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF] which are 'unknown'-labeled voxels f ∈ F ⊂ V that are adjacent to 'free' spaces. Our method extracts a set of filtered frontiers F ⊂ F using scores s(p i ) ⊂ S per position p i ∈ F based on the density of their spatial neighborhoods. The MAV then repeatedly calculates collision-free paths online, across the scene until all reachable frontiers are visited.

IV. SPLATPLANNER

We propose a hybrid framework that combines the advantages of frontier-reasoning (i.e., global scene coverage, natural termination) with the effectiveness of RRTs* in planning collision-free flight-paths. The number of costly calls to RRTs* is alleviated by an NBV-sampling based on our novel Permutohedral Frontier Filtering (PFF) procedure. Our method relies on two interconnected modules, as detailed below and illustrated in Fig. 2.

A mapping routine continuously integrates depth and odometry sensor information to update the occupancy map V. The main loop of the planning unit activates the subsequent mechanisms: our PFF efficiently associates scores to every frontier f ∈ F based on their spatial neighborhoods in V. Next, the most promising goal candidate positions are extracted from the scored frontiers and are evaluated in terms of the unknown-labeled volume within corresponding frustums and the time to execute the corresponding trajectory. The output trajectory is then selected as the best trade-off between its associated UV and its execution time, translating into a natural balance between local and global exploration.

A. Mapping Routine

Occupancy Map and Derived Information. Map updates occur when new depth measurements are received from the active sensor (e.g., Kinect, or Intel Realsense D400 series). The occupancy values of voxels in V that lie inside the current view frustum are then directly inserted into V by using odometry data and assuming a standard probabilistic occupancy [START_REF] Loop | A closedform bayesian fusion equation using occupancy probabilities[END_REF], [START_REF] Vespa | Efficient octree-based volumetric slam supporting signed-distance and occupancy mapping[END_REF]. While most of the mapping methods use ray-casting operations to maintain occupancy maps [START_REF] Hornung | Octomap: An efficient probabilistic 3d mapping framework based on octrees[END_REF], [START_REF] Vespa | Efficient octree-based volumetric slam supporting signed-distance and occupancy mapping[END_REF], [START_REF] Oleynikova | Voxblox: Incremental 3d euclidean signed distance fields for on-board mav planning[END_REF], [27], we chose the projection mapping which is an efficient alternative especially when dealing with regular grid maps. This is consistent with conclusions drawn in existing studies on the topic [START_REF] Klingensmith | Chisel: Real time large scale 3d reconstruction onboard a mobile device using spatially hashed signed distance fields[END_REF]. A simple Euclidean Distance Transform (EDT) applied to V [27], [START_REF] Felzenszwalb | Distance transforms of sampled functions[END_REF] is also used to derive a volumetric collision map to handle collisionchecking. This allows efficient O(1) look-ups vs. O(log(N )) for octrees [START_REF] Vespa | Efficient octree-based volumetric slam supporting signed-distance and occupancy mapping[END_REF]. Each update also leads to re-assessing frontiers F due to potential changes in unknown-and free voxels they separate. Efficient Updates. While V and F need to be updated each time new depth information is received, the EDT map is continuously updated at a frequency of 4Hz, which is sufficient in practice to ensure its relevance when matching reasonably realistic MAV velocities. All of these updates are only envisioned within the current view-frustum of the MAV.

B. Novel Permutohedral Frontier Filtering (PFF)

Overview and Input to PFF. The exploration planning process first starts by using our PFF to associate a score of frontier-neighborhood density to each frontier voxel. This score is the criterion we use to guide our planning. To do so, we use permutohedral lattice structures to support bilateral filtering operations to efficiently approximate this score. Permutohedral lattices are widely used in 2D image processing and geometry processing to do high dimensional filtering [START_REF] Adams | Fast high-dimensional filtering using the permutohedral lattice[END_REF]. Other recent applications include, e.g., semantic segmentation of 3D point clouds using Deep Neural Networks [START_REF] Su | Splatnet: Sparse lattice networks for point cloud processing[END_REF], or fast point cloud registration [START_REF] Gao | Filterreg: Robust and efficient probabilistic point-set registration using gaussian filter and twist parameterization[END_REF]. A Permutohedral Lattice is composed of identical high-dimensional tetrahedra named simplices, where the enclosing simplex (i.e., cell) of any given point in the higher-dimensional space can be found by a simple rounding algorithm (as illustrated in Fig. 3). Such structures have been proven to yield very accurate approximations to expensive filtering problems for even high d-dimensional inputs by processing them in a (d + 1)-dimensional space. It uses very efficient operations requiring only a fraction of the computation [START_REF] Baek | Some useful properties of the permutohedral lattice for gaussian filtering[END_REF].

As such, our PFF consumes the 3D coordinates of the frontier set F and goes through three operations, splat, blur and then slice, each-of-which being supported by a lattice. Processing Steps and Parameters. Splat first interpolates the input 3D coordinates onto their enclosing 4D permutohedral simplices using barycentric weights. Blur then applies a separable Gaussian filter resulting in a weighted combination of entities with their simplicial neighbors which equates to an implicit spatial aggregation of features. Slice finally interpolates the lattice features back onto their original 3D coordinates with corresponding densities, using the same weights used in splatting. The only parameter to the method is a scaling diagonal d × d matrix Λ that controls the discretization (spacing) of the simplicial cells (here, d = 3).

Formally, the sequence of operations can be written as a matrix multiplication, as follows:

∆ = E slice B blur S splat F, (1)
where ∆ contains per-frontier filtered density scores, F is the N × 3 matrix version of frontiers F and is transformed through three N × 4 matrices in higher dimensional space E slice , B blur , S splat respectively supporting slice, blur, splat operations, and N = card(F). Advantages of our PFF. The procedure has the following main benefits.

• Splat, blur and slice are linear in frontier inputs and their combination amounts to multiplying sparse matrices. • Through the Blur operation in particular, the process seamlessly generates an implicit grouping, i.e., a neighborhood aggregation of frontiers in linear time. Splat and Slice are just means to interact with the initial 3D space and amount to a basic linear interpolation each. This avoids the costly spatial clustering used by several frontier-based planners altogether [START_REF] Dornhege | A frontier-void-based approach for autonomous exploration in 3d[END_REF], [START_REF] Dornhege | A frontier-void-based approach for autonomous exploration in 3d[END_REF].

• PFF is only parametrized by the scaling matrix Λ which is a diagonal matrix of inverse values of the desired standard deviations (stds) per spatial coordinate. Throughout our experiments, we consider one common std for all three coordinates as σ xyz = 1m. • The framework allows to handle much more complex features in dimensionality on top of the 3D coordinates we consider [START_REF] Su | Splatnet: Sparse lattice networks for point cloud processing[END_REF]. We leave this avenue as future work, e.g., to integrate semantics to our exploration formulation. Additional details and advantages regarding the general permutohedral filtering framework can be found in the dedicated study of Baek et al. [START_REF] Baek | Some useful properties of the permutohedral lattice for gaussian filtering[END_REF].

C. Goal Extraction and Path Sampling

The output of the preceding PFF scoring is used to extract a list of promising goal positions to visit. To do so, the goal extraction aims at favoring areas with high density scores evenly spread across the space to ultimately bound the computed feasible RRT*-paths from sparsely-sampled goals.

The goal extraction operation assumes positions within the frontier set, ranked in decreasing density scores and iterates over frontiers by only retaining points that are far enough from previously retained positions (up to a radius threshold r thresh ). The detailed algorithm is provided in Algo. 1. Finally, the set of retained goals is formed by considering a uniform sampling of N unif orm extracted frontiers across the space, augmented by the top N scores scored entities remaining after the aforementioned spatial filtering to prevent near-duplicates to occur. Our random selection criterion ensures an even distribution of goals and secures the inclination towards global exploration. The density-favoring criterion on the other hand, guarantees that the most promising areas are not left out, regardless of their spatial distribution. In our experience, this yields a much better trade-off in practice between local-and global exploration than pure uniform sampling [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF] or pure local development [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF].

Once the limited set of promising goals G is computed, we plan their feasible trajectories P i = [p, ..., p i ] stemming from the current MAV position using RRT* [START_REF] Karaman | Sampling-based algorithms for optimal motion planning[END_REF] with path simplification, as implemented in the Open Motion Planning Library (OMPL) [START_REF] Sucan | The open motion planning library[END_REF]. A standard collision checking is also applied throughout the linear segments of the computed paths with a safety bounding radius R centered on the MAV. An occlusion checking by casting a ray from the current position to the goal candidates ensures mutual visibility between endpoints. An additional time-out forces the RRT* to provide viable solutions within a limited time (set to 5 ms), for maintaining the overall pace of the exploration.

D. Viewpoint Evaluation, Yaw Angles and Gain Function

At this stage, the promising goals resulting from previous steps are guaranteed by construction to be valid and reachable. Next, we describe how we prioritize the exploration to maximize its efficiency by evaluating the volumetric gain relative to the time it costs to execute the associated trajectories. This consists in estimating through ray-casting the viewdependent Unmapped Volume (UV) intersecting the frustum bounded between distances to the camera center d min and d max . α (resp. β) is the horizontal (resp. vertical) angular increment used in ray-casting (typically, α = β = 1 • ). Thus, a 360 • horizontal UV-sweep produces a view-independent estimate of the volume assuming a fixed (sensor-specific) vertical fov, as follows:

V (d min , d max , α, β) = 4 tan ( α 2 ) tan ( β 2 ) dmax dmin r 2 dr = 4 3 tan ( α 2 ) tan ( β 2 )(d 3 max -d 3 min ) (2
) Yaw Optimization. Yaw values ψ i are associated to the positions p i encompassing goal candidates and intermediate waypoints alike, by retaining the horizontal orientation that maximizes its view-dependent UV within the computation of the volume. Please note that the optimal yaws are retained while calculating the volume with no additional post-process. Gain Function. Finally, the gain function explicitly optimizes the volumetric exploration speed in m 3 /s, to execute the path P i that maximizes the following expression: where U (µ i ) is the UV of the destination pose at position p i and P i its connecting path to current MAV position p with pose µ. In turn, T (P i ) is the total travel time to execute P i assuming a constant acceleration a max .

g(µ i , P i ) = U (µ i ) T (P i ) , (3)
V. IMPLEMENTATION DETAILS Simulation Framework. Except where stated otherwise, throughout our experiments we consider a common testbed built on the Robot Operating System (ROS Kinetic) library [START_REF] Quigley | Ros: an open-source robot operating system[END_REF] on a laptop equipped with an Intel Core i7 CPU, 16GB RAM. We simulate a FireFly hexacopter MAV model from Ascending Technologies and its physics are modeled by the popular Gazebo-based RotorS simulator [START_REF] Furrer | Robot Operating System (ROS): The Complete Reference[END_REF]. The control is insured by a multi-rotor Model Predictive Control (MPC) [START_REF] Kamel | Model predictive control for trajectory tracking of unmanned aerial vehicles using robot operating system[END_REF]. Standard collision-checking is done within a sphere of radius R centered at the MAV's position. As the computed trajectories are typically piecewise-linear displacements, we use a polynomial trajectory optimization [START_REF] Richter | Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments[END_REF] to send graceful paths to the MPC. The final rendering uses the Vulkan API1 , assuming perfect poses from RotorS. It simulates a 30Hz DepthVision camera. All considered datasets were integrated as standard meshes into Gazebo. Parameter Settings and Reproducibility. The parameters to all our experiments are provided in Table I, including ones that were originally omitted by the referenced competition.

VI. RESULTS

In this section, we analyze the performance of our Splat-Planner system and its relative positioning w.r.t the state-ofthe-art through quantitative and qualitative experiments.

A. Datasets and Baselines

In our comparative experiments, we consider the recent state-of-the-art planners ESM [START_REF] Schmid | An efficient sampling-based method for online informative path planning in unknown environments[END_REF], AEP [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF] and FFI [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF]. ESM is the current top-performing pure sampling-based method [START_REF] Schmid | An efficient sampling-based method for online informative path planning in unknown environments[END_REF] while AEP and FFI are among the best hybrid systems for autonomous exploration.

We first consider 3 challenging synthetic datasets of increasing complexity and size. (b) FFI [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF] (As captured from their paper).

(c) SplatPlanner (Ours) achieves a simpler trajectory and a better coverage.

(d) FFI [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF] (As captured from their paper).

Fig. 4: Comparative evaluation vs. FFI [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF] on the POW-ERPLANT simulation in terms of exploration speed (a-b), corresponding trajectories and produced maps (c-d). Our SplatPlanner achieves faster explorations throughout the considered maximum exploration velocities v max .

Fig. 5: Exploration of the MAZE after 250s using our approach. Voxels are colored based on their height, while the trajectory ranges progressively from white to blue.

• MAZE -A hand-crafted scene of 20m x 20m x 2.5m typically used to study exploration systems by narrowing down their behaviors to their most basic expression (Fig. 5). • POWERPLANT -A large outdoor of 33m x 31m x 26m. It is publicly available and was used by FFI [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF] in particular.

In absence of a public code of their method it is a common test-bed to compare our performances (Fig. 4c). • COMPLEX FACILITY -An original challenging CAD model we are sharing publicly. It covers 20m x 20m x 4.6m amounting to a 185m2 area and depicts a very geometrically complex industrial scene that has been modeled by a human expert (Fig. 6a).

Please note that in terms of datasets, our experimental setup is at least on par quantity-wise with the most rigorously evaluated works in the field (e.g., [START_REF] Cieslewski | Rapid exploration with multi-rotors: A frontier selection method for high speed flight[END_REF], [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF]). Our COMPLEX FACILITY however, is significantly more complex and challenging than commonly envisioned datasets [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF], [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF], [START_REF] Bircher | Receding horizon" next-best-view" planner for 3d exploration[END_REF].

B. Comparative Setup and Evaluation Criteria

Autonomous exploration algorithms are typically evaluated on synthetic datasets in controlled simulated environments. This allows for a more fair comparison in terms of experimental conditions and also avoids the expensive failure cases in real flights. A detailed description of the simulation framework is provided in Section V. First, we analyze performance vs. ESM [START_REF] Schmid | An efficient sampling-based method for online informative path planning in unknown environments[END_REF] and AEP [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF] by integrating their respective public implementations 2 to our experimental setup to allow for a fair comparison, as previously discussed.

Next, in absence of a public implementation for FFI [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF], we modify our experimental setup to match the assumptions they disclose in the corresponding paper, and propose a fair side-by-side comparison on the public POWERPLANT dataset using the authors' reported performances and illustrations (Fig. 4b,4d). In particular, we replace our MPC by its RotorS-based counterpart and use the reported parameters (Fig. 4a,4c, Table I). Performance is evaluated w.r.t to the following criteria.

• Exploration speed is measured quantitatively by means of the explored volume over time, averaged over 10 runs to account for the stochastic nature of the methods. This is the commonly adopted practice in the field. • Exploration efficiency assesses the ability of a system to make the most out of its exploration. Quantitatively this equates to the final (plateau) volumetric coverage in terms of mapped volume. Qualitatively, this is assessed visually by comparing the covered areas.

C. Positioning vs. State-of-the-art

Pure Performance. Our SplatPlanner significantly and consistently exhibits superior performance w.r.t the considered state-of-the-art methods ESM and AEP throughout the experiments in exploration speed (Fig. 7a, 7b, 6b). The tendency is also confirmed w.r.t the final explored volume (i.e., efficiency) except on the COMPLEX FACILITY where ESM seems on par with SplatPlanner. W.r.t FFI on the POWERPLANT, SplatPlanner also performs consistently better throughout different maximum velocities (Fig. 4a,4b), except before the 500s mark where the competition is slightly faster for v max = 2.5 m/s. Beyond this limit, the data favors the proposed approach leading to a far superior efficiency (final explored volume). This tendency is confirmed by the qualitative scene coverage as well (Fig. 4c,4d).

Parameter Settings and Robustness. (vs. 5-6) that remain stable on all scenes. This supports the superior robustness of SplatPlanner w.r.t state-of-the-art in this aspect as well. Additional Insights. Table II shows comparative exploration planning statistics w.r.t state-of-the-art. Our method requires much fewer, but slower planning iterations. Yet, it develops faster, into a much longer path overall. [START_REF] Schmid | An efficient sampling-based method for online informative path planning in unknown environments[END_REF] 128 N/A 128 Fig. 8: SplatPlanner runs online and on-board from takeoff to termination with no human intervention nor prior knowledge about this large 15m x 10m x 3.5m WAREHOUSE.

D. Real-Flight Performance

We evaluate the practical robustness of our end-to-end system on a challenging fully-autonomous flight (Fig. 8). Our custom MAV flies through a large WAREHOUSE that is bound at 15m x 10m x 3.5m and runs our SplatPlanner algorithm online and on-board during 349s. The results of this experiment are depicted step by step in Fig. 1 and are the direct output of on-board processing. In comparison to realflight experiments provided by top-performing planners [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF], [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF], ours takes place in a significantly more complex, larger indoor environment than the ones referenced. This represents an improvement in volumetric size of the considered scenes ranging from 2.75x [START_REF] Dai | Fast frontier-based information-driven autonomous exploration with an mav[END_REF] to 4.66x [START_REF] Selin | Efficient autonomous exploration planning of large-scale 3-d environments[END_REF] over the leading competition. In terms of hardware, the MAV we consider is a custom quadrotor using a DJI A3 flight controller. The equipped sensors include an Intel T265 VI-SLAM for odometry, a D455 depth VGA camera and an Intel NUC with an Intel Core i7-10710U and 16GB of memory.

Additional detailed information about the real-flight and simulation experiments are provided in a supplementary video at https://youtu.be/DCcfA2HB1GI.

VII. CONCLUSION

We have presented SplatPlanner, an end-to-end autonomous system for 3D exploration planning in unknown environments using an MAV equipped with a depth sensor. The proposed method improves over recent state-of-theart methods in terms of exploration efficiency and speed, as consistently supported by the considered simulation experiments. An additional real-flight scenario also underlines the practical robustness of our global solution.

As future work, we plan on integrating semantic reasoning into our formulation by leveraging the pose and volumetric occupancy of detected objects of interest.

Fig. 2 :

 2 Fig. 2: SplatPlanner -System overview.

Fig. 3 :

 3 Fig. 3: Permutohedral Frontier Filtering -PFF transforms the frontier voxels through 3 successive bilateral filtering operations (splat-blur-slice) on permutohedral lattices, and produces their density scores efficiently.

3 )

 3 vmax = 2.5 m/s vmax = 1.5 m/s vmax = 0.7 m/s (a) SplatPlanner (Ours).

  Qualitative comparison of the maps produced at t = 300s. Voxels are colored based on their height.

Fig. 6 :Fig. 7 :

 67 Fig.6: COMPLEX FACILITY -Our SplatPlanner explores this complex environment more efficiently and better retrieves complex geometric details w.r.t the state-of-the-art competition.

Algorithm 1 :

 1 Goal Candidate Extraction Input: P : list of position / score pairs (p i , s i ) in decreasing scores, r thresh : radius threshold Output: G : set of goal candidates foreach position p i ∈ P do discarded ← F alse; foreach p j ∈ G do if p ip j < r thresh then

	discarded ← T rue;
	break;
	end
	end
	if not discarded then
	G ← (p i , s i )
	end
	end

TABLE I :

 I Experimental settings and parameters.

	Method	Parameter	MAZE	POWERPLANT	FACILITY
		res. (m)	0.1	0.2	0.1
		R (m)	0.5	0.5	0.5
		vmax (m/s)	1.5	0.7, 1.5, 2.5	1.5
	All	amax (m/s 2 )	2.5	2.5	2.5
		ωmax (rad/s)	1.57	0.75, 1.57	1.57
		dmax (m)	5	7	5
		f ov [h, v]	[90 • , 60 • ]	[115 • , 60 • ]	[90 • , 75 • ]
	Ours	r thresh (m) σxyz (m)	2.5 1.0	2.5 1.0	2.5 1.0
		N	30	50	30
		gzero	2	2	2
	AEP [3]	λ	0.5	0.75	0.5
		σ 2 tresh lmax (m)	0.2 1.5	0.2 3	0.2 1.5
		n local	30	50	30
	ESM [22]	r local (m) r update (m)	1.5 3.	3.0 6.	1.5 3.0
		lmax (m)	1.5	3	1.5

TABLE II :

 II COMPLEX FACILITY -Statistics after 300s.

	Method	#Iterations	Per-iter. avg time (ms)	Path length (m)
	Ours	48	280 ± 34	157
	AEP [3]	90	54 ± 25	124
	ESM

https://www.khronos.org/vulkan/

https://github.com/ethz-asl/mav_active_3d_ planning and https://github.com/mseln/aeplanner