• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 17
  • 2
  • 1
  • 1
  • 1
  • 1
  • Tagged with
  • 26
  • 11
  • 8
  • 8
  • 8
  • 5
  • 5
  • 5
  • 5
  • 5
  • 5
  • 5
  • 4
  • 4
  • 4
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Code generation from specifications in higher-order logic

Haftmann, Florian January 2009 (has links)
München, Techn. Univ., Diss., 2009.
2

A separation logic framework for HOL

Tuerk, Thomas January 2011 (has links)
No description available.
3

Eine formale algorithmische Synthese digitaler Schaltungen

Kapp, Kai. January 2005 (has links) (PDF)
Universiẗat, Diss., 2005 u.d.T.: Knapp, Kai: Eine automatisierte optimierende formale Synthese steuerflussbehafteter Schaltungsbeschreibungen--Karlsruhe.
4

Efficiency in a fully-expansive theorem prover

Boulton, Richard John January 1993 (has links)
No description available.
5

Certifying system translations using higher order theorem provers

Blech, Jan Olaf January 2008 (has links)
Zugl.: Kaiserslautern, Techn. Univ., Diss., 2008
6

De osynliga barnen : Om den svenska statens skyldigheter gentemot de svenska barnen i nordöstra Syrien

Karlsson, Christina January 2021 (has links)
No description available.
7

Model-based Testing of Operating System-Level Security Mechanisms / test à base de modèles formels pour les mécanismes de sécurité dans les systèmes d’exploitation

Nemouchi, Yakoub 30 March 2016 (has links)
Le test à base de modèle, en particulier test basé sur des assistants à la preuve, réduit de façon transparente l'écart entre la théorie, le modèle formel, et l’implémentation d'un système informatique. Actuellement, les techniques de tests offrent une possibilité d'interagir directement avec de "vrais" systèmes : via différentes propriétés formelles, les tests peuvent être dérivés et exécutés sur le système sous test. Convenablement, l'ensemble du processus peut être entièrement automatisé. Le but de cette thèse est de créer un environnement de test de séquence à base de modèle pour les programmes séquentiels et concurrents. Tout d'abord une théorie générique sur les monades est présentée, qui est indépendante de tout programme ou système informatique. Il se trouve que notre théorie basée sur les monades est assez expressive pour couvrir tous les comportements et les concepts de tests. En particulier, nous considérons ici : les exécutions séquentielles, les exécutions concurrentes, les exécutions synchronisées, les exécutions avec interruptions. Sur le plan conceptuel, la théorie apporte des notions comme la notion raffinement de test, les cas de tests abstraits, les cas de test concrets, les oracles de test, les scénarios de test, les données de tests, les pilotes de tests, les relations de conformités et les critères de couverture dans un cadre théorique et pratique. Dans ce cadre, des règles de raffinement de comportements et d'exécution symbolique sont élaborées pour le cas générique, puis affinées et utilisées pour des systèmes complexes spécifique. Comme application pour notre théorie, nous allons instancier notre environnement par un modèle séquentiel d'un microprocesseur appelé VAMP développé au cours du projet Verisoft. Pour le cas d'étude sur la concurrence, nous allons utiliser notre environnement pour modéliser et tester l'API IPC d'un système d'exploitation industriel appelé PikeOS.Notre environnement est implémenté en Isabelle / HOL. Ainsi, notre approche bénéficie directement des modèles, des outils et des preuves formelles de ce système. / Formal methods can be understood as the art of applying mathematical reasoningto the modeling, analysis and verification of computer systems. Three mainverification approaches can be distinguished: verification based on deductive proofs,model checking and model-based testing.Model-based testing, in particular in its radical form of theorem proving-based testingcite{brucker.ea:2012},bridges seamlessly the gap between the theory, the formal model, and the implementationof a system. Actually,theorem proving based testing techniques offer a possibility to directly interactwith "real" systems: via differentformal properties, tests can be derived and executed on the system under test.Suitably supported, the entire process can fully automated.The purpose of this thesis is to create a model-based sequence testing environmentfor both sequential and concurrent programs. First a generic testing theory basedon monads is presented, which is independent of any concrete program or computersystem. It turns out that it is still expressive enough to cover all common systembehaviours and testing concepts. In particular, we consider here: sequential executions,concurrent executions, synchronised executions, executions with abort.On the conceptual side, it brings notions like test refinements,abstract test cases, concrete test cases,test oracles, test scenarios, test data, test drivers, conformance relations andcoverage criteria into one theoretical and practical framework.In this framework, both behavioural refinement rules and symbolic executionrules are developed for the generic case and then refined and used for specificcomplex systems. As an application, we will instantiate our framework by an existingsequential model of a microprocessor called VAMP developed during the Verisoft-Project.For the concurrent case, we will use our framework to model and test the IPC API of areal industrial operating system called PikeOS.Our framework is implemented in Isabelle/HOL. Thus, our approach directly benefitsfrom the existing models, tools, and formal proofs in this system.
8

