The increasing use of the Web as the platform for delivering business processes arises the need to protect both sensitive data exchanged over the Internet and the applications using these data. In this context, authentication, integrity and confidentiality of exchanged messages are requested during interactions between processes, and are commonly called WS* specifications. In this paper, we propose a formal specification of the above security requirements and the corresponding assertions in the exchanged messages, built on the XSB logic programming language. Our framework analyzes the generated models and verifies that incoming messages fulfill the security requirements of a Web service. Furthermore, it verifies the compatibility between two policies, which is a significant condition in order to guarantee secure end-to-end SOAP invocations, and it is not currently supported by WS* specifications.