Julien Boite
email: julien.boite@thalesgroup.com

Pierre-Alexis Nardin
email: pierre-alexis.nardin@thalesgroup.com

Filippo Rebecchi
email: filippo.rebecchi@thalesgroup.com

Mathieu Bouet
email: mathieu.bouet@thalesgroup.com

Vania Conan
email: vania.conan@thalesgroup.com

StateSec: Stateful Monitoring for DDoS Protection in Software Defined Networks

Software-Defined Networking (SDN) allows for fast reactions to security threats by dynamically enforcing simple forwarding rules as counter-measures. However, in classic SDN all the intelligence resides at the controller, with the switches only capable of performing stateless forwarding as ruled by the controller. It follows that the controller, in addition to network management and control duties, must collect and process any piece of information required to take advanced (stateful) forwarding decisions. This threatens both to overload the controller and to congest the control channel. On the other hand, stateful SDN represents a new concept, developed both to improve reactivity and to offload the controller and the control channel by delegating local treatments to the switches. In this paper, we adopt this stateful paradigm to protect end-hosts from Distributed Denial of Service (DDoS). We propose StateSec, a novel approach based on in-switch processing capabilities to detect and mitigate DDoS attacks. StateSec monitors packets matching configurable traffic features (e.g., IP src/dst, port src/dst) without resorting to the controller. By feeding an entropy-based algorithm with such monitoring features, StateSec detects and mitigates several threats such as (D)DoS and port scans with high accuracy. We implemented StateSec and compared it with a state-of-the-art approach to monitor traffic in SDN. We show that StateSec is more efficient: it achieves very accurate detection levels, limiting at the same time the control plane overhead.

I. INTRODUCTION

Denial of Service (DoS) attacks gained momentum in the recent years, threatening both network and web infrastructures around the world. By using distributed spambots (DDoS) and/or sophisticated reflection techniques (DRDoS), attackers can easily generate traffic volumes in the order of Tbps [START_REF] Conan | World's largest 1 Tbps DDoS Attack launched from 152,000 hacked Smart Devices[END_REF], also causing catastrophic consequences, as proven by the Dyn attack in October, 2016 that led to major disruptions of internet services both in US and Europe [START_REF] York | Dyn Statement on 10/21/2016 DDoS Attack[END_REF].

Following a recent trend, traditional network security appliances are migrating towards programmability concepts. Indeed, Software-Defined Networking (SDN) enables an easier network and service management, resulting an interesting means to enforce security policies. In particular, many previous works in the literature illustrated how to take benefit from the flexibility of SDN in order to quickly setup countermeasures to security threats, such as DDoS, generally by dynamically enforcing simple forwarding rules [START_REF] Giotis | Combining OpenFlow and sFlow for an effective and scalable anomaly detection and mitigation mechanism on SDN environments[END_REF]. Also, security equipment manufacturers have already started to develop and sell commercial products based on SDN concepts [START_REF] Radware | DefenseFlow -SDN Based Network DDoS, Application DoS and APT Protection[END_REF]. Following the classical SDN approach -all the network intelligence resides at the controller, and the switches have the simple task of enforcing a stateless forwarding as dictated by the controller -most of the state-of-the-art approaches rely completely on the controller for dealing with threat protection processes. In this case, a controller has to deal both with stateful forwarding decisions and application processing, thus risking being overloaded and failing consequently.

Recently, a novel approach called stateful SDN has been proposed to improve reactivity and to offload the controller and the control plane channel by delegating some local treatments to the switches [START_REF] Bianchi | OpenState: Programming Platform-independent Stateful OpenFlow Applications Inside the Switch[END_REF]. In stateful SDN, the forwarding logic is modeled as multiple Finite State Machines (FSM) implemented into switches as state tables associated with preconfigured flow tables in the forwarding pipeline.

In this paper, we start from the stateful SDN concept as defined in [START_REF] Bianchi | OpenState: Programming Platform-independent Stateful OpenFlow Applications Inside the Switch[END_REF], and we design on top of it a novel DDoS detection and mitigation strategy named StateSec to showcase the benefits of such an approach. StateSec exploits the efficient monitoring capabilities offered by stateful SDN, namely the delegation of local processing to switches, to reduce the burden on the controller, still achieving very accurate detection levels. StateSec consists of three main steps, shown in Fig. 1 and having the following properties:

• Traffic monitoring of pertinent features (e.g., IP src, IP dst, port src, port dst) is handled inside the switch by using stateful programming, thus allowing scalable and very precise monitoring of traffic to feed the detection algorithm. • Anomaly detection is based on an entropy-based algorithm [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF] currently implemented on the controller side (the detection could be integrated directly into the switch when Extended Finite State Machine (XFSM) [START_REF] Bianchi | Open Packet Processor: a programmable architecture for wire speed platform-independent stateful in-network processing[END_REF] will be available). By feeding this algorithm with exact information about the traffic, we manage to detect and differentiate several types of attacks with high accuracy (e.g., DoS, DDoS, Port Scan, etc.). • Whenever anomalies are detected, mitigation actions are taken at the controller by setting up the most appropriate set of reactions. For instance, DoS attacks originating from a single source are simply filtered. However, more complex mitigation actions can be applied in case of evolved attacks (e.g., rate-limiting, forwarding suspicious traffic towards a blackhole or a DPI engine, etc.). To validate the benefits of StateSec, we compare its performance against native OpenFlow monitoring and sFlow [START_REF]sFlow specification Version 5[END_REF], which is a well-known approach for traffic monitoring in SDN. Evaluations are carried out in a controlled environment that mimics a company-wide network deployment and the results confirm the effectiveness of StateSec in both reducing the overhead on the control plane and quickly detecting and mitigating ongoing DDoS attacks.

The remainder of this paper is structured as follows. In Section II, we discuss the related work. StateSec's design considerations are presented in Section III, and details on its current implementation are given in Section IV. The evaluation of StateSec with a DoS use case first, and then with different DDoS attacks is presented in Section V. Finally, Section VI draws the conclusions and points out future work.

II. RELATED WORK

Different types of DDoS attacks exist [START_REF] Douligeris | DDoS attacks and defense mechanisms: Classification and state-of-the-art[END_REF]. Their impact can be significant: they are able to generate such a huge amount of traffic causing targets to crash and the associated service(s) to become partially or totally unavailable. Detecting and mitigating DDoS attacks is far from being straightforward. First, they usually do not come from a single identified source, which makes remediation very difficult without also affecting legitimate traffic. Second, they appear either very suddenly, thus requiring fast reaction to counter their effects, or very slowly, thus making the detection even more complicated [START_REF] Park | Analysis of slow read dos attack[END_REF].

Simplicity and flexibility are some of the key features offered by SDN, making it an ideal candidate for managing network security. Hence, multiple SDN-based DDoS detection and mitigation schemes have been proposed in the literature. Some of them discuss the bottlenecks introduced by SDN (e.g., related to the flow tables exhaustion at switches and the controller overload), focusing on the protection of the network itself [START_REF] Dhawan | Sphinx: Detecting security attacks in software-defined networks[END_REF], [START_REF] Dharma | Time-based DDoS Detection and Mitigation for SDN Controller[END_REF]. Others deal more with the protection of communication endpoints (user terminals and application servers) [START_REF] Giotis | Combining OpenFlow and sFlow for an effective and scalable anomaly detection and mitigation mechanism on SDN environments[END_REF], [START_REF] Oktian | Mitigating Denial of Service (DoS) attacks in OpenFlow networks[END_REF]- [START_REF] Shin | AVANT-GUARD: Scalable and Vigilant Switch Flow Management in Software-Defined Networks[END_REF]. Similarly, in this paper we focus on the protection of the communication endpoints by taking advantage of SDN concepts.

In SDN, the controller has a global view of the network and interacts with switches using a dedicated protocol (e.g., Open-Flow [START_REF] Mckeown | OpenFlow: Enabling Innovation in Campus Networks[END_REF]). For this reason, implementing a DDoS protection application on top of the controller is somehow a standard approach. As a result, most of the related work describe methods implemented at the controller level. They mainly differ from each other depending on how they perform the three steps required to handle DDoS protection, namely 1) traffic monitoring, 2) attack detection, and 3) attack mitigation. For instance, a controller application can store information such as host/port bindings by frequently requesting switches for ports and flows statistics through standard OpenFlow messages [START_REF] Oktian | Mitigating Denial of Service (DoS) attacks in OpenFlow networks[END_REF]. It is thus possible to detect anomalies and react with Quality of Service and Block State mitigation actions. However, performing many, yet simple, computations on the controller side has a negative impact in terms of performance (e.g., throughput decrease, latency increase). Another option is to replicate the traffic towards an Intrusion Detection System (IDS) [START_REF] Chung | NICE: Network Intrusion Detection and Countermeasure Selection in Virtual Network Systems[END_REF]. Threat identification can be performed by correlating IDS alerts through attack graphs at the controller. Simpler yet powerful options are to use statistical tests [START_REF] Soldo | Traffic anomaly detection based on the ip size distribution[END_REF] or entropybased algorithms for anomaly detection [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF].

