With the rise of the mobile computing market, Android has received tremendous attention from both academia and industry. Application programming in Android is known to have unique characteristics, and Android apps be particularly vulnerable to various security attacks. In response, numerous solutions for particular security issues have been proposed. However, there is little broad understanding about Android app code structure and behaviors along with their implications for app analysis and security defense, especially in an evolutionary perspective. To mitigate this gap, we present a longitudinal characterization study of Android apps to systematically investigate how they are built and execute over time. Through lightweight static analysis and method-level tracing, we examined the code and execution of 17,664 apps sampled from the apps developed in each of eight past years, with respect to metrics in three complementary dimensions. Our study revealed that (1) apps functionalities heavily rely on the Android framework/SDK, and the reliance continues to grow, (2)Activitycomponents constantly dominated over other types of components and were responsible for the invocation of most lifecycle callbacks, (3) event-handling callbacks consistently focused more on user-interface events than system events, (4) the overall use of callbacks has been slowly diminishing over time, (5) the majority of exercised inter-component communications (ICCs) did not carry any data payloads, and (6) sensitive data sources and sinks targeted only one/two dominant categories of information or operations, and the ranking of source/sink categories remained quite stable throughout the eight years. We discuss the implications of our empirical findings for cost-effective app analysis and security defense for Android, and make cost-effectiveness improvement recommendations accordingly.

During repackaging, malware writers statically inject malcode and modify the control flow to ensure its execution. Repackaged malware is difficult to detect by existing classification techniques, partly because of their behavioral similarities to benign apps. By exploring the app's internal different behaviors, we propose a new Android repackaged malware detection technique based on code heterogeneity analysis. Our solution strategically partitions the code structure of an app into multiple dependence-based regions (subsets of the code). Each region is independently classified on its behavioral features. We point out the security challenges and design choices for partitioning code structures at the class and method level graphs, and present a solution based on multiple dependence relations. We have performed experimental evaluation with over 7,542 Android apps. For repackaged malware, our partition-based detection reduces false negatives (i.e., missed detection) by 30-fold, when compared to the non-partition-based approach. Overall, our approach achieves a false negative rate of 0.35 percent and a false positive rate of 2.97 percent.

Malware collusion is a technique utilized by attackers to evade standard detection. It is a new threat where two or more applications, appearing benign, communicate to perform a malicious task. Most proposed approaches aim at detecting stand-alone malicious applications. We point out the need for analyzing data flows across multiple Android apps, a problem referred to as end-to-end flow analysis. In this work, we present a flow analysis for app pairs that computes the risk level associated with their potential communications. Our approach statically analyzes the sensitivity and context of each inter-app flow based on inter-component communication (ICC) between communicating apps, and defines fine-grained security policies for inter-app ICC risk classification. We perform an empirical study on 7,251 apps from the Google Play store to identify the apps that communicate with each other via ICC channels. Our results report four times fewer warnings on our dataset of 197 real app pairs communicating via explicit external ICCs than the state-of-the-art permission-based collusion detection.

Most existing Android malware detection and categorization techniques are static approaches, which suffer from evasion attacks, such as obfuscation. By analyzing program behaviors, dynamic approaches are potentially more resilient against these attacks. Yet existing dynamic approaches mostly rely on characterizing system calls which are subject to system-call obfuscation. This paper presents DroidCat, a novel dynamic app classification technique, to complement existing approaches. By using a diverse set of dynamic features based on method calls and inter-component communication (ICC) Intents without involving permission, app resources, or system calls while fully handling reflection, DroidCat achieves superior robustness than static approaches as well as dynamic approaches relying on system calls. The features were distilled from a behavioral characterization study of benign versus malicious apps. Through three complementary evaluation studies with 34 343 apps from various sources and spanning the past nine years, we demonstrated the stability of DroidCat in achieving high classification performance and superior accuracy compared with the two state-of-the-art peer techniques that represent both static and dynamic approaches. Overall, DroidCat achieved 97% F1-measure accuracy consistently for classifying apps evolving over the nine years, detecting or categorizing malware, 16%-27% higher than any of the two baselines compared. Furthermore, our experiments with obfuscated benchmarks confirmed higher robustness of DroidCat over these baseline techniques. We also investigated the effects of various design decisions on DroidCat's effectiveness and the most important features for our dynamic classification. We found that features capturing app execution structure such as the distribution of method calls over user code and libraries are much more important than typical security features such as sensitive flows.

Inter-Component Communication (ICC) enables useful interactions between mobile apps. However, misuse of ICC exposes users to serious threats such as intent hijacking/spoofing and app collusions, allowing malicious apps to access privileged user data via another app. Unfortunately, existing ICC analyses are largely incompetent in both accuracy and scale. This poster points out the need and technical challenges of prioritized analysis of inter-app ICC risks. In this poster, we propose MR-Droid, a MapReduce-based computing framework for accurate and scalable inter-app ICC analysis in Android. MR-Droid extracts data-flow features between multiple communicating apps and the target apps to build a large-scale ICC graph. Our approach is to leverage the ICC graph to provide contexts for inter-app communications to produce precise alerts and prioritize risk assessments. This process requires large app-pair data, which is enabled by our MapReduce-based program analysis. Our initial extensive experiments on 11,996 apps from 24 app categories (13 million pairs) demonstrate the scalability of our approach.

Most existing research for Android focuses on particular security issues, yet there is little broad understanding of Android application run-time characteristics and their implications. To mitigate this gap, we present the first systematic dynamic characterization study of Android apps that targets a broad understanding of application behaviors in Android. Through lightweight method-level profiling, we collected 59GB traces of method calls and Intent-based inter-component communication (ICC) from 125 popular Android apps and 62 pairs among them that enabled an intensive empirical investigation of their run-time behaviors. Our study revealed that, among other findings, (1) the application executions were overwhelmingly dominated by the Android framework, (2) Activity components dominated over other types of components and were responsible for most lifecycle callbacks (3) most event handlers dealt with user interactions as opposed to system events, (4) the majority of exercised ICCs did not carry any data payloads, and (5) sensitive data sources and sinks targeted only one/two dominant categories of information or operations. We also discuss the implications of our results for cost-effective program analysis and security defense for Android.

As the Android app market keeps growing, there is a pressing need for automated tool supports to empower Android developers to produce quality apps with higher productivity. Yet existing tools for Android mostly aim at security and privacy protection, primarily targeting end users and security analysts. Towards filling this gap, we present DROIDFAX, a toolkit that targets the developers to help them comprehensively understand Android apps regarding their code structure and behavioral traits. To that end, DROIDFAX features a systematic app characterization in multiple dimensions and views, through lightweight code analysis and profiling of both ordinary method calls (including those via reflection and exceptional control flows) and inter-component communications (including those within and across apps). The toolkit also includes a statement coverage tracker that works directly on bytecode and a dedicated tracer of events occurred during app executions. Applying DROIDFAX in two use cases has resulted in important findings about app behavioral patterns and an advanced security defense technique for Android. Empirical results also showed promising efficiency and scalability of DROIDFAX for practical adoption. A demo video for DROIDFAX can be viewed here or downloaded here.

