RRCshort=RRC,long=Radio Resource Control ZMQshort=ZMQ,long=ZeroMQ
LSTMshort=LSTM,long=Long Short-Term Memory LALshort=LAL,long=Listen-and-Learn
SyALshort=SyAL,long=Sync-and-Learn SoALshort=SoAL,long=Source-and-Learn
TSshort=TS,long=Technical Specifications NRshort=NR,long=New Radio
URLLCshort=URLLC,long=Ultra-Reliable Low Latency Communications
eMBBshort=eMBB,long=enhancing Mobile Broadband mMTCshort=mMTC,long=massive
Machine Type Communications O-RANshort=O-RAN,long=Open Radio Access Network
NASshort=NAS,long=Non-Access Stratum UEshort=UE,long=User Equipment
MITMshort=MITM,long=man-in-the-middle OTAshort=OTA,long=over-the-air
CNshort=CN,long=core network gNBshort=gNB,long=gNodeB DoSshort=DoS,long=Deny
of Service BSshort=BS,long=Base Station RNTIshort=RNTI,long=Radio Network
Temporary Identifier ARshort=AR,long=Augmented Reality
IoTshort=IoT,long=internet of things AIshort=AI,long=Artificial Intelligence
SSDshort=SSD,long=Systematic and Scalabile vulnerabilities and unintended
emergent behavior Detection Detection DCIshort=DCI,long=Downlink Control
Information CRCshort=CRC,long=cyclic redundancy check
ROCshort=ROC,long=Receiver Operating Characteristics AUCshort=AUC,long=Area
Under the ROC Curve AKAshort=AKA,long=Authentication and Key Agreement
CDTshort=CDT,long=cybersecurity digital twin NLPshort=NLP,long=Natural
Language Processing

# Systematic Meets Unintended: Prior Knowledge Adaptive 5G Vulnerability
Detection via Multi-Fuzzing

Jingda Yang, Yanjun Pan,
Tuyen X. Tran, and Ying Wang J. Yang and Y. Wang is with Stevens Institute of
Technology. Y. Pan is with University of Arkansas and T. Tran is with AT&T
Labes Research. The corresponding author is Y. Wang<EMAIL_ADDRESS>This
effort was sponsored by the Defense Advanced Research Project Agency (DARPA)
under grant no. D22AP00144. The views and conclusions contained herein are
those of the authors and should not be interpreted as necessarily representing
the official policies or endorsements, either expressed or implied, of DARPA
or the U.S. Government.

###### Abstract

The virtualization and softwarization of 5G and NextG are critical enablers of
the shift to flexibility, but they also present a potential attack surface for
threats. However, current security research in communication systems focuses
on specific aspects of security challenges and lacks a holistic perspective.
To address this challenge, a novel systematic fuzzing approach is proposed to
reveal, detect, and predict vulnerabilities with and without prior knowledge
assumptions from attackers. It also serves as a digital twin platform for
system testing and defense simulation pipeline. Three fuzzing strategies are
proposed: Listen-and-Learn (LAL), Synchronize-and-Learn (SyAL), and Source-
and-Learn (SoAL). The LAL strategy is a black-box fuzzing strategy used to
discover vulnerabilities without prior protocol knowledge, while the SyAL
strategy, also a black-box fuzzing method, targets vulnerabilities more
accurately with attacker-accessible user information and a novel probability-
based fuzzing approach. The white-box fuzzing strategy, SoAL, is then employed
to identify and explain vulnerabilities through fuzzing of significant bits.
Using the srsRAN 5G platform, the LAL strategy identifies 129 RRC connection
vulnerabilities with an average detection duration of 0.072s. Leveraging the
probability-based fuzzing algorithm, the SyAL strategy outperforms existing
models in precision and recall, using significantly fewer fuzzing cases. SoAL
detects three man-in-the-middle vulnerabilities stemming from 5G protocol
vulnerabilities. The proposed solution is scalable to other open-source and
commercial 5G platforms and protocols beyond RRC. Extensive experimental
results demonstrate that the proposed solution is an effective and efficient
approach to validate 5G security; meanwhile, it serves as real-time
vulnerability detection and proactive defense.

###### Index Terms:

Fuzz Testing, Vulnerabilities Detection, RRC Protocols, 5G Stack, Digital Twin

††publicationid: pubid: 0000–0000/00$00.00 © 2021 IEEE

##  I Introduction

5G NR and NextG cellular networks promise a wide variety of heterogeneous use
cases that enable Ultra-Reliable Low Latency Communications (URLLC) and
enhance Mobile Broadband (eMBB) and massive Machine Type Communications (mMTC)
across various industries which require networking with unprecedented
flexibility. Flexibility is key in 5G NR, providing performance enhancements
and allowing vertical customization; however, these advances also increase the
complexity of security in NR protocols and implementations [1]. While
softwarization, virtualization, and disaggregation of networking
functionalities as the key enablers of the needed shift to flexibility, it
presents a potential attack surface to threats and requires rigorous testing
against vulnerabilities, which are often computationally expensive and
impractical in large-scale software stacks.

In existing large-scale codebases for both open source and commercially
available 5G stacks, compared to the state-of-the-art security research in
communication systems, which has resolved specific aspects or partitions of
security challenges to achieve assurance, the 5G and NextG networks need to
consider the security defense from a holistic perspective in detecting
vulnerabilities and unintended emergent behaviors. In addition, defense
strategies based on thorough testing often lack adaptation and robustness,
facing variations of attacks and compromising 5G assurance. Furthermore,
general system engineering approaches (e.g., system dynamics and agent-based
modeling) are inadequate in describing both the qualitative and quantitative
aspects of security features in 5G software stacks. Moreover, comprehensive
cybersecurity assessments involving physical objects, particularly over
critical infrastructures, can be expensive and time-consuming.

Unlike deterministic behaviors that can be verified via approaches like formal
methods, detecting unintended emergent behavior in 5G software stacks requires
repeatability and adds uncertainty to the results due to their stochastic
nature and various use scenarios. Additionally, the recently adopted O-RAN
[2], characterized by machine learning algorithms, introduces less
transparency to 5G communications. This uncertainty poses a significant
challenge to traditional vulnerability detection methods, as they may not be
able to effectively identify vulnerabilities arising from unexpected inputs or
behaviors resulting from machine learning algorithms. Therefore, an efficient
and systematic scheme that is based on experimental results for detecting
vulnerabilities and unintended emergent behaviors is crucial for ensuring the
security and robustness of 5G systems. Experimental work in the context of 5G
shifts simulation-driven research used in previous mobile network generations
to system implementation prototyping[3][4][5]. This change stems from several
factors including the widespread adoption of programmable Software Defined
Radios (SDR), network function virtualization (NFV), and subsequent open-
source softwarization of mobile network functions through various projects
such as Open Air Interface (OAI) [6], srsRAN [7]. The change also enables
digital twins to emerge as a disruptive concept for testing complex, large-
scale 5G network stacks with limited resources. A digital twin enables systems
analysis, design, optimization, and evolution to take place fully digitally or
in conjunction with a cyber-physical system. Compared to traditional
engineering approaches, digital twin solutions offer enhanced speed, accuracy,
and efficiency [8]. The applications of digital twin range from well-defined
low-flow device control communication, such as in Industry 4.0 [9], to more
sophisticated applications involving large volumes of data flow fields, such
as Augmented Reality (AR) [10].

The concept of digital twins has been applied to cybersecurity and risk
management in communication systems. Nguyen et al. [11] proposed a systematic
approach to using digital twins for developing and deploying complex 5G
environments and risk prevention systems. Additionally, Jagannath et al. [12]
developed an AI cloud modeling system to mitigate risks associated with
developing innovative technologies on existing systems. Network digital twins,
in conjunction with traditional fuzzing approaches, offer comprehensive
feasibility proof and evaluation for development and deployment on physical
systems [13]. Furthermore, digital twins technology can be utilized to
formulate specific and efficient standards for security training [14],
extending beyond software design and development.

Though various digital twin applications exist in manufacturing and research,
the exponential increase in data volume and volatile environments presents
significant challenges for using digital twins in physical systems. For
example, simulating and identifying unintended emergent behaviors in 5G to
provide scalable cybersecurity assurance through digital twins remains
difficult. As a result, digital twins are often limited to descriptive rather
than actionable functions in 5G and cybersecurity fields [15]. This study aims
to develop a digital twin platform that is not only descriptive but also
actionable against potential or actual attacks in a physical 5G system, from
the micro-atomic to the macro-geometric level. In addition, effective fuzzing
strategies are developed on the platform to detect vulnerabilities and
unintended emergent behaviors in 5G specifications and implementations.

In addition to an efficient testbed, many studies have proposed research on 5G
protocol vulnerability detection and the extension to a critical area
application. For instance, 3GPP TS 33.501a described how a significant number
of pre-authentication messages are sent in an unencrypted format, which can be
exploited to launch DoS attacks and obtain sensitive information, such as the
location of mobile subscribers in 5G/LTE [16]. In [17], the authors identified
the weakest links and channels vulnerable to sniffing and spoofing in the 5G
NR framework. Hussain et al. [18] proposed a property-directed approach for
qualitative and quantifiable analysis. Innovative strategies such as the
grammar-based fuzzing approach with a Markov chain model have recently been
proposed to generate high-risk fuzzing inputs [19]. Similarly, other stateful
transition models have been introduced to efficiently locate vulnerabilities
[20, 21, 22]. In an effort to further refine the fuzzing scope, formal
verification has been incorporated into fuzzing strategies as demonstrated by
HyPFuzz [23]. Capitalizing on advancements in deep learning technologies,
Rainfuzz [24] employs reinforcement learning to generate a heatmap,
facilitating an estimation of risk associated with varying permutations of
fuzzing cases. Additionally, Natural Language Processing (NLP) has been
introduced to analyze vulnerabilities directly from the source code [25]. In a
bid to enhance vulnerability assessment, the development of security metrics
[26] and dependent fields [27] offers a more comprehensive visualization of
vulnerability evaluation. These developments continue to contribute to the
effectiveness and efficiency of vulnerability detection and risk assessment.
Despite of the substantial contribution to protocol-based vulnerability
detection, a comprehensive and systematic approach for detecting
vulnerabilities and unintended emergent behaviors in the entire protocol,
considering varying perspectives on prior knowledge and fuzzing levels,
remains unaddressed.

Among vulnerability detection approaches, fuzz testing has been extensively
used in large-scale 5G and beyond systems for cybersecurity purposes.
Nevertheless, the major challenge in this area remains computational
complexity, which tends to increase exponentially with the size of the
protocol complexity. To confine the detection within the protocol scope,
Potnuru et al. [28] proposed a protocol-based fuzz testing to generate fuzz
testing cases with all possible identifiers and provided a comprehensive
understanding of how the reaction to different protocol-based attacks. Han et
al. proposed mutation-based fuzz testing [29], which can generate extreme
cases, like buffer overflow or incorrect format. Combining the advantages of
protocol and mutation, Salazar et al. provided a rule-based fuzzer [30], which
can cover all protocol-based cases and part of extreme cases. In [31], Ma et
al. proposed a state transaction method to analyze serial attacks, which can
be achieved by modifying different messages in different states. Their
approaches significantly augmented the complexity and diversity of attacks.
However, assuming prior knowledge may implicitly limit the applicability of
vulnerability detection methods, as attackers will exploit vulnerabilities
based on the most efficient means available, utilizing their knowledge of the
system. Successful tokenized-based general-purpose fuzzers (GPF), such as
LZfuzz [32], eliminate the requirements for access to well-documented
protocols and implementations, while focusing on plain-text fuzzing.
Additionally, the non-selective traverse type of fuzzing relies on massive
computation resources [31]. To address the challenges of the prior knowledge
requirements and computation complexity, we propose a multiple dimension
multi-layer protocol-independent fuzzing framework based on digital twin
system, which is combined with machine learning algorithms aiming to detect
protocol vulnerabilities and unintended emergent behaviors in fast-evolving 5G
and NextG specifications and large-scale open programmable 5G stacks.

