UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Software tools for untangling safety-critical source code Feng, Feng 2005

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2005-0438.pdf [ 5.12MB ]
Metadata
JSON: 831-1.0092175.json
JSON-LD: 831-1.0092175-ld.json
RDF/XML (Pretty): 831-1.0092175-rdf.xml
RDF/JSON: 831-1.0092175-rdf.json
Turtle: 831-1.0092175-turtle.txt
N-Triples: 831-1.0092175-rdf-ntriples.txt
Original Record: 831-1.0092175-source.json
Full Text
831-1.0092175-fulltext.txt
Citation
831-1.0092175.ris

Full Text

SOFTWARE TOOLS FOR UNTANGLING SAFETY-CRITICAL SOURCE CODE by FENG FENG B.ENG, Southeast University of China, 1996 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF THE REQUIREMENTS FOR THE DEGREE OF . Master of Applied Science in THE F A C U L T Y OF G R A D U A T E STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH C O L U M B I A OCTOBER 2005 ©Feng Feng, 2005 ABSTRACT Software Safety is an emerging discipline that focuses on the use of software to mitigate the risks of mishaps occurring, especially for software-intensive systems. Research on Software Safety methodology has largely focused on "front-end" of the whole safety process such as the specification of safety requirements. Aside from work on highly specialized techniques such as software fault injection, relatively little attention have been given by researchers to the "back-end" of verifying the safety of software implementation. One of the biggest difficulties of safety verification for software implementation is that safety-related source code often cross-cuts the modular structure of the software system. A recent doctoral dissertation by Ken Wong at the University of British Columbia identifies several possible methods that could be used to extract these safety-related code fragments from many components of software system. In this dissertation, we extend Wong's research, with an emphasis on using techniques and tools originally developed for other purposes such as the re-engineering of software systems. In particular, we focus on AOP (Aspect Oriented Programming) and Program Slicing. Aside from evaluating these techniques and tools to untangle software source code, we provide the design and implementation of our own slicing tool, which combines the advantages of both static and dynamic source code analysis to implement a hybrid approach. As a case study for our investigation, we have designed and implemented a model of a safety-critical software system that processes air traffic control radar surveillance data, which exhibits several cross-cutting safety concerns. We use this case study to investigate how various techniques and tools may be used to extract a representation of a cross-cutting safety concern from source code. 11 TABLE OF CONTENTS ABSTRACT II TABLE OF CONTENTS III LIST OF FIGURES VI ACRONYMS VII 1. INTRODUCTION 1 1.1 Thesis Statement 1 1.2 Related Work 4 1.2.1 Static Code Analysis 4 1.2.2 Dynamic Code Analysis 7 1.2.3 Program Slicing 8 1.2.4 AOP 8 1.2.5 Code Instrumentation 9 1.3 Case Studies 10 1.4 Contributions of this Dissertation 11 1.5 Overview of Dissertation 11 2. BACKGROUND 13 2.1 System & Software Safety 13 2.2 Software Safety Concerns 16 2.2.1 Software Safety Concern in the Source Code 17 2.2.2 Software Safety Concern Models 17 2.3 Separating Safety Concerns 19 2.3.1 Hyperspace 20 2.3.2 Concern Graph Approach 21 2.3.3 Aspect Oriented Programming 22 2.3.4 Program Slicing 23 2.4 Summary 24 3. ASPECT ORIENTED PROGRAMMING 25 3.1 Introduction 25 3.1.1 Spring 28 3.1.2 AspectWerkz 29 i i i 3.1.3 AspectJ 29 3.2 Safety Concern as Aspect 30 3.3 Summary 33 4. PROGRAM SLICING 35 4.1 Slicing Introduction 35 4.1.1 Static Slicing 36 4.1.2 Dynamic Slicing 37 4.1.3 Hybrid Slicing 39 4.2 Evaluation of Existing Slicing Tools 40 4.2.1 Spyder 40 4.2.2 Unravel 41 4.2.3 CodeSurfer 42 4.2.4 Java Slicing Tools 43 4.3 Summary 46 5. SLICER DESIGN AND IMPLEMENTATION 47 5.1 Dynamic Analysis of Java Program 48 5.2 Soot Introduction 51 5.3 Call Graph Construction 53 5.4 Slicing Algorithm 54 5.5 Summary 62 6. RDPS EXAMPLE 63 6.1 RDPS Introduction 63 6.2 Approaches to Separate Safety Concerns 67 6.2.1 Text Search 67 6.2.2 AOP 68 6.2.3 Program Slicing 70 6.3 Summary 73 7. SUMMARY AND FUTURE WORK 74 7.1 Summary of the Contribution of the Dissertation 74 7.1.1 Using AOP to separate safety concern 75 7.1.2 Demonstration of the use of SOOT for Program Slicing applied on safety analysis. 76 7.1.3 Combining static and dynamic analysis of system safety code 77 7.2 Future Work 77 iv 7.2.1 Improvement of the slicing tool 77 7.2.2 Improvement on the program model of "concern graph" 78 7.2.3 Software visualization tools 78 7.3 Conclusion 78 BIBLIOGRAPHY 80 APPENDIX A SLICING TOOL SOURCE CODE 87 APPENDIX B RDPS SOURCE CODE 105 v LIST OF FIGURES Figure 2.1 Safety Risk Management 14 Figure 2.2 Cost vs Safety Effort (Seeking Balance) 15 Figure 3.1 Concern decomposition 26 Figure 3.2 "Log" Function Code Snippet 1 26 Figure 3.3 Log" Function Code Snippet 2 27 Figure 3.4 "Log" Function Aspect Pseudo Code 27 Figure 3.5 Spring PointCut Definition 29 Figure 3.6 AspectJ Pointcut Types 30 Figure 3.7 DataProcessor.java Code Snippet 31 Figure 3.8 AnotherDataProcessor.java Code Snippet 32 Figure 3.9 "Process" Aspect 32 Figure 3.10 DataProcessor.java Refactored Code Snippet 32 Figure 3.11 "Process" Refactored Aspect 33 Figure 5.1 Java class code execution model 48 Figure 5.2 Java Source Code Snippet 52 Figure 5.3 Java Bytecode Snippet 52 Figure 5.4 Corresponding Jimple Code 52 Figure 5.5 Example Program and call graphs 53 Figure 5.6 Slicing Work Flow 54 Figure 5.7 Hello Java 57 Figure 5.8 Corresponding Jimple Code 57 Figure 5.9 Jimple Code Static Slicing Result 58 Figure 5.10 Java Code Slicing Result 5 8 Figure 5.11 Hello.java Code Snippet 59 Figure 5.12 Hello.jimple Code Snippet 60 Figure 5.13 Instrumented Jimple Code Snippet 61 Figure 5.14 Java Code Snippet For Instrumentation 61 Figure 5.15 Java Code Snippet For Instrumentation 62 Figure 6.1 Radar Data Processor Class Diagram 64 Figure 6.2 Sequence Diagram Showing Steady State Behaviour 65 Figure 6.3 RDPS Code Snippet 68 Figure 6.4 RDPS Aspect Code Snippet 69 Figure 6.5 call graph Portion Related to Slicing Input 71 Figure 6.6 RDPS Jimple Code Slice Snippet 72 Figure 6.7 RDPS Java Code Slice Resul 72 vi ACRONYMS AOP Aspect Oriented Programming AST Abstract Syntax Tree A T C Air Traffic Control B C E L Byte Code Engineering Library CFG Control Flow Graph CGLIB Code Generation Library COTS Commercial Off The Shelf DDG Dynamic Dependence Graph DODG Dynamic Object-oriented Dependence Graph DPDG Dynamic Program Dependence Graph EJB Enterprise Java Bean F A A Federal Aviation Administration FEAT Feature Exploration and Analysis Tool GUI Graphic User Interface JPDA Java Platform Debugger Architecture JRE Java Runtime Environment J V M Java Virtual Machine MOOSE Montreal Object Oriented Slicing Environment OO Object Oriented PDG Program Dependence Graph RDPS Radar Data Processing System SDG System Dependence Graph SFTA Software Fault Tree Analysis vii 1. INTRODUCTION A recent doctoral dissertation by Wong [Won05] considers the problem of untangling source code in safety-critical systems. Wong argued that software safety verification should not only be limited at the specification and design level, e.g., requirement analysis and verification, but also be expanded to the implementation level, i.e., the source code. Because software source code contains many safety-unrelated details, Wong proposed a method to build a safety concern model by extracting information from source code. Although Wong's dissertation suggests that software tools might be used in the process of constructing a safety concern model, it does not investigate this possibility in much depth. Specifically, it does not provide a direct answer of how to extract and represent software concern from the source code. Wong pointed out several possible methods such as Program Slicing and the "concern graph" approach may be used to solve this problem [Won05]. Prompted by Wong's ideas, we have investigated the possibility to untangle the safety-critical code from the software implementation using several different methods such as Aspect Oriented Programming (AOP) and Program Slicing. In particular, we designed a slicing tool which can be used to extract the portion of safety-critical code from the whole software system. As part of our investigation, we have applied these methods to example systems including a simplified implementation of a software system to process Air Traffic Control (ATC) radar inputs. 1.1 Thesis Statement The thesis statement of this dissertation is as follows: 1 Software safety concerns often involve fragment of source code that crosscut the modular structure of the software system. This "cross-cutting" feature makes software verification very difficult, especially with the increased size of complexity of modern software system. Software tools should be used to untangle the safety-critical code to verify the safety of source code. A recent doctoral dissertation by Ken Wong at the University of British Columbia identifies several possible methods that could be used to extract representations of cross-cutting safety concerns from source code. We investigated several possible techniques including Aspect Oriented Programming and Program Slicing which can be used to achieve this goal. Our investigation casts some doubt on the use of Aspect Oriented Programming as a means of isolating cross-cutting safety concerns. At the same time, the results of our investigation suggest that Program Slicing is worth more investigation as a means of carrying out the methodology proposed by Wong in his dissertation. Software safety, according to Leverson, involves ensuring that the software will execute within a system context without resulting unacceptable risk [Lev86]. It becomes important when computers are used to control real-time, safety-critical processes [Lev86]. With the large-scale application of computer systems, system safety experts often find themselves facing such software-safety-related issues. For non-software-intensive systems, system safety experts often perform analysis by separating "safety concern" from the rest of the system. The term "safety concern" may be defined as a hypothesis about a specific combination of internal or external events that might lead to an occurrence of a hazard [Won05]. In this sense, "software safety concern" is a "safety concern" that involves software functionality. Isolating safety-critical functions is not always possible in modern software systems, especially in large software-intensive systems where the safety-critical functionality is interleaved with core system functionality [Won05]. Accordingly, safety engineers should also focus on extracting these "safety concerns" from the source code, i.e., 2 representing the software concern at the source code level, instead of "keeping safety-critical software as small and simple as possible" [Pvp90]. To thoroughly analyze a software safety concern, it is usually necessary to examine the relevant source code. As Wong [Won05] explains, the relevant source code may not conveniently be isolated in a single module of the software architecture. Instead, the relevant source code may consist of fragments scattered across the software architecture. We use the term "cross-cutting safety concern" to refer to the situation where the relevant source code for a software safety concern consists of fragments scattered across the software architecture. In general, whenever two properties being programmed must compose differently and yet be coordinated, we say that they cross-cut each other. [Kic97]. There are many approaches and techniques used to minimize safety risk associated with software. This includes: (1) hazard analysis, (2) safety requirements specification and analysis, (3) designing for safety, (4) testing, (5) certification and standards [LutOO]. On the other hand, we still lack the means to verify the software safety of the software implementation, i.e., the source code. Although "front-end" analysis such as the safety requirements analysis is crucial for the system safety, the verification of the software implementation is also very important because it can evaluate if the software-related hazards are finally mitigated. However, there is little emphasis is put on this research area. Currently, there are a variety of methods and techniques proposed to address the cross-cutting concerns such as Aspect Oriented Programming (AOP) [Kic97], program slices [Wei84], software visualization tools [Sfm97], and the "concern graph" approach [Rob02]. However, some approaches do not include modelling existing concerns in the source code, but only extracting cross-cutting concerns during the design phase of software development. In this dissertation, we mainly focus on the possibility of using methods such as AOP and Program Slicing to separate the concerns at the source code level. 3 AOP [Kic97] was proposed to support the programmer in cleanly separating components and aspects from each other, by providing mechanisms that make it possible to extract and compose them to produce the overall system. It has been informally suggested within the AOP community that AOP may serve as an effective means of isolating safety concerns [Kic03]. The research described in this dissertation has investigated this possibility. Program Slicing is a technique for simplifying programs by focusing on selected aspects of semantics. Basically, slicing algorithms can be mainly put into two groups: dynamic or static. In this dissertation, we will describe an approach that combines the dynamic and static methods of slicing. This combination offers the advantage of improved performance and precision by which we can effectively prune source code unrelated to the safety concern of our interest. We can finally extract "safety-related slice" from the implementation by means of this approach. 1.2 Related Work This section provides a brief introduction of the existing techniques which can be used for safety verification in software implementation. 1.2.1 Static Code Analysis Static analysis techniques have mainly been applied to source code although it is possible to analyze other products such as specifications, designs and fault trees. For example, Software Fault Tree Analysis (SFTA) was proposed by Leveson [LCS91] for software safety analysis. However, the analysis of source code is the also very important for safety analysis because source code is ultimately what determines the behavior of the system. 4 Static code analysis can be applied to interface, call graph, control flow, data flow, and data structure. Static analysis for safety verification includes data flow analysis and control flow analysis. Control Flow Analysis A control flow graph is a graphical representation of the algorithmic structure of a module. That is, it depicts the flow of control from the entry point to the exit point of the module [Mig04]. The purpose of control flow analysis (flow charting) is to reconstruct and examine the logic of the code. Constructing flow charts is one of the first analytical activities that the analyst can perform as it enables the analyst to become familiar with the code and its design architecture. The drawback to flowcharting is that it is generally costly and time consuming. A better approach is to use the team concept and have the safety engineers interface directly with the software developers and system engineers in order to understand system processing. In some cases, the software developers or system engineers already have control flow charts which, in turn, can be made available for review by the safety engineer as needed. Each case needs to be evaluated to determine which process would be more beneficial and cost effective to the program. In either case, flow-charting should be done at a conceptual level. Each block of the flow chart should describe a single activity (either single line of code or several lines of code) in a high-level verbal manner, as opposed to simply repeating each line of code verbatim. Applying control flow analysis to safety verification prevents the hazard risk incurred by the logic of the system. Hence, it can only provide a limited assurance for the software safety. 5 Call Graph A call graph is a diagram that identifies the modules in a system or computer program and shows which modules call one another [ISPE]. It can be used to eliminate unreachable functions, or to replace dynamic methods by directly static methods. Hence, it is very useful for software optimization and understanding. A call graph can also be used for safety verification. It gives an intuitive view of the whole system which can be used to verify the correctness of the system "logic". Data Flow The purpose of data flow analysis is to identify errors in the use of data that is accessed by multiple routines. Except for a very small application, it would be extremely difficult to determine the data flow path for every data item. Therefore, it is essential to differentiate between those data items that will affect or control the safety-critical functions of a system from those that will not. Data is generally passed globally or locally between software modules. Parameter passing (locally) is much easier to analyze, since the program explicitly declares which routines are passing data. Data globally passed should also be traced, but further information will often have to be recorded to understand which subroutines are involved. A table should be constructed to record the data flowing through the components of the whole system and the data passing through the layers of parameters. A l l safety-critical variables should be included in this table. We can identify the potential safety-related data errors by finding data which is not correctly initialized, conditions which is not suitable for data manipulation, unintended data modification, etc. 6 1.2.2 Dynamic Code Analysis Dynamic analysis is the analysis of the properties of a running program over one or more execution cycles. It can be seen as a complimentary method of static analysis. In contrast to static analysis, which examines a program's text to derive properties that hold for all executions, dynamic analysis derives properties that hold for one or more executions by examination of the running program (usually through program instrumentation). While dynamic analysis cannot prove that a program satisfies a particular property, it can detect violations of properties as well as provide useful information to programmers about the behaviour of their programs [Bel99]. There are some disadvantages about dynamic analysis compared to static analysis. Dynamic analysis usually needs to "instrument" the code which incurs extra system resource and possibly decreases the performance. And just as stated above, dynamic analysis can not prove the system safety and can only cover limited code paths. Hence, its result can not generalize to further executions. Combining static and dynamic code analysis can enhance each other by providing information that would otherwise be impossible. The results from both analyses are in different system context and are complementary for each other. The potential benefits of this combination are clearly articulated by Ernst [Ern03]: Static analysis is conservative and sound: the results may be weaker than desirable, but they are guaranteed to generalize to future executions. Dynamic analysis is efficient and precise: it does not require costly analyses, though it does require selection of test suites, and it gives highly detailed results regarding those test suites. In this dissertation, we will show how static and dynamic analyses may be combined in practice to achieve these potential benefits. 7 1.2.3 Program Slicing Program Slicing was introduced by Mark Weiser [Wei82], which can be used for abstracting programs. It is useful for software testing, debugging, understanding, maintenance. Informally, Program Slicing tries to answer such question: "Which statements in this program affect the value of variable v at statement si" A l l those statements that affect the variable v are called "program slices". The original definition of "program slice" by Weiser[Wei82], which requires the slice to be static, executable and backward, is now supplied with the new meanings that a program slice can be dynamic, non-executable and forward. Although programming slicing was proposed more than twenty years ago, there are not many mature slicing tools for practical use. Most of these tools are tools designed for experimental purpose [Hof95]. In particular, there are fewer tools for object-oriented languages such as Java and C++ [Won05]. Applying Program Slicing for safety analysis has been suggested by Gallagher [GL93]. It can be used to identify the possible safety hazards related to our specific safety concern. This approach can be used to find the safety-critical code paths. Safety-critical code paths provide the answer for the similar question as above, i.e., "Which are the factors possibly result in the hazard variable v at statement si" Gallagher also proposed applying dynamic analysis for safety analysis. This dissertation will investigate this proposal in more details. 1.2.4 AOP As stated above, Aspect Oriented Programming (AOP) was proposed in 1997 [Kic97] to solve the cross-cutting concerns which are shown in object oriented software and not easily resolved by current OO techniques. Such cross-cutting code may include security checking, transaction management and logging. These codes are distributed in different system functionalities and hard to be cleanly separated from the other parts of the system. 8 Similarly, safety related issues crosscut the software system. It will be desirable if we can encapsulate the safety concern in "aspects" and we can deal with the well defined aspects instead of the separated, cross-cutting safety functions. However, this approach is not perfect due to the essential difference between "safety concerns" and other "common concerns" such as logging, security and system-wide error-handling. This difference will be illustrated in detail in Chapter 3. Additionally, the "granularity" of current AOP implementations limits its application to separate safety concern. The term "granularity" represents the basic unit of source code we can manipulate. For example, the "granularity" of AspectJ is at function (method) or property level while the granularity of safety concern is at the source code "statement" level, i.e., the minimum unit which AOP can manipulate is "method" or "property", not the detailed "statements". 1.2.5 Code Instrumentation Our approach to Program Slicing heavily depends on the code instrumentation to get the dynamic information paths. Code instrumentation can be used to modify the existing software code to observe or modify its behaviour. It has a variety of different applications, such as coverage analysis and performance analysis. The instrumentation code can intervene in any existing code at any execution point and it can record the system state including the control flow, call graph. Our slicing tool for Java code is based on SOOT, an optimization framework of Java. This framework is implemented in Java and supports three intermediate representations: Baf, Jimple and Grimp. Baf is transformed from class code (.class) for simple manipulation. Grimp is suitable for decompilation. Jimple, which is the main data representation we will deal with, is suitable for optimization. SOOT also provides a variety APIs for program optimization, system analysis, profiling. 9 We use SOOT as the framework for code instrumentation. Through SOOT, we can record all the statements which are actually executed at run time. We can also build the actual control flow graph combining the static analysis of the source code. Another ideal property of SOOT is that it can not only "instrument" the source code but also the class code (in .class form). This is extremely useful since large software systems usually employ a lot of COTS (Commercial Off The Shelf) software in which case the source code may not be available. 1.3 Case Studies We have implemented a "toy" model of a radar data processing system (RDPS), which transforms the incoming radar data into a set of tracks that can be displayed by an air traffic management system (ATM). There are four main modules in the system: "Radar", "Correlator", "Track", and "Datablock". The "Radar" corresponds to a physical radar facility. It is responsible for receiving the radar data and transferring it to "Correlator" for further processing. The "Correlator" module is responsible to match the newly incoming radar data. It either initiates a new "Track" or updates an existing "Track". The "Track" corresponds to each track of an aircraft. The "Datablock" module is responsible for transforming the geographic information into a display location. The safety concern, such as incorrect display of altitude, cross-cuts the whole system. And it may cause serious results such as aircraft crash. It is a tiresome and boring task if we use text searching techniques like "grep" to find all the possible variables which could affect the display. Using the slicing tool we developed can easily locate all related statements. There are also other simple examples in this dissertation. These examples are mainly for explanation purpose. 10 1.4 Contributions of this Dissertation The following summarizes the contributions of this dissertation: • An in-depth analysis of using AOP to isolate the cross-cutting safety related concern. • Demonstration the use of SOOT for Program Slicing applied on software safety analysis. • Combining static and dynamic analysis of system safety to get more useful information than what can be obtained by an approach which is just static or just dynamic. 1.5 Overview of Dissertation Chapter 2 presents the background material that provides context for processing safety concerns such as software safety testing. Chapter 3 introduces the AOP notion and how we try to use it to address the problem of cross-cutting safety concerns. In particular, we give an example to demonstrate why AOP is not suitable to abstract the safety concern from source code. Chapter 4 elaborates the concept of code slicing, including static and dynamic slicing. It also lists the common slicing tools in the market and the effort we try to use these tools to address the safety concerns. Chapter 5 describes the design and implementation of our slicing tool. 11 Chapter 6 demonstrates the RDPS (Radar Data Processing System) example. It gives the details on how we use our tool to address the specific safety concern. Chapter 7 summarizes this dissertation and provides an overview of potential future research and some concluding thoughts. 12 2. BACKGROUND With the large-scale deployment of modern software system, especially OO software, it is more and more difficult to isolate the safety-critical function from other software modules. These safety related functionalities often spread across the whole system and become cross-cutting "safety concerns", as we stated in the introduction. There has been some research to address such concerns such as safety testing and fault tree analysis. This chapter will present background material that provides additional context for safety concerns and the techniques used to deal with these concerns. The fundamentals of system and software safety will also be presented, followed by the elaboration of safety concern. We will address different approaches including AOP and code slicing, which are used to separate safety concerns. 2.1 System & Software Safety Different institutions have different definitions of "system safety". According to [SSHOO], the definition of "system safety" is described as "a specialty within system engineering that supports program risk management. It is the application of engineering and management principles, criteria and techniques to optimize safety. The goal of System Safety is to optimize safety by the identification of safety related risks, eliminating or controlling them by design and/or procedures, based on acceptable system safety precedence". F A A ' s system safety handbook establishes a five-step approach to safety risk management as: Planning, Hazard Identification, Analysis, Assessment, and Decision [SSHOO]. Wong also mentioned five similar safety tasks: Hazard Identification, Hazard Analysis, Risk Assessment, Risk Mitigation and Safety Verification [Won05]. To summarize their approaches, we think a six-step approach would be more appropriate, i.e., 13 "Safety Verification" should also be included in the risk management process besides the other five tasks in [SSHOO]. Safety risk management focuses on the safety engineering process which provides techniques and methods to identify prioritize and eliminate the hazards. It should be involved in the whole system life cycle including design, development, activation and verification. Safety Planning Safety Verification Figure 2.1 Safety Risk Management In the planning stage, the safety engineer should evaluate every factor which possibly affects the system safety including equipment, facilities, procedures and personnel. The planning effort is integrated and continuing throughout all the system phases. It should include not only the resources including hardware and software but also all system processes. However, a successful safety planning should also take other factors such as performance and budget into consider. According to [SSHOO], system safety program balance is the product of the interplay between system safety and the other three familiar program elements of cost, schedule, and performance as shown in Figure 2.2[SSHOO]. The "SEEK" point represents a perfect balance between cost and safety efforts. 14 Cost - $ Safety effort • Figure 2.2 Cost vs Safety Effort (Seeking Balance) The stages of Hazard Identification, Hazard Analysis and Hazard Assessment are closely related to each other. The safety engineer should categorize and identity the system hazards. Based on the result of Hazard Identification, Hazard Analysis is performed. Both the hazard severity and the likelihood of occurrence must be evaluated. The more severe the consequences of an accident, the lower the probability of its occurrence must be for the risk to be acceptable. And as we stated above, safety engineers should also take the other factors such as costs of implementing hazard control. During the hazard analysis, safety engineers apply techniques such as Fault Tree Analysis. Based on the results of analysis and assessment, safety engineers mitigate the hazard accordingly. In the last, safety engineers need to verify the whole system safety, i.e., the hazard been mitigated adequately. Software safety is understood within the context of system safety. Moreover, software can be considered as another component in the system safety. Similarly, safety tasks such 15 as hazard analysis are performed on software safety. Accordingly, the analysis techniques such as Fault Tree Analysis can also be extended to the software safety area. There are some fundamental differences between the software systems and other systems due to the nature of software. As in [Pvp90], such differences are complexity, error sensitivity, correlated failures and hard to test. It is worth noting that the characteristic of hard-to-test is due to the discrete nature of software. Engineers can get the testing results by testing two close function points. This assumption does not hold because software does not have "obvious" function points. They are discrete and spread over the whole system. A l l these factors bring the difficulties not only to safety analysis but also for safety verification, especially for safety verification of source code. According to [WJ98], the term "safety verification case" was introduced to refer to a document that records the safety verification of the source code. The safety verification case is intended to ensure the inspectability, maintainability and repeatability of the safety verification of the source code. The use of this term is intended to emphasis the contributory relationship of the document to the overall system safety [Won05]. The inputs of the safety verification case development process are a large amount of source code and a set of identified hazards. The output of the process is the safety verification case with detailed evidence that provides a rigorous argument that the hazard cannot occur given specific, explicitly stated assumptions about the hardware and software [Won05]. As we stated before, this process is extremely difficult due to the cross-cutting nature of software safety concerns. 2.2 Software Safety Concerns As stated in Chapter 1, "safety concern" is a hypothesis about specific events that might lead to an occurrence of a hazard. Those specific events which may result in a mishap, generated from the software component of the system, are "Software Safety Concerns". 16 2.2.1 Software Safety Concern in the Source Code The analysis of source code is often seen as a review of the quality of the source code. Usually, the purpose of the source code analysis is to find the anomalies and potential bugs, not the safety concerns which may contribute to specific hazards. The identification of software safety concerns in the source code is necessary to provide evidence that such hazards' have been correctly assessed and successfully mitigated. However, this task is extremely difficult because anything within the source code (such as variables and run-time constants) and something outside of the source code (such as an erroroneous input from an operator) could contribute to an occurrence of a hazard. For the factors outside of the source code, many of them are also related to the incorrect and implicit reference of the software components in the source code. It is difficult to extract and represent the safety concern from source code due to the "long thin slice problem" [Won98]. The term "long thin slice problem" is referred to the fact that a small amount of source code which contributes to the hazard is buried among a large amount of non-executable code. Such difficulty can be overcome by experienced engineers who are familiar with the whole system. However, it may be extremely difficult for other people to perform this task even with the assistance of searching tools such as "grep". Instead, a software safety concern model needs to be built for safety verification. 2.2.2 Software Safety Concern Models The notion of "safety concern models" is the representation of the possible control and data flow paths. As we stated in the Chapter 1, control flow is the particular kind of view of the code where the code path is ordered by time of execution. Data flow is the view of code where the code path is ordered by the dependency of data computations based on previous data computations [Won05]. Extracting concern modules from the source code allows the engineer focus on the details of interest and ignores other less important details. 17 Hazard analysis requires a safety model of the system [Lev95]. However, as previously noted, many software hazard analyses are based on the analysis of the requirements and specifications. For example, [MLR97] describes an integrated approach to safety analysis of requirements applying on a guidance system for a high-speed civil transport. Software safety verification of the source code depends on a model which is built from the source code. This model might be only a "mental model" [VV95], but it is still useful for safety analysis [Won05]. However, as we stated above, such model is difficult to construct and maintain due to the scattered nature of the source code details. The desired properties of this software safety concern model should be conservative approximation, sufficiently complete and tractable. "Conservative approximation" means that every property of the model is also a property of the actual system. The conservative model provides simplicity for safety analysis. The notion "sufficiently complete" means the model contains enough information to interpret every executable statement in the model for the purpose of safety. This provides the necessary coverage for safety analysis. "Tractable" requires the number of the different places in the source code should be reasonable to understand each line of code [Won05]. A method was proposed to construct the software safety concern models [Won05]. This method consists of four basic steps, "flatten", "fillet", "partition" and "translate". We will present a brief introduction in the following. The process of "flatten" modifies the original classes by making explicit all the attributes, methods, conditions and invariants the class inherit from other classes. It also involves replacing the formal parameters with actual parameters, expanding, templates and changing parameter names. This process reduces the number of different places in the source code which may reduce the cognitive overhead of mentally combining scattered code fragments. This process seems expanding the code base, but it provides an efficient way to eliminate the uncertainty which resulted from inheritance in OO software. 1 8 The process of "fillet" involves identifying the source code we are interested in for specific hazard analysis and pruning irrelevant source code. We can use object-collaboration diagrams to guide the initial search corresponding to the hazard scenario. A l l related code paths (control flow and data flow) are extracted from the source code. We also need to remove irrelevant functionality according to the code reachability, conservative approximation and separate validation. The process of "fillet" provides necessary preciseness for the specific safety concern analysis. The purpose of "partition" is to identify different processes that are involved in the specific safety concern and evaluate their contribution to the safety related code paths. This process provides a different view of safety concern by the analysis of different contributors (including their communications) to the specific safety concern. The final step, "translate", provides a form representing the pruned source code. This process provides the user a more expressive way for the understanding of the specific safety concerns. These forms include "informal English", programming languages and formal mathematical notations. There are several existing techniques which can be used during these different build phases. For example, "code searching tools" can be used for "fillet", "Petri Nets" for "partitioning" and some language subsets for "translation". In our research, we are more interested in the tools and techniques which are used to separate safety concerns especially in source code. In the following, we will present a general background introduction of the techniques to separate software cross-cutting concerns. 2.3 Separating Safety Concerns As stated in Chapter 1, software safety concern is a cross-cutting concern. There are many techniques proposed to address such cross-cutting concerns such as subject-19 oriented programming [OSS96], hyperspace [THS99], aspect-oriented programming [Kic97] and the "concern graph" approach [Rob02]. 2.3.1 Hyperspace As described in [Hyp], Hyperspace is a technique used to achieve the goal of "multi-dimensional separation of concerns (MDSOC)", whose purpose is to enable "encapsulation of all kinds of concerns in a software system, simultaneously", "overlapping and interacting concerns" and "on-demand remodularization" [Hyp]. The dimensions of concerns can include "class", "feature", and "configuration". Hyperspace provides an approach to identify, encapsulate and manipulate such concerns. This approach also provides a mechanism to integrate and remove different dimensions of concerns. This approach does not rely on specific programming languages, compilers, and development environments. The notion of "concern" in hyperspace has a broad meaning. Every specific concept or goal we are interested in can be viewed as a concern. For example, "logging" can be viewed as a specific kind of concern which is not as inherent as other feature concerns or functional concerns. However, we can easily identify "logging" concern and integrate it with existing concerns. This process is not invasive, i.e., we can change the behaviour of program without changing its original source code or features. We do not have to take the "logging" concern into consider in the very beginning either. Instead, we can modulate and manage these concerns in any development or maintenance phase. These characteristics provide great usability and flexibility. One key advantage of hyperspace over other separating concern approaches is on-demand remodularization. It can identify and encapsulate a broad range of concerns. Hence it gives great help for software reengineering and refactoring. Other benefits of hyperspace include [Ot02]: 20 • Hyperslices are grouping constructs that collect together all software that pertains to a particular concern. • Integration and other kinds of relationships are separate from artifacts. • Hyperslices are declaratively complete, separately understandable, and reusable. • Concerns can span lifecycle phases. However, hyperspace can only support primitive concern units at the granularity of declarations (e.g., functions or members). Although this simplifies the implementation of the approach, it brings the limitation that it can only handle the "high-level" concerns, not the concerns extracted from the statements of source code. 2.3.2 Concern Graph Approach Robillard proposed the "concern graph" approach for concern representation and analysis [Rob02]. "Concern graph" is a model to abstract the concerns scattered over the source code. Specifically, these concerns are related to the elements of OO programs, i.e., each vertex in the "concern graph" represents the class, method or field, and each edge between the vertexes represents the semantic relationships such as "read", "declare", and "check". [Rob02] also provides a tool, FEAT (Feature Exploration and Analysis Tool), to extract a concern subset model form the Java source program. Through FEAT, the users can use different queries to get their concerns of interest. Furthermore, FEAT can provide the mapping between the concerns and source code. Users can easily navigate to the corresponding source code from the concern vertices and edges in the GUI. Compared to Hyperspace, the notion of "concern" in "concern graph" is more conservative however more expressive. This approach is more suitable for extracting the concerns from existing source code. Through FEAT, we can get a more intuitive and abstract view of the concerns. \ 21 This "concern graph" approach has its own limitations. Firstly, this model does not include the intra-method program elements. Intra-method elements, such as local variables, may contribute less to the specific concern than intro-method elements. However, the concern graph is not complete without them. As the authors argued, including such elements in the "concern graph" would increase the size of the model dramatically. The choice of the authors is a kind of trade-off between efficiency and coverage. This may apply for some general concerns. But we think it is not suitable for special concerns such as safety concern because the coverage and accuracy is more important to deal with software safety. Secondly, this approach does not distinguish different instances of edges. For example, within a method body, the model does not distinguish between two different call sites to the same method. The purpose of this choice was to simplify the model representation. However, as we mentioned earlier, different parameters (or local variables) also have important impact on the specific concern. 2.3.3 Aspect Oriented Programming As introduced briefly in Chapter 1, Aspect Oriented Programming (AOP) was proposed by Kiczales in 1997 [Kic97]. He introduced the new program construct "aspect" which is used to capture the cross-cutting concerns. Using "aspect", we can cleanly encapsulate and manipulate a variety of cross-cutting concerns. From AOP's point of view, every software system is composed of different kinds of concerns, including business logic, performance, data persistence, logging and debugging, and so on. These concerns may be captured by program modules or classes (in OO programming). However, as we described in Section 2.3.1, each concern usually exists in its "context". In the module where the concern seems encapsulated perfectly, it may not capture another specific concern while the context changes. Neither the procedural programming nor OO programming paradigm provides a mechanism to define and process the concerns neatly. Using AOP, we can design the software system as a bundle 22 of "aspects" or change the behaviour of the existing system according to our specific concern. Because AOP is not bound to any specific platform, language or programming paradigm, it has been implemented in many forms such as AspectJ and AspectC. However, a common disadvantage of these implementations is that "aspect" is captured at the "granularity" of method or field. For example, users of AspectJ can use regular expressions to extract different concerns from source code. However, these regular expressions are limited at the method or field level. As we described above, this is not enough for the analysis of safety concerns. In the next chapter, we will discuss our research of applying AOP to separate safety concern from source code in detail. 2.3.4 Program Slicing Program Slicing [Wei84], as introduced in Chapter 1, is the process during which we extract the code slice from the source code. We can view code slice as a subset for specified software concerns of the original source code. These software concerns are closely related to control flow or data flow of the whole system (The terms "Program Slicing" and "Code Slicing" are used interchangeably in the relevant literature, and we will follow this practice in the rest of this dissertation). An advantage of Program Slicing is generated code slices contain more comprehensive information about the specified concern than other approaches mentioned above. For example, Program Slicing can not only capture the inter-method program elements but also the intra-method program elements such as local variables. This characteristic is very important for software safety analysis. We will present more details about Program Slicing and how we can use it for software safety analysis in Chapter 4 and Chapter 5. 23 2.4 Summary This chapter provided the general context of system and software safety and software safety concerns. In particular, we introduced the software safety concern model which was used to deal with the cross-cutting safety concerns. The steps to build this safety model were also presented. Finally, we discussed different techniques used to separate software concerns. In the following, our research will mainly focus on how to separate the safety concern from source code effectively. 24 3. ASPECT ORIENTED PROGRAMMING This chapter will introduce Aspect-Oriented Programming (AOP) which is used to separate cross-cutting concerns. It will also demonstrate how we attempted to use AOP to isolate safety concerns and why this attempt was not successful. Kiczales [Kic97] presented AOP as a new programming technique in 1997 to capture some cross-cutting problems which Object-Oriented Programming (OOP) and Procedure-Oriented Programming (POP) failed to support. Many implementations of AOP have emerged since then. In the following, we will present the basic notions and techniques used by AOP, especially the first implementation of AOP for Java, AspectJ. We also show how we try to use AOP to separate cross-cutting concerns, in particular, safety concerns. 3.1 Introduction One of the main purposes of software design is to decompose a system into smaller units. These units are used to encapsulate and modulate system characteristics such as system functionalities. According to different programming techniques, these units can be procedures, functions or objects. A l l these decomposition mechanisms tended to design units according to different system behaviours and functions [Kic97]. However, this does not apply to some specific non-functional "concerns". These concerns are often spread across the whole system and cannot be encapsulated in units. In AOP, the system is composed of different "aspects". The main purpose of AOP is to capture and manipulate these "aspects". 25 Business Logic Persistence Security Logging Figure 3.1 Concern decomposition To better understand the background of AOP, we show an example as follows. We have a software requirement which says "all the functions need to put the user's name into the log." It is not difficult that we design a "log" unit to encapsulate this functionality and use it in each module. function log(variable user_name){ write(user_name); 1 function functionA(...){ ....business logic...; log(user_name); ) function functionB(...)( . . . . business logic...; log(user_name); ) Figure 3.2 "Log" Function Code Snippet 1 It seems this solution encapsulate all the functions perfectly. Nevertheless, if the requirement changes to "all the functions need to put the user's name and time into the log.", what should we do now? We can rewrite a new module "log2" to capture this new requirement. 26 function log2(variable user_name, variable time){ write(user_name, time); } function functionA(...)j ....biz logic...; log2(user_name,time); ) function functionB(...){ ....biz logic...; log2(user_name,time); ) Figure 3.3 Log" Function Code Snippet 2 This requires us do some manual work to replace the original "log" function in the with the new "log2" function. We may use some text search-and-replace tools to do such work. However, how about the case the requirement changing to "some cases using log, other cases using log2?" We can still use the search-and-replace tool to solve such problems, but we need pay attention to the specific differences. This problem is caused by the fact that the "log" function spread over the whole system. When we need do some change for "log" functionality, we need apply them to all the places in the system. It would be perfect if we capture the requirement in the following form: function log(variable user_name)( write(user_name); ) all functions: log(user_name) Figure 3.4 "Log" Function Aspect Pseudo Code Compared to the original example, we only need change one place if the requirement changes. Obviously, this is a cleaner way to capture this "log" cross-cutting concern. AOP can suit these needs perfectly. In the terminology of AOP, all the cross-cutting concerns can be encapsulated into an "aspect". AOP provides a well defined way to define and manipulate these "aspects". 27 There are many frameworks supporting AOP in the market which include Spring, AspectWerkz and AspectJ. In the following, we will present a brief introduction for them. 3.1.1 Spring Spring is a light-weight J2EE framework [Spring]. It applies AOP to enterprise concerns such as transaction management. Key AOP concepts supported include: • Interception: Custom behaviors can be inserted before or after method invocations against any interface or class. This is similar to "around advice" in AspectJ terminology. • Introduction: Specifying that an advice should cause an object to implement additional interfaces. • Static and dynamic pointcuts: Specifying the points in program execution at which interception should take place. Static pointcuts concern method signatures; dynamic pointcuts may also consider method arguments at the point where they are evaluated. Pointcuts are defined separately from interceptors, enabling a standard interceptor to be applied in different applications and code context. Spring supports both dynamic and static pointcuts. Static pointcuts contain two kinds: regular expression and attribute-driven. Here is an example of regular expression pointcut: <bean id="settersAndAbsquatulatePointcut" class="org.springframework.aop.support.RegexpMethodPointcut"> <property name="patterns"> <list> <value>.*get.*</value> <value>.*absquatulate</value> </list> 28 </property> </bean> Figure 3.5 Spring PointCut Definition Dynamic pointcuts are costlier to evaluate than static pointcuts. They take into account method arguments, as well as static information. This requires that they must be evaluated with every method invocation; the result cannot be cached, as arguments will vary. The main example is the control flow pointcut similar to the "cflow" in AspectJ. 3.1.2 AspectWerkz AspectWerkz is another framework supporting AOP [ASZ]. It supports not only method interception but also field interception. AspectWerkz supports dynamic pointcuts as well as static pointcuts. It can also use the Regular expression for static pointcuts, for example: "int foo.*.Bar.method()" - will match int method() but not "int method(int i)". For the dynamic pointcuts, AspectWerkz has the similar types of pointcuts as AspectJ. 3.1.3 AspectJ AspectJ is a language-extension for Java which provides support for AOP. To better understand the example as follows, we introduce some terms of AspectJ here. A "join point" is a well-defined point in the program flow such as method in Java. A "pointcut" picks out certain "join points" and values at those points. A piece of "advice" is code that is executed when a "join point" is reached. "Aspect" is the unit of modularity for crosscutting concerns. They behave somewhat like Java classes, but may also include "pointcuts", "advice" and inter-type declarations. AspectJ (version 1.0) supports the following "poincuts" [Aopp]: 29 Methods and Constructors caW(Signature) every call to any method or constructor matching Signature at the call site execul\on(Signature) every execution of any method or constructor matching Signature Fields gel(Signature) every reference to any field matching Signature set(S/g nature) every assignment to any field matching Signature. The assigned value can be exposed with an args pointcut Exception Handlers hand]er(TypePattern) every exception handler for any Throwable type in TypePattern. The exception value can be exposed with an args pointcut Advice adviceexecution() every execution of any piece of advice Initialization staticinitialization(7ype/'a??ern) every execution of a static initializer for any type in TypePattern \nhia\izaUon(Signature) every initialization of an object when the first constructor called in the type matches Signature, encompassing the return from the super constructor call to the return of the first-called constructor preinitialization(S;'g7M?wre) every pre-initialization of an object when the first constructor called in the type matches Signature, encompassing the entry of the first-called constructor to the call to the super constructor Lexical W\\.\\\n(TypePattern) every join point from code defined in a type in TypePattern withincode(5(gnar«re) every join point from code defined in a method or constructor matching Signature Instanceof checks and context exposure Xhis(Type or Id) every join point when the currently executing object is an instance of Type or Ws.type target(7y/;e or Id) every join point when the target executing object is an instance of Type or Id's type args(7ype or Id, ...) every join point when the arguments are instances of Types or the types of the Ids Control Flow cf\ow(Pointcut) every join point in the control flow of each join point P picked out by Pointcut, including P itself cflowbelowCPo/Vi/CMO every join point below the control flow of each join point P picked out by Pointcut; does not include P itself Figure 3.6 AspectJ Pointcut Types 3.2 Safety Concern as Aspect As described in the above sections, AOP can be used to "insert" certain implementation details at appropriate places in the source code. The user of AOP must be aware of these approriate places and they must assure of the correctness of these "join points". The use 30 of AOP can not provide safety engineers the safety concern details in the souce code automatically. Even if the safety engineers are aware of all the safety concern details in the source code, however, it is still hard to encapsulate these concerns using AOP. In the following, we will show a simple example to describe the cross-cutting nature of "safety concern". We also show how AspectJ is used to capture such concerns and its shortcomings. In this example, our main safety concern is the properties of class "DataSource". (In the sense of "safety concern", we mean any unexpected changeJo or from "DataSource" could bring safety hazards to the whole system.) We want to know if and how this concern could affect other system behaviours or properties. Here we show some code snippets. The complete source code is listed on Appendix. "DataSource" class represents the data we want to trace (specifically, its property "propl" and "prop2"). "DataProcessor" and "AnotherDataProcessor" represents the data processing class. Both have "Process" method in which we change the "propl", "prop2". "DataProcessor" also has a "prop3" property which also is changed in the "Process" method. Here is the "Process" method of "DataProcessor": public void Process()( dataSource.prop 1 = 2; this.prop3 = dataSource.prop 1 + dataSource.prop2; this.prop4 = dataSource.prop 1 - dataSource.prop2; dataSource.prop2 = 3; ) Figure 3.7 DataProcessor.java Code Snippet Here is the "Process" method of "AnotherDataProcessor". Public void Process() { dataSource.prop 1 =4; 31 dataSource.prop2 = 5; ) Figure 3.8 AnotherDataProcessor.java Code Snippet From above we can see the code to change the values of "propl" and "prop2" of "DataSource" spreads over two different methods. If we want to use a "pointcut" to describe the changes, of "propl" and "prop2", we can use the "pointcut" to locate where these properties are changed: pointcut Property lChanged():execution(* Process(..)); after():Property 1 Changed() (...) Figure 3.9 "Process" Aspect In the above Java statement, this "pointcut" chooses the execution points of method "Process" of both data processing classes. However, the types of "pointcut" in AspectJ are limited. The smallest unit of "pointcut" is method or field (Please check above diagram for details). In the case of "method unit", we can insert the concern-processing code if and only if the concern code is located at the beginning or end position inside the method. For example, the code changing the "prop3" is in the middle of the in the middle of the "Process" method of "DataProcessor". We can not simpley use "after()" or "befor()" to insert our processing code. Instead, we need to refactor the code as follows. Public void Process(){ dataSource.prop 1 = 2; ChgProperty3(); //prop3 = dataSource.prop 1 + dataSource.prop2; this.prop4 = dataSource.prop 1 - dataSource.prop2; dataSource.prop2 = 3; ) public void ChgProperty3(){ prop3 = dataSource.prop 1 + dataSource.prop2; 32 ) Figure 3.10 DataProcessor.java Refactored Code Snippet When we want to define the "pointcut" for the value change of "prop3", we use code like this: pointcut property3Changed():execution(*DataProcessor.ChgProperty3(..)); after():Property3Changed() (...) Figure 3.11 "Process" Refactored Aspect Using the above "refactor" method, we can separate some specific safety-related features or properties and encapsulate them into methods. Then we can use AOP to encapsulate them into aspects. However, this approach has some disadvantages. The most serious problem is that it is a "code-invasive" way to handle such concerns. This approach needs break the original source code into specific parts to adapt to specific concerns. With the change of "safety context", the contents of safety concerns changes. This brings us a problem: how can we organize the source code to suite for the new "safety aspect" without affecting the original one? For example, if now we have a new safety concern related to "prop4" of "DataProcessor", we need to refactor the code again. This surely is another "cross-cutting" concern. The problem exists in the fact that "safety concern" is a high-level and abstract concern but it is also "detail-oriented". This "detail-oriented" characteristic of safety concern is unique comparing to other concerns AOP can handle. AOP does provide a way to abstract concerns such as transaction and logging. However, it only functions at method or field level. 3.3 Summary We presented a brief introduction of AOP and its implementations in this chapter. We also showed how we use AspectJ to encapsulate the safety concern into an "aspect". Basically, AOP can insert the relevant code from various aspects into designated locations, i.e., "join points", in the main program. It is still the AOP user's obligation to 33 define these "join points" and assure the correctness of these "join points". For software safety concern, the use of AOP can not automatically provide the safety concern details to software safety engineers. 34 4. PROGRAM SLICING Program Slicing is an analysis technique that extracts program slices, i.e., portions of a program, from program statements. The extent of an extracted program slices is determined by its relevance to a particular computation [Bin96]. This technique is often used in program debugging, testing, program maintenance, understanding [KL88, HPR89, GL91.CFV93]. In this chapter, we will investigate the possibility of applying Program Slicing to software safety verification. In particular, we will try to use Program Slicing to extract safety concerns from source code of safety-critical systems, especially from the source code of systems designed in an Object Oriented (OO) style. This chapter is organized as follows. Section 1 introduces the concept of Program Slicing and introduces different kinds of slicing methods. Section 2 evaluates the existing slicing tools to see whether they could be used effectively for the purpose of extracting portion of the source code relevant to a particular safety concern. Section 3 summarizes this chapter. 4.1 Slicing Introduction Weiser [Wei84] introduced the notion of a "code slice", which he described as an executable program with a behaviour that must be identical to that of the specified subset of the original program. In Weiser's original description, the program slice has two crucial properties: executable and behaviour-preserving. With a slicing criterion, involving statements and a set of variables, program slicers can determine all the statements and variables that affect the values of the selected variables and statements. According to Weiser, Program Slicing is usually static, i.e., it does not involve any run-35 time information, and is backward, in that slicers usually try to find the "source" of the specific variable values. Subsequently, a wide variety of alternative slicing algorithms were proposed, such as interface slicing [Bec93], and conditioned slicing [Can98]. Basically, all of the different slicing algorithms can be categorized as either: static slicing or dynamic slicing. With the programming paradigm shifting from a procedural to an OO approach, however, the analysis of slicing is further complicated. One of the important slicing approaches is dynamic slicing [KL90], which involves program input, run-time data flow analysis, and control flow analysis. The use of dynamic slicing could bring us a more precise slice. In the following, we will introduce these different approaches. 4.1.1 Static Slicing According to Weiser [Wei84], the original slicing criterion is a pair "<p, V>", where "p" is a program point and " V " is a subset of program variables. A program slice based on the slicing criterion "<p, V>" is a subset of program statements that preserves the behaviour of the original program at the program point "p" with respect to program variables in " V " , i.e., the values of the variables in " V " at program point "p" are the same in both the original program and in the slice. Since this algorithm is based on the static control flow graph, it is called "static" slicing. Several basic algorithms are used for static slicing of structured programs, such as "Dataflow Equations", "Information-flow Relations," and "Dependence Graphs" [Tip95]. Special attention should be given to the "Dependence Graphs" method since it has been thoroughly studied, and many new approaches have grown from this method. Ottenstain first proposed the Program Dependence Graph (PDG), a program representation where vertexes represent statements and predicates, while edges carry information about control and data dependencies [Ott84]. The vertexes must be ordered to preserve the semantics of the original program. In this representation, the original 36 slicing criterion "<p, V>" is changed to "<v, V>", where "v" represents the vertex and " V " represents all the directly or indirectly affected variables. This form of slicing is also a kind of backward slicing, in contrast to forward slicing. Horwitz extended the PDG algorithm for computing the inter-procedural slices based on the System Dependence Graph (SDG). In comparison to the original PDG approach, he considers the "procedure calling contexts," to produce more precise slices with this approach [Hb90]. 4.1.2 Dynamic Slicing Static slicing is very useful for program analysis. However, it can not provide a precise analysis in some cases. For example, in the statement: "If condition A and condition B happens, then Hazard H is present." Several questions could be asked about this statement, such as "What if condition A happens, condition B happens, or neither of these conditions happens?" if these conditions are determined at the runtime, it is impossible to use static slicing to tell whether Hazard H is actually present or not. Instead, we could use conditioned slicing and/or dynamic slicing to locate the actual hazard precisely. Gallagher addressed this idea: " A static program slice can be further refined by examining the trajectory of specific inputs through the program: we can use a dynamic slice to observe individual instances of the computation." [G193] The concept of dynamic Program Slicing was first presented by Korel and Lasky [K190]. The dynamic slicing algorithm uses dynamic analysis to identify only the statements that affect the variables of interest for a particular anomalous execution trace [LucOl]. Because run-time information is used to compute the program slices, the size of the generated program slices may be significantly decreased. Another advantage of dynamic slicing, as stated by Korel and Lasky [K190], is the run-time handling of arrays and pointer variables. Dynamic slicing treats each element of an array individually, whereas 37 static slicing considers each definition or use of any array element as a definition or use of the entire array. The basic algorithms to compute dynamic slices are based on dynamic flow analysis, dynamic dependence relation analysis, and dynamic graph analysis. Miller was the first to present a Dynamic Program Dependence Graph (DPDG), a dynamic variation of PDG [Mc89]. With this approach, a static PDG is constructed prior to program execution, which is then augmented with code that generates a log file. During debugging, all of this information is combined to compute the dynamic PDG of the specific code blocks. Agrawal proposed the algorithm based on the Dynamic Dependence Graph (DDG). The dynamic slicing criterion is identified with a vertex in DDG, and the dynamic slice is computed by determining all reachable DDG vertices. A statement of the control predicate is included in the slice if it can be reached from at least one of the determined vertices [Ah90]. Zhao [Zha98] proposed the Dynamic Object-oriented Dependence Graph (DODG), which explicitly represents various dynamic dependences between statement instances for a particular execution of the OO program. The dynamic slicing criterion for an OO program was defined in the form "(s,v,t,i)", where "s" is a statement in the program, "v" is a variable used at "s", and "t" is an execution trace of the program with input " i " . The generated dynamic slice of an OO program using the above slicing criterion consists of all statements in the program that actually affect the value of a variable "v" at statement "s" [Zha98]. The main distinction between Zhao's dynamic slice and Korel's dynamic slice is that Zhao's slice is non-executable. Dynamic slicing has several advantages over static slicing, one of which is its precision. Because dynamic slicing can find most of the statements that can actually affect the specific variables, it ignores non-related execution paths, procedures and statements. On the other hand, the disadvantages of dynamic slicing are also obvious. First, dynamic slicing can not provide a full coverage for all possible execution paths and cannot 38 guarantee the completeness of the slices. Second, dynamic slicing often requires changes to be made in the behaviour of the original programs to record the run-time information, which may decrease the performance of original programs. 4.1.3 Hybrid Slicing Gupta and Sofia [GsOl] proposed a hybrid slicing algorithm to take advantages of both static and dynamic slicing. This approach improves the precision and quality of static slices by incorporating dynamic information in static slicing and enabling the computation of hybrid slices. This technique requires information from debugging (breakpoint information) as well as the dynamic call graph. The accuracy of static slicing is improved by analyzing the execution paths more precisely. Gupta also claimed that hybrid slicing improves the quality of slicing information by associating each statement with an execution interval that is divided by breakpoints or call/return points [GsOl]. Rilling and Karanth [RkOl] proposed a hybrid slicing framework, as an integrated part of MOOSE (Montreal Object Oriented Slicing Environment). In contrast to previous approaches such as the PDG or the CFG, this slicing framework depends on the "removable block" notation, which was originally proposed by Korel and Ferguson [Kf92]. Removable blocks are described as being the smallest component of the program text that can be removed during slicing computation without violating the syntactical correctness of the program. The algorithm proposed by Rilling utilizes a syntax tree which contains removable blocks that differs from the classical algorithms using control or data flow. Although the hybrid slicing algorithm seems promising, research in this area is still in its initial phase. The hybrid slicing algorithm needs' to be further exploited and more thoroughly investigated. 39 4.2 Evaluation of Existing Slicing Tools Since the notion of "Program Slicing" was proposed more than 20 years ago, many code slicing tools are designed using different methods. However, most of the slicing tools are designed for research purpose [Won05]. The evaluation of slicing tools has ever been performed by Hoffner [Hof95]. Hoffner evaluated several slicing tools such as Kamkar's slicing tool, Spyder, Schatz' slicing tool, and FOCUS [Hof95]. Most of these slicing tools are based on procedural languages such as C, Pascal, and FORTRAN. Later, new slicing tools emerged, though most are for experimental purposes, and less support is available for object-oriented languages such as C++ and Java, compared to that available for the procedural languages. The criteria used by Hoffner [Hof95] to evaluate different slicing tools: Correctness -how well do generated slices conform to the slicing criteria; Precision - do the generated slices contain the precise information; Languages - can the tools be used to slice different programming languages; and Efficiency - the time-efficiency or space-efficiency of the specific slicing algorithms. Most of the tools are strictly for research purposes, and many of the tools mentioned by Hoffner are now out of date (i.e., no longer available). In the following subsections, a more detailed evaluation of these tools is provided 4.2.1 Spyder Spyder is a debugging tool to assist users in locating bugs. The slicing part is one integrated part of the tool, which was described by Agrawal [Agr91]. The implementation is based on GNU's C compiler GCC and debugger GDB, and both static and dynamic slicing can be performed. 40 The targeted language for this tool is ANSI C, however, after downloading the whole source code, we found that it could not be compiled using GCC 3.2.2, likely because of out-of-date library dependencies and language characteristics. The basic algorithm of Spyder is based on graph reachability in dependence graphs. The program to be sliced is instrumented and compiled to an executable program. Then the program is executed and its I/O is recorded. This information is then used by the debugger to execute the program and generate a dynamic dependence graph. The slice is finally constructed by traversing the dependence graph. The implementation of Spider can only use backward slices at the statement level. This tool does not support many characteristics of ANSI C such as the "define" statements. Another disadvantage of this tool is in the way it is implemented. For its instrumentation, Spyder must "customize" the GCC and GDB to record and extract the dynamic information. This may affect the compatibility— new software that can be compiled by the newest GCC successfully, may not pass the compilation using the older version of GCC. 4.2.2 Unravel Unravel is a prototype Program Slicing tool supplied by the National Institute of Standards and Technology (NIST). The tool was developed in C with a user interface written with the MIT Athena Widgets and the X Window System. The targeted language is ANSI C. Unravel can only provide a static slicing function and the source code is also out-of-date. After fixing several bugs related to the API of xLib and the out-of-date C styles, it can be compiled finally. We tried this tool on simple cases such as slicing a simple file, and found that it worked. Nevertheless, problems are seen when trying to slice multiple program components. 41 Unravel contains three main components: analyzer, linker, and slicer. In contrast to Spyder, Unravel does not modify the GCC or GDB. Instead, it implements the analyzer module which has almost the same function as a compiler. It generates a file in a different format for the linker. Unravel provides all the necessary information for constructing a syntax tree, getting the memory address of the variables, and constructing a PDG. Still, as was also the case for Spyder, it seems Unravel is not compatible very well with the newest GCC version. 4.2.3 CodeSurfer CodeSurfer is a powerful source code analysis and navigation tool. It displays different kinds of information about the program in details. CodeSurfer was developed on the basis of the Wisconsin Program Integration System, which was also evaluated by Hoffner. To our knowledge, this tool is the most mature tool for Program Slicing, available in the market. CodeSurfer claims to fully support ANSI C language and have an alpha support for C++. It can do static forward or backward slicing. After installing this tool, we began our evaluation by running some simple tests. First, CodeSurfer seems to be more user-friendly than most other slicing tools that we tested. Users can easily configure the settings and provide the input data. Second, CodeSurfer provides rich information for the whole program. Also, we found that it generated the desired results for our simple test cases. After trying to run more complicated test cases, however, we found that the results were not sufficiently precise. Too much information was generated that was irrelevant to the slicing criteria. CodeSurfer uses the SDG for Program Slicing. It contains several phases: a) front end, when a language-specific front end is invoked and is responsible for creating intermediate files that are used in subsequent phases; b) pointer analysis, when a point-to graph is created for the whole program; and c) SDG builder, when the final SDG is generated through the CFGs extracted from the source code and the pointed-to database [Art03]. 42 CodeSurfer provides support for richer language characteristics, compared to most of the other slicing tools. Nevertheless, as Anderson [Art03] mentioned, "our experience is that the slicing operations are generally not used much for program understanding because they often deliver too much information to be easily comprehended." In any case, they are still useful for understanding such questions as: "What affects X that does not affect Y ? " or "What affects both X and Y ? " Other than above slicing tools, we also evaluated other slicing tools mentioned in Hoffner's research [Hof95]. The result was disappointing, however, since it seems most of the tools are out-of-date now. 4.2.4 Java Slicing Tools A l l slicing tools mentioned so far are for ANSI C or C++. Our initial version of RDPS was implemented in C and then ported to C++. A C/C++ slicing tool is desirable since we want to evaluate the safety of our Radar Data Processing System (RDPS) through Program Slicing. However, based on the above evaluations for C/C++ slicing tools, we feel Java slicing tools may be more approriate for this task because Java has some desirable characteristics such as platform independency. In the following subsections, we briefly introduce slicing algorithms for Java programs and evaluate the slicing tools designed for Java. Like most of the other slicing tools, Java slicing tools are also based on PDG, SDG or their extensions. In contrast to C/C++ slicing tools that perform slicing on source code, in the Java slicing tools, we may apply slicing algorithms in two kinds of forms, Java source code and Java byte code. Both of these forms can be either static or dynamic. Java is a modern object-oriented language and has many features such as inheritance and polymorphism, which are difficult to handle with conventional methods. 43 In the following, we briefly evaluate several Java slicing tools, which were generally found to have different limitations. Bandera/lndus Bandera is a model-checking tool designed by Kansas State University, and the Program Slicing is an integrated part of the whole tool set. Model-checking is one kind of finite-state verification techniques, which is capable of exposing subtle defects in the logic of sequential and concurrent systems [Ban]. Although tools like SPIN [Spin] can be used for the formal verification of distributed software systems, they can only accept a description of a finite-state transition system as input. The Bandera project addresses one of the major obstacles in the practical finite-state verification of software and bridges the semantic gap between non-finite-state software systems expressed as source code and the tool input languages. Hence, Program Slicing is useful for excluding irrelevant information from the source code. As mentioned above, slicing is a single component of the Bandera tool set. Bandera contains several components such as a sheer, transition system builder, and other analysis utilities. A l l of these components are built on top of the Soot Java compiler framework [Soot]. The Soot framework is used to convert Java source code into an internal representation called Jimple, which is essentially a three-address code version of J V M byte-codes. It includes all of the concurrency-related operations, such as enter-monitor that enters the monitor in association with a variable. This is discussed in more detail in the subsection Sheer Design and Implementation. We evaluated the slicing function supplied by Bandera, which can perform static forward or backward slicing for Java source programs. The slicing for one simple Java source file was performed successfully. However, it seems to be unable to perform the same function over multiple files. In addition, the generated slices are reflected only in the Jimple format, which some users may be unfamiliar with. 44 Later, the Bandera group moved the analyses and transformations into a new project called Indus. It is intended to serve as an umbrella for static analyses, transformations, and other modules that deliver the analyses / transformations into a particular application such as Bandera, or a platform such as Eclipse. Indus has three main components, though we are only interested in its Program Sheer component. The Program Slicer component of "Indus" was designed according to the same requirements used by Bandera. The implementation is architected as a library rather than as an application to facilitate the reuse of its subparts and the core is independent of the application. We have tried to use "Indus" over Eclipse through the Kaveri plugin [Kav] for Eclipse. "Indus" passed the test in slicing a simple Java source file, though we noted it is much slower than Bandera. After feeding it with our Radar Data Processing System (RDPS) source files, however, the tool at first failed with the error message: "not enough memory." After increasing the maximum memory amount setting of the J V M , the tool seemed to enter into a non-stop loop. Because we could not get the source code of "Indus", we could not ascertain the reason for the fault. These tests were performed under the version of "Indus" 0.4. ADAS/DCSIicer The Aspect-Based Dynamic Analysis and Slicing System (ADAS) is a tool designed by Osaka University [Adas]. It performs dynamic slicing using newly aspect-oriented techniques such as AspectJ to instrument the byte code. This tool is supposed to work under Eclipse 2.1 with AJDE plugin 1.0.6 and AJDT plugin 0.5.2. These plugins are designed to process AspectJ programs under the Eclipse environment. Because the fundamental components of the AspectJ compiler change drastically in Eclipse 2.1, they (or their versions) cannot work in this environment any more. On the other hand, the A D A S depends not only on Eclipse 2.1 for the GUI part, but also on out-of-date AspectJ compiler components. Despite all efforts to make it work, we were unable to get it to function according to the claims. 45 4.3 Summary In this chapter, we presented a brief introduction of Program Slicing and evaluated different slicing tools which can be used on RDPS. In particular, we have tried several slicing tools which can be applied on Jave source code. However, we found these tools have different limitations which lead us to design and implement our own slicing tool. 46 5. SLICER DESIGN AND IMPLEMENTATION As stated in last chapter, we found most of slicing tools were outdated and were not suitable for safety analysis through the evaluation of them. Although new slicing tools are still emerged, they are mainly built for research purpose. Moreover, many of these new slicing tools often have defects and are not open-source, which results in an extra difficulty for our research. In order to carry out our research, i.e., using Program Slicing to extract safety concern from source code, we decided to build our own slicing tool. When we started to design the slicing tool, we faced the problem of selection for different programming language support by the slicing tool. Currently, the mainstream programming languages are C, C++ and Java. Based on our knowledge and experience, we finally chose Java as the supported language of the slicing tool because a lot of research has been carried to make Java more suitable for safety-critical and real-time applications [Bollella+2000a, Dau]. As stated in section 4.1, both static slicing and dynamic slicing have advantages and disadvantages over each other. Static slicing often generates more slices than needed while dynamic slicing generates less slices but more precise. Moreover, object-oriented program languages such as Java have many dynamic features such as dynamic dispatch and dynamic binding, which makes it more difficult to get the precise slices by static slicing. In safety analysis, precision is a very important characteristic. We do not want the safety information "buried" in the great volume of program slices. Accordingly, we need incorporate the dynamic analysis with static slicing. The concept of dynamic analysis, especially how to apply dynamic analysis for Java programs, will be described in further detail in this chapter. We will also introduce SOOT, a Java optimization framework, which our slicing tool depends on. An example of our slicing tool is also presented. 47 5.1 Dynamic Analysis of Java Program Dynamic analysis includes dynamic data flow analysis and dynamic control flow analysis, which is often used by dynamic slicing to identify only the statements that affect the variables of interest for a particular anomalous execution trace [LucOl]. Dynamic analysis of Java program often requires the record of execution traces and code instrumentation. Different dynamic analysis methods may have different impacts on computation time and memory space. To better understand the different dynamic analysis techniques, we first look at the Java program execution cycle. V J Figure 5.1 Java class code execution model We can collect dynamic information at any step in Figure 5.1. For example, we can build a tool to pre-process the Java source code and insert Java codes. These Java codes will dynamically analyze dependence relations between statements on execution. We can also extend J V M and insert the instrumentation code dynamically. These approaches have both advantages and disadvantages, which will be discussed in the following. The approach of "Pre-processing" was addressed by Ohata [OhfiOl], the main benefit of which is its simplicity. Using JavaCC, which is a Java parser generator written in the Java programming language, we can build a pre-processing environment easily. One of the-advantages of JavaCC is its "extremely customizable" feature, which offers many different options to customize the behaviour of JavaCC and the behaviour of the generated parsers [JCC]. Hence, we can customize the parser to insert the additional code 48 dynamically. The approach of "Java Compiler Customization", which was stated earlier by Umemori [Ukyi03], can be used together with other techniques such as "Byte Code Instrumentation" to insert additional code dynamically. One use of this method was generating the cross-reference table between source code and byte code. By referring to this cross reference table, we can point the slice criterion specified on the source code into the slice criterion on the bytecode, and calculate the slice on the bytecode. The approach of "Bytecode Instrumentation" can be used to insert bytecode dynamically. Several existing Java class libraries are available to facilitate the process of instrumentation. For example, the Byte Code Engineering Library (BCEL) [BCEL] provides the low level API. Javaassit, another bytecode processing class library[JAS], provides a high level interface, however, its function is limited. Soot [SOOT], a high level optimization and compiler framework, can be used to construct the abstract syntax tree (AST) graph and analyze the dynamic information. In particular, Soot provides the API which can be used to instrument the bytecode at different levels. A more detailed discussion about Soot will be presented in next section. The approach of " J V M extension" can also be applied to instrument the Java bytecode dynamically. By customizing J V M , we can record the dynamic data flow path, which can be used to construct the PDG of bytecode. However, this approach often causes the consequence that the specific dynamic code instrumentation tool (including dynamic slicing tool) can only run under the specific customized J V M . For example, the latest version of J V M is 1.5 which is used by the application program while the customized version is 1.2, which often causes unnecessary confusion and problems. The method of "Class Loader Customization" can be used at the stage of "bytecode loading" and before the actual execution of Java bytecode. This approach is widely used 49 in AOP. For example, AspectWerkz, one of the Java AOP frameworks [ASZ], applies this approach for dynamic weaving. This approach is often used together with other byte code instrumentation techniques such as Javaassist to insert the bytecode at load time. In addition to above methods, we can also use "JPDA", the Java Platform Debugger Architecture (JPDA) which provides the infrastructure for building end-user debugger applications for Java 2 Platform, to implement byte code instrumentation. These instrumentations include static, load-time, and dynamic instrumentation. For static instrumentation, the class file is instrumented before it is loaded into the J V M . After a class file is loaded by the J V M , the raw bytes of the class file can be sent for instrumentation to the JPDA agent. A class that is already loaded (and possibly even running) is modified and can be instrumented dynamically. JPDA has a rich set of APIs which can be used for dynamic analysis of source code/bytecode. We finally chose the Byte-Code Instrumentation as our solution for dynamic analysis. This approach does not have any dependency on specific compilers or Java Virtual Machines (JVM). It is able to instrument the Java byte code dynamically according to the open Java Language Specification. Aside from that, it does not have a high requirement for Java Runtime Environment (JRE), which is the main disadvantage of JPDA method. Another decision we made about the slicing tool was that the tool must be able to perform slicing not only on Java source code but also on object code (in .class format). This is based on the fact that most modern software systems now employ a wide variety of COTS, which do not provide their own source code. The COTS components may affect our variables of choice in an intricate way. No other means are available, except slicing the Java object code, to include the analysis of COTS in slicing. Instead of writing our library for Java Byte-Code analysis and instrumentation which is a time-consuming and error-prone task, we choose Soot, a third-party library, as the "back-end" for the slicing tool. We will present a short introduction of Soot and its role in the 50 implementation. In addition, the construction of the call graph is discussed, as well as the technique used to instrument the code dynamically. 5.2 Soot Introduction Soot [SOOT] is a Java optimization framework developed by the Sable group of McGi l l University. It provides functions to optimize or instrument the Java byte code and has four intermediate representations for analyzing and transforming Java byte code: • Baf: a streamlined representation of byte code, which is simple to manipulate. • Jimple: a typed 3-address intermediate representation suitable for optimization. • Shimple: a variation of Jimple. • Grimp: an aggregated version of Jimple suitable for decompilation and code inspection [Soot]. To optimize the Java byte code, Soot transforms Java byte code from Baf to Grimp, then back to Baf, and then to byte code. Each specific transformation is performed to handle some specific Java characteristics. For instance, Java bytecode contains a constant pool which contains all the program constants. Java bytecode instructions must refer to indices in this pool in order to access fields, methods, classes, and constants, and this constant pool must be tediously maintained. Baf abstracts away the constant pool, and thus it is easier to manipulate Baf code. In our research, the tasks (i.e., building call graph and incrementing byte code) are mainly focused on Jimple representations. To get an intuitive impression of Jimple, one example of Java source code,its bytecode and corresponding Jimple representation is shown below: 51 public void testfName n) { n.print2("variable"); System.out.println("Hello test"); } Figure 5.2 Java Source Code Snippet public void test(com.test.Name); aload_ 1 ldc #2; invokevirtual #3; pop getstatic #4; ldc #5; invokevirtual #6; return Figure 5.3 Java Bytecode Snippet public void test(com.test.Name) { com.test.Hello this; com.test.Name n; java.io.PrintStream Sri; this := @this: com.test.Hello; n := @parameterO: com.test.Name; virtualinvoke n.<com.test.Name: java.lang.String print2(java.lang.String)>("variable"); $rl = <java.lang.System: java.io.PrintStream out>; virtualinvoke $rl.<java.io.PrintStream: void println(java.lang.String)>("Hello test"); return; } Figure 5.4 Corresponding Jimple Code Java bytecode always executes in the Java Virtual Machine (JVM). A J V M is a stack-based machine which makes the Java bytecode instructions very simple [JVM]. From the above code, we can see that the implicit stack variables have been replaced by additional local variables in the Jimple representation. A l l of the method calls are replaced with a more explicit method signature. Such features are useful for analyzing the virtual method resolution. We can see the Jimple bytecode is easier to understand and process than the original Java bytecode. In particular, it is worth mentioning that each method call in the original Java source code ("print2" and "println") is replaced by the Jimple keyword "virtualinvoke" which corresponds to the Java bytecode keyword "invokevirtual". We may have four different method calls in Jimple: "virtualinvoke", "specialinvoke", "interfaceinvoke" and "staticinvoke" depending on the types of method calls in Java source code. For example, "specialinvoke" can replace the method calls which construct new Java objects (i.e., the original Java method is the object constructor). 52 5.3 Call Graph Construction As introduced in Chapter 1, call graph is often used to identify modules in the system and shows which modules call another. In our slicing tool design, call graph is constructed as the back-trace tree, in particular, the back-trace tree for Jimple code. In the empirical analysis of call graph, a major obstacle was that the callees are not easily defined in object-oriented languages such as C++/Java. To illustrate this, the following example from Grove [Gddc97] is given: procedure maini). { return AO + B () + C } procedure A() { return max(4, 7!; } procedure BO { return max(4.5, 2.5! } procedure CO { return max<3, 1) ; } (a) P.xample Program Figure 5.8 Example Program and call graphs In this example, function "max" takes two forms: either the "integer" or the "float" as its parameters. However, in some cases, some function call with the "float" parameters could be transferred to the call with the "integer" parameters implicitly. This makes it more complicated to construct a precise call graph As mentioned above, however, all of the method calls are transformed to the explicit method signature in the Jimple form. For example, in Java, the statement "n.print2("variable");" changes to "virtualinvoke n.<com.test.Name: java.lang.String print2(java.lang.String)>("variable");", where we can find the signature function "print2" containing the necessary parameter type. Hence, the Jimple format eliminates uncertainty and the construction of the call graph becomes straightforward. : 0 •• ^malrQ C D C D C D CT) CT) (ID max ^ (b) Context-Insensitive max 0 ^ { ^ m a x ^ (c) Context-Sensiti ve 53 5.4 Slicing Algorithm Our slicing algorithm is based on a data/control flow analysis and call graph. Before performing backward slicing, the user needs the input of slicing criteria (e.g., variable name, variable location in the source file). The whole process flow is represented by the following diagram: Source Code Slicing Criteria Call Graph Construction / • Static Backward Slicing • < 7 Program Execution/Instrumentation \ 7 Dynamic Slicing Figure 5.9 Slicing Work Flow In the "call graph construction", the main goal is to construct a global call graph for later use. First, we analyze all the program modules. In each module, we construct a graph node for each method. We call such graph node "vertex". Then we store the vertex into a global vertex table. Each method in this module may call other methods. We check if the callee has been stored in the global vertex table. If so, we simply add a new "edge" between this callee vertex and caller vertex. Otherwise, we create a new callee vertex and then add the new edge. To facilitate the back trace, we also store other properties such as 54 the source code line number where the callee get called in the caller vertex. A l l the vertexes may have multiple callers and callees. They may not have any callees, but they do have a common "root", i.e., the "main" method of this application. If a vertex does not have this common root, it will not get called while in execution. Finally, we get a complete call graph for each method in this application. In "Static Backward Slicing", we get the variable names of our interest, i.e., slicing variables, and the method name where the variable locates from "Program Input". First, we will check the program statements containing the slicing variables to find all the input variables which may affect the values of slicing variables. If so, we add the new variables into the group of slicing variables and go backward to the previous statement. For instance, in statement " A = B + C", variable " A " is our slicing variable. Its value is determined by variable " B " and "C" . So we will put " B " and " C " into the group of slicing variables and go backward to repeat the last step. When we get to the beginning of this method, usually the first line of this method, we need to check the caller of this group. We treat this method as a vertex and search for all possible caller vertexes. Then for each caller vertex, we repeat the same process until we get to the "root" vertex. During the process, we record all the slicing variable names and their corresponding locations, i.e, the name of the method and source code line numbers. This result can give us a clear indication where and which variables may affect the specific variable values of our interest. To better understand the process of "instrumentation", we need bring in the notion of "code block", which contains single or multiple program statements and can be viewed as the vertex of control flow graph (CFG). In "Program Execution/Instrumentation", we insert additional program code into each possible "code block" of the original program. This additional code plays the role as "Recorder". It records whether the specific control flow executes at runtime. After execution of this program, we have a record of which block are actually executed. 55 At the final "Program Slicing" stage, through the analysis of this dynamic execution record, we can get all the actual executed program statements and methods. Accordingly, we can find the actual caller vertex of the specific vertex. This decreases the number of program slices and makes the slicing result more precise. In the following, a simple example is presented, in which, backward slicing is performed step by step. 56 public void outPut(int s){ intt= 1; int result = t+s; ) public static void main(String[] vars)( int a = 1; int t = 2; Hello h = new Hello(); if(a=l){ 5: h.outPut(t+a); )else( 7: h.outPut(t); Figure 5.10 Hello.java public void outPut(int){ com.test. Hello this; int s, t, result; this := @this: com.test.Hello; s := ©parameterO: int; t= 1; result = t + s; return; ) public static void main(java.lang.String[]){ java.lang.String[] vars; int a, t, $i0; com.test.Hello h, $r0; Block 0: vars := ©parameterO: java.lang.String[]; a= 1; t = 2; $r0 = new com.test. Hello; specialinvoke $r0.<com.test.Hello: void <init>()>(); h = $r0; if a != 1 goto labelO; Block 1: $i0 = t + a; 8: virtualinvoke h.<com.test.Hello: void outPut(int)>($iO); goto label 1; Block2: labelO: 10: virtualinvoke h.<com.test.Hello: void outPut(int)>(t); Block 3: label 1: return; ) Figure 5.11 Corresponding Jimple Code A l l of the processing is based on the Jimple code. For example, in the above code, suppose our task is to slice variable "result" in the method "outPut(int s)". First, we 57 supply the slicing tool with the slicing criterion: the variable name "result", and the location "outPut(int s)". Then, we construct the call graph of the whole source code. In the call graph, we record not only the callers but also the calling positions, e.g., for the graph node "outPut", we record its calling node "main" and the locations: line 4 and 6 of method "main". Then, we begin the backward static slicing. We check variable "result", and find it is determined by the right hand variables "t" and "s". We trace back along with the control flow and find "t" is determined in this method. Nevertheless, "s" is a parameter passed into this method. We then search the call graph to find the callers and the calling location. In this example, we find the caller "main", and the location information: line 4 and 6 of method "main". According to the calling context mapping, we find the parameter "s" has changed to "t". We then perform backward slicing of variable "t" from each of these locations. Finally, we get all the variables that may affect the variable "result". In this example, we get the following results: <com.test.Hello: void outPut(int)>#3 <com.test.Hello: void outPut(int)>#2 <com.test.Hello: void outPut(int)>#l <com.test.Hello: void main(java.lang.String[])>#8 <com.test.Hello: void main(java.lang.String[])>#7 <com.test.Hello: void main(java.lang.String[])>#2 <com.test.Hello: void main(java.lang.String[])>#l <com.test.Hello: void main(java.lang.String[])>#10 Figure 5.14 Jimple Code Static Slicing Result int result = t+s; int t = 1 ; h.outPut(t) ; h.outPut(t+a); intt= 2 ; int a = 1; Figure 5.15 Java Code Slicing Result 58 It is worth noting that the bold lines in Figure 5.9 correspond to the "line 5" and "line 7" in Figure 5.7. From Figure 5.7, we can see only "line 5" in this program can be executed. However, the static slicing results contain both "line 5" and "line 7". In the "Execution/Instrument" stage, a line of code which calls a "log" method will be automatically inserted before each code block. We then run the instrumented code as we would run any other normal Java class code. In addition to finishing the original task, the instrumented code also produces a log file that records the executed blocks' numbers. This is the dynamic information we need to perform dynamic slicing in our hybrid approach. It is worth noting that the bold lines in Figure 5.9 correspond to the "line 5" and "line 7" in Figure 5.7. From Figure 5.7, we can see only "line 5" in this program can be executed. However, the static slicing results contain both "line 5" and "line 7". In the "Execution/Instrument" stage, a line of code which calls a "log" method will be automatically inserted before each code block. We then run the instrumented code as we would run any other normal Java class code. In addition to finishing the original task, the instrumented code also produces a log file that records the executed blocks' numbers. This is the dynamic information we need to perform dynamic slicing in our hybrid approach. In the above example: public static void main(String[] vars){ int a = 1; int t = 2; Hello h = new Hello(); block 0 if(a==l) { h.outPut(t+a); block 1 }else{ h.outPut(t); block 2 } } Figure 5.16 Hello.java Code Snippet 59 The corresponding Jimple code of the code above is shown as follows. A = 1; t = 2; $rO = new com.test.Hello; specialinvoke $rO.<com.test.Hello: void <init>()>(); h = $r0; if a != 1 goto labelO; $i0 = t + a; virtualinvoke h.<com.test.Hello: void outPut (int)>($iO); goto label 1; labelO: virtualinvoke hxcom.test.Hello: void outPut (int)>(t); label 1: return; Figure 5.17 Hello.jimple Code Snippet To generate the "instrumented version" of the above code, we input the following command: j ava com.test.Main - f j imple - p jb use-original-namesrtrue Most of .the instrumentations are executed by the class "com.test.Main", which is the main instrumentation class in our slicing tool. This command will instrument the above code and produce the following Jimple code. staticinvoke <com.test.InfoLogger: void log(java.lang.String)>("<com.test.Hello: void main(java.lang.String[])>ABlock #0Avars := @parameterO: java.lang.String[]"); vars := ©parameterO: java.lang.String[]; a= 1; t = 2; $rO = new com.test.Hello; specialinvoke $rO.<com.test.Hello:- void <init>()>(); h = $rO; if a != 1 goto labelO; staticinvoke <com.test.InfoLogger: void log(java.lang.String)>("< com.test.Hello: void main(java.lang.String[])>ABlock #1 A$iO = t + a"); $i0 = t + a; 60 virtualinvoke hxcom.test.Hello: void outPut(int)>($iO); goto label 1; labelO: staticinvoke <com.test.InfoLogger: void log(java.lang.String)>("< com.test.Hello: void main(java.lang.String[])>ABlock #2Avirtualinvoke h.<com.test.Hello: void outPut(int)>(t)"); virtualinvoke hxcom.test.Test: void outPut(int)>(t); label 1: staticinvoke <com.test.InfoLogger: void log(java.lang.String)>("< com.test.Hello: void main(java.lang.String[])>ABlock #3Areturn"); staticinvoke <com.test.InfoLogger: void flush()>(); return; Figure 5.18 Instrumented Jimple Code Snippet From the above code, we can see at the beginning of each block, a bold line of "staticinvoke" method was inserted. As we introduced in Section 5.2, "staticinvoke" is a keyword in Jimple code, which calls the instrumentation method "log" of class "com.test.InfoLogger" in this case. The following is the source code of "log" method: public static synchronized void log(String s) { System.err.println(s); writer.println('s); } Figure 5.19 Java Code Snippet For Instrumentation Basically, this "log" method does nothing more than outputting the information to a log file. After we run the above instrumented version of "com.test.Hello", we get the log file which contains the information such as "<com.test.Hello: void main (java.lang.String[])> ABlock #0A10 := @this: com.test.Hello", which can tell us that the "Block 0" of the "main" method in the "com.test.Hello" class was actually executed. This log file of this instrumented program is as follows. •ccom.test.Hello: void main(java.lang.String[])>ABlock #0Avars := @parameterO: java.lang.String[] <com.test.Hello: void <init>()>ABlock #0Athis := @this: com.test.Hello <com.test.Hello: void main(java.lang.String[])>ABlock #lA$i0 = t + a <com.test.Hello: void outPut (int)>ABlock #0Athis := ©this: com.test.Hello 61 <com.test.Hello: void main(java.lang.String[])>ABlock #3Areturn Figure 5.20 Java Code Snippet For Instrumentation In the above code, we can see that "Block' 2" is not included in this log file, which means "Block 2" is not actually executed. From Figure 5.7, we can see "Block 2" contains "line 10" of the Jimple bytecode which corresponds to the "line 7" of Java source code. Hence, the last line of the original slicing result in Figure 5.9 can be removed. To sum up, by integrating with dynamic analysis of the program source code, we can achieve a more precise result without the expensive time and resource costs of static slicing. This is a desired approach for software safety analysis. 5.5 Summary This chapter discussed how to apply Program Slicing to extract software safety concern from the source code. We also provided our design and implementation of the slicing tool for safety analysis. In particular, we explored the techniques which were used to collect the dynamic information for Program Slicing. We reached this conclusion that combining both static and dynamic slicing can get a more precise result for software safety analysis. 62 6. RDPS EXAMPLE In this chapter, we will present the Radar Data Processing System (RDPS) as an example for software safety concern analysis. We will try to use three different techniques for the safety analysis: text search ("grep"), AOP and Program Slicing. In the following, we will first give a brief background introduction of the RDPS. Then we will go through all the details of the different techniques for safety analysis. This analysis leads to our overall conclusion that Program Slicing is the most suitable techniques for safety analysis, by comparing these different approaches. 6.1 RDPS Introduction A Radar Data Processing System (RDPS) is a computer-based system that transforms Air Traffic Control (ATC) radar data into a set of "tracks" that can be displayed directly to air traffic controllers or used as input to other computer-based systems. In addition to generating a stream of track updates messages, RDPS will typically include functionality to generate various kinds of warnings. For example, this may include a functionality to generate a Minimum Safe Altitude Warning (MSAW) when the altitude of an aircraft, as indicated by transponder data, is below the designated minimum safe altitude for a particular location. The four most interesting classes of this architecture are the "Radar", "Correlator", "Track" and "Datablock" classes. Each instance of the "Radar" classes corresponds to a physical radar site that serves as a source of radar data for the RDPS. For a typical air traffic control facility, there will be several radar sources with partially overlapping coverage of the airspace. The "Correlator" class yields a single object that matches incoming radar reports to "tracks" and decides when a new track should be created. Each instance of the "Track" class corresponds to a single aircraft currently within radar coverage. For a busy airspace, there may several hundred "Track" objects in existence at any one time - and each of these 63 "tracks" is being refreshed by an incoming radar report several times each minute. Finally, instances of the "Datablock" classes correspond to the representation of a single aircraft on an aircraft controllers situation display. -DataBlocfeMariiSRcr' • ChangeV iewOr i g'i n C I * Truck j^Keg i s t a rt ima i" (J; H M b i i u O u i Q tKot i f j -Q 1 DatftHlock Bjsplay ' ] * -SiiiDi'SiJlayO. HlpdatqO •'-* 1 ti roeUBrtnger pA'ddTifflCP-O +R«ii>veTi«cr{)-.. 4-Sctti rneOr i g:3 n t] ^Correlator •AiitJTrFick'O" -RecovB.Tnjck.t) -lllkliHuTnhck,{); Figure 6.1 Radar Data Processor Class Diagram The "steady state" behaviour of the RDPS is illustrated by the sequence diagram shown in Figure 6.2. The scenario represented by this diagram begins with the receipt of a new radar report from the Radar Network Interface. The "Radar" generates a new "radar return" report and sends it to the "Correlator". The "Correlator" analyzes this "radar return" and finds it match with an existing "Track" object. So the "Correlator" notifies the corresponding "Track". The "Track" yields a request to "DataBlockManager" to update its track state. "DataBlockManager" updates the corresponding "DataBlock" object and submits a request to "Display" to update the position of "DataBlock". 64 AtcClierit^M [ jRadarNtttworlr | |;: Radar] ^Correlator] j-;:Track I [i :TimoManatier j j "•: DataBlockMariaqerl| ' . DataBlock [ |, :'DisrJIav^] Figure 6.2 Sequence Diagram Showing Steady State Behaviour A list of the identified hazards for this system includes the following conditions: • the displayed position of a track is incorrect; • the displayed altitude of a track is incorrect; • an established track within the current area of interest is not displayed; As illustrated above, the title of a hazard may be deceptively simple. Using techniques such as Fault Tree Analysis, we may discover that a hazardous condition such as "the displayed position of a track is incorrect" could occur in a variety of ways. The most obvious cause is a defect in the sequence of data operations that transform incoming radar data into a pixel position on a CRT display. Other less obvious causes include a delay in processing radar data, such that the displayed position is stale with respect to the most recently received radar data. It is also possible that the radar surveillance data for one aircraft may be swapped accidentally with the radar surveillance data for a different aircraft. Discovering all of the possible causes of a hazardous condition depends on a detailed understanding of the relevant source code. 65 When analyzing source code with respect to particular safety concern, we are searching for answers to a variety of questions about relevant portions of the source code. For example, this may include such questions as [JJ04]: • What compile-time constants or secondary sources of external data are involved in the processing of critical data? • Is the processing logic complete? For example, does it include provisions for when an optional element of the input data is not available? • What could cause time-dependent data to be delayed during processing? For example, when the CPU is heavily loaded, could this result in a backlog of incoming radar reports to be processed? For the purposes of discussion, we focus on just one of the above-mentioned hazards -namely, the possibility that the position data contained in a track update generated by the RDPS is incorrect. The display of incorrect position information to an air traffic controller could mislead the controller into making a decision that quickly and directly results in a catastrophic mishap such as a mid-air collision. The portion of the RDPS implementation involved in the processing of position information is a safety concern that cross-cuts the architecture shown in Figure 6.1. Position information contained in track updates generated by the RDPS is derived from position information contained in the radar reports received as input by the RDPS. Position information flows from incoming radar reports to generated track updates through each of the classes shown in Figure 6.1. Throughout its processing by the RDPS, the position information is contained within an aggregate data item that includes other kinds of information such as geographical position in terms of latitude and longitude. In order to extract this safety concern, we will use three different approaches: text search ("grep"), AOP and Program Slicing. 66 6.2 Approaches to Separate Safety Concerns In this section, we will present our techniques to separate this specific concern ("position information"). We also compare these techniques to get our conclusion, i.e., Program Slicing is the most effective way to separate the safety concern. 6.2.1 Text Search As Robillard [Rob02] mentioned, lexical searching tools such as "grep", has been used to separate the cross-cutting concerns. In this subsection, we will use "grep" to go through the source code (Appendix A) to analyze the "Position" concern. Firstly, we search for the aircraft position shown on the display. The aircraft position is obtained only from the following statements: System.out.println(" Create aircraft "+pDB.GetId()+ " at "+w+ ", "+h+ " An"); (File: TextDisplay.java line: 31) "w" and "h" are set by previous statements: int h=(int)(pDB.GetPosition().north * height); (File: TextDisplay.java line: 29) int w-(int)(pDB.GetPosition().east * width); (File: TextDisplay.java line: 30) "height"and "width" are run-time constants. This function is called by the following statement: display.Create(this); (File:DataBlock.java line: 27) The previous call is: pdb. Create();(File:DataBlockMgr.java line:70) "pdb" is determined by the previous statements: pdb.position.north = (track.positionLL. latitude-viewOrigin. latitude+latScope)/( 2 HatScope); pdb.position.east =(track.positionLL. longitudeviewOrigin. longitude+lonScope)/( 2 HonScope); 67 (File:DataBlockMgr.java line:62) A l l are run-time constants except for "track.positionLL.latitude" and "track.positionLL.longitude". "track" is the parameter of method : public void DisplayTrack(Track track,int Ibl) (File:DataBlockMgr.java line:33) This method is called by: dbMgr.DisplayTrack(this,lbl);(File:Track.java line:40) We will ignore many details in the text searching process. This process is tiresome, boring and error-prone. During this process, we went through most of the system components and dug into the program details. Finally, we found the position of aircraft is determined by "azimuth", "slant range" and "mode C" values of the radar report, and other constant values In order to present this concern from the source code, we can organize all these extracted statements and variables into a single document. For example: System.out.println("Create aircraft "+pDB.GetId()+" at "+w+" ,"+h+" !\n"); (File: TextDisplay.java line: 31) int h=(int)(pDB.GetPosition().north * height); (File: TextDisplay.java line: 29) int w=(int)(pDB.GetPosition().east * width); (File: TextDisplay.java line: 30) Figure 6.3 RDPS Code Snippet This solution could answer our question, i.e., which elements in the source code can possibly affect this "position" concern? However, if the specific concern of our interest changes, we have to repeat the entire manual work from the very beginning. In this sense, this approach is only a "workable" approach, but not a good one. 6.2.2 AOP As we discussed in Chapter 3, AOP can also be used to separate the safety concerns. An ideal solution to our problem would allow the safety analyst to see all of the source code involved in the processing of position information "in one place" rather than trying to piece together multiple fragments, which are scattered across the architecture and tangled together 68 with other aspects of processing that have no impact on the position information reported in track updates. We can capture the "position" concern by encapsulating it into an "aspect". However, as we showed in Chapter 3, this approach contains too many context-sensitive program details which are hard to put together into one aspect. We need to "refactor" our source code to suit the AOP. For example, we can define the following "pointcut" and "advice": pointcut getDataBlockPosition():execution(* GetRadarReturnProperty(..)) || execution(* Radar.SetRadarReturnPos(..)) || execution(* Correlator.SetTrackPosition(..)) || execution(* DataBlockMgr.DisplayTrack(..)); before():getDataBlockPosition() { ) Figure 6.4 RDPS Aspect Code Snippet In the above statements, all the methods are not fine-grained enough to point to the exact positions of those statements which are actually related to the position of the aircraft. For instance, the above method "DisplayTrack" (DataBlockMgr.java) contains such program statements which are related to the aircraft position: pdb.position.north =(track.positionLL.latitude-viewOrigin.latitude+latScope)/(2*latScope); pdb.position.east=( track.positionLL.longitude-viewOrigin.longitude+lonScope)/(2 *lonScope); We can encapsulate these statements into another method "ChgDataBlockPosition" and then pick this method as a "joint point" instead of choosing the method "DisplayTrack" (DataBlockMgr.java). However, this approach, as we stated in Chapter 3, has one serious limitation. It cannot automatically find all the "join points". It still needs to deal with the source code details and, more importantly, in a "code-invasive" way. This invasive way brings change to the original source code, which also means increasing the hazards to the original software. For software safety analysis, this is unacceptable. 69 6.2.3 Program Slicing In order to use our Program Slicing tool, we need the soot library and JRE library. Before we slice the position information out of the original source code, we need translate the original code (in .Java format) into Jimple code (in jimple format).The input of the slicing tool is the variable name of our interest and the location of the variable. In this case, it is the variable of aircraft position on the display and the signature of the method it belongs to, which is "<com.atc.TextDisplay: void Create(com.atc.DataBlock)>#h". In the above statement, "<com.atc.TextDisplay: void Create(com.atc.DataBlock)>" is the method signature of the method "Create" (TextDisplay.java). The character "#" is the delimiter we defined. The "h" is the height position of the aircraft on the display. As we stated in Chapter 5, call graph construction is very important for Program Slicing. We can build the call graph of RDPS through the slicing tool. Due to the large number of the graph vertexes and edges, we can not show the whole picture of the call graph. In the following, we will show the portion of the call graph which are related to the slicing input. 70 Figure 6.5 call graph Portion Related to Slicing Input In the figure above, each graph vertex represents a method in a Java class and is shown in the format "class name: method name". 71 Following the detailed steps described in Chapter 5, we get the result from the output file. This file contains all the lines which related to the variable "h" and the methods' signatures they belong to. Due to the length limitation of the slicing result, we just give a portion of the result: Fig 5.6 shows the code slice in Jimple format and Fig 5.7 shows the corresponding code slice of the original Java source file. From the above, we can see that Program Slicing can automatically separate the "position" concern and encapsulates it as a "slice". If the concern of our interest changes (e.g., we want to investigate which factors can affect the height position of the aircraft on the display), we do not need to look for corresponding statements manually. We only need to change the input parameters and run the slicing tool again. This approach also has its limitations: it cannot add the "advice" code like AOP does and the "slice" is non-executable. However, as we stated in Chapter 2, this slicing technique is mainly used for safety verification. It does not necessarily have the ability to add extra flexibility and dynamicity to the original source code. Comparing this slicing approach with AOP and text search, we can find that Program Slicing is more desirable for safety analysis of RDPS. Many other safety-crital systems such as the Chemical Factory Management System described in [Won05], have the similar cross-cutting safety concerns. Hence, we can apply this technique to them as well. <com.atc.TextDisplay:void create(com.atc.DataBlock)>#7 <com.atc.TextDisplay:void Create(com.atc.DataBlock)>#6 <com.atc.TextDisplay:void Create(com.atc.DataBlock)>#5 int h=(int)(pDB.GetPosition().north * height); return position pdb.Create(); Figure 6.6 RDPS Jimple Code Slice Snippet Figure 6.7 RDPS Java Code Slice Result 72 6.3 Summary In this chapter, we presented a brief introduction of RDPS. We also showed how to separate software safety concerns using different techniques such as AOP, text search and slicing. We compared their pros and cons and drew the conclusion that Program Slicing is the most efficient way to separate safety concerns. 73 7. SUMMARY AND FUTURE WORK There is an urgent need to provide safety engineers with methods and tools capable of verifying the safety of the increasingly complex and integrated safety-critical software. The goal of this dissertation was to investigate different techniques to separate the software safety concern and verify software safety. The traditional approaches to solve these safety concerns are based on the effort to isolate "safety-related" components as much as possible. However, the increasingly complex and integrated nature of modern safety-critical software makes it more and more difficult. Instead of insisting on isolating the safety concern from the rest of the system, Dr. Wong [Won05] argued that software safety must be assured by not only requirement analysis but also source code verification. There is a variety of existing techniques for software source code analysis such as software visualization tools which is very useful for software understanding and debugging. There are also several new methods proposed to address the "cross-cutting" nature of modern OO software such as AOP and Hyperspace. However, there is little research on how to handle the "cross-cutting" nature of software safety. In this dissertation, we mainly compared two different approaches to separate the "cross-cutting" code from the rest of the system from the view of software safety. We now summarize the results of the dissertation, including our contributions to the field of software safety verification. We also discuss some avenues for future research. We finish by presenting some concluding thoughts. 7.1 Summary of the Contribution of the Dissertation The following thesis statement can summarize the work of this dissertation: 74 Software safety concerns often involve fragment of source code that crosscut the modular structure of the software system. This "cross-cutting" feature makes software verification very difficult, especially with the increased size of complexity of modern software system. Software tools should be used to untangle the safety-critical code to verify the safety of source code. A recent doctoral dissertation by Ken Wong at the University of British Columbia identifies several possible methods that could be used to extract representations of cross-cutting safety concerns from source code. We investigated several possible techniques including Aspect Oriented Programming and Program Slicing which can be used to achieve this goal. Our investigation casts some doubt on the use of Aspect Oriented Programming as a means of isolating cross-cutting safety concerns. At the same time, the results of our investigation suggest that Program Slicing is worth more investigation as a means of carrying out the methodology proposed by Wong in his dissertation. The contributions of this dissertation can be summarized as follows: • An in-depth analysis of using AOP to isolate the cross-cutting safety related concern. • Demonstration of the use of SOOT for Program Slicing applied on safety analysis. • Combining static and dynamic analysis of system safety code to get a more precise result. 7.1.1 Using AOP to separate safety concern The first contribution involves investigation the possibility to use AOP to isolate the safety concern. Kiczales once mentioned that AOP can be used to abstract the "safety concern" from the system [Kic03]. 75 Conceptually, AOP is designed to inject certain implementation details at appropriate places in the source code. For example, to address a cross-cutting security concern about file access, AOP may be used to ensure that specific security checks are injected into the source code wherever the code attempts to access files. For this reason, the AOP community sometimes uses the term"weaving" to describe the process by which code elements are injected into the code at appropriate places to address a cross-cutting concern. But the problem addressed by this research is not solved by weaving code elements into the code. Instead, the task of untangling safety-critical code is really to find all the approprate places related to the specific safety concern in the source code. In addition, current AOP implementations do not provide a perfect way to encapsulate the safety concern even if the safety engineers are aware of all the details on specifc safety concern.We illustrated this by providing an example in details. In Chapter 3, we defined the concern whose source code was scattered among the whole source code. We also showed the cross-cutting "position" concern which spread over the main components of the whole system in RDPS example. In these two examples, we can see AOP is not a suitable tool to address such safety concerns. 7.1.2 Demonstration of the use of SOOT for Program Slicing applied on safety analysis. There is a variety of Program Slicing tools available. However, most of them are only built for research purpose [Won05]. There is little research effort spent on applying Program Slicing for software safety analysis, especially for the safety analysis of modern complex OO software. SOOT is a popular open-source framework for program optimization, especially designed for Java language. This framework provides a rich set of APIs to manipulate the Java code, including the capability to instrument Java byte code dynamically. Accordingly, it 76 has the ability to slice not only Java source code but also the Java byte code. In today's world, modern software is often comprised of a variety of COTS whose source code is seldom available. Accordingly, the ability of slicing byte code is a very important characteristic of Java slicing tool. We can slice the byte code through SOOT which is an advantage over other slicing tools. 7.1.3 Combining static and dynamic analysis of system safety code Static analysis for the source code can provide us with the necessary coverage for safety verification. We analyze the call graph to get the call flow of the whole target system (e.g.,RDPS). The use of this technique covers all the methods of the all components in the target system. Dynamic analysis, during our research, involves dynamic insertion byte code into the original target system. These inserted byte code monitors and reports the actual execution paths. This approach decreases the number of program slices and provides us with the more precise result. Combining both static and dynamic analysis techniques enables us to better explore their advantages. This "hybrid" approach makes our analysis both complete and accurate. 7.2 Future Work 7.2.1 Improvement of the slicing tool There are several possible directions to improve our slicing tool. Firstly, our tool is a non-GUI application right now. It does not have a GUI to show the slicing result for the user. Adding the interaction with the user would increase the convenience and decrease the operation difficulty for the user. Secondly, we can improve the functionality and the 77 performance of our tool by applying other slicing algorithms. So far, we have the ability to perform backward slicing. We can expand the slicing function of our slicing methods by providing forward slicing. Additionally, we can integrate with other slicing algorithms to improve the performance of our tool. 7.2.2 Improvement on the program model of "concern graph" As we stated in Chapter 2 , the "concern graph" approach can also be used to separate the software concern. Due to the consideration of potential computational and memory cost, the original concern graph program model is restricted to the analysis of inter-method control flow and data flow while local (intra-method) elements were excluded. It is a challenging task to keep the original functionality while extending the application scope of "concern graph". 7.2.3 Software visualization tools There is a wide range of visualisation tools such as V G J [VGJ] and xSuds [Xsuds] that can be used for the navigation and presentation of software information. One typical use of such tools is to provide a "graphical" view for software source code, in which each graphic element represents a software unit. It supports different views of the program such as source code listing and call graph. However, most of the existing tools were not designed to extract or highlight safety concern from the source code. More research wil l be needed to use this technique for safety concern encapsulation and representation. 78 7.3 Conclusion Safety concerns often cross-cut the main structures of a complex software system. For safety verification purpose, software engineers should be provided with an integral view of such concerns. There are many techniques which could help us to achieve this task. We have discussed the possibility of using AOP, text searching, and Program Slicing to resolve this cross-cutting concern. We also compared their pros and cons. In these techniques, Program Slicing seemed more promising because it can successfully represent the details of safety concern without incurrence of the lost of flexibility. The research field of software safety verification and representation still needs more investigation. There are many questions that still have no answers. For instance, how can we effectively encapsulate the safety concern in the development phase, i.e., how can we map the safety requirement to a program unit (component or "aspect")? There is more work to do towards this direction. This dissertation is our first step to achieve the goal. 79 BIBLIOGRAPHY [Adas] [Agr91] [Agr99] [Ah90] [Aopp] [Art03] [ASZ] [Ban] [Bel99] [BCEL] [Bec93] Takashi Ishio, http://sel-pop.ics.es.osaka-u.ac.jp/~t-isio/adas.html (visited April 5, 2004) Hiralal Agrawal, "Towards Automatic Debugging of Computer Programs", PhD thesis, Purdue University, 1991. Gagan Agrawal, "Simultaneous Demand-Driven Data-flow and Call Graph Analysis", in Proceedings of International Conference on Software Maintainance (ICSM), pp. 453-462, September 1999. Hiralal Agrawal and Joseph R. Horgan, "Dynamic Program Slicing", In Proceedings of the ACM SIGPLAN'90 conference on Programming language design and implementation, pp. 246-256, 1990. The AspectJ 5 Development Kit Developer's Notebook, http://www.eclipse.org/aspecti/doc/next/adkl5notebook/in dex.html (visited June 30, 2005) Paul Anderson, Thomas Reps, and Tim Teitelbaum, "Design and Implementation of a Fine-Grained Software Inspection Tool", IEEE Transactions on Software Engineering , 29(8), August 2003. AspectWerkz, http://aspectwerkz.codehaus.org/ (visited April 5, 2004) Bandera, http://bandera.projects.cis.ksu.edu/ (visited April 5, 2004) Thorns Bell, "The concept of dynamic analysis", Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, pp. 216-234, France, 1999. B C E L , http://iakarta.apache.org/bcel/ (visited January 13, 2005) Jon Beck and David Eichmann, "Program and interface slicing for reverse engineering", Proceedings of the 15th international conference on Software Engineering, pp. 509-518, May 1993. 80 [Bin96] [Bollella+2000a] [Can98] [CFV93] [Chot99] [Dau] Dave Binkley and Keith Gallagher, "Program Slicing", Advances in Computers, Vol 43, 1996. Marvin Zelkowitz, Editor, Academic Press San Diego, C A . Greg Bollella, J. Gosling, B. Brosgol, P. Dibble, S. Furr, D. Hardin, and M . Turnbull, The Real-Time Specification for Java. Addison-Wesley, 2000. Gerardo Canfora, Aniello Cimitile, and Andrea De Lucia, "Conditioned Program Slicing", In Mark Harman and Keith Gallagher, editors, Information and Software Technology Special Issue on Program Slicing, vol40, pp. 595-607, 1998. F. Cutillo, Piernicola Fiore, Giuseppe Visaggio, "Identification and extraction of domain indepen-dent components in large programs", In Proceedings of the Working Conference on Reverse Engineering, June 1993. Siobhan Clarke, William Harrison, Harold Ossher and Peri Tarr, "Subject-Oriented Design: Towards Improved Alignment of Requirements, Design and Code", ACM SIGPLAN Notices, 1999. Jean-Marie Dautelle, Validating Java™ for Safety-Critical Applications, http://iavolution.org/doc/Man33955.pdf (visited September 28, 2005) [Ern03] [Gddc97] [GL91] [G193] [GsOl] Michael D. Ernst, "Static and dynamic analysis: synergy and duality". In 1CSE Workshop on Dynamic Analysis (WODA), May 2003. David Grove, Greg DeFouw, Jeffrey Dean and Craig Chambers, "Call Graph construction in object-oriented languages", A C M SIGPLAN Notices archive, 32(10), October 1997. Keith B. Gallagher and James R. Lyle, "Using Program Slicing in software maintenance", IEEE Transactions on Software Engineering, 17(8), August 1991. Keith Gallagher and James Lyle, "Software Safety and Program Slicing", Proceedings of the 12th Annual Conference on Computer Assurance, June 1993. Rajiv Gupta and Mary Lou Soffa, "Hybrid Slicing: An Approach for Refining Static Slices using Dynamic 81 Information," ACM SIGSOFT Third Symposium on the Foundations of Software Engineering, pp. 29-40, 1995. [Hof95] [Hb90] [HPR89] [Hyp] [IkiOl] [ISPE] [JAS] [JCC] [JJ04] [JLAN] [JVM] Tommy Hoffner, Mariam Kamkar and Peter Fritzson, "Evaluation and Comparison of Program Slicing Tools", Technical Report LiTH-IDA-R-95-01, Dept. of Computer and Information Science, Linkoping University, Sweden, 1995 Susan Horwitz, Thomas Reps and David Binkley, "Interprocedural slicing using dependence graphs", ACM Transactions on Programming Languages and Systems, 12(1): 26-60, January 1990. Susan Horwitz, Jan Prins, and Thomas Reps, "Integrating non-interfering versions of programs", ACM Transactions on Programming Languages and Systems, July 1989. I B M Research, http://www.research.ibm.com/hyperspace/ (visited February 22, 2005) Takashi Ishio, Shinji Kusumoto and Katsuro Inoue, "Program Slicing Tool for Effective Software Evolution Using Aspect-Oriented Technique", Sixth International Workshop on Principles of Software Evolution (IWPSE'03), 2003. IEEE Standard 610.12-1990, IEEE Standard Glossary of Engineering Terminology, Institute of Electrical and Electronics Engineers, Inc. New York. 1994. Javaassist, http://www.csg.is.titech.ac.ip/~chiba/iavassist/(visited February 6, 2004) JavaCC, https://iavacc.dev.iava.net/ (visited March 17, 2004) Jeffrey Joyce, The draft of "Is Aspect Oriented Programming Useful For Safety-critical Applications?" 2004. James Gosling, Bi l l Joy, Guy Steele and Gilad Bracha, "The Java Language Specification, Third Edition", http://java.sun.com/docs/books/ils/download/langspec-3.0.pdf (visited June 30, 2005) Tim Lindholm, Frank Yellin, "The JavaTM Virtual Machine Specification, Second Edition", 82 http://iava.sun.com/docs/books/vmspec/2nd-edition/html/VMSpecTOC.doc.html (visited June 30, 2005) [Jw03] [Kav] [Kf92] [Kic03] [Kic97] [KL88] [KL90] [Ko97] [Lan97] [Lar96] Jeffrey J. Joyce and Ken Wong, "Hazard-driven Testing of Safety-related Software", 21st International System Safety Conference, Ottawa, Ontario, Canada, 4-8 August 2003. Kaveri Plugin, http://indus.proiects.cis.ksu.edu/proiects/kaveri.shtml (visited June 30, 2005) Bogdan Korel, and R.Ferguson, "Dynamic slicing of distributed programs", Applied Mathematics & Computer Science Journal, 2(2): 199-215, 1992. Gregor Kiczales, "FW: [aosd-discuss] Obliviousness Principle in Aspect-Oriented Software Development", http://server2.hostvalu.com/pipermail/discuss aosd.net/200 3-August/000630.html (visited February 17, 2004). Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Lopes, Jean-Marc Loingtier and John Irwin, "Aspect-Oriented Programming", In European Conference on Object-Oriented Programming, June 1997. Bogdan Korel and Janusz Laski, "STAD - A system for testing and debugging: User perspective", In Proceedings of the Second Workshop on Software Testing, Verification and Analysis, pp. 13-20, July 1988. Bogdan Korel and Janusz Laski, "Dynamic slicing of computer programs", The Journal of Systems and Software, 13(3), November 1990. Bogdan Korel, "Computation of Dynamic Program Slices for Unstructured Programs", IEEE Transactions on Software Engineering , 23(1), January 1997 Filippo Lanubile and Giuseppe Visaggio, "Extracting Reusable Functions by Flow Graph-Based Program Slicing", IEEE Transactions on Software Engineering, 23(4), 1997. Loren Larsen and Mary Jean Harrold, "Slicing object-oriented software", In Proceedings of the 18th international conference on Software engineering, pp. 495 - 505, March 1996. [Lev86] Nancy G. Leveson, "Software safety: why, what, and 83 how", ACM Computing Surveys (CSUR), 18(2), 1986. [Lev91] [ L u c O l ] [LCS91] [Mc89] [McdOl] [Mig04] [OhfiOl] [Ot02] [Pvp90] [ R k O l ] [ L u t O O ] Nancy G. Leveson, Stephen S. Cha and Timothy J. Shimeall, "Safety Verification of Ada Programs Using Software Fault Trees", IEEE Software archive, 8(4), 1991. Andrea De Lucia, "Program slicing: Methods and applications", In 1 st IEEE International Workshop on Source Code Analysis and Manipulation, pp. 142—149, Florence, Italy, 2001. Nancy G. Leveson, Steven S. Cha, and Timothy J. Shimall, "Safety Verification of Ada Programs using software fault trees", IEEE Software, 8(7):48-59, July 1991. Barton P. Miller and Jong-Deok Choi, " A mechanism for efficient debugging of parallel programs", SIGPLAN Notices, 24(1): 141-150, 1989. John McDermid, "Software Safety: Where's the Evidence?" in Aus Workshop on Industrial Experiemce with Safety Critical Systems and Software, 2001. Andrew McGettrick, https://www.cis.strath.ac.uk/teaching/ug/classes/52.422/stat ic.and.dynamic.analysis.doc (visited June, 2005) Fumiaki Ohata, Kouya Hirose, Masato Fujii, Katsuro Inoue, " A Slicing Method for Object-Oriented Programs Using Lightweight Dynamic Information", Proceedings of the 8th Asia-Pacific Software Engineering Conference, December 2001. Harold Ossher and Peri Tarr, "Multi-Dimensional Separation of Concerns and the Hyper-space Approach", In Software, Architectures and Component Technology (M. Aksit, ed.), 293-323, Kluwer, 2002. David L. Parnas, A. John van Schouwen and Shu Po Kwan, "Evaluation of safety-critical software", Communications of the ACM, 33(6), 1990. Juergen Rilling and Bhaskar Karanth, " A Hybrid Program Slicing Framework", First IEEE International Workshop on Source Code Analysis and Manipulation, pp. 12-23, November 2001. Robyn R. Lutz, "Software engineering for safety: a roadmap", Proceedings of the Conference on The Future of 84 Software Engineering, A C M Press, New York, 2000. [Rob02] [Sfm97] [SMM04] [Soot] [Spin] [Spring] [SP88] [SSHOO] [SysOO] [THS99] Martin P. Robillard and Gail C. Murphy, "Concern graphs: finding and describing concerns using structural program dependencies", Proceedings of the 24th International Conference on Software Engineering, 2002. M.-A.D . Storey, F.D. Fracchia, H.A. Mueller, "Cognitive Design Elements to Support the Construction of a Mental Model during Software Visualization", in 5th International Workshop on Program Comprehension (WPC '97), May 28 -30, 1997 Elias Sinderson, Vish Magapu and Ronald Mak, "Middleware and web services for the collaborative information portal of NASA's Mars exploration rovers mission", Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, pp. 1-17, 2004. SOOT Framework, http://www.sable.mcgill.ca/sooty (visited June 30, 2005) Spin, http://spinroot.com/spin/whatispin.html (visited June 30, 2005) Rod Johnson, http://www.theserverside.com/articles/article.tss?l=SpringF ramework (visited June 30, 2005) Elliot Soloway, Jeannine Pinto, Stan Letovsky, David Littman, Robin Lampert, "Designing Documentation to Compensate for Delocalized Plans", In Communications of the ACM, 31(11):1259- 1267.November 1988. System Safety Handbook, http://www.asv.faa.gov/RISK/SSHandbook/contents.htm. (visited June 30, 2005) Systa Tarja, "Static and Dynamic Reverse Engineering Techniques for Java Software Systems", Ph.D. Dissertation, University of Tamperem Department of Computer and Information Sciences, 2000. Peri Tarr, Harold Ossher, William Harrison, Stanley M . Sutton, Jr. "N Degrees of Separation: Multi-Dimensional Separation of Concerns", Proceedings of the International Conference on Software Engineering (ICSE'99), May 1999. 85 [Tip95] [Ukyi03] [VGJ] [Wei82] [Wei84] [Won05] [Won98] [Xsuds] [Yan04] [Zhang03] Frank Tip, " A Survey of Program Slicing Techniques. Technical", Report CS-R9438, Centrum voor Wiskunde en Informatica (CWI), Amsterdam, The Netherlands, 1994. Fumiaki Umemori, Kenji Konda, Reishi Yokomori, Katsuro Inoue, "Design and Implementation of Bytecode-based Java Slicing System", Third IEEE International Workshop on Source Code Analysis and Manipulation, September 2003. Manual for VGJ , http://www.eng.auburn.edu/departinent/cse/research/graph drawing/manual/vgj manual.html (Visited June, 2005) Mark Weiser, "Programmers Use Slices When Debugging", Communications of the ACM, 25(7):446 -452, July 1982. Mark Weiser, "Program Slicing," IEEE Transactions on Software Engineering, SE-10(4): 352-357, July 1984. Ken Wong, "Untangling Safety-Critical Source Code", PhD thesis, The University of British Columbia, April 2005 Ken Wong, "Looking at Code With Your Safety Goggles On", Ada-Europe'98, June 1998 Telcordia Software Visualization and Analysis Toolsuite (xSuds). http://xsuds.argreenhouse.com (visited June, 2005) Shiping Yang, Nan Sang and Guangze Xiong, "Safety Testing of Safety Critical Software Based on Critical Mission Duration", Proceedings. 10th IEEE Pacific Rim International Symposium on Dependable Computing, 2004. Xiangyu Zhang, Rajiv Gupta and Youtao Zhang, "Precise dynamic slicing algorithms", Proceedings of the 25th International Conference on Software Engineering, 2003. 86 APPENDIX A SLICING TOOL SOURCE CODE ExceptionAdapter.java package com.test; import Java.io.*; class ExceptionAdapter extends RuntimeException { private final String stackTrace; public Exception originalException; public ExceptionAdapter(Exception e) { super(e.toStringO); originalException = e; StringWriter sw = new StringWriter(); e.printStackTrace(new PrintWriter(sw)); stackTrace = sw.toString(); } public void printStackTrace() { printStackTrace(System.err); } public void printStackTrace(java.io.PrintStream s) { synchronized(s) { s.print(getClass().getName() + ": "); s.print(stackTrace); } } public void printStackTrace(java.io. Print Writer s) { synchronized(s) { s.print(getClass().getName() + ": "); s.print(stackTrace); } } public void rethrow() throws Exception { throw originalException; } } GraphNode.java package com.test; import java.util.List; import java.util. ArrayList; * Call Graph Node * Each node represents a InvokeStmt */ class GraphNode { List parents = null; List children = null; String methodsignature = null; public GraphNode(String m) { this.methodSignature = new String(m); //body = getGraphNodeBody(m); //this.parents = new ArrayList(); //this.children = new ArrayList(); } public String toString() { return this.methodSignature; } public List getParents() { return this.parents; } public List getChildren() { return this.children; } /** * @param child must not be null */ public void addChild(GraphNode child) { try{ if (this.children == null) this.children = new ArrayList(); if (! this.children.contains(child)) { this.children.add(child); child. addParent(this); } }catch(Exception e) { //throw new InvalidGraphNodeException("addChild") } } public void removeChild(GraphNode child) { try{ if (this.children.contains(child)) 87 { this.children.remove(child); child.removeParent(this); } }catch(Exception e) { //throw new InvalidGraphNodeException("removeChild") } } /** * @param parent must not be null */ public void addParent(GraphNode parent) { try{ if (this.parents == null) this.parents = new ArrayList(); if (!this.parents.contains(parent)) { this.parents.add(parent); parent.addChild(this); } }catch(Exception e) { //throw new lnvalidGraphNodeException("addParent") } } public void removeParent(GraphNode parent) { try{ if (this.parents.contains(parent)) { this.parents.remove(parent); parent.removeChild(this); } }catch(Exception e) { } } public boolean containsParent(GraphNode node) { try{ if (this.parents.contains(node)) return true; }catch(Exception e) { } return false; } public boolean containsChild(GraphNode node) { try{ if (this.children.contains(node)) return true; }catch(Exception e) { } return false; } } InfoLogger.java package com.test; import java.io.*; public class InfoLogger { private static Print Writer writer = null; static { try{ writer = new PrintWriter(new BufferedWriter(new FileWriter("CF.out"))); }catch(Exception e) { e.printStackTrace(); } } public static synchronized void log(String s) { System.err.println(s); writer.println(s); } public static synchronized void flush() { writer.flush(); writer.closeO; } } Main.java package com.test; import soot.*; public class Main{ public static void main(String[] args) { if (args.length == 0) { System.err.println("Usage: Java Main [options] classname"); . System.exit(0); } 88 /* * add control flow instrumenter */ Pack jtp = PackManager.v().getPack("jtp"); jtp.add(new Transform("jtp.CFInstrumenter", new CFInstrumenter())); soot. Main, main(args); } } Test.java package com.test; import soot.options.*; import soot.toolkits.scalar.*; import soot.*; import soot.util.*; import java.util.*; import java.io.*; import soot.jimple.*; import soot.jimple.internal.*; import soot.toolkits.graph.*; public class Test { Map unitToLocalsAfter; Map unitToLocalsBefore; UnitGraph graph; NormalUnitPrinter printer=null; public Test(String[] args) { try{ G.reset(); System.gc(); Options. v().set_keep_line_number(true); Options. v().set_keep_offset(true); PhaseOptions.v().setPhaseOption("jb","u se-original-names:true"); String className = "com.test.Hello"; SootClass els = Scene. v().loadClassAndSupport(className); cls.setApplicationClassO; Set pkgs = new HashSet(); pkgs.add("com.test"); builder.setlncludingPkgs(pkgs); builder.build(); BackwardSlicing bs = new BackwardSlicing(className,pkgs); Set vars = new HashSet(); vars.add("<com.test.Hello: void outPut(int)>#result"); String sig = "<com.test.Hello: void outPut(int)>"; List units = new ArrayList(); bs.slice(sig,vars,units); PrintWriter writer = null; try { writer = new PrintWriter(new BufferedWriter(new FileWriter("result.txt"))); for(Iterator it = units.iterator();it.hasNext();) { String s = (String)it.next(); writer.println(s); } writer. flush(); writer.close(); }catch(Exception e) { e.printStackTrace(); } Analyzer analyzer = new Analyzer(); analyzer.analyzeCresult.txt","CF.out"); } catch (Exception e) { e.printStackTrace(); } } public static void main(String[] args) { Test flow = new Test(args); } } Analyzer.java /* Analyzer extends the abstract class BodyTransformer, * and implements <pre>internalTransform</pre> method. */ package com.test; import soot.*; import soot.jimple.*; import soot.util.*; CFGBuilder builder = CFGBuilder.newInstance(className); 89 import soot.toolkits.graph.*; import java.util.*; import java.io.*; public class Analyzer { static Map lines = new HashMap(); static Map blocks = new HashMapQ; public void analyze(String staFile, String dynFile) { // store all the lines of the effective blocks Map dynMap = new HashMap(); try{ processInput(staFile,dynFile); }catch(Exception e) { e.printStackTrace(); } //now find the lines if contained in the blocks Iterator bit = blocks.keySet().iterator(); while(bIt.hasNext()) { String method = (String)blt.next(); Set blockSet = (Set)blocks.get(method); Set dynLines = new HashSet(); for(Iterator it = blockSet.iterator();it.hasNext();) { String bNum = (String)it.next(); Body body = Scene. v().getMethod(method).retrieveActiveBod y(); BlockGraph bg = new BriefBlockGraph(body); UnitGraph ug = new BriefUnitGraph(body); List blockList = bg.getBlocks(); Object blockArr[] = blockList.toArray(); // get block's head and tail's Unit Index Block block = (Block)blockArr[Integer.valueOf(bNum).intVal ue()]; Unit head = block. getHead(); Unit tail = block.getTail(); int headlndex=0,taillndex=0; Iterator ult = ug.iterator(); int count = -1; while(uIt.hasNext()) { ++count; Unit unit = (Unit)ult.next(); if (unit == head) { headlndex = count; continue; } if (unit == tail) { taillndex = count; break; } } for (int i = headlndex;i<taillndex+l; i++) { dynLines.add(Integer.toString(i)); } } Set staLines = (Set)lines.get(method); Set shareLines = BackwardSlicing.inBothSet(staLines,dynLines); // store final common lines dynMap. put(method,shareLines); } } public void processInput(String staFile, String dynFile) throws Exception { BufferedReader sReader = new BufferedReader(new FileReader(staFile)); String line = sReader.readLine(); while(line != null) { int index = line.indexOf('#'); String method = line.substring(index); String sNum =line.substring(index+l,line.length()); int num = Integer.valueOf(sNum).intValue(); Set set = (Set)lines.get(method); if (set == null) { set = new HashSet(); } set.add(sNum); lines. put(method,set); line = sReader.readLine(); } BufferedReader dynReader = new BufferedReader( new FileReader(dynFi le)); String _line = dynReader.readLine(); while(_line != null) { int index = _line.indexOf('A'); - String method = Jine.substring(index); 90 int fst = _line.indexOf('#'); int 1st = Jine.lastIndexOf(,/v); String sBlock = _line.substring(fst+l,lst); Set set = (Set)blocks.get(method); if (set == null) { set = new HashSet(); } set.add(sBlock); blocks .put( method, set); line = dynReader.readLine(); } } } BackwardSlicing.java package com.test; import soot.options.*; import soot.toolkits.scalar.*; import soot.*; import soot.util.*; import java.util.*; import java.util.logging.Logger; import soot.jimple.*; import soot.jimple.internal.*; import soot.toolkits.graph.*; class BackwardSlicing { List vars; // variables which needs slicing List units; // unit indexes in the slicing path String var; CFGBuilder cfgBuilder; Set pkgs; Logger log = Logger.getAnonymousLogger(); public BackwardSlicing(String className, Set pkgs) { this.pkgs = pkgs; cfgBuilder = CFGBuilder.newInstance(className,pkgs); } public void init() { //build CFG //TODO: move away cfgBuilder.build(); } * @param map: parameterMap * @param head: parentMethod#index * @param subMethod: subMethod * @param vars: contains the parents' locals([parentMethod#var]+) * TODO: remove all the vars of no mapping */ private void chgVarToChild(String head, String subMethod, Map map,Set vars){ String method = head.substring(0,head.indexOf('#')); Set toRemove = new HashSet(); Set toAdd = new HashSet(); Iterator varlt = vars.iterator(); while(varIt.hasNext()) { String var = (String)varlt.next(); if (var.startsWith(method)) { String varName = \ var. substring( var. indexOf('#')+1); Set subVars = (Set)map.get(head+"#"+varName); boolean mapping = false; if (sub Vars == null) continue; for(Iterator it=subVars.iterator();it.hasNext();) { String sub Var = (String)it.next(); if (subVar.startsWith(subMethod)) { mapping = true; to Add. add(sub Var); } } if (mapping) toRemove.add(var); } } vars.removeAll(toRemove); vars.addAU(toAdd); } /** * @param map: parameterMap * @param head: parentMethod#index * @param subMethod: subMethod * @@param vars: contains the children's locals([subMethod#var]+) * TODO: remove all the vars of no mapping */ private void chgVarToParent(String head, String subMethod, Map map.Set vars){ Iterator itKey = map.keySet().iterator(); String method = head. substring(0,head. indexOf('#')); while(itKey.hasNext()) { String key = (String)itKey.next(); 91 if (key. starts With(head)) { Set values = (Set)map.get(key); Set toRemove = inBothSet(values,vars); if (!toRemove.isEmpty()){ vars.removeAll(toRemove); vars.add(method+key.substring(key.lastlndexOf( '#'))); } } Set toRemove = new HashSet(); Iterator varlt = vars.iterator(); while(varIt.hasNext()) { String var = (String)varlt.next(); if (var.startsWith(subMethod)) { toRemove.add(var); } } vars. remove Al l(toRemove); } // remove all the $vars in $method scope private void removeInScopeVars(Set vars, String method) { Set toRemove = new HashSet(); Iterator varlt = vars.iterator(); while(varIt.hasNext()) { String var= (String)varlt.next(); if (var.startsWith(method)) { toRemove.add(var); } } vars.removeAll(toRemove); } private Set getRhsVarOfUnit(Unit unit) { Set set = null; Iterator it = unit.getUseBoxes().iterator(); try{ set = new HashSet(); while(it.hasNext()) { ValueBox box = (ValueBox) it.next(); Value value = box.getValue(); if (value instanceof Local) { Local 1 = (Local)value; set.add(l.getName()); }else if (value instanceof StaticFieldRef) { StaticFieldRef ref= (StaticFieldRef)value; set.add(ref.getField().getSignature()); }else if (value instanceof InstanceFieldRef) { InstanceFieldRef ref= (InstanceFieldRefJvalue; Value v = ref.getBase(); if (v instanceof Local) { Local 12 = (Local)v; set.add(12.getName()+"#"+ref.getField().getSign ature()); } }else if (value instanceof ArrayRef) { ArrayRef ref = (ArrayRef)value; // TODO: array index should be considered Value v = ref.getBase(); if (v instanceof Local) { Local 12 = (Local)v; set.add(l2.getName()); } } //ThisRef,ParameterRef not considered } }catch(Exception e) { throw new ExceptionAdapter(e); } return set; /** * variable's identidy are decided by both method signature and its name * For static field ref, only by its name(ie.the field's signature) */ private boolean valueInSet(String signature, Value value, Set set) { String key = null; String s = cfgBuilder.getValueVarName(value); // Add for static field ref if(s = null) return false; if (value instanceof StaticFieldRef) \ .{ key = s; }else key = signature+"#"+s; return (set.contains(key)); } 92 static Set inBothSet(Set a, Set _b) { Set a = _a; Set b = _b; Set set = new HashSet(); if ((a == null) && (b == null)) return set; if(a = null) { set.addAll(b); } else if (b == null) { set.addAll(a); }else { for(Iterator it=a.iterator();it.hasNext();) { String s = (String)it.next(); if (b.contains(s)) { set.add(s); } } } return set; } static Set inSetANotB(Set _a, Set _b) { if(_a==null) return null; if (_b == null) return (new HashSet(a)); Set a = _a; Setb = _b; Set set = new HashSet(); for(Iterator it=a. iterator(); it. hasNext();) { String s = (String)it.next(); if (Ib.contains(s)) { set.add(s); } } return set; } // Add Rhs of the unit to vars private void addUseToVars(String method, Unit unit, Set _vars) { Iterator uselt = unit.getUseBoxes().iterator(); while(useIt.hasNext()) { ValueBox box = (ValueBox)uselt.nextQ; Value use = (Value)box.getValue(); String useName = cfgBuilder.getValueVarName(use); if (useName != null) { if (use instanceof StaticFieldRef) { _vars. add(useName); }else { _vars. add(method+"#"+useName); } } } } private boolean inPackages(String method, Set pkgs) { if ((pkgs != null) && (!(pkgs.isEmpty())) ) { Iterator pkglt = pkgs.iterator(); while(pkgIt.hasNext()) { String pkgName = (String)pkglt.next(); if (method.startsWith("<"+pkgName)) { return true; } } } return false; } // trace the calling methods private void traceCaller(String method, Set vars, List list) { // Go up to the methods which called this method. List parents = cfgBuilder.getCallingMethodlnfo(method); // Here are two situations: // 1. Having reached to "main". // 2. No mappings due to package limits if (parents == null) { return; } Iterator parlt = parents. iterator(); while(parIt.hasNext()) { String par = (String)parlt.next(); chgVarToParent(par,method,cfg Builder. getParameterMap(), vars ); 93 String parMethod = par.substring(0,par.indexOf('#')); int index = Integer. valueOf(par. substring(par. indexOf('#') +l)).intValue(); assert index > 0; int prelndex = index-1; SootMethod psm = Scene. v().getMethod(parMethod); Body pb = psm.retrieveActiveBodyO; Objectf] units = pb.getUnits().toArray(); Iist.add(par); back_trace(parMethod,_units,preIndex,vars, list); traceCaller(parMethod,vars,list); chgVarToChild(par,method,cfgBuilder.getParam eterMap(),vars); } } public void slice(String method, Set vars, List list) { backSlice(method, vars, list); traceCaller(method, vars, list); } /** * @param method: method signature * @param vars: variables' names in the form of "signature#varName" * or the form "fieldSignature" for static field * @param list: units traced in the form of "signature#unitlndex" * TODO: For each method, a data dependency (including * ThisRef,ReturnValue,Parameters,static instance Ref)should be cached. * So we only need load the method once. * Note: a global set taking the form(method#parentMethod#parentMethodInde X ) * will be needed for breaking possible calling loops */ public void backSlice(String method, Set _vars, List list) { try{ boolean inPkg = inPackages(method,this.pkgs); if(HnPkg) return; Set vars = _vars; assert (vars != null); assert (method != null); SootMethod sm = Scene. v().getMethod(method); Body body = sm.retrieveActiveBody(); Chain units = body.getUnits(); Unit unit = (Unit)units.getLast(); int index = units.size()-l; back_trace(method, units.toArray(),index, vars, list); }catch(Exception e) { throw new ExceptionAdapter(e); } } private void traceSubMethod(String method, String subMethod, int index, Set vars, List list) { Map map = cfgBuilder.getParameterMap(); Set toAdd = new HashSet(); Iterator iter = vars.iterator(); while(iter.hasNext()) { String s = (String)iter.next(); int idx = s.indexOf('#'); // idx = -1 if it is the static field if (idx ==-1) { continue; } String key = s.substring(0,idx)+"#"+Integer.toString(in dex); key += s.substring(idx); Set subVars = (Set)map.get(key); if((subVars != null) && (!(subVars.isEmpty()))) { toAdd.addAll(subVars); } } vars.addAll(toAdd); list.add(method+"#"+Integer.toString(index)); backSlice(subMethod,vars,list); chgVarToParent((method+"#"+Integer.toString(i ndex)),subMethod,map,vars); } /** * processing the conditional vars */ 94 * processing the conditional vars */ private void singleStepTraceCond(int index, Unit unit, String method, Set vars, List list) { Set condition Vars = (Set)cfgBuilder.unitToVars.get(unit); Set newVars = null; newVars = inSetANotB(condition Vars, vars); if (newVars != null) { vars.addAll(new Vars); } singleStepTrace(index,unit,method,vars,list); } * @param index: the Sunit's index of Smethod * @param unit: current unit * @param method: method signature * @param vars: affected variable names(method_signature#var_name) * @param list: method_signature#unit_index */ private void singleStepTrace(int index, Unit unit, String method, Set vars, List list) { Stmt stmt = (Stmt)unit; if (stmt.containsInvokeExprO) { String subMethod = stmt.getInvokeExpr().getMethod().getSignature( ); boolean inUse = false; boolean inDef = false; boolean inPkgs = inPackages(subMethod,this.pkgs); //GetLHSoftheunit Iterator defBoxIt = unit.getDefBoxes().iterator(); while(defBoxIt.hasNext()) { ValueBox box = (ValueBox) defBoxIt.next(); Value value = box.getValue(); if (valueInSet(method, value, vars)) { inDef = true; break; } } //GetRHSofthe unit Iterator boxlt = unit.getUseBoxes().iterator(); while(boxIt.hasNext()) { ValueBox box = (ValueBox) boxIt.next(); Value value = box.getValue(); if (valueInSet(method, value, vars)) { inUse = true; break; } } if (inDef) { // SsubMethod not in pkgs if (linPkgs) { addUseToVars(method,unit,vars); return; }else { return; } } //Because Jimple convert all the variables into locals first, //parameters passed between parents and children must be the //local variables of the parents. //Note: static instance field can be passed in as globals! if (inUse) { if(linPkgs) { return; Jelse { return; } }// InvokeExpr contains vars }else // this stmt does not contain InvokeExpr { Iterator deflt = unit.getDefBoxes().iterator(); while(deflt.hasNextO) { ValueBox vb = (ValueBox)defIt.next(); Value def = vb.getValue(); String defName = cfgBuilder.getValueVarName(def); if (defName != null) { if (def instanceof StaticFieldRef) { if (vars.contains(defName)) { 95 ValueBox vb = (ValueBox)defIt.next(); Value def = vb.getValue(); String defName = cfgBuilder.getValueVarName(def); if (defName != null) { if (def instanceof StaticFieldRef) { if (vars.contains(defName)) { addUseToVars(method, unit, vars); break; } }else if (vars.contains(method+"#"+defName)) { addUseToVars(method,unit,vars); list.add(method+"#"+Integer.toString(inde x)); break; } } } } /** * find Sunit belongs to which block of $method */ private Block blockOfUnit(String method, Unit unit) { Body body = Scene. v().getMethod(method).retrieveActiveBod y(); BlockGraph bg = new BriefBlockGraph(body); List blocks = bg.getBlocks(); for(Iterator it = blocks.iterator();it.hasNext();) { Block block = (Block)it.next(); Iterator ult = block.iterator(); while(uIt.hasNext()) { Unit u = (Unit)ult.next(); if (u == unit) { return block; } } } assert false; return null; } private void backTrace(int index, String method, Objectf] units, Unit unit, Set vars, List tracedUnits, UnitGraph ug, List usedUnits) { if (usedUnits.contains(unit)) { return; } singleStepTraceCond(index,unit,method,vars,tra cedUnits); usedUnits.add(unit); List preds = ug.getPredsOf(unit); if ((preds == null) || (preds.size() == 0))// first unit return; else{ Iterator pit = preds.iterator(); while(pIt.hasNext()) { Unit pred = (Unit)plt.next(); int ind = getUnitIndex(units,pred); backTrace(ind,method,units,pred,vars,tracedUnit s,ug,usedUnits); } ' } } private int getUnitIndex(Object[] units, Unit unit) { for(int i=0;i<units.length;i++) { if (unit == (Unit)units[i]) • { return i; } } return -1; } /** * Backward trace the Sunits of $method which have indexes equal or less than $_index. * Put all traced $units of this Smethod into SusedUnits in case units loop * Store all the valid traced Sunits into StracedUnits * BUGFIX: should go back through blocks instead of units */ private void back_trace(String method, Object[] units, int _index, Set vars, List tracedUnits) { int index = _index; Unit unit = (Unit)units[index]; List usedUnits = new ArrayListQ; 96 UnitGraph ug = new BriefUnitGraph(Scene.v().getMethod(me thod).retrieveActiveBody()); backTrace(index, method, units,unit,vars,tracedUnits,ug,usedUnits); } CFGBuilder.java package com.test; import soot.options.*; import soot.toolkits.scalar.*; import soot.*; import soot.util.*; import java.util.*; import java.util.logging.Logger; import soot.jimple.*; import soot.jimple.internal.*; import soot.toolkits.graph.*; /** * Control Flow Graph Builder * */ public class CFGBuilder { Map nodelndexer = new HashMap(); private Map nodeMap = new HashMap(); private Map parameterMap = new HashMap(); Map unitToVars = new HashMapO; Map paralndexToLocals = new HashMapO; private String className; private Set packageNames ; private Set graphNodeClasses = new HashSet(); private static CFGBuilder instance = new CFGBuilder(); private Logger log = Logger.getAnonymousLogger(); /** * @param className: main class name * @param pkgs: package names */ private CFGBuilderQ {} public static CFGBuilder newInstance(String. className) { instance.setClassName(className); return instance; } public static CFGBuilder newlnstance(String className, Set pkgs) { instance.setClassName(className); instance. setlncludingPkgs(pkgs); return instance; } public Map getNodeIndexes() { return nodelndexer; } public Map getNodeMap() { return nodeMap; } ' public Map getParameterMap() { return parameterMap; } public void setClassName(String s) { className = s; } /** * @param sig: sub method signature * @return set: parent methods information */ public List getCallingMethodInfo(String sig) { GraphNode node = getGraphNode(sig); if (node == null) return null; return (List)nodelndexer.get(node); } private GraphNode getGraphNode(SootMethod s) { if (s == null) return null; String sig = s.getSignature(); return getGraphNode(sig); } // Change to graph node set private GraphNode getGraphNode(String s) { GraphNode node = null; try{ node = (GraphNode)nodeMap.get(s); 97 if (node == null) { node = new GraphNode(s); nodeMap.put(s,node); } }catch(Exception e) { throw new ExceptionAdapter(e); } return node; } • public void setlncludingPkgs(Set pkgs) { this.packageNames = pkgs; } public Set getIncludingPkgs() { return this.packageNames; } /** * TODO: move into another utility class * Value will be translated to: * 1. local name; * 2. static field signature * 3. instance field name+ field signature * 4. array name * and will not contain constant value */ public String getValueVarName(Value value) { String s = null; try{ if (value instanceof Local) { Local 1 = (Local)value; s = l.getName(); }else if (value instanceof StaticFieldRef) { StaticFieldRef ref = (StaticFieldRef)value; s = ref.getField().getSignature(); }else if (value instanceof InstanceFieldRef) { InstanceFieldRef ref= (InstanceFieldRef) value; Value v = ref.getBaseO; if (v instanceof Local) { Local 12 = (Local)v; s = 12.getName()+"." +ref.getField().getSignature(); } }else if (value instanceof ArrayRef) { ArrayRef ref = (ArrayRef)value; // TODO: array index should be considered Value v = ref.getBase(); if (v instanceof Local) { Local 12 = (Local)v; s = 12.getName(); } } }catch(Exception e) { throw new ExceptionAdapter(e); } return s; } /* private Set getSetFromMap(Unit unit, Map _parameterMap) { Set set = null; try{ set = (Set)_parameterMap.get(key); if (_set == null) { _set = new HashSet(); } }catch(Exception e) { throw new ExceptionAdapter(e); } return _set; } */ private Set getSetFromMap(Object key, Map _parameterMap) { Set _set = null; try{ _set = (Set)_parameterMap.get(key); if (_set == null) { set = new HashSet(); } }catch(Exception e) { throw new ExceptionAdapter(e); } return set; } private void mapLocals(String head, List list, String subHead, Stringf] names) { assert ((names != null) && (list != null)); try{ int size = list.size(); String s = null; Set set = null; 98 assert (list.sizefj == names.length); for(int i=0;i<size;i++) { Value value = (Value)list.get(i); s = getValueVarName( value); if (s !=null) { set = getSetFromMap(head+s,this.parameterMap); _set.add(subHead+names[i]); parameterMap. put(head+s,_set); paraIndexToLocals.put(subHead+Integer.tp String(i),names[i]); } } }catch(Exception e) { throw new ExceptionAdapter(e); } private void mapUnitToVars(Body body) { BlockGraph graph = new BriefBlockGraph(body); Object[] unitArray = body.getUnits().toArray(); String signature = body.getMethod().getSignature(); int size = graph.getBlocks().size(); int[] blocks = new int[size]; for(int i=0;i<size;i++) { blocks[i] = 0; } Set vars = new HashSet(); List heads = graph.getHeads(); Iterator it = heads.iterator(); while (it.hasNext()) { Block block = (Block)it.next(); mapBlockToVars(block, vars, unitArray,signature,blocks); } } /** * @param block: all units of the block are in the scope of vars. * @param vars: conditional variables'set * @param unitArray: array of all units in the method * @param sig: signature of method which contains block * @param blocks: indicate whether a block been processed. */ private void mapBlockToVars(Block block, Set vars, Object[] unitArray, String sig, int[] blocks) { int base = 0; Unit head = block.getHead(); Set vars = new HashSet(); vars.addAll(_vars); int blocklndex = block.getIndexInMethod(); if (blocks[blockIndex] ==1) return; // map the block's unit to vars if ((vars != null) && (!(vars.isEmpty()))) { for(Iterator it=block. iterator();it.hasNext();) { Unit u = (Unit)it.next(); Set set = getSetFromMap(u,this.unitToVars); set.addAU(vars); this.unitToVars.put(u, set); } } blocks[blocklndex] = 1; if (block.getSuccs().size() == 0) return; Stmt tail = (Stmt)block.getTail(); Value key=null; if (tail instanceof IfStmt) { Value condition = ((IfStmt)tail).getCondition(); Set varNames = new HashSet(); Iterator conlt = condition. getUseBoxes().iterator(); while(conIt. hasNext()) { ValueBox cvb = (ValueBox)conIt.next(); Value cv = cvb.getValue(); String varName = getValueVarName(cv); if (varName != null) varNames.add(sig+"#"+varName); } Set newVars = new HashSet(); newVars.addAll(vars); new Vars.addAll(varNames); Objectf] succs = block.getSuccs().toArray(); if (succs.length == 1) { mapBlockToVars((Block)succs[ 0],newVars,unitArray,sig,blocks ); return; } Block blockO = (Block)(succs[0]); Block blockl = (Block)(succs[l]); 99 if (block0.getSuccs().contains(blockl)) { Set set2 = new HashSet(); set2.addAll(vars); mapBlockToVars(blockl,set2,unitArray,sig,bloc ks); mapBlockToVars(blockO,newVars,unitArray,sig ,blocks); }else if(blockl.getSuccs().contains(blockO)) { Set set2 = new HashSet(); set2.addAll(vars); mapBlockToVars(blockO,set2,unitArray,sig,bloc ks); mapBlockToVars(blockl,newVars,unitArray,sig ,blocks); }else { mapBlockToVars(blockO,newVars,unitArray,sig ,blocks); mapBlockToVars(blockl,newVars,unitArray,sig ,blocks); } }else if (tail instanceof TableSwitchStmt) { key = ((TableSwitchStmt )tail).getKey(); }else if (tail instanceof LookupSwitchStmt) { key = ((LookupSwitchStmt)tail).getKey(); } // tail is TableSwitchStmt or LookupSwitchStmt if (key !=null) { String varName = getValueVarName(key); Set newVars = new HashSet(); newVars.addAll(vars); if (varName != null) newVars. add(sig+"#"+varName); for(Iterator succIt=block.getSuccs().iterator();succIt.hasNext ();) { Block block = (Block)succIt.next(); mapBlockToVars(_block,newVars,unitArray,sig ,blocks); } } key = null; } * FIXME: use UnitGraph.getTails() */ private Set getReturnVars(Body body) { Set set = new HashSet(); try{ assert (body != null); String s = body.getMethod().getSignature(); Iterator it = body.getUnits().iterator(); while(it.hasNext()) { Stmt stmt = (Stmt)it.next(); if (stmt instanceof ReturnStmt) { ReturnStmt rs = (ReturnStmt)stmt; Value value = rs.getOp(); String str = getValueVarName(value); if (str != null) set.add(s+"#"+str); } } }catch(Exception e) { throw new ExceptionAdapter(e); } return set; } /** * @param s: "method#varname" * @return set: "varname" */ private Set getVarNames(Set s) { Set set = new HashSet(); try{ Iterator it = s.iterator(); while(it.hasNext()) { String str = (String)it.next(); set.add(str.substring(str.indexOf('#')+l)); } }catch(Exception e) { throw new ExceptionAdapter(e); } return set; } public void build() { try{ SootClass clazz = Scene. v().loadClassAndSupport(this.className) clazz.setApplicationClass(); Chain chain = Scene.v().getClasses(); for(Iterator it=chain.iterator();it.hasNext();) 100 { SootClass sc = (SootClass)it.next(); if (packageNames.contains(sc.getJavaPackageNam e())) { graphNodeClasses.add(sc); } } for(Iterator it = graphNodeClasses.iterator();it.hasNext();) { SootClass sc = (SootClass)it.next(); List methods = sc.getMethods(); for (Iterator iter = methods.iterator();iter.hasNext();) { SootMethod sm = (SootMethod)iter.next(); String methodSignature = sm.getSignature(); GraphNode node = getGraphNode(methodSignature); Body body = sm.retrieveActiveBody(); mapUnitToVars(body); Chain units = body.getUnits(); int index = -1;//FIXME: index is of "units" or units.innerchain? List indexes = null; for(Iterator iter2 = units.iterator();iter2.hasNext();) { Unit unit = (Unit)iter2.next(); index++; Stmt stmt = (Stmt)unit; if (stmt.containsInvokeExprO) { InvokeExpr expr = stmt.getInvokeExpr(); SootMethod subMethod = expr.getMethod(); Type type = subMethod.getReturnType(); boolean isVoid = false; if (type instanceof VoidType) isVoid = true; int defLen = unit.getDefBoxes().size(); boolean hasReturnValue = defLen>0?true:false boolean islnstance = ! (subMethod.isStatic()); String subSig = subMethod.getSignature(); int localCount = subMethod. getParameterCount(); String this = null,_This=""; Set set = null; List locals = expr. get Args (); boolean noIndexMapping = false; GraphNode subNode = getGraphNode(sub Method); node.addChild(subNode); indexes = (List)nodelndexer.get(subNode); if (indexes == null) { indexes = new ArrayList(); } String key = methodSignature+"#"+new Integer(index); indexes.add(key); nodeIndexer.put(subNode,indexes); // Add for paralndexToLocals // so we don't need load sub method // Map return value if (lisVoid) { if (hasReturnValue) { Set retVars = (Set)paraIndexToLocals.get(subSig+"#" +Integer.toString(-2)); String ret = null; if((retVars != null )&& !(retVars.isEmpty())) { ValueBox vbox = (ValueBox)unit.getDefBoxes().get(0); Value value = _vbox.getValue(); ret = getValueVarName(_value); assert ret != null; String var = key+"#"+ret; set = getSetFromMap(var,this. parameterMap); for (Iterator retVarlt = retVars.iterator();retVarIt.hasNext();) { String _retVar = (String)retVarIt.next(); set. add(subS ig+"#"+_ret Var); } parameterMap.put(var,set); }else { noIndexMapping = true; } } } // Map ThisRef if (islnstance) 101 { this = (String)paraIndexToLocals.get(subSig+"# "+Integer.toString(-l)); if (this Nnull) { InstancelnvokeExpr iie = (InstancelnvokeExpr)expr; Value base = iie.getBase(); if (base instanceof Local) { _This = ((Local)base).getName(); assert This != null; String str = key+"#"+_This; set = getSetFromMap(str,this.parameterMap); set.add(subSig+"#"+_this); parameterMap.put(str,set); } }else { noIndexMapping = true; } } // Map locals { int size = _locals.size(); String s = null; Set set = null; String head = key+"#"; String subHead = subSig+"#"; for(int i=0;i<size;i++) { Value value = (Value)locals.get(i); s = getValueVarName(value); if (s ==null) continue; String name = (String)paraIndexToLocals.get(subHead+I nteger.toString(i)); if (name != null) { set = getSetFromMap(head+s,this.parameterMap); _set.add(subHead+name); parameterMap.put(head+s,_set); }else { noIndexMapping = true; } } } nomapping: if (noIndexMapping) { if (!subMethod.isConcrete()) continue; Body subBody = subMethod.retrieveActiveBodyO; // Get the locals of the sub method Stringf] locals = new StringflocalCount]; for(int i=0;i<localCount;i++) { locals[i] = subBody. getParameterLocal(i).getName(); } // Map ThisRef if (islnstance) { this = subBody.getThisLocal(). getN ame(); InstancelnvokeExpr iie = (InstancelnvokeExpr)expr; Value base = iie.getBase(); if (base instanceof Local) { This = ((Local)base).getName(); String str = key+"#"+_This; set = getSetFromMap(str,this.parameterMap); set.add(subSig+"#"+_this); paraIndexToLocals.put(subSig+"#"+Int eger.toStrin g(-l),_this); parameterMap.put(str,set); } } mapLocals(key +"#",_locals,sub Sig+"#",locals); // Map return value String ret = null; if(lisVoid) { Set _rets = getReturnVars(subBody); if (hasReturn Value) { ValueBox vbox = (ValueBox)unit.getDefBoxes().get(0); Value value = _vbox.getValue(); ret = getValueVarName(_value); assert ret != null; String var = key+"#"+ret; set = getSetFromMap(var,this.parameterMap); set.addAll(_rets); parameterMap.put(var,set); } paraIndexToLocals.put(subSig+"#"+Int eger.toString(-2), getVarNames(_rets)); } 102 } } } } } }catch(Exception e) { throw new ExceptionAdapter(e); } } public void testNodeIndex() { try{ Set pkgs = new HashSet(); pkgs.add("com.test"); setlncludingPkgs(pkgs); build(); Set keys = nodeIndexer.keySet(); Iterator it = keys.iterator(); while(it.hasNext()) { GraphNode node = (GraphNode)it.next(); } }catch(Exception e) { throw new ExceptionAdapter(e); } } public void testAHMaps() { try{ //Set pkgs = new HashSet(); //pkgs.add("com.test"); //setlncludingPkgs(pkgs); build(); //Test graph node map Set keys = nodeIndexer.keySet(); Iterator it = keys.iterator(); while(it.hasNext()) { GraphNode node = (GraphNode)it.next(); } Set params = parameterMap.keySet(); Iterator pit = params.iterator(); while(pit.hasNext()) { String s = (String)pit.next(); } }catch(Exception e) { throw new ExceptionAdapter(e); } } } CFI nstru menter.java /* CFInstrumenter extends the abstract class BodyTransformer, * and implements <pre>internalTransform</pre> method. */ package com.test; import soot.*; import soot.jimple.*; import soot.util.*; import soot.toolkits.graph.*; import java.util.*; public class CFInstrumenter extends BodyTransformer { /* some internal fields */ static SootClass InfoLogger; static SootMethod log, flush; static { InfoLogger= Scene. v().loadClassAndSupport("com. test. I nfoLogger"); log = InfoLogger.getMethodByName("log"); flush = InfoLogger.getMethod("void flush()"); } protected void internalTransform(Body body, String phase, Map options) { SootMethod method = body.getMethod(); Chain units = body.getUnits(); Iterator stmtlt = units.snapshotIterator(); System.out.println("instrumenting method : " + method.getSignature()); BriefBlockGraph bbg = new BriefBlockGraph(body); List blocks = bbg.getBlocks(); Iterator it = blocks.iterator(); while(it.hasNext()) { Block block = (Block)it.next(); Stmt stmt = (Stmt)block.getHead(); String s = method.getSignature() + "A" + block.toShortStringO + "A" + stmt.toString(); InvokeExpr incExpr= Jimple. v().newStaticInvokeExpr(log, StringConstant.v(s)); Stmt incStmt = Jimple. v().newInvokeStmt(incExpr); units.insertBefore(incStmt, stmt); } String signature = method.getSubSignature(); boolean isMain = signature.equals("void main(java.lang.String[])"); 103 // re-iterate the body to look for return statement if (isMain) { stmtlt = units.snapshotIterator(); while (stmtIt.hasNext()) { Stmt stmt = (Stmt)stmtlt.next(); if ((stmt instanceof ReturnStmt) ||(stmt instanceof ReturnVoidStmt)) { InvokeExpr reportExpr= Jimple. v().newStaticInvokeExpr(flush); Stmt reportStmt = Jimple. v().newInvokeStmt(reportExpr); units.insertBefore(reportStmt, stmt); } } } } } APPENDIX B RDPS SOURCE CODE A T C C I i e n t . j a v a package com.atc; public class AtcClient { AtcClient(String fName) { RadarNerwork network = new RadarNetwork(); Radar radar_97 = new Radar("97"); Radar radar_96 = new Radar("96"); Radar radar_20 = new Radar("20"); Radar radar_18 = new Radar("18"); radar_97.Register(network); radar_96.Register(network); radar_20.Register(network); radar_l 8.Register(network); network.Process(fName); } public static void main(String[] av) { if (av. length != 2) { System.out.println("Usage:AtcClient script_file :name: "+av[0]); } AtcClient client = new AtcClient(av[0]); } } T r a c k . j a v a package com.atc; public class Track { public Track(int _id) { source = null; modeA=null; modeC=null; bearing=0.0; speed=0.0; position = new RadarPosition(0.0,0.0); positionLL = new GeograPosition(0.0,0.0); label=0; id = id; } public void RegisterTimer() { TimeManager timeManager = TimeManager.Instance(); timeManager.AddTimer(this); } public void Notify(int lbl) { DataBlockMgr dbMgr = DataBlockMgr.Instance(); dbMgr.DisplayTrack(this,lbl); } String source = null; String modeA = null; String modeC = null; double bearing = 0; double speed = 0; long observationTime = 0; RadarPosition position = null; GeograPosition positionLL = null; int id;// TRACK id int label; //"0"-represents tentative track, "1"-represents formal track long updateTime = 0; //time of last update long startTime = 0;// "real" time origin • public String toString() { String s = "Source: "+source+" id:"+id +" mode A:"+modeA+" mode C:"+modeC+" observation time:"+Long.toString(observationTime) +" bearing: "+bearing+" speed: "+speed+" aircraft latitude:" +positionLL.latitude +" longitude:"+positionLL.longitude +" local east distance: "+position.east+" north distance: "+position.north; return s; } public static void main(String[] args) { Track ra=new Track(0); System.out.println(ra); } } 105 A t c C o n s t a n t s . j a v a package com.ate; public final class AtcConstants { public static final double PI = 3.14159; // The earth's radius,in meters public static final long RADIUS = 63781000; // general constants // merters per nautical mile public static final int MPN = 1852; // meters per foot public static final double MPF = 0.3048; // feet per nautical mile public static final int FPN = 6080; // define radian unit public static final double RU = (PI/180); // Track Object Expiry VSP timeout in second public static final int T O E V S P = 10; // Track Update Expiry VSP timeout in second public static final int TUEJVSP = 7; // Standard Pressure Setting public static final double SPS = 29.92; // Feet Per Inch- Every inch in pressure corresponds to 1000 feet in height public static final int FPI = 1000; // Maximum lateral displacement VSP public static final int MLD_VSP = 3000; // Minimum speed VSP in m/s public static final double MIN_SP_VSP = -50.0; // Maximum speed VSP public static final double M A X S P V S P = 50.0; // Maximum vertical displacement VSP in lOOfeet public static final double MAX_V_VSP = 10.0; // Define the maximum speed public static final double MAX_SP = 10000; // Graphical Object Expiry VSP timeout in second public static final int G O E V S P = 10; // create the aircraft option public static final int AIRCRAFTOPT = 1; // create text block option public static final int TEXTBLOCKOPT = 2; // Maintainable maximum GRAD number public static final int M A X G R A D N U M = 500; // Each radar antenna will rotate at a constant rate // Logical Scan time - typically about 6 seconds public static final double LS_TIME = 6; // Logical Scan range - Each source has a limited range, e.g., 90 miles public static final double L S R A N G E = 90; // Mode C Header public static final String MCH ="FL"; // Mode C value minimum and maximum public static final int M C V M I N = 12; public static final int M C V M A X = 1267; // Mode C value unit: 100 feet public static final int M C V U N I T = 100; // Azimuth in angle to North 0-360 public static final double AZ_MIN = 0; public static final double AZ_MAX = 360; // slant range in nautical miles public static final double SRMIN = 0; public static final double SR_MAX = 1000; in the input file // define the data public static final "source"; public static final "mode_a"; public static final "mode_c"; public static final "azimuth"; public static final "slantrange"; public static final public static final "longitude"; public static final public static final "position"; public static final int T R A C C U P D A T E T = 1 // track create update tag public static final int T R A C D U P D A T E T = 2;// track delete tag public static final int TRACJVIUPDATET = 3;// track move update tag public static final boolean CAS = false; public static final double CAS_VALUE = 30.0; public static final boolean SOU_HEM = false; RADA SOURCE= RADA MA = RADA _MC = RADA AZ = RADA .SR = RADA LA = "latitude RADA" ~LO = RADA TI = "time"; RADA POS = } C o r r e l a t o r . j a v a package com.atc; import java.util.*; import java.util.logging.*; public class Correlator { 106 private Correlator() { tracks = new Vector(); } public static Correlator Instance() { if (instance = null) { instance = new Correlator(); } return instance; } public void Correlate(RadarReport rep) { boolean bFormal = false; adjmodc(rep); if (tracks = null) return; int size = tracks.size(); for(int sz=0;sz<size;sz++) { Track track = (Track)tracks.get(sz); if ((meet_mod_a_cri(rep,track)= 0) && (meet_prox_cri(rep,track)=0)) { gen_form_track(rep,track); if (track.label = 0) { track.label = 1; //Add update and time out timer track.RegisterTimer(); track.Notify(AtcConstants.TRAC_C_UPDATE_T ); Jelse { track.Notify(AtcConstants.TRAC_M_UPDATE_T ); } bFormal = true; break; } } if(!bFormal) { Track pTrack = new Track(trackld); gen_ten_track(pTrack,rep); tracks.addElement(pTrack); } } private void adj_mod_c(RadarReport ra) { int dis=0; int mc = 0; try { String mode_c = ra.modeC.substring(3);/* strip "FL" */ mc= Integer.parseInt(mode_c); } catch (Exception e) { System. out.println(e); } if(AtcConstants.CAS) { dis = (int)(AtcConstants.CAS_VALUE -AtcConstants.SPS)* AtcConstants.FPI/AtcConstants.MCVUNIT; } mc += dis; ra.modeC = Integer.toString(mc); } private int gen_ten_track(Track pdes, RadarReport rep) { Logger logger = Logger.getAnonymousLogger(); logger.log(Level.INFO,''gen_ten_track\n"); pdes.source = rep.source; if ((rep.modeA != null) && (!rep.modeA.equals(""))) pdes.modeA = rep.modeA; pdes.modeC = rep.modeC; pdes.bearing = 0; pdes.speed = 0; pdes.observationTime = rep.observationTime; pdes.startTime = System.currentTimeMillis(); pdes.position = rep.position; pdes.positionLL =rep.positionLL; pdes.id = GetTrackId(); pdes.label = 0; return 0; } private int gen_form_track(RadarReport ra,Track tr) { Logger logger = Logger. getAnonymousLogger(); 107 logger.log(Level.iNFO,"Correlator::gen_form_trac k-source:" +ra.source+"\n"); tr.source = ra.source; if((ra.modeA != null) && (ra.modeA != "")) tr.modeA = ra.modeA; tr.modeC = ra.modeC; tr.updateTime = ra.observationTime; tr.bearing = get_bea(ra.position.east -tr.position.east, ra.position.north - tr.position.north); tr.speed = get_sp(tr.position, Integer.parseInt(ra.modeC),tr.observationTime, ra.position, Integer.parselnt(ra.modeC), ra.observationTime); tr.position.north = ra.position.north; tr.position.east = ra.position.east; tr.positionLL = ra.positionLL; return 0; } private double get_bea(double ea, double no) { return (Math.atan2(ea,no)/AtcConstants.RU); } private int meet_mod_a_cri(RadarReport ra, Track tr) { if ((ra.modeA = null) || (ra.modeA = "")) return 0; if (ra.modeA.equals(tr.modeA)) return 0; return -1; } private int meet_prox_cri(RadarReport ra, Track tr) { return 0; } private int meet_alt_cri( RadarReport pra, Track PO { int ramc = Integer.parselnt(pra.modeC); int tr_mc = Integer.parselnt(pt.modeC); if ((ra_mc = 0) ||(tr_mc = 0) |[(Math.abs(ra_mc - tr_mc)< AtcConstants.MAX_V_VSP)) return 0; return -1; } private double get_sp(RadarPosition si,int al, long tl, RadarPosition s2,int a2,long t2) { double dis, l_dis,w_dis,h_dis,t; l_dis = si.east - s2.east; wdis = si.north - s2.north; h_dis = (al-a2)*AtcConstants.MCV_UNIT*AtcConstants.MP F; dis = Math.sqrt(l_dis*l_dis +w_dis*w_dis + h_dis*h_dis); t = Math.abs((t2-tl)); if (t <= 0) /* this should not happen in real situation */ return (AtcConstants.MAX_SP_VSP-l); /* only for debug use */ return (dis/t); } private int GetTrackId() { return trackld++; } private static Correlator instance = null; private static int trackld = 0; private Vector tracks = null; } D a t a B l o c k M g r . j a v a package com.atc; import java.util.*; public class DataBlockMgr { public static DataBlockMgr Instance() { if (instance = null) { instance = new DataBlockMgr(); } return instance; } 108 private DataBlockMgr() { dbs = new Hashtable(); viewOrigin = new GeograPosition(32.0,43.0); latScope = 5.0; lonScope = 5.0; } public void DisplayTrack(Track track,int lbl) { GeograPosition pos = track.positionLL; DataBlock pdb = GetDataBlock(track); if(pdb = null) { pdb = new DataBlock(track.id); dbs.put(track,pdb); } if (!InScope(pos)) { if (lbl = AtcConstants.TRACDUPDATET) { dbs.remove(track); } else if (lbl == AtcConstants.TRAC_C_UPDATE_T) { }else if (lbl = AtcConstants.TRACMUPDATET) { } return; } else { pdb.position.north =(track.positionLL.latitude -viewOrigin.latitude+latScope) /(2*latScope); pdb.position.east =(track.positionLL.longitude -viewOrigin.longitude+lonScope) /(2*lonScope); if (lbl = AtcConstants.TRACDUPDATET) { pdb.Remove(); dbs.remove(track); }else if (lbl = AtcConstants.TRAC_C_UPDATE_T) { pdb.Create(); }else if (lbl = AtcConstants.TRACMUPDATET) { pdb.Update(); } } } public GeograPosition GetViewOrigin() { return viewOrigin; } public void SetViewOrigin(GeograPosition pos) { viewOrigin.latitude = pos.latitude; viewOrigin.longitude = pos.latitude; ShowAllTracks(); } public void SetLatitudeScope(double scope) { latScope = scope; ShowAllTracks(); } public double GetLatitudeScope() { return latScope; } public void SetLongitudeScope(double scope) { lonScope = scope; ShowAllTracks(); } public double GetLongitudeScope() { return lonScope; } public boolean InScope(GeograPosition pos) { if ((pos.latitude>viewOrigin.latitude-latScope) &&(pos.latitude<viewOrigin.latitude+latScope) &&(pos.longitude>viewOrigin.longitude-lonScope) &&(pos.longitude<viewOrigin.longitude+lonScop e)) return true; return false; } //Track& GetTrack(DataBlock& db); public DataBlock GetDataBlock(Track tr) { try{ return ((DataBlock)dbs.get(tr)); }catch(Exception e) { System.out.println(e); return null; } } 109 private void ShowAllTracks() { for (Enumeration e = dbs.keys(); e.hasMoreElements();) { Track track=(Track)e.nextElement(); if (InScope(track.positionLL)) { DataBlock db = (DataBlock)dbs.get(track); db.position.north =(track.positionLL.latitude -viewOrigin.latitude+latScope) /(2*latScope); db.position.east =(track.positionLL.longitude -viewOrigin. longitude+lonScope) /(2*lonScope); db.Update(); } } } private static DataBlockMgr instance; private Hashtable dbs = null; private GeograPosition viewOrigin = null; private double latScope = 0.0;//unit "degree" private double lonScope = 0.0; } G e o g r a P o s i t i o n . j a v a /* * Created on 2004-4-4 * To change the template for this generated file go to * Window&gt;Preferences&gt;Java&gt;Code Generation&gt;Code and Comments */ package com.atc; public class GeograPosition { public double latitude = 0.0; public double longitude = 0.0; public GeograPosition(double la,double lo) { latitude = la; longitude = lo; }; public GeograPosition() { latitude = 0.0; longitude = 0.0; }; } R a d a r . j a v a package com.atc; import java.util.logging. *; public class Radar { Radar(String source) { this.source = source; } public void Register(RadarNetwork net) { radarNetwork = net; radarNetwork.RegisterRadar(this); } public void Process(RadarReturn ret) { double gr,f,f2,f3,nr,er; String mode_c = ret.modeC.substring(3);/* strip "FL" */ int mc= Integer.parselnt(modec); GeograPosition netPosition = radarNetwork. GetPosition(); if(mc = 0) { gr = ret.slantRange * 1.0008 - 0.22; }else { f = (double)mc * AtcConstants.FPI; f2 = f / AtcConstants.FPN; f3 = f2 * f2; gr = Math.sqrt( ret.slantRange * ret.slantRange - f3);/* ground range in NM */ } nr = gr * Math.cos(ret.azimuth * AtcConstants.RU); er = gr * Math.sin(ret.azimuth * AtcConstants.RU); RadarPosition rada_dis=GefRadarDistance(ret.sourcePosition); ret.position.north = (rada_dis.north + nr)*AtcConstants.MPN; ret.position.east = (rada_dis.east + er)*AtcConstants.MPN; RadarReport report = new RadarReportQ; 1 10 report, source = ret.source; report, azimuth = ret.azimuth; report. slantRange = ret.slantRange; report.modeA = ret.modeA; report.modeC = ret.modeC; report. observationTime = ret.observationTime; report.sourcePosition = ret.sourcePosition; report.position = ret.position; report.positionLL = ll_pos(report.position); Logger logger = Logger.getAnonymousLogger(); logger.log(Level.INFO,"report.la: "+report.positionLL.latitude +" lo: "+report.positionLL.longitude+"\n"); Correlator correlator = Correlator.Instance(); correlator.Correlate(report); } private RadarPosition GetRadarDistance(GeograPositionpos) { RadarPosition position = new RadarPosition(); GeograPosition netPos = radarNetwork.GetPosition(); RadarPosition post = Mercator(netPos); RadarPosition pos2 = Mercator(pos); position.east = pos2.east - pos Least; position.north = pos2.north - pos2.north; return position; } private GeograPosition ll_pos(RadarPosition pos) { GeograPosition p = new GeograPosition(); double la,lo, tmp, tc,d; /* * if we use double * get BUG ! */ GeograPosition ell = radarNetwork.GetPosition(); la = cll.latitude * AtcConstants.RU; lo = ell.longitude * AtcConstants.RU; tmp = (pos.north * pos.north + pos.east * pos.east); tmp = Math.sqrt(tmp); d = tmp/AtcConstants.RADIUS; tc = Math.atan2(pos.east, pos.north); p.latitude = Math.asin(Math.sin(la)*Math.cos(d) +Math.cos(la)*Math.sin(d)*Math.cos(tc)); if (Double.compare(Math.cos(p.latitude),0) == 0) p.longitude = lo; else p.longitude = mod(lo -Math.asin(Math.sin(tc)*Math.sin(d) /Math.cos(p.latitude))+AtcConstants.PI,2*AtcCon stants.PI) -AtcConstants.PI; p.latitade = p.latitude/AtcConstants.RU; p.longitude = p.longimde/AtcConstants.RU; retarn p; } private double mod(double y, double x) { return (y - x*(int)(y/x)); } private RadarPosition Mercator(GeograPosition P) { RadarPosition pp = new RadarPosition(); double l,lo,e,n; // if we are on southern hemisphere if (AtcConstants.SOUHEM) 1 = p.latitude * AtcConstants.RU * (-1); else 1 = p.latitude * AtcConstants.RU; lo = p.longitude * AtcConstants.RU; e = AtcConstants.RADiUS * lo; n = AtcConstants.RADiUS * Math.log(Math.tan(AtcConstants.PI/4 +1/2)); pp.east = e; pp.north = n; return pp; } private RadarNetwork radarNetwork; String source; } R a d a r N e t w o r k . j a v a ^ package com.atc; 1 11 private Hashtable radarMap = null; RadarNetwork(GeograPosition p) { position = p; radarMap = new Hashtable(); } RadarNetwork() { position = new GeograPosition(32.0,43.0); radarMap = new Hashtable(); } public void RegisterRadar(Radar radar) { String so = radar.source; radarMap.put(so, radar); } public void Process(String fName) { try { BufferedReader fs = new BufferedReader(new FileReader(fName)); String line = null; int count=0, init = 0; RadarReturn radarReturn = new RadarReturn(); while(fs != null) { line = fs.readLine(); if(line!=null) line = line.trim(); else return; if (line.charAt(O) =='#') { if (init !=0) { Dispatch(radarReturn); count ++; } else { init= 1; } continue; } int tok = line.indexOf('='); if(tok==-l) continue; String name = line.substring(0,tok); String value = line.substring(tok+l); if (name.equals(AtcConstants.RADASOURCE)) { radarReturn.source = value; }else if (name.equals(AtcConstants.RADAMA)) { radarReturn.modeA = value; }else if (name.equals(AtcConstants.RADA_MC)) { radarReturn.modeC = value; }else if (name.equals(AtcConstants.RADA_AZ)) { radarReturn.azimuth Double, parse Double! tic); }else if (name.equals(AtcConstants.RADA_SR)) { radarReturn. slantRange =' Double.parseDouble(value); }else if (name.equals(AtcConstants.RADA_TI)) { StringTokenizer st = new StringTokenizer( value,":"); Calendar now = Calendar.getlnstance(); now.set(Calendar.HOUR,Integer.valueOf(st.nextT oken()).intValue()); now.set(Calendar.MINUTE,Integer.valueOf(st.nex tToken()).intValue()); now.set(Calendar.SECOND,Integer.valueOf(st.nex tToken()).intValue()); radarReturn.observationTime = now.getTimeInMillis(); }else if (name.equals(AtcConstants.RADA_LA)) { radarReturn.sourcePosition.latitude = Double.parseDouble(value); }else if (name.equals(AtcConstants.RADALO)) { radarReturn.sourcePosition.longitude = Double.parseDouble( value); } } }catch(Exception e) { System.out.println(e); } 112 } public void SetPosition(double lat, double log) { position.latitude = lat; position.longitude = log; } public GeograPosition GetPosition() { return position; } // void SetTimeOrigin(char* time); private void Dispatch(RadarReturn ret) { String so = ret.source; if (radarMap.containsKey(so)) { Radar radar = (Radar)radarMap.get(so); radar .Process(ret); } } private GeograPosition position; } RadarPosition.Java package com.atc; public class RadarPosition { public double east = 0.0; public double north = 0.0; RadarPosition(double ea.double no) { east = ea; north = no; }; RadarPosition() { east = 0.0; north = 0.0; } } RadarReport.java package com.atc; public class RadarReport extends RadarReturn { GeograPosition positionLL = null;// Aircraft geographic position RadarReport() { super(); positionLL = null; } } RadarReturn.java package com.atc; public class RadarReturn { public RadarReturn() { sourcePosition = new GeograPosition(32.0,43.0); position = new RadarPosition(0.0,0.0); } String source=null; double azimuth=0.0; // azimuth - angle from true north double slantRange=0.0; // slant range-in Nautical miles String modeA=null; // Mode A SSR code - a 12-bit code String modeC=null; long observationTime=0; GeograPosition sourcePosition=null; RadarPosition position=null; public String toString() { String s = "Source: "+source+" azimuth: "+Double.toString(azimuth) +" slant range:"+Double.toString(slantRange) +" mode A:"+modeA+" mode C:"+modeC +" observation time:" + Long.toString(observationTime) +" radar latitude:"+ sourcePosition.latitude +" longitude:" + sourcePosition.longitude +" local east distance:" + position.east + " north distance:" + position.north; return s; } public static void main(String[] args) { RadarReturn ra=new RadarReturn(); System.out.println(ra); } } 113 T e x t D i s p l a y . j a v a package comatc; public class TextDisplay { TextDisplayO { width = 1024; height = 768; } TextDisplay(int w,int h) { width = w; height = h; } public void Create(DataBlock pDB) { int h=(int)(pDB.GetPosition().north * height); int w=(int)(pDB.GetPosition().east * width); System.out.println("Create aircraft "+pDB.GetId() +" at "+w+" ,"+h+" !\n"); } public void Update(DataBlock pDB) { int h=(int)(pDB.GetPosition().north * height); int w=(int)(pDB.GetPosition().east * width); System.out.println("Update aircraft "+pDB.GetId() +" at "+w+" ,"+h+" ! V ) ; }; public void Remove(DataBlock pDB) { int h=(int)(pDB.GetPosition().north * height); int w=(int)(pDB.GetPosition().east * width); System.out.println("Remove aircraft "+pDB.GetId() +" at "+w+" ,"+h+" !\n"); }; public void SetHeight(int h) { height = h; } public void SetWidth(int w) { width = w; } private int width;/* display width in "pixel" */ private int height;/* display height in "pixel" */ } T i m e M a n a g e r . j a v a package com.atc; import java.util.*; public class TimeManager { public static TimeManager Instance() { if (instance = null) { instance = new TimeManager(); } return instance; } public void AddTimer(Track track) { Timer updateTimer = new Timer(); UpdateTask updateTask = new UpdateTask(); updateTask.track = _track; updateTimer.schedule(updateTask, AtcConstants.TUE_VSP* 1000); timerTable.put(_track, updateTimer); Timer expTimer = new Timer(); ExpireTask expireTask = new ExpireTask(); expireTask.track = track; expireTask. timer = expTimer; expTimer.schedule(expireTask, AtcConstants.TOE_VSP* 1000); } public void RemoveTimer(Track track) { } private static TimeManager instance = null; private Hashtable timerTable = null; private TimeManager() { timerTable = new Hashtable(); } class UpdateTask extends TimerTask { Track track = null; public void run() { track.Notify(AtcConstants.TRAC_M_UPDATE_T ); } } class ExpireTask extends TimerTask { 1 14 Track track = null; Timer timer = null; public void run() { if (track != null) { long now = System.currentTimeMillis(); if ((now - track. startTime)>(track. updateTime - track.observationTime + AtcConstants.TOE_VSP)) { if (timer != null) timer.cancel(); Timer ti = (Timer)timerTable.remove(track); if(ti!=null) ti.cancel(); } } } } } 115 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0092175/manifest

Comment

Related Items