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

Abstraction
----------------------------------

This projects will enhance the ‘Baggy Bounds with Accurate Checking’ [1] work. I
will provide more efficient runtime checks in BBAC framework by adding more
informations to the memory object’s padding area. A new padding area scheme will
be designed to make these informations compact and efficient to fetch. I will
create some new runtime checks on these additional informations.

Project Background
----------------------------------

Baggy [2] is a compiler-time transform and runtime hardening solution that
detects out-of-bounds pointer arithmetic errors. The memory allocation in Baggy
are wrapped with a allocator 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. Baggy stores
its memory objects layout in a contiguous array. With the memory object’s
location and size informations, Beggy can do a simple check to determine if a
pointer q computed from pointer p stays within the same allocation size.

Baggy Bounds with Accurate Checking (BBAC) inherits the memory layout from
Baggy. 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.

Overview
----------------------------------

Inspired by Beggy 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. Concretely speaking, first, I will focus on the kinds of errors we will
check. Second, I need to come up with addtional data needed to be stored. Third,
this work needs a well-designed meta-data encoding to ensure the additional data
to be compact in size and efficient in lookup. Thus I will design a padding area
encoding scheme. And a runtime hardening support is needed to guarantee the
safety of program execution. Finally I will adopt some benchmarks, to evaluate
the performance of this scheme.

For example, to implement accurate dangling pointer error checks, we can add
points-to sets to the padding area. This enhancement will make it possible to
find the dangling pointer stored in heap. With the help of runtime check on
memory objects, we can easily locate the pointers which points to the
deallocated memory.

For another example, to ensure thread safety at runtime, we can add guarded_by
relations to the memory object’s padding area. With the help of constant time
runtime check, this enhancement will efficiently gurantee that all the
operations to a memory are provided by a particular mutex lock.

Criteria of Success
----------------------------------
I will mainly focus on the points-to enhanment of BBAC, so the criteria of
success is :

1. Expand padding area to store some additional informations (at least points-to
sets).
2. A encoding scheme to keep these informations in a limited memory space.
3. Runtime support to check the memory object related bugs (at least pointer
dangling in heaps).
4. Benchmarks on the generated executables.

Timeline
----------------------------------
Before GSoC’16 Official Startup
+ Port SAFECode to latest LLVM release (LLVM 3.8.0).
+ Get familiar with SAFECode compiler.
+ Design the new checks and list the informations needed by these checks.
+ Read more publications on runtime memory hardening.
Week 1
+ Design the encoding scheme of padding area.
Week 2 - 4
+ Build the pass infrastructure on SAFECode to automatically generate hardening
instructions.
+ Implement new memory operating functions, to support embedding the additional
informations to the padding area.
Week 5 - 6
+ Implement points-to related checks (mainly pointer dangling check).
Week 7 - 8
+ Implement the other checks. This will be discussed with John Criswell.
Week 9 - 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
Telecomunications working in the area of static program analysis. My CV can be
found in [2]. 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
contribute to 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
Mobilie: (+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.
[2] http://zhengyangl.com/cv.pdf


The latest update of this proposal can be found in the following link. Please
let me know your comments on this proposal as a GSoC project. Any comments on
how to refine this proposal are welcome. I will be very grateful if someone puts
me in the right direction for the project.

https://docs.google.com/document/d/1SNmdULUqN52zDhM1Odw93DW_vX-2WlL0VgceNWaMLP0/edit?usp=sharing


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160324/33af849d/attachment.html>

> I am Zhengyang, a M.S. candidate at Beijing University of Posts and
Telecomunications working in the area of static program analysis. My CV can be
found in [2]. 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
contribute to this summer with LLVM.
You sound super cool :)

I'm curious, what kind of static analysis stuff are you into?

Also: Can you give examples of the kinds of bugs you're looking for? I'd
like to make sure were not duplicating effort.

sent from my (stupid) windows phone

