[anatari]

You can build a trie of all the AWS keys and then for each Android binary, traverse each series of bytes until it either terminates at a leaf node or fails to continue. If it fails, you start over again on the next byte. Or in order words, the trie allows you to easily test if a given byte is the start of an AWS key, and so then you just check every possible offset. Believe the run time will only be O(n*k) where n is the size of the binary and k is the size of the AWS key, plus enough memory to store the trie which is probably relatively small; less than 1m AWS accounts?

[ajanuary]

Using Aho-Corasick [1] the runtime would be about O(n+k+)

[1] http://en.m.wikipedia.org/wiki/Aho–Corasick_string_matching_...