CSE6049

News

• No class on 5/15 (the anniversary of the university’s founding) and 5/29 (national holiday)
• This is a regular offline course; see “Time & Location” below.

Basic Information

• Instructor: Woosuk Lee
  • Office Location: Rm#403, Eng. Bldg 3
  • Telephone: 031-400-1031
  • Email: woosuk at hanyang.ac.kr
  • Office Hours: Monday 10:00 - 12:00
• Time & Location
  • Monday 15:00 - 17:30 @ Y301-0406, 1st Eng. Bldg

References

• The course textbook:
  • Static Program Analysis by Moeller and Schwartzbach
  • Introduction to Static Analysis: An Abstract Interpretation Perspective by Xavier Rival and Kwangkeun Yi
• Materials from related courses: CS6340: Software Analysis and Testing at Georgia Tech

Student presentation

• link is available at the HY-LMS

Contents

• Introduction to Program Analysis
• Introduction to Software Testing
• Random Testing
• Automated Test Generation
• Dataflow Analysis
• Pointer Analysis
• Datalog Analysis
• Type Systems
• Delta Debugging
• Dynamic Symbolic Execution

Grading

• Student presentation: 80%
• Attendance: 20%

Reating Material

Reading material related to the lesson

• Introduction to Software Analysis
  • What is static program analysis? talk by Matthew Might.
    • Explains why program analysis is undecidable and develops a static analysis to play with in Racket.
  • Lessons from Building Static Analysis Tools at Google
    • Describes experiences developing and deploying program analysis tools at Google.
  • What Developers Want and Need from Program Analysis: An Empirical Study
    • One of the best empirical studies about program analysis.
  • A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs - Describes experiences applying a commercial static analysis tool by Coverity to large C/C++ programs.
  • From Start-ups to Scale-ups: Opportunities and Open Problems for Static and Dynamic Program Analysis
    • Describes experiences developing and deploying program analysis tools at Facebook.
• Introduction to Software Testing
  • Pex and Moles
    • Unit test generation tools in Visual Studio for .NET programs.
  • Hints on Test Data Selection: Help for the Practicing Programmer
    • Original paper that introduced the idea of mutation testing.
  • A Theory of Predicate-Complete Test Coverage and Generation slides
    • Introduces a new code coverage metric based on predicates.
• Random Testing
  • A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs, ASPLOS 2010
    • Describes fuzz testing in Microsoft’s Cuzz tool to find concurrency bugs.
  • QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs, ICFP 2000 video
    • Describes fuzz testing in the QuickCheck tool to test properties of Haskell programs.
  • Evaluating Fuzz Testing, CCS 2018 blog post
    • Describes flaws in past evaluations of fuzz testing and gives guidelines going forward.
• Automated Test Generation
  • Korat: Automated Testing Based on Java Predicates, ISSTA 2002
    • Paper that introduced Korat.
  • Feedback-Directed Random Test Generation, ICSE 2007 Randoop webpage
    • Paper that introduced Randoop.
  • NEZHA: Efficient Domain-Independent Differential Testing, IEEE S & P 2017 video
    • A general differential testing approach to find bugs in binaries.
  • Finding and Understanding Bugs in C Compilers, PLDI 2011 CSmith
    • Adapts differential testing to find bugs in various C compilers.
  • DeepXplore: Automated Whitebox Testing of Deep Learning Systems, SOSP 2017 video
    • Adapts differential testing to find bugs in deep neural networks.
• Pointer Analysis
  • Pointer Analysis, Foundations and Trends in Programming Languages, 2015
    • Recent survey of pointer analysis.
• Type Systems
  • Type Systems, CRC Handbook, 2004
• Delta Debugging
  • Effective Program Debloating via Reinforcement Learning, CCS 2018, webpage
    • Describes how to accelerate program reduction using a machine learning-based approach
  • Test-Case Reduction for C Compiler Bugs, PLDI 2012, webpage
    • Program reducer specialized for isolating C compiler bugs