Does your program do what it is supposed to be doing? Without running the program providing an answer to this question is much harder if the language does not support static type checking. Of course, even if compile-time checks are in place only certain errors will be detected: compilers can only second-guess the programmer’s intention. But, type based techniques go a long way in assisting programmers to detect errors in their computations earlier on. The question if a program behaves correctly is even harder to answer if the program consists of several parts that execute concurrently and need to communicate with each other. Compilers of standard programming languages are typically unable to infer information about how the parts of a concurrent program interact with each other, especially where explicit threading or message passing techniques are used. Hence, correctness guarantees are often conspicuously absent. Concurrency management in an application is a complex problem. However, it is largely orthogonal to the actual computational functionality that a program realises. Because of this orthogonality, the problem can be considered in isolation. The largest possible separation between concurrency and functionality is achieved if a dedicated language is used for concurrency management, i.e. an additional program manages the concurrent execution and interaction of the computational tasks of the original program. Such an approach does not only help programmers to focus on the core functionality and on the exploitation of concurrency independently, it also allows for a specialised analysis mechanism geared towards concurrency-related properties. This dissertation shows how an approach that completely decouples coordination from computation is a very supportive substrate for inferring static guarantees of the correctness of concurrent programs. Programs are described as streaming networks connecting independent components that implement the computations of the program, where the network describes the dependencies and interactions between components. A coordination program only requires an abstract notion of computation inside the components and may therefore be used as a generic and reusable design pattern for coordination. A type-based inference and checking mechanism analyses such streaming networks and provides comprehensive guarantees of the consistency and behaviour of coordination programs. Concrete implementations of components are deliberately left out of the scope of coordination programs: Components may be implemented in an external language, for example C, to provide the desired computational functionality. Based on this separation, a concise semantic framework allows for step-wise interpretation of coordination programs without requiring concrete implementations of their components. The framework also provides clear guidance for the implementation of the language. One such implementation is presented and hands-on examples demonstrate how the language is used in practice.

This work investigates a series of phenomena that shed light on the analysis of attitudes de se. We adopt Lewis’ (1979) proposal that attitudes de se involve self-ascription of a property, and investigate how this view of mental content is reflected in natural language. The implementation favored is a strong version of Lewis’ position: root and embedded clauses are uniformly treated as being of property type. Our approach elaborates Chierchia’s (1990) view that de se construals arise via binding by an abstraction operator in the clausal left periphery. Part I develops an argument that such operators occur in root as well as embedded clauses. This is contrasted with the view that the evaluation index incorporates an individual parameter, a prominent version of which treats the behavior of predicates of taste such as tasty as evidence that truth is relativized to individuals (Lasersohn, 2005; Stephenson, 2007a, 2007b). Chapter 2 argues against this view, defending a semantics for taste predicates that requires no appeal to an individual parameter. Chapter 3 employs an argument from Moore’s Paradox to motivate the proposal that root clauses bear individual abstractors in their left periphery, while Chapter 4 identifies phenomena that the system accounts for. Part II concerns two elements whose distribution is confined to embedded clauses: controlled PRO and the logophoric pronoun in the Niger-Congo language Ewe. Chapters 5 and 6 investigate the semantics of partial control, a variety of control where the controller denotes a proper subset of the understood subject. The view that control complements express properties lends itself to a principled account of which predicates license partial control. Chapter 7 presents novel data regarding the logophoric pronoun in Ewe. We show that, contrary to what had been assumed in the absence of the necessary fieldwork, Ewe logopohors are not obligatorily de se. We propose an account of this finding that is compatible with the implementation of the property view that we favor. Chapter 8 closes the dissertation by considering why it should be that certain expressions, such as PRO, are obligatorily de se while others, like the Ewe logophor, can be de re. / Linguistics

An end-to-end guarantee of software correctness by formal verification must consider two sources of bugs. First, the verification tool must be correct. Second, programs are often verified at the source level, before being compiled. Hence, compilers should also be trustworthy. Verifiers and compilers' complexity is increasing. To simplify code analysis and manipulation, these tools rely on intermediate representations (IR) of programs, that provide structural and semantic properties. This thesis gives a formal, semantic account on IRs, so that they can also be leveraged in the formal proof of such tools. We first study a register-based IR of Java bytecode used in compilers and verifiers. We specify the IR generation by a semantic theorem stating what the transformation preserves, e.g. object initialization or exceptions, but also what it modifies and how, e.g. object allocation. We implement this IR in Sawja, a Java static analysis toolbench. Then, we study the Static Single Assignment (SSA) form, an IR widely used in modern compilers and verifiers. We implement and prove in Coq an SSA middle-end for the CompCert C compiler. For the proof of SSA optimizations, we identify a key semantic property of SSA, allowing for equational reasoning. Finally, we study the semantics of concurrent Java IRs. Due to instruction reorderings performed by the compiler and the hardware, the current definition of the Java Memory Model (JMM) is complex, and unfortunately formally flawed. Targetting x86 architectures, we identify a subset of the JMM that is intuitive and tractable in formal proofs. We characterize the reorderings it allows, and factor out a proof common to the IRs of a compiler.

