Breakthrough in Reachability Analysis of the Domain Name System
2024-12-12
Researchers have presented the first decision procedure for verifying the Domain Name System (DNS), establishing its complexity as 2ExpTime. The study formalizes DNS semantics and uses a novel abstraction based on positive prefix-testable languages, reducing the DNS verification problem to the verification problem for pushdown systems. This approach effectively models attack vectors in DNS, such as amplification attacks and rewrite blackholing, providing a new theoretical foundation for ensuring DNS security and reliability.