Solutions based on service-oriented architecture are gaining popularity. However a wider adoption, especially for business critical functions, is hampered by the trust deficit that exists between consumers and providers, as consumers are shielded from the service architectures and the operation of the service itself. Security certification can be used as a means to bridge this trust deficit. Common Criteria for Information Technology Evaluation (CC) is a widely recognized and used security certification scheme. However, the CC scheme was tailored to provide assurance for traditional software provisioning models and hence cannot be applied to SOA solutions as is. In this paper, we present the limitations of the CC scheme when applied in SOA, the challenges that must be overcome for its adoption and possible directions through which some of those challenges can be met. In particular, we point out that CC scheme should be extended to allow for dynamic evaluation of deployed systems (which includes the operational environment) and for handling assurance of composite services.