  The network virtualization paradigm envisions an Internet where arbitrary
virtual networks (VNets) can be specified and embedded over a shared substrate
(e.g., the physical infrastructure). As VNets can be requested at short notice
and for a desired time period only, the paradigm enables a flexible service
deployment and an efficient resource utilization.
  This paper investigates the security implications of such an architecture. We
consider a simple model where an attacker seeks to extract secret information
about the substrate topology, by issuing repeated VNet embedding requests. We
present a general framework that exploits basic properties of the VNet
embedding relation to infer the entire topology. Our framework is based on a
graph motif dictionary applicable for various graph classes. Moreover, we
provide upper bounds on the request complexity, the number of requests needed
by the attacker to succeed.
