A GNSS Anti-Spoofing Technique Based on the Spatial Distribution Characteristic of the Residual Vectors

In this section, the main idea of the SRV-RAIM method is introduced and a basic algorithm based on this idea is proposed. Simulations are also done to evaluate the performance of the SRV-RAIM algorithm and compared with the performance of the conventional traversal-RAIM.

According to the previous section, the $SR{V}_a$ and the $SR{V}_s$ are spatially separated in most of the spoofing conditions. However, in order to make full use of this characteristic to achieve the purpose of separating the real and spoofing signals, two problems remain to be solved: the one is that the best projection vector $v_0=\arg {\min }_{v}NH(v)$ is unable to be solved mathematically because there is no prior knowledge about $G_s$ and $Î\mathrm{”}{x}_{a}s$ , only $G$ is known; the other is that even though the $v_0$ is given, it is also difficult to directly separate real satellites from spoofing satellites because the number of spoofing satellites is unknown.

$SR{V}_a$ and $SR{V}_s$ are discretely distributed in the space, which means that the set of vectors that satisfies Eq. ( 17 ) is the union of continues subspaces and $v_0$ is the vector in this set. Therefore, the basic strategy to solve the first problem is searching the value of $v$ in a subspace $S_v$ with a finite number of vectors, instead of the whole space, to find $v_0$ . This strategy may reduce the probability to find $N{H}_0=0$ , but it is a necessary sacrifice to reduce the amount of computation. If $v_0$ is a uniform distributed random vector in space, then a good strategy for choosing a subspace $S_v$ is as follows: the vectors in the subspace should be as uniformly distributed in space as possible.

To solve the second problem, instead of finding all real satellites at once, finding 5 real satellites or 5 spoofing satellites is easier. If $v_0$ is given and $N{H}_0=0$ , the biggest five projections $D_1={\{p_i(v_0)\}}_{i⩽5}$ correspond to five real satellites ( $N_a⩽5$ ) or the smallest five projections $D_2={\{p_i(v_0)\}}_{i⩾N-4}$ correspond to five spoofing satellites ( $N_s⩾5$ ). After the five real (or spoofing) satellites are found, the rest of real (or spoofing) satellites can be found easily, because the pseudorange measurements of real (or spoofing) satellites are consistent, but the pseudorange measurements of real satellites are not consistent with those of spoofing satellites. Therefore, if a vector $v$ on which the biggest five projections $D_1={\{p_i(v)\}}_{i⩽5}$ , or the smallest five projections $D_2={\{p_i(v)\}}_{i⩾N-4}$ correspond to five satellites, whose pseudorange measurements are consistent, can be found, the real satellites and the spoofing satellites can be separated. Based on this idea, it is not necessary the find the best vector $v_0$ , which is impossible. That also means that even if the $SR{V}_a$ and the $SR{V}_s$ are not spatially separated ( $N{H}_0>0$ ), it may also be possible to separate the $SR{V}_a$ from the $SR{V}_s$ . That gives another chance to reduce the number of vectors in the subspace $S_v$ .

Based on the above analysis, the problem of separating the $SR{V}_a$ and the $SR{V}_s$ can be simplified as a hypothesis test problem as follows:

(1) $H_0:\exists v\in S_v,\text{\hspace{0.17em}s.t.,\hspace{0.17em}}{D}_1\subseteq S_a,D_1\subseteq S_s,D_2\subseteq S_a,\text{\hspace{0.17em}or\hspace{0.17em}}{D}_2\subseteq S_s$ ;

(2) $H_1:\exists /v\in S_v,\text{\hspace{0.17em}s.t.,\hspace{0.17em}}{D}_1\subseteq S_a,D_1\subseteq S_s,D_2\subseteq S_a,\text{\hspace{0.17em}or\hspace{0.17em}}{D}_2\subseteq S_s$ .

$S_a$ is the set of projections of real satellites, and $S_s$ is the set of projections of spoofing satellites.

In this paper, four projection vector subspaces ( $S_v$ ) are considered, and $p(H_0)$ of each subspace is given by simulations. The simulation conditions are shown in Table 1 , and simulation results are shown in Table 4 .

Assume that $v_0$ is evenly distributed in the 4-dimentional space, in this case, the vectors in $S_v$ is suggested to be also evenly distributed in the 4-dimentional space, but it is not easy to construct such a perfect subspace $S_v$ . An easier way to construct a subspace is that the coordinates of the vectors in the subspaces are lattice points (the value of coordinate axis is $-1$ , 0, or 1) near the origin, and the lattice points are as far away as possible. Except for $S_0$ , this paper gives three subspaces, defined as follows:

