[pt] Atualmente, podemos observar uma clara tendência na direção de sistemas cada vez maiores e mais complexos quanto às suas partes e formas de interconexão. Num cenário como este, torna-se imperativa a preocupação com a modelagem da estrutura, organização geral e formas de interação presentes nesses sistemas, assim como com as garantias de que certos requisitos críticos sejam atendidos. O contexto de nosso trabalho engloba disciplinas de Engenharia de Software, como Arquitetura de Software e Técnicas de Modelagem, e disciplinas mais formais como Verificação de Modelos, Lógicas Modais e Álgebras de Processos. Nosso trabalho tem inspirações nestas disciplinas mas apresenta, de fato, um cunho metodológico, localizando-se nas fronteiras da ES com Métodos Formais, onde buscamos investigar e estabelecer uma forma sistemática para utilização efetiva de métodos formais logo nas etapas iniciais do desenvo lvimento. Mais especificamente, mostramos como é possível, a partir de modelos baseados em abstrações arquiteturais, obter-se sistematicamente um modelo formal sobre o qual possamos realizar certos tipos de análise comportamental. Nossa proposta inclui um sistema notacional básico para expressar modelos arquiteturais, junto com sua semântica formal, e um protótipo construído para dar suporte a tarefas de especificação e análise formal orientadas por abstrações arquiteturais. Com isto, pretendemos abordar alguns dos aspectos essenciais de uma metodologia de desenvolvimento que integre ferramentas e técnicas formais na etapa de modelagem arquitetural. / [en] There is a trend nowadays towards bigger and more complex systems concerning their parts and interconnectivity. In such scenario, modeling structure, overall organization and interaction have become a main concern, as well as fulfillment of mission critical requirements. The scope of our work encompasses Software Engineering related subjects such as Software Architecture, Modeling Techniques and more formal disciplines like Model Checking, Modal Logics and Process Algebra. Although inspired by such techniques, there is, indeed a methodological orientation in our work, traversing the boundaries of Software Engineering with Formal Methods, through which we seek to investigate and establish a systematic way for the effective utilization of formal methods in the first steps of software development. Still, more specifically, we show how it is possible, starting from models based on architectural abstractions, to systematically produce a formal model upon which we can execute certain forms of behavior analysis. Our proposal includes a basic notational system to express architectural models along with their formal semantics and a prototype built to support specification and formal analysis tasks oriented by architectural abstractions. With this, we intend to stress some essential aspects of a development methodology which aims to integrate tools and formal techniques to software modeling.

In software engineering, software reuse has been a popular topic since 1968. Nowadays, Software Product Line (SPL) engineering promotes systematic reuse throughout the whole software development process. Within SPL, reusability strongly depends on variability. In this context, variability modelling and management are crucial activities that crosscuts all development stages. Different techniques are used to model variability and one of them is Feature Diagrams (FDs). FD languages are a family of popular modelling languages used to model, and reason on, variability. Since the seminal proposal of a FD language, namely FODA, many extensions have been proposed to improve it. However, the pros and cons of these languages are difficult to evaluate for two main reasons: (1) most of them are informally defined and (2) no well defined criteria were used to justify the extensions made to FODA. As a consequence, variability modelling and management techniques proposed in the literature or used by practitioners may be suboptimal. Globally, this work underlines that the current research on FDs is fragmented and provides principles to remedy this situation. A formal approach is proposed to introduce more rigour in the motivation, definition and comparison of FD languages. Thereby, examining their qualities should be more focused and productive. A formal approach guarantees unambiguity and is a prerequisite to define formal quality criteria and to produce efficient and safe tool automation. A quality analysis is necessary to avoid the proliferation of languages and constructs that are an additional source of misinterpretations and interoperability problems. The creation or selection of a FD language should be driven and motivated by rigourous criteria. Translations from one FD language to another should be defined and carefully studied to avoid interoperability problems. The main contributions of this work are: (1) to use a quality framework to serve as a roadmap to improve the quality of FD languages, (2) to formally evaluate and compare FD language qualities according to well-defined criteria and following a clear method, (3) to formally define and motivate a new FD language that obtains the best scoring according to the quality criteria and (4) to develop tool support for this language.

Les systèmes embarqués ont évolué d'une manière spectaculaire et sont devenus partie intégrante de notre quotidien. En réponse aux exigences grandissantes en termes de nombre de fonctionnalités et donc de flexibilité, les parties logicielles de ces systèmes se sont vues attribuer une place importante malgré leur manque d'efficacité, en comparaison aux solutions matérielles. Par ailleurs, vu la prolifération des systèmes nomades et à ressources limités, tenir compte de la performance est devenu indispensable pour bien les concevoir. Dans cette thèse, nous proposons une démarche rigoureuse et intégrée pour la modélisation et l'évaluation de performance tôt dans le processus de conception. Cette méthode permet de construire des modèles, au niveau système, conformes aux spécifications fonctionnelles, et intégrant les contraintes non-fonctionnelles de l'environnement d'exécution. D'autre part, elle permet d'analyser quantitativement la performance de façon rapide et précise. Cette méthode est guidée par les modèles et se base sur le formalisme $mathcal{S}$BIP que nous proposons pour la modélisation stochastique selon une approche formelle et par composants. Pour construire des modèles conformes au niveau système, nous partons de modèles purement fonctionnels utilisés pour générer automatiquement une implémentation distribuée, étant donnée une architecture matérielle cible et un schéma de répartition. Dans le but d'obtenir une description fidèle de la performance, nous avons conçu une technique d'inférence statistique qui produit une caractérisation probabiliste. Cette dernière est utilisée pour calibrer le modèle fonctionnel de départ. Afin d'évaluer la performance de ce modèle, nous nous basons sur du model checking statistique que nous améliorons à l'aide d'une technique d'abstraction. Nous avons développé un flot de conception qui automatise la majorité des phases décrites ci-dessus. Ce flot a été appliqué à différentes études de cas, notamment à une application de reconnaissance d'image déployée sur la plateforme multi-cœurs STHORM. / In the present work, we tackle the problem of modeling and evaluating performance in the context of embedded systems design. These have become essential for modern societies and experienced important evolution. Due to the growing demand on functionality and programmability, software solutions have gained in importance, although known to be less efficient than dedicated hardware. Consequently, considering performance has become a must, especially with the generalization of resource-constrained devices. We present a rigorous and integrated approach for system-level performance modeling and analysis. The proposed method enables faithful high-level modeling, encompassing both functional and performance aspects, and allows for rapid and accurate quantitative performance evaluation. The approach is model-based and relies on the $mathcal{S}$BIP formalism for stochastic component-based modeling and formal verification. We use statistical model checking for analyzing performance requirements and introduce a stochastic abstraction technique to enhance its scalability. Faithful high-level models are built by calibrating functional models with low-level performance information using automatic code generation and statistical inference. We provide a tool-flow that automates most of the steps of the proposed approach and illustrate its use on a real-life case study for image processing. We consider the design and mapping of a parallel version of the HMAX models algorithm for object recognition on the STHORM many-cores platform. We explored timing aspects and the obtained results show not only the usability of the approach but also its pertinence for taking well-founded decisions in the context of system-level design.

Network protocol construction is a complex and error prone task. The challenges originate both from the inherent complexity of developing correct program code and from the distributed nature of networked systems. Protocol errors can have devastating consequences. Even so, methods for ensuring protocol correctness are currently only used to a limited extent. A central reason for this is that they are often complex and expensive to employ. In this thesis, we develop methods to perform network protocol testing and verification, with the goal to make the techniques more accessible and readily adoptable. We examine how to formulate correctness requirements for ad hoc routing protocols used to set up forwarding paths in wireless networks. Model checking is a way to verify such requirements automatically. We investigate scalability of finite-state model checking, in terms of network size and topological complexity, and devise a manual abstraction technique to improve scalability. A methodology combining simulations, emulations, and real world experiments is developed for analyzing the performance of wireless protocol implementations. The technique is applied in a comparison of the ad hoc routing protocols AODV, DSR, and OLSR. Discrepancies between simulations and real world behavior are identified; these are due to absence of realistic radio propagation and mobility models in simulation. The issues are mainly related to how the protocols sense their network surroundings and we identify improvements to these capabilities. Finally, we develop a methodology and a tool for automatic verification of safety properties of infinite-state network protocols, modeled as graph transformation systems extended with negative application conditions. The verification uses symbolic backward reachability analysis. By introducing abstractions in the form of summary nodes, the method is extended to protocols with recursive data structures. Our tool automatically verifies correct routing of the DYMO ad hoc routing protocol and several nontrivial heap manipulating programs.

Communicating Sequential Processes (CSP) is a formal language whose primary purpose is to model and verify concurrent systems. The CSP++ toolset was created to embody the concept of selective formalism by making machine-readable CSPm specifications both executable (through the automatic synthesis of C++ source) and extensible (by allowing the integration of C++ user-coded functions). However, these user-coded functions were limited by their inability to share data with each other, which meant that their application was constrained to solving simple problems in isolation. We extend CSP++ by providing user-coded functions in the same CSP process with safe access to a shared storage area, similar in concept and API to Pthreads' thread-local storage, enabling cooperation between them and granting them the ability to undertake more complex tasks without breaking the formalism of the underlying specification. This feature's utility is demonstrated in our line-following robot case study.

Change management is a discipline fundamental to the task of building ever more complex computing systems. Properly managed change provides a means whereby alterations to existing components of a complex artefact and their relationships can be evaluated, managed and evolved. This thesis takes as its example Official RAAF Publications, some of which need to be revised as a result of changes to the system they describe. The thesis develops a model of change propagation providing a set of operations to examine and record the changes to a set of publications. Additional operations enable coping with reversing decisions and handling the unexpected arrival of externally generated amendments. The model is extended to cover a finer granularity of entities (at the page level) to determine whether this greater level of detail would ease some tasks. A further extension provides the notion of relationships between the publications of concern, focusing on a dependency relationship between two publications. This enables exploration of the possibility of improving the process by reducing the risk of missing publications needing revision and providing a means by which some tasks can be partly automated thus speeding up the process. The models presented were developed in Sum, a variant of the Z specification language, to gain greater insight into the essential details of the operations and data structures involved. By ignoring implementation details the essential logical steps of each model can be emphasised and their differences and similarities contrasted. This thesis demonstrates that fine-grained change management is feasible. The thesis develops processes that automatically track the status of changes as they are propagated through a set of documents. The greater knowledge of work done on individual pages allows only the page(s) of concern to be affected. The work also enables recommendations to be made as to the applicability of each model and, by comparing the models, provides insight into the amount of work and resources required for tackling change at different levels of granularity.

Change management is a discipline fundamental to the task of building ever more complex computing systems. Properly managed change provides a means whereby alterations to existing components of a complex artefact and their relationships can be evaluated, managed and evolved. This thesis takes as its example Official RAAF Publications, some of which need to be revised as a result of changes to the system they describe. The thesis develops a model of change propagation providing a set of operations to examine and record the changes to a set of publications. Additional operations enable coping with reversing decisions and handling the unexpected arrival of externally generated amendments. The model is extended to cover a finer granularity of entities (at the page level) to determine whether this greater level of detail would ease some tasks. A further extension provides the notion of relationships between the publications of concern, focusing on a dependency relationship between two publications. This enables exploration of the possibility of improving the process by reducing the risk of missing publications needing revision and providing a means by which some tasks can be partly automated thus speeding up the process. The models presented were developed in Sum, a variant of the Z specification language, to gain greater insight into the essential details of the operations and data structures involved. By ignoring implementation details the essential logical steps of each model can be emphasised and their differences and similarities contrasted. This thesis demonstrates that fine-grained change management is feasible. The thesis develops processes that automatically track the status of changes as they are propagated through a set of documents. The greater knowledge of work done on individual pages allows only the page(s) of concern to be affected. The work also enables recommendations to be made as to the applicability of each model and, by comparing the models, provides insight into the amount of work and resources required for tackling change at different levels of granularity.

