Syed Raheel Hassan

Maxime Syrame
email: maxime.syrame@edu.univ-fcomte.fr

Julien Bourgeois
email: julien.bourgeois@femto-st.fr

Protecting Grids from Cross-Domain Attacks Using Security Alert Sharing Mechanisms $

Keywords: Security Management of Grid Computing Networks, Security Alert Sharing, Security Level Assessment, Blocking Cross Domain Attacks, Security Evaluation in Grid Computing Networks

In single administrative domain networks there is only one security policy which can be evaluated by the IT security manager thanks, to monitoring and reporting tools. Grid networks are often composed of different administrative domains owned by different organizations dispersed globally. Such networks are referred to as multi-administrative domain networks. Each domain might have its own security policy and may not want to share its security data with less-protected networks, making it more complex to ensure the security of such networks and protecting them from cross-domain attacks. We propose a Security Event Manager (SEM) called Grid Security Operation Center (GSOC), which facilitate IT security managers in giving a view of the security of the whole grid network without compromising confidentiality of security data. To do so, GSOC provides a security evaluation of each administrative domain (AD) and a parametric security alerts-sharing scheme. Alert sharing can then be tuned in order to meet local security policy rules.

$ Thanks to: the Laboratory of Computer Science University of Franche-Comte France, Higher Education Commission of Pakistan, Quaid-e-Awam University of Engineering, Sciences and Technology Pakistan for supporting our work financially. Grid'5000 network for providing us the platform to perform tests. Gérard Cécé for verifying the mathematical equations.

INTRODUCTION

General Security Problems in Computer Networks

In traditional computer networks, it is not recommended to send unencrypted passwords over the network as they can be easily sniffed out by the adversaries. If manually set passwords are weak then there exists many tools that could allow to break them [START_REF] Cheswick | Firewalls and Internet Security; Repelling the Wily Hacker[END_REF][START_REF] Hauser | The hacker's choice, a very fast network logon cracker which support many different services[END_REF][START_REF]Guess who is a password brute force utility for attacking secure shell version 2 accounts[END_REF]. However usage of manually set password do not preclude the use of strong passwords that would not be easily breakable. The asymmetric-based authentication system is made vulnerable if the attackers use denial-of-service (DoS) attacks on the servers which maintains the certificates and the public/private keys. Most of the time the entire network is compromised from the users that use very simple passwords. Sometimes by the weird security administration that allows the attackers to gain access in the organizations network. The attackers also exploits the vulnerabilities that exist in the applications running in the network [START_REF] Bart | Introduction to Grid Computing[END_REF]. When one or multiple nodes are compromised in a single administrative domain network, it is easy to take quick actions on the hosts and network of the organization to identify the source of the problem. Once the source is identified, new policies and restrictions can be placed within the organization's network to block future threats.

Specific Security Problems in Grid Computing

For attackers, grid services are very interesting targets to violate quality of service (QoS) by launching DoS and distributed denial-of-service (DDoS) attacks. Section 6.4 of the RFC 3820 [START_REF] Tuecke | Internet X.509 Public Key Infrastructure (PKI) Proxy Certificate Profile[END_REF] mentions there are possibilities for launching DoS attacks on the machines that are responsible for generating key pairs and when granting dynamic delegations using proxy certificates. By the growth of web service and XML technologies in grid computing networks, the application level firewalls are unable to detect sophisticated attacks fabricated using content of the messages [START_REF] Cremonini | An xml-based approach to combine firewalls and web services security specifications[END_REF]. VPNs also struggle to provide end-to-end security as they protect layer 2 or layer 3. When a node in the grid computing gets compromised it is very hard to identify the source of the problem because there are multiple nodes from different administrative domains collaborating with each other. In such cases there is always a high possibility that attacks could be propagated to other organization's network which are the part of that grid network.

Proposed Suggestions for Improving the Security of Grid Computing

Keep in mind that 100 percent security is an unrealistic objective [START_REF] Chakrabarti | Grid Computing Security[END_REF]. To maintain the security up to maximum, grid computing networks possess Grid Security Infrastructure (GSI) [START_REF]Globus: Grid security infrastructure (gsi)[END_REF] and Public Key Infrastructure (PKI) [START_REF]Public-key infrastructure[END_REF] that uses certificates for validating the legitimate users into the network. However, in [START_REF] Cody | Security in grid computing: A review and synthesis[END_REF] Cody et al. envision future research in grid computing will focus on high performance vs high security in grid computing networks because data encryption is inversely proportional to performance. In [START_REF] Schwiegelshohn | Perspectives on grid computing[END_REF], Schwiegelshohn et al. quoted the example of the XtreemOS [START_REF] Coppola | Virtual organization support within a grid-wide operating system[END_REF] project which is using native Linux system-level support for authentication mechanisms (such as PAM, Kerberos and SQL based authentication) instead of a specific middleware based authentication. Their aim is to reduce the complexity of the middleware. They therefore propose security authentication to be shifted to operating systems. Propagation of cross-domain attacks can be blocked if the security information can be shared among the members of the grid computing network [START_REF] Bourgeois | Managing security of grid architecture with a grid security operation center[END_REF].

Despite all precautions and propositions, chances still exist that adversaries can target the victim whenever they receive the opportunity. Therefore, there is a high need to have a security monitoring system in place that works in parallel with other security components. It must be scalable and fault-tolerant. It must handle sophisticated network attacks launched using the power of grid networks, must can block cross-domain attacks, must report security breaches in real time, and must share them with other members of the grid computing network. This paper proposes a grid security operation center dedicated for the grid computing networks. The reminder of this paper consists of five sections: a discussion of related work in section 2, an explanation of GSOC design in section 3, a proposition of security evaluation in section 4, a presentation of experiments and results in section 5, and concludes with a proposition of future work in section 7.

RELATED WORK

Figure 1 shows the classification of different types of monitoring and security management tools. Kenny and Coghlan [START_REF] Kenny | Towards a grid-wide intrusion detection system[END_REF] proposed SANTA-G (Grid- Enabled System Networks Trace Analysis) which is based on the RGMA (Relational Grid Monitoring Architecture), is an implementation of GMA which is developed under the European DataGrid (EDG). SANTA-G uses Snort [START_REF]Snort network intrusion prevention and detection system (ids/ips)[END_REF] for monitoring network traffic and is composed of three components: Sensors that need to be installed on the monitored devices, a Query Engine, and a GUI. Snort logs suspicious activities that occur in the network. These logs are then forwarded to a SANTA-G sensor which analyzes them and looks for attacks. If a new attack is found, the corresponding log will be sent to the query engine and saved in the database. The query engine publishes the detected attack to its users. The SANTA-G model lacks incident detection, a tracking and response platform, and analysis of reported events to check the patterns for distributed attacks meaning it can not properly detect distributed-denial-of-service-attacks (DDoS). The RGMA has the main database which holds the reported attacks by one or more SANTA-Gs which are running in a grid network. Due to this design limitation, if the size of the network grows rapidly then multiple SANTA-G's begin sending alerts simultaneously making it difficult to hold the alert information for long periods of time. It can, therefore, only correlate reported attacks for a short period of time. This lower its detection capacity for attacks or scans that are using slow-timed pace. SANTA-G only uses Snort as a source of data, giving a restricted view of the network security. SANTA-G does not have a security alert-sharing mechanism and cannot detecting cross-domain attacks.

