# Toward Safe Integration of Legacy SCADA Systems in the Smart Grid

Aldar C-F. Chan
University of Hong Kong  Jianying Zhou
Singapore University of Technology and Design

###### Abstract

A SCADA system is a distributed network of cyber-physical devices used for
instrumentation and control of critical infrastructures such as an electric
power grid. With the emergence of the smart grid, SCADA systems are
increasingly required to be connected to more open systems and security
becomes crucial. However, many of these SCADA systems have been deployed for
decades and were initially not designed with security in mind. In particular,
the field devices in these systems are vulnerable to false command injection
from an intruding or compromised device. But implementing cryptographic
defence on these old-generation devices is challenging due to their
computation constraints. As a key requirement, solutions to protect legacy
SCADA systems have to be an add-on. This paper discusses two add-on defence
strategies for legacy SCADA systems — the data diode and the detect-and-
respond approach — and compares their security guarantees and applicable
scenarios. A generic architectural framework is also proposed to implement the
detect-and-respond strategy, with an instantiation to demonstrate its
practicality.

##  1 Introduction

A SCADA (Supervisory, Control And Data Acquisition) system is a cyber network
of communicating devices used for instrumentation and control of a distributed
infrastructure, such as an electric power grid, in order to manage the
respective physical processes. The SCADA system of a power grid can monitor
and control various electric equipment along the power delivery path —
including various transformers, circuit breakers, protective relays and
automatic re-closers — while acquiring different measurements, which provide
information about the loading conditions at different parts of the power grid
and health conditions of transmission lines, etc. Hence, correct operation of
a SCADA system is critical to the reliability of any power distribution system
[2, 3].

A successful malicious attack targeting at the SCADA system could potentially
cause extensive power outage. Such service disruption could even have
cascading effects onto other critical infrastructures [3]. However, most of
the SCADA systems currently in active use have been deployed for decades and
very few of them were originally designed with security in mind [19, 22, 29].
These legacy SCADA systems were assumed to operate in isolation at first, with
obscurity and physical isolation being the main security strategy. But
nowadays, this design assumption is challenged not only by new security
threats — including demonstrated break-in’s of power substations [28],
discovered worms on PLCs (Programmable Logic Controllers) and other industrial
control system platforms [17, 23], and the exposure of supposedly obstructed
documents (such as SCADA system configuration and operation manuals) on the
Internet [19] — but also by the changing operational model which desires a
higher level of integration with relatively open systems [14], such as the AMI
(Advanced Metering Infrastructure), in the envisioned smart grid for data
sharing and orchestration of process control.

The increasing connectivity of these legacy SCADA systems with external smart
grid systems, with comparatively more open access, could increase the attack
surface for attackers to compromise devices inside the SCADA systems or send
forged data or commands directly from outside. Nonetheless, these legacy SCADA
systems will take decades to be phased out from operation since they are so
highly integrated with the power equipment they monitor [7, 22]. It is thus
essential to devise protection mechanisms to safeguard legacy SCADA systems as
they are increasingly integrated with newer smart grid systems.

In particular, legacy SCADA systems are typically vulnerable to forged data or
commands sent from intruding or compromised devices (i.e. insider attacks) [2,
7, 13, 19, 22, 26]. For instance, a compromised SCADA RTU (Remote Terminal
Unit) could launch a false command attack whereby an attacker impersonates the
master station to send false control commands to other RTUs, say, to
maliciously trip a particular circuit breaker. On the other hand, false
readings from compromised instrumentation devices could present a distorted
picture of the system status to the master station, thus possibly triggering a
false alarm and disruptive actions [13]. Currently, most legacy SCADA systems
could have little defense to this kind of attacks as no source authentication
or command verification mechanism is in place [2, 4, 7, 19, 22, 26].

Implementing cryptographic defence on the old-generation devices in these
SCADA systems is impossible due to their resource constraints, and protection
has to resort to the bump-in-the-wire approach [29], which is generally
regarded as very inefficient. While authentication and authorization
frameworks (such as IEC62351-8) — which are increasingly applied for
authentication and access policy enforcement in distributed smart grid and
newer SCADA systems [2, 26] — can avoid or minimize false command injection,
it remains challenging to deploy them in some legacy SCADA systems and
protocols due to the computational and communication overheads involved, as
well as, the need of modifications at both the protocol and device level. To
avoid protocol modification, legacy-compliant message authentication [7] is
proposed to embed authentication data as an additional payload of some
specific SCADA protocols. However, it requires modifications of the device
software and is applicable only to a few, usually newer SCADA protocols and
devices that are powerful enough to run common cryptographic primitives.
Generic strategies through enhanced incident management [1] or better process
monitoring [3] could improve SCADA system security but require a higher degree
of human involvement and intervention. It is fair to say truly add-on, non-
intrusive protection for legacy SCADA systems and protocols remains
challenging.

This paper studies and compares two different strategies to secure legacy
SCADA systems for safe integration with smart grid systems. Both approaches do
not require any modification on the devices, protocols or communication
channels, and are scalable for different numbers of devices. The need of human
intervention is also minimized. The first approach, called the “data diode”
approach [10, 24, 30], is commonly adopted in the industry and aims to
preserve the isolation of a legacy SCADA system while facilitating outward
information flow to newer smart grid systems. The second approach aims to open
up a legacy SCADA system for bidirectional information flow, with mechanisms
in place to detect and identify false commands sent by intruding devices or
compromised nodes. This paper proposes a high-level, architectural framework
for the second approach to implement a detect-and-respond strategy to
neutralize the effects of false command attacks on a SCADA field network.
While this paper focuses on false command detection based on verification
against an authenticated copy of each command received through a secure
channel, the framework provides a general basis for incorporating other attack
detection methods [13, 18, 12] to implement a defence strategy. This paper
will also compare the applicability and usability of the two approaches.

The contributions of this paper is two-fold. First, a generic architectural
framework is proposed to implement the detect-and-respond strategy for the
protection of legacy SCADA systems against false command attacks, with a view
to opening up these SCADA systems for integration with relatively more open
smart grid systems. The proposed technique is non-intrusive and truly add-on
without requiring modifications on existing devices and systems. It is also
scalable in the sense that only one defending device is needed per field
network. To demonstrate the practicality of the proposed framework, an
instantiation of the detect-and-respond strategy on the Siemens Sinaut 8FW
protocol [27] — a common industrial protocol for legacy SCADA systems — is
presented with performance results. Second, this paper presents a
comprehensive review of the current landscape of research in legacy SCADA
system protection. It compares the data diode and detect-and-respond
approaches, discussing their benefits and limitations, and provides practical
guidelines for their application.

The rest of this paper is organized as follows. In the next section, legacy
SCADA systems and false command attacks against them are discussed. The data
diode strategy and the detect-and-respond strategy are presented in Section 3
and Section 4 respectively. Finally, Section 5 concludes with a comparison of
the two strategies.

##  2 False Command Attacks against Legacy SCADA Systems

A typical SCADA system, as depicted in Figure 1, consists of PLCs and RTUs in
the older versions and IEDs (Intelligent Electronic Devices) in the newer
versions as the basic units for deployment in power substations or remote
sites (for monitoring transmission lines) at different geographic locations.
Each of these field devices has interfaces to sensors and actuators used to
monitor and control equipment in a power delivery system. The field devices in
a substation or remote site form a local area network, known as the field
network, and are usually connected together over a broadcast medium to a sub-
master or data concentrator, which in turn is connected to the MTU (Master
Terminal Unit) or master station at the main control center through leased
lines over a telecom operator’s network. While various topologies are in use
for connecting field devices with the sub-master, a broadcast channel — such
as EIA-485 serial ports in the party-line mode over a pilot cable (as shown in
Figure 2) or DNP3 in the multi-drop or data concentrator mode111Earlier SCADA
systems were designed based on proprietary protocols. DNP3 is a standard
adopted in newer SCADA systems for connecting RTUs and IEDs with an MTU. — is
typically used in SCADA systems.

Figure 1: A typical legacy SCADA system and the possibility of false command
attacks Figure 2: EIA-485 serial ports connected in the party-line mode

Despite cost efficiency achieved in cable layout and maintenance, the use of
broadcast channels also eases insider attacks from compromised devices. For
example, a compromised RTU can pose the MTU to issue a forged command to
another RTU or PLC, causing the latter to behave abnormally. Experiments have
been repeatedly reported to demonstrate the possibility of using off-the-shelf
protocol analyzer software to intercept control messages and inject false
commands in some legacy SCADA systems [13], with some showing the possibility
to trip a circuit breaker maliciously. In a few cases, even though the circuit
breaker signaled the master station that it had opened, the master station did
not respond as it had not instructed the circuit breaker to open.

This type of attacks was inconceivable in the original design of SCADA
systems, and SCADA devices have little resource to defend against them.
Obscurity in system design, command formats and operation, combined with
physical isolation, have long been the main and possibly the only strategy for
securing legacy SCADA systems. However, the effectiveness of obscurity may
have become unreasonable. For instance, it has been demonstrated that fuzzing
can effectively discover or recover unknown SCADA commands of a SCADA device
[6]. Physical break-in’s to power substations have been occasionally reported
[28]. Even worse, obscurity and isolation are no longer effective in the
envisioned smart grid, wherein SCADA systems have to coexist and possibly
communicate with other relatively more open networks, in order to implement
two-way flow of information and energy. Operation in isolation could be an
overly strong assumption for SCADA systems to operate nowadays against the
smart grid backdrop.

Exploitation of software vulnerabilities on field device computing platforms
is a necessary, key step to compromise field devices in a SCADA system. This
is the only possible way which allows an attacker to install his code on a
target machine and spread it to others. The belief that embedded processors
used in field devices have relatively less exploitable software
vulnerabilities or it is difficult to compromise an embedded system has become
untenable, as demonstrated by the case of the Stuxnet worm discovered in 2010,
which has a rootkit to infect PLCs over a proprietary SCADA system and damaged
a number of centrifuge equipment in an Iranian nuclear facility [17, 23].
Subsequent generations of Stuxnet were also discovered. In fact, it has been
demonstrated that with crafted instructions and data, compromising an embedded
processor is within reach to attackers in general. These compromises could
normally go undetected by the MTU since, as demonstrated by the Stuxnet worm,
a compromised device could play man-in-the-middle to conceal all malicious
activities from the MTU.

In addition, should a physical break-in to a substation or remote site be
possible, an attacker could simply tap in his own attacking devices directly
onto the SCADA network to manipulate other innocent devices. With the
increasing connectivity with other systems in the smart grid, this threat is
particularly real since these newer smart grid systems typically allow more
open access to general users. For instance, a smart meter may be accessible to
a household user’s computer for reading meter data and setting consumption
patterns and alerts. Similarly, an electric vehicle (EV) charging station in a
public car park could have a digital interface open for the general public for
functionalities like making reservation or checking charging status of an EV.

##  3 Data Diode Approach

