Today, the Business Process Execution Language (BPEL) is the most emerging specification for Web Service Composition, which is an important part of the SOA paradigm. Defining a stateful communication protocol, BPEL enables potential for new security vulnerabilities. In this paper, we present a severe Denial-of-Service attack on a leading BPEL engine, illustrating new threats on availability in the context of BPEL. Derived from our observations, we developed a protection concept and implemented an application level firewall fending these types of attacks.