NAR-Miner: Discovering Negative Association Rules from Code for Bug Detection
Inferring programming rules from source code based on data mining techniques has been proven to be effective to detect software bugs. Existing studies focus on discovering positive rules in the form of $A \Rightarrow B$, indicating that when operation $A$ appears, operation $B$ should also be here. Unfortunately, the negative rules ($A \Rightarrow \neg B$), indicating the mutual suppression or conflict relationships among program elements, have not gotten the attention they deserve. In fact, violating such negative rules can also result in serious bugs.
In this paper, we propose a novel method called NAR-Miner to automatically extract negative association programming rules from large-scale systems, and detect their violations to find bugs.
However, mining negative rules faces a more serious rule explosion problem than mining positive ones. Most of the obtained negative rules are uninteresting and can lead to unacceptable false alarms. To address the issue, we design a semantics-constrained mining algorithm to focus rule mining on the elements with strong semantic relationships. Furthermore, we introduce information entropy to rank candidate negative rules and highlight the interesting ones. Consequently, we effectively mitigate the rule explosion problem. We implement NAR-Miner and apply it to a Linux kernel (v4.12-rc6). The experiments show that the uninteresting rules are dramatically reduced and 17 detected violations have been confirmed as real bugs and patched by kernel community. We also apply NAR-Miner to PostgreSQL, OpenSSL and FFmpeg and discover six real bugs.
Wed 7 NovDisplayed time zone: Guadalajara, Mexico City, Monterrey change
15:30 - 17:00
MiningJournal-First / Research Papers at Horizons 6-9F
Chair(s): Hridesh Rajan Iowa State University
|Finding Better Active Learners for Faster Literature Reviews|
Zhe Yu , Nicholas A. Kraft ABB Corporate Research, Tim Menzies North Carolina State UniversityDOI
|Mining Semantic Loop Idioms|
Miltiadis Allamanis Microsoft Research, Cambridge, Earl T. Barr University College London, Christian Bird Microsoft Research, Prem Devanbu University of California, Mark Marron Microsoft Research, Charles Sutton University of EdinburghDOI
|NAR-Miner: Discovering Negative Association Rules from Code for Bug Detection|
Pan Bian Renmin University of China, China, Bin Liang Renmin University of China, China, Wenchang Shi Renmin University of China, China, Jianjun Huang Renmin University of China, China, Yan Cai Institute of Software, Chinese Academy of Sciences
|Path-Based Function Embedding and Its Application to Error-Handling Specification Mining|
Daniel DeFreez University of California, Davis, Aditya V. Thakur University of California, Davis, Cindy Rubio-González University of California, Davis