We describe a set of artifacts for dynamic analysis of Android apps, including a dataset used in a dynamic characterization study, source code used for performing the study, an Android inter-app benchmark suite, and definition of Android behavioral metrics.

Programmers produce code clones when developing software. By copying and pasting code with or without modification, developers reuse existing code to improve programming productivity. However, code clones present challenges to software maintenance: they may require consistent application of the same or similar bug fixes or program changes to multiple code locations. To simplify the maintenance process, various tools have been proposed to automatically detect clones [1], [2], [3], [4], [5], [6]. Some tools tokenize source code, and then compare the sequence or frequency of tokens to reveal clones [1], [3], [4], [5]. Some other tools detect clones using tree-matching algorithms to compare the Abstract Syntax Trees (ASTs) of source code [2], [6]. In this paper, we present CCLEARNER, the first solely token-based clone detection approach leveraging deep learning. CCLEARNER extracts tokens from known method-level code clones and nonclones to train a classifier, and then uses the classifier to detect clones in a given codebase. To evaluate CCLEARNER, we reused BigCloneBench [7], an existing large benchmark of real clones. We used part of the benchmark for training and the other part for testing, and observed that CCLEARNER effectively detected clones. With the same data set, we conducted the first systematic comparison experiment between CCLEARNER and three popular clone detection tools. Compared with the approaches not using deep learning, CCLEARNER achieved competitive clone detection effectiveness with low time cost.

Program anomaly detection models legitimate behaviors of complex software and detects deviations during execution. Behavior deviations may be caused by malicious exploits, design flaws, or operational errors. Probabilistic detection computes the likelihood of occurrences of observed call sequences. However, maintaining context sensitivity in detection incurs high modeling complexity and runtime overhead. We present a new anomaly-based detection technique that is both probabilistic and 1-level calling-context sensitive. We describe a matrix representation and clustering-based solution for model reduction, specifically reducing the number of hidden states in a special hidden Markov model whose parameters are initialized with program analysis. Our extensive experimental evaluation confirms the significantly improved detection accuracy and shows that attacker's ability to conduct code-reuse exploits is substantially limited.

Static analysis is challenged by the dynamic language constructs of JavaScript which often lead to unacceptable performance and/or precision results. We describe an approach that focuses on improving the practicality and accuracy of points-to analysis and call graph construction for JavaScript programs. The approach first identifies program constructs which are sources of imprecision (i.e., root causes) through monitoring the static analysis process. We then examine and suggest specific context-sensitive analyses to apply. Our technique is able to to find that the root causes comprise less than 2% of the functions in JavaScript library applications. Moreover, the specialized analysis derived by our approach finishes within a few seconds, even on programs which can not complete within 10 minutes with the original analysis.

Despite the popularity of JavaScript for client-side web applications, there is a lack of effective software tools supporting JavaScript development and testing. The dynamic characteristics of JavaScript pose software engineering challenges such as program understanding and security. One important feature of JavaScript is that its objects support flexible mechanisms such as property changes at runtime and prototype-based inheritance, making it difficult to reason about object behavior. We have performed an empirical study on real JavaScript applications to understand the dynamic behavior of JavaScript objects. We present metrics to measure behavior of JavaScript objects during execution (e.g., operations associated with an object, object size, and property type changes). We also investigated the behavioral patterns of observed objects to understand the coding or user interaction practices in JavaScript software. Copyright © 2015 John Wiley & Sons, Ltd.

The trend constantly being observed in the evolution of advanced modern exploits is their growing sophistication in stealthy attacks. Code-reuse attacks such as return-oriented programming allow intruders to execute mal-intended instruction sequences on a victim machine without injecting external code. We introduce a new anomaly-based detection technique that probabilistically models and learns a program's control flows for high-precision behavioral reasoning and monitoring. Our prototype in Linux is named STILO, which stands for STatically InitiaLized markOv. Experimental evaluation involves real-world code-reuse exploits and over 4,000 testcases from server and utility programs. STILO achieves up to 28-fold of improvement in detection accuracy over the state-of-the-art HMM-based anomaly detection. Our findings suggest that the probabilistic modeling of program dependences provides a significant source of behavior information for building high-precision models for real-time system monitoring.

Context sensitivity is a technique to improve program analysis precision by distinguishing between function calls. A specific context-sensitive analysis is usually designed to accommodate the programming paradigm of a particular programming language. JavaScript features both the object-oriented and functional programming paradigms. Our empirical study suggests that there is no single context-sensitive analysis that always produces precise results for JavaScript applications. This observation motivated us to design an adaptive analysis, selecting a context-sensitive analysis from multiple choices for each function. Our two-staged adaptive context-sensitive analysis first extracts function characteristics from an inexpensive points-to analysis and then chooses a specialized context-sensitive analysis per function based on the heuristics. The experimental results show that our adaptive analysis achieved more precise results than any single context-sensitive analysis for several JavaScript programs in the benchmarks.

As mobile computing becomes an integral part of the modern user experience, malicious applications have infiltrated open marketplaces for mobile platforms. Malware apps stealthily launch operations to retrieve sensitive user or device data or abuse system resources. We describe a highly accurate classification approach for detecting malicious Android apps. Our method statically extracts a data-flow feature on how user inputs trigger sensitive API invocations, a property referred to as the user-trigger dependence. Our evaluation with 1433 malware apps and 2684 free popular apps gives a classification accuracy (2.1% false negative rate and 2.0% false positive rate) that is better than, or at least competitive against, the state-of-the-art. Our method also discovers new malicious apps in the Google Play market that cannot be detected by virus scanning tools. Our thesis in this mobile app classification work is to advocate the approach of benign property enforcement, i.e., extracting unique behavioral properties from benign programs and designing corresponding classification policies.

JavaScript is widely used in Web applications because of its flexibility and dynamic features. However, the latter pose challenges to static analyses aimed at finding security vulnerabilities, (e.g., taint analysis).

SUMMARY There is tension between programming language design for modularity and flexibility of programming and the amenability of the resulting programs to static analysis. At the start of Software Practice and Experience in 1971, most languages in commercial use were procedural (e.g., FORTRAN, ALGOL, PL/I) and on the whole were easier to analyze than languages of today such as JavaScript and Python. Modern languages include dynamic features, which enhance prototyping of approaches, often resulting in programs that are difficult for software tools or humans to understand. Starting with this perspective, we explore the relationship between language features and the ability of static analysis to precisely determine control flow and data flow in programs, thus enabling program optimization, transformation and understanding. Copyright © 2011 John Wiley & Sons, Ltd.

