Una vez me pasó esto.
Cuando rooteaste tu teléfono, de alguna manera te infectaste con malware. En mi caso creo que fue la aplicación que utilicé para rootear mi teléfono la que infectó mi dispositivo (luego parcheó el acceso al root y dijo que el proceso había fallado). Lo que hace este malware es servirte anuncios y autodescargar aplicaciones cada pocas horas. Se replica a sí mismo y se esconde en múltiples ubicaciones de manera que si encuentras alguno de sus archivos e intentas eliminarlo, simplemente se repara. De todas formas, vamos a la solución.
Vas a necesitar unas cuantas cosas. Si tienes una tarjeta de memoria en tu teléfono, asume que está infectada. Tendrás que borrarla por completo. O, para estar seguro, consigue otra tarjeta de memoria que no haya tocado tu teléfono. A continuación, comprueba en Internet si puedes conseguir el firmware de fábrica de tu teléfono. Descarga esto y colócalo en tu tarjeta de memoria limpia.
Ahora coge tu teléfono y arranca en el recovery (tiene que ser un recovery personalizado como TWRP ya que tienen amplias opciones que el stock no ofrece), navega a la sección donde puedes borrar tus datos y marca cada casilla. Luego deja que borre tu teléfono. Existe la posibilidad de que tu teléfono se bloquee, pero esto no importa ya que vamos a flashear la ROM original. Apague su teléfono y luego inserte su tarjeta de memoria. Entra de nuevo en el recovery y flashea la ROM original. Sin embargo, ten en cuenta que este paso difiere según el fabricante del dispositivo. Si tienes un Samsung debes usar Odin, de lo contrario busca el proceso para tu teléfono en particular. Sólo después de hacer esto fui capaz de arreglar mi teléfono. Pero lo vendí unas semanas después, así que no puedo confirmar si estaba completamente limpio. Sin embargo, estoy seguro de que funcionará.
No te molestes en hacer una copia de seguridad de los datos antes o durante este proceso o tu teléfono se infectará de nuevo (lo aprendí por las malas). Incluso algo que puede parecer trivial como los archivos de música o de imagen podría estar infectado. Buena suerte