A formal method for attack modelling and detection

This paper presents a formal methodology for attack modeling and detection for networks. Our approach has three phases. First, we extend the basic attack tree approach 1 to capture (i) the temporal dependencies between components, and (ii) the expiration of an attack. Second, using the enhanced attack trees (EAT) we build a tree automaton that accepts a sequence of actions from input stream if there is a traverse of an attack tree from leaves to the root node. Finally, we show how to construct an enhanced parallel automaton (EPA) that has each tree automaton as a subroutine and can process the input stream by considering multiple trees simultaneously. As a case study, we show how to represent the attacks in IEEE 802.11 and construct an EPA for it.

Formal analysis of card-based payment systems in mobile devices

To provide card holder authentication while they are conducting an electronic transaction using mobile devices, VISA and MasterCard independently proposed two electronic payment protocols: Visa 3D Secure and MasterCard Secure Code. The protocols use pre-registered passwords to provide card holder authentication and Secure Socket Layer/ Transport Layer Security (SSL/TLS) for data confidentiality over wired networks and Wireless Transport Layer Security (WTLS) between a wireless device and a Wireless Application Protocol (WAP) gateway. The paper presents our analysis of security properties in the proposed protocols using formal method tools: Casper and FDR2. We also highlight issues concerning payment security in the proposed protocols.

Desenvolvimento formal de aplicações para smartcards

Smart card applications represent a growing market. Usually this kind of application manipulate and store critical information that requires some level of security, such as financial or confidential information. The quality and trustworthiness of smart card software can be improved through a rigorous development process that embraces formal techniques of software engineering. In this work we propose the BSmart method, a specialization of the B formal method dedicated to the development of smart card Java Card applications. The method describes how a Java Card application can be generated from a B refinement process of its formal abstract specification. The development is supported by a set of tools, which automates the generation of some required refinements and the translation to Java Card client (host) and server (applet) applications. With respect to verification, the method development process was formalized and verified in the B method, using the Atelier B tool [Cle12a]. We emphasize that the Java Card application is translated from the last stage of refinement, named implementation. This translation process was specified in ASF+SDF [BKV08], describing the grammar of both languages (SDF) and the code transformations through rewrite rules (ASF). This specification was an important support during the translator development and contributes to the tool documentation. We also emphasize the KitSmart library [Dut06, San12], an essential component of BSmart, containing models of all 93 classes/interfaces of Java Card API 2:2:2, of Java/Java Card data types and machines that can be useful for the specifier, but are not part of the standard Java Card library. In other to validate the method, its tool support and the KitSmart, we developed an electronic passport application following the BSmart method. We believe that the results reached in this work contribute to Java Card development, allowing the generation of complete (client and server components), and less subject to errors, Java Card applications.

A formal methodology for the verification of concurrent systems

There is an increasing emphasis on the use of software to control safety critical plants for a wide area of applications. The importance of ensuring the correct operation of such potentially hazardous systems points to an emphasis on the verification of the system relative to a suitably secure specification. However, the process of verification is often made more complex by the concurrency and real-time considerations which are inherent in many applications. A response to this is the use of formal methods for the specification and verification of safety critical control systems. These provide a mathematical representation of a system which permits reasoning about its properties. This thesis investigates the use of the formal method Communicating Sequential Processes (CSP) for the verification of a safety critical control application. CSP is a discrete event based process algebra which has a compositional axiomatic semantics that supports verification by formal proof. The application is an industrial case study which concerns the concurrent control of a real-time high speed mechanism. It is seen from the case study that the axiomatic verification method employed is complex. It requires the user to have a relatively comprehensive understanding of the nature of the proof system and the application. By making a series of observations the thesis notes that CSP possesses the scope to support a more procedural approach to verification in the form of testing. This thesis investigates the technique of testing and proposes the method of Ideal Test Sets. By exploiting the underlying structure of the CSP semantic model it is shown that for certain processes and specifications the obligation of verification can be reduced to that of testing the specification over a finite subset of the behaviours of the process.

Formal Modeling and Analysis Techniques for High Level Petri Nets

