ACSploit: Exploit Algorithmic Complexity Vulnerabilities

Presented at Black Hat Asia 2019, March 28, 2019, 10:15 a.m. (30 minutes)

Algorithmic Complexity (AC) vulnerabilities arise when a program uses an algorithm with a particularly inefficient worst-case computational complexity, and allows a user to provide input that will trigger it. Determining whether a program is vulnerable requires more than an understanding of what algorithms the program implements. It also requires understanding how user input is filtered and formatted before it's given to the potentially exploitable algorithm. One way to do this is with time consuming manual analysis, such as reverse engineering, static code review, or debugging. Alternatively, feeding the algorithm input formatted to trigger its worst case, and then measuring the effects in time (i.e. CPU utilization) and space (e.g. RAM or disk usage) is quicker and requires less skill.

ACsploit is a command-line utility that generates worst-case inputs to commonly used algorithms, such as sorting, hashing, string manipulation, etc. It is modular and highly configurable, supporting a wide variety of user-specified constraints on the generated output, allowing it to appropriately fit the requirements of the application under test. ACsploit also supports an equally wide array of output formats to assist the user in delivering the resulting exploit from ACsploit to the target system. ACsploit supports both script-driven and interactive uses through a familiar Metasploit-like interface. Originally developed under the DARPA STAC program to help rapidly triage potential AC vulnerabilities, we are now releasing ACsploit as an open-source tool to the broader vulnerability researcher community.

ACsploit comes with algorithmic complexity exploits for 30+ algorithms and is easily extensible. It's designed to allow members of the community to contribute new exploit modules, input constraints, and output formatters to expand upon all aspects of its functionality. Future plans for the development of ACsploit include debugger integration and a testing framework for measuring resource usage by the targeted application.


Presenters:

  • Scott Tenaglia - Research Director, Two Six Labs
    Mr. Scott Tenaglia is a Research Director and Principal Research Engineer focusing on algorithmic complexity, side-channel, and memory corruption vulnerabilities through static reverse engineering, dynamic program tracing, and symbolic execution. Previously, Mr. Tenaglia was a Lead Cyber Security Engineer at MITRE Corporation. While at MITRE, Mr. Tenaglia supported a number of research and operational programs focused on all aspects of binary and program analysis, including reverse engineering, vulnerability research, incident response and malware analysis. Mr. Tenaglia earned bachelors degrees in Computer Science and Mathematics from Purdue University, and a masters degree in Computer Science with a concentration in Machine Learning from Johns Hopkins University.

Links:

Similar Presentations: