Inference of behavioral models that support program analysis

The use of models to study the behavior of systems is common to all fields. A behavioral model formalizes and abstracts the view of a system and gives insight about the behavior of the system being developed. In the software field, behavioral models can support software engineering tasks. In particular, relevant uses of behavioral models are included in all the main analysis and testing activities: models are used in program comprehension to complement the information available in specifications, are used in testing to ease test case generation, used as oracles to verify the correctness of the executions, and are used as failure detection to automatically identify anomalous behaviors. When behavioral models are not part of specifications, automated approaches can automatically derive behavioral models from programs. The degree of completeness and soundness of the generated models depends from the kind of inferred model and the quality of the data available for the inference. When model inference techniques do not work well or the data available for the inference are poor, the many testing and analysis techniques based on these models will necessarily provide poor results. This PhD thesis concentrates on the problem of inferring Finite State Automata (the model that is likely most used to describe the behavior of software systems) that describe the behavior of programs and components and can be useful as support for testing and analysis activities. The thesis contributes to the state of the art by: (1) Empirically studying the effectiveness of techniques for the inference of FSAs when a variable amount of information (from scarce to good) is available for the inference; (2) Empirically comparing the effectiveness of techniques for the inference of FSAs and Extended FSAs; (3) Proposing a white-box technique that infers FSAs from service-based applications by starting from a complete model and then refining the model by incrementally removing inconsistencies; (4) Proposing a black-box technique that infers FSAs by starting from a partial model and then incrementally producing additional information to increase the completeness of the model.