CS 217 Software Verification and Validation Week 2, Summer 2014 Instructor: Dong Si http://www.cs.odu.edu/~dsi REVIEW OF LAST CLASS What is (software) testing? Softeware Testing – definition The process consisting of all life cycle activities, concerned with planning, preparation and evaluation of software products and related work products to determine: – that they satisfy specified requirements, – to demonstrate that they are fit for purpose and – to detect defects 4 Validation & Verification Validation : Have we built the right software? i.e., do the requirements satisfy the customer? (This is dynamic process for checking and testing the real product. Software validation always involves with executing the code) Verification : Have we built the software right? i.e., does it implement the requirements? This is static method for verifying design, code. Software verification is human based checking of documents and files Introduction to Software Testing, Edition 2 (Ch 1) © Ammann & Offutt 5 COMPUTER BUG? What is a computer bug? In 1947 Harvard University was operating a room-sized computer called the Mark II. – made of vacuum tubes A moth flew into the computer and was killed by the high voltage. Operators traced an error in the Mark II and taped the bug to log book. Hence, the first computer bug! I am not making this up :-) 7 The Term Bug Bug is used informally Sometimes speakers mean fault, sometimes error, sometimes failure, Incident, problem, Inconsistency … often the speaker doesn’t know what it means ! This class will try to use words that have precise, defined, and unambiguous meanings BUG Introduction to Software Testing, Edition 2 (Ch 1) © Ammann & Offutt 8 Software Faults, Errors & Failures Software Fault : A static defect in the software Software Failure : External, incorrect behavior with respect to the requirements or other description of the expected behavior Software Error : An incorrect internal state that is the manifestation/expression of some fault Faults in software are equivalent to design mistakes in hardware. Software does not degrade. Introduction to Software Testing, Edition 2 (Ch 1) © Ammann & Offutt 9 Fault and Failure Example The doctor tries to diagnose the root cause, the disease – Fault A patient gives a doctor a list of symptoms – Failures The doctor may look for anomalous internal conditions (high blood pressure, irregular heartbeat, bacteria in the blood stream) – Errors Most medical problems result from external attacks (bacteria, viruses) or physical degradation as we age. They were there at the beginning and do not “appear” when a part wears out. Introduction to Software Testing, Edition 2 (Ch 1) © Ammann & Offutt 10 Sources of Problems Requirements Definition: Erroneous, incomplete, inconsistent requirements. Design: Fundamental design flaws in the software. Implementation: Mistakes in chip fabrication, wiring, programming faults, malicious code. Support Systems: Poor programming languages, faulty compilers and debuggers, misleading development tools. Sources of Problems (Cont’d) Inadequate Testing of Software: Incomplete testing, poor verification, mistakes in debugging. Evolution: Sloppy redevelopment or maintenance, introduction of new flaws in attempts to fix old flaws, incremental escalation to inordinate complexity. Summary: Why Do We Test Software ? A tester’s goal is to eliminate faults as early as possible • Improve quality • Reduce cost • Preserve customer satisfaction Introduction to Software Testing, Edition 2 (Ch 1) © Ammann & Offutt 13 Testing main principles Testing Principles (1) Testing can demonstrate only the presence of defects and not their absence – Testing can show that defects are present, but cannot prove that there are no defects. Testing reduces the probability of undiscovered defects remaining in the software but, even if no defects are found, it is not a proof of correctness. Exhaustive testing is impossible – Exhaustive testing (all combinations of inputs and preconditions) is not feasible except for trivial cases. Instead of exhaustive testing, risk analysis and priorities should be used to focus testing efforts. Testing Principles (2) Early testing is important – Testing activities should start as early as possible in the software or system development life cycle and should be focused on defined objectives. Defects are clustering – A small number of modules contain most of the defects discovered during pre-release testing, or are responsible for the most operational failures. Testing Principles (3) Testing is context dependent – Testing is done differently in different contexts. For example, military software is tested differently from an business site. Software Testing Process V&V Targets Code & Implementation Unit test Software Design Integration test System test System engineering 18 Software Development Lifecycles Code and Fix Waterfall Cycle LOGIC IN COMPUTER SCIENCE Week 2, topic 1 Motivation Logic became popular in the early 20th century among philosophers and mathematicians What constitutes a correct proof in Mathematics? Some ‘correct’ proofs were later disproved by other mathematicians Concept of logic helps us to figure out what constitutes a correct argument and what constitutes a wrong argument 21 Motivation Faults (bugs) have been detected in proofs (programs) Bugs are hard to detect! LOGIC enabled mathematicians to point out WHY a proof is wrong, or WHERE in the proof, the reasoning has been faulty. By symbolizing arguments rather than writing them out in some natural language (which is fraught with ambiguity), checking the correctness of a proof becomes a much more viable task. 22 Motivation Since the latter half of the 20th century, logic has been used in computer science for various purposes ranging from software validation and verification to theoremproving. 23 Objective of the class Understand why logic is important to Software Testing To prepare the student for using logic as a formal tool in computer science 24 Introduction to Logic Logic is called the CALCULUS of Computer Science! LOGIC --- Computer Science CALCULUS --- Physical sciences & Engineering CS areas where we use LOGIC Architecture (logic gates) Software Engineering (Validation & Verification) Programming Languages (Semantics & Logic Programming) AI (Automatic theorem proving) Algorithms (Complexity) Databases (SQL) 25 History of Logic Symbolic Logic (500 BC – 19th century) Algebraic Logic (Mid to late 19th century) Mathematical Logic (19th century to 20th century) Logic in Computer Science 26 Fundamental of Logic Declarative statements Examples of declarative statements – “A is older than B” – “There is ice in the glass” – In CIS, describing the data (variables, functions, etc.) 27 Propositions - a statement that is either true or false. For every proposition p, either p is T or p is F For every proposition p, it is not the case that p is both T and F 28 Discussion… Which statement is a proposition? A . Which bird did the cat kill? B. It is a beautiful day today! C. William's wife's name is Irene. D. Give me an A! 29 Discussion… Which statement is a proposition? A. 2 + 3 = 5 B. 4 / 9 C. 1 + 1 = 3 D. Both A and C 30 Fundamental of Logic We are interested in precise declarative statements about computer systems and programs We not only want to specify such statements, but also want to check whether a given program or system fulfills specifications that user needs 31 Fundamental of Logic 5 basic connectives: – And – Or – Not – If…then…(else) – If and only if 32 Logic in CIS Simple Logic underlies the reasoning in mathematical statements / programming languages Objective is to develop codes to model the situations that we encounter 1. Reasoning about situations formally 2. Then constructing arguments/programs about them that can be executed on a machine We also want to check whether a computer program or a system satisfies the specifications - TESTING 33 Propositional Logic: Basics Propositional logic describes ways to combine some true statements to produce other true statements. If it is proposed that `Jack is taller than John' and `John can run faster than Jack' are both T =`Jack is taller than John and John can run faster than Jack'. Propositional logic allows us to formalize such statements. In concise form: A ^ B 34 Propositional Logic: Basics For CS/CIS, we will restrict our attention to mathematical objects, programs, and data structures in particular. Statements in a logical language are constructed according to a predefined set of formation rules called ‘syntax rules’. Same for computer languages C/C++. Java, HTML,….. All have their own ‘syntax rules’ But the LOGIC behind them are the same ! 35 Propositional Logic: Basics Why English or any other natural language can’t be used? – Meaning of an English sentence can be ambiguous, subject to different interpretations depending on the context and implicit assumptions. – Another important factor is conciseness. Natural languages tend to be wordy, and even fairly simple mathematical statements become exceedingly long (and unclear) when expressed in them. The logical languages should contain special symbols used for abbreviating syntactical constructs. Declarative sentences in English string of symbols in CIS 36 Propositional Logic in CIS Compressed but complete encoding of declarative statements allows us to concentrate on our argumentation Software is sequence of such declarative statements Automatic manipulation of such statements, something that machines love to do “Siri” in Apple: “If…Then…” logics in cloud 37 Propositional Logic Composition of atomic sentences p: I won the lottery yesterday q: I will purchase a lottery ticket today r: I played a football game yesterday ~ p: Negation. “I did not win the lottery last week” p v r: Disjunction. The statement is true if at least one of them is true. “I won the lottery or played a football game yesterday.” 38 Propositional Logic p ^ r: Conjunction. “Yesterday I won the lottery and played a football game.” p q: Implication. “If I won the lottery last week, then I will purchase a lottery ticket today.” p is called the assumption and q is called conclusion. 39 Propositional Logic p q: Implication, Some interpretations – p implies q – If p then q – p is a sufficient condition for q – q is a necessary condition for p – q if p – q follows from p – q provided p – q is a consequence of p – q whenever p 40 Natural Deduction Proof Set of rules which allow us to draw a conclusion by given a set of preconditions Constructing a proof is much like a programming! It is not obvious which rules to apply and in what order to obtain the desired conclusion, be careful to choose proof rules! 41 Rules of Natural Deduction Fundamental rule 1 (rule of detachment) p p q ...q The rule is a valid inference because [p ^ (p q)] q is a tautology! 42 Rules of Natural Deduction Example: if it is 11:00 o’ clock in Norfolk if it is 11:00 o’ clock in Norfolk, then it is 11:00 o’ clock in DC then by rule of detachment, we must conclude: it is 11:00 o’ clock in DC 43 Rules of Natural Deduction Fundamental rule 2 (transitive rule) p q ...p q r r This is a valid rule of inference because the implication (p q) ^ (q r) (p r) is a tautology! 44 Rules of Natural Deduction FR 3 (De Morgan’s law) ~(p v q) = (~p) ^ (~q) ~(p ^ q) = (~p) v (~q) FR 4 (Law of contrapositive) p q = (~q ~p) FR 5 (Double Negation) ~(~p) = p 45 Examples of Arguments If a baby is hungry, then the baby cries. If the baby is not mad, then he does not cry. If a baby is mad, then he has a red face. Therefore, if a baby is hungry, then he has a red face. Model this problem!! h: a baby is hungry c: a baby cries m: a baby is mad r: a baby has a red face h ~m m c ~c r ...h h c m r c m r ...h r 46 Logic is the Skeleton What remains when arguments are symbolized is the bare logical skeleton It is this form that enables us to analyze the program / code / software. Software V&V = Logical proof & Logic error detection 47 CODE COVERAGE Week 2, topic 2 Definition Code coverage is a measure used to describe the degree to which the source code of a program is tested by a particular test suite. A program with high code coverage has been more thoroughly tested and has a lower chance of containing software bugs than a program with low code coverage. 49 Coverage criterias Function coverage - Has each function (or subroutine) in the program been called? √ Statement coverage - Has each statement in the program been executed? √ √ 50 Coverage criterias Branch coverage - Has each branch of each control structure (such as in if and case statements) been executed? For example, given an if statement, have both the T and F branches been executed? Another way of saying this is, has every edge in the program been executed? 51 Coverage criterias Condition coverage - Has each Boolean sub-expression evaluated both to true (T) and false (F) ? In “A and B”, if sub-expression A is evaluated both to T and F if sub-expression B is evaluated both to T and F 52 Example consider the following C++ function: If during this execution function 'foo' was called at least once, then function coverage for this function is satisfied. 53 Example consider the following C++ function: Statement coverage for this function will be satisfied if it was called e.g. as foo(1,1), as in this case, every line in the function is executed including ’z = x;’. 54 Example consider the following C++ function: Tests calling foo(1,1) and foo(0,1) will satisfy branch coverage because, in the first case, the 2 if conditions are met and z = x; is executed, while in the second case, the first condition (x>0) is not satisfied, which prevents executing z = x;. 55 Example consider the following C++ function: (x>0) && (y>0) T,F T,F Condition coverage can be satisfied with tests that call foo(1,1), foo(1,0) and foo(0,0). These are necessary because in the first two cases, (x>0) evaluates to true, while in the third, it evaluates false. At the same time, the first case makes (y>0) true, while the second and third make it false. 56 Condition / branch coverage? Condition coverage does not necessarily imply branch coverage. For example: Condition coverage can be satisfied by two tests: However, this set of tests does not satisfy branch coverage since neither case will meet the if condition. 57

Descargar
# SWE 637: Here! Test this!