Made available in DSpace on 2014-06-12T15:51:19Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Message Sequence Charts (MSC) é uma linguagem gráfica, usada na academia e na indústria, cujo objetivo é descrever o comportamento de componentes de sistemas e seus ambientes. A sintaxe e a semântica de um diagrama MSC padrão são definidos pelo International Telecommunication Union. A motivação para esse trabalho foi originada a partir de esforços para modelar cenários de aplicações de aparelhos móveis com o objetivo de automatizar a geração de testes, no contexto de uma colaboração entre Centro de Informática da Universidade Federal de Pernambuco (CIn- UFPE) e a Motorola, no contexto do projeto Brasil Test Center (BTC). Ao modelar algumas destas aplicações que envolvem múltipla sincronização utilizando como linguagem de modelagem, MSC padrão, constatou-se que os diagramas são de difícil entendimento ou com um comportamento diferente do desejado. É proposta neste trabalho uma extensão de MSC com o objetivo de permitir a descrição de mensagens síncronas, que permitem descrever eventos instantâneos (abstraindo-se a duração do tempo real para que a conexão seja estabelecida) e podendo envolver várias instâncias de MSC. Essa extensão é conservativa, no sentido que o comportamento das construções existentes não é afetado pela mesma; além disso, em um mesmo diagrama é possível conter mensagens síncronas e mensagens assíncronas. Foi desenvolvido um algoritmo de transformação, que a partir de um diagrama escrito na notação MSC estendido, gera um diagrama correspondente na notação de MSC padrão. Este algoritmo tem por objetivo permitir a transitividade entre as notações e demonstrar suas equivalências. Este algoritmo de transformação implementa mensagens síncronas como uma seqüência de mensagens assíncronas seguindo um algoritmo particular de handshake. A segunda contribuição desse trabalho é a definição de uma semântica para a notação padrão e estendida de MSC. Essa definição é dada em termos da álgebra de processos CSP (Communicating Sequential Processes). O formalismo introduzido na notação de Message Sequence Charts com CSP permite mostrar a equivalência entre um diagrama na notação de MSC estendido e seu correspondente descrito em MSC padrão, gerado a partir do algoritmo de transformação. Além disso, modelar MSC como um processo descrito na notação CSP permite uma análise sobre seus diagramas, usando um rico conjunto de leis algébricas de CSP, bem como o uso de ferramentas, como FDR2 e o Probe. Finalmente, para validar a estratégia proposta, desenvolveu-se um exemplo que ilustra a utilização da notação estendida de MSC, notação síncrona; a conversão desta notação para a notação padrão e a equivalência entre o MSC estendido e o padrão. Mostramos, ainda, o uso da ferramenta Power Tool Kit(PTK) para geração de casos de teste a partir de diagramas MSC

The ever-growing competition in current electronics industry has resulted in stringent time-to-market goals and reduced design time available to engineers. Lesser design time has subsequently raised a need for high-level synthesis design methodologies that raise the design to a higher level of abstraction. Higher level of abstraction helps in increasing the predictability and productivity of the design and reduce the number of bugs due to human-error. It also enables the designer to try out dierent optimization strategies early in the design stage. In-spite of all these advantages, high-level synthesis design methodologies have not gained much popularity in the mainstream design flow mainly because of the reasons like lack of readability and reliability of the generated register transfer level (RTL) code. The compiler framework presented in this thesis allows the user to draw high-level graphical models of the system. The compiler translates these models into synthesizeable RTL Verilog designs that exhibit their desired functionality following communicating sequential processes (CSP) model of computation. CSP model of computation introduces a good handshaking mechanism between different components in the design that makes designs less prone to timing violations during implementation and bottlenecks while in actual operation. / Master of Science

