Exploiting Program and Property Structure for Efficient Runtime Monitoring

Modern software systems are complex and often built using components that are provided with their application programming interface (API) to assist a user. However, this API is informal and if used incorrectly, may lead to bugs that are hard to detect. In order to address the problem of API conformance checking, researchers have proposed various analysis techniques including static and dynamic typestate analysis. However, it is extremely challenging to develop a static analysis that is both precise and scalable. On the other hand, dynamic analysis or runtime monitoring of programs may incur heavy overhead, thereby limiting its application only to a subset of realistic programs. This heavy overhead could be a result of handling of the monitors that are created during runtime, or the events generated by program instrumentation, or some other factors related to program and property interaction. Our research focuses on developing techniques that optimize program instrumentation to reduce the monitoring overhead without compromising error reporting. The techniques are guided by the cost models that we have developed for runtime monitoring and based on a hybrid approach that combines static with dynamic typestate analysis to exploit the benefits of both approaches. In addition, the approach also leverages the property structure to make monitor optimization more effective. In this dissertation, we present cost models for runtime monitoring that are based on our understanding of the existing monitoring tools. The cost models describe key factors that influence the monitoring overhead as well as the relationship among them. We develop two novel analysis techniques, namely the residual analysis and the stutter-equivalent loop transformation, that target the number of events as that is a primary factor associated with the total cost of monitoring. We present the results of their evaluation based on some open source applications and benchmarks that show that the techniques can effectively reduce the monitoring overhead. Adviser: Matthew B. Dwye