A data diode is a unidirectional gateway, similar to a firewall, which sets a
digital barrier to enforce network perimeter control for a restricted network
(such as a SCADA system) and fend off unwanted accesses from the less secure
networks it is connected to (such as smart grid systems). Yet a data diode
provides a stronger security guarantee than a firewall since strict one-way
communication — from the restricted network to the less secure network only —
is enforced by a certain physical law rather than digital logic, with little
chance of reverse communication. Data diodes are often built using fibre
optics coupler or transceivers, through the removal of the transmitter
component from one side of the communication and the respective receiver
component from the opposite side.222Although different hardware
implementations of a data diode exist, supporting different physical channels
(e.g. RS-232, EIA-485, USB, Ethernet), most implementations make use of
optical couplers to guarantee physical isolation. This makes it physically
impossible to compromise such devices to achieve reverse connectivity.
Moreover, they usually do not contain firmware, thus requiring minimal or no
configuration at all, or have minimal software supported by micro-kernels that
can be formally verified. Whereas, firewalls are often prone to configuration
mistakes and relatively accessible for exploit by skilful attackers. While
firmware upgrade is regularly needed in firewall maintenance, patching is
seldom needed for data diode deployment. Finally, data diodes are the only
devices receiving the EAL7 (Evaluation Assurance Level 7), the highest grade
in the Common Criteria [9] (an international standard evaluating the level of
security of equipment).

Figure 3: Deployment scenario of the data diode approach Figure 4: TCP message
flow in a unidirectional gateway [10]

Data diodes allow organisations to retrieve valuable data generated at the
process level from a critical infrastructure for consumption by a wider group
of users in a relatively more open system while assuring the isolation and
integrity of the critical infrastructure. As shown in Figure 3, a data diode
allows data acquired by SCADA field devices to be pushed from the SCADA system
so that they can be combined with other datasets captured by smart grid
systems like AMI and EV systems which poll the physical conditions of the same
electric power grid, in order to give a more holistic and precise picture of
the conditions of the electric power grid for more accurate data analysis and
hence resource planning. The correlation of these different datasets can also
provide valuable insights for fault identification and predictive maintenance.
Should the analysis lead to desired actions to be carried out in the SCADA
system, the feedback will be through human communications. While existence of
compromised nodes is possible in the smart grid systems, the data diode
guarantees that they cannot send in false commands to field devices in the
legacy SCADA system or infect/compromise them.

Despite similarities in the isolation mechanism, commercially available data
diode solutions differ in supported services and protocols. In order to
support TCP/IP-based SCADA protocols, such as MODBUS/TCP and DNP3, data diodes
usually have to make use of additional software components for each side of
the unidirectional link to emulate the bidirectional message flow for the
three-way handshake and acknowledgements needed in a typical TCP session. As
demonstrated by [10] and shown in Figure 4, the software components include an
application proxy and a protocol breaker. The application proxy emulates the
TCP server on the sender side to respond to the SCADA device (TCP client) with
TCP connection-oriented messages and acknowledgements while forwarding
messages from the TCP client to the unidirectional link. Similarly, the
application proxy emulates the TCP client on the receiver side. But it does
not forward any message from the TCP server on the receiver side to the
unidirectional link. Note that only TCP connection messages sent from the
SCADA system to the smart grid system are allowed by the data diode. The
protocol breaker acts as a middleware for packet encapsulation and possibly
applying encryption and forward error correction (FEC) to data transferred
over the unidirectional link. FEC is especially important to ensure correct
data delivery for the noisy environment of typical SCADA systems.

##  4 Detect-and-Respond Approach

While data diodes provide strong security and isolation/decoupling assurance
for legacy SCADA systems, sometimes they are too restrictive for certain
application scenarios of the smart grid. Neither is it optimal to rely on
human communications for feedback to a SCADA system. There is a realistic need
for two-way flow of data between a SCADA system and a smart grid system.
Proposals such as [30] therefore emerged to add a reverse channel to data
diodes. But whether the advantages of a data diode over a typical firewall can
be preserved in such a modification is highly uncertain. More importantly, to
what degree that the security assurance of a data diode is undermined with the
addition of a reverse channel needs to be assessed carefully. In scenarios
requiring bidirectional data exchange between a SCADA system and a smart grid
system, it is therefore more reasonable to assume the existence of compromised
devices in the SCADA system [13, 16, 18, 12, 19, 22, 23] and devise mechanisms
to detect false commands [13, 16, 18, 19] and/or identify compromised nodes
[19, 22]. In general, a detect-and-respond strategy is preferred despite that
many of the proposed schemes in the literature merely cover attack detection.
Once a false command is detected, its impacts should be voided or neutralised
promptly, and ideally, in an automatic manner with minimum human intervention
required.

This paper presents a generic, high-level architectural framework to implement
the detect-and-respond strategy for legacy SCADA systems. An embodiment in the
form of a trusted protection agent is also given to illustrate typical steps
needed to neutralise the effects of false commands injected by compromised
field devices. The notion of the protection agent is similar to that of a
trust node in [12]. The difference is that the protection agent actively
neutralises the effects of false commands, whereas, the trust node only serves
as a trusted routing agent to selectively relay messages between field devices
and the master station. Since the framework is defined in a general setting,
it should be applicable to different types of SCADA protocols and provide a
basis for systematically crafting defence mechanisms fit for different SCADA
systems and field devices. Besides, there is flexibility for incorporating
different detection algorithms or mechanisms such as [13, 18] into the
framework. The framework is also complementary to and could be combined with
other approaches [1, 3, 7] for securing SCADA systems.

The underlying assumption for implementing the detect-and-respond strategy
with a protection agent is that the protection agent is well protected with
different protection mechanisms in place to implement the defence-in-depth
strategy so as to minimize the probability of its compromise. In practice,
there are various conventional techniques to achieve the security hardening of
the protection agent effectively, which will be discussed in Section 4.1 and
4.4. In the worst case, if a physical break-in to a power substation happens,
the protection agent could be compromised. But the question is, if an attacker
successfully breaks in to a power station, he could actually tap in his own
device to launch any type of attacks. The only reason for him to compromise
the protection agent is to stop the protection agent from alerting the master
station in order to conceal his attacks. That is, even for physical break-
in’s, the protection agent would only increase the difficulty for an attacker
to launch attacks sneakily.

###  4.1 Protection Agent

As depicted in Figure 5, a protection agent is installed as an add-on device
in each field network of a SCADA system, which can be made up of PLCs, RTUs or
IEDs. Leveraging on the broadcast medium typically found in most field
networks, the protection agent — as a network sniffer — monitors commands
issued to all the field devices on the network to detect malicious activities.
As a safe assumption, the protection agent is generally a much more powerful
machine than typical field devices, given that the underlying processor used
in the protection agent could be generations away from those used in the field
device of a legacy SCADA system. In addition, compared to the low-bandwidth
physical channel used by these field devices (typically, in the range of
1.2-19.2 kbps [27, 20, 29]), the protection agent can easily be equipped with
a wireless link of much higher bandwidth to the MTU or master station. Note
that the design of the protection agent does not preclude other communication
channels such as a fiber link.333A wireless channel is assumed here simply
because it is one of the common approaches for adding new communication
channels between a remote substation and a control centre. We can therefore
assume that the protection agent has a faster (with a higher bandwidth and a
lower latency) and typically more reliable communication channel (for most of
the time) with the MTU than the field devices. On the basis of a more powerful
machine with a faster communication channel to the MTU, security hardening on
the protection agent is much easier. We assume that the protection agent has a
secured, authenticated channel with the master station. Multi-factor entity
authentication (for example, those based on pre-shared secret keys stored in a
tamper-resistant device, physical unclonable functions [25, 15], or even new
approaches [8] etc.) could be adopted to implement this authenticated channel
to strengthen its security assurance. Compared to the field device platforms
with little resources for the implementation of cryptographic defence, the
protection agent is more ready to implement cryptographic algorithms and
protocols, and other security mechanisms requiring more resources (such as
firewall or remote code attestation). In short, the protection agent can be
viewed as a trusted proxy for the MTU.

Figure 5: A SCADA system with protection agents installed

On the other hand, the protection agent can be seen as a reliable incognito
for the MTU, monitoring what is happening in the field network. It is assumed
that the protection agent can interpret the underlying protocol messages (as
coded in its design) and can sniff messages in the field network. As discussed
in Section 2, devices in the same field network are usually connected over a
broadcast channel, meaning that such traffic sniffing is a practical
assumption. Difference in topology would only affect the number devices that
can be eavesdropped. With the protection agent monitoring the traffic in
place, the previously observed problem of some legacy SCADA systems that the
MTU is not aware of a circuit breaker having been tripped by an attacker since
it has not initiated the tripping [11] would not happen if a protection agent
is installed in the field network. When the protection agent observes the
tripping command in the field network but does not receive the same command
through the trusted communication channel shared with the MTU, it would report
the tripping event back to the MTU, which would then be aware of a possible
intrusion. While there is possibility that an attacker might physically remove
the protection agent from a field network, security mechanisms could be
implemented on the protection agent to detect any malicious removal. For
instance, the MTU can run a challenge-response verification protocol with the
protection agent by sending a sequence of specially crafted random messages
(i.e. nonces) — destined at a void device identity — to the protection agent
via the field network; if the protection agent is disconnected from the field
network, it would not be able to receive these messages to respond to the
MTU’s challenge correctly. Besides, remote code attestation could be
implemented to provide the assurance that the software being executed on the
protection agent has not been tampered with. It should be emphasized that a
protection agent offers more resources and flexibility than a typical field
device like an RTU or PLC for implementing preventive security measures and
intrusion detection mechanisms.

###  4.2 Detect-and-Respond Defence of Protection Agent

The detect-and-respond mechanism of the protection agent can simply be
implemented as a finite state machine as shown in Figure 6. The basic idea is
as follows:

  1. 1.

Whenever the MTU issues a SCADA command to any field device, it also sends an
authenticated message of the same command (protected by a certain
cryptographic algorithm such as AES-CCM) to the corresponding protection agent
which is connected to the same field network as the concerned field device is
in.

  2. 2.

The protection agent listens or eavesdrops in the field network, sniffing all
SCADA commands issued to the field devices in the same field network, and
verifies the authenticity and integrity of each of these SCADA commands by
comparing them with the authenticated commands directly received from the MTU
in the authenticated channel shared between the protection agent and the MTU.

  3. 3.

For any forged or false command detected (say, by comparing the command
received in the field network and that received in the secured channel), the
protection agent, possibly after verifying with the MTU, issues a SCADA
command to the affected field device to reverse the action caused by the false
command to cancel out any undesirable action initiated by the attacker. This
is called the “fight-back” or neutralization mechanism as the protection agent
takes action — in response to a detected malicious command — to correct it.

Figure 6: The state machine diagram of a SCADA protection agent State |  Description |  Tasks
---|---|---
_Queue_ |  State to queue newly received SCADA and authenticated commands |  • read commands from the receiving port • queue the command to the SCADA or authenticated queue accordingly

_Listen_ |  Idle state when the SCADA queue is empty |  • check if the SCADA queue is non-empty and trigger the “Start” state when the queue is non-empty

_Start_ |  State to tell between a new SCADA command received or an old SCADA command pending the completion and confirmation of corrective actions taken
|  • check whether a new SCADA command arrives and trigger command
verification if positive
_Check Rule_ |  State to check the local rule set to see if the received SCADA command is illegitimate and violates the prescribed rules |  • evaluate the SCADA command against the local rule set • if the SCADA does not pass any of the rules, trigger the correction process. Otherwise, check the authenticity of the SCADA command

