Ibrahim Sbeity
email: ibrahim.sbeity@cea.fr

Christophe Villien
email: christophe.villien@cea.fr

Christophe Combettes

Benoît Denis

Veronica Belmega

Marwa Chafii

A Novel Satellite Selection Algorithm Using LSTM Neural Networks For Single-epoch Localization

Keywords: Global Navigation Satellite System, Satellite Selection, Single-epoch Positioning, Machine (Deep) Learning, Long-Short Term Memory Neural Network

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Accurate and resilient positioning services based on the Global Navigation Satellite System (GNSS) have become essential into a variety of outdoor applications, such as autonomous vehicles and unmanned aerial vehicles, blueforce and first responders tracking, seamless end-to-end logistics and supply chains optimization, large-scale crowd-sensing, etc.

By itself, single-epoch GNSS localization is a key enabler that can provide tracking filters with input observations so as to refine further the mobile position and exploit its dynamics through hybrid data fusion (e.g., combining GNSS with other modalities from inertial sensors, odometers, etc.). Beyond, single-epoch localization is also and foremost typically used to initialize the navigation processor in charge of tracking the GNSS filtered solution [START_REF] Grewal | Global positioning systems, inertial navigation and Integration[END_REF].

The signals received from satellites can be severely affected by Non-Line of Sight (NLOS) and multipath (MP) propagation in harsh environments, such as urban canyons, hence leading to strongly biased pseudo-range measurements. In this context, selecting the most reliable and/or most informative measurements (while discarding the most harmful ones) is of primary importance to preserve the accuracy of this preliminary singleepoch positioning stage and, hence, of the overall navigation system. This down-selection step is even more critical and challenging as several tens of measurements are typically made available within modern GNSS receivers at each time epoch (i.e., while considering multiple satellites from different constellations), making exhaustive search computationally prohibitive. Most basic selection approaches mainly exploit signal features at single link level (e.g. carrier-to-noise power density ratio C/N 0 , elevation angle θ, etc.) so as to excludeor mitigate the influence of -satellites that would presumably contribute to large positioning errors [START_REF] Hartinger | Variances of gps phase observations: The sigma-ϵ model[END_REF], [START_REF] Brunner | Gps signal diffraction modelling: the stochastic sigma-δ model[END_REF].

For the remaining satellites fulfilling these basic single-link quality criteria, many selection techniques have been proposed such as, subset-testing [START_REF] Zhu | Evaluation and comparison of gnss navigation algorithms including fde for urban transport applications[END_REF], RANSAC [START_REF] Castaldo | P-ransac: An integrity monitoring approach for gnss signal degraded scenario[END_REF], iterative reweighting [START_REF] Akram | Gnss positioning accuracy enhancement based on robust statistical mm estimation theory for ground vehicles in challenging environments[END_REF], etc. These methods involve different tradeoffs between computational complexity and performance. However, because of the huge combinatorial complexity of testing all possible subsets of satellites, exhaustive search is not tractable and

In this paper, we introduce a novel pre-processing approach suited to single-epoch stand-alone positioning, which aims at overcoming major drawbacks of conventional selection techniques. More specifically, we redefine the initial satellites selection problem as a weighting problem, where one first originality lies in the application of machine learning (ML) into the domain/space of pseudo-range residuals (i.e., relying on intermediary positioning results conditioned on specific subsets of satellites) for determining the best satellite weights.

In order to fully exploit the potential of deep learning tools in harnessing hidden correlations between pseudorange measurements, as well as possible joint effects from discarding several satellites at a time (on final positioning performance), we exploit a long-short term memory neural network (LSTM NN), which is fed with a customized pseudo-range residuals matrix (processed as a whole), representing a second originality of our contribution. This NN is trained to predict quality factors that account for the link-wise standard deviations of pseudo-range errors. These predictions are finally used to compute nearly-optimal satellite weights within a standard weighted least squares (WLS) positioning solver.

To sum up, our main contributions are two fold. First, we introduce a novel deep learning-based technique to solve the satellite selection problem dedicated to improve the accuracy of single-epoch positioning. The main ingredients of our approach are the LSTM NN architecture coupled with the new and customized pseudo-range residual matrix used as the NN input. Second, we improve the computation of the measurement weights in comparison with conventional parametric methods. Finally, our approach is tested on both synthetic simulation data and real-field experimental data from extensive measurement campaigns, which were conducted with a dedicated test platform under typical vehicular mobility in a variety of scenarios and environments.

Note that our approach can be beneficial to both realtime location-based applications requiring accurate positioning information (e.g., autonomous vehicles, unmanned aerial vehicles...) and offline post-processing applications (e.g., aiming at correcting raw online GNSS trajectory a posteriori).

The rest of this paper is structured as follows. First, Section II introduces the system model and the general problem formulation. On this occasion, we also recall representative satellites selection techniques from the literature. Then, our construction of the residuals matrix, its use as an input to the LSTM NN, as well as the underlying machine learning model, are detailed in Section III. Finally, numerical results on both synthetic and real datasets are analyzed in Section IV.

II. PROBLEM FORMULATION

We start by describing the problem under study and then we summarize the most representative existing work.

A. Single epoch solution

For the sake of simplicity and without any loss of generality, we consider a set of N single band, single constellation, pseudo-ranges measurements {ρ i } i=1...N (the same formulation would apply for carrier phase, pseudo-range rates, etc.), while for the experimental validations reported in Sec. IV we will deal with multi-band and multi-constellation scenario. For those pseudo-range measurements, the appropriate compensations computed from ephemeris data (satellite vehicle (SV) clock bias, ionospheric and tropospheric delays, Sagnac correction etc.) have already been applied. In the absence of multi-path or any strong bias, the i-th SV measurement can be modeled as

ρ i = (x -x i ) 2 + (y -y i ) 2 + (z -z i ) 2 + c δ + η i , (1)
where ρ i is the pseudo-range between a receiver R and the i-th SV, and (x i , y i , z i ) and (x, y, z) the coordinates for the i-th satellite and the receiver, respectively. The parameter c is the speed of light, and δ is the clock bias between the receiver and the considered constellation; η i is the observation noise which represents the receiver noise and residual errors from ionosphere and troposphere delays, etc. Although ionosphere and troposphere residual errors (i.e. after correction from navigation message) are highly correlated over time, they could be considered as independent and zero mean for single epoch processing. Hence, we can assume that the observation noise follows a centered Gaussian distribution η i ∼ N (0, σ 2 i ). Our aim is to estimate the vector X = [x, y, z, δ] ⊤ from the measurements {ρ i } i=1...N . A widely used and efficient solution is provided by the maximum-likelihood estimator (MLE) [START_REF] Rossi | Mathematical Statistics: An Introduction to Likelihood Based Inference[END_REF], which simplifies to a weighted least-squares for our Gaussian noise model

