How do I remove what appears to be malware on my Nexus 5?

I have a Nexus 5 phone running Android 6.0.1 (security patch level 1 Jun 2016).

It appears that over the past few days it has become infected with malware.

Periodically (every 10-15 minutes) a transparent notification appears near the bottom of the screen that looks like this (the numbers will change, and possibly the non-English text).

Here's what I have tried so far:

• Installed Malwarebytes and ran a scan but it couldn't detect it.


• Installed a few Antivirus programs (AVG, 360 Security) and it didn't find anything out of the ordinary.


• Installed OS Monitor to see if there are any suspicious processes running or network connections open but nothing stands out.


• Closed all running apps


• Rebooted the phone

The notifications keep popping up. I'm a bit stuck here - this definitely looks like malware, but not sure where to go from here. Obviously a factory reset is an option, but I'd like to expore other options first.

Any recommendations about how to proceed?