We propose a novel testing approach that combines information from UML sequence models and state machine models. Current approaches that rely solely on sequence models do not consider the effects of the message path under test on the states of the participating objects. Dinh-Trong et al. proposed an approach to test input generation using information from class and sequence models.We extend their Variable Assignment Graph (VAG) based approach to include information from state machine models. The extended VAG (EVAG) produces multiple execution paths representing the effects of the messages on the states of their target objects.We performed mutation analysis on the implementation of a video store system to demonstrate that our test inputs are more effective than those that cover only sequence diagram paths.