Various coverage criteria are commonly used to assess the quality of test suites, but achieving full coverage according to these criteria is often impossible or impractical. Our research starts from the popular assumption that a disproportionate number of faults is likely to reside in recently changed code. Based on this assumption, we propose several change-based coverage criteria that reflect to what extent changes with respect to a previous program version are exercised by a test suite. In a set of experiments on programs from the SIR repository, we found change-based criteria to reveal faults bet- ter than traditional criteria, and to enable the construction of much smaller test suites with similar fault detection effectiveness. We also report on a case study that shows that achieving 100% coverage according to a change-based criterion is feasible and that by doing so we were able to find additional faults, including one fault that was not intentionally seeded in the subject program.

This paper explores the use of context sensitivity both intra- and inter-procedurally in a blended (static/dynamic) program analysis for identifying source of object churn in framework-intensive Web-based applications. Empirical experiments with an existing blended analysis algorithm compare combinations of (i) use of a context-insensitive call graph with a context-sensitive calling context tree, and (ii) use (or not) of context-sensitive code pruning within methods. These experiments demonstrate achievable gains in scalability and performance in terms of several metrics designed for blended escape analysis, and report results in terms of object instances created, to allow more realistic conclusions from the data than were possible previously.

In prior work we have developed an escape analysis to help developers identify sources of object churn (i.e., excessive use of temporaries) in large framework-based applications. We have developed Hi-C, an Eclipse plug-in that allows users to visualize, filter, and explore analysis results to aid them in diagnosis of object churn and in program comprehension in general.

We present the best papers of the International Symposium on Software Testing and Analysis (ISSTA) 2008.

In modern software systems, programs are obtained by dynamically assembling components. This has made it necessary to subject component providers to access-control restrictions. What permissions should be granted to each component? Too few permissions may cause run-time authorization failures, too many constitute a security hole. We have designed and implemented a composite algorithm for precise static permission analysis for Java and the CLR. Unlike previous work, the analysis is modular and fully integrated with a novel slicing-based string analysis that is used to statically compute the string values defining a permission and disambiguate permission propagation paths. The results of our research prototype on production-level Java code support the effectiveness, practicality, and precision of our techniques, and show outstanding improvement over previous work.

Developers use unit testing to improve the quality of software systems. Current development tools for unit testing help with automating test execution, with reporting results, and with generating test stubs. However, they offer no aid for designing tests aimed specifically at exercising the effects of changes to a program. This paper describes a unit testing tool that leverages a change model to assist developers in the creation of new unit tests. The tool provides developers with quantitative feedback and detailed information about change effects, which not only facilitate the writing of more effective tests, but also motivate developers with an achievable coverage goal.

Software development teams exchange source code in shared repositories. These repositories are kept consistent by having developers follow a commit policy, such as ldquoProgram edits can be committed only if all available tests succeed.rdquo Such policies may result in long intervals between commits, increasing the likelihood of duplicative development and merge conflicts. Furthermore, commit policies are generally not automatically enforceable. We present a program analysis to identify committable changes that can be released early, without causing failures of existing tests, even in the presence of failing tests in a developer's local workspace. The algorithm can support relaxed commit policies that allow early release of changes, reducing the potential for merge conflicts. In experiments using several versions of a non-trivial software system with failing tests, 3 newly enabled commit policies were shown to allow a significant percentage of changes to be committed.

This paper describes the implementation and evaluation of a program that uses active recruiting and peer-led team learning to try to increase the participation and success of women and minority students in undergraduate computer science. These strategies were applied at eight universities starting in the fall of 2004. There have been some impressive results: We succeeded in attracting under-represented students who would not otherwise have taken a CS course.Evaluation shows that participation in our program significantly improves retention rates and grades, especially for women.Students in the program, as well as the students who served as peer leaders, are uniformly enthusiastic about their experience.

Framework-intensive applications (e.g., Web applications) heavily use temporary data structures, often resulting in performance bot-tlenecks. This paper presents an optimized blended escape analysis to approximate object lifetimes and thus, to identify these tempo-raries and their uses. Empirical results show that this optimized analysis on average prunes 37 % of the basic blocks in our bench-marks, and achieves a speedup of up to 29 times compared to the original analysis. Newly defined metrics quantify key properties of temporary data structures and their uses. A detailed empirical eval-uation offers the first characterization of temporaries in framework-intensive applications. The results show that temporary data struc-tures can include up to 12 distinct object types and can traverse through as many as 14 method invocations before being captured.

Crisp is an Eclipse plug-in tool for constructing intermediate versions of a Java program that is being edited. After a long editing session, a programmer will run regression tests to make sure she has not invalidated previously tested functionality. If a test fails unexpectedly, Crisp allows the programmer to select parts of the edit that affected the failing test and to add them to the original program, creating an intermediate version guaranteed to compile. Then the programmer can re-execute the test in order to locate the exact reasons for the failure by concentrating on those affecting changes that were applied. Using Crisp, a programmer can it- eratively select, apply, and undo individual (or sets of) affecting changes and, thus effectively find a small set of failure-inducing changes. Crisp is an extension to our change impact analysis tool, Chianti, [6].

Although it is common in large Java programs to rethrow exceptions, existing exception-flow analyses find only single exception-flow links, thus are unable to identify multiple-link exception propagation paths. This paper presents a new static analysis that, when combined with previous exception-flow analyses, computes chains of semantically-related exception-flow links, and thus reports entire exception propagation paths, instead of just discrete segments of them. These chains can be used 1) to show the error handling architecture of a system, 2) to assess the vulnerability of a single component and the whole system, 3) to support better testing of error recovery code, and 4) to facilitate the tracing of the root cause of a logged problem. Empirical findings and a case history for Tomcat show that a significant portion of the chains found in our benchmarks span multiple components, and thus are hard to find manually.

This paper defines a new analysis paradigm, blended program analysis, that enables practical, effective analysis of large framework-based Java applications for performance understanding. Blended analysis combines a dynamic representation of the program calling structure, with a static analysis applied to a region of that calling structure with observed performance problems. A blended escape analysis is presented which enables approximation of object effective lifetimes, to facilitate explanation of the usage of newly created objects in a program region. Performance bottlenecks stemming from overuse of temporary structures are common in framework-based applications. Metrics are introduced to expose how, in aggregate, these applications make use of new objects. Results of empirical experiments with the Trade benchmark are presented. A case study demonstrates how results from a blended escape analysis can help locate, in a region which calls 223 distinct methods, the single call path responsible for a performance problem involving objects created at 9 distinct sites and as far as 6 call levels away.

