Tuesday, October 31, 2006

Paper: "Securing Software by Enforcing Data-flow Integrity"

Securing Software by Enforcing Data-flow Integrity
Miguel Castro, Microsoft Research; Manuel Costa, Microsoft Research Cambridge; Tim Harris, Microsoft Research


Software attacks often subvert the intended data-flow in a vulnerable program. For example, attackers exploit buffer overflows and format string vulnerabilities to write data to unintended locations. We present a simple technique that prevents these attacks by enforcing data-flow integrity. It computes a data-flow graph using static analysis, and it instruments the program to ensure that the flow of data at runtime is allowed by the data-flow graph. We describe an efficient implementation of data-flow integrity enforcement that uses static analysis to reduce instrumentation overhead. This implementation can be used in practice to detect a broad class of attacks and errors because it can be applied automatically to C and C++ programs without modifications, it does not have false positives, and it has low overhead.


Blogger Geoffrey Lefebvre said...

Securing Software by Enforcing Data-flow Integrity

Miguel Castro, Microsoft Research; Manuel Costa, Microsoft Research Cambridge; Tim Harris, Microsoft Research

Presented by Manual Costa

Manual Costa began is presentation by noting that most of the software in use today is written in C++. This body of software has a large amount of defects and there exists many ways to exploit these defects such as corrupting control data. He presented some of the various approaches to securing software. He noted that removing or avoiding all defects is hard and that although it is possible to prevent attacks based on control-data exploits, certain attacks can succeed without compromising control-flow. Approaches based on tainting can prevent non control-data exploits but they may have false positive and have a high overhead.

To address these issues, the authors present a new approach to secure software based on enforcing Data-Flow Integrity (DFI). Their approach uses reaching definition analysis to compute a data-flow graph at compile time. For every load, compute the set of stores that may produce the loaded data. An ID is assigned to every store operation and for each load, the set of allowed IDs is computed. The results of the analysis is used to add run-time checks that will enforce data-flow integrity. Stores are instrumented to write their ID into the runtime definition table (RDT). The RDT keeps track of the last store to write to each memory location. Loads are instrumented to check if the store in the RDT is in their set of allowed writes. If a store ID is not in the set during a check, a exception is raised. Because the analysis is conservative, an exception guarantees the presence of an error. There are no false positive. Manual also noted that control-flow attacks are a form of data-flow attacks. It is possible to use the same mechanism to protect control-flow data.

Manual described a set of optimizations to improve the runtime performance. The most important optimization is to rename store IDs so that they appear as a continuous range in the definition set. The membership test can be replaced with a subtraction and a compare. The evaluation presented demonstrates that this optimization is fundamental to the performance of DFI. The space overhead is around 50% and the runtime overhead ranges from 44% to 103%.

Brad Karp from College University London asked if DFI handles function pointers and other complex program constructs. Manual answered that DFI handles function pointers but has problems with certain pieces of software written in assembly. These problems can result in not detecting certain DFI violation. An alternative would be to use CFI in this case. It is important to understand that these limitations are a property of the program to instrument, not the attack. Douglas Terry from Microsoft Research asked if every store had to be instrumented. Manual acknowledged.

9:50 PM  

Post a Comment

<< Home