Non-Distinguishable Inconsistencies as a Deterministic Oracle for Detecting Security Bugs

Qingyang Zhou, Qiushi Wu, Dinghao Liu, Shouling Ji, Kangjie Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Security bugs like memory errors are constantly introduced to software programs, and recent years have witnessed an increasing number of reported security bugs. Traditional detection approaches are mainly specification-based-detecting violations against a specified rule as security bugs. This often does not work well in practice because specifications are difficult to specify and generalize, leaving complicated and new types of bugs undetected. Recent research thus leans toward deviation-based detection which finds a substantial number of similar cases and detects deviating cases as potential bugs. This, however, suffers from two other problems. First, it requires enough similar cases to find deviations and thus cannot work for custom code that does not have similar cases. Second, code-similarity analysis is probabilistic and challenging, so the detection can be unreliable. Sometimes, similar cases can normally have deviating behaviors under different contexts. In this paper, we propose a novel approach for detecting security bugs based on a new concept called Non-Distinguishable Inconsistencies (NDI). The insight is that if two code paths in a function exhibit inconsistent security states (such as being freed or initialized) that are non-distinguishable from the external, such as the callers, there is no way to recover from the inconsistency from the external, which results in a bug. Such an approach has several strengths. First, it is specification-free and thus can support complicated and new types of bugs. Second, it does not require similar cases and by its nature is deterministic. Third, the analysis is practical by minimizing complicated and lengthy data-flow analysis. We implemented NDI and applied it to well-tested programs, including the OpenSSL library, the FreeBSD kernel, the Apache httpd server, and the PHP interpreter. The results show that NDI works for both large and small programs, and it effectively found 51 new bugs, most of which are otherwise missed by the state-of-the-art detection tools.

Original languageEnglish (US)
Title of host publicationCCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Number of pages15
ISBN (Electronic)9781450394505
StatePublished - Nov 7 2022
Event28th ACM SIGSAC Conference on Computer and Communications Security, CCS 2022 - Los Angeles, United States
Duration: Nov 7 2022Nov 11 2022

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Conference28th ACM SIGSAC Conference on Computer and Communications Security, CCS 2022
Country/TerritoryUnited States
CityLos Angeles

Bibliographical note

Funding Information:
We thank the anonymous reviewers for their valuable suggestions and comments. This research was supported in part by the NSF awards CNS-1815621, CNS-1931208, and CNS-2045478. Any opinions, findings, conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of NSF.

Publisher Copyright:
© 2022 ACM.


  • deterministic bug detection
  • non-distinguishable inconsistencies
  • static analysis


Dive into the research topics of 'Non-Distinguishable Inconsistencies as a Deterministic Oracle for Detecting Security Bugs'. Together they form a unique fingerprint.

Cite this