[wyck]

Install a network monitor or go even deeper and sniff packets.

[greesil]

I feel like this could be automated. Spin up a virtual device on a monitored network. Install one app, click on some stuff for awhile, uninstall and move onto the next. If the app reaches out to a lot of random sites then flag it

Google could do this. I'm sure Apple could as well. Third parties could for a small set of apps

[jeroenhd]

This is being done by a couple of SDKs, it'd be much easier to just find and flag those SDK files. Finding apps becomes a matter of a single pass scan over the application contents rather than attempting to bypass the VM detection methods malware is packed full of.