TEAGER is a tool suite supporting test automation based on UML state machines, conforming to the UML semantics definition. For testing, the various sources of non-determinism in state machines pose major challenges. This article discusses those challenges and the approach for their solution taken in TEAGER. This includes probabilistic batch generation of test cases, which include expected observations, test execution and evaluation, as well as a probabilistic simulator for state machines, which is useful for model validation.