Cloud computing services offer elastic computing and storage to end-users over the Internet in a pay-as-you-go way. Many businesses have started using cloud computing. A Service Level Agreement (SLA) between a cloud service provider (CSP) and a user is a contract that specifies the resources and performances that the cloud should provide. However, a CSP has the incentive to cheat on SLA, e.g., providing users with less CPU and memory resources than that specified in the SLA, which allows the CSP to support more users and make more profits. Unfortunately, there are no tools to allow users to verify the SLA. We study the important issue of verifying SLA in a semi-trusted (or untrusted) cloud. In this paper, we focus on the verification of CPU speed, which is an important metric in cloud SLA. We propose a lightweight stealthy test algorithm that can check if a CSP provides the CPU speed as specified in the SLA. Using real experiments, we show that the algorithm can detect cloud cheating on CPU speed (i.e., SLA violations) in a stealthy way.