Regardless of the detection strategy employed, the native OpenFlow approach for monitoring, with the controller that periodically gathers the flow table entries to collect counters, has the unpleasant effect of congesting the control plane [START_REF] Giotis | Combining OpenFlow and sFlow for an effective and scalable anomaly detection and mitigation mechanism on SDN environments[END_REF]. Performance can be improved by using the sampling techniques of sFlow [START_REF]sFlow specification Version 5[END_REF]. However, sFlow must be carefully configured because the gains on the control plane load trades off the monitoring precision [START_REF] Mann | Living on the edge: Monitoring network flows at the edge in cloud data centers[END_REF]. Another option is to delegate as much computation as possible to the switches without compromising their performance, letting the controller being only in charge of mitigation [START_REF] Chin | An SDN-Supported Collaborative Approach for DDoS Flooding Detection and Containment[END_REF], [START_REF] Shin | AVANT-GUARD: Scalable and Vigilant Switch Flow Management in Software-Defined Networks[END_REF], [START_REF] Liu | One sketch to rule them all: Rethinking network flow monitoring with UnivMon[END_REF]. An emerging approach in this sense is stateful SDN [START_REF] Bianchi | OpenState: Programming Platform-independent Stateful OpenFlow Applications Inside the Switch[END_REF], that implies faster reaction times and less load over the control plane [START_REF] Bifulco | Improving SDN with InSPired switches[END_REF]. StateSec implements a stateful monitoring process running into the switch to gather very precise information and feed an entropy-based detection algorithm.

III. StateSec'S DESIGN BASICS

We have developed StateSec with the overall objective of protecting the communication endpoints from various security threats by employing SDN concepts. While throughout the paper we focus on (D)DoS attacks, StateSec can be easily employed to detect and mitigate other security threats such as port scans and ICMP flooding. In the design phase, we covered the three stages required to handle security management function, namely monitoring, detection and mitigation as depicted in Fig. 1. Our objective is a quick reaction time and a reduction of the overhead induced on the control channel by the communications between a switch and its controller. To this end, StateSec delegates part of the processing to the switches, following the stateful SDN principles [START_REF] Bianchi | OpenState: Programming Platform-independent Stateful OpenFlow Applications Inside the Switch[END_REF].

A. Monitoring & detection: local information stays local

As it emerges from Fig. 2, most of the related works perform all the three stages of the security management function at the controller. Following this classical approach, a SDN switch can be seen as a "dumb" device, with all the network intelligence located at the controller. This implies that, in order to monitor the traffic, the controller has to retrieve the entire flow table entries of any controlled switch. As we will see in Section IV-A, this approach is neither efficient nor scalable.

Instead, StateSec delegates monitoring and (in the near future) detection directly into the switches. Since both traffic monitoring and anomaly detection involve only local information, they can be done not necessarily at a central location (e.g., the controller). When an anomaly is detected, the switch notifies the controller so that counter-measures can be elaborated and applied, potentially network-wide. On the one hand, this model does not break the SDN philosophy: the controller retains the full control of the network management (e.g., by orchestrating mitigation actions when needed). On the other hand, switches have to become smarter in order to handle some local processing in place of the controller.

Since monitoring and detection are tightly coupled, one may want to process the monitored information directly where observed. StateSec targets this objective, thus saving the communications required to collect the information at a different place before processing it. However, delegating both monitoring and detection to a switch is not straightforward, since it depends on the abstraction used for the in-switch processing.

B. In-switch Processing Abstraction

StateSec relies on OpenState [START_REF]OpenState SDN project[END_REF], an open source implementation of the stateful SDN concept originally proposed in [START_REF] Bianchi | OpenState: Programming Platform-independent Stateful OpenFlow Applications Inside the Switch[END_REF] 1 . In-switch processing benefits from three additional components at the switch, as detailed in Fig. 3 For instance, this action could be employed to increase the counter associated with a given src IP key.

At the foundation of StateSec resides a programmable control loop embedded into the switch. State transitions are configured in the Flow tables and different actions can be applied depending on the state of a packet. The bottom line is that this stateful implementation allows the switch to 1) keep states associated with packet features, and 2) apply programmatically forwarding actions to packets according to these states. This approach goes in the direction of delegating tasks to the switch by programming it to perform conditional actions without resorting to the controller. OpenState also defines OpenFlowcompatible messages (by using the experimenter field) for the controller to configure and operate the above-mentioned structures in the switch (e.g., to get the state table entries).

C. What is possible today, what to expect for tomorrow?

The current OpenState implementation allows the switch to run only simple Finite State Machines (FSMs), where transitions are limited to a change of state. Even if this abstraction is already powerful (e.g., examples of applications are proposed in [START_REF]OpenState SDN project[END_REF]), it does not allow the switch to perform comparisons or complex computations yet. As a consequence, the detection process, which consists in comparing values against some thresholds, cannot be implemented inside the switch at the current stage of development. However, authors of OpenState are currently working on an extended abstraction to allow performing simple computations and memory operations during state transitions [START_REF] Bianchi | Open Packet Processor: a programmable architecture for wire speed platform-independent stateful in-network processing[END_REF]. StateSec is ready by design for this evolution. Indeed, we made the choice of a simple enough detection algorithm to be easily implemented with the operations that will be available in the extended abstraction. We expect its rapid integration into the switch as soon as the extended in-switch processing abstraction will be available.

IV. StateSec'S IMPLEMENTATION

Following the design decisions explained before, in this section we give an overview of the implementation of StateSec. We describe the three main stages required to handle the security management function, namely monitoring, detection and mitigation. StateSec implements the whole DDoS detection and mitigation process. In order to offer efficient, fast and reliable protection, it targets delegating both the monitoring and detection processes to the switch, while the controller elaborates and orchestrates the mitigation actions.

A. Monitoring

Information about traffic flows must be gathered in order to feed the detection algorithm. In particular, StateSec needs to collect information about each traffic feature taken into account in the detection. In our evaluations, we considered four main traffic features, namely dst IP, dst port, src IP, src port along with the information on the type of transport layer protocol employed (e.g., TCP, UDP, etc.). These features are employed in the detection process, so the switch needs to monitor them all.

Several methods already exist in SDN environments for traffic monitoring. In the following, we will list these approaches, highlighting also their drawbacks in terms of switching performance and control plane overhead. In effect, they turn out to be far from optimal for listing traffic features (e.g., destination IP addresses) and counting how many times they appear during a time interval. On the contrary, we developed a monitoring scheme that makes the tracking of traffic features quick and efficient, by exploiting the standalone reconfiguration of state tables offered by stateful in-switch processing.

1) Native OpenFlow Monitoring: the OpenFlow protocol defines the messages exchanged between the controller and a switch [START_REF] Mckeown | OpenFlow: Enabling Innovation in Campus Networks[END_REF]. The controller can natively gather the content of flow tables, including packet and byte counters associated to each entry, using the FlowStatsRequest message. While interesting for gathering aggregate flow statistics, the native OpenFlow monitoring does not scale well when listing and counting many traffic features with small granularity (e.g., statistics over each src IP or src port), as required for DDoS detection. Indeed, for any individual feature to monitor, this approach requires inserting a new flow rule in the flow table of the switch. A direct effect dictated by the increased size of flow tables is a reduction in forwarding performance. For instance, let consider one traffic feature: the destination IP address. Monitoring (e.g., listing and counting occurrences) all the destination IP addresses seen in packets' headers requires inserting one forwarding rule per IP address (a second flow rule may also be created for each IP address as source when the source IP address traffic feature is monitored). The same principle applies to each monitored traffic feature. With this approach, flow tables at switches are quickly overfilled, impacting negatively the performance of forwarding.

2) sFlow Sampling: sFlow is a well-known monitoring approach relying on packet sampling [START_REF]sFlow specification Version 5[END_REF]. An sFlow agent integrated into the switch is in charge of both sampling packets at a configurable rate [START_REF]sFlow sampling rates[END_REF] and transmitting their header to a collector, logically running near the controller. Many SDN equipment manufacturers have already integrated sFlow agents in their products. Moreover, one of the reference software switches, Open vSwitch (OVS), is also sFlow-compatible.

