1CS 350: Introduction toSoftware EngineeringSlide Set 3C. M. OverstreetOld Dominion UniversitySpring 2005Why GCS (Guidance and Control Software)?z NASA & FAA interest in “ultra-reliable”softwarez NASA/Langley lead in previous project (still core of knowledge about project)z Complex but not too complexz I like it because:z Real-time systemz Application knowledge required (just like real life)z Really messy in places (just like real life)z ~100 pg. req. doc.z Bad features (just like real life)z I’d do a bunch of things differently but we’re stuck with other people’s bad decisionsComments on Real Timez In a real-time system:z Computational tasks must complete by a deadlinez Often cyclical: computations repeat at a specified frequencyz Operating system considerationsz Many OS’s allow you to schedule the start time for a task (see cron in UNIX). z Much harder to guarantee that a task will complete by a deadline, particularly for interrupt driven systems2Software Experimentationz Std Problem is SE: many opinions, few factsz Purpose of GCS: get some real dataz Study a software systems that:z Doesn’t cost too much to buildz Small but not too smallz Is in the “right” application domainz Flight control, real timez Can be used for data collectionz Want failure rate data (e.g. MTTF)z Want to understand kinds of errors people makeN-version Softwarez Purpose: increase software reliabilityz One idea:z Develop one requirements documentz Give copies to several different development groups (say 5)z Each group develops complete systemz Independently! No info exchange!!z Run all five systems:z Give each identical inputz Wait for each to produce required outputz Compare 5 outputs & take majority as the correct outputz Question: does this work?Failure Probabilities - 1z In software reliability world, failures are treated as "random" events (even though they aren't)z Each programs has "input space":z The set of data the program will receive when running, including the fact that it will see some inputs frequently, others rarely.3Failure Probabilities - 2z Then probability of program failure is based on idea:z Randomly pick a data value from the program's input space (where selecting particular values reflects how frequently they will be seen when the program really runs).z Observe whether or not the program failsz Do this for all values in input space (properly weighted).z Pr(failure with a randomly selected input) = (number failures) / (number tests)Failure Probability Commentsz Simple concept. But involves several potentially hard problems:z What is the distribution of inputs the program will really encounter in use?z Input space often too large to run all program with all possible inputsz How do you tell when the program fails (assuming it doesn't crash)?z Typical industry interest is how often software will fail when used by their customers. This is a similar idea.z Depends on both frequency of use and typical input dataN-version Software - 2z Statistical concept: event independencez Knowing one event occurred doesn’t change probably of another event.z Independence ⇔ Pr(A^B)=Pr(A)×Pr(B)z Often, this is not truez Key Question:z Do separately developed versions really fail independently?z Or if one fails, does that make it more likely that another will fail also?4Oracle Problem - 1z When testing software, how do you detect all erroneous outputs?z Unsolved SE problem for many applicationsOracle problem - 2z Federal Aviation Administration (FAA) specifies that the failure rate for commercial aircraft of less than 10-9.z How many test cases should you run to determine this?z Generally considered a statistical problem: if the software is given a "random" input, what is the likelihood of the program producing incorrect output (assuming it doesn't crash)?z How do you check the answers?GCS GoalGenerate data for software reliability studyz What types of mistakes to do programmers make?z How often do different programmers make the same mistake?z If “approved” software development procedures are used (here, RTCA/DO-178B--required by FAA), how reliable will the software be?5Estimates, program 2z New estimates:z How long in each phasez Estimation procedure1. Understand assignment2. Based on your experience (from prog 1?), estimate LOC for prog 2; modify if appropriate3. Use your productivity data from prog 1 (min/loc); modify if appropriate4. Time est. = size (from step2) X (min/loc from step 3)5. Adjust time estimate, if appropriate6. Use phase percentages from prog 1 to estimate phase percentage (then minutes) for prog 2. Again, adjust, if appropriateForm examplez Minutes/LOC, LOC/Hourz From prog 1, modified as appropriatez Time in phase (min) (based on prog 1, perhaps modified)z Planning-- if you spent 15% on prog planning, start with 0.15*time est prog 2z Code Design—same againz Test Designz Codez Compilez Postmortemz Total Timez Max Timez Min timeGCS Context - 2Use n-versions to address the oracle problem:z Assume, say, 5 complete versions of GCS are available.z Give each a set of inputs.z After all finish, compare outputs.z If identical repeat (run another test)z If at least one differsz We’ve found an errorz Don’t know which program.z May be a problem with ambiguous requirements.Does this solve the oracle problem?6GCS Context - 3Execution context:V2V1V4 V5Sensor DataVoter/LoggerPhysics, Environ.SimulatorEngine CommandsSensorDataSeparateGCSversionsV3Bigger Context, Designz Viking project was largez Done by teams, different teams for different phasesz Main phases:z Launch rocket (with Viking lander as payload)z Fly payload to Mars, place into orbitz Start decent of payload to target location; parachute deployedz Control descent to surface of Marsz Conduct scientific mission & transmit data to Earthz Analyze data collectedOur part!Reading the spec - 1z Read pp. 3-18, 89-123 for Mod.z Read as reference doc. That is, most important is to be aware of what is there and where there rather than to memorize lots of details.z Point: when you get to code design, you will (we hope) remember that something about this was discussed in several places, then reread those parts.7Reading the spec - 2z Examples:z Section on vector notation and frames of reference: if you design, code, or test a module that deals with frames of reference, you will need to understand this discussionz Rotating history variables: likewise. z Point: wherever certain variables are modified, it’s up to