###  I-A Contributions

The Dolev-Yao formal verification model [33] has been widely used in the field
of cryptography and security protocol analysis. It simplifies the analysis of
cryptographic protocols by assuming that an attacker has the ability to
intercept, modify, and fabricate messages. The lack of consideration of
specific algorithmic weaknesses limits its application in large-scale
distributed networks [34]. The prior knowledge required by attackers can be
considered as the cost of the attack and the impacts or risks to the target
network can be considered as the gain. Counting on the cost and gain for
attacks being performed in unexpected scenarios, it is necessary to build a
systematic solution that adapts to scenarios and detects vulnerabilities and
their impacts. Thus, based on the awareness of prior knowledge, our fuzzing
strategies include ‘LAL’, ‘SyAL’ and ‘SoAL’, which are analogous to black-box,
grey-box, and white-box models. Prior knowledge, in this context, refers to
any information that an attacker possesses about a system or element before
attempting to exploit vulnerabilities. This information includes protocols,
synchronization information, zero-day exploits, or any other relevant
information that can be used to exploit potential vulnerabilities.
Furthermore, we develop a digital twin framework that connects to an
experimental platform to enable systematic and accumulative vulnerability
detection for 5G and NextG protocols through fuzz testing, leveraging our
existing work in [35] and [36]. The RRC protocols and implementations on
srsRAN are adapted to serve as digital twin proof-of-concept of the designed
system, and a relay model acts as an attacker.

In particular, the proposed LAL command-level strategy assumes no prior
knowledge of protocols nor access to code stacks. The protocol-independent
characteristic of it enables an automatic verification for 5G and NextG
protocols and large-scale open programmable stacks release. Then by leveraging
some prior and domain knowledge, a more strategic grey-box approach, SyAL
command-level fuzzing, is formed to achieve higher efficiency and accuracy in
detecting vulnerabilities. In scenarios with access to the source code, the
designed SoAL bit-level fuzzing works as a white-box strategy to perform a
more sophisticated approach on the identified high-risk commands via LAL and
SyAL. Our proposed fuzzing system offers sufficient automation and efficiency
that could serve as a feasible approach to validate security for 5G protocols
and implementations. It also enables real-time system vulnerability detection
and proactive defense.

The states of commands in wireless connections can primarily be divided into
three zones: valid and legal states (green zone), illegal and invalid states
(red zone), and not illegal and not valid states (yellow zone), as illustrated
in Fig. 1. ‘Legal’ indicates whether a command can pass the integrity check,
while ‘valid’ refers to whether the command can function as intended. For
example, states in the not illegal and not valid zone are those that do not
trigger the defense mechanism but can introduce potential threats. Compared to
intended attacks, which are defined in the protocol and located in the red
zone, unintended vulnerabilities are more challenging to detect in 5G wireless
communication. Therefore, our focus is on detecting unintended
vulnerabilities, which are difficult to identify using the integrity
protection mechanisms of the UE and gNB.

Figure 1: Definition of fuzz testing region.

Our main contributions are summarized below:

  1. 1.

Taking into account the attacker strategies with different levels of prior
knowledge, we design three fuzzing strategies named LAL, SyAL, and SoAL. These
strategies offer an efficient and comprehensive solution for vulnerability
detection in 5G specifications and stacks.

  2. 2.

We propose a probability-based fuzzing approach that can reduce the average
number of fuzzing cases expected to detect a vulnerability from linear to
logarithmic growth, resulting in significant scalability and efficiency
improvements for complex systems.

  3. 3.

We design a renovated 5G CDT platform based on classical 5G cybersecurity
modeling. Compared to existing ones, the introduced platform is not only
describable but also actionable for potential or actual attacks in a physical
5G system.

  4. 4.

A proof-of-concept of the designed framework piloting RRC protocols in the
srsRAN platform is developed. The discovered vulnerable states and
transactions of the RRC protocol provide insights for fortifying 5G and NextG
protocols.

  5. 5.

The digital twin solution can directly scale to other existing and future
open-source and commercial 5G platforms and protocols other than RRC.

The rest of the paper is organized as follows: Section II describes the
overview and setup of LAL system. Section III-C provides rule-based, and LSTM-
based prediction approaches to quantifiably evaluate the feasibility and
performance of our system. We discuss the application of LAL in 5G and NextG
software stacks in Section VII.

##  II System Design

###  II-A System Overview

The proposed system is scenario-adaptive to different levels of knowledge
background, from no knowledge (black-box) to thorough knowledge (white-box)
about protocols and Fig. 2 shows the architecture of the proposed scenario-
adaptive fuzzing system. First, attack model configuration is required as
input, where we can define the security goals and target high-risk protocols
or modules in a specific software stack based on contextual information and
domain knowledge. Then, Given the input, the system could identify fuzzing
locations and generate appropriate attack models. For example, the model would
take the black-box LAL strategy when the attack configuration is no knowledge,
and the white-box SoAL strategy would be selected as the attack model when the
attack configuration is thorough knowledge. Finally, based on the attack
model, the fuzzing strategy function will generate the fuzzing sequences
ordered by the priorities. The output of the system contains the
identification of high-risk states and transactions, the detected
vulnerabilities, and the prediction of the vulnerable path. The consistency of
our detected vulnerabilities with existing exploits, which will be illustrated
in the following sections, proves the feasibility and efficiency of our
system.

Figure 2: Overview of 5G fuzz testing methods.

Based on the format and impact, we focus on the validity and legitimacy of
commands. Legitimacy indicates whether the command will pass protocol and
cryptographic checkers, and validity represents whether the command will lead
to a threat. Correspondingly, commands mainly fall into three classes: valid
states, illegal or invalid states, and other logical states, the relationship
of which is shown in Fig. 1. Most command-level fuzzing states can be regarded
as legal states because all command-level states are collected from regular
connections. However, the validity of command-level fuzzing states can only be
decided based on the result of connections, in which valid means fuzzing state
has no influence on protocol stack and invalid means fuzzing state will lead
to a threat or vulnerability. On the contrary, bit-level fuzzing states
contain both illegal and legal states. Therefore, we use the source code
interpreter as the integrity checker to identify whether the bit-level fuzzing
states are legal or illegal. As for the validity of bit-level fuzzing states,
we take the same measurement approach with command-level fuzzing states to
label.

In this paper, we focus on neither illegal nor valid states (represented as
the yellow zone in Fig. 1) in the RRC protocol. We disregard easily
identifiable valid and illegal states, typically marked as successful and
rejected connections, respectively. The states neither illegal nor valid, in
which we are interested, are defined as legal and invalid. These states cannot
be detected by the system through the designed exception-handling mechanism
and entail unexpected vulnerabilities. In particular, we discovered 129
vulnerabilities that are actual implementation flaws in the RRC protocol. In
practice, an attacker can record and replay commands exchanged between UE and
the base station to establish a fake UE’s connection with the base station,
thus enabling a Man-in-the-Middle attack. Furthermore, by changing bits over
the air, the attacker can launch a DoS attack by hijacking legitimate users.

###  II-B Hardware and Software Setup

Fig. 3 shows the designed srsRAN-based MITM digital twin model to simulate
emergent behavior and wildly unexpected emergent behaviors usually occurring
during legitimate physical communications. In our digital twin model,
fundamental functions of UE and gNB are implemented by srsRAN. Furthermore, we
use ZMQ, an asynchronous socket message-transfer framework implemented with
TCP protocol, as the substitute for wireless communications between UE and gNB
in the digital twin. Then we set up a MITM relay, which can listen and forward
the socket messages between UE and gNB, to represent attackers in our proposed
digital twin model. As for CN, we use Open5GS to achieve all necessary
functions of 5G protocols.

Figure 3: Digital engineering view for 5G vulnerability and unintended
emergent behavior detection.

As the core of the proposed digital twin model, MITM relay is responsible for
message listening, modification, and recording. The following is the detailed
structure of our proposed MITM relay implementation:

  * $\bullet$

Message listening. In Up_link channel, the proposed MITM relay can listen to
messages from UE by port 2003 following TCP protocol and forward the UE
messages to gNB by port 2000. Same in the downlink channel, the proposed MITM
relay can listen to port 2002 to get messages from gNB and forward them to
port 2001 of UE.

  * $\bullet$

Message modification. Based on the fuzzing probability system, illustrated in
the following section, the relay will take command-level and bit-level fuzzing
strategies to modify the message to detect vulnerabilities.

  * $\bullet$

Message recording. We build a database, shown in Fig. 6, to store the history
of messages, which we listen from UE and gNB chronologically. And our database
will also record fuzzed cases and the status of each connection attempt.

With the updated probability system by status monitors in UE and gNB, the
relay can efficiently learn the threat patterns and detect the
vulnerabilities. Not limited to MITM attacks, the relay can also simulate
overshadowing attacks or false BS attacks by message modification. Our
proposed relay can simulate any physical wireless attacks, which proves our
relay is qualified for the digital twin of attackers in the real world.

As shown in Fig 4, we apply the relay model across different layers. In
particular, we apply our fuzzing strategies to the RRC layer and the MAC
layer. The RRC layer represents the logic layer connected to the management
layer, while the MAC layer represents the management layer connected to the
physical layer. We conducted fuzzing in the RRC layer on a simulation
platform, where all identifiers can be modified at the function level.
However, fuzzing in the MAC layer was performed on an over-the-air platform to
directly change commands at the bit level. By comparing results from these
layers, we provide a more detailed mechanism analysis of the attack model
based on the inherent nature of different layers. For instance, the RRC layer
regenerates the checksum for integrity checks after command-level or bit-level
fuzzing, whereas the MAC layer directly forwards the fuzzed message without
generating the corresponding new checksum.

Figure 4: Fuzzing cross different layers.

The virtual relay mode in our platform enables the detection of
vulnerabilities through abstract and agile methodologies. It’s also vital to
evaluate real-world performance and potential vulnerabilities for a thorough
assessment. Our platform’s realistic testing environment allows for detailed
analysis of vulnerabilities, their impacts, and the system’s resilience to
various attack scenarios. In the OTA mode, depicted in Figure 5, we use srsRAN
configured as the UE to control the USRP B210 device, facilitating
communication with the Amarisoft Call Box, which acts as both the gNB and CN
components. The Amarisoft Call Box can be substituted with srsRAN for an open,
programmable Radio Access Network (RAN) and Core Network. However, current
challenges with the stability and lack of performance benchmarks in open-
source software-defined radio platforms like srsRAN, which hinder the
practical application of research in industry, lead us to use the Amari Call
Box as our benchmark framework. We retrieve communication logs from the
Amarisoft Call Box via SSH through a switch, ensuring no impact on connection
quality and performance during tests. This setup ensures seamless integration
of components, efficient data exchange and analysis, and provides a reliable,
comprehensive environment for our experimental investigations.

Figure 5:  Over the Air (OTA) Mode Experimental Setup and Configuration

##  III LAL Command-level Strategy

When our proposed system has no prior knowledge or understanding of protocols,
the system will try to detect and predict vulnerabilities without any domain
knowledge. All commands received by our relay will be encrypted and Fourier
transformed. Even under such conditions, the system proves the ability to
detect vulnerabilities in black-box environment. Especially to discover and
mitigate vulnerabilities and unintended emergent behaviors in the 5G stack
with sufficient automation and adequate scalability, we design a protocol-
independent Listen-and-Learn (LAL) based fuzzing system.

