We discuss the necessity of considering security constraints in virtual network embedding problems.We formulate the security-aware virtual network embedding as an optimization problem.Two heuristic algorithms are proposed to solve the security-aware virtual network embedding problem.Both algorithms show efficiency and effectiveness in our simulation. Network virtualization is one of the fundamental building blocks of cloud computing, where computation, storage and networking resources are shared through virtualization technologies. However, the complexity of virtualization exposes additional security vulnerabilities, which can be taken advantage of by malicious users. While traditional network security technologies can help in virtualized environments, we argue that it is cost-effective to isolate virtual resources with high security demands from the untrusted ones.This paper attempts to tackle the security issue by offering physical isolation during virtual network embedding, the process of allocating virtual networks onto physical nodes and links. We start from modeling the security demands in virtualized environments by analyzing typical security vulnerabilities. A simple abstracted concept of security demands is defined to capture the variations of security requirements, based on which we formulate security-aware virtual network embedding as an optimization problem. The proposed objective and constraint functions involve both resource and security restrictions. Then, two heuristic algorithms are developed to solve this problem with splittable or unsplittable virtual links, respectively. Our simulation results demonstrate their efficiency and effectiveness.