\name: Efficient and Accurate Verification for Risk-Avoidance Routing in LEO Satellite Networks

Today’s LSNs like SpaceX’s Starlink [2] consist of hundreds to thousands of LEO satellites that work as “routers in space”, together with many geo-distributed ground stations connecting satellites and terrestrial network infrastructures. Satellites communicate with ground entities (\eg ground stations or satellite terminals) via ground-satellite radio links (GSL). Besides, many satellite constellations (\eg Starlink and Kuiper) leverage high-speed laser inter-satellite links (ISLs) for inter-satellite networking and communication. As visualized in [24], because satellites move at a high velocity in various orbital directions over the Earth, the entire LSN experiences frequent topology changes, especially in space-ground connections. LSN traffic between two terrestrial nodes (\eg from a Starlink’s satellite terminal to a remote ground station) is forwarded by a network path constructed by uplink/downlink and ISLs. To deal with the unique LSN topology fluctuation, many recent works have proposed space routing mechanisms (\eg [20, 21]) to dynamically build and maintain paths for any two terrestrial nodes connected to the LSN.

As plotted in Fig. 1, because satellites move globally, they might enter an uncontrolled risk area, posing routing security threats in LSNs. In this paper, we define a “risk area” as a geographical region where malicious attackers may exist there and launch the following attacks on satellites above the area:

• •

  Information stealing. Attackers in the risk area can eavesdrop on traffic and extract or speculate private data [9]. As shown in Fig. 1, assume traffic from the satellite terminal is expected to be forwarded to the ground station by a planned network path marked by the solid arrows, attackers in risk areas can eavesdrop on traffic forwarded from S7 to S9.

• •

  Traffic hijacking. More powerful attackers in a risk area can hijack [10, 11, 12] the route and cause path inconsistency. They propagate error routing advertisements to allure surrounding satellites to forward packets to them and redirect traffic to specific nodes for censorships, or other man-in-the-middle attacks like packet injection, modification, and counterfeit. In the example illustrated in Fig. 1, the attacker in the risk area may modify the planned path to S7$\rightarrow$S4$\rightarrow$S5$\rightarrow$S9.

Therefore, to avoid the above risks, it should be essential for satellite network operators (SNOs) to: (i) apply avoidance policies to force their traffic to bypass potential risk areas, and more importantly, (ii) verify that the actual paths are consistent to the planned avoidance policies in practice.

Over the past decade, the network community has had a body of efforts working on network path verification. In particular, existing path verification efforts can be classified into two main categories: crypto-based and delay-based approaches. Crypto-based path verification. One classic path verification approach is to embed the planned path (\eg a sequence of nodes that build the network path) into the header of each packet. Then intermediate nodes authenticate and update related fields before sending to the next node [13, 14, 15]. These approaches have three limitations in LSNs. First, each intermediate node needs to perform cryptographic operations like calculating MACs hop by hop, which involves high computation overhead that could be unaffordable for resource-constrained satellites. Second, the increased length of the verification header also leads to extra packet header overhead, resulting in goodput ratio reduction (as will be analyzed in detail in §VI). Third, per-hop authentication inevitably involves additional processing delay on each node. Note that the high mobility of LEO satellites incurs frequent path changes [25, 22, 20], if the packet processing delay is too high, the pre-calculated path might be invalid on the route. Although some recent works like PPV [26] and MASK [27] propose probabilistic authentication instead of verifying every packet hop by hop, the computation overhead can be still high when the traffic volume is large. Delay-based path verification. Alibi Routing [16] proposes a new path verification approach, exploiting the key idea that a detour from the planned path to any node in the risk area will breach the maintained delay by incurring significant extra delay. To verify whether a network path from a source ($Src$) to its destination ($Dst$) passes through the risk area, Alibi Routing pre-computes a target area that is far away from the risk area where possible verifiable relays (called alibis) are located. It enforces that the path from $Src$ to $Dst$ must pass through the alibis. Because the relay is very far from the risk area, if the $Src\rightarrow Dst$ path passes through the risk area, the observed end-to-end delay should be significantly higher than the maintained value. However, these approaches are based on a fundamental assumption that the delay between two terrestrial nodes has a linear relationship with their great-circle distance. Although this assumption exists in many scenarios in today’s terrestrial Internet [19], it is not applicable in LSNs with highly dynamic topology. An increase in path delay may not necessarily be caused by traversing the risk area but path changes due to topology fluctuation. We conduct a quantitative analysis to demonstrate how the unique topology fluctuations in LSNs affect the verification accuracy of existing delay-based approaches. Our analysis is based on the real Starlink constellation information [2] and an LSN simulation based on StarryNet [23] (details will be illustrated in §VI). We build a virtual LSN consisting of 1584 satellites with 72 orbits and 22 satellites per orbit (Starlink Phase 1, Shell 1) and 165 geo-distributed ground stations [28] around the world. We simulate about 2000 city pairs communicating over the LSN and use the shortest path routing upon the +Grid topology, \ie a satellite connects two neighboring satellites in the same orbit and two in the adjacent orbits [20].

