Abstract: In Dynosoar project, we aim at proposing reconfiguration capabilities to Service-Oriented Architecture (SOA), targeting user-defined security policies, which can be trusted through innovative security testing methods and tools. SOA aims at decreasing the level of coupling between services and at increasing the reuse, evolution and adaptation of the system. A SOA consists of an orchestration that models the services and the control flow of events between services. A service integrator composes these different services (maybe dynamically discovered on the web) to propose a new composite service. From this perspective, SOA offers a very exciting solution for building composite distributed systems. Services are dynamic and highly reconfigurable: a service integrator can compose different services in many different ways, each service proposing different variants. It rapidly leads to the combinatorial explosion of possible composite services. Among reconfiguration criteria, one aspect is becoming crucial for trusting a configured orchestration: its capacity to embed a reconfigurable security policy. In Dynosoar, we consider security policies dedicated to SOA, which allow each user expressing how her data can be manipulated into an orchestration. The problem is thus (1) to select valid orchestrations among the huge number of possible reconfigurations and (2) to test the robustness of security mechanisms of the selected orchestrations. Dynosoar addresses two crucial dimensions: the generation of valid orchestrations, embedding a security policy, from the set of possible reconfigurations and the final security testing of orchestrations. The hard points we focus on are: 1) choosing among a possibly infinite number of services (re)configurations the smallest and more relevant subset which have to be tested. This subset of service configurations must satisfy the security policy as well as sequential execution constraints. 2) testing one specific configuration in isolation, i.e., without real external service providers. We specifically target the security policies with testing.