Emad Alsuwat
email: alsuwat@email.sc.edu

Hatim Alsuwat
email: alsuwath@email.sc.edu

John Rose
email: rose@cse.sc.edu

Marco Valtorta

Csilla Farkas
email: farkas@cse.sc.edu

Detecting Adversarial Attacks in the Context of Bayesian Networks

Keywords: Adversarial machine learning, Bayesian Networks, Data poisoning attacks, The PC algorithm, Long-duration attacks, Detection Methods

In this research, we study data poisoning attacks against Bayesian network structure learning algorithms. We propose to use the distance between Bayesian network models and the value of data conflict to detect data poisoning attacks. We propose a 2-layered framework that detects both one-step and long-duration data poisoning attacks. Layer 1 enforces "reject on negative impacts" detection; i.e., input that changes the Bayesian network model is labeled potentially malicious. Layer 2 aims to detect long-duration attacks; i.e., observations in the incoming data that conflict with the original Bayesian model. We show that for a typical small Bayesian network, only a few contaminated cases are needed to corrupt the learned structure. Our detection methods are effective against not only one-step attacks but also sophisticated long-duration attacks. We also present our empirical results.

Introduction

During the last decade, several researchers addressed the problem of cyber attacks against machine learning systems (see [START_REF] Liu | A survey on security threats and defensive techniques of machine learning: a data driven view[END_REF] for an overview). Machine learning techniques are widely used; however, machine learning methods were not designed to function correctly in adversarial settings [START_REF] Gardiner | On the security of machine learning in malware c&c detection: A survey[END_REF][START_REF] Huang | Adversarial machine learning[END_REF]. Data poisoning attacks are considered one of the most important emerging security threats against machine learning systems [START_REF] Paudice | Detection of adversarial training examples in poisoning attacks through anomaly detection[END_REF][START_REF] Wang | Data poisoning attacks against online learning[END_REF]. Data poisoning attacks aim to corrupt the machine learning model by contaminating the data in the training phase [START_REF] Biggio | Poisoning attacks against support vector machines[END_REF]. Data poisoning was studied in different machine learning algorithms, such as Support Vector Machines (SVMs) [START_REF] Biggio | Poisoning attacks against support vector machines[END_REF][START_REF] Koh | Understanding black-box predictions via influence functions[END_REF][START_REF] Mei | Using machine teaching to identify optimal training-set attacks on machine learners[END_REF], Principal Component Analysis (PCA) [START_REF] Biggio | Poisoning attacks to compromise face templates[END_REF][START_REF] Biggio | Poisoning adaptive biometric systems[END_REF], Clustering [START_REF] Biggio | Poisoning complete-linkage hierarchical clustering[END_REF][START_REF] Biggio | Is data clustering in adversarial settings secure?[END_REF], and Neural Networks (NNs) [START_REF] Yang | Generative poisoning attack method against neural networks[END_REF]. However, these efforts are not directly applicable to Bayesian structure learning algorithms.

There are two main methods used in defending against a poisoning attack: (1) robust learning and (2) data sanitization [START_REF] Chan | Data sanitization against adversarial label contamination based on data complexity[END_REF]. Robust learning aims to increase learning algorithm robustness, thereby reducing the overall influence that contaminated data samples have on the algorithm. Data sanitization eliminates contaminated data samples from the training data set prior to training a classifier. While data sanitization shows promise to defend against data poisoning, it is often impossible to validate every data source [START_REF] Chan | Data sanitization against adversarial label contamination based on data complexity[END_REF].

In our earlier work [START_REF] Alsuwat | Cyber attacks against the pc learning algorithm[END_REF][START_REF] Alsuwat | Bayesian structure learning attacks[END_REF], we studied the robustness of Bayesian network structure learning algorithms against traditional (a.k.a one-step) data poisoning attacks. We proposed two subclasses of data poisoning attacks against Bayesian network algorithms: (i) model invalidation attacks and (ii) targeted change attacks. We defined a novel link strength measure that can be used to perform a security analysis of Bayesian network models [START_REF] Alsuwat | How to generate the network you want with the pc learning algorithm[END_REF].

In this paper, we further investigate the robustness of Bayesian network structure learning algorithms against long-duration (a.k.a multi-step) data poisoning attacks (described in Section 3). We use the causative model proposed by Barreno et al. [START_REF] Barreno | The security of machine learning[END_REF] to contextualize Bayesian network vulnerabilities. We propose a 2-layered framework to detect poisoning attacks from untrusted data sources. Layer 1 enforces "reject on negative impacts" detection [START_REF] Nelson | Misleading learners: Co-opting your spam filter[END_REF]; i.e., input that changes the model is labeled malicious. Layer 2 aims to detect long-duration attacks; i.e., it looks for cases in the incoming data that conflict with the original Bayesian model.

The main contributions of this paper are the following: We define longduration data poisoning attacks when an attacker may spread the malicious workload over several datasets. We study model invalidation attacks which aim to arbitrarily corrupt the Bayesian network structure. Our 2-layered framework detects both one-step and long-duration data poisoning attacks. We use the distance between Bayesian network models, B 1 and B 2 , denoted as ds(B 1 , B 2 ), to detect malicious data input (Equation 3) for one-step attacks. For long-duration attacks, we use the value of data conflict (Equation 4) to detect potentially poisoned data. Our framework relies on offline analysis to validate the potentially malicious datasets. We present our empirical results, showing the effectiveness of our framework to detect both one-step and long-duration attacks. Our results indicate that the distance measure ds(B 1 , B 2 ) (Equation 3) and the conflict measure Conf (c, B 1 ) (Equation 4) are sensitive to poisoned data.

