Esquemas baseados em grafos, em diferentes níveis de formalismo, são um forte apelo para a constituição de representações de sistemas complexos e de grande porte aplicados em várias áreas do conhecimento. Este fato responde pelo crescimento acentuado de métodos e representações formais baseadas em grafos e aplicadas em diferentes áreas, especialmente na Engenharia. As Redes de Petri (RdP) constituem um destes métodos, que apareceu em 1962 e desde então tem contribuído para o avanço dos métodos formais para o tratamento de sistemas de controle, sistemas discretos, logística, workflow, cadeia de fornecedores, redes de computadores, e uma variada classe de outros sistemas. Da mesma forma que outras representações formais, as primeiras tentativas de uso prático destas redes estiveram sempre ligadas ao domínio de aplicação, o que levou à criação de várias extensões. Por outro lado, a necessidade de se aplicar a representação em redes para sistemas de grande porte suscitou a discussão sobre as limitações do formalismo e sobre a necessidade de se inserir redes de alto nível. No entanto, todo este desenvolvimento, apesar de sua difusão em diferentes domínios, levantou a discussão sobre a unificação das redes. Desde 1992 a unificação do formalismo das RdPs é discutida pela comunidade acadêmica e, finalmente, no início deste século um padrão ISO/IEC foi proposto. Esta proposta conduz a dois desafios: i) mostrar que um formalismo de redes que seja candidato a ser usado na prática pertença de fato à classe de redes prescrita pelo padrão; ii) participar da discussão sobre a semântica das extensões propondo ambientes computacionais para o uso prático na modelagem e design de sistemas de grande porte. A rede GHENeSys, concebida e desenvolvida no Design Lab da Universidade de São Paulo, é uma rede estendida com conceitos de orientação a objetos, um mecanismo de hierarquia e, até o momento, parece ser uma das primeiras tentativas de prover um ambiente de modelagem e design com as propriedades de uma rede unificada, com capacidade para cobrir as diferentes variantes das RdP e suas extensões. Neste trabalho é apresentada uma proposta de ambiente integrado de modelagem para a representação de sistemas a eventos discretos (SEDs) em RdP, baseada em um formalismo enquadrado dentro da norma ISO/IEC 15909 recentemente proposta. Este formalismo é a rede GHENeSys, que terá sua definição estendida utilizando como base a definição das RdPs Coloridas (CPN) com o objetivo de permitir a representação de tipos nas marcas. Um protótipo para testes, resultado da integração de diversos trabalhos desenvolvidos separadamente por membros do D-Lab que nunca foram implementados nem integrados em formalismo único, é apresentado. Este protótipo é utilizado em um estudo de caso com a finalidade de validar de forma prática os novos elementos acrescentados à definição da rede GHENeSys para permitir a modelagem de sistemas utilizando os elementos das RdPs de alto nível. / Graph schemas are a strong approach to the representation (in dierent degrees of formality) of large and complex systems in several areas of knowledge. This fact has provided a continuous growth of methods and new formal schemas, specially in Engineering. Petri Nets(PN) are one of these methods, which appears in 1962 and since then has improved the representation of discrete control, discrete systems, logistics, workflow, supply chain, computer networks, and a variety of other systems. As any other representation, the first attempts to use it in practice were always made in a close relation between the representation and the domain of discourse, openning opportunity for several extensions. Also the need to use it in large systems brought a discussion about the formalism and the need for high level systems. However, all this development, besides the broad use in different domains, rose the need for an unified approach. Since 1992 such unification has been addressed by the scientific community and finally, in the beginning of this century, a ISO/IEC standard was proposed. That proposal also brings two new challenges: i) to show that any proposed net that belongs to Petri Net class proved itself as satisfying the requirements of the standard; ii) to enter the discussions of the semantics of extensions and also provide practical and unified system environments that can really support the design of large and complex systems. In this work, we present a proposal for the developing of an integrated modeling environment for the representation of discrete event systems using Petri Nets. This environment will use an underlying formalism framed within the rules defined recently by the ISO/IEC, in the standard 15909. The formalism to be used will be the GHENeSys net, which will have its definition extended using the definition of the Coloured PN (CPN) as a starting point in order to allow the representation of types within the net tokens. A testing prototype for this integrated modeling environment, result of the integration of several previous works of D-Lab members that were never implemented or integrated in a unique formalism, is presented. This prototype will be used in a case study in order to validate in practical way the new elements added to the definition of GHENeSys, to allow the modeling of systems using the elements of HLPNs.

