Various embodiments of a computer-implemented method, system and computer program product determine degradation of an application program. At least one execution state of the application program, executing in a virtual machine, is sampled. A number of occurrences of the at least one execution state are counted to provide at least one count. The at least one execution state and at least one count, respectively, are stored.