Chrysalis Analysis: Incorporating Synchronization Arcs in ...

Chrysalis Analysis: Incorporating Synchronization Arcs in ...

Chrysalis Analysis: Incorporating Synchronization Arcs in Dataflow-Analysis-Based Parallel Monitoring Michelle Goodstein*, Shimin Chen, Phillip B. Gibbons, Michael A. Kozuch and Todd C. Mowry* *Carnegie Mellon University HP Labs China Intel Labs Pittsburgh Motivation Software bugs are common, even in sequential code Chip multi-processors increasing importance of parallel software Parallel software introduces new species of bugs Bugs can lead to crashes, security exploits and other harms to system We would like to detect bugs before they cause harm One solution: Monitor programs at runtime using lifeguards Chrysalis Analysis 2 Michelle Goodstein Commit Order Dynamic Program Monitoring Update p2s metadata

. . taint p2 . . *p2 . . Update metadata Lifeguard Metadata: Tainted? p1 0 p2 0 1 p3 . p4 . Application Application is dynamically monitored by a lifeguard as it runs Monitors each dynamic instruction Lifeguard maintains finite-state machine model of correct execution Checks metadata to see if program does something wrong Ex: Is performing *p2 safe (e.g., is p2 untainted)? Chrysalis Analysis 3 Michelle Goodstein Commit Order

Dynamic Program Monitoring ERROR: metadata Is *p2 safefor ? p2 tainted . . taint p2 . . *p2 . . Check metadata Lifeguard Metadata: Tainted? p1 0 p2 1 p3 . p4 . Application Application is dynamically monitored by a lifeguard as it runs Monitors each dynamic instruction Lifeguard maintains finite-state machine model of correct execution Checks metadata to see if program does something wrong Ex: Is performing *p2 safe (e.g., is p2 untainted)? Chrysalis Analysis

4 Michelle Goodstein Dynamically Monitoring Parallel Programs . . . untaint p *p . . Commit Order . . . . . . . . Thread 0 . . . taint p . . . .

Thread 1 Lifeguard 0 Lifeguard 1 Lifeguard 2 Thread 2 Updating metadata straightforward for sequential programs Intuition: Monitor parallel applications with parallel lifeguards Parallel apps: inter-thread data dependences complicate lifeguards Ideal: Lifeguards process trace in app instructions global commit order Butterfly Analysis [ASPLOS 2010] : No inter-thread data dependences Cannot measure using todays hardware Relaxed memory consistency models: no total order Chrysalis Analysis 5 Michelle Goodstein Butterfly Analysis: Dynamic Parallel Monitoring . . . untaint p *p . . Commit Order . . . . . . .

. Thread 0 . . . taint p . . . . Thread 1 Lifeguard 0 Lifeguard 1 Lifeguard 2 Thread 2 Butterfly Analysis + Proceed without capturing inter-thread data dependences + Supports relaxed memory consistency models - Ignores explicit software synchronization Chrysalis Analysis 6 Michelle Goodstein Commit Order Chrysalis Analysis: Generic Dynamic Dataflow Analysis Platform

. . lock L untaint p . . . . . . . . *p unlock L . Thread 0 . . . lock L taint p: unlock L . . Lifeguard 0 Lifeguard 1 Lifeguard 2 Thread 2 Thread 1 Generic parallel dynamic dataflow analysis framework Lifeguards can be built on top of generic dataflow examples This talk: TaintCheck

Not only race detection: Analyses robust even when races present Behaves conservatively but correctly When two conflicting metadata values possible, assume worst case Incorporates high-level synchronization arcs Our experiments: 97% reduction in false positives (relative to Butterfly) Chrysalis Analysis 7 Michelle Goodstein Roadmap for Remainder of Talk Review of Butterfly Analysis Highlight key changes to execution model to incorporate sync arcs Vector clocks Asymmetry Illustrate research challenges and solutions Calculating local/global states Computing side-in/side-out primitives Experimental evaluation Template color coding: Butterfly , Chrysalis Chrysalis Analysis 8 Michelle Goodstein Butterfly Analysis: Fundamentals Occurs.strictly

