ATFundament of High Perf Comp
ATFundament of High Perf Comp CS 6463
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 47 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 6463 at University of Texas at San Antonio taught by Qing Yi in Fall. Since its upload, it has received 43 views. For similar materials see /class/231381/cs-6463-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.
Reviews for ATFundament of High Perf Comp
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
0 078A Dependence Based Program Analysis Richard Johnson Keshav Pingali 43116 Overview 0 Problem Description 0 Solution to the Problem 0 Definitions and Terms 0 Outline of Algorithm 0 Examples 0 Conclusion 7C um Problem Description 0 Constant Propagation 0 Partial Redundancies The classic constant propagation and the elimination of partial redundancies algorithms are based on data flow analysis The values are computed iteratively by propagating information from inputs of statements to their outputs in the case forward analysis and from outputs to inputs in the case of backward analysis This approach has several disadvantages P3115 r 76 um Problem Description The disadvantages are 0 Information is propagated throughout the control flow graph 0 When the vector at some point in the program is updated the entire control flow graph below that point or above it in backward analysis may be reanalysized 0 Many optimizations benefit from analysis performed in stages but this is difficult to do in the standard approach Two solutions 0 Defuse chains 0 Static Single Assignment SSA p 415 776 um Def Use Chains and SSA Edge Description o A defuse chain for a variable x is an edge pair 61 62 such that o the source of 61 defines x 0 the destination of 62 uses 1 and 0 there is a control flow path from 61 to 62 with no assignment to x 0 An SSA edge for variable x corresponds to an edge pair 61 62 such that 0 there exists a definition of x that reaches 61 0 there exists a use of x reachable from 62 0 there is no assignment to x on any control flow path from 61 to 62 and 0 61 dominates 62 P 515 7C um Problem Description cont Defuse chains provide a partial solution to these problems but there are three problems with using defuse chains 0 Defuse chains cannot be used for backward dataflow problems because they do not incorporate sufficient information about the control structure of the program 0 The lack of information in defuse chains affects the precision of the analysis 0 The worst case size of the defuse chains is 0E2V where E is the number of edges of the control flow graph and V is the number of variables p 515 7 13 um Problem Description cont The size problem can be overcome by using a factored representation of defuse chains called static single assignment SSA form which has the worstcase asymptotic size 0EV SSA uses a gb function to combine defuse edges having the same destination to reduce the size issue The problem with the SSA form is it cannot be used for backward analysis p 715 TC um Solution to the Problem The Dependence Flow Graph DFG is a representation of the program dependences which generalizes defuse chains and static single assignment SSA form The DFG for a program can be constructed in 0EV time The algorithm itself can be used to construct a program s control dependence graph in 0E time and its SSA representation in 0EV time which are improvements over existing algorithms Unlike defuse chains which go directly from definitions to uses a DFG edge for a variable x can bypass a region of the control flow graph only if this region is a singleentry singleexit region that does not contain an assignment to x since such a region has neither data nor control information that is of interest to the program analysis p 815 r 76 um De nitions and Terms 0 A node or edge x is said to dominate node or edge y in a directed graph if every path from start to y includes x o A node or edge x is said to postdominate node or edge y in a directed graph if every path from y to end includes x o A node or edge x is said to be control dependent on node n if x postdominates all edges on some path from n to x but x does not postdominate n lntuitively n is a conditional branch that determines if control will pass through x p 915 7C um De nitions and Terms cont o A DFG edge for variable x corresponds to an edge pair 61 62 such that 1 there exists a definition of x that reaches 61 2 there exists a use of x reachable from 62 3 there is no assignment to x on any control flow path from 61 to 62 4 61 dominates 62 5 62 postdominates 61 and 6 every cycle containing 61 also contains 62 and vise versa Conditions 1 through 4 are the same as in the SSA representation In the DFG the merge operator plays the same role as gb functions do in SSA form Conditions 4 through 6 formally specify that the region of the control flow graph between 61 and 62 must be a singleentry singleexit region p 12015 A Comparison of Program Representations mmwl w mmrm kmmmrm u a CPU with defuse cha39ms b SSA form c DFG form t6 um Outline of Algorithm 1 Determine the variables defined within each singleentry singleexit region 2 Create a baselevel DFG with no region bypassing 3 Perform region bypassing using the information found in Step 1 4 Remove dead flow edges generated by bypassing p 1216 An Illustration of BF G Construction comml Flow quotquotquotquotquot quot 339 lamanu for x 9 dnpemlem for 3 39 39 39 39 Iggf i 392 I a emmpie CFG b baselevel DFG c after region bypassng and dead edga removal 7 MC um Def Use Constant Propagation Example if p then z 1 x 39 z2 else z 2 x z1 y i X a allpaths The first use of 2 can be replaced by 1 and the second use of 2 by 2 The right hand sides of the two definitions of 1 can now be simplified to the constant 3 and the final use of 1 can be replaced by 3 p 1416 776 um DF G Constant Propagation Example p true if p then x 1 else x 2 y i X b possiblepaths By ignoring the definition on the unexecuted branch the use of 1 in the last statement can be determined to have a value 1 Such possible path constants are common in code generated from inine expansion of procedures or macros but algorithms that use defuse chains alone do not find these constants p1516 Improving Security Using Extensible Lightweight Static Analysis David Evans and David Larochelle Presented by Sreedevi Jagavarapu Overview EIEIEIEIEI Introduction Common Vulnerabilities Mitigating Software Vulnerabilities Splint Overview Buffer Overflows I Use warnings I Describing functions I Analyzing Program values Extensible checking I Detecting format bugs I Taintedness attributes Conclusion Introduction III Security attacks exploit I Poorly chosen passwords l Careless configuration I Software implementation flaws Common Vulnerabilities Other 16 39 Mallormetl Input 15 Access 16 Butler overllowa 19 Format bugs 6 Resource leaks 5 Pallmames 1 0 Symbolic links 11 Figure l l ommun Vulnerabilities and Exposures list for the rst nine months at 20m Must at the entries ar enmmun aws detectable by static analysis including 339 butler overflow vulnerabilities Mitigating Software Vulnerabilities III Limiting damage Modifying program binaries to insert runtime checks Running applications in restricted environments III Eliminating flaws Human Code reviews III Timeconsuming and expensive Testing III Ineffective for finding security vulnerabilities Static Analysis III Rather than observe program execution they analyze source code directly Goal of the paper III Goal Review a tool called Splint Previously known as LCLint I It uses lightweight static analysis I It detects vulnerabilities in programs I Similar to compiler I Annotations added to program Splint Overview III Annotations l Denoted using C comments identified by an character following the comment marker III Analysis We can analyze both theoretically and practically It analyzes procedure calls from annotations III Preconditionspostconditions No guarantee that all messages indicate real bugs No guarantee that all bugs will be found Buffer Overflows III It is single most important security problem of the past decades eg Overwriting a buffer on the stack replacing the return address C programs are vulnerable l C is designed with emphasis on performance and simplicity l Unsafe functions in ANSI C eg getsenters unbounded amount of input Splint detects both stack and heap based buffer overflows I Use warnings I Describing functions I Analyzing Program values Use Warnings El Produce warnings whenever code uses library functions susceptible to buffer overflow vulnerabilities III Splint reports all uses of gets fwarn bufferoverflowhigh quotUse of gets leads to m X El Limitation l Alert possibly dangerous code but provide no assistance Describe Functions III This property can describe by adding a requires clause to the declaration I I strcpy Wirequlres maxSetisigt maxReads2i I It uses two buffer attributes El Maxset III MaxRead III Produce warnings I If maXSet 5 gt maxReadt I 5 might be over run by strcpy call Analyzing Program Values El Splint analyzes a function body annotated precondition El It generates preconditions and post conditions at the expression level in the parse tree using internal rules I eg char bufmaxsize III Preconditions maxSet buf MAXSIZE 1 and minSet buf 0 El Sprint issues a warnings about the unsatisfied condition I If it cannot determine that the value is between 0 and MAXSIZE 1 Extensible Checking El It is used to detect misuses of files and sockets fail to close a file Detecting format bugs Taintedness attributes Detecting Format Bugs El Format bug Attacker can send hostile input as the format string for a variable arguments I egprintfn Detect Format vulnerabilites l Provide warnings for any unknown string at compile time I set formatconst flag I Detect weather it comes from user or external environment III Eg Perl s taint option I Set T flag Taintedness Attributes El EIEIEIEIEI Splint can detect dangerous operations with tainted values at compile time Taintedness attributes associated with char objects Annotations are tainted ancl untainted Transfers Merge Defaults Definition of Taintedness Attribute attribute taintedness context reference char oneof untainted tainted annotations tainted reference gt tainted untainted reference gt untainted transfers tainted as untainted gt error quotPoesibly tainted storage used as untaintedquot merge tainted untainted gt tainted defaults reference gt tainted literal gt untainte null gt untainted end How to run Splint El Running Splint is an iterative process El Splint checks approximately 1000 lines per second so it is fairly easy to run Splint III The goal is to eliminate all the warnings by modifying code or adjusting annotations Running Splint on wuftpd False warnings checking wu pd Cause Number Percent External assumptions 6 79 Arithmetic limitations 13 171 Alias analysis 3 39 Flow control 20 263 Loop heuristics 10 132 Uther 24 316 Pros and Cons of Splint III Advantages l Lightweight static analysis detects software vulnerabilities l Splint can only find problems inconsistencies between code language conventions assumptions documented annotations III Disadvantages l Splint produces more warning messages leading to confusion I It will not eliminate all security risks Conclusion El No tool will eliminate all security risks III Lightweight static analysis tools will help codify known security vulnerabilities and integrate into development process El Splint plays an important part in codifying security vulnerabilities References El El 1 Common Vulnerabilities and Exposures version 20010918 The Mitre Corporation 2001 httpcvemitreorg current Nov 2001 2 D Wagner et al A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities Proc 200 Network and Distributea7 System Security Symp Internet Society Reston Va 2000 wwwisocorgndss2000proceedings current Nov 2001 3 I Goldberg et al A Secure Environment for Untrusted Helper Applications Confining the Wily Hacker Proc Sixth Usenix Security Symp UseniX Assoc Berkeley Calif 1996 wwwcsberkeleyedudawpapersanususeniX96ps current Nov 2001 4 D Evans and A Twyman Flexible PolicyDirected Code Safety IEEE Symp Security and Privacy IEEE CS Press Los Alamitos Calif 1999 pp 32 45 5 A Baratloo N Singh and T Tsai Transparent RunTime Defense Against StackSmashing Attacks ProcNmth Usenix Security Symp UseniX Assoc BerkeleyCalif 2000 wwwusenixorgeventsuseniX2000generalbaratloohtml current Nov 2001 Static analysis tools for detecting buffer overflow vulnerabilities Sreedevi Jagavarapu Introduction Introduction Splint Uno Orion Conclusion The Problem Programs are buggy Manual inspection print statements debuggers are not always effective and are time consuming There is lack of information on which software analyzer tools are most helpful Static Analysis Tools Static Analysis analyze programs without running them Analysis is possible before a program is compliable No test suite is necessary May not find every memory error Some Static Analysis Tools C 3 FlexeLint Coverity Fawfinder Discover PolySpace CodeAssure Klocwork Prexis CodeS PREfast Fortify Orion TS4 DMS Jawa Klocwork Orion FindBugS lt2nh Splint Smatch Blast Uno CQual MOP Easy to Use Splint very easy to use Knowledge of annotations is not compulsory Knowledge of annotations allows full functionality Good documentation Easy to run eg host splint filenamec Splint Annotations Denoted using C comments identified by an character following the comment marker Running Splint is an iterative process Splint checks approximately 1000 lines per second so it is fairly easy to run Splint The goal is to eliminate all the warnings by modifying code or adjusting annotations UNO It is a simple tool for source code analysis It is designed to intercept primarily the three most common types of software defects Use of uninitialized variables Nullpointer references Outof bounds array indexing Orion A static analyzer from Bell Labs offering analysis of C C tunable to increase speedprecision incremental interprocedural analysis builtin and userdefined checks aim at semantic errors usebefore def rather than type mismatch concentrate on UNO errors first Orion s Approach 2Phase AnalySIs Parsing Find Check Report GNU gcc potential feasibility errors error of each and paths path warnings 1 Analysis with light weight dataflow info 2 Tunable tradeoff speed vs precision 0 fast approximate internal solvers o slower more precise external solvers Pros and Cons of evaluated tools Splint was a helpful static tool Can be used during development and debugging It produces more warnings leading to confusion No guarantee that all messages indicate real bugs or all bugs will be found Splint some times misses the significant errors Splint hides error report in a list of explanations Orion analyzes C and C source code Conclusion No tool will eliminate all security risks