Fang-Yie Leu et al. proposes three versions of an intrusion detection system dedicated to grid networks: GIDS (Grid Intrusion Detection System), PGIDS (Performance GIDS), and FGIDS (Fault-tolerant GIDS) [START_REF] Leu | Integrating grid with intrusion detection[END_REF][START_REF] Leu | A performance-based grid intrusion detection system[END_REF][START_REF] Leu | Intrusion detection based on grid[END_REF]. All variations of GIDS consist of four types of components: dispatchers, which assign network traffic to Detection Nodes (DN) for detecting attacks; a scheduler to balance the load between dispatchers; DN which use Intrusion Detection System Module (IDSM) for packet analysis and for detecting attacks; and a Block List Database (BLD) to hold intrusion information and suspected IP addresses. The objective of GIDS is to detect logical, momentary and chronic attacks. GIDS attack detection accuracy is not very accurate as it does not matches the patterns of similar attacks that occurred in the past by the same attacker. The scope for attack detection is very small [START_REF] Leu | Integrating grid with intrusion detection[END_REF] since they used TCP, UDP and ICMP flood attacks. To overcome these issues they proposes PGIDS, the objective of PGIDS is to add DoS/DDoS attack detection to GIDS, but PGIDS suffers from DN failure under massive DDoS attacks. A new version, called FGIDS, tackles this problem. The [START_REF] Chu | The architecture of the large-scale distributed intrusion detection system[END_REF] is a scalable and faulttolerant solution. The LDIDS can be applied in grid computing networks due to its modular nature but lacks in the efficiency of the inter communication of its security components. Furthermore, in [START_REF] Chu | The architecture of the large-scale distributed intrusion detection system[END_REF] no details are given about the types of attacks that are detectable by LDIDS.

The Distributed Intrusion Detection System on Grid (DIDoS) proposed by Poula Silva et al. [START_REF] Silva | Composition of a dids by integrating heterogeneous idss on grids[END_REF] is a hierarchy of multiple intrusion detection systems. The experiments are performed using a grid simulator called Gridsim which can only model and validate the collaboration between the different components of DIDos but not real grid environment conditions. DI-DoS does not provides a mechanism for sharing alerts between the different administrative domains.

Distributed Security Operation Center (DSOC) proposed by Ganame et al. [START_REF] Ganame | A global security architecture for intrusion detection on computer networks[END_REF] does not have an intelligent security alert-sharing mechanism between different administrative domains either. Therefore, it cannot detect cross-domain attacks.

Table 1 summarizes the main features of any security management system that handles the security of the grid computing networks. It shows the shortcomings of the security systems that are discussed in this section. In this paper we will discuss GSOC (Grid Security Operation Center) which can overcome the limitations of the discussed solutions.

GSOC DESIGN

The GSOC modular design is based on [23][24]. GSOC is composed of seven components namely Event Generating Box (EBox), Logs Collecting Box (CBox), Local Analyzer (LA(DBox+ABox)), Global Intrusion Database (GIDB), Global Analyzer (GA), Remote Logs Collecting Box (RCBox), and Secure Virtual Organization Box (SVOBox). Figure 5 is a general overview of GSOC architecture and shows the main components of GSOC and their position within the grid network. These components, except SVOBox, are discussed in detail in [START_REF] Bourgeois | Managing security of grid architecture with a grid security operation center[END_REF][START_REF] Hassan | Minimization of security alerts under denial of service attacks in grid computing networks[END_REF]. In this paper only the short description of these components will be presented.

Security Alert Generating Mechanism

EBoxes (see figure 2) are the source of data for GSOC and cover a wide range of devices, from a normal computer to any device in the grid computing network. The nice feature is no additional software is required to be installed on the EBoxes in order to send logs. GSOC uses only standard logging systems and transport protocol. To integrate a new EBox in GSOC, a simple configuration has to be made like a log redirection. One CBox collects data from multiple EBoxes using standard transport protocols. The logs are processed depending on their protocol and then forwarded to the dispatcher which sends them the to the proper application agent. The application agents extract the information from the logs and create formatted events which are sent to the basic correlation module. One application agent is required for each type of log collected. CBoxes operate at each local site of an Administrative Domain (AD). One CBox is sufficient for one local site, but more than one CBox can be added depending on the number of active sensors and the amount of logs they generate. The Basic Correlation (BC) module has a defined time limit which holds the reported security alerts for one minute and correlates for detecting attacks. The Basic Correlation module forwards the correlated attack information to the Advanced Correlation (AC) module for detecting distributed attacks. The advanced correlation module collects logs from multiple CBoxes and further correlates for more sophisticated and distributed attacks. If an attack is detected, the ABox reports it to the administrator in real time and saves the security alert permanently in Local Intrusion Database (LIDB). The same reported alert will also be saved in the Global Intrusion Database (GIDB) as a backup of LIDB (see figure 4). LIDB is a database that contains all the core configurations related to the network devices, user configurations, security rules, and vulnerability database from Common Vulnerabilities Exposures (CVE) [START_REF]Common vulnerabilities and exposures is a dictionary of publicly known information security vulnerabilities and exposures[END_REF]. The mechanism for detecting distributed attacks using basic and advance correlation is discussed in detail in [START_REF] Hassan | Minimization of security alerts under denial of service attacks in grid computing networks[END_REF].

GSOC Architecture Internal View

Figure 4 is the architectural internal view of each component of the GSOC. The reported alerts saved in the LIDB are also forwarded to the GIDB for security evaluation and to be shared with other ADs that compose the grid computing network. The GIDB consists of two parts. The upper part contains a replica of all configurations done within the LAs, reported security alerts from all the local sites of the AD and messages from all RCBoxes. The RCBoxes work like CBoxes except RCBoxes collect logs from the most important sensors in the AD. These sensors could be general security devices, proprietary softwares or customizable network monitoring systems. The purpose of collecting these logs is to double check the logs for network attacks. RCBoxes have been introduced in the GSOC design (i) to detect attacks that target security management devices (ii) when the attacker camouflages its attacks and (iii) when the attackers target GSOC components. The RCBoxes receive copies of the logs from the sensors and forward them to the GA. The GA correlates the received logs and forwards them to the GIDB. Thus, RCBox provides a way to compare the deviation (∆) in the logs generated during normal operation of the network with the abnormal behavior using GIDB. The deviation is calculated by comparing the message received in the GIDB from all local sites and the messages received from all RCBoxes. The deviation is directly proportional to the possibility of attacks. Figure 3 shows the deviation (∆), the messages received by the RCBoxes, the messages received from local sites, a short report, a detailed report, the security alert sharing option, and a security evaluation of two ADs. At the final stage the SVOBox evaluates the security level value for each AD. Security evaluation is discussed in detail in section 4.

The lower part of GIDB is called External GIDB and is responsible for sharing the reported security alerts with other ADs in a grid computing network. Security alert sharing can be very effective in blocking cross-domain attacks while keeping in view the composition of grid computing network which includes:

(i) Different ADs that consist of multi-local sites combined together to form a network.

(ii) The size of the network increases and decreases dynamically.

(iii) Nodes from one AD can collaborate with nodes from other ADs where different security policies are applied.

(iv) Both the administrator of the ADs whose nodes are communicating with each other do not know the nature of the attacks that are in progress at either side.

This raises the need for a solution that would provide the network administrators functionalities that can inform them of the nature of attacks that are under progress in any external ADs. One solution to this problem is to provide a way to share, between different ADs, their security alerts. But, sharing all security alerts of one entire network with another administrative is something that security policy should forbid. To address this issue GSOC provides a mechanism by which the network administrator of an AD can share specific security alerts with selected ADs depending on their security level of either low, medium, and high which rank the confidentiality of the alerts. The details of each category is discussed in detail in section 4. Figure 6 shows the overview of the reported security alert sharing mechanism between six administrative domains. SVOBox assigns security level values by manipulating the number of security alerts generated within the local sites of the AD. All the security alerts generated in different ADs of a grid network can be seen at the SVOBox main dashboard. The SVOBox dashboard access is granted to the network administrator of each AD. Only the ADs who are sharing their resources with each other are allowed to send and receive the security alerts between them (figure 3).

SECURITY EVALUATION OF ADMINISTRATIVE DOMAINS

Security evaluation of administrative domains that form a grid computing network is required in order to create trust between ADs. Security levels are a representation of the current security state of the AD. Evaluating the security of an AD which can be a multi-sites network is a complex task as it includes many heterogeneous devices. Security can be evaluated using multiple metrics. Some possibilities are:

(i) The skills of the IT security team that includes experience, certifications, trainings, and their availability.

(ii) The security devices and softwares used including (i.e., firewalls, intrusion detection and prevention systems (IDPS) and anti-virus softwares). Their configuration level includes the security rules and policies that must be updated on time.

