research-article

Open access

DISCOVER: detecting algorithmic complexity vulnerabilities

Authors:

Payas Awadhutkar,

Ganesh Ram Santhanam,

Benjamin Holland,

Suresh KothariAuthors Info & Claims

ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Pages 1129 - 1133

https://doi.org/10.1145/3338906.3341177

Published: 12 August 2019 Publication History

Abstract

Algorithmic Complexity Vulnerabilities (ACV) are a class of vulnerabilities that enable Denial of Service Attacks. ACVs stem from asymmetric consumption of resources due to complex loop termination logic, recursion, and/or resource intensive library APIs. Completely automated detection of ACVs is intractable and it calls for tools that assist human analysts.

We present DISCOVER, a suite of tools that facilitates human-on-the-loop detection of ACVs. DISCOVER's workflow can be broken into three phases - (1) Automated characterization of loops, (2) Selection of suspicious loops, and (3) Interactive audit of selected loops. We demonstrate DISCOVER using a case study using a DARPA challenge app. DISCOVER supports analysis of Java source code and Java bytecode. We demonstrate it for Java bytecode.

References

[1]

{n.d.}. XML Security: A Billion Laughs. https://cytinus.wordpress.com/2011/07/ 26/37/.

[2]

Jean-Philippe Aumasson, DJ Bernstein, and M BOBLET. 2012. Hash-flooding DoS reloaded: attacks and defenses. In 29th Chaos Communications Congress.

[3]

Payas Awadhutkar, Ganesh Ram Santhanam, Benjamin Holland, and Suresh Kothari. 2017. Intelligence Amplifying Loop Characterizations for Detecting Algorithmic Complexity Vulnerabilities. In 2017 24th Asia-Pacific Software Engineering Conference (APSEC). IEEE, 249–258.

[4]

Scott A. Crosby and Dan S. Wallach. 2003. Denial of Service via Algorithmic Complexity Attacks. In Proceedings of the 12th Conference on USENIX Security Symposium - Volume 12. USENIX Association, 3–3.

Digital Library

[5]

DARPA. 2014. Space / Time Analysis for Cybersecurity (STAC). Technical Report. Information Innovation Office, Arlington, VA.

[6]

Tom Deering, Suresh Kothari, Jeremias Sauceda, and Jon Mathews. 2014. Atlas: A New Way to Explore Software, Build Analysis Tools. In Companion Proceedings of the 36th International Conference on Software Engineering (ICSE Companion 2014). ACM, New York, NY, USA, 588–591.

Digital Library

[7]

Jens Dietrich, Kamil Jezek, Shawn Rasheed, Amjed Tahir, and Alex Potanin. 2017. Evil Pickles: DoS Attacks Based on Object-Graph Engineering. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 74. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[8]

Yanick Fratantonio, Aravind Machiry, Antonio Bianchi, Christopher Kruegel, and Giovanni Vigna. 2015. CLAPP: characterizing loops in Android applications. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. ACM, 687–697.

Digital Library

[9]

Carlo A Furia, Bertrand Meyer, and Sergey Velder. 2014. Loop invariants: Analysis, classification, and examples. ACM Computing Surveys (CSUR) 46, 3 (2014), 34.

Digital Library

[10]

Benjamin Holland, Payas Awadhutkar, Suresh Kotharti, Ahmed Tamrawi, and Jon Mathews. 2018. Comb: Computing relevant program behaviors. In 2018 IEEE/ACM 40th International Conference on Software Engineering: Companion (ICSE-Companion). IEEE, 109–112.

Digital Library

[11]

Alexander Klink and Julian Walde. 2011. Efficient Denial of Service Attacks on Web Application Platforms. In 28th Chaos Communication Congress.

[12]

Daniel Kroening, Natasha Sharygina, Stefano Tonetta, Aliaksei Tsitovich, and Christoph M Wintersteiger. 2013. Loop summarization using state and transition invariants. Formal Methods in System Design 42, 3 (2013), 221–261.

