Pour s'assurer que les personnes âgées soient en sécurité au domicile, le projet INOVUS s'intéresse aux risques liés à l'utilisation de la cuisinière. Dans le cadre de ce projet, les travaux de M.Sc. présentés dans ce mémoire se concentrent sur la perspective logicielle de la détection et de la prévention des risques physiques pour la personne, lors de la réalisation de tâches utilisant la cuisinière. Dans un premier temps, une revue des risques à domicile recensés dans la littérature a permis de définir la couverture nécessaire à une telle solution. Certaines situations dangereuses ont ensuite été sélectionnées pour définir un modèle de solution satisfaisant. Le développement d'une solution de sécurité pour la personne entraîne des contraintes de fiabilité de très haut niveau pour la technologie produite.Pour répondre à ce besoin, la proposition de ces travaux de M.Sc. est l'utilisation de spécifications formelles. Ces outils permettent d'obtenir un plus haut degré de fiabilité de logiciels. En se basant sur ces outils, un modèle de solution a été élaboré pour le projet INOVUS, et ce à l'aide du vérificateur de modèle ALLOY. Enfin, une implémentation en Java de ce prototype a été réalisée afin d'évaluer les résultats de détection des situations dangereuses. Ce prototype permet alors à la fois de valider l'approche de développement choisie, ainsi que d'établir une preuve de concept d'une telle solution de sécurité.

En analyse de risques, les arbres d’attaque sont utilisés pour évaluer les menaces sur un système. Les méthodes formelles permettent leur analyse quantitative et leur synthèse, mais les propriétés exprimant la qualité des arbres d’attaque par rapport au système n’ont pas été formalisées. Dans ce document, nous définissons un nouveau cadre formel pour les arbres d’attaque prenant en compte un modèle opérationnel du système, et dotant les arbres d’une sémantique de chemins. Nous définissons les propriétés de correction des raffinements, et étudions leurs complexités. A partir d’une attaque optimale dans un modèle de système quantitatif, nous guidons la conception d’un arbre d’attaque, en indiquant ses feuilles qui contribuent à l’attaque optimale considérée. / In risk analysis, attack trees are used to assess threats to a system. Formal methods allow for their quantitative analysis and synthesis, but the properties expressing the quality of the attack trees with respect to the system have not been formalized. In this document, we define a new formal framework for attack trees that takes an operational model of the system into account, and provides the trees with a path semantics. We define the correctness properties of refinements, and study their computational complexity. Given an optimal attack in a quantitative system model, we guide the design of a attack tree, indicating its leaves that contribute to considered the optimal attack.

Les voies de signalisation canoniques traditionnelles aident à comprendre l'ensemble des processus de signalisation à l'intérieur de la cellule. Les données phosphoprotéomiques à grande échelle donnent un aperçu des altérations entre différentes protéines dans différents contextes expérimentaux. Notre objectif est de combiner les réseaux de signalisation traditionnels avec des données de séries temporelles phosphoprotéomiques complexes afin de démêler les réseaux de signalisation spécifiques aux cellules. Côté application, nous appliquons et améliorons une méthode de séries temporelles caspo conçue pour intégrer des données phosphoprotéomiques de séries temporelles dans des réseaux de signalisation de protéines. Nous utilisons une étude de cas réel à grande échelle tirée du défi HPN-DREAM BreastCancer. Nous déduisons une famille de modèles booléens à partir de données de séries temporelles de perturbations multiples de quatre lignées cellulaires de cancer du sein, compte tenu d'un réseau de signalisation protéique antérieur. Les résultats obtenus sont comparables aux équipes les plus performantes du challenge HPN-DREAM. Nous avons découvert que les modèles similaires sont regroupés dans l'espace de solutions. Du côté informatique, nous avons amélioré la méthode pour découvrir diverses solutions et améliorer le temps de calcul. / Traditional canonical signaling pathways help to understand overall signaling processes inside the cell. Large scale phosphoproteomic data provide insight into alterations among different proteins under different experimental settings. Our goal is to combine the traditional signaling networks with complex phosphoproteomic time-series data in order to unravel cell specific signaling networks. On the application side, we apply and improve a caspo time series method conceived to integrate time series phosphoproteomic data into protein signaling networks. We use a large-scale real case study from the HPN-DREAM BreastCancer challenge. We infer a family of Boolean models from multiple perturbation time series data of four breast cancer cell lines given a prior protein signaling network. The obtained results are comparable to the top performing teams of the HPN-DREAM challenge. We also discovered that the similar models are clustered to getherin the solutions space. On the computational side, we improved the method to discover diverse solutions and improve the computational time.

