The popularity and openness of Android have made it the easy target of malware operators acting mainly through malware-spreading apps. This requires an efficient malware detection system which can be used in mass market and is capable of mitigating zero-day threats as opposed to signature-based approach which requires regular update of database. In this paper, an efficient host-server-based malicious app detection system is presented where on-device feature extraction is performed for the app to be analyzed and extracted features are sent over to remote server where machine learning is applied for malware analysis and detection. At server-end, static features such as permissions, app components, etc., have been used to train classifier using random forest algorithm resulting in detection accuracy of more than 97%.