Digital Library

[13]

MITRE. {n.d.}. CWE-407: Algorithmic Complexity. https://cwe.mitre.org/data/ definitions/407.html.

[14]

Apogee Research. {n.d.}. Public release items for the DARPA Space/Time Analysis for Cybersecurity (STAC) program. https://github.com/Apogee-Research/STAC.

[15]

Ahmed Tamrawi and Suresh Kothari. 2016. Projected Control Graph for Accurate and Efficient Analysis of Safety and Security Vulnerabilities. In Software Engineering Conference (APSEC), 2016 23rd Asia-Pacific. IEEE, 113–120.

[16]

Ahmed Tamrawi and Suresh Kothari. 2018. Projected control graph for computing relevant program behaviors. Science of Computer Programming 163 (2018), 93– 114.

[17]

Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. 2010. Soot: A Java bytecode optimization framework. In CASCON First Decade High Impact Papers. IBM Corp., 214–224.

Digital Library

[18]

Valentin Wüstholz, Oswaldo Olivo, Marijn JH Heule, and Isil Dillig. 2017. Static detection of DoS vulnerabilities in programs that use regular expressions. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 3–20.

Digital Library

Cited By

Wang ZBu DTian WCui B(2024)Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in RecursionApplied Sciences10.3390/app1405185514:5(1855)Online publication date: 23-Feb-2024
https://doi.org/10.3390/app14051855
Misu MAchar RLopes C(2024)SourcererJBF: A Java Build Framework For Large-Scale CompilationACM Transactions on Software Engineering and Methodology10.1145/363571033:3(1-35)Online publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1145/3635710
Liu YMeng WYin HStavrou ACremers CShi E(2022)AcquirerProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3559337(2071-2084)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3559337

Index Terms

DISCOVER: detecting algorithmic complexity vulnerabilities
1. Security and privacy
  1. Software and application security

Recommendations

A moving target defence approach for detecting deception attacks on cyber-physical systems
Abstract
Cyber-physical systems have posed new challenges, affecting their users. The information security of these systems against cyber-attacks is considered one of the most complex issues in a wide range of defences. The present study ...
Security beyond cybersecurity: side-channel attacks against non-cyber systems and their countermeasures
Abstract
Side-channels are unintended pathways within target systems that leak internal information, exploitable via side-channel attack techniques that extract the target information, compromising the system’s security and privacy. Side-channel attacks ...
The Importance of Cybersecurity Awareness Training in the Aviation Industry for Early Detection of Cyberthreats and Vulnerabilities
HCI International 2023 – Late Breaking Papers
Abstract
Nowadays, cybercriminals are targeting organizations to launch cyberattacks by exploiting cyberthreats and vulnerabilities. Hackers keep increasing the sophistication of the cyberattacks to orchestrate the different criminal hacking phases from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

August 2019

1264 pages

ISBN:9781450355728

DOI:10.1145/3338906

General Chairs:
Marlon Dumas
University of Tartu, Estonia
,
Dietmar Pfahl
University of Tartu, Estonia
,
Program Chairs:
Sven Apel
Saarland University, Germany
,
Alessandra Russo
Imperial College, UK

Copyright © 2019 ACM.

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

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESEC/FSE '19

Sponsor:

SIGSOFT

ESEC/FSE '19: 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering

August 26 - 30, 2019

Tallinn, Estonia

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
575
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)13

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZBu DTian WCui B(2024)Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in RecursionApplied Sciences10.3390/app1405185514:5(1855)Online publication date: 23-Feb-2024
https://doi.org/10.3390/app14051855
Misu MAchar RLopes C(2024)SourcererJBF: A Java Build Framework For Large-Scale CompilationACM Transactions on Software Engineering and Methodology10.1145/363571033:3(1-35)Online publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1145/3635710
Liu YMeng WYin HStavrou ACremers CShi E(2022)AcquirerProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3559337(2071-2084)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3559337

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents