По мере усложнения малвари:
1. Вычистить руками
2. Вычистить антивирусами
3. Сбросить телефон до заводских настроек
4. Купить новый телефон
Большинство заражений - пользователь сам ставит какой-то шлак из левых источников.
Менее вероятный вариант - малварь ставится через другой, относительно легитимный (взломаный/перепроданый) софт.
Очень маловероятный способ - таргет атаки, где эксплоитом пробивается браузер/мессенджер/ос/ещё что.