Static and Dynamic Program Analysis: Synergies and Applications Mayur Naik Intel Labs, Berkeley

Static and Dynamic Program Analysis: Synergies and Applications

• Mayur Naik

• Intel Labs, Berkeley

• CS 243, Stanford University March 9, 2011

Today’s Computing Platforms

A Challenge in Mobile Computing

• Rich apps are hindered

• by resource-constrained

• mobile devices (battery,

• CPU, memory, ...)

A Challenge in Cloud Computing

A Challenge in Parallel Computing

• Most Java programs are

• so rife with concurrency

• bugs that they work only

• by accident.

• – Brian Goetz

• Java Concurrency in Practice

Terminology

• Program Analysis

• Discovering facts about programs

• Dynamic Analysis

• Program analysis using program executions

• Static Analysis

• Program analysis without running programs

This Talk

• Techniques

Our Result: Mobile Computing

• Techniques

Our Result: Cloud Computing

• Techniques

Our Result: Parallel Computing

• Techniques

Talk Outline

• Overview

• Seamless Program Partitioning

• Automatic Performance Prediction

• Scalable Program Verification

• Future Directions

Program Partitioning: CloneCloud [EuroSys’11]

CloneCloud on Face Detection App

Talk Outline

• Overview

• Seamless Program Partitioning

• Automatic Performance Prediction

• Scalable Program Verification

• Future Directions

From Offline to Online Program Partitioning

• CloneCloud uses same partitioning regardless of input

• But different partitionings optimal for different inputs

• 1 image: phone-only optimal
• 100 images: (phone + cloud) optimal

• Challenge: automatically predict running time of a function on an input

• can be used to decide online whether or not to partition
• but also has many other applications

The Problem: Predicting Program Performance

Our Solution: Mantis [NIPS’10]

Offline Stage of Mantis

Static Slicing Analysis

• static-slice(v) = { all actions that may affect value of v }

• Computed using data and control dependencies

From Dependencies to Slices

Offline Stage of Mantis

Offline Stage of Mantis

Mantis on Apache Lucene

• Popular open-source indexing and search engine

• Datasets used: Shakespeare and King James Bible

• 1000 inputs, 100 for training

• Feature counts:

• instrumented = 6,900
• considered = 410 (6%)
• chosen = 2

• Similar results for other apps

Talk Outline

• Overview

• Seamless Program Partitioning

• Automatic Performance Prediction

• Scalable Program Verification

• Future Directions

Static Analysis of Concurrent Programs

The Thread-Escape Problem

• thread-local(p,v): Is v reachable from single thread at p on all inputs?

The Thread-Escape Problem

• thread-local(p,v): Is v reachable from single thread at p on all inputs?

• Needs to reason about all inputs  Use static analysis

The Need for Program Abstractions

• All static analyses need abstraction

• represent sets of concrete entities as abstract entities

• Why?

• Cannot reason directly about infinite concrete entities
• For scalability

• Our static analysis:

• How are pointer locations abstracted?
• How is control flow abstracted?

Example: Trivial Pointer Abstraction

Example: Allocation Sites Pointer Abstraction

Example: k-CFA Pointer Abstraction

Complexity of Static Analysis

Drawback of Existing Static Analyses

• Different queries require different parts of the program to be abstracted precisely

• But existing analyses use the same abstraction to prove all queries simultaneously

• ⇒ existing analyses sacrifice precision and/or scalability

Insight 1: Client-Driven Static Analysis

• Query-driven: allows using separate abstractions for proving different queries

• Parametrized: parameter dictates how much precision to use for each program part for a given query

Example: Client-Driven Static Analysis

Insight 2: Leveraging Dynamic Analysis

Example: Leveraging Dynamic Analysis

Benchmark Characteristics

Precision Comparison

Precision Comparison

Running Time Breakdown

Sparsity of Our Abstraction

Feedback from Real-World Deployments

• 16 bugs in jTDS

• Before: As far as we know, there are no concurrency issues in jTDS
• After: Probably the whole synchronization approach in jTDS should be revised from scratch

• 17 bugs in Apache Commons Pool

• Thanks to an audit by Mayur Naik many potential synchronization
• issues have been fixed -- Release notes for Commons Pool 1.3

• 319 bugs in Apache Derby

• This looks like very valuable information … could this tool be run
• on a regular basis? It is likely that new races could get introduced
• as new code is submitted

Talk Outline

• Overview

• Seamless Program Partitioning

• Automatic Performance Prediction

• Scalable Program Verification

• Future Directions

Program Analyses as Building Blocks

Dependency Graphs of Analyses in Chord

Applications Built Using Chord

• Systems:

• CloneCloud: Program partitioning [EuroSys’11]
• Mantis: Performance prediction [NIPS’10]

• Tools:

• CheckMate: Dynamic deadlock detection [FSE’10]
• Static datarace detection [PLDI’06, POPL’07]
• Static deadlock detection [ICSE’09]

• Frameworks:

• Evaluating heap abstractions [OOPSLA’10]
• Learning minimal abstractions [POPL’11]
• Abstraction refinement [PLDI’11]

Example Application: Configuration Debugging

Conclusion

• Modern computing platforms pose exciting and unprecedented software engineering problems

• Static analysis, dynamic analysis, and machine learning can be combined to solve these problems effectively

• Program analyses can serve as reusable components in solving diverse software engineering problems