Le contrôle de l'information émise par un système a vu son utilité grandir avec la multiplication des systèmes communicants. Ce contrôle peut être réalisé par exemple pour révéler une information du système, ou au contraire pour en dissimuler une. Le diagnostic notamment cherche à déterminer, grâce à l'observation du système, si une faute a eu lieu au sein de celui-ci. Dans cette thèse, nous établissons des bases formelles à l'analyse des problèmes du diagnostic pour des modèles stochastiques. Nous étudions ensuite ces problèmes dans plusieurs cadres (fini/infini, passif/actif). / The control of the information given by a system has seen increasing importance recently with the multiplication of communicating systems. This control can be used in order to disclose an information of the system, or, oppositely, to hide one. Diagnosis for instance tries to determine from the observation produced by the system whether a fault occurred within it or not. In this PhD, we establish formal foundations to the analysis of the diagnosis problems for stochastic models. We then study these problems in multiple framework (finite/infinite, passive/active).

Ce travail s'inscrit dans le cadre de la vérification formelle de programmes. La vérification de modèle permet de s'assurer qu'une propriété est vérifiée par le modèle du système. Cette thèse étudie la vérification paramétrée de réseaux composés d'un nombre non borné de processus identiques où le nombre de processus est considéré comme un paramètre. Concernant les réseaux de protocoles probabilistes temporisés nous montrons que les problèmes de l'accessibilité et de synchronisation sont indécidables pour des topologies de communication en cliques. Cependant, en considérant des pertes et créations probabiliste de processus ces problèmes deviennent décidables. Pour ce qui est des réseaux dans lequel les messages n'atteignent qu'une sous partie des composants choisie de manière non-déterministe, nous prouvons que le problème de l'accessibilité paramétrée est décidable grâce à une réduction à un nouveau modèle de jeux à deux joueurs distribué pour lequel nous montrons que l'on peut décider de l'existence d'une stratégie gagnante en coNP. Finalement, nous considérons des stratégies locales qui permettent d'assurer que les processus effectuent leurs choix non-déterministes uniquement par rapport a leur connaissance locale du système. Sous cette hypothèse de stratégies locales, nous prouvons que les problèmes de l'accessibilité et de synchronisation paramétrées sont NP-complet. / This thesis deals with formal verification of distributed systems. Model checking is a technique for verifying that the model of a system under study fulfills a given property. This PhD investigates the parameterized verification of networks composed of many identical processes for which the number of processes is the parameter. Considering networks of probabilistic timed protocols, we show that the parameterized reachability and synchronization problems are undecidable when the communication topology is a clique. However, assuming probabilistic creation and deletion of processes, the problems become decidable. Regarding selective networks, where the messages only reach a subset of the components, we show decidability of the parameterized reachability problem thanks to reduction to a new model of distributed two-player games for which we prove decidability in coNP of the game problem. Finally, we consider local strategies that enforce all processes to resolve the non-determinism only according to their own local knowledge. Under this assumption of local strategy, we were able to show that the parameterized reachability and synchronization problems are NP-complete.

