# Testing Abnormality of a Sequence of Graphs: Application to Cybersecurity

Clarisse Boinay, Christophe Biernacki, Cristian Preda, François Foyer

<figure><img src="image_1.png" /></figure>

## To cite this version:

Clarisse Boinay, Christophe Biernacki, Cristian Preda, François Foyer. Testing Abnormality of a Sequence of Graphs: Application to Cybersecurity. 2024. hal-04868124

HAL Id: hal-04868124

https://inria.hal.science/hal-04868124v1

Submitted on 6 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

# Testing Abnormality of a Sequence of Graphs: Application to Cybersecurity

C. Boinay¹, C. Biernacki², C. Preda³, F. Foyer⁴

¹ Seckiot & Inria, ² Inria & U. Lille, ³ U. Lille & Inria ⁴ Seckiot

Juin 2024

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

Université
de Lille

<figure><img src="image_9.png" /></figure>

SECKIOT

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>
<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

# Outline

1. Graphs in OT

2. Testing graph abnormality

3. Application to laboratory data

4. Ongoing & Future Works

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>
<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

Operational Technology (OT)

* Part of modern **critical infrastructures** such as water treatment plants, oil refineries, power grids, and nuclear and thermal power plants

* Composed of **heterogeneous and complex components**: sensors and actuators, programmable logic controllers, supervisory control and data acquisition and human-machine interface

It is thus essential, but also challenging, to preserve OT from malicious actions (**attacks**)

<figure><img src="image_36.png" /></figure>
# Attacks in OT: Stuxnet as a game-changer

<figure><img src="image_37.png" /></figure>

Stuxnet: 1st attack of an industrial system (Iranian nuclear power plant)

* Multiplication of the attacks since Stuxnet

* Stuxnet has shown that isolation of the network isn't enough to prevent attack

<figure><img src="image_38.png" /></figure>
<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

Standard approaches to detect an attack

* Solutions in IT (Information Technology) not sufficient to stop OT attacks (Raman, Ahmed et Mathur 2021)

* Firms use attacks history signature-based methods (Umer et al. 2022), but

* What happens with a *novel type of attack*?

* What happens if the *signature* is not well-chosen?

* Anomaly detection is the most efficient to stop a new attack since it can detect deviation of the normal behaviour (Raman, Ahmed et al. 2021)

Thus we focus on *signature-free anomaly detection...*

<figure><img src="image_43.png" /></figure>
A way to see anomalies in the network: the graph

According to Neil et al. 2013, an attack in a network don't happen in isolation, but implies **an increase of communication** between multiple endpoints. Modeling the network with a graph allows to see such anomalies.

Typical behaviour are:

- Exploration of the attacker: a **star** in the graph

- Lateral movement: a **directed path** in the graph

Possible modeling:

- a node = an IP address

- a packet sent = an edge

<figure><img src="image_44.png" /></figure>
<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

Illustrating star and path

<figure><img src="image_49.png" /><figcaption>Normal graph (left), graph with a path (middle), graph with a star (right)</figcaption></figure>

<figure><img src="image_50.png" /></figure>

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>

<figure><img src="image_55.png" /></figure>
Graph anomaly detection in cybersecurity, a sparkling
subject

■ OT: up to our knowledge, no graph anomaly detection

■ IT: graphs have been already used, for instance:

■ Calls of binary functions (Cohen, Yger et Rossi Nov 2021)

