SafeDS: Safe Data Structures for C++

Memory corruption vulnerabilities in low-level languages such as C/C++ have been a problem in computer security for a long time. Accordingly, there has been a wide variety of proposed solutions for detecting or preventing memory corruption attacks. Due to the constantly evolving nature of such attacks and the importance of achieving high performance in most applications, no comprehensive solution has yet been developed to efficiently secure all data in the program memory and mitigate such attacks. Nevertheless, solutions that only protect critical data in memory provide a balance between security and efficiency that could be practical in many applications. Accordingly, we introduce SafeDS, an extension to the C++ standard library containers that provides secure design and implementation for three frequently-used data structures. We assume a powerful adversary with arbitrary read/write access to the memory but unable to access and modify reserved registers. Data integrity is ensured by SafeDS within the data structures in the presence of such adversary through calculating a Message Authentication Code (MAC) for each element, which can then be used to validate data when reading from the data structure. Our secure data structures are implemented as a part of the gcc-11.1.0 C++ Standard Library and are compatible with both ARM and x86 architectures. We use the Pointer Authentication (PA) hardware extension on ARM-v8 and Intel AES-NI instruction set to calculate MACs on ARM and x86 architectures, respectively. By testing our prototype against applications that use the data structure APIs in the C++ standard library, such as OpenCV, we show that switching to the secure version of data structures requires minimal changes to the applications’ original source code. Our secure data structures use a Merkle tree to securely store one MAC for each instance of them in the program. Therefore, we can theoretically estimate that an overhead of order O(log(i)) will be added to the data structure operations, where i is the number of data structure instances in the program. However, since the design for the secure data structures ties the MAC calculation and verification to the normal steps of the operations, the rest of the MAC related operations only add a constant overhead. The performance of our prototype has been evaluated using the provided performance tests in OpenCV, and our results show that the secure data structures introduce an overall overhead of 3.4% compared to the baseline. Furthermore, we present game-based proofs to prove the security of our designed data structures against data corruption attacks