Abstract: 

Algorithmic Complexity (AC) vulnerabilities can be exploited to cause a denial of service attack. Specifically, an adversary can design an input to trigger excessive (space/time) resource consumption. It is not possible to build a fully automated tool to detect AC vulnerabilities. Since it is an open-ended problem, a human-in-loop exploration is required to find the program loops that could have AC vulnerabilities. Ascertaining whether an arbitrary loop has an AC vulnerability is itself difficult, which is equivalent to the halting problem.

This paper is about a pragmatic engineering approach to detect AC vulnerabilities. It presents a statically-informed dynamic (SID) analysis and two tools that provide critical capabilities for detecting AC vulnerabilities. The first is a static analysis tool for exploring the software to find loops as the potential candidates for AC vulnerabilities. The second is a dynamic analysis tool that can try many different inputs to evaluate the selected loops for excessive resource consumption. The two tools are built and integrated together using the interactive software analysis, transformation, and visualization capabilities provided by the Atlas platform.

The paper describes two use cases for the tools, one to detect AC vulnerabilities in a Java bytecode and another to use the tools in an undergraduate algorithm class for students to perform experiments to learn different aspects of algorithmic complexity.

Venue: 16th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2016), Raleigh, North Carolina, October 2, 2016.

Authors: Benjamin Holland, Ganesh Ram Santhanam, Payas Awadhutkar, Suresh Kothari

Paper (PDF): SID-SCAM2016.pdf

Slides (PDF): SID-SCAM2016-slides.pdf

Tool: https://ensoftcorp.github.io/SID

Source Code: https://github.com/EnSoftCorp/SID

https://www.youtube.com/watch?v=8dH7q9aPD44