_Verify Command_ |  State to check whether the received SCADA command is really from the MTU through the use of the authenticated channel |  • if the SCADA command has a matched authenticated command received in the authenticated queue, issue a pass, otherwise, request the MTU to verify through the authenticated channel and check again • if the SCADA command fails, trigger the correction process

_Fight-back_ |  State to correct or reverse the actions caused by a malicious command |  • look up from a pre-set table for the corrective actions needed for a particular SCADA command • issue the listed SCADA commands to the affected RTUs to reverse the actions of the malicious command

_Verify Correction_ |  State to confirm that the correction is in effect |  • read the status of the affected RTUs to confirm that the corrective actions have been applied

Table 1: Details of the protection agent implementation as a state machine

In principle, the neutralization mechanism could invalidate or void out forged
commands, restoring the field device to the original state. But the degree of
neutralization or residual effect of a false command would depend on the
actual implementation of the logic and the SCADA command set of a field
device. This defence approach shares some similarities with the fight-back
mechanism of OSPF (Open Shortest Path First) — a link state routing protocol
used in the Internet — through which an innocent router could publicly
renounce a malicious route update forged by an attacker [21].

In case of missing commands, the protection agent can request the MTU to
resend a command over the secured, authenticated channel for verification.
Besides, the implementation of the protection agent could be further extended
by including additional false command detection mechanisms beyond comparison
with an authenticated copy of a legitimate command. For example, the detection
mechanisms of [13, 18] can possibly be used by the protection agent to trigger
neutralization, preferably after confirmation by the MTU. However, in order to
respond correctly to any maliciously injected commands, the deployed detection
mechanism should provide sufficient details to help identify the commands
falsely injected by the attacker.

In some cases, a forged or malicious command could be immediately detected in
the local field network without relying on authenticated messages from the
MTU. For example, the remote software update of a field device is normally
prohibited by most utility operators. However, in some SCADA systems composed
of RTUs, the denial of a remote software update request is implemented on the
MTU side only, while the RTUs in the field network usually have no mechanism
to deny a software update request or distinguish whether it is initiated by
the MTU or an intruding device. In other words, a compromised RTU or an
intruding attacker device could still initiate a remote software update at any
RTU in the same field network, which will not be denied by the latter. This
flaw would greatly facilitate the spread of worms or malicious instruction
sequences over a field network. In a typical SCADA deployment, a firewall
usually only safeguards a field network from external attacks and would not be
able to stop such an insider threat since the attack is launched from within
the field network by a compromised field device or an intruding device
connected to the field network. In contrast, the protection agent could
possibly halt the malicious software update. A local rule set can be
implemented on the protection agent, explicitly specifying that only manual
update is allowed. When the protection agent detects an automatic software
update command, it can immediately halt the update by issuing another command,
without having to check with the MTU.

The same technique can be used for other clearly harmful actions. For
instance, the protection agent can enforce that a certain range of parameters
is prohibited in some SCADA commands. With the local rule on protection
agents, the damage of the centrifuge equipment caused by the Stuxnet worm
could be avoided, since the command with parameters causing excessive spin
speed could be invalidated by the protection agent. Similarly, the protection
agent can be configured to eliminate or invalidate set point commands — which
are used in typical SCADA systems to preset the thresholds on certain measured
system variables (such as voltages or phase angles at certain point of a power
grid) for triggering protective actions like tripping a circuit breaker — with
harmful parameters.

In details, two command queues are implemented in the protection agent, which
respectively stores SCADA commands received in the field network and
authenticated commands received through the secured, authenticated channel
between the MTU and the protection agent. When the SCADA command queue is
empty, the protection agent is at the “Listen” state waiting for new SCADA
commands. The arrival of a new SCADA command will trigger the protection agent
to verify the authenticity of the requested action and reverse it in case it
is a fake command. A list of tasks to be implemented at different states of
the protection agent is shown in Table 1.

The detect-and-respond strategy deviates from intuition and standard
techniques used in securing a communication network. Whereas existing schemes
would suggest filtering all bogus messages injected by an attacker, the
proposed mechanism aims to tolerate the intrusion for a while if the resulting
malicious actions are not critically harmful and then correct or neutralize
the malicious actions. For critical actions which are usually banned by norm,
the local rule set in the protection agent would stop them immediately from
onset. Since the detect-and-respond approach favors local, distributed
defence, it is more scalable than centralized defence mechanisms.

###  4.3 Example Implementation with Siemens Sinaut 8FW Protocol

Telegram Type |  Priority to neutralize |  Protection agent’s actions to neutralize
---|---|---
• control (Type 64) • replace command (Type 195) |  High |  • Topple the command • Report the action back to MTU and wait for acknowledgement. If negative acknowledgement is received, topple the command back.

• analogue/digital set point (Type 65-67/68-70) • modification of threshold value limit (Type 205) • modification of smoothing factor (Type 206) • remote parameterization (Type 212) |  High |  • Temporarily store a copy of the suspected command • Apply the latest confirmed parameter setting stored in the protection agent to form a command • Use replace command (Type 195) to switch the parameter setting back • Report the action back to MTU and wait for acknowledgement. If negative acknowledgement is received, apply the stored suspected command, otherwise, erase stored command

• start-up request (start up/restart) (Type 211) • switch on/off recipient in
master station (Type 203) • switch off record transfer from/to station (Type
204)
|  Medium |  • Report to the MTU and wait for confirmation. If confirmed, topple the command.

• switch on/off for temporal lists (Type 201-202) • synchronization of fine
time (type 207) • setting of minutes (Type 208) • setting of calendar (Type
209) • switch on/off addresses in the lists (Type 210) • 4-byte-storage
interrogation control (Type 214) • interrogation command ZFBIT and STOP-cause
(Type 215-222)
|  Low |  • Report to the MTU and wait for confirmation. If confirmed, topple the command or restore the stored parameters.
• check command (Type 192) • check command (type 192) • message repeat request
/ TFK-acknowledge (Type 193) • start acknowledgement (Type 194) • single/group
interrogation command (Type 196-197) • multiple request (Type 198-200) •
matrix-check command (Type 213)
|  Low |  • Neutralization is not necessary.
Table 2: Implementation of the detect-and-respond defence on Siemens Sinaut
8FW protocol

Table 2 illustrates how the detect-and-respond defence strategy can be
implemented with respect to the command set of the Siemens Sinaut 8FW protocol
[27], a popular industrial protocol commonly used in legacy SCADA systems. The
Sinaut 8FW protocol was the standard protocol used by Siemens devices and
systems for communicating control and monitoring messages between MTU systems
and RTU devices before being replaced by IEC 60870-5-101. It was broadly
supported by devices provided by other manufacturers like ABB and GE. While
the principle of the detect-and-respond strategy can be equally applied to
newer protocols like IEC 60870-5-101 and 60870-5-104, its implementation with
these protocols is outside the scope of this paper, partly because it is
possible to implement authentication mechanisms in these protocol [26]. In
contrast, the resource constraints of devices running the Sinaut 8FW protocol
preclude the possibility of implementing any security mechanism despite that
the protocol is still actively used in a non-negligible fraction of systems.
In other words, it is more critical to investigate add-on protection for the
Sinaut 8FW protocol over others. Each command is enclosed in a control message
in the form of a telegram. Table 2 only shows telegram types sent in the
control direction (from the MTU to field network), with other telegram types
in the monitoring direction (from the field network to the MTU) skipped since
these telegram types are largely for messages sent to the MTU.

False commands that may have critical impact on the functioning of a SCADA
system are neutralized first and then verified with the MTU, whereas, the less
critical ones are corrected upon confirmation from the MTU. Most of the
neutralization actions can be readily implemented through the replace command
telegram. For commands which switch on/off a certain feature or function, the
neutralization can simply be done by toppling the command in the oppositive
direction with respect to the false command. For commands which involve
updating of parameters like thresholds or set points to trigger preventive
actions, the protection agent stores the latest version of all the parameters
of a field device (with parameters of different field devices stored in
different tables) and apply relevant ones to form a replace command when
necessary to revert the parameters affected by a false command.

Experimentation was carried out on an Intel 2.5GHz Quad Core Celeron CPU (with
8GB RAM) — which simulates the protection agent — to estimate the response
time of the protection agent to issue a neutralization command or telegram for
different types of false commands. The protection agent is connected to a
server (which simulates the master station) through a WiFi link. On the other
side, the protection agent is connected to another single board computer
through a RS232 serial port (set at a baud rate of 19200), which simulates a
compromised field device (in Scenario 1) or a master station (in Scenario 2)
to issue commands to the protection agent. Two types of response time are
measured corresponding to two different scenarios. In the first scenario (i.e.
Scenario 1), the protection agent is set to receive no message from the master
station and the compromised field device (simulated by the single board
computer) injects a false command to the serial port to trigger the protection
agent to neutralize the command. The response time needed to issue a
neutralization command after the injection of a false command is measured. In
the second scenario (i.e. Scenario 2), the single board computer simulates an
authentic command from the master station. That is, the injected command is
authentic but the protection agent mistakenly considers it as a false command.
The protection agent first issues a neutralization command and then queries
the master station which always returns a negative acknowledgement. That is,
the protection agent has to switch back the command and cancel the effects of
the neutralization command. The response time for the protection agent to
issue the second command after the injection of the first command by the
single board computer is measured.

The experimental measurements are presented in Figure 7. The average response
time required for the protection agent to look up the parameter for a
particular field device identity and issue a neutralization command or
telegram for different types of false commands (at high priority) is 45.52 ms
with a standard deviation of 9.28 ms. The average response time required for
the protection agent to switch back the command for the second scenario is
175.32 ms with a standard deviation of 27.5 ms. Compared to the maximum
tolerable delay for SCADA transactions, which is 0.54s [5], this processing
delay is acceptable (respectively, 8.4% and 32.4% of the maximum tolerable
delay).

Figure 7: Response time of the protection agent for: (a) Scenario 1:
Neutralization of a malicious command; (b) Scenario 2: Ratification of false
neutralization.

###  4.4 Security Analysis

The key assumption for the detect-and-respond mechanism based on a protection
agent is that the protection agent is trusted and has a reliable communication
channel to the master station. This should be a reasonable assumption in
practice.

First, it is considerably harder to compromise a protection agent than a
typical field device. But it is easier to detect any compromise of the
protection agent. As discussed in Section 4.1, since the protection agent is
based on a more powerful computing platform compared to a field device,
various techniques — such as remote code attestation to ensure that a correct
version of software is executed on the protection agent and challenge-response
verification to ensure that the protection agent is not disconnected from the
field network — can be readily applied to strengthen the security assurance of
the protection agent and detect any compromise. Besides, if a protection agent
is compromised, the attacker can cause no more harm than what he can achieve
with a compromised field device when no protection agent is deployed. Since
compromising a protection agent is more difficult than compromising a field
device, adding a protection agent would make the job of an attacker more
difficult and strengthen system security.