sFlow offers significant benefits when compared to the native OpenFlow approach, since the monitoring functionality is totally decoupled from forwarding, i.e., it is not necessary to add flow rules to ensure both forwarding and monitoring of flows. Based on sampled packets, the sFlow collector allows performing DDoS detection by maintaining an up-to-date list of features and counters. However, sampling may introduce a significant approximation, potentially harming the detection accuracy. Indeed, the configuration of the sampling rate is very important [START_REF] Mann | Living on the edge: Monitoring network flows at the edge in cloud data centers[END_REF], as we will show in Section V. Obviously, by lowering the sampling rate the precision decreases. On the other hand, a too high sampling rate concurs in overloading the control plane channel. Indeed, it is of paramount importanceand most of the time this step requires a fine tuning -to find the right tradeoff between detection accuracy and overhead on the control channel.

3) StateSec's State-Based Monitoring: we developed a new system that relies on stateful in-switch processing to implement forwarding-independent and modular monitoring of traffic features. StateSec's monitoring uses the state and flow tables in an OpenState-compliant switch to list features and count the exact number of times they appear, independently from the forwarding rules. Considering a single traffic feature, e.g., src IP, the controller initializes the following elements in the switch (cf. Fig. 3):

• a flow table is configured as stateful, and the controller inserts in the associated state table an entry to make any unknown key associated to the 'DEFAULT' state (in the case of counting packets, the 'DEFAULT' state is 0), • the lookup scope extracts from the packet headers the field corresponding to the monitored traffic feature (src IP in this example), • the update scope looks at the same field as the lookup scope, corresponding to the monitored traffic feature.

Finally advance. For traffic monitoring applications, in order to count the amount of packets having the same traffic feature, the next value of a state is simply an increment by one of its current value. We developed an efficient inc_state() action to perform such a state update, calling this action in a default flow table entry that matches all packets, whatever their state is. As a consequence, the state associated to the src IP (in general, the monitored traffic feature) of the packet is updated in the state table (a new entry is created for the first occurrence). This process is repeated for each monitored traffic feature, and different tables are linked to form a pipeline where each State table monitors one traffic feature, independently from forwarding. 2This process allows the switch to count the exact number of times each symbol appears for each traffic features one wants to monitor, ensuring thus a high accuracy of the detection algorithm. Regardless of where it is deployed, the detection algorithm can access this information through a new StateSec control message that atomically retrieves and flushes (to reset counters values after the lecture) the content of state tables. By periodically gathering the traffic feature keys and the associated states/counters from state tables, the detection algorithm can perform its duties.

B. Detection

In order to validate the benefits of the in-switch monitoring offered by StateSec, we adapted a simple statisticalbased algorithm from the literature [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF]. One advantage of this strategy is that it is directly applicable to the traffic features that are offered by the switch. Moreover, once XFSM will be available, this lightweight detection algorithm could be easily integrated into the switch. Indeed, unlike patternbased detection tools, statistical approaches do not require large memory nor high processing power. We thus developed StateSec's detection process using an entropy-based algorithm, a statistical approach for detecting anomalies in a distribution. formula given below, where p i stands for the probability of the symbol i to appear, and n represents the number of symbols.

H(X) = - n i=1 p i log 2 (p i ) log 2 (n)
A statistically high incidence for a given symbol to appear leads to a reduced entropy (and to a slightly more concentrated distribution). Conversely, low and dispersed incidences translate to higher entropy values. It follows that entropy-based algorithms are widely used for the detection of attacks in communication networks [START_REF] Giotis | Combining OpenFlow and sFlow for an effective and scalable anomaly detection and mitigation mechanism on SDN environments[END_REF], [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF]. By identifying significant changes in the randomness of consecutive traffic features distributions, this statistical approach can detect several type of attacks, including (D)DoS, with better accuracy than methods based on volume metrics [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF].

Next, we correlate different traffic features entropy variations to identify the type of attack. Table I shows that monitoring the entropy of four traffic features distributions (dst IP, dst port, src IP, src port) allows differentiating between multiple types of attacks. For instance, a significant decrease of the entropy for both the dst IP and the dst port features may be observed when a (D)DoS attack occurs. Increases or decreases in the entropy of the src IP feature qualify whether or not the attack is distributed. Similarly, the src port may be employed to detect spoofing attacks.

Fig. 4 serves to illustrate the variations in entropy induced on the dst IP traffic feature while a UDP DoS flooding attack occurs around t = 90s. The detected drop in the entropy value results from the fact that the target of the DoS attack represents a large share of the destination traffic seen at the switch. However, some IP addresses or ports may also send or receive more packets than others in real networks, e.g., servers providing very popular services. In this case, a hefty drop in entropy for the dst IP traffic feature might be related to certain properties of legitimate traffic and not to malicious actions (e.g., unexpected flash crowds arising after major events). Hence, selecting a good detection threshold and implementing additional protection mechanisms is paramount to avoid detecting potential false positives.

2) Detection Thresholds and Sensitivity: the sensitivity of the detection process is one of the key elements allowing to identify threats with a limited number of false positives. We employed a statistical model to define the lowest and highest acceptable values of entropy. For any given traffic feature to monitor, the initial entropy values collected by the detection algorithm bootstrap a learning phase -assuming no attack occurs during the bootstrap, these samples can be considered as a snapshot of the steady-state situation. After the bootstrapping phase is completed, any new entropy value is compared against statistics from the sample of entropy values collected so far (learning never stops, but abnormal entropy values are discarded from reference samples). The statistics computed from this sample are the mean µ e and the standard deviation σ e . From the normal distribution defined by N (µ e , σ e ), we identify the upper and lower bounds that determine whether or not the last computed entropy results from a legitimate situation. Following the normal distribution, detection thresholds can be configured to be located at µ e ± m • σ e with m ∈ N. The value of m relates to the algorithm sensitivity. For instance, if the system is configured to use thresholds one σ e away from the mean (m = 1), it will be very sensitive but may generate more false positives than with thresholds three σ e away from the mean (m = 3).

3) Outliers Protection: a key step consists in identifying the victim(s) (e.g., target hosts and service ports), and, if possible, the attacker(s), (e.g., hosts and source ports) that generate the attack. No matter the value chosen for m, in order to reduce further the impact of false positives we enforce an additional mechanism to protect outliers. In effect, in any network some legitimate hosts (e.g., IP addresses) or services (e.g., ports) are much more solicited than others (e.g., an HTTP server receives a lot more traffic at its address on port 80). This evidence does not sit well with a detection based only on statistical methods, and additional care should be taken in order to limit the occurrence of false positives. For this reason, when the last computed entropy for a traffic feature resides in-between the upper and the lower bounds, then no entropy violation is detected (we assume being in a legitimate situation). Similarly to the entropy detection phase, the algorithm computes the mean µ d and the standard deviation σ d , this time directly on the dictionary of symbols and their associated counters. Symbols below or above the µ d ± m • σ d thresholds are considered as outliers (e.g., IP addresses that are much more solicited than the others, in a non entropy-violation situation) and will be stored. Then, whenever an entropy violation is detected, an additional step is taken to verify whether the suspects are from these stored values. If that is the case, an alert is launched only if the counters are outside µ d ± m • σ d . 4) Detection Process Primer: the detection process consists in computing the entropy of each monitored traffic feature (src addr, src port, dst addr, dst port), based on the list of symbols and their associated counters. Then, the algorithm computes the upper and lower thresholds and evaluates whether the entropy value is below or above these bounds, individually for each traffic feature. If the entropy of one or multiple traffic features generates a drop or raise that crosses thresholds, an anomaly is detected. In any case, outlier values are stored to improve the detection in the future. This process is repeated at regular interval of times, called Time Window in the rest of the paper. When an anomaly is detected, the variations in the entropy for the different traffic features are analyzed, taking also into account the outliers, combined to identify the attack (following Table I), and the mitigation process takes place consequently.

C. Mitigation

Finally, mitigation action(s) are elaborated to protect legitimate users. Once a violation is detected, new flow rule(s) are installed into the switch with a high priority to match suspicious packets. The precision of mitigation rule(s) depends in large extent on the precision of the information identified in the detection phase (source and destination IP addresses and ports). The controller installs mitigation rules into the switch through standard OpenFlow functionalities. Existing actions allow to drop, queue, prioritize, blackhole or even forward traffic towards an IDS. We can also imagine many more complex actions: for instance, suspicious traffic could be forwarded towards a Deep Packet Inspection (DPI) device (or Virtual Network Function) running somewhere in the network for a further analysis conditioning a final remediation decision.

