Wed 7 Nov 2018 16:15 - 16:37 at Horizons 6-9F - Mining Chair(s): Hridesh Rajan

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 Nov

fse-2018-research-papers
15:30 - 17:00: Research Papers - Mining at Horizons 6-9F
Chair(s): Hridesh RajanIowa State University
fse-2018-Journal-First15:30 - 15:52
Talk
Zhe Yu, Nicholas A. KraftABB Corporate Research, Tim MenziesNorth Carolina State University
DOI
fse-2018-Journal-First15:52 - 16:15
Talk
Miltiadis AllamanisMicrosoft Research, Cambridge, Earl BarrUniversity College London, Christian BirdMicrosoft Research, Prem DevanbuUniversity of California, Mark MarronMicrosoft Research, Charles SuttonUniversity of Edinburgh
DOI
fse-2018-research-papers16:15 - 16:37
Talk
Pan BianRenmin University of China, China, Bin LiangRenmin University of China, China, Wenchang ShiRenmin University of China, China, Jianjun HuangRenmin University of China, China, Yan CaiInstitute of Software, Chinese Academy of Sciences
fse-2018-research-papers16:37 - 17:00
Talk
Daniel DeFreezUniversity of California, Davis, Aditya ThakurUniversity of California, Davis, Cindy Rubio-GonzalezUniversity of California, Davis