6Graph: A graph-theoretic approach to address pattern mining for Internet-wide IPv6 scanning

IPv6 target generation is critical in fast IPv6 scanning for Internet-wide surveys and cybersecurity analysis. However, existing techniques generally suffer from low hit rates because the targets are generated from inappropriate address patterns. To address the problem, we propose 6Graph, a graph-theoretic method for IPv6 address pattern mining. It first divides the IPv6 address space into different regions according to the structural information of a set of known addresses. Then, 6Graph maps the addresses of each region into undirected graphs and conducts the density-based graph cutting for address clustering to mine IPv6 address patterns and detect the misclassified addresses iteratively. Besides, we exploit the random IPv6 target generation based on Hamming distance without additional and complicated target selection. Experiments on 11 large-scale candidate datasets show that the address patterns of 6Graph have a higher seed density than the existing methods. Further results over real-world networks indicate that 6Graph can achieve 12.6%–35.8% hit rates on the candidate datasets, which is an 8.8%–275.0% improvement over the state-of-the-art methods in Internet-wide scanning.