One of the most severe threats to Internet security are Denial of Service attacks. Intended to annihilate the availability of a network-based service, this kind of attack troubles all service providers. In this paper we focus on a special type of Denial of Service attacks that relies on message flooding techniques, overloading the victim's service with invalid requests. We describe some well-known and some rather new attacks, discuss commonalities and approaches for countermeasures. A main focus of this paper is directed towards Denial of Service attacks on Web Services and Web Service Compositions. We resume these threats by illustrating some possible attacks, and we relate our experimental results to the well-known attack impact of the TCP SYN Flooding attack.