In May 2009, Google conducted a company wide FindBugs "fixit". Hundreds of engineers reviewed thousands of FindBugs warnings, and fixed or filed reports against many of them. In this paper, we discuss the lessons learned from this exercise, and analyze the resulting dataset, which contains data about how warnings in each bug pattern were classified. Significantly, we observed that even though most issues were flagged for fixing, few appeared to be causing any serious problems in production. This suggests that most interesting software quality problems were eventually found and fixed without FindBugs, but FindBugs could have found these problems early, when they are cheap to remediate. We compared this observation to bug trends observed in code snapshots from student projects.

Many analysis techniques have been proposed to determine when a potentially null value may be dereferenced. But we have observed in practice that not every potential null dereference is a "bug" that developers want to fix. In this paper we discuss some of the challenges of using a null dereference analysis in practice, and reasons why developers may not feel it necessary to change code to prevent ever possible null dereference. We revisit previous work on XYLEM, an interprocedural null dereference analysis for Java, and discuss the challenge of comparing the results of different static analysis tools. We also report experimental results for XYLEM, Coverity Prevent, Fortify SCA, Eclipse and FindBugs, and observe that the different tools tradeoff the need to flag all potential null dereferences with the need to minimize the number of cases that are implausible in practice. We conclude by discussing whether it would be useful to extend the Java type system to distinguish between nullable and nonnull types, and prohibit unchecked dereferences of nullable types.

Recent research has tried to identify changes in source code repositories that fix bugs by linking these changes to reports in issue tracking systems. These changes have been traced back to the point in time when they were previously modified as a way of identifying bug introducing changes. But we observe that not all changes linked to bug tracking systems are fixing bugs; some are enhancing the code. Furthermore, not all fixes are applied at the point in the code where the bug was originally introduced. We flesh out these observations with a manual review of several software projects, and use this opportunity to see how many defects are in the scope of static analysis tools.

Object layout schemes used in C++ and other languages rely on (sometimes numerous) compiler generated fields. We describe a language-independent object layout scheme, which is space optimal, that is, objects are contiguous, and contain no compiler generated fields other than a single type identifier. As in C++ and other multiple inheritance languages such as CECIL and DYLAN, the new scheme sometimes requires extra levels of indirection to access some of the fields. Using a data set of 28 hierarchies, totaling almost 50,000 types, we show that this scheme improves field access efficiency over standard implementations, and competes favorably with (the non-space-optimal) highly optimized C++ specific implementations. The benchmark includes an analytical model for computing the frequency of indirections in a sequence of field access operations. Our layout scheme relies on whole-program analysis, which requires about 10 microseconds per type on a contemporary architecture (Pentium III, 900Mhz, 256MB machine), even in very large hierarchies. We also present a layout scheme for separate compilation using the user-annotation of virtual inheritance edge that is used in C++.

There are many difficulties associated with developing correct multithreaded software, and many of the activities that are simple for single threaded software are exceptionally hard for multithreaded software. One such example is constructing unit tests involving multiple threads. Given, for example, a blocking queue implementation, writing a test case to show that it blocks and unblocks appropriately using existing testing frameworks is exceptionally hard. In this paper, we describe the MultithreadedTC framework which allows the construction of deterministic and repeatable unit tests for concurrent abstractions. This framework is not designed to test for synchronization errors that lead to rare probabilistic faults under concurrent stress. Rather, this framework allows us to demonstrate that code does provide specific concurrent functionality (e.g., a thread attempting to acquire a lock is blocked if another thread has the lock). We describe the framework and provide empirical comparisons against hand-coded tests designed for Sun’s Java concurrency utilities library and against previous frameworks that addressed this same issue. The source code for this framework is available under an open source license.

Static analysis tools for software defect detection are becoming widely used in practice. However, there is little public information regarding the experimental evaluation of the accuracy and value of the warnings these tools report. In this paper, we discuss the warnings found by FindBugs, a static analysis tool that finds defects in Java programs. We discuss the kinds of warnings generated and the classification of warnings into false positives, trivial bugs and serious bugs. We also provide some insight into why static analysis tools often detect true but trivial bugs, and some information about defect warnings across the development lifetime of software release. We report data on the defect warnings in Sun's Java 6 JRE, in Sun's Glassfish JEE server, and in portions of Google's Java codebase. Finally, we report on some experiences from incorporating static analysis into the software development process at Google.

At the University of Maryland, we have been working to improve the reliability and security of software by developing new, effective static analysis tools. These tools scan software for bug patterns or show that the software is free from a particular class of defects. There are two themes common to our different projects: 1. Our ultimate focus is on utility: can a programmer actually improve the quality of his or her software using an analysis tool? The important first step toward answering this question is to engineer tools so that they can analyze existing, nontrivial programs, and to carefully report the results of such analyses experimentally. The desire to better understand a more human-centered notion of utility underlies much of our future work. 2. We release all of our tools open source. This allows other researchers to verify our results, and to reuse some or all of our implementations, which often required significant effort to engineer. We believe that releasing source code is important for accelerating the pace of research results software quality, and just as importantly allows feedback from the wider community. In this research group presentation, we summarize some recent work and sketch future directions.