The proposed LAL fuzzing system is designed to target the RRC protocols, which
are recognized as one of the most critical cellular protocols for radio
resources management [28]. The RRC protocol configures the user and control
planes according to the network status and allows the implementation of radio
resource management. We fuzz the RRC protocols with the srsRAN 5G platform and
the tunneled NAS protocols through message reorder, injection, and
modification. We implement two-dimensional fuzzing— command-level and bit-
level, but we focus on command-level fuzzing in this work. We identify high-
risk attack paths by generating the state-Transaction graph from the command-
level fuzzing results. We further perform timely high-risk scenarios
prediction with state Transaction based LSTM.

By embedding the message exchange sniffer and the LSTM based prediction model
in virtual wireless simulation, our LAL fuzzing system is capable of
automatically and efficiently determining the command-level fuzzing message
according to the states of UE and gNB. Besides, as the designed framework is
protocol independent, it can be quickly adapted and transferred to new-
released code stacks and protocols. For example, it can be easily turned into
a hybrid design to provide provable assurance and formal threat detection for
5G software stacks by combining deterministic detection approaches such as
formal methods. Finally, we incorporate an LSTM model based on rapid
vulnerability detection. This prediction model enables proactive defenses
against potential attacks through learning the early-stage abnormal state
transaction paths. In short, the designed LAL fuzzing system can be applied to
5G and NextG architectures (e.g., ORAN) for real-time vulnerability and
unintended behavior monitoring, prediction, detection, and tracking.

###  III-A State Recording

The authentication and authorization scheme in 5G, being viewed as a finite
state transaction, enables the graphics-based analysis to identify the pattern
of the risks. During the fuzzing, the recorded states include the following
information: ‘message time’, ‘original bytes’, ‘RRC channel’, ‘message type’,
and ‘physical channel’. ‘Message time’ represents message sending time, and
‘RRC channel’ indicates which protocol we should use for message decoding. The
RRC procedure of the UE can be uniquely identified with the ’Message type’
[37]. Due to a lack of domain knowledge about encryption and transformation,
we use a general 5G protocol, pycrate [38], to interpret the first six hex
values and select the cross mapping of interpreted ‘message type’ as the
identifier to a state. Even though this interpretation approach can not
provide the correct translation of command, the feasibility of vulnerability
detection and prediction can still be proved in Sec III-C. Besides, the
‘rrcConnectionSetupComplete’ message is used as the identifier of the
successful completion of RRC establishment. When the monitor in gNB detects
the ‘rrcConnectionSetupComplete’ message, the testing case will be terminated
and labeled as a successful connection. When the monitor in gNB cannot detect
the ‘rrcConnectionSetupComplete’ message within a predefined timeout limit
($600$ seconds in the proof-of-concept experiments), it is considered a failed
connection.

We build a database to record the state and fuzzing cases. Fig. 6 illustrates
the structure of the database. The foreign keys in Fig. 6 are generated from
the primary keys of the refereed table like ‘action_id’ is generated from the
primary key ‘action_id’ in table Action. The statements of each table are
described in the following:

  * $\bullet$

State. Each state represents the state of RRC status. For each message sent
from either UE or eNB, the system will update the description of sent commands
in the table state.

  * $\bullet$

Action. Each action item records parsed message, whose channel and physical
channel represent where the commands come from.

  * $\bullet$

Probability. Each probability item records the probability of fuzzing cases
for corresponding states and actions. If one fuzzing case leads to RRC
connection failure, the probability increases. The completion rate indicates
the record of bit-level fuzzing and will be none if there is only command-
level fuzzing.

Figure 6: Structure of the database

###  III-B Command-level Fuzzing Strategy

Command-level and bit-level fuzzing are two primary protocol fuzz testing
approaches. They are also common approaches for protocol attacks. Compared to
bit-level attacks, which require time and frequency synchronization along with
information in UE profiles, command-level attacks are usually low-cost and
less information needed. Hence, we primarily focus on command-level fuzzing to
detect vulnerabilities under a black-box environment.

For fuzzing purposes, the LAL observes and collects the exchanged legitimate
messages and saves them to the fuzzing message candidate pool. At the command
level, commands are replaced by other commands in the same physical channel to
test whether any communication error state occurs. More specifically, fuzz
testing is implemented iteratively through each case in the pool. Within each
loop, we first simulate UE and gNB for connection initialization. Then we
decode the observed message and get two primary RRC identifiers: ‘interpreted
message type’ and ‘interpreted RRC TransactionIdentifier’. If the message in
this physical channel has never been observed before, we record the message
and mark it with the corresponding channel. Moreover, if there is still any
unapplied message replacement, we adapt this replacement and delete it in the
recording. Due to the change of temporary identifiers, such as rnti, most of
the replaced messages are illegal for UE or gNB. In this way, our fuzz testing
framework replaces messages with not only regular ones but also abnormal
messages since the number of message permutations grows with the increasing
number of cases. Due to no requirement of prior knowledge, LAL can be quickly
adapted and transferred to new-released code stacks and protocols.

###  III-C Result assessment

####  III-C1 State Based Vulnerability Prediction Model

As commands are listened to and selectively added to the candidate pool during
the experiments, the system needs to traverse the commands in the pool with
priority orders to perform command-level fuzzing. As an initial step to
command priority exploration, we show the RRC connection state distribution of
commands fuzzing at various channels in Fig. 7, where DL and UP in the x-axis
represent downlink and uplink channels, respectively. Among a total of $205$
collected fuzz testing cases with RRC procedures, there are $76$ successful
connections and $129$ failed connections. The majority of the failed RRC
connections are through uplink fuzzing. The failures in the downlink fuzzing
channel are primarily caused by PCCH Messages, which are used for paging the
UEs whose cell location is not known to the network.

Figure 7: RRC connection state fuzzing distribution. TABLE I: Fuzzing Test and State Distribution in Different Types Amount | Successful Connection | Failed Connection
---|---|---
| Cases
---
States
| 76
---
39
| 129
---
7

From the distribution, we can conclude that the downlink channel protocols are
more robust with unintended messages, and uplink channels are more vulnerable
than the downlink. However, due to PCCH-Messages broadcast and explicit
content nature among the downlink channel, its vulnerability could affect a
more extensive range of communications and potentially cause a DoS attack for
all UEs within the cell of the BS.

For the $129$ failed connection in Fig. 7, we identify high-risk states as
those with high frequencies in failed connections. Our results show that no
state only appears in failed connections but not in successful ones. We
identify $7$ high-risk states with higher frequencies than the average.
However, the RRC connection failure cannot be fully covered with those high-
risk states solely as rule-based detection. Therefore, we introduce
transaction-based detection using the sequenced states to enhance
vulnerability identification.

####  III-C2 Vulnerability Identification via State Transaction

With the sequence of fuzzing tests being executed, the system automatically
generates a state transaction probability map. The probability map predicts
the connection risks, and further rerouting strategies can be developed to
avoid certain states and transactions that may potentially lead to RRC
connection failures. The RRC state changes from one to another are defined and
recorded as a transaction. We can graphically represent the state and
transaction during the RRC procedures as the vertex and edge to ease further
graphics-based analysis for risk identification and prediction.

The occurrence of the state-transaction cases can be used for the rule-based
prediction of failed connections. Fig. 9 shows the state transaction frequency
on successful and failed connections, from which we can observe $7$ high-risk
state-transaction cases that almost only occur in failed connections. This
rule-based prediction using transaction frequency is more trustworthy compared
to the prediction based on state frequency. Because among all $7$ high-risk
state transactions, there is only one transition: from state 0 to state 2,
occurring in a total of 76 successful connections for only one time. By
further looking into the results of Fig. 9, we observe that $70.54\%$ failed
connections include at least one high-risk transaction. Hence, given that
recall equals $70.54\%$, a more accurate algorithm is necessary to identify
and predict RRC connection failures. In the following, we presented an LSTM
based vulnerability prediction on providing high-confidence predictions.

---
(a)
(b)
Figure 8: State transaction frequency on: (a) successful connection; (b)
failed connection.

####  III-C3 LSTM Based Vulnerability Prediction

The results from Sec. III-C1 and III-C2 show that the statistic and rule-based
classification can only achieve recall up to $70.54\%$, which is unreliable in
practice. Therefore, we design an LSTM based vulnerability prediction model
for reliability enhancement and early prediction. With the early prediction of
RRC connection failures, we can enable RRC state rerouting strategy to avoid
the failures.

We define the input of LSTM as the sequenced states from the fuzzing
occurrence and the length of the sequenced states as the cut-off length. The
cut-off length determines how long a state transaction path can be sufficient
to meet the expected accuracy. Two approaches are used to specify the cut-off
length: _duration from beginning_ and _number of states from beginning_. To
avoid overfitting, we use $20\%$ of the dataset as testing data and $0.001$ as
the learning rate of the model. Moreover, for each input size, we average the
accuracy, precision, and recall over $100$ runs. Each run includes $30$
epochs, and each epoch includes $10$ batches. As shown in the performance
evaluation of both approaches in Fig. 9, accuracy grows with the increasing
number of steps or times and increases sharply after the $8$-th step.

---
(a)
(b)
Figure 9: Receiver Operating Characteristics (ROC) analysis of LSTM over: (a)
steps; (b) duration.

To balance the performance and reaction time, we generate ROC curves over
steps and duration to find the strategy with the least cut-off length and
almost $90\%$ AUC. From Fig. 9(a), $10$ steps is the optimal strategy that
achieves stable $89\%$ AUC. And we can get that $0.08s$ is the optimal
strategy that achieves $96\%$ AUC. Therefore, we take $10$ steps and $0.08$s
as the input to do deeper analysis on the converge performance of LSTM. From
converge performance of LSTM, we find that LSTM can learn the optimal
parameter in 2 or 3 epochs. The fast convergence proves that our system has
the ability to learn the pattern of failed connections. The average cut-off
duration of $10$-th steps is $0.072$ seconds with the accuracy achieving
$89\%$, which is consistent with setting the cut-off length as $0.08$ seconds
through the duration cut-off approach. The accurate and timely prediction also
provides sufficient time for proactive defense before RRC connection
completion or failure, with an average of $3.49$ seconds.

With an average performance of LSTM meeting the accuracy expectation, we
analyze failed predictions, including False Positive and False Negative ones,
for further improvements. The following patterns are summarized as
misclassified cases.

False Positive: When there are three messages, which are interpreted as paging
messages, sent by gNB within the first ten states in connections, the model
may misclassify this connection as a failed one. Because most of the failed
connections also have three paging messages in the first ten states. This
pattern can be addressed by a finer definition of paging messages in future
work.

False Negative: The cases with multiple times of interpreted
$\rm{active\\_set\\_update}$ messages in downLink channels are classified as
failed connections and lead to false alarms. A high frequency of interpreted
$\rm{active\\_set\\_update}$ messages occur more frequently in successful
connections. Cross-layer or side channel information could be applied to
improve the false alarm rate in future work.

The proposed vulnerability and unintended behavior detection system could also
be applied in real-time, in compliance with O-RAN architecture [39]. When
deployed for real-time monitoring, timing in detection is critical to mitigate
the vulnerabilities and provide assurance and high-quality communications.
There are sufficient intervals, an average of $3.49$ seconds, between
successful detection time and RRC connection successful/failed time, as shown
in Fig. 10, which gives enough defense time for potential attacks. Moreover,
we have tinier gaps between fuzzing occurrence time and successful detection
time.

Figure 10: Comparison of detection time and completion time.

