Divide, Predict, Conquer: Adaptive Internet-wide Service Discovery with Limited Seeds

Internet-wide service discovery forms the foundation of Internet situational awareness and security research, yet it faces the challenge of identifying services across massive open ports. Existing methods, which rely heavily on extensive prior knowledge (seeds) and suffer from low efficiency, are limited to specific scenarios with small scales and few service types.To this end, we propose SPADE, an efficient Internet-wide service prediction and discovery method with adaptive and divide-and-conquer characteristics. It acquires limited seeds from target hosts through a multi-level adaptive sampling strategy, then progressively extracts two-tier service deployment features and performs multi-layer predictions in phases. This approach significantly enhances prediction performance while substantially boosting efficiency. Across 12 comparative experiments spanning three-level prediction scenarios and four datasets, SPADE achieves over 94% in both Top-1 hit rate and coverage, significantly outperforming the state-of-the-art methods, especially in scenarios where seeds are limited or even scarce. More notably, it only requires 0.15%-1% of the seeds needed by the state-of-the-art approach to surpass its performance. Furthermore, SPADE achieves a 219-805× speedup in service discovery, completing predictions within 7 minutes across all scenarios and datasets (including hundred-million-scale target hosts), while the state-of-the-art method requires ≥ 22 hours.