Le présent mémoire propose une investigation approfondie de l’analyseur Alloy afin de juger son adaptabilité en tant que vérificateur de modèles. Dans un premier temps, l’étude dresse un tableau comparatif de six vérificateurs de modèles, incluant Alloy, afin de déterminer lequel d’entre eux est le plus apte à résoudre les problématiques de sécurité fonctionnelle posées par les systèmes d’information. En conclusion de cette première phase, Alloy émerge comme l’un des analyseurs les plus performants pour vérifier les modèles sur lesquels se fondent les systèmes d’information. Dans un second temps, et sur la base des problématiques rencontrées au cours de cette première phase, l’étude rapporte une série d’idiomes pour, d’une part, présenter une manière optimisée de spécifier des traces et, d’autre part, trouver des recours afin de contourner les limitations imposées par Alloy. À ces fins, le mémoire propose deux nouveaux cas d’espèce, ceux d’une cuisinière intelligente et d’une boîte noire, afin de déterminer si oui ou non l’analyseur est capable de gérer les systèmes dynamiques possédant de nombreuses entités avec autant d’efficacité que les systèmes qui en possèdent moins. En conclusion, le mémoire rapporte que Alloy est un bon outil pour vérifier des systèmes dynamiques mais que sa version récente, DynAlloy, peut être encore mieux adapté pour le faire puisque précisément conçu pour faire face aux spécificités de ce type de système. Le mémoire s’achève sur une présentation sommaire de ce dernier outil.

Un large éventail de nouvelles applications met l’accent sur la nécessité de disposer de modèles de processus métier capables de manipuler des données imprécises ou incertaines. Du fait de la présence de données probabilistes, les comportements externes de tels processus métier sont non markoviens. Peu de travaux dans la littérature se sont intéressés à la vérification de tels systèmes. Ce travail de thèse étudie les questions de modélisation et d’analyse de ce type de processus métier. Il utilise comme modèle formel pour décrire les comportements des processus métier un système de transitions étiquetées dans lequel les transitions sont gardées par des conditions définies sur une base de données probabiliste. Il propose ensuite une approche de décomposition de ces processus qui permet de tester la relation de simulation entre processus dans ce contexte. Une analyse de complexité révèle que le problème de test de simulation est dans 2-EXPTIME, et qu’il est EXPTIME-difficile en termes de complexité d’expression, alors que du point de vue de la complexité en termes des données, il n’engendre pas de surcoût supplémentaire par rapport au coût de l’évaluation de requêtes booléennes sur des bases de données probabilistes. L’approche proposée est ensuite étendue pour permettre la vérification de propriétés exprimées dans les logiques P-LTL et P-CTL. Finalement, un prototype, nommé ‘PRODUS’, a été implémenté et utilisé dans le cadre d’une application liée aux systèmes d’information géographiques pour montrer la faisabilité de l’approche proposée. / There is a wide range of new applications that stress the need for business process models that are able to handle imprecise data. This thesis studies the underlying modelling and analysis issues. It uses as formal model to describe process behaviours a labelled transitions system in which transitions are guarded by conditions defined over a probabilistic database. To tackle verification problems, we decompose this model to a set of traditional automata associated with probabilities named as world-partition automata. Next, this thesis presents an approach for testing probabilistic simulation preorder in this context. A complexity analysis reveals that the problem is in 2-exptime, and is exptime-hard, w.r.t. expression complexity while it matches probabilistic query evaluation w.r.t. data-complexity. Then P-LTL and P-CTL model checking methods are studied to verify this model. In this context, the complexity of P-LTL and P-CTL model checking is in exptime. Finally a prototype called ”PRODUS” which is a modeling and verification tool is introduced and we model a realistic scenario in the domain of GIS (graphical information system) by using our approach.