In the context of Service-Oriented Systems (SOS), services represent loosely coupled discrete units that can be created, invoked, composed and decomposed upon a client request. In such a setting, where complex systems are composed out of services based on the client request, ensuring the expected level of Quality-of-Service (QoS) becomes a difficult task. In systems built on service-oriented principles, the formal specification of both functional and extra-functional system behavior, service availability, compatibility and interoperability between different services and systems have become important issues. To be compliant with the new features, the REMES language has been extended towards SOS with new constructs that have been given formal semantics. In this thesis, we propose transformation rules, definitions and techniques for transforming these new constructs into Timed Automata (TA) counterparts to facilitate the formal analysis. Also, we present an extension to an existing REMES SOS IDE toolset for performing an automated transformation of the REMES SOS models into the TA framework suitable for the formal analysis with the UPPAAL model-checker. The contribution from our work is on two fronts: a) define transformation rules for all of the constructs specific for the REMES SOS modeling and b) prototype implementation of the transformation rules as an extension add-on to the already existing IDE for modeling SOS to perform the automated transformation. The benefit of performing an automated transformation of the REMES SOS models in TA is twofold. First, by automating the transformation process, the process of validation of the models becomes faster. Second, we considerably reduce the influence from the human factor in the entire process, and at the same time lower the risks of introducing errors into the systems in the phase of creating the formal model. Additional benefit from the automated process is that the SOS designer does not have to be a verification expert in order to be able to verify the modeled system.

Enterprise SIM profile provisioning solution is currently in development by some big players in the telecommunication industry. This solution may support an enterprise user staying anonymous to mobile network operators when remotely subscribing to SIM profiles. Another advantage refers to providing a seamless solution to enterprises where they can handle subscriptions of their employees. However, the solution is still in an early stage of production, and it is of utmost importance to proactively detect threats and deviant behaviors. The focus of this master thesis is providing a part towards achieving a secure solution by gaining insight and understanding of the system behavior. Colored Petri Nets technique is applied to the process and provides deterministic insights on system behavior. The solution of enterprise remote SIM profile provisioning is analyzed from different reachability goals by performing multiple simulations of different cases. Simulations are performed using different conditions and provide an understanding of system behavior with not fulfilled conditions. Essential aspects of this work can be in consideration when developing the solution to not end up in a state where a user receives a bad SIM profile or exposes the system to other threats.

The run-time reconfiguration of Field Programmable Gate Arrays (FPGAs) opens new avenues to hardware reuse. Through the use of process migration between hardware and software, an FPGA provides a parallel execution cache. Busy processes can be migrated into hardware-based, parallel processors, and idle processes can be migrated out increasing the utilization of the hardware. The application of hardware/software process migration to the acceleration of Register Transfer Level (RTL) circuit simulation is developed and analyzed. RTL code can exhibit a form of locality of reference such that executing processes tend to be executed again. This property is termed executive temporal locality, and it can be exploited by migration systems to accelerate RTL simulation. In this dissertation, process migration is first formally modeled using Finite State Machines (FSMs). Upon FSMs are built programs, processes, migration realms, and the migration of process state within a realm. From this model, a taxonomy of migration realms is developed. Second, process migration is applied to the RTL simulation of digital circuits. The canonical form of an RTL process is defined, and transformations of HDL code are justified and demonstrated. These transformations allow a simulator to identify basic active units within the simulation and combine them to balance the load across a set of processors. Through the use of input monitors, executive locality of reference is identified and demonstrated on a set of six RTL designs. Finally, the implementation of a migration system is described which utilizes Virtual Machines (VMs) and Real Machines (RMs) in existing FPGAs. Empirical and algorithmic models are developed from the data collected from the implementation to evaluate the effect of optimizations and migration algorithms. / Ph. D.

