Optimal Transport, Independance versus Indetermination duality, impact on a new Copula Design

28/10/2015
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14300

Résumé

This article leans on some previous results already presented in [10], based on the Fréchet’s works,Wilson’s entropy and Minimal Trade models in connectionwith theMKPtransportation problem (MKP, stands for Monge-Kantorovich Problem). Using the duality between “independance” and “indetermination” structures, shown in this former paper, we are in a position to derive a novel approach to design a copula, suitable and efficient for anomaly detection in IT systems analysis.

Optimal Transport, Independance versus Indetermination duality, impact on a new Copula Design

Collection

application/pdf Optimal Transport, Independance versus Indetermination duality, impact on a new Copula Design Benoit Huyot, Yves Mabiala, Jean-François Marcotorchino

Média

Voir la vidéo

Métriques

133
19
462.18 Ko
 application/pdf
bitcache://70aa388a0ded90168526018aad459e00fddae75d

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/11784/14300</identifier><creators><creator><creatorName>Jean-François Marcotorchino</creatorName></creator><creator><creatorName>Benoit Huyot</creatorName></creator><creator><creatorName>Yves Mabiala</creatorName></creator></creators><titles>
            <title>Optimal Transport, Independance versus Indetermination duality, impact on a new Copula Design</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><subjects><subject>Optimal transport</subject><subject>MKP problem</subject><subject>Indetermination and independance structures</subject><subject>Condorcet and relational analysis</subject><subject>Copula theory</subject></subjects><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Fri 17 Aug 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">70aa388a0ded90168526018aad459e00fddae75d</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24690</version>
        <descriptions>
            <description descriptionType="Abstract">
This article leans on some previous results already presented in [10], based on the Fréchet’s works,Wilson’s entropy and Minimal Trade models in connectionwith theMKPtransportation problem (MKP, stands for Monge-Kantorovich Problem). Using the duality between “independance” and “indetermination” structures, shown in this former paper, we are in a position to derive a novel approach to design a copula, suitable and efficient for anomaly detection in IT systems analysis.

</description>
        </descriptions>
    </resource>
.

Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Optimal Transport, Independance versus Indetermination duality, impact on a new Copula Design Benoit Huyot, Yves Mabiala Thales Communications and Security 29 October 2015 Benoit Huyot, Yves Mabiala 1 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba 1 Cybersecurity problem overview Current Intrusion Detection Systems Anomaly based IDS IDS as a classification problem 2 Properties of Copula Function Copula theory historic Sklar’s Theorem and Frechet’s Bounds Regularity properties on copula function 3 Copula theory used in anomalies detection applications Classification AUC with copula paradigm Experimental results Benoit Huyot, Yves Mabiala 2 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Current Intrusion Detection Systems Rule based approaches Suitable to detect previously known patterns Rules are easily understandable Easy addition of new rules But Unable to detect unknown patterns Benoit Huyot, Yves Mabiala 3 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Anomaly based IDS Anomaly based approaches Suitable to detect unknown patterns Time consuming to update model Alerts are difficult to understand through existing tools Too many false alerts But Our approach is an attempt to overcome these problems Benoit Huyot, Yves Mabiala 4 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Anomaly based IDS Anomaly detection as a classification problem Y is a binary random variable where Y = 0 if the event is abnormal Y = 1 else. p0 is the a priori attack probability define by p0 = P(Y ≤ 0) X represents the difference characteristics of the network event If X is a p-dimensional random vector, the cumulative distribution function will be denoted F(x) = P(X1 ≤ x1, ..., Xp ≤ xp) Benoit Huyot, Yves Mabiala 5 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba IDS as a classification problem Scoring function Scoring function is defined as P(Y = 0|X = x) By definition we have P(Y = 0|X = x) = P(Y = 0, X = x) P(X = x) Anomalies are identified thanks to the classical Bayes’s rule model Empirical estimation is difficult due to the ”Curse of Dimensionnality” Joint probabilities will be computed using copula theory to ease computations Benoit Huyot, Yves Mabiala 6 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Copula theory historic Introduction to Copula theory Originated by M.Fr´echet in 1951 Fr´echet, M. (1951): ”Sur les tableaux de corr´elations dont les marges sont donn´ees”, Annales de l’Universit´e de Lyon, Section A no 14, 53-77 A.Sklar gave a breakthrough in 1959 Sklar, A. (1959), ”Fonctions de r´epartition `a n dimensions et leurs marges”, Publ. Inst. Statist. Univ. Paris 8: 229-231 Benoit Huyot, Yves Mabiala 7 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Sklar’s Theorem and Frechet’s Bounds Main results on copula function Theorem (Sklar’s theorem) Given two continuous random variables X and Y in L1, with cumulative distribution functions written F and G. It exists an unique function C, called, copula such as: P(X ≤ x, Y ≤ y) = C(F(x), G(y)) Theorem (Fr´echet-Hoeffding’s Bounds) Given a copula function C, ∀(u, v) ∈ [0, 1]2 we have the following Fr´echet’s bounds: Max(u + v − 1, 0) ≤ C(u, v) ≤ Min(u, v) Benoit Huyot, Yves Mabiala 8 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Regularity properties on copula function 2-increasing property or Monge’s conditions B + D = C(u1, v2) D + C = C(v1, u2) A + B + C + D = C(v1, v2) D = C(u1, u2) A = (A + B + C + D) − (B + D) − (D + C) + D and A ≥ 0 ∀(u1, v1) as 0 ≤ u1 ≤ v1 ≤ 1 ∀(u2, v2) as 0 ≤ u2 ≤ v2 ≤ 1 C(v1, v2) − C(u1, v2) − C(v1, u2) + C(u1, u2) ≥ 0 Benoit Huyot, Yves Mabiala 9 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Regularity properties on copula function Copula is an Holderian function B + C + E = C(u2, v2) − C(u1, v1) A + C + E = C(u2, 1) − C(u1, 1) B + C + D = C(v2, 1) − C(v1, 1) B + C + E ≤ (B + C + D) + (A + C + E) We obtain a 1-Holderian condition for the Copula C: ∀(u1, v1, u2, v2) ∈ [0, 1]4 |C(u2, v2)−C(u1, v1)| ≤ |u2−u1|+|v2−v1| Benoit Huyot, Yves Mabiala 10 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Copula theory used in anomalies detection applications Only unfrequent events could have a score greater than 1 2 Looking for attack remains to looking for rare events Fr´echet’s Bounds gives us P(Y = 0|X) ≤ min(P(X), P(Y = 0)) P(X) and we get: P(Y = 0|X) ≥ 1 2 ⇒ P(X) ≤ 2.P(Y = 0) Benoit Huyot, Yves Mabiala 11 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Lower bound for anomalies detection It’s possible to show limit The ”lower tail dependance” is defined as: λL = Lim v→0 C(v, v) v λL ≤ Lim v→0 C(u, v) v Benoit Huyot, Yves Mabiala 12 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Variation of the score function We want to study to variation of v → C(u, v) v in [0, 2p0] 1 v2 v ∂C ∂v (u, v) − C(u, v) ≤ 0 ⇔ ∂C ∂v (u, v) ≤ C(u, v) v link to convexity ⇔ v ∂ ∂v logC(u, v) ≤ 1 link to Fisher’s information Benoit Huyot, Yves Mabiala 13 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Classification AUC with copula paradigm ROC curve and AUC Sensitivity: True Positive Rate, C(p0, s) p0 1-Specificity (anti-Specificity): False Positive Rate, s 1 − p0 (1 − C(p0, s)) AUC = 1 2p0(1 − p0) 1 − p2 0 − 1 0 (C(p0, s) − 1)2 ds In case of a bivariate random vector X we get: AUC = K1(p0)−K2(p0) 1 0 1 0 (C2(s1, s2) − 1)2 ∂2 ∂s1∂s2 C2(s1, s2)ds1ds2 Benoit Huyot, Yves Mabiala 14 Optimal transport problem In the Monge-Kantorovich problem we want to minimize following quantity: minh A 0 B 0 h(x, y) − 1 AB 2 Under constraints: 1 A 0 B 0 h(x, y) = 1 2 A 0 h(x, y) = g(y) 3 B 0 h(x, y) = f (x) The solution is given by: h∗ (x, y) = f (x) B + g(y) A − 1 AB The cumulative distribution function associated to the solution is: H∗ (x, y) = y F(x) B + x G(y) A − xy AB Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Classification AUC with copula paradigm Algorithm principle Benoit Huyot, Yves Mabiala 16 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Experimental results Experimental results Quantile level used for copula benchmark Quantile level 10−4 5.10−4 10−3 5.10−3 10−2 Optimal Transport Copula Detection rate 18.64% 73.86% 74.32% 74.82% 75.09% False alarms rate 23.15% 2.32% 4.38% 3.72% 4.71% Clayton Copula Detection rate 0.0% 0.0% 19.28% 71.73% 79.86% False alarms rate 0.0% 0.0% 0.63% 36.76% 34.20% Frechet’s upper bound Copula Detection rate 30.35% 31.39% 32.73% 36.93% 79.11% False alarms rate 41.26% 38.68% 31.89% 27.48% 27.95% Benoit Huyot, Yves Mabiala 17 Outline Cybersecurity problem overview Properties of Copula Function Copula theory used in anomalies detection applications Ba Experimental results Thanks for your attention! Benoit Huyot, Yves Mabiala 18 Link to Fisher’s Information We will use the following equation: v C(u, v) ∂ ∂v C(u, v) = ∂ ∂v logC(u, v).v This condition is the statistical score The variance of this quantity gives the Fisher’s Information Sensitivity Sensitivity represents how many events are well assigned to anomalies Sensitivity : P( ˆY = 0|Y = 0) ˆY = 0 when F(X) ≤ s for a given threshold s ˆY = 0 when X ∈ F−1([0; s]) Sensitivity: P(X ∈ F−1([0; s])|p0) Sensitivity Sensitivity appears so as : P( ˆY = 0|Y = 0) = P(Y = 0, ˆY = 0) P(Y = 0) = P(Y = 0, X ≤ F−1 X (s)) P(Y = 0) = C(p0, s) p0 Specificity/Antispecificity Antispecificity represents how many misclassifications are given by the algorithm Specificity : P( ˆY = 1|Y = 1) ˆY = 1 when F(X) ≥ s for a given threshold s ˆY = 1 when X ∈ F−1([s; 1]) Specificity: P(X ∈ F−1([s; 1])|p0) Antispecificity Antispecificity appears using survival copula function as: 1 − P( ˆY = 1|Y = 1) = P( ˆY = 0|Y > 0) = P( ˆY = 0) P(Y > 0) P(Y > 0| ˆY = 0) = s 1 − p0 (1 − C(p0, s)) Area under ROC Curve (AUC) AUC = 1 0 PD(PF )dPF Using an integration by substitution we obtain: AUC = 1 0 PD(s). ∂PF (s) ∂s ds Sensitivity: PD(s) = C(p0, s) p0 Antispecificity PF (s) = s 1 − p0 (1 − C(p0, s)) AUC = 1 p0(1 − p0) 1 0 C(p0, s) − C(p0, s)2 − sC(p0, s)C (p0, s) ds AUC simplification AUC = 1 p0(1 − p0) 1 0 C(p0, s) − C(p0, s)2 − sC(p0, s)C (p0, s) ds An integration by parts give us: A3 = − sC2(p0, s) 2 1 0 + 1 2 1 0 C(p0, s)2 ds = − p2 0 2 + 1 2 1 0 C(p0, s)2 ds AUC = 1 p0(1 − p0) 1 0 C(p0, s) − 1 2 C(p0, s)2 ds − p0 2(1 − p0) Using this simplification X − 1 2 X2 = − 1 2 X2 − 2X + 1 + 1 2 it comes: AUC = 1 2p0(1 − p0) 1 − p2 0 − 1 0 (C(p0, s) − 1)2 ds AUC in a bivariate case Using the Frechet-Hoeffding’s upper bounds and the lower tail dependence we get: 1 0 (λLs − 1)2 ds ≤ 1 0 (C(p0, s) − 1)2 ds ≤ 1 0 (min(p0, s) − 1)2 ds It comes : K + λ2 L 1 0 (s − 1)2 ds ≤ 1 0 (C(p0, s) − 1)2 ds ≤ 1 0 (s − 1)2 ds If X is a bivariate random vector: 1 0 (s − 1)2 ds = 1 0 1 0 (C2(s1, s2) − 1)2 ∂2 ∂s1∂s2 C2(s1, s2)ds1ds2