This paper presents a new tool for anomaly detection called Correlational Paraconsistent Machine (CPM), which is applied in mathematical treatment of uncertainties that may arise during the normal network traffic behavior modeling. The presented CPM incorporates two unsupervised models for traffic characterization, and principles on paraconsistency to evaluate the network for the presence of irregularity at traffic levels. Using flow data collected at the backbone of a real network, we present two case studies and show that our approach can accurately detect anomalies and validate the consistency of the process.