Resilient Distributed Systems (RDS) are large-scale distributed systems that remain de-pendable despite their very dynamic, open-ended, and inherently unpredictable environ-ments. This combination of system and environment properties makes development of soft-ware architectures for RDS using contemporary architecture models and abstractions very challenging. Therefore, the thesis proposes: (1) new architecture abstractions that are tailored for building dynamic software architectures for RDS, (2) design models and processes that endorse these abstractions at design time, and (3) means for efficient implementation, execu-tion, and analysis of architectures based on these abstractions. Specifically, the thesis delivers (1) by introducing the DEECo component model, based on the concept of component ensembles. Contributing to (2), the thesis presents the Invari-ant Refinement Method, governing dependable, formally-grounded design of DEECo-based architectures, and the ARCAS method, focusing on dependable realization of open-ended dynamic component bindings typical for DEECo. Furthermore, it pursues (3) by presenting a formal operational semantics of DEECo and its mapping to Java in terms of an execution environment prototype - jDEECo. Additionally, the semantics is used as a basis for formal analysis via model...

In this dissertation we prove the Completeness, Soundness and Compactness of the Monadic Hybrid Calculus MHC and we prove its expressive equivalence to the Monadic Predicate Calculus MPC. The Monadic Hybrid Calculus MHC is a new system that is based on the (propositional) modal logic S5. It is “Hybrid” in the sense that it includes quantifier free MPC and therefore, unlike S5, allows free individual constants. The main innovation in this system is the elimination of bound variables. In MHC, upper case letters denote properties and lower case letters denote individuals. Universal quantification is represented by square brackets, [], and existential quantification is represented by angled brackets, 〈〉. Thus, All Athenians are Greek and mortal is formalized as [A](G∧M), Some mortal Greeks are Athenians as 〈M∧G〉A, and Socrates is mortal and Athenian as s(M∧A). We give the formal syntax and the formal semantics of [MHC] and give Beth-style Tableau Rules (Inference Rules). In these rules, if [P]Q is on the right then we select a new constant [v] and we add [vP] on left, vQ on the right, and we cancel the formula. If [P]Q is on the left then we select a pre-used constant p and split the tree. We add pP on the right of one branch and pQ on the left of the other branch. We treat 〈P〉Q similarly. Our Completeness proof uses induction on formulas down a path in the proof tree. Our Soundness proof uses induction up a path. To prove that MPC is logically equivalent to the Monadic Predicate Calculus, we present algorithms that transform formulas back and forth between these two systems. Compactness follows immediately. Finally, we examine the pragmatic usage of the Monadic Hybrid Calculus and we compare it with the Monadic Predicate Calculus using natural language examples. We also examine the novel notions of the Hybrid Predicate Calculus along with their pragmatic implications. / Graduate / 0800 / 0984

La vérification formelle de programme n'apporte pas de garantie complète si l'outil de vérification est incorrect. Et, si un programme est vérifié au niveau source, le compilateur pourrait introduire des bugs. Les compilateurs et vérifieurs actuels sont complexes. Pour simplifier l'analyse et la transformation de code, ils utilisent des représentations intermédiaires (IR) de programme, qui ont de fortes propriétés structurelles et sémantiques. Cette thèse étudie d'un point de vue sémantique et formel les IRs, afin de faciliter la preuve de ces outils. Nous étudions d'abord une IR basée registre du bytecode Java. Nous prouvons un théorème sur sa génération, explicitant ce que la transformation préserve (l'initialisation d'objet, les exceptions) et ce qu'elle modifie et comment (l'ordre d'allocation). Nous implantons l'IR dans Sawja, un outil de développement d'analyses statiques de Java. Nous étudions aussi la forme SSA, une IR au coeur des compilateurs et vérifieurs modernes. Nous implantons et prouvons en Coq un middle-end SSA pour le compilateur C CompCert. Pour la preuve des optimisations, nous prouvons un invariant sémantique de SSA clé pour le raisonnement équationnel. Enfin, nous étudions la sémantique des IRs de Java concurrent. La définition actuelle du Java Memory Model (JMM) autorise les optimisations aggressives des compilateurs et des architectures parallèles. Complexe, elle est formellement cassée. Ciblant les architectures x86, nous proposons un sous-ensemble du JMM intuitif et adapté à la preuve formelle. Nous le caractérisons par ses réordonnancements, et factorisons cette preuve sur les IRs d'un compilateur. / An end-to-end guarantee of software correctness by formal verification must consider two sources of bugs. First, the verification tool must be correct. Second, programs are often verified at the source level, before being compiled. Hence, compilers should also be trustworthy. Verifiers and compilers' complexity is increasing. To simplify code analysis and manipulation, these tools rely on intermediate representations (IR) of programs, that provide structural and semantic properties. This thesis gives a formal, semantic account on IRs, so that they can also be leveraged in the formal proof of such tools. We first study a register-based IR of Java bytecode used in compilers and verifiers. We specify the IR generation by a semantic theorem stating what the transformation preserves, e.g. object initialization or exceptions, but also what it modifies and how, e.g. object allocation. We implement this IR in Sawja, a Java static analysis toolbench. Then, we study the Static Single Assignment (SSA) form, an IR widely used in modern compilers and verifiers. We implement and prove in Coq an SSA middle-end for the CompCert C compiler. For the proof of SSA optimizations, we identify a key semantic property of SSA, allowing for equational reasoning. Finally, we study the semantics of concurrent Java IRs. Due to instruction reorderings performed by the compiler and the hardware, the current definition of the Java Memory Model (JMM) is complex, and unfortunately formally flawed. Targetting x86 architectures, we identify a subset of the JMM that is intuitive and tractable in formal proofs. We characterize the reorderings it allows, and factor out a proof common to the IRs of a compiler.