L'objectif principal de cette thèse est de proposer les méthodes permettant d'obtenir le délai de transmission de bout en bout pire cas exact d'un réseau AFDX. Actuellement, seules des bornes supérieures pessimistes peuvent être calculées en utilisant les approches de type Calcul Réseau ou par Trajectoires. Pour cet objectif, différentes approches et outils existent et ont été analysées dans le contexte de cette thèse. Cette analyse a mis en évidence le besoin de nouvelles approches. Dans un premier temps, la vérification de modèle a été explorée. Les automates temporisés et les outils de verification ayant fait leur preuve dans le domaine temps réel ont été utilisés. Ensuite, une technique de simulation exhaustive a été utilisée pour obtenir les délais de communication pire cas exacts. Pour ce faire, des méthodes de réduction de séquences ont été définies et un outil a été développé. Ces méthodes ont été appliquées à une configuration réelle du réseau AFDX, nous permettant ainsi de valider notre travail sur une configuration de taille industrielle du réseau AFDX telle que celle embarquée à bord des avions Airbus A380. The main objective of this thesis is to provide methodologies for finding exact worst case end to end communication delays of AFDX network. Presently, only pessimistic upper bounds of these delays can be calculated by using Network Calculus and Trajectory approach. To achieve this goal, different existing tools and approaches have been analyzed in the context of this thesis. Based on this analysis, it is deemed necessary to develop new approaches and algorithms. First, Model checking with existing well established real time model checking tools are explored, using timed automata. Then, exhaustive simulation technique is used with newly developed algorithms and their software implementation in order to find exact worst case communication delays of AFDX network. All this research work has been applied on real life implementation of AFDX network, allowing us to validate our research work on industrial scale configuration of AFDX network such as used on Airbus A380 aircraft. / The main objective of this thesis is to provide methodologies for finding exact worst case end to end communication delays of AFDX network. Presently, only pessimistic upper bounds of these delays can be calculated by using Network Calculus and Trajectory approach. To achieve this goal, different existing tools and approaches have been analyzed in the context of this thesis. Based on this analysis, it is deemed necessary to develop new approaches and algorithms. First, Model checking with existing well established real time model checking tools are explored, using timed automata. Then, exhaustive simulation technique is used with newly developed algorithms and their software implementation in order to find exact worst case communication delays of AFDX network. All this research work has been applied on real life implementation of AFDX network, allowing us to validate our research work on industrial scale configuration of AFDX network such as used on Airbus A380 aircraft.

L’Ingénierie Dirigée par les Modèles (IDM) est une approche populaire pour le développement logiciel qui favorise l’utilisation de modèles au sein des processus de développement. Dans un processus de développement logiciel base sur l’IDM, le logiciel est développé en créant des modèles qui sont transformés successivement en d’autres modèles et éventuellement en code source. Quand l’IDM est utilisée pour le développement de logiciels complexes, la complexité des modèles et des transformations de modèles augmente, risquant d’affecter la fiabilité du processus de développement logiciel ainsi que le logiciel en résultant.Traditionnellement, la fiabilité des logiciels est assurée au moyen d’approches pour la vérification de logiciels, basées sur l’utilisation de techniques pour l’analyse formelle de systèmes et d’approches pour le test de logiciels. Pour assurer la fiabilité du processus IDM de développement logiciel, ces techniques ont en quelque sorte été adaptées pour essayer de s’assurer la correction des modèles et des transformations de modèles associées. L’objectif de cette thèse est de fournir de nouveaux mécanismes améliorant les approches existantes pour la vérification de modèles statiques, et d’analyser comment ces approches peuvent s’avérer utiles lors du test des transformations de modèles. / Model-Driven Engineering (MDE) is a popular approach to the development of software which promotes the use of models as first-Class citizens in the software development process. In a MDE-Based software development process, software is developed by creating models to be successively transformed into another models and eventually into the software source code. When MDE is applied to the development of complex software systems, the complexity of models and model transformations increase, thus risking both, the reliability of the software development process and the soundness of the resulting software. Traditionally, ensuring software correctness and absence of errors has been addressed by means of software verification approaches, based on the utilization of formal analysis techniques, and software testing approaches. In order to ensure the reliability of MDE-Based software development processes, these techniques have some how been adapted to try to ensure correctness of models and model transformations. The objective of this thesis is to provide new mechanisms to improve the landscape of approaches devoted to the verification of static models, and analyze how these static model verification approaches can be of assistance at the time of testing model transformations.

