If the app is structured as an interpreter running scripts, it seems easy to deliver another script. On other platforms (not sure about Android) similar tricks can be played with compiled libs.
In other words, even if you had some algorithm could somehow look at a program state and with 100% accuracy determine if that state was the start of an interpreter main loop, there would be at least one program where you couldn't be certain that you'd run your algorithm on every program state.
So the same techniques used by antiviruses, be it heuristics, signatures of known interpreters and droppers, simulated execution could be used by app stores to drastically reduce bad actors. The fundamental weakness will always be there for advanced, unique malware.
"Interestingly enough, we have also observed that most AV's also failed in detecting the dropper campaigns (sometimes for years), meaning that some awareness needs to be raised on the topic,"