With the increase in cyberattacks, developing appropriate strategies to mitigate and prevent them is essential. In the literature, tools exist that either help prevent or mitigate them. Attack graphs help define mitigation strategies because they help represent and visualize the attacker’s position on a system. However, the mitigation actions are not instantiated on the attack graph. This paper proposes an approach to generate an automated attack-defense graph based on real-time monitored system alerts and an extensive and comprehensive state-of-the-art review. We propose to enrich logical attack graphs generated by a logical reasoner. The enrichment process is possible thanks to a vulnerability ontology that infers additional impacts for an exploited vulnerability. We propose a countermeasure selection approach based on graph matching to generate an optimal Incident Response (IR) playbook. We propose instantiating the generated playbook’s IR actions to get an attack-defense graph in real-time. This instantiation is done thanks to anti-correlation. The anti-correlation ensures that the countermeasures are instantiated on the appropriate attack graph nodes. Only the IR actions whose execution can be launched automatically are applied. We validate our approach using two use-case scenarios that target critical industrial infrastructures. We analyze the countermeasures instantiated on the attack graphs for the scenarios that can achieve the attack goal. We evaluated the approach concerning the security relevance of instantiated countermeasures in attack graphs for several attack paths. The countermeasures instantiated on a node are always relevant to the attacker’s action represented by this node. We also evaluate the approach regarding time performance, considering several situations for the use-case scenarios. The generation time depends on the number of vulnerabilities involved in the scenario. The generation time is on average 0.161 s when the playbook has been generated before the attack defense graph generation process.

This paper addresses uncertainty in resource demands and heterogeneous requests with affinity and anti-affinity constraints on virtual nodes and links in traditional Virtual Network Embedding. This is realized using stochastic modeling and methods based on an initial Integer-Linear Programming (ILP) model formulation of the VNE problem. The ILP is extended to build a non-linear Chance-Constrained Programming (CCP) model to address uncertainty. The derived CCP model is then linearized for exploitation by standard solvers. Numerical experiments and comparisons with state-of-the-art methods illustrate the efficiency of our approaches. The results provide insight to cloud service providers on their resource investment to serve clients with affinity and anti-affinity requirements under uncertainty.

International audience

This paper focuses on a dynamic embedding of client-constrained heterogeneous Virtual Network (VN) requests with multiple nodes and links affinity and anti-affinity requirements. For this Virtual Network Embedding (VNE) problem, we formulate an Integer-Linear Programming (ILP)-based model that achieves joint mapping of virtual nodes and links of each VN onto the dynamically updated Substrate Network (SN). This model not only meets the clients expressed isolation constraints but also includes VN request arrivals and departures to update SN information. Numerical experiments illustrate the efficiency of the proposed methods and their ability to find optimal solutions. Performance reports provide cloud service providers with insights into additional investments in nodes and links they should make to serve clients with anti-affinity requirements.

International audience

International audience

The density increasing in Radio Access Networks (RAN) caused the migration of traditional base stations to the cloud to meet huge traffic of end-users' demands. In this context, virtualization techniques can add more flexibility and programmability to scale in/out virtual storage, network and computing resources. However, Cloud-RAN (C-RAN) requires real-time processing and scheduling of its demands represented as service chains. In this paper, we formulate the joint assignment and scheduling problem in C-RAN using linear programming approach. Placement and scheduling algorithms allowing to allocate efficiently computing resources for C-RAN Virtual Network Functions (VNFs) with respect to the RAN services chaining are introduced and their behavior is quantified through real traces. We illustrate and highlight the feasibility and efficiency of our proposed algorithms through different scenarios in various considered network instances. Metrics such as cpu cores occupancy, network throughput, and successful subframe decoding rate are used to illustrate our algorithms' efficiency.

Real-time requirements in video streaming and processing are increasing and represent one of the major issues in industry 4.0 domains. In particular, Face Detection (FD) use-case has attracted the interest of industrial and academia researchers for various applications such as cyber-physical security, fault detection, predictive maintenance, etc. To ensure applications with real time performance, Edge Computing is a good approach which consists in bringing resources and intelligence closer to connected devices and hence, it can be used to cope with strong latency and throughput expectations. In this paper, we consider optimal routing, placement and scaling of virtualized face detection services at the edge. We propose an edge networking approach based on Integer Linear formulation to cope with small problem instances. A reinforcement learning solution is proposed to address larger problem sizes and scalability issues. We assess the performance of our proposed approaches through simulations and show advantages of the reinforcement learning approach to converge towards near-optimal solutions in negligible time.

With the rapid deployment of Internet of Things (IoT) applications, video processing and streaming requirements are increasing, and edge computing is a good candidate to cope with strong latency and throughput expectations. In this paper, we consider the optimal routing, placement and scaling of IoT-based service function chains for object detection. We propose an edge networking approach dealing with limited CPU and network bandwidth resources in a joint optimization based on Integer Linear Programming for small problem instances, and a graph-based approximation to cope with scalability issues. We evaluate the efficiency of our algorithms through simulations and show that the graph-based approach converges towards a near-optimal solution in negligible time and is thus suitable for real-time function chain placement.

We propose a meta-heuristic based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II) to address the NP-Hard service function chain placement problem. This work considers the minimization of the mapping cost and of the physical links utilization for virtualized network functions (VNF) chaining. The proposed NSGA-II based algorithm finds a Pareto front to select solutions that meet the multiple objectives and performance tradeoffs of providers. Simulation results and comparison with a multi-stage algorithm and a matrix based heuristic from the literature, highlight the efficiency and usefulness of the proposed NSGA-II-based approach.

We focus on the full coverage hole problem in the context of Cloud Radio Access Networks while considering joint holes detection and cells interferences minimization. We propose a Branch and Cut algorithm describing the convex hull of this NP-Hard problem. New valid inequalities based on chordless cycles detection and network connectivity are added to this formulation to accelerate convergence time and detect rapidly coverage holes. Our Branch and Cut algorithm finds optimal solutions in acceptable times even for large problem instances. Simulation results and comparison to the state of the art highlight the efficiency and the usefulness of our approach.

Vehicular Edge Computing Network (VECN) is a new concept with the potential to support future vehicular applications by providing close-to-vehicles great computation services. This would especially enhance the performance of the delay sensitive safety applications designed for autonomous driving. However, VECN is a target of several attacks which aim at disrupting the offloading mechanism requested by legitimate vehicles. Thereby, in this paper, we propose a security scheme for VECN based on behavioral game to prevent the network attacks over the offloading operations and hence to improve the efficiency of the vehicular safety services. According to our simulation results, the proposed Secure Vehicular Edge Computing (S-VECN) has great advantages in optimizing the end-to-end delay of the offloading operations, while enhancing the detection and classification rates of malicious nodes.

This paper proposes Steiner-based algorithms to extend already deployed tenant slices or Virtualized Network Functions Forwarding Graphs (or Service Function Chains) as demand grows or additional services are appended to prior service functions and chains. The tenant slices are hosted by Network Function Virtualization Infrastructure (NVFI) providers that can make use of the proposed algorithms to extend tenant slices on demand for growing traffic loads and service extensions including protection and security services(such as extending a slice with a dedicated security slice). The paper proposes a Steiner-based ILP as an exact solution for small graphs and Steiner based approximation algorithms to improve scalability for larger problems.

This paper considers the optimal placement of Baseband Unit (BBU) function split in Cloud Radio Access Networks (C-RANs) which is an essential key technology in C-RAN deployment. In particular, the BBU function split is modeled as directed chains to be mapped to a network infrastructure. As such, we propose an Integer Linear Program (ILP) formulation for small and medium size networks. Alternatively, we introduce four heuristic algorithms with significantly less complexity. We then benchmark the four heuristic algorithms based on the construction of a multi-stage graph. The simulation results strongly confirm the efficiency and scalability of our algorithms as well as their ability to achieve an optimal solution.