##  IV SyAL Domain Assisted Strategy

Synchronization in the generated random identifier of each fuzzing case
enables more domain information background possible for MITM attacker,
including command type and critical identifier values. Leveraging the domain
knowledge, we propose a probability-based command-level fuzzing system called
Synchronize-and-Learn (SyAL) to help our proposed digital twin MITM attacker
be more efficient in prioritizing and locating the more vulnerable areas. In
the proof-of-concept of this study, we fix the RNTI of UE to keep commands
synchronized in different fuzzing cases. RNTI is the CRC mask, which is
generated in synchronization procedure and required to encode and decode DCI
message. The synchronized commands provide domain-assisted background
knowledge for our digital twin MITM attacker. Furthermore, our proposed
probability-based command-level fuzzing system takes a Sync-and-Learn strategy
to learn the vulnerability pattern efficiently and prioritize high-risk
commend-level fuzzing cases. The result of this study proves the significance
of timing in the 5G AKA.

###  IV-A Not Illegal Command-level Fuzzing in the Not-illegal Not-valid Set

Besides the illegal command-level fuzzing in LAL, we will continue not illegal
command-level fuzzing, which contains correct identifiers and can be
appropriately interpreted by UE and gNB, in this section. Through changing the
occurrence timing of not illegal commands, we can find a path that can
transfer from ‘green zone’, valid states, to ‘yellow zone’, not illegal and
not valid states, in Fig. 1. This part of the experiment provides substantial
proof of the feasibility of the listen-and-replace relay attack directed by a
part of the communication context. Due to the limitation of the numerous
capacity for command-level fuzzing permutation, we focus on the downlink
channel, which is sent from gNB and is more vulnerable than uplink. All
messages in the downlink channel are duplicated with the same RNTI and belong
to legal or not illegal commands (the ‘green zone’ or ‘yellow zone’ in Fig.
1).

###  IV-B Probability-based Fuzzing Strategy

With the domain knowledge of message types, we proposed a probability-based
command-level fuzzing system to learn the vulnerability pattern efficiently
and prioritize high-risk commend-level fuzzing cases. The efficiency of our
proposed probability-based command-level fuzzing system outperforms
traditional fuzzing systems, like brute force fuzzing.

Algorithm 1 describes the detailed process of a probability-based fuzzing
system. First, we build up a database to store all commands in the downlink
channel, whose structure shows in Fig. 6. Then we initialize a command-level
fuzzing probability matrix $D.p$ with the size of $n\times n$, $n$ is the
number of commands, to represent the probability of command fuzzing cases. The
value of $D.p_{i,j}$ means the probability of the fuzzing case, which changes
from command $i$ to command $j$, is high-risk. After initialization, the
system updates the command-level fuzzing probability matrix based on the
fuzzing result after each fuzzing test. The command-level fuzzing probability
matrix update follows the independent rule: the system can only update the row
and column corresponding to fuzzed commands. Moreover, in each fuzzing case,
the system uses the proposed digital twin MITM attacker to generate fuzzing
cases based on the value of the command-level fuzzing probability matrix
$D.p$.

Input: $I_{1}$, $I_{2}$

Output: $O_{1}$, $O_{2}$

Initialization: Database $D$, $ratio=0.1$, $\alpha=0.5$,
$D(p,p^{\prime})\leftarrow$ probabilities for replacement commands,
$fuzzed\leftarrow False$

1: procedure Fuzzing_Relay($I_{1}$)

2: while exist_fuzzing(D) do

3: start_simulator()

4: command_history $c\leftarrow$ []

5: while $!\,time\\_out()$ do

6: if $a$ = received_action($I_{2}$) then

7: if $a$ = rrc_Connection_Complete then

8: break

9: end if

10: update $D$($a$)

11: if fuzzed then

12: continue

13: else

14: $a^{\prime}$ = $random(D.p[a,:])$ //Weighted random

15: $send\\_as\\_O_{2}$($a^{\prime}$)

16: $c$ += ($a$,$a^{\prime}$)

17: $D.p^{\prime}.update.$($a^{\prime}$) $fuzzed$ = $true$

18: end if

19: end if

20: end while

21: if connection_failed() then

22: $D.p$[$a$,$a^{\prime}$] += $D.p[a,a^{\prime}]\times\alpha$

23: else

24: $D.p$[$a$,$a^{\prime}$] -= $D.p[a,a^{\prime}]\times\alpha\times ratio$

25: end if //Update database as $O_{2}$

26: end while

Algorithm 1 SyAL Fuzzing Testing

###  IV-C Result Assessment

TABLE II: Legal Command-level Fuzzing Test Distribution in Different Types Amount | Successful Connection | Failed Connection
---|---|---
| Cases
---
States
| 3037
---
43
| 54
---
13 (high-risk)

As mentioned in Table II, there are 3080 possible fuzzing cases and only 43
vulnerabilities. In Fig. 11, we present fuzz testing tracks of two fuzzing
strategies: random fuzzing and probability-based fuzzing, until all
vulnerabilities are found. In Fig. 11(a), there are 2811 fuzzing cases fuzzed
by random fuzzing strategy until all vulnerabilities founded. However, the
probability-based fuzzing strategy takes only 1027 fuzzing cases to get all
vulnerabilities in Fig. 11(b). Therefore, we can easily conclude that the
probability-based fuzzing strategy can locate the vulnerabilities much more
efficiently than the random fuzzing strategy.

---
(a)
(b)
Figure 11: Fuzz testing tracks on downlink channels of: (a) random fuzzing;
(b) probability-based fuzzing.

Further, we use the hyper-parameter strategy with the permutation of change
percentage $\alpha$ from 0.1 to 2 and failed attenuation $ratio$ from 0.9 to
0.1 to get the optimal parameters set for probability-based fuzzing strategy.
However, the result of the hyper-parameter, which is shown in Fig. 12,
provides an intuition that the modification of the probability ratio makes no
difference in the gradients of the vulnerability detection ratio curve. Even a
larger increasing probability ratio may speed up the detection in the first
period; the final estimated number of steps to detect all vulnerabilities is
almost indistinguishable.

Figure 12: Sensitivity analysis of different probability ratio.

We use several algorithms to fit strategies and generate the best
representations for each strategy. With the assumption that the number of
fuzzed cases is $i$, we find that the regress exponential algorithm,
$2.072\times\mathrm{e}^{0.004i}$ orange dashed line in Fig. 13, is the best
fitting algorithm to the beginning period of probability-based fuzzing with
$R^{2}$ value of 0.972. And for the end of probability-based fuzzing,
vulnerabilities that do not follow the learned pattern are the primary reason
for slow-down growth, like the case which changes command AV to command U
shown as blue square in Fig. 11(b). Furthermore, for random fuzzing, the
linear algorithm, $0.015i-0.617$ blue dashed line in Fig. 13, is the best
fitting algorithm with $R^{2}$ value of 0.987.

To accelerate the speed of vulnerability detection in the beginning period, we
design a probability-based fuzzing strategy with extra prior knowledge. In the
preknowledge probability-based fuzzing strategy, we assign two arbitrary
vulnerabilities as the extra prior knowledge to skip the pattern collection
procedures in the beginning period. We run 20 times of each strategy, and plot
the average and part of random points in Fig. 13. The random fuzzing strategy
has the worst performance among the three strategies, and the other strategies
have similar performance except for the beginning period. In the beginning
period, the prior knowledge can provide a local gaudiness for the probability
fuzzer to efficiently locate the vulnerabilities, which is twice faster than
the probability-based fuzzing strategy, especially in the first 500 fuzzing
cases. Then, we can take advantage of extra prior knowledge to speed up the
short-term efficiency of vulnerability detection.

Figure 13: Comparison of Benchmark random-based fuzzing and probability-based
fuzzing.

To better understand the detected vulnerabilities in our proposed probability-
based fuzzing strategy, we have selected some commands as samples, listed in
Table III, to analyze and evaluate their impacts on both the RRC layer and the
MAC layer. The results, as shown in Table IV, indicate that reactions vary
between different layers. For instance, replacing command A with command B in
the RRC layer will pass the integrity check at the gNB but lead to a failed
connection due to the inconsistency caused by the command substitution.
However, replacing Command A with Command B in the MAC layer will lead to
repeated transmission of commands from the UE, effectively resulting in a
Denial of Service (DoS) attack.

TABLE III: Command List Command Index | Command Type
---|---
A | RRC connection request
B | RRC connection setup complete
C | UL information transfer
D | Security mode complete
E | UE capability information
TABLE IV: Comparison of Fuzz Strategy in Different Platforms Fuzz Strategy (Up-Link) |  RRC layer |  MAC layer
---|---|---
command A $\rightarrow$ command D |  Failed connection |  Repeat of command A
command B $\rightarrow$ command D |  Failed connection |  Failed connection

##  V SoAL Bit-level Strategy

Source-and-Learn (SoAL) Bit-level Strategy provides a digital twin of some
active attacks such as overshadowing [40], which can change part of identifier
values of communicated commands. In this strategy, we take two approaches,
before-encryption and after-encryption, to represent two different scenarios,
with domain knowledge and without domain knowledge. Compared to the
traditional psychical overshadowing test, our proposed bit-level strategy
achieves efficient vulnerability detection, which helps us fuzz more
vulnerable cases and focus on the protocol.

###  V-A Risk Prioritized Fuzzing strategy

Bit-level fuzzing is to randomly change the value of different identifiers in
the specific command to generate different fuzzing cases. Following the
guidance of command-level fuzzing, we can take more efficient bit-level
fuzzing to locate vulnerabilities. For instance, based on the result of
command-level fuzzing, we can first do bit-level fuzzing on these high-risk
commands, e.g., command C and command H in Fig. 11.

During the bit-level fuzzing procedure, we set a message detection and multi-
lists of identifiers which cover the value range. For any specific message,
the system takes a random value which has never been used to replace the
identifier. There are two replacement strategies on bit-level fuzzing: before-
encryption and after-encryption. Before-encryption approach is to change the
identifier values before the protocol encryption while after-encryption
approach is implemented in a reserved way. In this way, we can try all
possible fuzzing cases to specific identifiers in special commands.

###  V-B Result Assessment of Bit-level Fuzzing

Based on the result of Qpaque command-level and domain probability-based
command-level fuzzing. As shown in Table V, three high-risk commands, ‘RRC
Setup Request,’ ‘RRC Reconfiguration,’ and ‘RRC connection,’ are selected as
our bit-level fuzzing target.

In the ‘RRC Setup Request’ command, we fuzz it with both the before-encryption
and after-encryption approaches. For the before-encryption approach, there
were three identifiers: ‘ue-Identity’, ‘Establishment Cause’, and ‘spare’.
Since the ‘spare’ identifier never contains critical information and only
occupies 1 bit, we only do bit fuzzing on ‘ue-Identity’ and ‘Establishment
Cause’. As shown in Table V, any value for ‘ue-Identity’ will not affect the
connection. However, a different value of ‘Establishment Cause’ can make
connection transfer into different service types, as also mentioned in [41].
For example, if we change ‘Establishment Cause’ from bit 0110 to bit 0000, UE
can only request an emergency call. Moreover, with the after-encryption
approach, all fuzzing cases lead to disconnection. This shows the integrity
check for 5G protocol can identify whether the message is modified or not.

To further analyze the mechanism of the attack model across different layers,
we use the ‘RRC Setup Request’ command as an example, as detailed in Table VI.
In the MAC layer, all fuzzing attempts, regardless of the command identifier,
result in failed connections. This outcome clearly indicates that an integrity
check is crucial during the authentication process, as bit-level fuzzing
without regeneration of the integrity checksum effectively simulates a Denial
of Service (DoS) attack.