V. StateSec'S EVALUATION

We evaluated StateSec's performance in terms of false positives, detection accuracy and control plane overhead over a real testbed. This allows identifying and discussing the tradeoff between the cost of a precise monitoring and the detection efficiency. Since the core contribution of the paper concerns the efficiency of the monitoring phase, we compare StateSec's results to those obtained with the same entropy-based detection strategy coupled with sFlow for monitoring.

A. Experimental Testbed Setup

The evaluation has been carried out in a controlled environment composed of two virtual machines (VMs): one running an extended version of the Ryu controller (3 vCPUs clocked at 2GHz, with 16 GB RAM), and the other (2 vCPUs clocked at 2GHz, with 8 GB RAM) running Mininet [START_REF]Mininet[END_REF], a powerful tool used to emulate complex data plane topologies. In our experiments, Mininet emulates one switch running either our extended version of OpenState, or a standard Open vSwitch (OVS) coupled with an sFlow agent 3 , one replaying host, several attacker hosts, and one application server as depicted in Fig. 5.

B. Scenario and Parameters

In our experiments, host h1 replays legitimate traffic taken from the "BigFlows" trace (available at [25]), which captures a real network traffic on a busy private network's access point 3 We used OVS for experiments with sFlow because this software switch can integrate an sFlow agent while ofsoftswich13 cannot. to the Internet. This approach makes it possible to mimic a much more complex topology than the one presented in Fig. 5. The employed trace contains 50000 packets and has been chosen to include a significant number of hosts (679) that exchange diverse types of legitimate traffic (9605, 40249 and 118 packets for UDP, TCP and ICMP respectively), making it comparable to the traffic generated in a large company. The trace is indefinitely replayed at the speed of 3.3 Mb/s. The attacker(s) generates a (D)DoS flooding attack towards the server listening on ports 69 (TFTP) and/or 80 (HTTP), by using hping3 [START_REF] Sanfilippo | hping[END_REF] (1 pkt/1200 µs). During each experiment, we captured the traffic exchanged between the switch and the controller (control plane traffic) using tcpdump, and we observed also the reaction time of the detection process. We evaluate the performance of StateSec and sFlow for different values of three key parameters:

• Time Window: the time interval in seconds between two calls to the detection algorithm. With StateSec, the controller has to gather first the counters for the monitored traffic features from the switch, then it can trigger the detection algorithm. With sFlow, samples are gathered in real-time with sflowtool. In both cases, the Time Window parameter has a direct impact on both reactivity and control overhead. • Detection Sensitivity: the sensitivity value m that defines the thresholds to be used in the detection process (both for StateSec and sFlow), as described in Section IV-B. A fine tuning of this parameter is required in order to avoid as much as possible the presence of false positives. • Sampling Rate: the period used to sample packets with sFlow. Its value defines how many packets must be seen before picking a sample and sending it to the collector. The sampling rate [START_REF]sFlow sampling rates[END_REF] is configured with values ranging from 1 (high -a sample for each packet) to 100 (lowa sample each 100 packets) in our experiments.

For each set of parameters, we ran the experiments 30 times with a fixed initial time (26 s) of the (D)DoS attack in order to highlight the particular interactions between the sampling rate value and the detection accuracy.

C. DoS Experiments Results

First, we analyze the impact of the detection sensitivity value m on the amount of false positives at stationary regime without attacks, by replaying the traffic trace and counting detections. The fine tuning of detection thresholds is particularly critical in order to cut down the number of false positives, thus preventing artificial denial of service to legitimate users while preserving sensitivity to real attacks. Fig. 6 gives an idea of the values at stake (note the logarithmic y-axis). As a result, in order to avoid as much as possible false positives, in the following we will use a detection sensitivity set to m = 3 if not explicitly mentioned. Fig. 6 highlights also two clear trends: 1) by increasing the Time Window value, the sensitivity value without false positives decreases; and 2) for increasing sampling levels (sFlow only), regardless of the sensitivity value, the amount of false positives decreases. Unfortunately, as we will see later, longer Time Window and higher sampling rates imply increased control overhead.

We confirm this observation by looking at Fig. 7 that represents the average traffic flowing on the control plane channel during one Time Window. The overhead for StateSec includes the messages exchanged to gather counters from the state tables, whose size depends on the variety of traffic flowing through the switch. Instead, with sFlow it includes the packet samples sent from the agent to the collector. In this case, the control plane traffic depends rather on the data traffic throughput at the switch. We observe that with frequent sampling (e.g., sampling rate set to 1), sFlow overloads the control plane. This is the price to pay for using sFlow with the same precision level offered by StateSec, which in turns provides always exact counters. On the other side, StateSec generates less load on the control plane than sFlow with sampling rates set both to 5 and 10 and Time Window values higher than 2 seconds. So, unless using sFlow with very low sampling rates (e.g., a sample every 50 or 100 packets) in exchange for the penalty of a lower precision, StateSec is more efficient: it generates less overhead maintaining very precise monitoring information.

Ultimately, the detection rate is the most meaningful parameter for any credible (D)DoS protection strategy. At the same time, reactivity plays a major role, since it relates to the expected outage time of targets before a threat is mitigated. In that sense, Fig. 8 depicts the average attack detection rates for StateSec and sFlow for different sampling rates and Time Window intervals in case of an attack. We differentiate the reactivity performance by considering two types of detection, namely whether an attack is detected within two Time Windows or not. As expected, sFlow with low sampling rates leads to poor detection rates, implying also longer reaction times. In a nutshell, low sampling rates lead to less accurate detections and lower reactivity. Moreover, we note that sFlow performance depends heavily on the interplay between Time Window and sampling rates. Generally, longer time intervals permit sFlow to sample multiple suspicious packets increasing thus the detection likelihood (e.g., compare Time Window = 1 s Sensitivity false positives (%) 0.5 1 1.5 2 2.5 3 3.5 0.01% 0.1% 1% 10% q q q q q q q q q Time Window = 2 s Sensitivity 0.5 1 1.5 2 2.5 3 3.5 0.01% 0.1% 1% 10% q q q q q q q q q Time Window = 3 s Sensitivity 0.5 1 1.5 2 2.5 3 3.5 0.01% 0.1% 1% 10% q q q q q q q Time Window = 4 s Sensitivity 0.5 1 1.5 2 2.5 3 3.5 0.01% 0.1% 1% 10% q q q q q q q q q Time Window = 5 s Sensitivity 0.5 1 1.5 2 2.5 3 3.5 0.01% 0.1% 1% 10% q q q q q q q q

StateSec & sFlow (s=1) sFlow (s=5) sFlow (s=10) sFlow (s=25) sFlow (s=50) sFlow (s=100) q q q q q q q q q q q q q q q q q q StateSec sFlow (s=1) sFlow (s=5) sFlow (s=10) sFlow (s=25) sFlow (s=50) sFlow (s=100) Time Window (s) C-Plane load per interval (Kb) 1 2 3 4 5 0 400 800 q q q q q q q q q q q Fig. 7. Control plane channel load during one Time Window.

the improvement of detection rates for sFlow). On the other hand, lower sampling rates coupled with longer Time Windows tends to smooth out the entropy variations, reducing significantly the detection rate for the magnitude of attack that we tested (an example of this event can be seen in Fig. 8 for Time Window 5s and sampling rate 50).

D. Distributed DoS Experiments Results

We extend the DoS scenario used so far to evaluate how StateSec detects and mitigates multiple DDoS attacks. DDoS Attacks: in principle, DDoS attacks have a distributed source. If attackers are limited in number compared to the legitimate hosts, StateSec is able to identify most of the attackers. In that case, StateSec filters out each attacker as it was generating a simple DoS attack towards a unique target. On the other hand, whenever the DDoS attack is much stronger, i.e., it is generated by a number of attackers comparable to the number of hosts sending legitimate traffic, StateSec still can detect the attack without being able always to identify attackers. In order to evaluate this, we replayed the same traffic trace as for the DoS evaluation, this time employing multiple attacking hosts, and we observed that StateSec mitigates precisely simultaneous attacks from up to 35 hosts (out of the 679 total hosts in the BigFlows trace). In case the number of attackers is larger, StateSec protects the application service by temporarily dropping all the traffic towards the victim. Slow DDoS Attacks: by using slow traffic that appears legitimate in terms of protocols and rates, slow DDoS attacks try to pass undetected by traditional statistical strategies [START_REF] Park | Analysis of slow read dos attack[END_REF]. Indeed, when entropy variations are not pronounced enough, the algorithm will not detect any anomaly. This traffic, harmless at first sight, aims at exhausting the victims resources.

We extended StateSec to detect also this type of attacks by comparing the last computed entropy value not only to the distribution of the whole history of entropies, but also to the distribution of the history excepting the last n values (in our evaluations, we considered n = 4). If there is a significant decrease in the current entropy value compared to values seen in the past, a slow DDoS attack is detected.

We compared how StateSec and sFlow face slow DDoS attacks using a Time Window of 5 seconds, and a detection sensibility set to m = 2 (entropy variations are not significant enough to use thresholds 3 times away from the mean). To do so, we emulated a slow DDoS attack with 20 attackers flooding UDP packets towards the same destination and port. Only one attacker is present at the beginning of the attack, and a new attacker starts flooding every 5 seconds with a low intensity attack (1 pkt/10000 µs). Fig. 9 shows that StateSec offers detection rates near 80%. When StateSec detects the attack, nearly 85% of attackers are identified and the traffic they send is blocked. In addition, this result highlights again the consequence of a low precision in the monitoring: when the attack comes slowly, it is even clearer that sFlow used with low sampling rates cannot accurately detect and mitigate threats.

VI. CONCLUSION AND PERSPECTIVES

In this paper, we presented StateSec, a novel approach based on stateful SDN to protect communication endpoints from (D)DoS attacks. StateSec relies on in-switch processing capabilities to delegate the traffic monitoring phase to the switch. We developed the required extensions to make this scheme a reality, and evaluated its performance on a real testbed. Comparisons against sFlow confirm that StateSec is efficient in terms of control plane occupation, while it is clearly better in terms of monitoring precision, and, as a consequence, on detection accuracy.

Future work consists in adapting StateSec to the extended in-switch processing abstraction that authors of OpenState are currently developing, in order to actually integrate our entropy-based detection process into the switch. We also plan to elaborate more sophisticated mitigation actions, potentially taking network-wide decisions over more complex topologies.

Fig. 1 .

 1 Fig. 1. The three main steps of the security management function, generally implemented at the SDN controller.

Fig. 2 .

 2 Fig. 2. Classical approaches to DDoS detection and mitigation are controllercentric (left). StateSec delegates monitoring and detection functions to the switch since they are performed on local information (right).

Fig. 3 .

 3 Fig. 3. StateSec switch architecture.

1 )Fig. 4 .

 14 Fig.[START_REF] Radware | DefenseFlow -SDN Based Network DDoS, Application DoS and APT Protection[END_REF]. Entropy variations for the dst IP traffic feature: an UDP flooding attack is performed around t = 90s towards a single node. This generates a significant drop in the entropy, that returns back to normal levels after detection and mitigation of the attack (traffic from malicious hosts is discarded).

Fig. 5 .

 5 Fig. 5. Testbed topology: host h1 replays legitimate traffic from the trace "BigFlows" [25] with tcpreplay. Each attacker host generates a DoS attack towards the HTTP/TFTP server.

Fig. 6 .

 6 Fig. 6. False positives detected by StateSec and sFlow depending on the detection sensitivity m when no attacks are performed. For m > 2.5 the amount of false positives is below 0.1% for any configuration.

Fig. 8 .

 8 Fig.8. rates with detection sensitivity set to m = 3. Note the hefty drop in detection with sFlow for large Time Window and low sampling rates.

Fig. 9 .

 9 Fig. 9. Slow DDoS detection rates for a Time Window of 5s and n = 4.

  State match field: an additional field to match on in the Flow table. Using the state of a packet (carried in metadata) as a match field allows applying statedependent policies to packets. 3) Set state action: a new action to update the state for a configurable key (e.g., a src IP) inside the State table.

: 1) State table: linked to a Flow table configured as stateful, the State table associates a configurable key (e.g., a src IP) to a state. Whenever a feature of the received packet matches one of the keys, the associated state value is added to the packet's metadata and forwarded to the Flow table. 2)

TABLE I ENTROPY

 I VARIATIONS RESULTING FROM DIFFERENT TYPE OF ATTACKS.

	Type of Attack	Dst IP	Dst Port	Src IP	Src Port
	DoS flooding
	DDoS flooding
	DoS flooding
	with spoofed src port
	DDoS flooding
	with spoofed src port
	ICMP DoS flooding
	ICMP DDoS flooding
	Port Scan
	Port Scan with
	spoofed src port

OpenState is developed on top of the Ryu controller and the ofsoftswitch13 software switch.

Note that the forwarding table can stand either at the beginning or at the end of the pipeline.

ACKNOWLEDGMENT

This work has been partly funded by the EU in the context of the H2020 BEBA project (Grant Agreement 644122).


Anais Guignard

Member, IEEE Jean-Marc Faure

Member, IEEE Gregory Faraut

J.-M Faure

Lurpa

Model-based testing of PLC programs with appropriate conformance relations

Keywords: Conformance test, Programmable Logic Controller, Critical systems, Test verdict, Test duration, Mealy machine

Numerous theoretical results have been obtained in the field of conformance testing, a very promising formal technique to improve dependability of critical systems. Nevertheless, developing on this basis PLC test techniques that produce correct conformance verdicts requires to take into account the real technological features of PLC. This paper proposes conformance relations that meet this objective. Examples illustrate the benefits of the contribution.

I. INTRODUCTION

Since around twenty years, numerous researches have been carried out to improve PLC 1 (Programmable Logic Controller) programs development by using formal methods based on well-defined models ( [START_REF] Frey | Formal methods in PLC programming[END_REF], [START_REF] Johnson | Improving automation software dependability: A role for formal methods?[END_REF]). These works have yielded several worthwhile results in the domains of design ( [START_REF] Estevez | Model-based validation of industrial control systems[END_REF], [START_REF] Vyatkin | Software engineering in industrial automation: State-of-theart review[END_REF], [START_REF] Obermeier | A model-driven approach on object-oriented PLC programming for manufacturing systems with regard to usability[END_REF]), verification ( [START_REF] Rausch | Formal verification of PLC programs[END_REF], [START_REF] Adiego | Applying model checking to industrial-sized PLC programs[END_REF], to name a few) or implementation ( [START_REF] Basile | On the implementation of industrial automation systems based on PLC[END_REF]) of PLC programs. Whatever the benefits of these works, they are not integrating experiments on real PLC and assume that the whole program, in an IEC 61131-3 language for instance, is known, at the end of design or before verification or implementation. This knowledge is not the main concern of the end-users of critical automated systems. On the other hand, these users want to be sure that the PLC that executes this program behaves as specified, on the basis of experiments; this means that, whatever the current values of the PLC inputs and outputs and the sequence of inputs that is sent to the PLC, it generates the sequence of outputs that is planned in the specification. This explains why conformance testing is gaining a strong interest in industry and is advocated ( [START_REF]Nuclear power plants -Instrumentation and control systems important to safety -Software aspects for computer-based systems performing category A functions[END_REF], [START_REF]Communications Networks and Systems in Substations -Part 10: Conformance testing[END_REF], for instance) for controllers of critical systems, like railway transport, power production and distribution.

The overall aim of conformance testing is indeed to check experimentally whether an implementation, seen as a blackbox with inputs and outputs, behaves as specified. In this paper, the implementation will be a PLC which executes cyclically a control code that may have been generated automatically2 from the specification or not. The objective of this test technique (Figure 1) is to check whether the execution of this code by the PLC conforms to the specification, only by observing the output changes in response to the input changes; the code itself is unknown (black-box approach). It must be underlined that, compared to test techniques based on simulation [START_REF] Barth | Automated generation of simulation models for control code tests[END_REF], conformance testing does not require to build a model of the controlled plant; hence, the test results are more generic. Several worthwhile theoretical results have been obtained in the domain of model-based conformance testing by using different formal specification models: Mealy machines -or finite state machines-( [START_REF] Lee | Principles and methods of testing finite state machines-a survey[END_REF], [START_REF] Dorofeeva | FSM-based conformance testing methods: A survey annotated with experimental evaluation[END_REF]), Petri nets [START_REF] Zhu | A methodology of testing high-level Petri nets[END_REF], labeled transitions systems [START_REF] Brinksma | Testing transition systems: An annotated bibliography[END_REF]. They have been mainly applied to test communication protocols [START_REF] Jard | Tgv: theory, principles and algorithms, a tool for the automatic synthesis of conformance test cases for non-deterministic reactive systems[END_REF]. More recently, conformance testing of PLC that control critical systems has been addressed [START_REF] Provost | Testing programmable logic controllers from finite state machines specification[END_REF], [START_REF] Provost | Generation of single input change test sequences for conformance test of programmable logic controllers[END_REF]; in this work, the specification is represented as a Mealy machine, a formalism for Discrete Event Systems with inputs and outputs which is well-suited to describe the external behavior of a PLC. This formal specification can be obtained from a model in a tailor-made language, as presented in [START_REF] Provost | A formal semantics for Grafcet specifications[END_REF]; another example of such a translation of a model in an industrial language into a formal model may be found in [START_REF] Seidner | Formal methods for systems engineering behavior models[END_REF]. Selecting this formalism implies that only non-timed systems will be considered in what follows. A timed model, in the form of a timed automaton for instance, may be indeed non-deterministic, e.g. because the time intervals that define the guards of two concurrent transitions starting from the same state are overlapping. To be selected as the specification of a controller, which must be compulsorily deterministic, such a model shall be previously determinized, by using for instance the formal techniques presented in [START_REF] Bertrand | A game approach to determinize timed automata[END_REF]. However, these worthwhile theoretical results are rather new and will be only considered in further work on model-based testing of PLC.

