Example embodiments disclosed herein relate to propagating belief information about malicious and benign nodes. In one example, a domain name system (DNS) resolution graph including multiple nodes is determined. In this example, a first subset of nodes is determined based on an initial benign value or an initial unknown value associated with the respective nodes. In the example, benign belief information is propagated for the first subset based on the respective initial benign values. Moreover, in the example, a second subset of the nodes is determined based on an initial malicious value or an initial unknown value. Malicious belief information is propagated for the second subset based on the respective malicious values. The propagated belief information is copied to a DNS resolution graph.