Except for the ‘RRC Setup Request’ command, we also fuzz other two downlink
commands, ‘RRC Reconfiguration’ (command C in Fig. 11) and ‘RRC Connection’
(command H in Fig. 11). In ‘RRC Reconfiguration’ command, we take ‘sr-
ConfigIndex’ as our target because this identifier is responsible for radio
scheduling and critical for connection establishment. However, no matter how
we modify the ‘sr-ConfigIndex’, the connection between UE and gNB can still be
established. On the contrary, when we fuzz the identifier ‘srb1_srn_id’ in
‘RRC Connection’ command with different values, UE rejects the connection
establishment. Therefore, we conclude that UE may have alternative methods to
negotiate the ‘sr-ConfigIndex’, but cannot accept a new ‘srb_id’.

TABLE V: Result of Bit-level Fuzzing

Channel | Command | Identifier | Fuzzing Value | Result
---|---|---|---|---
CCCH (Up_Link) |  RRC Setup Request | ue-Identity | 00 | successful
01 | successful
10 | successful
Establishment Cause | 0000 | emergency
0001 | nulltype
0010 | high_prio_access
0011 | nulltype
0100 | mt_access
0101 | nulltype
0110 | mo_sig
0111 | nulltype
1000 | mo_data
1001 | nulltype
1010 |  | delay_tolerant
---
_access_v1020
1011 | nulltype
1100 |  | mo_voice
---
_call_v1280
1101 | nulltype
1110 | spare1
1111 | nulltype
spare | None | None
PDCCH (Down_Link) |  RRC Reconfiguration | sr-Configindex | <5 | successful
<15 | successful
<35 | successful
<75 | successful
<155 | successful
<157 | successful
= 157 | successful
CCCH (Down_Link) |  RRC Connection | srb1.srb_id | 0 | Reject
2 | Reject

TABLE VI: Comparison of Different Bit-level Strategies

Command | Identifier |  | Fuzzing
---
Value
| Fuzzing in
---
RRC Layer
| Fuzzing in
---
MAC Layer
RRC Connection Request | UE-Identity | 00 | successful | failed
01 | successful | failed
10 | successful | failed
Establishment Cause | 0000 | emergency | failed
0001 | nulltype | failed
0010 | high_prio_access | failed
0011 | nulltype | failed
0100 | mt_access | failed
0101 | nulltype | failed
0110 | mo_sig | failed
0111 | nulltype | failed
1000 | mo_data | failed
1001 | nulltype | failed
1010 |  | delay_tolerant
---
_access_v1020
failed
1011 | nulltype | failed
1100 |  | mo_voice
---
_call_v1280
failed
1101 | nulltype | failed
1110 | spare1 | failed
1111 | nulltype | failed

In Fig. 14, our system shows the ability to detect vulnerabilities
efficiently. Among all 33 possible before-encryption cases, our system detects
10 vulnerabilities. As for the after-encryption approach, we find that it is
unlikely to find a successful case because of the integrity check. Hence, we
conclude that only fuzzing before-encryption is the only appropriate way for
vulnerability detection in bit-level fuzzing.

Figure 14: RRC high-risk command fuzzing distribution

##  VI Comparison Analysis

As shown in Table VII, in the landscape of fuzzing methodologies, our models
(LAL, SyAL, SoAL) emerge as a sophisticated evolution from existing paradigms
represented by BASESAFE [42], BaseSPEC [43], FIRMWIRE [44], LTEFuzz [45],
LTEInspector [46], and Directfuzz [47]. Each model is characterized by a
specific approach that dictates the required level of pre-knowledge and the
degree of automation in the fuzzing process. Adopting a black box approach,
the LAL model eliminates the requirements for complex system knowledge and
gets the capacity of automatically command-level fuzzing. This model enables
an extensive evaluation of the system’s external interfaces, independent of
the internal architecture. This black box approach contrasts sharply with the
semi-automated, white box strategies of models like BASESAFE and BaseSPEC,
which require comprehensive internal system understanding for testing baseband
and conducting non-task boundary fuzzing, respectively. On the other hand, the
SyAL model is categorized within the grey box domain, denoting a moderate
level of protocol structure comprehension, thereby refining the precision of
the fully automated bit-level fuzzing capabilities. This model offers a
compromise, bridging the extensive system insight required by white box
models—such as LTEInspector, which engages in rule-based, command-level
fuzzing with full access to LTE source software—and the no-prior-knowledge
approach embodied by LAL. Lastly, the SoAL model parallels the white box
strategies by employing an exhaustive knowledge-based, semi-automated strategy
with bit-level fuzzing. Compared to FIRMWIRE’s prerequisite of baseband
initialization through boot procedures, this approach can thoroughly examine
the system’s vulnerabilities without root privilege. We collectively present
various models with different automation levels and knowledge prerequisites,
enabling them to be flexibly deployed across various testing scenarios. The
LAL model is notable for its operational independence from system pre-
knowledge; SyAL strikes a balance with limited insight into the protocol
structure; and SoAL aligns with traditional white box methods in its detailed
approach but surpasses them in automation efficiency.

TABLE VII: Comparison Analysis with Different Fuzzing Strategies Approaches | System Model |  | Prior-knowledge
---
Requirement
Fuzzing Technologies | Automation Level
BASESAFE | White box | Baseband firmware |  | Command-level fuzzing in
---
non-task boundaries
Semi-automated
BaseSPEC | White box | Baseband firmware |  | Bit-level fuzzing in
---
non-task boundaries
Semi-automated
FIRMWIRE | White box |  | Initialize the baseband
---
through boot
| Command-level fuzzing in
---
Baseband’s RTOS APIs
Semi-automated
LTEFuzz | White box |  | Fully controllable LTE
---
open source software
| Rule-based
---
command-level fuzzing
Semi-automated
LTEInspector | White box |  | Abstract LTE model
---
| Rule-based
---
command-level fuzzing
Semi-automated
Directfuzz | Gray box |  | RTL input range
---
| Coverage guided
---
bit-level fuzzing
Fully-automated
Ours |  | Listen-and-Learn
---
(LAL)
Black box |  | No prior-knowledge
---
required
Command-level fuzzing | Fully-automated
| Synchronize-and
---
-Learn (SyAL)
| Gray box
---
(Protocol
Structure)
Meassge inerpreter |  | Bit-level fuzzing
---
Fully-automated
| Source-and-Learn
---
(SoAL)
White box | SrsRAN modification | Bit-level fuzzing | Semi-automated

##  VII Conclusion

We designed a novel fuzzing approach that systematically and cumulatively
detects vulnerabilities for 5G and NextG protocols. Our approach is designed
to detect, characterize, predict, and reveal vulnerabilities with varying
levels of prior knowledge assumptions for attackers, beginning from no prior
knowledge to full source code access. A digital twin framework was proposed
and three fuzzing strategies were developed: LAL (black-box fuzzing), SyAL
(gray-box fuzzing), and SoAL (white-box fuzzing). In black-box scenarios where
no prior knowledge of the platform is known, the LAL strategy randomly
arranges the sequence of commands. In gray-box scenarios where partial access
to information is allowed, the SyAL strategy randomly replays the record
commands with access to critical synchronization information for potential
user information collection, which is similar to RNTI. When the system is a
white-box that supports full access to source code, the SoAL method performs
bit-level fuzzing guided by the command-level fuzzing of LAL and SyAL for risk
analysis transparency and reasoning.

In particular, the LAL strategy detected 129 vulnerabilities with 39 command
types using only transmitted messages, and the embedded LSTM model efficiently
predicted over 89% of connection failures in 0.072 seconds on average. We then
proposed a probability-based vulnerability detection method in the SyAL
strategy, which achieves a linear growth of time cost with system size and
allows for the detection of all vulnerabilities with partial user privacy
information. This outperforms traditional fuzzing models with exponential
growth of time consumption. In addition, based on the results of the SyAL
strategy, the proposed SoAL method not only validates the integrity mechanism
of 5G protocols but also detects three types of man-in-the-middle (MITM)
vulnerabilities that are critical to protocol security. Extensive simulation
results demonstrated that the designed fuzzing system is an efficient,
automated approach that supports real-time vulnerability detection and
proactive defense for existing 5G platforms and future released protocols.

## Acknowledgment

This effort was sponsored by the Defense Advanced Research Project Agency
(DARPA) under grant no. D22AP00144. The views and conclusions contained herein
are those of the authors and should not be interpreted as necessarily
representing the official policies or endorsements, either expressed or
implied, of DARPA or the U.S. Government.

