Cooperative awareness basic services are key components of several Connected Autonomous Vehicles (CAV) functions. We present a rigorous approach to the analysis of cooperative awareness basic services in a CAV setup. Our approach addresses a major challenge in the traditional analysis techniques of such services, namely, coming up with effective scenarios that can meaningfully cover their various behaviours, exercise the limits of these services and come up with a quantitative means for design-space exploration.Our approach integrates model-based testing and search-based testing to automatically generate scenarios and steer the scenario generation process towards generating inputs that can lead to the most severe hazards. Additionally we define other objectives that maximise the coverage of the model and the diversity of the generated test inputs. The result of applying our technique to the analysis of cooperative awareness services leads to automatically generated hazardous scenarios for parameters that abide by the ETSI ITS-G5 vehicular communications standard. We show that our technique can be used as an effective design-space exploration method and can be used to design adaptive protocols that can mitigate the hazards detected through our initial analysis. © 2020 by IEEE