Modern network virtualization platforms enable users to specify custom topologies and arbitrary addressing schemes for their virtual networks. These platforms have, however, been targeting the data center of a single provider, which is insufficient to support (critical) applications that need to be deployed across multiple trust domains, while enforcing diverse security requirements. This paper addresses this limitation by presenting a novel solution for the central resource allocation problem of network virtualization -- the virtual network embedding, which aims to find efficient mappings of virtual network requests onto the substrate network. We improve over the state-of-the-art by considering security as a first-class citizen of virtual networks, while enhancing the substrate infrastructure with resources from multiple cloud providers. Our solution enables the definition of flexible policies in three core elements: on the virtual links, where alternative security compromises can be explored (e.g., encryption); on the virtual switches, supporting various degrees of protection and redundancy if necessary; and on the substrate infrastructure, extending it across multiple clouds, including public and private facilities, with their inherently diverse trust levels associated. We propose an optimal solution to this problem formulated as a Mixed Integer Linear Program (MILP). The results of our evaluation give insight into the trade-offs associated with the inclusion of security demands into network virtualization. In particular, they provide evidence that enhancing the user's virtual networks with security does not preclude high acceptance rates and an efficient use of resources, and allows providers to increase their revenues.

1. Paper title changed to be more suitable; 2. Rewrite Introduction (section 1), Secure Virtual Network Embedding Problem (section 3) and MILP Formulation (Section 5) to make it clearer; 3. Figure 3 inserted to help in explanation on the main and backup VNE mappings; 4. Added references on Related Work (Section 7)