Browsing by Author "Ma, Kin-Keung"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Directed symbolic execution
    (2011-04-07) Ma, Kin-Keung; Khoo, Yit Phang; Foster, Jeffrey S.; Hicks, Michael
    In this paper, we study the problem of automatically finding program executions that reach a particular target line. This problem arises in many debugging scenarios, e.g., a developer might learn that a failure is possible on a particular line but might not know exactly how to reproduce the failure or even whether it is reproducible. This can happen particularly often for bug reports from static analysis tools, which can produce false positives. We propose two new directed symbolic execution strategies that aim to solve this problem: shortest-distance symbolic execution (SDSE) uses a distance metric in an interprocedural control flow graph to guide symbolic execution toward a particular target; and call-chain-backward symbolic execution (CCBSE) iteratively runs forward symbolic execution, starting in the function containing the target line, and then jumping backward up the call chain until it finds a feasible path from the start of the program. We also propose Mix- CCBSE, a strategy in which CCBSE is composed with another search strategy to yield a hybrid that is more powerful than either strategy alone. We compare SDSE, CCBSE, and Mix-CCBSE with several existing strategies from the literature. We find that, while SDSE performs extremely well in many cases, it sometimes fails badly. However, by mixing CCBSE with KLEE's search strategy, we obtain a strategy that has the best overall performance across the strategies we studied.
  • Thumbnail Image
    Item
    Evaluating Interaction Patterns in Configurable Software Systems
    (2009-06-16) Reisner, Elnatan; Song, Charles; Ma, Kin-Keung; Foster, Jeffrey S.; Porter, Adam
    Many modern software systems are designed to be highly configurable, which makes testing them a challenge. One popular approach is combinatorial configuration testing, which, given an interaction strength $t$, computes a set of configurations to test such that all $t $-way combinations of option settings appear at least once. Basically, this approach assumes that interactions are complete in the sense that any combination of $t$ options can interact and therefore must be tested. We conjecture, however, that in practical systems interactions are limited. If our conjecture is true, then new techniques might be developed to identify or approximate infeasible interactions, greatly reducing the number of configurations that must be tested. We evaluated this conjecture with an initial empirical study of several configurable software systems. In this study we used symbolic evaluation to analyze how the settings of run-time configuration options affected a test suite's line coverage. Our results strongly suggest that for these subject programs, test suites and configuration options, at least at the level of line coverage, interactions between configuration options are not complete.
  • Thumbnail Image
    Item
    Using Symbolic Evaluation to Understand Behavior in Configurable Software Systems
    (2009-12-12) Reisner, Elnatan; Song, Charles; Ma, Kin-Keung; Foster, Jeffrey S.; Porter, Adam
    Many modern software systems are designed to be highly configurable, which increases flexibility but can make programs hard to test, analyze, and understand. We present an initial empirical study of how configuration options affect program behavior. We conjecture that, at certain levels of abstraction, configuration spaces are far smaller than the worst case, in which every configuration is distinct. We evaluated our conjecture by studying three configurable software systems: vsftpd, ngIRCd, and grep. We used symbolic evaluation to discover how the settings of run-time configuration options affect line, basic block, edge, and condition coverage for our subjects under a given test suite. Our results strongly suggest that for these subject programs, test suites, and configuration options, when abstracted in terms of the four coverage criteria above, configuration spaces are in fact much smaller than combinatorics would suggest and are effectively the composition of many small, self-contained groupings of options.