CS 6340: Software Analysis and Testing - rightingcode.org

CS 6340: Software Analysis and Testing - rightingcode.org

Introduction to Software Analysis CS 6340 Why Take This Course? Learn methods to improve software quality reliability, security, performance, etc. Become a better software developer/tester Build specialized tools for software diagnosis and testing For the war stories The Ariane Rocket Disaster (1996) Post Mortem Caused due to numeric overflow error

Attempt to fit 64-bit format data in 16-bit space Cost $100Ms for loss of mission Multi-year setback to the Ariane program Read more at http://www.around.com/ariane.html Security Vulnerabilities Exploits of errors in programs Widespread problem Moonlight Maze (1998)

Code Red (2001) Titan Rain (2003) Stuxnet Worm Getting worse 2011 Mobile Threat Report (Lookout Mobile Security) 0.5-1 million Android users affected by malware in first half of 2011 3 out of 10 Android owners likely to face web-based threat each year Attackers using increasingly sophisticated ways to steal data and money

What is Program Analysis? Body of work to discover useful facts about programs Broadly classified into three kinds: Dynamic (execution-time) Static (compile-time) Hybrid (combines dynamic and static) Dynamic Program Analysis Infer facts of program by monitoring its runs Examples: Array bound checking Purify Datarace detection Eraser

Memory leak detection Valgrind Finding likely invariants Daikon Static Analysis Infer facts of the program by inspecting its source (or binary) code Examples: Suspicious error patterns Lint, FindBugs, Coverity Memory leak detection Facebook Infer

Checking API usage rules Microsoft SLAM Verifying invariants ESC/Java QUIZ: Program Invariants An invariant at the end of the program is (z == c) for some constant c. What is c? int p(int x) { return x * x; } void main() { int z; if (getc() == a) z = p(6) + 6;

else z = p(-7) 7; z=? } QUIZ: Program Invariants An invariant at the end of the program is (z == c) for some constant c. What is c? Disaster averted! int p(int x) { return x * x; } void main() { int z; if (getc() == a)

z = p(6) + 6; else z = p(-7) 7; if (z != 42) disaster(); } z = 42 Discovering Invariants By Dynamic Analysis int p(int x) { return x * x; } (z == 42) might be an invariant (z == 30) is definitely not an invariant

void main() { int z; if (getc() == a) z = p(6) + 6; else z = p(-7) 7; if (z != 42) disaster(); } z = 42 Discovering Invariants By Static Analysis int p(int x) { return x * x; } is definitely (z == 42) might be an

invariant (z == 30) is definitely not an invariant void main() { int z; if (getc() == a) z = p(6) + 6; else z = p(-7) 7; if (z != 42) disaster(); } z = 42 Terminology

Control-flow graph Abstract vs. concrete states Termination Completeness Soundness Example Static Analysis Problem Find variables that have a constant value at a given program point void main() { z = 3; while (true) { if (x == 1) y = 7; else

y = z + 4; assert (y == 7); } } Iterative Approximation [x=?, y=?, z=?] z =3 [x=?, y=?, z=3] while (x > 0) true false [x=?, y=?, z=3] [x=?, y=?, z=3]

if (x == 1) [x=1, y=?, z=3] y =7 true false [x=?, y=?, z=3] y=z+4 [x=1, y=7, z=3] [x=?, y=7, z=3] assert (y == 7)

QUIZ: Iterative Approximation [b=?] Fill in the value of variable b that the analysis infers at: 1) the loop header 2) entry of loop body 3) exit of loop body b=1 1) false 2) Enter ? if a definite value cannot be inferred.

while (true) true b=b+1 3) QUIZ: Iterative Approximation [b=?] Fill in the value of variable b that the analysis infers at: 1) the loop header 2) entry of loop body 3) exit of loop body b=1

1) [b=1] false 2) [b=?] Enter ? if a definite value cannot be inferred. [b=1] while (true) true [b=1] [b=?]

b=b+1 3) [b=?] [b=2] [b=?] QUIZ: Dynamic vs. Static Analysis Match each box with its corresponding feature. Dynamic Static Cost Effectiveness

A. Unsound (may miss errors) B. Proportional to C. Proportional to D. Incomplete programs execution programs size (may report time spurious errors) QUIZ: Dynamic vs. Static Analysis Match each box with its corresponding feature. Dynamic Cost Effectiveness B. Proportional to programs execution time

