Network virtualization promises to fulfill the demand for an agile Internet that is friendly to technological innovation. In the past, tremendous efforts have been dedicated to studying the fundamental problem in network virtualization, namely Virtual Network Embedding (VNE). However, until recently, very limited work has addressed the security issues and implications of VNE or network virtualization as a whole, despite their importance. On one hand, the literature lacks a systematic overview of security issues in network virtualization (e.g., which can be VNE-relevant or VNE-irrelevant). On the other hand, existing studies on security-aware VNE share common limitations. This paper aims to present a timely study to fill the above needs with the following contributions: First, we present a classified comprehensive overview of security issues that arise in the context of network virtualization based on multiple criteria. Second, based on the review of existing approaches in Security-aware Virtual Network Embedding (SVNE), a novel framework is presented to address VNE-relevant security issues in network virtualization. Third, our extensive evaluation uncovers a few important implications and shows that the proposed framework can address the SVNE problem with reduced time (compared to that of the regular VNE approach).