The precision and scalability of path-sensitive program analyses depend on their ability to distinguish feasible and infeasible program paths. Analyses express path feasibility as the satisfiability of conjoined branch conditions, which is then decided by cooperating decision procedures such as those in satisfiability modulo theory (SMT) solvers. Consequently, efficient underlying decision procedures are key to precise, scalable program analyses. When we investigate the branch conditions accumulated by inter-procedural path-sensitive analyses of object-oriented programs, we find that many relate to an object's dynamic type. These conditions arise from explicit type tests and the branching implicit in dynamic dispatch and type casting. These conditions share a common form that comprises a fragment of the theory of partial orders, which we refer to as type-based partial orders (TPO) . State-of-the-art SMT solvers can heuristically instantiate the quantified formulae that axiomatize partial orders, and thereby support TPO constraints. We present two custom decision procedures with significantly better performance. On benchmarks that reflect inter-procedural path-sensitive analyses applied to significant Java systems, the custom procedures run three orders of magnitude faster. The performance of the two decision procedures varies across benchmarks, which suggests that a portfolio approach may be beneficial for solving constraints generated by program analyses.

Self-adaptive software systems monitor their state and then adapt when certain conditions are met, guided by a global utility function. In prior work we developed algorithms and conducted a post-hoc analysis demonstrating the possibility of adapting to software failures by judiciously changing configurations. In this paper we present the REFRACT framework that realizes this idea in practice by building on the self-adaptive Rainbow architecture. REFRACT extends Rainbow with new components and algorithms targeting failure avoidance. We use REFRACT in a case study running four independently executing Firefox clients with 36 passing test cases and 7 seeded faults. The study show that workarounds for all but one of the seeded faults are found and the one that is not found never fails -- it is guarded from failing by a related workaround. Moreover, REFRACT finds workarounds for eight configuration-related unseeded failures from tests that were expected to pass (and did under the default configuration). Finally, the data show that when a failure and its workaround are found, configuration guards prevent the failure from appearing again. In a simulation lasting 24 hours we see over 150 guard activations and no failures with workarounds remaining beyond 16 hours.

While a large body of research is dedicated to testing for feature interactions in configurable software, there has been little work that examines what constitutes such a fault at the code level. In consequence, we do not know how prevalent real interaction faults are in practice, what a typical interaction fault looks like in code, how to seed interaction faults, or whether current interaction testing techniques are effective at finding the faults they aim to detect. We make a first step in this direction, by deriving a white box criterion for an interaction fault. Armed with this criterion, we perform an exploratory study on hundreds of faults from the field in two open source systems. We find that only three of the 28 which appear to be interaction faults are in fact due to features' interactions. We investigate the remaining 25 and find that, although they could have been detected without interaction testing, varying the system configuration amplifies the fault-finding power of a test suite, making these faults easier to expose. Thus, we characterize the benefits of interaction testing in regards to both interaction and non-interaction faults. We end with a discussion of several mutations that can be used to mimic interaction faults based on the faults we see in practice.