Machine Translated by Google

Un algorithme double­oracle évolutif pour

Jeu de tromperie multi­domaines
Ahmed Bilal Asghar, Ahmed Hemida et Charles Kamhoua Jon Kleinberg
Direction de la sécurité des réseaux L'informatique
Laboratoire de recherche de l'armée DEVCOM Université Cornell

Résumé—Cet article étudie un jeu multicouche représentant un système peut le reconnaître. La théorie de l'hyperjeu, qui modélise diverses perspectives
cyber­physique dans lequel un défenseur doit protéger un ensemble de subjectives des participants dans des conditions d'incertitude, est utilisée par Cho
ressources d'un adversaire. Le défenseur utilise des actions trompeuses dans
et al. [7] pour évaluer l'efficacité des signaux de tromperie défensive pour dissuader
les domaines cyber et physique. Les deux domaines sont interconnectés et
les attaquants. De plus, Wan et al. [8] discutent des stratégies de tromperie basées
les gains des joueurs dépendent de leurs actions dans les deux domaines.
Nous étudions la complexité de ce jeu multi­domaines et utilisons une sur l'hyperjeu pour contrer les attaques de menaces persistantes avancées (APT),
approche à double oracle pour le résoudre, en présentant des programmes exécutées par étapes séquentielles comme indiqué dans le cadre de la chaîne de
linéaires en nombres entiers pour les oracles des joueurs. destruction cybernétique.
En raison de la grande dimensionnalité de l'espace d'action combiné du
L'application de la théorie des jeux aux mécanismes de cyberdéfense,
défenseur, le jeu devient intraitable même pour les réseaux de taille moyenne.
Par conséquent, nous proposons un oracle de défense heuristique pour notamment par le biais de techniques de tromperie, est un axe clé de la littérature
résoudre efficacement les problèmes à grande échelle. Nos simulations sur la cybersécurité [9]–[11]. La théorie des jeux propose une approche structurée
valident que la méthode proposée peut résoudre efficacement les problèmes à grande échelle. les interactions entre attaquants et défenseurs dans des conditions
pour modéliser
Les résultats numériques démontrent qu'en utilisant l'oracle heuristique, le d'incertitude. Différents types de jeux sont utilisés pour étudier différents scénarios
gain du défenseur est, en moyenne, dans les 16 % de la solution optimale
d'attaque/défense. Les jeux bayésiens, un sous­ensemble de la théorie des jeux,
pour des instances de problèmes aléatoires.
sont particulièrement efficaces dans ce domaine, offrant un cadre robuste pour
I. INTRODUCTION développer des stratégies optimales de cyberdéception en tenant compte des
doutes et des erreurs de jugement potentiels de l'attaquant. La théorie des jeux
Il a été démontré que la cyber­tromperie joue un rôle crucial dans la lutte contre
améliore non seulement l'efficacité des stratégies de cyberdéception, mais
les désavantages informationnels auxquels sont confrontés les défenseurs face
contribue également de manière significative à la résilience globale des défenses
à des cybermenaces inconnues [1]. Son objectif principal est de développer des
de cybersécurité [12]. Une nouvelle approche théorique des jeux pour analyser et
tactiques robustes qui améliorent les stratégies défensives en trompant les parties
atténuer les vulnérabilités zero­day a également été introduite dans [13]. De plus,
qui tentent de mener des attaques importantes.
l'interaction entre la théorie des jeux et l'apprentissage automatique dans le
Dans la même lignée que la tromperie physique classique [2], la cyber­tromperie
développement de stratégies de déception défensive est explorée dans [5]. Enfin,
consiste à créer des environnements, des systèmes ou des données conçus pour
un cadre théorique de jeu stratégique pour l'allocation de pots de miel au sein de
tromper les attaquants, redirigeant ou empêchant ainsi leurs actions de cibler des
réseaux tactiques dynamiques, visant à renforcer la cyber­tromperie, est étudié
actifs précieux [3]. Le cœur de la cyber­tromperie est sa nature proactive,
dans [14].
transformant les mécanismes de défense traditionnels en positions de sécurité
dynamiques, imprévisibles et plus résilientes. En incorporant des éléments
Dans certains scénarios, le défenseur et/ou l'attaquant peuvent manquer
trompeurs dans les cadres de cybersécurité, les défenseurs peuvent créer un
d'informations complètes sur l'état du jeu ou sur les actions de l'autre. Des jeux
environnement plus ambigu et plus difficile pour les attaquants, augmentant le coût
stochastiques partiellement observables peuvent modéliser de tels scénarios [15].
et la difficulté de leurs activités malveillantes [4]. Cette stratégie permet non
seulement de détecter les menaces de manière précoce, mais renforce également
la résilience globale du système, en utilisant la désinformation et l'ambiguïté Tromperie physique : Similaire à la cyber­tromperie, la tromperie physique

comme outils de défense [5]. implique la manipulation stratégique des environnements et des ressources
physiques pour tromper les adversaires. En général, elle fait appel à des tactiques

Notre objectif dans cet article sera d’étudier les attaques coordonnées qui se telles que le déploiement d'objets leurres, l'utilisation de camouflage et le placement

déroulent simultanément dans des systèmes couplés cyber et physiques et de stratégique d'informations trompeuses pour créer de fausses perceptions sur les

développer des politiques de tromperie efficaces qui fonctionnent dans ce contexte capacités, les intentions et les ressources précieuses du défenseur [16], [17].

multi­domaines. Pour poser le contexte de cette question, nous examinons d’abord

ce qui a été fait séparément dans les domaines cyber et physique. Attaques : les attaques sur l'intégration des systèmes cyberphysiques (CPS)
exposent les vulnérabilités que les adversaires peuvent exploiter, ce qui pose
Dans la littérature sur la cybersécurité, le concept de tromperie défensive des problèmes de sécurité importants. Les cyberattaques peuvent avoir de graves
théorique des jeux a été largement étudié [5]. Un jeu de tromperie spécifique est répercussions sur les performances du système et ouvrir la voie à des attaques
proposé par Schlenker et al. [6], où le défenseur utilise stratégiquement la physiques plus dévastatrices.
tromperie en fonction des actions de l'attaquant, tandis que l'attaquant peut ne pas Un exemple notable d’une telle attaque a été celui des réseaux électriques
être conscient de la tromperie ou ukrainiens [18], un cadre CPS standard, qui était
Machine Translated by Google

