In this paper we propose a novel approach to the problem of deep attestation. Deep attestation is a particular case of remote attestation, a.k.a. verifying the integrity of a platform with a remote verification server. Currently, two solutions have been proposed by the ETSI for remote attestation of the hypervisors and hosted VMs. The first is called single-channel and requires the attestation of the hypervisors for each VM, while the other requires only one attestation of the hypervisor. However, in the latter case, we have no assurance that the two attestations come from components hosted on the same physical platform.

We look at the property of linkage, which is part of the reason why deep attestation is performed: verifying both a virtual machines and its host, and checking that both run on the same physical hardware by linking their attestation. Our contribution is two-fold: first, we provide a formal model in which the security and linkability of system-wide attestation can be analyzed, no matter the underlying mechanism for attestation being considered such as Trusted Platform Machines (TPM). Furthermore, we have implemented and analyzed its performance. When compared to multiple channel attestation, our computational overhead is minor. Additionally, compared to single channel attestation, our performance is drastically better while having comparable linking guarantees.