The rest of the paper is structured as follows. In section 2, we present the problem setting. In section 3, we present long-duration data poisoning attacks against Bayesian network structure learning algorithms. In section 4, we present our 2-layered detection framework and our algorithms. In section 5 we present our empirical results. In section 6, we give an overview of related work. In section 7, we conclude and briefly discuss ongoing work.

Problem Setting

We focus on structure learning algorithms in Bayesian networks. Let DS v = {c 1 , . . . , c N } be a validated dataset with N case. Each case c is over attributes x 1 , . . . , x n and of the form c =< x 1 = v 1 , . . . , x n = v n >, where v i is the value of attribute x i . A Bayesian network model B 1 is learned by feeding a validated dataset DS v into a Bayesian structure learning algorithm, BN Algo, such as the PC algorithm, which is the most widely used algorithm for structure learning in Bayesian networks [START_REF] Spirtes | Causation, prediction, and search[END_REF], as shown in Equation 1.

B 1 = BN Algo(DS v ) (1)
The defender attempts to divide an incoming dataset, DS p , coming from an untrusted source, into clean and poisoned cases. The attacker aims to inject a contaminated dataset, DS p with the same attributes as DS v and N 2), such that there is a missing link, a reversed link, or an additional link in B 2 that is not in B 1 .

B 2 = BN Algo(DS u ) (2)
To estimate the impact of the poisoned dataset on the validated dataset, we define a distance function between two Bayesian network models B 1 and B 2 , denoted as ds(B 1 , B 2 ). Intuitively, B 1 is the validated model and B 2 is the potentially corrupted model. Let B 1 = (V, E 1 ) and B 2 = (V, E 2 ) be two Bayesian network models where

V = {x 1 , x 2 , . . . , x n } and E = {(x u , x v ) : x u , x v ∈ V }. Let B 1 be
the validated model resulting from feeding DS v to a Bayesian network structure learning algorithm, and B 2 be the newly learned model resulting from feeding DS u to a Bayesian network structure learning algorithm. Let e 1 = (x u , x v ) be a directed edge from vertex x u to vertex x v , and e 2 = (x v , x u ) be a directed edge from vertex x v to vertex x u (e 2 is the reverse of e 1 ). The distance function, ds(B 1 , B 2 ), is a non-negative function that measures the changes in the newly learned model B 2 with respect to the original model B 1 . The distance function, ds(B 1 , B 2 ), is defined as follows: (Distance measure) Let Bayesian network models B 1 = (V, E 1 ) and B 2 = (V, E 2 ) be the results of feeding DS v and DS u , respectively, to a Bayesian network structure learning algorithm. ds(B 1 , B 2 ) is defined as the sum of distances over pairs of vertices (x u , x v ) ∈ V × V as follows:

ds(B 1 , B 2 ) = (xu,xv)∈V ×V ds xuxv (B 1 , B 2 ) ( 3
)
where

ds xuxv (B 1 , B 2 ) is the distance between every pair of vertices (x u , x v ) ∈ V × V .
We define ds xuxv (B 1 , B 2 ) as the cost of making a change to B 1 that results in the newly learned model B 2 . The function ds xuxv (B 1 , B 2 ) between the two Bayesian network models B 1 and B 2 is defined as follows [START_REF] De Jongh | A comparison of structural distance measures for causal bayesian network models[END_REF]: To investigate the coherence of an instance case, c =< x 1 = v 1 , . . . , x n = v n > (or simply < v 1 , . . . , v n >), in DS p with the validated model B 1 , we use conflict measure, denoted as Conf (c, B 1 ). Conflict measure, Conf (c, B 1 ), is defined as follows: (Conflict measure) Let B 1 be a Bayesian network model and let DS p be an incoming dataset, Conf (c, B 1 ) is defined as the process of detecting how well a given case < v 1 , . . . , v n > fits the model B 1 according to the following equation:

Status 1 (True Negative Edges): if ((e 1 ∈ E 1 && e 2 ∈ E 1 ) && (e 1 ∈ E 2 && e 2 ∈ E 2 )),
Conf (c, B 1 ) = log 2 P (v 1 ) . . . P (v n ) P (v) (4)
where c =< v 1 , . . . , v n >, and P (v) is the prior probability of the evidence v [START_REF] Nielsen | Bayesian networks and decision graphs[END_REF].

If P (v) = 0, then we conclude that there is inconsistency among the observations < v 1 , . . . , v n >. If the value of Conf (c, B 1 ) is positive, then we can conclude that < v 1 , . . . , v n > are negatively correlated (i.e., unlikely to be correlated as the model requires; P (v 1 , . . . , v n ) < P (v 1 ) × . . . × P (v n )) and thus are conflicting with the model B 1 . The higher the value of Conf (c, B 1 ) is, the more incompatibility we have between B 1 and < v 1 , . . . , v n >.

In this paper, we adopt the causative model proposed by Barreno et al. [START_REF] Barreno | The security of machine learning[END_REF]. Attacks on machine learning systems are modeled as a game between malicious attackers and defenders. In our setting, defenders aim to learn a validated Bayesian network model B 1 using the dataset DS v with the fewest number of errors (minimum ds function). Malicious attackers aim to mislead the defender into learning a contaminated model B 2 using the dataset DS u , obtained by polluting DS v with DS p . We assume that malicious attackers have full knowledge of how Bayesian network structure learning algorithms work. Also, we assume that attackers have knowledge of the dataset DS v . In addition, we assume that the poisoning percentage at which attackers are allowed to add new "contaminated" cases to DS v , β, is less than or equal to 0.05. The game between malicious attackers and defenders can be modeled as follows: Note, that the goal of malicious attackers is to maximize the quantity ds(B 1 , B 2 ). The notations used in this paper are summarized as follows:

