One way to combat denial of service attacks on cloud-based virtual networks is to use unpredictable network addresses, aiming to increase attacker effort by requiring attackers to search a large IP address space to find a target host. IP address randomization is used by several moving target defenses, relying on the assumption that it is difficult for an attacker to predict newly allocated IP addresses. This work analyzes whether IP addresses used by cloud providers are unpredictable enough in practice. We analyze the IP address allocation behaviors in two major cloud computing providers (Amazon Web Services and Google Cloud Platform) and find that the actual entropy provided by allocated IP addresses is limited. We evaluate several prediction models, including a simple frequency-based model as well as a Markov process model that produces an address prediction set from time series data of collected IP addresses. Our results show that simple models can reduce the search space for allocated IP addresses and diminish the effectiveness of randomization defenses.