Numerous auto-scaling strategies have been proposed in the past few years for improving various Quality of Service (QoS) indicators of cloud applications, for example, response time and throughput, by adapting the amount of resources assigned to the application to meet the workload demand. However, the evaluation of a proposed auto-scaler is usually achieved through experiments under specific conditions and seldom includes extensive testing to account for uncertainties in the workloads and unexpected behaviors of the system. These tests by no means can provide guarantees about the behavior of the system in general conditions. In this article, we present a Performance Evaluation framework for Auto-Scaling (PEAS) strategies in the presence of uncertainties. The evaluation is formulated as a chance constrained optimization problem, which is solved using scenario theory. The adoption of such a technique allows one to give probabilistic guarantees of the obtainable performance. Six different auto-scaling strategies have been selected from the literature for extensive test evaluation and compared using the proposed framework. We build a discrete event simulator and parameterize it based on real experiments. Using the simulator, each auto-scalers performance is evaluated using 796 distinct real workload traces from projects hosted on the Wikimedia foundations servers, and their performance is compared using PEAS. The evaluation is carried out using different performance metrics, highlighting the flexibility of the framework, while providing probabilistic bounds on the evaluation and the performance of the algorithms. Our results highlight the problem of generalizing the conclusions of the original published studies and show that based on the evaluation criteria, a controller can be shown to be better than other controllers.