Attacks relying on the space-time complexity of algorithms implemented by software systems are gaining prominence. Software systems are vulnerable to such attacks if an adversary can inexpensively generate inputs that cause the system to consume an impractically large amount of time or space to process those inputs, thus denying service to benign users or disabling the system. The adversary can also use the same inputs to mount side-channel attacks that aim to infer some secret from the observed space-time system behavior.
In her talk, Corina Pasareanu, Associate Research Professor, NASA, discusses ISSTAC: Integrated Symbolic Execution for Space-Time Analysis of Code. The project has developed automated analysis techniques and implemented them in an industrial-strength tool that allows the efficient analysis of software (in the form of Java bytecode) with respect to space-time complexity vulnerabilities. The analysis is based on symbolic execution, a well-known analysis technique that systematically explores program execution paths and also generates inputs that trigger those paths. Corina gives an overview of the project, highlighting scalability challenges and how they were addressed.