1) Put in their detailed rules that this (uploading entire address books) is not allowed.
2) Remove apps from the Apple App Store if they are found to violate this rule.
Apple could also remove such apps from phones after the fact as if they were hostile malware. This may be going too far, but it can be done: http://cybernetnews.com/apple-can-remotely-remove-bad-apps-f... I mention this since by saying "What is Apple supposed to do to prevent.." you may be asking if there's anything Apple can do at all. Yes, of course there is. It's not hard to do something when you own the app store and have control over all the devices.