We propose a novel framework to detect changes in the performance behavior of an IaaS service. The proposed framework leverages the concept of the IaaS signature to represent an IaaS service's long-term performance behavior. A new type of performance signature called categorical IaaS signature is introduced to represent the performance behavior more accurately. A novel performance noise model is proposed to accurately identify IaaS performance noise and accurate changes in the performance behavior of an IaaS service. A set of experiments based on real-world datasets is carried out to evaluate the effectiveness of the proposed framework.