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

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>