(iii) Security contingency plans in case of severe attacks.

(iv) Time required to restore all the systems and services after shutdown in case of disasters.

(v) User awareness programs, for maintaining their system's security.

(vi) Reports of deep vulnerability scans, security scans, and pen tests must also be considered.

All the above mentioned aspects needs to be evaluated by a third party for non-biased evaluation results. We aim to provide an automated security evaluation of a dynamic network at a given time whereas security standard like ISO 27000 works on a progressive view of the security. we are using an automated security evaluation which takes into account dynamic network and its real-time constraints [START_REF] Karim | Defining a simple metric for real-time security level evaluation of multi-sites networks, Parallel and Distributed Processing[END_REF]. For evaluating security level values in GSOC, some equations written below have been applied to any AD which is a part of the grid computing network. These equations help GSOC to categorize the ADs by processing the number of low, medium and high alerts generated within their local sites. These levels are criticality levels that are assigned by to each alert by the network administrator of each AD. GSOC categorizes the ADs according to three security levels. Security level one is the highest security level while three is the lowest one (see figure 6). Security evaluation of a network can also be done using tools like Nessus [START_REF]Security scanner for oracle and various flavors of unix[END_REF], OpenVAS [START_REF]The open vulnerability assessment system (openvas)[END_REF] or Saint [START_REF]Vulnerability management, assessment, penetration testing (saint)[END_REF]. In GSOC the result of these three tools are also incorporated to give a better view to the administrator. Table 2 shows the number of security alerts detected during scan on 10 computers. The configuration of the computers are CPU 2.4 GHz and RAM 512 MB. Vulnerabilities are present in any software and they are reported at regular basis. There is a high possibility that many vulnerabilities can be reported if a machine contains lots of non-updated softwares. In our experiments, we used multiple machines with older and new release of updates.

LAV (Low Alert Value) is the number of low level alerts reported which are, for example, information like session opening, session closing, or services start/stop/restart. MAV (Medium Alert Value) is the number of medium Case-I: When an AD operates under normal circumstances, LAV is always greater than MAV, which is greater than HAV (LAV > M AV > HAV ).

Case-II: There is a slight change in the normal behavior of an AD or in any one of its local sites. This happens when the inexperienced attackers try to launch basic attacks. Some examples might be, manual use of incorrect password attempts, port scans, and ICMP flooding. They use their personal machines without IP spoofing for launching these attacks, making these attacks easily detectable.

Case-III: There is a major change in the normal behavior of an AD or in any one of its local sites. This case occurs when the experienced attackers use multiple machines for launching distributed attacks. They use automated tools and spoof their IPs. The duration of the attacks last for a very long period of time and they mix their attacks with normal behavior to camouflage their operations. These attacks are difficult to detect and very destructive in nature. Some of the examples of these attacks are the use of brute force attacks using automated tools such as THC Hydra [START_REF] Hauser | The hacker's choice, a very fast network logon cracker which support many different services[END_REF] & Guess Who [START_REF]Guess who is a password brute force utility for attacking secure shell version 2 accounts[END_REF], DoS & DDoS attacks using Slowloris [START_REF] Rsnake | Slowloris http denail of service[END_REF], and UDP & TCP flooding by changing the maximum transmission unit (MTU) of the packets.

NOTE:

The standard policy must be adopted by all members of the grid computing network for assigning the critical values to the attacks in order to have a homogeneous reporting systems. Let GN be a grid computing network:

Formalization of Security Evaluation

GN = {AD 1 , AD 2 , ............AD m } with AD (i) = {LS (i) 1, LS (i) 2, .............LS (i) n i }
where n i is the number of local sites of the administrative domain, and m is the number of administrative domains in GN. Now LAV, MAV and HAV at time "t" can be determined by:

LAV -→ LA (ADi) (t) = n i j=1 LSA L (t)
LAV is the number of total low alerts reported within all local sites of an AD.

M AV -→ M A (ADi) (t) = n i j=1 LSA M (t)
MAV is the number of total low alerts reported within all local sites of an AD.

HAV -→ HA (ADi) (t) = n i j=1 LSA H (t)
HAV is the number of total low alerts reported within all local sites of an AD. Now the AD can be set to SL1, SL2 or SL3, if any of the equations from 1 to 6 matches with the LAV, MAV, and HAV conditions. Equation 1shows that the AD has medium security alerts greater than low and high, whereas low security alerts; are greater than high security alerts, therefore it should be placed in SL2 (see graph).

(LAV (AD) < M AV (AD) and LAV (AD) > HAV (AD)

) then SL = 2 (1)
Low Medium High Number of SA Equation 2shows that the AD has high security alerts greater than low and medium, whereas low security alerts are greater than medium security alerts; therefore it should be placed in SL3 (see graph).

elseif (LAV (AD) > M AV (AD) and LAV (AD) < HAV (AD) ) then SL = 3 (2)

Low

Medium High Number of SA Equation 3shows that the AD has low security alerts greater than high and medium, whereas medium security alerts are greater than high security alerts; therefore it should be placed in SL1 (see graph). 4shows that the AD has low security alerts greater than high and medium, whereas high security alerts are greater than medium security alerts; therefore it should be placed in SL2 (see graph).

elseif (M AV (AD) < LAV (AD) and HAV (AD) < LAV (AD) ) then SL = 2 (4)

Low

Medium High Number of SA Equation 5shows that the AD has high security alerts greater than low and medium, whereas medium security alerts are greater than low security alerts; therefore it should be placed in SL3 (see graph).

elseif (M AV (AD) > LAV (AD) and M AV (AD) < HAV (AD) ) then SL = 3 (5)

Low

Medium High Number of SA Equation 6shows that the AD has medium security alerts greater than low and high, whereas high security alerts are greater than low security alerts; therefore it should be placed in SL3 (see graph). 7 is the graphical representation of the data of 10 machines that shows that in normal circumstances the low alerts are always greater than medium and high alerts. These results are taken by the scan from Nessus, OpenVAS and Saint, and validate the equations used for security evaluation in GSOC.

EXPERIMENTS AND RESULTS

This section compares the behavior of two types of security management systems. The first one is developed for traditional computer network, but could be deployed in grid computing networks; the second one is developed for grid computing networks. The Distributed Security Operation Center (DSOC), which while developed for traditional computer networks has been used for executing different tests is classified in figure 1 under the category "Security solutions for traditional networks deployable in grid computing networks." The DSOC will be used for representing other security solutions that exist in a similar category. Graphs 8 and 9 show the security alert rate in minutes. The graphs shows three attack details, namely those of Brute Force attacks (BF), Denial of Service attacks (DoS), and Distributed Denial of Service attacks (DDoS) launched on DSOC and on GSOC using multiple sites of the Grid'5000 (G5K) network. The details of the network can be seen at [START_REF]Grid'5000 is a scientific instrument for the study of large scale parallel and distributed systems[END_REF].

Attack Scenario-I

Figure 10 consists of two parts. The upper part represents a simplified view of G5K network with CBox running at the Rennes site. The LA+ABox, LIDB, GA+GIDB are running at the Nancy site. The approved users are allowed access to these sites where they can reserve many nodes and perform their experiments. These users are also allowed to reserve any number of machines between nine other sites of the G5K. The lower part is a simplified view of our lab network where two users from Machine 1 and 2 via ssh connection 1 & 2 are allowed to connect into the G5K network. Attackers 1 & 2 try to get access to machines 1 and 2 by launching brute force attacks using a dictionary of passwords that contains 8048 passwords. Attacker 2 was not successful on Machine 1 due to a strong password. Attacker 1 was successful and cracked the password of Machine 2 after 10 minutes which is found at the 5000th location of the password file 3 . Attacker 1 using machine 2 is a threat within local and external networks which are connected together. Attacker 1 can perform malicious activities in G5K since the connection originated from the approved user machine. For the G5K network, Machine 1 was a trusted machine but is now compromised; 4 shows that the G5K network is accessible by Attacker 1. Attacker 1 can further launch more brute force attacks on other machines of the G5K. If successful, the results are very destructive.