Discrete Event Logistics Systems (DELS) are a class of dynamic systems that are defined by the transformation of discrete flows through a network of interconnected subsystems. The DELS domain includes systems such as supply chains, manufacturing systems, transportation networks, warehouses, and health care delivery systems. Advancements in computer integrated manufacturing and intelligent devices have spurred a revolution in manufacturing. These smart manufacturing systems utilize technical interoperability and plant-wide integration at the device-level to drive production agility and efficiency. Extending these successes to enterprise-wide integration and decision-making will require the definitions of control and device to be extended and supported at the operations management and the business planning levels as well. In the future, smart operational control mechanisms must not only integrate real-time data from system operations, but also formulate and solve a wide variety of optimization analyses quickly and efficiently and then translate the results into executable commands. However in contemporary DELS practice, these optimization analyses, and analyses in general, are often purpose-built to answer specific questions, with an implicit system model and many possible analysis implementations depending on the question, the instance data, and the solver. Also because of the semantic gap between operations research analysis models such as job-shop scheduling algorithms and IT-based models such as MES, there is little integration between control analysis methods and control execution tools. Automated and cost-effective access to multiple analyses from a single conceptual model of the target system would broaden the usage and implementation of analysis-based decision support and system optimization. The fundamental contribution of this dissertation is concerned with interoperability and bridging the gap between operations research analysis models and practical applications of the results. This dissertation closes this gap by constructing a standard domain-specific language, standard problem definitions, and a standard analysis methodology to answer the control questions and execute the prescribed control actions. The domain specific language meets a broader requirement for facilitating interoperability for DELS, including system integration, plug-and-play analysis methods and tools, and system design methodologies. The domain-specific language formalizes a recurring product, process, resource, and facility description of the DELS domain. It provides a common language to discuss our systems, including the questions that we want to ask about our systems, the problems that we need to solve in order to answer those questions, and the mechanisms to deploy the solution. A canonical set of control questions defines the comprehensive functional specification of all the decision-making mechanisms that a controller needs to be able to provide; i.e. a model of analysis models or a metamodel of operational control. These questions refine the interoperability mechanism between system and analysis models by mapping classes of control analysis models to implementation and execution mechanisms in the system model. A standard representation of each class of control problems is only a partial solution to fully addressing operational control. The final contribution of this dissertation constructs a round-trip analysis methodology that completes the bridge between operations research analysis models and deployable control mechanisms. This contribution formalizes an analysis pathway, from formulating an analysis model to executing a control action, that is grounded in a more fundamental insight into how analysis methods are executed to support operational control decision-making.

Cette thèse traite de la vérification formelle de systèmes critiques où la correction du système dépend du respect des contraintes temporelles. La première partie étudie la modélisation et la vérification formelle par model-checking de systèmes temps réel dans le contexte de l’industrie aéronautique et spatiale. La deuxième partie décrit notre méthode d’exploitation des symétries pour les réseaux de Petri temporels. Nous définissons un opérateur de composition symétrique pour la construction de réseaux. Puis nous proposons des solutions pour la construction d’espaces d’états quotients par la relation d’équivalence induite par les symétries. Notre méthode s’applique aux réseaux de Petri, temporels ou non. A notre connaissance il s’agit de la première méthode applicable aux réseaux de Petri temporels. Des résultats expérimentaux encourageants sont présentés. / This thesis deals with formal verification of critical systems where the system’s correction depends on compliance with time constraints. The first part studies the formal modeling and verification by model-checking of realtime systems in the context of the aerospace industry. The second part describes our method for symmetry reduction of Time Petri Net. We define a symmetric composition operator for building Net. Then we present our solution for construction of quotients of the state spaces by the equivalence relation induced by symmetries. Our method applies to Petri nets, temporal or not, but to our knowledge this is the first methodology for Time Petri Nets. Encouraging experimental results are presented.

Service-oriented systems (SOS) have recently emerged as context-independent component-based systems. In contrast to components, services can be created, invoked, composed and destroyed at run-time. Services are assumed to be platform independent and available for use within heterogeneous applications. One of the main assets in SOS is service composability. It allows the development of composite services with the main goal of reusable functionality provided by existing services in a low cost and rapid development process at run-time. However, in such distributed systems it becomes difficult to guarantee the quality of services (QoS), both in isolation, as well as of the newly created service compositions. Means of checking correctness of service composition can enable optimization w.r.t. the function and resource-usage of composed services, as well as provide a higher degree of QoS assurance of a service composition. To accomplish such goals, we employ model-checking technique for both single and composed services. The verification eventually provides necessaryinformation about QoS, already at early development stage.This thesis presents the research that we have been carrying out, on developing of methods and tools for specification, modeling, and formal analysis of services and service compositions in SOS. In this work, we first show how to formally check QoS in terms of performance and reliability for formallyspecified component-based systems (CBS). Next, we outline the commonalities and differences between SOS and CBS. Third, we develop constructs for the formal description of services using the resource-aware timed behavioral language called REMES, including development of language to support service compositions. At last, we show how to check service and service composition(functional, timing and resource-wise) correctness by employing the strongest post condition semantics. For less complex services and service compositions we choose to prove correctness using Hoare triples and the guarded command language. In case of complex services described as priced timed automata(PTA), we prove correctness via algorithmic computation of strongest post-condition of PTA. / Q-ImPreSS

