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



Yüklə 3,02 Mb.
tarix20.09.2018
ölçüsü3,02 Mb.
#69568


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




Yüklə 3,02 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2022
rəhbərliyinə müraciət

    Ana səhifə