When checking #8219321 and #9695860 did you make new APKs that were never "in the wild" or did you rely on existing examples?
While they haven't gone into details, I've gotten the impression that their checks are primarily based on recognizing bad APKs rather than recognizing bad constructs. While that's certainly a good defense to include (for attacks that are expensive to recognize and as a general backup), it is limited because it's inherently backward-looking. I guess I'm wondering how deep their "not proactive" approach goes.
I used Impactor to perform this test. Impactor generates all of the packages it needs at runtime (it includes enough of the aapt machinery to compile its own manifest files). In order to work around some situations where packages get "wedged" on some devices, all of the packages it generates have a unique package identifier based on the current timestamp. The APK files I was installing are thereby always "never before seen" files.
(FWIW, it is my understanding that Verify Apps is part of Play Services, so updates to it can be pushed at any time to all devices: if they previously were just sending a SHA-1 of the entire APK to the server, and now needed to check if the file size divided by the current day was a mersenne prime, they could push an update to do that on the client. They thereby are not limited to only "inherently backward-looking" techniques for this protection.)
Thanks for the extra detail. It's good to see that Google is clearly doing more than just signature-style checks. I knew they could do that sort of thing in Play Services, but, based on past coverage/discussion I wasn't confident that they were.
That still leaves open the question of security issues that aren't well-known, of course. Thinking about it a bit more, I can see the attraction of not adding extra complexity to the Play Services verifier until they "had to". If they're doing server-side checks and analysis that include undisclosed/low-profile issues that could be a reasonable balance (even if there is some lag time involved for simulations and the like), but if they're not...
Sadly, we're unlikely to ever know the difference.
While they haven't gone into details, I've gotten the impression that their checks are primarily based on recognizing bad APKs rather than recognizing bad constructs. While that's certainly a good defense to include (for attacks that are expensive to recognize and as a general backup), it is limited because it's inherently backward-looking. I guess I'm wondering how deep their "not proactive" approach goes.