Abstract:
Algorithmic complexity vulnerabilities (ACVs) can be exploited to cause denial-of-service. Detecting ACVs is hard because of the numerous kinds of loop complexities that cause ACVs. This renders automatic detection intractable for ACVs. State-of-the-art loop analyses aim to obtain precise loop iteration bounds automatically; they can do so for relatively simple loops. This research focuses on techniques to amplify intelligence so that the analyst can gain a deeper knowledge of complex loops that is necessary to discover ACVs. We describe: (a) loop abstractions and use them to define patterns and other characterizations of loop behaviors which in turn can be applied to create automated filters to isolate complex loops with high likelihood of ACVs, (b) innovative visual querying mechanisms for interactive loop analysis; they enable the analyst to hypothesize ACVs and gather the necessary evidence for targeted dynamic analysis for confirming ACVs. These capabilities are illustrated with an ACV detection case study. We present an empirical study using over 5000 loops from 4 open source libraries, and 18 DARPA challenge apps. The study evaluates the usefulness of the loop characterizations and patterns to enable the analyst to create effective filters to isolate complex loops.
Venue: The 24th Asia-Pacific Software Engineering Conference (APSEC 2017), Nanjing, China, December, 2017.
Authors: Payas Awadhutkar, Ganesh Ram Santhanam, Benjamin Holland, Suresh Kothari