[llvm-dev] [GSoC] Final Proposal 'Enhance SAFECode’s Baggy Bounds Checking'

[Zhengyang Liu via llvm-dev]

First of all, I am really sorry about my time scheduling. I did not manage to upload my proposal at the last minutes before Google Summer of Code submission deadline. Could you kindly take the following revision as my final proposal?


Abstraction
---------------------
This projects will enhance the ‘Baggy Bounds with Accurate Checking’ (BBAC) [1] work. By adding information to the memory object’s padding area, we can perform various safety checks with limited overhead. I will mainly focus on providing runtime policy hardening. This work will prevent most of illegal memory accesses efficiently.
Project Background

Baggy Bounds Checking(BBC) [2] is a compiler-time transform and runtime hardening solution that detects out-of-bounds pointer arithmetic errors. The memory allocation in BBC are wrapped with allocators that aligns all memory objects on a power-of-two address space and pads the size of the memory object to be an equivalent power-of-two. In this way the layout of memory can be encoded compactly, and the meta-data about the memory object can be fetched in constant time. BBC stores its memory objects layout in a contiguous array. With the memory object’s location and size information, BBC can do a simple check to determine if a pointer q computed from pointer p stays within the same allocation size.

BBAC inherits the memory layout from BBC. It stores precise object size at the end of the padding data, making it accurate and efficient to lookup object bounds meta-data at runtime. BBAC is already implemented in SAFECode. With help of array bound meta-data, BBAC archives runtime array bound check efficiently.

Overview
---------------------
Inspired by BBC and BBAC, I realize that there is still a lot we can do on BBAC. We can use padding area of a memory object to prevent various memory errors. Concrete speaking:
1.Focus on adding the policy meta-data storing support to origin BBAC.
2.Design a efficient algorithm which will check the ownership of memory object at runtime before the access to that object.
3.Create a new load/store operator, which implements the runtime object access check algorithm.
4.Points-to analysis is needed to calculate the pointer information to the memory object.
5.Implement a compiler pass. This pass will automatically redirect the memory access operations to the load/store operator.
6.Adopt some benchmarks to evaluate the performance of generated executions.

Design Overview of the Policy Meta-data Check Algorithm
---------------------
1. Data Structure
The new policy meta-data is a hash table storing at the padding area of memory object. The element key-value pair follows the form of <owner-identifier, permission>.  The owner-identifier is the unique identifier of the pointer pointed to the memory object.  The permission is a read/write bit-vector inspired by the permission code of Unix file system. Suppose the lower bit is read, the higher bit is write. 01 means the pointer has the read permission and cannot write to that object.
2. Algorithm
When a memory object is access by a pointer, an efficient algorithm will look up the policy meta-data and get the correspondent permission code. If the permission check is not passed, it instantly throws out a errno and terminate the program.

Criteria of Success
---------------------
I will mainly focus on the policy hardening enhancement of BBAC, the criteria of success is:
1. An efficient algorithm to efficiently check the permission of the memory object before load/store operations.
2. Runtime support to check illegal memory access bugs.
3. Benchmarks on the generated executables. (the benchmarks will be designed).

Timeline
---------------------
Before GSoC’16 Official Startup
+ Port SAFECode to latest LLVM release (LLVM 3.8.0).
+ Get familiar with SAFECode compiler.
+ Read more publications on runtime memory hardening.
Week 1 - 2
+ Add the policy hash map to original BBAC.
Week 3 – 5
+ Implement points-to analysis .
Week 6 - 7
+ Implement new memory operating algorithm, to support run-time access hardening.
Week 8 - 9
+ Implement compiler pass, to redirect memory operations to our new algorithm.
Week 10 - 11
+ Adopt benchmarks on the generated executables. Evaluate the performance.
After GSoC’16
+ Work out a research paper on this work.

About Me
---------------------
I am Zhengyang, a M.S. candidate at Beijing University of Posts and Telecommunications working in the area of static program analysis. Most of my works are based on Clang Static Analyzer.  I have contributed to Static Analysis Suite (SAS) from CERN PH-SFT as Google Summer of Code 2015 project. About the preparation for this proposal, I have studied several research papers of compiler time transform and runtime program hardening techniques. I am interested in working with LLVM community, and hoping to spend this summer with LLVM.

Contact
---------------------
Zhengyang Liu,
Networking Security Research Center,
State Key Labs of Networking and Switching Technology,
Beijing University of Posts and Telecommunications, Beijing, China.

Email: zhengyang-liu at hotmail.com
Mobile: (+86) 185-1911-7347

Reference
---------------------
[1] Ding, Baozeng, et al. "Baggy bounds with accurate checking." Software Reliability Engineering Workshops (ISSREW), 2012 IEEE 23rd International Symposium on. IEEE, 2012.
[2] Akritidis, Periklis, et al. "Baggy Bounds Checking: An Efficient and Backwards-Compatible Defense against Out-of-Bounds Errors." USENIX Security Symposium. 2009.

Best Regards,
Zhengyang.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160325/5ef608c7/attachment.html>