Embedded systems are microprocessor-based systems that cover a large range of computer systems from ultra small computer-based devices to large systems monitoring and controlling complex processes. The particular constraints that must be met by embedded systems, such as timeliness, resource-use efficiency, short time-to-market and low cost, coupled with the increasing complexity of embedded system software, demand technologies and processes that will tackle these issues. An attractive approach to manage the software complexity, increase productivity, reduce time to market and decrease development costs, lies in the adoption of the component based software engineering (CBSE) paradigm. The specific characteristics of embedded systems lead to important design issues that need to be addressed by a component model. Consequently, a component model for development of embedded systems needs to systematically address extra-functional system properties. The component model should support predictable system development and as such guarantee absence or presence of certain properties. Formal methods can be a suitable solution to guarantee the correctness and reliability of software systems.   Following the CBSE spirit, in this thesis we introduce the ProCom component model for development of distributed embedded systems. ProCom is structured in two layers, in order to support both a high-level view of loosely coupled subsystems encapsulating complex functionality, and a low-level view of control loops with restricted functionality. These layers differ from each other in terms of execution model, communication style, synchronization etc., but also in kind of analysis which are suitable. To describe the internal behavior of a component, in a structured way, in this thesis we propose REsource Model for Embedded Systems (REMES) that describes both functional and extra-functional behavior of interacting embedded components. We also formalize the resource-wise properties of interest and show how to analyze such behavioral models against them. / PROGRESS

This dissertation develops a new model transformation approach that supports engineering model integration, which is essential to support contemporary interdisciplinary system design processes. We extend traditional model transformation, which has been primarily used for software engineering, to enable model-based systems engineering (MBSE) so that the model transformation can handle more general engineering models. We identify two issues that arise when applying the traditional model transformation to general engineering modeling domains. The first is instance data integration: the traditional model transformation theory does not deal with instance data, which is essential for executing engineering models in engineering tools. The second is syntactical inconsistency: various engineering tools represent engineering models in a proprietary syntax. However, the traditional model transformation cannot handle this syntactic diversity. In order to address these two issues, we propose a new multi-layer syntactical model transformation approach. For the instance integration issue, this approach generates model transformation rules for instance data from the result of a model transformation that is developed for user model integration, which is the normal purpose of traditional model transformation. For the syntactical inconsistency issue, we introduce the concept of the complete meta-model for defining how to represent a model syntactically as well as semantically. Our approach addresses the syntactical inconsistency issue by generating necessary complete meta-models using a special type of model transformation.

This dissertation supports human decision-making with a Model-Based Systems Engineering methodology enabling engineering analysis, and in particular Operations Research analysis of discrete-event logistics systems, to be more widely used in a cost-effective and correct manner. A methodology is a collection of related processes, methods, and tools, and the process of interest is posing a question about a system model and then identifying and building answering analysis models. Methods and tools are the novelty of this dissertation, which when applied to the process will enable the dissertation's goal. One method which directly enables the goal is adding automation to analysis model-building. Another method is abstraction, to make explicit a frequently-used bridge to analysis and also expose analysis model-building repetition to justify automation. A third method is formalization, to capture knowledge for reuse and also enable automation without human interpreters. The methodology, which is itself a contribution, also includes two supporting tool contributions. A tool to support the abstraction method is a definition of a token-flow network, an abstract concept which generalizes many aspects of discrete-event logistics systems and underlies many analyses of them. Another tool to support the formalization method is a definition of a well-formed question, the result of an initial study of semantics, categories, and patterns in questions about models which induce engineering analysis. This is more general than queries about models in any specific modeling language, and also more general than queries answerable by navigating through a model and retrieving recorded information. A final contribution follows from investigating tools for the automation method. Analysis model-building is a model-to-model transformation, and languages and tools for model-to-model transformation already exist in Model-Driven Architecture of software. The contribution considers if and how these tools can be re-purposed by contrasting software object-oriented code generation and engineering analysis model-building. It is argued that both use cases share a common transformation paradigm but executed at different relative levels of abstraction, and the argument is supported by showing how several Operations Research analyses can be defined in an object-oriented way across multiple layered instance-of abstraction levels. Enabling Operations Research analysis of discrete-event logistics systems to be more widely used in a cost-effective and correct manner requires considering fundamental questions about what knowledge is required to answer a question about a system, how to formally capture that knowledge, and what that capture enables. Developments here are promising, but provide only limited answers and leave much room for future work.