Network traffic classification is important to many network applications. Machine learning is regarded as one of the most effective technique to classify network traffic. In this paper, we adopt the fast correlation-based filter algorithm to filter redundant attributes contained in network traffic. The attributes selected by this algorithm help to reduce the classification complexity and achieve high classification accuracy. Since the traffic attributes contain a large amount of users’ behavior information, the privacy of user may be revealed and illegally used by malicious users. So it’s demanding to classify traffic with certain segment of frames which encloses privacy-related information being protected. After classification, the results do not disclose privacy information, while may still be used for data analysis. Therefore, we propose a random perturbation algorithm based on relationship among different data attributes’ orders, which protects their privacy, thus ensures data security during classification. The experiment results demonstrate that data perturbed by our algorithm is classified with high accuracy rate and data utility.