# SecBeam: Securing mmWave Beam Alignment against Beam-Stealing Attacks

Jingcheng Li, Loukas Lazos, Ming Li  University of Arizona
{jli2972, llazos<EMAIL_ADDRESS>
###### Abstract

Millimeter wave (mmWave) communications employ narrow-beam directional
communications to compensate for the high path loss at mmWave frequencies.
Compared to their omnidirectional counterparts, an additional step of aligning
the transmitter’s and receiver’s antennas is required. In current standards
such as 802.11ad, this beam alignment process is implemented via an exhaustive
search through the horizontal plane known as beam sweeping. However, the beam
sweeping process is unauthenticated. As a result, an adversary, Mallory, can
launch an active beam-stealing attack by injecting forged beacons of high
power, forcing the legitimate devices to beamform towards her direction.
Mallory is now in control of the communication link between the two devices,
thus breaking the false sense of security given by the directionality of
mmWave transmissions.

Prior works have added integrity protection to beam alignment messages to
prevent forgeries. In this paper, we demonstrate a new beam-stealing attack
that does not require message forging. We show that Mallory can amplify and
relay a beam sweeping frame from her direction without altering its contents.
Intuitively, cryptographic primitives cannot verify physical properties such
as the SNR used in beam selection. We propose a new beam sweeping protocol
called SecBeam that utilizes power/sector randomization and coarse angle-of-
arrival information to detect amplify-and-relay attacks. We demonstrate the
security and performance of SecBeam using an experimental mmWave platform and
via ray-tracing simulations.

##  I Introduction

Millimeter Wave (mmWave) communications are a key enabling technology for the
Next-Generation of wireless networks [39, 26]. The abundance of available
bandwidth offers unprecedented opportunities for high data rates, ultra-low
latency, and massive connectivity. However, the short wavelength poses new
challenges at the physical layer due to the substantial signal attenuation
(which is proportional to the center frequency) and susceptibility to blockage
[26]. To compensate for this high attenuation, mmWave devices employ high-gain
directional transmissions which are possible due to the small antenna factor
necessary at small wavelengths. New highly-directional antenna systems pack
many antenna elements into a small area which can be electronically steered to
form high-gain pencil like beams at any desired direction.

Compared to their omnidirectional counterparts, narrow-beam directional
systems require continuous beam management [37]. The beam management process
consists of the initial phase of beam alignment between the Tx and the Rx and
the subsequent phase of beam tracking if any of the Tx or Rx are mobile, or
the physical environment changes. Recent standards such as the IEEE 802.11ad
[14] and its enhanced version IEEE 802.11ay [11], describe beam alignment as
an exhaustive search process called sector-level sweep (SLS) where all
possible directions are scanned before the optimal Tx and Rx antenna
orientations are decided. Specifically, one device acts as the initiator $I$,
whereas the other acts as the responder $R$. The initiator sequentially sends
sector sweep frames (beacons) in every candidate direction using narrow-beam
transmissions while the responder receives in quasi-omni mode.

Figure 1: Beam-stealing attack against the SLS protocol. $I$ and $R$ beamform
towards the adversary instead of the LoS path.

The responder measures the received power from each receivable beacon and
determines the initiator’s direction (sector) with the highest signal-to-noise
ratio (SNR). The process is repeated in the opposite direction to define the
responder’s sector with the highest SNR. Upon completion, the initiator’s and
the responder’s beams are aligned to the direction that maximizes the
cumulative antenna gain which can be a line-of-sight (LoS) path or a
reflection path.

The beacons in the SLS protocol, however, are unauthenticated and can be
easily forged. An adversary, Mallory, can launch an active beam-stealing
attack by injecting forged beacons of high power, forcing the legitimate Tx
and Rx to beamform towards her direction [30]. This attack is shown in Figure
1 where the initiator selects sector 1 instead of sector 8 and the responder
selects sector 3 instead of 4. Mallory is now in control of the communication
link between $I$ and $R$, thus breaking the false sense of security given by
the directionality of mmWave transmissions [18, 42]. She can eavesdrop on the
link, apply traffic analysis to infer information from encrypted
communications [22], inject and modify messages, or selectively drop them.

A few methods have been proposed to prevent beam-stealing attacks [28, 41, 31,
4, 36, 35]. Steinmetzer $et\ al.$ introduced an authenticated beam sweep
protocol [28]. The main idea is to prevent the forging of beacons by
guaranteeing their authenticity and freshness via cryptographic means (e.g.,
encrypt and sign beacon transmissions). However, we postulate that a beam-
stealing attack is still feasible against an authenticated beam sweep
protocol. Specifically, we demonstrate a new amplify-and-relay attack that
does not require access to cryptographic primitives on behalf of Mallory.

Amplify-and-relay beam-stealing attacks. To achieve beam-stealing when beacons
are authenticated, Mallory can launch a relay attack as shown in Figure 1.
When $I$ transmits a beacon toward Mallory (sector 8), Mallory swiftly
amplifies and relays the beacon toward the responder. Mallory does not need to
decode the beacon or modify its contents, as the beacon only needs to be
received at higher power. Because the beacon is generated by $I$ and contains
the correct authenticator, it passes authentication at $R$. Due to the signal
amplification, $R$ is led to believe that sector 8 yields the highest SNR and
provides this feedback to $I$. The relay attack is repeated in the $R$ to $I$
direction, leading $I$ to believe that the third sector of $R$ yields the
highest SNR.

The amplify-and-relay attack is feasible because the added cryptographic
protections validate the contents of the beacons, but fail to authenticate the
physical property used for sector selection which is the SNR. Practically, the
attack distorts the wireless environment and cannot be dealt with by
cryptographic means alone.

Existing relay attacks that aim at breaking proximity constraints (e.g., [8,
9]) are different from amplify-and-relay beam-stealing attacks in terms of
goals and assumptions. Other known attacks of similar nature are signal
cancellation attacks where a carefully placed adversary relays a transmitted
signal with the purpose of causing destructive interference at the intended
receiver [23, 21], which are harder to realize. An intuitive defense against
relay attacks is to differentiate between the legitimate transmitter and the
relay. Fingerprinting techniques such as those in [4, 36, 35] extract unique
fingerprints from the devices such as antenna patterns, frequency offset and
DC offset characteristics, etc. However, these methods require training, may
utilize multiple access points and are not applicable when devices meet for
the first time. Others, such as the angle-of-arrival-based detection method
[41] and SNR fingerprinting methods [36] assume that the locations of the
devices are fixed and known.

In this paper, we address the problem of securing the SLS protocol of 802.11ad
against amplify-and-relay beam-stealing attacks. Our main contributions are as
follows:

  * •

We demonstrate a new amplify-and-relay attack against the beam alignment
process of mmWave communications. This attack defeats cryptographic defenses
that rely on beacon authentication to detect beacon forging.

  * •

We develop an attack detection method that exploits the power-delay profile
(PDP) of the mmWave channel. Assuming that the LoS path is available, any
amplified relay path will have a longer delay and a higher SNR compared to the
LoS path. However, a signal traveling through the LoS path should incur the
least attenuation due to its free space propagation over a shorter distance.
We use the discrepancies in the PDP to detect amplify-and-relay attacks over
paths longer than the LoS path.

  * •

The PDP detection method assumes the presence of the LoS path, which may not
be true. To generalize attack detection to all environments, we propose the
SecBeam protocol that derives security from a combination of power
randomization and coarse AoA detection. The focal idea is to hide the sector
identity and randomize the beacon transmit power to prevent Mallory from fine-
tuning her amplification power. Without knowledge of the sector ID and
transmit power, Mallory has to amplify the beacons from all sectors she can
hear. This leads to a disproportionate number of beacons arriving from the
same direction, violating the geometrical mmWave channel model [15]. SecBeam
requires minimal modifications to the original SLS protocol of 802.11ad.

  * •

We analyze the security of SecBeam and show that it can detect an amplify-and-
forward attacker that relays incoming beacons at fixed transmit power or at
fixed amplification. We experimentally evaluate the performance and security
of SecBeam on a 28GHz mmWave testbed in typical indoor environments. Our
experiments demonstrate that SecBeam allows legitimate devices to optimally
align their beams while detecting amplify-and-relay attacks with high
probability.

##  II The SLS protocol in IEEE 802.11ad and attack

###  II-A The SLS protocol in IEEE 802.11ad

The beam alignment process in the IEEE 802.11ad, also known as “sector-level
sweep (SLS)”, aims at maximizing the combined Tx-Rx antenna gain [14]. This is
done by sweeping the plane using fine-beam and quasi-beam antenna
configurations and identifying the directions (sectors) of optimal antenna
alignment. Sweeping is achieved electronically by controlling the individual
antenna elements [10]. An example of a steerable antenna pattern is shown in
Figure 2. The antenna can be set to quasi-omni mode for wider coverage, or to
a fine-beam mode for the highest gain.

Figure 2: A steerable mmWave antenna that can operate in fine-beam mode or
quasi-omni mode.

The main idea of SLS is shown in Figure 3. One device assumes the role of the
initiator ($I$) whereas the other assumes the role of the responder ($R$). The
initiator sets its antenna in fine-beam mode and sweeps through the plane
transmitting sector sweep frames (SSF). The receiver operates in quasi-omni
mode, recording the received SNR from each sector as shown in Figure 3(a). In
the next phase, the two devices switch roles. The responder transmits in fine-
beam mode while the initiator is in quasi-omni mode. Additionally, the
responder provides feedback about the optimal initiator’s sector (highest
SNR), as recorded from the previous phase. Finally, the initiator provides
feedback to the responder about the optimal responder’s sector and the two
antennas are aligned as shown in Figure 3(b). In detail, the SLS protocol
consists of the three phases shown in Figure 4(a).

---
(a) (b)
(c) (d)
Figure 3: The SLS process of 802.11ad: (a) $I$ sweeps through the plane in
fine-beam mode while $R$ receives in quasi-omni mode, (b) $I$ repeats the
sector sweep for every quasi-omni pattern of $R$, (c) $R$ sweeps through the
plane in fine-beam mode while $I$ receives in quasi-omni mode, (d) The
antennas of $I$ and $R$ are optimally aligned.

Initiator sector sweep phase.

  1. 1.

The plane is divided into $N$ sectors $S_{1},S_{2},\ldots S_{N}.$ The
initiator $I$ sweeps through each $S_{i}$ and transmits sector sweep frame
(SSF) $SSF_{I}(i)$, using the fine-beam mode.

  2. 2.

The responder $R$ measures the SNR for each received SSF, while in quasi-omni
mode.

  3. 3.

Steps 1 and 2 are repeated for every quasi-omni antenna orientation in $R$ to
cover $R$’s plane. The responder records the sector $S^{\ast}_{I}$ with the
highest SNR.

Responder sector sweep phase.

  1. 4.

The responder switches to fine-beam mode whereas the initiator switches to
quasi-omni mode. The responder $R$ sweeps through each sector $S_{i}$ and
transmits $SSF_{R}(i)$, using the fine-beam mode. Further, the responder
populates the sector sweep (SSW) feedback field of the SSF with the $I$’s
optimal transmitting secctor $S^{\ast}_{I},$ as identified in the previous
phase.

  2. 5.

The initiator records the sector $S^{\ast}_{R}$ with the highest received SNR
and also learns $S^{\ast}_{I}$ from $R$’s feedback.

Acknowledgement phase.

  1. 6.

The initiator sends a SSW-Feedback frame to $R$ indicating $R$’s optimal
transmitting sector $S^{\ast}_{R}$. The feedback is transmitted in fine-beam
mode using sector $S^{\ast}_{I}$, whereas the responder is in quasi-mode.

  2. 7.

At the last step, the responder transmits a sector sweep ACK to the initiator
using sector $S^{\ast}_{R}$.

  3. 8.

The two antennas are aligned at the $S^{\ast}_{I}$-$S^{\ast}_{R}$ direction.

|
---|---
(a) | (b)
Figure 4: (a) SLS protocol in IEEE 802.11ad standard, (b) beam-stealing attack
against SLS protocol

In the example of Fig. 3, the responder identifies $S_{I}^{\ast}=S_{8}$
whereas the initiator identifies $S_{R}^{\ast}=S_{4}$. The two devices use the
$S_{8}-S_{4}$ antenna orientation for communications.

###  II-B Beam-Stealing Attack Against the SLS Protocol

In this section, we describe the beam-stealing attack against SLS protocol in
IEEE 802.11ad presented by Steinmetzer et al. [30]. The attack is launched by
$\mathcal{M}$ who forges the SSF frames. The timeline of the attack is shown
in Fig. 4(b).

Mallory positions herself within range of both $I$ and $R$ (though the attack
can be also launched by two colluding devices). During the initiator sector
sweep phase, Mallory measures the SNR from all sectors of $I$ and chooses the
one that yields the highest SNR, denoted by $S^{\prime}_{I}$. Because the
communication protocol lacks an authentication mechanism, Mallory impersonates
$R$ by forging $R$’s SSFs and indicating $S^{\prime}_{I}$ as the best sector.
The same process is repeated during the responder sector sweep phase, where
$\mathcal{M}$ chooses the best sector $S^{\prime}_{R}$ and informs $R$ through
forged SSF frames on behalf of $I$. Ultimately, $I$ and $R$ choose sectors
$S^{\prime}_{I}$ and $S^{\prime}_{R}$ that beamform towards $\mathcal{M}$, as
illustrated in Figure 1. $I$ and $R$ choose sectors $S_{1}$ and $S_{3}$
instead of $S_{8}$ and $S_{4}$. Mallory gains full control over the
communication between the victim devices, enabling a range of potential
attacks such as eavesdropping, traffic analysis, data modification and
injection.

###  II-C Authenticated Beam Sweeping

It is evident that the beam stealing attack is possible due to the lack of
authentication and integrity protection on the SSF frames. To counter this
vulnerability, Steinmetzer et al. proposed an authenticated version of SLS
where $I$ and $R$ are assumed to possess public/private key pairs [28] which
are used to securely establish a session key $s$. The session key is used for
mutual authentication and freshness to protect against message forgeries and
replay attacks. Specifically, during the initiator sector sweep phase, $I$
generates a unique cryptographic nonce $v_{I}$ that is sent with every SSF
frame. R receives the SSF frames, determines the best sector $S^{\ast}_{I}$,
and computes an authenticator $\alpha_{R}$ of length $l_{\alpha}$ as

$\alpha_{R}=\text{auth}_{l_{\alpha}}(S^{\ast}_{I},v_{I},s)=\text{trunc}(h(S^{\ast}_{I},v_{I},s),l_{\alpha}),$

where $\text{auth}_{l_{\alpha}}(S^{\ast}_{I},v_{I},s)$ computes an
authenticator of size $l_{\alpha}$ as a truncated hash function of the
concatenation of $S^{\ast}_{I},v_{I}$ and $s$. In the responder sweep phase,
$R$ generates a nonce $v_{R}$. The initiator computes its authenticator as
$\alpha_{I}=\text{auth}_{l_{\alpha}}(S^{\ast}_{R},v_{R},s)$ for the optimally
selected sector $S^{\ast}_{R}$. After both devices complete their sweeps, $I$
sends $S^{\ast}_{R}$ and $\alpha_{I}$ in a feedback frame and $R$ acknowledges
with $S^{\ast}_{I}$ and $\alpha_{R}$. Finally, both devices verify the
received authenticators. If both verifications are successful, $I$ and $R$ set
their sectors accordingly. Without access to the shared secret $s$, $M$ cannot
create a forgery. Moreover, the nonces $v_{I}$ and $v_{R}$ guarantee
freshness.

Figure 5: Amplify-and-relay attack. $\mathcal{M}$ receives an authentic SSF
while $I$ is scanning sector 1. $\mathcal{M}$ amplifies and relays the SSF
without decoding. The responder authenticates the SSF and perceives sector 1
to yield the highest SNR.

##  III Amplify-and-relay Beam-Stealing Attack

The authenticated beam sweep protocol proposed in [28] is still vulnerable to
beam stealing attacks. This is because the cryptographic protections cannot
prevent Mallory from forging the wireless environment by simply amplifying
authentic SSFs. We present a new type of attack that we call amplify-and-relay
beam stealing that allows Mallory to attract $I$’s and $R$’s beams without
access to the shared secret $s.$

The attack operates as follows. Mallory positions herself at some location
between $I$ and $M$ away from the LoS (we later examine Mallory’s candidate
attack locations). Mallory is equipped with two directional antennas (or a
patch antenna that can operate two beams), which point towards the general
direction of $I$ and $R$, respectively. These antennas operate in quasi-omni
mode to allow reception of $I$ and $R$’s transmissions, as Mallory may not
know the exact position of the two devices and the wireless environment (e.g.,
blockage). During the initiator sweeping phase, Mallory receives an
authenticated SSF using the antenna pointing to $I$, amplifies it, and relays
it intact with the antenna pointing to $R$. The responder authenticates the
SSF and records the highest SNR from $M$’s direction due to the applied
amplification. The same amplification and relay is applied in the opposite
direction during the responder sweep frame phase, leading $I$ to indicate
$M$’s direction as the beast one for beam alignment.

We emphasize that although timely relay of the SSFs is helpful, it is not
necessary. First, the SLS protocol does not specify stringent timing
constraints between the transmission of successive SSFs at different sectors.
Second, some SSFs are not ever received by the intended receiver ($I$ or $R$)
due to antenna misalignment. Therefore, even if the relayed message arrives
late, it is not a replay of the direct transmission and freshness is not
violated.

Mallory can follow two amplification strategies when launching the beam
stealing attack. The first is the fixed power (FP) strategy in which
$\mathcal{M}$ relays received signal(s) at a fixed transmit power, regardless
of the received power. The closer distance of $\mathcal{M}$ to $I$ and $R$ (if
$\mathcal{M}$ is in between) or a higher transmit power than the legitimate
devices guarantees that $\mathcal{M}$’s relayed SSFs will be received with the
highest SNR. However, if Mallory transmits at fixed power for all incoming
SSFs, the receiver will measure the same SNR for several transmit sectors
leading to easy attack detection. To succeed in her attack, Mallory may relay
at high power only one SSF that she received. An alternate strategy is to
apply fixed amplification (FA) to any incoming SSF leading at varying received
power at the receiver. The main benefit of the $FA$ strategy is that the
received SNR is maximized when the transmitter ($I$ or $R$) is best aligned
with $\mathcal{M}$ (due to the highest received power at $\mathcal{M}$)
leading to a natural alignment of $I$ and $R$ with $\mathcal{M}.$

---
(a) RF chain of $I$ and $R$
(b) Hardware used in the platform
(c) Experimental topology
Figure 6: The mmWave experimental platform. |  |  |
---|---|---|---
(a) | (b) | (c) | (d)
Figure 7: (a)Amplify-and-relay beam-stealing attack on the initiator sector
sweep using $FP$ strategy, (b) attack on the initiator sector sweep using $FA$
strategy, (c) attack on the responder sector sweep using $FP$ strategy, (d)
attack on the responder sector sweep using $FA$ strategy.

###  III-A Demonstration of the Amplify-and-Relay Attack

In this section, we experimentally demonstrate the amplify-and-relay attack.

Experimental Setup. Our experimental setup consisted of USRPs and Wi-Fi cards
connected to the TMYTEK mmWave platform. Specifically, we implemented the
baseband functionality of the initiator and Mallory on two Ettus USRP N320s
[1]. Each USRP was connected to a TMYTEK up-down (UD) converter [2] that
upscaled the signal from the sub-6GHz to a center frequency of 28GHz with
160MHz bandwidth. Transmission took place via a directional BBox lite patch
antenna with 16 elements. The antenna supports electronically steerable
sectors with half-power beamwidth of $30^{\circ}$, covering the plane with 12
non-overlapping sectors. The maximum transmit power of the USRPs was 30dBm.
The platform configuration is shown in Fig. 6.

The responder was implemented with an AX 210 Wi-Fi card to allow for the
extraction of CSI measurements by the PicoScence CSI tool [16]. The signal was
received using the BBox lite antenna and downconverted to the sub-6 GHz band
using the UD converter. The card extract CSI measurements and computed the
RSS. Moreover, we used the Wi-Fi card to measure the noise floor, which
remained consistent at -128dBm throughout all the experiments. All hardware
was controlled by a desktop computer and synchronized using the Ettus
OctoClock-G module.

The experimental topology is shown in Fig. 7(a). We positioned all three
devices in a laboratory of rectangular shape with typical office furniture
(bookcases, desks with workstations, whiteboards, etc.) $I$ and $R$ were
placed 4.3m apart whereas $\mathcal{M}$ was placed in between (but not in the
LoS) at distances 2.4m and 2.7m from $I$ and $R$, respectively. To mimic the
SLS protocol in IEEE 802.11ad as we described in Section II-A, we fixed the
$R$’s beam and employed the TMXLAB Kit to electronically steer $I$’s beam. The
transmitter conducted a $360^{\circ}$ sweep of the entire plane. Upon
completion of one sweep, $R$ switched to the next fixed receive direction
while $I$ repeated the sweep. This sector sweep process was repeated in the
other direction (with $I$ and $R$ switching roles) to determine the optimal
beam of $R$.

During a fixed power attack, the legitimate devices and Mallory transmitted at
10dBm, whereas during a fixed amplification attack, $\mathcal{M}$ amplified
its received signal by 70dB. Mallory was synchronized with the initiator and
the responder via the the Ettus OctoClock-G module and transmitted the same
SSF frame at the same time as the initiator or the responder (depending on the
round).

Attack Evaluation. In Fig. 7, we show the highest measured SNR at the
responder during the initiator sweep phase. Figure 7(a) corresponds to a fixed
power attack. Without an attack, the responder measures the highest SNR when
the initiator transmits at sector 1. During the attack, Mallory only amplified
beam sector 12 that is best aligned towards her. Therefore, the responder
measures the same SNR in all other sectors except sector 12, where the SNR is
about 10dB higher than that of sector 1. This results in informing $I$ that
its best transmitting sector is sector 12, thus beamforming towards
$\mathcal{M}.$ Figure 7(b) shows the fixed amplification attack case that
causes the same optimal sector change as the $FP$ attack. One main difference
is that during an $FA$ attack, all sectors are amplified at the same gain thus
causing an elevated SNR at $R$ compared to the absence of the attack.

Figures 7(c) and 7(d) show the $FP$ and $FA$ attacks launched during the
responder sector sweep phase. In both attacks, the beam selection shifts from
sector 7 to sector 8 pointing to $\mathcal{M}$ instead of the LoS. We note
that when $I$ and $R$ use sectors 12 and 8 respectively, they can no longer
directly communicate. The only way to communicate is via $\mathcal{M}.$ To
verify the generality of the attack with respect to the adversary positioning,
we repeated the experiments with $\mathcal{M}$ placed behind the initiator.
The results of the second setup verify the attack feasibility and are
presented in Appendix -A.

##  IV A baseline Defense Method

We first propose a baseline method for detecting amplify-and-relay attacks
that exploits the invariable physical properties of propagation time. The main
idea is to use the longer signal propagation and processing times of the relay
path over the legitimate path. This method is specifically applicable to the
mmWave environment where multipath is limited. We use power delay profile
(PDP) analysis to measure the timing of various paths and correlate it to the
received power. As the mmWave signal attenuates rapidly with distance, it is
expected that the LoS path is the strongest and takes the least delay to
propagate to the receiver. Detecting high SNR at a path with higher delay is
indicative of an amplify-and-relay attack, provided that the LoS path (or any
other shorter path) is unobstructed.

The PDP can be derived from the receiver’s channel impulse response (CIR)
[25]. Let $X(f,t)$ and $Y(f,t)$ be the transmitted and received signals in the
frequency domain and $H(f,t)$ be the CSI. Then $H(f,t)$ can be expressed as

$H(f,t)=\frac{Y(f,t)}{X(f,t)}=e^{-j2\pi\Delta
ft}\sum_{k=1}^{N}a_{k}(f,t)e^{-j2\pi f\tau_{k}(t)},$

where $e^{-j2\pi\Delta ft}$ is the phase shift caused by the carrier frequency
difference $\Delta f$ between $I$ and $R$, $N$ is the number of paths,
$e^{-j2\pi f\tau_{k}(t)}$ is the the phase shift caused by the delay
$\tau_{k}(t)$ of the $k^{th}$ multipath, and $a_{k}(f,t)$ is the amplitude of
the $k^{th}$ multipath. Then the CIR, $h(t,\tau)$ can be calculated by
applying an IFFT to the CSI,

$h(t,\tau)=\sum_{k=1}^{N}a_{k}(t,\tau)e^{-j\theta_{k}(t,\tau)}\delta[\tau-\tau_{k}(t)],$

where $e^{-j\theta_{k}(t,\tau)}$ is the phase shift and $\delta[\cdot]$ is a
delta function. If choosing a time period equal or smaller than the channel’s
coherence time, the CIR can be considered to be constant. Then the amplitude
of the CIR, $|h(\tau)|$, can be extracted as,

$|h(\tau)|=\sum_{k=1}^{N}a_{k}(\tau)\delta(\tau-\tau_{k}),$

and the PDP is $|h(\tau)|^{2}$. Instead of using the PDP of each transmit
sector directly, we apply an additional step to calculate the collective power
delay profile (CPDP). Specifically, we extract the amplitude and time delay of
the highest amplitude path from the PDP of each SSF transmission and combine
them in a single CPDP. This combination is possible only if time can be
measured at high accuracy (which is possible at mmWave due to the available
bandwidth) and if SSFs are transmitted periodically at precisely known times.
In benign scenarios, the first peak of the CPDP corresponds to the LoS path
between legitimate users. The signal strength received from this path is
expected to be the strongest among all possible sectors. If a path that
appears later has a stronger RSS, an attack is detected. Note that any
reflections in mmWave not only travel longer distances, but also experience
high attenuation due to the lower reflection coefficients as the small
wavelength is comparable to surface imperfections.

Figure 8: Topology. |
---|---
(a) | (b)
Figure 9: CPDP: (a) without attack, the first peak is the strongest. (b) with
a beam-stealing attack, the fourth peak is the strongest.

Numerical Examples. We utilized the ray-tracing-based simulator mmTrace [29]
to provide an illustration of how to employ CPDP to detect relay attacks in
the initiator sector sweep. The topology under consideration is depicted in
Fig. 8. The distances between devices are $d_{IR}=5m$, $d_{MR}=4.1m$ and
$d_{IM}=4m$. The initiator ($I$) is configured with $N=32$ sectors with a HPBW
of $12^{\circ}$, while the responder ($R$) is equipped with six non-
overlapping quasi-omni patterns with an HPBW of $60^{\circ}$. $I$ conducts an
SLS sweep for each quasi-omni pattern, while $R$ measures the PDP for each
transmit sector and extracts the highest amplitude path from each PDPs to
create CPDP. If $R$ observes multiple peaks with the same delay in different
quasi-omni patterns, he chooses the one with the highest RSS.

The results of CPDP without attack is illustrated in Fig. 9(a). It is observed
that the signals arriving later are weaker than the first peak as they travel
along longer paths. However, in the presence of a beam-stealing attack (Fig.
9(b)), the fourth peak is stronger than earlier peaks, even though it comes
from a longer path. This is due to the adversary amplifying and relaying the
signal on that path. In such a scenario, $R$ can detect the attack and reject
the signal from $I$. Note that our results do not include any processing
delays due to relaying.

It should be noted that Mallory could avoid detection if it lies in the LoS
path. However, the beam-stealing attack is not meaningful because the beams of
$I$ and $R$ will lie in the optimal path and $I$ and $R$ can directly
communicate unless $\mathcal{M}$ introduces physical blockage. Moreover, this
method does assume the existence of a faster path (e.g. LoS) than the
adversary’s relay. Finally, the stringent synchronization requirement for
computing the CPDP may require custom hardware [27]. To address these
limitations, we propose an alternative protocol based on path loss and AoA.

---
(a) Physical layer commitment
(b) Coarse AoA detection
Figure 10: Overview of the SecBeam protocol: (a) the two sector sweep rounds
of the SecBeam protocol and (b) when $\mathcal{M}$ relays all sectors it
hears, $R$ receives multiple SSFs over the same receiving sector, indicating
the same coarse AoA.

##  V The SecBeam Protocol

We propose SecBeam, a secure beam sweeping protocol that detects amplify-and-
relay attacks. To thwart fixed power amplification attacks, SecBeam implements
a physical-layer commitment scheme were a transmitter commits to use the same
power level over successive transmission rounds. Moreover, SecBeam
incorporates coarse angle-of-arrival (AoA) information to detect fixed
amplification attacks. To motivate the SecBeam design, we first provide an
overview of the focal ideas and follow with a detailed protocol description.

###  V-A Overview

The main challenges in detecting an amplify-and-relay attack are that (a)
cryptographic operators are not violated during a signal relay and (b) $I$ and
$R$ do not have any prior knowledge of their relative positions and of the
wireless environment. Without this information, a receiver cannot detect if a
physical property such as SNR has been altered.

Physical layer commitments. To counter fixed power attacks, we construct a
physical-layer security primitive that resembles a commitment scheme. We
extend the SLS protocol to operate in two rounds. During the first round, $I$
sweeps across each beam sector $S_{i}$ sequentially using maximum power
$P_{\max}$. The responder $R$ calculates the path loss at round 1 as
$PL_{i}(1)=P^{T}_{i}(1)-P^{R}_{i}(1)$ by subtracting the received power from
the transmit power (in dB) using $P^{T}_{i}(1)=P_{\max},\forall i.$ This round
serves as a physical commitment to the wireless environment even if this
environment is distorted by Mallory.

During the second round,$I$ repeats the sector sweep with two randomizations
in place. First, $I$ randomizes the sector sweeping sequence so it is no
longer sequential. Second, $I$ randomizes the transmit power on every sector.
The sector ID $S_{i}$ and the transmit power $P^{T}_{i}(2)$ are included in
the SSF (which is encrypted). The responder calculates the path loss at round
2 and verify that $PL_{i}(1)\approx PL_{i}(2),\forall i.$ This round serves as
a physical decommitment, where the transmit power $P^{T}_{i}(2)$ and sector ID
$S_{i}$ are used to physically verify the commitment of the first round. An
example of the two-round sector sweep is shown in Fig. 10(a).

The power and sweeping sequence randomization have two effects on Mallory’s
attack. If Mallory amplifies both rounds at fixed power, the path loss
computed by $R$ would be different between the two rounds, thus revealing the
attack. Mallory could attempt to detect the potentially lower received power
from $I$. However, the randomization of the sweeping sequence and encryption
of the sector ID does not allow Mallory to infer which sector it is receiving
from at each round. Since Mallory does not know which sector in the second
round corresponds to the one she relayed in the first round she could not fine
tune its transmit power to make the path loss consistent across both rounds.
The only strategy that is viable is to amplify all sectors overheard at
$\mathcal{M}$ with fixed amplification, that is, to launch a fixed
amplification attack.

Coarse AoA detection. To counter fixed amplification attacks, we exploit
another physical layer phenomenon that arises in the presence of a relay.
Because Mallory is forced to apply a fixed amplification to all sectors (SSFs)
it hears, an unusually high number of sectors will appear to arrive from the
same direction. That is, although the initiator is sweeping the plane, the
signal arrives to the responder from the same direction, thus indicating the
presence of a relay. In the example of Fig. 10(b), sectors 1, 2, 6, and 7 all
appear to be received at the same sector of $R.$ To extract AoA information
without requiring the application of complex AoA estimators such as MUSIC [13]
during the sweeping process, $R$ uses the quasi-omni mode to roughly estimate
the incoming direction of a received signal. As the quasi modes are switched,
$R$ can calculate for how many transmitting sectors each quasi-omni receiving
sector appears to be the optimal. It can then use those statistics for
detecting relays.

###  V-B Protocol details

We now present the detailed steps of the SecBeam protocol. The protocol is
facilitated by a shared secret $s$ established between $I$ and $R$ using
public keys, as described in [28].

First round initiator sector sweep.

  1. 1.

The initiator and the responder derive keys $k_{1}$ and $k_{2}$ from the
shared common secret $s.$ Key $k_{1}$ is used for integrity protection and
$k_{2}$ is used for encryption.

  2. 2.

The initiator sweeps through sectors $S_{1},S_{2},\ldots S_{N}$ in this order
and transmits sector sweep frame $SSF_{i}^{I}(1)$ at each $S_{i}$, using the
fine-beam mode. Each $SSF_{i}^{I}(1)$ contains an authenticator
$\alpha_{i}(1)=\text{MAC}(S_{i},P_{i}^{T}(1),v_{i}(1),k_{1})$, where MAC is a
message authentication code function, $P_{i}^{T}(1)$ is the transmission power
of $SSF_{i}^{I}(1)$ and $v_{i}(1)$ is a nonce. The initiator attaches
$\alpha_{i}(1),P_{i}^{T}(1),v_{i}(1)$ to $SSF_{i}^{I}(1)$, encrypts it with
$k_{2}$ and transmits it at power $P_{i}^{T}(1)=P_{\max}.$

  3. 3.

The responder decrypts $SSF_{i}^{I}(1)$ using key $k_{2}$ and verifies the
authenticator $\alpha_{i}(1)$ using $k_{1}$. The responder records the path
loss $PL_{i}(1)=P_{\max}-P_{i}^{R}(1)$, where $P_{i}^{R}(1)$ is the received
power from sector $S_{i}.$

  4. 4.

The responder finds the sector with the smallest path loss (highest SNR) as
$S^{\ast}_{I}(1)=\arg\min_{i}PL_{i}(1)$.

First round responder sector sweep.

  1. 5.

The initiator and the responder switch roles and repeat steps 1) to 4). Each
sweep frame $SSF_{i}^{R}(1)$ includes the best sector $S^{\ast}_{I}$ and the
path loss vector $PL(1)=\\{PL_{1}(1),PL_{2}(1)\ldots Pl_{N}(1)\\}$ in the SSW
feedback field.

