Reduction of quality (RoQ) attack is an atypical denial of service (DoS) attack, which has a strong concealment. Consequently, most traditional methods of detection are no longer applicable. There are a number of new methods developed recently. However, most of these methods have higher false positive rate in varying degree. In this paper, a novel method is proposed based on the principle of time-frequency analysis with Wavelet multi-resolution and Cepstral technique. First, according to different time-domain characteristics, the potential anomaly is detected and the abrupt change point is located. Secondly, the local traffic around the abrupt change point is analyzed by cepstrum. The potential characteristics of attack periodicity is extracted. By the two-stage detection, this new method ultimately can confirm whether the network is affected by the attack. Results of simulations and real network experiments demonstrate that the presented algorithm can detect RoQ attacks accurately with very low false positive rate and false negative rate.