Identifying categories and choices for software testing based on informal specifications

It would be ideal to test a program with all its possible inputs (that is, the input domain). In this way, any fault that may exist in the program would be guaranteed to be detected. In practice, however, this 'exhaustive' approach is difficult, or almost impossible, to apply because of limited testing resources. Therefore, a more feasible approach is to construct a test suite, which is a subset of the input domain, for testing. The fundamental problem of this approach is how to construct a test suite so that the comprehensiveness of the test cases, as compared to the input domain, is jeopardized as less as possible. To solve this problem, two closely related test suite generation techniques have been developed and have attracted much attention. They are the CHOiCe reLATion framEwork (abbreviated as CHOC'LATE) and the Classification-Tree Methodology (abbreviated as CTM). A main advantage of both techniques is that they can be applied to informal specifications, which are commonly used in the commercial software industry. In CHOC'LATE and CTM, an early step is to identify a set of categories and choices from the specification, through which a test suite is generated. This set of categories and choices is very important because it affects the comprehensiveness of the test suite, which in turn affects the chance of detecting software faults. We observe that neither the original developers of CHOC'LATE=CTM nor follow-up researchers have proposed a systematic method for identifying categories and choices from informal specifications. As a result, the identification process is often performed in an ad hoc, impromptu manner. Without doubt, an impromptu approach cannot assure the quality of the identified categories and choices. This thesis addresses such a problem, with a view to developing an effective methodology for identifying categories and choices from informal specifications. To provide the background motivation, we conduct two rounds of empirical studies using several commercial specifications primarily written in an informal manner. The first round of studies investigates the common mistakes made by inexperienced software testers in an impromptu identification approach. This round of studies serves three purposes: (a) to make the knowledge of common mistakes known to other testers so that they can avoid repeating the same mistakes, (b) to facilitate researchers and practitioners develop systematic identification methodologies, and (c) to provide a means of measuring the effectiveness of newly developed identification methodologies. We also present a checklist to help testers detect the common mistakes. In the second round of studies, we shift our focus to experienced testers with many years of commercial experience in software development and testing. The objectives of the studies are: (a) to investigate the differences in the types and amounts of mistakes made between inexperienced and experienced testers in an impromptu identification approach, and (b) to determine, after discussing the mistakes with the testers and providing them with a checklist as a simple guideline for detecting problematic categories and choices, the extent of mistake reduction in the next identification exercise. We also discuss which specification components are useful for category and choice identification. Thereafter, we present the most significant work of the thesis: our DividE-and-conquer methodology for identifying categorieS, choiceS, and choicE Relations for Test case generation (abbreviated as DESSERT). The methodology is particularly useful for informal specifications which are complex and contain many different types of specification components. The theoretical framework and the associated algorithms of DESSERT will be discussed in detail. We shall also describe two case studies using commercial specifications to demonstrate the effectiveness of DESSERT.