How to track down an app that shows ads on smartphone screen? I have a problem with malware apps. Looks like some app called "Native" installed itself, and created a shortcut for itself, all without my permission. After that happened, I have pop-up ads every time I unlock my screen.

I have 2 security apps: Avast and 360 security. Neither of them can find anything wrong on my phone.

Because this new app "Native" uses such a common word as its name, I cannot find anything about it on the Internet, and I don't see anything called "Native" when I browse in the "Settings"->"Applications" menus. 

So I am stuck with ads popping up every time I unlock the screen. What may be the possible solution?
Android 4 &amp; 5


When the advertisement shows up, press the app switch button to display the recents menu (if the advertisement is full-screen and cover your soft buttons, swiping down from the top of the screen will make it appear).
It will show the name of the app displaying the advertisement.
From there, long press on the app and chose &quot;app info&quot;
Uninstall the app.

Android 6
For Android 6 the process is similar, however the recents menu looks a bit different. In this step you now have to long press the app icon in the title bar:

Android 7
For Android 7 the process is similar, however the recents menu looks a bit different. In this step you now have to long press the app icon then an info icon appears in the title bar that opens the settigs dialog of the app the screen belongs to: