Over the past decade, Network Functions Virtualization (NFV) has revolutionized networking by leveraging virtualization to separate Network Functions (NFs) from dedicated physical hardware. However, this architecture introduces unique security risks, such as stealthy attacks causing discrepancies between tenant-level NF specifications and cloud provider-level deployment. To safely utilize NFV, robust security auditing mechanisms are crucial to ensure compliance and detect breaches. Yet, existing methods face challenges: NFV tenants have limited access to cloud infrastructure, and providers are hesitant to share data due to confidentiality concerns. Relying solely on providers for auditing may overlook tenant-specific requirements and legitimate modifications by attackers. Furthermore, current solutions often require unrealistic infrastructure modifications. This thesis introduces novel auditing solutions for both tenants and providers of NFV, addressing these limitations. Firstly, an interactive anonymization tool called iCAT facilitates selective, privacy-preserving data sharing between tenants and providers. It utilizes an anonymization space to model various anonymization techniques, translating requirements from both parties into suitable primitives using NLP and ontology modeling. Secondly, a tenant-based, two-stage solution enhances auditing autonomy. The first stage utilizes tenant-side information to detect integrity breaches, while the second stage anonymizes provider-level data for tenant verification, offering control, transparency, and accuracy in breach identification. Additionally, a cryptographic approach is combined with side-channel watermarking to bolster tenant security. This lightweight solution enables continuous detection and classification of cloud-level attacks on service function chains, encoding cryptographic trailers as side-channel watermarks. This approach ensures verifiable attack detection without significant overhead, overcoming challenges such as limited side channel capacity and packet delay. By addressing these issues, the proposed solutions aim to enhance the security of NFV deployments and enable safer utilization of this innovative networking architecture.