In modern software development, regression tests are used to confirm the fundamental functionalities of an edited program and to assure the code quality. Difficulties occur when testing reveals unexpected behaviors, which indicate potential defects introduced by the edit. However, the changes that caused the failure(s) are not always easy to find. We propose a heuristic that ranks method changes that might have affected a failed test, indicating the likelihood that they may have contributed to a test failure. Our heuristic is based on the calling structure of the failed test (e.g., the number of ancestors and descendents of a method in the test's call graph, whether the caller or callee was changed, etc.). We evaluated the effectiveness of the heuristic in 14 pairs of edited versions in the Eclipse jdt core plug-in, using the test suite from its compiler tests plug-in. Our results indicate that when a failure is caused by a single method change, our heuristic ranked the failure-inducing change as number 1 or number 2 of all the method changes in 67% of the delegate tests (i.e., representatives of all failing tests). Even when the failure is caused by some combination of the changes, rather than a single change, our heuristic still helps.

Knowledge of interclass test dependences is crucial to decide class test order, facilitating the design of an efficient integration test plan. In order to discover precise interclass test dependences, we proposed a semantic-based definition and designed a safe approximation algorithm to calculate the dependence according to the given definition. The algorithm propagates semantic dependences at method-level granularity and is parameterized by the precision of the corresponding program analysis. We have experimented with nine benchmarks and showed that the algorithm is rather accurate in that it discovers dependence cycles precisely in 6 out of 9 benchmarks (as evaluated by human inspection). The algorithm uncovers additional opportunities for concurrent testing in each of the benchmarks, with an on average expected 52.5% time savings over the ORD-based definition.

Abstract Call graphs are widely used to represent calling relationships among methods. However, there is not much interest in calling relationships among library methods in many software engineering applications, such as program understanding and testing, especially when the library is very big and the calling relationships are not trivial. This paper explores approaches for generating more accurate application call graphs for Java. A new data reachability algorithm is proposed and fine tuned to resolve library callbacks accurately. Compared with an algorithm that resolves library callbacks by traversing the whole‐program call graph, the fine‐tuned data reachability algorithm results in fewer spurious callback edges. In empirical studies, the new algorithm shows a significant reduction in the number of spurious callback edges. On the basis of the new algorithm, a library abstraction can be calculated automatically and applied in amortized slicing and dataflow testing. Copyright © 2007 John Wiley & Sons, Ltd.

Testing and code editing are interleaved activities during program development. When tests fail unexpectedly, the changes that caused the failure(s) are not always easy to find. We explore how change classification can focus programmer attention on failure-inducing changes by automatically labeling changes Red, Yellow, or Green, indicating the likelihood that they have contributed to a test failure. We implemented our change classification tool JUnit/CIA as an extension to the JUnit component within Eclipse, and evaluated its effectiveness in two case studies. Our results indicate that change classification is an effective technique for finding failure-inducing changes.

During program maintenance, a programmer may make changes that enhance program functionality or fix bugs in code. Then, the programmer usually will run unit/regression tests to prevent invalidation of previously tested functionality. If a test fails unexpectedly, the programmer needs to explore the edit to find the failure-inducing changes for that test. Crisp uses results from Chianti, a tool that performs semantic change impact analysis [1], to allow the programmer to examine those parts of the edit that affect the failing test. Crisp then builds a compilable intermediate version of the program by adding a programmer-selected partial edit to the original code, augmenting the selection as necessary to ensure compilation. The programmer can reexecute the test on the intermediate version in order to locate the exact reasons for the failure by concentrating on the specific changes that were applied. In nine initial case studies on pairs of versions from two real Java programs, Daikon [2] and Eclipse jdt compiler [3], we were able to use Crisp to identify the failure-inducing changes for all but 1 of 68 failing tests. On average, 33 changes were found to affect each failing test (of the 67), but only 1-4 of these changes were found to be actually failure-inducing.

Chianti is a change impact analysis tool for Java that is implemented in the context of the Eclipse environment. Chianti analyzes two versions of a Java program, decomposes their difference into a set of atomic changes, and a partial order inter-dependences of these changes is calculated. Change impact is then reported in terms of affected (regression or unit) tests whose execution behavior may have been modified by the applied changes. For each affected test, Chianti also determines a set of affecting changes that were responsible for the test's modified behavior. This latter step of isolating failure inducing changes for one specific test from irrelevant changes can be used as a debugging technique in situations where a test fails unexpectedly after a long editing session.

Crisp is a tool (i.e., an Eclipse plug-in) for constructing intermediate versions of a Java program that is being edited in an IDE such as Eclipse. After a long editing session, a programmer usually would run regression tests to make sure she has not invalidated previously checked functionality. If a test fails unexpectedly, Crisp uses input from Chianti, a tool for semantic change impact analysis, to allow the programmer to select parts of the edit that affected the failing test and to add them to the original program, creating an intermediate version guaranteed to compile. Then the programmer can re-execute the test in order to locate the exact reasons for the failure by concentrating on those affecting changes that were applied. Using Crisp, a programmer can iteratively select, apply, and undo individual (or sets of) affecting changes and, thus effectively find a small set of failure-inducing changes.

Program flow analysis has many applications in software tools for program understanding, restructuring, verification, testing and reverse engineering. There are two important requirements for a flow analysis to be applied successfully in software tools: precision and practicality. We propose annotated inclusion constraints - a new general framework for formulating and implementing precise inclusion-based flow analyses. The framework can be instantiated in two dimensions: one can select a flow analysis that can be modeled using inclusion constraints (e.g., class analysis, points-to analysis) and add a dimension of precision by choosing appropriate annotations (e.g., field sensitivity, context sensitivity). The framework encompasses a large spectrum of relatively precise flow analyses. We formulate and implement several points-to analyses for Java as instances of the framework. The experiments show that precision dimensions such as field sensitivity and context sensitivity have significant impact on the points-to analysis and its clients. In the same time, using annotations to model these precision dimensions results in efficient and practical analysis. Therefore, flow analyses based on annotated constraints can be successfully incorporated in software tools.

The goal of points-to analysis for Java is to determine the set of objects pointed to by a reference variable or a reference object field. We present object sensitivity , a new form of context sensitivity for flow-insensitive points-to analysis for Java. The key idea of our approach is to analyze a method separately for each of the object names that represent run-time objects on which this method may be invoked. To ensure flexibility and practicality, we propose a parameterization framework that allows analysis designers to control the tradeoffs between cost and precision in the object-sensitive analysis. Side-effect analysis determines the memory locations that may be modified by the execution of a program statement. Def-use analysis identifies pairs of statements that set the value of a memory location and subsequently use that value. The information computed by such analyses has a wide variety of uses in compilers and software tools. This work proposes new versions of these analyses that are based on object-sensitive points-to analysis.We have implemented two instantiations of our parameterized object-sensitive points-to analysis. On a set of 23 Java programs, our experiments show that these analyses have comparable cost to a context-insensitive points-to analysis for Java which is based on Andersen's analysis for C. Our results also show that object sensitivity significantly improves the precision of side-effect analysis and call graph construction, compared to (1) context-insensitive analysis, and (2) context-sensitive points-to analysis that models context using the invoking call site. These experiments demonstrate that object-sensitive analyses can achieve substantial precision improvement, while at the same time remaining efficient and practical.

Software engineering research and programming language design have enjoyed asymbioticrelationship, with traceable impacts since the 1970s, when these areas were first distinguished from one another. This report documents this relationship by focusing on several major features of current programming languages: data and procedural abstraction, types, concurrency, exceptions, and visual programming mechanisms. The influences are determined by tracing references in publications in both fields, obtaining oral histories from language designers delineating influences on them, and tracking cotemporal research trends and ideas as demonstrated by workshop topics, special issue publications, and invited talks in the two fields. In some cases there is conclusive data supporting influence. In other cases, there are circumstantial arguments (i.e., cotemporal ideas) that indicate influence. Using this approach, this study provides evidence of the impact of software engineering research on modern programming language design and documents the close relationship between these two fields.

This paper presents a new compile-time analysis that enables a testing methodology for white-box coverage testing of error recovery code (i.e., exception handlers) of server applications written in Java, using compiler-directed fault injection. The analysis allows compiler-generated instrumentation to guide the fault injection and to record the recovery code exercised. (An injected fault is experienced as a Java exception.) The analysis 1) identifies the exception-flow "def-uses" to be tested in this manner, 2) determines the kind of fault to be requested at a program point, and 3) finds appropriate locations for code instrumentation. The analysis incorporates refinements that establish sufficient context sensitivity to ensure relatively precise def-use links and to eliminate some spurious def-uses due to demonstrably infeasible control flow. A runtime test harness calculates test coverage of these links using an exception def-catch metric. Experiments with the methodology demonstrate the utility of the increased precision in obtaining good test coverage on a set of moderately sized server benchmarks.

