Systems, methods, and interfaces for the management of virtual machine instances and other programmatically controlled networks are provided. The hosted virtual networks are configured in a manner such that a virtual machine manager of the virtual network may monitor activity such as user requests, network traffic, and the status and execution of various virtual machine instances to determine possible security assessments. Aspects of the virtual network may be assessed for vulnerabilities at varying levels of granularity and sophistication when a suspicious event or triggering activity is detected. Illustrative embodiments of the systems and methods may be implemented on a virtual network overlaid on one or more intermediate physical networks that are used as a substrate network.