format and install new OS to get rid of viruses
Things you can do:


Downgrade to your stock ROM and install a good antivirus and run a complete device scan because some of them are powerful enough to remove viruses from system files in priveledged user mode.
Install Ubuntu Touch instead of android as shown in this guide. The guide is actually primarily for nexus devices but you can make it work for Galaxy S6 by finding the stock ROM yourself and other stuff for the S6 yourself instead of following the links given in the guide which are for nexus devices.
If that doesn't work and you are unable to install Ubuntu touch for some reason try this.