The best response to malware is a permissions system that isn't broken
With Android apps, permissions are take-it-or-leave-it. You do not have a say in the matter (I'm not including rooting your phone, must of the people at work wouldn't even understand that phrase never mind actually do it). Users NEED to be able to say "oi! no."
I will give you an example. Orange France has an app called "Orange et moi" that tells you promotional rubbish, but can also report on your outstanding allocations for data and free voice calls. Among other stuff. [ https://play.google.com/store/apps/details?id=com.orange.orangeetmoi ] It used to tell me there was a newer version, but I could continue using the older one. Now it refuses, saying I can either upgrade or quit.
Upgrade?
Are you sitting comfortably? Here goes with the permissions it, a carrier-provided app, wants:
Services that cost you money: directly call phone numbers; Your location: coarse (network-based) location, fine (GPS) location; Your messages: read SMS or MMS; Network communication: full Internet access; Your personal information: read contact data; Phone calls: read phone state and identity; Storage: modify/delete USB storage contents, modify/delete SD card contents; System tools: change Wi-Fi state, change network connectivity, prevent phone from sleeping; Network communication: view network state, view Wi-Fi state; System tools: automatically start at boot, measure app storage space; Default: directly install apps, modify battery statistics...
The last one, about battery statistics, says "Not for use by normal apps" in its description. Anyway, are alarm bells ringing yet? Directly install apps? Read contact data? I'm sorry, I took a look at this list and deleted the app entirely. I'll use the website from now on.
That I cannot tell this app to rein in its ambitions is a failing of Android; and an encouragement to app authors to drop in more permissions than are necessary. It is scary how much stuff wants to read your addressbook, and you only choice is to do without. There needs to be an option entitled "screw you and the horse you rode in on" so you can choose to install the app and you can tell it what it won't be doing. But since this means many would turn off internet access and location-based services (used by AdMob among others), I can't see Google doing this any time soon.