* Stream of messages sent between IP addresses (in classification see Xiao et al. 2020; Abou Rida, Parrend et Amhaz 2021, in unsupervised learning with community detection, auto-encoder, scan statistics and edge streaming based on node embedding through random walk (see Ding et al. 2012; Neil et al. 2013; Leichtnam et al. 2020, Paudel et Huang 2022)

* But only one statistical work to test if there is an anomaly (Neil et al. 2013), otherwise **poor statistical framework...**

<figure><img src="image_56.png" /></figure>
<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>

<figure><img src="image_59.png" /></figure>

<figure><img src="image_60.png" /></figure>

# Outline

1. Graphs in OT

2. Testing graph abnormality

3. Application to laboratory data

4. Ongoing & Future Works

<figure><img src="image_61.png" /></figure>

<figure><img src="image_62.png" /></figure>

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>

<figure><img src="image_65.png" /></figure>

<figure><img src="image_66.png" /></figure>
# Our data: dynamical graphs of counting

* $N$ IP addresses communicate over a time $[0, T]$ at different times $t \in [0, T]$ by sending messages

* $[0, T] = \cup_{i=1}^n I_i$ divided into $n$ intervals of equal length $\Delta_t$

* Only the number of messages is recorded for each $I_i$

* The aggregated data is $G = (G_i)_{1 \le i \le n}$ where $G_i = (N, \mathcal{E}_i)$ with the set of nodes $N = \{1, \dots, N\}$ and $\mathcal{E}_i$ the list of (possibly duplicated) edges which send messages during $I_i$

* Equivalently to the $G_i$s, we can construct the adjacency matrices $X^i$s such that $\forall 1 \le k, l \le N, X_{k,l}^i$ is the number of messages sent by the IP address $k$ to the IP address $l$

<figure><img src="image_67.png" /></figure>
<figure><img src="image_68.png" /></figure>

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /></figure>

<figure><img src="image_71.png" /></figure>

Justifying aggregation

Aggregating a Markov chain implies a quick loss of dependence between the aggregated time series. Independence of the aggregated values implies the **independence of the dynamical graphs of counting**, simplifying then the analysis.

Aggregating the communication over $\Delta_T$ ables to detect the increase of communication, **specifically to the dynamicity $\Delta_T$**

Aggregating the instantaneous graphs ables to see the **paths and the star in the same aggregated graph** (agnostic representation).

<figure><img src="image_72.png" /></figure>

<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /></figure>

<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /></figure>

<figure><img src="image_77.png" /></figure>
<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

Big picture

<figure><img src="image_82.png" /></figure>

For a time step $\Delta t$

Which distribution in the network space?

<figure><img src="image_83.png" /></figure>

<figure><img src="image_84.png" /></figure>

<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /></figure>

<figure><img src="image_89.png" /></figure>
## Our solution for testing abnormality of a graph

We assume that the normal graphs are independent and identically distributed.

1. Learn a normal behaviour (distribution $P_0$) over a sequence of graphs $G = (G_i)_{1\le i\le n}$ with a flexible family $\mathcal{F}$ of probability distributions such that $P_0 \in \mathcal{F}$

2. Test if a new graph $G_i$ has the normal behaviour ($i \ge n+1$)

$$ \begin{cases} H_0 : G_i \sim P_0 \\ H_1 : G_i \not\sim P_0 \end{cases} $$

### Test Statistics

Compute the distribution of the log-likelihood $L_0$ of the distribution $P_0$ to get a pvalue of $L_0(G_i)$

<figure><img src="image_90.png" /></figure>
<figure><img src="image_91.png" /></figure>

<figure><img src="image_92.png" /></figure>

<figure><img src="image_93.png" /></figure>

<figure><img src="image_94.png" /></figure>

Choosing between different competitors

Retain the distribution family $\mathcal{F}$ which products the greater power for a given alternative distribution $\mathbb{P}_1$ ($i > n$)

$$H_1 : \mathcal{G}_i \sim \mathbb{P}_1$$

The distribution $\mathbb{P}_1$ represents a kind of attack, thus different scenarios to be tested...

<figure><img src="image_95.png" /></figure>

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>

<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>
# A generic candidate: the Stochastic Bloc Model

## What is the Stochastic Bloc Model?

- A mixture of probability of *K* latent classes

- A clustering model on graphs with *K* clusters

## Why the Stochastic Bloc Model?

- The state space is the graph: a generic approach to detect anomalies

- We think that any probability of graphs can be approached by a Stochastic Bloc Model by increasing the number of classes *K* as continuous density functions can be approximated by finite mixture of Normal (Nguyen et al. 2020)

## How to compute the Stochastic Bloc Model on multiple graphs?

- We assume the independence of the graphs given the partition

- We have done an adaptation of the Variational Expectation Maximization algorithm (VEM, Mariadassou, Robin et Vacher 2010) to multiple graphs

<figure><img src="image_102.png" /></figure>
# An efficient computation of the Variational Expectation Maximization

## Problem:

- The VEM may be inefficient as it is slow and it can find local maxima

- Spectral methods have been used to initialize the VEM in the undirected and unvalued case (Lei et Rinaldo 2015)

## Our solution:

- **Initialize with a Singular Value Decomposition:** as the partition based on the Singular Value Decomposition has been shown to converge to the SBM in the directed and unvalued case (Sussman et al. 2012), we demonstrate through experimentations, that it converges efficiently also to the SBM in the directed and valued case

<figure><img src="image_103.png" /></figure>
<figure><img src="image_104.png" /></figure>

<figure><img src="image_105.png" /></figure>

<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /></figure>

# Outline

1. Graphs in OT

2. Testing graph abnormality

3. Application to laboratory data

4. Ongoing & Future Works

<figure><img src="image_108.png" /></figure>

<figure><img src="image_109.png" /></figure>

<figure><img src="image_110.png" /></figure>

<figure><img src="image_111.png" /></figure>

<figure><img src="image_112.png" /></figure>

<figure><img src="image_113.png" /></figure>
<figure><img src="image_114.png" /></figure>

<figure><img src="image_115.png" /></figure>

<figure><img src="image_116.png" /></figure>

<figure><img src="image_117.png" /></figure>

Laboratory Data

■ A laboratory of Seckiot

■ 6 hours aggregated into $\Delta_{T} = 1$ minute

■ 5 hours of benign traffic followed by 9 attacks

■ 13 IP addresses

Careful: a test is performed on a controlled system, test on more complex data would be done in the future.

<figure><img src="image_118.png" /></figure>
<figure><img src="image_119.png" /></figure>

<figure><img src="image_120.png" /></figure>

<figure><img src="image_121.png" /></figure>

<figure><img src="image_122.png" /></figure>

# Interpretability of the abnormality

Two other statistics of test:

- Degree-out

- Log-likelihood of the edges

→ We learn the distribution of such statistics over the learning dataset and compute the pvalues of each degree-out and log-likelihood of edges

<figure><img src="image_123.png" /></figure>
<figure><img src="image_124.png" /></figure>

<figure><img src="image_125.png" /></figure>

<figure><img src="image_126.png" /></figure>

<figure><img src="image_127.png" /></figure>

Detection of the attacks and interpretability

<table><thead><tr><th>Attack</th><th>pvalue of L<sub>0</sub></th><th>Abnormal nodes (α = 0.027%)</th><th>Abnormal edges (α = 0.027%)</th></tr></thead><tbody><tr><td>ping sweep</td><td>12.66%</td><td>1</td><td>12</td></tr><tr><td>ARP scan</td><td>9.5%</td><td>0</td><td>6</td></tr><tr><td>overwrite registers</td><td>0%</td><td>2</td><td>6</td></tr><tr><td>get PLC info</td><td>11%</td><td>2</td><td>2</td></tr><tr><td>replay authent</td><td>0%</td><td>2</td><td>2</td></tr><tr><td>scan port modbus</td><td>9.9%</td><td>1</td><td>6</td></tr><tr><td>man in the middle</td><td>1.8%</td><td>1</td><td>0</td></tr><tr><td>restart PLC</td><td>0%</td><td>1</td><td>2</td></tr><tr><td>stop PLC</td><td>9.9%</td><td>2</td><td>2</td></tr></tbody></table>

<figure><img src="image_128.png" /></figure>

<figure><img src="image_129.png" /></figure>

<figure><img src="image_130.png" /></figure>

<figure><img src="image_131.png" /></figure>

<figure><img src="image_132.png" /></figure>

<figure><img src="image_133.png" /></figure>

<figure><img src="image_134.png" /></figure>
# Analysis of the result

## True positives on the test set

- Some attacks have a low pvalue for the statistic log-likelihood of the graph

- With further analysis, we can say that abnormal nodes or edges are rightfully detected

- For each attack, there is at least one true positive of one of the three statistics

## False Positive Rate for each of the statistics on the validation set:

- Log-likelihood of the graph: 0% ($α = 0.027%$)

- Degree-out: 0% ($α = 0.027%$)

- Log-likelihood of the edges: 0% ($α = 0.027%$)

<figure><img src="image_135.png" /></figure>
<figure><img src="image_136.png" /></figure>

<figure><img src="image_137.png" /></figure>

<figure><img src="image_138.png" /></figure>

<figure><img src="image_139.png" /></figure>

# Outline

1. Graphs in OT

2. Testing graph abnormality

3. Application to laboratory data

4. Ongoing & Future Works

<figure><img src="image_140.png" /></figure>

<figure><img src="image_141.png" /></figure>

<figure><img src="image_142.png" /></figure>

<figure><img src="image_143.png" /></figure>

<figure><img src="image_144.png" /></figure>

<figure><img src="image_145.png" /></figure>
<figure><img src="image_146.png" /></figure>

<figure><img src="image_147.png" /></figure>

<figure><img src="image_148.png" /></figure>

<figure><img src="image_149.png" /></figure>

# A changing set of nodes over time

**Problem:** in various situations, the IP addresses can change, new equipments are installed, internet IP addresses appear or disappear in the network

**Solution:** the SBM can be adapted to this case through the *missing value setting*. A node which disappears is said to be missing. A node appearing was said to be missing. **The test doesn't change.**

<figure><img src="image_150.png" /></figure>

<figure><img src="image_151.png" /></figure>

<figure><img src="image_152.png" /></figure>

<figure><img src="image_153.png" /></figure>

<figure><img src="image_154.png" /></figure>

<figure><img src="image_155.png" /></figure>
<figure><img src="image_156.png" /></figure>

<figure><img src="image_157.png" /></figure>

<figure><img src="image_158.png" /></figure>

<figure><img src="image_159.png" /></figure>

Ongoing works

■ Search for the *rightful time step of aggregation*: try different values of split $\Delta_t$. An attack might not be seen for any $\Delta_t$

■ Interpretability of the classes: what is the link between the VLAN and the clusters of IP addresses

<figure><img src="image_160.png" /></figure>
<figure><img src="image_161.png" /></figure>

<figure><img src="image_162.png" /></figure>

<figure><img src="image_163.png" /></figure>

<figure><img src="image_164.png" /></figure>

Thank you for your attention

<figure><img src="image_165.png" /></figure>

<figure><img src="image_166.png" /></figure>

<figure><img src="image_167.png" /></figure>

<figure><img src="image_168.png" /></figure>

<figure><img src="image_169.png" /></figure>

<figure><img src="image_170.png" /></figure>

<figure><img src="image_171.png" /></figure>
<figure><img src="image_172.png" /></figure>

<figure><img src="image_173.png" /></figure>

<figure><img src="image_174.png" /></figure>

<figure><img src="image_175.png" /></figure>

<figure><img src="image_176.png" /></figure>

Abou Rida, Amani, Pierre Parrend et Rabih Amhaz (2021). "Anomaly Detection for CyberSecurity Using Inductive Node Embedding with Convolutional Graph Neural Networks". In:

Complex Networks and their Applications 2021, 30 novembre - 2 décembre 2021, Madrid, Spain. url: https://hal.archives-ouvertes.fr/hal-03393640.

<figure><img src="image_177.png" /></figure>

Cohen, Roxane, Florian Yger et Fabrice Rossi (Nov 2021). "Adding semantic to level-up graph-based Android malware detection". In:

Complex Networks and their Applications 2021, 30 novembre - 2 décembre 2021, Madrid, Spain. url: https://hal.archives-ouvertes.fr/hal-03393640.

<figure><img src="image_178.png" /></figure>

Ding, Qi et al. (2012). "Intrusion as (Anti)Social Communication: Characterization and Detection". In:

Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining '12. Beijing, China: Association for Computing Machinery, p. 886-894.

isbn: 9781450314626. doi: 10.1145/2339530.2339670. url: https://doi.org/10.1145/2339530.2339670.

<figure><img src="image_179.png" /></figure>

Lei, Jing et Alessandro Rinaldo (fév. 2015). "Consistency of spectral clustering in stochastic block models". In: The Annals of Statistics 43.1. issn: 0090-5364.
doi: 10.1214/14-aos1274. url: http://dx.doi.org/10.1214/14-aos1274.

<figure><img src="image_180.png" /></figure>

Leichtnam, Laetitia et al. (juin 2020). "Sec2graph: Network Attack Detection Based on Novelty Detection on Graph Structured Data". In:

DIMVA 2020: 17th Conference on Detection of Intrusions and Malware, and Vulnerability T. 12223. Lecture Notes in Computer Science. Lisbon, Portugal, p. 238-258. doi: 10.1007/978-3-030-52683-2\_12. url: https://hal.inria.fr/hal-02950489.

<figure><img src="image_181.png" /></figure>

<figure><img src="image_182.png" /></figure>

<figure><img src="image_183.png" /></figure>

<figure><img src="image_184.png" /></figure>

<figure><img src="image_185.png" /></figure>

<figure><img src="image_186.png" /></figure>

<figure><img src="image_187.png" /></figure>

<figure><img src="image_188.png" /></figure>

<figure><img src="image_189.png" /></figure>

<figure><img src="image_190.png" /></figure>

<figure><img src="image_191.png" /></figure>

<figure><img src="image_192.png" /></figure>

<figure><img src="image_193.png" /></figure>

<figure><img src="image_194.png" /></figure>

<figure><img src="image_195.png" /></figure>

<figure><img src="image_196.png" /></figure>
<figure><img src="image_197.png" /></figure>

Mariadassou, Mahendra, Stéphane Robin et Corinne Vacher (2010). "Uncovering latent structure in valued graphs : A variational approach". In : The Annals of Applied Statistics 4.2, p. 715-742. doi : 10.1214/10-A0AS361. url : https://doi.org/10.1214/10-A0AS361.

<figure><img src="image_198.png" /></figure>

Neil, Joshua et al. (2013). "Scan Statistics for the Online Detection of Locally Anomalous Subgraphs". In : Technometrics 55.4, p. 403-414. doi : 10.1080/00401706.2013.822830. eprint : https://doi.org/10.1080/00401706.2013.822830. url : https://doi.org/10.1080/00401706.2013.822830.

<figure><img src="image_199.png" /></figure>

Nguyen, T. Tin et al. (jan. 2020). "Approximation by finite mixtures of continuous density functions that vanish at infinity". In : Cogent Mathematics amp; Statistics 7.1. Sous la dir. de Lishan Liu, p. 1750861. issn : 2574-2528. doi : 10.1080/25742558.2020.1750861. url : http://dx.doi.org/10.1080/25742558.2020.1750861.

<figure><img src="image_200.png" /></figure>

Paudel, Ramesh et H. Howie Huang (2022). "Pikachu : Temporal Walk Based Dynamic Graph Embedding for Network Anomaly Detection". In : NOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium, p. 1-7. doi : 10.1109/NOMS54207.2022.9789921.

<figure><img src="image_201.png" /></figure>

Raman, Gauthama, Chuadhry Mujeeb Ahmed et Aditya Mathur (2021). "Machine learning for intrusion detection in industrial control systems : challenges and lessons from experimental evaluation". In : IEEE Transactions on Industrial Informatics. doi : 10.1186/s42400-021-00095-5.

<figure><img src="image_202.png" /></figure>
<figure><img src="image_203.png" /></figure>

Sussman, Daniel L. et al. (2012).

A consistent adjacency spectral embedding for stochastic blockmodel graphs.

arXiv: 1108.2228 [id='stat.ML'] fullname = 'MachineLearning' isactive = True; name = None; archive = 'stat' is general = Falsedescription = '

Coversmachinelearningpapers(supervised, unsupervised, semi -
supervisedlearning, graphicalmodels, reinforcementlearning, bandits, highdimensionalinferen

<figure><img src="image_204.png" /></figure>

Umer, Muhammad Azmi et al. (2022). "Machine learning for intrusion detection in industrial control systems : Applications, challenges, and recommendations".

In : International Journal of Critical Infrastructure Protection, p. 100516. issn :
1874-5482. doi : https://doi.org/10.1016/j.ijcip.2022.100516. url :
https://www.sciencedirect.com/science/article/pii/S1874548222000087.

<figure><img src="image_205.png" /></figure>

Xiao, Qingsai et al. (2020). "Towards Network Anomaly Detection Using Graph Embedding". In: Computational Science – ICCS 2020 12140, p. 156-169.

<figure><img src="image_206.png" /></figure>