Second, the more powerful platform used for a protection agent (compared to a
field device) enables the implementation of common cryptographic primitives,
thereby allowing the use of standard protocols such as the TLS (Transport
Layer Security) to secure the communication channel between a protection agent
and the master station. The confidentiality and authenticity of each message
sent over the channel is thus assured. An out-of-band wireless channel is
assumed for the communication between a protection agent and the master
station because it is the most cost-effective way, and a popular means, to add
a new communication channel to a power substation. To address the reliability
issues associated with a wireless channel, the protection agent can request
the master station to resend any missed command or explicitly
acknowledge/confirm any command it has sent through the field network. Since
such a channel usually has a higher bandwidth and a lower latency compared to
the field network, the processing delay is usually reasonable. As demonstrated
by the experimental results, the latency for the confirmation required for a
missed command (Scenario 2) seems practically acceptable. Alternatively, an
in-band, authenticated communication channel [7] or a more reliable
communication channel such as a fiber link could be used.

###  4.5 Cost and Benefit Analysis

The detect-and-respond strategy embodied by the protection agent offers a
number of advantages as follows.

  1. 1.

The protection mechanism is non-intrusive and truly add-on while strong
cryptographic mechanisms can be adopted to protect the communications between
a field network and the MTU (via a protection agent), without replacing any
field devices or modifying their code. No laying of new cables is needed, as
wireless links like mobile cellular networks could be used between protection
agents and the MTU.

  2. 2.

Compared to the bump-in-the-wire approach [1, 14] which adds a new
cryptographic device per field device, a smaller number of protection agents
are required, with one required for each field network in most cases. A
typical field network could have at least 30 devices, whereas, the maximum
number of field devices per network is limited by the protocol’s address
space. As an example, up to 128 and 65535 devices per network are allowed for
Sinaut 8FW and IEC60870-5-104 respectively. Hence, compared with the bump-in-
the-wire approach, the detect-and-respond approach can reduce the number of
cryptographic devices by a factor between 1/128 and 1/30. The minimum number
of protection agents needed for a SCADA system is roughly equal to the number
of its field networks. For instance, less than 100 protection agents are
needed to secure the SCADA system of Singapore’s 22kV distribution grid (with
$\sim 10,000$ substations and the IEDs connected in multiple field networks in
a ring topology), whereas, 1-2 protection agents suffice to cover that of its
66kV distribution grid (with $\sim 100$ substations and the field devices
connected through a mesh topology). In other words, there are about 100 field
networks (with each in the ring topology) for the SCADA system of the 22kV
distribution grid, and only one field network in the mesh topology for the
SCADA system of the 66kV distribution grid.

  3. 3.

The protection agent would not become a bottleneck since additional protection
agents can be deployed to a given field network with many field devices (say,
more than 300 devices). In such cases, the set of field devices in a network
can be grouped into partitions based on their identities and multiple
protection agents could be installed in the network with each responsible for
a distinct partition. Since any number of protection agents can be added to a
field network and the field devices need not be aware of the presence of a
protection agent, the solution is scalable.

  4. 4.

The detect-and-respond strategy is particularly effective for defending
against insider attacks, which existing solutions like firewalls often cannot
withhold. A firewall normally cannot filter messages sent from a field device
located behind it or forged messages from outside if no authentication
mechanism is in place. Unlike a firewall, the protection agent does not
present a single point of failure. If it is down, the field network would
still operate as usual, which is not the case for a firewall.

##  5 Conclusions

The instrumentation and control of a power grid is usually carried out by a
SCADA system which is a distributed network of cyber-physical devices taking
measurements and issuing commands at different parts of a power grid.
Obscurity and operation in isolation have long been the security strategy of
SCADA systems. However, this is no longer a reasonable assumption for SCADA
systems in the smart grid context with the need of connectivity with other
relatively open networks. False command injection is a real threat to legacy
SCADA systems. While effective security mechanisms and algorithms for command
authentication are largely an overkill for implementation on field devices in
legacy SCADA systems, these devices would normally take decades to be phased
out as they are closely integrated with the power equipment. This paper
discusses and compares two different approaches, namely, the data diode
strategy and the detect-and-respond strategy, to secure legacy SCADA systems
for safe integration with other smart grid systems. A detailed comparison of
the two approaches can be found in Table 3.

|  Data diode |  Detect-and-respond
---|---|---
Security assurance |  Highest (EAL7) |  Medium to High
Applicable cases |  Limited range |  Wide range
Pros |  • Isolation preserved with a high level of security • No modifications on field devices required • Highly scalable, with only one data diode required per system |  • Flexible to incorporate other techniques for attack detection and neutralization • Allow bidirectional data exchange • No modification on field devices required • Scalable
Cons |  • Only allow unidirectional data flow from SCADA systems to other systems • Little flexibility |  • More complex design required to maintain security • Design strongly dependent on the SCADA protocols in use
Table 3: Comparison between the data diode and detect-and-respond strategy

The detect-and-respond strategy proposed in this paper presents a number of
advantages for securing legacy SCADA systems, including scalability and
usability for a wide range of smart grid scenarios. The proposed framework is
also generally applicable to different SCADA protocols and systems, while a
concrete instantiation on Siemens Sinaut 8FW protocol is presented in this
paper. While the data diode strategy offers the highest level of security
guarantee, it can only be applied to a restricted number of use cases wherein
unidirectional data exchange suffices. In contrast, the detect-and-respond
strategy is a more flexible approach which can be applied in almost all
scenarios but generally offer a lower level of security guarantee and is more
complex to design.

## References

  * [1] C. Alcaraz, I. Agudo, D. Nuñez, and J. López.  Managing incidents in smart grids à la cloud.  In Proccedings of IEEE CloudCom 2011, pages 527–531, December 2011.
  * [2] C. Alcaraz, J. López, and S. D. Wolthusen.  Policy enforcement system for secure interoperable control in distributed smart grid systems.  J. Netw. Comput. Appl., 59:301–314, 2016.
  * [3] C. Alcaraz, J. López, J. Zhou, and R. Roman.  Secure SCADA framework for the protection of energy control systems.  Concurr. Comput. Pract. Exp., 23(12):1431–1442, 2011.
  * [4] R. Amoah and E. Camtepe, S. amd Foo.  Securing DNP3 broadcast communications in SCADA systems.  IEEE Transactions on Industrial Informatics, 12(4):1474–1485, July 2016.
  * [5] C. L. Bowen, T. K. Buennemeyer, and R. W. Thomas.  Next generation SCADA security: Best practices and client puzzles.  In Proceedings of the 6th Annual IEEE SMC Information Assurance Workshop, June 2005.
  * [6] S. Bratus, A Hansen, and A. Shubina.  LZfuzz: A fast compression-based fuzzer for poorly documented protocols.  Darmouth Computer Science Technical Report TR2008-634, September 2008\.
  * [7] J. H. Castellanos, D. Antonioli, M. O. Tippenhauer, and M. Ochoa.  Legacy-compliant data authentication for industrial control system traffic.  In proc. ACNS’17, Springer-Verlag LNCS vol. 10355, pages 665–685, July 2017.
  * [8] A. C-F. Chan, J. W. Wong, J. Zhou, and J. C. M. Teo.  Scalable two-factor authentication using historical data.  In proc. ESORICS’16, Springer-Verlag LNCS vol. 9878, pages 91–110, September 2016.
  * [9] Common Criteria.  Common methodology for information technology security evaluation, Rev. 5 (ISO/IEC 18045), April 2017.
  * [10] M. B. de Freita, R. T. Cruz, and P. Simoes.  SDN-enabled virtual data diode.  In proc. SECPRE’18, CyberICPS’18, Springer-Verlag LNCS vol. 11387, pages 102–118, January 2019.
  * [11] A. Hahn.  Cyber security of the smart grid: Attack exposure analysis, detection algorithms, and testbed evaluation.  Iowa State University Graduate Theses and Dissertations, 2013.
  * [12] Md. M. Hasan and H. T. Mouftah.  Optimization of trust node assignment for securing routes in smart grid SCADA networks.  IEEE Systems Journal, 13(2):1505–1513, September 2018.
  * [13] Y. He, J. Mendis, and J. Wei.  Real-time detection of false data injection attacks in smart grid: A deep learning-based intelligent mechanism.  IEEE Transactions on Smart Grid, 8(5):2505–2516, May 2017.
  * [14] E. Heine, H. Khurana, and T. Yardley.  Exploring convergence for SCADA networks.  In proc. ISGT’11, January 2011.
  * [15] C. Herder, M-D. M. Yu, F. Koushanfar, and S. Devadas.  Physical unclonable functions and applications: A tutorial.  Proceedings of the IEEE, 102(8):1126–1141, August 2014\.
  * [16] A. Humayed, J. Lin, F. Li, and B. Luo.  Cyber-physical systems security — a survey.  IEEE Internet of Things Journal, 4(6):1802–1831, December 2017\.
  * [17] R. Langner.  Stuxnet: Dissecting a cyberwarfare weapon.  IEEE Security & Privacy, 9(3):49–51, May 2011.
  * [18] H. Lin, A. Slagell, Z. T. Kalbarczyk, P. W. Sauer, and R. K. Iyer.  Runtime semantic security analysis to detect and mitigate control-related attacks in power grids.  IEEE Transactions on Smart Grid, 9(1):163–178, March 2016.
  * [19] S. McLaughlin, C. Konstantinou, X. Wang, L. Davi, A-R. Sadeghi, and R. Karri.  The cybersecurity landscape in industrial control systems.  Proceedings of the IEEE, 104(5):1039–1057, March 2016.
  * [20] Mobus.  Mobus over serial line — specification and implementation guide v 1.02.  Mobus Docummentation, December 2006.
  * [21] G. Nakibly, A. Kirshon, D. Gonikman, and D. Boneh.  Persistent OSPF attacks.  In proc. NDSS’12, February 2012.
  * [22] S. Nazir, S. Patel, and D. Patel.  Assessing and augmenting SCADA cyber security: A survey of techniques.  Computers & Security, 70:436–454, September 2017.
  * [23] A Nourian and S. Madnick.  A systems theoretic approach to the security threats in cyber physical systems applied to Stuxnet.  IEEE Transactions on Dependable and Secure Computing, 15(1):2–13, February 2018.
  * [24] H. Okhravi and F. T. Sheldon.  Data diodes in support of trustworthy cyber infrastructure.  In proc. CSIIRW’10, pages 1–4, April 2010.
  * [25] R. Pappu, B. Recht, J. Taylor, and N. Gershenfeld.  Physical one-way functions.  Science, 297:2026–2030, 2002.
  * [26] D. S. Pidikiti, R. Kalluri, R. K. S. Kumar, and B. S. Bindhumadhava.  SCADA communication protocols: vulnerabilities, attacks and possible mitigations.  CSIT, 1:135–141, 2013.
  * [27] Siemens.  Sinaut st-7 station control system — system manual.  SINAUT Docummentation, Edition 05/2001, May 2001.
  * [28] K. Tweed.  Bulletproofing the grid.  IEEE Spectrum, April 2014.
  * [29] A. K. Wright, J. A. Jinast, and J. McCarty.  Low-latency cryptographic protection for SCADA communications.  In proc. ACNS 2004, June 2004.
  * [30] J-H. Yun, Y. Chang, Kim K-H., and W. Kim.  Security validation for data diode with reverse channel.  In proc. CRITIS’16, October 2016.


