Android devices are shipped in several flavors by more than 100 manufacturer partners, which extend the Android "vanilla" OS with new system services, and modify the existing ones. These proprietary extensions expose Android devices to reliability and security issues. In this paper, we propose a coverage-guided fuzzing platform (Chizpurfle) based on evolutionary algorithms to test proprietary Android system services. A key feature of this platform is the ability to profile coverage on the actual, unmodified Android device, by taking advantage of dynamic binary re-writing techniques. We applied this solution on three high-end commercial Android smartphones. The results confirmed that evolutionary fuzzing is able to test Android OS system services more efficiently than blind fuzzing. Furthermore, we evaluate the impact of different choices for the fitness function and selection algorithm.