Resource sharing among users serves as the foundation of cloud computing, which, however, may also cause vulnerabilities to diverse co-residence attacks launched by malicious virtual machines (VM) residing in the same physical server with the victim VMs. In this paper, we aim to defend against such co-residence attacks through a secure, workload-balanced, and energy-efficient VM allocation strategy. Specifically, we model the problem as an optimization problem by quantifying and minimizing three key factors: (1) the security risks, (2) the power consumption and (3) the unbalanced workloads among different physical servers. Furthermore, this work considers a realistic environmental setting by assuming a random number of VMs from different users arriving at random timings, which requires the optimization solution to be continuously evolving. As the optimization problem is NP-hard, we propose to first cluster VMs in time windows, and further adopt the Ant Colony Optimization (ACO) algorithm to identify the optimal allocation strategy for each time window. Comprehensive experimental results based on real world cloud traces validates the effectiveness of the proposed scheme.