New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Mrs. Carolyne Abbott

Dependability CS 686

Mrs. Carolyne Abbott
GPA 3.71

John Knight

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

John Knight
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 31 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 686 at University of Virginia taught by John Knight in Fall. Since its upload, it has received 30 views. For similar materials see /class/209676/cs-686-university-of-virginia in ComputerScienence at University of Virginia.


Reviews for Dependability


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15
Dealing With Faults DeallrlthhFaults w v mmm llarirlkn a4 Fundamental Principle Of Dependability Fundamental Principle of Dependability a the system requirements are captured correctly b all of the fault to which a system is subject ar determined an c the effects of each potential fault are mitigated adequately then the system will meet its dependability requirements DeallrlthhFaults H4 v mmm llnmkn a4 El Dealing With Faults Fault Tolerance Executiontime techniques that cope with the effects of faults Fault Forecasting Estimate current number future incidence and likely consequences Deallrlg WthFaults w v mmm llnmkn a4 Lack Of Dependability Earlier The reason dependability is less than perfect is Faults IVo faults I70 probem This is incomplete think about definition of failure Deallnth Faults lm v mlmm lln mu a4 Dealing With Faults Fault AvoidancePrevention Development techniques that prevent the introduction of faults Fault Elimination Development techniques that find and remove faults already introduced before system deployment Deallrlu wm Faults w vmmm lln mu a4 Dealing With Faults Fault Avoidance System Opera 39on s mates Deallnth Faults lln v rmmru lln mu a4 5 Technology Exploration Avoidance Degradation faulE Elimination X Design faulE Tolerance Byzantine faulE Forecasting I E gg DealinnghFaulfs H4 v mmm llnrlnkn e4 7 g Fault Avoidance DealinngFaults iin v rmmru in ma M E Fault Avoidance Faults never arise Perfect solution if it could be done Helpful if only possible for some faults Particular fault classes Speci c faults that are othenNise dif cult to Combine with fault forecasting to deal with imperfect avoidance DealinnghFaulfs w v mmm llnmkn m g Degradation Fault Avoidance By definition cannot be avoided they arise during operation In practice avoiding degradation faults can be approximated Careful manufacturing techniques Careful component selection Careful attention to infant mortality Rate of occurrence can end up very low DealinngFaults Hm v mlmm nu mu m m Byzantine Fault Avoidance Two major sources Highlevel data distribution Gatelevel circuit operating at logic limit Byzantine faults avoided by avoiding major sources Do not distribute data via multiple routes Manufacture circuits to keep devices away from the logic edge DealinnghFaulfs w v mmm llnmkn m n Design Fault Avoidance In principle can always be avoided Avoid by restricting practice Eg programming in HLL Initialize all variables No assignment in C Boolean expressions Always an else clause in case statements Programming guidelines eg Ada 95 Quality and Style GuideMes for Professional Programme5 DealinngFaults Hm v mlmm nu mu m 12 Fault Elimination DealinthhFaulfs w v mmm llnrhkn a4 Degradation Fault Elimination System might contain degradation faults prior to delivery Defective components used Components failed during system assemny Systematic search Careful analysis of infant mortality rates DealinnghFaulfs H4 v mmm llnmkn m Design Fault Elimination Example Software faults Four steps Software produces wrong result Testing Identify cause in software Testing Repair software Make sure Testing Very common for repair to introduce new ault DealinnghFaulfs H4 v mmm llnmkn m Fault Elimination Find faults in system prior to deployment Systematic search process Starting point Fault categories System design Fault trees Related information Process needs to be exhaustive DealinngFaulfs w v rmmru Hr mu a4 Design Fault Elimination To eliminate a design fault four critical steps needed Presence of the fault has to be detected Fault has to be identified Fault has to be repaired Resulting new design has to be veri ed to ensure no new fault has been introduced by removal of original fault Search process for design faults DealinngFaulfs w v rmmru Hr mu m 9 Fault Tolerance DealinngFaulfs w v rmmru Hr mu m Faults and Dependability W K mmm llnrhkn 4 mam raumowmdablw Hm v rmmru llnrhkn 4 Failures Faults and Errors Failure Delivered service deviates from correct service Component vs system Erroneous state error Part of system state that might cause a failure if nothing is done about it Fault The adjudged cause of an error Degradation vs design vs Byzantine faults W K mmm llnmkn 4 A Bug In One Program Bug raumowmdablw Hm v rmmru llnmkn 4 Erroneous State Disk Printer raumowmdablw W K mmm llnmkn 4 Lack Of Dependability The reason dependability is less than perfect is Faults IVo faults I70 probem raumowmdablw Hm v rmmru llnmkn 4 539 Fault Characteristics Manifstation39 Dormant Active present and does cause an error Du ration Permanent Fault it breaks and stays broken Transient Fau it breaks but then appears to be OK again rare amp Deperaarrr present but does not cause an error Types Of Fault Degradatio Something broke Design Something was built incorrectly Byzantine Something arbitrary happened Fault amp Dependabilit Types Of Fault Degradab39on vs deslyn vs Byzan 39ne This is a CRITICAL a l39s 39ncbbn Why Because We have to predict all fault instances We have to deal with all fault instances Different fault types require different techniques for identification and treatment To the extent possible we have to do this perfectly rare amp Deperaarrr 5 And Now For Something Relatively Normal Fault amp Dependabilit m Degradation Faults The system used to work but now it does not Examples Light bulb burns out Something broke for some reason Physical damageivibrauon humidity temperature infant mortali End of useful lifeAWear out rate amp Deperaarrr Bathtub Curve lg Lifetime Degradation Faults Pmbahlity cf Failure Fault amp Dependabilit lZ Q And Now For Something Completely Different Fm a Dependsn x3 Design Faults The system never worked Nothing broke The design is awed Examples lncorrecte ecmca Wmng Software defectgbut be very careful Wrdw Ms What is a design Tne system39s componene and now they are nterconnected my a Wham m Design Faults vs Software Design Software Lifecycle Dsign Faulis Fm a Dependsn l5 Software Fault Manifestation So ware Heisenbugs vs Borrbugs Jim Gray Error always occurs Bohrbug Error sometimes occurs Heisenbug Causes Of Nondeterminism Concurrency I Different Data Failure To Initialize Data HardwareSoftware Interaction my a Wham is Q And Now For Something Else Entirely Different Fm a Dependsn n Clock Drift Clocks drift even ifthey are built well Many systems incorporate multiple redundant clocks To bound error clocks need to be synchronized This is not hard imple solution midvalue select my a Wham xx MidValue Select Time 100 2 Jun 110 3 Time 110 OK Everybody Synchronize 4 Jun D 110 90 100 110 W K mmm llnrinkn 4 90 100 110 Byzantine Faulty Clock 100 100 105 110 3 Different Values 5 0K Everybody Synchronize Y Y A o 4 90 100 11 90 ma 110 y r 90 110 110 W K mmm llnmkn 4 El Dealing With Faults Fault PreventionAvoidance Fault Elimination Fault Tolerance Fault Forecasting Faumowmdablw H4 v mmm llnmkn 4 Faulty Clock 100 a 60 100 110 iv Same Value 0 0 I l 50 100110 soma11 i 110 110 OK Everybody Synchronize Faumowmdablw Hm v mimm llnrinkn 4 Byzantine Faults They are real they do occur Mostly associated with data transmission They are caused by many physical effects including Voltages and clocks at marginal levels Faulty connectors Electrical noise Other external sourcs cosmic rays etc Voting solution is very expensive Faumowmdablw Hm v mimm llnmkn 4 El Dealing With Faults Fault AvoidancePrevention Development techniques that prevent the introduction of faults Fault Elimination Development techniques that find and remove faults already introduced before system deployment Faumowmdablw Hm v mimm llnmkn 4 5 Dealing With Faults Fault Tolerance Executiontime techniques that cope with the effects of faults Fault Forecasting Estimate current number future incidence and likely consequences w x mmm llnrirlkn a4 Anticipated Faults You can t tolerate what you don t expect But if we expected it we would avoid or eliminate the fault In general We can itemize the classes of faults that can occur We can define what we want done if the fault occurs and if the error is detected w x mmm llnmkn a4 27 Dealing With Faults Fault Ellmll iahol i Fault Tolerance Fault Forecale n su mates Faumommabiit w x Himm llnmkn 4 29 Dealing With Faults at Faul Avoidance Fault Ellmll iahol i Fault Tolerance System Opera 39on Fault Forecasting Rate SD FauszDwmdablllty lm x mimm llnrirlkn 4 Anticipated Faults Some examples Lightbulb Filament burns out Overheat and burn nearby material Do not expect it to explode Automobile tire Lose air Do not expect it to experience electrical overload FauszDwmdablllty lm x mimm llnmkn 4 2E Component Failure Semantics Component 39 How much damage to the system occurs when a component fails It might be a ot Example an Ada exception Failure semantics de nition of dama e Components that are expected to fail must have prede ned failure semantics Fauts amp Dwmdablllw w xmimm llnmkn M an Formal Software Specification Famal peu tanun Hm v mmm in ma A What Goes Wrong Am big u ity You meant what exactlyquot Incompleteness You didn39t say what to do for that inputquot It seemed like the right thing tn do with that cond39tion quot Inconsistency When the user selects this menu item do thisquot If the user selects this menu item do thatquot Famal peu tanun Hm v mmm in ma A Software Specification Remember software specification derives from system design FUmalSpE ta m Hm v n ma in mm A What Goes Wrong Wrong functionality But we always display a dancing pig on the screen when the aircraft misses the carrier deck What are we supposed to doquot Naivety Implement a company wide email system on that 10 yearold PC in the cornerquot Etc Software engineers are not quali ed to malre important decisions about functionality FUmalSpE ta m Hm v n ma in mm A Real Specification As Opposed To Class Assignments eal specifications are Complex Dif cult to write correctly Dif cult to write clearly In practice specifications are I 39 Incomplete Erroneous 6 wt Let s look at some real requirements Famal Spen tanun 2 Jam c Krith 2mm All Rm Resaved glPacemakerDefib Requirements The Guidant VENTAK PRIZMTM AICD automatic implantable cardioverter defibrillators are designed to detect and terminate ventricular tachycardia VT and ventricular fibrillation VF and provide bradycardia therapy atrial andor ventricular pacing Therapies include both Iow and highenergy shocks using either a biphasic or monophasic waveformquot Famal Speci tanm 2 Jam c KFIQHI 2mg All Riuhts Resaved 5 SPacemakerDefib Requirements Monitoring the heart Pacing as necessary Defibrillating as necessary Operational parameterization Communication with programmer Hardware fault tolerance management Extensive patient data recording Formal Specification John C lmight 2009 All Righls Reserved 7 E PacemakerDefibrillator Images courtesy of Guidant Corporation Formal Specification John C lmight 2009 All Righls Reserved 8 E Why Do Software Systems Fail To a first approximation requirements specification is the dominant source of problems in safetycritical and high assurance software systems Formal Specification John C lmight 2009 All Righls Reserved 9 Why Do Software Systems Fail Majority of safetycritical defects derive from poor requirements Lutz Majority of all defects derive from poor requirements AF Rome Laboratory The hardest single part of building a software system is deciding precisely what to buildquot Brooks Formal Specification John C lmight 2009 All Righls Reserved 10 Why Do Software Systems Fail It is not the internal complexity of a module but the complexity of the module s connection to its environment that yields the persistent safetyrelated errors seenquot Lutz More has been screwed up on the battlefield and misunderstood at the Pentagon because of the lack of understanding of the English language than any other single factorquot Vessey Formal Specification John C lmight 2009 All Righls Reserved 11 Why Are Specifications Important Errors Caused Errors Fourd ERRORS rements Specificaitons Design Implement Testing A alysis Requi n Formal Specification John C lmight 2009 All Righls Reserved 12 Why Do Software Systems Fail x mm You To SIAKT to own HAVE 0F Au MY worms 39I LIKE THE DODMiD Formal Speu canun e Jchn c mum 2mm All Rights Reeved 13 1 Software Faults Introduced in specification Commission Omission I am notreferring to Requirements changes Requirements creep Specifications are extremely problematic System is not clearly defined is not an appropriate excuse Famal Spem tatim e JDhnC KnghthQ All Rm Reserved 14 Requirements Analysis Incomplete requirements are common Don t confuse requirements capture with system development they are notthe same Requirements analysis requires user dialog Dialog might include Prototype development Case studies Model development However specification must be complete FormalSpeu cannn w v w nru Hr m 4 15 Requirements Analysis Investment in requirements analysis always pays 0 Requirements mistakes are the most expensive to i Iterative development of specifications is perfectly reasonable and common Exploration of problem space is expected Introduction of computer system changes m FamalSpem catim w x m me llnmkn r1 5 Natural Language Most specifications are written in natural language English We are trained throughout our education to use it It is very powerful but not adequate Problems with English Ambiguous Imprecise Not formally de ned Dialects Formal Speu canun e Jchn c Kniul39vt 2mm All who Reeved 17 150 At Least Use Formal Speci ca on For Software Famal Spem tatim e JDhnC KnghthQ All Rm Reserved 1E Any notation with precise semantics can be used Formalism typically applied to just part of a speci cation Notations use discrete mathematics some graph speci cation Z or VDM for data manipulation Statecharls for system states and transitions Natural language for nonfunctional speci cations Famal peu tanun rm v MVWFD in ma n 539 Notations For Formal Specification ics Several notations are sometimes used in the same Recall Formal Specification Improved accuracy and completeness lflrlm lha ll39i iiari remis Reader npnmd Establish useful properties understanding of the speci cation Famal Spm ta nn l l39rl K r14 7WD ll R HM R A 2 Types Of Languages Procedural Computation de ned by desired sequence of actions computer is to perform Most highlevel languages are procedural Declarative Computation de ned by desired state that computer should be in Many speci cation languages are declarative Functiona Computation de ned as desired function computer is to evaluate Most functional languages derive from LISP Famal Span tanuri a John c Krith mm Al mum Rzaved Formal Specification There are lots of good notations eg va z o Statecharls 0 SCR o RSML o Larch Benefits of use turn out to be Communication Analysis Clearer funkrig by speci er FUmalSpE ta m rm v m mo in mm n Formal Specification Goals of formal specification Complete consistent concise unambiguous specifications Valid specifications state exactly what the user wants Specifications based on formal semantic model Formal semantics permit degendabe communication between all parties Case studies show a variety of advantages FUmalSpE ta m rm v m mo in mm n Types Of Languages Highlevel language programs are actually speci cations Compilers write the program for you So you have been specifying programs not writing them The big difference in languages is Declarative Says nothing about How just WHAT Procedural Says nothing about WHAT just HDW Famal Spetl tanm a John c Knuht 2mg All Rights Rzaved 24 y and m Punt iyi Declarative nce x gt u M wz lt x Aim lyll 2 gt x a Natural language The program shall read one positive input and wrim one ou u that is the inmger square root of the input The output squared shall be less than or equal to the input and the output1 squared shall be greater than the input Famal pecl tanun we r mtmm in mu 1 5 Mode Based Specifications State Description See relauoris etc lrivariari Predicate Calculus 1 l I t I I amp IkePost Condx w Pre Condition Post Condition What Has To Be True lieore Ari What Has To Be True liftsAri Operation can Be Applied Operauon ls Applied Famal pecl tanun we r mtmm in mu 1 When Means Equals In procedural language assignmentmeans Use values ofvariables on RHS to compute value of variable on LHS Example a b c What about a Old value ofa used l1 compute new value There are two as eclarative languages have predicates with equaling not assignment Famal Specl tannri to John c Krith mm All Rights Resaved 29 Mode Based Specification Do not confuse with modelbased development Literally build a model of the system you want Components System state State changs 555 and mc 39ons Pre A Post Condi 39ons Predicate Calculus A modelbased specification is much like a program But a modelbased spec catbn is NOT a procedural program Famal peti tanm we r H mu in ma 1 E General Forms SpeCI lcation System State Programming Similar To i LEE litmus 1 System Operation is macro ans D Famal peti tanm we r H mu ii all ma 1 When Means Equals In operations need to be able to refer to Before state values for preconditions what must be true lieale operation is applied After state values for postconditions what must be true afteroperation is applied Special notation primed varables Variable nam 39 Variable name39 is after state Example Precondition a lt 1 Predicatesl Postcondition a a b Famal Spam ta m to John c Knght 2mg All Rights Resaved an How wouidWe tStat eiTl39iiS Formaiiw Collecuon of student grade records Famal Speci tannn T m vmmm iin mu a Using ModelBased Specification Written in a formal language so Check the syntax ie use of language constructs Check the typs ie use of variables You can39t do this with natural language Review the specification with all parties Clear communication unambiguous meaning You can39t do this with natural language Build an implementation to make it so Develop tests from the precise speci cation Famal Speci tannn T m vmmm iin mu a Things To Note This is a declarative speci cation It is written in Z There is no prescribed algorithm The order of the clauses can be changed and it means the same thing It is a complete specification of sort It includes detail that might easily be forgotten or assumed Engineers can understand this type of thing quite easily Famal Speci tanon 2 Jam c Krith 2mm All Rm Rzaved Important Reme b r We are talking about a speci cation We are nutmlking about a program We do not know the actual GPAs we are going m work on We cannot include them in the speci cation explicitly so we need a way ofsaying what they are like Operation is a predicate that says The Implementation Must Make This True When It Executes FamalSpeti tanm Hm v n ma iin mu Simple 2 Example Implement the following specification in Java Integersort IP N Output 52 N N 61 View Vk leeOutputlkelnw A v 1 prut rl aqwl s Outpumum v a1np14t7lt160v3x leelnpu xgtlOCOA Msg quotInvalxdmpu 39 Famal Speti tanm T m v n ma iin mu Another Simple 2 Example Requirement An autopilot program an maintain an aircraft s altitude to a preset value within a speci ed tolerance Specification details Ifcurrent altitude is below preset value then adjust elevators to climb And vice versa Note imprecision in both requirements and specification Ask your self whether you could implement the specification as you build the specification Famal Sueti tanm o Jnrn c Knght 2mg All Rights Rzaved Programming Languages And Correctness By Construction Implementation Fault Avoidance Implementation Starting with a specification hopefully formal and pro ably in a declarative language we have to develop an implementation Implementation written typically in a highlevel programming language Butthe program is the bitsthat go into memory Neverforget that w menru llama a What Goes Wrong Wrong functionality commission Missing functionality omission Incorrect management of resources Processors in concurrent systems Storage in all systems Files and the IO devices in all system Unanticipated exceptions Translation and library faults Fault in generated code wrong library defective libra wron implementation instance defective linker or loa er w menru llama a Pedagogical Goals Be aware of the problem areas that arise in implementation Be familiar with the limitations in various programming languages Become familiar with the concept of correctness by construction Understand the principles of static analysis w vmmnu llama a Uhker amp Laadsr Liner392 l L w vmmnu llama a Programming Languages Eosd languages do not guarantee good software u Good languags can help the developer Poor languages can hinder the develop Many classes of mistakesong reco nized to derive from language faCIlities led o Safequotsubse13 of some languages Standards that ban known problematic practices Programming Ian uage is the most fundamental too that the deve oper has Language choice should support dependability goa s w vmmnu llama a g Examples Of The Problem Taken from A Software Fault Prevention Approach in Coding and Root Cause Analysis by Weider D Yu Obtained from analysis of several million lines of code in the Lucent 5ESS switching system mostly C Project goal fault avoidance with large systems written in Ha Kmrmru llama n 7 g Examples Of The Problem Nearly 50 of the errors found were low level coding errors rm Kmrmnu llama n g Operator Precedence 1f blkptrrgtrptheadfltdesc amp hashigher precedence than amp LTCLAS HWMATEFLT Should be corrected to 1f blkptrrgtrptheadfltdesc amp HME LTCLAS H LT m mretrytti Eq al precedence but assoclate right to I ft Should be corrected to w e5 it mean to numretry increment the pointer then dereference it w Kmrmm llama n g g For Loop Control for 1dx El 1dx lt 4n d15p5tr1ngidx coTsuccess 1dx Should be corrected to This is actually compiler for ldx u ldx lt 4n 1dx l dependent d15p5tr1ng1dx COTsuccess1dx l w Kmrmm ill m n SI Logic Faults on Lucent 5ESS Use ofuninitialized Assignmentaqua variabls Bit elds not unsigned or enum Misuse of break and continue slatemeng Incorrect Ioglcal AND and mask operators Operamr precedence Preprocessor condltlonal Loop boundar 5 errors INdEXing DUBide arraYS Comment delimiters Truncation of values Unsigned variables and Misuse of pointers CPmPar sons Incorrect AND and OR tsts 39 M39suse 0f type cast39ng rm Kmrmru llama n n g Project Results Techniques developed to help reduce number of coding defects of this type Effect was a 345 reduction in rate between release Tand release 739 Corresponding reduction in test costs was 183 testing cost per source code line Cost of techniques 100K cost savings in rework and testing 7M yes you can do it Is this good enough rm Kmrmru llama n It is basically typeless Syntagtlt is confusing Pointers are the wrong semantics for parameters Most training is totally inadequate Why use a defective tool and then try to x it with a set of restrictions Develop a better tool If you must use C be velycareful What Is Wrong With C What Happens In Practice 1 I w vrwanru Hr ma a 13 w vrwanru in ma a 14 Programming Standards 5 Some Programming Standards Could all this be avoided with standards Motor Industry Software Reliability In principle Yes Association MISRA for C In practice N0 httpwwwmisraorgulg 39 W2 quotgt I f f d Free Software Foundation for various things an ar sare rareyl ever en orce I systematically by tools httpwwwgnuorgprep standardst Standards are never complete I Ada QufilltY amp Style GUldellneS For Fault avoidance is not the primary goal of most meesswnal Programmers standards httpwwwadaicorgdocs95style95stylede W WWW in M A 15 W WWW in M A 15 mm lVWWV misra urg uk g MISRA C Standard Ada A Superior Choice MISRAC Rule 47 Project instigated by Department of Defense in No dependence should be placed on C s operator ate 19705 d le 39 39 prece ence ru 5 m expressms All DoD projects expected to use It MISRAC Rule 59 Intended to replace plethora of languages in use The statements forming the body ofan if else if at the time more than 500 elsewhile dowhie orfor statement shallalways I Ori inal standard released in 1983 Ada 83 be enclosed in braces Egased on Pascal MISRAC Rule 66 Result of extensive design competition Ony expressions concerned With loop control Two major language revisions since then Ada 95 should appearwlthln a for statement and Ada 2005 w vrwanru Hr ma a 17 w vrwanru in ma a m g From The Ada 2005 LRM The need for languages that promote reliability and simplify maintenance is well established Henee 39 o s 5 S as s 39e s o e o ions ave been avoided syntax ofthe language avoids the use ofenco ed more Englishlikeeonstruets Finally the langu same degree of checking between units as within aunit Tlrri xmtmm llama rt emphasis vims placed on programre ili overeaseofwr mg ple es of thel guagereq that gr lablesbeexplicitly declared and thatthe39 t pebespecl ed sineethet o avari 1 var teom erscan e ins i les are Q What Is Ada Systems programming Precise control of machine representation Access to systemdependent elements Bare machine targets no operating system Standard packages for many purposes Comprehensive support for separate compilation Comprehensive support for numeric types in particular representation on target Tlrri xmtmm llama rt SI E 9 Separate Compilation Essential capability in any development enVIron ment What are the semantics Typically language semantics D erentfor separate compilation Parameter types and number not checked Relies on system linker and utilities like make Ada semantics Lazy compilation identical to le include Linking is part of compilation Dependency checking is part of compilation Tlrri xmtmm llama rt Q What Is Ada Targets include Embedded systems Longlived complex software Eliminate as man known dan erous elements of existing languages as possilee Objectbased and objectoriented Parameterized types generics Realtime concurrent programming Comprehensive exception handling Powerful type system Tlrri xmtmm llama rt Q What Is Ada No language subsets permitted Language extends to Iinktime Compiler validation procss Z I compilers required m pass very comprehensive test suim Ada Compiler Validation Capability ACVC ANSI and ISO language standards Has a complete infrastructure Compilers and other tools Careful and detailed definitions Textbooks amp training Cannot cover much of language here Tlrri xmtmm llama rt g Correctness By Construction Could we do better than languages like Ada Yes build implementation so that correctness accrues from the construction process Small part of this is to use a programming language that precludes as many fault sources as possible What next Need an approach or approaches that help the engineer to the extent possible Tlrri xmtmm llama rt g C By C Three Approaches g Correctness By Construction Ahmad Canasta Synthesis is clearly best but limited at present Re nement is good but very restrictive Analysis is fairly general and works well Analysis tends to produce Vastly better software Cheaper software surprisingly Basic thesis of the SPARAda project Basic approach also developed for C and Java SPARK is nata toy used in many industrial development projects Synthesis Eg SimLIink Refinement Analysis Eg SPARK the hnetmm iinmn rt 2 the hnetmm llama rt g Resources g Overview programming language with precise wellede ned syntax and htt wwws arkadacom tics Technical materials SPARK uses an Ada subset I Annotation mechanism designed m allow lowlevel Publlcatlons espemallv sperifirah39un of software htipwwwsparkadacomdownloadsSpARKgspdt SPARK uses stylized commens Etc Code built from lowelevel design not directly from highelevel 39 speci ica ion High Integrity Software The SPARK Ada Analysis tools to establish important properties about code A roach to Safe and Securi relative m lowelevel specification pp Verification that lowelevel design implemene highelevel John Barnes Addison Wesley 2003 speci cation is a sepaam issue n SPARK provides Correctness by Construction Peter Amey Bomber Simpli mpmm the hnetmm iinmn rt 27 the hnetmm llama rt SI SPARK Application Example g SPARK Application Example Lockheed C130J avionics upgrade Civil certi cation to DO17BB level A Military certification to UK Def Std 0055 Coding in SPARK Ada Signi cant errors found by static analysis in code already passing DO17BB level A SPARK code only 10 of residual errors found in full Ada Cost of MCDC testing reduced by 80 Ada found tohave only 10 of the residual Lockheed claims errors found 39n c Code quality improved by 10x over industw norms 39 Programming language does matter Productivity improved by 4X Remember the use of C in safetycritical Developmentaasb wens 50 aftypiazl systems is This is cast effec ve he hnetmm iinmn rt 29 the hnetmm llama rt SPARK Software Concept SPARK Development Process Develop or emanoe mp the annobanons to Ina13 ageles i ntyemm39gsl l Loader Charmin Vt h s rb et SPARK TDH enhance somare to implement Ughs s 39 Executable Software speo canon documenmd by annotations Hm ymmm llama A 31 Hm ymmm llama A 32 SPARK Analysis Simple Example Data Flow m z Demmmmeweme AnaleiS es seems 1 mm x39 t IEdtcomp1le my Emma 3 34 m w s s N W e ems Feeksge hady swxesaa 3 Examine mince else game Control How L K m X gt39 ill u hegm 39 r I a I e x s 1 N x t men see it s 1 see it t man sees 39SWWSH P055 summar z e z ISimpll er om g Functional Simpli sr quot39 ess iZZS Z Z X 39 N Y Z Yquot ISummar COMSCWSSS 3 u quot Pruier z e n eruan post 1 Nomehg level a speci ca ess iwesss w t mm us As a A 33 Hm ymmm llama A 34 Verification Condition 1 Proof Summary FD pethlsl tam stett ED tunetme check assaclaced mth statement at me 5 VEs a ancEduxeisum ancEduxeisumil m x gt l l l es emvee In e l l l i anm lTa lvcg i sw l pm i ptv l False l TEI nu l u 1 lstett l ttt check a 5 l l IESl l l l l gexiflxst 2 l stett l ttt check a 7 l l was i l l l i get Jail 3 l stett l ttt check a 7 l l was i l l l l gexiflxst 4 i stett l ttt check a a l l was i l l l l g2 last 5 l s l ttc check I3 5 l was i l l l l 5 l stett l essett a 9 l l was i l l l l 7 l9 l essett a 9 l l x39Esl l l l l a l stett l ttt check a 12 l l was i l l l l 9 i stett l ssett a brush l l was i l l l l gt m l stett l se a brush l l was i l l l l x gt7 ntegexiflxst n l s l I3 l l was i l l l l x lt nEEgexilasr Hm ymmm llama A E Hm ymmm llama A as SPARK Ada Subset Items removed include erics xoep ions Dynamically sized arrays Implicitsu typ Result remains a powerful and useful language Hm xmtmm llama n 37 SPARK Ada Subset A subset of Ada Any correct SPARK Ada program is also a correct Ada program True Ada but impossible to wrim erroneous program in the sense of the Ada LRM Logical soundness no language ambiguities Formal de nition of syntax and logical semantics Subset removes the troublsome parts of language Security all language semantic rules are ef ciently machinecheckable Hm xmtmm llama n so SPARK Ada Properties Bounded time and space rsources required calculated staticall Expressive power industrial strength applications SP RK Ada has minimal runtime requirements No basking originally now relaxed No exception handling No need to verify complex runstime system Hm xmtmm llama n w SPARK Ada Includes but is not limited to39 Scalar types numeratr39on character Boolean oat xed Array types and strings Records Full range of expressions Stammen 7 ssignment case loop if exit procedure call entry call return delay K m s Complem separation of speci cation and implemenmtion Inheritance Tasks including entries and entry calls Separate compilation Hm xmtmm llama n 40 What Did SPARK Ada Omit asks Much omitted Ravenscar pro le remains Many aspece otrasxlng innplt proot Exceptions complex dynamic control ow innple proor Generics templams No fundamental expressive power pes e naraoenmr Access types Pomtels Dynamic allotanm is a leichle to dwmdabll V451 to Dme that storage is Deva exhausmd dullrl execlmorl cererally inteasiole Also need to msule no memory leaks no danoino Dumas etc N te The Java approach is rim a solunm Hm xmtmm llama n 41 Formal Semantics Example wh11e statement What exactly does it mean Model Rewrite while using model Conditions Branches Assignment ioms Basic building blocks of computation Hm xmtmm llama n 42 Loop Invariant while a loop end loop How many times is s execute We have no ideaiit depends So how can we prove Invari 39 anything t Documene ioob number ot True betore and atter loop b Not true dunng loop body Ari algebraE lagEaewres39sian Allows iogc statement atter loop n tine computaoon ot dnei d on the data during execution iterau oris does not matter ody llrri xrintanru uan n o matter now many umes executed oop Loop Invariant Example Simple program to do integer division gtlty g u I r x lnnp xit when r lt y n r r i r r r e y True for end ioo Pr No iterations oOneiterauon Loop Invariant Any number of iterations in r r gt 0 The SPARK Annotations Language m is own ngnt Embedded m commene dnat beg SPARK is tine Ada subset camb39n Annotauons de ne Somvare sbeoncaoon intended dependencies between data items Thus two types of annotations Proof Speorcaoon tor broototoorrectness properties Data ow 1 forming the moi about yanoos s Tnose dnat constitute formal speci cation understandable llrri y mtmm nu ma ouroeroode re ll l quot3 ed with tne annotau on language iatonsnbs ottne code make code more Annotations should be written before code is written Simple Example Barnes package ndoneter quotu m mn rote Inleqex procedure Zexni39l39xlp quotu qlnhal runction Readi39l39xlp return Integer quotu qlnhal in mp runction Readi39l39nlal return Inle quotit qlnhal in rote e Inc quotu qlnhal in out mp Toto sen deriues mp rron mp L rote rron rote quotu post Txlp Txlp 1 end rote e rote llrri y mtmm nu ma Properly Se arated Speci cation An n otated Think OfThis n Interface 1 llrri xrintanru uan n Annotation Example Barnes Basic procedure specification says very little pro ore o d x in integer Merely a procedural statement No notion of declarative speci cation in the code Annotated procedure speci cation says a lot IDEtalirm l I new procedure nddx in integer quotat io n in out Ta 3 quotat deriuee Tntal rum Tntal x quota re x gt 0 quotat past Tntal Tntal x llrri xrintanru uan n Simple Example Barnes package had ndoneter is mp Toto Integer procedure zero mp is necin mp e end zero mp Implementation Th ink Of Th is 1m Readi39l39xlp return Inleqax is As class return mp end Readi39l39xlp runction Readi39l39nlal return Inteuer i l 1 Hm xrintanru Humid n 46 Discrete Mathematics A Brief Survey See me if this is unfamiliar Doom MimieiesmimWinmi x Universitv arVirginia I ite SpVeCIVI ca39tion As A ModelBased Specifications State Description See relations etc lrivari ans Predicate Calculus Pre Condition Post Condition What Has To Be True lieore An What Has To Be True AfterAri Operation Cari Be Appiied Operation is Appiied Propositions Propositions n A proposition is a statement that is either true or false Aiice isA SuperUSei Edit is A USER Command 1 Such statements can be formalized as propositional variables Aiceiisiaisupelusel EffLIE USERJommand 1 Carefully distinguish between I A symbol Aliceiisiaisupelusel I A meaning Aiice i5 a super user Examples El The Sun is shining El The Earth is a planet El A term in the Senate is six years El It is dark outside We can represent these propositions as propositional variables The Sun is shiningquot I e The Earth is a planetquot I t A term in the Senate is six yearsquot I d It is dark outsidequot Propositions And Specification El State what has to be true when the software runs El Nothing about how El Implementation written to make it true I Informal example what is this I Input a positive real number I Output a positive real number I Output Output Input I Note equalitynot assignment Propositional Expressions a Complex proposltlol ls bullt usll lg loglcal operators LOGIC NAME SYMBOL lMTulTlvE MEAN NO I Negatlurl a l Curllurlctlurl A and l Dlslurlctlurl v or I Impllcatlun 3 when l Equlvalence 3 same as El Truth tables tabulate results of loglcal operators B B A A aA AA E T E E E T T T E E T E E T E E E T T E T T T T Examples El Recall the propositional variables I s unis shiningquot I e The Earth is a planetquot I t A term in the Senate is six yearsquot It is dark outsidequot El Here are some expressions I a e I at I s d I a s 3 d Uses Of The Operators ashortpassword singleuser multiuser Iegaluser passwordcorrect singleuser 3 nouserlogin superuser cgt allfilesreadable Implication Uses Of Implication a Following naturallanguage 39agments translate to A 3 B I gt I IfAthel39l B B M Aorll AIS sufflclel39lt forB IS n cessaryforA 1 Example oany natural language can be confusing El BE CAREFUL WITH IMPLICATION MAJOR SOURCE OF ERRORS p1 3 p2 does not mean p2 3 p1 Complete Example ii Speci cation for very simple shutdown system for a nuclear reactor ii Propositional variables and their meanings Shutdown System Specification ii Speci cation a set of propositions coreitherrnalialarrn reactorishutdovyri A udibleialarrn buildingiradiationialarm 2 reactorishutdovyri A audibleialarrn reactoripovyerihigh coolingisystemion A Sensorisysterniori operatorsioniduty reactoriowipowel 2 operatorsioriiduty ii Predicates are l Expressions containing yariaoies l Booiean yaiued expressions wnen yanaoies naye yaiues ii Typical predicates de ne relationships in Example predicates l Expressions ouiitwitn reiationai operators lt 2 gt ii Compound expressions are built with operators from propositional calculus ii Examples temperature lt lemperalurejimil riiesize lt 7000 A daierastref lt 700 l coolingisystemion cooiing waterpumps working I sensorisysterniori aii sensors working I operatorsioniduty aii operators in controi room I rea toripowerihigh reactorati MWatts l eactoripowerilow reactoratio MWa l rea tor nutdown reactorcore snutdow l coreitherrnal aiarm tnerrnai sensornastnggereo l buiidii igiradiatioi iiaiarm radiation sensor nastnggered audibleialarm piant emergency warning sounds P red icates Quantifiers ii Propositions cannot express facts easily about classes of D Examples l lfariy one ortne controi computers is not available tne airtrarric controi system must not opera e I All ortne riies in tne riie system tnat naye oeen cnanged since tne iast backup was taken are scneduied to be written to tape in Quanti ers are a notation for expressing facts about classes Quantifiers Three quantifiers are I Existential 3 Fact is true for at least one member of a class I Unique 31 Fact is true for exactly one member of a class I Universal V Fact is true for every member of a class i Quantified expressions are propositions they are either true or false Existential Quantifiers a General Form 3 variablelist predicate o predicate Bound Variables in Where variablelist is a lists ofvariable declarations predicate and predicate are predicates predicate restricts quanti ed variables predicate de nes the truth or falsehood of quanti er a Read 3 There Exists Such That ForWhlch Existential Quantifiers El Unique existential quantifier is identical except there is only one item in the class El Examples 3x110evenxoxlt3 True 3 p P userprogramp o runningp Eij1100ij1oiij739 2 False 3 le F modi ed le o sizefile gt 1000 Universal Quantifier D General Form V variablelist predicate o predicate Bound Variables in Where variablelist is a lists ofvariable declarations predicate and predicate are predicates predicate restricts quanti ed variables predicate de nes the truth or falsehood of quanti er Universal Quantifier n Exam pies V x 110 evenx o x x lt 100 False V p P userprogramp o userp V s Student cs686s o smarts True V le F modi ed le o backupflle a Read V ForAll i Such That ltls The Case That Sets Sets El A set is An unordered collection of items wi out replication El Elements come from a Universe of elements El Sets can be defined by enumeration coo red green blue grey sizes 1 3 10 7 36 people Jack John Jim Joanne El Sets can also be defined by comprehension l Sometimes called set builder notationquot Set Comprehension El An elegant compact notation for defining large sets El Syntax of comprehension signature predicate o term El The signature declares variables El The predicate I Restricts the values of the variab es I Can be omitted omit also for default case of true I The term I Is an expression de ning the structure ofset elements I Can be omitted omit 0 also if expression is identity Examples El The set of squares of the integers between 1 and 10 I x 11000 xs10 ox x 1 49 4 100 9 16 25 81 36 64 El The set of pairs with first element lt second element and first and second elements between 1 amp 10 Ia110b110altboab 1 2 1 3 14 1 5 9 10 Predefined Sets El Certain sets are used so frequently that they are predefined El N the set of natural numbers I N 0 1 2 34 El N the set of positive natural numbers N 1 234 El Z the set of integers z Set Membership El Syntax x e A X e A 1 Meaning xan element ofA x not an element of A El Examples red colors True black e colors True 4 321 0 1 2 34 El R the set of real numbers El The empty set 6 Set Cardinality El Syntax A El Meaning Numberof elements inA El Examples coors 4 sizes 5 El What about Complement Sets El Formal definition for the complement of a set T x X e A I Or 0 A where Uis the universal set El Examples assuming I Z I 1 2 3 21 0 4 5 6 I New York Washington 3 4 New York Washington 1 2 1 2 a The difference ofany set s With the empty set Will be the set s Complement Sets Subset El Properties of complement sets ISyntax ACBABAltZB El Meaning One set a proper subset subset of another El Examples Recall sizes 13 10 7 36 3 7 36 c sizes True 3 25 c sizes False El A proper subset of a set is a subset with cardinality less than the set I A A Complementation law I A U A U Complement law I A n A Complement law Set Union Properties Of Set Union El Formal definition for the union of two sets AUBxxerrxeB El Examples I 1 2 3U 34 51 2 34 5 I New York Washington U 34 New York Washington 3 4 1 2U o 1 2 El A U Q A Identity law El A U U U Domination law El A U A A ldempotent law El A U B B U A Commutative law El A U B U C A U B U C Associative law Set Intersection El Formal definition for the intersection of two sets AnBxxeAandxe B El Examples 1 2 3m 34 53 I New York Washington n 3 4 a No elements in common 1 2 n o o a Any set intersection Witn tne empty set yields tne empty set Properties Of Set Intersection El A n U A Identity law El A n Q Q Domination law El A n A A ldempotent law El A n B B n A Commutative law El A n B n C A n B n C Associative law Disjoint Sets El Formal definition for disjoint sets two sets are disjoint if their intersection is the empty set El Further examples I 1 2 3 and 3 4 5 are not disjoint I New York Washington and 3 4 are disjoint I 1 2 and are disjoint a Their intersection is the empty set I and are disjoint a Their intersection is the empty set Set Difference El Formal definition for the difference of two sets A A B A n B 6 Important El Further examples I 1 2 33 4 51 2 I New York Washington 3 4 New York Washington 1 2 1 2 u The difference ofarry sets With the empty set Will be the set s Symmetric Difference El Formal definition for the symmetric difference of A Bxxerrxe BandxeAnB A B A U B A n B 6 Important El Further examples I 1 2 3 3451245 I New York Washington 9 3 4 New York Washington 3 4 1 2 o1 2 El The Symmetric difference of any sets With the empty set Wiii bet e sets Powe rsets El The powerset of a set is the set of all subsets of that set El The powerset of a set Xis denoted P X El Examp e I l 12 0i 1 2 12 El Used frequently in specification to define restrictions on types 1 Example Xis the set of all users privilegedusers e P Relations Cross Cartesian Product El Quick review El Two sets A and B El Cross aka Cartesian product is I Set oftwotuples I First element from A I Second element from B El Cartesian product ofA and B written A X B is a baEADEB El Note this is all members ofA and B El So it might be huge and it is of limited value Binary Relations El A relation is a set of ordered pairs usually with a name El Each element of the pair comes from a set El So a relation is a subset of the Cartesian product sets El More precisely for a relation R on sets A and B R g A X B RIaiA bil3Paib ai17 where pa b defines the relationship Domain And Range El Domain of a relation I Set of items firstin pair El Example dom memory Sun03 Sun06 MacZ El Range of a relation I Set of items secondin pair El Example ran memory 512 1024 128 new mumsicsmimWumi Unlverslty orViruiriie Relation Inverse El Inverse of a relation is a relation ll Inverse of a relation I Reverse order of pairs I Denoted by superscript 1 El Example memory1 512 H Sun03 1024 l r Sun06 128 t V MacZ ll Note the power available with the inverse new mm mm W mi Unlversltv uf Viruiriie Functions A Bit Of Terminology El Relation R on sets A and B R A X B El Not all elements ofA or B need be in R El So there are four sets that we need to be concerned about I A Source set I B Target set I The part ofA actually used in R Domain I The part of B actually used in R n El Note These definitions are not universally agree Frequent Special Use Of Relations ii Examples of special relations I Toothbrushes to people in a household I Peopleto ages I Soclal Securlty Numbers to credit reports I People to seats in a ball arllt i All these examples are relations with the following property Each Item In The Domain Maps To One Item In The Range n This property occurs frequently in speci cation ii Shorthand notation forthis is a func ion Functions El A function is a special kind of relation El Each item in the domain maps to one item in the range El Example Partial And Total Functions El A function is total if mapping is defined for all items in the source set ie domainsource set El A function is partial if mapping is defined for some items in the source se TOT L FUN TION AL FUN Injective Functions El A partial or total function is infective if its inverse is also a function El Also called OnetoOne functions NOer NJE TlVE UNCTION Surjective Functions El A partial or total function is surjecfive if domain maps to all of target set El Also called Onto functions CTlVE FUNCTION Bijective Functions El A partial or total function is bijecfive if it is injective and surjective El Also referred to as OnetoOne correspondence PARTIAL BlJECTlVE FUNCTION TOTAL BlJECTlVE FUNCTION A Notation For Functions El Function declaration different arrows for different types of functions F X


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.