L'attaque a été compromise en 2015 en raison de la disponibilité d'informations Dans le domaine physique, le défenseur déploie une flotte de ressources
open source. L'attaque a commencé par un e­mail de phishing diffusant le physiques, telles que des véhicules terrestres sans pilote (UGV), pour protéger
logiciel malveillant BlackEnergy, permettant un accès non autorisé aux les actifs physiques contre d'éventuelles attaques. Ces ressources physiques
données sensibles et au contrôle du système. Cette violation a conduit à l'arrêt sont placées stratégiquement à divers endroits essentiels à la protection de
à distance des sous­stations et a été suivie d'attaques de logiciels malveillants l'environnement. Cependant, l'efficacité de ces ressources physiques est
qui ont détruit des fichiers critiques et empêché la récupération du système. influencée par leurs systèmes de contrôle, qui résident dans le domaine
Une attaque par déni de service (DoS) ultérieure sur les centres d'appels a cybernétique. Le domaine cybernétique comprend un réseau de nœuds et de
laissé près de 225 000 consommateurs sans électricité pendant plusieurs heures [19].
bords représentant des ordinateurs, des serveurs et d'autres périphériques
Un autre exemple récent est l’attaque par ransomware qui a touché le réseau réseau. Les nœuds contrôlant les ressources physiques sont essentiels, car la
Colonial Pipeline aux États­Unis en avril 2021 [20]. compromission de ces nœuds peut perturber les opérations des ressources
L’intégration de la tromperie dans le domaine physique dans les cadres de physiques qu'ils contrôlent. Par conséquent, la protection de ces nœuds
sécurité améliore la capacité du défenseur à protéger les actifs critiques en cybernétiques est essentielle pour garantir la sécurité des actifs physiques.
augmentant la complexité et l’incertitude auxquelles sont confrontés les
adversaires, augmentant ainsi le coût et le risque de leurs activités malveillantes. L'adversaire opère dans les deux domaines, dans le but d'attaquer
directement les ressources physiques et de compromettre les nœuds
Multidomaine : Dans le paysage de la modélisation de la cybersécurité, en cybernétiques qui les contrôlent. Si l'adversaire parvient à compromettre un
particulier lorsqu’il s’agit d’intégrer des éléments de cyber­tromperie, il est nœud cybernétique, la ressource physique correspondante devient vulnérable,
évident que les jeux joués au sein d’une seule couche ou d’un seul domaine la rendant potentiellement incapable de répondre aux attaques physiques.
ne parviennent pas à saisir la dynamique complexe des scénarios Lorsqu'une ressource physique est directement attaquée, la ressource physique
multidomaines. Les approches mono­couches traditionnelles ne parviennent la plus proche doit réagir pour atténuer l'attaque.
pas à prendre en compte l’interaction complexe entre les domaines cybernétique
et physique, qui est essentielle pour une compréhension holistique des Le défenseur emploie diverses tactiques trompeuses pour renforcer la
menaces de sécurité et des stratégies d’atténuation. Cette insuffisance souligne sécurité. Dans le domaine cybernétique, des honeypots peuvent être déployés
la nécessité d’un modèle multi­domaine qui englobe deux couches distinctes : pour attirer et neutraliser les cyberattaques. Dans le domaine physique, le
l’une représentant l’espace cybernétique et l’autre l’espace physique. Une telle défenseur peut désigner certains agents physiques comme protégés, en les
approche bifurquée permet une simulation et une analyse plus nuancées, dotant de mesures de sécurité avancées pour résister aux cyberattaques. Cela
permettant aux défenseurs de concevoir des tactiques de tromperie plus garantit que ces agents restent opérationnels même si leurs nœuds
sophistiquées et plus efficaces qui couvrent à la fois les spectres numériques cybernétiques de contrôle sont compromis.
et physiques de leurs environnements opérationnels. Par conséquent, cette En intégrant des stratégies dans les deux domaines, le défenseur vise à
évolution vers des modèles multi­domaines marque une étape cruciale dans le créer un mécanisme de défense robuste qui minimise le taux de réussite de
développement de stratégies de cybersécurité complètes. l'adversaire et maximise la protection des actifs précieux. Nous décrivons
maintenant en détail les deux domaines ainsi que les rôles de l'attaquant et du
Nos contributions peuvent être résumées comme suit : défenseur.
• Nous proposons un nouveau cadre pour protéger un système cyberphysique
en tant que jeu de tromperie multi­domaines. Le cadre proposé garantit A. Domaine physique

une tromperie bien coordonnée et cohérente entre les domaines cyber Nous modélisons le domaine physique comme un graphe pondéré G1 =
et physique. • Nous explorons la complexité du jeu (V1, E1), où V1 représente l'ensemble des sommets et E1 l'ensemble des
multicouche développé en montrant que la recherche de l'équilibre de Nash arêtes. Chaque nœud v V1 correspond à un emplacement qui doit être
à l'aide des techniques de pointe existantes échoue même sur les protégé par le défenseur. Chaque nœud v a un poids associé (v), qui signifie
réseaux de taille moyenne. le gain pour l'attaquant s'il attaque avec succès ce nœud. Les arêtes (i, j) E1
sont pondérées par wi,j , représentant la distance entre les nœuds i et j.
• Nous proposons une nouvelle approche pour résoudre le jeu de tromperie
multi­domaines en exploitant l'algorithme du double oracle dans des
environnements multicouches. Nous nous concentrons plus Le défenseur dispose d'une flotte de N agents physiques, tels que des
particulièrement sur les performances de véhicules terrestres sans pilote (UGV), qui sont déployés à des sommets
l'oracle du défenseur. • Enfin, nous évaluons l'évolutivité du jeu proposé. spécifiques {v1, v2, . . . , vN } V1 dans le graphe physique.
Ces agents ont pour mission de protéger les emplacements de l'environnement.
II. ÉNONCÉ DU PROBLÈME
Inversement, un adversaire opère dans le même environnement, dans le but
Dans cet article, nous étudions un scénario multi­domaines dans lequel le d'attaquer ou de compromettre ces emplacements ou ces biens physiques.
défenseur protège un ensemble de ressources contre un adversaire cherchant
à lancer des attaques. Le scénario englobe deux domaines interconnectés : le Lorsqu'un nœud u V1 est ciblé par une attaque, l'agent physique le plus
domaine physique et le domaine cybernétique. Bien que notre scénario soit proche de l'emplacement attaqué est alerté et peut répondre. La probabilité
formulé dans le contexte d'un problème réaliste spécifique, nous l'utilisons d'une attaque réussie est une fonction monotone f de la distance entre le lieu
également plus largement pour démontrer comment nous pensons que des de l'attaque et l'emplacement de l'agent physique répondant. Formellement,
approches multi­domaines peuvent être développées en général.
Machine Translated by Google

la probabilité qu'une attaque sur v V1 soit réussie est donnée par P[attaque sur v domaine cybernétique

réussie] = f(wv,s), où s est l'emplacement de l'agent physique le plus proche, c'est­à­dire.

s = arg minx {v1,v2,...,vN } wx,v. Si une attaque réussit, l'attaquant gagne une récompense

égale au poids du sommet attaqué ; si l'attaque échoue, l'attaquant encourt une pénalité
de capture D. Le gain du défenseur est le négatif du gain de l'attaquant.

B. Cyberdomaine Nous

modélisons le cyberdomaine comme le graphe G2 = (V2, E2), où V2 représente domaine physique

l'ensemble des sommets (nœuds) et E2 représente l'ensemble des arêtes. Dans

le contexte du cyberdomaine, ce graphe représente un cyberréseau où chaque
Fig. 1. Configuration multi­domaine : le plan bleu représente le domaine cybernétique avec
nœud correspond à une entité distincte, telle qu'un ordinateur, un serveur ou un le graphe cybernétique. Le chemin d'attaque est mis en évidence en rouge et un honeypot
périphérique réseau. Les arêtes entre les nœuds indiquent les canaux de est placé sur un bord. Le plan vert représente le domaine physique avec le graphe physique
et les agents physiques. L'agent translucide désigne l'agent protégé.
communication ou les connexions potentielles entre ces entités au sein du réseau.
Les lignes pointillées bleues indiquent quel nœud cybernétique contrôle quel agent physique.

Dans le cyberespace, un sous­ensemble de sommets Ve V2 représente les Dans un scénario pratique, cela pourrait signifier que le défenseur a alloué des
nœuds d'entrée, tandis qu'un autre sous­ensemble Vt V2 représente les nœuds ressources pour mettre en œuvre un chiffrement avancé et des mécanismes
cibles. Les nœuds d'entrée servent de points d'entrée dans l'environnement d'authentification robustes pour les commandes envoyées depuis le nœud

