skip to main content
10.1145/2976749.2978383acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
research-article
Open access

SFADiff: Automated Evasion Attacks and Fingerprinting Using Black-box Differential Automata Learning

Published: 24 October 2016 Publication History

Abstract

Finding differences between programs with similar functionality is an important security problem as such differences can be used for fingerprinting or creating evasion attacks against security software like Web Application Firewalls (WAFs) which are designed to detect malicious inputs to web applications. In this paper, we present SFADIFF, a black-box differential testing framework based on Symbolic Finite Automata (SFA) learning. SFADIFF can automatically find differences between a set of programs with comparable functionality. Unlike existing differential testing techniques, instead of searching for each difference individually, SFADIFF infers SFA models of the target programs using black-box queries and systematically enumerates the differences between the inferred SFA models. All differences between the inferred models are checked against the corresponding programs. Any difference between the models, that does not result in a difference between the corresponding programs, is used as a counterexample for further refinement of the inferred models. SFADIFF's model-based approach, unlike existing differential testing tools, also support fully automated root cause analysis in a domain-independent manner.
We evaluate SFADIFF in three different settings for finding discrepancies between: (i) three TCP implementations, (ii) four WAFs, and (iii) HTML/JavaScript parsing implementations in WAFs and web browsers. Our results demonstrate that SFADIFF is able to identify and enumerate the differences systematically and efficiently in all these settings. We show that SFADIFF is able to find differences not only between different WAFs but also between different versions of the same WAF. SFADIFF is also able to discover three previously-unknown differences between the HTML/JavaScript parsers of two popular WAFs (PHPIDS 0.7 and Expose 2.4.0) and the corresponding parsers of Google Chrome, Firefox, Safari, and Internet Explorer. We confirm that all these differences can be used to evade the WAFs and launch successful cross-site scripting attacks.

References

[1]
Peach fuzzer. http://www.peachfuzzer.com/. (Accessed on 08/10/2016).
[2]
F. Aarts, J. D. Ruiter, and E. Poll. Formal models of bank cards for free. In Software Testing, Verification and Validation Workshops (ICSTW), IEEE International Conference on, 2013.
[3]
F. Aarts, J. Schmaltz, and F. Vaandrager. Inference and abstraction of the biometric passport. In Leveraging Applications of Formal Methods, Verification, and Validation. 2010.
[4]
D. Angluin. Learning regular sets from queries and counterexamples. Information and computation, 75(2):87--106, 1987.
[5]
G. Argyros, I. Stais, A. Keromytis, and A. Kiayias. Back in black: Towards formal, black-box analysis of sanitizers and filters. In Security and privacy (S&P), 2016 IEEE symposium on, 2016.
[6]
J. Balcázar, J. Díaz, R. Gavalda, and O. Watanabe. Algorithms for learning finite automata from queries: A unified view. Springer, 1997.
[7]
M. Botincan and D. Babić. Sigma*: Symbolic Learning of Input-Output Specifications. In POPL, 2013.
[8]
C. Brubaker, S. Jana, B. Ray, S. Khurshid, and V. Shmatikov. Using frankencerts for automated adversarial testing of certificate validation in SSL/TLS implementations. In Security and privacy (S&P), 2016 IEEE symposium on, 2014.
[9]
D. Brumley, J. Caballero, Z. Liang, J. Newsome, and D. Song. Towards automatic discovery of deviations in binary implementations with applications to error detection and fingerprint generation. In USENIX Security Symposium (USENIX Security), 2007.
[10]
J. Caballero, S. Venkataraman, P. Poosankam, M. Kang, D. Song, and A. Blum. FiG: Automatic fingerprint generation. Department of Electrical and Computing Engineering, page 27, 2007.
[11]
Y. Chen, T. Su, C. Sun, Z. Su, and J. Zhao. Coverage-directed differential testing of JVM implementations. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 85--99. ACM, 2016.
[12]
T. Chow. Testing software design modeled by finite-state machines. IEEE transactions on software engineering, (3):178--187, 1978.
[13]
T. H. Cormen. Introduction to algorithms. MIT press, 2009.
[14]
L. D'Antoni and M. Veanes. Minimization of symbolic automata. In ACM SIGPLAN Notices, volume 49, pages 541--553. ACM, 2014.
[15]
P. Fiterau-Broştean, R. Janssen, and F. Vaandrager. Learning fragments of the TCP network protocol. In Formal Methods for Industrial Critical Systems. 2014.
[16]
P. Fiterau-Broştean, R. Janssen, and F. Vaandrager. Combining model learning and model checking to analyze TCP implementations. In International Conference on Computer-Aided Verification (CAV). 2016.
[17]
Fyodor. Remote OS detection via TCP/IP fingerprinting (2nd generation).
[18]
A. Groce, G. Holzmann, and R. Joshi. Randomized differential testing as a prelude to formal verification. In International Conference on Software Engineering (ICSE), 2007.
[19]
A. Groce, D. Peled, and M. Yannakakis. Adaptive model checking. In Tools and Algorithms for the Construction and Analysis of Systems, pages 357--370. 2002.
[20]
J. Jung, A. Sheth, B. Greenstein, D. Wetherall, G. Maganis, and T. Kohno. Privacy oracle: a system for finding application leaks with black box differential testing. In CCS, 2008.
[21]
D. Kozen. Lower bounds for natural proof systems. In FOCS, 1977.
[22]
F. Massicotte and Y. Labiche. An analysis of signature overlaps in Intrusion Detection Systems. In IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2011.
[23]
W. McKeeman. Differential testing for software. Digital Technical Journal, 10(1), 1998.
[24]
H. Raffelt, B. Steffen, and T. Berg. Learnlib: A library for automata learning and experimentation. In Proceedings of the 10th international workshop on Formal methods for industrial critical systems (FMICS), 2005.
[25]
D. Richardson, S. Gribble, and T. Kohno. The limits of automatic OS fingerprint generation. In ACM workshop on Artificial intelligence and security (AISec), 2010.
[26]
J. D. Ruiter and E. Poll. Protocol state fuzzing of TLS implementations. In USENIX Security Symposium (USENIX Security), 2015.
[27]
G. Shu and D. Lee. Network Protocol System Fingerprinting-A Formal Approach. In IEEE Conference on Computer Communications (INFOCOM), 2006.
[28]
M. Sipser. Introduction to the Theory of Computation, volume 2. Thomson Course Technology Boston, 2006.
[29]
M. Veanes, P. D. Halleux, and N. Tillmann. Rex: Symbolic regular expression explorer. In International Conference on Software Testing, Verification and Validation (ICST), 2010.
[30]
M. Veanes, P. Hooimeijer, B. Livshits, D. Molnar, and N. Bjorner. Symbolic finite state transducers: Algorithms and applications. ACM SIGPLAN Notices, 47, 2012.
[31]
W. Xu, Y. Qi, and D. Evans. Automatically evading classifiers a case study on PDF malware classifiers. In Proceedings of the 2016 Network and Distributed Systems Symposium (NDSS), 2016.
[32]
X. Yang, Y. Chen, E. Eide, and J. Regehr. Finding and understanding bugs in C compilers. In PLDI, 2011.

