Cloud computing is an essential technology for the future of the information technology industry. However, the cloud security level is identified as the biggest challenge faced by cloud providers and a major concern for cloud adopters. Economic Denial of Sustainability (EDoS) attack is one of the major threats targeting the cloud. The EDoS attack exploits the cloud elasticity and auto-scaling features to charge a cloud adopter bill an excessive amount of cost leading to large-scale service withdrawal or bankruptcy. A novel reactive approach referred to as the EDoS Attack Defense Shell (EDoS-ADS) is proposed to mitigate EDoS attacks while taking into account most of the existing mitigation techniques drawbacks. Specifically, the EDoS-ADS has the ability to identify the legitimacy of clients even if they belong to a Network Address Translation (NAT) based network. Thus, EDoS-ADS is the first known technique that effectively prevents an EDoS attack from blocking an entire NAT-based network from accessing the cloud. The experimental results show that EDoS-ADS successfully differentiates between legitimate and attacker clients even when they belong to the same NAT-based network.