Attack Scenario-II

Usually, an experienced attacker uses a combination of multiple attacks to hide their activities. The easiest scenario is to first launch a DoS attack from Attacker 3 that generates the alerts of DoS 5 . These alerts are generated deliberately to attract the attention of the network administrator and fill the GUI of the security management system. After some time Attacker 2 from the other machine starts launching another attempt of brute force attacks 6 to crack the password of Machine 1. These attacks last for short periods of time and are restarted after some time.

Attack Scenario-III

A more complex scenario is to launch the DDoS from multiple machines (Attacker 4 to Attacker 6) by spoofing IP addresses 7 & 8 . These attackers generate several alerts and because of the IP spoofing need more time from the administrator to detect the actual source of the attacks. These attacks cover two objectives: It overloads the network and its components so the legitimate users cannot access it and allows them to destabilize the security management systems. In this way, the malicious activities are not easily detectable and if they are detected, they will be reported very late to the administrator due to the high number of security alerts processing time.

By deploying GSOC between G5K and our lab network, attack types I, II & III can be blocked at very early stage. The CBox which is running in our network collects all unsuccessful authentication failures attempts and sends them to the LA 9 . The LA correlates all the logs, generates a brute force attack attempts, and saves it in LIDB. The sharing mechanism of GSOC allows the lab network to share this information with the G5K network. The administrator of the G5K network has access to the brute force attempt alarm in our lab which includes the IP address, user ID, start time of attack, end time of attack, and total number of fail attempts 10 . This information helps the network administrator of G5K to stop the access of that user. In this way an attack which is propagated from one administrative domain to another can be blocked.

In figure 8 the DSOC detects the attacks between 1 or 2 minutes and reports them at the dashboard. The DSOC generates an alarm for almost every attempt. These alarms utilize network bandwidth in case of a multisite network, and they use a reasonable amount of disk space if the attacks continue for long periods of time. The reported security alarms are only available within the premises of one AD. This limitation does not suit grid networks as there are attacks that use computer worms which expands by themselves. These attacks could therefore expand to other members of a grid network. A mechanism has therefore been adopted in GSOC for sharing reported security alerts between multiple ADs to protect other members in a grid network for possible cross-domain attacks. See figure 11 where there is no security alert sharing mechanism. This scenario can lead to propagate some serious network attacks to other members of the grid. In figure 12 the security mechanism exists but it is not intelligent because ADs are sharing security alerts randomly. This sharing of information cannot be result oriented as it uses more network bandwidth and exposes internal security information to insecure ADs. Keeping these issues in mind, an efficient approach is to share the security alerts after classifying the ADs. See figure 6 for a depiction of security evaluation through the assignment of sharing mechanisms into three categories SL1 as most secure, SL2 as more secure, and SL3 as least secure. This classification gives a global view of security within a grid network to its members.

In figure 9 the GSOC detects the attack within one minute on the CBox. By the second minute they are detected on the ABox, which correlates the alerts coming from multiple local sites and discards false positives. By the third minute the details of the attacks are available on the SVOBox. By the fourth minute all alerts are ready for sharing with other ADs in a grid computing network. This can help blocking cross-domain attacks. It utilizes less bandwidth and disk space and gives a global view of security for the entire grid network.

DISCUSSION

Due to the nature of grid computing networks, a security management system must comply to some basic factors. According to our research the most important are scalability, fault-tolerance, security alerts correlation, security evaluation, and security alert sharing. GSOC covers all these factors as it has scalability due to its modular design. It can handle networks that are growing dynamically. RCBox provides fault-tolerance capability in case if any of the CBox fails or comes under attack. GSOC has two step correlation basic and advance which help to keep it stable especially when the grid network is under DDoS attacks. GSOC has dynamic and static security evaluation which informs the member of the grid about the members that are vulnerable to the attacks. This helps to share their resources with them by applying more strict security policies. SVOBox provides security alerts sharing mechanism which is the most important factor in blocking cross-domain attacks. OSSIM and GSOC are suitable to be deployed in grid computing network to manage its security as shown in Table 1. Subsection 6.1 shows a small test about the performance of these systems. OSSIM [33] is a product of Alien Vault Professional Corporation. It is an open source freely available Security Information and Event Management (SIEM) system but some advance reporting capabilities are not freely available. It is a framework for the management of the security infrastructure of the large organizations.

Stability Comparison of Security Management Systems

Figure 13 is the graphical view which shows the comparison of different security management systems (SMS). It shows the degradation in performance when the high intensity of attack continues for long period of time on the SMS. For comparing the performance of each SMS one round of BF attack was perform on a machine using a list of passwords. Guess Who [START_REF]Guess who is a password brute force utility for attacking secure shell version 2 accounts[END_REF] performed more than 8000 passwords attempts on one victim machine. The red line in figure 13 shows the number of attempts made by the attacker on the victim machine. To detect this attack three SMS namely GSOC, DSOC and OSSIM are placed in parallel. The detection rate of GSOC remains stable throughout the attack. The detection rate of DSOC remains stable until 35 minutes but after that it starts degrading its performance. The detection rate of OSSIM remains stable until 20 minutes but after that it also starts degrading its performance. Both the DSOC and OSSIM detects the attacks but when the attack continues for long period of time there performance become bad to worse. This performance degradation is very crucial if the attacker gets success in its attacks. Due to this reason the alerts are reported with the delay and the delay continue to increase as shown in the graph. In this case even the DSOC and OSSIM will detect attack after a certain delay but this delay give a fair chance to the attacker to do some harmful activities successfully. Whereas in the case of GSOC it continue detecting the attacks with a negligible delay.

CONCLUSION AND FUTURE WORK

Grid computing networks are complex environments to protect as they raise multiple challenges, one of them being the heterogeneous structure of a grid network which can be composed of different administrative domains. This heterogeneity lowers the possibility of alert sharing and therefore decreases the protection of the network when dealing with cross-domain attacks. In this paper, we have proposed GSOC which fulfills all the prerequisites for becoming a prototype security solution for grid computing networks. The distributed and modular architecture of GSOC allows it to scale up to the size of the grid computing network. The experiments have shown a network administrator of any AD can share its security alerts at any time with others. In case of a severe distributed attack GSOC can give a global view of the network security after 4 minutes while other tools have failed to do so. The classification of the ADs in security levels using security evaluation creates a trust between the members of the grid network. Alert sharing mechanisms can still be improved. Depending on the security policy, on the criticality level of the alerts and on the security level of the AD, a customizable anonymity of alerts based on [START_REF] Jurczyk | Dobjects+: Enabling privacypreserving data federation services[END_REF][START_REF] Xiao | Dpcube: Releasing differentially private data cubes for health information[END_REF] could be used in order to be able to share even the most critical alerts and therefore improving the correlation.

In cloud computing networks the most recent issues are discussed by Balduzzi et al. [START_REF] Balduzzi | A security analysis of amazon's elastic compute cloud service[END_REF]. They performed vulnerability tests on 5000 virtual machine images available in four different data centers of Amazon [START_REF]Amazon elastic compute cloud (amazon ec2)[END_REF] and reported several security issues in public virtual images. Bugiel et al. [START_REF] Bugiel | Amazonia: when elasticity snaps back[END_REF] also raised the similar issues but they performed experiments on 1255 Amazon images and the scope of their experiments was limited in covering security issues. Garfinkel and Rosenblum [START_REF] Garfinkel | When virtual is harder than real: security challenges in virtual machine based computing environments[END_REF] highlighted the use of third party virtual images and their security issues. Glott et al. [START_REF] Glott | Trustworthy clouds underpinning the future internet[END_REF] discussed the security issues that occurs when the virtual images are shared within multiple users in cloud infrastructure. Bleikertz at al. [START_REF] Bleikertz | Security audits of multi-tier virtual infrastructures in public infrastructure clouds[END_REF] used graph theory techniques to deploy secure virtual machine images in Amazon EC2 infrastructure. The main focus of all the researchers is to emphasis that there exists some serious security threats in cloud computing infrastructures. GSOC can be deployed in cloud computing infrastructure after certain modifications and can address these issues up to certain extend. New boxes should be introduced at each service, that means one box for infrastructure, one for platform and one for software. These boxes must be programmed to handle the specific security issues occurred at each service level and verify newly added and modified images by the cloud users. If found a vulnerability in any image, they must block that image for other users. These boxes must works separately and report to the LA, but if needed can also collaborate to detect the attacks which are launched using all the three service levels. For every service there can be a separate LA. All the LAs at each service level must report to the GA which will handle the security of the entire cloud. Multiple SVOBoxes can be used if the cloud network is composed of hybrid or multi-public clouds. The manager of all the boxes will be the Cloud Box (CLBox).