cybernétique, tandis que les nœuds cibles sont les emplacements que l'adversaire cybernétique à ces agents physiques protégés. Cela empêche l'attaquant de les
cherche à compromettre ou à attaquer. désactiver par des moyens cybernétiques. En déployant stratégiquement des
Ces nœuds cibles correspondent aux nœuds qui contrôlent les N agents honeypots dans le domaine cybernétique et en renforçant certains agents
physiques. Pour faciliter la notation, dans cet article, nous supposons que chaque physiques, le défenseur peut créer une stratégie de défense en couches qui
nœud cible contrôle un agent physique, bien que les résultats présentés puissent améliore la sécurité des systèmes physiques et cybernétiques.
être étendus au cas où plusieurs agents physiques sont contrôlés par un nœud actifs.

cible cybernétique. Le nœud ui Vt désigne le nœud cible cybernétique qui

III. MODÈLE DE JEU
contrôle l'agent physique i. Notez que l'agent physique i peut être déployé sur
n'importe lequel des sommets physiques v V1. Nous modélisons le problème discuté dans la section précédente comme un jeu de
forme normale à somme nulle à deux joueurs Γ(N , A, R), où N = {d, a} désigne les deux
L'attaquant peut utiliser un chemin d'attaque depuis un nœud d'entrée dans joueurs, le défenseur et l'attaquant. Les ensembles A = {Ad, Aa} et R = {Rd, Ra}
Ve vers un nœud cible dans Vt pour compromettre l'un des nœuds cibles. représentent respectivement les ensembles d'actions et les fonctions de récompense des
Si un nœud cible ui est attaqué avec succès, l'actif physique i associé à ce nœud joueurs. Nous décrivons ces ensembles en détail ci­dessous.
cible peut être compromis par l'attaquant. Si un agent physique est compromis, il
ne peut pas répondre à une attaque physique et l'un des agents physiques
A. Actions de l'attaquant
restants doit répondre à sa place.
Dans le domaine cybernétique, les actions de l'attaquant impliquent la sélection
d'un des chemins d'attaque depuis les nœuds d'entrée Ve jusqu'aux nœuds cibles
C. Actions trompeuses Vt dans le cybergraphe G2. Ces chemins d'attaque sont représentés par A2 |} où
Afin de protéger les nœuds cybernétiques contre les attaques, le défenseur pj est un chemin d'attaque
un =depuis
{p1, . un
. . ,nœud
p|A2 d'entrée
un
jusqu'à un nœud cible dans
peut déployer jusqu'à h pots de miel sur les bords du réseau cybernétique. Un pot G2. Bien que le nombre de chemins dans un graphe puisse croître de manière
de miel est un système de leurre conçu pour attirer les cyberattaques et les exponentielle avec le nombre de sommets, pour gérer la complexité informatique,
détourner des cibles légitimes. Si une cyberattaque utilise un chemin d'attaque qui nous limitons l'espace d'action de l'adversaire à l'ensemble des chemins d'attaque
passe par l'un de ces pots de miel, le défenseur peut détecter et empêcher la qui se trouvent dans un certain facteur du nombre d'arêtes du chemin le plus court.
compromission de l'agent physique correspondant. Cependant, l'attaquant
poursuivra toujours l'attaque physique. La restriction des chemins en fonction de la longueur des arêtes est justifiée par
l'observation selon laquelle les cyberattaquants optent généralement pour des
Dans le domaine physique, le défenseur peut mettre en œuvre des actions itinéraires raisonnablement directs plutôt que de se promener longuement dans le
trompeuses pour sécuriser davantage le réseau. Plus précisément, le défenseur cybergraphe. Cette approche s'aligne sur des travaux antérieurs, tels que [11], qui
peut désigner n'importe quel g des N agents physiques comme agents définissent les chemins d'attaque dans les cybergraphes à l'aide de critères similaires.
« protégés ». Ces agents protégés sont équipés de mesures de sécurité Il convient de noter que même dans cette hypothèse, le nombre de chemins
supplémentaires pour résister aux cyberattaques, garantissant que même si leur pourrait encore croître de manière exponentielle.
nœud cybernétique correspondant est attaqué avec succès, l'agent physique reste Dans le domaine physique, l'attaquant sélectionne un sommet à cibler dans le
capable de répondre aux attaques physiques. graphe G1. Ainsi, l'ensemble des actions de l'attaquant dans le domaine physique
est A1 = V1. un
Machine Translated by Google

La combinaison de ces actions d'attaquant de chaque domaine donne les bords le long du chemin. Soit le nœud cible du chemin pa noté ui .
l'ensemble des actions de l'attaquant pour le jeu complet, noté Aa = A1. Par Si ui est attaqué avec succès et que l'agent physique i
× A2 . une action d'attaquant peut être écrite comme aa = (pa, va), où
conséquent, n'est pas protégé (c'est­à­dire i / {i1, . . . , ig}), alors l'agent physique i est
un un

