The secret document leakage incidents have raised awareness for the need to better security mechanisms. A leading cause of the incidents has been due to accidental disclosure through via removable storage devices. As a remedy to the issue, many organizations have been employing private cloud platform or virtual desktop infrastructure (VDI) to prevent the leakage of the secret documents. In spite of the various security benefits of cloud-based infrastructure, there are still challenges to prevent the secret document leakage incidents. In this paper, we present a novel scheme, called Doc-Trace, to provide an end-to-end traceability for the secret documents by inserting steganographic pattern into unused regions of the secret documents on private cloud and VDI platforms. We devise a computationally efficient storage scanning mechanism for providing end-to-end traceability for the storage scanning can be performed in an event-driven manner since a steganographic mark are encoded into a well-regulated offset address of the storage, which decrease the computation overhead drastically. To evaluate the feasibility of the proposed scheme, this work has been undertaken on a real cloud platform based on OpenStack.