The emergence of the cloud computing paradigm has altered the delivery models for ICT services. Unfortunately, the widespread use of the cloud has a cost, in terms of reduced transparency and control over a user's information and services. In addition, there are a number of well-understood security and privacy challenges that are specific to this environment. These drawbacks are particularly problematic to operators of critical information infrastructures that want to leverage the benefits of cloud. To improve transparency and provide assurances that measures are in place to ensure security, novel approaches to security evaluation are needed. To evaluate the security of services that are deployed in the cloud requires an evaluation of complex multi-layered systems and services, including their interdependencies. This is a challenging task that involves significant effort, in terms of both computational and human resources. With these challenges in mind, we propose a novel security assessment methodology for analysing the security of critical services that are deployed in cloud environments. Our methodology offers flexibility, in that tailored policy-driven security assessments can be defined based on a user's requirements, relevant standards, policies, and guidelines. We have implemented and evaluated a system that supports online assessments using our methodology, which acquires and processes large volumes of security-related data without affecting the performance of the services in a cloud environment.