Notation Description DS[x 1 , . . . , x n ]
Schema for datasets with attributes x 1 , . . . ,

x n DS v = {c 1 , . . . , c N } Validated dataset instance with attributes x 1 , . . . , x n DS p = { c1 , . . . , cN1 }} Crafted dataset instance with attributes x 1 , . . . , x n DS i c = { c1 , . . . , cNi }} Contaminated dataset instance at time point i β Data poisoning percentage for DS v λ i Data poisoning rate for DS i c B 1
The result of feeding DS v to a learning algorithm B 2

The result of feeding DS u to a learning algorithm

ds(B 1 , B 2 )
Distance function between models B 1 and

B 2 Conf (c, B 1 )
Conflict measure of how well the case c fits B 1

Long-duration Data Poisoning Attacks

In our earlier work data poisoning attacks [START_REF] Alsuwat | Cyber attacks against the pc learning algorithm[END_REF], we studied data poisoning attacks against Bayesian structure learning algorithms. For a Bayesian structure learning algorithms, given the dataset, DS v , and the corresponding model, B 1 (Equation 1), a malicious attacker attempts to craft an input dataset, DS p , such that this contaminated dataset will have an immediate impact on DS v and thereby on B 1 . The defender periodically retrains the machine learning system to recover the structure of the new model, B 2 , using DS u , the combination of the original dataset DS v and the attacker supplied DS p . We call such an attack a "one-step" data poisoning attack as malicious attackers send all contaminated cases at once. In this section, we introduce long-duration data poisoning attacks against structure learning algorithms. Long-duration poisoning attacks are adversarial multi-step attacks in which a malicious attacker attempts to send contaminated cases over a period of time, t = {1, 2, . . . , w}. That is, at every time point i, a malicious attacker sends in a new dataset, DS i c , which contains N i cases, λ i N i of which are corrupted cases for some 0 < λ i < 1 (λ i is the data poisoning rate at which we allowed to add contaminated cases to DS i c at iteration i). Even though the defender periodically retrains the model, B 2 , at time i using the dataset

DS i l d , which is equal to DS v ∪ i t=1 DS t c
, it is not easy to detect the long-duration attack since such an attack is not instantaneous.

By the end of the long-duration poisoning attack, i.e., at time point w, the attacker would have injected w t=1 DS t c to DS v , resulting in a new dataset, DS w l d . We assume that attackers cannot add more than βN cases to DS v (i.e., 0 < w t=1 λ t N t < βN ). When the defender retrains the model, B 2 , using the dataset DS w l d , the attack will dramatically affect the resulting model. Note that this attack is sophisticated since the attacker may not need to send contaminated cases with the last contaminated dataset (the w th dataset) in the long-duration attack, i.e., DS w c may trigger the attack with no poisoned cases, as our experiments show.

We propose causative, long-duration model invalidation attacks against Bayesian network structure learning algorithms. Such attacks are defined as malicious active attacks in which adversarial opponents attempt to arbitrarily corrupt the structure of the original Bayesian network model in any way. The goal of adversaries in these attacks is to poison the validated training dataset, DS v , over a period of time t = {1, . . . , w} using the contaminated dataset w i=1 DS t c such that DS v will be no longer valid. We categorize causative long-duration model invalidation attacks against Bayesian network structure learning algorithms into two types: Due to space limitation, in this work, we only provide a brief description of long-duration data poisoning attacks that aim to achieve a certain attack by sending in contaminated cases over a period of time t. We refer the reader to our technical report [START_REF] Alsuwat | Long duration data poisoning attacks on Bayesian networks[END_REF] for the full algorithmic details.

Framework for Detecting Data Poisoning Attacks

In this section, we present our detective framework for data poisoning attacks. Our techniques build on the data sanitization approach that was proposed by Nelson et al. [START_REF] Nelson | Misleading learners: Co-opting your spam filter[END_REF]. We extend Nelson et al. approach such that it is applicable to detect both one-step and long-duration causative attacks.

The main components of our framework are: (1) Structure learning Algorithms: the PC learning algorithm, (2) FLoD: first layer of detection, and (3) SLoD: second layer of detection.

First Layer of Detection: In the FLoD, our framework uses "Reject On Negative Impact" defense [START_REF] Nelson | Misleading learners: Co-opting your spam filter[END_REF] to examine the full dataset (DS v ∪ DS p ) to detect the impact of DS p on DS v . The attacker aims to use DS p to change the Markov equivalence class of the validated model, B 1 . The first layer of detection detects the impact of adversarial attacks that aim to corrupt the model B 1 using onestep data poisoning attacks. FLoD is useful for efficiently filtering obvious data poisoning attacks.

Algorithm 1: First Layer of Detection

Input :

DS v = {c 1 , . . . , c N } and DS p = { c1 , . . . , cN1 } Output: ds(B 1 , B 2 ) 1 Generate B 1 from DS v ; 2 Generate B 2 from DS v ∪ DS p ; 3 Calculate ds(B 1 , B 2 )
as described in section 2;