For each communication pair ($Src$, $Dst$) and a given risk area, \nameaccomplishes the verification as follows. (1) Dynamic relay selection. \namefirst calculates a time-varying relay set which includes all relays for ($Src$, $Dst$) at different time slots. Then it estimates the segment detour delay threshold which is used to calculate the segment delay upper bound based on the relay sequence. All the information is computed based on the predictable satellite trajectory and dynamic LSN topology. Once decided, the SNO operation center delivers the results to $Src$. (2) Intra-segment state probing. If a path changes or a new session begins, end users, relays and SNO negotiate session keys [14] which is out of our scope in secure channels [32]. After that, each relay (including $sat_{d}$) periodically (\eg tens of seconds) sends a probing packet to its previous relay to probe delay of the current segment. To ensure that probing packets are not tampered with, all nodes on a segment path authenticate the probing packet with adjacent shared symmetric keys [16]. (3) Authentication fields initiation. Before a packet’s departure, $Src$ inserts the corrected sending timestamp, hash value, and relay authentication fields $AUTH$ in the packet header. (4) Relay-based segment verification. Network nodes forward the packets according to the planned path. When a relay receives packets, it verifies the segment path based on its probing ground truth and detour threshold. If packets do not traverse the risk area, the relay computes a MAC value and inserts it with the timestamp to update its part in $AUTH$ field. (5) Destination verification. After receiving a packet, $Dst$ verifies the packet’s source (out of our scope), $AUTH$ fields updated by relays, and the last segment path to determine whether the packet bypasses the risk area.

To accomplish efficient and accurate verification, \nameneeds to solve the following LSN-specific challenges. Appropriate relay selection under LEO dynamics. Considering the high dynamics in LSNs, correctly and timely selecting verifiable relays away from the risk area while not involving too much additional delay at a global scale is challenging. Specifically, we formulate the Avoidance-Verifiable Dynamic Relay Selection (AVDRS) problem in LSNs, based on which we further design an efficient solution. Unpredictable delay jitters. Only exploiting the period probing delay ground truth as an upper bound to verify whether a packet has gone through the risk area is too strict. It’s impossible that the real delays are equal to the probing delays exactly. It’s hard to distinguish whether an observed micro delay increase is caused by slight delay jitters or detours which may mislead the segment delay-based verification. In the next section, we introduce the details of \nameand describe how \nameaddresses these challenges.

Before communication begins, $Src$ and SNO exchange Veri infos including the detour threshold list $\Delta$, and relays during a future period. Every time a connection begins or relays change (inspected by querying its local cache in each time slot), $Src$, $Dst$, and relays negotiate session keys and achieve the path authorization [14] (out of our scope) through secure channels between them and SNO [32]. Then, when sending a packet, $Src$ first sends a probe to test the current access delay $D_{access}$ to eliminate the error brought by the first hop. Next, $Src$ records the corrected sending timestamp ${ts}_{0}={ts}_{send}+D_{access}+\alpha$ ($\alpha$ is processing time) and calculates the truncation of the hash value $HASH=H(Payload||PATH||\Delta^{\,ts_{0}}||ts_{0}||\mathcal{RE}^{\,ts_{0}})[0:l]$, where $[0:l]$ is the truncation of the lowest $l$B of the data to improve goodput [15, 27]. Then $Src$ constructs the reserved $AUTH$ chain, makes a final packet source authorization and sends $pkt$. Each relay’s $AUTH$ field is shown in Fig. 7 where $l=4$, including relay’s ID $r_{i}$, segment detour threshold $\delta_{ij}$, timestamp $ts_{i}$ when sending out the packet, and its MAC authentication value.

When receiving a packet, the satellite should determine if it is a relay by checking the $AUTH$ chain. If not, it just forwards it without doing any operations. Otherwise, after negotiating the session keys and obtaining the segment path and relay sequence, periodically, the relay probes with a nonce to its previous relay for some link states like queuing and processing delay. The probing reply packets must have been authenticated hop by hop on this segment path through the neighboring shared symmetric keys [16, 26]. Then, the relay obtains the probing delay $dt_{r_{i-1}r_{i}}$ of the segment path. Similarly, $sat_{d}$ announces the last segment delay to $Dst$. Next, upon receiving normal communication packets, the relay $r_{i}$ just checks if its previous relay $r_{i-1}$ has updated ${AUTH}_{i-1}$ but ignores its validation as \nameoffloads the step to $Dst$. Then, it determines whether the real delay of this segment path has exceeded the upper bound, \ie

If not, it calculates ${MAC}_{K_{r_{i}}}(HASH||ts_{i}||r_{i})[0:l]$ and inserts it into the packet together with $ts_{i}$ and sends the packet. If all the intermediate relays have updated the related fields and the packet is forwarded to ${sat}_{d}$, ${sat}_{d}$ inserts the time $ts_{d}$ when it receives the packet and forwards to $Dst$.

