Muhammad Naeem Irfan - Analysis and Optimization of Software Model Inference Algorithms

Despite the apparent advantage, software models are often neglected during the development phase and mostly very partial specifications of software systems are available. Maintaining formal models is time consuming and expensive. Even if one tries to maintain software models, implementations evolve rapidly with the passage of time thus invalidating such models. The software models steer the testing of software systems. The model inference technique extracts structural and design information of a software system and presents it as a formal model. The learned abstract software model is consistent with the behavior of the particular software system. However, the learned models are rarely complete and it is difficult to calculate the number of tests required to learn precise and complete model of a software system.

The thesis provides analysis and improvements on the Mealy adaptation of the model inference algorithm L* [Angluin 87]. We target to reduce the number of tests required to learn Mealy models of software systems. The algorithm requires learning models by asking two types of tests. First type of tests are asked to construct models, whereas the second type of tests are asked to test the correctness of these models. The proposed techniques reduce the number of tests required to learn software models.