-----Original Message-----
From: "Zhengyang Liu via llvm-dev" <llvm-dev at lists.llvm.org>
Sent: ‎3/‎24/‎2016 10:47 AM
To: "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org>
Subject: [llvm-dev] [GSoC'16] Proposal for Enhance SAFECode’s Baggy Bounds
Checking

Abstraction

----------------------------------


This projects will enhance the ‘Baggy Bounds with Accurate Checking’ [1] work. I
will provide more efficient runtime checks in BBAC framework by adding more
informations to the memory object’s padding area. A new padding area scheme will
be designed to make these informations compact and efficient to fetch. I will
create some new runtime checks on these additional informations.


Project Background
----------------------------------



Baggy [2] is a compiler-time transform and runtime hardening solution that
detects out-of-bounds pointer arithmetic errors. The memory allocation in Baggy
are wrapped with a allocator 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. Baggy stores
its memory objects layout in a contiguous array. With the memory object’s
location and size informations, Beggy can do a simple check to determine if a
pointer q computed from pointer p stays within the same allocation size.


Baggy Bounds with Accurate Checking (BBAC) inherits the memory layout from
Baggy. 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.


Overview
----------------------------------



Inspired by Beggy 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. Concretely speaking, first, I will focus on the kinds of errors we will
check. Second, I need to come up with addtional data needed to be stored. Third,
this work needs a well-designed meta-data encoding to ensure the additional data
to be compact in size and efficient in lookup. Thus I will design a padding area
encoding scheme. And a runtime hardening support is needed to guarantee the
safety of program execution. Finally I will adopt some benchmarks, to evaluate
the performance of this scheme.


For example, to implement accurate dangling pointer error checks, we can add
points-to sets to the padding area. This enhancement will make it possible to
find the dangling pointer stored in heap. With the help of runtime check on
memory objects, we can easily locate the pointers which points to the
deallocated memory.


For another example, to ensure thread safety at runtime, we can add guarded_by
relations to the memory object’s padding area. With the help of constant time
runtime check, this enhancement will efficiently gurantee that all the
operations to a memory are provided by a particular mutex lock.


Criteria of Success
----------------------------------

I will mainly focus on the points-to enhanment of BBAC, so the criteria of
success is :


1. Expand padding area to store some additional informations (at least points-to
sets).
2. A encoding scheme to keep these informations in a limited memory space.
3. Runtime support to check the memory object related bugs (at least pointer
dangling in heaps).
4. Benchmarks on the generated executables.


Timeline 
----------------------------------

Before GSoC’16 Official Startup 
+ Port SAFECode to latest LLVM release (LLVM 3.8.0).
+ Get familiar with SAFECode compiler.
+ Design the new checks and list the informations needed by these checks.
+ Read more publications on runtime memory hardening.
Week 1
+ Design the encoding scheme of padding area.
Week 2 - 4
+ Build the pass infrastructure on SAFECode to automatically generate hardening
instructions.
+ Implement new memory operating functions, to support embedding the additional
informations to the padding area.
Week 5 - 6
+ Implement points-to related checks (mainly pointer dangling check).
Week 7 - 8
+ Implement the other checks. This will be discussed with John Criswell.
Week 9 - 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
Telecomunications working in the area of static program analysis. My CV can be
found in [2]. 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
contribute to 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
Mobilie: (+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.
[2] http://zhengyangl.com/cv.pdf




The latest update of this proposal can be found in the following link. Please
let me know your comments on this proposal as a GSoC project. Any comments on
how to refine this proposal are welcome. I will be very grateful if someone puts
me in the right direction for the project.


https://docs.google.com/document/d/1SNmdULUqN52zDhM1Odw93DW_vX-2WlL0VgceNWaMLP0/edit?usp=sharing
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160324/fd992733/attachment.html>

On 3/24/16 10:46 AM, Zhengyang Liu via llvm-dev wrote:
> Abstraction
> ----------------------------------
>
> This projects will enhance the ‘Baggy Bounds with Accurate Checking’ 
> [1] work. I will provide more efficient runtime checks in BBAC 
> framework by adding more informations to the memory object’s padding 
> area. A new padding area scheme will be designed to make these 
> informations compact and efficient to fetch. I will create some new 
> runtime checks on these additional informations.
>
> Project Background
> ----------------------------------
>
> Baggy [2] is a compiler-time transform and runtime hardening solution 
> that detects out-of-bounds pointer arithmetic errors. The memory 
> allocation in Baggy are wrapped with a allocator 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. Baggy stores its memory 
> objects layout in a contiguous array. With the memory object’s 
> location and size informations, Beggy can do a simple check to 
> determine if a pointer q computed from pointer p stays within the same 
> allocation size.
>
> Baggy Bounds with Accurate Checking (BBAC) inherits the memory layout 
> from Baggy. 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.
>
> Overview
> ----------------------------------
>
> Inspired by Beggy
It should be "Baggy" and not "Beggy."  Also, I prefer
"BBC" over
"Baggy," but that is just my personal preference.
> 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. Concretely speaking, first, I will focus on the kinds of 
> errors we will check. Second, I need to come up with addtional data 
> needed to be stored. Third, this work needs a well-designed meta-data 
> encoding to ensure the additional data to be compact in size and 
> efficient in lookup. Thus I will design a padding area encoding 
> scheme. And a runtime hardening support is needed to guarantee the 
> safety of program execution. Finally I will adopt some benchmarks, to 
> evaluate the performance of this scheme.
First, you should clearly state that a prototype version of BBAC is 
already implemented in the SAFECode compiler, and you should explain 
which types of run-time checks it already performs.

You should also clearly state which types of errors you plan to detect 
within the GSoC time frame.  For example, if you are going to implement 
explicit checks for dangling pointers, you should describe exactly how 
you plan to implement those checks (e.g., what metadata is required, 
when that metadata will be created and updated, and how run-time checks 
will use it).  Cite sources as needed.
>
> For example, to implement accurate dangling pointer error checks, we 
> can add points-to sets to the padding area. This enhancement will make 
> it possible to find the dangling pointer stored in heap. With the help 
> of runtime check on memory objects, we can easily locate the pointers 
> which points to the deallocated memory.
Storing points-to set information in the metadata will allow you to 
detect casting errors and some dangling pointer errors, but it will not 
catch all.  If you have a dangling pointer to one memory object and it 
points to another memory object in the same set due to a dangling 
pointer error, your approach will not detect the error.
>
> For another example, to ensure thread safety at runtime, we can add 
> guarded_by relations to the memory object’s padding area.
You should not assume that the reader knows what "guarded_by" means.  
You should briefly describe it and cite a source (preferably a 
peer-reviewed paper if possible).

Please keep in mind that your proposal will be reviewed by people other 
than the potential mentor (in other words, I won't be the only person 
reviewing your proposal).  You should make sure that your proposal is 
comprehensible to them.
> With the help of constant time runtime check, this enhancement will 
> efficiently gurantee that all the operations to a memory are provided 
> by a particular mutex lock.
>
> Criteria of Success
> ----------------------------------
> I will mainly focus on the points-to enhanment of BBAC, so the 
> criteria of success is :
>
> 1. Expand padding area to store some additional informations (at least 
> points-to sets).
This already exists.
> 2. A encoding scheme to keep these informations in a limited memory space.
You can add as much padding as you want, so it's not clear to me why 
this is needed.
> 3. Runtime support to check the memory object related bugs (at least 
> pointer dangling in heaps).
> 4. Benchmarks on the generated executables.
Which benchmarks do you plan to use?
>
> Timeline
> ----------------------------------
> Before GSoC’16 Official Startup
> + Port SAFECode to latest LLVM release (LLVM 3.8.0).
This should really be done as part of GSoC.
> + Get familiar with SAFECode compiler.
> + Design the new checks and list the informations needed by these checks.
> + Read more publications on runtime memory hardening.
> Week 1
> + Design the encoding scheme of padding area.
Your proposal should, ideally, provide a rough sketch of the design so 
that it isn't being worked on during GSoC.
> Week 2 - 4
> + Build the pass infrastructure on SAFECode to automatically generate 
> hardening instructions.
> + Implement new memory operating functions, to support embedding the 
> additional informations to the padding area.
> Week 5 - 6
> + Implement points-to related checks (mainly pointer dangling check).
Which points-to analysis will you be using?
> Week 7 - 8
> + Implement the other checks. This will be discussed with John Criswell.
> Week 9 - 11
> + Adopt benchmarks on the generated executables. Evaluate the performance.
> + After GSoC’16
> Work out a research paper on this work.
Making this into a research paper would be great!
>
> About Me
> ----------------------------------
> I am Zhengyang, a M.S. candidate at Beijing University of Posts and 
> Telecomunications working in the area of static program analysis. My 
> CV can be found in [2]. 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 contribute to 
> this summer with LLVM.
I recommend attaching a full-fledged CV or resume with your proposal 
instead of providing a link (though a link will do if there is no other 
way to attach a CV/resume).  You want to give the reviewers as little 
work to do as possible when reviewing your application.

Regards,

John Criswell
>
> 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
> Mobilie: (+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.
> [2] http://zhengyangl.com/cv.pdf
>
>
> The latest update of this proposal can be found in the following link. 
> Please let me know your comments on this proposal as a GSoC project. 
> Any comments on how to refine this proposal are welcome. I will be 
> very grateful if someone puts me in the right direction for the project.
>
>
https://docs.google.com/document/d/1SNmdULUqN52zDhM1Odw93DW_vX-2WlL0VgceNWaMLP0/edit?usp=sharing
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

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