The Parameterised Model Checking Problem asks whether an implementation Impl(t) satisfies a specification Spec(t) for all instantiations of parameter t. In general, t can determine numerous entities: the number of processes used in a network, the type of data, the capacities of buffers, etc. The main theme of this thesis is automation of uniform verification of a subclass of PMCP with the parameter of the first kind, using techniques based on counter abstraction. Counter abstraction works by counting how many, rather than which, node processes are in a given state: for nodes with k local states, an abstract state (c(1), ..., c(k)) models a global state where c(i) processes are in the i-th state. We then use a threshold function z to cap the values of each counter. If for some i, counter c(i) reaches its threshold, z(i) , then this is interpreted as there being z(i) or more nodes in the i-th state. The addition of thresholds makes abstract models independent of the instantiation of the parameter. We adapt standard counter abstraction techniques to concurrent reactive systems modelled using the CSP process algebra. We demonstrate how to produce abstract models of systems that do not use node identifiers (i.e. where all nodes are indistinguishable). Every such abstraction is, by construction, refined by all instantiations of the implementation. If the abstract model satisfies the specification, then a positive answer to the particular uniform verification problem can be deduced. We show that by adding node identifiers we make the uniform verification problem undecidable. We demonstrate a sound abstraction method that extends standard counter abstraction techniques to systems that make full use of node identifiers (in specifications and implementations). However, on its own, the method is not enough to give the answer to verification problems for all parameter instantiations. This issue has led us to the development of a type reduction theory, which, for a given verification problem, establishes a function phi that maps all (sufficiently large) instantiations T of the parameter to some fixed type T and allows us to deduce that if Spec(T) is refined by phi(Impl(T)), then Spec(T) is refined by Impl(T). We can then combine this with our extended counter abstraction techniques and conclude that if the abstract model satisfies Spec(T), then the answer to the uniform verification problem is positive. We develop a symbolic operational semantics for CSP processes that satisfy certain normality requirements and we provide a set of translation rules that allow us to concretise symbolic transition graphs. The type reduction theory relies heavily on these results. One of the main advantages of our symbolic operational semantics and the type reduction theory is their generality, which makes them applicable in other settings and allows the theory to be combined with abstraction methods other than those used in this thesis. Finally, we present TomCAT, a tool that automates the construction of counter abstraction models and we demonstrate how our results apply in practice.

