This article examines the problem of malware in smart devices and recent progress made in detection techniques. We first present a detailed analysis on how malware has evolved over the last years for the most popular platforms. We identify exhibited behaviors, pursued goals, infection and distribution strategies, etc. and provide numerous examples through case studies of the most relevant specimens. We next survey, classify and discuss efforts made on detecting both malware and other suspicious software (grayware), concentrating on the 20 most relevant techniques proposed between 2010 and 2013. Based on the conclusions extracted from this study, we finally provide constructive discussion on open research problems and areas where we believe that more work is needed.