In the summer of 2006, the FindBugs project was challenged to improve the null pointer analysis in FindBugs so that we could find more null pointer bugs. In particular, we were challenged to try to do as well as a publicly available analysis by Reasoning, Inc on version 4.1.24 of Apache Tomcat. Reasoning's report is a result of running their own static analysis tool and using manual auditing to remove false positives. Reasoning reported a total of 9 null pointer warnings in Tomcat 4.1.24, of which only 2 were reported by FindBugs 1.0. While we wanted to improve the analysis in FindBugs, we wanted to retain our current low level of false positives.

We developed Marmoset, an automated submission and testing system, to explore techniques to provide improved feedback to both students and instructors as students work on programming assignments, and to collect data to perform detailed research on the development processes of students. To address the issue of feedback, Marmoset provides students with limited access to the results of the instructor's private test cases using a novel token-based incentive system. This both encourages students to start their work early and to think critically about their work. Because students submit early, instructors can monitor all students' progress on test cases, helping identify challenging or ambiguous test cases early in order to update the project specification or devote additional time in lecture or lab sessions to the difficult test cases.To study and better understand the development process of students, Marmoset can be configured to transparently capture snapshots to a central repository everytime students save their files. These detailed development histories offer a unique, detailed perspective of each student's progress on a programming assignment, from the first line of code written and saved all the way through the final edit before the final submission. This type of data has proven extremely valuable many uses, such as mining new bug patterns and evaluating existing bug-finding tools.In this paper, we describe our initial experiences using Marmoset in several introductory computer science courses, from the perspectives of both instructors and students. We also describe some initial research results from analyzing the student snapshot database.

Using static analysis to detect memory access errors, such as null pointer dereferences, is not a new problem. However, much of the previous work has used rather sophisticated analysis techniques in order to detect such errors.In this paper we show that simple analysis techniques can be used to identify many such software defects, both in production code and in student code. In order to make our analysis both simple and effective, we use a non-standard analysis which is neither complete nor sound. However, we find that it is effective at finding an interesting class of software defects.We describe the basic analysis we perform, as well as the additional errors we can detect using techniques such as annotations and inter-procedural analysis.In studies of both production software and student projects, we find false positive rates of around 20% or less. In the student code base, we find that our static analysis techniques are able to pinpoint 50% to 80% of the defects leading to a null pointer exception at runtime.

This paper describes the new Java memory model, which has been revised as part of Java 5.0. The model specifies the legal behaviors for a multithreaded program; it defines the semantics of multithreaded Java programs and partially determines legal implementations of Java virtual machines and compilers.The new Java model provides a simple interface for correctly synchronized programs -- it guarantees sequential consistency to data-race-free programs. Its novel contribution is requiring that the behavior of incorrectly synchronized programs be bounded by a well defined notion of causality. The causality requirement is strong enough to respect the safety and security properties of Java and weak enough to allow standard compiler and hardware optimizations. To our knowledge, other models are either too weak because they do not provide for sufficient safety/security, or are too strong because they rely on a strong notion of data and control dependences that precludes some standard compiler transformations.Although the majority of what is currently done in compilers is legal, the new model introduces significant differences, and clearly defines the boundaries of legal transformations. For example, the commonly accepted definition for control dependence is incorrect for Java, and transformations based on it may be invalid.In addition to providing the official memory model for Java, we believe the model described here could prove to be a useful basis for other programming languages that currently lack well-defined models, such as C++ and C#.

The Java memory model described in Chapter 17 of the Java Language Specification gives constraints on how threads interact through memory. This chapter is hard to interpret and poorly understood; it imposes constraints that prohibit common compiler optimizations and are expensive to implement on existing hardware. Most JVMs violate the constraints of the existing Java memory model; conforming to the existing specification would impose significant performance penalties. In addition, programming idioms used by some programmers and used within Sun's Java Development Kit is not guaranteed to be valid according to the existing Java memory model.Furthermore, implementing Java on a shared-memory multiprocessor that implements a weakmemory model poses some implementation challenges not previously considered. Copyright © 2000 John Wiley & Sons, Ltd.

Java class files are often distributed as jar files, which are collections of individually compressed class files (and possibility other files). Jar files are typically about 1/2 the size of the original class files due to compression. I have developed a wire-code format for collections of Java class files. This format is typically 1/2 to 1/5 of the size of the corresponding compressed jar file (1/4 to 1/10 the size of the original class files).