4 if ds(B 1 , B 2 ) > 0 then 5 Return ds(B 1 , B 2 ); 6
Send DS p to be checked offline; In the FLoD, we use the distance function ds described in section 2 as a method for detecting the negative impact of DS p on the validated model B 1 . If ds(B 1 , B 2 ) is greater than zero, then the new incoming dataset, DS p , is potentiality malicious. In this case, we sent DS p to be checked offline. Otherwise, we proceed with the second layer of detection, SLoD, looking for long-duration data poisoning attacks.

Algorithm 1 provides algorithmic details of FLoD detect one-step data poisoning attacks.

Second Layer of Detection: In the SLoD, our framework uses "Data Conflict Analysis" [START_REF] Nielsen | Bayesian networks and decision graphs[END_REF] to examine the newly incoming dataset DS p to detect if DS p has conflicting cases with the original model B 1 . The Second layer of detection detects sophisticated adversarial attacks that aim to corrupt the model B 1 , such as long-duration data poisoning attacks.

Algorithm 2: Second Layer of Detection

Input :

DS v = {c 1 , . . . , c N } and DS p = { c1 , . . . , cN1 } Output: DS v , DS conf . 1 Generate B 1 from DS v ; 2 DS conf = φ; 3 for every case c in DS p do 4 Calculate P (v)
i.e., the probability of the evidence for c; Send DS conf to be checked offline;

5 if P (v) = 0 then 6 DS conf = DS conf ∪ {c} i.e.,
17 end 18 DS v = DS v ∪ (DS p \DS conf ); 19 Return DS v , DS conf ; 20 end
In the SLoD, we use the value of the conflict measure Conf (c, B 1 ) described in section 2 as a method for detecting whether or not a case, c, in the newly incoming dataset, DS p , is conflicting with the original model B 1 . If the P (v) is equal to zero, then the case c is inconsistent with the validated model B 1 . If Conf (c, B 1 ) is positive, then the case c is incompatible with the validated model B 1 . In these two situations, we add inconsistent and incompatible cases to DS conf . DS conf is then sent to be checked offline. Thereby, the model B 1 will be retrained according to the following equation:

B 1 = BN Algo(DS v ) where DS v = DS v ∪ (DS p \DS conf ).
Algorithm 2 provides algorithmic details of the SLoD detect long-duration data poisoning attacks.

The process of applying our framework is summarized in Figure 1. The workflow of our framework is described as follows: (1) A validated dataset, DS v , which is a clean training dataset that is used to recover a validated machine learning model B 1 . (2) A new incoming dataset, DS p , which is coming from an untrusted source and a potentially malicious dataset, is used along with DS v to learn B 2 .

(3) FLoD checks for one-step data poisoning attacks. If model change occurs (i.e., ds(B 1 , B 2 ) > 0), send DS p for offline evaluation. Else, (4) SLoD checks for long-duration data poisoning attacks. If the value of conflict measure is positive (i.e., Conf (c, B 1 ) > 0), send conflicting data to offline evaluation. Else, update the validated dataset.

Empirical Results

We implemented our prototype system using the Chest Clinic Network [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF]. The Chest Clinic Network was created by Lauritzen and Spielgelhalter [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF] and is widely used in Bayesian network experiments. As shown in Figure 2, Visit to Asia is a simple, fictitious network that could be used at a clinic to diagnose arriving patients. It consists of eight nodes and eight edges. The nodes are as follows:

( We used the Chest Clinic Network to demonstrate the data poisoning attacks and our detection capabilities. In each experiment, we manually generated poisoned datasets. Given the contingency table of two random variables A and B in a Bayesian network model with i and j states, respectively. To introduce a malicious link between A and B, we add corrupt cases to the cell with the highest test statistic value in the contingency table. To remove the link between A and B, we transfer cases from the cell with the highest test statistics value to the one with the lowest value.

One-step Data Poisoning Attacks

To set up the experiment, we implemented the Chest Clinic Network using Hugin TM Research 8.1. We then used Hugin TM case generator [START_REF] Madsen | The hugin tool for probabilistic graphical models[END_REF][START_REF] Olesen | ahugin: A system creating adaptive causal probabilistic networks[END_REF] to generate a simulated dataset of 20, 000 cases. We call this dataset DS v . Using the PC algorithm on dataset DS v with 0.05 significance setting [START_REF] Madsen | The hugin tool for probabilistic graphical models[END_REF], the resulting validated structure, B 1 = P C Algo(DS v ), is given in Figure 3. While the two networks in Figures 2 and3 belong to different Markov equivalence classes, we will use the validated network B 1 as the starting point of our experiment.

We evaluated the effectiveness of one-step data poisoning attacks against the validated dataset DS v (i.e., against the validated model B 1 ). An attacker aims to use one-step data poisoning attacks to inject in a contaminated dataset DS p into DS v , resulting in the dataset DS u . The defender retrains the machine learning model by feeding the new dataset DS u to the PC learning algorithm (B 2 = P C Algo(DS u )), resulting in the model B 2 .

We aim to study the attacker's goals, i.e., study the feasibility of one-step data poisoning attacks, which might be as follows: (i) introduce new v-structures: that is, (1) add the links D -S and S -E to the serial connections D → B → S and S → L → E, respectively, and (2) add the link A -E to the diverging connection A ← T → E; (ii) break an existing v-structure T → E ← L, i.e., shield the collider E; (iii) remove the weakest edge, i.e., remove the edge T → A; and (iv) add the most believable edge, i.e., add the edge B → L. (Note that, for finding the weakest link in a given causal model or the most believable link to be added to a causal model, we refer the readers to our previous works [START_REF] Alsuwat | Cyber attacks against the pc learning algorithm[END_REF][START_REF] Alsuwat | How to generate the network you want with the pc learning algorithm[END_REF] for technical details on how to measure link strength of causal models).

In all of the scenarios, the attacker succeeded in corrupting the new model that was going to be learned by the defender, the model B 2 . The attacker had to introduce a dataset DS p with 67 corrupt cases (data items) to introduce the link D-S in the newly learned model B 2 . To introduce links S-E and A-E required 21 and 7 corrupt cases, respectively. To shield the collider E, the attacker only needed 4 poisoning data items. The attacker had to modify only 3 cases to break the weakest link A -T . To add the most believable link B -L required to only 7 corrupt data items.

Long-duration Data Poisoning Attacks

To set up the implementation of long-duration attacks, let DS v be a validated training dataset with attributes x 1 , . . . , x n and N cases, and β be data poisoning rate at which attackers are allowed to add new "contaminated" cases to DS v . Let DS i c be a newly crafted dataset also with attributes x 1 , . . . , x n and N i cases, and λ i be data poisoning rate at which attackers allowed to add new crafted cases to DS i c (we default set 0 ≤ w t=1 λ i N i ≤ βN ). We start by calculating τ , which is the maximum number of poisoned cases that could be added to DS v over a period of time t = {1, . . . , w}. We then learn the structure of the validated model B 1 from DS v using the PC algorithm.

We then iterate w times. In each iteration t, we generate a clean dataset DS t clean and a poisoned dataset DS t p . We let DS t c = DS t clean ∪ DS t p (note that, DS t c has N t cases, λ t N t of which are poisoned). After that, we create the union of DS t c and DS v , resulting in DS t l d , which is used to learn the structure of model B 2 . Note that, in each iteration the number of cases in DS t p should be between 0 (i.e., no poisoned cases) and τ w , which is the maximum number of poisoned cases that could be added to DS t c in the t th iteration.

We terminate after iteration w. If w t=1 λ t N t ≤ βN , we return DS t l d ; otherwise, we print a failure message since implementing the long-duration attack on DS v is not feasible.

We assumed that w = 4, which means that the attacker is allowed to send in four contaminated datasets to achieve the long-duration data poisoning attack. We divided the 20, 000 case dataset that was generated for one-step data poisoning attacks in section 5.1 into five datasets as follows: 12, 000 cases are used as DS v ; and the rest is divided into four datasets of 2, 000 cases each. We call these four datasets DS 1 Clean , DS 2 Clean , DS 3 Clean , and DS 4 Clean . Using the PC algorithm on dataset DS v with 0.05 significance setting [START_REF] Madsen | The hugin tool for probabilistic graphical models[END_REF], the resulting validated structure, B 1 = P C Algo(DS v ), is given in Figure 3, which is the starting point of this experiment.

We evaluated the effectiveness of long-duration data poisoning attacks against the validated dataset DS v (i.e., against the validated model B 1 ). At every time point t = {1, . . . , w}, the attacker injects a contaminated dataset DS t Crafted into DS t Clean , resulting in the dataset DS t c . This resulting dataset is then sent in as a new source of information. The defender receives DS t c and retrains the validated model, B 1 , by creating the union of DS v and the new incoming dataset DS t c and feeding them to the PC algorithm, resulting in the model B 2 (i.e.,

B 2 = P C Algo(DS v ∪ DS t c
)). The results of our experiments are presented in Table 1. In all of the scenarios, the attacker succeeded in achieving the desired modification. In our experiments, we assumed that t = {1, . . . , 4}. For every one of the studied long-duration attacks on the dataset DS v (Tables 1a, 1b, 1c, 1d, 1e, and 1f), the adversary had to send in the attack over 4 datasets. That is, at every time point t (for t = 1, . . . , 4), the attacker had to create the union of DS t Clean and DS t Crafted resulting in DS t c , which was going to be sent to the targeted machine learning system as a new source of information. The defender, on the other hand, retrained the machine learning model every time a new incoming dataset DS t c arrived. Note that, in our experiments, long-duration attacks require the same number of contaminated cases as the one-step data poisoning attacks. An important observation is that the malicious attacker does not always have to send poisoned cases in the last dataset that will trigger the attack. For instance, in our experiments, when introducing the link A → E (Table 1a), shielding collider E (Table 1b), and removing the weakest edge (Table 1f), the last contaminated dataset, DS 4 c , had contaminated cases, which makes it impossible for the defender to find what caused a change in the newly learned model.

Discussion: Detecting Data Poisoning Attacks

The results of using our framework to detect one-step data poisoning attacks are presented in Table 2. Algorithm 1 succeeded to detect the negative impact (i.e., the change in the Markov equivalence class) of the new incoming dataset DS p on the validated model B 1 . The results using our framework to detect long-duration data poisoning attacks are summarized in Table 3. Algorithm 2 succeeded to detect the longduration impact of DS c on the validated dataset DS v . Note, that FLoD using traditional reject on negative impact was not able to detect long-duration attacks. However, when using the SLoD, we were able to detect the conflicting cases, which are either inconsistent or incompatible with the original validated model B 1 (A detailed experiment is presented in Figure 4). Such cases might be exploited by a malicious adversary to trigger the long-duration attack at a later time. Also, in some attacks no poisoned cases are required to be sent with DS c to trigger the long-duration attack, which is very hard to detect. In summary, our 2-layered approach was able to detect both one-step and long-duration attacks. Moreover, our solution did not lose all the incoming datasets; we only send conflicting cases to be checked offline. We have carried out over 200 experiments for long-duration attacks. A comprehensive description of these experiments is given in [START_REF] Alsuwat | Long duration data poisoning attacks on Bayesian networks[END_REF].

Related Work

In this section, we will give a brief overview of adversarial machine learning research; focusing on data poisoning.Recent surveys on adversarial machine learning can be found in [START_REF] Barreno | The security of machine learning[END_REF][START_REF] Gardiner | On the security of machine learning in malware c&c detection: A survey[END_REF][START_REF] Liu | A survey on security threats and defensive techniques of machine learning: a data driven view[END_REF]. Data Poisoning Attacks: As machine learning algorithms have been widely used in security-critical settings such as spam filtering and intrusion detection, adversarial machine learning has become an emerging field of study. Attacks against machine learning systems have been organized by [START_REF] Barreno | The security of machine learning[END_REF][START_REF] Barreno | Can machine learning be secure?[END_REF][START_REF] Huang | Adversarial machine learning[END_REF] according to three features: Influence, Security Violation, and Specificity. Influence of the attacks on machine learning models can be either causative or exploratory. Causative attacks aim to corrupt the training data whereas exploratory attacks aim to corrupt the classifier at test time. Security violation of machine learning models can be a violation of integrity, availability, or privacy. Specificity of the attacks can be either targeted or indiscriminate. Targeted attacks aim to corrupt machine learning models to misclassify a particular class of false positives whereas indiscriminate attacks have the goal of misclassifying all false positives. Evasion attacks and Data poisoning attacks are two of the most common attacks on machine learning systems [START_REF] Huang | Adversarial machine learning[END_REF]. Evasion attacks [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF][START_REF] Kantchelian | Evasion and hardening of tree ensemble classifiers[END_REF][START_REF] Laskov | Practical evasion of a learning-based classifier: A case study[END_REF] are exploratory attacks at the testing phase. In an evasion attack, an adversary attempts to pollute the data for testing the machine learning classifier; thus causing the classifier to misclassify adversarial examples as legitimate ones. Data poisoning attacks [START_REF] Alfeld | Data poisoning attacks against autoregressive models[END_REF][START_REF] Biggio | Poisoning attacks against support vector machines[END_REF][START_REF] Koh | Understanding black-box predictions via influence functions[END_REF][START_REF] Mei | The security of latent dirichlet allocation[END_REF][START_REF] Mei | Using machine teaching to identify optimal training-set attacks on machine learners[END_REF][START_REF] Yang | Generative poisoning attack method against neural networks[END_REF] are causative attacks, in which adversaries attempt to corrupt the machine learning classifier itself by contaminating the data in the training phase.

Data poisoning attacks are studied extensively during the last decade [START_REF] Alsuwat | Cyber attacks against the pc learning algorithm[END_REF][START_REF] Biggio | Poisoning complete-linkage hierarchical clustering[END_REF][START_REF] Biggio | Poisoning attacks to compromise face templates[END_REF][START_REF] Biggio | Poisoning adaptive biometric systems[END_REF][START_REF] Biggio | Poisoning attacks against support vector machines[END_REF][START_REF] Biggio | Is data clustering in adversarial settings secure?[END_REF][START_REF] Koh | Understanding black-box predictions via influence functions[END_REF][START_REF] Mei | Using machine teaching to identify optimal training-set attacks on machine learners[END_REF][START_REF] Muñoz-González | Towards poisoning of deep learning algorithms with backgradient optimization[END_REF][START_REF] Yang | Generative poisoning attack method against neural networks[END_REF]. However, attacks against Bayesian network algorithm are limited. In our previous work, we were addressed data poisoning attacks against Bayesian network algorithms [START_REF] Alsuwat | Cyber attacks against the pc learning algorithm[END_REF][START_REF] Alsuwat | Bayesian structure learning attacks[END_REF][START_REF] Alsuwat | How to generate the network you want with the pc learning algorithm[END_REF]. We studied how an adversary could corrupt the Bayesian network structure learning algorithms by inserting contaminated data into the training phase. We showed how our novel measure of strengths of links for Bayesian networks [START_REF] Alsuwat | How to generate the network you want with the pc learning algorithm[END_REF] can be used to do a security analysis of attacks against Bayesian network structure learning algorithms. However, our approach did not consider long-duration attacks. Defenses and Countermeasures: Detecting adversarial input is a challenging problem. Recent research [START_REF] Carlini | Adversarial examples are not easily detected: Bypassing ten detection methods[END_REF][START_REF] Feinman | Detecting adversarial samples from artifacts[END_REF][START_REF] Lu | Safetynet: Detecting and rejecting adversarial examples robustly[END_REF] illustrate these challenges. Our work ad-dresses these issues in the specific context of Bayesian network structure learning algorithms. Data sanitization is a best practice for security optimization in the adversarial machine learning context [START_REF] Chan | Data sanitization against adversarial label contamination based on data complexity[END_REF]. It is often impossible to validate every data source. In the event of a poisoning attack, data sanitization adds a layer of protection for training data by removing contaminated samples from the targeted training data set prior to training a classifier. Reject on Negative Impact is one of the widely used method for data sanitization [START_REF] Barreno | The security of machine learning[END_REF][START_REF] Chan | Data sanitization against adversarial label contamination based on data complexity[END_REF][START_REF] Liu | A survey on security threats and defensive techniques of machine learning: a data driven view[END_REF]. Reject on Negative Impact defense assesses the impact of new training additions, opting to remover or discard samples that yield significant, negative effects on the observed learning outcomes or classification accuracy [START_REF] Barreno | The security of machine learning[END_REF][START_REF] Chan | Data sanitization against adversarial label contamination based on data complexity[END_REF]. The base training set is used to train a classifier, after which, the new training instance is added and a second classifier is trained [START_REF] Barreno | The security of machine learning[END_REF]. In this approach, classification performance is evaluated by comparing error rates (accuracy) between the original and the new, retrained classifier resulting from new sample integration [START_REF] Liu | A survey on security threats and defensive techniques of machine learning: a data driven view[END_REF]. As such, if new classification errors are substantially higher compared to the original or baseline classifier, it is assumed that the newly added samples are malicious or contaminated and are therefore removed in order to maximize and protect classification accuracy [START_REF] Barreno | The security of machine learning[END_REF].

Conclusion and Future Work

Data integrity is vital for effective machine learning. In this paper, we studied data poisoning attacks against Bayesian network structure learning algorithms. We demonstrated the vulnerability of the PC algorithm against one-step and long-duration data poisoning attacks. We proposed a 2-layered framework for detecting data poisoning attacks. We implemented our prototype system using the Chest Clinic Network which is a widely used network in Bayesian networks. Our results indicate that Bayesian network structure learning algorithms are vulnerable to one-step and long-duration data poisoning attacks. Our framework is effective in detecting both one-step and long-duration data poisoning attacks, as it thoroughly validates and verifies training data before such data is being incorporated into the model.

Our ongoing work focuses on offline validation of potentially malicious datasets. Currently, our approach detects datasets that either change the Bayesian network structure (distance measure) or in conflict with the validated model (conflict measure). We are investigating methods for 1) distinguishing actual model shift from model enrichment, i.e., our initial model was based on data that was not fully representative of the "true" distribution, and 2) determining if cases are truly conflicting or again if the initial model poorly approximates the "true" distribution. We are also investigating the applicability of Wisdom of the Crowd (WoC) [START_REF] Yi | The wisdom of the crowd in combinatorial problems[END_REF]. Rather than human experts, we plan to use an ensemble of classifiers, i.e., take the votes of competing algorithms instead of the votes of humans. In the case of an ensemble of classifiers, one could investigate the likelihood of unexpected cases and adjust the sensitivity to anomalies by how much perturbation it causes in the model.