#  Indirect Point Cloud Registration:
Aligning Distance Fields using a
Pseudo Third Point Set

Yijun Yuan and Andreas Nüchter All authors are with Informatics VII : Robotics
and Telematics, University of Würzburg {yijun.yuan|andreas. nuechter}@uni-
wuerzburg.de

###### Abstract

In recent years, implicit functions have drawn attention in the field of 3D
reconstruction and have successfully been applied with Deep Learning. However,
for incremental reconstruction, implicit function-based registrations have
been rarely explored. Inspired by the high precision of deep learning global
feature registration, we propose to combine this with distance fields. We
generalize the algorithm to a non-Deep Learning setting while retaining the
accuracy. Our algorithm is more accurate than conventional models while,
without any training, it achieves a competitive performance and faster speed,
compared to Deep Learning-based registration models. The implementation is
available on github111https://github.com/Jarrome/IFR for the research
community.

###### Index Terms:

Localization; Mapping; SLAM

##  I Introduction

During the fast development of artificial intelligence, perception always has
been playing an important role as it is the most fundamental component for
other tasks. In the field of perception, 3D laser scanners producing 3D point
clouds are the most direct and accurate tools to perceive the geometry of the
environment of a robotic system. Reconstruction, detection, tracking, etc.,
are typical tasks of a perception system.

3D reconstruction, with its high potential for commercial applications, has
recently received a lot of attention. Major contributions in this field
include methods using Truncated Signed Distance Field (TSDF) based algorithms
[1]. By using continuous implicit functions, shapes can be represented in
arbitrary resolution with high quality. To build reconstructions
incrementally, frame-to-frame pose transformations are required. Here, the
Point Cloud Registration (PCR) algorithm plays an important role. The
performance of the feature extraction and association strongly affects the
performance of the registration algorithm [2].

For the 3D reconstruction application, the point-to-implicit technique is
commonly used because it shows high utility for its capability to seamlessly
couple registration into the reconstruction framework [3]. By minimizing the
total energy of one point cloud on the field of a given point cloud, the
transformation is optimized. However, this class of registration requires to
iteratively fit one point cloud in the distance field of the other, which is
in-efficient. The seminal work by M. Slavcheva proposes an implicit-to-
implicit algorithm and improves the accuracy of registrations [4]. However,
this method requires discretizing the field into dense voxels of distance
values, which represents the function with volumes. The advantage of a dense
representation is that it provides voxel-to-voxel matched. But the
disadvantage is the inefficiency both in space and time. Thus, it is used only
for small object reconstruction. In this paper, we focus on a sparse solution
for implicit-to-implicit registration.

[width=.4]im/tmp

[width=.48]im/tmp2

Figure 1: Diagram of Pseudo-point set registration. $\varphi$ is a
transformation invariant function. $\mathbf{P}$ and $\mathbf{Q}$ in moon shape
are two frames to register. The dots $\mathbf{S}$ and
$\mathbf{S}^{{}^{\prime}}$ are the pseudo-points. While registration to solve
$\mathbf{G}^{-1}(\xi)$, only $\mathbf{S}^{{}^{\prime}}$ is used, $\mathbf{P}$
and $\mathbf{Q}$ remain fixed.

Since PCR is one of the most important functions in 3D perception, it also
draws more attention to the Deep Learning (DL) community. The DL research
around PCR can be classified into two categories: (a) feature matching
registration and (b) global feature registration.

Feature matching registrations rely on point detectors [5, 6, 7] and
descriptors [6, 7, 8, 2], then point matching is applied to solve the
transformation. Very large rotations can be handled by matching-based
registration [9]. Anyhow, they are usually considered as a coarse registration
to provide an initial guess for fine registration. In hybrid models [10, 11],
they assemble different registration modules to achieve a coarse-to-fine
result. In contrast to feature matching-based registrations, global feature
registrations are more direct. For example, a network model has been designed
as a black-box to take a pair of frames as input and output transformation
result [10]. More specific point cloud registrations using global features of
each point cloud have also been explored [12, 13, 14]. Those methods use a
global feature (vector) to represent each point cloud, which does not require
correspondences for registration.

We consider the global feature registration as highly interesting, because it
eases the computation of point matching between a new arrived keyframe and
batches of the previous $k$-frames. In addition, the global features are kept
for future uses. To compare with the conventional method, DL-based algorithms
require a large amount of time for training. When a new collection of data is
obtained, those DL-based models cannot directly be used because the unseen
data might not contain the same context as the trained dataset. Which results
in an arbitrary guess.

In this paper, we introduce a pseudo point-based method. Following the diagram
given in is shown in Fig. 1: Assume we have a function $\mathbf{\varphi}$ that
is transformation invariant with an arbitrary scan $\mathbf{P}$ and a pseudo
point set $\mathbf{S}$ as input. Thus $\varphi$ feature is unchanged when both
$\mathbf{P}$ and $\mathbf{S}$ apply the same transformation. Then a
transformation between the point cloud $\mathbf{P}$ and $\mathbf{Q}$ is
equivalent to transforming $\mathbf{S}^{\prime}$ (in
$\varphi({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbf{P}},\cdot)$)
in the inverse direction. Applying a similar registration framework to feature
metric class registrations (DL methods), our model achieves similar or even
better performance without any training. In addition, feature metric class
registrations are not compatible with real-world scenes [12, 14]. But our
method is applicable in both indoor and outdoor settings.

The contributions of this paper are:

  * •

We propose a new direction of registration that registers a third pseudo point
cloud while keeping the pairs of point clouds fixed. Thus the distance fields
are also fixed.

  * •

We propose the first implicit-to-implicit registration algorithm that does not
require volumetric representation of the fields. I.e., we register two
distance fields (or implicit-to-implicit) with sparse representations of the
field.

  * •

We generalize the feature-metric registration framework to a non-DL setting.

##  II Related Work

###  II-A Implicit-to-implicit registration

A Signed Distance Field (SDF) is an implicit function
$f:\mathbb{R}^{3}\rightarrow\mathbb{R}$ that maps a point
$\mathbf{p}\in\mathbb{R}^{3}$ to its closest surface location with signed
distance [15].

Point-to-implicit registrations project point clouds to a SDF to circumvent
the computation of correspondences. It shows a more robust registration
performance than ICP and is well-compatible with SDF-based 3D reconstruction
algorithms. But it suffers from the unreliability of sparse data and erroneous
distance fields. SDF-2-SDF, as the first implicit-to-implicit registration
algorithm, minimizes the energy between two dense volumetric SDFs, yielding a
larger convergence radius and more accurate performance [15]. However, limited
to the grid structure, SDF-2-SDF is restricted to be used in small settings.
To enable a large-scale scene reconstruction, SDF-TAR performs registration on
a fixed number of limited-extent volumes with parallel computation [16].

But the above methods rely on an explicit volumetric representation of the
implicit function. It is in-efficient to recompute the field in each
iteration. To this end, we propose to register with two fixed distance fields,
by introducing a third pseudo point cloud into the registration process.

###  II-B Feature Metric Registration

Feature Metric Registrations (FMRs) are the group of algorithms for global
feature registration with currently best performances. PointNetLK first
introduced a registration framework with the feature distance [12]. By
iteratively updating the intermediate transformation, PointNetLK achieves high
accuracy on synthetic datasets.

Then FMR contributes on top of it and a semi-supervised algorithm was proposed
in [13] to release the model from category labels. In addition, this algorithm
works well on indoor datasets. However, those two models are using an
approximate Jacobian, which means the step size should be carefully designed
for avoiding too large or small steps along the gradient.

Recently, [14] propose an analytical Jacobian for replacing the approximate
Jacobian in PointNetLK. The analytical Jacobian consists of a feature gradient
and warp Jacobian. They claim that the analytical Jacobian circumvents the
numerical limitations.

In FMRs, iterating relies on the transformation of the whole point cloud
$\mathbf{P}$, which is inefficient. In this paper, we propose to directly
update on the features.

##  III Background

###  III-A Feature Metric Registrations

Given two point clouds $\mathbf{P}_{S}\in\mathbb{R}^{N_{S}\times 3}$,
$\mathbf{P}_{\tau}\in\mathbb{R}^{N_{\tau}\times 3}$, registration aims at
finding the rigid transformation $\mathbf{G}(\xi)$ such that
$dist(\mathbf{G}(\xi)\cdot\mathbf{P}_{S},\mathbf{P}_{\tau})$ is minimized.
Here $\mathbf{G}(\xi)$ denotes the transformation with twist parameters $\xi$.

For feature metric registration, one minimizes the feature distance

$\displaystyle\arg\min_{\xi}\|\phi(\mathbf{G}(\xi)\cdot\mathbf{P}_{S})-\phi(\mathbf{P}_{\tau})\|_{2}^{2}.$
(1)

where $\phi:\mathbb{R}^{N\times 3}\rightarrow\mathbb{R}^{K}$ denotes the
encoding function with point number $N$ and global feature dimension $K$.

Then by rewriting the transformation on $\mathbf{P}_{\tau}$ side, their warp
increment $\Delta\xi$ is obtained by

$\displaystyle\arg\min_{\Delta\xi}\|\phi(\mathbf{P}_{S})-\phi(\mathbf{G}^{-1}(\xi^{i}\circ^{-1}\Delta\xi)\cdot\mathbf{P}_{\tau})\|_{2}^{2},$
(2)

where $\circ^{-1}$ is an inverse composition. By using the first-order Taylor
expansion, it yields

$\displaystyle\arg\min_{\xi}\|\phi(\mathbf{P}_{S})-\phi(\mathbf{G}^{-1}(\xi^{i})\cdot\mathbf{P}_{\tau})-\mathbf{J}\Delta\xi\|_{2}^{2},$
(3)

where

$\displaystyle\mathbf{J}=\frac{\partial\phi(\mathbf{G}^{-1}(\xi)\cdot\mathbf{P}_{\tau})}{\partial\xi^{T}}\in\mathbb{R}^{K\times
6}.$ (4)

Recently an analytical Jacobian has been proposed in [14]. It circumvents the
numerical unstable of approximate Jacobian [12] with step choices. The
analytical Jacobian consists of the Feature Jacobian and the Warp Jacobian:

$\displaystyle\mathbf{J}=\frac{\partial\phi(\mathbf{G}^{-1}(\xi)\cdot\mathbf{P}_{\tau})}{\partial(\mathbf{G}^{-1}(\xi)\cdot\mathbf{P}_{\tau})^{T}}\frac{\partial(\mathbf{G}^{-1}(\mathbf{\xi})\cdot\mathbf{P}_{\tau})}{\partial\xi^{T}}.$
(5)

Then by solving

$\displaystyle\xi=\mathbf{J}^{+}[\phi(\mathbf{P}_{S})-\phi(\mathbf{P}_{\tau})]$
(6)

we obtain the transformation and update as

$\displaystyle\mathbf{P}_{S}\leftarrow\mathbf{G}(\xi)\cdot\mathbf{P}_{S}.$ (7)