This paper presents a new compile-time analysis that enables a testing methodology for white-box coverage testing of error recovery code (i.e., exception handlers) in Java web services using compiler-directed fault injection. The analysis allows compiler-generated instrumentation to guide the fault injection and to record the recovery code exercised. (An injected fault is experienced as a Java exception.) The analysis (i) identifies the exception-flow 'def-uses' to be tested in this manner, (ii) determines the kind of fault to be requested at a program point, and (iii) finds appropriate locations for code instrumentation. The analysis incorporates refinements that establish sufficient context sensitivity to ensure relatively precise def-use links and to eliminate some spurious def-uses due to demonstrably infeasible control flow. A runtime test harness calculates test coverage of these links using an exception def-catch metric. Experiments with the methodology demonstrate the utility of the increased precision in obtaining good test coverage on a set of moderately-sized Java web services benchmarks.

This paper reports on the design and implementation of Chianti, a change impact analysis tool for Java that is implemented in the context of the Eclipse environment. Chianti analyzes two versions of an application and decomposes their difference into a set of atomic changes. Change impact is then reported in terms of affected (regression or unit) tests whose execution behavior may have been modified by the applied changes. For each affected test, Chianti also determines a set of affecting changes that were responsible for the test's modified behavior. This latter step of isolating the changes that induce the failure of one specific test from those changes that only affect other tests can be used as a debugging technique in situations where a test fails unexpectedly after a long editing session. We evaluated Chianti on a year (2002) of CVS data from M. Ernst's Daikon system, and found that, on average, 52% of Daikon's unit tests are affected. Furthermore, each affected unit test, on average, is affected by only 3.95% of the atomic changes. These findings suggest that our change impact analysis is a promising technique for assisting developers with program understanding and debugging.

Testing of polymorphism in object-oriented software may require coverage of all possible bindings of receiver classes and target methods at call sites. Tools that measure this coverage need to use class analysis to compute the coverage requirements. However, traditional whole-program class analysis cannot be used when testing incomplete programs. To solve this problem, we present a general approach for adapting whole-program class analyses to operate on program fragments. Furthermore, since analysis precision is critical for coverage tools, we provide precision measurements for several analyses by determining which of the computed coverage requirements are actually feasible for a set of subject components. Our work enables the use of whole-program class analyses for testing of polymorphism in partial programs, and identifies analyses that potentially are good candidates for use in coverage tools.

We present a new approach that uses compiler-directed fault-injection for coverage testing of recovery code in Internet services, to evaluate their robustness to operating system and I/O hardware faults. We define a set of program-fault coverage metrics that enable quantification of Java catch blocks exercised during fault-injection experiments. We use compiler analyses to instrument application code in two ways: to direct fault injection to occur at appropriate points during execution, and to measure the resulting coverage. As a proof of concept for these ideas, we have applied our techniques manually to Muffin, a proxy server; we obtained a high degree of coverage of catch blocks, with on average 85% of the expected faults per catch being experienced as caught exceptions.

Adequate testing of polymorphism in object-oriented software requires coverage of all possible bindings of receiver classes and target methods at call sites. Tools that measure this coverage need to use class analysis to compute the coverage requirements. However, traditional whole-program class analysis cannot be used when testing partial programs. To solve this problem, we present a general approach for adapting whole-program class analyses to operate on program fragments. Furthermore, since analysis precision is critical for coverage tools, we provide precision measurements for several analyses by determining which of the computed coverage requirements are actually feasible. Our work enables the use of whole-program class analyses for testing of polymorphism in partial programs, and identifies analyses that compute precise coverage requirements and therefore are good candidates for use in coverage tools.

The object relation diagram (ORD) of a program is a class interdependence diagram which has applications in a wide variety of software engineering problems (e.g., integration testing, integration coverage analysis, regression testing, impact analysis, program understanding, and reverse engineering). Because the imprecision of the ORD directly affects the practicality of its usage, it is important to investigate techniques for constructing precise ORDs. This paper makes three contributions. First, we develop the extended object relation diagram (ExtORD), a version of the ORD designed for use in integration coverage analysis. The ExtORD shows the specific statement that creates an interclass dependence, and can be easily constructed by extending techniques for ORD construction. Second, we develop a general algorithm for ORD construction, parameterized by class analysis. Third, we demonstrate empirically that relatively precise class analyses can significantly improve diagram precision compared to earlier work, resulting in average size reduction of 55% for the ORD and 39% for the ExtORD.

