Over the last decade, several value-added services have been proposed for deployment in the Internet. Many of these services (e.g. IP Multicast) are stateful services introducing state maintenance overhead into the network for their operation. This characteristic makes these ser- vices vulnerable to a specific type of denial-of-service (DoS) attacks called state overload attack. In this paper, we examine state overload attacks in value-added services and in particular IP multicast. We describe why these attacks are possible and present two solutions to prevent them. In both cases, we describe the solutions, evaluate their overhead, and outline incremental deployment strategies for their deployment.