I had the same problem (on a Samsung Galaxy S7) and after downloading and running 4 different anti-virus apps from the Playstore and not finding anything, I realized that it must be a new "feature" of the Samsung Messenger app. It turns out it was. In your Messenger go to the "Settings" then to...