Figure 1 :

 1 Figure 1: Classification of tools which monitor grid computing networks and security management tools for traditional and grid computing networks.

Figure 2 :

 2 Figure 2: Intercommunication view of EBox, CBox and Local Analyzer

Figure 3 :

 3 Figure 3: SVOBox Main Dashboard

Figure 4 :

 4 Figure 4: GSOC Internal Architectural View

3 F 2 FFigure 5 :

 325 Figure 5: GSOC General Overview

Figure 6 :

 6 Figure 6: GSOC Security Alert Sharing Mechanism

  LA = Low Alerts. MA = Medium Alerts. HA = High Alerts. LAV = Low Alerts Value. MAV = Medium Alert Value. HAV = High Alert Value. SL = Security Level. GN = Grid Network. LS = Local Site. LSA = Local Sites Alerts. t = time at which the alerts detected. L = Low, M = Medium and H = High.

  elseif (LAV (AD) > M AV (AD) and M AV (AD) > HAV (AD) ) then SL = 1

  elseif (M AV (AD) > LAV (AD) and M AV (AD) > HAV (AD) ) then SL = 3[START_REF] Cremonini | An xml-based approach to combine firewalls and web services security specifications[END_REF] Nessus SA (L1,M1,H1) OpenVAS SA (L2,M2,H2) Saint SA (L3,M3,H3)

Figure 7 :

 7 Figure 7: Security Alert Statistics of 10 Machines using Nessus, OpenVAS and Saint

Figure 8 :

 8 Figure 8: Detection rate of BF, DoS and DDoS in Distributed Security Operation Center (DSOC)

Figure 9 :

 9 Figure 9: Detection rate of BF, DoS and DDoS in Grid Security Operation Center (GSOC)

Figure 10 :

 10 Figure 10: Stopping propagation of cross-domain attacks between our lab and G5K network

Figure 11 :

 11 Figure 11: No Mechanism for Security Alert Sharing in Grid Computing Network Scenario

Figure 12 :Figure 13 :

 1213 Figure 12: Unintelligent Mechanism for Security Alert Sharing in Grid Computing Network Scenario

Table 1 :

 1 Comparison of Different Grid Security Management Solutions

	GSS	DoS	DDoS	BF	SAS	SE	Cor	CDA	SC	FT	Comments
	GSOC	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Fully Suitable
	OSSIM	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Suitable
	Prelude [19]	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Suitable
					No	No	No	No	Yes	Yes	Partially Suitable
	LDIDS	Yes	?	?	Yes	No	Yes	Yes	Yes	Yes	Not Suitable
	DIDSoG	Yes	No	?	Yes	No	Yes	Yes	Yes	Yes	Partially Suitable
	GSS=Grid Security Solution, DoS=Denial of Service Attacks, DDoS=Distributed Denial of Service
	Attacks, BF=Brute Force Attacks, CDA=Cross-Domain Attacks, SAS=Security Alert Sharing,
	SE=Security Evaluation, Cor=Correlation, CDA=Cross-Domain Attacks, SC=Scalability, FT=Fault
				Tolerance, ? = Not known.
	FGIDS has introduced a new module called Backup Broker to help the sched-
	uler assign another DN to a dispatcher if a massive attacks occurs. FGIDS
	collects events from multiple sites of an administrative domain, but without
	having any correlation method for security alerts, it could be vulnerable to
	DDoS attacks that use grid computing power. Distributed attacks can be
	detected in one administrative domain but they cannot be detected if they
	target devices that are located in different administrative domains. More
	generally, cross-domain attacks cannot be detected by the different versions
	of GIDS.
	The architecture of Large-Scale Distributed Intrusion Detection
	System (LDIDS) proposed by Yonggang et al.

Table 2 :

 2 Security Evaluation Comparison of 10 Machines

	OpenVas				Nessus		Saint
	M #	LA	MA	HA	LA	MA	HA	LA	MA	HA
	M1	10	1	1	27	4	0	8	2	3
	M2	10	1	1	27	4	0	11	2	0
	M3	10	1	1	27	4	0	7	2	2
	M4	28	4	1	96	16	0	14	2	3
	M5	10	1	0	21	3	0	7	3	3
	M6	10	1	1	26	4	0	8	2	1
	M7	10	1	1	27	4	0	8	2	1
	M8	10	1	1	26	4	0	8	2	0
	M9	10	1	1	27	4	0	8	2	2
	M10	7	1	0	30	2	0	7	1	1
	Total	115	13	8	334	49	0	86	20	16

LA=Low Alerts, MA=Medium Alerts, HA=High Alerts, M#=Machine Number alerts reported, and HAV (High Alert Value) is the number of high alerts reported in any AD. The behavior of the AD can be categorized according to three case :


Sonia Cafieri
email: sonia.cafieri@enac.fr

Nicolas Durand
email: nicolas.durand@aviation-civile.gouv.fr

Aircraft deconfliction with speed regulation: new models from mixed-integer optimization

Keywords: air traffic management, conflict avoidance, MINLP, modeling, global exact solution, heuristic

Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact solver. The problem being very difficult to solve, we also propose a heuristic procedure where the problem is decomposed and it is locally exactly solved. Computational results show that the proposed approach provides satisfactory results.

Introduction

Aircraft sharing the same airspace are said to be potentially in conflict when they are too close to each other according to their predicted trajectories, that is, their relative horizontal and vertical distances do not both satisfy two given safety distances. Detection and resolution of aircraft conflicts, also referred to as aircraft deconfliction, is one of the most crucial issues in Air Traffic Management (ATM) to guarantee air traffic safety. This is even more evident observing that the air traffic level currently attained in Europe is around tens of thousands of flights per day and it is expected to be multiplied by a factor of two during the next 20 years [START_REF]Eurocontrol long-term forecast : IFR Flight Movements 2010-2030[END_REF]. The European project SESAR (Single European Sky ATM Research) [START_REF]The european ATM master plan[END_REF] gives the guidelines to go towards an Air Traffic Management characterized by more efficiency and more safety, which should essentially result from a higher level of automation of ATM. The request for increasing automation of ATM comes from the observation that the high level of automation that has been introduced on aircraft in the last 50 years, for example with the Flight Management System, does not correspond to the level of automation on the ground. In the context of aircraft conflict detection and resolution, air traffic control is still widely performed manually on the ground by air traffic controllers watching the traffic movements on a radar screen and giving instructions to pilots. Therefore, the need for automatical tools to integrate human work, shifting responsibilities from the ground to the air, is evident. Increasing levels of traffic also raise the problem of managing traffic in such a way as to increase the capacity of control in the air sectors.

Aicraft potential conflicts can be solved in different ways, which lead to different mathematical modeling approaches. The most commonly exploited way is based on the idea of achieving separation changing the trajectory (heading) or the flight level of the aircraft involved in the conflict. This kind of separation maneuvers is the one usually exploited by air traffic controllers when they detect a potential conflict. Another way is based on the idea of separating aircraft by slightly changing their speeds but keeping the predicted trajectories. A speed regulation which occurs in a reasonable small range (namelly, from -6% to +3% of the original speed), allows a subliminal control as suggested by the European ERASMUS project [START_REF] Bonini | How ERASMUS can support an increase in capacity in[END_REF]. This project showed the advantage of such a control, which is not perceived by air traffic controllers, and promoted it as an interesting alternative to the more traditional trajectory change.