The goal of points-to analysis for Java is to determine the set of objects pointed to by a reference variable or a reference objet field. Improving the precision of practical points-to analysis is important because points-to information has a wide variety of client applications in optimizing compilers and software engineering tools. In this paper we present object sensitivity, a new form of context sensitivity for flow-insensitive points-to analysis for Java. The key idea of our approach is to analyze a method separately for each of the objects on which this method is invoked. To ensure flexibility and practicality, we propose a parameterization framework that allows analysis designers to control the tradeoffs between cost and precision in the object-sensitive analysis.Side-effect analysis determines the memory locations that may be modified by the execution of a program statement. This information is needed for various compiler optimizations and software engineering tools. We present a new form of side-effect analysis for Java which is based on object-sensitive points-to analysis.We have implemented one instantiation of our parameterized object-sensitive points-to analysis. We compare this instantiation with a context-insensitive points-to analysis for Java which is based on Andersen's analysis for C [4]. On a set of 23 Java programs, our experiments show that the two analyses have comparable cost. In some cases the object-sensitive analysis is actually faster than the context-insensitive analysis. Our results also show that object sensitivity significantly improves the precision of side-effect analysis, call graph construction, and virtual call resolution. These experiments demonstrate that object-sensitive analyses can achieve significantly better precision than context-insensitive ones, while at the same time remaining efficient and practical.

This paper describes the implementation of an online feedback-directed optimization system. The system is fully automatic; it requires no prior (offline) profiling run. It uses a previously developed low-overhead instrumentation sampling framework to collect control flow graph edge profiles. This profile information is used to drive several traditional optimizations, as well as a novel algorithm for performing feedback-directed control flow graph node splitting. We empirically evaluate this system and demonstrate improvements in peak performance of up to 17% while keeping overhead low, with no individual execution being degraded by more than 2% because of instrumentation.

The goal of point-to analysis for Java is to determine the set of objects pointed by a reference variable or a reference object field. This information has a wide variety of client applications in optimizing compilers and software engineering tools. In this paper we present a point-to analysis for Java based on Andersen's point-to analysis for C [5]. We implement the analysis by using a constraint-based approach which employs annotated inclusion constraints. Constraint annotations allow us model precisely and efficiently the semantics of virtual calls and the flow of values through object fields. By solving systems of annotated inclusion constraints, we have been albe to perform practical and precies points-to analysis for Java

Small changes can have major and nonlocal effects in object-oriented languages, due to the use of subtyping and dynamic dispatch. This complicates life for maintenance programmers, who need to fix bugs or add enhancements to systems originally written by others. Change impact analysis provides feedback on the semantic impact of a set of program changes. This analysis can be used to determine the regression test drivers that are affected by a set of changes. Moreover, if a test fails, a subset of changes responsible for the failure can be identified, as well as a subset of changes that can be incorporated safely without affecting any test driver.

Instrumenting code to collect profiling information can cause substantial execution overhead. This overhead makes instrumentation difficult to perform at runtime, often preventing many known offline feedback-directed optimizations from being used in online systems. This paper presents a general framework for performing instrumentation sampling to reduce the overhead of previously expensive instrumentation. The framework is simple and effective, using code-duplication and counter-based sampling to allow switching between instrumented and non-instrumented code.

The first interprocedural modification side-effects analysis for C (MOD C ) that obtains better than worst-case precision on programs with general-purpose pointer usage is presented with empirical results. The analysis consists of an algorithm schema corresponding to a family of MOD C algorithms with two independent phases: one for determining pointer-induced aliases and a subsequent one for propagating interprocedural side effects. These MOD C algorithms are parameterized by the aliasing method used. The empirical results compare the performance of two dissimilar MOD C algorithms: MOD C ( FSAlias ) uses a flow-sensitive, calling-context-sensitive interprocedural alias analysis; MOD C ( FIAlias uses a flow-insensitive, calling-context-insensitive alias analysis which is much faster, but less accurate. These two algorithms were profiled on 45 programs ranging in size from 250 to 30,000 lines of C code, and the results demonstrate dramatically the possible cost-precision trade-offs. This first comparative implementation of MOD C analyses offers insight into the differences between flow-/context-sensitive and flow-/context-insensitive analyses. The analysis cost versus precision trade-offs in side-effect information obtained are reported. The results show surprisingly that the precision of flow-sensitive side-effect analysis is not always prohibitive in cost, and that the precision of flow-insensitive analysis is substantially better than worst-case estimates and seems sufficient for certain applications. On average MOD C ( FSAlias ) for procedures and calls is in the range of 20% more precise than MOD C ( FIAlias ); however, the performance was found to be at least an order of magnitude slower than MOD C ( FIAlias ).

At each program point, points-to analysis for statically typed object oriented programming languages (e.g., Java, C++) determines those objects to which a reference may refer (or a pointer may point) during execution. Points-to analysis is necessary for any semantics based software tools for object oriented systems. Our new complexity results for points-to analysis distinguish the difficulty of intraprocedural and interprocedural points-to analyses for languages with combinations of single-level types (i.e., types with data members only of primitive type), exceptions with or without subtyping, and dynamic dispatch. Our results include: 1) the first polynomial-time algorithm for points-to analysis in the presence of exceptions that handles a robust subset of Java without threads and can be applied to C++; 2) proof that the above algorithm is safe, in general, and provably precise on programs with single-level types and exceptions without subtyping, but not dynamic dispatch, thus, this case is in P; 3) proof that an interprocedural points-to analysis problem with single-level types and exceptions with subtyping, but without dynamic dispatch, is PSPACE-hard, while the intraprocedural problem is PSPACE-complete. Other complexity characterizations of points-to analysis in programs without exceptions are presented, including an algorithm with worst-case bound of O(n/sup 5/), which improves over the O(n/sup 7/) worst-case bound achievable from previous approaches of T. Reps et al. (1995) and W.A. Landi and B.G. Ryder (1991).

Pointer aliasing analysis is used to determine if two object names containing dereferences and/or field selectors, (e.g., *p,q->t), may refer to the same location during execution.Such information is necessary for applications such as dataflow-based testers, program understanding tools, and debuggers, but is expensive to calculate with acceptable precision.Incremental algorithms update data flow information after a program change rather than recomputing it from scratch, under the assumption that the change impact will be limited.Two versions of a practical incremental pointer aliaaing algorithm have been developed, based on Land&Ryder flow-and context-sensitive alias analysis.Empirical results attest to the time savings over exhaustive analysis (a six-fold speedup on average), and the precision of the approximate solution obtained (on average same solution as exhaustive algorithm for 75% of the tests.)

Relevant context inference (RCI) is a modular technique for flow- and context-sensitive data-flow analysis of statically typed object-oriented programming languages such as C++ and Java. RCI can be used to analyze complete programs as well as incomplete programs such as libraries; this approach does not require that the entire program be memory-resident during the analysis. RCI is presented in the context of points-to analysis for a realistic subset of C++. The empirical evidence obtained from a prototype implementation argues the effectiveness of RCI.

