Web services are software components defined by WSDL, registered by UDDI and invoked by SOAP protocols. The port used by Web services and SOAP is not typically blocked by conventional firewalls. Therefore, a new type of firewall named Web service firewall or XML firewall is required. There are a number of commercial Web service firewall products. Several academic projects have also been done on Web service firewalls. This category of Web service firewalls are briefly introduced in this paper and their drawbacks are mentioned. We have proposed a Web service firewall architecture that supports authentication and authorization mechanisms. It also provides prevention of SOAP-based attacks. In this paper, we will present the proposed architectural design for a Web service firewall. A formal model for the access control of the proposed architecture using coloured Petri nets (CPNs) is also presented. The CPN model is used for the analysis of the proposed architectural design. The model can also be served as a high-level design for implementation of the Web service firewall.