before . *p . Commit Order . . . . Concurrent . region . . . . Occurs.strictly before . *p . untaint p *p . . . . taint p . Concurrent .

Window region Key Insight: Only consider a window W of uncertainty W must account for all buffering in pipeline and memory system Large relative to ROB, memory access latency Small relative to total execution Our experiments: 1000s-10,000s of instructions/thread Chrysalis Analysis 9 Michelle Goodstein Butterfly Analysis: Reasoning About Concurrent Regions Commit Order Concurrent Region of Execution Traces . . . A: untaint p . . . . . . . . B: *p . .

Thread 0 . . . . C: taint p . . . . Thread 2 Thread 1 Lifeguard 1 Three Possible Orderings C A C B p tainted *p unsafe Lifeguard must behave conservatively Chrysalis Analysis 10 A A B B C

p untainted *p safe Michelle Goodstein Butterfly Analysis: Ignoring Sync Arcs Causes False Positives Commit Order Concurrent Region of Execution Traces . . D: lock L A: untaint p . . . . . . . . B: *p E: unlock L . Thread 0 . . . F: lock L C: taint p G: unlock L . . . Thread 2

Thread 1 Lifeguard 1 Three Possible Orderings C A C B p tainted *p unsafe Butterfly Analysis considers an impossible interleaving to be valid Chrysalis Analysis 11 A A B B C p untainted *p safe Michelle Goodstein Chrysalis Analysis: Incorporating Sync Arcs Improves Precision Commit Order Concurrent Region of Execution Traces

. . D: lock L A: untaint p . . . . . . . . B: *p E: unlock L . Thread 0 . . . F: lock L C: taint p G: unlock L . . . Thread 2 Thread 1 Lifeguard 1 Two Possible Orderings D E C

F A G C B G E p untainted p untainted *p safe*p safe Under all possible orderings, *p safe! Chrysalis Analysis D A B F 12 Michelle Goodstein Chrysalis Analysis: Incorporating Sync Arcs Into Butterfly Analysis . . D: lock L A: untaint p

Commit Order . . . . . . . . B: *p E: unlock L . Thread 0 . . . F: lock L C: taint p G: unlock L . . . Lifeguard 0 Lifeguard 1 Lifeguard 2 Thread 2 Thread 1

Chrysalis Analysis: Generalize Butterfly Analysis to include sync arcs + Improved precision (compared to Butterfly Analysis) + Relaxed consistency models OK, no explicit hardware required Research challenges solved More complex thread execution model More complex dataflow analysis framework Chrysalis Analysis 13 Michelle Goodstein Commit Order Butterfly Analysis: A Brief Review . . . . . . . . . . . . . . . . . . . . . .

. untaint p *p . . . . . . . . . . . . taint p . . . . . . . . . . Consider an online execution trace Chrysalis Analysis 14 Michelle Goodstein W taint p untaint p *p

Epoch 4 Epoch 3 Commit Order Epoch 2 Epoch 1 Epoch 0 Butterfly Analysis: Epochs Partition Thread Execution Execution divided into epochs separated by at least W events/thread Chrysalis Analysis 15 Michelle Goodstein Epochs: Reasoning About Concurrency taint p RelativeSliding To Centerwindow Epoch limited to 3 epochs Commit Order untaint p *p W W

From the perspective of the center epoch Most epochs are non-adjacent Instructions in these epochs execute strictly before or strictly after Two epochs are adjacent to center epoch 3 epoch window of potentially concurrent instructions Chrysalis Analysis 16 Michelle Goodstein Butterfly Analysis: Concurrency Within Three Epoch Window l-1 Thread t Epochs l+1 l Head Commit Order Body Tail Wings Chrysalis Analysis Wings 17 Michelle Goodstein

Butterfly Analysis: Parallel Forward Dataflow Analysis l-1 Thread t Body l+1 Commit Order Epochs l Head Tail Wings Wings Extend standard dataflow primitives (In, Out, Gen, Kill) Introduced two new primitives: Side-Out and Side-In Side-Out: Effects of concurrency a block exposes to other threads Side-In: Effects of concurrency other threads expose to a block Chrysalis Analysis 18 Michelle Goodstein Butterfly Analysis: Parallel Dataflow Analysis l-1 Thread t

Body l+1 Commit Order Epochs l Head Tail Wings Wings Extend standard dataflow primitives (In, Out, Gen, Kill) Introduced two new primitives: Side-Out and Side-In Side-Out: Effects of concurrency a block exposes to other threads Side-In: Effects of concurrency other threads expose to a block Chrysalis Analysis 19 Michelle Goodstein Butterfly Analysis: Parallel Dataflow Analysis l-1 Thread t Body l+1

Commit Order Epochs l Head Tail Wings Wings Two-pass lifeguard analysis over 3-epoch sliding window Lifeguard threads execute in parallel Maintains state Global state: Summarizes earlier epochs outside the window Local state: Global state augmented with info from the head Chrysalis Analysis 20 Michelle Goodstein Generalizing Butterfly Analysis: Incorporating Sync Arcs Thread 0 taint p . .

. . . Thread 1 Epoch 1 . . untaint p *p Thread 1 . . . lock L taint p unlock L Epoch 2 Epoch 1 . . . Epoch 2 Thread 0 lock L untaint p *p unlock L

. . . Butterfly Analysis: p conservatively tainted at *p in Thread 0, epoch 2 If mutual exclusivity is enforced, *p must be untainted! Useful ordering information implied by sync also lost Chrysalis Analysis 21 Michelle Goodstein Chrysalis Analysis: Incorporating Sync Arcs To Improve Precision Epoch 1 Thread 1 . . . . . lock L taint p unlock L . . Epoch 2 Commit Order Thread 0

lock L untaint p *p unlock L . . . . . . Goal: Incorporate synchronization-based happens-before arcs Butterfly Analysis framework not general enough to handle arbitrary arcs Chrysalis Analysis 22 Michelle Goodstein Chrysalis Analysis: Incorporating Synchronization Arcs lock L untaint p *p unlock L <0,1> lock L taint p unlock L

<0,2> . . . Thread 1 <0,3> <1, 0> <2, 1> <3, 1> Commit Order Epoch 2 Epoch 1 Thread 0 . . . No longer simple, symmetric graph Asymmetry causes complexity Goal: Incorporate synchronization-based happens-before arcs Instrument sync with vector clocks to capture happens-before arcs Calculate dataflow primitives (In, Out, Side-In, Side-Out, Gen, Kill) at boundaries Chrysalis Analysis considers p untainted at *p in subblock <2,1> Chrysalis Analysis

23 Michelle Goodstein Butterfly Analysis: Recall Graph Model l-1 Body l+1 Head Epochs l Thread t Tail Commit Order Wings Wings Original Butterfly Analysis: From perspective of the body Chrysalis Analysis 24 Michelle Goodstein Butterfly Analysis: Creating Local State l-1 Thread t

Epochs l taint p l+1 untaint p *p Commit Order Wings Local State ( Chrysalis Analysis Wings ) calculated by augmenting Global State with effects of Head 25 Michelle Goodstein Butterfly Analysis: Calculating Side-Out l-1 Thread t taint p Epochs l taint: p: 1 {p} l+1

untaint p *p Commit Order Wings Wings Each block in the wings has a side-out ( Chrysalis Analysis 26 ) generated by lifeguard Michelle Goodstein Butterfly Analysis: Computing Side-In l-1 Thread t taint p p:1 Epochs l p:1 taint: {p}untaint p l+1 *p Commit Order

Wings Wings All side-out from the wings are combined into one side-in ( Chrysalis Analysis 27 ) Michelle Goodstein Chrysalis Analysis: Incorporating Sync Arcs Thread t Epochs l+1 l l-1 Head Head Body Body Commit Order Tail Wings Wings In general: Sync introduces asymmetry/complexity, in body and wings Chrysalis Analysis