The aim of this paper is to improve the previous results on model-based conformance testing of PLC by proposing two conformance relations that allow correct test verdicts to be delivered in a reduced time. In the previous works indeed [START_REF] Provost | Translating grafcet specifications into Mealy machines for conformance test purposes[END_REF], the conformance verdict was delivered after a predetermined time that corresponded to the longest computation time of all outputs, for every test step; hence, the overall duration of the test was unnecessarily long. The core idea of this paper is to base the conformance verdict on a variable-length sequence of observations of the outputs for several consecutive PLC cycles and not on a unique observation after a fixed time. The number of observations that will appear in the proposed conformance relation will permit to determine the lower bound of the duration of each test step, and consequently of the whole test duration. A beneficial consequence of this choice is that the conformance verdicts are more reliable because incorrect evolutions which lead to a correct state are detected, which was not the case with the previous approach. This article extends the work presented in [START_REF] Guignard | A conformance relation for modelbased testing of PLC[END_REF] so that several transitions may be fired sequentially for a unique change of the input values. Moreover, more detailed examples of testing of correct and flawed implementations are given to illustrate the benefits of our proposal.

The outline of the article is the following. A reminder on conformance test of Mealy machines is proposed in the second section. The experimental conditions of test execution on PLC are given at section III. Section IV permits to define conformance relations that lead to correct conformance verdicts; these relations are exemplified on cases of correct and flawed programs. Concluding remarks and prospects are drawn up in the last section.

II. BACKGROUND

A. Formal model of the specification

This work assumes that the industrial specification has been translated into a Mealy machine, a widespread formalism to represent the specification in conformance testing of non-timed systems, as presented in [START_REF] Provost | Translating grafcet specifications into Mealy machines for conformance test purposes[END_REF], for instance. Formally, a Mealy machine is a 6-tuple M = (I M , O M , S, s init , δ, λ) where:

• I M is the input alphabet, finite set of input events i M • O M is the output alphabet, finite set of output events o M • S is a finite set of states s • s init ∈ S is the initial state • δ : S × I M → S is the transition function • λ : S × I M → O M is the output function
The following assumptions will be made to build a conformance test sequence from this specification model:

• The transition function is complete and deterministic (i.e. every transition δ(s × i M ) with s ∈ S and i M ∈ I M is defined once and only once). • The Mealy machine which describes the specification is minimal. This implies that every state is reachable from the initial state and distinguishable. More details on minimization of Mealy machines can be found in [START_REF] Gill | Introduction to the theory of finite-state machines[END_REF], [START_REF] Chandrasekaren | DISCRETE MATHEMATICS[END_REF], for instance. • There is no unstable cycle, sequence of more than one transition, all labeled with the same input event, that returns to a state after having left this state. The absence of unstable cycle is a special variant of livelock freedom.

It must be noted that self-loops are possible because a self-loop includes only one transition; hence, it is not considered as an unstable cycle.

B. Faults model

When the specification and the implementation are both represented by Mealy machines which satisfy the previous assumptions, the implementation conforms to the specification iff their I/O languages are equivalent; hence, language equivalence is the conformance relation. This relation is not satisfied when the implementation contains at least one of the following faults:

• output faults: when a transition is fired, the correct state is reached but the output event which is emitted is not that expected (output label of the transition in the specification model); • transfer faults: when a transition is fired, the state which is reached is not that expected (destination state of the transition in the specification model) even if the right output event is emitted. These two types of faults are illustrated at Figure 2 where the specification model M spec contains 3 states S M = {s 1 , s 2 , s 3 }, and is defined from an input alphabet I M = {i 1 , i 2 , i 3 } and an output alphabet O M = {o 1 , o 2 , o 3 }; this machine satisfies the above assumptions. The implementation M imp is defined on the same alphabets but includes one output fault and one transfer fault. • Construction of a test sequence from the specification model. This sequence is an ordered list of test steps where a test step includes a couple of an input value that will be applied to the implementation and an output value that is expected. A test objective that defines the coverage percentage of the test must be mandatorily defined before building this sequence. • Execution of the test sequence by a test-bench, electronic device that sends inputs to the implementation, observes its responses and compare these responses to those expected. Comparison of the observed outputs to the expected ones requires a conformance relation (language equivalence or that proposed in [START_REF] Styp | A conformance testing relation for symbolic timed automata[END_REF] or [START_REF] Ponce De Leon | Conformance relations for labeled event structures[END_REF]) has been clearly defined previously. The first phase is detailed in this subsection; the second phase is described at section III when the implementation is a PLC that executes a control program.

Formally, a test sequence is an ordered list of elementary test steps et = (s s , I exp , s d , O exp ) where:

• s s ×s d ∈ S ×S where s s is the source state of a transition and s d is the destination state of this transition In this case, the strategy to build the test sequence, called T-method [START_REF] Lee | Principles and methods of testing finite state machines-a survey[END_REF], is to take at least once each transition of the Mealy machine that represents the specification; the test coverage is called "all-transitions" in this case. When the implementation model includes more states than the specification, other strategies are to be selected [START_REF] Chow | Testing software design modeled by finite-state machines[END_REF], [START_REF] Luo | Test selection based on communicating nondeterministic finite-state machines using a generalized wp-method[END_REF]. Furthermore, if the implementation is a PLC, it is possible to build one continuous sequence that covers all transitions because it is always possible to return to the initial state from any state, by issuing a reset event that restarts the PLC.

• I exp ∈ I M , O exp ∈ O M where I exp (O exp ) is the input (output)
Construction of the test sequence that meets this objective while being minimum-length3 is a well-known optimization problem which can be solved by applying the Chinese postman algorithm to the machine [START_REF] Naito | Fault detection for sequential machines by transitions tours[END_REF]. Moreover, if the implementation under test is a PLC that executes a control code, it is possible to reduce somewhat this sequence [START_REF] Provost | Testing programmable logic controllers from finite state machines specification[END_REF]. The input events correspond indeed in that case to combinations of logic inputs; when two successive transitions of the Mealy machine share the same input event, for instance the transition (s s , I exp , s d , O exp ) and the transition (s d , I exp , s d , O exp ), self-loop on the destination state of the previous transition, it is possible to test these two transitions in only one test step because the values of the inputs of the PLC are not modified during this step.

The complete test sequence T S obtained from the specification model of Figure 2 is given below:

T S = ((s 1 , i 1 , s 1 , o 1 ), (s 1 , i 2 , s 2 , o 2 ), (s 2 , i 1 , s 3 , o 3 ), (s 3 , i 2 , s 2 , o 2 ), (s 2 , i 3 , s 2 , o 2 ), (s 2 , i 1 , s 3 , o 3 ), (s 3 , i 3 , s 1 , o 1 )) (1)
It can be easily verified that this sequence meets the test objective (every transition of the specification is taken at least once) while it comprises 7 test steps and the Mealy machine 9 transitions. This comes from the selected strategy; the transitions (s 1 , i 2 , s 2 , o 2 ) and (s 2 , i 2 , s 2 , o 2 ), for instance, may be both tested during the second test step. This strategy may be used for every self-loop on a state which is labeled by an input event that is also the label of an incoming transition of this state.

Last, it must be noted that a test sequence does not define the duration of each test step, delay between the occurrences of the input events of two consecutive test steps, that must be greater than the delay between the occurrence of the input event of the first step and the occurrence of the expected output event of this step. This issue really matters however when testing real controllers that are not infinitely reactive; it will be addressed in section IV.

III. TEST SEQUENCE EXECUTION

