To see the other types of publications on this topic, follow the link: Formal methods (Computer science).
Dissertations / Theses on the topic 'Formal methods (Computer science)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Formal methods (Computer science).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Tran, Sang Cong. "Applications of formal methods in engineering." Thesis, University of Warwick, 1991. http://wrap.warwick.ac.uk/60452/.
Full textAbstract:
The main idea presented in this thesis is to propose and justify a general framework for the development of safety-related systems based on a selection of criticality and the required level of integrity. We show that formal methods can be practically and consistently introduced into the system design lifecycle without incurring excessive development cost. An insight into the process of generating and validating a formal specification from an engineering point of view is illustrated, in conjunction with formal definitions of specification models, safety criteria and risk assessments. Engineering specifications are classified into two main classes of systems, memoryless and memory bearing systems. Heuristic approaches for specification generation and validation of these systems are presented and discussed with a brief summary of currently available formal systems and their supporting tools. It is further shown that to efficiently address different aspects of real-world problems, the concept of embedding one logic within another mechanised logic, in order to provide mechanical support for proofs and reasoning, is practical. A temporal logic framework, which is embedded in Higher Order Logic, is used to verify and validate the design of a real-time system. Formal definitions and properties of temporal operators are defined in HOL and real-time concepts such as timing marker, interrupt and timeout are presented. A second major case study is presented on the specification a solid model for mechanical parts. This work discusses the modelling theory with set theoretic topology and Boolean operations. The theory is used to specify the mechanical properties of large distribution transformers. Associated mechanical properties such as volumetric operations are also discussed.
2
Yao, Yow-Wei. "Formal methods for protocol conversion /." The Ohio State University, 1991. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487693923198251.
Full text
3
Lu, Yueping. "On the formal methods for protocol conformance testing." Thesis, University of Ottawa (Canada), 1990. http://hdl.handle.net/10393/5824.
Full textAbstract:
The use of formal methods allows automated generation and optimization of test sequences. Developing formal methods for generating communications protocol conformance tests has drawn considerable attention in recent years. This thesis describes the implementation of five formal methods of protocol conformance test sequence generation proposed in the literature. These methods are: Transition tour (T) method, Distinguishing sequence (D) method, Characterizing sequence (W) method, Unique Input/Output sequence (UIO) method and Multiple UIO-method. Some related graph theoretic optimization techniques for the Chinese Postman Problem (CPP) and Rural Chinese Postman Problem (RCPP) are applied to T-method and UIO-method respectively to determine minimum-cost test sequences. It is shown in this thesis that the solution to the RCPP can also be applied to D-method and W-method to derive minimum-cost test sequences. The application of five formal methods to a real protocol, Transport protocol class 4, is then discussed.
4
Ibrahim, Rosziati. "Formal methods applied to component-based systems." Thesis, Queensland University of Technology, 2000.
Find full text
5
Trafford, Paul Joseph. "The use of formal methods for safety-critical systems." Thesis, Kingston University, 1997. http://eprints.kingston.ac.uk/20609/.
Full textAbstract:
An investigation is presented into the use of formal methods for the production of safety-critical systems with embedded software. New theory and procedures are tested on an industrial case study, the formal specification and refinement of a communications protocol for medical devices (the Universal Flexport protocol [copyright]). On reviewing the current literature, a strong case emerges for grounding any work within an overall perspective that integrates the experience of safety engineering and the correctness of formal methods. Such a basis, it is argued, is necessary for an effective contribution to the delivery with assurance of life-critical software components. Hence, a safety-oriented framework is proposed which facilitates a natural flow from safety analysis of the entire system through to formal requirements, design, verification and validation for a software model undergoing refinement towards implementation. This framework takes a standard safety lifecycle model and considers where and how formal methods can play apart, resulting in procedures which emphasise the activities most amenable to formal input. Next, details of the framework are instantiated, based upon the provision of a common formal semantics to represent both the safety analysis and software models. A procedure, FTBuild, is provided for deriving formal requirements as part of the process of generating formalised fault trees. Work is then presented on establishing relations between formalised fault trees and models, extending results of other authors. Also given are some notions of (property) conformance with respect to the given requirements. The formal approach itself is supported by the enhancement of the theory of con-formance testing that has been developed for communication systems. The basis of this work is the detailed integration of already established theories: a testing system for process algebra (the Experimental System due to Hennessy and de Nicola) and a more general observation framework (developed by the LOTOSphere consortium). Notions of conformance and robustness are then examined in the context of refinement for the process algebra, (Basic) LOTOS, resulting in the adoption of the commonly accepted 'reduction' relation for which a proof is given that it is testable. Then a new algorithm is developed for a single (canonical) tester for reduction, which is unified in that it tests simultaneously for both con-formance and robustness. It also allows, in certain cases, a straightforward implementation as a Full LOTOS process with the ability to give some diagnostics in the case of failure. The text is supported by examples and some guidelines for use. Finally, having established these foundations, the methodology is demonstrated on the Flexport protocol through two iterations of FTBuild which demonstrate how the activities of specification, safety analysis, validation and refinement are all brought together.
6
Joochim, Tossaporn. "Bringing requirements engineering to formal methods : timing diagrams for Event-B and KAOS." Thesis, University of Southampton, 2010. https://eprints.soton.ac.uk/72396/.
Full textAbstract:
Event-B is a language for the formal development of reactive systems. At present the RODIN toolkit (RODIN, 2009) for Event-B is used for modelling requirements, specifying refinements and verification. In order to extend the ability to model graphically requirements for the real-time domain, where timing constraints are essential, we use Timing diagrams for Event-B, UML-B and Knowledge Acquisition in autOmated Specification (KAOS). The Timing diagrams, based on UML 2.0 Timing diagram notation (OMG, 2007), provide an intuitive graphical specification capability for timing constraints and causal dependencies between system events. Translation schemes to Event-B, UML-B and KAOS are proposed and presented. The benefit of our contribution is providing a graphical option to generate timing constraints and causal dependencies of a reactive system to Event-B, UML-B and KAOS Goals. Thus, instead of manually generating these Event-B, UML-B and KAOS Goal models in a textual form, users can use the TD as a graphical front-end, and these target models are created automatically. We compare the three applications of the Timing diagrams in terms of their contribution to formal requirements engineering. A partial case study of a Lift System is used to demonstrate the translation in practice.
7
Kim, Soon-Kyeong. "A metamodel-based approach to integrate object-oriented graphical and formal specification techniques /." St. Lucia, Qld, 2001. http://www.library.uq.edu.au/pdfserve.php?image=thesisabs/absthe16467.pdf.
Full text
8
Topintzi, Ermioni. "System concepts and formal modelling methods for business processes." Thesis, City University London, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.390937.
Full text
9
Powell, John D. "A graph theoretic approach to assessing tradeoffs on memory usage for model checking." Morgantown, W. Va. : [West Virginia University Libraries], 2000. http://etd.wvu.edu/templates/showETD.cfm?recnum=1355.
Full textAbstract:
Thesis (M.S.)--West Virginia University, 2000.Title from document title page. Document formatted into pages; contains vii, 167 p. : ill. Includes abstract. Includes bibliographical references (p. 107-109).
10
Seotsanyana, Motlatsi. "Formal specification and verification of safety interlock systems : a comparative case study /." Thesis, Link to the online version, 2007. http://hdl.handle.net/10019/710.
Full text
11
Shu, Guoqiang. "Formal Methods and Tools for Testing Communication Protocol System Security." The Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1211333211.
Full text
12
Shands, Deborah Ann. "A formal method for classifying distributed systems /." The Ohio State University, 1994. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487854314871212.
Full text
13
Gibson, J. Paul. "Formal object oriented development of software systems using LOTOS." Thesis, University of Stirling, 1993. http://hdl.handle.net/1893/24014.
Full textAbstract:
Formal methods are necessary in achieving correct software: that is, software that can be proven to fulfil its requirements. Formal specifications are unambiguous and analysable. Building a formal model improves understanding. The modelling of nondeterminism, and its subsequent removal in formal steps, allows design and implementation decisions to be made when most suitable. Formal models are amenable to mathematical manipulation and reasoning, and facilitate rigorous testing procedures. However, formal methods are not widely used in software development. In most cases, this is because they are not suitably supported with development tools. Further, many software developers do not recognise the need for rigour. Object oriented techniques are successful in the production of large, complex software systems. The methods are based on simple mathematical models of abstraction and classifi cation. Further, the object oriented approach offers a conceptual consistency across all stages of software development. However, the inherent flexibility of object oriented approaches can lead to an incremental and interactive style of development, a consequence of which may be insuffi cient rigour. This lack of rigour is exacerbated by the inconsistent and informal semantics for object oriented concepts at all stages of development. Formal and object oriented methods are complementary in software development: object oriented methods can be used to manage the construction of formal models and formality can add rigour to object oriented software development. This thesis shows how formal object oriented development can proceed from analysis and requirements capture to design and implementation. A formal object oriented analysis language is defined in terms of a state transition system semantics. This language is said to be customer-oriented: a number of graphical views of object oriented relations in the formal analysis models are presented, and the specifi cations produced say what is required rather than how the requirements are to be met. A translation to ACT ONE provides an executable model for customer validation. This translation is founded on a precise statement of the relationship between classes and types (and subclassing and subtypes). The structure of the resulting ACT ONE requirements model corresponds to the structure of the problem domain, as communicated by the customer. The step from analysis to design requires an extension to the requirements model to incorporate semantics for object communication. A process algebra provides a suitable formal model for the specifi cation of communication properties. LOTOS, which combines ACT ONE and a process algebra in one coherent semantic model, provides a means of constructing object oriented design semantics. Design is de fined as the process of transforming a customer-oriented requirements model to an implementation-oriented design, whilst maintaining correctness. Correctness preserving transformations (CPTs) are defined for: transferring requirements structure to design structure, manipulating design structure and changing internal communication models. Design must be targetted towards a particular implementation environment. The thesis examines a number of different environments for the implementation of object oriented LOTOS designs. It illustrates the importance of understanding programming language semantics. We show how Eiffel can be used to implement formal object oriented designs. A case study which evaluates the formal object oriented models and methods, developed in this thesis, is reported. This identifi es re-use at all stages of software development and emphasises the role of structure: it improves understanding and communication, and makes validation and veri fication easier and better. The thesis shows that formal object oriented technology is ready for transfer to industry. These methods should be exploited sooner rather than later: object oriented development can incorporate formal methods without signi ficant cost, and formal methods can utilise the object oriented paradigm to manage complexity. The thesis provides a rationale for formal object oriented development and a set of conceptual tools which makes the development of software systems a true engineering discipline.
14
Nilsson, Marcus. "Regular model checking /." Uppsala : Acta Universitatis Upsaliensis : Univ.-bibl. [distributör], 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-4793.
Full text
15
Andrade-Gómez, Héctor Adolfo. "Model checking for open systems a compositional approach to software verification /." [Gainesville, Fla.] : University of Florida, 2001. http://purl.fcla.edu/fcla/etd/ank6403.
Full textAbstract:
Thesis (Ph. D.)--University of Florida, 2001.Title from first page of PDF file. Document formatted into pages; contains xi, 144 p.; also contains graphics. Vita. Includes bibliographical references (p. 139-143).
16
Lu, Yun. "Mapping Template Semantics to SMV." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1205.
Full textAbstract:
Template semantics is a template-based approach to describing the semantics of model-based notations, where a pre-defined template captures the notations' common semantics, and parameters specify the notations' distinct semantics. In this thesis, we investigate using template semantics to parameterize the translation from a model-based notation to the input language of the SMV family of model checkers. We describe a fully automated translator that takes as input a specification written in template semantics syntax, and a set of template parameters, encoding the specification's semantics, and generates an SMV model of the specification. The result is a parameterized technique for model checking specifications written in a variety of notations. Our work also shows how to represent complex composition operators, such as rendezvous synchronization, in the SMV language, in which there is no matching language construct.
17
Zaccai, Diego Sebastian. "A Balanced Verification Effort for the Java Language." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1461243619.
Full text
18
Rubio, Medrano Carlos Ernesto. "A formal approach to specifying access control security features of Java modules." To access this resource online via ProQuest Dissertations and Theses @ UTEP, 2008. http://0-proquest.umi.com.lib.utep.edu/login?COPT=REJTPTU0YmImSU5UPTAmVkVSPTI=&clientId=2515.
Full text
19
Turilli, Matteo. "Ethics and the practice of software design." Thesis, University of Oxford, 2012. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.711646.
Full text
20
Kjellsson, Kenji. "Formal Methods in Verification of Interface and Bus Protocols." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-177354.
Full textAbstract:
This master thesis is performed on behalf of the Swedish technology company Ericsson and is meant to evaluate the efficiency of an assertion-based Verification Intellectual Property (abVIP) against an already existing constrained random Verification Intellectual Property (crVIP). The abVIP is a verification entity which is connected with a predefined design and proves that the design is adhering to the specification properties through conditional checks, which uses mathematical proofs rather than prolonged simulation based input stimuli. A market research meant to cover the popularity of abVIPs within the EDA vendors has been conducted. This research showed that the focus of the commercially available VIPs are still on the traditional simulation based crVIP, as only a third of the contacted EDA vendors openly offered any commercial abVIPs for various protocols. These companies are Cadence Design System, Jasper Design Automation and Mentor Graphics. Based on the market research, the AXI 4 protocol has been chosen to be explored due to its popularity in formal based verification. The exploration phase answered questions related to how commercial abVIPs are built and what methods they considered. This was of particular interest as no industry standard methodology for formal based verification existed at time of writing. The companies for which the abVIPs were obtained from are referred to as company A and company B to avoid any confidentiality liability. Both abVIPs were assessed and shared many similarities although one was clearly more user friendly than the other. Finally, a custom abVIP have been developed during the course of this thesis for an Ericsson design which utilizes the serial Inter-IC (I2C) bus protocol. This abVIP verification performance is compared against already existing crVIP verification results. This phase showed that the development time of an abVIP is unchanged from that of a crVIP. The verification environment development time differed however in the favor of the abVIP. By not having to instantiate auxiliary modules, scoreboards or test cases, the abVIP was shown to gain weeks which were needed in the crVIP. For a significantly smaller subset of the crVIP verification set, the abVIP required more than twice the time needed for the crVIP to yield 100% assertion results. This indicates that protocols which rely on long chains of system clock operations results in large amount of states which the formal tool has to visit. For this reason, one verification run ended up in a state space so large the results did not converge. Thus it was concluded in this thesis that abVIPs are ultimately not a replacement of crVIPs but rather a complement and should be treated so by Ericsson as well. This is especially the case if the protocol to verify is a serial one.
21
Salehi, Fathabadi Asieh. "An approach to atomicity decomposition in the Event-B formal method." Thesis, University of Southampton, 2012. https://eprints.soton.ac.uk/340357/.
Full textAbstract:
Formal methods are mathematically based techniques and tools to model software and hardware systems. Event-B is a formal method that emerged over the last decade as an evolution of classical B. Event-B is supported by an open and extensible Eclipse-based tool-set, called Rodin. Rodin provides an integrated environment supporting the whole process of multi-stage modelling and handling of the associated proofs. Rodin extensibility is exploited by developing a number of plug-ins to extend the main platform capabilities. During recent years, Event-B and Rodin have been used to model some real-world complex systems and prove consistency properties of them. However developing models of large and complex systems is not an easy task, since it can result in complex models and difficult proofs. There are some techniques in Event-B which can help to tackle the difficulties of modelling complex systems; refinement and model decomposition are two examples. Atomicity decomposition was recently introduced as another technique to help with the structuring of refinement-based development of complex systems in Event-B. In this research, we have investigated how the development process with Event-B can be enriched further by using the atomicity decomposition approach. The atomicity decomposition approach provides a graphical notation to structure refinement and to support the explicit sequencing of events in an Event-B model. In this approach, modelling usually starts with a single atomic event of the system which is split to two or more sub-events in the next refinement level. We have further developed the atomicity decomposition patterns and features. A formal description of the atomicity decomposition language is presented. The transformation rules from an atomicity decomposition diagram to the Event-B model are defined. The atomicity decomposition diagrams can be transformed to Event-B models using these rules. Exploiting the extensibility of the Rodin platform, a Rodin plug-in tool was developed to provide atomicity decomposition support in Event-B. The modelling and tool extensions developed in this thesis are applied to two complex case studies, the Media Channel System and the BepiColombo System. We present an evaluation of the atomicity decomposition approach using insights gained from these case studies.
22
Kremer, Steve. "Modelling and analyzing security protocols in cryptographic process calculi." Habilitation à diriger des recherches, École normale supérieure de Cachan - ENS Cachan, 2011. http://tel.archives-ouvertes.fr/tel-00636769.
Full textAbstract:
In his habilitation theses Steve Kremer presents some selected research results in the area of formal analysis of security protocols. His contributions include application of formal methods to electronic voting protocols and security APIs, automated methods for verifying equivalence properties, compositional reasoning for security protocols and computational soundness results.
23
Pino, Lou. "A formal method for modeling and analysis of requirements for software /." Thesis, McGill University, 1993. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=69740.
Full textAbstract:
Requirements that are well understood by a client and a provider are a major contributor to developing and supporting reliable, quality software on time and within budget. This thesis has two thrusts to facilitate improved interpretation of requirements: (1) a requirements model and (2) a new formalism called LaP, with automated tools, to express and analyze requirements. The new formalism is based on the integration of an algebraic based language, Larch, and an extended finite state machine based language, Promela. Larch comes with a theorem prover (Larch Prover) and Promela comes with a tool (SPIN) to aid in the validation of dynamic properties. It is the objective of LaP to express the control and data intensive aspects of requirements. The two thrusts are demonstrated by building a requirements model for real telecommunications requirements that ask for a system that can manage the access configurations of user's accounts in telecommunications equipment.
24
Fruth, Matthias. "Formal methods for the analysis of wireless network protocols." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:df2c08f4-001c-42d3-a2f4-9922f081fb49.
Full textAbstract:
In this thesis, we present novel software technology for the analysis of wireless networks, an emerging area of computer science. To address the widely acknowledged lack of formal foundations in this field, probabilistic model checking, a formal method for verification and performance analysis, is used. Contrary to test and simulation, it systematically explores the full state space and therefore allows reasoning about all possible behaviours of a system. This thesis contributes to design, modelling, and analysis of ad-hoc networks and randomised distributed coordination protocols. First, we present a new hybrid approach that effectively combines probabilistic model checking and state-of-the-art models from the simulation community in order to improve the reliability of design and analysis of wireless sensor networks and their protocols. We describe algorithms for the automated generation of models for both analysis methods and their implementation in a tool. Second, we study spatial properties of wireless sensor networks, mainly with respect to Quality of Service and energy properties. Third, we investigate the contention resolution protocol of the networking standard ZigBee. We build a generic stochastic model for this protocol and analyse Quality of Service and energy properties of it. Furthermore, we assess the applicability of different interference models. Fourth, we explore slot allocation protocols, which serve as a bandwidth allocation mechanism for ad-hoc networks. We build a generic model for this class of protocols, study real-world protocols, and optimise protocol parameters with respect to Quality of Service and energy constraints. We combine this with the novel formalisms for wireless communication and interference models, and finally we optimise local (node) and global (network) routing policies. This is the first application of probabilistic model checking both to protocols of the ZigBee standard and protocols for slot allocation.
25
John, Sheline Anna. "Runtime verification of composite web services." To access this resource online via ProQuest Dissertations and Theses @ UTEP, 2008. http://0-proquest.umi.com.lib.utep.edu/login?COPT=REJTPTU0YmImSU5UPTAmVkVSPTI=&clientId=2515.
Full text
26
André, Amaury Bosso. "Verificação formal de workflows com spin." [s.n.], 2010. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275795.
Full textAbstract:
Orientador: Jacques WainerDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-16T22:50:12Z (GMT). No. of bitstreams: 1 Andre_AmauryBosso_M.pdf: 698462 bytes, checksum: 3a97278e3328845adbb26c7cb448204b (MD5) Previous issue date: 2010
Resumo: O gerenciamento de workflows é uma realidade atualmente, mas os sistemas atuais carecem de suporte à verificação de correção em modelos de workflow. Este trabalho visa a realização de verificações em processos, objetivando a detecção de erros sintáticos, como a existência de atividades mal modeladas, ou seja, sem condições de entrada ou de saída. É objetivo deste trabalho também a definição de verificações de ordem estrutural, como detectar se o processo de workflow não possui deadlocks (estado em que o processo trava sem possibilidade de progredir), ou verificar se existem atividades mortas no processo (atividades impossíveis de serem executadas), ou se há terminações incompletas, ou seja, transições pendentes após o processo ter atingido seus objetivos. Além de verificações sintáticas e estruturais, é necessário também a realização de verificações semânticas do modelo, ou seja, é importante que os processos possam ser validados quanto a características que dizem respeito à sua organização lógica, a um nível um pouco mais alto de informação do que simplesmente estrutural. Por exemplo, é diretamente impactante na qualidade do modelo de um processo, definir se este possui conflitos ao acesso de recursos. Dessa forma, um processo estruturalmente correto, pode ficar travado em um deadlock, devido à concorrência quanto ao acesso de um recurso comum entre atividades distintas. Além disso, verificações de restrições de custo, por exemplo, também podem inviabilizar um processo. Todas essas verificações são importantes para decidir se um processo de workflow é correto. A maior contribuição deste trabalho, é então a definição de uma modelagem de processos de workflow que possibilite a verificação de problemas sintáticos, estruturais e semânticos, todos em uma única ferramenta, que se mostra escalável para processos reais, além de possibilitar a verificação de questões ad-hoc, específicas de cada instância, como verificar ordenações entre atividades específicas, etc
Abstract: Workflow management is a reality nowadays, but today's systems give very little support to verify correctness in workflow models. This work aims to perform formal verification, with the goal of detecting syntactic errors, like the existence of activities poorly modeled, in other words, activities with no precondition or effect. It is a goal too, the definition of workflows structural verification, as to detect if the process does not have deadlocks (state in which the process is stuck with no possibility of getting any further), or verifying if there are dead activities in the process (activities impossible to be reached), or if exist incomplete terminations, ie, pending transitions after the process reached its objectives. Besides syntactic and structural verifications, it is necessary too, to perform semantic verifications in the process, in other words, it is important to validate the processes in respect to characteristics of its logical organization, in a higher level of information than simply structural verification. For example, it is directly impacting in the quality of the process model the definition if it has resource access conflicts. In this way, a process that is structurally correct, can be stuck in a deadlock, due to the concurrency in the access of a common resource of distinct activities. Besides that, verifications of costs restrictions, for example, can spoil a process. All these verifications are important to decide if a workflow model is correct. The main contribution of this work is the definition of workflow processes modeling that makes it possible to perform syntactic, structural and semantic verifications, all in a unique tool, that is showed to be scalable for real process, and even possible to verify ad-hoc questions, specific to the model, as checking activities ordering, for example
Mestrado
Inteligência Artificial, Verificação e Validação
Mestre em Ciência da Computação
27
Palombo, Hernan Miguel. "A Comparative Study of Formal Verification Techniques for Authentication Protocols." Scholar Commons, 2015. http://scholarcommons.usf.edu/etd/6008.
Full textAbstract:
Protocol verification is an exciting area of network security that intersects engineering and formal methods. This thesis presents a comparison of formal verification tools for security protocols for their respective strengths and weaknesses supported by the results from several case studies. The formal verification tools considered are based on explicit model checking (SPIN), symbolic analysis (Proverif) and theorem proving (Coq). We formalize and provide models of several well-known authentication and key-establishment protocols in each of the specification languages, and use the tools to find attacks that show protocols insecurity. We contrast the modelling process on each of the tools by comparing features of their modelling languages, verification efforts involved, and analysis results
Our results show that authentication and key-establishment protocols can be specified in Coq’s modeling language with an unbounded number of sessions and message space. However, proofs in Coq require human guidance. SPIN runs automated verification with a restricted version of the Dolev-Yao attacker model. Proverif has several advantages over SPIN and Coq: a tailored specification language, and better performance on infinite state space analysis.
28
Kong, Cindy. "Formal Methods Applied to the Specification of an Active Network Node." University of Cincinnati / OhioLINK, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin982104729.
Full text
29
Vadaparty, Sirisha Lakshmi. "Semantic tableaux program." CSUSB ScholarWorks, 2006. https://scholarworks.lib.csusb.edu/etd-project/2953.
Full textAbstract:
This project created a program that takes predicate calculus formulas and creates a visual Semantic Tableaux truth tree, thereby proving or disproving a conclusion. Formal methods used in developing and verifying software and hardware are mathematically based techniques for describing and reasoning about system properties. Such formal methods provide frameworks within which people specify, develop, and verify systems in a systematic, rather than ad hoc, manner. Formal methods include the more specific activities of program specification, program verification and hardware verification.
30
Kerfoot, Eric D. "Formal relationships in sequential object systems." Thesis, University of Oxford, 2010. http://ora.ox.ac.uk/objects/uuid:63ed35ee-5ad5-4b8f-858d-fe3868700ed0.
Full textAbstract:
Formal specifications describe the behaviour of object-oriented systems precisely, with the intent to capture all properties necessary for correctness. Relationships between objects, and in a broader sense the relationship between whole components, may not be adequately captured by specifications. One critical component of specifications having a role in relationships are invariants which define a constraint between multiple objects. If an object's invariant relies on external objects for its conditions, correct operations which abide by their specifications modifying these external objects may violate the constraint. Such an invariant defines a relationship between multiple objects which is unsound since it does not adequately describe the responsibilities which the objects in the relationship have to each other. The root cause of this correctness loophole is the failure of specifications to capture such relationships adequately as well as their correctness requirements. This thesis addresses this shortcoming in a number of ways, both for individual objects in a sequential environment, and between concurrent components which are defined as specialized object types. The proposed Colleague Technique [29] defines sound invariants between two object types using classical Design-by-Contract [35] methodologies. Additional invariant conditions introduced through the technique ensure that no correct operation may produce a post-state which does not satisfy all invariants satisfied by the pre-state. Relationships between objects, as well as their correct specification and management, are the subjects of this thesis. Those relationships between objects which can be described by invariants are made sound with the Colleague Technique, or the lightweight ownership type system that accompanies it. Behavioural correctness beyond these can be addressed with specifications in a similar manner to sequential systems without concurrency, in particular with the use of runtime assertion checking [11].
31
Roop, Parthasarathi Computer Science & Engineering Faculty of Engineering UNSW. "Forced simulation : a formal approach to component based development of embedded systems." Awarded by:University of New South Wales. School of Computer Science and Engineering, 2000. http://handle.unsw.edu.au/1959.4/20470.
Full textAbstract:
Application specific digital systems, called embedded systems, touch almost every aspect of modern human life. As a result, there is considerable interest in automating the design (called synthesis) of these systems. Further, given the time-to-market pressures and increasing system complexities, component reuse during synthesis is being touted as a key to success. This thesis proposes a formal framework for reusing system-level components during synthesis. Within the framework for component reuse, component matching is a key problem that must be addressed. Given the specification of a design function, and a device stored as a component in a library, component matching addresses the question of whether the device can implement the function. Often system-level components are multi-functional and generic, and it is rarely the case that the function is directly realizable by a device. Hence, an important aspect of matching is to decide whether the device can be dynamically adapted to match the function. This thesis proposes a formalization of the matching problem using formal models of the function and device, denoted by F and D respectively. D matches F provided there exists an interface I that adapts D dynamically to produce the same behaviour as F. None of the existing implementation verification techniques within formal methods can be used to test for the existence of an I between arbitrary pairs of F and D. In this thesis, a new simulation relation called forced simulation is proposed between the states of F and D. It is then formally established that the existence of a forced simulation relation is a necessary and sufficient condition for the existence of I for a pair of F and d. Two kinds of forced simulation are proposed, one each for synchronous and asynchronous interactions with the environment. Based on forced simulation, a polynomial time algorithm for automatic matching of F and D is also developed. The distinguishing feature of the algorithm is that when successful, it generates an interface that automatically adapts the device to behave like the function. The algorithm is illustrated by reusing two rogrammable components from Intel and some typical embedded controllers.
32
Lagerkvist, Mikael Zayenz. "Machine Assisted Reasoning for Multi-Threaded Java Bytecode." Thesis, KTH, Electronic, Computer and Software Systems, ECS, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-9512.
Full textAbstract:
In this thesis an operational semantics for a subset of the Java Virtual Machine (JVM) is developed and presented. The subset contains standard operations such as control flow, computation, and memory management. In addition, the subset contains a treatment of parallel threads of execution.
The operational semantics are embedded into a $µ$-calculus based proof assistant, called the VeriCode Proof Tool (VCPT). VCPT has been developed at the Swedish Institute of Computer Science (SICS), and has powerful features for proving inductive assertions.
Some examples of proving properties of programs using the embedding are presented.
I det här examensarbetet presenteras en operationell semantik för en delmängd av Javas virtuella maskin. Den delmängd som hanteras innehåller kontrollflöde, beräkningar och minneshantering. Vidare beskrivs semantiken för parallella exekveringstrådar.
Den operationella semantiken formaliseras i en bevisassistent for $µ$-kalkyl, VeriCode Proof Tool (VCPT). VCPT har utvecklats vid Swedish Institiute of Computer Science (SICS), och har kraftfulla tekniker för att bevisa induktiva påståenden.
Några exempel på bevis av egenskaper hos program användandes formaliseringen presenteras också.
33
Cabral, Glauber Módolo. "Criação de uma biblioteca padrão para a linguagem HasCASL." [s.n.], 2010. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275798.
Full textAbstract:
Orientador: Arnaldo Vieira MouraDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-16T20:14:05Z (GMT). No. of bitstreams: 1 Cabral_GlauberModolo_M.pdf: 1025512 bytes, checksum: 7aaf4d32142384e7200596499be77cca (MD5) Previous issue date: 2010
Resumo: Métodos formais são ferramentas da Engenharia de Software que empregam formalismos matemáticos na construção de programas. Em geral, são compostos por uma ou mais linguagens de especificação e algumas ferramentas auxiliares. A linguagem de especificação algébrica Common Algebraic Specification Language (Casl) foi concebida para ser a linguagem padrão na área de especificação algébrica. A linguagem HasCasl é a extensão da linguagem Casl responsável por suportar lógica de segunda ordem e possui um subconjunto de sua sintaxe que se assemelha à linguagem de programação Haskell e que pode ser executado. O uso prático de uma linguagem de especificação depende da disponibilidade de uma biblioteca padrão de especificações pré-definidas. Embora Casl possua tal biblioteca, esta não disponibiliza propriedades e tipos de dados de segunda ordem. Esta dissertação descreve a especificação de uma biblioteca para a linguagem HasCasl com funções e tipos de dados de segunda ordem, tendo como referência a biblioteca Prelude da linguagem Haskell. Os tipos de dados especificados incluem o tipo booleano, listas, caracteres e cadeias de caracteres, além de classes e funções presentes na biblioteca Prelude. Uma primeira versão da biblioteca faz uso de tipos de dados com avaliação estrita, devido à complexidade de iniciar o processo de especificação com o uso de tipos com avaliação preguiçosa. Um refinamento posterior da biblioteca incluiu o suporte a tipos de dados com avaliação preguiçosa. A verificação de ambas as versões da biblioteca foi realizada com o uso da ferramenta Hets, responsável por traduzir as especificações escritas na linguagem HasCasl para a linguagem HOL e gerar necessidades de prova verificadas com o auxílio do provador de teoremas Isabelle. Para ilustrar o uso dos tipos de dados especificados foram incluídas algumas especificações de exemplo envolvendo listas e tipos booleanos. Algumas sugestões de extensão à biblioteca são propostas, tais como o suporte à recursão e às estruturas infinitas, além do aperfeiçoamento do suporte a provas relacionadas a especificações importadas da biblioteca da linguagem Casl
Abstract: Formal methods can be used as software engineering tools that employ mathematical formalisms for building and verifying programs. They are usually composed of one or more specification languages and some auxiliary tools. The Common Algebraic Specification Language (Casl) is designed to be the standard language in the area of algebraic specification, taking tecnical elements from other specification languages. The HasCasl language is the extention of the Casl language that is responsible for supporting secondorder logic, which has a subset of its syntax resembling the Haskell programming language. The practical use of a specification language depends on the availability of a standard library of pre-defined specifications. CASL has such a library and its specifications can be imported by specifications developed in HasCasl. However, the library of the Casl language does not provide higer order properties and data types. This dissertation describes the specification of a library for the language HasCasl based on the Prelude library from the Haskell programming language. The library created her provides second-order functions and data types. It does so by specifying data types and functions existing in Haskell language, such as boolean, list, character and string types. The first version of our library uses types with strict evaluation. The second version of the library has been refined to support types with lazy evaluation. Verification of both libraries was performed using the Hets tool, which translates specifications to the HOL language, producing proof needs that were discharged with the help of the Isabelle theorem prover. To illustrate the use of our library, some example specifications using lists and boolean types are included. Some suggestions for extension of the library are proposed, dealing with support for infinite structures and numeric data types
Mestrado
Linguagens de Programação
Mestre em Ciência da Computação
34
Campbell, Sherrie L. "ADEPT a tool to support the formal analysis of software design /." Oxford, Ohio : Miami University, 2009. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=miami1250195339.
Full text
35
Gaither, Danielle. "Improving Software Quality through Syntax and Semantics Verification of Requirements Models." Thesis, University of North Texas, 2018. https://digital.library.unt.edu/ark:/67531/metadc1404542/.
Full textAbstract:
Software defects can frequently be traced to poorly-specified requirements. Many software teams manage their requirements using tools such as checklists and databases, which lack a formal semantic mapping to system behavior. Such a mapping can be especially helpful for safety-critical systems. Another limitation of many requirements analysis methods is that much of the analysis must still be done manually. We propose techniques that automate portions of the requirements analysis process, as well as clarify the syntax and semantics of requirements models using a variety of methods, including machine learning tools and our own tool, VeriCCM. The machine learning tools used help us identify potential model elements and verify their correctness. VeriCCM, a formalized extension of the causal component model (CCM), uses formal methods to ensure that requirements are well-formed, as well as providing the beginnings of a full formal semantics. We also explore the use of statecharts to identify potential abnormal behaviors from a given set of requirements. At each stage, we perform empirical studies to evaluate the effectiveness of our proposed approaches.
36
Krishna, Aneesh. "Practical methodologies for agent-oriented conceptual modelling." Access electronically, 2006. http://www.library.uow.edu.au/adt-NWU/public/adt-NWU20060815.122954/index.html.
Full text
37
Yeo, Chuohao 1979. "An investigation of methods for digital television format conversions." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/87302.
Full textAbstract:
Thesis (M.Eng. and S.B.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.Includes bibliographical references (p. 75-76).
by Chuohao Yeo.
M.Eng.and S.B.
38
Fourie, Jean Francois. "Reducing communication in distributed model checking." Thesis, Stellenbosch : University of Stellenbosch, 2009. http://hdl.handle.net/10019.1/2176.
Full textAbstract:
Thesis (Msc (Mathematical Sciences. Computer Science))--University of Stellenbosch, 2009.ENGLISH ABSTRACT: Model checkers are programs that automatically verify, without human assistance, that certain user-specified properties hold in concurrent software systems. Since these programs often have expensive time and memory requirements, an active area of research is the development of distributed model checkers that run on clusters. Of particular interest is how the communication between the machines can be reduced to speed up their running time. In this thesis the design decisions involved in an on-the-fly distributed model checker are identified and discussed. Furthermore, the implementation of such a program is described. The central idea behind the algorithm is the generation and distribution of data throughout the nodes of the cluster. We introduce several techniques to reduce the communication among the nodes, and study their effectiveness by means of a set of models.
AFRIKAANSE OPSOMMING: Modeltoetsers is programme wat outomaties bevestig, sonder enige hulp van die gebruiker, dat gelopende sagteware aan sekere gespesifiseerde eienskappe voldoen. Die feit dat hierdie programme dikwels lang looptye en groot geheues benodig, het daartoe aanleiding gegee dat modeltoetsers wat verspreid oor ’n groep rekenaars hardloop, aktief nagevors word. Dit is veral belangrik om vas te stel hoe die kommunikasie tussen rekenaars verminder kan word om sodoende die looptyd te verkort. Hierdie tesis identifiseer en bespreek die ontwerpsbesluite betrokke in die ontwikkeling van ’n verspreide modeltoetser. Verder word die implementasie van so ’n program beskryf. Die kernidee is die generasie en verspreiding van data na al die rekenaars in die groep wat aan die probleem werk. Ons stel verskeie tegnieke voor om die kommunikasie tussen die rekenaar te verminder en bestudeer die effektiwiteit van hierdie tegnieke aan die hand van ’n lys modelle.
39
Pamplin, Jason Andrew. "Formal Object Interaction Language: Modeling and Verification of Sequential and Concurrent Object-Oriented Software." unrestricted, 2007. http://etd.gsu.edu/theses/available/etd-04222007-205349/.
Full textAbstract:
Thesis (Ph. D.)--Georgia State University, 2007.Title from file title page. Ying Zhu, committee chair; Xiaolin Hu, Geoffrey Hubona, Roy Johnson, Rajshekhar Sunderraman, committee members. Electronic text (216 p. : ill. (some col.)) : digital, PDF file. Description based on contents viewed Nov. 29, 2007. Includes bibliographical references (p. 209-216).
40
Tadonki, Claude. "High Performance Computing as a Combination of Machines and Methods and Programming." Habilitation à diriger des recherches, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00832930.
Full textAbstract:
High Performance Computing (HPC) aims at providing reasonably fast computing solutions to both scientific and real life technical problems. Many efforts have indeed been made on the way to powerful supercomputers, both generic and customized configurations. However, whatever their current and future breathtaking capabilities, supercomputers work by brute force and deterministic steps, while human mind works by few strokes of brilliance. Thus, in order to take a significant advantage of hardware advances, we need powerful methods to solve problems together with highly skillful programming efforts and relevant frameworks. The advent of multicore architectures is noteworthy in the HPC history, because it has brought the underlying concept of multiprocessing into common consideration and has changed the landscape of standard computing. At a larger scale, there is a keen desire to build or host frontline supercomputers. The yearly Top500 ranking nicely illustrates and orchestrates this supercomputers saga. For many years, computers have been falling in price while gaining processing power often strengthened by specialized accelerator units. We clearly see that what commonly springs up in mind when it comes to HPC is computer capability. However, this availability of increasingly fast computers has changed the rule of scientific discovery and has motivated the consideration of challenging applications. Thus, we are routinely at the door of large-scale problems, and most of time, the speed of calculation by itself is no longer sufficient. Indeed, the real concern of HPC users is the time-to-output. Thus, we need to study each important aspect in the critical path between inputs and outputs, and keep striving to reach the expected level of performance. This is the main concern of the viewpoints and the achievements reported in this book. The document is organized into five chapters articulated around our main contributions. The first chapter depicts the landscape of supercomputers, comments the need for tremendous processing speed, and analyze the main trends in supercomputing. The second chapter deals with solving large-scale combinatorial problems through a mixture of continuous and discrete optimization methods, we describe the main generic approaches and present an important framework on which we have been working so far. The third chapter is devoted to the topic accelerated computing, we discuss the motivations and the issues, and we describe three case studies from our contributions. In chapter four, we address the topic of energy minimization in a formal way and present our method based on a mathematical programming approach. Chapter five debates on hybrid supercomputing, we discuss technical issues with hierarchical shared memories and illustrate hybrid coding through a large-scale linear algebra implementation on a supercomputer.
41
Piva, Fabio Rogério 1982. "Verificação formal de protocolos de trocas justas utilizando o metodo de espaços de fitas." [s.n.], 2009. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276154.
Full textAbstract:
Orientador: Ricardo DahabDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-13T10:57:18Z (GMT). No. of bitstreams: 1 Piva_FabioRogerio_M.pdf: 1281624 bytes, checksum: 2d4f949b868d1059e108b1cd79314629 (MD5) Previous issue date: 2009
Resumo: Os protocolos de trocas justas foram propostos como solução para o problema da troca de itens virtuais, entre duas ou mais entidades, sem que haja a necessidade de confiança entre elas. A popularização da internet criou uma crescente classe de usuários leigos que diariamente participam de transações de troca, como comercio eletrônico (e-commerce), internet banking, redes ponto-a-ponto (P2P), etc. Com tal demanda por justiça, e preciso garantir que os protocolos de trocas justas recebam a mesma atenção acadêmica dedicada aos protocolos clássicos. Neste contexto, fazem-se necessárias diretrizes de projeto, ferramentas de verificação, taxonomias de ataques e quaisquer outros artefatos que possam auxiliar na composição de protocolos sem falhas. Neste trabalho, apresentamos um estudo sobre o problema de trocas justas e o atual estado da arte das soluções propostas, bem como a possibilidade de criar, a partir de técnicas para a verificação formal e detecção de falhas em protocolos clássicos, metodologias para projeto e correção de protocolos de trocas justas.
Abstract: Fair exchange protocols were first proposed as a solution to the problem of exchanging digital items, between two or more entities, without forcing them to trust each other. The popularization of the internet resulted in an increasing amount of lay users, which constantly participate in exchange transactions, such as electronic commerce (ecommerce), internet banking, peer-to-peer networks (P2P), etc. With such demand for fairness, we need to ensure that fair exchange protocols receive the same amount of attention, from academia, as classic protocols do. Within this context, project guideliness are needed, and so are verification tools, taxonomies of attack, and whatever other artifacts that may help correct protocol design. In this work we present a study on the fair exchange problem and the current state-of-the-art of proposed solutions, as well as a discussion on the possibility of building, from currently available formal verification and attack detection techniques for classic protocols, methods for fair exchange protocols design and correction.
Mestrado
Ciência da Computação
Mestre em Ciência da Computação
42
Nova, Luis. "A Formalization of an Extended Object Model Using Views." Thesis, University of Waterloo, 2000. http://hdl.handle.net/10012/1130.
Full textAbstract:
Reuse of software designs, experience and components is essential to making substantial improvements in software productivity, development cost, and quality. However, the many facets of reuse are still rarely used in the various phases of the software development lifecycle because of a lack of adequate theories, processes, and tools to support consistent application of reuse concepts. There is a need for approaches including definitions, models and properties of reuse that would provide explicit guidance to a software development team in applying reuse. In particular there is a need to provide abstractions that clearly separate the various functional concerns addressed in a software system. Separating concerns simplifies the identification of the software components that can benefit from reuse and can provide guidance on how reuse may be applied. In this thesis we present an extended model related to the separation of concerns in object-oriented design. The model, called views, indicates how an object-oriented design can be clearly separated into objects and their corresponding interfaces. In this model objects can be designed so that they are independent of their environment, because adaptation to the environment is the responsibility of the interface or view. The view can be seen as expressing the semantics for the 'glue' that joins components or objects together to create a software system. Informal versions of the views model have already been successfully applied to operational and commercial software systems. The objective of this thesis is to provide the views notion with a theoretical foundation to address reuse and separation of concerns. After clearly defining the views model we show the formal approach to combining the objects, interfaces (views), and their interconnection into a complete software system. The objects and interfaces are defined using an object calculus based on temporal logic, while the interconnections among object and views are specified using category theory. This formal framework provides the mathematical foundation to support the verification of the properties of both the components and the composite software system. We then show how verification can be mechanized by converting the formal version of the views model into higher-order logic and using PVS to support mechanical proofs.
43
Matias, Matthew John. "Program Verification of FreeRTOS using Microsoft Dafny." Cleveland State University / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=csu1400085349.
Full text
44
Soares, Junior Jurandy Martins. "Teste de conformidade em contexto guiado por casos de teste do componente." [s.n.], 2006. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276102.
Full textAbstract:
Orientador: Ricardo de Oliveira AnidoDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-10T11:44:38Z (GMT). No. of bitstreams: 1 SoaresJunior_JurandyMartins_M.pdf: 1209765 bytes, checksum: d8d6bebdcb7b65ed4a9fdb7e84508766 (MD5) Previous issue date: 2006
Resumo: Testar um subsistema embarcado em um sistema complexo, assumindo-se que os demais subsistemas são livres de falhas, é conhecido como teste de conformidade em contexto. A complexidade deste teste reside no fato do subsistema mais externo, conhecido como contexto, ocultar muitas interações e eventos nos quais o sistema embarcado, conhecido como componente, participa. Nas últimas décadas alguns algoritmos foram desenvolvidos para resolver o problema. Muitos deles, no entanto, ignoram as condições nas quais podem ser aplicados. Nesta dissertação estudamos a teoria e os algoritmos relacionados a teste de conformidade e a teste de conformidade em contexto, propomos uma nova abordagem guiada por casos de teste do componente e analisamos as condições necessárias e suficientes para aplicá-Ia. A validação das condições necessárias e suficientes foi feita em estudos de casos com a pilha de protocolos do TCP/IP, com os protocolos HTTP e HTTPS via Proxy e com DHCP via relay-agent. Os algoritmos estudados foram experimentados nas especificações dos protocolos ABP, SCU e TCP
Abstract: Testing a subsystem embedded into a complex system, in which the other subsystems are assumed to be fault-free, is known as confonnance testing in contexto The complexity behind this test resides in the fact that the most external system, known as context, hides many interactions and events in which the embedded subsystem, known as component, participates. In the last decades some algorithms were developed to solve the problem. Many of them, however, ignore the conditions under which they can be applied. In this dissertation we study the theory and the algorithms related to confonnance testing and conformance testing in context, we propose a new approach guided by component's test cases, and we analyze the necessary and sufficient conditions to apply it. The validation of the necessary and sufficient conditions was done in case studies with the TCP/IP protocol stack, with the protocols HTTP and HTTPS . via Proxy, and with DHCP via relay-agent. The algorithms studied were experimented in the specifications of protocols ABP, seu e TCP
Mestrado
Engenharia de Protocolos
Mestre em Ciência da Computação
45
Pradalier, Sylvain. "A formal approach to the modeling, simulation and analysis of nano-devices." Phd thesis, Ecole Polytechnique X, 2009. http://tel.archives-ouvertes.fr/tel-00780567.
Full textAbstract:
Nano-devices are molecular machines synthesized from molecular subcomponents whose functions are combined in order to perform the func- tion of the machine. It frequently results of relative motions of subcomponents triggered by chemical events such as excitement induced by light, acidity or tem- perature changes. Thus the function consists in the transformation of a chemical event into a mechanical event. An important and characteristic feature of these devices is their intrinsic compositional nature. Therefore process-algebra for- malisms are natural candidates for their modeling. To this aim we introduce a dialect of the -calculus, the nano calculus. It is a rule-based language, the basic agents are molecules, with explicit representa- tion of molecular complexations and internal states. Its stochastic semantics is governed by rules which correspond to chemical reactions. The stochastic rate of the rule, possibly in nite, corresponds to the kinetic rate of the reaction. We illustrated its relevance for the modeling and simulation of nano-devices with an example stemming from the collaboration with the chemistry department of bologna: the [2]RaH rotaxane. We modeled it in nano and simulated its behaviour under various conditions of concentration: rst we validate our model by checking its correspondance with the experimental data and then we investi- gate extreme conditions not observable in practice. We were able to show that some classical assumption about kinetic rates were not correct any longer in this setting. The calculus has many advantages for the modelling of biochemical sys- tems. It is in particular compact, easily reusable and modi able and maybe more importantly much biological-like and thus easier to learn for biochemists. On the other hand the -calculus, also often used to model biochemical sys- tems, has a much more developed theory and more available tools. We present an encoding from the nano calculus to the stochastic -calculus. It satis es a very strong correctness property: S ! T , [[S]] ! [[T]], where S and T are nano terms, is the rate of the reaction and [[:]] is the encoding. Thus it permits to use nano as a front-end formalism and still get the bene ts of the theory and tools of the -calculus. We carry on with a study of the chemical master equation. It probabilisti- cally describes the possible behaviours of the system over time as a di erential equation on the probability to be in a given state at a given instant. It is a key notion in chemistry. There have been many e orts to solve it, and methods such as the Gillespie's algorithm has been developed to simulate its solution. We introduce and motivate a notion of equivalence based on the chemical master equation. It equates state with similar stochastic behavior. Then we prove that this equivalence corresponds exactly to the notion backward stochastic bisimu- lation. This bisimulation di ers from the usual ones because it considers ingoing transitions instead of outgoing transitions. This results is worth in itself since it establishes a bridge between a chemical semantics and a computer semantics, but it is also the rst step towards a metrics for biochemistry. Finally we present an unexpected consequence of our study of the nano calculus. We study the relative expressiveness of the synchronous and asyn- chronous -calculus. In the classical setting the latter is known to be strictly less expressive than the former. We prove that the separation also holds in the stochastic setting. We then extend the result to the -calculi with in nite rates. We also show that under a small restriction the asynchronous -calculus with in nite rates can encode the synchronous -calculus without in nite rates. In- terestingly the separation results are proved using the encodability of the nano calculus. We also propose and motivate a stochastic -calculus with rates of di erent orders of magnitude: the multi-scale -calculus to which we generalize our results. Finally we prove that in the probabilistic settings the asynchronous -calculus can be encoded into the asynchronous one.
46
Ravalli, Gilbert, and gravalli@swin edu au. "Translation of on object role model schema into the formal language Z." Swinburne University of Technology, 2005. http://adt.lib.swin.edu.au./public/adt-VSWT20060502.130326.
Full textAbstract:
In the development of information systems for business, structured approaches are widely used in practice. Structured approaches provide a prescription and guidelines for how to go about the process of developing an information system, are relatively easy to learn and provide tools which are well suited to their task. However, the products of structured approaches are sometimes seen to be vague and imprecise since requirements are written using natural language or represented in the form of models which do not have a formal foundation. This vagueness or ambiguity can be the source of problems later in development of the information system. A possible solution to this is to represent requirements using formal methods since these are seen as precise and unambiguous. However, formal methods are typically only a mathematical language for representing requirements. They are often regarded as difficult to learn and use. Even though formal methods of one sort or another have been in existence for many years they are not popular and appear unlikely to become popular in the future.
One possible approach to providing the advantages of structured approaches and formal methods is to provide translation procedures from the products of structured approaches to a formal description in a suitable formal language. The work in this thesis follows this theme and is aimed at the creation of a translation procedure from an Object Role Model (ORM) schema to a Z specification. An object role model schema is the end product of a process called the Natural Language Information Analysis Method (NIAM) which is used to produce an information model for an information system. NIAM is a method which has been used successfully in industry since the mid 1970s and continues to be used today.
This thesis provides a translation procedure from ORM to Z which is less arbitrary and more comprehensive than previous conversion procedures in the literature. It establishes a systematic method for
(i) choosing suitable types and variables for a Z specification and
(ii) predicates that express all the standard constraints available in ORM modelling.
The style of representation in Z preserves ORM�s concepts in a way that aids traceability and validation. The natural language basis of ORM, namely the use of elementary facts, is preserved. Furthermore, an ORM schema differentiates between abstract concepts and the means by which these concepts are represented symbolically and this thesis provides a representation in Z that maintains the distinction between conceptual objects and their symbolic representation. Identification schemes of entity types are also translated into the Z specification but it is left as an option in the translation procedure.
Guiding and evaluating the work conducted here are a published set of criteria for the evaluation of a conceptual schema. These have helped in making decisions regarding the translation procedure and for assessing my work and that of others.
47
Kwan, Irwin. "On the Maintenance Costs of Formal Software Requirements Specification Written in the Software Cost Reduction and in the Real-time Unified Modeling Language Notations." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1092.
Full textAbstract:
A formal specification language used during the requirements phase can reduce errors and rework, but formal specifications are regarded as expensive to maintain, discouraging their adoption. This work presents a single-subject experiment that explores the costs of modifying specifications written in two different languages: a tabular notation, Software Cost Reduction (SCR), and a state-of-the-practice notation, Real-time Unified Modeling Language (UML). The study records the person-hours required to write each specification, the number of defects made during each specification effort, and the amount of time repairing these defects. Two different problems are specified—a Bidirectional Formatter (BDF), and a Bicycle Computer (BC)—to balance a learning effect from specifying the same problem twice with different specification languages. During the experiment, an updated feature for each problem is sent to the subject and each specification is modified to reflect the changes. The results show that the cost to modify a specification are highly dependent on both the problem and the language used. There is no evidence that a tabular notation is easier to modify than a state-of-the-practice notation.
A side-effect of the experiment indicates there is a strong learning effect, independent of the language: in the BDF problem, the second time specifying the problem required more time, but resulted in a better-quality specification than the first time; in the BC problem, the second time specifying the problem required less time and resulted in the same quality specification as the first time.
This work demonstrates also that single-subject experiments can add important information to the growing body of empirical data about the use of formal requirements specifications in software development.
48
Qamar, Muhammad nafees. "Spécification et animation de modèles de conception de la sécurité avec Z." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00716404.
Full textAbstract:
L'écriture de spécifications pour des logiciels en général et en particulier pour des applications sécurisées demande de développer des techniques qui facilitent la détection et la prévention des erreurs de conception, dès les premières phases du développement. Ce besoin est motivé par les coûts et délais des phases de vérification et validation. De nombreuses méthodes de spécification, tant formelles qu'informelles ont été proposées et, comme nous le verrons dans cette thèse, les approches formelles donnent des spécifications de meilleure qualité.L'ingénierie des systèmes sécurisés propose l'utilisation de modèles de conception de la sécurité pour représenter les applications sécurisées. Dans de nombreux cas, ces modèles se basent sur les notations graphiques d'UML avec des extensions, sous forme de profils comme SecureUML, pour exprimer la sécurité. Néanmoins, les notations d'UML, même étendues avec des assertions OCL, sont insuffisantes pour garantir la correction de ces modèles. Ceci est notamment du aux limites des outils d'animation utilisés pour valider des modèles UML étendus en OCL. Nous proposons de combiner des langages formels comme Z avec UML pour valider des applications en animant leurs spécifications, indépendamment de futurs choix d'implémentation. Le but de cette thèse est de présenter une approche pour analyser par animation des modèles de conception de la sécurité. Nous utilisons un outil pré-existant, RoZ, pour traduire les aspects fonctionnels du modèle UML en Z. Cependant, RoZ ne couvre pas la modélisation des aspects sécuritaires. Dans cette thèse, nous avons complété l'outil RoZ en l'associant à un noyau de sécurité qui spécifie les concepts du modèle RBAC (Role Based Access Control). Nous utilisons l'animation pour explorer dynamiquement et ainsi valider les aspects sécuritaires de l'application.Notre approche et les outils qui la supportent intègrent UML, SecureUML (un langage de modélisation de la sécurité), RBAC, RoZ, Z et Jaza, un animateur pour le langage Z. L'animation des spécifications prend la forme de scénarios définis par l'utilisateur qui permettent de se convaincre que la spécification décrit correctement ses besoins. Notre approche permet une validation dès la phase de spécification, qui prend en considération l'interaction entre les modèles fonctionnel et sécuritaire, et qui fait abstraction des choix de l'implémentation. Les éléments du modèle fonctionnel peuvent être utilisés comme contexte dans la définition des permissions du modèle de sécurité. Notre approche ne met pas de contrainte sur ce modèle fonctionnel ce qui permet de l'utiliser pour une vaste gamme d'applications.
49
Rogers, Jason Lee. "Secure distribution of open source information." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2004. http://library.nps.navy.mil/uhtbin/hyperion/04Dec%5FRogers.pdf.
Full text
50
Lei, Li. "Hardware/Software Interface Assurance with Conformance Checking." PDXScholar, 2015. https://pdxscholar.library.pdx.edu/open_access_etds/2323.
Full textAbstract:
Hardware/Software (HW/SW) interfaces are pervasive in modern computer systems. Most of HW/SW interfaces are implemented by devices and their device drivers. Unfortunately, HW/SW interfaces are unreliable and insecure due to their intrinsic complexity and error-prone nature. Moreover, assuring HW/SW interface reliability and security is challenging. First, at the post-silicon validation stage, HW/SW integration validation is largely an ad-hoc and time-consuming process. Second, at the system deployment stage, transient hardware failures and malicious attacks make HW/SW interfaces vulnerable even after intensive testing and validation. In this dissertation, we present a comprehensive solution for HW/SW interface assurance over the system life cycle. This solution is composited of two major parts. First, our solution provides a systematic HW/SW co-validation framework which validates hardware and software together; Second, based on the co-validation framework, we design two schemes for assuring HW/SW interfaces over the system life cycle: (1) post-silicon HW/SW co-validation at the post-silicon validation stage; (2) HW/SW co-monitoring at the system deployment stage. Our HW/SW co-validation framework employs a key technique, conformance checking which checks the interface conformance between the device and its reference model. Furthermore, property checking is carried out to verify system properties over the interactions between the reference model and the driver. Based on the conformance between the reference model and the device, properties hold on the reference model/driver interface also hold on the device/driver interface. Conformance checking discovers inconsistencies between the device and its reference model thereby validating device interface implementations of both sides. Property checking detects both device and driver violations of HW/SW interface protocols. By detecting device and driver errors, our co-validation approach provides a systematic and ecient way to validate HW/SW interfaces. We developed two software tools which implement the two assurance schemes: DCC (Device Conformance Checker), a co-validation framework for post-silicon HW/SW integration validation; and CoMon (HW/SW Co-monitoring), a runtime verication framework for detecting bugs and malicious attacks across HW/SW interfaces. The two software tools lead to discovery of 42 bugs from four industry hardware devices, the device drivers, and their reference models. The results have demonstrated the signicance of our approach in HW/SW interface assurance of industry applications.