Embodiments of the present invention allow for “end-user” provisioned instances to securely identify themselves beyond a simple user ID and password. Specifically, embodiments of the present invention use a multi-part security approach that includes (among other things): an identifying key (e.g., a shared private key) known by the cloud security system and the instance; and at least one additional security factor such as an identifier found in TCP/IP packets (e.g., an internet protocol address). In a typical embodiment, a request for an instance (e.g., a virtual machine) is received, and a template (e.g., an image) corresponding to the requested instance is identified. From this template, the instance is provisioned. Under the embodiments of the present invention, the instance will be provisioned to include a security key. When a request is thereafter received from the instance, the request is validated using the security key and the additional security factor(s).