In the iteration, we solve Eq. 6 and Eq. 7 alternatively to make the final
registration as

$\displaystyle\mathbf{G}=\Delta\mathbf{G}_{n}\cdot\cdots\Delta\mathbf{G}_{0},$
(8)

where $\Delta\mathbf{G}=\exp(\sum_{i}\xi_{i}\mathbf{T}_{i})$.

##  IV Methodology

In each iteration, Eq. 7 always requires passing the original point cloud
$\mathbf{P}_{S}$ into the encoder function, which takes $\mathbb{O}(N\cdot C)$
where $N$ and $C$ are the maximum iterations and the number of points
respectively. It suffers from a similar problem as described in [15, 16],
i.e., it requires to repeat operations on the original point clouds.

We consider this transformation on point cloud to be inefficient and propose
to solve it by using another small point set to “communicate” with
$\mathbf{P}_{S}$ and $\mathbf{P}_{\tau}$ instead of letting $\mathbf{P}_{S}$
and $\mathbf{P}_{\tau}$ “contact” directly. We use a random sampled $L$-points
point cloud $\mathbf{P}_{a}\in\mathbb{R}^{L\times 3}$ where $L\ll N$.

Then we use the encoding function $\varphi(\cdot,\mathbf{P}_{a})$ with
$\varphi:\mathbb{R}^{N\times 3}\times\mathbb{R}^{L\times
3}\rightarrow\mathbb{R}^{K}$ to extract features from the point cloud with
$\mathbf{P}_{a}$ involved. So $\varphi(\mathbf{P}_{S},\mathbf{P}_{a})$ between
$\mathbf{P}_{S}$ and $\mathbf{P}_{a}$ is the $\mathbf{P}_{S}$ feature.
$\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})$ is the feature extracted from
$\mathbf{P}_{\tau}$.

Here we assume $\varphi(\mathbf{P}_{S},\mathbf{P}_{a})$ is transformation
invariant to $\mathbf{P}_{S}$ and $\mathbf{P}_{a}$ as in Fig. 1, such that the
transformation on $\mathbf{P}_{S}$ is equivalent to the inverse transformation
on $\mathbf{P}_{a}$, i.e.,

$\displaystyle\varphi(\mathbf{G}(\xi)\cdot\mathbf{P}_{S},\mathbf{P}_{a})=\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}(\xi)\cdot\mathbf{P}_{a}).$
(9)

###  IV-A Distance Field as a Transformation Invariant Function

(a) Intel 2D map.

(b) Distance field map.

(c) KITTI scan.

(d) Distance field 2D sketch.

Figure 2: Distance field demonstrations. The above is for 2D Intel map
generated with [17]. Below is on selected KITTI-odometry frame.

The formulation in Eq. 9 holds only when each dimension value of
$\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}\mathbf{P}_{a})$ will not change after
rotation and translation on the inputs of $\varphi$. Thus, in the view of the
feature metric, where $\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})$ and the
transformed $\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}\mathbf{P}_{a})$ are
compared, we cannot separately use the feature of
$\mathbf{P}_{S}/\mathbf{P}_{\tau}$ or $\mathbf{P}_{a}$. Because we neither
transform $\mathbf{P}_{S}/\mathbf{P}_{\tau}$ in our iteration design, nor
$\mathbf{P}_{a}$ gives anything itself. Therefore, we consider
$\mathbf{P}_{a}$ as a medium to help represent the geometry of
$\mathbf{P}_{S}/\mathbf{P}_{\tau}$. We observe that the point order of
$\mathbf{P}_{a}$ is actually fixed for
$\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}\mathbf{P}_{a})$ and
$\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})$ in one registration process. Which
provides independence in each dimension and makes the algorithm design more
flexible (in Sec. IV-C and Sec. IV-D). In addition, the function for each
point should provide continuous values for derivation computation.

We propose to introduce the distance field and use the score of
$\mathbf{p}_{i}\in\mathbf{P}_{a}$ in the field $\mathbf{D}_{\mathbf{P}_{S}}$
as the $i$-th dimension of
$\varphi(\mathbf{P}_{S},\mathbf{P}_{a})\in\mathbb{R}^{L}$. The concept of the
distance field is then utilized for the transformation invariant function with
the input of scan and pseudo points. Since an unsigned distance field is able
to work on an arbitrary point cloud, that is not limited to a closed shape, we
implement our algorithm under this more generalized setting. The distance
field is a function that computes the smallest distance between query point
$\mathbf{x}$ and the point cloud $\mathbf{P}$

$\displaystyle\mathbf{D}_{\mathbf{P}}(\mathbf{x})=\min_{\mathbf{p}\in\mathbf{P}}(||\mathbf{p}-\mathbf{x}||_{2}^{2}).$
(10)

The demonstration of distance field is in Fig. 2.

###  IV-B Pseudo-point Feature Metric Registration

[width=.8height=.4]im/pipe_

Figure 3: Algorithm pipeline of the proposed method. The pink arrows denote
computations that are carried out once. The yellow arrows denote computations
in an iterative fashion. The 1, 2, 3, 4 are sequential steps in an iteration.
We show algorithm of this pipeline in supplementary material2.

Given above function $\varphi$, shown similarly in Fig. 1, the transformation
between $\mathbf{P}_{S}$ and $\mathbf{P}_{\tau}$ becomes the inverse-alignment
of $\mathbf{P}_{a}$ to make
$\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}\cdot\mathbf{P}_{a})$ and
$\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})$ equal. Which is

$\displaystyle\arg\min_{\xi}\|\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}(\xi)\cdot\mathbf{P}_{a})-\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})\|_{2}^{2}$
(11)

By computing the Jacobian one is not able to describe the gradient on the
whole field. Different from Eqs. 2 and 3 that rewrite the transformation onto
the target $\mathbf{P}_{\tau}$ side. Instead, we keep updating the feature of
$\mathbf{P}_{S}$ and update Jacobian in each iteration. Eq. 11 is rewritten by
adding an incremental $\Delta\xi$ as

$\displaystyle\arg\min_{\Delta\xi}\|\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}(\xi^{i}\circ^{-1}\Delta\xi)\cdot\mathbf{P}_{a})-\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})\|_{2}^{2}.$
(12)

Using the first-order Taylor expansion, Eq. 12 becomes

$\displaystyle\arg\min_{\xi}\|\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})-\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}(\xi^{i})\cdot\mathbf{P}_{a})-\mathbf{J}\Delta\xi\|_{2}^{2}$
(13)

In our algorithm, the Jacobian is computed in each iteration. The analytical
Jacobian is formulated. It contains the feature Jacobian over the pseudo-point
set and multiplies the warp Jacobian of pseudo-point set over the
transformation parameters:

$\displaystyle\mathbf{J}=\frac{\partial\varphi(\mathbf{P}_{S},\mathbf{G}(\xi^{i})^{-1}\cdot\mathbf{P}_{a})}{\partial(\mathbf{G}(\xi^{i})^{-1}\cdot\mathbf{P}_{a})^{T}}\frac{\partial(\mathbf{G}(\xi^{i})^{-1}\cdot\mathbf{P}_{a})}{\partial\xi^{T}}.$
(14)

The warp Jacobian
$\frac{\partial(\mathbf{G}(\xi^{i})^{-1}\cdot\mathbf{P}_{a})}{\partial\xi^{T}}\in\mathbb{R}^{L\times
3\times 6}$ follows to the corresponding formulation on the pseudo-point set
$\mathbf{P}_{a}$ as PointNetLK-Revisited [14] uses it for the original point
set. The feature Jacobian
$\mathbf{J}_{feat}=\frac{\partial\varphi(\mathbf{P}_{S},\mathbf{G}(\xi^{i})^{-1}\cdot\mathbf{P}_{a})}{\partial(\mathbf{G}(\xi^{i})^{-1}\cdot\mathbf{P}_{a})^{T}}\in\mathbb{R}^{L\times
3\times L}$ is the gradient with closest points of pseudo-points in our
implementation:

$\displaystyle\begin{split}\mathbf{J}_{feat,(i,\cdot,i)}&=2(\mathbf{x}_{i}-\mathbf{p})\in\mathbb{R}^{3},\\\
&\text{with}\ \mathbf{x}_{i}\in\mathbf{P}_{a},\
\mathbf{p}=\operatorname*{arg\,min}_{\mathbf{p}\in\mathbf{P}_{S}}(||\mathbf{p}-\mathbf{x}_{i}||_{2}^{2}).\end{split}$
(15)

And the remaining non-filled entries of $\mathbf{J}_{feat}$ are set to zero.
Our pseudo-set analytical Jacobian is far more efficient than the analytical
Jacobian of [14] and is discussed in supplementary material222See github
page1.

Then by following Eq. 6, $\xi$ is solved with

$\displaystyle\xi=\mathbf{\mathbf{missing}}J^{+}[\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})-\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}(\xi_{-})\cdot\mathbf{P}_{a})]\oplus\xi_{-}$
(16)

where $\oplus$ is denoting the update between two twist vectors, $\xi_{-}$ is
denoting the twist parameters from last iteration. The whole diagram of the
registration is shown in Fig. 3. Before the first iteration,
$\varphi(\mathbf{P}_{S},\cdot)$ and
$\varphi(\mathbf{P}_{\tau},\mathbf{P}_{a})$ are prepared. Then in each
iteration $i$, we transform $\mathbf{P}_{a}$ as
$G^{-1}(\xi_{i})\mathbf{P}_{a}$ to compute the feature and Jacobian for
$\varphi(\mathbf{P}_{S},\mathbf{G}^{-1}(\xi_{-})\cdot\mathbf{P}_{a})$. Then
the incremental transformation is solved with the linear system
$\mathbf{J}\xi=\mathbf{r}$, where $\mathbf{r}$ is the residual of features.

###  IV-C Robust regression with Weights

Different from deep feature metric registration that dimensions are correlated
to each other, in our method each dimension of a feature is actually
corresponding to a single pseudo-point. This means each dimension is
independent to the others. Thus, we are able to add weight to each dimension
of the function $\mathbf{J}\xi=\mathbf{r}$ to adjust the importance of each
dimension. Therefore, we implement the Iterative Reweighted Least Squares
(IRLS) to solve for the $\xi$. With the weighted formulation, we actually
solve the sum of $L_{1}$ version of Eq. 12. For more detail on IRLS, please
follow
333https://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares#cite_ref-
Burrus_1-0 and [18].

TABLE I: Accuracy and generalizability. Results on 20 object categories, i.e.,
unseen categories of the baseline learning methods, from ModelNet40 and
ShapeNetCore. $\downarrow$ means smaller values are better.

| ModelNet40 | ShapeNetCore
---|---|---
| Rot. Err. (deg.) $\downarrow$ | Trans. Err. $\downarrow$ | Rot. Err. (deg.) $\downarrow$ | Trans. Err. $\downarrow$
Algorithm | RMSE | Median | RMSE | Median | RMSE | Median | RMSE | Median
ICP∗ [19] | 39.33 | 5.036 | 0.474 | 0.058 | 40.71 | 5.825 | 0.478 | 0.073
DCP∗ [20] | 5.500 | 1.202 | 0.022 | 0.004 | 8.587 | 0.930 | 0.021 | 0.003
DeepGMR∗ [21] | 6.059 | 0.070 | 0.014 | 8.42e-5 | 6.043 | 0.013 | 0.005 | 9.33e-6
PointNetLK∗ [12] | 8.183 | 3.63e-6 | 0.074 | 5.96e-8 | 12.941 | 4.33e-6 | 0.115 | 5.96e-8
PointNetLK-Revisited∗ [14] | 3.350 | 2.17e-6 | 0.031 | 4.47e-8 | 3.983 | 2.06e-6 | 0.049 | 2.98e-8
Ours | 5.168 | 1.83e-6 | 0.055 | 4.47e-8 | 4.042 | 2.95e-6 | 0.047 | 5.96e-8

  * ∗

Values taken from [14].

###  IV-D Truncation Strategy

In the implementation, truncation is used to remove the outlier points as in
each iteration, certain dimensions of $\varphi$ are freely removed together
with its corresponding Jacobian. For example, if the $j$-th pseudo-point is
removed, $K^{+}=K-1$ for the feature $\varphi$ of both sample and template
point cloud, then the $j$-th row of the Jacobian is also ignored in Eq. 6. It
is also feasible as it is considered as part of $\varphi$ function to block
certain dimensions in the iteration. The specific implementation of the
truncation is described in Sec. V-D.

###  IV-E Computational cost

The computation cost of our method includes the implementation of the distance
function. With the recent neural network based distance field [22, 23], it
costs $\mathbb{O}(N)+\mathbb{O}(KL)$ to get the point cloud global latent and
to iterate $K$ times for the pseudo-point set. In this paper, we focus on the
algorithm itself, and compute the distance value for each pseudo-points by
using $k$-d tree search. Excluding the $\mathbb{O}(N\log N)$ tree-building
time, the registration time complexity of our model is $\mathbb{O}(KL\log N)$.

In comparison, excluding the $\mathbb{O}(N\log N)$ tree building time, ICP
takes $\mathbb{O}(KN\log N)$ for iterating $K$ times. Feature metric
registrations require $\mathbb{O}(KN)$. More detail about space complexity is
given in supplementary material2.

##  V Experiments, Results, and Discussion

Next, we focus on the registration performance to evaluate our model on
synthetic datasets, an indoor dataset, and an outdoor dataset. The deep
learning based models are known to exceed the conventional method on
performance. However, our results show that, even without any training of the
model, as a feature-metric method, our model achieves competitive results to
the state-of-the-art learned models.

###  V-A Datasets

Figure 4: Data examples. The four rows are selected examples from ModelNet,
ShapeNet, 3DMatch, KITTI-Odometry datasets respectively. In the first two
rows, aside from the black point cloud we also plot its object surface as in
[14] for better visualization.

####  V-A1 ModelNet40 [24]

ModelNet40 is a synthetic 3D object dataset contains 40 categories of daily
objects. For a fair comparison, we follow PointNetLK-Revisited to select 20
categories from ModelNet40 as a testing set, the rest is for the training of
other learning models.

####  V-A2 ShapeNetCoreV2 [25]

ShapeNetCore is a subset of ShapeNet that contains 55 common object
categories. Again, for a fair comparison, 12 categories are selected from
ShapeNetCoreV2 separately for testing and the rest for the training of other
learned models.

####  V-A3 3DMatch [26]

3DMatch collects RGB-D scans from several datasets. It contains complex indoor
scenes, such as kitchen, office, etc. We follow PointNetLK-Revisited to choose
8 categories of scenes for testing. In addition, only those testing pairs with
at least 70% overlap are kept.

####  V-A4 KITTI-odometry [27]

KITTI-odometry is a large-scale outdoor LiDAR point cloud dataset around
cities. It consists of 22 sequences. The first 11 sequences are provided with
ground truth trajectory. This test on outdoor data is used to compare with
outdoor registration models to further explore the capacity of our algorithm.

Selected examples of used data are shown in Fig. 4.

###  V-B Baselines

We use as baseline ICP [19], DCP [20], DeepGMR [21], PointNetLK [12], and the
most recent state-of-the-art PointNetLK-Revisited [14] for synthetic
registration and indoor registration. We also test it on an outdoor dataset
which is not applicable to deep feature-based registration [14]. Thus we use
the benchmark from outdoor registration paper [28] with the baseline ICP [19],
G-ICP [29], 3DFeat-Net [6], DeepVCP [30], and DeepCLR [28].

###  V-C Metrics

The difference between prediction and ground truth for rotation (in degree)
and translation (in meter) is evaluated as relative rotation error
(RRE$=\arccos(Tr(R^{T}R-1)/2)$) and relative translation error (RTE). To
represent the variance of registration and the error distribution we use the
root mean square error (RMSE) and median error (MAE) of RRE, RTE as metrics.

###  V-D Setting

The rigid transformation used for testing consists of a rotation randomly
drawn in [$None$, $None$] and a translation in [$0$, $0$.8] for synthetic and
indoor test [14]. The outdoor test follows [28]. As our model does not require
training, we directly feed all of the points as input.

The maximum number of iterations is set to 10 for iterative methods on
synthetic data and to 20 on real data. The number of pseudo points $L$ is
$1000$ in all experiments.

For pseudo set generation, we implement a random pseudo set and a neighborhood
pseudo set generation for following experiments. For truncation, we filtered
out pseudo-points if (1) too many pseudo-points redundantly neighbors to the
same surface point and (2) pseudo-points are not on the surface normal
direction, as those points are more likely to be far away from the surface or
in a no-surface region.

All experiments are implemented on a NUC-computer (CPU-i7-10710U, 32GB
memory).

###  V-E Synthetic Data Test

In the synthetic test, pseudo set are uniformly drawn from $[-1,1]^{3}$ cube.
No truncation has been used.

The evaluation performance is shown in Tab. I. Our non-learning method (IFR)
obtained a competitive performance to the new state-of-the-art PointNetLK-
Revisited [14]. The feature-metric class methods (PointNetLK, PointNetLK-
Revisited, ours) achieves a median rotation error at $1\text{\times}{10}^{-6}$
level and a translation error at $1\text{\times}{10}^{-8}$ level, which is
much more precise than the rest.

(a) Rotation threshold.

(b) Translation threshold.

Figure 5: Success Rate. The $x$-axis is logarithmic.

To further demonstrate the competitive performance, we plot the success to
error threshold curve in Fig. 5. Even at a very small maximum threshold, the
success rates of our method and DL-based PointNetLK-Revisited are still
similar and at a high level, well-reflecting the performance of our non-
learning IFR model.

###  V-F Efficiency

In [14], PointnetLK-Revisited shows a better efficiency than other baselines
with a sample of $10^{4}$ points on a single CPU. It is feasible to test on
CPU excluding the acceleration techniques as the time complexity is more
intuitively reflected from the time cost. Similarly, we also sample $10^{4}$
points and test with our Intel Core i7-10710U CPU at 1.10GHz (a low power
processor). PointNetLK-Revisited took 1.97s, while our model took 0.27s.

###  V-G Robustness Test

Data collected with real sensors usually suffer from noise and sparsity. Thus
to further assess the robustness of our algorithm, we test for these
properties. PointnetLK-Re shows much better robustness than other baselines
[14]. Thus, we merely compare with the best PointnetLK-Re and shows scores
with it.

####  V-G1 Different Density

We implement the test on ModelNet Test set used in the previous part. Due to
the large requirement on GPU memory for PointNetLK-Re, we set the upper bound
of point number to $2$00,000. Then we randomly select points from the sample
point cloud. The performance of our IFR algorithm is demonstrated in Fig.
6(a). It outperforms the DL state of the art on the whole range of sparsity.

(a) Sparse data.

(b) Robustness to noise.

Figure 6: Robustness to noise and sparsity.

####  V-G2 Different Noise Level

The noise robustness test is similar to the previous setting. To add noise to
the data, we randomly generate Gaussian Noises with
$\sigma\in\\{0.01,0.02\cdots 0.1,0.2\\}$ to every point in both point clouds.
Our IFR uses the distance field as a basis. Therefore, the noise is addressed
at (1) data preprocessing, (2) smoothed distance field, and (3) on our general
algorithm side. To clarify the capability and limitation of our method, our
algorithm deals with noise at level (3), i.e., on the algorithm side by taking
$k=5$ nearest neighbors as the mean feature at the encoding step.

From Fig. 6(b), we observe that in the range [$0$, $0.06$] meter in the noise,
our IFR achieves a relative or even better success rate. However, when the
noise becomes extremely high, $0.1\text{\,}\mathrm{m}$ or
$0.2\text{\,}\mathrm{m}$ for example, our curve drops faster than the DL-based
PointNetLK-Re. However, this extreme noise is not expected in real life, i.e.,
for realistic sensors. Therefore, in the next part, we will evaluate our IFR
algorithm in real scenes.

###  V-H Real Indoor Data Test

After the robustness test, we turn to the real dataset that combines various
aspects and challenges in the real world.

For the synthetic tests, the distance fields are very similar and the
generation within uniform cube or neighborhood will not affect the result.
However, in the real scene test, the distance fields for the two point cloud
are usually partially different, which is more severe in space with large
distances from the surface. Thus points far from the surface will falsely
affect the result. Thus, we use points in the neighborhood for the real scene.

In the implementation, we draw $\mathbf{P}_{a}$ near the point cloud
$\mathbf{P}_{\tau}$ with a Gaussian distribution centered at the surface
points.

The scores are given in Tab. II. In the table, ICP achieves even better scores
than any of the learning methods. However, our model outperforms all. With a
truncation strategy (in Sec. IV-D), the registration even achieves $1$.106
Median Rot. Error and $0$.049 Median Trans. Error. Ablation study in Sec. V-J
is implemented to demonstrate the functionality of different modules. We also
outperform PointNetLK-Re but do not add it to this table. The reason is
detailed in supplementary2.

TABLE II: Performance on complex, real-world scenes. All learning methods were
trained on the synthetic ModelNet40 dataset and tested on the real-world
3DMatch dataset to investigate their generalizability across data with
different distributions.

Rot. Error (degrees) Trans. Error (m) Algorithm RMSE $\downarrow$ Median
$\downarrow$ RMSE $\downarrow$ Median $\downarrow$ ICP∗ [19] 24.772 4.501
1.064 0.149 DCP∗ [20] 53.905 23.659 1.823 0.784 DeepGMR∗ [21] 32.729 16.548
2.112 0.764 PointNetLK∗ [12] 28.894 7.596 1.098 0.260 Ours 23.814 4.191 1.057
0.161 Ours w/ trunc 40.42 1.106 1.546 0.049

  * ∗

Values taken from [14].

TABLE III: RMSE on KITTI with artificial transformation. As compared deep
learning based methods are trained on 00-07 sequences, we run tests on 08-10
sequences.

ICP Point2Point∗ [19] ICP Point2Plane∗ [19] G-ICP∗ [29] 3DFeat-Net∗ [6]
DeepVCP∗ [30] DeepCLR∗ [28] Ours Rot. Err. (deg.) 0.088 0.079 0.029 0.199
0.164 0.053 0.088 Trans. Err. 0.177 0.140 0.109 0.116 0.071 0.080 0.068

  * ∗

Values taken from [28].

###  V-I Outdoor Data Test

From our knowledge, the implicit function based reconstructions have only been
applied to synthetic and indoor data sets, i.e., that is the basic case for
use. But to explore the capacity of our approach, we also test it on well-
known outdoor LiDAR data, i.e., the KITTI-odometry. Because the KITTI point
cloud has varying density, in implementation we use an ISS-keypoint detector
to sample points as surface points $\mathbf{P}_{\tau,sub}$
($\mathbf{P}_{\tau,sub}$ for pseudo-set generation). From which, we generate
$\mathbf{P}_{a}$ as for the indoor test. The same truncation strategy as for
the indoor test is also applied in this test.

The quantitative evaluation compared to the state-of-the-art (traditional and
DL-based registration) on outdoor data is given in Tab. III. Our method
achieves the best translation error and competitive rotation error to deep
learning methods. However, G-ICP scores best on the rotation error.

In addition, we predict sequence 00 and plot it in Fig. 7. Without any loop
closure, it still provides a highly accurate trajectory.

Figure 7: Registered trajectory for Kitti-odometry sequence 00 without loop-
closure.

###  V-J Ablation Study

We implement an ablation study to show the impact of three different modules:
IRLS, truncation, and pseudo-set generation. Because the different settings do
not obviously improve the synthetic test, the study is applied to indoor test
with the 3DMatch dataset.

In Tab. IV, “without IRLS” option disables IRLS and uses Eq. 16 to solve the
transformation parameters $\xi$, “with truncation” option truncate dimensions
following Sec. V-D, uniform pseudo and neighborhood pseudo options are
following the experiment setting at Sec. V-E and Sec. V-H respectively. We
plot two types of pseudo sets in supplementary material2.

The full table with eight tests is provided at Tab. IV. With one option
change, firstly, with IRLS or without IRLS, we observe that “with IRLS” group
#(5,6,7,8) shows a smaller median error than its corresponding test in group
#(1,2,3,4) respectively. This also holds for major “with truncation” group
#(4,7,8) to respectively exceed “without truncation” group #(2,5,6). Moreover,
major neighborhood pseudo group #(4,6,8) shows a smaller median error than
their corresponding uniform pseudo group #(3,5,7) respectively.

The above comparison shows the effects of different modules (with IRLS, with
truncation, and neighborhood pseudo). With all three modules equipped, #8
scores the best.

However, with a truncation, our model (in Sec. IV-D) overfits two frames
easier. As shown in Tab. IV, our model with truncation strategy achieves very
accurate median rotatational and translational error. Though it provides more
accurate results. But its higher RMSE in Tab. IV means that when it fails, it
solves completely wrong.

TABLE IV: Ablation Study on IRLS, truncation and pseudo-set generation.

|  |  |  |  | uniform | neighborhood | Rot. Error | Trans. Error
---|---|---|---|---|---|---|---|---
| #
---
w/ IRLS | w/o IRLS | w/ trunc | w/o trunc | pseudo | pseudo | RMSE | Median | RMSE | Median
1 |  |  |  |  |  |  | 18.732 | 7.073 | 0.969 | 0.311
2 |  |  |  |  |  |  | 25.074 | 7.393 | 1.129 | 0.265
3 |  |  |  |  |  |  | 46.522 | 7.503 | 1.607 | 0.281
4 |  |  |  |  |  |  | 37.896 | 2.998 | 1.492 | 0.118
5 |  |  |  |  |  |  | 19.042 | 5.732 | 0.972 | 0.248
6 |  |  |  |  |  |  | 23.018 | 4.443 | 1.057 | 0.157
7 |  |  |  |  |  |  | 44.102 | 4.687 | 1.617 | 0.160
8 |  |  |  |  |  |  | 32.886 | 0.913 | 1.148 | 0.036

##  VI Conclusion and future work

In this paper, we have presented an indirect point cloud registration method
using a pseudo third point set. Our method registers two distance fields by
only moving the pseudo-points, reducing the redundant movement of original
point clouds. In addition, we have extended the Feature Metric Registration
class algorithms to a non-deep learning setting. While using the analytical
Jacobian, our pseudo-points based design highly reduces the theoretical space
and time complexity. From the comparison, our non-learning method achieved
competitive and for some scenes better results than those learned models.

In the future, we plan to embed this registration algorithm in an implicit-
mapping based SLAM framework.

## References

  * [1] P. Koch, S. May, M. Schmidpeter, M. Kühn, C. Pfitzner, C. Merkl, R. Koch, M. Fees, J. Martin, D. Ammon, _et al._ , “Multi-robot localization and mapping based on signed distance functions,” _Journal of Intelligent & Robotic Systems_, vol. 83, no. 3, pp. 409–428, 2016.
  * [2] Y. Yuan, D. Borrmann, J. Hou, Y. Ma, A. Nüchter, and S. Schwertfeger, “Self-supervised point set local descriptors for point cloud registration,” _Sensors_ , vol. 21, no. 2, p. 486, 2021.
  * [3] J. Huang, S.-S. Huang, H. Song, and S.-M. Hu, “Di-fusion: Online implicit 3d reconstruction with deep priors,” in _Proceedings of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition_ , 2021, pp. 8932–8941.
  * [4] M. Slavcheva, “Signed distance fields for rigid and deformable 3d reconstruction,” Ph.D. dissertation, Technische Universität München, 2018\.
  * [5] J. Li and G. H. Lee, “Usip: Unsupervised stable interest point detection from 3d point clouds,” in _Proceedings of the IEEE/CVF International Conf. on Computer Vision_ , 2019, pp. 361–370.
  * [6] Z. J. Yew and G. H. Lee, “3dfeat-net: Weakly supervised local 3d features for point cloud registration,” in _Proceedings of the Europ. Conf. on Computer Vision (ECCV)_ , 2018, pp. 607–623.
  * [7] F. Lu, G. Chen, Y. Liu, Z. Qu, and A. Knoll, “Rskdd-net: Random sample-based keypoint detector and descriptor,” _arXiv preprint arXiv:2010.12394_ , 2020\.
  * [8] X. Bai, Z. Luo, L. Zhou, H. Fu, L. Quan, and C.-L. Tai, “D3feat: Joint learning of dense detection and description of 3d local features,” in _Proceedings of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition_ , 2020, pp. 6359–6367.
  * [9] H. Yang, J. Shi, and L. Carlone, “Teaser: Fast and certifiable point cloud registration,” _IEEE Transactions on Robotics_ , vol. 37, no. 2, pp. 314–333, 2020.
  * [10] C. Choy, W. Dong, and V. Koltun, “Deep global registration,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 2514–2523.
  * [11] F. Lu, G. Chen, Y. Liu, L. Zhang, S. Qu, S. Liu, and R. Gu, “Hregnet: A hierarchical network for large-scale outdoor lidar point cloud registration,” in _Proceedings of the IEEE/CVF International Conf. on Computer Vision_ , 2021, pp. 16 014–16 023.
  * [12] Y. Aoki, H. Goforth, R. A. Srivatsan, and S. Lucey, “Pointnetlk: Robust & efficient point cloud registration using pointnet,” in _Proceedings of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition_ , 2019, pp. 7163–7172.
  * [13] X. Huang, G. Mei, and J. Zhang, “Feature-metric registration: A fast semi-supervised approach for robust point cloud registration without correspondences,” in _Proceedings of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition_ , 2020, pp. 11 366–11 374.
  * [14] X. Li, J. K. Pontes, and S. Lucey, “Pointnetlk revisited,” in _Proceedings of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition_ , 2021, pp. 12 763–12 772.
  * [15] M. Slavcheva, W. Kehl, N. Navab, and S. Ilic, “Sdf-2-sdf: Highly accurate 3d object reconstruction,” in _Europ. Conf. on Computer Vision_. Springer, 2016, pp. 680–696.
  * [16] M. Slavcheva and S. Ilic, “Sdf-tar: Parallel tracking and refinement in rgb-d data using volumetric registration.” in _BMVC_ , 2016.
  * [17] Y. Yuan and S. Schwertfeger, “Incrementally building topology graphs via distance maps,” in _2019 IEEE International Conf. on Real-time Computing and Robotics (RCAR)_. IEEE, 2019, pp. 468–474.
  * [18] J. E. Gentle, “Matrix algebra,” _Springer texts in statistics, Springer, New York, NY, doi_ , vol. 10, pp. 978–0, 2007.
  * [19] P. J. Besl and N. D. McKay, “Method for registration of 3-d shapes,” in _Sensor fusion IV: control paradigms and data structures_ , vol. 1611\. International Society for Optics and Photonics, 1992, pp. 586–606.
  * [20] Y. Wang and J. M. Solomon, “Deep closest point: Learning representations for point cloud registration,” in _Proceedings of the IEEE/CVF International Conf. on Computer Vision_ , 2019, pp. 3523–3532.
  * [21] W. Yuan, B. Eckart, K. Kim, V. Jampani, D. Fox, and J. Kautz, “Deepgmr: Learning latent gaussian mixture models for registration,” in _Europ. Conf. on Computer Vision_. Springer, 2020, pp. 733–750.
  * [22] J. J. Park, P. Florence, J. Straub, R. Newcombe, and S. Lovegrove, “Deepsdf: Learning continuous signed distance functions for shape representation,” in _Proceedings of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition_ , 2019, pp. 165–174.
  * [23] J. Chibane, A. Mir, and G. Pons-Moll, “Neural unsigned distance fields for implicit function learning,” _arXiv preprint arXiv:2010.13938_ , 2020.
  * [24] Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang, and J. Xiao, “3d shapenets: A deep representation for volumetric shapes,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1912–1920.
  * [25] A. X. Chang, T. Funkhouser, L. Guibas, P. Hanrahan, Q. Huang, Z. Li, S. Savarese, M. Savva, S. Song, H. Su, _et al._ , “Shapenet: An information-rich 3d model repository,” _arXiv preprint arXiv:1512.03012_ , 2015.
  * [26] A. Zeng, S. Song, M. Nießner, M. Fisher, J. Xiao, and T. Funkhouser, “3dmatch: Learning local geometric descriptors from rgb-d reconstructions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 1802–1811.
  * [27] A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in _2012 IEEE conference on computer vision and pattern recognition_. IEEE, 2012, pp. 3354–3361.
  * [28] M. Horn, N. Engel, V. Belagiannis, M. Buchholz, and K. Dietmayer, “Deepclr: Correspondence-less architecture for deep end-to-end point cloud registration,” in _2020 IEEE 23rd International Conf. on Intelligent Transportation Systems (ITSC)_. IEEE, 2020, pp. 1–7.
  * [29] A. Segal, D. Haehnel, and S. Thrun, “Generalized-icp.” in _Robotics: science and systems_ , vol. 2, no. 4. Seattle, WA, 2009, p. 435.
  * [30] W. Lu, G. Wan, Y. Zhou, X. Fu, P. Yuan, and S. Song, “Deepvcp: An end-to-end deep neural network for point cloud registration,” in _Proceedings of the IEEE/CVF International Conf. on Computer Vision_ , 2019, pp. 12–21.