This paper assesses the benefits of cloud federation for cloud providers. Outsourcing and insourcing are explored as means to maximize the revenues of the providers involved in the federation. An exact method using a linear integer program is proposed to optimize the partitioning of the incoming workload across the federation members. A pricing model is suggested to enable providers to set their offers dynamically and achieve highest revenues. The conditions leading to highest gains are identified and the benefits of cloud federation are quantified.

This paper addresses the problem of cloud and networking resources mapping in distributed and hybrid cloud environments. In this context private and public resources are acquired and combined to set up tenant dedicated virtual infrastructures to fulfil distributed applications requirements. An exact algorithm is proposed to map jointly nodes and links of the requested virtual infrastructure graph to the physical graph from multiple providers (data centers and network providers). We view the problem as a virtual network mapping and use integer linear programming to find optimal solutions. To address complexity and scalability for large virtual and physical networks of thousands of nodes, an efficient heuristic algorithm, relying on topology patterns and bipartite matching, is used to provide close to optimal solutions and reduce mapping delays by three to four orders of magnitude.

Virtual Content Delivery Network (vCDN) migration is necessary to optimize the use of resources and improve the performance of the overall SDN/NFV-based CDN function in terms of network operator cost reduction and high streaming quality. It requires intelligent and enticed joint SDN/NFV migration algorithms due to the evident huge amount of traffic to be delivered to end customers of the network. In this paper, two approaches for finding the optimal and near optimal path placement(s) and vCDN migration(s) are proposed (OPAC and HPAC). Moreover, several scenarios are considered to quantify the OPAC and HPAC behaviors and to compare their efficiency in terms of migration cost, migration time, vCDN replication number, and other cost factors. Then, they are implemented and evaluated under different network scales. Finally, the proposed algorithms are integrated in an SDN/NFV framework.

We address the online virtual network embedding problem within the Cloud's backbone to optimally map the virtual routers and links in the substrate network in order to maximize the Cloud's provider revenue. Since the problem is NP-hard, we propose a novel approach, named VNE-GH, to significantly reduce the problem size using the Gomory-Hu transformation without losing useful information on the virtual network embedding problem. Starting from the Gomory-Hu compact tree structure, we formulate the virtual network embedding as an Integer Linear Program and resolve the reduced size problem using the branch- and-cut algorithm. Results obtained via extensive simulations show that VNE-GH outperforms the most prominent related work strategies in terms of i) acceptance rate of virtual network requests and ii) Cloud provider's revenue.

This paper addresses profit optimization through insourcing and outsourcing virtual resources (seen as VMs) for cloud infrastructure providers. A linear program is proposed to assist IaaS providers, involved in a cloud federation, in adjusting their hosting and cooperation decisions in response to their workloads and available resources. The proposed exact formulation takes into account the prices and quotas proposed by the federation members and the costs of resources and their networking to maximize providers revenues. The algorithm performance evaluation and the identified benefits show the conditions for profitable cloud federations and the efficiency of the proposed model in improving profit.

The emergence of cloud computing makes the use of remote storage more and more common. Clouds provide cheap and virtually unlimited storage capacity. Moreover, thanks to replication, clouds offer high availability of stored data. The use of public clouds storage make data confidentiality more critical as the user has no control on the physical storage device nor on the communication channel. The common solution is to ensure data confidentiality by encryption. Encryption gives strong confidentiality guarantees but comes with a price. The time needed to encrypt and decrypt data increases with respect to the size of input data, making encryption expensive. Due to its overhead, encryption is not universally used and a non-negligible amount of data is insecurely stored in the cloud. In this paper, we propose a new mechanism, called Light Blind, that allows confidentiality of data stored in the cloud at a lower time overhead than classical cryptographic techniques. The key idea of our work is to partition unencrypted data across multiple clouds in such a way that none of them can reconstruct the original information. In this paper we describe this new approach and we propose a partition algorithm with constant time complexity tailored for modern multi/many-core architectures.

