I've written a program that can effortlessly scan the entire Internet (masscan). Unfortunately, scanning the Internet is against most "Acceptable Use Policies". Therefore, if you try to run it form your home network or a hosting environment (like the Amazon cloud), they'll quickly shut you down. Where, then, can legitimate researchers run this tool?
I don't know a good answer. We work closely with a hosting provider. We give them free consulting, such as pentesting and incident analysis. We handle all the abuse complaints ourselves, responding quickly to them, and adding anybody who asks to our "exclude" list. They in turn allow us to do something that most hosting providers would not.
It's not that scanning is intrinsically bad or illegal, it's just that it's associated with hackers/scammers/spammers. If they know that you are a good guy, most hosting companies wouldn't care. Your struggle is to convince them that you are a good guy.
But frankly, being the good guy is a lot of hassle. I don't mind being called a "fucking asshole" in the abuse complaints (which happens), but I do mind the legal threats. I'm extremely open and transparent about my scans, documenting when I do them, what I'm doing, the raw results, and the source code of the tool I use. Yet, all this can become evidence in a trial in the modern climate of over-prosecution of researchers. It might be safer to take the black hat route.
The black hat route is to anonymously get some bitcoins (such as off Craig's list or at the local park of your city), then use hosting environments that accept bitcoins. You'll pay about $10 to $20 for a VPS (virtual private server), and then download and run masscan. By the time they get around to canceling your account, you can complete a single scan of a port on the Internet. Running masscan, it's about 10 hours running at 100,000 packets/second or 40-mbps. VPSs can easily go faster than that on gigabit connections, such as 400,000 packets/second.
Another black hat route is to go to the scammer-friendly ISPs, the ones who already host hackers, spammers, gambling sites, and porn sites. There are a lot of them in China, Russia, and the Caribbean.
Then there is the well-known technique of compromising desktops around the world and distributing your scan across them. Masscan hqas a lot of good features for dividing scans across machine, though if you are going this route, you should probably use nmap instead. Masscan is for one massive scan from a small number of machines, nmap is better at small scans from a massive number of machines. You'd be breaking a bunch of laws just compromising those machines in the first place, so of course I wouldn't recommend it, it's just something that others have done.
The Internet is designed to be an "end-to-end" network, where such massive scanning is as normal as spidering websites for search engines. A lot of people aren't happy about this, of course, but such scanning is intrinsic to the design of the Internet. Moreover, the more we know about the state of the Internet, the better we can secure it. It's astonishing how little people know about what's listening on the Internet. The more we do this, and publish our results, the better off the Internet will be.
If anybody has better strategies on where to scan from, please drop me a comment. I'd love to see more scanning.