X = arg min X N i=1 ω i (ρ i -h i (X) 2 , (2)
with the observation function for satellite S i defined as

h i (X) = (x -x i ) 2 + (y -y i ) 2 + (z -z i ) 2 + c δ, (3)
and the weights equal to

ω i = 1 (σ 2 ) i . (4)
The solution can be easily computed using an optimization algorithm such as Gauss-Newton or Levenberg-Marquardt [START_REF] Moré | The levenberg-marquardt algorithm: Implementation and theory[END_REF].

B. GNSS Satellite Selection and Weighting Problems

Generally, a first basic SV selection based on satellite elevation or C/N 0 thresholds is performed to excluded presumably strongly biased measurements. Then, the standard deviation of the remaining measurements will be estimated using an empirical functions, for example, as the following,

(σ 2 ) i = 1 sin 2 (θ i ) σ 2 ρZ + σ 2 ρc (C/N 0 ) i + σ 2 ρa (a 2 ) i , (5)
where this functions mainly depends on satellite elevation θ 0 , C/N 0 , acceleration a i , and other empirically calibrated coefficients (σ 2 ρZ , σ 2 ρc , σ 2 ρa ) that are hard to be tuned. However, some measurements could be strongly biased by multi-path for instance, and violate the expected Gaussian model resulting in a significant degradation of the solution accuracy. It is thus of primary importance to exclude these measurements from the solution, either by discarding them or by assigning them a zero weight, which is called deweighting. Such measurements can be efficiently detected at the navigation processor stage based on innovation monitoring tests for instance [START_REF] Zhu | Extended kalman filter (ekf) innovation-based integrity monitoring scheme with c / n0 weighting[END_REF], but this requires that the tracking filter has converged and that the predicted state (i.e., position, receiver clock offset, etc.) is accurate enough. Nevertheless, for single epoch processing, no predicted solution is available and SV selection relies on measurements only with very limited prior knowledge. This implies that the detection of k faults among N measurements could potentially results in a huge number of subsets, C N k , to test in case of an exhaustive search, which may be intractable in real-time and even for postprocessing. As an example, assuming at most 10 faults among 40 measurements would result in more than 847 × 10 6 subsets to test, which is computationally prohibitive.

C. Existing Works

In GNSS, fault detection and exclusion (FDE) usually rely on statistical tests and consistency checks to identify and reject corrupted signals to improve the integrity of the navigation solution. Various FDE techniques already exist in the literature, such as classical FDE [START_REF] Knight | A comparison of outlier detection procedures and robust estimation methods in gps positioning[END_REF], [START_REF] Kuusniemi | User-level reliability monitoring in urban personal satellite-navigation[END_REF], the brute force subset testing approach [START_REF] Angrisano | Gnss reliability testing in signal-degraded scenario[END_REF], ARAIM techniques [START_REF] Zhai | Fault exclusion in multiconstellation global navigation satellite systems[END_REF], [START_REF] Joerger | Solution separation versus residualbased raim[END_REF], and others that depend on the Range Consensus (RANCO) [START_REF] Zhao | A modified range consensus algorithm based on ga for receiver autonomous integrity monitoring[END_REF]. More recent works [START_REF] Combettes | Ekf based on two fde schemes for gnss vehicle navigation[END_REF] have proposed a new FDE algorithm that is based on both a standalone FDE block making use of the residual test relying on WLS, and an FDE-based Extended Kalman Filter (EKF). This solution alternates between the two branches, based on a covariance matrix threshold. Typically, the EKF utilizing FDE is employed when the covariance matrix falls below a pre-defined threshold. If the covariance exceeds this limit, the FDE is used on its own. This algorithm was shown to provide significant performance gains in terms of accuracy compared to conventional state-of-the-art FDE algorithms. For this reason, we choose it as a reference for benchmark purposes in this paper. However, since we consider by definition a single-epoch localization application, we have configured this algorithm to use only its standalone FDE block.

III. PROPOSED SYSTEM ARCHITECTURE

As mentioned above, we herein consider a single-epoch stand-alone positioning framework based on pseudo-ranges, without performing differential corrections, where measurements are just pre-processed based on the ephemeris data (i.e., compensating for ionospheric, tropospheric, and Sagnac effects, as well as satellite clock errors). One main objective is hence to leverage the complex -and likely hidden -interdependencies and joint effects (over multiple links) through supervised deep machine learning, so as to efficiently weight (or de-weight) the contributions from all satellites.

Overcoming the difficulty of labeling the data per link on the one hand, while still observing the joint effects on positioning performance of multiple links from various standpoints (e.g., link quality, Geometric Dilution of Precision (GDoP), etc.) on the other hand, ML is thus applied directly into the space/domain of pseudo-range residuals. For this sake, our approach consists in constructing a matrix of such residuals, where the i-th row contains all the residuals computed from a solution while excluding the i-th measurement. Then, using this matrix as the input of a LSTM NN. The latter is trained to predict the weights ωi related to the underlying distribution of pseudo-range errors according to (4) for valid measurements, noting that a single measurement is observed from each distribution N (0, σ 2 i ). In addition, we expect that the algorithm will predict nearly null weights ωi ≈ 0 for strongly biased satellites to exclude them. Accordingly, we turn the initial (hard) selection problem into a (soft) weighting problem. The overall system architecture of our proposed approach is illustrated in Fig. 1.

A. Residual Matrices Construction

At each navigation epoch, we assume that multiple (N ) satellite signals are received and a new matrix of positioning residuals M is constructed, as follows. We generate N subsets S n of N -1 satellites, where we exclude one distinct satellite (i.e, n th satellite) at a time.

S n = {ρ i }, i = 1 . . . N, i ̸ = n (6)
For each subset S n , we calculate the corresponding solution X n using (2). Then, for each of the N resulting positions {X 1 , ..., X N } we calculate the N -1 pseudo-range residuals

δρ i Xn = ρ i -h i (X n ), i ̸ = n (7)
Coefficient [M] n,i (i.e. row n, column i) of the residual matrix M is simply given by the corresponding residual for nondiagonal coefficient, or by an arbitrary large value γ for the diagonal terms indicating that the satellite has been excluded (the pseudo-code for constructing the residual matrix is shown in Algorithm 1)

[M] n,i = δρ i Xn , i ̸ = n γ, i = n (8)
Each row n of the matrix will thus provides residuals associated with the exclusion of the n-th measurement. Although it assumes a single fault per subset (i.e., row), the motivation of building such a matrix is that it may be able to reveal hidden inter dependencies between the measurements and their effects on the computed solution, while being fed as a single input to the neural network.

Algorithm 1: Residual Matrix construction

for n ∈ range(N ) do X n ← arg min X N i=1 i̸ =n (ρ i -h i (X) 2 for i ∈ range(N ) do if n=i then M[n,i] ← γ else M[n,i] ← δρ i Xn end end end return M B. Long-Short Term Memory Neural Network
The overall structure of the proposed residual matrix and more particularly, the evolution of the pseudo-range residual patterns over the N subsets (i.e., over the matrix rows), both provide rich information about the sought inter-dependencies and their combined effects, which can be advantageously captured by machine learning tools. By analogy, the pseudorange residuals matrix can be interpreted as a concatenation of N feature column vectors, each containing the feature values for N pseudo time steps. Each feature column vector thus corresponds to the set of pseudo-range residuals of one single satellite from each of the N subsets.

In this kind of problems, the LSTM NN algorithm, which is a type of recurrent neural network (RNN) [START_REF] Huang | Deep Learning: Fundamentals, Theory and Applications[END_REF], has the advantage of keeping memory over multiple (possibly distant) pseudo time steps. Hence, is also suited to exploit the correlations across the matrix rows in our case, even if we explicitly deal with a single-epoch problem. Similar applications of the LSTM NN to other time-invariant problems have already been considered. For instance, in [START_REF] Graves | Offline handwriting recognition with multidimensional recurrent neural networks[END_REF], LSTM NN was used to process data with long-range interdependence (i.e., using geometric properties of the trajectory for unconstrained handwriting recognition).

IV. NUMERICAL RESULTS

Here, we analyse the performance of our proposed deep learning based approach obtained on synthetic and real data.

A. Synthetic Data

In order to thoroughly test and validate the feasibility of our proposed approach in capturing the hidden inter-dependencies within the residual matrix, but also its ability to accurately approximate the standard deviations of pseudo-range errors, we first generate a dataset of synthetic simulation data mimicking the behavior of a real GNSS systems. This allows us to illustrate the main performance trends, as well as to validate our approach before applying it to real-world data (See Section IV-B).

This dataset consists of 180, 000 epochs, each containing N = 60 pseudo-range measurements with respect to 60 different satellites. The random noise terms affecting those pseudo-ranges are supposed to be independent and identically distributed (i.i.d.), following a distribution obtained as a mixture of normal and exponential distributions. The latter shall indeed account for the possibility to experience either typical errors expected from so-called "good" satellites or much more harmful (and likely positively biased) outlier measurements from "bad" satellites

f (x) = α 1 σ √ 2π e -(x-µ) 2 2σ 2 + (1 -α)λe -λx , ( 9
)
where α is the mixture parameter, which represents the probability that the measurement error realization is drawn from the normal distribution of mean µ and standard deviation σ, and λ is the decay rate of the exponential distribution. All these parameters were fine-tuned so as to fit the empirical distribution of real pseudo-range measurements, which were collected along with a reference ground-truth system in various operating conditions. The latter will be used in Subsection IV-B for further performance assessment. The generated synthetic data was then divided into three disjoint datasets: training, validation, and testing, with respective proportions of 60%, 20%, and 20% [START_REF] Géron | Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems[END_REF], in order to ensure a robust evaluation of the performance of our approach. The process of dividing the data into three sets is a common practice in machine learning, known as the train-validation-test split.

The training dataset is used to train the neural network and learn the underlying patterns in the data. The validation dataset is used to evaluate the performance of the neural network during training, and fine-tune the hyperparameters based on its performance. The testing dataset is used as an independent measure to evaluate the generalization performance of the prediction, which is an indication of how well the neural network will perform on new unseen data. This technique helps to prevent from overfitting effects, which occur when a neural network fits too closely the training dataset but performs poorly on new unseen data.

Note that labelling in our decision problem is a very challenging task since finding the best satellites' set is not tractable due to prohibitive combinatorial complexity (even offline and knowing the reference). This is the reason why we decided to convert the initial decision problem into a weighting problem. Following a supervised training, the data was hence labeled as:

ω i = 1/(ρ i -h(X true )) 2 , ( 10
)
where X true is the ground truth position. This intuitive choice is validated by our performance curves in Fig. 2 and3. Using this synthetic dataset, an empirical evaluation was first conducted on multiple neural network architectures, including convolutional neural networks (CNN), fully connected neural networks (FCNN), and various other types of recurrent neural networks (Simple-RNN, LSTM, Bi-LSTM and Gated recurrent units (GRU)). The simulation results then confirmed that the LSTM algorithm could provide the best WLS positioning performance (i.e., after applying the best weights out of NN predictions) in our problem. Its architecture was hence further optimized empirically during the training phase, based on real data. The best neural network consisted of one hidden LSTM layer containing 512 neurons followed by a dense layer containing 60 neurons with a ReLu activation function. On this occasion, the mean squared error (MSE) was used as loss function, and an early stopping callback was implemented to prevent overfitting. The used neural weights optimizer during training was Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF].

Finally, the WLS positioning performance based on our prediction method has been compared with theoretical bounds (i.e., Cramer Rao lower bound (CRLB)) [START_REF] Closas | Cram Ér-rao bound analysis of positioning approaches in gnss receivers[END_REF], as well as two genie-aided solutions on the one hand, and a suboptimal unweighted strategy on the other hand (i.e., as a worst-case baseline solution with equally-weighted pseudo-ranges from all the satellites). More precisely, the first tested method, referred to as "Ground-truth Weights", utilizes weights as in [START_REF] Knight | A comparison of outlier detection procedures and robust estimation methods in gps positioning[END_REF] with the ground-truth position, before applying WLS positioning. The second method, named "Predicted weights", uses the proposed algorithm to predict link-wise quality factors which is used to compute weights as in ( 4) for WLS positioning. The third method, referred to as the "Genie-aided" solution, is based on the assumption that a prior knowledge of the biased satellites is available, and utilizes this information to completely exclude biased satellites from the localization solution. This method serves here as a first reference in our benchmark, accounting for the best performance that could be achieved with perfect detection and exclusion of biased satellites. Finally, in the fourth "Equal weights" method, all the satellite measurements are taken into account in WLS positioning (i.e., with the same relative importance, regardless of their actual errors). This somehow represents a worstcase assumption without any exclusion, and serves as another reference in our benchmark, accounting for the performance that can be achieved without any prior knowledge, neither of the biases themselves, nor of their respective statistics. Fig. 2 and3 show the empirical cumulative density function (CDF) of horizontal and vertical positioning errors obtained with the four weighting strategies above. Those methods were first applied on a dataset including 9% of strongly biased satellites (i.e., among the 60 available). When compared to the evenly weighted positioning solution, the proposed approach is then shown to yield a typical accuracy improvement in 95% of the tested epochs (i.e., CDF at the characteristic 95%-quantile) of about 1.02 m in terms of horizontal errors (See Fig. 2) and 1.18 m in terms of vertical errors (See Fig. 3). On the other hand, when compared with the "Genie-aided" approach, the difference in accuracy for 95% of the tested epochs is about 0.59 m in terms of horizontal error, and 0.77 m in terms of vertical error.

Fig. 4 presents the 1-σ confidence ellipse for various weighting approaches in comparison with the CRLB. The results are acquired through the execution of Monte Carlo trials for a specified satellite and receiver geometry. The "Genie-aided" weighting approach shows close agreement with the CRLB in terms of accuracy, while the evenly weighted approach demonstrates inferior accuracy. The "Predicted weights" extracted from our approach, exhibits accuracy that lies between the CRLB and the "Equal weights" with a tendency towards the CRLB. The "Ground-truth Weights" approach outperforms the CRLB since noise mitigation is based on a perfect knowledge of the exact bias, which would not be available to any real estimator.

Still based on synthetic data, a sensitivity study was also conducted to analyze the performance of our approach for different percentages of strongly biased satellites. A preliminary analysis of the real dataset revealed that concrete real-life cases could have up to 9% biased satellites (i.e., among all the available satellites per epoch). Accordingly, we generated different synthetic datasets, while varying the percentage of strongly-biased satellites (among the 60).

Fig. 5 shows the evolution of the positioning error at 95% of the CDF (i.e., the 95%-percentile) as a function of this varying ratio. The results indicate that, as the proportion of biased satellites increases, the performance gain achieved with our approach in comparison with the equally weighted approach tends to grow more rapidly than the performance degradation observed in comparison with the idealized "Genieaided weights" approach, remaining in the same order of magnitude (i.e., less than 2 m vs. more than 2.6 m with the "Equal weights" strategy). This allowed us to further validate the robustness of our approach (i.e., far beyond the toy case of one single biased satellite), before applying it to real-world data, as discussed in the next section.

B. Real Data

Here, we present the most representative results obtained by extensive experimental testing and validation based on reallife data, which was collected from multiple measurement campaigns in a variety of operating conditions. These conditions included open skies, dense urban areas, and various mobility regimes. The data was collected using cutting-edge pieces of equipment and more specifically, an ublox ZED-F9P receiver, which is dual-band and endowed with Real-Time Kinematics (RTK) capabilities. A side cm-level ground-truth referencing system was also utilized to ensure the accuracy and integrity of the collected data, as well as to establish the ground-truth information. The tested GNSS receiver is capable of receiving up to N = 60 satellite signals from multiple GNSS constellations (i.e. GPS, GLONASS, GALILEO, etc.) over multiple frequencies (i.e. L1, L2, E1, and E5 bands). Overall, this testing phase consisted of 56 distinct sessions for a total of 181, 000 epochs, providing a comprehensive, representative and diverse dataset for evaluation.

The number of satellites received during each epoch could fluctuate, depending on the operating conditions. In certain environments, such as crowded urban areas for instance, the number of available satellites could be significantly lower than in open sky conditions as illustrated in Fig. 6. The figure depicts the variation in satellite availability during navigation in two conditions: open sky and urban areas. During this session, the availability in open sky regions remains stable at approximately 30 satellites, whereas in narrow urban canyons such as the one depicted in Fig. 6, the availability drops to a minimum of 9 satellites, as indicated by color-coded fluctuations. It is worth noting that in other sessions, the number of available satellites may increase up to 45. This variability is also influenced by the position of the satellites at the time of navigation. As a result, the dimension of our residuals matrix could have significantly varied as well. To address this issue, we employed padding to resize all the residuals matrices to a common matrix size. Additionally, we leveraged the ability of LSTM networks to handle variablelength input sequences by masking the non-present steps of the sequence, represented by rows of the residuals matrix in our representation.

For the purpose of optimizing the neural network architecture with a minimal number of layers and neurons while preserving performance, we employed a technique known as grid search. This involved varying the number of hidden layers and the number of neurons per layer as hyperparameters.

To prevent overfitting, we utilized an early stopping callback during the training process. The performance of each trained network was evaluated on an unseen test dataset. Through this process, we could determine that the optimal architecture consisted of 2 hidden layers with 893 neurons in each (See Fig. 1). Moreover, the neural network was trained using labels that were defined according to [START_REF] Knight | A comparison of outlier detection procedures and robust estimation methods in gps positioning[END_REF], where the X true stands for the ground truth position collected from the reference groundtruth system. Similar to the tests performed on synthetic data, Fig. 7 and 8 show quite significant improvements in terms of both horizontal and vertical errors, in comparison with the state-ofthe-art solution from [START_REF] Combettes | Ekf based on two fde schemes for gnss vehicle navigation[END_REF] (See Subsec. II-C). Typically, our approach exhibits a performance gain of 0.61 m (resp. 1.38 m) in terms of horizontal error at 68% (resp. 95%) of the CDF. As for the vertical error, we also observe an improvement of 0.66 m (resp. 1.43 m) at 68% (resp. 95%) of the CDF. This consistent performance improvement across all data points and for the different problem dimensions illustrates again the robustness of our proposal in improving localization accuracy under various operating conditions.

As shown in Fig. 9, which depicts a segment of one navigation session in a particularly penalizing environment (urban canyon), our approach could provide reliable single-epoch positioning results all along the tested trajectory, whereas the state-of-the-art approach fails in several important portions. More generally, over all the tested sessions, the state-of-theart approach was shown to fail in providing any solution in Fig. 8. Empirical CDF of horizontal error for various measurements weighting/selection strategies (incl. [START_REF] Combettes | Ekf based on two fde schemes for gnss vehicle navigation[END_REF]), based on real field data. Fig. 9. Example of positioning traces obtained for one of our field navigation sessions (urban canyon), for the proposed approach (green dots), the approach in [START_REF] Combettes | Ekf based on two fde schemes for gnss vehicle navigation[END_REF] from recent state-of-the-art (red dots), and the ground-truth reference system (blue solid line). about 8% of the tested epochs (in average), while our approach could systematically provide a reliable positioning solution. Our proposal thus seems even more particularly suited to severe operating conditions and/or challenging environments.

V. CONCLUSIONS

In this paper, we have introduced a new pre-processing technique for single-epoch standalone GNSS positioning based on deep machine learning, which aims at optimally weighting the pseudo-range contributions from available satellites. In particular, we rely on an LSTM neural network architecture, which is fed by a customized matrix of conditional pseudorange residuals. Performance assessment on both synthetic data and real data resulting from multiple navigation sessions show the high potential and relevance of our approach in challenging operating contexts, where conventional parametric satellites selection techniques would fail. Accordingly, this solution is suited to real-time applications requiring good continuity of the navigation service, as well to offline applications necessitating high-accuracy traces retrieval.

Future works could consider utilizing other satellite features/metrics (e.g., C/N 0 , elevation) as complementary information channels (i.e., besides the matrix of residuals currently in use) while feeding the learning process.

Fig. 1 .

 1 Fig. 1. The complete architecture of our proposed approach.

Fig. 2 .

 2 Fig. 2. Empirical CDF of horizontal positioning error for various measurements weighting methods, based on synthetic data.

Fig. 3 .

 3 Fig. 3. Empirical CDF of vertical positioning error for various measurements weighting methods, based on synthetic data.

Fig. 4 .

 4 Fig. 4. Comparison of Positioning confidence ellipses for various approaches with the CRLB.

Fig. 5 .

 5 Fig. 5. 95%-quantile of positioning error for different measurements weighting methods, as a function of the ratio of biased satellites (among 60), based on synthetic data.

Fig. 6 .

 6 Fig. 6. Variation of satellite availability while navigating in different conditions (open sky vs urban area).

Fig. 7 .

 7 Fig. 7. Empirical CDF of horizontal error for various measurements weighting/selection strategies (incl. [16]), based on real field data.

  A Novel Satellite Selection Algorithm Using LSTM Neural Networks For Single-epoch Localization Ibrahim Sbeity * † , Christophe Villien * , Christophe Combettes * , Benoît Denis * , E. Veronica Belmega ‡ † , and Marwa Chafii § ¶


domain: info math spi

text:
Arnaud Valence
email: arnaud.valence@esiea.fr

ICAR, a categorical framework to connect vulnerability, threat and asset managements

Keywords: Vulnerability management, threat management, asset management, CVE, CWE, CAPEC, CVSS, CPE, Category theory

published or not. The documents may come

Introduction

When it comes to cyber systems defense, security operations management has long involved separate tasks: vulnerability management, cyber threat management, and asset management. Today, these disciplines are intended to interoperate within a broader framework, supported by public knowledge bases on cyber threats, vulnerabilities, and IT assets. This interoperability draws an integral and integrated research path, at the interface between ontology language, database theory and cybersecurity, in order to understand how adversaries use vulnerabilities to achieve their goals. • Some works propose unied ontologies, more or less interoperable, such as Kurniawan et al. [START_REF] Kurniawan | An ATT&CK-KG for Linking Cybersecurity Attacks to Adversary Tactics and Techniques[END_REF], preceded in this by partial ontologies such as UCO and SPESES, which do not yet include the CTI incorporated in the ATT&CK (even if they can include other vulnerability repositories, such as the CYBOX, KillChain or STUCCO standards).

• Other research explores the track of domain-specic languages (DSL), and in essence that of the Meta Attack Language (MAL) meta-language. This is the case for Xiong et al.'s EnterpriseLang meta-language [START_REF] Xiong | Cyber security threat modeling based on the MITRE Enterprise ATT&CK Matrix[END_REF] and Åberg and Sparf 's AttackLang meta-language [START_REF] Åberg | Validating the Meta Attack Language Using MITRE ATT&CK Matrix[END_REF].

• A third research direction proposes to deepen the graph visualization aspects of attack paths through a relational representation of threats and vulnerabilities. This is the case of the BRON model of Hemberg et al. [START_REF] Hemberg | Linking Threat Tactics, Techniques, and Patterns with Defensive Weaknesses, Vulnerabilities and Aected Platform Congurations for Cyber Hunting[END_REF].

The approach proposed here is a new way to deepen the mathematical aspects of integrated security operations management. This approach combines the advantages in that (i) like the rst approaches mentioned above, it develops a unied vision of vulnerability and threat repositories;

(ii) like the second ones, they articulate vulnerabilities and threats within the framework of a cybersecurity-oriented meta-language, except that and this is a fundamental point it is a mathematical metalanguage rather than an ontological one 1 .

(iii) like the third ones, it deepens the study of graph visualization and structural properties of the unied cybersecurity ontology, by borrowing the powerful and rICARous graph-theoretic concepts of category theory.

We believe that category theory can be put to good use by cybersecurity teams. Following the example of a growing number of researchers, involved in more and more diverse elds of knowledge, we believe that the concepts of category theory oer important keys to understanding that simplify and unify the treatment of security operations. We see category theory as the very language of interoperability that enables the integrated management of assets, vulnerabilities, and cyber threats.

The article is organized as follows. The second section discusses the construction of the integrated cybersecurity resource, which will lead to the knowledge graph called ICAR. Based on this, the third section shows how to exploit the knowledge graph to answer dierent concrete cybersecurity queries. We will see how the categorical concepts allow us to handle bottomup (from assets to defend to adversaries) as well as top-down (from adversaries to assets) queries. The fourth section concludes.

2 Building the ICAR resource

Data sources

The data sources are from the knowledge bases provided by the NIST (National Institute of Standards and Technology) and the MITRE Corporation.

• Common Platform Enumeration (CPE) is a way of assigning standardized identiers to classes of IT assets.

• Common Vulnerabilities and Exposures (CVE) is a knowledge base listing publicly known vulnerabilities. Each CVE entry contains an identication number, a description and at least one reference to publicly known cyber security vulnerabilities. Additional information may include patch information, severity scores and impact assessments according to the Common Vulnerability Scoring System (CVSS), as well as links to exploit information and advisories. These ve knowledge bases (or six including CVSS) thus make up an integrated ontological resource for cybersecurity (which we will call ICAR).

At this point, it is important to note that this resource only represents the abstract relationships between the data sources. In the language of database, we would say that it shows the column headings of the primary and secondary keys, but not the column entries themselves.

Ontologies as knowledge graphs

The integrated ontological resource can be represented more formally as a graph.

Denition 1 (Graph). A graph G is a sequence G := (V, E, src, tgt), where V et E are sets (respectively the set of vertices and the set of arrows of G), and src, tgt : E → V are functions (respectively the source and target function of G). An arrow e ∈ E with source src(e) = v and target tgt(e) = w is represented as follows:

v e ----→ w.
On this basis, it is possible to represent each dictionary (or ontology) by a vertex and each link between dictionaries by an arrow, without forgetting that dictionaries can have internal links. This is the case of CAPEC Patterns are intended to focus on the compromise of applications in order to understand the path taken by adversaries to exploit end-to-end application weaknesses in the information system (IS), while techniques describe the concrete dynamics of an attack scenario executed step by step to compromise the IS (see [START_REF]CAPEC -ATT&CK Comparison[END_REF] for more details). Thus, technique T1528, which describes the theft of application access tokens in order to obtain credentials for access to remote systems and resources, can be contextualised in two dierent ways: (i) as a step to legitimise application actions under the guise of an authenticated user or service by obtaining a trusted identier, hence its belonging to the CAPEC-21 (Exploitation of Trusted Identiers) pattern, (ii) as a strategic step to steal account names and passwords, hence its belonging to the TA0006 (Credential Access) tactic. Ultimately, the techniques em-body attack tactics as the "how" of the attack (where tactics characterise the "why").

Semantic facts and knowledge schema

We can do better. What the knowledge graph represents are roughly the data tables (the vertices) and the data columns (the arrows). However, there is still some information missing which is not made explicit in the graph: the path equivalences in G.

Denition 2 (Path). Let G = (V, E, src, tgt) be a graph.

A path of length n in G, denoted p ∈ P ath (n) G is a sequence p = (v 0 a 1 -----→ v 1 a 2 -----→ v 2 a 3 -----→ . . . an -----→ v n )
of arrows in G. In particular, P ath (0) G = V and P ath (1) G = E. The set of all paths in G is denoted

P ath G := n∈N P ath (n) G .
Paths may themselves carry higher level information about the knowledge structure. This is the case if constraints are imposed on the paths to translate properties that make sense. These constraints can then be expressed as path equivalences.

Denition 3 (Path equivalence). Let G = (V, E, src, tgt) be a graph and p, q : b → c ∈ P ath

(n)
G two paths in G. A categorical path equivalence relation in G, or simply a path equivalence in G, is a relation denoted ≃ such that p ≃ q if and only if src(p) = src(q) and tgt(p) = tgt(q). Moreover, if m : a → b and n : c → d are two arrows in G, then m and n are respectively an epimorphism (a right simpliable morphism) and a monomorphism (a left simpliable morphism), i.e. p ≃ p if and only if mp ≃ mq and pn ≃ qn.

Following Spivak [START_REF] Spivak | Functorial data migration[END_REF], we call this equivalence relation facts.

There are facts in our study. It is indeed natural to ask for a form of reciprocity in the links between weaknesses and attack patterns. If an attack pattern CAP EC -X exploits a weakness CW E -Y , it is natural that it is part of the patterns referenced by this weakness. We can therefore add a path equivalence in the knowledge structure to obtain the following fact:

(CAPEC-X Has --→ CWE-Y Has --→) ≃ CAPEC-X.
for all CAPEC-X ∈ CAPEC and CWE-Y ∈ CWE.

Parent/child relations express other facts. It is natural to require that a weakness CWE-X declaring a child CWE-Y is itself declared as the parent of the child. We therefore have a constraint such as

(CWE-X isP arentOf -------→ CWE-Y isChildOf ------→) ≃ CWE-X.
It is also possible to express path equivalences in the more convenient algebraic form of path equalities, using composition operator (.). The two previous equivalence relations can then be rewritten, for any i ∈ {CWE, CAPEC} i.Has.Has =i, i.isChildOf.isParentOf =i, i.isParentOf.isChildOf =i.

(1) Are there other facts? Couldn't we ask that the child of a weakness belong to the same attack pattern as its parent, or one of its children? The answer is no. The data structure of the CWE and CAPEC does not have this characteristic. No hybrid facts can be derived from the two previously dened facts.

This negative result can be attributed to the meaning provided by the labelling of arrows. Stress that facts are dependent on the meaning of arrows.

They are semantic facts. For example, in a bijective data structure where each parent has exactly one child and a child exactly one parent, there is an equivalence between the path p = (v

0 isOnlyP arentOf ---------→ v 1 isOnlyChildOf ---------→) ∈ P ath (2)
G and the path p ′ = v 0 ∈ P ath (0) G , but this equivalence no longer holds in a data structure with multiple parents and children. This is why it is not possible to apply Spivak's theory of ologs [START_REF] Spivak | Ologs: A Categorical Framework for Knowledge Representation[END_REF]. Ologs are elegant categorical frameworks for rICARously representing knowledge structures exploiting databases, but are limited to structures of functional type. It is inappropriate in this study since the vertices of our knowledge graph generally have several arrows, and may in some cases have none.

On the other hand, the usual theory of oriented (multi)graphs is too broad to capture all the properties present in this study, since we added a path equivalence property. If we add the facts 1 to the knowledge graph 1, we obtain a richer structure called (knowledge) schema . Denition 4 (Categorical schema). A categorical schema S consists of a pair S := (G, ≃) where G is a graph and simeq a path equivalence on G.

In the remainder of this study, we will speak more simply of a schema, in the absence of any risk of confusion.

More about relation CW E ⇆ CAP EC

It was noted that the CWE and CAPEC dictionaries are linked in both directions. This may seem strange, as a mapping can in principle be read both ways: if the weaknesses correctly refer to the attack patterns, it should be possible to recover the former from the latter. Actually, this is not always the case. Kanakogi et al. [START_REF] Kanakogi | Tracing CAPEC Attack Patterns from CVE Vulnerability Information using Natural Language Processing Technique[END_REF] report some CAPEC-IDs that are not identied by CWE-IDs that fall within their attack pattern. As a result, some CVE-IDs would not be correctly mapped to their attack pattern(s). The authors give the example of the CVE-2018-18442 vulnerability, which is linked to a weakness due to network packet ooding. However, while there is an attack pattern for this weakness (the CAPEC-125 pattern), the fact is that the vulnerability is also associated with the CWE-20 weakness (incorrect input validation) which, according to the authors, prevents the vulnerability from being linked to the CAPEC-125 pattern, as the latter is not referenced by the CWE-20 weakness. This problem then motivates the authors to link CVE-IDs directly to CAPEC-IDs. Their solution is to use similarity indicators between CVE-IDs and CAPEC-IDs, thanks to machine learning and natural language processing.

In fact, the traceability problem discussed by Kanakogi et al. does not describe an architectural aw (since weaknesses can list several attack patterns), but reects the incomplete mapping between dictionaries. From this point of view, the strategy of the authors seems to be good, even if it consists in directly linking dictionaries that are not graphically related. In the end, this direct approach seems to be complementary to ours in that it allows to complete the collection of arrows that will be used to populate the knowledge schema. This remark is also valid for other approaches of direct mapping between dictionaries, like the projects of Grigorescu et al. [START_REF] Grigorescu | CVE2ATT&CK: BERT-Based Mapping of CVEs to MITRE ATT&CK Techniques[END_REF], Kuppa et al. [START_REF] Kuppa | Linking CVE's to MITRE ATT&CK Techniques[END_REF] or Ampel et al. [START_REF] Ampel | Linking Common Vulnerabilities and Exposures to the MITRE ATT&CK Framework: A Self-Distillation Approach[END_REF], which aim to link CVE-IDs to MITRE ATT&CK tactics and techniques.

ICAR as schema instance

The knowledge schema provides an abstract view of cybersecurity data ontologies, the "skeleton". It represents the structure of the data in the form of a triplet (of vertices, arrows and equivalence relations) in exactly the same way as the attributes of database tables present the n-uplets of the database.

It is now a question of populating the knowledge schema in such a way as to make the knowledge base explicit. This explicitation is in fact an instantiation (a "concretisation") of its schema. 3. the equality I(p) = I(q) for any path equivalence p ≃ q.

Denition 5 (Instance)

In other words, an instance on S is a path equivalence preserving functor F : S → Set.

Among the innite number of instances that can be generated by C, there is one that interests us the most: the up-to-date resource for cybersecurity ontologies. We call this instance ICAR for Integrated CAtegorical Resource. Only the substring <vendor>:<product> is represented here. ( * : Non available)

We check that ICAR actually is in categorical normal form. Condition 1 is met because each dictionary has a single primary key column. Condition 2 is assumed to be met by the successive updates of the dictionaries: if a new entry appears in the foreign key columns, it is assumed that it is indexed at the same time in another table as a primary key. There are no unreferenced entries in primary key. On the other hand, it is possible that no foreign key is associated with the entry of a new item as a primary key. This is typically the case when, for instance, an asset aected by a vulnerability has not yet been found, or the weakness corresponding to this vulnerability is still awaiting identication, etc. It is also possible for a primary key column to have no foreign key column. In this case (very common in databases), the table is limited to a single column. This is the case here for the CPE and Tactics tables. In this case, we speak of a leaf column. Condition

3 is respected because it is easy to check that the facts 1 are translated into relational equivalences in database: the attack patterns declared in the weaknesses declare in turn the declaring weaknesses, and vice versa, and the children declared by the weaknesses or the attack patterns declare in turn their declaring parents.

3 Using the ICAR resource

In this section, we illustrate the applicability of ICAR through several use cases. First of all, we must start by introducing the assets of the IS subject to attack.

Instantiate ICAR with an IS

Graph 1 brings together knowledge about vulnerability and threat managements in a single categorical schema. But there is still to consider the asset management. Assets are explicitly taken into account by Kiesling et al. [START_REF] Kiesling | The SEPSES Knowledge Graph: An Integrated Resource for Cybersecurity[END_REF] in the SEPSES knowledge graph. Indeed, we nd there the sub-graph CPE hasP roduct ------→ Product. We take up this idea with two dierences. Firstly, we consider only a subset of assets. This restriction allows us to refer to a concrete entity to be analysed, i.e. an IS made up of assets inventoried in a database (to be monitored or investigated). This inventory of assets is commonly materialised by a conguration management database (CMDB).

Secondly, and by pure convention, we reverse the arrow formalising the dependency between CPEs and assets. We therefore have the following Q1 query: Query 1 (Q1). Instantiate an inventory of assets DB X ∈ Product.

Let's start by noting that the instantiation we're talking about here is dierent from the instantiation of the knowledge schema. The idea now is to instantiate an object which already has the database structure (ICAR), in other words to populate ICAR (where ICAR instantiates the knowledge schema as a "concretisation"). In category theory, this notion of instantiation can be approached in many ways. In fact, there are at least two ways of dealing with Q1, either by rst "connecting" table Product to table CPE and then ltering on the assets DB X ⊂ Product, or by directly connecting 2 It can also happen that the CPE reference is not entered in the CMDB. Furthermore, there are many "exotic" assets that are not listed in the CPE dictionary DB X and CPE tables. In the rst case, a ltering operation must be added to the asset connection operation. This operation is not trivial in category theory. Moreover, it implies adding ex post the quantitative aspect induced by the potential presence of more assets with same CPE reference. This is why we will apply the second method, which is easier and more direct. The idea of ltering will nevertheless be discussed later in order to answer query Q6.

In pratical terms, if we think in terms of database management, the addition of DB X to ICAR can be understood as a database migration, and more precisely as a database union. This intuition can be translated into terms of "categorical data". The idea of "migration" nds a natural translation in category theory with the concept of functor. Let S be the (categorical) schema associated with gure 1 (i.e. devoid of assets) and T the schema associated with gure 2 (i.e. enriched with an inventory of assets). Following the example of Spivak [?, 13], we can then dene a schema morphism (i.

I ⇝ I • F (3)
as well as the functors Σ F , Π F : S -Inst → T -Inst as adjoint functors of ∆ F , respectively on the left and on the right.

In the language of category theory, ∆ F , Σ F and Π F are called pullback 3 , left pushforward and right pushforward respectively.

Intuitively, ∆ F can be understood as a projection operator in the sense that data (tables, columns) is duplicated. In contrast, Σ F is interpreted in terms of unifying tables, and Π F in terms of joining tables. This dierence between left and right pushforwards (between unication and junction) is important. When the tables to be joined have no common key, the merging operation can take place in one of two ways:

• either by adding the rows of the second table to those of the rst, which has the eect of creating Skolem variables in the unlled "foreign" columns (in this case we reason on the sum of the primary key spaces); 3 Here, the term "pullback" is understood as "a category of instances assigning a set of row-IDs to a schema element". This denition is related to Grothendieck's construction (and bration).

• either by multiplying the rows of the second table with those of the rst, which has the eect of duplicating the rows of the rst table as many times as there are rows in the second (in this case we reason on the product of the primary key spaces).

But the situation is simplied if tables have a common key. In this case, left pushforward and right pushforward are equivalent and there is no duplication of rows or new variables created. This is exactly what happens in our case since asset inventories are supposed to include CPE IDs. Table reconciliation therefore occurs naturally by matching the foreign keys of the inventories with the primary keys of the CPE dictionary.

List all vulnerable assets

For a CISO or security analyst, one of the most natural queries is to list the vulnerable assets of the IS.

Query 2 (Q2). List all vulnerable assets of a given IS

To process this query, one must rst list the entries in the CMDB whose foreign key (i.e. the CPE attribute) also appears as a foreign key in the CVE table. In category theory terminology, we say that we use a pullback (or ber product), which is one of the many variations of the categorical concept of For assets aected by several vulnerabilities, an additional projection morphism is necessary. We then obtain the set of vulnerable assets denoted by AffectedAssets X .

List all vulnerabilities of the IS

In the same way, it is also useful to list all vulnerabilities aecting a given IS.

Query 3 (Q3). List all vulnerabilities of a given IS

This query, which is a dual of the previous one, consists in keeping only the vulnerabilities from the pullback 3. This list is obtained by using the right projection of DB X × CP E CVE. The resulting set is denoted Vuln X .

List the vulnerabilities aecting an asset

Similarly, it is natural to ask for a list of vulnerabilities aecting a particular asset in the IS. Query 4 (Q4). List the vulnerabilities aecting an asset x ∈ DB X .

To process this query, we have to isolate the pairs (asset, vulnerability) of the same asset x in the pullback 3. We therefore need to reason about the following commutative diagram:

List the assets aected by a vulnerability

From the pullback DB X × CP E CVE, we see that it is also possible to lter the resulting pairs by CVE rather than by asset. This ltering fulls another mission of the CISO (or of any administrator or analyst whether or not they have been mandated to do so): that of monitoring the changes needed to guarantee the logical and physical security of the IS for which he is responsible. This task includes monitoring vulnerabilities likely to aect the IS, and in practice begins by consulting the security alerts issued by the CERT (to which every CISO is in principle a subscriber). Each alert contains one or more CVE entries on a given subject. When a CISO becomes aware of a vulnerability, he has to ask themselves whether the IS is aected, with the level of attention weighted by its CVSS score. Assuming that the new vulnerability is added to ICAR, we therefore have the following Q5 query, dual to Q4 : Query 5 (Q5). List the assets aected by a vulnerability y ∈ CVE. This query is processed by choosing from DB X × CP E CVE the pairs corresponding to the vulnerability y we are looking for, which we note DB X × CP E y (i.e. as many pairs as assets impacted by y).

The same applies to the resulting commutative diagram, which is a pullback, and by combining Q4 with Q5 we obtain the pair (x, y) giving the vulnerability y of the asset x, that is useful for consulting the remediation status of a vulnerability to be treated (is it xed, in progress, scheduled...?).

x × y As we saw with Q1, pullback can be used to assign a set of row-IDs to a schema element, which seems to do the trick. However, we need an additional ingredient to lter on the values taken by the entries in the CVSS score column. Indeed, migration functors dened above do not operate in the context of schema morphism, but in that of type morphism. We therefore need a notion of typing. Denition 9 (Typing). Let S be a schema and A a discrete category (i.e. a category containing only objects and identity morphisms) composed of attribute names. A typing for S is a triplet (A, i, γ) where i is a functor from A to S mapping each attribute to its vertex, and γ is a functor from A to Set, mapping each attribute to its type.

Then, i reects the pairing of the knowledge graph's vertices with the attributes of A and γ reects the assignment of the attributes of A to their type. Consequently, we call a typed instance a pair (I, δ) where I : S → Set is an instance together with a natural transformation δ : Intuitively, δ reects the assignment of a type to each ID in I. Typically, this could be the assignment of a string type or a oat type, but more generally it can be any type. Now, as Spivak points out [START_REF] Spivak | Functorial data migration[END_REF], if we go back to pulback, we see that it is possible to adapt migration functors to type-change functors. Denition 10 (Type-change functor). Let S be a schema and k : A → B a morphism of typing instances. We refer to the induced functors ∆k : S -Inst /A → S -Inst /B and Σk , Πk : S -Inst /A → S -Inst /B as type-change functors. ∆k , Σk and Πk are respectively called the pullback, the left pushforward and the right pushforward type-change functor.

I • i ⇒ γ. A i / / γ $ $ S Set (a) Typed schema A ⇐ δ i / / γ $ $ S I z z Set (b) Typed instance
In the context of Q8, we are therefore dealing with a morphism of typing instances which associates a subtype B with the predened type A = [0.0, 10.0] ⊃ B.

Measuring the attack surface of an IS

The attack surface is a summary of the weak points in a IS that an attacker can exploit to gain access and carry out malicious actions. The more weak points there are, the greater the attack surface and the greater the risk of being attacked. Measuring the attack surface therefore makes it possible to assess the barriers an attacker needs to overcome to exploit the weakness.

Query 7 (Q7). Measuring the attack surface of an IS X.

There are a thousand and one ways of dening the attack surface of an IS, and just as many ways of measuring it once it has been dened. One of the simplest denitions is based on the CVSS scores of the vulnerabilities present in the IS. From that point on, the attack surface can be measured in dierent ways, bearing in mind that the CVSS standard is itself a system of metrics based on three metric groups [START_REF]Vulnerability Metrics[END_REF] 4 .

The simplest indicators are :

(i) the list of assets aected by a vulnerability with their associated CVSS score (as many weak points exploitable by an attacker) ;

(ii) the sum of the assets aected by a vulnerability weighted by their CVSS score.

Formally, indicator (i) corresponds to the set of pairs {(DB X -ID, CV SS-ID)} for any asset DB X -ID and for any score vulnerability CV SS -ID. 4 Base, Temporal, and Environmental. The base metrics produce a score ranging from 0 to 10, which can then be modied by scoring the temporal and environmental metrics. In addition to the base score, the CVSS standard is made up of two other groups of measures: temporal scores and environmental scores. The latter are not provided by the NVD, either because they change over time due to events external to the vulnerability (temporal scores), or because they refer to impacts that are relative to the organisation (environmental scores). CV SS summarises as a simple list the mapping of possible entry points for a potential attacker, with their associated criticality.

Seen as the product of DB X and CV SS, DB X × CP E CV SS can then be used to dene the synthetic indicator (ii). Assuming that the assets aected are of equal importance, the synthetic attack surface indicator, AttackSurface, is easily obtained as the sum of the CVSS scores projected into the list on the right:

AttackSurface := (x,y)∈DB X × CP E
CV SS

right(x, y)

We note that, despite their equal importance, vulnerable assets do not involve equally important threats (as attack media). Not only do the assets aected dier in the severity of their vulnerabilities, but they can also dier in the number of vulnerabilities aecting them, and it is not uncommon for an asset to accumulate vulnerabilities. For example, Gitlab 15. It should be noted that, in all cases, the attack surfaces thus dened on the basis of CVSS metrics cannot be interpreted as measures of risk 5 . In risk analysis, risk is always the product of a threat, a vulnerability and a severity.

ICAR lacks far too much information to be used as a basis for risk analysis, both in terms of business analysis (business values, feared events, impact of damage suered) and threat analysis (sources of risk, attractiveness of the IT target, etc.). CVSS metrics can only measure the severity of vulnerabilities, which is only one component of risk.

List vulnerabilities that can be exploited by a technique or tactic

We now turn to the long paths to examine how vulnerability management is linked to threat management. This link is bidirectional: top-down and bottom-up. We start with the top-down approach. It is natural to ask what vulnerabilities can be exploited by a given technique pursuing a given tactic.

This approach makes it possible to map the dangers corresponding to the dierent tactical stages of the kill chain, which is useful for organisation's defenders, who can prioritise vulnerabilities to be remedied, and for its adversaries, who can investigate their attacks. For example, at the start of an attack, the adversaries apply one or more reconnaissance techniques. They may, for example, target a website or an active directory with the aim of compromising accounts, creating accounts, obtaining capabilities (resource development tactics) or even taking their attack a step further with initial access tactics (remote access to the network, installation of a passive listening system, etc.). The list of vulnerabilities that can be exploited by this tactic can then enable the defender to be more vigilant about the assets that 5 As the NVD also points out, "CVSS is not a measure of risk" [?] Denition 11 (Sieve). Let v be a technique or a tactic. A sieve on v is a collection S of morphisms such that :

1

. e ∈ S ⇒ cod(e) = v, 2. (e ∈ S ∧ cod(f ) = dom(e)) ⇒ e • f ∈ S.
In other words, a sieve on an object A in ICAR is a collection of arrows of codomain v closed by precomposition of morphisms in ICAR. However, this denition does not correspond exactly to Q8. On the one hand, the universal aspect of the collection of arrows is missing, as we are looking for the list of all vulnerabilities that can be exploited by a technique or tactic. This universality property is provided by the notion of maximal sieve. Denition 12 (Maximal sieve). A sieve S on v is said to be maximal (or principal) if it contains all the arrows of codomain v. It is denoted ↑ v.

On the other hand, the resulting sieve has too many arrows, since it includes all the precompositions of v-target morphisms. However, what counts for Q8 are only the CVE-domain arrows. To subtract the other arrows (i.e. arrows of CWE, CAPEC or Sub-technique domain), we need a notion of differential sieve. Let S be a sieve on v in ICAR and S ′ a sieve on v in ICAR', where ICAR' is the subcategory of ICAR without CVEs.

In other words, ICAR' consists of the sub-collection of objects from ICAR such that Ob(ICAR ′ ) = Ob(ICAR) -{w ∈ CV E}, and the subcollection of morphisms of ICAR such that Mor(ICAR ′ ) = Mor(ICAR) -{e ∈ Mor(ICAR)|src(e) ∈ CV E}. In this context, the object satisfying Q8 for techniques is the dierential sieve S T = S\S ′ . S T therefore contains all the arrows whose domain is the set Techniques and whose codomain is the set CVE. To give a clearer idea, gure 5 represents the construction stages of Q8 for technique T1499 (Endpoint Denial of Service), from the subcategory extracted "under technique T1499" (a), to the maximum sieve on T1499 (b), and nally to the dierential sieve (c) answering to Q8. be exploited by a tactic. All we have to do is point the sieve construction S T A to the tactic(s) we want, for example to tactic TA0040 (Impact), which is the tactic performed by technique T1499.

List techniques and tactics related to a vulnerability

We now turn our attention to the bottom-up approach. From the point of view of the defender, who knows his IS, it is natural to ask what attack techniques (and therefore tactics) are associated with its vulnerabilities. This knowledge enables them to focus on the vulnerabilities deemed most dangerous from the point of view of their tactical exploitation. This knowledge is also useful for the adversary if he knows some of the targeted assets or even in the absence of any information about the attacked IS. We therefore have query Q9: Query 9 (Q9). List techniques and tactics related to a vulnerability This is essentially the dual request of Q8. Since category theory is an ideal framework for studying all kinds of dualities, we just have to do use dual notions of predened notions. We thus introduce a notion of cosieve. Denition 13 (Cosieve). Let v be a vulnerability. A cosieve on v is a collection coS of morphisms such that :

1. e ∈ coS ⇒ dom(e) = v, 2. (e ∈ coS ∧ dom(f ) = cod(e)) ⇒ f • e ∈ coS.

We then dene the notions of maximal cosieve and dierential cosieve as before. The dierential cosieve coS T A corresponding to Q8 is then given by the complement of the cosieve on v whose target is not a tactic: coS T A = C coS coS ′ = coS\coS ′ , where coS and coS ′ are cosieve on a vulnerability v in ICAR and ICAR' respectively. coS T A is the collection of arrows with source v and target T actics. The construction is the same for techniques. Simply dene the set ICAR ′′ = ICAR ′ -T echniques and repeat the reasoning from the cosieves in ICAR' and ICAR. The "threat surface" is the set of techniques (or tactics) that an attacker can use to exploit the vulnerabilities of an IS. The threat surface is the counterpart of the attack surface on threat management 6 .

Query 10 (R10). Measuring the threat surface of IS X Formally, the threat surface is a simple extension of the dierential cosieve used to list the techniques and tactics associated with a vulnerability. We just need to apply the dierential cosieve to all the vulnerabilities in the IS, i.e. to the set Vuln X .

Conclusion and future work

The aim of this article was to provide a mathematical foundation for common queries in cybersecurity management. The proposed ICAR categorical model thus covers vulnerability management, threat management and asset management in a unied framework. However, ICAR is not a method for enriching cybersecurity ontologies. In particular, it does not allow us to investigate the relations between vulnerability management and threat management. In this sense, the empirical results of the queries examined here are dependent on the quality of the data they use. Our model therefore underlines the importance of work aimed at more nely meshing the various dictionaries of the NIST and the MITRE corporation. Generally speaking, it is clear that query and visualisation models will be enhanced by AI-based works mentioned above.

This article only gives an overview of possible queries for cybersecurity operations. Others could naturally have been envisaged, such as the search for the shortest attack path (i.e. the path with the fewest breaches to exploit).

Other queries will be considered later on. Future work will also address the algorithmic design of queries. In this sense, ICAR model should also be seen as a mathematical foundation for establishing a database schema compatible with the dened categorical schema and associated categorical notions. In other words, the queries dealt with in this article will subsequently be extended in terms of query language (SQL). The aim is to provide a bidirectional dictionary between conceptual categorical queries and database queries.

1

  From a general perspective, the research eorts strive to integrate several repositories: the Common Platform Enumeration (CPE) listing IT assets, the Common Vulnerabilities and Exposures (CVE) listing discovered vulnerabilities, the Common Weakness Enumeration (CWE) listing commonly appearing weaknesses, the MITRE ATT&CK framework listing Adversary Tactics and Techniques (ATT) and the Common Attack Pattern Enumeration and Classication (CAPEC) which helps facilitate attack identication and understanding. The latter repository thus acts as a bridge connecting vulnerability management and threat management. On this basis, research work has explored several avenues.

Figure 1 :

 1 Figure 1: Representation of the security knowledge graph

  Let S := (G, ≃) a categorical schema where G := (V, E, src, tgt) is a graph. An instance I on S is given by 1. a set I(v) for any vertex v ∈ V ; 2. a function I(e) : I(v) → I(v ′ ) for any arrow e : v → v ′ ;

  3:a:microsoft:internet_explorer:8.0.6001:beta:*:*:*:*:*:* VM008 cpe:2.3:a:vmware:vcenter_server:6.0:3b:*:*:*:*:*:* LB001 cpe:2.3:h:f5:big-ip_10250v:-:*:*:*:*:*:*:* OS007 cpe:2.3:o:linux:linux_kernel:2.6.39:*:*:*:*:*:*:* OS008 cpe:2.3:o:paloaltonetworks:pan-os:8.1.16:*:*:*:*:*:*:*

Figure 2 :

 2 Figure 2: Knowledge schema with inventory of assets

  e. a functor) F : S → T . Migration functors follow. Denition 7 (Migration functors). Let S and T be two schemas, S -Inst and T -Inst instances on S and T respectively, F : S → T a schema morphism and I ∈ T -Inst : T → Set. Then the composite functor S F -→ T I -→ Set lives in the S-instance (I • F ∈ S -Inst) and we dene the functor ∆ F such that ∆ F : T -Inst → S -Inst (2)

8 (Figure 3 :

 83 Figure 3: Pullback od DB X and CPE

  It turns out that this diagram also denes a pullback, by virtue of the pullback propagation theorem. Consider the following diagram: such that the commutative square on the right-hand side is a pullback. It follows that that of the left-hand side is also a pullback, and consequently the entire commutative diagram. The set x × CP E CVE thus satises Q4 by providing all vulnerabilities impacting asset x.

6

 6 List vulnerabilities by criticalityIn cybersecurity, vulnerabilities are not of equal importance. There is a tendency to focus on the most severe vulnerabilities. It is not uncommon for a CISO to plan enhanced monitoring for critical vulnerabilities. Typically, he may request a regular report on vulnerabilities with a score of 9 or more (in CVSS v3.0 notation), or more generally with a score within a range S ⊂ [0.0, 10.0]. Query Q6 follows. Query 6 (Q6). List vulnerabilities by CVSS score s ∈ S ⊂ [0.0, 10.0].

Figure 4 :

 4 Figure 4: Typing

Figure 6 /Figure 6 :

 66 Figure 6: Construction of Q9 for techniques associated with vulnerability CVE-2006-5268

•

  Common Attack Pattern Enumeration and Classication (CAPEC) enumerates and classies attack patterns to facilitate the identication and understanding of attacks. The attack patterns have a tree structure, i.e. they are organised into categories and sub-categories of attacks. They allow the ATTs to be linked to CWE weaknesses.

Table 1 :

 1 6 (Categorical normal form). A database is said to be in categorical normal form if 1. any table t has a single primary key column ID t xed at the beginning; 2. any entry belonging to a column c ∈ t refers to a primary key in a single table t ′ , which is denoted by p c : t → t ′ ;3. any database equivalence between two relations p c , q c : t → t ′ must be declared as a path equivalence in the corresponding categorical schema, i.e. p c ≃ q c . Extracts of ICAR entries. The CPE dictionary is formatted on the following scheme

				CPE
	ID
	240.99_kindle_books_project:240.99_kindle_books
	@nubosoftware/node-static_project:@nubosoftware/node-static
	@thi.ng/egf_project:@thi.ng/egf
	gwa_autoresponder_project:gwa_autoresponder
	01org:tpm2.0-tools
				CVE		CVSS
	ID		CWE	CPE		CVSS	ID
	CVE-2023-1684	CWE-434 NA*		2.1	6.8
	CVE-2023-28371 CWE-22 Stellarium:Stellarium 4.3	6.9
	CVE-2023-21038 NA*	NA*		9.5	7.0
	CVE-2023-21039 NA*	NA*		2.1	7.1
	CVE-2023-21032 NA*	NA*		4.1	7.2
				CWE
	ID	ChildOf ParentOf		CAPEC
	CWE-787 119		121-124		NA*
	CWE-79	74		80,81,83-87,692		63,85,209,588,591,592
	CWE-89	943		564		7,66,108-110,470
	CWE-20	707		179,622,1173,1284-1289 3,7-10,13,14,22-24...
	CWE-125 119		126,127		540
				CAPEC
	ID	ChildOf ParentOf CWE	Techniques
	CAPEC-698 542	-	507,829 1027,1176,1505,1587
	CAPEC-699 651	-	1300	1111
	CAPEC-700 161	-	284	1599
	CAPEC-701 94		-	294,345 1557
	CAPEC-702 180	-	1296	1574
			Techniques		Tactics
		ID	Tactics		ID
		T1548 TA0004,TA0005	TA0043
		T1134 TA0004,TA0005	TA0042
		T1531 TA0040		TA0001
		T1087 TA0007		TA0002
		T1098 TA0003		TA0003

To x ideas, we represent in the tables 1 an extract of ICAR, where appear at the time of writing the most salient added or updated entries, among more than 20,000 CPE, about 176,000 CVEs, 668 CWEs, 559

CAPECs, 193

Techniques and 14 Tactics.

It is dicult not to make a connection with a database schema, as we suggested above. It is indeed possible to see an arrow e ∈ E ∈ G ∈ C as a relation linking the table identied by src(e) with a table identied by tgt(e). For example, the arrow CWE → CAPEC expresses that the table CWE points to the table CAPEC, i.e. entries that have a primary key in CWE are related to entries that have a primary key in CAPEC, via the secondary keys found in the CAPEC column of the table CWE.

At this point we can see that the database schema is not in normal form, since the attribute values are not necessarily atomic (so a weakness frequently has several parents and several CAPECs). Strictly speaking, we should decompose the database schema so as to express it in rst normal form. In fact, we do not need this normalization in this study because it would unnecessarily transform the resource ICAR by adding redundancy. We do, however, need a normal form to check the consistency of ICAR. This leads us to a concept of categorical normal form.

Denition cpe:<cpe_version>:<part>:<vendor>:<product>:<version>: <update>:<edition>:<language>:<sw_edition>:<target_sw>:<target_hw>:<other>.

  This is indeed what CMDBs suggest, which normally provide for each component added to the database as a primary key a foreign key CPE as illustrated in table 2.

Table 2 :

 2 Extract columns ID and CPE from a CMDB CMDB can thus be connected to ICAR via the CPE attribute. It can be noted that this correspondance is surjective (each CPE reference refers to at least one asset in the CMDB) but not necessarily injective since a CMDB can have several assets with the same CPE 2 . And nally, it is possible to complete the knowledge schema C of which ICAR is the instance, which is represented in gure 2 by noting DB X the inventory of assets from the CMDB of SI X.

					isChildOf	isChildOf	isSubT echniqueOf
			CV SS
			Has		Has
			CV E	Has	CW E	CAP EC	Has	T echnique
			Has		Has		accomplishesT actic
	DB X	Has	CP E		isP arentOf	isP arentOf	T actic

  It is obtained from the schema morphism CV E

					has --→ CV SS and the pullback
	CP E DB X ×	CV E previously dened as follows:
		DB X × CP E O O CV SS	has / / CV SS O O
		has		has
		CP E DB X ×	CV E	has	/ / CV E
		has		has
		DB X	has	/ / CP E
	The product DB X × CP E

  X data set connected to DB X must be added to the ICAR resource. In this case, it is sucient to repeat the previous developments by reasoning about the pullback IM P T X × CP E CV SS :

	8.0 has vulnerabilities CVE-2022-3411, CVE-2022-4138, CVE-2022-3759 and CVE-2023-0518, the last three of which are of high severity. These indicators obviously give a simplistic view of attack surfaces as they actually characterise IT systems. In reality, the assets of an IS do not have the same sensitivity for a variety of reasons: some assets are exposed to the Internet, others are not; some are in production, others in pre-production, de-velopment, decommissioning, etc.; some are constrained to high availability, others are not, etc. However, it is possible to take into account the impor-tance of assets by adding a sensitivity criterion. This criterion is generally incorporated into CMDBs, which include a "CI Importance" property for this purpose, in line with ITIL architecture. If aected assets are of unequal importance, then each asset must be weighted by an importance indicator, CP E CV SS DB X × CP E CV SS has o o has / / CV SS IM P T X × CP E CV E has O O has DB X × CP E CV E has o o has / / has O O has CV E has O O has i.e. a new IM P T IM P T X × IM P T X DB X has o o has / / CP E

It may be noted that the DSL approach adds an ontological layer to the ontology already at work in the MITRE and NIST repositories.

The threat surface is strictly speaking an attack surface, but since this name is usually used to describe the vulnerabilities of the IS, we use the term "threat surface"

Obviously, the reasoning is the same for the list of vulnerabilities that can