Conflict avoidance is expected to be performed while deviating as little as possible from the original aircraft flight plan, that is, risks of collision should be avoided minimizing the impact of the separation maneuvers on the flight efficiency. To this aim, various solution strategies have been proposed for the corresponding optimization problem. A review is provided in [START_REF] Kuchar | A review of conflict detection and resolution modeling methods[END_REF]. Solution algorithms are mainly based on evolutionary computation [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF][START_REF] Durand | Optimal resolution of en-route conflict[END_REF][START_REF] Durand | Neural nets trained by genetic algorithms for collision avoidance[END_REF][START_REF] Durand | Ant-colony optimization for air traffic conflict resolution[END_REF]. Genetic algorithms tailored on the air traffic problem are widely used. These approaches consist in generating a population of aircraft trajectories from an initial population using the basic operators of selection, mutation and crossover, which are performed taking into account the features of the problem to gain efficiency. The solution space is a set of finite maneuvers, usually based on heading angle modifications. These methods are computationally efficient (few CPU time consuming), but the global optimal solution and even a feasible solution (with no conflicts) is not guaranteed to be achieved in a given time.

Recent advances in mixed-integer linear and nonlinear programming open new perspective for the deconfliction modeling and efficient solution. The first attempt to use mixed-integer optimization is by Pallottino et al. in [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF], where, though under stringent hypothesis, an interesting modeling based on a geometrical construction leads to a mixed-integer linear programming problem that can be solved by CPLEX. More recently, mixed-integer programming has been proposed again for aircraft conflict resolution. In the very recent PhD thesis by Martin-Campo [START_REF] Martin-Campo | The collision avoidance problem: methods and algorithms[END_REF] (see also [START_REF] Alonso-Ayuso | Collision avoidance in air traffic management: a mixed-integer linear optimization approach[END_REF][START_REF] Alonso-Ayuso | A mixed 01 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: Velocity changes through a time horizon[END_REF]), new nonlinear models are proposed, starting from a modification of the one in [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF]. In [START_REF] Vela | A mixed-integer program for flightlevel assignment and speed control for conflict resolution[END_REF] a linear model is obtained for flight levels assignment and speed regulation for conflict avoidance. The speed regulation strategy is also modeled by mixed-integer programming in recent work [START_REF] Rey | A mixed integer linear model for potential conflict minimization by speed modulations[END_REF][START_REF] Rey | Potential air conflicts minimization through speed regulation[END_REF] for minimization of potential conflicts.

In this paper, we propose new modeling for aicraft deconfiction based on speed regulation, keeping trajectories unchanged. Mixed-Integer Nonlinear Programming (MINLP) formulations appear to be the natural candidates for the addressed ATM problems, where the need for modeling logical choices suggests the simultaneous presence of mixed (continuous-integer) variables, and nonlinear constraints arise from separation condition modeling. In this context, the main challenge is to propose mathematical formulations which are able to model the complex choices characterizing the target problems without imposing any unrealistic constraint.

We first compute deterministic global solutions, using a general-purpose solver for MINLP. To deal with the computational difficulty of the problem, we also propose another strategy, where the optimality guarantee is forsaken in exchange for the computational efficiency, but exact solutions are computed locally. This solution strategy is based on hybridizing mathematical programming and a heuristic tailored on the problem.

The paper is organized as follows. In Section 2 we propose two mixed-integer optimization models for aircraft deconfliction based on speed regulation. Section 3 deals with the computational solution of the considered problem. In subsection 3.2 we discuss the results of computational experiments carried out with a general purpose global optimization solver. The proposed heuristic based on local exact solutions is presented in subsection 3.3. Some concluding remarks are given in Section 4.

Modeling aircraft deconfliction

In a mathematical programming model for deconfliction, the main constraint is represented by the aircraft separation condition. We therefore first discuss about such condition. We assume, for the sake of simplicity, that aircraft fly at the same flight level. They are then identified by 2-dimensional points on a plane and the horizontal separation has to be respected. The aircraft separation between two aircraft i and j at the instant time t is expressed by the following condition:

||x r ij (t)|| ≥ d, (1)
where d is the minimum required separation distance (usually, 5 NM 1 ) and x r ij (t) is the relative distance between aircraft i and j. Under the hypothesis that aircraft speed changes occur instantaneously at a given instant time t, we can consider that uniform motion laws apply before and after t. Hence, the relative position of aircraft i and j can be expressed as the sum of the relative initial position of aircraft i and j and the product of their relative speed v r ij by the time:

x r ij (t) = x rd ij + v r ij t ∀t. (2)
Squaring (1), with x r ij (t) expressed by (2), and deriving with respect to t, one can see that the minimum is attained for

t m = - v r ij x rd ij (v r ij ) 2 .
(3)

1 1 NM (Nautical Mile) = 1852 m
Substituting into (1), the following expression for the separation condition is obtained:

(x rd ij ) 2 - (v r ij x rd ij ) 2 (v r ij ) 2 -d 2 ≥ 0. (4)
Note that condition (4) has to be checked only when the inner product v r ij x rd ij is negative. In this case, indeed, aircraft are converging, generating a potential conflict. A more classical approach consists in considering the separation constraint in the form

||x r ij (t)|| = ||x i (t) -x j (t)|| ≥ d ∀t
and discretizing with respect to the time variable t, obtaining a set of constraints each one corresponding to an instant time. Equation ( 4) does not depend on the time variable t anymore, thus reducing the number of constraints. Nevertheless, in our modeling (4) is imposed in several time windows, as detailed in the following.

We now define mathematical programming models for the aircraft deconfliction problem such that aircraft separation is based only on speed regulation (other separation strategies, like heading angle or flight level modification, are not allowed). More precisely, starting from the known initial position and velocities of aircraft, reasonable small (in the sense that is precised below) changes in aircraft speeds are performed to have condition (4) satisfied along the predicted trajectories at each instant time t.

Various objective functions can be considered for the addressed problem. Conflict avoidance is expected to be performed while deviating as little as possible from the original aircraft flight plan, that is, risks of collision should be avoided minimizing the impact of the separation maneuvers on the flight efficiency. To stay as close as possible to the original flight plan, we minimize the sum of aircraft speed modifications:

min k∈A q 2 k , (5)
where ∀k in the set A of aircraft, q k expresses the speed change of aircraft k. This function can be slightly modified to take into account the minimization of the time windows when the speed changes occur, as detailed below.

The decision variables are q k , k ∈ A. These variables are bounded in order to ensure a "subliminal" speed control, as suggested by the ERASMUS project [START_REF] Bonini | How ERASMUS can support an increase in capacity in[END_REF]. Specifically, we impose that the speed change for aircraft k cannot be greater than +3% and smaller than -6% of its original speed. Other variables, both continuous and integer (in particular binary), are also employed in our problem formulation to express the afoarmentioned separation condition as follows.

In the first and simplest modeling we impose to aircraft an a priori speed change, at the instant time t = 0, and let them keep the new speed (w.r.t. the original predicted one) during the whole trajectory. We introduce auxiliary continuous variables for the relative speed and the inner product v r ij x rd ij in (4) and impose for each pair of aircraft i and j the separation condition (4). Equation (3) gives rise to a constraint, for each pair of aircraft, defining the minimum instant time. To check if t m is greater than 0, a binary variable y ij is introduced for each pair (i,j)

y ij = 1 if t m ≥ 0 0 otherwise (6)
and constraints are added accordingly. The separation condition is then checked only when t m ≥ 0:

∀i, j ∈ A y ij x rd ij (v r ij ) 2 -(v r ij x rd ij ) 2 -(d 2 (v r ij ) 2 ) ≥ 0, (7)
We now propose a general model, where no conditions are imposed on the order and on the instant time of separation maneuvers execution. Each aircraft can modify its speed at any possible instant time t s during its trajectory and go back to its original speed at any possible instant time t ′ s . Instant times t s and t ′ s are so unkown for each aircraft, and for each pair of conflicting aircraft it is not known the order of the respective instant times of speed change.

