A communication partner correspondence relationship collecting device includes a communication partner specifying unit that specifies a subject communication partner whose correspondence relationships are to be collected; a DNS query transmission controller that controls a DNS client such that the DNS client transmits a DNS query to the subject communication partner in a given cycle shorter than a cycle in which the IP address corresponding to the subject communication partner is changed and that collects IP addresses corresponding to the subject communication partner from responses to the DNS queries; and a correspondence relationship log information creator that creates log information from the IP addresses corresponding to the subject communication partner, which are the IP addresses collected by the DNS query transmission controller, and at least one of a set of dates and a set of times at which responses are made to the DNS queries.