Source-linked AI summary
On the "Naturalness" of Buggy Code
Baishakhi Ray, Vincent Hellendoorn, Saheel Godhane, Zhaopeng Tu, Alberto Bacchelli, Premkumar Devanbu
TL;DR
The paper asks whether code that statistical language models find unnatural is indicative of poor code quality. Using entropy on code implicated in bug-fix commits, it finds that buggy code is more unnatural and becomes more natural when repaired, while entropy-based inspection performs about as cost-effectively as PMD and FindBugs and improves their warning ordering.
Problem
The paper asks whether unnaturalness, measured as entropy or improbability, indicates poor code quality and can identify code implicated in bug fixes.
Method
The paper uses statistical language models to measure code entropy and analyzes code implicated in bug-fix commits, comparing entropy-based inspection with static bug finders using AUCEC.
Results
Buggy code is significantly more unnatural and becomes more natural after repair; entropy-based defect prediction is about as cost-effective as PMD and FindBugs, while entropy ordering improves their warnings.
Takeaways & Limitations
Entropy scores are a useful adjunct to defect prediction and may help influence search-based bug-repair methods.
Takeaways & Limitations
The evidence may omit bugs not identified in commit messages or bugs that remain unfixed, and combined commits may delete non-buggy high-entropy lines or misidentify lines.
Abstract
from arXiv · showhide
Real software, the kind working programmers produce by the kLOC to solve real-world problems, tends to be "natural", like speech or natural language; it tends to be highly repetitive and predictable. Researchers have captured this naturalness of software through statistical models and used them to good effect in suggestion engines, porting tools, coding standards checkers, and idiom miners. This suggests that code that appears improbable, or surprising, to a good statistical language model is "unnatural" in some sense, and thus possibly suspicious. In this paper, we investigate this hypothesis. We consider a large corpus of bug fix commits (ca.~8,296), from 10 different Java projects, and we focus on its language statistics, evaluating the naturalness of buggy code and the corresponding fixes. We find that code with bugs tends to be more entropic (i.e., unnatural), becoming less so as bugs are fixed. Focusing on highly entropic lines is similar in cost-effectiveness to some well-known static bug finders (PMD, FindBugs) and ordering warnings from these bug finders using an entropy measure improves the cost-effectiveness of inspecting code implicated in warnings. This suggests that entropy may be a valid language-independent and simple way to complement the effectiveness of PMD or FindBugs, and that search-based bug-fixing methods may benefit from using entropy both for fault-localization and searching for fixes.
1. INTRODUCTION
The paper tests whether statistical language-model naturalness can identify buggy code, using bug-fix histories to compare defective lines with their fixes and evaluate inspection guidance.
- Motivation: Code naturalness is repetitive and predictable, allowing statistical language models to support several software-engineering tasks.Prior applications include code suggestion, cross-language porting, coding standards, idiom mining, and de-obfuscation.
- Motivation: The paper hypothesizes that syntactically correct but unnatural code is more likely to be defective.Language models assign lower naturalness to rarely encountered code, motivating entropy-based defect localization.
- Study design: The study analyzes 8,296 bug-fix commits from 10 projects and evaluates naturalness at line level.Line-level analysis provides finer prediction granularity than the file- or module-level granularity common in traditional defect prediction.
- Main findings: Buggy code is significantly more unnatural, and its unnaturalness drops significantly when fixes replace it.The paper also reports that entropy-ordered inspection is comparable to FindBugs and PMD, while entropy-based warning ordering improves their performance.
2. BACKGROUND
The background introduces language models, cache-enhanced n-grams, static bug finders, cost-sensitive evaluation, and the research questions connecting code entropy with defect prediction.
- 2.1 Language Modeling: Language models estimate the probability of code sequences as products of token-level conditional probabilities.They model how likely each token is given preceding context.
- 2.1 Language Modeling: N-gram models use a Markov assumption: each token depends only on the previous n−1 tokens.Prefixes sharing those recent tokens are placed in the same equivalence class, making estimation tractable.
- 2.1 Language Modeling: Reverse probabilities using subsequent tokens are also computed to improve identification of buggy lines.The paper estimates n-gram probabilities from training-corpus continuation frequencies and uses epilog information in reverse.
- 2.1 Language Modeling: Cache language models combine global n-gram regularities with local-context regularities through an adaptive interpolation weight.The cache captures locality; γ/(γ + H) gives greater preference to the n-gram model when the prefix appears infrequently in the cache.
- 2.2–2.3 Defect Prediction: The study uses cross-entropy from a cache-enhanced language model to measure line improbability and compares it with static bug finders.Static bug finders such as PMD and FindBugs are fast, widely used, and unsound; both approaches identify lines worthy of inspection.
- 2.3 Evaluating Defect Predictions: AUCEC measures inspection cost against defect-finding payoff, with lift charts comparing prioritized inspection to random inspection.The evaluation also considers partial and full credit criteria for identifying bugs from defective lines.
- 2.4 Research Questions: The research asks whether buggy lines are less natural than non-buggy lines and whether entropy can order static-analysis warnings more effectively.The study also frames bug-fix histories as evidence for testing whether repaired lines become more natural.
3. METHODOLOGY
The study analyzes Java projects and bug-fix histories to compare buggy, fixed, and non-buggy code, using entropy from cache language models to measure code naturalness.
- 3.1 Study Subject: The study covers 10 open-source Java projects from GitHub and the Apache Software Foundation.The projects include web frameworks, databases, search systems, SDKs, and distributed systems.
- 3.1 Study Subject: The data includes 266 snapshots, 782,661 file versions, 202.6 million non-commented source lines, and 8,296 bug-fixing commits.The commits include both development-time and post-release bugs.
- 3.1 Study Subject: The study uses two datasets: project-history snapshots covering ongoing development and selected Apache releases linked to post-release JIRA bugs.The second dataset also includes warnings from FindBugs and PMD for comparison with entropy-based bug finding.
- 3.2 Data Collection: Phase I samples project snapshots every three months, uses git diff to identify changed lines, and excludes commits deleting more than 30 or no lines.The filtering targets buggy lines present in old file versions; the filtered deletion count has a median of 5.
- 3.2 Data Collection: Commits are labeled bug fixes when their logs contain error-related keywords after bag-of-words filtering and stemming.The keywords include terms such as “bug,” “fix,” “issue,” and “defect.”
- 3.2 Data Collection: The analysis compares 58,374,475 unchanged lines, 88,058 buggy lines, and 204,242 fixed lines across the projects.Buggy lines are corrected old-version lines, while fixed lines are their corresponding new-version replacements.
- 3.3 Measuring entropy using cache language model: Entropy is measured with cross-entropy from statistical language models, where code resembling the training corpus receives higher probability and lower entropy.For each file, the cache model is trained on old versions of other files and evaluated on the current file.
- 3.3 Measuring entropy using cache language model: Cache-model parameters are examined using one-line bug fixes from Elasticsearch and Netty, comparing buggy-line entropy with non-buggy lines in the same file.The comparison is expressed as the entropy difference between buggy and non-buggy lines.
4. EVALUATION
The evaluation finds that buggy lines are less natural than non-buggy lines, become more natural after fixes, and can guide inspection competitively with static bug finders.
- RQ1: Buggy versus non-buggy lines: Buggy lines have higher entropies than non-buggy lines, with statistically significant differences.The difference is larger for smaller maximum-delete thresholds and remains significant across studied thresholds.
- RQ2: Entropy after fixes: 1.19 to 1.26 bit: buggy-line entropy drops after bug fixes with 95% confidence.The analysis compares mean entropies of buggy and fixed hunks because individual buggy lines do not always correspond one-to-one with fixed lines.
- RQ2: Entropy after fixes: Some fixes increase entropy, including a 5.75-bit increase caused by a copy-paste error.The copied variable name was common in the corpus, making the buggy line appear natural before correction.
- RQ3: Directing inspection effort: At 20% inspected lines, the default $gram model performs nearly twice as well as random, but at 5% it performs only 17% better.Performance is measured with AUCEC under partial credit and varies across inspection budgets and projects.
- RQ3: Directing inspection effort: Adding line types and bugginess history makes NBF consistently outperform random and generally exceed twice random performance on AUCEC5.The $gram+wType model improves performance in all but one system and is designated NBF for subsequent evaluation.
- RQ4: Comparing and combining predictors: NBF performs comparably to static bug finders, while ordering their warnings by priority and entropy significantly improves their performance.The combined model outperforms both static bug finders in all tested cases and is significantly better than them overall, while remaining similar to NBF.
5. THREATS TO VALIDITY
The study identifies threats involving buggy-line identification, fixed-line comparisons, external validity, cross-language generalization, and evaluation assumptions. The authors argue these issues are unlikely to invalidate the overall results, while acknowledging important scope and measurement constraints.
- Internal validity: Bug-fix commits may contain false negatives and false positives because buggy lines were identified from commit-message-based procedures.Unfixed bugs and omitted bug-fix messages may distort the observed entropy profiles.
- Internal validity: Combining bug fixes with refactorings or formatting may delete non-buggy high-entropy lines, potentially skewing comparisons.The authors expect such lines to be a minority of the studied lines.
- Internal validity: Comparisons between buggy and fixed lines may be skewed if bug-fix commits replace lines with larger numbers of fixed lines.The authors found no evidence of this phenomenon but acknowledge it as a threat.
- Evaluation: The SBF-versus-NBF comparison assumes equally informative indicated lines, although static finders provide specific warnings and NBF marks lines as surprising.The study also credits static-finder warnings even when their warning is unrelated to the overlapping bug.
- Evaluation: AUCEC has been criticized for ignoring the cost of false negatives, motivating future work on better widely accepted measures.This limits how defect-prediction performance should be interpreted.
- Generalizability: System selection threatens external validity, despite including GitHub and Apache systems with varied ages, sizes, and bug ratios.The cross-language sanity check found consistent results in three C/C++ projects, but broader generalization remains an open question.
6. RELATED WORK
Related work frames this study at the intersection of statistical defect prediction, static bug finding, and grammatical error correction. Its distinctive contribution is applying purely statistical language models to defect prediction at line level.
- Statistical defect prediction: Statistical defect prediction learns from historical bug data to rank code locations for inspection under a fixed inspection budget.Earlier approaches commonly operate at file level, though module- and method-level prediction is also possible.
- Statistical defect prediction: This work presents line-level statistical defect prediction as a novel extension of prior defect-prediction granularity.The authors state that previous work had not used purely statistical models to predict defects at line level.
- Static bug finding: Static bug finders use heuristic pattern matching or more formal semantic analyses to locate known categories of defects.FindBugs and PMD exemplify fast, widely used pattern-matching tools, while formal approaches trade speed for stronger guarantees.
- Grammatical error correction: Grammatical error correction differs fundamentally because natural language has a limited vocabulary and enumerable error corrections, unlike open-vocabulary programming languages.Programming-language defects therefore cannot be treated as a similarly closed set of correction choices.
7. CONCLUSION
The conclusion tests whether code naturalness can indicate defects and whether repair makes code more natural. Across the reported analyses, entropy identifies buggy code, complements static bug finders, and may guide automated repair searches.
- Conclusion: Entropy-based language models support the hypothesis that improbable code is more likely to be associated with bugs.The paper treats entropy as an operational measure of code unnaturalness.
- Conclusion: Buggy code tends to become more natural when repaired.The study reports a significant drop in unnaturalness after buggy code is replaced by fix code.
- Conclusion: Entropy-based defect prediction is about as cost-effective as PMD and FindBugs after adjustment for syntactic variance.The comparison concerns directing inspection toward likely defective lines.
- Conclusion: Ordering PMD and FindBugs warnings by associated entropy produces the most cost-effective method reported.The ordering is deterministic and uses entropy scores for warnings produced by the static bug finders.
- Conclusion: The findings suggest entropy can complement defect prediction and influence searches in some automated bug-repair methods.The proposed use includes directing attention to suspicious code and influencing repair search.