Second round initiator sector sweep.

  1. 6.

The initiator calculates the transmission power range for each sector $S_{i}$
as $r_{i}:[P_{i,\min},P_{\max}-\epsilon].$ Here, $P_{i,\min}$ is the minimum
transmission power that allows decoding at $R$ and is calculated as
$P_{i,\min}=P_{f}+PL_{i}(1),$ where $P_{f}$ is the receiver’s sensitivity.
Parameter $\epsilon$ is the expected path loss variation over the same path.

  2. 7.

The initiator perturbs the sector sweep sequence $S=\\{S_{1},S_{2},$
$\ldots,S_{N}\\}$ using a pseudorandom permutation $\Pi.$ The initiator sweeps
through the $N$ sectors using sequence $\Pi(S).$

  3. 8.

For each sector $S_{i}$, $I$ randomly selects the transmission power
$P_{i}^{T}(2)\in r_{i}$, calculates authenticator $\alpha_{i}(2)$, attaches
$\alpha_{i}(2),P_{i}^{T}(2),v_{i}(2),$ and $S_{i}$ to $SSF_{i}^{I}(2)$,
encrypts it with $k_{2}$ and transmits it with power $P_{i}^{T}(2)$.

  4. 9.

Path loss test: The responder decrypts the $SSF_{i}^{I}(2)$ using key $k_{2}$
and verifies the authenticator $\alpha_{i}(1)$ using $k_{1}$. The responder
records the path loss $PL_{i}(2)=P_{i}^{T}(2)-P_{i}^{R}(2)$, where
$P_{i}^{R}(2)$ is the received power from sector $S_{i}$ during the second
round. If $|PL_{i}(1)-PL_{i}(2)|>\epsilon$, $R$ detects an attack and aborts
the protocol. Parameter $\epsilon$ is the same expected path loss variation
over the same path as in Step 6.

  5. 10.

