Most people who install firewalls and NAT routers do so without the intention of commiting fraud. Those who do allow their friends and neighbors to freeload would run afoul of their provider's TOS, but these bills would also make that a criminal offense.
DDoS networks, which are usually intended to hide the controller's address, would also be outlawed. And that's a good thing.
Anti-spyware and personal firewalls do not attempt to conceal or circumvent anything; they're intended to block communications which could be harmful to the user's equipment. Even a NAT router, which might "hide" the fact that you're using five computers on your broadband connection, is not concealing "the existence or place of origin or destination of any communication", as your public IP address is still on every packet you transmit. There is a method for counting the number of computers behind a NAT router, if an ISP really wants to be that petty.
But, IMHO, this would not make firewalls illegal. Everybody uses them, and I wouldn't think these states would really want to shut down the Internet by being so stupid.