When $Dst$ receives the packet, it verifies the packet in the following steps: (i) it first authenticates the packet’s source validation (this is out of our scope); (ii) after that, it calculates the hash value in the same way as $Src$ to verify if the packet has been tampered; (iii) then it authenticates the MAC chain of relays by re-computing MACs with their shared session keys to verify that the real path has indeed gone through these relays and passed all these relay’s verifications; (iv) lastly, $Dst$ authenticates the last segment path in the same way as relay‘s. If all the four conditions are satisfied, $Dst$ accepts it and considers it not traversing the $RA$.

We set a traffic hijacking scene where packets are forwarded to the risk nodes to see if the prolonged detour delay can be detected. After running our experiments on StarryNet for several hours, \name’s verification accuracy reaches $100\%$ in the cases of different numbers of relays. The real detour delay is larger than the pre-set upper bound, as such, no packet that enters the risk area is considered as not traversing the risk area. In the simulation testbed, Alibi produces $38.7\%$ and $27.3\%$ average FP and FN ratios when the risk area is Egypt. Such poor accuracy of Alibi results from frequent variation of the GSLs between satellites and static relays.

Selecting relays far away from the risk area ensures better verification accuracy but incurs larger delay inflation. So we set a configurable variable $\theta$ in Constraint 3 that depicts the size of $NLRP$ (\ie the distance between the $NLRP$ borders and the marginal risk satellites) to make a trade-off between verification accuracy and end-to-end delay. As shown in Fig. 8, a larger $NLRP$ does incur a longer end-to-end delay, which holds true in both constellations as shown in Table I. However, from a global perspective, the average extra delay of \nameis within a reasonable range compared with Alibi. The maximum delay inflation of Alibi reaches $156.54\%$ and $175.49\%$ in two risk countries respectively when $f=0.5$. Besides, limited by the small number and uneven distribution of ground relays, Alibi cannot always find verifiable relays. When $f$ is larger, there is a high possibility that no fixed relays will be found. From our analysis, only 112 of the 197 communication pairs can be assigned a fixed relay when the risk area is North Korea. However, \namecan choose global satellites as relays to verify a path only if the users’ access satellites are not located inside the $NLRP$. On top of that, Fig. 9 plots the detour delay thresholds under different $\theta$s defined in Constraint 3. \nameachieves a delay buffer from tens to hundreds of milliseconds. This additional buffer against unpredictable delay jitters functions better when the $NLRP$ is larger. When avoiding Egypt, the detour threshold increases as the $\theta$ increases. However, there is no explicit detour threshold increase when avoiding North Korea. For example, the average detour thresholds of the three cases of different $\theta$s in Starlink are all about 75ms, which means when the risk area is small, setting a smaller $\theta$ may be enough to achieve a high verification accuracy.

We analyze the overheads in two aspects: communication overhead and computation overhead and compare \namewith three crypto-based approaches ICING [13], OPT [14], and EPIC [15]. The verification header length of the three methods increases as the path length grows because they verify the path hop by hop. Communication overhead. Our \namefield length is at most $48B$ no matter how many hops $N$ a route has as there are two relays at most (one relay consumes $16B$ fields) as shown in Table II. To compare them in a meaningful way, we use a $40B$ IPv6 header plus the security-related fields. As shown in Fig. 10, the longer the path is, the more communication overhead the hop-by-hop methods incur especially ICING. Since the constellation scale is much larger than a single AS in the terrestrial network, it’s normal to transmit traffic on a path with tens of hops in LSNs. Fig. 10 plots the theoretically maximum goodput ratios (GR) under different hops. \nameachieves 110.16%, 43.53%, and 11.33% higher GRs than ICING, OPT, and EPIC respectively in the case of 30 hops, 1024B payload, and the number of relays $\sigma=2$.

Besides, \nameis not a hop-by-hop verification method, incurring only a little verification delay caused by at most two cryptographic operations. We compare \nameto EPIC which also has one MAC operation per hop. As shown in Table III, \name’s verification delay is 97.2% less than EPIC when the path has 35 hops.

We analyze the RTTs when a path loads different numbers of flows in parallel obtained from StarryNet as shown in Fig. 13. When the number of flows is small, \namenearly incurs no verification delays. As the number of flows grows, \nameincurs more verification delay, especially when $\sigma=2$. The average verification delay of processing between 700 and 1000 flows in parallel is 86ms, 92ms, and 134ms in three $\sigma$s respectively. Hence, SNOs should consider setting a larger $NLRP$ when the number of flows is large. Next, we analyze the number of required relays. If the number is small, the key negotiation overhead is low. \namewill choose a certain number $\sigma$ of relays for a communication pair $cp$ at a certain time. The proportion of these time slots when selecting $\sigma$ relays is $RAR_{\sigma}^{\,cp}$. For example, \nameselects a relay for a pair $cp$ for 600s during the past 1000s, so $RAR_{1}^{\,cp}=600/1000=0.6$. Fig. 13 plots the boxplot of $RAR_{\sigma}$s of 197 global pairs in Starlink when avoiding Egypt. The average $RAR_{2}$ of all these pairs when $\theta=1$ is only 29.6%.