Abstract: Automatic composition of web services is a challenging task. Many works have considered simplified automata models that abstract away from the structure of messages exchanged by the services. For the domain of security services (such as digital signing or timestamping) we propose a novel approach to automated composition of services based on their security policies. The approach amounts to collecting the constraints on messages, parameters and control flow from the components services and the goal service requirements.??A constraint solver checks the feasability of the composition — possibly adapting the message structure while preserving the semantics — and displays the service composition as a message sequence chart. The resulting composed service can be verified automatically for ensuring that it cannot be subject to active attacks from intruders. The services that are input to our system are provided in a declarative way using a high level specification language. The approach is fully automatic and we show on a case-study how it succeeds in deriving a composed service that is currently proposed as a product by OpenTrust.