## References

  * [1] Y. Wang, A. Gorski, and L. A. DaSilva, “AI-Powered Real-Time Channel Awareness and 5G NR Radio Access Network Scheduling Optimization,” 2021.
  * [2] O-RAN Alliance, “O-RAN: Towards an Open and Smart RAN,” _O-RAN Alliance_ , no. October, 2018.
  * [3] Y. Wang, A. Gorski, and A. da Silva, “Development of a Data-Driven Mobile 5G Testbed: Platform for Experimental Research,” in _IEEE International Mediterranean Conference on Communications and Networking_ , 2021.
  * [4] J. Breen, A. Buffmire, J. Duerig, K. Dutt, E. Eide, A. Ghosh, M. Hibler, D. Johnson, S. K. Kasera, E. Lewis, D. Maas, C. Martin, A. Orange, N. Patwari, D. Reading, R. Ricci, D. Schurig, L. B. Stoller, A. Todd, J. Van der Merwe, N. Viswanathan, K. Webb, and G. Wong, “POWDER: Platform for Open Wireless Data-driven Experimental Research,” _Computer Networks_ , vol. 197, 2021.
  * [5] Y. Wang, P. Tran, and J. Wojtusiak, “From Wearable Device to OpenEMR: 5G Edge Centered Telemedicine and Decision Support System,” in _the 15th International on Health Informatics_ , 2022.
  * [6] Informationstechnische Gesellschaft im VDE, E. Verband der Elektrotechnik, and Institute of Electrical and Electronics Engineers., _WSA 2019 : 23rd International ITG Workshop on Smart Antennas._
  * [7] I. Gomez-Miguelez, A. Garcia-Saavedra, P. D. Sutton, P. Serrano, C. Cano, and D. J. Leith, “srsLTE: An Open-Source Platform for LTE Evolution and Experimentation,” 2 2016. [Online]. Available: http://arxiv.org/abs/1602.04629
  * [8] D. Holmes, M. Papathanasaki, L. Maglaras, M. A. Ferrag, S. Nepal, and H. Janicke, “Digital twins and cyber security–solution or challenge?” in _2021 6th South-East Europe Design Automation, Computer Engineering, Computer Networks and Social Media Conference (SEEDA-CECNSM)_. IEEE, 2021, pp. 1–8.
  * [9] B. Teisserenc and S. Sepasgozar, “Adoption of blockchain technology through digital twins in the construction industry 4.0: A pestels approach,” _Buildings_ , vol. 11, no. 12, p. 670, 2021.
  * [10] F. Böhm, M. Dietz, T. Preindl, and G. Pernul, “Augmented reality and the digital twin: State-of-the-art and perspectives for cybersecurity,” _Journal of Cybersecurity and Privacy_ , vol. 1, no. 3, pp. 519–538, 2021.
  * [11] H. X. Nguyen, R. Trestian, D. To, and M. Tatipamula, “Digital twin for 5g and beyond,” _IEEE Communications Magazine_ , vol. 59, no. 2, pp. 10–15, 2021.
  * [12] J. Jagannath, K. Ramezanpour, and A. Jagannath, “Digital twin virtualization with machine learning for iot and beyond 5g networks: Research directions for security and optimal control,” in _Proceedings of the 2022 ACM Workshop on Wireless Security and Machine Learning_ , 2022, pp. 81–86.
  * [13] P. Almasan, M. Ferriol-Galmés, J. Paillisse, J. Suárez-Varela, D. Perino, D. López, A. A. P. Perales, P. Harvey, L. Ciavaglia, L. Wong _et al._ , “Network digital twin: Context, enabling technologies and opportunities,” _arXiv preprint arXiv:2205.14206_ , 2022.
  * [14] S. Vakaruk, A. Mozo, A. Pastor, and D. R. López, “A digital twin network for security training in 5g industrial environments,” in _2021 IEEE 1st International Conference on Digital Twins and Parallel Intelligence (DTPI)_. IEEE, 2021, pp. 395–398.
  * [15] H. X. Nguyen, R. Trestian, D. To, and M. Tatipamula, “Digital Twin for 5G and beyond,” _IEEE Communications Magazine_ , vol. 59, no. 2, pp. 10–15, 2 2021.
  * [16] R. P. Jover and V. Marojevic, “Security and protocol exploit analysis of the 5G specifications,” _IEEE Access_ , vol. 7, pp. 24 956–24 963, 2019.
  * [17] M. Lichtman, R. Rao, V. Marojevic, J. Reed, and R. P. Jover, “5g nr jamming, spoofing, and sniffing: Threat assessment and mitigation,” in _2018 IEEE International Conference on Communications Workshops (ICC Workshops)_ , 2018, pp. 1–6.
  * [18] S. R. Hussain, M. Echeverria, I. Karim, O. Chowdhury, and E. Bertino, “5Greasoner: A property-directed security and privacy analysis framework for 5G cellular network protocol,” in _Proceedings of the ACM Conference on Computer and Communications Security_. Association for Computing Machinery, 11 2019, pp. 669–684.
  * [19] H. Al Salem and J. Song, “Grammar-based fuzzing tool using markov chain model to generate new fuzzing inputs,” in _2021 International Conference on Computational Science and Computational Intelligence (CSCI)_. IEEE, 2021, pp. 1924–1930.
  * [20] J. Yang, Y. Wang, T. X. Tran, and Y. Pan, “5g rrc protocol and stack vulnerabilities detection via listen-and-learn,” in _2023 IEEE 20th Consumer Communications & Networking Conference (CCNC)_. IEEE, 2023, pp. 236–241.
  * [21] H. Wang, B. Cui, W. Yang, J. Cui, L. Su, and L. Sun, “An automated vulnerability detection method for the 5g rrc protocol based on fuzzing,” in _2022 4th International Conference on Advances in Computer Technology, Information Science and Communications (CTISC)_. IEEE, 2022, pp. 1–7.
  * [22] F. He, W. Yang, B. Cui, and J. Cui, “Intelligent fuzzing algorithm for 5g nas protocol based on predefined rules,” in _2022 International Conference on Computer Communications and Networks (ICCCN)_. IEEE, 2022, pp. 1–7.
  * [23] C. Chen, R. Kande, N. Nyugen, F. Andersen, A. Tyagi, A.-R. Sadeghi, and J. Rajendran, “Hypfuzz: Formal-assisted processor fuzzing,” _arXiv preprint arXiv:2304.02485_ , 2023.
  * [24] L. Rullo, “Rainfuzz: reinforcement-learning driven heat-maps for boosting coverage-guided fuzzing,” 2021.
  * [25] K. Singh, S. S. Grover, and R. K. Kumar, “Cyber security vulnerability detection using natural language processing,” in _2022 IEEE World AI IoT Congress (AIIoT)_. IEEE, 2022, pp. 174–178.
  * [26] L. J. Moukahal, M. Zulkernine, and M. Soukup, “Vulnerability-oriented fuzz testing for connected autonomous vehicle systems,” _IEEE Transactions on Reliability_ , vol. 70, no. 4, pp. 1422–1437, 2021.
  * [27] Z. Salazar, F. Zaidi, W. Mallouli, A. R. Cavalli, H. N. Nguyen, and E. M. de Oca, “A formal approach for complex attacks generation based on mutation of 5g network traffic,” in _International Conference on Software and Data Technologies_ , vol. 1, 2022, pp. P–234.
  * [28] S. Potnuru and P. K. Nakarmi, “Berserker: ASN.1-based Fuzzing of Radio Resource Control Protocol for 4G and 5G,” in _International Conference on Wireless and Mobile Computing, Networking and Communications_ , vol. 2021-October. IEEE Computer Society, 2021, pp. 295–300.
  * [29] X. Han, Q. Wen, and Z. Zhang, “A mutation-based fuzz testing approach for network protocol vulnerability detection,” in _Proceedings of 2012 2nd International conference on computer science and network technology_. IEEE, 2012, pp. 1018–1022.
  * [30] Z. Salazar, H. N. Nguyen, W. Mallouli, A. R. Cavalli, and E. M. Montes De Oca, “5Greplay: A 5G Network Traffic Fuzzer - Application to Attack Injection,” in _ACM International Conference Proceeding Series_. Association for Computing Machinery, 8 2021.
  * [31] R. Ma, S. Ren, K. Ma, C. Hu, and J. Xue, “Semi-valid fuzz testing case generation for stateful network protocol,” _Tsinghua Science and Technology_ , vol. 22, no. 5, pp. 458–468, 2017.
  * [32] S. Bratus, A. Hansen, and A. Shubina, “Lzfuzz: a fast compression-based fuzzer for poorly documented protocols,” 2008.
  * [33] D. Dolev and A. Yao, “On the security of public key protocols,” _IEEE Transactions on information theory_ , vol. 29, no. 2, pp. 198–208, 1983.
  * [34] P. Syverson, C. Meadows, and I. Cervesato, “Dolev-yao is no better than machiavelli,” in _First Workshop on Issues in the Theory of Security—WITS’00_ , 2000, pp. 87–92.
  * [35] Jingda Yang, Ying Wang, Tuyen X. Tran, and Yanjun Pan, “5G RRC Protocol and Stack Vulnerabilities Detection via Listen-and-Learn,” in _IEEE Consumer Communications & Networking Conference_, 2023.
  * [36] D. Dauphinais, M. Zylka, H. Spahic, F. k. Shai, J. Yang, I. Cruz, J. Gibson, and Y. Wang, “Automated Vulnerability Testing and Detection Digital Twin Framework for 5G Systems,” in _9th IEEE International Conference on Network Softwarization_ , Madrid, 6 2023.
  * [37] TSGR, “TS 138 331 - V15.2.1 - 5G; NR; Radio Resource Control (RRC); Protocol specification (3GPP TS 38.331 version 15.2.1 Release 15),” Tech. Rep., 2018.
  * [38] P. Security, “Pycrate,” 2022. [Online]. Available: https://github.com/P1sec/pycrate#readme
  * [39] M. Polese, L. Bonati, S. D’Oro, S. Basagni, and T. Melodia, “Understanding o-ran: Architecture, interfaces, algorithms, security, and research challenges,” _arXiv preprint arXiv:2202.01032_ , 2022.
  * [40] N. Ludant and G. Noubir, “Sigunder: a stealthy 5g low power attack and defenses,” in _Proceedings of the 14th ACM Conference on Security and Privacy in Wireless and Mobile Networks_ , 2021, pp. 250–260.
  * [41] E. Bitsikas and C. Pöpper, “Don’t hand it over: Vulnerabilities in the handover procedure of cellular telecommunications,” in _Annual Computer Security Applications Conference_ , 2021, pp. 900–915.
  * [42] D. Maier, L. Seidel, and S. Park, “Basesafe: Baseband sanitized fuzzing through emulation,” in _Proceedings of the 13th ACM conference on security and privacy in wireless and mobile networks_ , 2020, pp. 122–132.
  * [43] E. Kim, D. Kim, C. Park, I. Yun, and Y. Kim, “Basespec: Comparative analysis of baseband software and cellular specifications for l3 protocols.” in _NDSS_ , 2021.
  * [44] G. Hernandez, M. Muench, D. Maier, A. Milburn, S. Park, T. Scharnowski, T. Tucker, P. Traynor, and K. Butler, “Firmwire: Transparent dynamic analysis for cellular baseband firmware,” in _Network and Distributed Systems Security Symposium (NDSS) 2022_ , 2022.
  * [45] H. Kim, J. Lee, E. Lee, and Y. Kim, “Touching the untouchables: Dynamic security analysis of the lte control plane,” in _2019 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2019, pp. 1153–1168.
  * [46] S. Hussain, O. Chowdhury, S. Mehnaz, and E. Bertino, “Lteinspector: A systematic approach for adversarial testing of 4g lte,” in _Network and Distributed Systems Security (NDSS) Symposium 2018_ , 2018.
  * [47] S. Canakci, L. Delshadtehrani, F. Eris, M. B. Taylor, M. Egele, and A. Joshi, “Directfuzz: Automated test generation for rtl designs using directed graybox fuzzing,” in _2021 58th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2021, pp. 529–534.

|  Jingda Yang (Graduate Student Member, IEEE) received the B.E. degree in
software engineering from Shandong University and the M.Sc. degree in computer
science from The George Washington University. He is currently a Ph.D. student
in the School of System and Enterprises at Stevens Institute of Technology.
His research interests are formal verification and vulnerability detection of
wireless protocol in 5G.
---|---
|  Ying Wang (Member, IEEE) received the B.E. degree in information
engineering at Beijing University of Posts and Telecommunications, M.S. degree
in electrical engineering from University of Cincinnati and the Ph.D. degree
in electrical engineering from Virginia Polytechnic Institute and State
University. She is an associate professor in the School of System and
Enterprises at Stevens Institute of Technology. Her research areas include
cybersecurity, wireless AI, edge computing, health informatics, and software
engineering.
---|---
|  Yanjun Pan (Member, IEEE) received the B.E. degree in Information
Engineering from Nanjing University of Aeronautics and Astronautics, China in
2016. She earned her M.S. degree and Ph.D. in Electrical and Computer
Engineering from the University of Arizona, USA, in 2018 and 2021,
respectively. She is an assistant professor in the Department of Computer
Science and Computer Engineering at the University of Arkansas. Her current
research interests include wireless security, information security, wireless
sensing, and network optimization, with emphases on physical layer security,
privacy-preserving technologies, mmWave sensing, and cross-layer optimization.
---|---
|  Tuyen X. Tran (Senior Member, IEEE) received the BEng degree (honors
program) in Electronics and Telecommunications from the Hanoi University of
Science and Technology, Vietnam, in 2011, the MSc degree in Electrical and
Computer Engineering (ECE) from the University of Akron, Ohio, in 2013, and
the PhD degree in ECE from Rutgers University, New Jersey, in 2018. His
research interests include wireless communications, mobile cloud computing,
and network optimization. He is currently a principal inventive scientist with
AT&T Labs Research, Bedminster, New Jersey.
---|---


# Concurrent normals of immersed manifolds

Gaiane Panina  Dirk Siersma

###### Abstract

It is conjectured since long that for any convex body $K\subset\mathbb{R}^{n}$
there exists a point in the interior of $K$ which belongs to at least $2n$
normals from different points on the boundary of $K$. The conjecture is known
to be true for $n=2,3,4$.

Motivated by a recent results of Y. Martinez-Maure, and an approach by A.
Grebennikov and G. Panina, we prove the following: Let a compact smooth
$m$-dimensional manifold $M^{m}$ be immersed in $\mathbb{R}^{n}$. We assume
that at least one of the homology groups $H_{k}(M^{m},\mathbb{Z}_{2})$ with
$k<m$ vanishes. Then under mild conditions, almost every normal line to
$M^{m}$ contains an intersection point of at least $\beta+4$ normals from
different points of $M^{m}$, where $\beta$ is the sum of Betti numbers of
$M^{m}$.

