《Formal MethodsCs Mwsu.ppt》由会员分享，可在线阅读，更多相关《Formal MethodsCs Mwsu.ppt（32页珍藏版）》请在三一办公上搜索。
1、Formal Methods,Contents,What are Formal Methods?DefinitionMythsHistoryTypes of formal methodsUse of mathematicsDo we really need Formal Methods?Design errorsEffects of design errorsThe promise of formal methodsThe Formal Methods DebateGeneral concernsWeaknesses in formal methodsSuccess of formal met
2、hods,What Are Formal Methods,Formal methods refers to a variety of mathematical modeling techniques that are applicable to computer system design.They include activities such as system specification,specification analysis and proof,transformational development,and program verification.,Definition,“F
3、ormal methods are mathematical approaches to software and system development which support the rigorous specification,design and verification of computer systems.”Fme04“they exploit the power of mathematical notation and mathematical proofs.“Gla04,Seven Myths of Formal Methods,Formal methods can gua
4、rantee that software is perfect.Work by proving that programs are correct.Only highly critical systems benefit from their use.They involve complex math.They increase the cost of development.They are incomprehensible to clients.Nobody uses them for real projects.,History,Formal specifications have be
5、en in use since the early days of computing.1940s:Turing annotated the properties of program states to simplify the logical analysis of sequential programs.1960s:Floyd,Hoare and Naur recommended using axiomatic techniques to prove programs meet their specifications.1970s:Dijkstra used formal calculu
6、s to aid to develop of non-deterministic programs.The interest in the use of formal methods in software engineering has continued to grow.,Definition,Formal is often confused with precise.A formal specification consists of three components:Syntax-grammatical rules to determine if sentences are well
7、formedSemantics-rules for interpreting the sentences in a precise,meaningful way within the domainProof Theory-rules for inferring useful information from the specification,What are Formal Methods?,Notation with precise syntax and semanticsDoesnt necessarily involve mathematicsAlthough mathematics i
8、s a formal notation There are levels of formulization.Techniques,methods,procedures,tools can support levels,Types of Formal Methods,A variety of formal methods exist:Abstract State Machines-The Abstract State Machine(ASM)thesis implies that any algorithm can be modeled by an appropriate ASM.http:/w
9、ww.eecs.umich.edu/gasm/B-Method-B is a formal method for the development of program code from a specification in the Abstract Machine Notation.http:/www.afm.sbu.ac.uk/b/Z A specification language used for describing computer-based systems;based set theory and first order predicate logichttp:/vl.zuse
10、r.org/“Unified Modeling Language(UML)provides system architectswith one consistent language for specifying,visualizing,constructing,and documenting the artifacts of software systems.”Visual notation for OO modelingExtensibleIndependent of programming languagesFormal basis for understanding the model
11、ing language,Other Types of Formal Methods,Others types include:CommUnityEstelleEsterelLotosOverture Modeling LanguagePetri NetsRAISESDLTRIO,Unity,and VDM Any programming language,Predicate Calculus,The first order predicate calculus is a formal language for expressing propositions.A properly-formed
12、 predicate calculus expression is called a well-formed formula or WFF(pronounced wiff).,Predicate Calculus,ConstantVariablePredicateFunctionConnectiveQuantifier,Predicate Calculus,Predicate Calculus,Whoever can read is literate.Dogs are not literate.Some dogs are intelligent.Some who are intelligent
13、 cannot read.,1.x R(x)L(x)2.x D(x)R(x)3.x D(x)I(x)4.x I(x)R(x),Levels of Rigor,Specifications,models,and verifications may be done using a variety of techniques.Level 1 represents the use of mathematical logic to specify the system.Level 2 uses pencil-and-paper proofs.Level 3 is the most rigorous ap
14、plication of formal methods.,Do we really need Formal Methods?Design errors,Digital systems can fail in catastrophic ways leading to death or tremendous financial loss.“Nas03Potential causes of failure include:physical failurehuman errorenvironmental factorsdesign errors-Design errors are the major
15、culprit.,Effects of Design Errors,Between June 1985 and January 1987,a computer-controlled radiation therapy machine,called the Therac-25,massively overdosed six people,killing two.On April 30,1999 Titan I cost taxpayers 1.23-billion dollars,all due to a software malfunction(incorrectly entered roll
16、 rate filter constant),Effects of Design Errors,Denver Airports computerized baggage handling system delayed opening by 16 months.Airport cost was$3.2 billion over budget.NASAs Checkout Launch and Control System(CLCS)cancelled 9/2002 after spending over$300 million.,The promise of Formal Methods,For
17、mal methods are needed to:Improve SW QualityReduce cost of verifying system Improve quality and rigor of entire development processReduce specification errors and provide a rational basis for choosing test dataExplore the properties of a design architecture,The Formal Methods Debate:General Concerns
18、,EvidenceNo Quantitative evidence Used with other techniques formal methods has led to highly reliable code;fewer errors and easy to test.Formal methods do not claim to remove the possibility of unwise design decisions.“San98ImpracticalityAutomatically generating proofs of program correctness are re
19、garded as unrealizable for realistic systems.Methods of automatically generating test cases that expose problems are available.CommunicationImproved documentation and better understanding of designs Difficult for untrained SW Eng/Consumer to understand specs.,Weaknesses in Formal Methods,Weaknesses:
20、Low-level ontologiesLimited ScopeIsolationCostPoor tool feedback,Success of Formal Methods,There are many examples of successful and cost-effective systems implemented using formal methods.Mainly in domain of transportation systemsAlso in domains such as:information systemstelecommunication systemsp
21、ower plant controlsecurity,Investigating Influence of Formal Methods:Case Study,Project:Praxis air-traffic control information system for UK Civil Aviation AuthorityUsed FMs before,not to this extentDeveloped functional requirements using 3 techniques:E-R analysisReal time extension of Yourdon-Const
22、antine structured analysisFormal Methods for specification and Design,Use of Formal Methods,Application Code:specification language to define data and operations(VDM Vienna Development Method)ConcurrencyFSM to define concurrency and invoke app codeLANMix of BDM and CCS(Calculus of communicating sequ
23、ential processes)Formal proofsUser Interface Code-pseudocode,Data,Quality in terms of faults and failures normalized by size(LOC)Reliability MTTFAssigned severity to failure reports(1-3)Documents and modules changed listedPartitioned data problems arising from code vs.spec/designClassified modules b
24、y type of design that influenced it,Questions,Did formal methods quantitatively affect code quality?Was one formal method superior to another?Answers:Quantitative evidence of high code qualityChanges to informally designed modules not significantly differentFewer VDM/CCS modules changed overallCode
25、developed using VDM alone required most changesFormally designed modules with fewer developers had fewer faults Overall significance between informal and formal methods is insignificantDifferences may have nothing to do with design method,but reflect those who use them:Quality was lower in larger gr
26、oups developing code together.,Lessons Learned,No evident formal design techniques alone produced higher quality codeFormal design with other techniques yielded highly reliable codeFormal specification and design effective in some,but not all circumstancesFormal specification led to simple,independe
27、nt components and straightforward unit testingFormal methods may be more effective acting as a catalyst for other techniques,such as testing,Success of Formal Methods,The following(abridged)list applications made using of formal methods:Ammunition Control System Architecture for a Family of Oscillos
28、copes B27 Traffic Control System Cancan Mediation Device Car Overtaking Protocol Control Logic Design of Robot Work Cells Data Acquisition,Monitoring and Commanding of Space Equipment Data logger for an implantable medical device ELSA(control system of a power plant),Why arent formal methods widely
29、used?,Software quality has improvedTime-to-market more importantUser interfaces are a greater part of systemsFormal methods have limited scalability,Formal Methods Humor?,What needs to be done to make“formal methods”industrial strength?,Bridge gap between real world and mathematicsMapping from forma
30、l specifications to code(preferably automated)Patterns identifiedLevel of abstraction should be supportedTools needed to hide complexity of formalismProvide visualization of specifications Certain activities not yet formulizable methodsNo one model has been identified which should be used for softwareFocus on WHY we use techniques and sell to managers,Formal Methods Humor?,