The main idea is then to deal with the different time windows where aircraft fly with their original (known) speed v or with a changed speed v + q, q representing a possible positive or negative speed change. Time windows are defined by instant times such that each aircraft changes its original velocity, i.e., it starts or ends flying with speed v +q. The speed is constant in each time window because of the assumption of instantaneous speed changes. In these time windows, aircraft k flyes with speed v k or v k + q k . New decision variables are introduced, representing the instant times such that aircraft k starts and respectively ends flying with changed speed:

∀k ∈ A t 1k , t 2k .
We have t 1k ≤ t 2k ∀k. Furthermore, t 1k and t 2k are always ≥ 0 and have an upper bound T , which represents the time horizon (usually around 20-30 minutes) during which the air traffic is observed and potential conflicts are solved. The optimization is performed repeatedly for successive time horizons with length T .

In order to be as close as possible to the original flight plans, the time intervals during which aircraft fly with a modified speed are also minimized. Thus, the objective function previously defined is modified in the following way:

min k∈A q 2 k (t 2k -t 1k ) 2 . ( 8
)
A number of auxiliary continuous and integer variables are also introduced. Suitable integer variables are in particular used to describe all possible time configurations. Due to the fact that t 1k , t 2k ∀k are unknowns of the problem and their sequential order is unknown as well, there are in fact 6 possible time configurations for each pair of aircraft. These are obtained considering the permutations of the 4 instant times characterizing the situation of a pair of aircraft changing their speed. Given a pair of aircraft i and j, let t 1i , t 1j and t 2i , t 2j be the instant times when i and j start and respectively end flying with changed speed. An order for t 1i , t 2i , t 1j , t 2j is not a priori known. By permutations of these instant times, excluding some cases giving rise to inconsistency (i.e., taking into account that ∀k t 1k ≤ t 2k and so a time sequence always starts with a t 1 instant and ends with a t 2 one), we obtain the following time configurations, where T represents the upper bound on time instants:

0 ≤ t 1i ≤ t 1j ≤ t 2i ≤ t 2j ≤ T (9) 0 ≤ t 1j ≤ t 1i ≤ t 2i ≤ t 2j ≤ T (10) 0 ≤ t 1i ≤ t 2i ≤ t 1j ≤ t 2j ≤ T (11) 0 ≤ t 1j ≤ t 2j ≤ t 1i ≤ t 2i ≤ T (12) 0 ≤ t 1i ≤ t 1j ≤ t 2j ≤ t 2i ≤ T (13) 0 ≤ t 1j ≤ t 1i ≤ t 2j ≤ t 2i ≤ T. ( 14
)
It is easy to see, taking into account lower (0) and upper bound (T ) for instant times, that each of these configurations defines 5 time intervals.

Aircraft separation condition has to be imposed in each time interval, for each time configuration. A number of variables and constraints are so adjoined to the model to handle all possible configurations. Firstly, the interval time for speed change must be at least equal to a certain amount

t min : ∀k ∈ A t 2k -t 1k ≥ t min . (15)
To model all possible time configurations we introduce binary variables z ℓ ij , ℓ ∈ {1, . . . , 6}, i, j ∈ A, stating, for each time configuration, what is the order of instant times for that configuration. For example, the binary variable z 1 ij , i, j ∈ A, associated to the first time configuration for the pair (i, j), is such that:

z 1 ij = 1 if t 1i ≤ t 1j and t 1j ≤ t 2i and t 2i ≤ t 2j 0 otherwise (16)
The following constraint imposes that only one configuration must hold:

∀i, j ∈ A ℓ∈{1,...,6} z ℓ ij = 1. ( 17
)
New variables are then introduced to define, for each pair of aircraft, their initial position in each time interval, their relative distance and their speeds. Distances covered by aircraft during each time interval are computed exploiting laws of uniform motion because of the aircraft's constant speed in each of such intervals. In the h-th time interval [t s , t s ′ ], h ∈ {1, . . . , 5}, for all aircraft k ∈ A the initial position x kh is given by

x kh = x k(h-1) + (t s ′ -t s )v k , ( 18
)
where vk is the original speed v k or the changed speed v k + q k , depending on the time configuration holding. So, (continuous) variables x kh ∀k ∈ A ∀h ∈ {1, . . . , 5}, are introduced and corresponding constraints adjoined to the formulation, expressing for each aircraft the 5 initial positions in the 5 time intervals. Each aircraft k has speed vk equal to its original speed or to the changed speed depending on the time configuration, so that variables z ℓ are used to identify the configuration holding. Relative distances x rd ij and relative speeds v r ij between aircraft are also defined, for each time configuration and each time interval, and constraints adjoined accordingly using variables x kh and again z ℓ .

Further constraints are then adjoined to the model to impose the condition (4) in each of the 5 time intervals, when t m ∈ [t s , t s ′ ], where [t s , t s ′ ] is the h-th time interval. In order to check if t m ∈ [t s , t s ′ ], binary variables are used. For all h ∈ {1, . . . , 5} a binary variable y lh is introduced such that y lh = 1 if t sh ≤ t mh and 0 otherwise, y rh is such that t mh ≤ t s ′ h and 0 otherwise. The following constraints are then imposed:

∀h ∈ {1, . . . , 5} t sh ≤ t mh + M(1 -y lh ), t mh ≤ t sh + My lh (19) t mh ≤ t s ′ h + M(1 -y rh ), t s ′ h ≤ t mh + My rh ( 20
)
where M is a sufficiently large constant. Condition ( 4) is then imposed for each time configuration ℓ ∈ {1, . . . , 6}, ∀h ∈ {1, . . . , 5} and i, j ∈ A, as follows:

y lh y rh (x rd ijh ) 2 - (v r ijh x rd ijh ) 2 (v r ijh ) 2 -d 2 ≥ 0. (21)
Finally, for each time interval, the following separation condition is also imposed:

∀h ∈ {1, . . . , 5}, ∀i, j ∈ A (x rd ijh ) 2 ≥ d 2 . ( 22
)
3 Solving aircraft deconfliction

Test problems generation

Let us consider as a testbed a set of n aircraft in 2-dimensional space, placed on a circle of a given radius r, with initial speed v and trajectory defined by a heading angle such that aircraft fly pointing toward the center of the circle (or slightly deviating with respect to such direction). The zone of conflict is around the center of the circle where aircraft are placed, and each aircraft may be in conflict with each other. In our computational experiments, we considered a time horizon T = 30 minutes, the standard separation distance d = 5 NM, initial speed equal to v = 4 × 10 2 NM/h for all aircraft and heading angles randomly generated varying between ±5 degrees with respect to the trajectories pointing toward the center of the circle. All aircraft are in conflict with each other, so that a number of conflicts equal to n(n -1)/2 is generated in the same conflict zone. See Figure 3.1. This kind of test problem, though does not correspond to a realistic situation, represents a good trade-off between simplicity of illustration and difficulty of resolution, to stress models and algorithms for deconfliction. It has been already used to this aim (see, e.g. [START_REF] Durand | Ant-colony optimization for air traffic conflict resolution[END_REF]).

Figure 1: n conflicting aircraft flying towards the center of a circle.

Results discussed in the following are obtained on a 2.4 GHz Intel Xeon CPU of a computer with 8GB RAM shared by three other similar CPU running Linux.

Global exact solution

We implemented the proposed models using the AMPL modeling language [START_REF] Fourer | The AMPL Book[END_REF].

We first employ a general purpose global optimization solver for MINLP to solve the addressed problem to global optimality. The solver of choice is COUENNE [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF], which implements a spatial Branch-and-Bound based on convex relaxations. Results are reported in Table 1 for the first proposed model. For each problem instance (given by a number n of aircraft and a radius r of the circle representing the considered airspace) we report the objective function value and the CPU time to solve the problem. We are able to obtain global exact solutions up to n = 6, i.e. [START_REF] Rey | Potential air conflicts minimization through speed regulation[END_REF] Increasing the number of aircraft n, the number of variables, in particular of binary variables used to model logical choices, and the number of constraints largely increases, thus growing the size of the search tree to explore. Hence, the time to reach the leaves of the tree, which represent optimal solutions, may become very high. Hence, as expected for a Branch-and-Bound algorithm, high memory and time requirements do not allow us to obtain optimal solutions for larger dimensions of the problem.