Once a test sequence has been constructed, it must be executed by using the experimental facility which is depicted 4a) and sends to the computer, through the fieldbus, its output values at the end of every cycle. It must be noted that the control code that corresponds to the computation of the variables (second phase of the cycle) is a priori unknown (black-box approach) and that no additional piece of code is added (non-intrusive approach). For each test step, the test program (Fig. 4b):

• sends to the I/O module an input combination that corresponds to the input event of this step, as detailed at section IV-A; • observes the sequence of outputs that are generated at the end of every cycle by the PLC in response to this input change; the definition of the minimal duration of this observation is the topic of section IV-C; • elaborates a test verdict on the basis of the observed and expected output sequences and according to the conformance relations which will be defined in section IV-D; once the verdict obtained, the input combination which corresponds to the next test step is sent to the I/O module if the verdict is positive (OK). Test execution is stopped otherwise (verdict KO). It must be noted that all inputs of the PLC are changed synchronously by the test-bench and are read synchronously, but not necessarily at the same time, because the I/O module can modify its outputs at any moment of the PLC cycle; hence, the input vector read by the PLC is identical to the input vector defined by the test program. Last, it will be assumed in the sequel of this paper that the internal states of the implementation are observable by the PLC outputs, i.e. a different combination of outputs is associated to every state.

IV. CONFORMANCE RELATIONS A. Defining alphabet from I/O combinations

Before building the conformance relations, it is important to note that usually a PLC is not an event-driven component but is time-driven, with time stamps defined by the I/O scanning, and does not receive/emit events but logic variables. Hence, the input and output events introduced in the definition of the Mealy machine must be defined from combinations of these variables, as follows.

Let V I (resp. V O ) be the set of Boolean input (resp. output) variables of the PLC. The input alphabet I M (output alphabet O M ) of the Mealy machine that describes the specification is composed of all the combinations of input (output) variables. The dimension of

I M (O M ) is |I M | = 2 |V I | (|O M | = 2 |V O | )
and each element of the input (output) alphabet is represented by a minterm4 defined on V I (V O ).

An example of a Mealy machine that represents, with these definitions, the expected behavior of a PLC with 2 input variables V I = {a, b} and 2 output variables V O = {X, Y } is given at Figure 5. This machine includes 4 states S = {1, 2, 3, 4} and 16 transitions which are all labeled with Boolean combinations 5 of the input and output variables. This model will be used as the specification throughout this article.

B. PLC cycle and consequences

Only mono-tasking (or single threaded) PLC which are commonly integrated in automated systems will be considered in this work. In this case, the control code is executed according to a cyclic I/O scanning (Fig. 4(a)) that can be periodic or not and comprises 4 phases:

• Inputs reading (R),

• Internal and output variables computation (C),

• Output values updating and transmission (U),

• Waiting time until the end of the period, if the cycle is periodic. 6The two well-known consequences of this scanning are that:

• The response time (delay between the occurrence of an input change and the occurrence of the corresponding output change) is not equal to zero obviously and is variable.

• Asynchronous changes of input variables may be detected as synchronous. The second issue appears when the PLC is connected to sensors that measure different non-correlated variables; when changes of several of these variables occur at different times during a PLC cycle, they are detected synchronously at the beginning of the next cycle. This is not the case when testing conformance of a PLC because all outputs of the test-bench (inputs of the PLC) are changed synchronously (Figure 7) at the beginning of a test step; therefore, this phenomenon need not to be considered in this work.

Fig. 7. Example of evolutions of input variables during test execution

The first issue is illustrated at Figure 8. The response time stands between one (the input change occurs just at the end of cycle i and is detected just after, at the beginning of cycle i + 1) and two (the input change occurs just at the beginning of cycle i and is detected only at the beginning of cycle i + 1) cycles. The lower and upper bounds of this delay are then one and two periods, if the scanning is periodic, or once and twice the maximal value of the cycle otherwise. The conformance relation will be stated at the next section from the results of these three analyses.

Test of a self-loop: Testing a self-loop means that, from the active state (S 1 in Figure 9.(a)), the input values are changed (from I i to I j , I i ∈ I M , I j ∈ I M and I i = I j in the figure, assuming that the previous test step was that of the leftmost transition) 7 and the expected output is that of the self-loop, while the active state remains the same. This value is identical to that of the previous test step because the destination state is the same for both transitions and the same output is associated to all transitions leading to a given state to distinguish every state.

According to the discussion of the previous section on the response time of a PLC, the minimum duration of a test step of a self-loop is equal to 2 PLC cycles, to be sure the input change has been correctly detected. This step will include two observations of the output values; these observations must be identical to deliver a positive conformance verdict.

Test of a transition whose source and destination states are different: A similar reasoning can be made for such a transition (Figure 9.(b)); at least 2 PLC cycles are compulsory to test the transition from S 1 to S 2 after the input values are changed (from I i to I j , assuming that the previous test step was that of the self-loop on S 1 ).

However, when there is a self-loop with the same input value on the destination state, it is possible to test during only one test step both the transition to S 2 and the self-loop, as mentioned at II-C; if the values of the inputs of the PLC are not modified indeed, a correct control code will execute sequentially the two transitions. It is obvious in that case that the test step must last at least 3 PLC cycles (2 for the transition which changes the active state, to be sure that the input change has been detected, and 1 for the self-loop on the destination state, because the firing of this self-loop does not require any input change).

Test of successively fired transitions : The above reasoning can be extended to more than 2 transitions. This will be illustrated on the case of the Mealy machine with three successively firable transitions presented at Figure 10. This structure where a state (S 2 in this figure) is both source and destination of two different transitions that share the same input label may be found when translating a specification in a tailored-made language into a Mealy machine [START_REF] Guignard | A conformance relation for modelbased testing of PLC[END_REF].

An input change from I i to I j , from the active state S 1 , may provoke the successive firing of three transitions: from S 1 to S 2 , from S 2 to S 3 and the self-loop on S 3 . However, the new input value must remain the same during at least 4 PLC cycles to be sure to observe this sequence of firings; this is the minimum duration of the test step for this input change.

D. Definitions

The discussion of the previous section has permitted to define the minimum duration, in term of number of PLC cycles, of a test step. It is now possible to propose a conformance relation based on the sequence of observed outputs at the end of each one of these cycles.

Let s c be the current active state, let I i ∈ I M and O i ∈ O M be the current values of the input and output (Boolean combinations of the input and output variables of the PLC), let I j be the input value for the considered test step, let Obs = (O i , O j , ...) be a sequence of consecutive observed outputs and let m be the number of successively firable transitions when the input is changed from I i to I j , Definition 1. The PLC under test is said conform to the specification when a unique transition is tested if the relation

(2) is satisfied:    Obs = (O i , O j ) or Obs = (O j , O j ) with O j such as λ(s c , I j ) = O j (2)
Then, the new active state of the Mealy machine is defined as

s d = δ(s c , I j ).
Definition 2. For the others cases, the PLC under test is said conform to the specification if the relation (3) is satisfied:

Obs = (O i , O 1 , ..., O m ) such as    ∀O l , l = 1..m, there is: λ(s l , I j ) = O l with s 0 = s c and s l = δ(s l-1 , I j ) or Obs = (O 1 , ..., O m+1 ) such as    ∀O l , l = 1..m + 1, there is: λ(s l , I j ) = O l with s 0 = s c and s l = δ(s l-1 , I j ) (3)
Then, the new active state of the Mealy machine is defined as

s d = s m .
The relation (2) must be selected for the test of a unique transition (self-loop or transition with different source and destination states) and the relation (3) for a sequence of m successively firable transitions. In both cases, the minimum sequence of consecutive observations Obs is given for the two cases discussed at IV-B. Observation sequences for a given input change that lead to a positive conformance verdict can be obtained by adding to the right of this sequence any number of observed values which are identical to the last one (O j for the relation (2) for instance); these sequences are not minimum-length, however. The benefit of these definitions will be shown in the next section by application to correct and flawed implementations that will be compared to the specification of Figure 5.

E. Examples

From the specification model of Figure 5, the test sequence (4) which starts from the initial state 1 can be built by using the technique presented in section II-C.

T S = (a.b, a.b, a.b, a.b, a.b, a.b, a.b, a.b, a.b, a.b) [START_REF] Vyatkin | Software engineering in industrial automation: State-of-theart review[END_REF] It is important to note that this sequence is not described in the general form of a test sequence (relation (II-C)); the source and destination states as well as the expected output value, for each test step, are not given. The states have been omitted only for readability reasons; they can be easily determined from the knowledge of the model and the sequence of inputs, if the initial state is known. On the other hand, the absence of the expected output value is explained by the definition of the conformance itself; as this definition is based on a sequence of observations and not only one observation, introducing a unique value does not make sense.

