Modern software systems are increasingly configurable. While this has many benefits, it also makes some software engineering tasks,such as software testing, much harder. This is because, in theory,unique errors could be hiding in any configuration,and, therefore,every configuration may need to undergo expensive testing. As this is generally infeasible, developers need cost effective technique for selecting which specific configurations they will test. One popular selection approach is combinatorial interaction testing (CIT), where the developer selects a strength t and then computes a covering array (a set of configurations) in which all t-way combinations of configuration option settings appear at least once. In prior work, we demonstrated several limitations of the CIT approach. In particular, we found that a given system’s effective configuration space. It is the minimal set of configurations needed to achieve a specific goal—could comprise only a tiny subset of the system’s full configuration space. We also found that effective configuration space may not be well approximated by t-way covering arrays. Based on these insights we have developed an algorithm called Random Testing discovery (Adaptive Testing). Adaptive Testing is an iterative learning algorithm that efficiently searches for a small set of configurations that closely approximates a system’s effective configuration space. On each iteration Adaptive Testing tests the system on a small sample of carefully chosen configurations, monitors the system’s behaviors, and then applies machine learning techniques to discover which combinations of option settings are potentially responsible for any newly observed behaviors. This information is used in the next iteration to pick a new sample of configurations that are likely to reveal further new behaviors. In prior work, we presented an initial version of Adaptive Testing and performed an initial evaluation with promising results. This paper presents an improved Adaptive Testing algorithm in greater detail. The key improvements are based on our use of composite proto-interactions. It is a construct that improves Adaptive Testing’s ability to correctly learn key configuration option combinations, which in turn significantly improves Adaptive Testing’s running time, without sacrificing effectiveness. Random Testing (RT) is an important and fundamental approach to testing computer software. Adaptive Random Testing (ART) has been proposed to improve the detection capability of RT. ART employs the location information of successful test cases (those that have been executed but not revealed a failure) to enforce an even spread of random test cases across the input domain. Distance-based ART (D-ART) and Restriction-based ART (R-ART) are the first two ART methods, which have considerably improved the fault-detection capability of RT. Both these methods, however, require additional computation to ensure the generation of evenly spread test cases. To reduce the overhead in test case generation, we present in this paper a new ART method using the notion of iterative partitioning. The input domain is divided into equally sized cells by a grid. The grid cells are categorized into three different groups according to their relative locations to successful test cases. In this way, our method can easily identify those grid cells that are far apart from all successful test cases for test case generation. Our method significantly reduces the time complexity, while keeping the high detection capability.