Coarse AoA test: The responder records the quasi-omni receive sector that
experiences the least path loss from each transmit sector $S_{i}.$ It
maintains the fraction of sectors heard at each receive sector as
$F=\\{f_{1},f_{2},\dots,f_{L}\\}$, where $L$ is the total number of quasi-omni
sectors that cover the plane. If $f_{j}>\beta\cdot N,j=1,2,\cdots,L$, $R$
detects an attack and aborts the protocol.

Second round responder sector sweep.

  1. 11.

The responder and the initiator switch roles and repeat steps (6) to (10).

###  V-C Security Analysis of SecBeam

Forgery attacks. The original SLS protocol is susceptible to forgery attacks
where Mallory can forge SSFs and change the feedback field on the optimal
transmitting beam [30]. Such attacks are prevented in SecBeam due to the
addition of integrity protection on the SSFs. Without access to the shared key
$s,$ Mallory cannot recover $k_{1}$ to generate a valid MAC (under standard
security assumptions for the MAC function). This security property is similar
to the one provided by the authenticated SLS in [28].

Detection of Fixed Power Attacks. Fixed power attacks are countered by the
power randomization method that is employed in the second round of SecBeam.
This is because when relaying SSFs at fixed power, the path loss test of Step
9 is violated. We demonstrate this in Proposition 1.

