Session A2: GNSS Security: Interference, Jamming, and Spoofing 1

A Low Complexity Implementation of the MLE-Based GNSS Anti-Spoofing Method
Xiaoxuan Xu, Hong Li, Mingquan Lu, Tsinghua University
Location: Beacon A

The threat of spoofing attacks to Global Navigation Satellite System (GNSS) is increasingly severe. Recently, a spoofing detection method based on Maximum Likelihood Estimation (MLE) has been proposed, called MLE-based GNSS anti-spoofing method(Wang et al., 2017). The method is based on Direct Position Estimation (DPE), which is a new positioning method that estimates position results by comparing the consistency between the signal replica based on position, velocity and time (PVT) estimation results and the received signal(Closas, Fernndez-Prades, & Fernndez-Rubio, 2007). The MLE-based GNSS anti-spoofing method uses DPE twice. The first DPE is used to reconstruct signal and eliminate it from the received signal, then the second DPE is performed on the residual signal. The detection statistics and PVT estimation results of the two DPEs are used to detect spoofing signals and estimate the results of false PVT and authentic PVT(Morales-Ferre et al., 2019). The MLE-based GNSS anti-spoofing method can be used on the single-antenna receiver(Zhou et al., 2023) and does not need additional network infrastructure(Tedeschi et al., 2022). The main advantage of the method is that it jointly processes all satellite signals in sight. As long as the difference between the spoofing PVT and the authentic PVT is beyond a certain range, the method works regardless of the spoofing strategy(Wang et al., 2017).
However, the main drawback of the MLE-based GNSS anti-spoofing method is its high computational complexity, which leads the method difficult to be implemented in practical applications. The substantial computational complexity encountered primarily stems from DPE, which can be attributed to two pivotal factors. One is that DPE requires multiple calculations and updates of large-scale matrices due to the high sampling rate of satellite signals. The other reason is that each DPE requires an optimal value search for the cost function, which is an eight dimensional nonlinear function of receiver position, clock bias, velocity, and clock drift. The high search dimension means that it requires eight loops using grid search, unacceptable in practical applications.
There have been already various methods to reduce the computational complexity of DPE. FFT is mainly used to implement correlation to reduce the time consumption of a single search(Closas & Gusi-Amigo, 2017). Many other methods are dedicated to reducing the number of searches. Because the cost function is an implicit function of the position and clock bias result, the gradient cannot be directly solved. Some methods use differential approximation gradient to apply gradient descent method to reduce complexity, but it is sensitive to initial value selection and easy to converge to local optimal values(Liu et al., 2013). The Spatial Alternating Generalized Expectation (SAGE) maximization algorithm searches only one dimension at a time iteratively while fixing the values of other dimensions until all dimensions reach the optimal value. This method has slow convergence speed(Closas, Fernandez-Prades, & Fernandez-Rubio, 2007). In addition, some methods set a threshold to average all PVT results, which are corresponding to the cost function exceeding the threshold, to obtain the final result, instead of searching the maximum value(Bradley et al., 2010). Another more effective method to reduce the number of searches is the low duty cycle DPE technology, which divides DPE implementation into two parts: measurement update and time update. Measurement update is the traditional DPE method, which is time-consuming. The time update part is to use Newton’s laws to estimate the PVT of the receiver at the next time and use ephemeris to predict the PVT results of satellites. This part has a short time consumption. The low duty cycle technology has been experimentally verified to achieve good positioning performance even when the duty-cycling is as low as 2%(Ng & Gao, 2016).
However, all these methods above assume that there are only authentic signals in the received signals, which means the uncertainty range of PVT initial values provided by traditional receiver is relatively small and therefore the search space is always small. When the receiver is spoofed, the PVT of spoofing signals is always significantly different from that of authentic signals, which means the uncertainty range of PVT initial values provided by traditional receivers may be significantly large. It leads to an expansion of the search space and further increases the computational complexity of the above methods, making it hard for real-time implementation of the MLE spoofing detection.
The method proposed in this paper aimed at decreasing the computational complexity of MLE-based GNSS anti-spoofing method when the uncertainty rang e of the initial PVT results is large. To construct the signal replica, the code phase, which mainly depends on the transmission delay, and Doppler frequency should be calculated correctly. When the PVT results of the satellites are known and atmospheric delay is eliminated, this problem is equivalent to an eight dimensional nonlinear function optimization problem for receiver PVT results. However, the transmission delay of the signal from the satellites to the receiver is only related to the position and clock bias of the receiver. The Doppler frequency is related to the position, velocity, and clock drift of the receiver and is mainly affected by the receiver velocity and clock drift. Therefore, the core strategy of the proposed method is to reduce the eight dimensional search to two four-dimensional searches, delay search and Doppler search, based on physical meaning. Delay search only targets the receiver position and clock bias search, while Doppler search only targets the receiver velocity and clock drift. When one search is in progress, the PVT parameters of the other search are fixed. Actually, there are two coupling terms as follows that will change simultaneously during the delay search and Doppler frequency search:
• Coupling term 1: the portion of the carrier Doppler frequency caused by changes in the receiver position. This portion will change in delay search.
• Coupling term 2: the portion of the code phase caused by code Doppler frequency. This portion will change in Doppler frequency search.
To verify the rationality of the decomposition, we calculated the coupling term. When the position change is less than 10km, the coupling term 1 is less than 10Hz and when the receiver speed is less than 180km/h,the coupling 2 is about 10?4 chips. Therefore, When the uncertainty of the initial PVT value is within the above range, the coupling terms can be regarded as constants. Then the proposed method achieves dimension reduction of the problem. Furthermore, because the cost function is more sensitive to code phase than Doppler frequency, we should operate delay search first and optimize the two searches separately:
• For delay search, the Particle Swarm Optimization(PSO) algorithm (Kennedy & Eberhart, 1995) is used to find the maximum of the MLE cost function. The main advantages of PSO are that it is easy to be implemented and is not sensitive to initial values. Its time complexity is a little higher than gradient descent methods, but much lower than grid search methods, while its global search capability is higher than gradient descent methods. To further decrease the computational complexity, we use FFT to establish a pre-correlated table and therefore transform the search operations into more efficient table lookup operations without significant loss of estimation accuracy.
• For Doppler frequency search, the Jacobian matrix of the cost function for receiver speed and clock drift can be directly solved, but solving the Hessian matrix is difficult. So Broyden-Fletcher-Goldfarb-Shanno (BFGS) method(Wu et al., 2019) is applied to find the maximum of the MLE cost function and estimate the velocity and clock drift of the receiver. BFGS iteratively approximates the Hessian matrix through Jacobian matrix, thereby enabling fast implementation of Doppler frequency search through gradient descent.
At the same time, we conducted simulation to study the impact of Doppler frequency uncertainty on delay search. Simulation is based on the authentic code phase and Doppler frequency of single satellite signal, with the code phase shifted by ± 1 chip at 0.1 chip intervals and the Doppler frequency shifted by ± 1kHz at 2Hz intervals respectively. Simulation results show that estimation uncertainty of code phase can still be maintained within 0.1 chips when uncertainty of Doppler frequency is within ± 500Hz. As for Doppler frequency search, we also conducted simulation to study the impact of code phase uncertainty and initial Doppler frequency uncertainty on Doppler frequency search. We find that when the code phase result of delay search is accurate, BFGS method allows for an uncertainty of approximately 140Hz, i.e. 95km/h if calculated based on velocity, between the initial Doppler frequency and the authentic value of the Doppler frequency. If the uncertainty of the code phase result is 0.3 chips, the range will be reduced to 70Hz, i.e. 48km/h if calculated based on velocity.
Besides, we also conducted practical experiments on two scenarios of timing spoofing attack and position spoofing attack, and set up two special spoofing strategies: full channel spoofing attack and non repetitive channel spoofing attack. The effectiveness of the proposed method is verified by detection success rate and detection time. At the same time, the gain of prior knowledge in reducing computational complexity was also studied through experiments. In the scenario of timing spoofing, we use full channel spoofing attack. In the scenario of position spoofing, non repetitive channel spoofing attack is chosen. The experimental results are shown below:
• As for the results of timing spoofing scenario, the success rate of detection using grid search is 100% but the average detection time is 163.28s. Using the proposed method, the success rate of detection is 85%. However, the average detection time drops greatly down to 3.13s. If we use the prior knowledge, which means the position and velocity of the receiver are known and we only need to conduct 2D search, the success rate is up to 97% and the average detection time drops lower to 1.82s.
• As for the results of position spoofing scenario, the success rate of detection using grid search is also 100% but the average detection time is up to 2847.1s, which is too long to detect spoofing. Using the proposed method, the success rate of detection is 81% and the average detection time drops down to 11.13s. If we use the prior knowledge, which means the velocity of the receiver is known and we only need to conduct 5D search, the success rate is up to 85% and the average detection time drops lower to 9.68s.
The results show that the proposed method can efficiently achieve spoofing detection and its time consumption is greatly reduced. The success rate of the proposed method is less than 100% because the PSO algorithm has a small probability of falling into local optima, but the success rate still meets requirements. Prior knowledge further reduces the search dimension by providing a part of PVT information, thereby reducing computational complexity and improving detection success rate. Besides, we conducted supplementary experiments to explore the factors that affect the detection performance and time consumption of the proposed method, providing guidance for its practical application in different scenarios. We find that the length of the observed signal and the number of particles are the main influencing factors. The number of particles affects the global convergence of PSO algorithm. The more particles there are, the stronger the global convergence of PSO is and the higher the detection success rate is, but it also linearly increases the detection time. Increasing the length of the observation signal can improve the detection success rate by increasing the signal-to-noise ratio gain brought by coherent integration without significantly increasing the detection time, but it will increase the spatial complexity.
In summary, the contribution of this article can be summarized as follows:
• To solve the problem of large PVT initial values uncertainty in spoofing scenario, a new low complexity implementation method is proposed to address the problem of high computational complexity in the MLE-based GNSS anti-spoofing method. Based on the physical meaning, we reduce the eight dimensional optimization problem to two four-dimensional optimization problems, namely delay search and Doppler frequency search, and optimize them separately. The proposed method significantly reduces the computational complexity while maintaining a high detection success rate.
• The proposed method can also be used to reduce the computational complexity of DPE in the scenario without spoofing. When the uncertainty of the initial PVT value of is relatively small, PSO and BFGS methods can converge to the global optimum value more quickly, and the time consumption will be shorter. When the initial uncertainty of the receiver PVT is relatively large, similar to the spoofing scenario, the proposed method can also greatly reduce the computational complexity and therefore help improve the robustness of DPE.
• Practical experiments are conducted to demonstrate the effectiveness of the proposed method under different spoofing strategies. And it has been verified that the proposed method can greatly reduce the computational complexity of the the MLE-based GNSS anti-spoofing method. Furthermore, we explored the main factors that affect the detection performance: the prior knowledge, the length of the observed signal and the number of particles, which will help promote widespread application of the MLE-based GNSS anti-spoofing method in the future.
REFERENCE
Bradley, B. K., Axelrad, P., Donna, J., & Mohiuddin, S. (2010). Performance analysis of collective detection of weak gps signals.
Proceedings of the 23rd International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS 2010), 3041–3053.
Closas, P., Fernandez-Prades, C., & Fernandez-Rubio, J. A. (2007). Ml estimation of position in a gnss receiver using the sage algorithm. 2007 IEEE International Conference on Acoustics, Speech and Signal Processing-ICASSP’07, 3, III–1045.
Closas, P., Fernndez-Prades, C., & Fernndez-Rubio, J. A. (2007). Maximum likelihood estimation of position in gnss. IEEE Signal Processing Letters, 14(5), 359–362.
Closas, P., & Gusi-Amigo, A. (2017). Direct position estimation of gnss receivers: Analyzing main results, architectures, enhancements, and challenges. IEEE Signal Processing Magazine, 34(5), 72–84.
Daniel, O., Lohan, E.-S., & Nurmi, J. (2015). Relaxed direct position estimation as strategy for open-loop gnss receivers. 2015 International Conference on Localization and GNSS (ICL-GNSS), 1–7.
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN’95-international conference on neural networks, 4, 1942–1948.
Liu, J., Cui, X., Lu, M., & Feng, Z. (2013). Direct position tracking loop based on linearised signal model for global navigation satellite system receivers. IET Radar, Sonar & Navigation, 7(7), 789–799.
Morales-Ferre,R., Richter,P., Falletti,E., DeLa Fuente,A., & Lohan,E. S. (2019). A survey on coping with intentional interference in satellite navigation for manned and unmanned aircraft. IEEE Communications Surveys & Tutorials, 22(1), 249–291.
Ng, Y., & Gao, G. X. (2016). Computationally efficient direct position estimation via low duty-cycling. Proceedings of the 29th International Technical Meeting of the Satellite Division of The Institute of Navigation (IONGNSS+ 2016), 86–91.
Tedeschi, P., Sciancalepore, S., & Di Pietro, R. (2022). Satellite-based communications security: A survey of threats, solutions, and research challenges. Computer Networks, 216, 109246.
Wang, F., Li, H., & Lu, M. (2017). Gnss spoofing detection and mitigation based on maximum likelihood estimation. Sensors, 17(7), 1532.
Wu, G., Zhang, M., & Guo, F. (2019). High-resolution direct position determination based on eigenspace using a single moving ula. Signal, Image and Video Processing, 13, 887–894.
Zhou, W., Lv, Z., Wu, W., Shang, X., & Ke, Y. (2023). Anti-spoofing technique based on vector tracking loop. IEEE Transactions on Instrumentation and Measurement, 72, 1–16.