Freiburg (Breisgau), University, Diss., 2001.

This thesis proposes a novel approach for the synthesis of delays for timed systems, in particular in the framework oftimed automata, a model for verifying real-time systems. Our approach relies on the following inverse method: given a reference valuation of the parameters, we synthesize a constraint on the parameters, guaranteeing the same timeabstract linear behavior as for the reference valuation. This gives a criterion of robustness to the system. By iterating this inverse method on various points of a bounded parameter domain, we are then able to partition the parametric space into good and bad zones, with respect to a given property one wants to verify. This gives a behavioral cartography of the system. This method extended to probabilistic systems allows to preserve minimum and maximum probabilities of reachability properties. We also present variants of the inverse method for directed weighted graphs and Markov Decision Processes. Several prototypes have been implemented; in particular, IMITATOR II implements the inverse method and the cartography for timed automata. It allowed us to synthesize parameter values for several case studies such as an abstract model of a memory circuit sold by the chipset manufacturer ST-Microelectronics, and various communication protocols.

Univ., Diss.--Saarbrücken, 2007.

Stuttgart, Univ., Studienarbeit, 2007.

Stuttgart, Univ., Diss., 2006.

Berlin, Techn. Univ., Diss., 2003. / Computerdatei im Fernzugriff.

Freiburg (Breisgau), University, Diss., 2004.

Cette thèse présente un schéma formel et efficace pour la vérification de systèmes temps-réel. Ce schéma repose sur la combinaison par abstraction de techniques déductives et de model checking, et cette combinaison permet de contourner les limites de chacune de ces techniques. La méthode utilise le raffinement itératif abstrait (IAR) pour le calcul d'abstractions finies. Etant donné un système de transitions et un ensemble fini de prédicats, la méthode détermine une abstraction booléenne dont les états correspondent à des ensembles de prédicats. La correction de l'abstraction par rapport au système d'origine est garantie en établissant un ensemble de conditions de vérification, issues de la procédure IAR. Ces conditions sont à démontrer à l'aide d'un prouveur de théorèmes. Les propriétés de sûreté et de vivacité sont ensuite vérifiées par rapport au modèle abstrait. La procédure IAR termine lorsque toutes les conditions sont vérifiées. Dans le cas contraire, une analyse plus fine détermine si le modèle abstrait doit être affiné en considérant davantage de prédicats. Nous identifions une classe de diagrammes de prédicats appelés PDT (predicate diagram for timed system) qui décrivent l'abstraction et qui peuvent être utilisés pour la vérification de systèmes temporisés et paramétrés. / This thesis provides an efficient formal scheme for the tool-supported real-time system verification by combination of abstraction-based deductive and model checking techniques in order to handle the limitations of the applied verification techniques. This method is based on IAR (Iterative Abstract Refinement) to compute finite state abstractions. Given a transition system and a finite set of predicates, this method determines a finite abstraction, where each state of the abstract state space is a true assignment to the abstraction predicates. A theorem prover can be used to verify that the finite abstract model is a correct abstraction of a given system by checking conformance between an abstract and a concrete model by establishing/proving that a set of verification conditions are obtained during the IAR procedure. Then the safety/liveness properties are checked over the abstract model. If the verification condition holds successfully, IAR terminates its procedure. Otherwise more analysis is applied to identify if the abstract model needs to be more precise by adding extra predicates. As abstraction form, we adopt a class of predicate diagrams and define a variant of predicate diagram PDT (Predicate Diagram for Timed systems) that can be used to verify real-time and parameterized systems.

Le formalisme des réseaux de Petri hybrides fonctionnels, notés HFPN pour Hybrid Functional Petri Nets en anglais, a démontré sa capacité à simuler les systèmes biologiques. L’inconvénient d’un formalisme aussi expressif est la difficulté d’exécuter des vérifications de propriétés dynamiques. Dans cette thèse, nous proposons une procédure de model-checking pour les réseaux de Petri hybrides temporisés, notés THPN pour Timed Hybrid Petri Nets en anglais, une sous-classe des HFPN. Cette procédure est basée sur la traduction du modèle THPN et de la propriété étudiée en automates temps-réel. Ceci est alors appliqué pour modéliser les régulations responsables de la métamorphose amphibienne. / The formalism of Hybrid Functional Petri Nets (HFPN) has proved its convenience for simulating biological systems. The drawback of the noticeable expressiveness of HFPN is the difficulty to perform formal verifications of dynamical properties. In this thesis, we propose a model-checking procedure for Timed Hybrid Petri Nets (THPN), a sub-class of HFPN. This procedure is based on the translation of the THPN model and of the studied property into real-time automata. It is applied to model regulations responsible for amphibian metamorphosis.

Les logiciels multi-partis sont des applications distribuées sur le web qui mettent en oeuvre des fonctions collaboratives. Ces applications sont les principales cibles des attaquants qui exploitent des vulnérabilités logicielles dans le cadre d'activités malveillantes. Récemment, un type moins connu de vulnérabilité, les anomalies logiques, a attiré l'attention des chercheurs. Sur la base d'informations tirées de la documentation des applications, il est possible d'appliquer deux techniques de test: la vérification du modèle, autrement appelé ``model checking'', et les tests de sécurité de type ``boîte noire''. Le champs d'application du model checking ne prend pas en suffisamment en compte les implémentations actuelles, tandis que les tests de type boîte noire ne sont pas assez sophistiqués pour découvrir les vulnérabilités logique. Dans cette thèse, nous présentons deux techniques d'analyse modernes visant à résoudre les inconvénients de l'état de l'art. Pour commencer, nous présentons la vérification de deux protocoles de sécurité utilisant la technique du model checking. Ensuite, nous nous concentrons sur l'extension du model checking pour soutenir les tests automatisés d'implémentations. La seconde technique consiste en une analyse boîte noire qui combine l'inférence du modèle, l'extraction du processus et du flot de donnée, ainsi qu'une génération de tests basés sur les modèles d'attaque d'une application. En conclusion, nous discutons de l'application de techniques développées au cours de cette thèse sur des applications issues d'un contexte industrielle. / Multi-party business applications are distributed computer programs implementing collaborative business functions. These applications are one of the main target of attackers who exploit vulnerabilities in order to perform malicious activities. The most prevalent classes of vulnerabilities are the consequence of insufficient validation of the user-provided input. However, the less-known class of logic vulnerabilities recently attracted the attention of researcher. According to the availability of software documentation, two testing techniques can be used: design verification via model checking, and black-box security testing. However, the former offers no support to test real implementations and the latter lacks the sophistication to detect logic flaws. In this thesis, we present two novel security testing techniques to detect logic flaws in multi-party business applicatons that tackle the shortcomings of the existing techniques. First, we present the verification via model checking of two security protocols. We then address the challenge of extending the results of the model checker to automatically test protocol implementations. Second, we present a novel black-box security testing technique that combines model inference, extraction of workflow and data flow patterns, and an attack pattern-based test case generation algorithm. Finally, we discuss the application of the technique developed in this thesis in an industrial setting. We used these techniques to discover previously-unknown design errors in SAML SSO and OpenID protocols, and ten logic vulnerabilities in eCommerce applications allowing an attacker to pay less or shop for free.