Petri Nets are a formal, graphical and executable modeling technique for the specification and analysis of concurrent and distributed systems and have been widely applied in computer science and many other engineering disciplines. Low level Petri nets are simple and useful for modeling control flows but not powerful enough to define data and system functionality. High level Petri nets (HLPNs) have been developed to support data and functionality definitions, such as using complex structured data as tokens and algebraic expressions as transition formulas. Compared to low level Petri nets, HLPNs result in compact system models that are easier to be understood. Therefore, HLPNs are more useful in modeling complex systems. There are two issues in using HLPNs - modeling and analysis. Modeling concerns the abstracting and representing the systems under consideration using HLPNs, and analysis deals with effective ways study the behaviors and properties of the resulting HLPN models. In this dissertation, several modeling and analysis techniques for HLPNs are studied, which are integrated into a framework that is supported by a tool. For modeling, this framework integrates two formal languages: a type of HLPNs called Predicate Transition Net (PrT Net) is used to model a system's behavior and a first-order linear time temporal logic (FOLTL) to specify the system's properties. The main contribution of this dissertation with regard to modeling is to develop a software tool to support the formal modeling capabilities in this framework. For analysis, this framework combines three complementary techniques, simulation, explicit state model checking and bounded model checking (BMC). Simulation is a straightforward and speedy method, but only covers some execution paths in a HLPN model. Explicit state model checking covers all the execution paths but suffers from the state explosion problem. BMC is a tradeoff as it provides a certain level of coverage while more efficient than explicit state model checking. The main contribution of this dissertation with regard to analysis is adapting BMC to analyze HLPN models and integrating the three complementary analysis techniques in a software tool to support the formal analysis capabilities in this framework. The SAMTools developed for this framework in this dissertation integrates three tools: PIPE+ for HLPNs behavioral modeling and simulation, SAMAT for hierarchical structural modeling and property specification, and PIPE+Verifier for behavioral verification.

Modeling and Verification of Privacy Enhancing Protocols

Privacy enhancing protocols (PEPs) are a family of protocols that allow secure exchange and management of sensitive user information. They are important in preserving users’ privacy in today’s open environment. Proof of the correctness of PEPs is necessary before they can be deployed. However, the traditional provable security approach, though well established for verifying cryptographic primitives, is not applicable to PEPs. We apply the formal method of Coloured Petri Nets (CPNs) to construct an executable specification of a representative PEP, namely the Private Information Escrow Bound to Multiple Conditions Protocol (PIEMCP). Formal semantics of the CPN specification allow us to reason about various security properties of PIEMCP using state space analysis techniques. This investigation provides us with preliminary insights for modeling and verification of PEPs in general, demonstrating the benefit of applying the CPN-based formal approach to proving the correctness of PEPs.

Resilience of water supply systems in meeting the challenges posed by climate change and population growth

This research project provides a scientifically robust approach for assessing the resilience of water supply systems, which are critical infrastructure, to impacts of climate change and population growth. An approach for the identification of trigger points that allows timely and appropriate management actions to be taken to avoid catastrophic system failure is an important outcome of this project. In the current absence of a formal method to evaluate the resilience of a water supply system, the approach developed in this study was based on the characterisation of resilience of a water supply system to a range of surrogate measures. Accordingly, a set of indicators are proposed to evaluate system behaviour and logistic regression analysis was used to assess system behaviour under predicted rainfall, storage and demand conditions.

面向方面软件开发的形式化方法与编译器技术分析研究

主要讨论"面向方面软件开发"或"面向方面编程"要如何运用形式化的相关方法来进行模型检测。简单介绍面向方面软件开发的内容,并运用编译器的理论知识来分析面向方面编程相关工具的应用。解释面向方面软件开发在测试代码工作上容易遇到的困难点与常见问题,并解释如何运用已知形式化方法来分析描述这些问题,进行模型检测(model checking),找出代码出错的问题点,阐述如何让面向方面软件开发出来的代码更加强固、稳定与可靠。

一种基于安全状态转移的简并测试集生成方法

在总结前人工作的基础上,结合安全操作系统对测试的特殊需求,提出了简并测试集(degenerate test set,简称DTS)的概念,设计了一种使用模型检测的基于安全状态转移的高效测试集生成方法.该方法以状态转移为化简对象,在利用模型检测技术生成测试用例的同时,归并相同的状态转移并化简需求集中的冗余属性,从而最终达到化简测试集的目的.在此基础上,探讨了单个用例失败时用例集的有效性问题,并对DTS生成算法进行了改进.实验结果表明,该方法可以有效地对测试集中的冗余进行化简.

Representing and recognizing scenario patterns

This paper presents a formal method for representing and recognizing scenario patterns with rich internal temporal aspects. A scenario is presented as a collection of time-independent fluents, together with the corresponding temporal knowledge that can be relative and/or with absolute values. A graphical representation for temporal scenarios is introduced which supports consistence checking as for the temporal constraints. In terms of such a graphical representation, graph-matching algorithms/methodologies can be directly adopted for recognizing scenario patterns.

A Type-Preserving Compiler from System F to Typed Assembly Language

L'utilisation des méthodes formelles est de plus en plus courante dans le développement logiciel, et les systèmes de types sont la méthode formelle qui a le plus de succès. L'avancement des méthodes formelles présente de nouveaux défis, ainsi que de nouvelles opportunités. L'un des défis est d'assurer qu'un compilateur préserve la sémantique des programmes, de sorte que les propriétés que l'on garantit à propos de son code source s'appliquent également au code exécutable. Cette thèse présente un compilateur qui traduit un langage fonctionnel d'ordre supérieur avec polymorphisme vers un langage assembleur typé, dont la propriété principale est que la préservation des types est vérifiée de manière automatisée, à l'aide d'annotations de types sur le code du compilateur. Notre compilateur implante les transformations de code essentielles pour un langage fonctionnel d'ordre supérieur, nommément une conversion CPS, une conversion des fermetures et une génération de code. Nous présentons les détails des représentation fortement typées des langages intermédiaires, et les contraintes qu'elles imposent sur l'implantation des transformations de code. Notre objectif est de garantir la préservation des types avec un minimum d'annotations, et sans compromettre les qualités générales de modularité et de lisibilité du code du compilateur. Cet objectif est atteint en grande partie dans le traitement des fonctionnalités de base du langage (les «types simples»), contrairement au traitement du polymorphisme qui demande encore un travail substantiel pour satisfaire la vérification de type.

Modeling of ALFA Programs Using PVS Theorem Prover

In Safety critical software failure can have a high price. Such software should be free of errors before it is put into operation. Application of formal methods in the Software Development Life Cycle helps to ensure that the software for safety critical missions are ultra reliable. PVS theorem prover, a formal method tool, can be used for the formal verification of software in ADA Language for Flight Software Application (ALFA.). This paper describes the modeling of ALFA programs for PVS theorem prover. An ALFA2PVS translator is developed which automatically converts the software in ALFA to PVS specification. By this approach the software can be verified formally with respect to underflow/overflow errors and divide by zero conditions without the actual execution of the code.

Modeling of ALFA Programs Using PVS Theorem Prover

In Safety critical software failure can have a high price. Such software should be free of errors before it is put into operation. Application of formal methods in the Software Development Life Cycle helps to ensure that the software for safety critical missions are ultra reliable. PVS theorem prover, a formal method tool, can be used for the formal verification of software in ADA Language for Flight Software Application (ALFA.). This paper describes the modeling of ALFA programs for PVS theorem prover. An ALFA2PVS translator is developed which automatically converts the software in ALFA to PVS specification. By this approach the software can be verified formally with respect to underflow/overflow errors and divide by zero conditions without the actual execution of the code

Plan exportador software de encriptación y firma digital de documentos altamente sensibles

