78. An exact approach for minimizing permission-switching overhead in control-flow graphs
Invited abstract in session TD-1: Data structures, stream Data structures.
Thursday, 14:30 - 16:00Room: L226
Authors (first author is the speaker)
| 1. | Jeroen Gardeyn
|
| Computer Science, KU Leuven | |
| 2. | Adriaan Jacobs
|
| Computer Science, KU Leuven |
Abstract
Memory Protection Key (MPK) is a popular mechanism to improve software security by granting or revoking access to sensitive memory regions at runtime.
This access can be controlled and checked with specialized CPU instructions.
The flow of execution between different blocks of code in a program function is described a control-flow graph (CFG).
When leveraging MPK, certain blocks of the CFG require either strict granted or revoked access to a sensitive memory region.
Other blocks are unconstrained, meaning the access permission can be in any state.
The compiler has to insert these (expensive) MPK-instructions in between the normal program code in such a way to satisfy the security requirements while minimizing the overhead incurred by the additional instructions.
This is not a trivial task since the number of feasible configurations scales exponentially with the number of unconstrained blocks, and the exact placement significantly impacts the performance overhead.
In this talk, we present an abstract model of the problem, using an analogy which should be easy to follow for people unfamiliar with computer security research.
We introduce a branch and bound algorithm in combination with decomposition and symmetry-breaking techniques.
Our current implementation is able to reach an optimal solution for every function across a broad range of large open-source C/C++ software projects, typically within a couple milliseconds.
Keywords
- Graph theory and networks
Status: accepted
Back to the list of papers