`
`
`
`
`
`soparesreenemarmmmemenorm
`
`STATIC ANALYSIS VIRUS DETECTION TOOLS
`FOR UNIX SYSTEMS?
`
`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 UNIX environment. The tools
`would be used to detect infected programsprior 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 mostlikely 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 filter, uses static analysis to determineall of the files which a program is capable
`of writing to. By knowing whatfiles a program can and cannot write, one can decide whether or not
`that program is suspicious. The paper discusses the features and shortcomings of both tools and gives
`some implementation details related to the detection of UNIX 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. Thetools are also useful for detecting more general malicious code, such as. Trojan
`Horses.
`
`
`
`
`
`
`
`
`
`
`
`
`
`1
`
`Introduction
`
`Ideally, one 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 [7]) 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. However, these run-time methods potentially expose the system 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 executeif 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 or 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 comparison, or they require user interaction at runtime, or they
`require access protection mechanism absent from most operating systems. Other approaches (e.g.
`'Supported by grants from Lawrence Livermore National Laboratory,
`the State of California MICRO program,
`and Deloitte Touche, Inc.
`2 Currently at Amdahl Corporation, Sunnyvale,CA
`
`350
`
`CS-1019
`Cisco Systems, Inc. v. Finjan, Inc.
`
`
`
`eyereseremasee
`
`

