Network Functions Virtualization (NFV) implements virtual network functions (such as firewall, IDS, etc.) as service chains over a cloud computing infrastructure to provide dynamic, scalable, and cost-efficient network services. This layered design of NFV is a double-edged sword that may also lead to unique security concerns for NFV tenants including the breach of the integrity of their service chains through various attacks (e.g., VNF bypassing, packet injection, etc.). To make things worse, the underlying infrastructure-level data is typically owned by third-party cloud providers, which renders such data unavailable to NFV tenants to directly examine the actual deployment of their service chains. In this work, we propose a blackbox approach, namely, artificial packet-pair dispersion (APPD), which can work around this limitation of unavailable infrastructure-level data to still allow NFV tenants to verify the integrity of service chains. To that end, APPD first estimates the throughput of incoming NFV traffic based on inter-packet delay by creating an artificial congestion (as natural congestion may not always be present in a high bandwidth environment involving cloud and NFV) for a short period of time. APPD then verifies service chain integrity by comparing this estimated throughput with the throughput of the actual traffic flowing through the service chains. Our experimental results with both real and synthetic datasets confirm the effectiveness and negligible overhead of APPD.