Change management is a discipline fundamental to the task of building ever more complex computing systems. Properly managed change provides a means whereby alterations to existing components of a complex artefact and their relationships can be evaluated, managed and evolved. This thesis takes as its example Official RAAF Publications, some of which need to be revised as a result of changes to the system they describe. The thesis develops a model of change propagation providing a set of operations to examine and record the changes to a set of publications. Additional operations enable coping with reversing decisions and handling the unexpected arrival of externally generated amendments. The model is extended to cover a finer granularity of entities (at the page level) to determine whether this greater level of detail would ease some tasks. A further extension provides the notion of relationships between the publications of concern, focusing on a dependency relationship between two publications. This enables exploration of the possibility of improving the process by reducing the risk of missing publications needing revision and providing a means by which some tasks can be partly automated thus speeding up the process. The models presented were developed in Sum, a variant of the Z specification language, to gain greater insight into the essential details of the operations and data structures involved. By ignoring implementation details the essential logical steps of each model can be emphasised and their differences and similarities contrasted. This thesis demonstrates that fine-grained change management is feasible. The thesis develops processes that automatically track the status of changes as they are propagated through a set of documents. The greater knowledge of work done on individual pages allows only the page(s) of concern to be affected. The work also enables recommendations to be made as to the applicability of each model and, by comparing the models, provides insight into the amount of work and resources required for tackling change at different levels of granularity.

Change management is a discipline fundamental to the task of building ever more complex computing systems. Properly managed change provides a means whereby alterations to existing components of a complex artefact and their relationships can be evaluated, managed and evolved. This thesis takes as its example Official RAAF Publications, some of which need to be revised as a result of changes to the system they describe. The thesis develops a model of change propagation providing a set of operations to examine and record the changes to a set of publications. Additional operations enable coping with reversing decisions and handling the unexpected arrival of externally generated amendments. The model is extended to cover a finer granularity of entities (at the page level) to determine whether this greater level of detail would ease some tasks. A further extension provides the notion of relationships between the publications of concern, focusing on a dependency relationship between two publications. This enables exploration of the possibility of improving the process by reducing the risk of missing publications needing revision and providing a means by which some tasks can be partly automated thus speeding up the process. The models presented were developed in Sum, a variant of the Z specification language, to gain greater insight into the essential details of the operations and data structures involved. By ignoring implementation details the essential logical steps of each model can be emphasised and their differences and similarities contrasted. This thesis demonstrates that fine-grained change management is feasible. The thesis develops processes that automatically track the status of changes as they are propagated through a set of documents. The greater knowledge of work done on individual pages allows only the page(s) of concern to be affected. The work also enables recommendations to be made as to the applicability of each model and, by comparing the models, provides insight into the amount of work and resources required for tackling change at different levels of granularity.

Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2007. / The ever-increasing reliance of society on computer systems has led to a need for highly reliable systems. There are a number of areas where computer systems perform critical functions and the development of such systems requires a higher level of attention than any other type of system. The appropriate approach in this situation is known as formal methods. Formal methods refer to the use of mathematical techniques for the specification, development and verification of software and hardware systems. The two main goals of this thesis are: 1. The design of mathematical models as a basis for the implementation of error-free software for the safety interlock system at iThemba LABS (http://www.tlabs.ac.za/). 2. The comparison of formal method techniques that addresses the lack of much-needed empirical studies in the field of formal methods. Mathematical models are developed using model checkers: Spin, Uppaal, Smv and a theorem prover Pvs. The criteria used for the selection of the tools was based on the popularity of the tools, support of the tools, representation of properties, representativeness of verification techniques, and ease of use. The procedure for comparing these methods is divided into two phases. Phase one involves the time logging of activities followed by a novice modeler to model check and theorem prove software systems. The results show that it takes more time to learn and use a theorem prover than a model checker. Phase two involves the performance of the tools in relation to the time taken to verify a property, memory used, number of states and transitions generated. In spite of the differences between models, the results are in favor of Smv and this maybe attributed to the nature of the safety interlock system, as it involves a lot of hard-wired lines.