Component-based software engineering is supported by performance prediction approaches on the design level ensuring desired properties of systems throughout their entire lifecycle. The achievable prediction quality is a direct result of the quality of the used performance models, which is usually assured by validation. Existing approaches often rely solely on the expertise of performance engineers to determine if sufficient testing has occurred. There is a lack of quantitative criteria capturing which aspects of a model have been assessed and covered successfully. In this paper, we define path coverage criteria for Palladio performance models and show how the required testing effort can be estimated for arbitrary Palladio models. We demonstrate the applicability of effort estimation for each coverage criterion, provide estimates for a complex model from the Common Component Modelling Example, and show how these estimates can guide criteria selection.