[ES] Producir software eficiente y efectivo es una tarea que parece ser tan difícil ahora como lo era para los primeros ordenadores. Con cada mejora de hardware y herramientas de desarrollo (como son compiladores y analizadores), la demanda de producir software más rápido y más complejo ha ido aumentando. Por tanto, todos estos análisis auxiliares ahora son una parte integral del desarrollo de programas complejos. La fragmentación de programas es una técnica de análisis estático, que da respuesta a ¿Qué partes del programa pueden afectar a esta instrucción? Su aplicación principal es la depuración de programas, porque puede acotar la zona de código a la que el programador debe prestar atención mientras busca la causa de un error. También tiene otras muchas aplicaciones, como pueden ser la paralelización y especialización de programas, la comprensión de programas y el mantenimiento. En los últimos años, su uso más común ha sido como preproceso a otros análisis con alto coste computacional, para reducir el tamaño del programa a procesar, y, por tanto, el tiempo de ejecución de estos. La estructura de datos más popular para fragmentar programas es el system dependence graph (SDG), un grafo dirigido que representa las instrucciones de un programa como vértices, y sus dependencias como arcos. Los dos tipos principales de dependencias son las de control y las de datos, que encapsulan el flujo de control y datos en todas las ejecuciones posibles de un programa. El área de lenguajes de programación está en eterno cambio, ya sea por la aparición de nuevos lenguajes o por el lanzamiento de nuevas características en lenguajes existentes, como pueden ser Java o Erlang. Sin embargo, la fragmentación de programas se definió originalmente para el paradigma imperativo. Aun así, hay características populares en lenguajes imperativos, como las arrays y las excepciones, que aún no tienen una representación eficiente y/o completa en el SDG. Otros paradigmas, como el funcional o el orientado a objetos, sufren también de un soporte parcial en el SDG. Esta tesis presenta mejoras para construcciones comunes en la programación moderna, dividiendo contribuciones en las enfocadas a dependencias de control y las enfocadas a datos. Para las primeras, especificamos una nueva representación de instrucciones catch, junto a una descripción completa del resto de instrucciones relacionadas con excepciones. También analizamos las técnicas punteras para saltos incondicionales (p.e., break), y mostramos los riesgos de combinarlas con otras técnicas para objetos, llamadas o excepciones. A continuación, ponemos nuestra mirada en la concurrencia, con una formalización de un depurador de especificaciones CSP reversible y causal-consistente. En cuanto a las dependencias de datos, se enfocan en técnicas sensibles al contexto (es decir, más precisas en presencia de rutinas y sus llamadas). Exploramos las dependencias de datos generadas en programas concurrentes por memoria compartida, redefiniendo las dependencias de interferencia para hacerlas sensibles al contexto. A continuación, damos un pequeño rodeo por el campo de la indecidibilidad, en el que demostramos que ciertos tipos de análisis de datos sobre programas con estructuras de datos complejas son indecidibles. Finalmente, ampliamos un trabajo previo sobre la fragmentación de estructuras de datos complejas, combinándolo con la fragmentación tabular, que la hace sensible al contexto. Además, se han desarrollado o extendido múltiples librerías de código con las mejoras mencionadas anteriormente. Estas librerías nos han permitido realizar evaluaciones empíricas para algunos de los capítulos, y también han sido publicadas bajo licencias libres, que permiten a otros desarrolladores e investigadores extenderlas y contrastarlas con sus propuestas, respectivamente. Las herramientas resultantes son dos fragmentadores de código para Java y Erlang, y un depurador de CSP reversible y causal-consistente. / [CA] La producció de programari eficient i eficaç és una tasca que resulta tan difícil hui dia com ho va ser durant l'adveniment dels ordinadors. Per cada millora de maquinari i ferramentes per al desenvolupament, augmenta sovint la demanda de programes, així com la seua complexitat. Com a conseqüència, totes aquestes anàlisis auxiliars esdevenen una part integral del desenvolupament de programari. La fragmentació de programes és una tècnica d'anàlisi estàtica, que respon a "Quines parts d'aquest programa poden afectar a aquesta instrucció?". L'aplicació principal d'aquesta tècnica és la depuració de programes, per la seua capacitat de reduir la llargària d'un programa sense canviar el seu funcionament respecte a una instrucció que està fallant, delimitant així l'àrea del codi en què el programador busca l'origen de l'errada. Tot i això, té moltes altres aplicacions, com la paral·lelització i especialització de programes o la comprensió de programes i el seu manteniment. Durant els darrers anys, l'ús més freqüent de la fragmentació de programes ha sigut com a <<preprocés>> abans d'altres anàlisis amb un alt cost computacional, per tal de reduir-ne el temps requerit per realitzar-les. L'estructura de dades més popular per fragmentar programes és el system dependence graph (SDG), un graf dirigit representant-ne les instruccions d'un programa amb vèrtexs i les seues dependències amb arcs. Els dos tipus principals de dependència són el de control i el de dades, aquests encapsulen el flux de control i dades a totes les possibles execucions d'un programa. L'àrea dels llenguatges de programació s'hi troba en constant evolució, o bé per l'aparició de nous llenguatges, o bé per noves característiques per als preexistents, com poden ser Java o Erlang. No obstant això, la fragmentació de programes s'hi va definir originalment per al paradigma imperatiu. Tot i que, també hi trobem característiques populars als llenguatges imperatius, com els arrays i les excepcions, que encara no en tenen una representació eficient i/o completa al SDG. Altres paradigmes, com el funcional o l'orientat a objectes, pateixen també d'un suport reduit al SDG. Aquesta tesi presenta millores per a construccions comunes de la programació moderna, dividint les contribucions entre aquelles enfocades a les dependències de control i aquelles enfocades a dades. Per a les primeres, hi especifiquem una nova representació d'instruccions catch, junt amb una descripció de la resta d'instruccions relacionades amb excepcions. També hi analitzem les tècniques capdavanteres de fragmentació de salts incondicionals, i hi mostrem els riscs de combinar-ne-les amb altres tècniques per a objectes, instruccions de crida i excepcions. A continuació, hi posem la nostra atenció en la concurrència, amb una formalització d'un depurador d'especificacions CSP reversible i causal-consistent. Respecte a les dependències de dades, dirigim els nostres esforços a produir tècniques sensibles al context (és a dir, que es mantinguen precises en presència de procediments). Hi explorem les dependències de dades generades en programes concurrents amb memòria compartida, redefinint-ne les dependències d'interferència per a fer-ne-les sensibles al context. Seguidament, hi demostrem la indecidibilitat d'alguns tipus d'anàlisis de dades per a programes amb estructures de dades complexes. Finalment, hi ampliem un treball previ sobre la fragmentació d'estructures de dades complexes, combinant-lo amb la fragmentació tabular, fent-hi-la sensible al context. A més a més, s'han desenvolupat o estés diverses llibreries de codi amb les millores esmentades prèviament. Aquestes llibreries ens han permés avaluar empíricament alguns dels capítols i també han sigut publicades sota llicències lliures, fet que permet a altres desenvolupadors i investigadors poder estendre-les i contrastar-les, respectivament. Les ferramentes resultants són dos fragmentadors de codi per a Java i Erlang, i un depurador CSP. / [EN] Producing efficient and effective software is a task that has remained difficult since the advent of computers. With every improvement on hardware and developer tooling (e.g., compilers and checkers), the demand for software has increased even further. This means that auxiliary analyses have become integral in developing complex software systems. Program slicing is a static analysis technique that gives answers to "What parts of the program can affect a given statement?", and similar questions. Its main application is debugging, as it can reduce the amount of code on which a programmer must look for a mistake or bug. Other applications include program parallelization and specialisation, program comprehension, and software maintenance. Lately, it has mostly been applied as a pre-processing step in other expensive static analyses, to lower the size of the program and thus the analyses' runtime. The most popular data structure in program slicing is the system dependence graph (SDG), which represents statements as nodes and dependences as arcs between them. The two main types of dependences are control and data dependences, which encapsulate the control and data flow throughout every possible execution of a program. Programming languages are an ever-expanding subject, with new features coming to new releases of popular and up-and-coming languages like Python, Java, Erlang, Rust, and Go. However, program slicing was originally defined for (and has been mostly focused on) imperative programming languages. Even then, some popular elements of the imperative paradigm, such as arrays and exceptions do not have an efficient or sometimes complete representation in the SDG. Other paradigms, such as functional or object-oriented also suffer from partial support in the SDG. This thesis presents improvements for common programming constructs, and its contributions are split into control and data dependence. For the former, we (i) specify a new representation of catch statements, along with a full description of other exception-handling constructs. We also (ii) analyse the current state-of-the-art technique for unconditional jumps (e.g., break or return), and show the risks of combining it with other popular techniques. Then, we focus on concurrency, with a (iii) formalisation of a reversible, causal-consistent debugger for CSP specifications. Switching to data dependences, we focus our contributions on making existing techniques context-sensitive (i.e., more accurate in the presence of routines or functions). We explore the data dependences involved in shared-memory concurrent programs, (iv) redefining interference dependence to make it context-sensitive. Afterwards, we take a small detour to (v) explore the decidability of various data analyses on programs with (and without) complex data structures and routine calls. Finally, we (vi) extend our previous work on slicing complex data structures to combine it with tabular slicing, which provides context-sensitivity. Additionally, throughout this thesis, multiple supporting software libraries have been written or extended with the aforementioned improvements to program slicing. These have been used to provide empirical evaluations, and are available under libre software licenses, such that other researchers and software developers may extend or contrast them against their own proposals. The resulting tools are two program slicers for Java and Erlang, and a causal-consistent reversible debugger for CSP. / Galindo Jiménez, CS. (2024). Program Slicing for Modern Programming Languages [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/211183