Precision and scalability are two desirable, yet often conflicting, features of data-flow analyses. This paper reports on a case study of the modification---ide-effects problem for C in the presence of pointers from the perspective of contrasting the flow and context sensitivity of the solution procedure with respect to precision and scalability. The results show that the cost of precision of flow- and context-sensitive analysis is not always prohibitive, and that the precision of flow- and context-insensitive analysis is substantially better than worst-case estimates and can be sufficient for certain applications. Program characteristics that affect the performance of data-flow analysis are identified.

We present initial empirical experiments with combined analysis, a scalabk analysis technique that uses a program decomposition to apply different aliasing algorithms to independent program segments. The effectiveness of the solution strategy is validated through application to side-effect and reference analysis of C programs.

Incremental static analysis seeks to efficiently update semantic information about an evolving software system, without recomputing “from scratch.” Interprocedural modification side effect analysis (MOD) calculates the set of variables possibly modified by execution of a procedure or a statement. We introduce a partial incrementalization of MOD for C systems using the hybrid method and present results of a study of 27 C programs, that predicts that our incremental MOD analysis will be substantially cheaper than exhaustive analysis for many program changes.

Pointer aliasing analysis is crucial to compile-time analyses for languages with general-purpose pointer usage (such as C), but many aliasing methods have proven quite costly. We present a technique that partitions the statements of a program to allow separate, and therefore possibly different, pointer aliasing analysis methods to be used on independent parts of the program. This decomposition enables exploration of tradeoff between algorithm efficiency and precision. We also present a new, efficient flow-insensitive pointer aliasing algorithm, which is used together with an existing flow-sensitive aliasing algorithm in our experiments. We demonstrate our technique in the context of determining side effects and variable fetches through names containing pointer dereferences (Thru-deref MOD/REF). Initial empirical results using a combination of a flow-sensitive and a flow-insensitive aliasing analysis on the same program, demonstrate that the resulting analysis is much faster than solely using the flow-sensitive method, and obtains similar precision for the Thru-deref MOD/REF problems.

Multisource data flow problems involve information which may enter nodes independently through different classes of edges. In some cases, dissimilar meet operations appear to be used for different types of nodes. These problems include bidirectional and flow-sensitive problems as well as many static analyses of concurrent programs with synchronization. K-tuple frameworks , a type of standard data flow framework, provide a natural encoding for multisource problems using a single meet operator. Previously, the solution of these problems has been described as the fixed point of a set of data flow equations. Using our k -tuple representation, we can access the general results of standard data flow frameworks concerning convergence time and solution precision for these problems. We demonstrate this for the bidirectional component of partial redundancy suppression and two problems on the program summary graph. An interesting subclass of k -tuple frameworks, the join-of-meets frameworks, is useful for reachability problems, especially those stemming from analyses of explicitly parallel programs. We give results on function space properties for join-of-meets frameworks that indicate precise solutions for most of them will be difficult to obtain.

Parallel data flow analysis methods offer the promise of calculating detailed semantic information about a program at compile-time more efficiently than sequential techniques. Previous work on parallel elimination methods (Zobel, 1990) has been hampered by the lack of control over interval size; this can prohibit effective parallel execution of these methods. To overcome this problem, we have designed the region analysis method, a new elimination method for data flow analysis. Region analysis emphasizes flow graph partitioning to enable better load balancing in a more effective parallel algorithm. We present the design of region analysis and the empirical results we have obtained that indicate: the prevalence of large intervals in flow graphs derived from real programs; and the performance improvement of region analysis over parallel Allen-Cocke interval analysis. Our implementation analyzed programs from the Perfect Benchmarks and netlib running on a Sequent Symmetry S81.>

Def-use analysis links possible value-setting statements for a variable (i.e. definitions) to potential value-fetches (i.e. uses) of that value. This paper describes the first algorithm that calculates accurate interprocedural def-use associations in C software systems. Our algorithm accounts for program-point-specific pointer-induced aliases, though it is currently limited to programs using a single level of indirection. We prove the NP-hardness of the interprocedural reaching definitions problem and describe the approximations made by our polynomial-time algorithm. Initial empirical results are also presented.>

We present a new interprocedural modification side effects algorithm for C programs, that can discern side effects through general-purpose pointer usage. Ours is the first complete design and implementation of such an algorithm. Preliminary performance findings support the practicality of the technique, which is based on our previous approximation algorithm for pointer aliases [LR92]. Each indirect store through a pointer variable is found, on average, to correspond to a store into 1.2 locations. This indicates that our program-point-specific pointer aliasing information is quite precise when used to determine the effects of these stores.

Non-concurrency analysis is a set of techniques for statically identifying pairs (or sets) of statements in a concurrent program which can never happen together. This information aids programmers in debugging and manually optimizing programs, improves the precision of data flow analysis, enables optimized translation of rendezvous, facilitates dead code elimination and other automatic optimizations, and allows anomaly detection in explicitly parallel programs. We present a framework for non-concurrency analysis, capable of incorporating previous analysis algorithms [CS88, DS92] and improving upon them. We show general theoretical results which are useful in estimating non-concurrency, and examples of non-concurrency analysis frameworks for two synchronization primitives: the Ada rendezvous and binary semaphores. Both of these frameworks have a low-order polynomial bound on worst-case solution time. We provide experimental evidence that static non-concurrency analysis of Ada programs can be accomplished in a reasonable time, and is generally quite accurate. Our framework, and the set of refinement components we develop, also exhibits dramatic accuracy improvements over [DS91], when the latter is used as a stand-alone algorithm, as demonstrated by our experiments.

We present a comprehensive approach to performing data flow analysis in parallel. We first identify three types of parallelism inherent in the data flow solution process: independent-problem parallelism, separate-unit parallelism and algorithmic parallelism. We then describe a unified framework to exploit them. Our investigations of typical Fortran programs reveal an abundance of the last two types of parallelism. In particular, we illustrate the exploitation of algorithmic parallelism in the design of our parallel hybrid data flow analysis algorithm and report on its empirical performance.

During execution, when two or more names exist for the same location at some program point, we call them aliases. In a language which allows arbitrary pointers, the problem of determining aliases at a program point is ρ-space-hard [Lan92]. We present an algorithm for the Conditional May Alias problem, which can be used to safely approximate Interprocedural May Alias in the presence of pointers. This algorithm is as precise as possible in the worst case and has been implemented in a prototype analysis tool for C programs. Preliminary speed and precision results are presented.

A?iasing occurs at some program point during execution when two or more names exist for the same location. We have isolated various programming language mechanisms which create aliases. We have classified the complexity of the fllas problem induced by each mechanism alone and in combination, as AfP-hard, complement tip-hard, or polynomial (’P). We present our problem classification, give an overview of our proof that finding interprocedural aliases in the presence of single level pointers is in 7, and present a represent tive proof for the NP-hard problems.