Analysis and verification of security protocols are typically carried out in two different models of cryptography: formal cryptography and computational cryptography. Formal cryptography, originally inspired by the work of Dolev and Yao [14], takes an abstract and idealized view of security, and develops its proof techniques based on methods and ideas from logic and theory of programming languages. It makes strong assumptions about cryptographic operations by treating them as perfectly-secure symbolic operations. Computational cryptography, on the other hand, has developed its foundations based on complexity theory. Messages are viewed as bit-strings, and cryptographic operations are treated as actual transformations on bit-strings with certain asymptotic properties.In this thesis, we explore the relation between the Dolev-Yao model and the computational model of public-key cryptography in two contexts: indistinguishability and non-malleability of expressions. This problem in the absence of key-cycles is partially addressed in [20, 21] by Herzog. We adapt our approach to use the co-inductive definition of symbolic security, whose private-key treatment was considered in coinduction, and establish our main results as follow: Using a co-inductive approach, we extend the indistinguishability and non-malleability results of Herzog in the presence of key-cycles. By providing a counter-example, we show that the indistinguishability property in this setting is strictly stronger than the non-malleability property, which gives a negative answer to Herzog's conjecture that they are equivalent. we prove that despite the fact that IND-CCA2 security provides non-malleability in our setting, the same result does not hold for IND-CCA1 security. We prove that, under certain hypothesis, our co-inductive formal indistinguishability is computationally-complete in the absence of key-cycles and with respect to any \emph{length-revealing} encryption scheme. In the presence of key-cycles, we prove that the completeness does not hold even with respect to IND-CPA security. / Graduate