pa est le chemin d'attaque dans le cyber­graphe et va est le sommet d'attaque compromis et ne peut pas répondre à une attaque physique. Dans ce cas, les
dans le graphe physique. agents physiques restants occupent les emplacements Vocc = {v1, . . . , vi−1,
Il convient de noter que même si l'ensemble des actions d'un joueur dans vi+1, . . . , vN }. Cependant, s'il y a un honeypot sur le chemin d'attaque, ou si
ce cas est le produit cartésien des actions disponibles dans chaque domaine, l'agent physique i correspondant au nœud cible cybernétique attaqué ui est
cela n'est pas toujours vrai, comme nous allons le voir dans le cas des actions « protégé », alors l'agent physique i reste actif, et tous les agents physiques
du défenseur. Par conséquent, ce jeu sert d'exemple illustratif mettant en occupent les emplacements dans l'ensemble Vocc = {v1, . . . , vN }.
évidence les deux scénarios : l'un où les actions d'un joueur dans un
environnement multi­domaines forment le produit cartésien des actions dans Considérez une attaque physique lancée au sommet va, le gain de
chaque domaine, et l'autre où le produit cartésien ne parvient pas à englober l'attaquant est exprimé comme :
toutes les actions disponibles.
Ra(aa, ad) = f(wva,s) (va) − (1 − f(wva,s))D, où s = arg minx Vocc wx,v,
B. Actions du défenseur
D est la pénalité de capture et f : R → [0, 1] est une fonction monotone représentant la
Dans le domaine cybernétique, le défenseur alloue h honeypots aux arêtes
probabilité que l'attaquant attaque avec succès le sommet va. Plus l'agent physique répondant
du graphe G2. Par conséquent, l'ensemble des actions disponibles pour le
est éloigné du sommet attaqué, plus la probabilité de réussite de l'attaque est élevée. Puisqu'il
défenseur dans le domaine cybernétique, noté A2 , se compose des |E2| d,
s'agit d'un jeu à somme nulle, la récompense du défenseur est Rd = −Ra.
h
allocations possibles de pots de miel.
Dans le domaine physique, le défenseur alloue N agents dans le graphe
G1 et désigne g de ces agents comme « protégés ». Ainsi, l'ensemble des
|V1| N
actions A1 comprend des actions possibles. D. Équilibre du jeu
d N g
Bien que les agents physiques soient homogènes par nature, c'est­à­dire Étant donné que le jeu de tromperie multi­domaines développé ci­dessus est fini (c'est­à­
qu'ils partagent les mêmes capacités et caractéristiques, l'affectation spécifique dire que chaque espace d'action est fini), il admet un équilibre de Nash en stratégie mixte
de ces agents aux sommets du graphe physique devient cruciale lorsqu'on [21], [22]. Une stratégie mixte est une distribution de probabilité sur l'espace d'action d'un
considère leur connexion aux nœuds cibles cybernétiques. En particulier, joueur. Une méthode pour trouver cette stratégie mixte est Double Oracle, abordée dans la
chaque nœud cible cybernétique ui est directement connecté à un agent section suivante.
physique correspondant, appelé agent i. Par conséquent, l'affectation d'agents
physiques aux sommets du graphe physique influence directement l'efficacité
IV. APPROCHE DU DOUBLE ORACLE
de la stratégie de défense dans le domaine cybernétique. Cette connexion
entre les agents physiques et les nœuds cibles cybernétiques souligne la Comme nous l'avons vu dans la section I, l'oracle double (DO) est souvent
nécessité de prendre en compte non seulement l'affectation des agents aux utilisé pour résoudre des jeux avec des espaces d'action extrêmement grands.
sommets, mais également l'affectation spécifique des agents aux nœuds L'algorithme commence par résoudre un jeu restreint relativement petit.
cibles cybernétiques. L'algorithme ajoute de manière itérative les meilleures stratégies de réponse
Pour capturer cette relation, nous introduisons l'ensemble A12 qui d, au jeu restreint jusqu'à ce qu'aucun joueur ne puisse améliorer sa stratégie,
représente toutes les permutations d'allocations d'agents physiques au sein ce qui conduit à une convergence vers un équilibre de Nash ou un équilibre
d'une action physique donnée. Par conséquent, dans le scénario multi­ de Nash approximatif [23]. L'algorithme du double oracle s'arrête lorsqu'aucun
domaines, l'ensemble des actions de défense est donné par Ad = A1. Cela joueur ne peut trouver une meilleure stratégie que celles déjà incluses dans le
implique qu'au×lieu
A2 × A12ensemble
d'un d. d'emplacements pour les agents physiques jeu restreint.
d d
dans le cybergraphe, un N­uplet est requis, où le i agent physique est connecté Étant donné que l’algorithme proposé repose sur l’algorithme DO, nous
Le
à ui dans le cybergraphe.
ème ème élément désigne l'emplacement du i présentons un aperçu des principales étapes et composants de DO.
Étape 1, initialisez l'ensemble des stratégies pour les deux joueurs (défenseur
et attaquant) avec un petit ensemble de stratégies initiales. Les stratégies
Par conséquent, une action de défenseur peut être représentée comme ad = (v1, . . . , vN ),
initiales peuvent être sélectionnées de manière aléatoire ou à l'aide d'une
{e1, . . . , eh}, {i1, . . . , ig} , où : • (v1, . . . , vN ) désigne les sommets
connaissance experte du domaine. Étape 2, définissez le jeu restreint en
physiques occupés par les agents physiques respectifs, • {e1, . . . , eh} E2 représente
utilisant les stratégies initiales. Étape 3, résolvez le jeu restreint pour trouver
l'ensemble des arêtes du pot de miel, •
l'équilibre actuel (c'est­à­dire le méta­NE) pour le jeu restreint. Étape 4,
{i1, . . . , ig} indique quels agents physiques sont désignés comme protégés.
calculez les meilleures stratégies de réponse pour les deux joueurs par rapport
à l'équilibre actuel en utilisant l'oracle de chaque joueur. L'oracle du défenseur
trouve la meilleure stratégie de réponse à la stratégie mixte actuelle de
C. Récompenses
l'attaquant, et l'oracle de l'attaquant trouve la meilleure stratégie de réponse à
Étant donné les actions aa = (pa, va) pour l'attaquant et ad = (v1, . . . , vN ), la stratégie mixte actuelle du défenseur. Étape 5, ajoutez les meilleures
{e1, . . . , eh}, {i1, . . . ,ig} pour le défenseur, définissons les récompenses stratégies de réponse aux ensembles respectifs de stratégies pour les joueurs
pour les deux joueurs. et mettez à jour le jeu restreint avec les nouvelles stratégies. Itérez sur les
Premièrement, dans le domaine cybernétique, le nœud cible cybernétique étapes précédentes (étape 2 à étape 5) jusqu'à ce que la condition d'arrêt soit
du chemin pa est attaqué avec succès s'il n'y a pas de honeypot sur aucun des remplie. La condition d'arrêt est remplie
Machine Translated by Google

Postes d'agent • ca : variable continue représentant le gain attendu par le défenseur pour l'action
physique
de l'attaquant a.

k­médiane Cyber Cupide

PIL Domaine ILP Pot de miel Affectation Heuristique max caP[attaque a] (1)
Allocation
Défenseur Oracle
a a¯
P[v] P[p]
Marginal k
Probabilité St
Action du défenseur yjr ≤ 1 j (2)
Calcul
r=1
n
r (3)
yjr = 1
Défenseur
Au moins
Oracle
j=1
Jeu LP
une meilleure réponse
Résolveur
Pas d'arrêt k n
Attaquant améliore le
Oracle résultat yjr = N (4)
r=1 j=1
Oui n
Joueur
xvjr = 1 v, r (5)
Politiques
j=1
Fig. 2. Organigramme de l'algorithme proposé. L'oracle défenseur heuristique est N
représenté dans la case en pointillés, illustrant le composant Oracle défenseur de la v, j (6)
yjs ≥ xvj0
méthode Double Oracle. Le composant Greedy Assignment utilise l'allocation de pot
s=1
de miel dans le domaine cybernétique et la position de l'agent physique dans le
N
domaine physique pour trouver une action de défense dans le jeu multi­domaines
comme expliqué dans la proposition IV.3. yjs − yjr ≥ xvjr v, j, r (7)
s=1
N
si aucun joueur ne peut améliorer son gain en s'écartant de la méta­NE zr = g (8)
actuelle, alors l'algorithme se termine. r=1

A. Défenseur Oracle λe = h (9)

e E
Étant donné la stratégie actuelle de l'attaquant, l'oracle du défenseur cherche à trouver
la meilleure action de réponse. À cette fin, supposons que la probabilité que l'attaquant dp ≤ Ipéλe p (10)

sélectionne l'action a parmi son ensemble actuel d'actions soit P[attaque a]. Le problème de e E

l'oracle du défenseur peut alors être décrit comme suit. hdp ≥ Ipeλe p (11)
e E

Problème IV.1 (Problème de l'oracle du défenseur). Trouver la meilleure environ ≤ (1 − dp)(1 − zr) xvjrµ(v, j)
action de réponse a Ad pour le défenseur qui maximise le gain attendu du j

défenseur, étant donné la stratégie mixte π de l'attaquant sur les actions a¯ + (dp + zr) xvj0µ(v, j), a (12)
Aa. j

Le problème IV.1 est NP­difficile puisque résoudre l'oracle du défenseur, Dans la contrainte (12), v est le sommet d'attaque dans l'action a de
avec h = g = 0, et aucun chemin de cyberattaque, équivaut à résoudre le l'attaquant, p est le chemin de cyberattaque dans l'action a et r est l'agent
problème k­médian [24] pour N agents physiques sur le graphe G1. physique associé au nœud cybernétique cible du chemin d'attaque p.
De plus,
Ci­dessous, nous présentons un programme entier pour résoudre le problème
µ(v, j) = (1 − f(wv,j ))D − f(wv,j ) (v). (13)
problème de l'oracle de Fender. Ses variables sont les suivantes :

• xvjr {0, 1} : indique si le sommet v V1 est attribué à un agent physique situé Dans la contrainte (10), Ipe est 1 si l'arête e est dans le chemin p et 0 sinon.
au sommet j V1 lorsque l'agent physique r est compromis par l'attaquant. Nous expliquons les contraintes du programme entier proposé dans la preuve
Nous avons également des variables xvj0 indiquant si le sommet v est attribué à de la proposition ci­dessous.
un agent physique situé au sommet j lorsqu'aucun agent n'est compromis par
Proposition IV.2. Le programme entier décrit ci­dessus résout le problème IV.1
l'attaquant.
de l'oracle du défenseur.

• yjr {0, 1} : indique si l'agent physique r est au sommet Preuve. Nous montrons d'abord que toute solution qui satisfait les contraintes
j V1. du programme en nombres entiers est aussi une solution au problème de
• zr {0, 1} : indique si l'agent physique r est protégé. • dp {0, 1} : indique l'oracle du défenseur. La contrainte (2) garantit que chaque emplacement j
si le chemin de cyberattaque p comporte un honeypot sur au moins un de ses bords. peut avoir au plus un agent, et la contrainte (3) garantit que chaque agent r
doit être à l'un des emplacements.
• λe {0, 1} : indique si l’arête e E2 possède un pot de miel. La contrainte (4) garantit que le nombre total d'agents doit
Machine Translated by Google

La contrainte (5) garantit que chaque sommet v est affecté à exactement un La résolution de ce problème ILP peut nécessiter beaucoup de calculs, en particulier
emplacement. La contrainte (6) garantit que si un sommet v est affecté à un agent à pour les problèmes de grande taille. Pour résoudre ce problème, nous proposons un
l'emplacement j alors qu'aucun agent n'est compromis, alors il doit y avoir un agent à solveur heuristique pour le problème de l'oracle du défenseur. Bien que cette
j. La contrainte (7) garantit que si un sommet v est affecté à un emplacement j alors heuristique ne fournisse pas toujours la solution optimale, elle est capable d'identifier
que l'agent r est compromis, il doit y avoir un agent à j autre que l'agent r. La contrainte une réponse appropriée pour le défenseur compte tenu de la stratégie actuelle de
(8) garantit que le nombre d'agents protégés est exactement g. La contrainte (9) l'attaquant dans un délai nettement plus court, ce qui la rend plus pratique pour les
garantit que le nombre de pots de miel placés sur les arêtes est exactement h. Les problèmes de plus grande taille. Nous évaluerons les performances de l'heuristique
contraintes (10) et (11) garantissent qu'un chemin de cyberattaque p est considéré dans la section des simulations.
comme protégé si au moins une arête du chemin possède un pot de miel. La contrainte
(12) garantit que le gain attendu pour le défenseur, ca, est correctement calculé selon
que le chemin d'attaque est protégé par un pot de miel ou que l'agent physique est Algorithme 1 : DEFENDERHEURISTICORACLE
protégé. Entrée : G1, G2, N, politique d'attaque π et ensemble d'actions actuel a
Aa
Sortie : Action du défenseur d Ad 1 pour les
Notez également que toute solution au problème de l'oracle du défenseur peut être chemins cybernétiques p dans un do
représentée par une solution réalisable du programme en nombres entiers. Étant donnée une 2 P[p] ← Probabilité que l'attaquant choisisse le chemin p 3 pour le
action pour le défenseur, nous pouvons attribuer les valeurs correspondantes aux variables
sommet v dans V1 do
xvjr, yjr, zr, dp et λe de telle sorte que toutes les contraintes soient satisfaites.
4 P[v] ← Probabilité que l'attaquant choisisse le sommet v

Par conséquent, le programme entier décrit ci­dessus modélise et résout 5 Résolvez ILP (14) pour trouver les allocations de pots de miel

correctement le problème de l'oracle du défenseur tel que défini dans le problème IV.1. 6 Résolvez ILP (15) pour trouver l'affectation d'agent physique 7 pour
chaque cybernœud cible que je fais
8 pi ← probabilité de réussite d'une cyberattaque sur un nœud
Notons que l'ensemble des contraintes (12) n'est pas linéaire dans les variables du
i
programme en nombres entiers. Afin de le convertir en programme linéaire en nombres
9 pour chaque agent physique i fais 10 R−i ←
entiers (ILP), nous ajoutons les variables u et u¯ au lieu de ca avec les contraintes
gain du défenseur sans agent i 11 R0 ← gain du défenseur avec tous
suivantes au lieu de la contrainte (12).
les agents présents 12 {i1, . . . , ig} ← indices des g agents avec les valeurs

les plus basses de R−i 13 R−i ← R0 pour i {i1, . . . , ig}

uvjp ≤ xvjT(p) uvjp ≤ v, j, p

1 − dp uvjp ≤ 1 − v, j, p

v, j, p 14 Affectez avec gourmandise des agents avec un R−i plus élevé à des nœuds cybernétiques
zT(p) uvjp ≥ xvjT(p) − dp
avec un pi plus élevé
− zT(p) u¯vjp ≤ xvj0 u¯vjp ≤ dp + zT(p) v, j, p

u¯vjp ≥ xvj0 + dp v, j, p
L'algorithme de l'oracle du défenseur heuristique est décrit dans l'algorithme 1.
+ zT(p) − 1 Ici, T(p) v, j, p
L'idée principale derrière l'heuristique est de diviser le problème en domaines
représente l'agent physique contrôlé par le v, j, p
cybernétique et physique et de résoudre les sous­problèmes plus petits dans chaque

nœud cybernétique qui est la cible du chemin p. La variable uvjp est 1 si le sommet v est domaine avant de combiner les solutions pour trouver l'action du défenseur.

assigné à un agent physique situé à j lorsque la cyberattaque sur le chemin d'attaque p est
réussie et que l'agent contrôlé par le nœud cible du chemin p n'est pas protégé. La variable Étant donné la probabilité que l'attaquant choisisse l'action de l'attaquant a = (p,
u¯vjp vaut 1 si le sommet v est affecté à un agent physique situé à j lorsque soit le chemin v), nous trouvons les probabilités marginales que l'attaquant choisisse le chemin
d'attaque p possède un honeypot, soit l'agent physique connecté au cybernœud attaqué est d'attaque p dans le cybergraphe et le sommet d'attaque v dans le graphe physique
protégé. Avec ces variables et l'objectif suivant, nous obtenons un ILP qui résout le problème dans les lignes 1 à 4. Nous trouvons ensuite les allocations de pots de miel sur les
de l'oracle du défenseur. arêtes du cybergraphe en résolvant l'ILP suivant :

max Chemins (14)

d'attaque
max P[attaque a] µ(v, j)(uvjp + ¯uvjp) P[p]dp p st Contraintes (9), (10)
a a j

Ici, p et v représentent respectivement le chemin cybernétique et le sommet de Ici, P[p] est la probabilité marginale que l'attaquant choisisse le chemin d'attaque p
dans sa politique actuelle π. Cette ILP est similaire à celle utilisée dans [23] pour le
l'attaque dans l'attaque a.
problème de recherche de barrages routiers dans un graphe physique.
B. Défenseur heuristique Oracle

Le programme linéaire en nombres entiers décrit ci­dessus fournit une solution Dans le domaine physique, le problème de la recherche de l'emplacement des
optimale au problème de l'oracle du défenseur. Cependant, agents en fonction des probabilités d'attaque à différents sommets peut être
Machine Translated by Google

formulé comme un problème k­médian avec N agents, c'est­à­dire que nous les agents blindés et l'allocation d'agents physiques à des emplacements tels
devons déterminer N emplacements d'agent à partir de V1 pour minimiser le que le pi le plus élevé soit multiplié par le nombre le plus élevé. Cela se traduit
coût total entre chaque sommet et son agent le plus proche. Le coût entre un par la stratégie de cupidité consistant à choisir les g agents physiques avec
agent à l'emplacement j et un sommet v V1 est le gain de l'attaquant pour les valeurs les plus basses de R−1 comme blindés de sorte que leur R−1
avoir attaqué l'emplacement j multiplié par la probabilité marginale que effectif devienne R0. Ensuite, nous connectons ces agents blindés à g
l'attaquant attaque l'emplacement v. Soit V V1 de N sommets l'ensemble terminaux cybernétiques avec les valeurs les plus élevées de pi .
des emplacements d'agent, alors la fonction objective est Les agents restants sont connectés avec avidité de telle sorte que les agents
avec des valeurs plus élevées de R−i sont connectés à des terminaux
min min P[v]µ(v, j), j V (15) cybernétiques avec une probabilité plus élevée d'attaque réussie pi .
V1
Le résultat suivant montre que le double oracle avec un oracle heuristique
où µ(v, j) est défini dans l'équation (13) et P[v] est la probabilité marginale que du défenseur aboutit à une limite inférieure pour le gain du défenseur. Le
l'attaquant attaque le sommet v. Nous résolvons ce problème en utilisant un résultat s'étend à partir de l'exactitude du double oracle [26] et est présenté
ILP [25]. pour plus d'exhaustivité.
Après avoir déterminé l'allocation des pots de miel dans le domaine
cybernétique et les emplacements des agents physiques dans le domaine Proposition IV.4. Si l'algorithme Double Oracle avec Oracle Défenseur

physique, l'étape suivante consiste à identifier les agents physiques protégés. Heuristique et Oracle Attaquant Optimal se termine avec πd et πa comme

De plus, nous devons établir la permutation des agents physiques, ce qui politiques de défenseur et d'attaquant respectivement et le gain attendu η pour

implique de déterminer les connexions entre les emplacements des agents le défenseur, alors il n'y a pas de politique d'attaquant qui puisse donner un

physiques et les nœuds cibles cybernétiques. Cela se fait dans les lignes 7 à gain de défenseur inférieur à η pour la politique de défenseur πd.

14. Étant donné que les bords des pots de miel sont connus, nous calculons
la probabilité d'une cyberattaque réussie sur le terminal cybernétique i comme Preuve. Supposons par contradiction qu'il existe une politique d'attaquant π¯a
pi . Nous trouvons ensuite le gain pour le telle qu'il y ait au moins une action aa dans son support qui n'est pas dans le
défenseur si l’agent i est compromis par l’attaquant comme R−i (avec R0 étant support de πa et que son gain attendu soit η2 < η pour le défenseur. Alors le
le gain lorsqu’aucun agent n’est compromis). gain attendu pour l'attaquant jouant l'action aa, avec la politique de défenseur
Les agents physiques g dont l'absence serait la plus dommageable, c'est­à­ donnée devrait être η2. Cela implique que l'algorithme Double Oracle n'aurait
dire les agents avec les valeurs les plus basses pour R−i , sont assignés pas dû se terminer puisque l'oracle de l'attaquant peut proposer l'action aa qui
comme blindés, de sorte que même si leur terminal cybernétique est attaqué, a un meilleur gain pour l'attaquant que le gain actuel de l'attaquant.
le gain du défenseur serait R0. Ensuite, les agents physiques avec des valeurs
plus élevées de R−i , c'est­à­dire les agents dont l'absence serait la moins
dommageable, sont assignés aux nœuds cybernétiques avec une probabilité
plus élevée d'attaque réussie. La proposition suivante montre que cette De plus, nous présentons le résultat suivant spécifique à un cas particulier
sélection gourmande d'agents blindés et cette assignation gourmande d'agents de l'instance du problème :
physiques aux nœuds cybernétiques sont optimales, compte tenu des
Proposition IV.5. Lorsque le nombre de pots de miel h est suffisant pour
allocations d'agents physiques et de pots de miel.
protéger tous les cybernœuds cibles, l'oracle de défense heuristique proposé
Proposition IV.3. Étant donné la politique d'attaque π pour un ensemble donné est optimal.
d'actions d'attaque a, l'allocation de honeypot sur E2 et l'allocation d'agent
Preuve. Puisque l'ILP du domaine cybernétique (14) trouve l'allocation optimale
physique sur V1, la sélection gourmande d'agents protégés et l'affectation
de honeypot, il protégera tous les nœuds cybernétiques. Dans ce cas, les
gourmande d'agents physiques aux nœuds cybernétiques, comme cela est fait
agents protégés n'ont pas d'importance, et il ne reste plus qu'à trouver la
dans l'algorithme 1, sont optimales.
meilleure allocation physique pour les N agents du domaine physique, ce qui
Preuve. Supposons que le gain du défenseur lorsque l'agent physique i est est fait de manière optimale par l'ILP (15).
compromis par l'attaquant soit R−i , où R0 est le gain lorsqu'aucun agent n'est
C. Attaquant Oracle
compromis. Le gain du défenseur peut alors s'écrire comme piR−i où pi est la
probabilité que l'attaquant parvienne à compromettre l'agent i, et p0 est la L'oracle de l'attaquant cherche à trouver la meilleure réponse à la stratégie
i=0:N
probabilité que la cyberattaque soit interceptée par un piège. actuelle du défenseur. Pour une version plus simple du problème à domaine
unique où l'attaquant doit trouver un chemin d'attaque et le défenseur place
Étant donné que les valeurs de pi sont données et que nous ne disposons que des obstacles (pots de miel), il est montré dans [23] que la résolution de
des emplacements physiques des agents, le gain des défenseurs dépend de l'oracle de l'attaquant est NP­difficile, et un ILP est proposé pour le résoudre.
l'agent physique connecté à quel terminal informatique. Notez également que, Étant donné que notre problème est une version plus générale qui inclut à la
dans le cas où un nœud informatique connecté à un agent physique protégé fois les domaines cyber et physique, nous pouvons étendre l'ILP de [23] pour
est attaqué avec succès, le gain du défenseur est toujours R0 car l'attaquant inclure des variables pour les emplacements d'attaque physique. En raison de
ne peut pas compromettre l'agent protégé. considérations d'espace, nous ne présentons pas l'ILP étendu dans cet article.
De plus, R0 ≥ R−i car la suppression d'un agent physique ne peut pas
augmenter le gain du défenseur. Par conséquent, si nous voulons maximiser De plus, dans la littérature sur la cybersécurité [10], [11], les cyberchemins
l'objectif, nous pouvons choisir i=0:N piR−i , peuvent être traités comme une entrée du problème ou calculés
Machine Translated by Google

104
comme une étape de prétraitement en trouvant tous les chemins entre les Alg. proposé (Graphique cybernétique ER)
Alg. proposé (BA Cyber graph)
nœuds d'entrée et les nœuds cibles qui se situent dans un certain facteur Optimal (graphique Cyber ER)
Optimal (graphique Cyber BA)
des longueurs de chemin les plus courtes. La motivation derrière cela est
que même si un cyberattaquant ne peut pas choisir le chemin le plus court 102