######  Proposition 1.

A fixed power attack on sector $S_{i}$ is detected by the path loss test if
the transmission power $P_{i}^{T}(2)$ in the second round satisfies

$P_{i}^{T}(2)<P_{i}^{T}(1)-\epsilon,$

where $\epsilon$ is a noise-determined parameter.

###### Proof.

The proof is provided in Appendix B. ∎

The intuition behind Proposition 1 is that by transmitting at a power lower
than $P_{i}^{T}(1)-\epsilon$ in the second round, the path loss difference
between the two rounds will violate the path loss test (will exceed
$\epsilon$) because the adversary relays at the same power, regardless of the
transmission power of $I$. Parameter $\epsilon$ must be selected in such a way
to account for the natural path loss variations between rounds. Such
variations are expected to be primarily caused by noise, as the geometric
properties of the mmWave channel lead to long coherence times in most
environments of interest. We study the choice of $\epsilon$ in the evaluation
via simulations and experiments.

Detection of Fixed Amplification Attacks. In a fixed amplification attack,
Mallory applies a fixed gain to each sector she relays as opposed to
transmitting at fixed power. Let Mallory receive from $N_{M}\leq N$ sectors
during the first round initiator sector sweep, when
$P_{i}^{T}=P_{\max},\forall i$. Let also $K\leq N_{M}$ denote the sectors
that, when amplified, achieve an SNR higher than the optimal sector without
attack. The probability of passing the path loss test in the second round
initiator sector sweep is given by Proposition 2.

Figure 11:  $P_{BS}$ when $N=32$, $N_{M}=21$ and $K=19$.

######  Proposition 2.

Given the number of sectors $N_{M}$ heard at $\mathcal{M}$ and the number of
sectors $K$ in $N_{M}$ with path loss smaller than the best path without
attack under a fixed amplification strategy, the probability $P_{BS}$ of a
successful beam stealing attack is given by

$Pr_{BS}=\frac{1}{\binom{N_{M}}{x}^{4}}\cdot\left(\sum_{i=1}^{\min(x,K)}\binom{K}{i}\binom{N_{M}-K}{x-i}\right)^{2}.$

###### Proof.

The proof is provided in Appendix C. ∎

Discussion. The probability of success for the fixed amplification attack is a
function of the number of sectors $N_{M}$ heard at $\mathcal{M}$ which is
location- and wireless environment-dependent and the choice of $x$. It is
evident that $Pr_{BS}$ becomes 1 when $x=N_{M}$ (i.e., Mallory amplifies all
sectors it hears in both rounds). The coarse AOA test is introduced to prevent
the success of this strategy. When Mallory amplifies and relays all $N_{M}$
sectors, the responder detects an unusual number of sectors arriving from the
direction of the relay, thus detecting the attack. For values of $x$ smaller
than the coarse AoA test $\beta N,$ the probability of success rapidly
declines due to the requirement of relaying the same set of sectors on both
rounds. In fact, based on the convexity of the binomial distribution [24],
selecting $x=1$ becomes Mallory’s most beneficial strategy. In this case, the
probability of success is $Pr_{BS}=K^{2}/N_{M}^{4}.$

As an example, Fig 11 shows $P_{BS}$, when $N=32,$ $N_{M}=21$ and $K=19.$ With
$\beta=0.5$, Mallory must select $x<16$ to pass the coarse AoA test with
certainty. In this case, $x=1$ yields the highest passing probability which is
in the order of $10^{-3}.$ This is a fairly low probability for an online
attack.

Another important remark for the analysis is that we have made the reasonable
assumption of an adversary that does not know a priori the exact locations of
$I$ and $R$. Therefore she uses quasi-omni beams to the general directions of
$I$ and $R$ in order to receive, amplify, and relay. If the adversary could
exactly pinpoint $I$’s and $R$’s locations, she could point fine beams at each
party, therefore substantially reducing the number of sectors $N_{M}$ received
by $\mathcal{M}.$ In this case, relaying all $N_{M}$ sectors passes the path
lost test, while also defeating the coarse AoA test if $N_{M}<\beta N.$

##  VI Parameter Selection and Evaluation

|
---|---
(a) | (b)
Figure 12: (a) LoS is unobstructed, (b) LoS is blocked by an obstacle with
permittivity equal to 2. $\mathcal{M}$ was placed at two different locations.
Figure 13: PDF and CDF of $\Delta P$ given $\sigma=1.8$

In this section, we use simulation based on ray-tracing (mmTrace) [29] to
select parameters for SecBeam and evaluate its security. The insights from the
simulations guide our experimental evaluations.

###  VI-A Simulation Setup

We consider two scenarios in our simulations, one where the LoS path between
$I$ and $R$ is unobstructed (Fig. 12(a)), and the other one with the LoS
blocked by an obstacle (Fig. 12(b)). All devices are placed in a self-defined
room with a size of $5m\times 5m$, where the wall permittivity is set as 3.24.
The center coordinate of the room is set to $(0,0)$, and the distance between
$I$ and $R$ is $d_{IR}=5m$. In addition, we consider two possible locations
for $\mathcal{M}$: $(1,0)$ and $(2,-2)$, which result in different distances
between $I$, $R$, and $\mathcal{M}$, shown in Table II. Each device has $N$
sectors in total, so the HPBW is $\lceil\frac{360^{\circ}}{N}\rceil$.
Additionally, the HPBW of $I$ and $R$’s quasi-omni pattern is $60^{\circ}$,
and their maximum transmit power is $P_{max}=0$ dBm. The initiator follows our
protocol to perform the two-round sector sweep, using $P_{max}$ in the first
round and randomized power in the second round. The adversary implements the
amplify-and-relay attack strategy with fixed amplification.

TABLE I: Simulation scenarios |  $d_{IR}$ |  $d_{MR}$ |  Room size |  Amp.
---|---|---|---|---
Scenario 1 |  5m |  1m |  $5\times 5\times 5$m |  40 dB
Scenario 2 |  5m |  1m |  $5\times 5\times 5$m |  50 dB
Scenario 3 |  5m |  1m |  $5\times 9\times 5$m |  40 dB
Scenario 4 |  5m |  $4.1$m |  $5\times 5\times 5$m |  70 dB
Scenario 5 |  5m |  $5.4$m |  $9\times 9\times 9$m |  70 dB
Figure 14: The highest frequency of a sector being the best receive sector with and without $\mathcal{M}$ in different scenarios. (a) | (b)
---|---
Figure 15: Path loss difference with $\mathcal{M}$ in LoS and NLos scenarios: (a) $\mathcal{M}$ chooses the same sector in two rounds of SSW, (b) $\mathcal{M}$ chooses different sectors in two rounds of SSW. (a) | (b)
---|---
Figure 16: Passing rates of a legitimate device ($P_{I}$ or $P_{R}$) and $\mathcal{M}$ ($P_{FA}$) versus $\beta$, for different $N$. (a) | (b) | (c) | (d)
---|---|---|---
Figure 17: Simulation results without $\mathcal{M}$: (a) RSS measured by $R$ when LoS is unobstructed, (b) path loss difference between two rounds when LoS is unobstructed, (c) RSS measured by $R$ when LoS is blocked, (d) path loss difference between two rounds when LoS is blocked. The path loss difference is lower than the threshold in both LoS and NLoS scenarios. |  |  |
---|---|---|---
(a) | (b) | (c) | (d)
Figure 18: When LoS between $I$ and $R$ is unobstructed:(a) The best Tx and Rx pair $S_{ij}$ without relay attack. (b) $S_{ij}$ under relay attack. (c) the frequency of a Rx sector being chosen as the best receive sector under relay attack. (d) $S_{ij}$ in a real setting. |  |  |
---|---|---|---
(a) | (b) | (c) | (d)
Figure 19: When LoS between $I$ and $R$ is blocked:(a) The best Tx and Rx pair
$S_{ij}$ without relay attack. (b) $S_{ij}$ under relay attack. (c) the
frequency of an Rx sector being chosen as the best receive sector under relay
attack. (d) $S_{ij}$ in a real setting. Sectors at RX are the best receive
sectors for the transmit sectors indicating in the same color in Tx.

###  VI-B Parameter Selection

The SecBeam protocol is parameterized by the threshold of path loss difference
$\epsilon$ and the frequency of one sector being chosen as the best receive
sector $\beta$. In the following, we use simulations to help with selection of
these parameters.

Selecting $\epsilon$. The value of $\epsilon$ needs to be selected high enough
to prevent false alarms when $\mathcal{M}$ is not present. The path loss can
be generally written as,

$PL(dB)=G_{T}(dBi)+G_{R}(dBi)-L_{ch}(dB)+X_{\sigma}(dBm),$ (1)

where $P^{T}$ is the transmit power, $G^{T}$ and $G^{R}$ are the respective
antenna gains, $L_{ch}$ is the channel attenuation according to some unknown
channel model, and $X_{\sigma}$ is a zero-mean Gaussian noise with a standard
deviation $\sigma$. Assuming fixed locations and paths, the path loss
difference $\Delta P(dB)$ between the two rounds is,

$\Delta P=\lvert PL_{i}(2)-PL_{i}(1)\rvert=\lvert
X_{\sigma}(2)-X_{\sigma}(1)\rvert.$ (2)

The path loss difference $\Delta P$ follows a folded normal distribution with
a $\frac{\sigma\sqrt{2}}{\sqrt{\pi}}$ mean and $\sigma^{2}(1-\frac{2}{\pi})$
variance. A typical value for $\sigma$ in the indoor environment is 1.8 [38].
The probability density function (PDF) and the cumulative distribution
function (CDF) of $\Delta P$ is shown in Fig. 13. In order to ensure a
specific passing rate of valid devices, we can select a suitable value for
$\epsilon$ based on the CDF of $\Delta P$. For instance, in our study, we
choose $\epsilon=6.6$dB to ensure that under benign conditions, the path loss
difference due to noise is less than $\epsilon$ with probability 99$\%$.

Selecting $\beta$. We then used our simulation results to determine the
threshold $\tau$. The optimal value of $\beta$ depends on the physical
environment. We listed five different simulation setups in Table. I where we
vary the room size, locations of $I$ and $\mathcal{M}$, and the amount of
amplification (Amp.) used by $\mathcal{M}$. The total number of sectors is
$N=32$ in all scenarios. We extract the highest frequency $f_{j},j=1,\dots,N$
in each setup with and without a relay attack, and the results are shown in
Fig. 14. In all the scenarios, there are a clear distinction between the beam
selection frequencies of benign and adversarial settings, which shows the
feasibility of the coarse AoA test.

In addition, we performed 1,000 simulations for $N=16,32$, and 64 with
different combinations of the locations of $I$ and $R$, room size, and
amplification gain. The passing rate of legitimate devices and $\mathcal{M}$
versus $\beta$ is shown in Fig. 16. We can see that the passing rate of $I$
and $FA$ attacker ($P_{I}$ and $P_{FA}$) both increase with $\beta$. When
$\beta=0.5$, $P_{I}=1$ while $P_{FA}=0$. So we conclude that $\beta=0.5$ is
sufficient to detect the attack for all values of $N$. It is worth mentioning
that when the LoS between $I$ and $R$ is blocked, the frequency of one sector
being selected as the best receive sector is higher than those shown in Fig.
14, since the LoS between $\mathcal{M}$ and victims is always unobstructed. We
discuss this in Sec. VI-C2.

###  VI-C Simulation Results

####  VI-C1 Fixed power relay attack

We use Setup 1 to demonstrate the security of SecBeam against the fixed power
relay attack. We show the results of the RSS measured by $R$ in two rounds and
the path loss difference when LoS is unobstructed and blocked in Fig. 17. From
Fig. 17(a), sector 22 is chosen as the best sector in the first round, while
in Fig. 17(c), the best sector is 30 because the LoS is blocked. We can also
see that the path loss difference across two rounds is smaller than the
threshold $\epsilon$ for all sectors, no matter whether the LoS is blocked or
not.

When the adversary is present, the results are shown in Fig. 15. When
$\mathcal{M}$ chooses different sectors in two SSW rounds, e.g. sector 30 in
the first round and sector 20 in the second round (Fig. 15(b)), the path loss
difference exceeds $\epsilon$ in both cases. Even if $\mathcal{M}$ could
choose the same sector in two SSW rounds coincidentally, (e.g. Sector 20 in
Fig. 15(a)), the pass loss difference is still higher than $\epsilon$ due to
the relay at fixed power and the power randomization by $I$.

####  VI-C2 Fixed amplification attack

Next, we show the simulation results when $\mathcal{M}$ uses the fixed
amplification relay strategy under simulation setup 2. We assume that
$\mathcal{M}$ amplifies all the received beams by 60 dB and relays them to
$R$. When LoS is unobstructed, the results are shown in Fig. 18. From Fig.
18(a), we can see that in the benign case, even if some receive sectors, e.g.
Sectors 6 and 8, are chosen more than once, $f_{6}=7/32$ and $f_{8}=7/32$ are
less than the threshold $\beta=0.5$. However, in Fig. 18(b) and (c),
$f_{10}=20/32$ under the FA attack, which is higher than the threshold, thus
$\mathcal{M}$ is detected. When the LoS is blocked, the results are shown in
Fig. 19. In this case, there is no dominant path between $I$ and $R$, and the
obstacle acts as a reflector. The best receive sector does not present any
strong directionality. Comparing with Fig. 18(b) and (c), we can observe
sector 10 is the best receive sector for 29 transmit sectors in Fig. 19(b) and
19(c) as expected.

##  VII Experimental Evaluation

###  VII-A Experimental Setup

To demonstrate the effectiveness and security of SecBeam in the real world, we
implemented it using our mmWave testbed as described in Section III-A.

Figure 20 provides an overview of the experimental setup, where $d_{IM}$ was
3m and $d_{MR}$ was 2.4m. To increase the number of reflection paths in the
environment, in certain setups, we added a whiteboard and a stop sign in the
room. The relay attack was implemented by synchronizing $\mathcal{M},$ $I$ and
$R$ via the Octo-clock module. This way the adversary could transmit the same
SSF frame synchronously with the legitimate devices, without incurring the
hardware delay of USRPs for switching between reception and transmission.

During the experiments, the transmitter sent 10,000 packets in each sector
with a 5 milliseconds delay between packets to facilitate data collection (In
reality, only one packet will be sent in each sector). In the first round, $I$
swept in its maximum transmit power $P_{max}=30$dBm. In the second round, $I$
randomly chose the transmit power sequence for each sector. For the fixed
power relay attack, the adversary chose signals from one Tx sector and relayed
them to the receiver using $P_{max}$. For the fixed amplification relay
attack, $\mathcal{M}$ amplified its received signals from $I$ with a fixed
amount and then relayed them to $R$.

Figure 20: Experimental setup. (a) without attack | (b) under attack
---|---
Figure 21: Path loss difference without and under attack during the initiator sector sweep phase. (a) | (b)
---|---
Figure 22: Experimental results without $\mathcal{M}$: (a) frequency of a
sector being chosen as the best receive sector with artificial reflectors, (b)
Frequency of a sector being chosen as the best receive sector without the
artificial reflectors.

###  VII-B Security Evaluation of SecBeam

####  VII-B1 Security against the fixed power relay attack

In our experimental setup, there are 7 transmit sectors that can be detected
by $R$ in the first round of sector sweep. The transmit powers for each sector
are randomly chosen as $P_{i}^{T}(2)=\\{16,7,22,0,10,9,18,19,4,11,10,15\\}$dBm
in the second round of sector sweep. The SNR measured at $R$ in two rounds of
SSW consist of two matrices of dimension $10,000\times 7$. Using these SNR
data and the known transmit power values, we calculated the average path loss
differences over 10000 measurements for each sector, shown in Fig. 21. We
observe that when there is no adversary present, the average path loss
difference for all sectors remains under 0.5 dB, and all 10000 path loss
differences for each transmit sector are smaller than the threshold
$\epsilon=6.6$. However, when the $FP$ attack is carried out, the average path
loss difference for the affected sector ($r_{12}$ in this example) is 14.9875
dB, which is greater than $\epsilon=6.6$.

####  VII-B2 Security against fixed amplification relay attack

We first present the frequency of any receive sector being chosen as the best
sector for legitimate devices, as illustrated in Figure 22. From Fig. 22(a),
when the artificial reflectors are present in the environment, the frequency
of choosing sector 7 at $R$ as the best sector is found to be $f_{7}=3/12$.
However, after removing the reflectors, in Figure 22(b), sector 7 at $R$ was
chosen 4 times out of 12 as the best receiving sector, resulting in
$f_{7}=4/12$. The values of $f_{7}$ in both environments are lower than the
threshold $\beta$, which indicates that the legitimate devices can pass the
coarse AoA test.

In the presence of an adversary, we conduct an experiment where the adversary
attempts to relay all the received signals to the intended receiver $R$. Our
experimental results, as shown in Fig. 23, revealed that the probability of
the adversary successfully relaying signals to $R$ from sector 3 was high
($f_{3}=9/12$) and exceeded the threshold value of $\beta=0.5$, indicating
that the $FA$ attack is detected. We show the best transmit and receive beam
pair $S_{ij}$ for this setup in Fig. 23(c). The black sectors in Fig. 23(c)
means that signals sent using these sectors cannot be received by $R$. When we
removed the reflectors, $f_{3}$ further increased to 11/12 as shown in Figs.
23(b) and (d), which is above the threshold value of $\beta$. The adversary is
detected.

(a) | (b)
---|---
|
(c) | (d)
Figure 23: Experimental results under $FA$ relay attack: (a) Frequency of a
sector being chosen as the best receive sector when artificial reflectors are
in the environment. (b) Frequency of a sector being chosen as the best receive
sector without artificial reflectors. (c) $S_{ij}$ on real mmWave devices with
artificial reflectors. (d) $S_{ij}$ on real mmWave devices without artificial
reflectors.

###  VII-C Time Efficiency of SecBeam

The run time of SecBeam is dominated by the number of sectors at the devices.
The time required for RSS and AoA measurements is negligible. Let the size of
each sector sweep frame be $F$ bytes, the number of frames sent by each sector
be $Y$, bandwidth be $BW$, both $I$ and $R$ have $N_{q}$ quasi-omni patterns,
the time interval between frames sent by the same antenna, Short Beamforming
Interframe Spacing (SBIFS), be $T_{S}$ and the time consumed to switch quasi-
omni pattern, Long Beamforming Interframe Spacing (LBIFS), be $T_{L}$. The
total time for protocol execution is computed as
$2N_{q}(N(\frac{YF}{BW}+(Y-1)T_{S})+(N-N_{q})T_{S}+(N_{q}-1)T_{L})+2(N_{q}-1)T_{L}$.
If we assume $F=26$, $Y=1$, $T_{S}=1\mu s$, and $T_{L}=18\mu s$ as defined in
the 802.11ad standard [14], $N=32$, $N_{q}=6$, and $BW=160$ MHz, the total
time consumed by SecBeam is 2.07 ms.

##  VIII Related Work

Relay attacks. The amplify-and-forward beam stealing attacks is a relay type
of attack. However, existing relay attacks against wireless systems have
different purpose. The majority of relay attacks aim at violating the
proximity/distance constraint between two devices (a prover and a verifier),
for applications where proximity-based access control is needed. For example,
keyless entry and start systems for cars [8, 9], contactless payment systems
with smartcards/RFID [17], etc. We emphasize that the beam-stealing attack
differs from the above relay attacks, since it aims at distorting the path-
loss property rather than proximity or distance. In addition, there is no
location restriction imposed on the attacker.

There is also another type of relay attack in the literature, namely signal
cancellation/annihilation attack [5, 23, 21, 12], where the attacker aims at
causing destructive interference at the intended receiver(s) of a wireless
communication link, which either leads to denial-of-service, or can be used to
achieve message modification via arbitrary bit flips. However, signal
cancellation is generally hard to carry out since it requires precise timing
and phase synchronization, which is also more challenging in mmWave
communication systems due to the directionality of the beams. In contrast, the
amplify-and-forward beam stealing attack is a form of MitM attack which
disrupts beam selection so that the attacker has full control of the
communication link between the legitimate devices (it can eavesdrop, modify,
or perform DoS against the messages exchanged). In addition, it is easier to
implement than signal cancellation.

Relay Attack Defenses. Existing defenses against relay attacks are not
applicable to defend against beam-stealing attacks in general. For example,
distance bounding protocols [7, 3, 6] aim at enforcing a lower-bound of the
distance from a prover to the verifier. However, we target general
communication scenarios where no proximity/distance bound is imposed on the
communicating devices. Although one can also use distance bounding as a secure
signal path length measurement to indirectly prove that no longer paths than
the dominating path (e.g., LoS) has a lower path-loss, implementing distance
bounding typically requires advanced hardware capabilities [32]. Moreover, $I$
and $R$ have no knowledge of the wireless environment. If a stronger signal
appears on a longer path, this could be because the shorter path experiences
higher absorption or diffraction if it is not the LoS.

Existing relay attacks can also be detected by verifying the co-presence of
devices via some common context, such as ambient conditions (e.g., sound,
lighting, motion, RF signals, etc) [19, 34, 33, 40, 20]. However, as stated
earlier, they are not applicable to defend beam-stealing attacks due to the
different purpose and assumptions of the attack.

On the other hand, another category of defenses utilize physical-layer
identification/RF fingerprinting methods to identify the transmitting devices
(or fingerprint the channel between the devices) via their signal
characteristics, in order to detect impersonation attacks or distinguish
different devices. For example, Balakrishnan $et\ al.$ [4] fingerprint mmWave
devices based on features extracted from their spatial-temporal beam patterns
and demonstrated the resistance of their protocol against impersonation
attacks. Wang $et\ al.$ [36, 35] adopted a similar idea, and utilized machine
learning algorithms to identify each device based on its unique beam pattern.
Although these methods can be applicable to detect beam-stealing attacks, they
all require a prior (secure) training phase to extract beam patterns of known
devices, which not only brings extra overhead but also does not work well when
the channel condition changes or new devices are introduced to the network. In
contrast, our proposed defense, SecBeam does not require any prior knowledge
about the devices or channel environment.

Finally, we are aware of only one work that proposed a specific defense
against the beam-stealing attack under the IEEE 802.11ad protocol (Steinmetzer
$et\ al.$ [28]). Since the original SLS protocol in IEEE 802.11ad is
unauthenticated which allows beam-stealing by simply modifying the SSW
messages, they integrated crypto machinery into the sector sweep process, in
order to authenticate the SSW messages, which prevents the simple form of
beam-stealing attacks. However, as we demonstrated in this paper, it is still
vulnerable to amplify-and-relay beam-stealing attacks. It is an open problem
to defend against such attacks.

##  IX Conclusions and Future Work

In this paper, we studied the security of the 802.11ad beam alignment protocol
for mmWave communications. Although prior work have added cryptographic
protection to secure beam alignment messages, we demonstrate that this
protocol is still vulnerable to a new amplify-and-relay beam stealing attack
that does not require message forging and bypasses cryptographic protections.
We then propose a new secure beam sweeping protocol, SecBeam, which exploits
power/sector randomization and coarse angle-of-arrival information to detect
amplify-and-relay attacks. Essentially, SecBeam constructs a physical layer
commitment scheme that commits to the path loss of each beam. SecBeam does not
require any prior knowledge of the physical environment and is compatible with
the current 802.11ad standard. We theoretically analyzed the security of
SecBeam, and used both ray-tracing simulations and real-world experiments on a
mmWave testbed to evaluate the security of our protocol. Results show that
SecBeam can detect two different types of amplify-and-relay attacks under
realistic scenarios. Future works will include extending our method to other
efficient beam alignment protocols beyond 802.11ad, for example, protocols
with sub-linear complexity.

## References

  * [1] [Online]. Available: https://www.ettus.com/all-products/usrp-n320/
  * [2] [Online]. Available: https://tmytek.com/products/frequency-converters/udbox5g
  * [3] A. Abidin, “Quantum distance bounding,” in _Proceedings of the 12th Conference on Security and Privacy in Wireless and Mobile Networks_ , 2019, pp. 233–238.
  * [4] S. Balakrishnan, S. Gupta, A. Bhuyan, P. Wang, D. Koutsonikolas, and Z. Sun, “Physical layer identification based on spatial–temporal beam features for millimeter-wave wireless networks,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 1831–1845, 2019.
  * [5] S. Čapkun, M. Čagalj, R. Rengaswamy, I. Tsigkogiannis, J.-P. Hubaux, and M. Srivastava, “Integrity codes: Message integrity protection and authentication over insecure channels,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 5, no. 4, pp. 208–223, 2008.
  * [6] C. Cremers, K. B. Rasmussen, B. Schmidt, and S. Capkun, “Distance hijacking attacks on distance bounding protocols,” in _2012 IEEE symposium on security and privacy_. IEEE, 2012, pp. 113–127.
  * [7] S. Drimer, S. J. Murdoch _et al._ , “Keep your enemies close: Distance bounding against smartcard relay attacks.” in _USENIX security symposium_ , vol. 312, 2007.
  * [8] A. Francillon, B. Danev, and S. Capkun, “Relay attacks on passive keyless entry and start systems in modern cars,” in _Proceedings of the Network and Distributed System Security Symposium (NDSS)_. Eidgenössische Technische Hochschule Zürich, Department of Computer Science, 2011.
  * [9] L. Francis, G. Hancke, K. Mayes, and K. Markantonakis, “Practical relay attack on contactless transactions by using nfc mobile phones,” _Cryptology ePrint Archive_ , 2011.
  * [10] H. Gao, W. Wang, Y. Wu, Y. Liu, G. F. Pedersen, and W. Fan, “Experimental comparison of on–off and all-on calibration modes for beam-steering performance of mmwave phased array antenna-in-package,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 70, pp. 1–9, 2021.
  * [11] Y. Ghasempour, C. R. Da Silva, C. Cordeiro, and E. W. Knightly, “Ieee 802.11 ay: Next-generation 60 ghz communication for 100 gb/s wi-fi,” _IEEE Communications Magazine_ , vol. 55, no. 12, pp. 186–192, 2017.
  * [12] N. Ghose, L. Lazos, and M. Li, “Help: Helper-enabled in-band device pairing resistant against signal cancellation.” in _USENIX Security Symposium_ , 2017, pp. 433–450.
  * [13] P. Gupta and S. Kar, “Music and improved music algorithm to estimate direction of arrival,” in _2015 International Conference on Communications and Signal Processing (ICCSP)_. IEEE, 2015, pp. 0757–0761.
  * [14] _IEEE Standard for Information technology–Telecommunications and information exchange between systems–Local and metropolitan area networks–Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 3: Enhancements for Very High Throughput in the 60 GHz Band_ , IEEE Std. IEEE 802.11ad, 2012.
  * [15] F. Jameel, S. Wyne, S. J. Nawaz, and Z. Chang, “Propagation channels for mmwave vehicular communications: State-of-the-art and future research directions,” _IEEE Wireless Communications_ , vol. 26, no. 1, pp. 144–150, 2018.
  * [16] Z. Jiang, T. H. Luan, X. Ren, D. Lv, H. Hao, J. Wang, K. Zhao, W. Xi, Y. Xu, and R. Li, “Eliminating the barriers: demystifying wi-fi baseband design and introducing the picoscenes wi-fi sensing platform,” _IEEE Internet of Things Journal_ , vol. 9, no. 6, pp. 4476–4496, 2021.
  * [17] Z. Kfir and A. Wool, “Picking virtual pockets using relay attacks on contactless smartcard,” in _First International Conference on Security and Privacy for Emerging Areas in Communications Networks (SECURECOMM’05)_. IEEE, 2005, pp. 47–58.
  * [18] M. Kim, E. Hwang, and J.-N. Kim, “Analysis of eavesdropping attack in mmwave-based wpans with directional antennas,” _Wireless Networks_ , vol. 23, no. 2, pp. 355–369, 2017.
  * [19] D. Ma, A. K. Prasad, N. Saxena, and T. Xiang, “Location-aware and safer cards: enhancing rfid security and privacy via location sensing,” in _Proceedings of the fifth ACM conference on Security and Privacy in Wireless and Mobile Networks_ , 2012, pp. 51–62.
  * [20] S. Mathur, R. Miller, A. Varshavsky, W. Trappe, and N. Mandayam, “Proximate: proximity-based secure pairing using ambient wireless signals,” in _Proceedings of the 9th international conference on Mobile systems, applications, and services_ , 2011, pp. 211–224.
  * [21] D. Moser, V. Lenders, and S. Capkun, “Digital radio signal cancellation attacks: An experimental evaluation,” in _Proceedings of the 12th conference on security and privacy in wireless and mobile networks_ , 2019, pp. 23–33.
  * [22] E. Papadogiannaki and S. Ioannidis, “A survey on encrypted network traffic analysis applications, techniques, and countermeasures,” _ACM Computing Surveys (CSUR)_ , vol. 54, no. 6, pp. 1–35, 2021.
  * [23] C. Pöpper, N. O. Tippenhauer, B. Danev, and S. Capkun, “Investigation of signal and message manipulations on the wireless channel,” in _Computer Security–ESORICS 2011: 16th European Symposium on Research in Computer Security, Leuven, Belgium, September 12-14, 2011. Proceedings 16_. Springer, 2011, pp. 40–59.
  * [24] L. T. RAMSEY, “Convexity of the binomial distribution,” 2005.
  * [25] T. S. Rappaport, _Wireless communications: Principles and practice, 2/E_. Pearson Education India, 2010.
  * [26] T. S. Rappaport, Y. Xing, G. R. MacCartney, A. F. Molisch, E. Mellios, and J. Zhang, “Overview of millimeter wave communications for fifth-generation (5g) wireless networks—with a focus on propagation models,” _IEEE Transactions on Antennas and Propagation_ , vol. 65, no. 12, pp. 6213–6230, 2017\.
  * [27] M. K. Samimi, G. R. MacCartney, S. Sun, and T. S. Rappaport, “28 ghz millimeter-wave ultrawideband small-scale fading models in wireless channels,” in _2016 IEEE 83rd Vehicular Technology Conference (VTC Spring)_. IEEE, 2016, pp. 1–6.
  * [28] D. Steinmetzer, S. Ahmad, N. Anagnostopoulos, M. Hollick, and S. Katzenbeisser, “Authenticating the sector sweep to protect against beam-stealing attacks in ieee 802.11 ad networks,” in _Proceedings of the 2nd ACM Workshop on Millimeter Wave Networks and Sensing Systems_ , 2018, pp. 3–8.
  * [29] D. Steinmetzer, J. Classen, and M. Hollick, “mmtrace: Modeling millimeter-wave indoor propagation with image-based ray-tracing,” in _2016 IEEE conference on computer communications workshops (INFOCOM WKSHPS)_. IEEE, 2016, pp. 429–434.
  * [30] D. Steinmetzer, Y. Yuan, and M. Hollick, “Beam-stealing: Intercepting the sector sweep to launch man-in-the-middle attacks on wireless ieee 802.11 ad networks,” in _Proceedings of the 11th ACM Conference on Security & Privacy in Wireless and Mobile Networks_, 2018, pp. 12–22.
  * [31] X. Tian, Q. Liu, Z. Wang, and M. Li, “Secure hybrid beamformers design in mmwave mimo wiretap systems,” _IEEE Systems Journal_ , vol. 14, no. 1, pp. 548–559, 2019.
  * [32] N. O. Tippenhauer, H. Luecken, M. Kuhn, and S. Capkun, “Uwb rapid-bit-exchange system for distance bounding,” in _Proceedings of the 8th ACM Conference on Security & Privacy in Wireless and Mobile Networks_, 2015, pp. 1–12.
  * [33] H. T. T. Truong, X. Gao, B. Shrestha, N. Saxena, N. Asokan, and P. Nurmi, “Comparing and fusing different sensor modalities for relay attack resistance in zero-interaction authentication,” in _2014 IEEE International Conference on Pervasive Computing and Communications (PerCom)_. IEEE, 2014, pp. 163–171.
  * [34] P. Urien and S. Piramuthu, “Elliptic curve-based rfid/nfc authentication with temperature sensor input for relay attacks,” _Decision Support Systems_ , vol. 59, pp. 28–36, 2014.
  * [35] N. Wang, L. Jiao, P. Wang, W. Li, and K. Zeng, “Machine learning-based spoofing attack detection in mmwave 60ghz ieee 802.11 ad networks,” in _IEEE INFOCOM 2020-IEEE Conference on Computer Communications_. IEEE, 2020, pp. 2579–2588.
  * [36] ——, “Exploiting beam features for spoofing attack detection in mmwave 60-ghz ieee 802.11 ad networks,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 5, pp. 3321–3335, 2021.
  * [37] Y. Wang, Z. Wei, and Z. Feng, “Beam training and tracking in mmwave communication: A survey,” 2022.
  * [38] X. Wu, Y. Zhang, C.-X. Wang, G. Goussetis, M. M. Alwakeel _et al._ , “28 ghz indoor channel measurements and modelling in laboratory environment using directional antennas,” in _2015 9th European Conference on Antennas and Propagation (EuCAP)_. IEEE, 2015, pp. 1–5.
  * [39] M. Xiao, S. Mumtaz, Y. Huang, L. Dai, Y. Li, M. Matthaiou, G. K. Karagiannidis, E. Björnson, K. Yang, C.-L. I, and A. Ghosh, “Millimeter wave communications for future mobile networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 35, no. 9, pp. 1909–1935, 2017.
  * [40] Z. Xu, J. Li, Y. Pan, L. Lazos, M. Li, and N. Ghose, “PoF: Proof-of-following for vehicle platoons,” in _Proceedings 2022 Network and Distributed System Security Symposium_ , 2022.
  * [41] Y. Yang, X. Wei, R. Xu, L. Peng, L. Zhang, and L. Ge, “Man-in-the-middle attack detection and localization based on cross-layer location consistency,” _IEEE Access_ , vol. 8, pp. 103 860–103 874, 2020.
  * [42] Y. Zhu, L. Wang, K.-K. Wong, and R. W. Heath, “Secure communications in millimeter wave ad hoc networks,” _IEEE Transactions on Wireless Communications_ , vol. 16, no. 5, pp. 3205–3217, 2017.

|  |
---|---|---
(a)Experimental setup | (b)$\mathcal{M}$ relays in $FP$ strategy | (c)$\mathcal{M}$ relays in $FA$ strategy
Figure 24: Amplify-and-relay beam-stealing attack setup and experimental
results when $\mathcal{M}$ uses $FA$ and $FP$ relay strategies. $R$ chooses
sector 7 without $\mathcal{M}$, and sector 6 when $\mathcal{M}$ relays in
either $FA$ or $FP$ strategies.

###  -A Amplfy-and-Relay Beam-Stealing Attack in Setup 2

The experimental setup, illustrated in Fig. 24(a), consists of devices that
are located at distances of $d_{IM}=2.7m$, $d_{IR}=4.3m$, and $d_{MR}=6m$. To
achieve synchronization between devices $I$ and $\mathcal{M}$, an external
clock (Ettus OctoClock-G) is used. In this configuration, $\mathcal{M}$ and
$R$ are situated in different quasi-omni patterns of $I$, enabling
$\mathcal{M}$ to relay sector sweep frames from $R$ to $I$ while $I$ is
receiving in the quasi-omni pattern towards itself. Consequently, there is no
need to synchronize $\mathcal{M}$ and $R$. The results of this setup are shown
in Fig. 24(b)(c) and Fig. 25. When there is no adversary, $I$ and $R$ select
sector 1 and sector 7 as the best beam pair.

Fig. 24(b) and Fig. 25(a) demonstrate the impact of $\mathcal{M}$ relaying
using $FP$ strategy, leading to $R$ and $I$ switching to sector 6 and sector
5, respectively. In Fig. 24(c) and Fig. 25(b), $\mathcal{M}$ relays using $FA$
strategy, resulting in the selection of sector 5 at $I$ and sector 6 at $R$
again. Ultimately, $\mathcal{M}$ successfully directs $I$ and $R$ to choose
beams pointing towards him in both strategies. We further verified that
without $\mathcal{M}$, $I$ and $R$ were unable to communicate using sector 5
and sector 6. These results are in line with those presented in Sec. III-A.

|
---|---
(a)$\mathcal{M}$ relays in FP strategy | (b) $\mathcal{M}$ relays in FA strategy
Figure 25: Amplify-and-relay beam stealing attack on $I$ using $FA$ and $FP$
strategies. $I$ chooses sector 1 without $\mathcal{M}$, and sector 5 when
$\mathcal{M}$ relays in either $FA$ or $FP$ strategies.

###  -B Proof of Proposition 1

Proposition 1. A fixed power attack on sector $S_{i}$ is detected by the path
loss test if the transmission power $P_{i}(T)(2)$ in the second round
satisfies

$P_{i}^{T}(2)<P_{i}^{T}(1)-\epsilon,$

where $\epsilon$ is a noise-determined parameter.

###### Proof.

Consider the transmission of an SSF at sector $S_{i}$ by $I$ during the first
round with power $P_{i}^{T}(1)$. The path loss calculated by $R$ is
$PL_{i}(1)(dB)=P_{i}^{T}(1)(dBm)-P_{i}^{R}(1)(dBm).$ Similarly, $R$ calculates
the path loss of the second round as
$PL_{i}(2)(dB)=P_{i}^{T}(2)(dBm)-P_{i}^{R}(2)(dBm).$ Taking the absolute
difference yields

$\displaystyle|PL_{i}(1)-PL_{i}(2)|$ $\displaystyle=$ $\displaystyle
PL_{i}(1)-PL_{1}(2)$ (3) $\displaystyle=$ $\displaystyle
P_{i}^{T}(1)-P_{i}^{R}(1)-P_{i}^{T}(2)+P_{i}^{R}(2)$ $\displaystyle>$
$\displaystyle P_{i}^{T}(1)-P_{i}^{T}(1)+\epsilon$ $\displaystyle>$
$\displaystyle\epsilon.$

In (3), we used the fact that $PL_{i}(1)>PL_{1}(2)$ because $I$’s transmission
power is reduced in the second round whereas Mallory transmits at fixed power
thus leading to the calculation of lower path loss. Moreover, because
Mallory’s transmission is at fixed power, it follows that
$P_{i}^{R}(1)=P_{i}^{R}(2).$ Finally, by design,
$P_{i}^{T}(2)<P_{i}^{T}(1)-\epsilon.$ ∎

###  -C Proof of Proposition 2

Proposition 2. Given the number of sectors $N_{M}$ heard at $\mathcal{M}$ and
the number of sectors $K$ in $N_{M}$ with path loss smaller than the best path
without attack under a fixed amplification strategy, the probability $P_{BS}$
of a successful beam stealing attack is given by

$Pr_{BS}=\frac{1}{\binom{N_{M}}{x}^{4}}\cdot\left(\sum_{i=1}^{\min(x,K)}\binom{K}{i}\binom{N_{M}-K}{x-i}\right)^{2}.$

###### Proof.

To prove Proposition 2, we first describe the adversary’s strategy. During the
first round, Mallory must choose which SSFs out of the $N_{M}$ ones that she
receives should be amplified and forwarded to $R.$ Given the online nature of
the attack, this decision is made in real time. Let Mallory decide to forward
$x$ out of the $N_{M}$ sectors, without being able to identify them since the
sector IDs are encrypted. The probability of choosing at least one sector that
can defeat the optimal legitimate sector without attack (and therefore steal
the beam) is given by the probability that any of the $K$ amplified sectors
that defeat the optimal one are chosen. We compute this probability as

$Pr_{1}=\sum_{i=1}^{\min\\{x,K\\}}\frac{\binom{K}{i}\cdot\binom{N_{M}-K}{x-i}}{\binom{N_{M}}{x}}.$
(4)

Equation (4) is the enumeration of all possible ways of choosing exactly $i$
sectors out of $K$, when Mallory chooses to amplify $x$ out of $N_{M}$ sectors
at random. In the second round, $\mathcal{M}$ has to amplify exactly the same
$x$ sectors to pass the path loss test. If any sector out of the $x$ amplified
in round 1 is not amplified in the second round, the path loss calculated for
that sector will differ by the amplification gain applied in the first round.

However, the sweep sequence is randomized in the second round by the
application of the pseudorandom permutation $\Pi.$ Moreover, Mallory cannot
decrypt SSFs to recover the sector ID. Even if she could, the online nature of
the attack does not permit enough time for frame decoding. Therefore, the
probability of passing the path loss test is given by the probability of
selecting the same set of $x$ SSFs, given by $Pr_{2}=1/\binom{N_{M}}{x}.$
Combining the events of choosing a sector that defeats the optimal one in the
first round and choosing the same sectors to amplify in the second round
yields Mallory’s success probability in stealing the initiator’s beam

$Pr_{FA}=\frac{1}{\binom{N_{M}}{x}^{2}}\cdot\left(\sum_{i=1}^{\min(x,K)}\binom{K}{i}\binom{N_{M}-K}{x-i}\right)$
(5)

To successfully steal the beams in both directions, $\mathcal{M}$ must succeed
in both the initiator and responder sector sweep processes. This probability
is given by $Pr_{BS}=\left(Pr_{FA}\right)^{2}$. ∎


capbtabboxtable[][]

11institutetext: KU Leuven, Belgium
11email<EMAIL_ADDRESS>
# Zero-Shot Recommendation as Language Modeling

Damien Sileo  0000-0002-3274-291X Wout Vossen  Robbe Raymaekers

###### Abstract

Recommendation is the task of ranking items (e.g. movies or products)
according to individual user needs. Current systems rely on collaborative
filtering and content-based techniques, which both require structured training
data. We propose a framework for recommendation with off-the-shelf pretrained
language models (LM) that only used unstructured text corpora as training
data. If a user $u$ liked Matrix and Inception, we construct a textual prompt,
e.g. ”Movies like Matrix, Inception, ${<}m{>}$” to estimate the affinity
between $u$ and $m$ with LM likelihood. We motivate our idea with a corpus
analysis, evaluate several prompt structures, and we compare LM-based
recommendation with standard matrix factorization trained on different data
regimes. The code for our experiments is publicly
available111https://colab.research.google.com/drive/...?usp=sharing.

##  1 Introduction

Recommender systems predict an affinity score between users and items. Current
recommender systems are based on content-based filtering (CB), collaborative
filtering techniques (CF), or a combination of both. CF recommender systems
rely on (User, Item, Interaction) triplets. CB relies on (Item, Features)
pairs. Both system types require a costly structured data collection step.
Meanwhile, web users express themselves about various items in an unstructured
way. They share lists of their favorite items and ask for recommendations on
web forums, as in 1222https://www.reddit.com/r/MovieSuggestions/...lost_river/
which hints at a similarity between the enumerated movies. .  Films like
Beyond the Black Rainbow, Lost River, Suspiria, and The Neon Demon.

The web also contains a lot of information about the items themselves, like
synopsis or reviews for movies. Language models such as GPT-2 [14] are trained
on large web corpora to generate plausible text. We hypothesize that they can
make use of this unstructured knowledge to make recommendations by estimating
the plausibility of items being grouped together in a prompt. LM can estimate
the probability of a word sequence, $P(w_{1},...w_{n})$. Neural language
models are trained over a large corpus of documents: to train a neural
network, its parameters $\Theta$ are optimized for next word prediction
likelihood maximization over $k$-length sequences sampled from a corpus. The
loss writes as follows:

$\mathcal{L}_{\text{LM}}=-\text{log
}\sum\limits_{i}P(w_{i}|w_{i-k}....w_{i-1};\Theta)$ (1)

We rely on existing pretrained language models. To make a relevance prediction
, we build a prompt for each user:

$p_{u,i}=\textit{Movies like }{<}m_{1}{>},...{<}m_{n}{>},{<}m_{i}{>}$ (2)

where ${<}m_{i}{>}$ is the name of the movie $m_{i}$ and ${<}m_{1}...m_{n}{>}$
are those of randomly ordered movies liked by $u$. We then directly use
$\widehat{R}_{u,i}=P_{\Theta}(p_{u,i})$ as a relevance score to sort items for
user $u$.

Our contributions are as follow (i) we propose a model for recommendation with
standard LM; (ii) we derive prompt structures from a corpus analysis and
compare their impact on recommendation accuracy; (iii) we compare LM-based
recommendation with next sentence prediction (NSP) [12] and a standard
supervised matrix factorization method [9, 15].

##  2 Related work

#### Language models and recommendation

Previous work leveraged language modeling techniques to perform
recommendations. However, they do not rely on natural language: they use
sequences of user/item interactions, and treat these sequences as sentences to
leverage the architectures inspired by NLP, such as Word2Vec [7, 1, 4, 11] or
BERT [19].

#### Zero-shot prediction with language models

Neural language models have been used for zero-shot inference on many NLP
tasks [14, 2]. For example, they manually construct a prompt structure to
translate text, e.g. Translate english to french : ”cheese” =${>}$, and use
the language model completions to find the best translations. Petroni et al.
[13] show that masked language models can act as a knowledge base when we use
part of a triplet as input, e.g. Paris in ${<}mask{>}$. Here, we apply LM-
based prompts to recommendation.

#### Hybrid and zero-shot recommendation

The cold start problem [17], i.e. dealing with new users or items is a long-
standing problem in recommender systems, usually addressed with hybridization
of CF-based and CB-based systems. Previous work [20, 10, 5, 6] introduced
models for zero-shot recommendation, but they use zero-shot prediction with a
different sense than ours. They train on a set of (User, Item, Interaction)
triplets, and perform zero-shot predictions on new users or items with known
attributes. These methods still require (User, Item, Interaction) or (Item,
Features) tuples for training. To our knowledge, the only attempt to perform
recommendations without such data at all is from Penha et al. [12] who showed
that BERT [3] next sentence prediction (NSP) can be used to predict the most
plausible movie after a prompt. NSP is not available in all language models
and requires a specific pretraining. Their work is designed as a probing of
BERT knowledge about common items, and lacks comparison with a standard
recommendation model, which we here address.

##  3 Experiments

###  3.1 Setup

#### Dataset