Results in Table 1 refer to the relaxed modeling where we assume that aircraft change their speed at t = 0 to achieve trajectory separation. The more general model that we propose in Sect.2 is, as expected, more computationally challenging, due specially to the larger number of binary variables and constraints used to model time configurations and time intervals. Therefore, we expect to solve to global optimality only small-size problems. For the sake of illustration, we describe computational results obtained with the most general model on problem instances involving a pair of aircraft. Results are given in Table 2. Aircraft are again supposed to move from an initial position given, in 2-dimensional space, on a circle (r = 1 × 10 2 NM) with v = 4 × 10 2 NM/h. Keeping the original speed, the aircraft would reach the center of the circle in 15 minutes. The problem is simplified in such a way that aircraft k is assumed to change its speed on an instant t 1k and keep the new speed. For each instance we report data details, given by the heading angles of the two aircraft, and solution details, given by velocity change (q k ) and instant time when the speed change occurs (t 1k ) for aircraft k, objective function value and CPU time. Again, objective function values show that slight speed changes are sufficient to achieve separation. CPU times are less then 2 seconds, thus showing that even the general model is promising for optimal deconfliction in reasonable time for small-scale problems.

We note that symmetric equivalent solutions are possible for the considered test problem, where for pairs of aircraft we can swap their roles. Spatial Branch-and-Bound algorithms, like the one implemented in COUENNE, suffer from the presence of symmetries, which led to very large Branch-and-Bound trees. Simple symmetry breaking constraint like q i ≤ q j ∀i, j ∈ A, i < j,

adjoined to the formulation, may help to speed up the resolution. However, they are not considered in our study, because they correspond to an unrealistic modeling of the addressed ATM problem.

A heuristic based on local exact solutions

From the numerical results discussed in the previous section, it appears that an exact solution algorithm for the addressed problem easily turns to be high memory and time demanding, due to the high number of conflicts and the number of variables and constraints largely increasing with n. However, we also note that on problem instances involving a small number of aircraft at a time, say 3-4 aircraft, a global solution can be efficiently computed. Based on this observation, we propose a solution procedure which is based on the idea of decomposing the overall problem into subproblems involving only a small number of aircraft and performing deconfliction on these subproblems, then combining all local solutions. The overall procedure is heuristic, based on Mathematical Programming and local exact solutions, in a matheuristic framework.

When dealing with aircraft conflict avoidance, one naturally looks at subproblems of the original one. In a realistic situation, the airspace section under consideration is a quite large portion of the airspace covering the trajectories of a large number of aircraft, among which generally only small groups of aircraft with close trajectories get potentially in conflict. This led some authors to introduce the concept of cluster.

Let a cluster be the transitive closing on conflicting pairs of aircraft (see [START_REF] Granger | A traffic complexity approach through cluster analysis[END_REF]). The heuristic is based on the idea of solving the deconfliction problem on clusters involving up to 4 aircraft at a time. Let ncl be the number of clusters. This number, and the aircraft therein, can be detected by a suitable pre-processing. The heuristic proceeds iteratively until deconfliction is successfully performed, or a given stopping criterion is satisfed. At each step, ncl deconfliction problems, one for each aircraft cluster, are sequentially solved by using an exact solver. Combining together all the results, one cannot expect in general to have all conflicts solved. This is because aircraft inside clusters may be in conflict also with aircraft inside other clusters. Should all conflicts be solved, the whole problem is solved and its solution is locally optimal. When this is not the case, that is, the number of remaining conflicts is greater than 0, a new step is performed. The next iteration is made in such a way to preserve as much as possible the information outcoming from the previous solution. To do so, the initial speed (which together with the initial position represents the data of the problem) of aircraft that are still in conflict is re-initialized taking into account the solution obtained at the previous step. More precisely, if the (optimal) solution obtained for cluster i is such that an aircraft in this cluster has been accelerated with respect to its original speed, then its speed is modified by a random slight further increase. If it has been decelerated, then its speed is modified by a random slight further decrease. In this way, the information obtained at the previous step is preserved and the chances to keep deconfliction inside clusters increase.

To update the aircraft speeds, a simple local search is performed. A number of candidates in the neighboroods of the initial speed values are tested, choosing the one that minimize a measure of the conflict severity. Specifically, we consider as such a measure the sum, over all conflicting aircraft, of the maximum violation of the separation constraints for each considered aircraft, relativized by dividing by the number of remaning conflicts. When one only conflict is to be solved, this search is intensified testing a larger number

Conclusion

We discussed about modeling and solving a challenging problem arising in Air Traffic Management, namely the problem of aircraft conflict resolution, via mixed-integer optimization. We proposed new MINLP formulations for deconfliction based on speed regulation, where conflicts are avoided allowing aircraft to only accelerate or decelerate, without any change in their trajectory. We first considered a speed regulation occurring at the instant time t = 0, modifying the initial speed of aircraft with respect to the original predicted one. We then proposed a modeling where speed regulation occurs during time windows in such a way that aircraft fly with a modified speed in a time interval and then go back to their previous speeds. Speed changes and time intervals when they occur are minimized jointly.

We solved the problem using a general purpose deterministic global optimization solver, showing that mixed-integer optimization programs for aircraft deconfliction solved by deterministic global optimization provides promising results. We also proposed a heuristic tailored on the problem and based on locally solving the problem to global optimality, which provides good quality results for medium-scale problems. Future work will address alternative mathematical programming formulations and possible reformulations of the proposed ones. From the point of view of solution approaches, a comparison with a Branch-and-Bound based on interval arithmetic and the further development of hybrid strategies, combining the above deterministic approaches with suitable heuristic ones, could provide interesting insights.

Table 1 :

 1 conflicts. Objective function values show that aircraft separation is always achieved with very slight speed changes. Conflict resolution for n aircraft flying towards the centre of a circle of radius r: objective function value and CPU time. Global optimal solutions are obtained with

	ID	n	r	obj	CPU time
					(sec.)
	pb n2	2	1 ×10 2 0.002531	0.15
	pb n3	3	2 ×10 2 0.001667	1.45
	pb n4	4	2 ×10 2 0.004009	12.87
	pb n5	5	3 ×10 2 0.003033	841.33
	pb n6	6	3 ×10 2 0.006033 51863.37

COUENNE.

Table 2 :

 2 Conflict resolution for 2 aircraft: optimal solutions and CPU time. The more general proposed model is used.

Table 3 :

 3 Conflict resolution for n aircraft flying towards the centre of a circle of radius r: objective function value and CPU time. Solutions are obtained with the proposed heuristic beased on local exact solutions on ncl clusters.

of candidates to increase the chances to solve the problem.

According to the ERASMUS directives, aircraft speed changes have to be bounded in the small range [-6%v, +3%v], v being the original speed. To fulfill this requirement, when speeds are modified during the algorithm, these bounds are checked and speeds adjusted accordingly. This may eventually lead to change the speed scenario provided by local exact solutions.

A sketch of the proposed algorithm is given in Alg. 1. It may be intended as a general framework, where, starting from the same basic idea tailored on the problem, one can implement different local solution computations and local searches. Results are reported in Table 3.3. Values are averaged over 10 runs. For all test problems, all conflicts have been solved (nconf l = 0). Objective function values show that deconfliction is always achieved with very slight speed changes. Comparing the solutions obtained on pb1 using 1 cluster (direct solution on Table 1) or 2, it appears that decomposing the problem does not significantly affect the quality of the result. While for n = 4 a direct solution is, as expected, more convenient, increasing n faster solutions are obtained using a higher number of smaller subproblems. The sharp bound imposed on speeds changes to perform a subliminal control is responsible of the most of the execution time. This subliminal control is anyway performed in reasonable time even on problems involving many conflicts at a time.

Algorithm 1 Aircraft Deconfliction