A. Unsound (may miss errors) Static C. Proportional to programs size D. Incomplete (may report spurious errors) Undecidability of Program Properties Can program analysis be sound and complete? Not if we want it to terminate! Questions like is a program point reachable on some input? are undecidable Designing a program analysis is an art Tradeoffs dictated by consumer

Who Needs Program Analysis? Three primary consumers of program analysis: Compilers Software Quality Tools Integrated Development Environments (IDEs) Compilers Bridge between high-level languages and architectures Use program analysis to generate efficient code int p(int x) { return x * x; } void main(int arg) { int z; if (arg != 0) z = p(6) + 6; else z = p(-7) - 7;

z = 42 print (z); } int p(int x) { return x * x; } void main() { print (42); } Runs faster More energy-efficient Smaller in size Software Quality Tools

Primary focus of this course Tools for testing, debugging, and verification Use program analysis for: Finding programming errors Proving program invariants Generating test cases Localizing causes of errors int p(int x) { return x * x; } void main() {

int z; if (getc() == a) z = p(6) + 6; else z = p(-7) 7; if (z != 42) disaster(); } z = 42 Integrated Development Environments Examples: Eclipse and Microsoft Visual Studio Use program analysis to help programmers: Understand programs Refactor programs Restructuring a program without changing its behavior

Useful in dealing with large, complex programs What Have We Learned? What is program analysis? Dynamic vs. static analysis: pros and cons Program invariants Iterative approximation method for static analysis Undecidability => program analysis cannot ensure termination + soundness + completeness Who needs program analysis?

Recently Viewed Presentations

  • Mortality Aggregation Examples - naic.org

    Mortality Aggregation Examples - naic.org

    Key Concepts forMortality Aggregation. Mortality segments subject to the same or similar underwriting processes may be aggregated to calculate credibility. Using separate mortality segment experience to set each corresponding assumption and then simply grouping the segments together to calculate credibility...
  • The 900-Pound Gorilla - US EPA

    The 900-Pound Gorilla - US EPA

    The 900-Pound Gorilla How STORET Affects the Development of Other Data Management Tools Gerald Burnette HydroGeoLogic, Inc. (865) 995-9953 www.hgl.com This Story Begins in an Earlier Time Design Goals of the New System The DASLER System DASLER and STORET: Worlds...
  • U.S. Military Medical Research and Material Command

    U.S. Military Medical Research and Material Command

    Overall, there is a trend toward delayed virologic rebound among participants receiving VRC01. This slide presents Kaplan-Meier curves evaluating time to rebound using two different threshold viral load levels. On the left, 20 copies/mL is used, representing the lower limit...
  • Multiple Myeloma and Understanding your Labs Matthew Ware

    Multiple Myeloma and Understanding your Labs Matthew Ware

    IMF, 2018. Percentage of plasma cells- Normal range is 1-2%. Morphology- mature, immature, atypical. Mature is better prognosis. Can derive kappa/lambda ratio from here or serum. Cytogenetics- Chromosomal abnormalities
  • A Doença Da Realidade Jorge Acário

    A Doença Da Realidade Jorge Acário

    a doenÇa da realidade jorge acÁrio comentÁrio aos islides sinais da doenÇa da realidade a destruiÇÃo da economia real ou estrutural se deve Á diminuiÇÃo da base monetÁria, achatamento salarial e elevaÇÃo do juro, para conter a inflaÇÃo pela diminuiÇÃo...
  • Greatest Common Factor

    Greatest Common Factor

    You previously learned about the distributive property, but in case you have forgotten about it… Given two terms, the first being a number and the second the sum of two numbers, the product of the two terms is the same...
  • RtI at Chisago Lakes High School

    RtI at Chisago Lakes High School

    Why RtI at the Secondary Level NCLB IDEA 2004 Prevention Traditional Model Ready? Pop Quiz Chisago Lakes High School 1200 students 10% special education 8% free/reduced lunch 1% English Language Learning Four, 85 minute blocks 98% graduation rate Credit increase:...
  • SPCC Rule Amendments: Streamlines Requirements for Regulated ...

    SPCC Rule Amendments: Streamlines Requirements for Regulated ...

    What is the SPCC Rule? Spill Prevention, Control, and Countermeasure rule. Part of the Oil Pollution Prevention regulation (40 CFR part 112) Includes requirements for Facility Response Plans (FRPs) for certain facilities which pose a greater threat to waterways and...