Symbolic execution is a well-studied method that has a number of useful applications, including generation of high-quality test suites that find many bugs. However, scaling it to real-world applications is a significant challenge, as it depends on the often expensive process of solving constraints on program inputs. Our insight is that when the goal of symbolic execution is test generation, non-semantics-preserving program transformations can reduce the cost of symbolic execution and the tests generated for the transformed programs can still serve as quality suites for the original program. We present five such transformations based on a few different program simplification heuristics that are designed to lower the cost of symbolic execution for input generation. As enabling technology we use the KLEE symbolic execution engine and the LLVM compiler infrastructure. We evaluate our transformations using a suite of small subjects as well as a subset of the well-studied Unix Coreutils. In a majority of cases, our approach reduces the time for symbolic execution for input generation and increases code coverage of the resultant suite.

Web applications can leak confidential user information due to the presence of unintended side-channel vulnerabilities in code. One particularly subtle class of side-channel vulnerabilities arises due to resource usage imbalances along different execution paths of a program. Such side-channel vulnerabilities are especially severe if the resource usage imbalance is asymptotic. This paper formalizes the notion of asymptotic resource side-channels and presents a lightweight static analysis algorithm for automatically detecting them. Based on these ideas, we have developed a tool called SCANNER that detects resource-related side-channel vulnerabilities in PHP applications. SCANNER has found 18 zero-day security vulnerabilities in 10 different web applications and reports only 2 false positives. The vulnerabilities uncovered by SCANNER can be exploited using cross-site search attacks to extract various kinds of confidential information, such as a user's medications or purchase history.

This paper describes a new class of denial-of-service (DoS) attack, which we refer to as Second Order DoS attacks. These attacks consist of two phases, one that pollutes a database with junk entries and another that performs a costly operation on these entries to cause resource exhaustion. The main contribution of this paper is a static analysis for detecting second-order DoS vulnerabilities in web applications. We have implemented our analysis in a tool called Torpedo, and we show that Torpedo can successfully detect second-order DoS vulnerabilities in widely used web applications written in PHP. Once our tool discovers a vulnerability, it also performs symbolic execution to generate candidate attack vectors. We evaluate Torpedo on six widely-used web applications and show that it uncovers 37 security vulnerabilities, while reporting 18 false positives.

Systematic testing plays a vital role in increasing software reliability. A particularly effective and popular approach for systematic testing is symbolic execution, which analyzes a large number of program behaviors using symbolic inputs. Even though symbolic execution is among the most studied analyses during the last decade, scaling it to real-world applications remains a key challenge. This paper studies how a class of semantics-preserving program transformations, namely compiler optimizations, which are designed to enhance performance of standard program execution (using concrete inputs), influence traditional symbolic execution. As an enabling technology, the study uses KLEE, a well-known symbolic execution engine based on the LLVM compiler infrastructure, and focuses on 33 optimization flags of LLVM. Our specific research questions include: (1) how different optimizations influence the performance of symbolic execution for Unix Coreutils, (2) how the influence varies across two different program classes, and (3) how the influence varies across three different back-end constraint solvers. Some of our findings surprised us. For example, applying the 33 optimizations in a pre-defined order provides a slowdown (compared to applying no optimization) for a majority of the Coreutils when using the basic depth-first search with no constraint caching. The key finding of our work is that standard compiler optimizations need to be used with care when performing symbolic execution for creating tests that provide high code coverage. We hope our study motivates future research on harnessing the power of symbolic execution more effectively for enhancing software reliability, e.g., by designing program transformations specifically to scale symbolic execution or by studying broader classes of traditional compiler optimizations in the context of different search heuristics, memoization, and other strategies employed by modern symbolic execution tools.

This paper identifies and formalizes a prevalent class of asymptotic performance bugs called redundant traversal bugs and presents a novel static analysis for automatically detecting them. We evaluate our technique by implementing it in a tool called CLARITY and applying it to widely-used software packages such as the Google Core Collections Library, the Apache Common Collections, and the Apache Ant build tool. Across 1.6M lines of Java code, CLARITY finds 92 instances of redundant traversal bugs, including 72 that have never been previously reported, with just 5 false positives. To evaluate the performance impact of these bugs, we manually repair these programs and find that for an input size of 50,000, all repaired programs are at least 2.45 faster than their original code.

The Max-Cut problem consists of partitioning the nodes of an undirected weighted graph into two subsets, such that the sum of the weights of the edges that connect two vertices in different partitions is maximized. It has applications in several fields like statistical physics, VLSI design, among others, and is known to be NP-Hard. We propose a Neighborhood generation method that balances diversity and quality of the obtained solutions. Consequently, the inclusion within Simulated Annealing and Tabu Search frameworks produces similar results to those reported by state-of-the-art methods such as VNSPR and Scatter Search, and in some cases improves them.