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.