28 Michelle Goodstein Chrysalis Analysis: Calculating Local State Thread t l-1 meet taint p taint: p:1 untaint p{p} untaint: p:0 {p} Commit Order Epochs l+1 l *p Wings Wings Highlighted blocks involved in local state computation for body Chrysalis Analysis 29 Michelle Goodstein

Chrysalis Analysis: Calculating Local State Thread t l-1 taint p untaint p Commit Order Epochs l+1 l *p Wings meet Wings Calculating local state becomes increasingly complex with more arcs Chrysalis Analysis 30 Michelle Goodstein Chrysalis Analysis: Side-In/Side-Out Thread t l-1 taint p untaint p

Commit Order Epochs l+1 l *p Wings Wings Arcs to/from the body alter the wings for each subblock, and the side-in Chrysalis Analysis 31 Michelle Goodstein Chrysalis Analysis: Side-In/Side-Out Thread t l-1 taint p untaint p Commit Order Epochs l+1 l *p Wings

Wings Arcs to/from the body alter the wings for each subblock, and the side-in Chrysalis Analysis 32 Michelle Goodstein Chrysalis Analysis: Side-In/Side-Out Thread t l-1 taint p untaint p Commit Order Epochs l+1 l *p Wings Wings Arcs to/from the body alter the wings for each subblock, and the side-in Chrysalis Analysis 33 Michelle Goodstein Chrysalis Analysis: Side-In/Side-Out

Thread t l-1 taint p untaint p Commit Order Epochs l+1 l *p Wings Wings Arcs to/from the body alter the wings for each subblock, and the side-in Chrysalis Analysis 34 Michelle Goodstein Chrysalis Analysis: Side-In/Side-Out (Reversed Arc) Thread t l-1 taint p untaint p Commit Order Epochs

l+1 l *p Wings Wings Each subblock in the body can have different set of wings Chrysalis Analysis 35 Michelle Goodstein Thread t Thread t l-1 Head l-1 Head Epochs l Body Epochs l Body l+1

Tail l+1 Contrast: Butterfly vs Chrysalis Analyses Tail Wings Wings Wings Butterfly Analysis Local state: calculate from head One set of wings/side-in per body Simple epoch summary updates global state Wings Chrysalis Analysis Local state: calculate from all predecessors Wings/side-in differ for each body subblock Epoch summary must consider partial order Includes arcs from epochs l+1 to l [extended epoch] Research Challenges - False positives due to missed synch

Chrysalis Analysis + 36 Improved precision Michelle Goodstein Chrysalis Analysis: Parallel Forward Dataflow Analysis With Sync Arcs l-1 Head Epochs l Body l+1 Commit Order Thread t Tail Wings Wings General dataflow analysis framework 2-pass lifeguards + global state update

Canonical examples: Reaching Definitions, Available Expressions Memory/Security lifeguards: TaintCheck, AddrCheck Provably sound Framework never misses an error (zero false negatives) Efficient analysis Use dataflow meet to avoid excessive recomputations Chrysalis Analysis 37 Michelle Goodstein Experimental Methodology Prototype built upon the Log-Based Architecture (LBA) framework [Chen08] Full Butterfly & Chrysalis Analysis stacks implemented in software Simulated hardware on shared-memory CMP using Simics Used LBA for dynamic instruction traces, inserting epoch boundaries Used LBA shim library to dynamically instrument synchronization calls Measured 2 CMP configurations: {4,8} cores Corresponds to {2,4} application and {2,4} lifeguard threads 4 SPLASH Benchmarks: FFT, FMM, LU, BARNES Comparison of Butterfly Analysis and Chrysalis Analysis Chrysalis Analysis 38 Michelle Goodstein Chrysalis Slowdown, Parallel Phase (Relative to Butterfly)