Constructing Semantically Sound Object-Logics for UML/OCL Based Domain-Specific Languages / Construction de Logiques-Objet Sémantiquement Correct pour des Langages à Domaines Spécifiques Basés sur UML/OCL

Tuong, Frédéric 06 April 2016 (has links)
Les langages de spécifications basés et orientés objets (comme UML/OCL, JML, Spec#, ou Eiffel) permettent la création et destruction, la conversion et tests de types dynamiques d'objets statiquement typés. Par dessus, les invariants de classes et les opérations de contrat peuvent y être exprimés; ces derniers représentent les éléments clés des spécifications orientées objets. Une sémantique formelle des structures de données orientées objets est complexe : des descriptions imprécises mènent souvent à différentes interprétations dans les outils qui en résultent. Dans cette thèse, nous démontrons comment dériver un environnement de preuves moderne comme un méta-outil pour la définition et l'analyse de sémantique formelle de langages de spécifications orientés objets. Étant donné une représentation d'un langage particulier plongé en Isabelle/HOL, nous construisons pour ce langage un environnement étendu d'Isabelle, à travers une méthode de génération de code particulière, qui implique notamment plusieurs variantes de génération de code. Le résultat supporte l'édition asynchrone, la vérification de types, et les activités de déduction formelle, tous "hérités" d'Isabelle. En application de cette méthode, nous obtenons un outil de modélisation orienté objet pour du UML/OCL textuel. Nous intégrons également des idiomes non nécessairement présent dans UML/OCL --- en d'autres termes, nous développons un support pour des dialectes d'UML/OCL à domaine spécifique. En tant que construction méta, nous définissons un méta-modèle d'une partie d'UML/OCL en HOL, un méta-modèle d'une partie de l'API d'Isabelle en HOL, et une fonction de traduction entre eux en HOL. Le méta-outil va alors exploiter deux procédés de générations de code pour produire soit du code raisonnablement efficace, soit du code raisonnablement lisible. Cela fournit donc deux modes d'animations pour inspecter plus en détail la sémantique d'un langage venant d'être plongé : en chargeant à vitesse réelle sa sémantique, ou simplement en retardant à un autre niveau "méta" l'expérimentation précédente pour un futur instant de typage en Isabelle, que ce soit pour des raisons de performances, de tests ou de prototypages. Remarquons que la génération de "code raisonnablement efficace", et de "code raisonnablement lisible" incluent la génération de code tactiques qui prouvent une collection de théorèmes formant une théorie de types de données orientés objets d'un modèle dénotationnel : étant donné un modèle de classe UML/OCL, les preuves des propriétés pertinentes aux conversions, tests de types, constructeurs et sélecteurs sont traitées automatiquement. Cette fonctionnalité est similaire aux paquets de théories de types de données présents au sein d'autres prouveurs de la famille HOL, à l'exception que certaines motivations ont conduit ce travail présent à programmer des tactiques haut-niveaux en HOL lui-même. Ce travail prend en compte les plus récentes avancées du standard d'UML/OCL 2.5. Par conséquent, tous les types UML/OCL ainsi que les types logiques distinguent deux éléments d'exception différents : invalid (exception) et null (élément non-existant). Cela entraîne des conséquences sur les propriétés aussi bien logiques qu'algébriques des structures orientées objets résultant des modèles de classes. Étant donné que notre construction est réduite à une séquence d'extension conservative de théorie, notre approche peut garantir la correction logique du langage entier considéré, et fournit une méthodologie pour étendre formellement des langages à domaine spécifique. / Object-based and object-oriented specification languages (likeUML/OCL, JML, Spec#, or Eiffel) allow for the creation and destruction, casting and test for dynamic types of statically typed objects. On this basis, class invariants and operation contracts can be expressed; the latter represent the key elements of object-oriented specifications. A formal semantics of object-oriented data structures is complex: imprecise descriptions can often imply different interpretations in resulting tools. In this thesis we demonstrate how to turn a modern proof environment into a meta-tool for definition and analysis of formal semantics of object-oriented specification languages. Given a representation of a particular language embedded in Isabelle/HOL, we build for this language an extended Isabelle environment by using a particular method of code generation, which actually involves several variants of code generation. The result supports the asynchronous editing, type-checking, and formal deduction activities, all "inherited" from Isabelle. Following this method, we obtain an object-oriented modelling tool for textual UML/OCL. We also integrate certain idioms not necessarily present in UML/OCL --- in other words, we develop support for domain-specific dialects of UML/OCL. As a meta construction, we define a meta-model of a part of UML/OCL in HOL, a meta-model of a part of the Isabelle API in HOL, and a translation function between both in HOL. The meta-tool will then exploit two kinds of code generation to produce either fairly efficient code, or fairly readable code. Thus, this provides two animation modes to inspect in more detail the semantics of a language being embedded: by loading at a native speed its semantics, or just delay at another "meta"-level the previous experimentation for another type-checking time in Isabelle, be it for performance, testing or prototyping reasons. Note that generating "fairly efficient code", and "fairly readable code" include the generation of tactic code that proves a collection of theorems forming an object-oriented datatype theory from a denotational model: given a UML/OCL class model, the proof of the relevant properties for casts, type-tests, constructors and selectors are automatically processed. This functionality is similar to the datatype theory packages in other provers of the HOL family, except that some motivations have conducted the present work to program high-level tactics in HOL itself. This work takes into account the most recent developments of the UML/OCL 2.5 standard. Therefore, all UML/OCL types including the logic types distinguish two different exception elements: invalid (exception) and null (non-existing element). This has far-reaching consequences on both the logical and algebraic properties of object-oriented data structures resulting from class models. Since our construction is reduced to a sequence of conservative theory extensions, the approach can guarantee logical soundness for the entire considered language, and provides a methodology to soundly extend domain-specific languages.
9

Improvement of interconnection networks for clusters: direct-indirect hybrid topology and HoL-blocking reduction routing

Peñaranda Cebrián, Roberto 03 March 2018 (has links)
Nowadays, clusters of computers are used to solve computation intensive problems. These clusters take advantage of a large number of computing nodes to provide a high degree of parallelization. Interconnection networks are used to connect all these computing nodes. The interconnection network should be able to efficiently handle the traffic generated by this large number of nodes. Interconnection networks have different design parameters that define the behavior of the network. Two of them are the topology and the routing algorithm. The topology of a interconnection network defines how the different network elements are connected, while the routing algorithm determines the path that a packet must take from the source to the destination node. The most commonly used topologies typically follow a regular structure and can be classified into direct and indirect topologies, depending on how the different network elements are interconnected. On the other hand, routing algorithms can also be classified into two categories: deterministic and adaptive algorithms. To evaluate interconnection networks, metrics such as latency or network productivity are often used. Throughput refers to the traffic that the network is capable of accepting the network per time unit. On the other hand, latency is the time that a packet requires to reach its destination. This time can be divided into two parts. The first part is the time taken by the packet to reach its destination in the absence of network traffic. The second part is due to network congestion created by existing traffic. One of the effects of congestion is the so-called Head-of-Line blocking, where the packet at the head of a queue blocks, causing the remaining queued packets can not advance, although they could advance if they were at the head of the queue. Nowadays, there are other important factors to consider when interconnection networks are designed, such as cost and fault tolerance. On the one hand, a high performance is desirable, but without a disproportionate increase in cost. On the other hand, the fact of increasing the size of the network implies an increase in the network components, thus the probability of occurrence of a failure is higher. For this reason, having some fault tolerance mechanism is vital in current interconnection networks of large machines. Putting all in a nutshell, a good performance-cost ratio is required in the network, with a high level of fault-tolerance. This thesis focuses on two main objectives. The first objective is to combine the advantages of the direct and indirect topologies to create a new family of topologies with the best of both worlds. The main goal is the design of the new family of topologies capable of interconnecting a large number of nodes being able to get very good performance with a low cost hardware. The family of topologies proposed, that will be referred to as k-ary n-direct s-indirect, has a n dimensional structure where the k different nodes of a given dimension are interconnected by a small indirect topology of s stages. We will also focus on designing a deterministic and an adaptive routing algorithm for the family of topologies proposed. Finally we will focus on analyzing the fault tolerance in the proposed family of topologies. For this, the existing fault tolerance mechanism for similar topologies will be studied and a mechanism able to exploit the features of this new family will be designed. The second objective is to develop routing algorithms specially deigned to reduce the pernicious effect of Head-of-Line blocking, which may shoot up in systems with a high number of computing nodes. To avoid this effect, routing algorithms able of efficiently classifying the packets in the different available virtual channels are designed, thus preventing that the occurrence of a hot node (Hot-Spot) could saturate the network and affect the remaining network traffic. / Hoy en día, los clústers de computadores son usados para solucionar grandes problemas. Estos clústers aprovechan la gran cantidad de nodos de computación para ofrecer un alto grado de paralelización. Para conectar todos estos nodos de computación, se utilizan redes de interconexión de altas prestaciones capaces de manejar de forma eficiente el tráfico generado. Estas redes tienen diferentes parámetros de diseño que definen su comportamiento, de los cuales podríamos destacar dos: la topología y el algoritmo de encaminamiento. La topología de una red de interconexión define como se conectan sus componentes, mientras que el algoritmo de encaminamiento determina la ruta que un paquete debe tomar desde su origen hasta su destino. Las topologías más utilizadas suelen seguir una estructura regular y pueden ser clasificadas en directas e indirectas, dependiendo de cómo estén interconectados los diferentes elementos de la red. Por otro lado, los algoritmos de encaminamiento también pueden clasificarse en dos categorías: deterministas y adaptativos. Para evaluar estas redes se suelen utilizar medidas tales como la latencia o la productividad de la red. La productividad mide el tráfico que es capaz de aceptar la red por unidad de tiempo. La latencia mide el tiempo que utiliza un paquete para alcanzar su destino. Este tiempo se puede dividir en dos partes. La primera corresponde al tiempo utilizado por el paquete en alcanzar a su destino en ausencia de tráfico en la red. La segunda sería la debida a la congestión de la red creada por el tráfico existente. Uno de los efectos de la congestión es el denominado Head-of-Line blocking, donde el paquete que encabeza una cola se queda bloqueado, por lo que el resto de paquetes de la cola no pueden avanzar, aunque pudieran hacerlo si ellos encabezaran dicha cola. Otros factores a tomar en cuenta son el coste y la tolerancia a fallos. Las prestaciones deben mantenerse conforme aumentamos el tamaño de la red, pero sin un aumento prohibitivo en el coste. Además, el hecho de aumentar el tamaño de la red implica un aumento en el número de elementos de dicha red, aumentando la probabilidad de la aparición de un fallo. Por ello, es vital contar con algún mecanismo de tolerancia a fallos en las redes para los grandes supercomputadores actuales. En otras palabras, es de esperar una buena relación coste-prestaciones con un alto nivel de tolerancia a fallos. Esta tesis tiene dos objetivos principales. El primer objetivo combina las ventajas de las topologías directas e indirectas para crear una nueva familia de topologías con lo mejor de ambas. En concreto, nos centramos en el diseño de una nueva familia de topologías capaz de interconectar una gran cantidad de nodos siendo capaz de obtener muy buenas prestaciones con un bajo coste hardware. La familia de topologías propuesta, que hemos llamado k-ary n-direct s-indirect, tiene una estructura n-dimensional, donde los diferentes k nodos de una dimensión se conectan entre sí mediante una pequeña topología indirecta con s etapas. También diseñaremos un algoritmo de encaminamiento determinista y otro adaptativo para la familia de topologías propuesta. Finalmente, nos centraremos en estudiar la tolerancia a fallos para la familia de topologías propuesta. Para ello se estudiarán los mecanismos de tolerancia a fallos existentes en topologías similares y se diseñará un mecanismo capaz de aprovechar al máximo las características de esta nueva familia. El segundo objetivo consiste en el desarrollo de algoritmos de encaminamiento capaces de evitar el pernicioso efecto Head-of-Line blocking, lo cual puede aumentar rápidamente en sistemas con un gran número de nodos de computación. Para evitar este efecto se diseñarán algoritmos de encaminamiento capaces de clasificar de forma eficiente los paquetes en los diferentes canales virtuales disponibles, evitando así que la aparición de un punto caliente (Hot-Spot) sat / Hui en dia, els clústers de computadors són utilitzats per solucionar grans problemes computacionals. Aquests clústers aprofiten la gran quantitat de nodes de computació per a oferir un alt grau de paral·lelització. Per a connectar tots aquests nodes de computació, s'utilitzen xarxes d'interconnexió d'altes prestacions capaços de manejar de manera eficient el trànsit generat. Aquestes xarxes tenen diferents paràmetres de disseny que defineixen el seu comportament, dels quals podríem destacar dues: la topologia i l'algoritme d'encaminament. La topologia d'una xarxa d'interconnexió ens defineix com es connecten els seus components, mentre que l'algoritme d'encaminament determina la ruta que un paquet ha de prendre des del seu node origen fins al seu node destí. Les topologies més utilitzades solen seguir una estructura regular i poden ser classificades en directes i indirectes, depenent de com estiguen interconnectats els diferents elements de la xarxa. D'altra banda, els algoritmes d'encaminament també poden classificar-se en dues categories: deterministes i adaptatius. Per avaluar estes xarxes es solen utilitzar mesures com ara la latència o la productivitat de la xarxa. La productivitat mesura el trànsit que és capaç d'acceptar la xarxa per unitat de temps. La latència mesura el temps que utilitza un paquet per arribar al seu destí. Aquest temps es pot dividir en dues parts. La primera correspon al temps emprat pel paquet a aconseguir al seu destí en absència de trànsit a la xarxa. La segona part seria la deguda a la congestió de la xarxa creada per el trànsit existent. Un dels efectes de la congestió és l'anomenat Head-of-line blocking, on el paquet que encapçala una cua es queda bloquejat, de manera que la resta de paquets de la cua no poden avançar, encara que poguessen fer-ho si ells encapçalessen la dita cua. Altres factors a tenir en compte són el cost i la tolerància a fallades. Per tant, les prestacions s'han de mantenir d'acord augmentem la mida de la xarxa, però sense un augment prohibitiu en el cost. A més, el fet d'augmentar la mida de la xarxa implica un augment en el número de elements d'aquesta xarxa, de manera que la probabilitat de l'aparició d'una fallada és més gran. Per això, és vital comptar amb algun mecanisme de tolerància a fallades en les xarxes d'interconnexió per als gran supercomputadors actuals. En altres paraules, és d'esperar bona relació cost-prestacions amb una alta tolerància a fallades. Aquesta tesi té dos objectius principals. El primer objectiu combina les avantatges de les topologies directes i indirectes per a crear una nova família de topologies amb el millor dels dos mons. En concret, ens centrem en el disseny de una nova família de topologies capaç d'interconnectar una gran quantitat de nodes sent capaç d'obtenir molt bones prestacions amb un baix cost hardware. La família de topologies proposada, que hem nomenat k-ary n-direct s-indirect, té una estructura n-dimensional, on els diferents k nodes d'una dimensió se connecten entre si mitjançant una petita topologia indirecta amb s etapes. També dissenyarem un algoritme d'encaminament determinista i un altre adaptatiu per a la família de topologies proposta. Finalment, ens centrarem en estudiar la tolerància a fallades per a la família de topologies proposada. Per a això s'estudiaran els mecanismes de tolerància a fallades existents en topologies similars i es dissenyarà un mecanisme capaç d'aprofitar al màxim les característiques d'aquesta nova família. El segon objectiu consisteix en la creació d'algoritmes d'encaminament capaços d'evitar el perniciós efecte Head-of-line blocking que pot créixer ràpidament amb un gran número de nodes de computació. Per a evitar aquest efecte es dissenyaran algoritmes d'encaminament capaços de classificar de forma eficient els paquets en els diferents canals virtuals disponibles, evitant així que l'aparició d'un punt calent ( / Peñaranda Cebrián, R. (2017). Improvement of interconnection networks for clusters: direct-indirect hybrid topology and HoL-blocking reduction routing [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/79550 / TESIS
10

Test generation and animation based on object-oriented specifications / Génération de tests et animation à partir de spécifications orientées objet

Krieger, Matthias 09 December 2011 (has links)
L'objectif de cette thèse est l'assistance à la génération de tests et à l'animation de spécifications orientées objet. Nous cherchons en particulier à profiter de l'état de l'art des techniques de résolution de satisfaisabilité en utilisant une représentation appropriée des données orientées objet. Alors que la génération automatique de cas de tests recherche un large ensemble de valeurs à fournir en entrée d'une application, l’animation de spécifications effectue les calculs qui sont conformes à une spécification à partir de valeurs fournies par l'utilisateur. L'animation est une technique importante pour la validation des spécifications.Comme fondement de ce travail, nous présentons des clarifications et une formalisation partielle du langage de spécification OCL (Object Constraint Language) ainsi que quelques extensions, afin de permettre la génération de tests et l'animation à partir de spécifications OCL.Pour la génération de tests, nous avons implémenté plusieurs améliorations à HOL-TestGen, outil basé sur le démonstrateur de théorème Isabelle, qui engendre des tests à partir de spécifications en Logique d’Ordre Supérieure (Higher-Order Logic ou HOL). Nous montrons comment des solveurs SMT peuvent être utilisés pour résoudre différents types de contraintes en HOL et nous présentons une approche modulaire de raisonnement par cas pour dériver des cas de tests. Cette dernière approche facilite l'introduction de règles de decomposition par cas qui sont adaptées aux spécifications orientées objet.Pour l'animation de spécifications, nous avons développé OCLexec, outil d'animation de spécifications en OCL. A partir de contrats de fonctions OCLexec produit les implémentations Java correspondantes qui appellent un solveur de contraintes SMT lors de leur exécution. / The goal of this thesis is the development of support for test generation and animation based on object-oriented specifications. We aim particularly to take advantage of state-of-the-art satisfiability solving techniques by using an appropriate representation of object-oriented data. While automated test generation seeks a large set of data to execute an implementation on, animation performs computations that comply with a specification based on user-provided input data. Animation is a valuable technique for validating specifications.As a foundation of this work, we present clarifications and a partial formalization of the Object Constraint Language (OCL) as well as some extensions in order to allow for test generation and animation based on OCL specifications.For test generation, we have implemented several enhancements to HOL-TestGen, a tool built on top of the Isabelle theorem proving system that generates tests from specifications in Higher-Order Logic (HOL). We show how SMT solvers can be used to solve various types of constraints in HOL and present a modular approach to case splitting for deriving test cases. The latter facilitates the introduction of splitting rules that are tailored to object-oriented specifications.For animation, we implemented the tool OCLexec for animating OCL specifications. OCLexec generates from operation contracts corresponding Java implementations that call an SMT-based constraint solver at runtime.

Page generated in 0.0254 seconds