Android mobile devices have reached a widespread use since the past decade, thus leading to an increase in the number and variety of applications on the market. However, from the perspective of information security, the user control of sensitive information has been shadowed by the fast development and rich variety of the applications. In the recent state of the art, users are subject to responding numerous requests for permission about using their private data to be able run an application. The awareness of the user about data protection and its relationship to permission requests is crucial for protecting the user against malicious software. Nevertheless, the slow adaptation of users to novel technologies suggests the need for developing automatic tools for detecting malicious software. In the present study, we analyze two major aspects of permission-based malware detection in Android applications: Feature selection methods and classification algorithms. Within the framework of the assumptions specified for the analysis and the data used for the analysis, our findings reveal a higher performance for the Random Forest and J48 decision tree classification algorithms for most of the selected feature selection methods.