Our exhaustive and incremental hybrid data flow analysis algorithms, based on iteration and elimination techniques, are designed for incremental update of a wide variety of monotone data flow problems in response to source program changes. Unlike previous incremental iterative methods, this incremental algorithm efficiently computes precise and correct solutions. We give theoretical results on the imprecision of restarting iteration for incremental update by fixed point iteration which provided motivation for our algorithm design. Described intuitively, the main algorithm idea is to factor the data flow solution on strong connected components of the flow graph into local and external parts, solving for the local parts by iteration and propagating these effects on the condensation of the flow graph to obtain the entire data flow solution. The incremental hybrid algorithm re-performs those algorithm steps affected by the program changes.

The authors have designed a family of parallel dataflow analysis algorithms for execution on a message-passing MIMD (multiple instruction multiple data) architecture, based on general purpose, hybrid dataflow analysis algorithms. They have exploited the natural task partitioning of the hybrid algorithms and have explored a static mapping-dynamic scheduling strategy. Alternative mapping-scheduling choices and refinements of the flow graph condensation utilized are discussed. This parallel hybrid algorithm family is illustrated on the reaching definitions problem, although parallel algorithms also exist for many interprocedural (e.g., aliasing) and intraprocedural (e.g., available expressions) problems.>

A model of data flow analysis and fixed point iteration solution procedures is presented. The faulty incremental iterative algorithm is introduced. Examples of the imprecision of restarting iteration from the intraprocedural and interprocedural domains are given. Some incremental techniques which calculate precise data flow information are summarized.>

Incremental data flow analysis algorithms have been designed to deal efficiently with change in evolving software systems. These algorithms document the current state of a software system by incorporating change effects into previously derived information describing the definition and use of data in the system. Unfortunately, the performance of these algorithms cannot, in general, be characterized by analytic predictions of their expected behavior. It is possible, however, to observe their performance empirically and predict their average behavior. The authors report on experiments on the empirical profiling of a general-purpose, incremental data flow analysis algorithm. The algorithm, dominator based and coded in C, was applied to statistically significant numbers of feasible, random software systems of moderate size. The experimental results, with quantifiable confidence limits, substantiate the claim that incremental analyses are viable and grow more valuable as a software system grows in size.>

The incremental software maintenance manager (ISMM) is a prototype software maintenance tool which uses incremental static analysis to assess the scope of proposed source code changes. Recently, ISMM has provided the basis for an empirical study of the calling structure of C systems. ISMM has also been used to profile the on-the-average performance of the incremental analysis algorithms. This is the first empirical evaluation of incremental analysis algorithms; it validates their usefulness, especially for large systems. The design and implementation of ISMM are described, and empirical studies of the C system calling structure are summarized.>

We present an algorithm for updating data flow information derived from a program, in response to program edits. Our algorithm, applicable to intraprocedural or interprocedural data flow problems, is more general than previous methods because it can update any monotone data flow problem defined on a reducible flow graph and can handle arbitrary program edits.Rather than design yet another special-purpose data flow update algorithm, we show how to reduce the class of data flow problems to another class of problems which already has a fast update algorithm. More specifically, we reduce a monotone data flow problem formulated for solution using Graham-Wegman elimination [12] to the problem of constructing and decorating an attributed tree structurally isomorphic to the dominator tree of the program flow graph.To update this dominator tree in response to program changes, we first show how to express domination in terms of two local properties of nodes and edges in the flow graph — niceness and deepness. Domination is then updated in response to an edge addition or deletion by repeatedly performing two local operations on the dominator tree, each operation restoring the local properties violated by the edge change. Second, we extend Reps' attributed tree update techniques [19,21,20] and his complexity analysis, to update attribute values in response to changes in this structure.

An incremental update algorithm modifies the solution of a problem that has been changed, rather than re-solving the entire problem. ACINCF and ACINCB are incremental update algorithms for forward and backward data-flow analysis, respectively, based on our equations model of Allen-Cocke interval analysis. In addition, we have studied their performance on a “nontoy” structured programming language L. Given a set of localized program changes in a program written in L, we identify a priori the nodes in its flow graph whose corresponding data-flow equations may be affected by the changes. We characterize these possibly affected nodes by their corresponding program structures and their relation to the original change sites, and do so without actually performing the incremental updates . Our results can be refined to characterize the reduced equations possibly affected if structured loop exit mechanisms are used, either singly or together, thereby relating richness of programming language usage to the ease of incremental updating.

FPOPT, a globally optimizing compiler for FP, was built to study the efficiency of compiling a functional programming language by translating it into an intermediate language and then optimizing that intermediate language. The FPOPT system, the design of the intermediate language and the optimizations performed are described. The relative effectiveness of these optimizations, singly and in combinations, are compared using an instrumented version of FPOPT.>

Computer science departments face an overwhelming demand from the university community for computer literacy courses. In 1982 at Rutgers University we began to offer a “hands-on” literacy course for non-computer science majors. The students learn the rudiments of BASIC, study “how the computer works” by learning a small pseudo-assembly language and experiment with a variety of applications software packages. Applications include text processing, modelling, game playing, CAI and spreadsheets. Our experiences with this course have been positive, although the logistics of handling 960 students per semester are formidable.

In this paper we present ACINCF and ACINCB, incremental update algorithms for forward and backward data flow problems, which are based on a linear equations model of Allen/Cocke interval analysis [Allen 77, Ryder 82a]. We have studied their performance on a robust structured programming language L. Given a set of localized program changes in a program in L, we can identify a priori the nodes in its flow graph whose corresponding data flow equations will be affected by the changes. We can characterize these affected nodes by their corresponding program structures and their relation to the original change sites.

The proliferation of large software systems written in high level programming languages insures the utility of analysis programs which examine interprocedural communications. Often these analysis programs need to reduce the dynamic relations between procedures to a static data representation. This paper presents one such representation, a directed, acyclic graph named the call graph of a program. We delineate the programs representable by an acyclic call graph and present an algorithm for constructing it using the property that its nodes may be linearly ordered. We prove the correctness of the algorithm and discuss the results obtained from an implementation of the algorithm in the PFORT Verifier [1].

Abstract The PFORT Verifier is a program which checks a FORTRAN program (i.e. a main program and a set of subprograms) for adherence to a large, carefully defined, portable subset of American National Standard FORTRAN called PFORT. Unlike many FORTRAN implementations, the Verifier diagnoses errors in interprogram‐unit communication through argument lists and COMMON. The Verifier is itself written in PFORT and has been installed on a variety of computers. This paper describes the development of PFORT and the Verifier. A detailed definition of PFORT noting its differences from ANS FORTRAN is included.