We use the standard the MovieLens 1M dataset [8] with 1M ratings from $0.5$ to
$5$, 6040 users, and 3090 movies in our experiments. We address the relevance
prediction task333Item relevance could be mapped to ratings but we do not
address rating prediction here., so we consider a rating $r$ as positive if
$r\geq 4.0$, as negative if $\leq 2.5$ and we discard the other ratings. We
select users with at least $21$ positive ratings and $4$ negative ratings and
thus obtain $2716$ users. We randomly select $20\%$ of them as test
users444Training users are only used for the matrix factorization baseline..
$1$ positive and $4$ negative ratings are reserved for evaluation for each
user, and the goal is to give the highest relevance score to the positively
rated item. We use $5$ positive ratings per user unless mentioned otherwise.
We remove the years from the movie titles and reorder the articles (a, the) in
the movie titles provided in the dataset (e.g. Matrix, The (1999)
$\rightarrow$ The Matrix).

#### Evaluation metric

We use the mean average precision at rank 1 (MAP@1) [18] which is the rate of
correct first ranked prediction averaged over test users, because of its
interpretability.

#### Pretrained language models

In our experiments we use the GPT-2 [14] language models, which are publicly
available in several sizes. GPT-2 is trained with LM pretraining (equation 1)
on the WebText corpus [14], which contains 8 million pages covering various
domains. Unless mentioned otherwise, we use the GPT-base model, with 117M
parameters.

###  3.2 Mining prompts for recommendation

[]

[0.99]  3-6 gram #Count ${<}m{>}$ and ${<}m{>}$ 387 ${<}m{>}$, ${<}m{>}$,
${<}m{>}$ 232 Movies like ${<}m{>}$ 196 ${<}m{>}$, ${<}m{>}$, ${<}m{>}$,
${<}m{>}$ 85 Movies similar to ${<}m{>}$ 25 Occurrence counts of 3-6 grams
that contain movie names in the Reddit corpus. ${<}m{>}$ denotes a movie name.

[0.99]  Comparison of LM recommendations MAP@1 with different prompt
structures.

We analyze the Reddit comments from May
2015555https://www.kaggle.com/reddit/reddit-comments-may-2015 to find out how
web users mention lists of movies in web text. This analysis will provide
prompt candidates for LM-based recommendations. We select comments where a
movie name of the MovieLens dataset is present and replace movies with a
${<}m{>}$ tag. This filtered dataset of comments has a size of $>900k$ words.
We then select the most frequent pattern with at least three words, as shown
in table 3.2. Movie names are frequently used in enumerations. The patterns
Movies like ${<}m{>}$ and Movies similar to  confirm that users focus on the
similarity of movies.

Figure 3.2 shows that prompt design is important but not critical for high
accuracy. Our corpus-derived prompts significantly outperform if you like
${<}m_{1}...m_{n}{>}$, you will like ${<}m_{i}{>}$ used in [12]. We will use
${<}m_{1}...m_{n}{>},{<}m_{i}{>}$ in the remaining of the paper due to its
superior results and its simplicity.

###  3.3 Effect of the number of ratings per test user

We investigate the effect of the number of mentioned movies in prompts. We
expect the accuracy of the models in making recommendations to increase when
they get more info about movies a user likes. We compare the recommendation
accuracy on the same users 0,1,2,3,5,10,15 or 20 movies per prompt.

Figure 1: MAP@1 of LM models with a varying number of movies per user sampled
in the input prompt.

Figure 1 shows that increasing the number of ratings per user has diminishing
returns and lead to increasing instability, so specifying $n\approx 5$ seems
to lead to the best results with the least user input. After 5 items, adding
more items might make the prompt less natural, even though the LM seems to
adapt when the number of items keeps increasing. It is also interesting to
note that when we use an empty prompt, accuracy is above chance level because
the LM captures some information about movie popularity.

###  3.4 Comparison with matrix factorization and NSP

We now use a matrix factorization as a baseline, with the Bayesian
Personalised Ranking algorithm (BPR) [15]. Users and items are mapped to $d$
randomly initialized latent factors, and their dot product is used as a
relevance score trained with ranking loss. We use [16] implementation with
default
hyperparameters666https://cornac.readthedocs.io/en/latest/models.html#bayesian-
personalized-ranking-bpr, we experimented with other hyperparameter
configurations but did not observe significant changes. $d=10$ and a learning
rate of $0.001$.

We also compare GPT-2 LM to BERT next sentence prediction [12] which models
affinity scores with
$\widehat{R}_{u,i}=\text{BERT}_{\text{NSP}}(p_{u},{<}m_{i}{>})$, where $p_{u}$
is a prompt containing movies liked by $u$. BERT was pretrained with
contiguous sentence prediction task [3] and Penha et al. [12] proposed to use
it as a way to probe BERT for recommendation capabilities.

Figure 2: MAP@1 for BPR models with increasing numbers of users compared the
zero-shot language models (with 0 training user). BERT-base and BERT-large
respectively have 110M and 340M parameters. GPT-2-base and GPT-2-medium have
117M and 345M parameters.

Figure 2 shows that the proposed LM-based recommendation significantly
outperforms $\text{BERT}_{\text{NSP}}$. We explain the difference by the fact
that LM are generative and actually model text likelihood, while next sentence
prediction is discriminative and can be based on simple discursive coherence
features. It is also interesting to note that LM-based models outperform
matrix factorization when there are few users, i.e $<50$ and $<100$ for base
and medium GPT-2, which demonstrates that LM-based recommendation is viable
for cold start regimes. Using models larger than the base versions lead to
better results, however when we evaluated with larger versions (we did not
perform the full experiments due to memory limitations), we did not see
additional improvement, which could be explained by overfitting.

###  3.5 Qualitative analysis of generations

Up until there, we have used LM to score the likelihood of sequences. LM can
also be used directly for text generation, unlike BERT. We here show LM-
generated prompt completions randomly sampled in our dataset, using greedy
decoding.

#### Prompt (P1):

Forrest Gump, Blade Runner, Modern Times, Amelie, Lord of the Rings The Return
of the King, Shaun of the Dead, Alexander, Pan’s Labyrinth, Cashback, Avatar:

#### Completion (C1):

3, The Hunger Games: Mockingjay Part 2, King Arthur, A Feast for Crows, The
Hunger Games: Catching Fire, Jackass, Jackass 2, King Arthur

#### Prompt (P2):

Independence Day, Winnie the Pooh and the Blustery Day, Raiders of the Lost
Ark, Star Wars Episode VI - Return of the Jedi, Quiet Man, Game, Labyrinth,
Return to Oz, Song of the South, Matrix:

#### Completion (C2):

and many more. The list can be read by clicking on the relevant section at the
left of the image. To access the list of releases

Some prompts, i.e. (P1) generate valid movie names, but others, like (P2), do
not. LM-based recommender do need a post-processing to match movie names in
the possible sampled generations.

##  4 Conclusion

We showed that standard language models can be used to perform item
recommendations without any adaptation and that they are competitive with
supervised matrix factorization when the number of users is very low (less
than 100 users). LM can therefore be used to kickstart recommender systems if
items are frequently discussed in the training corpora. Further research could
explore ways to adjust LM for recommendation purposes or to combine LM with
matrix factorization into hybrid systems. Another way to use of our findings
would be to generate movie recommendation datasets by mining web data which
could feed standard supervised recommendation techniques.

##  5 Acknowledgements

This work is part of the CALCULUS project, which is funded by the ERC Advanced
Grant H2020-ERC-2017 ADG 788506777https://calculus-project.eu/.

## References

  * [1] Barkan, O., Koenigstein, N.: Item2vec: Neural item embedding for collaborative filtering. In: 2016 IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP). pp. 1–6 (2016). https://doi.org/10.1109/MLSP.2016.7738886
  * [2] Brown, T.B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D.M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., Amodei, D.: Language models are few-shot learners (2020)
  * [3] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171–4186. Association for Computational Linguistics, Minneapolis, Minnesota (Jun 2019). https://doi.org/10.18653/v1/N19-1423, https://aclanthology.org/N19-1423
  * [4] Devooght, R., Bersini, H.: Long and short-term recommendations with recurrent neural networks. p. 13–21. UMAP ’17, Association for Computing Machinery, New York, NY, USA (2017). https://doi.org/10.1145/3079628.3079670, https://doi.org/10.1145/3079628.3079670
  * [5] Ding, H., Ma, Y., Deoras, A., Wang, Y., Wang, H.: Zero-shot recommender systems (2021)
  * [6] Feng, P.J., Pan, P., Zhou, T., Chen, H., Luo, C.: Zero shot on the cold-start problem: Model-agnostic interest learning for recommender systems. In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. p. 474–483. CIKM ’21, Association for Computing Machinery, New York, NY, USA (2021). https://doi.org/10.1145/3459637.3482312, https://doi.org/10.1145/3459637.3482312
  * [7] Guàrdia-Sebaoun, E., Guigue, V., Gallinari, P.: Latent trajectory modeling: A light and efficient way to introduce time in recommender systems. In: Proceedings of the 9th ACM Conference on Recommender Systems. pp. 281–284 (2015)
  * [8] Harper, F.M., Konstan, J.A.: The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst. 5(4) (Dec 2015). https://doi.org/10.1145/2827872, https://doi.org/10.1145/2827872
  * [9] Koren, Y., Bell, R., Volinsky, C.: Matrix factorization techniques for recommender systems. Computer 42(8), 30–37 (2009)
  * [10] Li, J., Jing, M., Lu, K., Zhu, L., Yang, Y., Huang, Z.: From zero-shot learning to cold-start recommendation. Proceedings of the AAAI Conference on Artificial Intelligence 33(01), 4189–4196 (Jul 2019). https://doi.org/10.1609/aaai.v33i01.33014189, https://ojs.aaai.org/index.php/AAAI/article/view/4324
  * [11] Li, Z., Zhao, H., Liu, Q., Huang, Z., Mei, T., Chen, E.: Learning from history and present: Next-item recommendation via discriminatively exploiting user behaviors. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 1734–1743 (2018)
  * [12] Penha, G., Hauff, C.: What does bert know about books, movies and music? probing bert for conversational recommendation. In: Fourteenth ACM Conference on Recommender Systems. p. 388–397. RecSys ’20, Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3383313.3412249, https://doi.org/10.1145/3383313.3412249
  * [13] Petroni, F., Rockaschel, T., Riedel, S., Lewis, P., Bakhtin, A., Wu, Y., Miller, A.: Language models as knowledge bases? In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). pp. 2463–2473. Association for Computational Linguistics, Hong Kong, China (Nov 2019). https://doi.org/10.18653/v1/D19-1250, https://aclanthology.org/D19-1250
  * [14] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I.: Language models are unsupervised multitask learners (2019), https://openai.com/blog/better-language-models/
  * [15] Rendle, S., Freudenthaler, C., Gantner, Z., Schmidt-Thieme, L.: Bpr: Bayesian personalized ranking from implicit feedback. p. 452–461. UAI ’09, AUAI Press, Arlington, Virginia, USA (2009)
  * [16] Salah, A., Truong, Q.T., Lauw, H.W.: Cornac: A comparative framework for multimodal recommender systems. Journal of Machine Learning Research 21(95), 1–5 (2020)
  * [17] Schein, A.I., Popescul, A., Ungar, L.H., Pennock, D.M.: Methods and metrics for cold-start recommendations. In: Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. p. 253–260. SIGIR ’02, Association for Computing Machinery, New York, NY, USA (2002). https://doi.org/10.1145/564376.564421, https://doi.org/10.1145/564376.564421
  * [18] Schröder, G., Thiele, M., Lehner, W.: Setting goals and choosing metrics for recommender system evaluations. In: UCERSTI2 workshop at the 5th ACM conference on recommender systems, Chicago, USA. vol. 23, p. 53 (2011)
  * [19] Sun, F., Liu, J., Wu, J., Pei, C., Lin, X., Ou, W., Jiang, P.: Bert4rec: Sequential recommendation with bidirectional encoder representations from transformer. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management. p. 1441–1450. CIKM ’19, Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3357384.3357895, https://doi.org/10.1145/3357384.3357895
  * [20] Volkovs, M., Yu, G., Poutanen, T.: Dropoutnet: Addressing cold start in recommender systems. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 30. Curran Associates, Inc. (2017), https://proceedings.neurips.cc/paper/2017/file/dbd22ba3bd0df8f385bdac3e9f8be207-Paper.pdf