Analyzing a program run can provide important insights about its correctness. Dynamic analysis of complex correctness properties, however, usually results in significant run-time overhead and, consequently, it is rarely used in practice. In this paper, we present an approach for exploiting properties of stateful program specifications to reduce the cost of their dynamic analysis. With our approach, analysis results are guaranteed to be identical to those of a traditional expensive dynamic analyses, while analysis cost is very low -- between 23% and 33% more than the un-instrumented program for the analyses we studied. We describe the principles behind our adaptive online program analysis technique, extensions to our Java run-time analysis framework that support such analyses, and report on the performance and capabilities of two different families of adaptive online program analyses.