Service Level Agreements (SLAs) specify the network Quality of Service (QoS) that providers are expected to deliver. Providers have to verify if the actual quality of the network traffic complies with the SLA. Ideally this should be done without introducing significant additional network load and the operational costs should be small. In this paper we propose a novel approach for the passive validation of SLAs based on direct samples of the customer traffic. The SLA contains pre-defined thresholds for QoS metrics, the maximum violation proportion and accuracy boundaries. We model the validation problem as proportion estimation of non-conformant traffic. Then we compare different sampling schemes according to their sampling errors and present a novel solution for estimating the error prior to the sampling. Finally we derive a solution for finding the optimum sample rate based on the SLA parameters.