Source code analysis techniques used for automated software testing are insufficient to find security flaws in programs. Therefore, security researchers have been employing also fuzzing techniques for finding bugs and vulnerabilities in target programs. With the proliferation of mobile devices, researchers have started to explore the use of fuzz tests on mobile platforms. While most of these studies are GUI-based and implemented at the application level, the detection of vulnerabilities in lower levels is very critical due to affecting a broader range of Android users. Therefore, in this study, a new approach is proposed to fuzz testing for Android application installation process. The use of a search heuristic namely genetic algorithms is investigated for efficient fuzz testing on DEX (Dalvik EXecutable) files. The proposed black box fuzzing tool called GFuzz is shown to be able to produce more unique crashes in Android in a shorter time than recently proposed similar approaches and to detect new and existing bugs.