entre le nœud d'entrée et le nœud cible, il éviterait de se promener sans but

d'exécution
Durée
(s)
dans le réseau car cela pourrait augmenter les chances d'être détecté.
Bien que le nombre de ces chemins puisse encore être exponentiel dans 100

le nombre de sommets du cybergraphe, pour nos simulations, nous

examinons toutes les actions possibles de l'attaquant pour l'oracle de
l'attaquant. Nous avons choisi cette approche au lieu d'utiliser l'ILP car elle 10­2
n=10,m=15 n=10,m=20 n=15,m=15 n=15,m=20
n'apportait pas d'amélioration considérable du temps d'exécution pour les Taille de l'instance du problème

tailles des graphes utilisés dans nos simulations.

Fig. 3. Comparaison du temps d’exécution de l’approche proposée avec le double oracle optimal.

V. SIMULATIONS

8
Dans cette section, nous évaluons les performances de l'algorithme Alg. proposé (Graphique cybernétique ER)
Alg. proposé (BA Cyber graph)
proposé. Pour la création de l'instance du problème, le graphe physique G1 7.5 Optimal (graphique Cyber ER)
Optimal (graphique Cyber BA)
a été construit en plaçant aléatoirement des sommets dans un environnement 7
planaire, puis en trouvant les distances les plus courtes entre chaque paire
6.5
de sommets. Les poids des sommets ont été sélectionnés aléatoirement et
indépendamment. Pour le cybergraphe, nous avons créé des graphes 6

Récompense
défenseur
attendue
du
aléatoires en utilisant le modèle Barabasi­Albert (BA) [27] et le modèle Erdos­ 5.5
Renyi (ER) [28]. Les programmes linéaires en nombres entiers ont été
5
résolus en utilisant le solveur Gurobi [29].
Comparaison avec l'Oracle optimal du défenseur : nous comparons les 4.5
n=10,m=15 n=10, m=20 n=15, m=15 n=15,m=20
performances de l'approche heuristique proposée à la solution optimale Taille de l'instance du problème

obtenue via une implémentation Double Oracle avec un oracle optimal du

Fig. 4. Gain du défenseur pour l'approche proposée par rapport au double oracle optimal.
défenseur. La figure 3 montre des boîtes à moustaches des temps
d'exécution, y compris la moyenne, le 25e percentile, le 75e percentile, les
valeurs minimales et maximales pour les deux approches sur 50 instances
aléatoires (25 chacune pour les cyber graphes BA et ER) pour chaque taille Évolutivité : pour évaluer l'évolutivité de l'approche, nous évaluons le
de problème. L'axe des x montre les tailles de problème (n pour les sommets temps d'exécution de l'algorithme sur des instances jusqu'à 70 sommets
de G1 et m pour les sommets de G2), et l'axe des y montre les temps cybernétiques et 70 sommets physiques, avec 5 agents physiques et 5
d'exécution sur une échelle logarithmique. Ces expériences ont été réalisées honeypots. Le nombre d'agents protégés est fixé à un.
pour N = 3, h = 1 et g = 1. Le graphique démontre que les temps d'exécution La figure 5 montre les temps d'exécution moyens de l'algorithme sur 25
de l'approche heuristique sont significativement plus courts que ceux de la instances aléatoires avec les cyber­graphes BA et ER.
solution optimale, l'approche heuristique étant jusqu'à 100 fois plus rapide Pour référence, dans les cas avec n = m = 70, N = 5 et h = 5, le nombre
pour les problèmes avec n = 15 et m = 20. La comparaison est effectuée d'actions du défenseur est de 3,75 × 1018 en moyenne pour les cyber­
pour des tailles de problème plus petites en raison du temps d'exécution graphes ER, et ces cas ont été résolus par l'approche proposée en 150
prohibitif pour les solutions optimales. secondes en moyenne.
La comparaison des gains est illustrée dans la figure 4. Comme prévu, Comparaison avec la solution de base à domaine unique App­
l'approche heuristique entraîne un gain de défense inférieur par rapport à la
solution optimale. La différence entre les deux approches est d'environ 16
% en moyenne. Cela indique que même si l'approche heuristique ne trouve 103
Graphique cybernétique Erdos­Renyi

pas de solutions optimales, elle peut trouver des solutions qui ne sont pas Graphique cybernétique Barabasi­Albert

loin d'être optimales dans un délai beaucoup plus court. Notez également 102
que comme N, h et g restent les mêmes, les graphes plus grands sont plus
difficiles à défendre, ce qui entraîne une diminution du gain à mesure que la 101
d'exécution
Durée
(s)

taille du problème augmente. Ces résultats indiquent également que les

graphes cybernétiques BA produisent des gains inférieurs par rapport aux
100
graphes cybernétiques ER. Cela peut être attribué au nombre moyen
d'arêtes plus élevé dans les graphes BA construits aléatoirement que dans
10­1
les graphes ER, offrant plus de chemins d'attaque aux attaquants potentiels, n=m=20 n=m=30 n=m=40 n=m=50 n=m=70
N=3, h=1 N=4, h=2 N=5, h=2 N=4, h=3 N=5, h=5
ce qui les rend plus difficiles à protéger. De plus, plus d'arêtes signifie plus Taille de l'instance du problème

d'actions de défense possibles, ce qui entraîne des temps d'exécution plus

longs pour les graphes cybernétiques BA. Fig. 5. Durée d’exécution de l’approche proposée avec des tailles d’instances importantes.
Machine Translated by Google

Alg. proposé (Graphique cybernétique ER) Ligne de base (graphique Cyber ER)
Alg. proposé (BA Cyber graph) Ligne de base (graphique BA Cyber)
[6] A. Schlenker, O. Thakoor, H. Xu, F. Fang, M. Tambe et P. Vayanos, « La cyber­
6
tromperie basée sur la théorie des jeux pour déjouer la reconnaissance du réseau
adverse », dans Adaptive Autonomous Secure Cyber Systems, pp. 183–204,
5 Springer, 2020.
[7] J.­H. Cho, M. Zhu et MP Singh, « Modélisation et analyse de jeux de tromperie basés
4 sur la théorie des hyperjeux », dans Autonomous Cyber Deception, pp. 49–74,
Springer, 2019.
[8] Z. Wan, J.­H. Cho, M. Zhu, AH Anwar, C. Kamhoua et MP
3
Récompense
défenseur
attendue
du

Singh, « Foureye : tromperie défensive contre les menaces persistantes avancées