Performance Results: Chrysalis Slowdown (relative to Butterfly) 3 2.5 2 1.5 1 0.5 0 Average Slowdown: 1.9x Chrysalis Analysis 39 Michelle Goodstein Potential Errors Reported By TaintCheck Precision Results: Potential Errors, Chrysalis vs Butterfly 62 25 38 93 93 20 15 13 12 9 10 5 1 0

10 5 3 0 0 0 0 0 0 Average Reduction in Reported Errors: 17.9x Chrysalis Analysis 40 Michelle Goodstein Precision Results: Percent Reduction in Potential Errors 100 % Reduction in Reported Potential Errors (Chrysalis, Relative to Butterfly) 98 96 94 92 90 88 86 84 82 80

Average Reduction in Reported Errors: 97% Chrysalis Analysis 41 Michelle Goodstein Chrysalis Analysis: Conclusions and Future Work General purpose parallel dynamic dataflow analysis platform Provably sound (never misses an error) Generalization retains advantages of Butterfly Analysis Supports relaxed memory consistency models Software framework No detailed inter-thread data dependence tracking TaintCheck Implementation Large reduction in false positives (average: 17.9x) Modest relative increase in overhead (average: 1.9x) Future work: Build many sophisticated runtime analysis tools in framework Chrysalis Analysis 42 Michelle Goodstein Questions?

Recently Viewed Presentations

  • SUMMER ACADEMY Grades 3-5 English Language Arts Summer 2013

    SUMMER ACADEMY Grades 3-5 English Language Arts Summer 2013

    Clock Buddies The Reading-Writing Connection "…writing is treated as an equal partner to reading, and more than this, writing is assumed to be the vehicle through which a great deal of the reading work and reading assessments will occur."
  • Slide_template_IHCP.ppt - Hacettepe

    Slide_template_IHCP.ppt - Hacettepe

    Two in vitro models are under investigation at ECVAM: human airway epithelial cell line Calu-3 and the human alveolar type cell line NCI H441 Key area - Systemic toxicity MEIC - Multicentre Evaluation of in vitro Cytotoxicity tests Initiated by...
  • video slide - fac.ksu.edu.sa

    video slide - fac.ksu.edu.sa

    All living organisms are composed of matter. Matter. is anything that takes up space and has mass. An . element. is the simplest form of matter. Cannot be broken down to other substances by chemical reactions.
  • 1950s & 1960s: Civil Rights  2015 Brain Wrinkles

    1950s & 1960s: Civil Rights 2015 Brain Wrinkles

    In 1960, a commission was formed by Atlanta banker John Sibley that held public hearings to see how Georgians felt about integration. The Sibley Commission found that 2 out of 3 Georgians would rather see schools closed that integrated. As...
  • Patient Safety Its the Way WeCare Buffy Key

    Patient Safety Its the Way WeCare Buffy Key

    "up to 98,000 people a year die because of medical mistakes in hospitals" "To Err is . Human" report - IOM. Medical . Errors - 2017 "10% of all U.S. deaths are now due to medical error" "3. rd. highest...
  • Enterprise Risk Management (ERM) in Action

    Enterprise Risk Management (ERM) in Action

    The Risk Management team notes that the new net retention is 1.7% of surplus, which is still below ABC's risk tolerance of 2.5%. ABCis more susceptible to multiple events per year, however. Because of concern over the possibility of losing...
  • Glencoe Biology - Rochester Community Schools

    Glencoe Biology - Rochester Community Schools

    * * * Reproduction and Development In most amphibians, fertilization is external Eggs must be laid and fertilized in water Fishes and Amphibians Tadpoles hatch from the egg and undergo metamorphosis from a fishlike animal to an air-breathing one. 28.3...
  • The New Craft of Intelligence What Should the

    The New Craft of Intelligence What Should the

    We desperately need analytic tools, and I would very much like to see General Kernan at JFCOM take on these 18 functionalities as part of the Future Intelligence Collaborative Environment (FICE), and in the process, working with the National Institute...