OP7: In Search of the Elusive Performance Bug

Daniel Lupei

We propose a tool that would make use of a performance model and symbolic execution to identify execution paths and concrete inputs that would cause performance bugs. The OP question suggests considering request parameters as triggering factors for performance bugs, but equally interesting would be to look at configuration settings as possible sources of performance bugs. Perhaps the latter could define classes of requests that can be handled properly or not, i.e., due to some configuration parameter the server could be more or less suitable to handle some types of requests.

The performance model should be able to estimate the latencies incurred when executing CPU  instructions, accessing data from memory while taking into consideration the memory hierarchy and accessing data from storage. Admittedly, constructing such a performance model is not an easy task, especially when it comes to the CPU; however, we argue that an approximate model will suffice, especially since for server applications, like Apache httpd, the I/O layer is usually the bottleneck. Furthermore, since we are interested in performance bugs inside the application and not in the underlying layers we can make a simplifying assumption that our request is running in isolation with respect to computation resources, i.e., the final running time is only a function of the input, the available computation resources and contention for non-computational resources (e.g., locks) with threads handling other requests. Lock contention on the other hand could be modeled by assigning high waiting times for acquiring the lock. A more accurate representation of this scenario that considers the handling of several requests in parallel would lead to significant increases in the analysis cost. I believe that proper lock contention analysis should be done separately while modeling only synchronization primitives and high cost operations (e.g., I/O).

Our tool would start by constructing the inter-procedural control flow of the application and compute the running cost of each basic block on the basis of our performance model. Then, the symbolic execution stage could try to identify high cost execution paths by using a heuristic that would take into consideration the assigned cost of each basic block. One example of such heuristic could assign to each branch the sum of the costs of all the basic blocks on the path in the CFG from this branch to the end of the program. For loops for which we cannot statically determine a bound, we will assume a default number of iterations.

Based on the high cost paths uncovered by the analysis we would consider performance bugs those whose running time exceeds some service level agreement and then determine inputs that would drive the application's execution down the same path in order to validate the performance bug.