`

`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:
`7
`* Source programsare linked with the standard library during compilation. In most systems,
`the operating system services, e.g. file open, file read, file write, are provided tothe user in
`the form of library functions. Hence a compiled and linkedprogramshould contain atmost.
`one instance of the trap instruction to the operating system for each system call. Simple
`viruses, 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
`® 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 filter 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.
`|
`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 wellas the implications of
`these assumptions. The implementation of the detectoris discussed, giving details about problems
`and results of experiments performed with it. A discussion of a simple UNIX virusis 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 |
`The purpose of the detectoris 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. Thefirst 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 service.
`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:
`
`4, Virus code can only occur in the code (text) segment of a program.
`
`1. The program uses a standard interface for communicating with the operating system, —
`2. The program is generated. with a compiler.
`|
`.
`3. The source program does not call the operating system directly through a trap, insteadit
`‘uses the operating system interface in the standard library.
`
`Assumption one ensures that determinationof 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 call in 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
`written in assembly language.
`The second and third assumption are necessary to ensure that a legitimate, uninfected 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 preparations, such as pushing the other
`information required for the call ((e.g. arguments) onto the stack, and then calls the routine which
`performs the service. This technique to handle systemservice call is verycommon and not confined
`to UNIX.
`For portability and upgrade compatibility reasons, a compiler does not. generate code that
`interface with the operating systemdirectly. Instead, the compiler will treat a system service call
`as a subroutine provided by the standard library. The actual operating system interface code,i.e.
`the system trap, resides in the library subroutine. Therefore,the actual interface should appear at
`most once. for each system ¢all in any compiled program. ?
`Finally, assumption four stemsfrom a consideration offile 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 ld, 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 formatis. similarto the secondexcept
`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 segmentation of code and
`data, meaning that executable code and non-executable data must residestrictly in their respective
`segments. Furthermore, the text segment is not 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 must
`do so by placing: all of its codeinto the text segment; it cannot hide any code in other parts of
`“In order to defeat the dotector, a virus would have.to use the opérating svatem.calls of theprograinit is.attempting
`to infect, rather than trivially attaching itselfto. 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 somewhat more resistant to viruses
`
`
`than ZMAGIC formatfiles since no unused space is available for a
`. However, a virus may
`
`still be able to infect such files if it can somehow hide the increase in the size of the host program
`(perhaps through a flaw in the operating system or by compressing the original code to obtain
`space). ZMAGIC format files are even more vulnerable. For instance, under SanO$ 4.0 the page
`size is eight kilobytes, meaning theaverage ZMAGIC formatprogram willhave approximately four
`kilobytes. of zero-padded space in both its text. and data sections. This space is large enangh to
`hold a-fairly complex virus writtenin assembly language.. However, in all three cases, the virus
`code must still appear in the text segment, making it detectable by. the detector.
`If all of these
`conditions are met, then the. detector can be used to determine if the program under consideration
`contains any duplicationof system calls.
`a
`
`2.2 . Implementation and Results -
`A prototype of the detector has been implemented on @ Sun 3 workstation running SunOS 3.4
`and has been tested on several of the standard programs from /bin, /usr/bin, and /usr/ucb, 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 SunOS 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 be 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 be the system call number. Furthermore, most of the standard library routines
`push the system call number immediately before executing the trap, making the analysis phase even
`simpler. The analyzer reports any duplications found as well. as the number of occurrences of all
`system calls.
`The results of the experiments performed on Snitch areas 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 duplication
`of services:
`/bin/csh contained two instances each of the getgid and getuid system calls. One
`may conjecture that such duplication occurred because of post-linking binary patching. Since the
`duplicated services were not of a serious nature; for a program as large as the C-shell, such an
`occurrence should not be surprising or indicativeof malicious code.
`
`2.3. A Simple Virus
`‘For purposesof testing Snitch, 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 a8 follows: First, the virus determines
`whether it has previously infected the target program. Under SunOS, executables have a standard
`header which contains format information, start-up code, a branch to the user’s code, and then
`“clean-up code. The format information tells in which format (OMAGIC, ZMAGIC, or NMAGIC)
`thefile is arranged. The start-up code initializes environment variables and other constructs while
`the clean-up code restores the old eavironment and makes a smoothreturn to the shell, All of this
`information is common to most executables and of a constant length. Therefore, the branch to
`the main body of code always occurs at a certain offset from the beginning of the text seg
`
`t
`
`353
`
`
`
`
`
`
`
`
`

`

`
`
`pacerenentemgeettitencneee
`
`Furthermore, the user code always immediately follows the clean-up code, making the branch
`address the samefor all programs. Thus, to determine previous infection, the virus simply examines
`the location in the text segment where the branch instruction occurs (bytes 70-73) and determinesif
`the address is the standard address (20A0 hexadecimal). If it is, the virus commences the infection
`process.
`_ Next, the virus determinesif 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 fileis not in ZMAGIC format the virus exits and passes
`controlto the legitimate code. Ifthefile isin ZMAGIC format, the virus determines whether there
`is zero-padded space at the end of the text segment. This task is 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 copiesitself from the host program into the
`target program by copying the last N bytes from the host program’s text segment. Tt then changes
`the branch instruction in the start-up code so that the virus codeis executed after the start-up
`code andbefore 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 nothave
`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 wasleft 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 would import only those services which it could not
`find.* Also the virus could escape detection by inserting a dummy system call that is absent
`from the uninfected program, pushing the system call numberonto the stack and jumping to the
`trap instruction inserted. Such viruses would escape detection by the current detector, although
`it could beextended to identify code that searches a program for system calls. 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 virusfilter is 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 propagationis their ability to modify executables. Our approach, although
`based on the technique of formal verification differs from classical verification. Verification entails
`proving a program with respect to a specification - a statement of what function the program is
`intended to compute. For the purpose of detectingsuspicious code, weare assumingno specification
`will be provided. Instead, programmed intothefilter is a property to be determined of the program
`under analysis. For the current. versionof the filter, the property is “the files that the program
`could write to”. The basic approachis first to identify all open ¢alls in the program and then
`4This may not be as easy as it sounds, however, since the virus inust. then know where each of its constituent
`parts is located within its code as well as how to extract them.
`:
`‘
`:
`
`354
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`feasible as only a small fraction of a program is involved in generating filenames. 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 - essentially to just those files. Crocker and Pozzo (see [4/) (hereafter abbreviated
`to Crocker) proposed a virus filter based on formal specification and verification techniques. But
`through the following hypotheses, they conjecture that the analysis will be vastly simple than that
`usually associated with program verification.
`
`Hypothesis 1 It-is possible tto formulate restrictions‘for the majority of nseful ‘programs such
`that the restriction is syntactically simple enough to be machine processable and fine-grained
`enough to represent the full range of authorized modifications made byreal programs.-A--—--
`restriction is-the specification of the modifications a programmakes,
`It is created by a
`program developer wishing to submitan executable program for potential use.
`Hypothesis 2 [tis“possible, on the average, to analyze benign programsin a straightforward way.
`Hypothesis 3 It is possible to classify modifications such that ordinary changes can be distin-
`guished from suspicious ones.
`
` -——--
`a
`
` to enumerate the possible filename arguments to these calls. As we demonstrate, the analysis is
`
`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 UNIXsystems, the propagation ofa virus through direct access to files is through the
`épen, create, rename, link and unlink system calls: Avirus 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 thefilteridentifies for dateis not
`empty, it.can be concludedthat the date program is suspicious. The analysis of the benign date
`program is very straightforward. Much less straightforward is the split program. Split reads a
`file and writes it in n-line pieces to a set.of output files. The name ofthe first output file is an
`argument specified in the command line with“aa” appended, the.second one with “ab” appended,
`and so on. If no output file argumentis given,“x*is used as default, The program should only
`create files starting with the prefix specified in the command line or thedefault prefix. Therefore,
`we can say the split program is safe if theenumerated files satisfy this restriction.
`In general, a program is said to be suspicious when
`
`1, The program’s acceptance criteria is not satisfied — there is a high potential for a virus. The
`acceptance criteria states that the enumerated set offilenames is acceptable to the user.
`2. The program is too complex to be evaluated by our filter. No definitive answer is obtained
`‘from the filter so the program is not accepted. In practice, it would be the responsibility of
`the programmer toarene that a suspicious program is not contaminated.
`Otherwise the program is said to be safe.
`After sampling some commonly-usedprograms, Crocker concluded that the patterns offilename
`generation could be classified aas follows:.
`Implied -~ Thereis a fixed, possibly empty,list of filesto be modified. For example,date modifies
`no file. vipw modifies / etc/passwd.
`
`355.
`
`.
`
`

`

`
`
`Parameters — Filenames are passed to the program as command line arguments. For example,
`~dndent indents and formats a C program specified in the commandline,
`Transformations — Some programs such as compilers and editors create new files based on the
`arguments in the command line. For example, compress transforms filename to filename. Z.
`Temporary files - New filenames are.generated independently. . For-example, vi generates tem-.
`porary files in the. /tmp directory,
`99° = cos
`.
`Dialogs - The. filename is provided by the user when the programis running. For example, csh
`(a standard UNIX command interpreter)file redirections are obtained from terminal input.
`
`In all of these classifications, the algorithms used to generate filenames are quite simple involve
`a small fraction of the total program. Since most realistic programs are far too complex to be
`analyzed in their entirety and most of the codeis unrelated to filename processing, our approach is
`to.isolate that part of the program concerned with filename generation and disregard the remaining
`part. The simplicity of the resulting reduced program should make thestatic analysis tractable.
`In summary, our filter tries to determine the namesofall 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, so part of our method eliminates that part of the program not
`related to filename processing, We call this methodslicing. After slicing, the residual program. is
`usually small in size and, thus, analyzable.
`,
`7
`a
`.
`A virus in a program could escape detection by thefilter 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'couldinfect a program being created using the editor. However, once infectedthis program
`could infect only those programsits designer has given it-access to. Any code in the original virus
`that. would involve writes to otherfiles would be detected by the filter.
`
`Implementation and Results
`3.2.
`This section discusses the implementation of our approach. The input to the virusfilter is a binary
`executable, The output is the enumerated set of the files that may be modified by this executable.
`The virus filter proceeds through six steps. The fitst five steps are the preprocessings required
`to extract the program fragments whichcontribute to filename generation. The last step involves
`symbolic execution and analysis. The six steps are as follows:
`
` ibb
`
`ifii
`
`1. Translation to an intermediate language
`. Determination of basic block and life span
`
`, Determination of data dependencies
`
`Oo.kwwoN~. Symbolic evaluation and analysis.
`
`. Anti-aliasing
`
`. Slicing
`
`"Given a program to be analyzed, the virusfilter first translates it into a C-like intermediate
`language. Then the filter relabels variables in order to decouple semantically disjoint variables
`sharing the same storage. Next, the data dependencies are found by analyzing the program syn-
`tactically. The filter performs anti-aliasing analysis to unify references to the same storage. Extra
`
`356
`
`

`

`filename enumeration.
`
`dependencies are added to the data dependency graph when aliased storage is found. Based on the
`data dependence graph, the program issliced 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
`The following simple example, writtenin our C-like 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 ofdecoupling variables by relabeling. Then, we separate it into two independent
`program fragments by applyingslicing. 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-like language. x is a
`filename string, i is an integer, str() is a function converting an integer to a string. Not shown .
`are the. open system calls,assumed to occur at any line in the program with filename argument X.
`
` Tine number
`1
`ieil
`2
`x = “ff?
`# string concatenation
`3
`x = x || strG)
`4
`A= i+i
`5o
`if (i <= 3) goto line 3°.
`6
`print x
`an
`7
`i = 200
`
`x = str(i)8 |
`
`
`intermediate code
`
`
`
`The filenames generated would be:
`f
`if the open system call follows line 2
`“fi, f12, fi2s
`follows line 5
`_£123
`follows line 6»
`200
`.
`,
`follows line 8.
`
`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 decompiledinto a machine indepen-
`dent, C-like, intermediatelanguage. We have designed the intermediate language such that analysis
`attendant to steps.2-6 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 vatiables 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 throughreference 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. Intuitively, the intermediate language should contain
`more information than the machine code, e.g. concerning types and addresses of symbols. We
`
`
`
`
`
`357
`
`

`

`should be able to locate extra information concerned with the high-level language from sources
`such as the symbol table. Even if we cannot find anything directly, we maystill be able to deduce ™
`data types, procedure entries, etc, from the style in which the compiler generates code.
`
`3.2.2 Basic Block and Life Span Analysis
`
`Variables are often recycled in many programsin order to save storage or simply as a matter of
`programming style. In many programs, variable i is a general purpose loop counter whichis reused
`in different, unrelated parts of the program. This recycling adds dependencies to the dataflow
`graph that can be eliminated. The elimination involves the renaming of the variables on theleft
`hand side of an assignment statements.
`__
`.
`After translating to the intermediatelanguage and relabeling, the program is decomposed into
`basic blocks for life span 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 be 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. propagates tobasic 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 hand: side may be derived from three possible sources
`because there are 3 assignments to i (lines 1, 4, and.7). The purpose oflife span analysis is to
`eliminate impossible combinations, i.e. i.7 can never be the i.4 of line 4.
`Variables on the left hand side are relabeled uniquely by their name and line number. The
`program-is broken into three basic blocks. Thelive variables are given in the rightmost columns.
`
`
`Life of
`Lite ofx - Intermediate code
`Line number
`
`
`=
`ry
`x.2 5 S°F??
`2
`
`
`3
`=x | str(i)
`.
`4
`i4ei¢i.
`
`if (i.< 3) goto line 3
`5
`
`6
`print x
`
`7
`1.7 = 200
`
`8 x.8 = str(i) ©
`
`3.2.3 Finding Data Dependencies
`Given the life span of the variables, the syntactic data dependencies canbe determinedby dataflow
`analysis. Consider, for example, statement 3 in the example after step 2: “x.3 = x || str(i)”. The -
`variables x and i are referenced; x.2 and x.3 are live when x is referenced; i.1 and i.4 arelive when
`i is referenced; x.3 is written to. Thus x.3 depends on i.1, 1.4, x.2, and x.3.
`Thus for step 3, the dependencies are determined to be:
`
`358
`
`
`
`
`
`

`

`
`
`3.2.5-Slicing
`
`/* x.3 depends on x.2 */
`
`x.3 «+ x.2,
`x.3 — x.3
`x.3 e+ i.l
`K.3 + 1.4
`i.4 = i.l
`1.4 — 1.4
`x.8 — 1.7
`
`The objective of the data dependencyanalysisis to slice theprogram into independent portions
`to simplify static analysis. Since filenames are usually generated by simple algorithms, syntactic
`dependencies are considered instead of semantic (real) dependencies. -This simplified-analysis-is
`adequatefor the worst case dependencies. In the above example, we can recursively trace back and
`find