Copious mobile operating systems exist in the market, but Android remains the user's choice. Meanwhile, its growing popularity has also attracted malware developers. Researchers have proposed various static solutions for Android malware detection. However, stealthier malware evade static analysis. This raises the need for a robust Android malware detection system capable of dealing with advanced threats and overcoming the shortcomings of static analysis. Hence, this work proposes a dynamic analysis-based Android malware detection system, CorrNetDroid, that works over network traffic flows. Many traffic features exhibit overlapping ranges in normal and malware datasets. Therefore, we first rank the features using two statistical measures, crRelevance and Normalized Mean Residue Similarity (NMRS), to assess feature-class and feature-feature correlations. Thereafter, we introduce a novel correlation-based feature selection algorithm that applies NMRS on crRelevance rankings to identify the optimal feature subset for Android malware detection. Experimental results highlight that our model effectively reduces the feature set while detecting Android malware with 99.50 percent accuracy when considering only two network traffic features. Furthermore, our experiments demonstrate that the NMRS-based algorithm on crRelevance rankings outperforms statistical tests such as chi-square, ANOVA, Mann-Whitney U test, and Kruskal-Wallis test. In addition, our model surpasses various state-of-the-art Android malware detection techniques in terms of detection accuracy.