Malware continues to be one of the major threats to Internet security. In the battle against cybercriminals, accurately identifying the underlying malicious server infrastructure (e.g., C&C servers for botnet command and control) is of vital importance. Most existing passive monitoring approaches cannot keep up with the highly dynamic, ever-evolving malware server infrastructure. As an effective complementary technique, active probing has recently attracted attention due to its high accuracy, efficiency, and scalability (even to the Internet level). In this paper, we propose Autoprobe, a novel system to automatically generate effective and efficient fingerprints of remote malicious servers. Autoprobe addresses two fundamental limitations of existing active probing approaches: it supports pull-based C&C protocols, used by the majority of malware, and it generates fingerprints even in the common case when C&C servers are not alive during fingerprint generation. Using real-world malware samples we show that Autoprobe can successfully generate accurate C&C server fingerprints through novel applications of dynamic binary analysis techniques. By conducting Internet-scale active probing, we show that Autoprobe can successfully uncover hundreds of malicious servers on the Internet, many of them unknown to existing blacklists. We believe Autoprobe is a great complement to existing defenses, and can play a unique role in the battle against cybercriminals.