(20) $$\{\begin{array}{l}{S}_1=\left\{e_1,e_2,e_3,e_4,\underset{i=1}{\overset{4}{{\displaystyle \sum }}}{a}_i{e}_i\right\},\\ S_2=S_1\cup \left\{\underset{i=1}{\overset{4}{{\displaystyle \sum }}}{b}_i{e}_i\right\},\\ S_3=S_2\cup \left\{\underset{i=1}{\overset{4}{{\displaystyle \sum }}}{c}_i{e}_i\right\}\end{array}$$

where $e_i(i=1,2,3,4)$ is a 4 $\times$ 1 vector, whose $i$ -th element is 1 and other elements are 0; $a_1=1,a_i\in \{-1,1\}(i=2,3,4)$ ; ${[b_1,b_2,b_3,b_4]}^{\mathrm{T}}$ is the column of the matrix $B=[B_1,B_2]$ ; ${[c_1,c_2,c_3,c_4]}^{\mathrm{T}}$ is the column of the matrix $C=[C_1,C_2]$ ,

(21) $$B_1=\left[\begin{array}{cccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill \end{array}\right],$$ $$B_2=\left[\begin{array}{cccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill \end{array}\right]$$

(22) $$C_1=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill -1\hfill \end{array}\right],$$ $$C_2=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill -1\hfill \end{array}\right]$$

Table 4 shows that the average $p(H_0;S_v=S_0)$ is 98.72%, much larger than 80.37% (the average $p(N{H}_0=0)$ in Table 2 ). That is because even if $N{H}_0>0$ , $H_0$ could also be possibly true. $S_0$ contains 4094 vectors, so it will take a large amount of computation to find the right $v_0$ . $S_1$ only contains 12 vectors, but the average $p_1(H_0)$ is reduced to 90.98%, comparing to $p_0(H_0)$ . By expanding $S_1$ to $S_2$ , the average $p(H_0)$ can arise to 94.74% ( $p_2(H_0)$ ), but the number of vectors in subspace only increases 12. By expanding $S_2$ to $S_3$ , the average $p(H_0)$ arises to 97.08% ( $p_3(H_0)$ ), and the number of vectors increases to 40. Table 4 shows that by expanding the set $S_v$ , the probability of $p(H_0)$ will increase, but the computational cost will also increase. $p_3(H_0)$ is very close to $p_0(H_0)$ , so the performance gained from expanding the $S_3$ is no longer significant, but the computational cost will continue to increase. Therefore, in this paper, $S_3$ is considered a good balance between performance and computational complexity, and is chosen for further simulations.

According to the simulation results, the two problems mentioned at the beginning are almost solved. However, in the previous discussion, a question is ignored: How to test $D_1\subseteq S_a$ , $D_1\subseteq S_s$ , $D_2\subseteq S_a$ , or $D_2\subseteq S_s$ . In this paper, we assume that the pseudorange measurements of real (or spoofing) satellites are consistent, but the pseudorange measurements of real satellites are not consistent with those of spoofing satellites. Based on this assumption, the question is translated to test if the pseudorange measurements of five satellites, whose projections are $D_1$ or $D_2$ , are consistent. A common method to test the consistency of pseudorange measurements is to use SSE as the test statistic, which is defined as

(23) $$\text{SSE}=\sqrt{\frac{\text{Δ}{y}^{\text{T}}\text{Δ}y}{n-4}}$$

where $\text{Δ}y$ is the least squares residuals, $n$ is the number of pseudorange measurements.

Based on the above discussion, an SRV-RAIM algorithm is proposed, as shown in Algorithm 1.

Note that the method only divides the pseudorange measurements into two groups. Extra information is needed to identify which group is real, and in this paper, the identification is ignored. Step 3 in Algorithm 1 is a detailed supplement of the SRV-RAIM algorithm, but not the core idea of it. Therefore, in this paper, only steps before Step 3 of the method are evaluated by simulations. The simulation conditions are basically the same as in Table 1 , except that the measurement error is considered as a Gauss noise with mean being 0 and standard deviation being 4 m. According to Ref. [ 12 ], the test threshold TH in the SSE method is calculated in the alarm rate of 95%. The simulation result is shown in Table 5 .

The method is considered “success” if real signals and spoofing signals are successfully separated. The method is considered “false” if the Flag is 1, but there is a group that contains both real signals and spoofing signals. The method is considered “fail” if Flag is 0. Table 5 shows that the SRV-RAIM algorithm has an average of 86.55% success rate, 3.01% of false rate, and 10.44% of failure. Comparing to the ideal performance 97.08%, shown in Table 4 , the practical performance is decreased by 10.53%. The main reason for the obvious performance reduction is the high miss detection and false alarm rate of the SSE method. When a miss detection of the SSE method happens, the SSE test statistic may still be smaller than the threshold even if there exist both spoofing signals and real signals. When the SSE method arises a false alarm, the SRV-RAIM algorithm may loss the right projection vector $v_k$ or fail in dividing the real signals and spoofing signals (Steps 9–33 in Algorithm 1). From Algorithm 1, it is obvious that the SSE method takes a very important part, so the performance of SSE will greatly affect the performance of the algorithm. Both the miss detection and the false alarm of the SSE method can cause a false separation or a failure of the SRV-RAIM algorithm. The performance of the SSE method decreases significantly in the following two scenarios:

(1) The real pseudorange is close to the spoofing one;

(2) The quality of satellite geometry is inferior^{[ 18 , 19 ]}.

The first case can be avoided because, in normal spoofing situations, the spoofing pseudorange will not always be close to the real one over time. Therefore, Step 3 in Algorithm 1 can correct the false separation. The second case happens because, in the SRV-RAIM method, the first step is testing the consistency of only five pseudorange measurements. The quality of satellite geometry may be inferior when the number of satellites is small. In this case, the false separation and failure probability can be reduced only when the difference between the spoofing pseudorange and the real pseudorange is large enough. Therefore, Step 3 in Algorithm 1 is very important for the reliability of the SRV-RAIM method, but in this paper, it will not be discussed further.

The computational effort of the method is mainly focused on the search for the correct vector $v_k\in S_v$ , and frequent positioning calculations to separate the pseudorange measurements into two groups. In this paper, the amount of computation is measured by the number of positioning calculations ( $n_s$ ) needed to separate real signals from spoofing signals, because it is the most computationally expensive part of Algorithm 1. The amount of computation of the SRV-RAIM is shown in Table 6 . The result shows that the computational cost of Algorithm 1 is very low, regardless of the number of spoofing satellites. The computational cost only arises a little when the spoofing number grows to 6. This is because the separation conditions of SRV worsens when the spoofing number increases, as shown in Table 2 , leading to the need to search more vectors $v_k\in S_v$ to find the first five signals that have consistent pseudorange measurements.

In order to further analyze the advantages and disadvantages of the SRV-RAIM algorithm, the performance of the conventional traversal-RAIM is also proposed. The main idea of the conventional traversal-RAIM method to solve multi-spoofing situations is to go through all the possible fault-free cases, and use SSE method to test if there exist fault signals until find the right one that pass the SSE test. Simulations are done to evaluate the conventional traversal-RAIM method, and the results are shown in Table 7 and Table 8 .

Table 7 shows that the conventional traversal-RAIM has an average success probability of 90.14%, an average false separation probability of 2.87%, and an average failure probability of 6.99%. The reasons that cause the false separation and failure of the traversal-RAIM are almost the same as SRV-RAIM method. Table 8 shows the amount of computation of the conventional traversal-RAIM method. It shows that the amount of computation increases rapidly when the number of spoofing satellites grews to 6, because of the increase number of possible combinations of fault satellites. The average computational cost of the traversal-RAIM method is 1361.1.

According to Table 6 and Table 8 , the amount of computation of the conventional traversal-RAIM is smaller than that of the SRV-RAIM method when the spoofing satellite number is 1 or 11. In this case, the SRV-RAIM method firstly tries to find 5 real (or spoofing) satellites, which requires several times of positioning calculations. After finding 5 real (or spoofing) satellites, the SRV-RAIM method needs 6 more times of positioning calculations (Step 12–19 in Algorithm 1) to find other 5 real (or spoofing) satellites. Comparing to the SRV-RAIM method, the conventional traversal-RAIM only needs to traverse 12 fault conditions. If lucky enough, the conventional traversal-RAIM only needs 1 time of positioning calculation, but the SRV-RAIM method needs 7 times of positioning calculation. When the number of spoofing satellites increases, the amount of computation of the SRV-RAIM method only increases a little, but the amount of computation of the conventional traversal-RAIM increases rapidly. The average computational cost of the SRV-RAIM method is only 1.7% of the conventional traversal-RAIM.

By comparing the simulation results of the conventional traversal-RAIM method and the SRV-RAIM method, it can be found that the effective probability of the SRV-RAIM method is 3.59% lower than that of the conventional traversal-RAIM, but the computational cost is reduced by 98.3%. This low computational complexity allows the algorithm to be run in-time on most of the GNSS receivers, and it greatly improves the availability of the GNSS receiver in spoofing environment.