Este plan exportador proyectado a un plazo de 3 años, servirá a ITAC IT APPLICATIONS CONSULTING S.A. para direccionar sus actividades en el mercado internacional para los años 2009, 2010, 2011. La prioridad de los 2 primeros años será el mejoramiento interno de la empresa, que será la aplicación de estrategias en diferentes campos como: capital humano, capital intelectual, capital cultural, crecimiento económico, estrategia comercial en el área internacional, construcción de capital financiero para la generación de ingresos. Para tener participación en mercados internacionales, mostrar su potencial exportador y lograr las expectativas de crecimiento de las ventas independientes a las obtenidas en el marcado local; pretende empezar en el año 2009, en el mercado Peruano con exportaciones por $36.000 USD correspondiente a 30 unidades, aumentando a $ 72000 USD con 60 unidades en el 2010 y $ 108000 USD y 90 unidades en el 2011. El Servicio a exportar fue “SecureFile” a partir del cual se definieron factores de éxito como lo son las ventajas competitivas del producto en sí mismo enumeradas a continuación: 1) Precio muy competitivo en el mercado, 2) Automatización del proceso de intercambio de información, 3) Software basado en estándares, 4) Se ejecuta en cualquier sistema operativo. A su vez se realizaron consultorías donde se diagnosticó todas las áreas de la empresa arrojando algunos resultados: La estructura organizacional esta bien definida, pero por su crecimiento y necesidad de incluir nuevo personal, no hay claridad en las funciones dentro del organigrama y depende totalmente de la dirección general. Por esto la gerencia debe estructurar mejor los departamentos comerciales creando nuevos cargos de acuerdo al proceso de internacionalización. Las políticas de personal se trabajan de manera informal con criterios validos para promover trabajadores (mérito, antigüedad, etc.), se realizan actualizaciones Tecnológicas mensuales, reconocimiento y participación en la empresa a sus funcionarios, excelentes relaciones personales que permiten hacer evaluaciones de desempeño acorde a las metas, gran variedad de motivación y responsabilidad social encaminada a los niños de bajos recursos. Aunque se debe crear un área de gestión humana y definir la frecuencia de las capacitaciones. Los ingresos son provenientes de la prestación de servicios de IT con incrementando de 256% durante los tres años anteriores para obtener $ 2`032.784.683 millones de pesos en el 2007. El nivel de endeudamiento también ha ido en aumento, por la necesidad de capacidad instalada, contrataciones de personal, el cumplimiento de requisitos del mercado y la necesidad generar buena imagen crediticia con entidades financieras. Cuenta con un musculo financiero para respaldar sus obligaciones inmediatas con $4,42 por $1 comprometido en el 2007 a pesar de ser el año con mayor nivel de endeudamiento arrojando pasivos corrientes por $127.715.281,37. Los cuatro socios cuentan con un comportamiento de 164,67% (2006) y 132,97% (2007) de rendimiento de sobre la inversión antes de impuestos. Para este año más del 95% de su información financiera y contable se maneja de manera sistematizada. El área Financiera de la empresa no es la más débil, pero no existe un departamento financiero con un solo responsable a la cabeza, por esto deben destinar un área separada de la administrativa con un asesor financiero que tenga disponibilidad de 100%. En el caso particular del proyecto de exportación los costos de producción se centran en SecureFile versión 3.0 que no representa costos marginales, ya que la replica de este software puede hacerse cuantas veces sea requerido sin afectar en ninguna proporción los costos. La empresa no utiliza un método formal para calcular sus costos de operación y desarrollo de programas. Pero ha desarrollado un sistema de evaluación de costos en tablas de Excel que de manera organizada logran un costeo acorde a sus necesidades específicas. Para la selección de los países: objetivo, alterno y contingente; se realizó una matriz de Selección de 6 países basados en la exigencia gubernamental en términos de seguridad de la información vía internet, y la percepción de los empresarios, competencia y otros factores económicos; arrojando como resultado a Perú, Costa Rica y México.

A mission control system for an autonomous underwater vehicle

The presented work focuses on the theoretical and practical aspects concerning the design and development of a formal method to build a mission control system for autonomous underwater vehicles bringing systematic design principles for the formal description of missions using Petri nets. The proposed methodology compounds Petri net building blocks within it to de_ne a mission plan for which it is proved that formal properties, such as reachability and reusability, hold as long as these same properties are also guaranteed by each Petri net building block. To simplify the de_nition of these Petri net blocks as well as their composition, a high level language called Mission Control Language has been developed. Moreover, a methodology to ensure coordination constraints for teams of multiple robots as well as the de_nition of an interface between the proposed system and an on-board planner able to plan/replan sequences of prede_ned mission plans is included as well. Results of experiments with several real underwater vehicles and simulations involving an autonomous surface craft and an autonomous underwater vehicles are presented to show the system's capabilities.