Hola smylow el programa que necesitas se llama AirPush Detector, va muy bien. Cuando veas publicidad o una estrellita en la barra de notificaciones, abres esa aplicación, buscará y te dirá quién es la que lo produce, después desde ahí mismo lo puedes desinstalar.
Y no necesitas ser root.