###### keywords:

Concurrent normals, focal sets, bifurcation, Morse-Cerf theory, tight and taut
immersions

[G. Panina]St. Petersburg Department of V.A.Steklov Institute of Mathematics
RAS, St. Petersburg<EMAIL_ADDRESS>[D. Siersma]Mathematisch
Instituut, Universiteit Utrecht, The<EMAIL_ADDRESS>MSC 34K18,
37G05 31 3 2023 https://doi.org/10.46298/cm.10840

##  1 Motivations

Our first motivation comes from the case when $M^{n-1}=\partial K$ is the
boundary of some convex body $K\subset\mathbb{R}^{n}$. It is conjectured since
long that there exists a point in the interior of $K$ which is the
intersection point of at least $2n$ normals from different points on the
boundary of $K$. The conjecture trivially holds for $n=2$. For $n=3$ it was
proven by E. Heil (see [3] and [2]) via geometrical methods and reproved by
Pardon via topological methods. The case $n=4$ was completed also by J. Pardon
in [9].

Recently Y. Martinez-Maure proved in [7] for $n=3,4$ that (under some mild
conditions) almost every normal through a boundary point to a smooth convex
body $K$ passes arbitrarily close to the set of points lying on normals
through at least six distinct points of $\partial K$. This result was reproved
by A. Grebennikov and G. Panina in [1]. Extending their method, we prove
related results for concurrent normals of immersed smooth compact manifolds.

Another motivation comes from tight embeddings of manifolds. A tight embedding
of $M^{m}$ is such that almost every linear function has exactly
$\beta(M^{m},\mathbb{Z}_{2})$ critical points, which is the minimal possible
amount.

In this paper we consider immersions of $m$-dimensional manifolds $M^{m}$ into
$\mathbb{R}^{n}$. Critical points of the squared distance function $d_{y}^{2}$
corresponds to normals through $y$. Linear functions can be viewed as the
limit to infinity of $d_{y}^{2}$.

It is also worth mentioning that there is a close relation between the number
of critical points of linear functions and the curvature of the embedding [5].

##  2 The geometry of the focal set

Consider an immersion $j:M^{m}\rightarrow\mathbb{R}^{n}$ of a smooth
$m$-dimensional connected manifold without boundary. In this paper we will
omit $j$ from the notation and write $M^{m}\subset\mathbb{R}^{n}$ instead.
However, we emphasize here that all constructions depend on the immersion.

######  Definition 2.1.

Given an immersed manifold $M^{m}$, the _normal_ $\mathcal{N}_{p}$ at a point
$p\in M^{m}$ is a line passing through $p$ and orthogonal to $M^{m}$ at the
point $p$.

The focal set of the immersed surface $M^{m}$ arises naturally in this paper.
We will use its definitions and properties borrowed from [8], [10], [11] and
[12] (the last two references also apply for immersions in spherical and
hyperbolic spaces). Following the standard approach, we make use of the
squared distance function to $M^{m}$:

$d^{2}_{y}:M^{m}\to\mathbb{R},\ \ d(x)=||x-y||^{2}.$

Given a point $y\in\mathbb{R}^{n}$, all the normals passing through $y$ can be
read off the function $d_{y}^{2}$:  A point $y$ lies on the normal
$\mathcal{N}_{p}$ for some $p\in M^{m}$ iff $p$ is a critical point of the
function $d_{y}^{2}$. So, the number of concurrent normals through a point $y$
is equal to the number of critical points of $d_{y}^{2}$.

By Sard’s theorem type arguments ([8], Theorem 6.6), $d_{y}^{2}$ is a Morse
function for almost all $y$.

######  Definition 2.2.

The bifurcation diagram of $d_{y}^{2}$ (cf. [13]) is called the _focal set_
$\mathcal{F}_{M}$ of $M^{m}$. In other words, the focal set coincides with the
set of points $y\in\mathbb{R}^{n}$ where the function $d^{2}_{y}$ is not a
Morse function (see [8]).

An equivalent definition (appearing in [8]) is the following: the focal set
$\mathcal{F}_{M}$ is the set of critical values of the evaluation map

$e:\mathcal{N(}M^{m})\rightarrow\mathbb{R}^{n}\;\;\;\;\;\;\;e(p,t\mathbf{n})=p+t\mathbf{n}$

from the normal bundle of $M^{m}$, where $p\in M^{m}$ and $\mathbf{n}$ is a
unit normal vector at $p$.

Note that $e$ is a map between manifolds of the same dimension. We will
discuss below the structure of its critical set $\mathcal{C}_{e}$.

The elements of $\mathcal{F}_{M}$ are called focal points. They generalize the
centers of principal curvatures of hypersurfaces. Generically the dimension of
$\mathcal{F}_{M}$ is $n-1$, but for instance, in the case of the round sphere
it degenerates to a point.

######  Definition 2.3.

For all $y\in\mathcal{N}_{p}$, the point $p$ is critical for $d^{2}_{y}$, and
for almost all $y\in\mathcal{N}_{p}$ the critical point $p$ is non-degenerate.
We say that a point $y\in\mathcal{N}_{p}$ is a $p$-focal point if $p$ is a
degenerate critical point of the function $d^{2}_{y}$.

The Morse index of $d^{2}_{y}$ at $p$ for a non-$p$-focal point
$y\in\mathcal{N}_{p}$ is equal to the number the $p$-focal points lying
between $p$ and $y$, counted with multiplicity. The multiplicity $\nu$ is
defined as the nullity of the Jacobian of $e$ at the point $(x,t\mathbf{n})$,
which equals to the nullity of the 2-jet of $d^{2}_{y}$ at $y=x+t\mathbf{n}$
[8].

Let $y=p+t\mathbf{n}$ be a point on $\mathcal{N}_{p}$. Once the normal vector
$\mathbf{n}$ is fixed, the set of $p$-focal points on the normal becomes
linearly ordered. We enumerate them as follows: $r_{j}$ is the $j$-th
$p$-focal point contained in $\\{t\geq 0\\}$ part of $\mathcal{N}_{p}$,
counting from the point $p$, and $r_{-j}$ is the $j$-th $p$-focal point
contained in $\\{t\leq 0\\}$ part, also counting from the point $p$, counted
with multiplicity.

We shall also consider the compactified normal line $\mathcal{N}_{p}$: adding
the point $\infty$ turns the normal to a circle. The $m$ points $\\{r_{i}\\}$
are indexed cyclically mod $m$ by numbers $1,\dots,m$, which fits with the
earlier defined notation: $r_{i}=r_{-m-1+i}$.

This ordering also yields sections of the normal bundle which stratify the
critical set $\mathcal{C}_{e}$. The regular points of $\mathcal{C}_{e}$
correspond to focal points with $\nu=1$, whose neighborhoods are smooth
codimension-$1$ submanifolds. The singular points correspond to focal points
of higher multiplicity. The singularities of the focal set consist not only of
the images of points with $\nu>1$ but also of self intersections and
singularities of the images of the points with $\nu=1$.

In the case $\nu=1$ it follows that $d^{2}_{y}$ has a singularity of corank 1
at $p$, so must be of type $A_{k}$ with $k\geq 2$. In the generic case this
type is $A_{2}$. Also, the Jacobian of the evaluation map $e$ has corank 1.
This means (see [6]) that in the generic case $e$ is a submersion with folds,
and $\mathcal{F}_{M}$ is locally the image of the fold set. It is also known
that the normal $\mathcal{N}_{p}$ at a $p$-focal points is tangent to the
focal set (which is a well known property for evolutes of curves); but if the
type is $A_{3}$ or higher then the focal set is not necessarily smooth (as is
known for the evolute).

The focal set $\mathcal{F}_{M}$ cuts the ambient space $\mathbb{R}^{n}$ into
chambers (that is, connected components of the complement of
$\mathcal{F}_{M}$). The type of the associated Morse functions $d^{2}_{y}$
depends only on the chamber containing $y$.

Transversal crossing of the focal hypersurface at its smooth $A_{2}$ point
amounts to a birth (or death) of two critical points of the function
$d_{y}^{2}$ whose indices are $i$ and $i-1$.

We end this section with the folowing definition:

######  Definition 2.4.

We say that the normal $\mathcal{N}_{p}$ is regular if

  * •

$\mathcal{N}_{p}$ does not intersect the singularities of $\mathcal{F}_{M}$,

  * •

$\mathcal{N}_{p}$ intersects the focal set transversally, except for the
$p$-focal points,

  * •

$d_{y}^{2}$ is of type $A_{2}$ at the point $p\in M^{m}$ for all non-$p$-focal
points $y\in\mathcal{N}_{p}\cap\mathcal{F}_{M}$,

  * •

there are exactly $m$ different $p$-focal points on $\mathcal{N}_{p}$.

The last condition excludes $p$-focal points at infinity (if the Gauss
curvature at $p$ is zero). For generic immersions almost every normal is
regular. Regularity implies that the focal set is a hypersurface close to the
intersections with the normal.

##  3 The concurrent normals theorem

Let us recall that Morse functions $f:M^{m}\rightarrow\mathbb{R}$ on a compact
manifold satisfy the Morse inequalities: The number of critical points of
index $i$ does not exceed the Betti number $\beta_{i}(M^{m},\mathbb{Z}_{2})$.
Therefore, the number of concurrent normals from a non-focal point $y$ is at
least the sum of Betti numbers
$\beta=\beta_{0}(M^{m},\mathbb{Z}_{2})+\dots+\beta_{m}(M^{m},\mathbb{Z}_{2})$.

######  Definition 3.1.

A point $y\notin\mathcal{F}_{M}$ is called an excess-k point if $y$ is an
intersection point of at least $\beta+k$ normals from different points on
$M^{m}$.

######  Definition 3.2.

A compact closed manifold $M^{m}$ is called $i$-trivial (for some $0<i<m$), if
the $i$-th Betti number vanishes: $\beta_{i}(M^{m},\mathbb{Z}_{2})=0$. In this
case, by Poincaré duality, we also have $\beta_{m-i}(M^{m},\mathbb{Z}_{2})=0$.

######  Theorem 3.3.

Let $M^{m}\subset\mathbb{R}^{n}$ be an immersed $C^{2}$-smooth compact
manifold. For any regular normal $\mathcal{N}_{p}$ holds:

  1. 1.

$\mathcal{N}_{p}$ contains an intersection point of at least $\beta+2$ normals
from different points on $M^{m}$.

  2. 2.

If $M^{m}$ is an $i$-trivial manifold, then $\mathcal{N}_{p}$ contains an
excess-4 point, i.e., the intersection of at least $\beta+4$ normals.

######  Remark 3.4.

One can localize the positions of excess-$4$ points: there exist excess-$4$
points on the segment $[r_{i}(p),r_{i+1}(p)]$, and also on the segment
$[r_{-i-1}(p),r_{-i}(p)]$, provided that $H_{i}(M^{m},\mathbb{Z}_{2})=0$
(here, we use our modulo $m$ notation for the indices). It is clear that
unless $i=\frac{m}{2}$, there are two such segments, since $\beta_{i}=0$
implies $\beta_{m-i}=0$. If $i=\frac{m}{2}$ there is a single interval.

######  Remark 3.5.

J. Pardon’s approach ([9]) works for any $m$-sphere, convex or not: Given an
immersion $j:S^{m}\rightarrow\mathbb{R}^{n}$, for any continuous
$J:B^{m+1}\rightarrow\mathbb{R}^{n}$ such that $J$ restricted to $\partial
B^{m+1}$ equals $j$, there exists an excess-$4$ point in $J(B^{m+1})$.