Les logiciels sont devenus une partie importante de notre vie quotidienne, car ils sont maintenant utilisés dans de nombreux périphériques hétérogènes, tels que nos téléphones, nos voitures, nos appareils ménagers, etc. Ces périphériques sont parsemés d’un certain nombre de logiciels intégrés, chacun gérant une tâche spécifique. Ces logiciels intégrés sont conçus pour fonctionner à l’intérieur de systèmes plus vastes avec un matériel varié et hétérogène et des ressources limitées. L'utilisation de logiciels embarqués est motivée par la flexibilité et la simplicité que ces logiciels peuvent garantir, ainsi que par la réduction des coûts. Les Cyber-Physical System (CPS) sont des logiciels utilisés pour contrôler des systèmes physiques. Les CPS sont souvent intégrés et s'exécutent en temps réel, ce qui signifie qu'ils doivent réagir aux événements externes. Un CPS complexe peut contenir de nombreux systèmes en temps réel. Le fait que ces systèmes puissent être utilisés dans des domaines critiques tels que la médecine ou les transports exige un haut niveau de sécurité pour ces systèmes. Les systèmes temps réel (RTS), par définition, sont des systèmes informatiques de traitement qui doivent répondre à des entrées générées de manière externe. Ils sont appelés temps réel car leur réponse doit respecter des contraintes de temps strictes. Par conséquent, l'exactitude de ces systèmes ne dépend pas seulement de l'exactitude des résultats de leur traitement, mais également du moment auquel ces résultats sont donnés. Le principal problème lié à l'utilisation de systèmes temps réel est la difficulté de vérifier leurs contraintes de synchronisation. Un moyen de vérifier les contraintes de temps peut consister à utiliser la théorie de la planification, stratégie utilisée pour partager les ressources système entre ses différents composants. Outre les contraintes de temps, il convient de prendre en compte d'autres contraintes, telles que la consommation d'énergie ou la sécurité. Plusieurs méthodes de vérification ont été utilisées au cours des dernières années, mais avec la complexité croissante des logiciels embarqués, ces méthodes atteignent leurs limites. C'est pourquoi les chercheurs se concentrent maintenant sur la recherche de nouvelles méthodes et de nouveaux formalismes capables de vérifier l'exactitude des systèmes les plus complexes. Aujourd'hui, une classe de méthodes de vérification bien utilisées est les techniques basées sur des modèles. Ces techniques décrivent le comportement du système considéré à l'aide de formalismes mathématiques, puis, à l'aide de méthodes appropriées, permettent d'évaluer l'efficacité du système par rapport à un ensemble de propriétés. Dans ce manuscrit, nous nous concentrons sur l'utilisation de techniques basées sur des modèles pour développer de nouvelles techniques de planification afin d'analyser et de valider la satisfiabilité d'un certain nombre de propriétés sur des systèmes temps réel. L'idée principale est d'exploiter la théorie de l'ordonnancement pour proposer ces nouvelles techniques. Pour ce faire, nous proposons un certain nombre de nouveaux modèles afin de vérifier la satisfiabilité d'un certain nombre de propriétés telles que l'ordonnancement, la consommation d'énergie ou la fuite d'informations. / Software’s become an important part of our daily life as they are now used in many heterogeneous devices, such as our phones, our cars, our home appliances … etc. These devices are dotted with a number of embedded software’s, each handling a specific task. These embedded software’s are designed to run inside larger systems with various and heterogeneous hardware and limited resources. The use of embedded software is motivated by the flexibility and the simplicity that these software can guarantee, and to minimize the cost. Cyber-Physical System (CPS) are software used to control physical systems. CPS are often embedded and run in real-time, which means that they must react to external events. A complex CPS can contains many real-time systems. The fact that these systems can be used in critical domains like medicine or transport requires a high level of safety for these systems. Real-Time Systems (RTS) by definition are processing information systems that have to respond to externally generated inputs, and they are called real-time because their response must respect a strict timing constraints. Therefore, the correctness of these systems does not depend only on the correctness of their treatment results, but it also depends on the timings at which these results are given. The main problem with using real-time systems is the difficulty to verify their timing constraints. A way to verify timing constraints can be to use Scheduling theory which is a strategy used in order to share the system resources between its different components. In addition to the timing constraints, other constraints should be taken in consideration, like energy consumption or security. Several verification methods have been used in the last years, but with the increasing complexity of the embedded software these methods reach their limitation. That is why researchers are now focusing their works on finding new methods and formalisms capable of verifying the correctness of the most complex systems. Today, a well-used class of verification methods are model-based techniques. These techniques describe the behavior of the system under consideration using mathematical formalisms, then using appropriate methods they give the possibility to evaluate the correctness of the system with respect to a set of properties. In this manuscript we focus on using model-based techniques to develop new scheduling techniques in order to analyze and validate the satisfiability of a number of properties on real-time systems. The main idea is to exploit scheduling theory to propose these new techniques. To do that, we propose a number of new models in order to verify the satisfiability of a number of properties as schedulability, energy consumption or information leakage.