A Causative, Long-duration Model Invalidation Attacks

In this Appendix, we explain the two subtypes of each of the causative longduration attacks which are based on the notion of d-separation and marginal independence tests.

The causative long-duration attacks which are based on the notion of dseparation are divided into two main subtypes as follows: We divide the causative long-duration attacks which are based on marginal independence tests into two main subtypes: (i) Removing the weakest edge attacks, in which adversarial opponents attempt to poison the validated learning dataset, DS v , using contaminated datasets, w t=1 DS t c , over a period of time t with the ultimate goal of removing weak edges. Note that, a weak edge in a Bayesian model, B 1 , is the easiest edge to be removed from B 1 . We use our previously defined link strength measure to determine such edges [START_REF] Alsuwat | How to generate the network you want with the pc learning algorithm[END_REF]. (ii) Adding the most believable yet incorrect edge attacks, in which adversaries can cleverly craft their input datasets, w t=1 DS t c , over a period of time t to poison DS v so that adding the most believable yet incorrect edge is viable. The most believable yet incorrect edge is a newly added edge to model, B 1 , with the maximum amount of belief. We use our link strength measure defined in [START_REF] Alsuwat | How to generate the network you want with the pc learning algorithm[END_REF] to determine such edges.

1 . 3 .

 13 The defender: The defender uses a validated dataset DS v , to produce a validated Bayesian network model B 1 . 2. The malicious attacker: The attacker injects a contaminated dataset, DS p , to be unioned with the original dataset, DS v , with the goal of changing the Markov equivalence class of the original validated model, B 1 . Evaluation by the defender: -The defender feeds the new dataset DS u (Note that, DS u = DS v ∪ DS p ) to a Bayesian network structure learning algorithm, resulting in B 2 . -The defender calculates the distance function ds(B 1 , B 2 ). -If ds(B 1 , B 2 ) = 0, then Bayesian models B 1 and B 2 are identical. Otherwise, i.e., ds(B 1 , B 2 ) > 0, the newly learned Bayesian model B 2 is different from the original validated model B 1 . -For each case c, the defender calculates the value of conflict measure Conf (c, B 1 ). -If Conf (c, B 1 ) is positive, then the case c conflict with the Bayesian model B 1 . Otherwise, the newly incoming case is validated and added to DS v .