######  Remark 3.6.

Tight embeddings and immersions are especially interesting: see the first
reminder of section 4. In any case, Theorem 3.3 holds true for non-tight ones
as well.

### Proof of Theorem 3.3

For $y\notin\mathcal{F}_{M}$ we say the function $d_{y}^{2}$ has $q$ extra
critical points of index $i$ whenever the number of critical points of index
$i$ is at least $\beta_{i}+q$.

######  Lemma 3.7.

In a neighbourhood of the point $r_{\pm k}$ on the regular normal
$\mathcal{N}_{p}$ there is an extra critical point of index $k$ and an extra
critical point of index $k-1$.

######  Proof 3.8.

The normal $\mathcal{N}_{p}$ is tangent to the focal hypersurface at the point
$r_{k}$. While moving along the normal, the critical point $p$ persists, and
its Morse index changes at the point $r_{k}$ from $k-1$ to $k$. Since a
deformation of the $A_{2}$ singularity can have only $0$ or $2$ Morse points,
it follows that $\mathcal{N}_{p}$ stays locally in the same chamber, except at
the tangent point. At the tangent point $r_{k}$ it meets the closure of a
chamber with two fewer critical points, that is, of index $k$ and $k-1$.

Since each regular normal contains at least one $p$-focal point, the lemma
implies the statement 1 of the theorem.

For a regular normal $\mathcal{N}_{p}$, consider a point $y=p+t\mathbf{n}$
moving along $\mathcal{N}_{p}$, starting at the point $p$. We recall that
$\mathcal{N}_{p}$ is compactified by adding a point at $\infty$, so $y$ makes
a full turn and eventually returns to $p$.

The point $p$ is the first minimum point of $d^{2}_{y}$, (its Morse index is
zero, $\mu=0$), next after passing $r_{1}$ its Morse index turns to $1$, and
so on. That is, after passing through $r_{i}$ we have $\mu=i$. Passing through
infinity is (generically) not a bifurcation point, but it changes each Morse
index $\mu$ to $m-\mu$. In particular, minima and maxima exchange their roles.
After that, the Morse index changes also in a controlled way, that is, after
passing through $r_{-i}$ we get $\mu=1-i$.

Combining the above with Lemma 3.7, we get:

  1. 1.

$d^{2}_{y}$ depends smoothly on $t$;

  2. 2.

$d^{2}_{y}$ is a Morse function for each $y$ except for finitely many
bifurcation points;

  3. 3.

for a regular normal each of the bifurcation points is $A_{2}$ for $d^{2}_{y}$
and has one of the two types:

    1. (a)

A birth/death point: Transversal crossing of the focal hypersurface translates
to two critical points with some neighbouring indices $k$ and $k-1$ colliding
and disappearing, or conversely, two critical points with neighbouring indices
appearing.

    2. (b)

An index exchange point: A tangential point to the focal hypersurface
translates to two critical points with neighbouring indices $i$ and $i-1$
colliding at $r_{i}$. There arises a degenerate critical point of type $A_{2}$
which splits afterwards into two non-degenerate critical points with the same
indices $i$ and $i-1$. Index exchange points are exactly the $p$-focal points
$r_{i}$ and $r_{-i}$.

Now we prove statement 2 of the theorem. Let $H_{i}(M,\mathbb{Z}_{2})$= 0.
with $i\leq m/2$. Then either $r_{i}$ or $r_{-i}$ exists. Assume that $r_{i}$
exists, and further assume we have no excess-$4$ points on the segment
$[r_{i},r_{i+1}]$. The point $r_{i}$ is an index exchange point and by Lemma
3.7 the function $d_{y}^{2}$ has exactly one extra critical point of index $i$
and exactly one extra critical point of index $i-1$ around $r_{i}$. For the
same reason there are two extra critical points of indices $i$ and $i+1$
around $r_{i+1}$.

Assume that $\beta+2$ is the maximal number of critical points on the segment
$[r_{i},r_{i+1}]$. The (unique!) critical point of index $i$ is the point $p$
and it is not allowed to bifurcate. Indeed, its Morse index persists on
$[r_{i},r_{i+1}]$. The extra critical point of index $i-1$ does not bifurcate
since no partner for an $A_{2}$-bifurcation is available. The same holds
around the point $r_{i+1}$ for the extra critical point of index $i+1$.

Since a contradiction arises from having two extra critical points of indices
$i-1$ and $i+1$, there exists at least one excess-$4$ point on the interval
$[r_{i},r_{i+1}]$. We note that the segment $[r_{i},r_{i+1}]$ might contain
infinity, but this fact poses no complications, since passing through $\infty$
maintains the number of critical points but inverts their indices.

##  4 Remarks

### A reminder on tight immersions

Given an immersed manifold $M^{m}$, the limit to infinity of the quadratic
distance function $d_{y}^{2}$ along a normal with direction $\mathbf{n}$ is
the linear function $l_{\mathbf{n}}:M^{m}\to\mathbb{R}$ defined by
$l_{\mathbf{n}}(x)=\langle x,\mathbf{n}\rangle$. The functions $d_{y}^{2}$ and
$l_{\mathbf{n}}$ have the same number of critical points with the same Morse
indices when $y$ is close enough to infinity. An immersion $M^{m}$ in
$\mathbb{R}^{n}$ is called tight if the number of critical points of
$l_{\mathbf{n}}$ equals $\beta(M^{m},\mathbb{Z}_{2})$ for almost all
$\mathbf{n}$. Tightness is a generalization of convexity; a tight embedding of
the $(n-1)$-sphere as a hypersurface is necessarily convex. Tight immersions,
including the relation to total absolute curvature have been studied
intensively by Chern-Lashoff, Kuiper, Banchoff and Kuehnel. See e.g. [11, 12,
4, 5].

Some useful examples: There exist tight immersions in $\mathbb{R}^{3}$ for all
oriented surfaces and non-oriented surfaces with Euler characteristic smaller
than $-1$. The projective plane, the Klein bottle and the projective plane
with one handle cannot be tightly immersed in $\mathbb{R}^{3}$. Examples of
$4$-dimensional $i$-trivial manifolds with (tight) embedding in
$\mathbb{R}^{5}$ are $S^{4}$, $S^{2}\times S^{2}$ and their connected sums
[4].

### On non-regular normals

For generic immersions there is a dense set of regular normals. Non-regular
normals are, for instance, those based at umbilical points and based at points
with zero Gaussian curvature, where one of the centers of curvature is at
infinity. But there are many cases where regular normals do not occur. We
mention here the round sphere and cylinder. This happens also in the case
where $d^{2}_{y}$ has exactly $\beta$ critical points for a dense set of $y$.
Such immersions are called taut immersions, which are very special, see e.g.
[11]. Taut is much more restrictive than tight. Their focal sets are very
degenerate.

If parts of the focal set have dimension $\leq n-2$, then we will get an
infinite number of normals from these focal points. To be more precise:
Consider the evaluation map $e$ from one of the $n-1$ dimensional strata of
$\mathcal{C}_{e}$. If this map reduces dimension, then for an image point $y$
the quadratic distance $d^{2}_{y}$ has non-isolated singularities.

Note also that for certain non-regular normals the proof of theorem 3.3 still
applies, e.g. when $M$ is $i$-trivial and the focal points $r_{i}$ and
$r_{i+1}$ have multiplicity $\nu=1$.

### Tubes over an immersed manifold

We describe below a higher excess estimate for tubes. Given an immersion
$M^{m}\subset\mathbb{R}^{n}$, the tube of $M^{m}$ with radius $r>0$ is defined
as the restriction of the evaluation map $e$ to the sphere bundle $S_{r}(M)$,
consisting of normal vectors of length $r$. For sufficiently small $r$ we get
an immersion $S_{r}(M)\subset\mathbb{R}^{n}$.

######  Proposition 4.1.

Let $y\notin\mathcal{F}_{M}\cup M^{m}$ be an excess-$k$ point for $M^{m}$.
Then $y$ is an excess-$2k$ point for $S_{r}(M)$.

######  Proof 4.2.

Any normal $\mathcal{N}$ from a point $y\in\mathbb{R}^{n}$ to $M^{m}$ is also
a normal to $S_{r}(M)$. A single intersection point $p\in M^{m}$ will give
precisely two intersection points $p_{1},p_{2}$ with $S_{r}(M)$. The normal
$\mathcal{N}$ is a normal for the points $p_{1},p_{2}$, so the total number of
critical points of $d^{2}_{y}$ doubles. The observation
$\beta(S_{r}(M),\mathbb{Z}_{2})=2\beta(M,\mathbb{Z}_{2})$ from [11] completes
the proof.

As a corollary: taut immersions give taut tubes (see [11]). Note that points
of $M$ produce non-isolated singularities for $d^{2}_{y}$.

For tubes, we can give more information about the locations and indices of the
excess points than in the proof of Theorem 3.3. The focal set of a tube
$S_{r}(M)$ consists of two pieces: $\mathcal{F}_{M}\cup M^{m}$ ([11], Theorem
3.3). The focus points on $M^{m}$ all have multiplicity $\nu=n-m$. For
$n-m\geq 2$ no normal to the tube can be regular. We can still compute the
index of $d_{y}^{2}$ at $p_{i}$ by counting the $p$-focal points with
multiplicity on the coinciding normals $\mathcal{N}_{p_{1}}$ and
$\mathcal{N}_{p_{2}}$. By traveling over the two normals as in the proof of
Theorem 3.3 we see that the excess doubles. This happens in the same intervals
as for $M^{m}$.

### Acknowledgements

The authors acknowledge useful discussions with George Khimshiashvili and
hospitality of CIRM, Luminy, where this research was completed in framework of
”Research in Pairs” program in November, 2022.

## References

  * [1] G. P. A. Grebennikov.  A note on the concurrent normal conjecture.  Acta Mathematica Hungarica, 167:529–532, 2022.
  * [2] E. Heil.  Existenz eines 6-normalenpunktes in einem konvexen körper.  Arch. Math. (Basel), 32(4):412–416, 1979.
  * [3] E. Heil.  Concurrent normals and critical points under weak smoothness assumptions.  Annals of the New York Academy of Sciences, 440(1):170–178, 1985\.
  * [4] W. Kühnel.  Tight embeddings of simply connected 4-manifolds.  Documenta Mathematica, 9:401–412, 2004.
  * [5] N. H. Kuiper.  Minimal total absolute curvature for immersions.  Invent. Math., 10:209–238, 1979.
  * [6] V. G. M. Golubitski.  Stable mappings and their singularities.  In Graduate Texts in Mathematics. Springer, 1973.
  * [7] Y. Martinez-Maure.  On the concurrent normals conjecture for convex bodies, 2021.
  * [8] J. Milnor.  Morse theory.  Princeton University Press, 1963.
  * [9] J. Pardon.  Concurrent normals to convex bodies and spaces of morse functions.  Math. Ann., 352(1):55–71, 2012.
  * [10] I. R. Porteous.  Geometric Differentiation for the intellegence of curves and surfaces.  Cambridge University Press, 1994.
  * [11] R. T.E.Cecil.  Tight and Taut Immersions of Manifolds.  Pitman, 1985.
  * [12] R. T.E.Cecil.  Geometry of Hypersurfaces.  Springer, 2015.
  * [13] S.-Z. V.Arnol’d, A.Varchenko.  Singularities of differentiable maps I and II.  Birkhäuser, 1985.

January 21, 2023April 16, 2023Jacob Mostovoy and Sergei Chmutov