via la théorie de l'hyperjeu », IEEE Transactions on Network and Service
2 Management, 2021.
[9] AH Anwar, C. Kamhoua et N. Leslie, « Un cadre théorique des jeux pour la cyber­
1 déception dynamique dans l'Internet des objets du champ de bataille », dans EAI
n=20, m=20 n=20, m=30 n=30, m=20 n=30, m=30 n=40, m=40 Int'l Conf. sur les systèmes mobiles et omniprésents : informatique, réseau et
N=3, h=1 N=3, h=3 N=4, h=2 N=4, h=2 N=5, h=2
services, pp. 522–526, 2019.
Taille de l'instance du problème
[10] AH Anwar et C. Kamhoua, « Théorie des jeux sur le graphique d'attaque pour la
cyber­tromperie », dans Int'l Conf. on Decision and Game Theory for Security,
Fig. 6. Comparaison des bénéfices de l’approche proposée avec l’approche de base.
Springer, 2020.
[11] AH Anwar, C. Kamhoua et N. Leslie, « Allocation de pots de miel sur les graphes
d'attaque dans les jeux de cyber­déception », dans Int'l Conf. on Computing,
approche : Pour comparer l'algorithme proposé avec une approche de base Networking and Communications, pp. 502–506, 2020.
pour les instances plus grandes, où la solution optimale n'a pas pu être [12] S. Ross, B. Chaib­draa et J. Pineau, « POMDP adaptatifs à Bayes. », dans NIPS, pp.
1225–1232, 2007.
obtenue, nous avons utilisé une méthode où les politiques de défense
[13] MA Sayed, AH Anwar, C. Kiekintveld, B. Bosansky et C. Kamhoua, « Cyber­tromperie
optimales pour les domaines cyber et physique ont été trouvées séparément contre les attaques zero­day : une approche théorique des jeux », dans Conférence
sans considérer l'autre domaine. Dans cette approche, étant donné une action internationale sur la théorie des décisions et des jeux pour la sécurité, pp. 44–63,
2022.
physique avec une probabilité Pphy et une action cyber avec une probabilité
[14] MA Sayed, AH Anwar, C. Kiekintveld et C. Kamhoua, « Allocation de pots de miel
Pcyb, l'action multi­domaine combinée a été considérée avec une probabilité pour la cyber­déception dans les réseaux tactiques dynamiques : une approche
PphyPcyb. Pour cette solution multi­domaine, le nœud cible cybernétique ui a théorique des jeux », dans Conférence internationale sur la théorie des décisions
et des jeux pour la sécurité, pp. 195–214, 2023.
été supposé être attribué à l'agent physique i. La meilleure politique d'action
[15] AH Anwar, CA Kamhoua, NO Leslie et C. Kiekintveld, « Allocation de pots de miel pour la
de l'attaquant dans le jeu multi­domaine a été trouvée pour calculer le gain
cyber­déception en cas d'incertitude », IEEE Transactions on Network and Service
attendu du défenseur. Ce gain est comparé au gain obtenu grâce à l'approche Management, vol. 19, no. 3, pp. 3438–3452, 2022.
proposée dans la Figure 6. En moyenne, l'approche de base a donné des
[16] AJ Mendez, « Un cas classique de tromperie », Studies in Intelligence, Journal of the
gains qui étaient 15 % inférieurs à ceux de la méthode proposée, la différence
American Intelligence Professional, hiver, vol. 2000, 1999.
atteignant jusqu'à 47 %.
[17] M. Johnson et J. Meyeraan, « La tromperie militaire : cacher le vrai et montrer le
faux », USAF Joint Forces Staff College, Joint and Combined Warfighting School,
vol. 7, 2003.
VI. CONCLUSION
[18] DU Case, « Analyse de la cyberattaque sur le réseau électrique ukrainien »,
Centre d'analyse et de partage d'informations sur l'électricité (E­ISAC), vol. 388, no.
Cet article présente un nouveau modèle de jeu à deux joueurs pour
1­29, p. 3, 2016.
défendre les systèmes cyber­physiques en intégrant des actions trompeuses [19] W. Duo, M. Zhou et A. Abusorrah, « Une étude sur les cyberattaques contre les
dans les domaines cyber et physique. Nous avons exploré la complexité de systèmes cyberphysiques : avancées et défis récents », IEEE/CAA Journal of
Automatica Sinica, vol. 9, no. 5, pp. 784–800, 2022.
cette interaction et proposé une approche à double oracle, utilisant des
[20] J. Beerman, D. Berent, Z. Falter et S. Bhunia, « Une revue de l'attaque par rançongiciel
programmes linéaires entiers et un oracle de défense heuristique pour les colonial pipeline », dans 2023 IEEE/ACM 23e Symposium international sur les
problèmes à grande échelle. Les simulations montrent que notre approche ateliers sur les clusters, le cloud et l'informatique Internet (CC­GridW), pp. 8–15,
heuristique permet d'obtenir des solutions quasi optimales de manière efficace. IEEE, 2023.
[21] JF Nash Jr, « Points d'équilibre dans les jeux à n personnes », Actes de la
Ce travail améliore la sécurité des systèmes cyber­physiques et offre des
académie nationale des sciences, vol. 36, no. 1, pp. 48–49, 1950.
perspectives pratiques pour les mécanismes de défense stratégiques. [22] T. Bas¸ar et GJ Olsder, Théorie des jeux dynamiques non coopératifs,
vol. 23. Siam, 1999.
ˇ ˇ
RÉFÉRENCES [23] M. Jain, D. Korzhyk, O. Vanek, V. Conitzer, M. Pechou ˇ cek et M. Tambe, « Un algorithme
double oracle pour les jeux de sécurité à somme nulle sur les graphes », dans La 10e
Conférence internationale sur les agents autonomes et les systèmes multiagents ­ Volume
[1] T. Peng, C. Leckie et K. Ramamohanarao, « Enquête sur les mécanismes de défense
1, pp. 327–334, Citeseer, 2011.
´
basés sur le réseau pour contrer les problèmes DoS et DDoS », ACM Computing
Surveys (CSUR), vol. 39, no. 1, pp. 3–es, 2007. [24] M. Charikar, S. Guha, E. Tardos et DB Shmoys, « Un algorithme d'approximation à
[2] MI Handel, « Renseignement et tromperie », The Journal of Strategic facteur constant pour le problème k­médian », dans le symposium ACM sur la
Études, vol. 5, no 1, pp. 122–154, 1982. théorie de l'informatique, pp. 1–10, 1999.
[3] J. Pawlick et Q. Zhu, « Deception by design : jeux de signalisation basés sur des [25] K. Jain et VV Vazirani, « Algorithmes d'approximation pour la localisation d'installations
preuves pour la défense du réseau », pré­impression arXiv arXiv:1503.05458, 2015. métriques et les problèmes k­médians utilisant le schéma primal­dual et la relaxation
[4] S. Roy, N. Sharmin, JC Acosta, C. Kiekintveld et A. Laszka, « Enquête et taxonomie lagrangienne », Journal of the ACM (JACM), vol. 48, no. 2, pp. 274–296, 2001.
des techniques de reconnaissance contradictoires », ACM Computing Surveys, vol.
55, no. 6, pp. 1–38, 2022. [26] HB McMahan, GJ Gordon et A. Blum, « Planification en présence de fonctions de
[5] M. Zhu, AH Anwar, Z. Wan, J.­H. Cho, CA Kamhoua et député coût contrôlées par un adversaire », dans Conférence internationale sur
Singh, « Une étude sur la tromperie défensive : approches utilisant la théorie des l’apprentissage automatique (ICML), pp. 536–543, 2003.
´
jeux et l'apprentissage automatique », IEEE Communications Surveys & Tutorials, [27] A.­L. Barabasi et R. Albert, « Emergence of scaling in random network », science,
vol. 23, no. 4, pp. 2460–2493, 2021. vol. 286, no. 5439, pp. 509–512, 1999.
Machine Translated by Google

˝ ´
[28] P. Erdos, A. Renyi, et al., « Sur l’évolution des graphes aléatoires »,
Publications de l'Institut de mathématiques de l'Académie hongroise
des Sciences, vol. 5, no. 1, pp. 17–60, 1960.
[29] Gurobi Optimization, LLC, « Manuel de référence de Gurobi Optimizer », 2023.