I recently installed a modded apk and even after uninstalling it it displays toast message (link below) each and every time I connect to the internet. I checked installed apps and system apps but there is nothing there. Installed Kaspersky and scanned nothing found. What can I do to know if the device is infected and remove it ?
First there was CarrierIQ (2011) on the HTC EVO 3D (and I think a few other less-known devices), which was a vendor faux pas. It couldn't really be uninstalled -- there had to be a ROM update.
Then came the first system-level Android malware, Droid Kungfu (2011). Kungfu would replace dhcpd and even the boot animation. It wasn't exactly an app that you could uninstall.
Obad (2013) was probably the first Android bootkit. However, it was relatively-easy to remove compared to what would come.
One of the nastiest Android bootkits was Mouabad (2014) aka Oldboot -- https://blog.lookout.com/mouabad
Oldboot was heavily-researched:
Later, in December 2014, Palo Alto Networks Unit42 released some research on an Android bootkit they found named Cool Reaper -- https://www.paloaltonetworks.com/content/dam/pan/en_US/assets/pdf/reports/Unit_42/unit42-cool-reaper.pdf -- http://contagiominidump.blogspot.com/2014/12/coolpad-android-devices-coolreaper.html
In 2015, the Cloudsota malware was found to be shipped on Android tablets sold on Amazon -- http://www.cmcm.com/blog/en/security/2015-11-09/842.html
Even recently in 2016 a Yashi smartphone was found to contain a bootkit -- http://www.tgsoft.it/english/news_archivio_eng.asp?id=693
The Adups Android bootkit was also detailed in late 2016 -- http://www.kryptowire.com/adups_security_analysis.html -- and it was sending private data to China -- https://www.schneier.com/blog/archives/2016/11/smartphone_secr.html
The company, Kryptowire, that found Adups also found some Blu Phone that contained bootkit-level malware in 2017, for phones again being sold on Amazon no-less -- https://threatpost.com/amazon-halts-sale-of-android-blu-phone-amid-spyware-concerns/127141/
This topic has also been discussed on the Android StackExchange forum here -- https://android.stackexchange.com/questions/164898/can-rooting-remove-all-malware-viruses-and-backdoors -- with some suggestions and links to more information on removing system-level rootkits, if not bootkits.