Many system specifications are modeled using extended finite state machines (EFSMs). Functional testing using EFSMs can be a difficult process for two reasons: path feasibility and path input data generation. In this paper we propose a search based approach to produce a feasible path in a given EFSM. Our method searches for a path that is feasible but not very easy to traverse, using a Hybrid Genetic Algorithm with a feasibility metric based on dataflow dependencies as a fitness function. The purpose of the algorithm is to find those test cases that traverse some difficult to reach transitions or combinations of transitions and those might not be covered by other testing methods, so using a set of this kind of test cases is very important in the testing process.