A UML é uma notação gráfica utilizada na modelagem de sistemas orientados a objetos, em diferentes domínios da computação. Por ser simples de utilizar, em relação a outras formas de modelagem, a UML é amplamente difundida entre os desenvolvedores de software, tanto na academia quanto na indústria. Entre as suas vantagens, encontram-se: (i) a representação visual das relações entre classes e entidades, pois ao se utilizar de diagramas, a UML facilita o entendimento e a visualização das relações dentro do sistema modelado; (ii) a legibilidade e usabilidade, sem que seja necessário a leitura do código do sistema, uma vez que um desenvolvedor pode compreender quais partes do código são redundantes ou reutilizadas; e (iii) uma ferramenta de planejamento, ao auxiliar na definição do que deve ser feito, antes que a implementação comece de fato, além de poder produzir código e reduzir o tempo de desenvolvimento. Todavia, a UML possui desvantagens, tais como: (i) ambiguidade entre elementos UML diferentes, devido a sobreposição dos diagramas; e (ii) falta de uma semântica clara, o qual geralmente faz com que a semântica da linguagem de programação seja adotada. Para mitigar essas desvantagens, pesquisadores buscam atribuir uma semântica formal à UML. Esse tipo de semântica é encontrado em modelos formais, onde o sistema modelado é livre de ambiguidades e possui uma semântica clara e precisa. Por sua vez, os modelos formais não são simples de serem criados e compreendidos por desenvolvedores. O grau de conhecimento em formalismo necessário para utilizar tal modelo é alto, o que faz com que seu uso seja menos difundido, comparado com a notação gráfica não formal da UML. Apesar dos esforços dos pesquisadores, as técnicas de formalização semântica da UML apresentam, no geral, um problema pouco abordado: apesar de utilizar a UML para modelar o sistema, o artefato final dessas técnicas é um trace formal. Considerando o conhecimento comum de um desenvolvedor de software, esse trace dificulta a análise dos problemas, encontrados pelos model checkers, e a correção dos mesmos no modelo UML. Com o objetivo de auxiliar o desenvolvedor na compreensão dos resultados formais (o trace citado), esta tese de doutorado apresenta uma abordagem baseada em Model-driven Architecture (MDA) capaz de representar as informações dos resultados formais dentro de um modelo UML. Por meio de transformações do modelo UML, essas representações, definidas utilizando a abordagem, auxiliam o desenvolvedor a visualizar o fluxo de execução do model checker dentro do modelo UML. Assim, acredita-se que as vantagens obtidas pela formalização semântica da UML podem ser mais difundidas e utilizadas pelos desenvolvedores, principalmente na indústria. / UML is a graphical notation used for modeling object-oriented software systems in different domains in computer science. Being simple to use, compared to other modeling techniques, UML is widespread among software developers, both in academia and industry. Among its advantages are: (i) the visual representation of the relationships between classes and entities, as when using diagrams, UML facilitates understanding and visualization of relationships within the modeled system; (ii) readability and usability without having to read the system code, since a developer can understand which parts of the code are redundant or reusable; and (iii) a planning tool, helping to define what needs to be done before the implementation actually begins, as well as being able to produce code and reduce development time. However, the UML also has disadvantages, such as: (i) ambiguity between different UML elements due to overlapping diagrams; and (ii) lack of clear semantics, which generally causes the semantics of the programming language to be adopted. To mitigate these disadvantages, researchers seek to assign a formal semantics to the UML. This type of semantics is found in formal models, where the modeled system is free of ambiguity and has a clear and precise semantics. On the other hand, formal models are not simple to create and understand by developers. The degree of formalism knowledge required to use such a model is high, which makes their use less widespread, compared to UML non-formal graphical notation. Despite the researchers efforts, in general the techniques that formalize the UML semantics has a problem that is forgotten: although using the UML to model the system, the final artifact of these techniques is a formal trace. Considering the common knowledge of a software developer, this trace makes it difficult to analyze the problems encountered by model checkers and to correct them in the UML model. In order to assist the developer in understanding the formal results (the trace above), this thesis presents an approach based on Model-driven Architecture (MDA) capable of representing the information of the formal results in the UML model. Through UML model transformations, these representations, set using the approach, help the developer to visualize the execution flow of the model checker within the UML model. Thus, we believe that the advantages obtained by formalizing the UML semantics may be more widespread and used by developers, especially in industry.

No description available.

Organisations such as governments and healthcare bodies are increasingly responsible for managing large amounts of personal information, and the increasing complexity of modern information systems is causing growing concerns about the protection of these assets from insider threats. Insider threats are very difficult to handle, because the insiders have direct access to information and are trusted by their organisations. The nature of insider privacy breaches varies with the organisation’s acceptable usage policy and the attributes of an insider. However, the level of risk that insiders pose depends on insider breach scenarios including their access patterns and contextual information, such as timing of access. Protection from insider threats is a newly emerging research area, and thus, only few approaches are available that systemise the continuous monitoring of dynamic insider usage characteristics and adaptation depending on the level of risk. The aim of this research is to develop a formal framework for an adaptive early warning and response system for insider privacy breaches within dynamic software systems. This framework will allow the specification of multiple policies at different risk levels, depending on event patterns, timing constraints, and the enforcement of adaptive response actions, to interrupt insider activity. Our framework is based on Usage Control (UCON), a comprehensive model that controls previous, ongoing, and subsequent resource usage. We extend UCON to include interrupt policy decisions, in which multiple policy decisions can be expressed at different risk levels. In particular, interrupt policy decisions can be dynamically adapted upon the occurrence of an event or over time. We propose a computational model that represents the concurrent behaviour of an adaptive early warning and response system in the form of statechart. In addition, we propose a Privacy Breach Specification Language (PBSL) based on this computational model, in which event patterns, timing constraints, and the triggered early warning level are expressed in the form of policy rules. The main features of PBSL are its expressiveness, simplicity, practicality, and formal semantics. The formal semantics of the PBSL, together with a model of the mechanisms enforcing the policies, is given in an operational style. Enforcement mechanisms, which are defined by the outcomes of the policy rules, influence the system state by mutually interacting between the policy rules and the system behaviour. We demonstrate the use of this PBSL with a case study from the e-government domain that includes some real-world insider breach scenarios. The formal framework utilises a tool that supports the animation of the enforcement and policy models. This tool also supports the model checking used to formally verify the safety and progress properties of the system over the policy and the enforcement specifications.