Statically-Informed Dynamic Analysis Tools to Detect Algorithmic Complexity Vulnerabilities

Authors:
  • BHBenjamin Holland
    Benjamin Holland
  • GSGanesh Ram Santhanam
    Ganesh Ram Santhanam
  • PAPayas Awadhutkar
    Payas Awadhutkar
  • SKSuresh Kothari
    Suresh Kothari
Publisher website
Google Scholar
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 Java bytecode and another for students in an undergraduate algorithm class to perform experiments to learn different aspects of algorithmic complexity Tool and Demo Video: https://ensoftcorp.github.io/SID.