`
`
`
`ways-“revmmwwwwx-mW»"W5'“?‘f‘“r"“fl"rfig~rfi~vc
`
`STATIC ANALYSIS VIRUS DETECTION TOOLS
`FOR UNIX SYSTEMS 1
`
`Paul Kerchen, Raymond Lo, John Crossley, Grigory Elkinbard, 2
`
`Karl Levitt, Ronald Olsson
`
`Division of Computer Science
`
`University of California
`
`Davis, CA 95616
`
`Abstract
`
`This paper proposes two heuristic tools for detecting viruses in a UNEX environment. The tools
`would be used to detect infected programs prior to their installation. The tools use static analysis and
`verification techniques. One tool, the detector, searches for duplication of operating system calls. A
`program compiled and linked from source code (such as C) makes calls to standard library routines
`for operating system services; relevant to detecting viruses are calls on files services, such as open and
`write. Such object code will contain only one instance of the standard library subroutine for each type
`of service requested by the program. A virus Would most likely carry along‘its own system calls; hence
`an infected program would have duplicate calls to the file service and is easily caught by the detector.
`The second tool, the filler, uses static analysis to determine all of the files which a program is capable
`of writing to. By knowing what files a program can and cannot write, one can decide whether or not
`that program is suspécious. The paper discusses the features and shortcomings of both tools and gives
`some implementacion details related to the detection of UNlX viruses.
`in order to defeat these tools,
`a virus would have to be quite complex and,
`if successful
`in avoiding detection by these tools, accept
`limited propagation. The tools are also useful for detecting more general malicious code. such as Trojan
`Horses.
`
`1
`
`Introduction
`
`Ideallfione would like to be able to detect an infected program without having to execute it and
`without noticeably impairing the performance of the system. Some virus detection techniques (see
`[6] and [7D rely on run-time checking of program behavior, but employ auxiliary hardware to avoid
`a performance penalty; the hardware can be viewed as a generalization of the familiar watchdog
`timer. Howaver, these run—time methods potentially expose the syatem to a virus which is able
`to‘do its. damage before being detected Other run-time techniques (see [2], [3], and [8]) do not
`allow a program to execute if it fails to pass certain tests; these methods are useful, but they may
`introduce an unacceptable amount of overhead to the execution time of programs. Typically, these
`methods involve protecting programs stored on a, disk with cryptographic checksums. Another
`method [10, 11} queries the users at runtime for all file modifications (it requires users to identify
`the programs that can write to his files. Most virus detection techniques have serious limitations
`because they detect and inhibit the spread of viruses, not their presence. They cannot be applied
`to programs which are obtained from unreliable sources since they all rely upon having a clean
`copy of the program available for cOmparlson, or they require user interaction at runtimo, or they
`require access protection mechanism absent from most operating systems. Other approaches (eg.
`3Supported by grants from Lawrence Livermore National Laboratory,
`the State of California MICRO program,
`and Deloitie Touche1 luc.
`2Currently at Amdalil Corporation, SunnyvalefiA
`
`350
`
`Cisco Systems, Inc. v. Finjan, Inc.
`
`(38-1019
`
`
`
`y7~mum”my..
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`viruses through detecting their discerning characteristic in an infected program.
`Our approach involves the analysis of a program prior to installation, the analysis attempting to
`identify suspicious code. By statically analyzing a program, one can in principle determine whether
`a program contains suspicious code; regardless of whether or not clean code is available. This paper
`presents two static-analysis methods under implementation for detecting suspicious code indicative
`of a virus. These methods are based on the following premises:
`'
`'
`'
`
`0 Source programs are linked with the standard library during compilation. In most systems,
`the operating system services, e.g. file open, file read, file write, are provided to‘the user in
`the form of library functions. Hence a compiled and linkedpregeanseshould contain aLmost.
`one instance of the trap instruction to the operating system for each system call. Simple
`virusesa attaching» themselves to the beginning or end of a program, would carry along their
`own trap instructions.
`Infected programs would have duplication of such trap instructions
`for some system calls.
`
`to the
`9 A program containing a virus will contain calls to write the virus to storage, e.g.
`disk, operating system memory, or to uninfected files. Suspicious code, then, could cause the
`program to Write to files the program under investigation is not expected to write to. By
`enumerating all of the files a program can potentially open, the user of the program is alerted
`to potentially suspicious code before he runs the program.
`
`These two points form the basis of the two UNIX tools being presented here. The detector
`tool examines a program to determine if it contains any duplicate instances of Operating system
`services (such as file operations like read and write), while the fitter tool will examine a program
`to ascertain which files the program can write. These tools are promising because they can detect
`a large class of viruses and limit the propagation of others. Although these tools are limited by a
`number of factors, they form a firm foundation upon which more sophisticated tools may be built.
`To date, the detector tool has been implemented and tested on several programs with promis~
`ing results; we have determined that all but one of the UNIX utilities on our Sun-3 workstation
`running SunOS 3.4 have no duplicate trap instructions. Furthermore, the detector has detected a
`handcrafted virus that is typical of UNIX viruses. A prototype of the filter is under development,
`but it has been hand-simulated on several utility programs.
`a
`.
`*
`The remainder of this paper discusses the basic approach of the detector and the filter tool.
`The discussion includes the assumptions attendant to each tool as well as the implications of
`these assumptions. The implementation of the detector is discussed, giving details about problems
`and results of experiments performed with it. A discussion of a simple UNIX virus is also given
`to facilitate the understanding of the implementation. Next, the concepts behind the filter are
`explained in detail. The shortcomings of each tool are discussed and extensions of the tools are
`suggested. as Work for the future;
`-
`'
`
` virus scanners) cope only with known viruses or virus strains. Our approach attempts to identify
`
`2 The Detector
`
`2.1 Basic Approach I
`
`The purpose of the detector is to identify duplicate calls to operating system services; duplicated
`calls might. be in an executable program and be indicative of a virus that has linked itself to the
`program. The first step in the detector’s analysis is to disassemble a program into its equivalent
`,
`assembly language representation. The next step consists of finding all instances of code which
`perform some operating system servrce.
`If two different pieces of code are found to contain the
`
`351
`
`
`
`
`
`
`
`

`

`same operating system services, then this condition is‘flagged as a duplication of services. For most
`programs, it is reasonable (and necessary) to make the following assumptions:
`
`1. The program uses a standard interface for communicating with the operating systems ,
`{NJ . The program is geueratedCWith a compiler.
`
`3. The source program does not call the operating system directly thmugh a. trap,‘instead it
`'uses the operating system interface in the standard library.
`
`4. Virus code can only occur in the code (text) segment of a program.
`
`
`
`
`
`fizzymmwmmewmermaflfifife-5Vwe1
`
`wewwwmwmmmws
`
`
`
`Assumption one ensures that determination of duplication of services will be relative straight
`forward.
`If all programs use the same format for using system services, the detector can always
`determine what the service is. For instance, in most implementations of UNIX, system calls are
`performed by pushing the system call number onto the stack and then executing a trap to the oper»
`ating system If the system call numberis always pushed immediately before the trap is executed,
`the detector simply has to examine the instruction preceding the trap to determine which service
`is being used. If a program does not follow such a scheme but instead handles each system callin a
`different way, the detector must then symbolically execute the program to determine the contents of
`the stack at the time of the trap instruction—a more difficult and potentially intractable problem
`Fortunately, most versions of UNIX use a standard calling scheme Thus this assumption is only
`' restrictive for those programs which do not use the standard calling scheme, such as some programs
`writtenin assembly language
`The second and third assumption are necessary to ensure that a legflimate, umnfected program
`will not have any duplication of services. Executable programs linked with the standard library
`will have one routine which handles all requests for a given operating system service Any time
`the program needs a service it effects the appropriate preoarations, such as pushing the other
`information required for the call 1'eg arguments) onto the stack, and then calls the xoutine which
`performs the service This technique to handle system service call18 very common and not confined
`to UNIX
`'
`.
`
`For portability and upgrade compatibility reasons, a compiler does not generate code that
`interface with the operating system directly Instead, the compiler will treat a system service call
`as a subroutine provided by the standard library The actual operating system interface code, ie
`the system trap, resides1n the library subroutine. Thereforethe actual interface should appear at
`most once for each system Call111 any compiled program 3
`'
`, Finally, assumption £011r stems from a consideration of file formats and their related restrictions
`under UNIX Typically, UNIX uses three file formats for executable files: OMAGIC ZMAGIC,
`and NMAGIC. The first OMAGIC, is obsolete and rarely used In this format the text segment
`is non—sharable and not write protected so the data segment is immediately contiguous with the
`text segment. The second ZMAGIC is the default format produced by (d the link editor For
`this format, the text and data sizes must both be multiples of the page size since the pages of the
`file are brought into the running image as needed The third format1s similar to the second except
`the data and text segments are not required to be multiples of the page size; the entire image
`is preloaded into memory at run time Most versions of UNIX enforce segmentatiori of code and
`data, meaning that executable code and nonexecutable data must reside strictly111 their respective
`segments Furthermore the text segment15 hot writable during run time and execution of the data
`segment is not allowed As a. result of these restrictions a virus which infects a program most
`do so by placing all of its code into the text segment; it cannot hide any code in other yarts of
`3’ln order to defeat; the deter:tor, a virus would have to use the operatirig systein calls of theprogram 1t is attempting
`to infect, rather than trivially attaching itself to the beginning or end of the program Later, we discuss ways to
`catch attempts to defeat the detector
`
`352
`
`

`

`
`
`the file. NMAGIC and OMAGIC format files, therefore, are aeroew at more resident to Viruses
`
`than ZMAGIC format files since no unused spaco is availa‘ole ioe a
`. Eleanor, a virus may
`still be able to infect such files if it can somehow hide the increase lo a e eiee o: the host. program
`(perhaps ,. through a. flaw in the. operating system or by compressing the original code to obtain
`space).
`* MAGIC format files are-even more vulnerable. For instance, cinder 3:219:63 eat the page
`size iseight kilobytes, meaning the’average ZMAGIC formatvprogramwillhave approximately four
`kilobytes of zero—padded space in both its text, and data. sections. This space is large eaoogh to
`hold afairly complex Virus wri-tten‘in assembly language. However, in, all three cases,» che virus-
`code'must still appear in the text segment, making itdetectable by, the detector.
`lf all‘of these
`conditions are met, then thedetector can be used to determine if the program under consideration
`contains any duplication. of system calls.
`»
`.
`>
`
`2.2 .Implementation‘ah‘d Results f
`
`A prototype of the detector has been implemented on a Sun 3' workstation running SunOS 3.4.
`and has been tested on several of the standard programs from /bin, filer/bin, and /u3r/ocb, but
`its application is not limited to UNIX systems. This prototype, called Snitch, is written in the
`C and Icon programming languages and consists of two major modules: the disassembler and the
`analyzer. The first module, the disassembler, takes an executable program as input and produces
`the equivalent Motorola 68020 assembly language representation as output. The second module,
`the analyzer. takes the output from the disassembler and examines it for duplicated code.
`For 813.1103 3.4, a system call is performed by pushing the system call number onto the» stack
`and then executing a trap instruction. Because the call expects the top of the stack to contain the
`number of the call to he made, determination of duplication of services becomes straightforward;
`one only needs to backtrack from the point of the trap to determine the last item pushed on the
`stack; that item will he the system call number. Furthermore, most of the standard library routines
`push the syetem call number immediately before executing the trap, making the analysis. phase even.
`simpler. The anayzer reports anyduplications found as. well as the number of occurrences of all
`system calls.
`'
`. The results of the experiments performed on Snitch are as follows. Approximately one hundred
`programs (mostly UNIX utilities) were tested for duplication of services with some of them infected
`with a simple virus (described in Section 3.2). All of the infected programs were found to have
`duplicated system calls, while only one uninfected program was flagged as having dapllcation
`of services:
`/bin/csh contained two instances each of the ’getgid and getuid system cells. One
`may conjecture that such duplication occurred because of post—linking binary patching. Since the
`duplicated services were not of a serioue nature; for a program as large as the C~shell, such an
`occurrence should not be surprising or indicative of malicious coder
`‘
`
`2.3 A Simple Virus
`
`'For purposes of testing Soitch, a. simple virus was created which infects SunOS 3.4 executables.
`The virus is considered simple because it makes no effort to conceal itself and it does not use a
`sophisticated method forreplication and propagation, although it is capable of avoiding multiple
`infections of the same program. Basically, the'virus works ae follows: First, the virus determiaee
`whether it has previously infected the target program. Under $111108, executables have a standard
`header which contains format information, start-up code, a branch to the user’s code, and thee:
`:cleaneup code. The format information tells in which format (OMAGIC, ZMAGIC, or NMAGECE
`the file is arranged. The start-up code initializes environment variables and other constructs area
`the clean—up code restores the old environment and makes a smooth return to the shell. All of t
`'
`information is common to most executables and of a constant length. Therefore, the breach *5:
`the main body of code always occurs at a certain offset from the beginning of the text 3e»
`
`'
`
`353
`
`
`
`
`
`
`
`
`
`

`

`
`
`
`
`4M,.~,....W.,Wed«flog”wwwwnwrwcwH
`
`Furthermore, the user code always immediately follows the clean-up code, making the branch
`address the same for all programs. Thus, to determine previous infection, the virus simply examines
`the locatlon in the text segment where the branch instruction occurs (bytes 70-73) and determines if
`the address is the standard address (ZOAO hexadecimal). Ifit is, the virus commences the infection
`process.
`7 Next, the virus determines if it has enough space to infect the program Without overwriting
`any legitimate code or increasing the size of the program. The only format which allows any zero-
`padded space is the ZMAGIC format; if the file is not in ZMAGEC format the virus exits and passes
`control‘to the legitimate code. Ifthe file is in ZMAGEC format, the virus determines Whether there
`is zero-padded space at'the end of the text segment. This taskis accomplished by looking for
`zero~padded space of length N between the end of program and the end of the text segment, which
`is multiple of 8K bytes. N is the length of the virus code.
`'
`'
`Finally, assuming there is. enough room, the virus copies. itself from the host program into the
`target program by copying the last N bytes from the host program’s text segment. It then changes
`the branch instruction in the start~up code so that the virus code is executed after the start-up
`code and before the legitimate code. Five system calls are used by this virus (open, lseek, read,
`write, and close) and its length is approximately 150 bytes. A program infected with this virus is
`easily detected by the detector.
`
`2.4 Limitations of the Detector
`
`The most obvious way of defeating the detector is simply to make the infected program not have
`any duplication of actual interface to the operating system; if the virus uses the existing services
`it cannot be detected with the detector. Use of existing services would be simplified if the symbol
`table information was left in a. given program. In this case, a virus could determine the location
`of the needed services and hook into them, thereby adding only that code which was not already
`present in the host program. Even without thesymbol table, a virus could search the host program,
`looking for the services it requires. Then, it wbuld import only those services which it could not
`find.“ Also thevirus could escape detection by inserting a. dummy system call that is absent
`from the uninfected program, pushing the system call number onto the stack and jumping to the
`trap inStruction inserted. Such viruses would escape detection by the current detector, although
`it could be extended to identify code that searches 3. program for system cells. We are currently
`investigating these and other approaches to defeat the detector and to extend the detector to make
`it more robust.
`
`3 The Filter
`
`3.1 Basic Approach
`
`A virus filteris an automatic classifier which applies static analysis techniques to detect the presence
`of a. virus. Since computer‘viruses multiply by implanting themselves in healthy programs, a.
`necessary condition for propagation is their ability to modify executables. Our approach, although
`based on the technique of formal verification differs from classical verification, Verificationentails
`proving a. program with respect to a specification — a statement of what function the program is
`intended to compute. For the purpose of detecting suspicious code, we. are assumingno specification
`will be provided. Instead, programmed into the filter is a property to be determined of the program
`under- analysis. For the current version'of the filter, the property is “the files that the program
`could write to”. The basic approach is first to identify all open Calls in the program and then
`
`”This may not be as easy as it sounds. hoWevergsince the virus must then know where each of its constituent
`parts is located within its code as Well as how to extract them.
`'
`’
`‘
`
`354,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`
`
`to enumerate the possible fileneme arguments to these calls. As we demonstrate, the analysis is
`feasible as only a small fraction of a program is involved in generating filenarnes. Upon being
`presented with the names of files that the program could write, the user could determine if the
`program is suspicious. Of course, a virus could still be present, but its propagation would be
`severely limited -v essentially to just those files. Crochet and Pozzo (see [43) (hereafter abbreviated
`to Crocker) proposed a virus filter based on formal specification and verification techniques“ But
`throughthe following hypotheses, they conjecture that the analysis will be vastly simple than that
`usually associated with program verification.
`
`Hypothesis 1 It is possible to formulate restrictions for the maiority of useful programs such
`that the restrictionis syntactically simple enough to be machine processable and fine~grained
`enough to represent the full range of authorized modifications made by real progremflfliri ,,
`restriction isthe specification of the modifications 3. program makes It is created by a
`program developer wishing to submit an executable program for potential use
`Hypothesis 2 It15 possible, on the average to analyze benign programs in a straightforward way
`
`Hypothesis 3 it is possible to classify modifications such that ordinary changes can be distin—
`guished from suspicious ones.
`
`Generally, we agree with Crocker’s hypotheses, but argue that for some programs (benign or
`infected) the semantic analysis required. is more complicated than implied by these hypotheses.
`In UNIX systems,
`the propagation of a. virus through direct access to files is through the
`open, create rename, link and unlink system calls A virus may open and write to an executable
`or replace an executable by its viral counterpart Using symbolic evaluation techniques, it is
`sometimes possible to determine the arguments to these system calls and hence the names of
`files being modified The enumeration of the files which may be modified by the program being
`investigated provides clues to detecting viruses For example the program date does not write to
`any files (except standard output) If the enumerated list of files thefilter identifies fer date is not
`empty, it can be concluded that the date program is suspicious. The analysis of the benign date
`program is very straightforward. Much less straightforwardis the split program Split reads a
`file and writes it in ruline pieces to a setof output files The name of the first output file1s an
`argument specified111 the command line with “aa” appended, the. second one with “ab” appended
`and so on If no output file argument is given, “It”is used as default The program should only
`create files starting with the prefix speczfiedin the command line or the default prefix Therefore,
`we can say the split program is safe if the enumerated files sausfy this restriction
`
`In general, s program is said to besuspicious when
`
`1 The program ’8 acceptance criteriais not satmfied - there15 a high potential for a virus The
`acceptance criteria states that the enumerated set of filenamesis acceptable to the user
`
`2 The program is too complex to be evaluated by our filter. No defimtive answer is obtained
`from the filter so the program is not accepted In practice it would he the responsibility of
`the programmer to argue that a suspicious program is not contaminated
`
`Otherwise the program is said to be safe.
`After sampling some Commonlyusedprograms Crocker concluded that the patterns of fileneme
`generation could be classified as follows:
`-
`
`ImpliedwwThere1s a fixed possibly empty, list of files to be modified For example, date modifies
`no file vipw modifies wee/passed
`
`355_
`
`

`

`Parameters —- Filenames are passed to the program as command line arguments. For example,
`* indent indents and formats 3 C program specified in the command line.
`
`l
`
`
`
`Transformations — Some programs such as compilers and editors create new files based on the
`arguments in the {10111de line. For example, compress transforms f ilename to f ilename .2.
`
`Temporary files e Newfilenames aregenerated independently. . Forexample, yi generates temr
`porary files inthe/tmp directory.
`'
`‘
`.7 .
`1‘
`'
`.
`‘
`.
`
`Dialogs « The'filename is provided by the near when the program'is running. For example, ooh
`(a. standard UNIX Command interpreter)" file redirections are obtained from terminal input.
`
`In all of tlleee classifications, the algorithms used to generate file'names are quite simple involve
`a small fraction of the total program. Si‘nte most realistic programs are far too complex to be
`analyzed in their entirety and most of the code is unrelated to fileneme processing,» our approach is
`toisolate that part of the program concerned with filename generation and disregard the remaining
`part. The simplicity of the resulting reduced program should make the static analysis tractable.
`In summary, our filter tries to determine the names of all files which might be modified by the
`program. By comparing the enumeration of names and the specified restriction, the virus filter can
`claim the program is safe or is suspicious. The complexity of the programs in their entirety may
`prohibit comprehensive analysis, 30 part of our method eliminates that part of the program not
`related to filename processing. We call this method slicing. After slicing, the residual program. is
`usually small in size and, thus, anelyzable.
`'
`Ayirns in evprogram could escape detect-ion by the filter if it is content to contaminate only
`those files for which the program has legitimate access. For example, a. virus hiding in the EMACS
`editor’could infect a program beingvcreeted using the editor. HoWever, once infected this'ptogram
`could infect only those programs its designer has given itanccess to. Any code in-the original virus
`that would involve writes to [other files would be detected by the filter.
`
`13.2
`
`Implementation and Results
`
`This section ditcnsses the implementation of our approach. The ingot to the virus filter is a binary
`executable. The output is the enumerated set of the files that may be modified by this executable.
`Thevviruslfilter proceeds through sixsteps. The first five steps‘ are the preprocessings required
`to extract; the program fragments which contribute to filename generation. The last step involves
`symbolic execution and analysis. The sixcteps are as follows:"
`
`1. Translation to an intermediate language -
`
`-
`
`. Determination of basic block and life span
`
`2 3
`
`, Determinetion of data dependencies
`V 4. Anti—aliasing,
`5 Slicing
`
`I
`
`6 . Symbolic evalnation and analysis:
`
`' Given a, program to be analyzed, the virus filter first translates it into a. (Hike intermediate
`.
`language. Then the filter relabels variables in order to decouple semantically disjoint variables
`sharing the some storage. Next, the data. dependencies are found by analyzing the program syn-
`tactically. The filter performs anti—aliasing analysis to unify references to the some storage. Extra.
`
`356 I”
`
`
`
`,7.
`g,
`l
`l2
`
`,
`
`

`

`dependencies are added to the data dependency graph when aliased storage is found“ Based on the
`data. dependence graph, the program is. sliced into pieces, Finally, the pieces which are related to
`filename processing are extracted and symbolically. executed. The filter also applies some theorem
`proving techniques, primarily to derive inductive assertions for the few, if any, loops involved in
`filename enumeration.
`The folloWing simple example, written in our (Hike intermediate language, is used to illustrate
`the'different steps of the virus filter. This example program consists of two independent fragments
`of code which perform different operations although they share the same variables. It demonstrates
`our method of decoupling variables by relabeling. Then, we separate it into two independent
`program fragments by applying» slicing. After locating the appropriate fragment containing the
`system calls, we apply symbolic evaluation and analysis to determine the filenames.
`Example: We pick up this example after translation to an intermediate C-lilre language. 2: is a
`filename string, i is an integer,’str() is a function converting an integer to a string. Not shown .
`are the open system callshassumed to occur at any line in the program with filename argument X.
`
`
`
`intermediate code
`
`# string concatenation
`
`Line number
`1 = l
`1
`x = “f”
`2
`x = x {l strCJ.)
`3
`i = 1 + i
`4
`. if ,(i <:. 3) gotovline 3‘ .
`{5_
`print it
`'
`‘
`6 L
`V
`,
`.
`i 3200
`7
`' l V '
`
`
`
`x : strCi)
`8
`
`
`
`
`
`
`The filenames generated would be:
`,f
`if the open system call follows line 2
`> £1, £12, £123
`follows line 5
`\ £123
`_
`follows line 6 ’
`200
`follows line 8.
`
`'
`
`‘
`
`l
`
`3.2.1 Translation to Intermediate Language
`The input to the virus filter is assumed to be a machine compiled binary program, not an arbitrary
`assembly language program. in the first stage, the program is decompiled into a machine indepen«
`dent, C-like, intermediate language We have designed the intermediate language such that analysis
`attendant to stepsQ-(S is simplified. To be specific, the intermediate language contains at most one
`assignment per statement and control is transferred by the goto statement only. The decompiler
`recovers semantic information about variables which are lost during the compilation. The goal is
`to partition memory into regions such that each region is the storage for a simple or structured
`variable. All storage locations are made explicit and side effects are eliminated. Library calls,
`like string assignments (string copy) and integer to string conversions, are replaced with defined
`functions in the intermediate language. Thus the virus filter is more likely to produce intelligible
`output through reference to higher level functions.
`Since our filter is designed to work with binary executables, we need a decompiler to translate
`machine codes to the intermediate language lntuitively, the intermediate language should contain
`more information than the machine code, eg. concerning types and addresses of symbols. We
`
`
`
`
`
`35'?
`
`

`

`should be able to locate extra information concerned with the high-level language from sources
`such as the symbol table, Even if we cannotfind anything directly, we may still be able to deduce,
`data types, procedure entries, etc, from the style izi’whi'ch the compiler generates code.
`
`'
`
`32.2 Basic Block and Life Span Analysis
`
`Variables are often} recycled in muddy programs in order to save storage or simply as a matter of
`programmihg style. In many programs, variable i is a general purpose loop counter which is reused
`in different, unrelated‘parts of the program. This recycling adds deoendencies to the datafiow
`graph that can be eliminated. The elimination involves the renaming of the variables on the left
`hand side of an assignment statements.
`“
`‘
`After translating to the inter-mediate. language and rel‘abellng,the program is decompoeed into
`basic blocks for life syan analysis‘ A basic block is a sequence of instructions in which
`
`1. All control transfer statements are at the end of the block.
`
`2. Only the head of a basic block can he the target of any control transfer statements.
`
`The life span of a variable corresponding to an assignment is the span of validity of its value.
`The life of a variable starts on its assignment and yropagates to, basic blocks that the current block
`can lead to. We now pick up the example be derived as the filter starts in step 2. In line 4 of the
`following table, the value of i at the right handseidemay be derivedrfrom three possible sources
`because thereare 3 assignments to i (lines 1, 4, and 7) The purpose of life span analysis isto
`eliminate impossible combinations; Le. if? can never be the L4 of line 4;,
`
`Variables on the left hand side are relabeled uniquely by their name and line number. The
`program is broken into three basicblocks. The, live variables are given in the rightmost columns.
`
`
`
` Line number
`
`Intermediate code
`
`l
`Life of):
`
`
`I
`
`Life oil
` ‘oo-qcnmoo‘azor—x
`
`H H:
`
`
`[l str(i)
`*3:
`,
`i + 1 ..
`.
`A )4
`,< 3) 89m 11m '3
`'
`
`print X
`
`
`x3 =‘ aura)"-
`
`3.2.3 Finding Date. Dependeheies’
`
`Given the life span of the variables, thesyntactlc data deperldencies can. be determinedby datafiow
`analysis. Consider, for example, statement 3 in the example after step 2: “32.3 .2 x [I etr(i)’l. ffhe \
`variables x and i are referenced; 22.2 and x.3 are live when x is referenced; LI and L4 are live when
`i is referenced;.x.3 is Written to. Thus x.3 depends on M, 1.4, x2, and x3.
`Thus for step 3,_,the dependenciee are determined to be:
`
`358’
`
`
`
`
`
`

`

`
`
`/* x. 3 depends on x 2 */
`
`11.3 s» x 2.
`x.3 (—w x.3
`x.3 <—-— 1.1
`
`Ix.3 +— 1.4
`1.4 4—- 1.1
`1A +— 1.4:
`x.8 4w 1.7
`
`The objective of the date dependency analysisis to slice. the program into independent portions
`to simplify static analysis Since filenames are usually gener