Cited By

View all
  • (2024)SMBugFinder: An Automated Framework for Testing Protocol Implementations for State Machine BugsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3685310(1866-1870)Online publication date: 11-Sep-2024
  • (2024)TLS-DeepDiffer: Message Tuples-Based Deep Differential Fuzzing for TLS Protocol Implementations2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00100(918-928)Online publication date: 12-Mar-2024
  • (2024)Aligning agent-based testing (ABT) with the experimental research paradigm: a literature review and best practicesJournal of Computational Social Science10.1007/s42001-024-00283-67:2(1625-1644)Online publication date: 16-May-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
October 2016
1924 pages
ISBN:9781450341394
DOI:10.1145/2976749
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2016

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. automata learning
  2. differential testing
  3. evasion attacks
  4. fingerprints
  5. web application firewalls

Qualifiers

  • Research-article

Funding Sources

  • Office of Naval Research (ONR)
  • H2020
  • ERC

Conference

CCS'16
Sponsor:

Acceptance Rates

CCS '16 Paper Acceptance Rate 137 of 831 submissions, 16%;
Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)156
  • Downloads (Last 6 weeks)22
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)SMBugFinder: An Automated Framework for Testing Protocol Implementations for State Machine BugsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3685310(1866-1870)Online publication date: 11-Sep-2024
  • (2024)TLS-DeepDiffer: Message Tuples-Based Deep Differential Fuzzing for TLS Protocol Implementations2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00100(918-928)Online publication date: 12-Mar-2024
  • (2024)Aligning agent-based testing (ABT) with the experimental research paradigm: a literature review and best practicesJournal of Computational Social Science10.1007/s42001-024-00283-67:2(1625-1644)Online publication date: 16-May-2024
  • (2023)BLEDiff: Scalable and Property-Agnostic Noncompliance Checking for BLE Implementations2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179330(3209-3227)Online publication date: May-2023
  • (2022)Coverage-guided differential testing of TLS implementations based on syntax mutationPLOS ONE10.1371/journal.pone.026217617:1(e0262176)Online publication date: 24-Jan-2022
  • (2022)Model-Based Grey-Box Fuzzing of Network ProtocolsSecurity and Communication Networks10.1155/2022/68806772022Online publication date: 1-Jan-2022
  • (2022)Learning Relationship-Based Access Control Policies from Black-Box SystemsACM Transactions on Privacy and Security10.1145/351712125:3(1-36)Online publication date: 19-May-2022
  • (2022)Active Learning of Discriminative Subgraph Patterns for API Misuse DetectionIEEE Transactions on Software Engineering10.1109/TSE.2021.306997848:8(2761-2783)Online publication date: 1-Aug-2022
  • (2022)HDiff: A Semi-automatic Framework for Discovering Semantic Gap Attack in HTTP Implementations2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN53405.2022.00014(1-13)Online publication date: Jun-2022
  • (2022)Fingerprinting and analysis of Bluetooth devices with automata learningFormal Methods in System Design10.1007/s10703-023-00425-y61:1(35-62)Online publication date: 1-Aug-2022
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media