Dynamic Analysis
Dynamic AnalysisCS252r Fall 2015
Reading The Concept of Dynamic Analysis by ThomasBall, FSE 1999 Efficient Path Profiling by Thomas Ball and JamesLarus, MICRO 1996 Adversarial Memory for Destructive Data Racesby Cormac Flanagan and Stephen Freund, PLDI2010Stephen Chong, Harvard University2
Dynamic Analysis Analysis of the properties of a running program Static analysis typically finds properties that holdof all executions Dynamic analysis finds properties that hold of oneor more executions Can't prove a program satisfies a particular property But can detect violations and provide useful information Usefulness derives from precision of informationand dependence on inputsStephen Chong, Harvard University3
Precision of Information Dynamic analysis typically instructs program toexamine or record some of run-time state Instrumentation can be tuned to precisely dataneeded for a problemStephen Chong, Harvard University4
Dependence on Program Inputs Easy to relate changes in program inputs tochanges in program behavior and programoutputDynamic Analysesareinput-centricStephen Chong, Harvard UniversityStatic Analysesareprogram-centric5
Complementary Techniques Completeness Dynamic analyses can generate "dynamic program invariants", i.e.,invariants of observed execution; static analyses can check them Dynamic analyses consider only feasible paths (but may notconsider all paths); static analyses consider all paths (but mayinclude infeasble paths) Scope Dynamic analyses examine one very long program path Can discover semantic dependencies widely separated in path and intime Static analyses typically and at discovering "dependence at a distance" PrecisionStephen Chong, Harvard University6
Two (plus a bonus) Dynamic Analyses Frequency Spectrum Analysis Efficient path profiling Dynamic race detectionStephen Chong, Harvard University7
Frequency Spectrum Analysis Understanding frequency of execution ofprogram parts can help programmer: partition program by levels of abstraction find related computations find computations related to specific attributes of inputor outputStephen Chong, Harvard University8
Understanding an Obfuscated CProgram#include stdio.h main(t, ,a)char *a;{return!0 t?t 3?main(-79,-13,a main(-87,1- ,main(-86,0,a 1) a)):1,t ?main(t 1, ,a):3,main(-94,-27 t,a)&&t 2? 13?main(2, 1,"%s %d %d\n"):9:16:t 0?t -72?main( ,t,"@n' ,#'/*{}w /w#cdnr/ ,{}r/*de} ,/*{* ,/w{% ,/w#q#n ,/#{l ,/n{n ,/ #n ,/#\;#q#n ,/ k#;* ,/'r :'d*'3,}{w K w'K:' }e#';dq#'l \q#' d'K#!/ k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/ #n';d}rw' i;#\){nl]!/n{n#'; r{#w'r nc{nl]'/#{l, 'K {rw' iK{;[{nl]'/w#q#n'wk nw' \iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \;;{nl'-{}rw]'/ ,}##'*}#nc,',#nw]'/ kd' e} ;#'rdq#w! nr'/ ') } }{rl#'{n' ')# \}' }##(!!/"):t -50? *a?putchar(31[a]):main(-65, ,a 1):main((*a '/') t, ,a 1):0 t?main(2,2,"%s"):*a '/' main(0,main(-61,*a,"!ek;dc i@bK'(q)-[w]*%n r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a 1);}Stephen Chong, Harvard University9
What it does. gcc -w obfus.c ./a.outOn the first day of Christmas my true love gave to mea partridge in a pear tree.On the second day of Christmas my true love gave to metwo turtle dovesand a partridge in a pear tree.On the third day of Christmas my true love gave to methree french hens, two turtle dovesand a partridge in a pear tree.Stephen Chong, Harvard University10
Program understanding We know what the program does Our aim is to understand how it does it Before reverse engineering it, let's have a model in mind: Gift t mentioned 13-t times in the poem (e.g. "five gold rings" occurs 13-5 8 times) So 1 2 . 11 12 13*6 78 gift mentions (66 mentions of non-partridge gifts) All verses except first have formOn the ordinal day of Christmas my true love gave to me list of gift phrases, from the ordinal day down to the second day and a partridge in a pear tree.and first verse isOn the first day of Christmas my true love gave to mea partridge in a pear tree. Unique strings: 3 strings for common structure ("On the", "day of Christmas.", "and a partridge .") 12 strings for the ordinals 11 strings for the second through twelfth gifts. approx. 3 12 11 26 unique strings in program, prints approx. 3*12 12 66 114 strings.Stephen Chong, Harvard University11
Model 12 days of Christmas (also 11, to catch "off-byone" cases) 26 unique strings 66 occurrences of non-partridge-in-a-pear-treepresents 114 strings printed, and 2358 characters printed.Stephen Chong, Harvard University12
Program understanding First let's make it readable:Stephen Chong, Harvard UniversityIt's a singlerecursive function!13
Path Profiling Count executions of paths of the function E.g., path executed 2358 times likely involved in printing charactersStephen Chong, Harvard University14
!HSUPPath ProfilingStephen Chong, Harvard UniversityEfficient PathProfiling, Ball andLarus, MICRO 199615
Path ProfilingProblem: path profilingnt Path ProfilingmJames R. Larus*Dept.ofComputerSciences Which pathsJamesthroughR. Larus* a procedure are most common?UniversityofWisconsin-MadisonDept.of ComputerSciences e.g.,performaggressiveoptimization on hot paths, make sure alllarus@cs.wisc.eduUniversityof Wisconsin-Madisonpathsaretested.larus@cs.wisc.edu Naive approach: count edge transitionsacyclicicbsumesh onlymesny ABDEF90ACDF 00020FToflFroa90600100200110400100020e inmented Not enoughtoprofilingdeterminepaths!Figure 1. informationExample in which edgedoesnot idenl-previtify the most frequently executed paths. The table conStephen Chong, Harvard Universitys, path16
Efficient Path Profiling (For DAGs) Encode each path as a unique integer and recordpath as state i.e., at end of DAG, value of a register identifies paththrough DAGprofiles, although the conhows. Also, the number ofinite and linear in the prooops offers an unboundedidering only acyclic pathscase, its size is still expo-e profiling is neither coma new and efficient techgorithm places instrumensStephendynamicfreChong,executionHarvard UniversityL-h.Br 2r O'r 4Ii?3Dr lEFccnmt [x-l IPathACDFACDEFABCDFABCDEFABDFABDEFEncoding01234517
Algorithm overview 1. Number paths uniquely 2. Use spanning tree to select edges toinstrument (and compute appropriate incrementfor each instrumented edge) 3. Select appropriate instrumentation 4. After profiling, given path number, figure outwhich path it corresponds toStephen Chong, Harvard University18
Compact path numbering Aim: assign non-negative constant value to each edgesuch that sum of values along any path from ENTRYto EXIT is unique. Moreover, path sums should be inrange 0.(NumPaths - 1) (i.e., minimal encoding)Stephen Chong, Harvard University19
Compact path numbering--- .-- -- . --- --”ifv is a leafAvertexNumPaths(v) 1;) else{NumPaths(v) 0;for each edge e v- w CVal (e) NumPathsCv);NumPaths(v) NumPathsCv)--”3:2I3200c0nLEJ NumPathsCw);Artex3:2;; v- w CFigure 5. AlgorithmathsCv);DAG. nLEJvertex v mathsedgesin aedges. If T is the set of spanning tree edges, then any graphStephen Chong, Harvard University6422.WFigure 6. Control-flow gcomputed by the algorithmInductionStep:Show20
Efficiently compute sums--- .-- -- . --- --” Find min-cost spanning treeNumPaths(v) 1;) else chord{( max costedges)ifv is a leafvertexNumPaths(v) 0;for each edge e v- w CVal (e) NumPathsCv);NumPaths(v) NumPathsCv) Chord edges will be instrumentedA3:2I32A A A 3 B 33 Move weights from non-chord NumPathsCw);edges to chord edges00vertec0nLEJwith integer01Figure 5. Algorithm for 4assigning values to edgesin5 aexit ofgraphthe froDFigure 6. Control-flowDAG.computed by the algorithm in FigurBCBCalongthatpaBC2-2-2this step may40D edges, then any graphDIn thethatnexedges. IfDT is the set of spanning treeInductionStep:Show-1edge1 not in T is a chord of the1 spanning tree.computation,any vertex v of heightH (HFor example, in the graph of Figure 2, vertex A is the 1 . . . W, of v musthave heightFaminimalnuEEFEFENTRYvertex and vertex F is the EXIT vertex. The unthe graph is a DAG), so the thein the DAG’sadorned graphtree. The edges(c)Cb)b) edges comprise a spanningIt is trivial to see that the numbStephen Chong, HarvardlabeledUniversity by squares are chords of the spanning tree.EXITis Cy ‘ ,uninstrumenteNumPaths(wi),21
Instrumentation Needed instrumentation: Initialize path register (r 0) at ENTRY Increment register on instrumented edges (r Inc(e)) Record path's counter at EXIT (count[r] ) Can optimize: Chord edge e can initialize counter (r Inc(e)) iff firstchord edge on every path from ENTRY to EXIT containing e Chord edge e may increment path register and memorycounter (count[r Inc(e)] ) iff last chord edge on everypath from ENTRY to EXIT containing eStephen Chong, Harvard University22
InstrumentationA A A 3 B 33terinitializatione isa chordcodewith integer value0145NTRY);exit of the DAG pot WS.emptyO{BCBCalongthatpath(thv WS.removeO;BC2-2-2ach edge e v- wthis step may have40e is a chord edgeDDDIn the next stepnstrumentce,'r Inc(e)');1-11if e is the only incomingedgeof wanmt[rcomputation, by fiWS.add(w);Fa minimal numberEFEF'r O');instrumentte,Ein the DAG’s spa(c)Cb)b)uninstrumented ery incrementcodeFigure 9. Optimization of instrumentationfor the controlform a spanning tflowgraphofFigure1.Figure 4. Three possible placementsof instrumentationXIT)ningtrees,thealgofor the{ control-flow graph from Figure 1.ot WS.emptyOtation along edgesw WS.removeO;ach edge e v- wControl-Flow4 Path Profiling of ArbitraryAfter reviewingStephen Chong, Harvard UniversityedgeI23
Details, details, details Algorithm works for DAGs Need to transform programs to be DAG like (andprofile on DAG sub-graphs of cyclic graph)Stephen Chong, Harvard University24
POP!Path ProfilingStephen Chong, Harvard University25
Path Profiling12 days of Christmas (also 11, to catch"off-by-one" cases)26 unique strings66 occurrences of non-partridge-in-apear-tree presents114 strings printed, and2358 characters printed. With manual examination: Path 0 (executed once) initializes the recursion with the call main(2,2,.). Paths 19, 22, and 23 control printing of the 12 verses. P19 first verse, P23 middle 10 verses, and P22 last verse. Paths 9 and 13 control printing of non-partridge-gifts within verse. (Frequencies of P9 P13 66) Paths 2 and 3 responsible for printing out a string. Paths 1 and 7 print out the characters in a string. (why two?) Path 4 skips over n sub-strings in the large string, each sub-string terminated with '/' Path 5 linearly scans the string that encodes the character translationStephen Chong, Harvard University26
Reversed-engineered ProgramStephen Chong, Harvard University27
Reversed-engineered ProgramStephen Chong, Harvard University28
Stephen Chong, Harvard University29
Adversarial Memory for DetectingDestructive Data Races By Flanagan and Freund, PLDI 2010 A dynamic analysis to find data races inconcurrent programs What's a data race?Stephen Chong, Harvard University30
adverrministicalues thatLEse whichrget protale” visates fairexample,ns an in-Program ModelFigure 3. Multithreaded program traces. 2 Trace:: Operation a, b 2 Operation :: s, t, u 2 Tidrd (t, x, v) wr (t, x, v) acq(t, m) rel (t, m) fork (t, u) join(t, u)x, y 2 Varm 2 Lockv 2 Value A multithreaded program has concurrently executingconsists of a number of concurrently executing threads, each withthreadsa (eachwith thread Tid) variablescy write,thread identifiert 2 Tid .identifierThese threadst manipulate(and stillx 2 Var and locks m 2 Lock . A trace captures an executionmanipulates variables and locksp. Each threadof a multithreaded program by listing the sequence of operationss (whichperformedby the variousthreadsin the system.We ignore control y (whichoperations (branches, looping, method calls, etc) and local compuate a partations,as they areexceptorthogonalto memory tomodelissues. Thus, Ignoreseverythingread/writesvariables,lockthethat anyset of operationsthat a thread t can perform are:operations,andfork/join.ill some rd (t, x, v) and wr (t, x, v), which read and write a value v froms guaranStephen Chong, Harvard Universitya variable x;31
e of mullthough aestructivehavior onntially 0%e 1, J UM un, whilens.developedprograms,ces. Interency, theyFigures 1ear underes not exraces thatal, multideterminkers needn order toacq(t, m) and rel (t, m), which acquire and release a lock m; fork (t, u), which forks a new thread u; andHappens-before relation and races join(t, u), which blocks until thread u terminates.This set of operations suffices for an initial presentation of our analysis; our implementation supports a variety of additional synchronization constructs, including wait, notify, volatile variables, etc.The happens-before relation for a trace is the smallesttransitively-closed relation over the operations3 in such that therelation a b holds whenever a occurs before b in and one ofthe following holds: [P ROGRAM ORDER ] Both operations are by the same thread. [L OCKING ORDER ]: a releases a lock that is later acquired by b. [F ORKORDER ] :a is fork (t, u) and b is by thread u. [J OIN ORDER ]: a is by thread u and b is join(t, u).If a happens before b, then we also say that b happens after a. If twooperations in a trace are not related by the happens-before relation,then they are considered concurrent. Two memory access conflictif they both access (read or write) the same variable, and at leastαone of the operations is a write. Using this terminology, a trace hasa race condition if it has two concurrent conflicting accesses. Two operations a and b are concurrent if neither a α b nor b a A trace has a race if there are two memory accessesMemoryModels at least one of them is a writeto the3.samevariable,detectingA memory model specifies what values can be returned for tioninaprogramtrace.Atrace islegal under athe JMM,memory model if the value v produced by each read operationStephen Chong, Harvard University32
Races are bad Often cause errors only on certain rare executions Hard to reproduce and reason about Exacerbated by multi-core processors and relaxed memory models BUT many races are benign E.g., approximate counters, optimistic protocols Lots of work on race detection Static: can be difficult to reason about all possible interleaving Dynamic: interleavings with races may be rare This work: standard dynamic analysis to detect "racy" variables Then try to produce an erroneous execution that exhibits the race andproduces observable incorrect behavior (e.g., crash, uncaught exception,etc.)Stephen Chong, Harvard University33
Double-checked locking exampleFigure 2. Double-checked locking.123class Point {double x, y;static Point p;4Point() { x 1.0; y 1.0; }56static Point get() {Point t p;if (t ! null) return t;synchronized (Point.class) {if (p null) p new Point();return p;}}789101112131415static double slope() {return get().y / get().x;}16171819public static void main(String[] args) {fork { System.out.println( slope() ); }fork { System.out.println( slope() ); }}2021222324}Stephen Chong, Harvard University Relaxed memorymodel means thatget().x couldevaluate to zero. (Thus, the race on p isdestructive, i.e., nonbenign) But most of the time,destructive behaviornot exhibited34
Adversarial Memory Exploits full flexibility of relaxed memory modelto try and cause crashes Tool tracks memory and synchronizationoperations of execution, and keeps a writebuffer recording history of writes to racyvariables When a thread asks for a value, return older (butstill legal) values whenever possibleStephen Chong, Harvard University35
Memory Models Sequential Memory Model: read operation a rd(t,x,v) in trace α may only return the value ofthe most recent write to that variable in α Intuitive but limits optimization by compiler, virtualmachine, and hardware. Happens-Before Memory Model: read operationa rd(t,x,v) in trace α may return the value ofany write operation b wr(u, x, v) provided:1. b does not happen after a; and2. no intervening write c to x where b α c α aStephen Chong, Harvard University36
Out-of-thin-air Considerx : y y : x Assume x and y are initially zero. Under happens-before memory model, the following trace is possible:rd(t1, x, 42) wr(t1, y, 42) rd(t2, y, 42) wr(t2, x, 42) Where did 42 come from?!? Java Memory Model extends the happens-before memory model with acausality requirement to preclude non-sensical traces as above This paper uses Progressive Java Memory Model: read operation a rd(t,x,v) in trace α may return the value of any write operation b wr(u, x, v) provided:1. b is before a in trace α; and2. no intervening write c to x where b α c α aStephen Chong, Harvard University37
Adversarial Memory Implementation Uses vector clocks to record time stamps of writeoperations Vector clocks can be used to determine the happensbefore relation Read operation for x at time Ct can return anyvalue so long as it satisfies the Progressive JavaMemory Model i.e., a write in the write buffer for x that happened attime Ki such that there is no write at time Kj whereKi Kj CtStephen Chong, Harvard University38
Adversarial Memory Heuristics Sequentially consistent: always return most recentlywritten value Oldest: chose "most stale" value. (occasionally returnmost-recent value to satisfy fairness assumptions) Oldest-but-different: return oldest element that isdifferent from the last value read Random: return a random value from the permittedvalues Random-but-different: return a random value from thepermitted value that is dfferent from the last value readStephen Chong, Harvard University39
EffectivenessProgramFieldFigure 8Figure 2Figure 2Figure p.xp.yCompany.elapsed timeCompany.modeUniversal.UNIVERSAL um1TspSolver.MinTourLenarray index [0] and [1]array index [0] and [1]array index [0] and [1]NoJumble0000000000000Erroneous Behavior Observation Rate (%)J UMBLE sQoSYesYesYesFigure 9. Observation rate for erroneous behavior under various heuristics. Destructive races are marked in bold. QoS indicates that the onlyobserved difference was significant slowdown.but the value of that variable is not used anywhere else in the program. Thus we consider this race benign.Program raytracer, JGFRayTracerBench.checksum1: Thisprogramcreatesa groupof worker threads that, upon completion,Stephen Chong,HarvardUniversitybarrier does not introduce happens-before edges between writesbefore the barrier and reads following the barrier, so read operationscould read stale data, causing the program to compute the incorrectfinal value. The program recognizes and reports this failure when40validating its result 100% of the time under J UMBLE.
ny.elapsed timeCompany.modeUniversal.UNIVERSAL umTspSolver.MinTourLenarray index [0] and [1]array index [0] and [1]array index [0] and [1]BaseTime ptyJumble Instances 8.96253,433Max. Buffer SizeNo Comp.With Comp.228440,0055105652623255322,047716,38332Figure 10. Performance of J UMBLE under the Sequentially-Consistent configuration.for all but two programs, and the garbage collection overhead wasnegligible. The montecarlo and lufact benchmarks benefitedthe most, and garbage collection enabled the buffers for those programs to be several orders of magnitude smaller that otherwise.For some array-intensive benchmarks, J UMBLE had to apply the[ REMOVE OLDEST ] rule to maintain this bound on write buffers, butin practice this rule did not limit J UMBLE’s ability to detect destructive races.6.3Checking the Eclipse Development EnvironmentTo validate J UMBLE in a moreStephen Chong, Harvard Universityrealistic environment, we also applied it to the Eclipse development environment, version 3.4.0.fully detects violations of sequential consistency [9, 10], but doesnot identify which sequential consistency violations cause destructive behavior. An interesting area for future work is to adapt Jumble’s adversarial memory approach to detect destructive race conditions for these memory models.Much other work (including, for example, [27, 40]) identifiesdefects in multithreaded programs by exploring many (or possiblyall) possible interleavings. Most of these tools assume sequentialconsistency. In contrast to this prior work based on scheduling nondeterminism, this paper proposes a complementary approach ofusing memory-model non-determinism to expose destructive races.Dynamic analyses to detect race conditions include Eraser’s 41
Dynamic analyses can generate "dynamic program invariants", i.e., invariants of observed execution; static analyses can check them Dynamic analyses consider only feasible paths (but may not consider all paths); static analyses consider all paths (but may include infeasble paths) Scope Dynamic analyses examine one very long program path
Dec 06, 2018 · Dynamic Strategy, Dynamic Structure A Systematic Approach to Business Architecture “Dynamic Strategy, . Michael Porter dynamic capabilities vs. static capabilities David Teece “Dynamic Strategy, Dynamic Structure .
There are many dynamic probe devices in the world, such as Dynamic Cone Penetrometer (DCP), Mackin-tosh probe, Dynamic Probing Light (DPL), Dynamic Probing Medium (DPM), Dynamic Probing High (DPH), Dynamic Probing Super High (DPSH), Perth Sand Penetrometer (PSP), etc. Table 1 shows some of the dynamic probing devices and their specifications.
Dynamic Mechanical Analysis Dynamic mechanical properties refer to the response of a material as it is subjected to a periodic force. These properties may be expressed in terms of a dynamic modulus, a dynamic loss modulus, and a mechanical damping term. Typical values of dynamic moduli for polymers range from 106-1012 dyne/cm2 depending upon .
example descriptions, and also considers in detail exactly what dynamic analysis is. The dissertation makes six main contributions. First, the descriptions show that metadata is the key component of dynamic analysis; in particular, whereas static analysis predicts approximations of a program's future, dynamic analysis remembers
tional dynamic analysis, but is typically much faster because (1) unsound static analysis can speed up dynamic analysis much more than sound static analysis can and (2) verifi-cations rarely fail. We apply optimistic hybrid analysis to race detection and program slicing and achieve 1.8x over a state-of-the-art race detector (FastTrack .
Hands-on Introduction to Dynamic Blocks 2 What is a Dynamic Block? A dynamic block has flexibility and intelligence. A dynamic block reference can easily be changed in a drawing while you work. You can manipulate the geometry in a dynamic b
W e present a nov el model called the Dynamic Pose Graph (DPG) to address the problem of long-term mapping in dynamic en vironments. The DPG is an extension of the traditional pose graph model. A Dynamic Pose Graph is a connected graph, denoted DPG hN ;E i,with nodes n i 2 N and edges ei;j 2 E and is dened as follo ws: Dynamic P ose Graph .
en vironment. Then we introduce the Dynamic Pose Graph (DPG) model. A. En vironment Model and Assumptions A general dynamic en vironment model captures mo ving, low-dynamic, high-dynamic, and stationary objects, in ad-dition to entities (such as w alls or other ph ysical struc-tures) that can change. Non-stationary objects mo ve at wide-