Model checking is a powerful technique for analyzing large, finite-state systems. In an infinite state system, however, many basic properties are undecidable. In this article, we present a new symbolic model checker which conservatively evaluates safety and liveness properties on programs with unbounded integer variables. We use Presburger formulas to symbolically encode a program's transition system, as well as its model-checking computations. All fixpoint calculations are executed symbolically, and their convergence is guaranteed by using approximation techniques. We demonstrate the promise of this technology on some well-known infinite-state concurrency problems.

Traditional array dependence analysis, which detects potential memory aliasing of array references is a key analysis technique for automatic parallelization. Recent studies of benchmark codes indicate that limitations of analysis cause many compilers to overlook large amounts of potential parallelism, and that exploiting this parallelism requires algorithms to answer new question about array references, not just get better answers to the old questions of aliasing. We need to ask about the flow of values in arrays, to check the legality of array privatization, and about the conditions under which a dependence exists, to obtain information about conditional parallelism. In some cases, we must answer these questions about code containing nonlinear terms in loop bounds or subscripts. This article describes techniques for phrasing these questions in terms of systems of contstraints. Conditional dependence analysis can be performed with a constraint operation we call the "gist" operation. When subscripts and loop bounds are affine, questions about the flow of values in array variables can be phrased in terms of Presburger Arithmetic. When the constraints describing a dependence are not affine, we introduce uninterpreted function symbols to represent the nonaffine terms. Our constraint language also provides a rich language for communication with the dependence analyzer, by either the programmer or other phases of the compiler. This article also documents our investigations of the praticality of our approach. The worst-case complexity of Presburger Arithmetic indicates that it might be unsuitable for any practical application. However, we have found that analysis of benchmark programs does not cause the exponential growth in the number of constraints that could occur in the worst case. We have studied the constraints produced during our aanalysis, and identified characteristics that keep our algorithms free of exponential behavior in practice.

Program slicing is an analysis that answers questions such as "Which statements might affect the computation of variable v at statement s?" or "Which statements depend on the value of v computed in statement s?". The answers computed by program slicing are generally a set of statements. We introduce the idea of iteration spacing slicing: we refine program slicing to ask questions such as "Which iterations of which statements might effect the computation in iterations I of statement s?" or "Which iterations of which statements depend on the value computed by iterations I of statement s?". One application of this general-purpose technique is optimization of interprocessor communication in data-parallel compilers. For example, we can separate a code fragment into 1) those iterations that must be done before a send, 2) those iterations that don't need to be done before a send and don't depend on non-local data and 3), those iterations that depend on non-local data. We examine application...

All existing methods for automated data/computation decomposition share a common failing: they are very sensitive

In many real-time systems relative timing constraints are imposed on a set of tasks. Generating a correct ordering for the tasks and deriving their proper start-time assignments is an NP-hard problem; it subsumes the non-preemptive scheduling problem. Even when the application imposes a total order on the tasks, generating proper start-times is still nontrivial if execution times may range between upper and lower bounds. We present the technique of parametric dispatching to enforce such timing constraints. During an off-line component, we check if the constraints can be guaranteed. If so, a calendar is produced that allows our on-line algorithm to generate upper and lower bounds on the start time of each task, based on the start times and execution times of previous tasks. A suitable start time for the task may then be selected taking into account the presence of other non-critical tasks in the system.>

Array data dependence analysis methods currently in use generate false dependences that can prevent useful program transformations. These false dependences arise because the questions asked are conservative approximations to the questions we really should be asking. Unfortunately, the questions we really should be asking go beyond integer programming and require decision procedures for a subclass of Presburger formulas. In this paper, we describe how to extend the Omega test so that it can answer these queries and allow us to eliminate these false data dependences. We have implemented the techniques described here and believe they are suitable for use in production compilers.>

We describe methods that are able to count the number of integer solutions to selected free variables of a Presburger formula, or sum a polynomial over all integer solutions of selected free variables of a Presburger formula. This answer is given symbolically, in terms of symbolic constants (the remaining free variables in the Presburger formula).For example, we can create a Presburger formula who's solutions correspond to the iterations of a loop. By counting these, we obtain an estimate of the execution time of the loop.In more complicated applications, we can create Presburger formulas who's solutions correspond to the distinct memory locations or cache lines touched by a loop, the flops executed by a loop, or the array elements that need to be communicated at a particular point in a distributed computation. By counting the number of solutions, we can evaluate the computation/memory balance of a computation, determine if a loop is load balanced and evaluate message traffic and allocate message buffers.

Existing compilers often fail to parallelize sequential code, even when a program can be manually transformed into parallel form by a sequence of well-understood transformations (as in the case for many of the Perfect Club Benchmark programs). These failures can occur for several reasons: the code transformations implemented in the compiler may not be sufficient to produce parallel code, the compiler may not find the proper sequence of transformations, or the compiler may not be able to prove that one of the necessary transformations is legal. When a compiler fails to extract sufficient parallelism from a program, the programmer may try to extract additional parallelism. Unfortunately, the programmer is typically left to search for parallelism without significant assistance. The compiler generally does not give feedback about which parts of the program might contain additional parallelism, or about the types of transformations that might be needed to realize this parallelism. Standard program transformations and dependence abstractions cannot be used to provide this feedback. In this paper, we propose a two-step approach to the search for parallelism in sequential programs. In the first step, we construct several sets of constraints that describe, for each statement, which iterations of that statement can be executed concurrently. By constructing constraints that correspond to different assumptions about which dependences might be eliminated through additional analysis, transformations, and user assertions, we can determine whether we can expose parallelism by eliminating dependences. In the second step of our search for parallelism, we examine these constraint sets to identify the kinds of transformations needed to exploit scalable parallelism. Our tests will identify conditional parallelism and parallelism that can be exposed by combinations of transformations that reorder the iteration space (such as loop interchange and loop peeling). This approach lets us distinguish inherently sequential code from code that contains unexploited parallelism. It also produces information about the kinds of transformations needed to parallelize the code, without worrying about the order of application of the transformations. Furthermore, when our dependence test is inexact we can identify which unresolved dependences inhibit parallelism by comparing the effects of assuming dependence or independence. We are currently exploring the use of this information in programmer-assisted parallelization.

Array data dependence analysis methods currently in use generate false dependences that can prevent useful program transformations. These false dependences arise because the questions asked are conservative approximations to the questions we really should be asking. Unfortunately, the questions we really should be asking go beyond integer programming and require decision procedures for a sublcass of Presburger formulas. In this paper, we describe how to extend the Omega test so that it can answer these queries and allow us to eliminate these false data dependences. We have implemented the techniques described here and believe they are suitable for use in production compilers.

Article Free Access Share on Partial evaluation of high-level imperative programming languages with applications in hard real-time systems Authors: Vivek Nirkhe View Profile , William Pugh View Profile Authors Info & Claims POPL '92: Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesFebruary 1992 Pages 269–280https://doi.org/10.1145/143165.143223Published:01 February 1992Publication History 25citation374DownloadsMetricsTotal Citations25Total Downloads374Last 12 Months15Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Many differentkinds of loop transformations have been described, such as loop interchange, loop skewing and loop fusion.Each transformation requires its own particular set of dependence analysis tests and paraltelizing a section of code may require perforfig a series of transformations.

The use of high-level programming constructs makes it difficult to estimate at compile-time the execution time and resource requirements of a program. The authors contend that partial evaluation provides a solution to this problem. They describe the application of partial evaluation to programming languages for hard-real-time systems and give examples of programs handled by the techniques. They discuss how the system appears from a user's perspective, provide a brief overview of the partial evaluation techniques used, and describe some limitations of the techniques and possible solutions. >

The Omega test is an integer programming algorithm that can determine whether a dependence exists between two array references, and if so, under what conditions. Conventional wisdom holds that integer programming techniques are far too expensive to be used for dependence analysis, except as a method of last resort for situations that cannot be decided by simpler methods. We present evidence that suggests this wisdom is wrong, and that the Omega test is competitive with approximate algorithms used in practice and suitable for use in production compilers. Experiments suggest that, for almost all programs, the average time required by the Omega test to determine the direction vectors for an array pair is less than 500 ¯secs on a 12 MIPS workstation. The Omega test is based on an extension of Fourier-Motzkin variable elimination (a linear programming method) to integer programming, and has worst-case exponential time complexity. However, we show that for many situations in which other (po...

Much recent work in polymorphic programming languages allows subtyping and multiple inheritance for records. In such systems, we would like to extract a field from a record with the same efficiency as if we were not making use of subtyping and multiple inheritance. Methods currently used make field extraction 3-5 times slower, which can produce a significant overall performance slowdown.

Article Free Access Share on Incremental computation via function caching Authors: W. Pugh Dept. of Computer Science, Cornell University, Ithaca, NY and Dept. of Comp. Sci., Univ. of Maryland, College Park, Md. Dept. of Computer Science, Cornell University, Ithaca, NY and Dept. of Comp. Sci., Univ. of Maryland, College Park, Md.View Profile , T. Teitelbaum Dept. of Computer Science, Cornell University, Ithaca, NY Dept. of Computer Science, Cornell University, Ithaca, NYView Profile Authors Info & Claims POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1989 Pages 315–328https://doi.org/10.1145/75277.75305Published:03 January 1989Publication History 138citation969DownloadsMetricsTotal Citations138Total Downloads969Last 12 Months130Last 6 weeks25 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF