agroce/cs569sp15
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
This is our class repo. This file is our syllabus. Topic: Static Analysis and Model Checking (mainly CBMC) CBMC can be found at www.cprover.org/cbmc Tasks: - Present 1 research paper on static analysis or model checking in class (25%) - Assignment to verify/find bug in real code using CBMC - Project -- either survey of an important static analysis/model checking topic, a small research project, or a more ambitious verification with CBMC ASSIGNMENT 1 DETAILS: -- Install and make sure you can run the latest CBMC. -- Find a (small, for your sake) C program (or function) online that implements something easy to explain and specify. You can write one. The code should be at least 50LOC and non-trivial (e.g., you can't prove a swap function correct) -- at least one loop, preferably. -- Write a harness that would be used to look for bugs in this code. -- If the code is correct, introduce some bugs in the code, preferably subtle ones that might easily escape a decent test suite. Check this -- does your harness find these bugs? -- Write up your results: was the program correct or buggy? What was hard to specify? Was there functionality you could not specify? How long did it take to verify with different loop bounds? How did turning on/off bounds and pointer checker affect cbmc runtime? Discuss the ability of the harness to find the bugs you introduced, and how to address the problem if it did not, including (if possible) a revised harness to find them. Minimum of 400 words. DUE DATE: April 21, 2015 (before class) Submission instructions: -- add a subdir projects/<youronidid>/assign1 and put everything in that directory RESEARCH PRESENTATION DETAILS: - send me an email with topic "569 PRESENTATION" and suggest a topic, and grab a possible presentation date - presentations will be 15-20 minutes, we'll try to do four per class - aim to start this next Thursday POSSIBLE TOPICS: - Predicate abstraction (using SATABS, or just the basic topic) - Intro paper or presentation: what is predicate abstraction? How is it different from CBMC's SAT-based bounded model checking http://www.cs.ucla.edu/~todd/research/pldi01.pdf SATABS tool: http://www.kroening.com/papers/tacas2005.pdf http://pm.inf.ethz.ch/publications/getpdf.php?bibname=Own&id=Novacek12.pdf BLAST (lazy abstraction) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.5090&rep=rep1&type=pdf Z3 (& SMT tools in general): http://research.microsoft.com/en-us/um/redmond/projects/z3/z3.pdf Concurrency: http://ti.arc.nasa.gov/publications/11593/download/ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.7642&rep=rep1&type=pdf http://www.kroening.com/papers/cav2013-wpo.pdf Uses of CBMC: - Fault localization -- http://www.cs.cmu.edu/~agroce/tacas04.pdf - Using traces to improve speed -- http://www.cs.cmu.edu/~agroce/tacas06.pdf Other topics: - Non-SAT Based/pred abs based model checkers SPIN Model Checker Java Pathfinder Symbolic Pathfinder (JPF + Symbolic Execution) - Symbolic execution tools (KLEE) (how is it different from model checking) Model checking for particular goals: - probabilistic model checking - model checking Android - model checking for security properties Other stuff -- model checking + dynamic analysis SCHEDULE file in github will contain taken papers + dates send me a paper topic by next Wed. morning
About
569 Class repo
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published