The growing adoption of virtualization technologies and micro-services architectures is re-shaping the traditional security paradigms for running software appliances. Services are now designed as graphs of simple applications deployed over a virtualized set of computing resources. Although de-coupling software from the underlying infrastructure brings immediate benefits in terms of elasticity, portability, automation and resiliency, the intermediate hypervisor tier also raises new security concerns about the mutual trustworthiness between those two layers and the potential threats in the virtualization substrate. In order to guarantee security in the virtualized environment it is therefore necessary to integrate the security aspect in the design of the service graph.