All they'd have to do in order to survive a factory reset is to write to the /system partition, which contains the main OS. A factory reset only wipes /data and a few caches.

Writing to /system requires it to be mounted read/write and permissions to do so, so they'd need a root exploit in order to pull it off, but there's quite a few to choose from especially as devices age and given that they're doing this outside Play Store where Google won't pick them up.

I'm just crossing my fingers advanced users don't lose the ability to side-load apps over bad publicity like this, maybe they should make it harder to enable though.