( 1 )

 1 Model invalidation attacks based on the notion of d-separation and (2) Model invalidation attacks based on marginal independence tests. Causative, long-duration model invalidation attacks which are based on the notion of d-separation are adversarial attacks in which adversaries attempt to introduce a new link in any triple (A -B -C) in the original Bayesian network model, B 1 . The goal of the introduced malicious link, (A -C), is to change the independence relations and the Markov equivalence class of B 1 . Within such attacks, we can identify two subtypes: (i) Creating a New Converging Connection (V-structure), and (ii) Breaking an Existing Converging Connection (Vstructure). See Appendix A for more details. Causative, long-duration model invalidation attacks which are based on marginal independence tests are adversarial attacks in which adversaries attempt to use marginal independence tests in order to change the conditional independence statements between variables in the original model, B 1 . Such attacks can be divided into two main subtypes: (i) Removing the Weakest Edge, and (ii) Adding the Most Believable Edge yet incorrect Edge. See Appendix A for more details.

Fig. 1 :

 1 Fig. 1: Framework for detecting data poisoning attacks.

Fig. 2 :Fig. 3 :

 23 Fig. 2: The original Chest Clinic Network.

(a) DS 1 c

 1 has 20 incompatible cases. (b) DS 2 c has 20 incompatible cases. (c) DS 3 c has 23 incompatible cases. (d) DS 4 c has 4 incompatible cases.

Fig. 4 :

 4 Fig. 4: The result of using SLoD to detect a long-duration attack that aims to introduce the link D → S in the Chest Clinic dataset, DS v . We present the case number in DS t c as the variable on the X-axis and the value our conflict measure Conf (c, B 1 ) as the variable on the Y-axis. A case is incompatible (conflicting) with the validated model B 1 if Conf (c, B 1 ) > 0.

  (i) Creating a new converging connection (v-structure) attacks, in which adversaries attempt to corrupt the original Bayesian network model, B 1 , by poisoning the validated dataset, DS v , using contaminated datasets w t=1 DS t c . Attackers aim to introduce a new v-structure by adding the link A → C to the serial connection A → B → C, link C → A to the serial connection A ← B ← C, or either one of the links A → C or C → A to the diverging connection A ← B → C in B 1 . (ii) Breaking an existing converging connection (v-structure) attacks, in which malicious attackers attempt to corrupt the original model, B 1 , by shielding existing colliders (v-structures). Such adversarial attacks can be performed by poisoning the dataset, DS v , over time using the poisoned datasets w t=1 DS t c such that new links are introduced to marry the parents of unshielded colliders in B 1 (i.e., add the link A → C to the converging connection A → B ← C).

  1 cases, into the validated training dataset, DS v . A learning error occurs if DS u , obtained by the union of DS v and DS p , results in a Bayesian network learning model B 2 (shown in Equation

  then there is no edge (neither e 1 nor e 2 ) between vertex x u and vertex x v in either models B 1 and B 2 . Hence, ds xuxv (B 1 , B 2 ) = 0.Status 2 (True Positive Edges): if ((e 1 ∈ E 1 && e 1 ∈ E 2 ) || (e 2 ∈ E 1 && e 2 ∈ E 2 )),then the same edge (either e 1 or e 2 ) appears from vertex x u to vertex x v in both models B 1 and B 2 . Hence, ds xuxv (B 1 , B 2 ) = 0. Status 3 (False Negative Edges): if ((e 1 || e 2 ∈ E 1 ) && (e 1 && e 2 ∈ E 2 )), then there is an edge (either e 1 or e 2 ) from vertex x u to vertex x v in B 1 that does not exist in B 2 . Without loss of generality, assume that the deleted edge from B 1 is e 1 , then if the indegree of vertex x v , denoted as indegree(x v ), which is the number if edge incoming to vertex x v , is greater than 1, then ds xuxv (B 1 , B 2 ) = 8 (deleting e 1 breaks an existing v-structure and changes the Markov equivalence class); otherwise, ds xuxv (B 1 , B 2 ) = 4 (deleting e 1 does not break an existing v-structure, but it changes the Markov equivalence class). Status 4 (False Positive Edges): if ((e 1 && e 2 ∈ E 1 ) && (e 1 || e 2 ∈ E 2 )), then there is an edge (either e 1 or e 2 ) from vertex x u to vertex x v in B 2 but not the in B 1 . Without loss of generality, assume that the added edge to B 2 is e 1 , then if the indegree of vertex x v , is greater than 1, then ds xuxv (B 1 , B 2 ) = 8 (adding e 1 introduces a new v-structure and changes the Markov equivalence class); otherwise, ds xuxv (B 1 , B 2 ) = 4 (adding e 1 does not introduce a new v-structure, but it changes the Markov equivalence class). Status 5 (False Positive and True Negative Edges): if ((e 1 ∈ E 1 && e 2 ∈ E 2 ) && (e 1 ∈ E 2 && e 2 ∈ E 1 )), then the edge from vertex x u to vertex x v in B 1 is the reverse of the edge from vertex x u to vertex x v in B 2 . Without loss of generality, assume that there is an edge, e 1 , from x u to x v in B 1 , then e 2 is the reverse of e 1 in B 2 . If the indegree of vertex x u , is greater than 1, then

	ds xuxv (B 1 , B 2 ) = 8 (reversing e 1 introduces a new v-structure and changes
	the Markov equivalence class); otherwise, ds xuxv (B 1 , B 2 ) = 2 (reversing e 1
	does not introduce a new v-structure, but it changes the Markov equivalence
	class).

Table 2 :

 2 Results of using FLoD to detect one-step poisoning attacks.

	Attack	Attack's class	ds(B1, B2) score
	Introduce the link A → E	New v-structure	12
	Introduce the link D → S	New v-structure	24
	Introduce the link S → E	New v-structure	54
	Introduce the link T → L Shield an existing collider	16
	Remove the link A → T	Delete the weakest link	4
	Introduce the link B → L Add the most believable link	32

Table 3 :

 3 Results of SLoD to detect long-duration data poisoning attacks.

	Attack	Attack's class	Algorithm 2 decision
	Introduce A → E	New v-structure	Inconsistent observations
	Introduce D → S	New v-structure	Incompatible observations
	Introduce S → E	New v-structure	Inconsistent observations
	Introduce T → L Shield an existing collider	Inconsistent observations
	Remove A → T	Delete weakest link	Inconsistent\Incompatible observations
	Introduce B → L Add most believable link	Inconsistent observations