Program Analyses for Understanding the Behavior and Performance of Traditional and Mobile Object-Oriented Software.

摘要

The computing industry has experienced fast and sustained growth in the complexity of software functionality, structure, and behavior. Increased complexity has led to new challenges in program analyses to understand software behavior, and in particular to uncover performance inefficiencies. Performance inefficiencies can have significant impact on software quality. When an application spends a substantial amount of time performing redundant work, software performance and user experience can deteriorate. Some inefficiencies can use up certain types of resources and lead to program crashes. In general, performance inefficiency is an important and challenging problem for modern software systems. It is also a shared problem for traditional and mobile object-oriented software. Static and dynamic analyses need to keep up with this trend, and this often requires novel technical approaches.;One important symptom of performance inefficiencies is run-time bloat: excessive memory usage and work to accomplish simple tasks. Bloat significantly affects scalability and performance, and exposing it requires good diagnostic tools. As the first contribution of this dissertation, we present a novel analysis that profiles the run-time execution to help programmers uncover potential performance problems.;Memory leaks, both for traditional and for mobile object-oriented software, present a significant problem for software quality. Static memory leak detection is challenging because it is extremely difficult to statically compute precise object liveness for large- scale applications. We bypass this difficulty by leveraging a common leak pattern.;In addition to static analysis, performance testing is an effective approach to discover memory leaks. For example, sustained growth in memory usage during test execution can indicate potential memory leaks. However, performance testing to ex- pose leaks for arbitrary software is very difficult, because, similar to other dynamic approaches, it also requires specific leak-triggering program inputs. As the third contribution of this dissertation, we introduce LeakDroid, a novel and comprehensive approach for systematic testing of resource leaks in Android applications. At the core of the proposed testing approach is model-based test generation that focuses specifically on coverage criteria aimed at resource leak defects. These criteria are based on the novel notion of neutral cycles: sequences of GUI events that should have a "neutral effect" and should not lead to increases in resource usage. Several important categories of neutral cycles are considered in the proposed test coverage criteria. As demonstrated by experimental evaluation and case studies on eight Android applications, the proposed approach is very effective in exposing resource leaks.;Model-based test generation such as LeakDroid depends critically on GUI models, which describe accessible GUI objects and corresponding user actions. GUI models ultimately determine the possible flow of control and data in GUI-driven applications. The ability to understand Android GUIs is critical for the reasoning of the semantics of an Android application.;GUI applications are usually organized as a series of GUI windows containing structures of GUI widgets. User interaction with these windows (e.g., navigating from one to another and then going back) drives the control flow of the application. In Android, an activity plays the role of a GUI window, and transitions between activities are managed with the help of an activity stack. To understand this additional aspect of Android semantics, we introduce the first static analysis to model the Android activity stack, the changes in this stack, and the related interactions between activities. The analysis is an important step toward fully modeling the control/data flow of an Android application. It can be leveraged by other researchers to prune infeasible control flow paths in static analysis for Android, or to discover more paths that would be missing without modeling of the activity stack.;In conclusion, this dissertation presents several dynamic and static program analysis techniques to understand the behavior of object-oriented software systems, to uncover potential performance inefficiencies in them, and to locate the root causes of these problems. The programs studied by these techniques are all written in Java, but we believe the proposed techniques are general enough to also be applied to systems written in other object-oriented languages. With these techniques, we advocate the insight that a carefully-selected subset of high-level behavioral patterns and pro- gram semantics must be leveraged in order to perform practical program analyses for modern software. (Abstract shortened by UMI.).