Software QA FYI - SQAFYI

Using Redundancies to Find Errors

By: Yichen Xie and Dawson Engler

Abstract—Programmers generally attempt to perform useful work. If they performed an action, it was because they believed it served some purpose. Redundant operations violate this belief. However, in the past redundant operations have been typically regarded as minor cosmetic problems rather than serious errors. This paper demonstrates that in fact many redundancies are as serious as traditional hard errors (such as race conditions or null pointer dereferences). We experimentally test this idea by writing and applying five redundancy checkers to a number of large open source projects, finding many errors. We then show that even when redundancies are harmless they strongly correlate with the presence of traditional hard errors. Finally we show how flagging redundant operations gives a way to detect mistakes and omissions in specifications. For example, a locking specification that binds shared variables to their protecting locks can use redundancies to detect missing bindings by flagging critical sections that include no shared state.

Index Terms—Extensible compilation, error detection, program redundancy, software quality.

Programming languages have long used the fact that many high-level conceptual errors map to low-level type errors. This paper demonstrates the same mapping in a different direction: many high-level conceptual errors also map to lowlevel redundant operations. With the exception of a few stylized cases, programmers are generally attempting to perform useful work. If they performed an action, it was because they believed it served some purpose. Spurious operations violate this belief and are likely errors. However, in the past redundant operations have been typically regarded as merely cosmetic problems, rather than serious mistakes. Evidence for this perception is that to the best of our knowledge the many recent error checking projects focus solely on hard errors such as null pointer dereferences or failed lock releases, rather than redundancy checking [2], [4], [5], [9], [13], [23], [25]. We experimentally demonstrate that in fact many redundancies signal mistakes as serious as traditional hard errors. For example, impossible Boolean conditions can signal mistaken expressions; critical sections without shared states can signal the use of the wrong variable; variables written but not read can signal an unintentionally lost result. Even when harmless, these redundancies signal conceptual confusion, which we would also expect to correlate with hard errors such as deadlocks, null pointer dereferences, etc.

In this paper we use redundancies to find errors in three ways: (1) by writing checkers that automatically flag redundancies, (2) using these errors to predict non-redundant errors (such as null pointer dereferences), and (3) using redundancies to find incomplete program specifications. We discuss each below.

We wrote five checkers that flagged potentially dangerous redundancies: (1) idempotent operations, (2) assignments that were never read, (3) dead code, (4) conditional branches that were never taken, and (5) redundant NULL-checks. The errors found would largely be missed by traditional type systems and checkers. For example, as Section II shows, assignments of variables to themselves can signal mistakes, yet such assignments will type check in any common programming language we know of.

Of course, some legitimate actions cause redundancies. Defensive programming may introduce “unnecessary” operations for robustness; debugging code, such as assertions, can check for “impossible” conditions; and abstraction boundaries may force duplicate calculations. Thus, to effectively find errors, our checkers must separate such redundancies from those induced by high-level confusion.

The technology behind the checkers is not new. Optimizing compilers use redundancy detection and elimination algorithms extensively to improve code performance. One contribution of our work is the realization that these analyses have been silently finding errors since their invention. We wrote our redundancy checkers in the MC extensible compiler system [15], which makes it easy to build systemspecific static analyses. Our analyses do not depend on an extensible compiler, but it does make it easier to prototype and perform focused suppression of false positive classes. We evaluated how effective flagging redundant operations is at finding dangerous errors by applying the above five checkers to three open source software projects: Linux, OpenBSD and PostgreSQL. These are large, widely-used source code bases (we check 3.3 million lines of them) that serve as a known experimental base. Because they have been written by many people, they are representative of many different coding styles and abilities.

We expect that redundancies, even when harmless, strongly correlate with hard errors. Our relatively uncontroversial hypothesis is that confused or incompetent programmers tend to make mistakes. We experimentally test this hypothesis by taking a large database of hard Linux errors that we found in prior work [8] and measure how well redundancies predict these errors. In our experiments, files that contain redundancies are roughly 45% to 100% more likely to have traditional hard errors compared to those drawn by chance. This difference holds across the different types of redundancies.

Finally, we discuss how traditional checking approaches

based on annotations or specifications can use redundancy checks as a safety net to find missing annotations or incomplete specifications. Such specification mistakes commonly map to redundant operations. For example, assume we have a specification that binds shared variables to locks. A missed binding will likely lead to redundancies: a critical section with no shared state and locks that protect no variables. We can flag such omissions because we know that every lock should protect some shared variable and that every critical section should contain some shared state.

This paper makes four contributions:
1) The idea that redundant operations, like type errors, commonly flag serious correctness errors.
2) Experimentally validating this idea by writing and applying five redundancy checkers to real code. The errors found often surprised us.
3) Demonstrating that redundancies, even when harmless, strongly correlate with the presence of traditional hard errors.
4) Showing how redundancies provide a way to detect dangerous specification omissions.

The main caveat with our approach is that the errors we count might not be errors since we were examining code we did not write. To counter this, we only diagnosed ones that we were reasonably sure about. We have had close to three years of experience with Linux bugs, so we have reasonable confidence that our false positive rate of bugs that we diagnose, while non-zero, is probably less than 5%.

In addition, some of the errors we diagnose are not traditional “hard errors”– they by themselves would probably not cause system crashes or security breaches. Rather, they are nonsensical redundancies that in our opinion result in unnecessary complexity and confusion. So the diagnosis of these errors involve personal judgments that may not be shared by all readers. Although they are not as serious as hard errors, we think they should nevertheless be fixed in order to improve program clarity and readability.

Sections II through VI present the five checkers. Section VII measures how well these redundant errors correlate with and predict traditional hard errors. Section VIII discusses how to check for completeness using redundancies. Section IX discusses related work. Finally, Section X concludes.

Full article...

Other Resource

... to read more articles, visit

Using Redundancies to Find Errors