Android rooten

Wie sieht das aus wenn ein Android Smartphone von einer bösartigen Anwendung gerootet wird?

Ich habe ein Jelly Bean 4.2.2 und es erscheinen auf einmal Erotik Icons auf dem Desktop. Außerdem bekomme ich ständig Werbung. Ich habe nun das Smartphone über das Bootmenu des Einschaltvorgangs resettet (Erase Memory). Außerdem vorher alle Sim Karten und externen SD Karten herausgenommen. Das Smartphone erscheint für die ersten Sekunden nach dem Start wie im Neuzustand. Dann jedoch tauchen die gleichen Icons erneut auf!? Ich habe weder eine Wlan Verbindung noch sonst was eingerichtet. Die bösartigen Apps müssen sich also irgendwie in dem Speicher eingenistet haben der zum Resetten für das Überschreiben benutzt wird?! Meine zweite Vermutung ist das das Bootmenu ausgetauscht wurde, das ich also nicht wirklich ein Reset durchgeführt habe. (Weil im Bootmenu chinesische Schriftzeichen in gelber Farbe sind und die anderen Menu Punkte des Bootmenus scheinbar funktionslos sind.) Kann man das Bootmenu beim rooten austauschen? Jetzt muß ich das Ding wohl selber rooten und ein freies Android OS drauf spielen.