This paper presents two exact algorithms for energy efficient scheduling of virtual machines (VMs) in cloud data centers. Modeling of energy aware allocation and consolidation to minimize overall energy consumption leads us to the combination of an optimal allocation algorithm with a consolidation algorithm relying on migration of VMs at service departures. The optimal allocation algorithm is solved as a bin packing problem with a minimum power consumption objective. It is compared with an energy aware best fit algorithm. The exact migration algorithm results from a linear and integer formulation of VM migration to adapt placement when resources are released. The proposed migration is general and goes beyond the current state of the art by minimizing both the number of migrations needed for consolidation and energy consumption in a single algorithm with a set of valid inequalities and conditions. Experimental results show the benefits of combining the allocation and migration algorithms and demonstrate their ability to achieve significant energy savings while maintaining feasible convergence times when compared with the best fit heuristic.

Abstract This article focuses on the problem of computing a minimum‐weight subgraph with unicyclic connected components. Although this problem is generally easy, it becomes difficult when a girth constraint is added. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Hence, the problem is solved by a cutting‐plane algorithm based on these inequalities and using a compact formulation derived from the transversality of the bicircular matroid. Numerical results are also presented. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013

A minimum cost maximum flow algorithm is proposed for resources(e.g. virtual machines) placement in clouds confronted to dynamic workloads and flows variations. The algorithm is compared to an exact method generalizing the classical Bin-Packing formulation using a linear integer program. A directed graph is used to model the allocation problem for cloud resources organized in a finite number of resource types; a common practice in cloud services. Providers can use the minimum cost maximum flow algorithm to opportunistically select the most appropriate physical resources to serve applications or to ensure elastic platform provisioning. The modified Bin-Packing algorithm is used to benchmark the minimum cost maximum flow solution. The latter combined with a prediction mechanism to handle dynamic variations achieves near optimal performance.

Radio resource and mobility managements are becoming more and more complex within nowadays rich and heterogeneous wireless access networking systems. Multiple requirements, challenges and constraints, at both technical and economical perspectives have to be considered. While the main objective remains guaranteeing the best Quality of Service and optimal radio resource utilization, economical aspects have also to be considered including cost minimization for users and revenue maximization for network providers. In this paper, we propose a game theoretic scheme where each available network plays a Stackelberg game with a finite set of users, while users are playing a Nash game among themselves to share the limited radio resources. A Nash equilibrium point is found and used for vertical handover decision making and admission control. We also introduce in the proposed model the user's requirements in terms of quality of service according to its running application and the network reputation that is conducted from the users' quality of experience and we study the effect of these parameters on the network pricing and revenue maximization problems.

Constrained pricing in a cloud computing environment is addressed using game theory. The objective of the model and the game is to enable cloud providers to maximize their revenue while satisfying users by maximizing their utilities. The users net utility is modeled as a function of resource demand with a corresponding price. The game consists in the cloud provider suggesting differentiated prices according to demand and users updating their requests in view of the proposed price. The objective is to determine the optimal suggested prices by the cloud-provider and the optimal user demands. A theoretical model based on Stackelberg game is proposed and a Stackelberg/Nash equilibrium solution is found. Performance results show that rejecting a certain number of users is not the best decision to select. Cloud provider should deploy the right amount of resources to maintain good reputation while satisfying users' requirements.

This paper focuses on the design of minimum-cost networks satisfying two technical constraints. First, the connected components should be unicyclic. Second, some given special nodes must belong to cycles. This problem is a generalization of two known problems: the perfect binary 2-matching problem and the problem of computing a minimum-weight basis of the bicircular matroid. It turns out that the problem is polynomially solvable. An exact extended linear formulation is provided. We also present a partial description of the convex hull of the incidence vectors of these Steiner networks. Polynomial-time separation algorithms are described. One of them is a generalization of the Padberg–Rao algorithm to separate blossom inequalities.