This position paper discusses the challenges and opportunities of applying search-based techniques to a formal environment of abstract state machines defined using a language called Event-B. Event-B is based on a formal abstract machine notation that has a mature tool support and gets continuous feedback from industry. Although search-based techniques recently developed for extended finite state machines may be adapted to this context, new challenges such as implicit states, non-determinism, non-numerical data types and hierarchical models are still to be solved for test data generation for Event-B models.