This test sequence contains only 10 terms but meets the objective (every transition is taken at least once) because several transitions are taken sequentially during some steps. The first step is the test of the self-loop on the initial state for the combination where both input variables are True; the minimum duration of this step is two PLC cycles. The transitions from state 1 to state 2, then from state 2 to state 4, then the self-loop on this state are fired during the second step; the minimum duration of this step is four PLC cycles. The longest sequence of successively firable transitions after an input change contains m = 3 transitions (steps 2, 5, 7 and 10).

Case of a correct implementation: The results of the execution of this sequence with a correct implementation, for instance the ST programm of Fig. 6, are presented at Table I 8 where the combination of input variables that is applied to the PLC, the source and destination states of the sequence of transitions (may be equal to only one transition) which is tested, the intermediate states, if any, the minimum-length observation sequence that is 2, 3 or 4 PLC cycles long and the test verdict are given, for each test step.

Case of flawed implementations: Two flawed implementations will be tested according to the definition of conformance in this section; the first one (Figure 11) includes an output fault, the second one a transfer fault (Figure 12).

In the model of Figure 11, the output associated to the transition from state 4 to state 2 is X.Y whereas X.Y is expected. The results of the execution of the test sequence (4) on this implementation are given at Table II. The first three test steps provide positive verdicts but for the fourth one that tests the transition from state 4 to state 2 as well as the selfloop on state 2 for the input combination a.b the sequence of output combinations is (X.Y , X.Y, X.Y ) and does not satisfy the relation [START_REF] Estevez | Model-based validation of industrial control systems[END_REF] in the definition of conformance. Obs should be (X.Y , X.Y , X.Y ) or (X.Y , X.Y , X.Y ) according to this relation. The output error is detected; the implementation does not conform the specification.

It must be clearly highlighted that a conformance relation that is based only on the last observation X.Y , as this is the case in previous works, would lead to a positive verdict because the output fault would not be detected. This verdict FIGURE 11 The model of Figure 12 includes a transfer fault 9 ; the transition going from state 2 to state 3 and labeled with the input combination a.b in the specification has been replaced by a self-loop on state 2 with the same input variables combination. The results of the execution of the test sequence (4) are given at Table III. The first six test steps provide positive verdicts, which is quite normal because the part of the implementation which is tested during these steps conforms to the specification; they have been omitted in this table for space reasons. The seventh test step also provides a positive verdict even if the observations are obtained by firing the transition from state 1 to state 2 then the self-loop on state 2 labeled with the input combination a.b and not the sequence from state 1 to state 3 through state 2; but, as the output is the same (X.Y ) for the correct and erroneous transitions, the transfer fault is not detected at this step. It is detected at test step eight where the sequence of observations (X.Y , X.Y ) does not satisfy the relation (2). 9 This fault corresponds to a dead code because the state 3 is not reachable.

F. Discussion

To sum up, this section has shown that a conformance relation based on a sequence of observations for several PLC cycles must be used to detect every output and transfer fault during the execution of the conformance test of a PLC.

With this conformance relation, the minimum duration of the whole test sequence, in term of number of PLC cycles, is given by: n i=1 m i where n is the number of test steps and m i the minimal number of PLC cycles for the i th test step.

The minimal duration of the test sequence (4), for instance, is equal to (5 * 2 + 1 * 3 + 4 * 4) = 29 PLC cycles, because m i is equal to 2 for 5 test steps, 3 for one step and 4 for the remaining four steps.

The minimum duration defines a realistic lower bound of the duration of the test and not a too pessimistic overestimation obtained by defining a constant value for the duration of every step, as this has been made in previous works.

The values m i are computed off-line, i.e. before test execution. Computing m i requires to determine the number of transitions of the Mealy machine that are successively fired for the considered test step, as exemplified in IV-C. A Mealy machine which describes a specification does not contain any 12 cycle of successively firable transitions; this would mean that the controller is totally unstable for some combination of the input variables, which is surely never expected. Hence, the length of the longest possible sequence of successively fired transitions is equal to |S| (cardinality of the set of states). This sequence crosses indeed once and only once every state and therefore comprises |S| -1 transitions from the source state to the destination state; the self-loop on this last state must then be fired. Consequently, even if this case is very rare, the maximal computational cost of this off-line analysis is a linear function of the number of states. Our approach scales correctly.

V. CONCLUSION

The numerous and worthwhile theoretical results obtained in the domain of conformance testing of Mealy machines are helpful to develop model-based testing methods of PLC then to improve dependability of critical systems, but must be adapted to take into account the technological features of these automation components that are not infinitely reactive but are based on a cyclic I/O scanning. This paper has shown that, at each test step, the conformance verdict must be based on a sequence of observations of the outputs for several consecutive PLC cycles, to detect every transfer and output fault.

The proposed conformance relations permit us to define the minimum duration of each test step, in terms of number of PLC cycles. Therefore, this work contributes to reduce the time, then the cost, of test, while meeting the test objective and providing reliable verdicts.

On-going work is aiming at extending these results to validation of PLC by using HIL (hardware-in-the-loop) techniques. In this case, the PLC is not connected to a test-bench but to a software simulation of the plant to form a closedloop system. Hence, the state space to analyze is not that of the implementation in isolation but the state space of the implementation constrained by the plant, which is smaller. Up to now, only non-exhaustive simulation has been considered in this approach. Our objective is to investigate whether formal analysis techniques which have been developed for conformance testing of PLC can be used to check completely the correctness of the implementation from sequences of observations of the inputs and outputs of the simulated plant.

Fig. 1 .

 1 Fig. 1. Objective of conformance test of a PLC

Fig. 2 .

 2 Fig. 2. An example of specification model and flawed implementation

  event of the transition in the specification • s d = δ(s s , I exp ) where δ is the transition function of the specification • O exp = λ(s s , I exp ) where λ is the output function of the specification It will be assumed in what follows that the implementation model has the same number of states than the specification.

Figure 3 .Fig. 3 .

 33 Fig. 3. Experimental facility for test execution

Fig. 4 .

 4 Fig. 4. Structure of the PLC and test programs To sum up, the PLC under test and the computer communicate via the I/O module and the network; the inputs of the PLC are sent by the computer via the I/O module and the outputs of the PLC at the end of every cycle are transmitted to the computer via the fieldbus.It must be noted that all inputs of the PLC are changed synchronously by the test-bench and are read synchronously, but not necessarily at the same time, because the I/O module can modify its outputs at any moment of the PLC cycle; hence, the input vector read by the PLC is identical to the input vector defined by the test program. Last, it will be assumed in the sequel of this paper that the internal states of the implementation are observable by the PLC outputs, i.e. a different combination of outputs is associated to every state.

Fig. 5 .

 5 Fig. 5. Specification of the considered example An example of correct implementation of this machine in Structured Text language is given at Figure 6.

Fig. 6 .

 6 Fig. 6. Example of correct implementation of the Mealy machine of the Fig.5 in PL7Pro

Fig. 8 .

 8 Fig. 8. Minimum (t1) and maximum (t2) response times

Fig. 9 .

 9 Fig. 9. (a) A generic self-loop; (b) A transition with different source and destination states

Fig. 10 .

 10 Fig. 10. Example of successively firable transitions

Fig. 11 .

 11 Fig. 11. A flawed implementation with an output fault

Fig. 12 .

 12 Fig. 12. A flawed implementation with a transfer fault

TABLE II CONFORMANCE

 II TEST EXECUTION OF THE IMPLEMENTATION OF

TABLE III CONFORMANCE

 III TEST EXECUTION OF THE IMPLEMENTATION OF FIGURE

When the PLC code has been automatically generated from the specification, testing permits to check the correctness of the generator, i.e. to check whether the semantics implemented in this generator is the same than the one which is understood by the designer of the specification, which is often not the case.

The minimum-length sequence is the sequence that meets the test objective in a minimum number of test steps.

A minterm defined on a set of n Boolean variables is the conjunction of all these variables in their positive or complemented form.

(.) represents the operator of conjunction and ( ) represents the complement.

This waiting time is equal to zero for a cyclic but not periodic I/O scanning, as this is the case in the Fig.4(a)

The labels of the transitions in this figure and the following ones are noted as couples of input and output events, for readability reasons, but it is reminded that they correspond to couples of combinations of input and output variables of the PLC.

In the following tables, in the column Verdict, OK means that the test is passed, for the considered test step, KO that the test has failed and ! that the test is non-conclusive. Moreover, the symbol ∅ (empty set) means None.

ACKNOWLEDGMENT

This work has been funded by the French Research Agency as part of the VACSIM project.